我想要的:
- 用户传入邮政编码或城市名称
- 我在数据库中搜索 5 个最近的位置 显示该位置
- 附近离用户最近的 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
- 身份证
- 名字
- 邮政编码
- 城市
现在我有第二张桌子,上面有世界上所有的城镇:
(约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) */
- 身份证
- 城市
- 邮政编码
- 纬度
- 经度
基于这篇文章和其他一些关于这个问题的阅读,我有一个存储过程,它给了我一个点(纬度/经度)附近最近城镇的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
我的问题:
我想输入邮政编码或城镇名称,然后从那里开始搜索。所以我的想法是我要求提供这些信息并查找世界上所有城镇/邮政编码的表格。之后,如果只找到一个结果,我就有 lat/lon 的信息,或者我会要求用户在有多个结果的情况下选择正确的选择。
之后,我开始寻找离我目前职位最近的城镇。假设我想要 50 个城镇/城市的列表。有了这个,我会去查找,看看包含位置的表是否与那里的 5 个结果匹配。
转念一想,这听起来是个坏主意......
方法1:
我阅读了存储过程,sql和怪物查询,并尝试获得以下内容:
传入邮政编码/城市名称,我会查找它,从大表中取出我的纬度/纬度(可能作为 mysql 中的函数),有了这个,我会寻找最近的城镇并立即加入位置表并得到我的 5 个最近的位置。
问题:
- 如何避免对同一个城市/邮政编码进行多次匹配?
- 通过简单的连接来获得 5 个最近的位置听起来是否可行?
方法2:
获取我的位置的所有纬度/纬度值,然后改为在此表上运行该过程。只是使用巨大的表格来检索我当前的位置?
有了这个,我需要收集我的位置的所有纬度/纬度。但这可能是最好的方法。
但是,拥有所有城市/邮政编码的庞大数据库只是为了获取位置似乎有点矫枉过正。我希望有另一种选择,那么也许...不知何故。。。
方法3
老实说,我想要的这个函数似乎已经写了一百万次了。那么我为什么要费心重新发明轮子呢?但我不知道如何找到合适的文章或书籍来实现我的目标。
你们中还有其他人对类似事情的最佳实践有想法吗?
首先有一些评论...
我在这里和其他论坛上看到了几十个(而不是数百万个)实现;你的比大多数都好。
根据一个数据源(我碰巧下载了),世界上大约有320万个城市。
为了提高性能,您需要避免检查所有 3M 行。 您已经在不断增长的边界框方面取得了良好的开端。 请注意,您应该有
INDEX(lat, lon),
INDEX(lon, lat)
优化器将在这些之间进行选择,第一个查询(带有COUNT(*)
)将将其视为"覆盖"。 它将是全球的条纹或楔形;对 3M 行有明显的改进。 最差的纬度(+34度)有96K个城市。 (1 度 = 69 英里/111 公里。 对于十分之一度,34.4是最差的,有10K城市。
(是的,我喜欢这种数据难题。
而且,我看到您处理日期变更线和极点。 我认为你不能把它们作为一个特例来改进。
(我只看了一眼公式和常量。
Geohash 和 Z 顺序索引帮助。 但是他们有一个小问题,你需要检查目标周围的多达4个区域 - 这就像没有意识到整数199999和200000彼此非常接近,尽管每个数字的第一个数字是不同的。
"用户传入邮政编码或城市名称" - 这是对两个简单表之一的点查询。 (除了可以有重复 - "圣何塞"和"圣安东尼奥"各超过320个。 排在名单后面的是第一个非西班牙语名字:"维多利亚",只有144个城市。
第二,我的实施...(它与你的有一些相似之处。
http://mysql.rjweb.org/doc.php/latlng
这通过使用PARTITIONing
将边界框缩小到大致正方形而不是条纹或楔形来提高性能。 如果你正在寻找 5 个最近的,我的算法很少会触及超过几十行,这些行将"聚集"在少量块中,从而保持非常低的磁盘命中次数。
在我的设计中,一个关键的事情是将所有必要的列放在一个表中。 找到最近的5个后,您可以转到其他桌子以获取辅助内容(电话号码等)。
至于邮政编码,在开始搜索最近的 5 个之前,将它们转换为纬度/纬度。
算法内部的连接很可能会破坏性能。
> 16K 行并不是那么多。
我有一个包含 3.1M 行的cities
表(数据取自 https://www.maxmind.com/de/free-world-cities-database)。我创建了一个"假"locations
表,其中包含 16K 个不同的随机 cityId 和一些虚拟数据。我使用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
执行时间为~70ms。
这可以通过子查询进行改进:
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)
执行时间:~40ms
如果将geoPoint
(冗余)存储在locations
表中,则可以避免与cities
表联接。
select l.*, st_distance(point(-0.127758, 51.507351), l.geoPoint) dist
from locations l
order by dist
limit 5
执行时间:~17ms
您仍然可以将cities
表联接到子查询,而不会降低性能。
请注意,所有这些查询都将计算所有 16K 行的距离并对其进行排序。但性能对您来说可能已经足够了。
如果这还不够快,或者locations
表会随着时间的推移而增长,或者如果您想在大表中搜索,您仍然可以使用geoPoint
和MBRWithin()
或MBRContains()
上的SPATIAL INDEX
执行类似于程序的操作。
算法:
- 在用户位置周围定义一个小多边形。
- 增加循环中多边形的大小,直到它至少包含 5 个位置。
- 使用面内的位置选择 5 个最近的位置。
请注意,根据您使用的多边形类型,在找到具有 5 个位置的多边形后,您可能需要再次增加大小。例如 - 如果你使用正方形(简单实现),你应该将大小加倍(增加长度的因子sqrt(2)),以绝对确保你不会错过正方形之外的位置,该位置比正方形内的第 5 个位置更近。这是因为正方形不是圆形。但是如果你使用八边形,你可能会说 - 这已经足够圆了 - 并跳过最后一步。
这可能不是最好的算法。但它实现起来非常简单,并且应该可以很好地扩展。