logo标签列表

寻找距离某个邮编最近的5个地点 - 我应该选择哪种方式？

mysqlsqlstored-proceduresinnodb
6

我想要的：

  1. 用户输入邮政编码或城市名称
  2. 我在数据库中搜索5个最接近的位置
  3. 向用户显示该位置附近的5个最近位置

到目前为止我所拥有的：

假设有一个包含以下内容的地点表：

(大约有16000行)

CREATE TABLE `locations` (
 `locationID` int(11) NOT NULL AUTO_INCREMENT,
 `name` varchar(150) NOT NULL,
 `firstname` varchar(100) DEFAULT NULL,
 `lastname` varchar(100) DEFAULT NULL,
 `street` varchar(100) NOT NULL,
 `city` varchar(100) NOT NULL,
 `state` varchar(100) NOT NULL,
 `zipcode` varchar(10) NOT NULL,
 `phone` varchar(20) NOT NULL,
 `web` varchar(255) DEFAULT NULL,
 `machine` enum('Unbekannt','Foo','Bar') DEFAULT 'Unbekannt',
 `surface` enum('Unbekannt','Foo','Bar','') DEFAULT 'Unbekannt',
 PRIMARY KEY (`locationID`)
) ENGINE=InnoDB AUTO_INCREMENT=25 DEFAULT CHARSET=utf8
  1. ID（编号）
  2. name（名称）
  3. zip code（邮政编码）
  4. city（城市）

现在我有了第二个包含全球所有城镇的表格：

（大约340万行）

