mysql 带有地理位置的大表 - 查找交集

Question

我有一个具有这种结构的大表(> 2000 万行)

[ Id, IdUser (int), Latitude(double), Longitude (double), EventDateTime (datetime) ] 

我需要找到用户在同一区域(500米以内)的所有时刻。

最好的解决方案是什么？

Answer 1

首先，我们不必编写充满超越函数的极其复杂的 SQL 查询，让我们定义一个存储函数 distance(lat1, lon1, lat2, lon2)得到两对点之间的距离。

DELIMITER $$
DROP FUNCTION IF EXISTS distance$$

CREATE FUNCTION distance(
        lat1 FLOAT, lon1 FLOAT,
        lat2 FLOAT, lon2 FLOAT
     ) RETURNS FLOAT
    NO SQL DETERMINISTIC
    COMMENT 'Returns the distance in metres on the Earth
             between two known points of latitude and longitude'
BEGIN
    RETURN 111045 * DEGREES(ACOS(
              COS(RADIANS(lat1)) *
              COS(RADIANS(lat2)) *
              COS(RADIANS(lon2) - RADIANS(lon1)) +
              SIN(RADIANS(lat1)) * SIN(RADIANS(lat2))
            ));
END$$

DELIMITER ;

现在我们需要比较表中的成对项目以查找巧合。假设我们想要时间比较的一分钟分辨率。此查询可以解决问题，但需要一段时间。

 SELECT DISTINCT a.IdUser, b.IdUser, 
                 DATE_FORMAT (a.EventDateTime, '%Y-%m-%d %H:%i:00) AS EventDateTime
   FROM table a
   JOIN table b
          ON a.IdUser < b.IdUser    /* compare different users */
         AND a.EventDateTime >= b.EventDateTime - INTERVAL 1 HOUR
         AND a.EventDateTime <= b.EventDateTime + INTERVAL 1 HOUR
         AND distance(a.Latitude, a.Longitude, b.Latitude, b.Longitude) <= 500.0

这将起作用，给出一对用户的列表以及他们彼此靠近的时间。但速度不会很快。

您将尝试使用索引。可能是 (EventDateTime, IdUser) 上的索引会有帮助的。您可能应该通过添加这样的时间限制来尝试此查询...

   WHERE a.EventDateTime >= CURDATE - INTERVAL 2 DAY
     AND a.EventDateTime <  CURDATE - INTERVAL 1 DAY

这样您就不需要花费数小时来运行查询。

现在，让我们尝试对自连接进行优化，以减少 distance 的使用。函数，并更好地使用索引。为此，我们需要知道(南北)纬度每度大约有 11045m，因此 500m 就是 500/111045 度。

此查询将生成南北相距 500m 以内的观测值对，然后使用 WHERE条款进一步消除仍然相距太远的点。这将减少 distance 的使用功能。

 SELECT a.IdUser, b.IdUser, 
        DATE_FORMAT (a.EventDateTime, '%Y-%m-%d %H:%i:00) AS EventDateTime
   FROM table a
   JOIN table b
             ON a.IdUser < b.IdUser    /* compare different users */
            AND a.EventDateTime >= b.EventDateTime - INTERVAL 1 HOUR
            AND a.EventDateTime <= b.EventDateTime + INTERVAL 1 HOUR
            AND a.Latitude >= b.Latitude - (500.0/111045.0)
            AND a.Latitude <= b.Latitude + (500.0/111045.0)
  WHERE distance(a.Latitude, a.Longitude, b.Latitude, b.Longitude) <= 500.0

值得尝试 (IdUser, EventDateTime, Latitude, Longitude) 上的复合覆盖索引尝试优化此查询。