CREATE TABLE `geoData` (
 `geoID` int(11) NOT NULL AUTO_INCREMENT,
 `countryCode` char(2) NOT NULL,
 `zipCode` varchar(20) NOT NULL,
 `name` varchar(180) NOT NULL,
 `state` varchar(100) NOT NULL,
 `stateCode` varchar(20) NOT NULL,
 `county` varchar(100) NOT NULL,
 `countyCode` varchar(20) NOT NULL,
 `community` varchar(100) NOT NULL,
 `communityCode` varchar(20) NOT NULL,
 `lat` mediumint(6) NOT NULL,
 `lon` mediumint(6) NOT NULL,
 PRIMARY KEY (`lon`,`lat`,`geoID`) USING BTREE,
 KEY `geoID` (`geoID`)
) ENGINE=InnoDB AUTO_INCREMENT=16482 DEFAULT CHARSET=utf8
/*!50100 PARTITION BY RANGE (lat)
(PARTITION p0 VALUES LESS THAN (-880000) ENGINE = InnoDB,
PARTITION p1 VALUES LESS THAN (-860000) ENGINE = InnoDB,
PARTITION p2 VALUES LESS THAN (-840000) ENGINE = InnoDB,
PARTITION p3 VALUES LESS THAN (-820000) ENGINE = InnoDB,
PARTITION p4 VALUES LESS THAN (-800000) ENGINE = InnoDB,
PARTITION p5 VALUES LESS THAN (-780000) ENGINE = InnoDB,
PARTITION p6 VALUES LESS THAN (-760000) ENGINE = InnoDB,
PARTITION p7 VALUES LESS THAN (-740000) ENGINE = InnoDB,
PARTITION p8 VALUES LESS THAN (-720000) ENGINE = InnoDB,
PARTITION p9 VALUES LESS THAN (-700000) ENGINE = InnoDB,
PARTITION p10 VALUES LESS THAN (-680000) ENGINE = InnoDB,
PARTITION p11 VALUES LESS THAN (-660000) ENGINE = InnoDB,
PARTITION p12 VALUES LESS THAN (-640000) ENGINE = InnoDB,
PARTITION p13 VALUES LESS THAN (-620000) ENGINE = InnoDB,
PARTITION p14 VALUES LESS THAN (-600000) ENGINE = InnoDB,
PARTITION p15 VALUES LESS THAN (-580000) ENGINE = InnoDB,
PARTITION p16 VALUES LESS THAN (-560000) ENGINE = InnoDB,
PARTITION p17 VALUES LESS THAN (-540000) ENGINE = InnoDB,
PARTITION p18 VALUES LESS THAN (-520000) ENGINE = InnoDB,
PARTITION p19 VALUES LESS THAN (-500000) ENGINE = InnoDB,
PARTITION p20 VALUES LESS THAN (-480000) ENGINE = InnoDB,
PARTITION p21 VALUES LESS THAN (-460000) ENGINE = InnoDB,
PARTITION p22 VALUES LESS THAN (-440000) ENGINE = InnoDB,
PARTITION p23 VALUES LESS THAN (-420000) ENGINE = InnoDB,
PARTITION p24 VALUES LESS THAN (-400000) ENGINE = InnoDB,
PARTITION p25 VALUES LESS THAN (-380000) ENGINE = InnoDB,
PARTITION p26 VALUES LESS THAN (-360000) ENGINE = InnoDB,
PARTITION p27 VALUES LESS THAN (-340000) ENGINE = InnoDB,
PARTITION p28 VALUES LESS THAN (-320000) ENGINE = InnoDB,
PARTITION p29 VALUES LESS THAN (-300000) ENGINE = InnoDB,
PARTITION p30 VALUES LESS THAN (-280000) ENGINE = InnoDB,
PARTITION p31 VALUES LESS THAN (-260000) ENGINE = InnoDB,
PARTITION p32 VALUES LESS THAN (-240000) ENGINE = InnoDB,
PARTITION p33 VALUES LESS THAN (-220000) ENGINE = InnoDB,
PARTITION p34 VALUES LESS THAN (-200000) ENGINE = InnoDB,
PARTITION p35 VALUES LESS THAN (-180000) ENGINE = InnoDB,
PARTITION p36 VALUES LESS THAN (-160000) ENGINE = InnoDB,
PARTITION p37 VALUES LESS THAN (-140000) ENGINE = InnoDB,
PARTITION p38 VALUES LESS THAN (-120000) ENGINE = InnoDB,
PARTITION p39 VALUES LESS THAN (-100000) ENGINE = InnoDB,
PARTITION p40 VALUES LESS THAN (-80000) ENGINE = InnoDB,
PARTITION p41 VALUES LESS THAN (-60000) ENGINE = InnoDB,
PARTITION p42 VALUES LESS THAN (-40000) ENGINE = InnoDB,
PARTITION p43 VALUES LESS THAN (-20000) ENGINE = InnoDB,
PARTITION p44 VALUES LESS THAN (0) ENGINE = InnoDB,
PARTITION p45 VALUES LESS THAN (20000) ENGINE = InnoDB,
PARTITION p46 VALUES LESS THAN (40000) ENGINE = InnoDB,
PARTITION p47 VALUES LESS THAN (60000) ENGINE = InnoDB,
PARTITION p48 VALUES LESS THAN (80000) ENGINE = InnoDB,
PARTITION p49 VALUES LESS THAN (100000) ENGINE = InnoDB,
PARTITION p50 VALUES LESS THAN (120000) ENGINE = InnoDB,
PARTITION p51 VALUES LESS THAN (140000) ENGINE = InnoDB,
PARTITION p52 VALUES LESS THAN (160000) ENGINE = InnoDB,
PARTITION p53 VALUES LESS THAN (180000) ENGINE = InnoDB,
PARTITION p54 VALUES LESS THAN (200000) ENGINE = InnoDB,
PARTITION p55 VALUES LESS THAN (220000) ENGINE = InnoDB,
PARTITION p56 VALUES LESS THAN (240000) ENGINE = InnoDB,
PARTITION p57 VALUES LESS THAN (260000) ENGINE = InnoDB,
PARTITION p58 VALUES LESS THAN (280000) ENGINE = InnoDB,
PARTITION p59 VALUES LESS THAN (300000) ENGINE = InnoDB,
PARTITION p60 VALUES LESS THAN (320000) ENGINE = InnoDB,
PARTITION p61 VALUES LESS THAN (340000) ENGINE = InnoDB,
PARTITION p62 VALUES LESS THAN (360000) ENGINE = InnoDB,
PARTITION p63 VALUES LESS THAN (380000) ENGINE = InnoDB,
PARTITION p64 VALUES LESS THAN (400000) ENGINE = InnoDB,
PARTITION p65 VALUES LESS THAN (420000) ENGINE = InnoDB,
PARTITION p66 VALUES LESS THAN (440000) ENGINE = InnoDB,
PARTITION p67 VALUES LESS THAN (460000) ENGINE = InnoDB,
PARTITION p68 VALUES LESS THAN (480000) ENGINE = InnoDB,
PARTITION p69 VALUES LESS THAN (500000) ENGINE = InnoDB,
PARTITION p70 VALUES LESS THAN (520000) ENGINE = InnoDB,
PARTITION p71 VALUES LESS THAN (540000) ENGINE = InnoDB,
PARTITION p72 VALUES LESS THAN (560000) ENGINE = InnoDB,
PARTITION p73 VALUES LESS THAN (580000) ENGINE = InnoDB,
PARTITION p74 VALUES LESS THAN (600000) ENGINE = InnoDB,
PARTITION p75 VALUES LESS THAN (620000) ENGINE = InnoDB,
PARTITION p76 VALUES LESS THAN (640000) ENGINE = InnoDB,
PARTITION p77 VALUES LESS THAN (660000) ENGINE = InnoDB,
PARTITION p78 VALUES LESS THAN (680000) ENGINE = InnoDB,
PARTITION p79 VALUES LESS THAN (700000) ENGINE = InnoDB,
PARTITION p80 VALUES LESS THAN (720000) ENGINE = InnoDB,
PARTITION p81 VALUES LESS THAN (740000) ENGINE = InnoDB,
PARTITION p82 VALUES LESS THAN (760000) ENGINE = InnoDB,
PARTITION p83 VALUES LESS THAN (780000) ENGINE = InnoDB,
PARTITION p84 VALUES LESS THAN (800000) ENGINE = InnoDB,
PARTITION p85 VALUES LESS THAN (820000) ENGINE = InnoDB,
PARTITION p86 VALUES LESS THAN (840000) ENGINE = InnoDB,
PARTITION p87 VALUES LESS THAN (860000) ENGINE = InnoDB,
PARTITION p88 VALUES LESS THAN (880000) ENGINE = InnoDB,
PARTITION p89 VALUES LESS THAN MAXVALUE ENGINE = InnoDB) */
  1. ID（标识符）
  2. 城市
  3. 邮政编码
  4. 纬度
  5. 经度

根据这篇文章和其他相关阅读，我有一个存储过程可以给出距离某个点（纬度/经度）最近的n个城镇或邮政编码。

我的存储过程：

    BEGIN
    DECLARE _deg2rad DOUBLE DEFAULT PI()/1800000;

    SET @my_lat := _my_lat,
        @my_lon := _my_lon,
        @deg2dist := 0.0111325,  
        @start_deg := _start_dist / @deg2dist,  
        @max_deg := _max_dist / @deg2dist,
        @cutoff := @max_deg / SQRT(2),  
        @dlat := @start_deg,  
        @lon2lat := COS(_deg2rad * @my_lat),
        @iterations := 0;        

    SET @sql = CONCAT(
        "SELECT COUNT(*) INTO @near_ct
            FROM geoData
            WHERE lat    BETWEEN @my_lat - @dlat
                             AND @my_lat + @dlat   
              AND lon    BETWEEN @my_lon - @dlon
                             AND @my_lon + @dlon");
    PREPARE _sql FROM @sql;
    MainLoop: LOOP
        SET @iterations := @iterations + 1;
        SET @dlon := ABS(@dlat / @lon2lat);  
        SET @dlon := IF(ABS(@my_lat) + @dlat >= 900000, 3600001, @dlon);  
        EXECUTE _sql;
        IF ( @near_ct >= _limit OR         
             @dlat >= @cutoff ) THEN       
            LEAVE MainLoop;
        END IF;
        SET @dlat := LEAST(2 * @dlat, @cutoff);   
    END LOOP MainLoop;
    DEALLOCATE PREPARE _sql;

    SET @dlat := IF( @dlat >= @max_deg OR @dlon >= 1800000,
                @max_deg,
                GCDist(ABS(@my_lat), @my_lon,
                       ABS(@my_lat) - @dlat, @my_lon - @dlon) );
    SET @dlon := IFNULL(ASIN(SIN(_deg2rad * @dlat) /
                             COS(_deg2rad * @my_lat))
                            / _deg2rad 
                        , 3600001);    


    IF (ABS(@my_lon) + @dlon < 1800000 OR    
        ABS(@my_lat) + @dlat <  900000) THEN 
        SET @sql = CONCAT(
            "SELECT *,
                    @deg2dist * GCDist(@my_lat, @my_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @my_lon - @dlon
                              AND @my_lon + @dlon   
                HAVING dist <= ", _max_dist, "
                ORDER BY dist
                LIMIT ", _limit
                        );
    ELSE
        SET @west_lon := IF(@my_lon < 0, @my_lon, @my_lon - 3600000);
        SET @east_lon := @west_lon + 3600000;
        SET @sql = CONCAT(
            "( SELECT *,
                    @deg2dist * GCDist(@my_lat, @west_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat 
                  AND lon BETWEEN @west_lon - @dlon
                              AND @west_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            UNION ALL
            ( SELECT *,
                    @deg2dist * GCDist(@my_lat, @east_lon, lat, lon) AS dist
                FROM geoData
                WHERE lat BETWEEN @my_lat - @dlat
                              AND @my_lat + @dlat   
                  AND lon BETWEEN @east_lon - @dlon
                              AND @east_lon + @dlon   
                HAVING dist <= ", _max_dist, " )
            ORDER BY dist
            LIMIT ", _limit
                        );
    END IF;

    PREPARE _sql FROM @sql;
    EXECUTE _sql;
    DEALLOCATE PREPARE _sql;
END

我的问题：

我想输入一个邮编或城镇名称并从那里开始搜索。所以我的想法是请求这些信息，然后查找全球所有城镇/邮政编码的表。之后，如果只找到一个结果，我就有了纬度/经度的信息，否则我会要求用户在有多个结果的情况下选择正确的选项。

之后，我开始搜索离我当前位置最近的城镇。假设我想要一个50个城镇/市的列表。然后，我会查找并看看包含位置的表中是否有5个匹配结果。

再想一想，这听起来像是个坏主意...

方法1：

我研究了存储过程、SQL和大型查询，并尝试获得以下内容：

通过传递邮政编码/城市名称，我会查找它，从巨大的表中获取我的纬度/经度（可能作为mysql函数），然后在那里寻找最近的城镇，并立即加入位置表，获取我的5个最接近的位置。

问题：

  • 如何避免同一城市/邮政编码名称的多个匹配？
  • 使用简单的联接可以获取5个最接近的位置吗？

方法2：

获取所有位置的纬度/经度值，然后在此表上运行该过程。只使用巨大的表来检索我的当前位置？

这样，我需要收集所有位置的纬度/经度。但这可能是最好的方法。

但是，仅为了获取位置而拥有所有城市/邮政编码的巨大数据库似乎有点过头了。我希望还有其他替代方案...某种方式...

方法3：

老实说，我想要的这个函数似乎已经写了无数次。那么我为什么要费心重新发明轮子呢？但我不知道如何找到正确的文章或书籍来完成我的目标。

你们中有没有人对这样的最佳实践有任何想法？

如果您正在使用邮政编码，那么我认为这比使用纬度/经度更容易。我不确定您是否在全球范围内或全美国使用此表。但是，如果它在美国境内，您可以使用邮政编码并将其分为3组，第一组代表州，第二组代表城市/县，第三组提供该城市内的确切区域。因此，在您的情况下，前三位数字将是您获取最近5个位置的目标。(我知道邮政编码在全球范围内使用，但我不知道美国以外的标准) - iSR5
您可以考虑使用地理哈希(https://en.wikipedia.org/wiki/Geohash)来代替经纬度表示位置 - 两个地方的地理哈希共同前缀越长，它们就越接近。 - Yuri Lachin
谢谢您指出这个问题 :) - floGalen
@PaulSpiegel 看我的编辑，大约有 340 万行和 16000 行。 - floGalen
术语混淆。 “5个最近的位置”意味着在位置表中找到5行。但我认为你的意思是从一个位置开始，在geoData中找到5行？此外，你提到了一个“用户”;他是否在16K个位置之一;如果是这样，你如何获得他的纬度/经度？或者他是从某个城市（geoData）的中心开始的；此时，位置的目的是什么？ - Rick James
显示剩余5条评论
2个回答
6

首先一些评论...

我在这里和其他论坛上看到过几十个实现；你的比大多数都要好。

根据一个数据源（我碰巧下载了），世界上大约有320万个城市。

为了性能，你需要避免检查所有3M行。你已经从不断增长的边界框入手做得很好。请注意，你应该有：

INDEX(lat, lon),
INDEX(lon, lat)

优化器将在第一个查询（带有COUNT(*)）和那些查询之间进行选择，并将其视为“覆盖”。这将是环绕地球的条纹或楔形;相比于3M行，这是一个明显的改进。最坏的纬度（+34度）有96K个城市。（1度=69英里/111公里）。对于十分之一度，34.4是最糟糕的，有10K个城市。
（是的，我喜欢这种数据难题。）
而且，我发现你可以处理日期线和极点。我认为你无法改善将它们作为特殊情况的做法。
（我只是浏览了公式和常数。）
Geohash和Z-order索引会有所帮助。但是它们有一个小问题，即您需要检查目标周围的4个区域--这就像没有意识到整数199999和200000非常接近，尽管每个数字的第一个数字不同。
"用户输入邮编或城市名称"——这是对两个简单表之一的点查询。(除了可能有重复项——超过320个"san jose"和"san antonio"。在列表中很靠后的第一个非西班牙语名称是"victoria"，只有144个城市。) 其次，我的实现...(它与你的有些相似。)

http://mysql.rjweb.org/doc.php/latlng

这种方法通过使用PARTITIONing将边界框保持在大致正方形而不是条纹或楔形，从而提高了性能。如果您要查找最近的5个，我的算法很少会触及超过几十行，并且这些行将“聚集”在少数块中，从而使磁盘访问次数非常低。
我设计中的关键是将所有必要的列放在一个表中。一旦找到最近的5个，您可以去其他表中获取附属信息（电话号码等）。
至于邮政编码，请在开始搜索最近的5个之前将它们转换为纬度/经度。
算法内部的连接很可能会破坏性能。
我所做的大部分工作都是基于你的文章。特别是存储过程。我删除了条件，并在Stack Overflow上发布问题时添加了评论，以使问题更短。我很喜欢阅读你的文章，这也是进行分区的原因。正如你在文章中提到的那样，我有90个分区，到目前为止，我的SQL性能非常快（约0.03秒）。我的第一个解决方案需要5秒以上才能找到最近的地点。所以，我应该从城市表中请求纬度/经度，并在我的位置表上使用存储过程吗？ - floGalen
我添加了三段文字--一个用于算法的表格; 如果使用 JOIN 很可能需要 5 秒以上的时间。 - Rick James
所以，如果我理解正确：我使用一个表格来查找用户输入（邮编/城市名称）的位置的纬度/经度，然后在我的表格上使用您的方法来获取最近的位置。我唯一需要获取的信息是我的位置的纬度/经度信息。您会有两个表格，一个用于城市，另一个用于位置吗？还是只有一个大表格和一些条件来过滤城市与位置？ - floGalen
啊，所以AI可以被定义为一个“键”（不管那是什么意思）？ - Strawberry
@Strawberry - 有时我使用的一种优化方法是利用主键的聚集：PRIMARY KEY(a,b,id); INDEX(id), ...。注意：我还没有在8.0的分区表中尝试过它。 - Rick James
显示剩余8条评论
2

16000行并不算太多。

我有一个名为cities的表格，其中包含了310万行数据（数据来自https://www.maxmind.com/de/free-world-cities-database）。我创建了一个“虚假”的locations表格，其中包含了16K个不同的随机城市ID和一些虚拟数据。我使用了一个带有POINT数据类型的列代替了latitude和longitude。以下是在MySQL 5.7.18上进行简单查询所得到的结果：

select l.*, c.*, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
from locations l
join cities c using (cityId)
order by dist
limit 5

执行时间约为70毫秒。

使用子查询可以改进执行时间：

select l.*, c.*, x.dist
from (
    select l.locationId, st_distance(point(-0.127758, 51.507351), c.geoPoint) dist
    from locations l
    join cities c using (cityId)
    order by dist
    limit 5
) x
join locations l using(locationId)
join cities c using(cityId)

执行时间：约40毫秒

如果您将geoPoint（冗余）存储在locations表中，就可以避免与cities表的连接。

select l.*, st_distance(point(-0.127758, 51.507351), l.geoPoint) dist
from locations l
order by dist
limit 5

执行时间：约17毫秒

您仍然可以将cities表连接到子查询中，而不会影响性能。

请注意，所有这些查询都将计算所有16K行的距离并对其进行排序。但是性能可能足够满足您的需求。

如果速度还不够快，或者locations表随着时间的推移而增长，或者您想在大表中搜索，则仍然可以使用类似于使用SPATIAL INDEX和MBRWithin()或MBRContains()的过程来处理geoPoint。

算法：

  • 定义用户位置周围的小多边形。
  • 循环增加多边形的大小，直到它包含至少5个位置。
  • 使用多边形内的位置选择5个最近的位置。

请注意，取决于您使用的多边形类型，您可能需要在找到包含5个位置的多边形后再次增加大小。例如-如果您使用正方形（简单实现），则应将大小加倍（将长度增加sqrt(2)倍），以确保不会错过比正方形内第5个位置更接近的位置。这是因为正方形不是圆形。但是，如果您使用八边形，则可以说-这已经足够像圆了-并跳过最后一步。

这可能不是最好的算法。但是它非常容易实现，并且应该足够可扩展。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接