*** MYSQL 算法难题: 查询距离指定坐标 10 公里范围内的所有店铺 ***

[Angela2022]

我有 MYSQL 表含 20 万条记录, 每条记录有店铺和位置经纬度字段. 现在我用 sql 查询距离指定坐标半径 10 公里内的所有店铺, 发现查询速度奇慢, 做了 index 后也是如此.

问题:
1. 上述需求,用啥数据格式的字段存位置经纬度合适?
2. 求最新最快的半径 10 公里内的所有店铺查询算法, 最好支持 MYSQL.

谢谢

[xmumiffy]

where 条件限制经纬度差距各+-0.1 度,然后再算

[leaflxh]

先把店铺按照城市区域分好区

[dode]

建一个大一些的基础网格系统，正方形，三角形，六边形，提前划分标记一下这些经纬度

[akira]

你先说下 你怎么计算距离的呢

[wenber]

[HanSonJ]

https://redis.io/docs/data-types/geospatial/

我第一次见坐标用 MySQL 实现的。。。你不得算距离啊

[liprais]

mysql 也有 geo 功能，自己看看文档呗

[toneewang]

这个需求是不是可以用空间数据类型来存啊

[toneewang]

https://www.mysqlzh.com/doc/176/143.html

[xmumiffy]

@xmumiffy 经度有错误,还要除余弦

[V2April]

@dode 六边形感觉是个有意思的思路，像文明 6 那样数格子就行了

[rabbbit]

Redis geo 或者 PostGIS

[laminux29]

思路错了。这就好比，你选择用汇编去实现，然后发个新帖子：汇编算法难题。

正确的思路是，选择支持地理范围直接查询的数据库，用它做个冗余数据库，专门做地理查询服务就行了，不要为难 MySQL ，很多场景，Mysql 并不适合。

[ZoR]

redis

[amon]

XY 问题，你还是使用 GEO 存储吧

[546L5LiK6ZOt]

之前做过地理位置相关的，经纬度小数点第一位精度是 10 公里左右，数据库按一位小数存经纬度，查询 sql 就变成等值查询了

[BeiChuanAlex]

我在想如果用 postgresql 会不会更好写。

[Vegetable]

@546L5LiK6ZOt 这也太糊弄了，0.9 和 1.1 匹配吗？

[mikewang]

根据坐标和 10 公里的条件，确定极限范围：
A <= 经度 <= B
C <= 纬度 <= D
然后在查到的数据中，使用子查询验证是否真正满足 10 公里的条件。
这样可以避免全表计算距离。

[xiangyuecn]

mysql 自带空间数据类型 geometry + 空间索引，可以自己研究一下 mysql 文档，查询就直接构造出一个圆面（用合适边数的多边形去近似即可），查出和这个圆面相交坐标点就 ojbk 了，基本上所有数据库通用

[xiangyuecn]

指定中心点坐标、半径，生成圆面的代码，可以参考我的 AreaCity-Query-Geometry 代码，30 行

https://github.com/xiangyuecn/AreaCity-Query-Geometry/blob/b626c53a85350c43c64e7886e926c3e9ac877a52/AreaCityQuery.java#L1375-L1402

其中采用 Haversine formula 算法 计算经纬度坐标的距离，5 行代码

[a1b2c3T]

没记错的话 redis 好像有这个功能，

[Thymolblue]

@546L5LiK6ZOt 实际上每经度距离和纬度相关，这样算这个库在北京就用不了了。

[iseki]

以前流行过 geohash ，如果 MySQL 自己的地理信息功能挑不起来大梁，可以尝试附加一个 geohash

[iseki]

另外如果可行，还是推荐使用现成可靠的地理信息设施，比如 PostGIS ，应该比 MySQL 自己的 GIS 功能强得多

[tracymcladdy]

不要折腾，全部加载出来，一个工具类的事

[sola97]

用过 postgis

[249239432]

楼上一群半吊子，这个是计算量的问题，需要消耗 cpu 资源的，不是换个工具换个数据库就能解决

我司需求是 600 万数据查询经纬度大于 50 米，解决方案是用 spark 并行计算，20 个 task ，一个任务配置 2G 内存

后端大概 50 台刀片机服务器集群，跑一次要 16 个小时

[lshero]

非要 mysql 吗 geohash 支持那么差劲的
一般用 ES 一步到位或者 Redis 得 geohash 取出 ID 后 mget 获取详情

[changdy]

@249239432 哈哈 笑死我了才 20w 条记录... 还需要购买额外的资源... 还说别人是半吊子..
说句不客气的话..200w 数据 postgis 也是轻轻松松搞定...
楼上那么多人提到了 geo 相关的服务..你这也不反思下自己... 果然你是最独特的...

希望你的下一条回复是 "经过认真分析,确实 geo 工具有可行性"

[yingqi1]

@249239432 我也是搞大数据的，你这个 spark 的方案是真的有问题。spark 也有空间计算库 GeoSpark...。不需要硬算了。不论什么需求，一个 Job16 个小时真的吓到了。 再说了，人家 OP 是要实时查询的方法，很明显用楼上的 redis/mysql geo 数据类型可以解决。

[Fa11ingWood]

这个不知道 我司用的是 pg pg 有自带的函数 ST_within 这个函数 能实现你说的功能

[249239432]

你们就不知道好好审题？，一个心眼钻牛角尖用什么工具、框架、软件上？
集群计算速度快还是用你那台数据库或者 postgis 计算快?

@yingqi1 我用程序硬算都能算出来，纠结这东西干什么，不用集群能变快么？

@changdy 我说的是我司方案，你意淫到别人头上去了？

[249239432]

@changdy 200w 数据轻松搞定，5 个小时搞定？

[lqs]

有个很简单很取巧的做法：

经度和纬度分两个字段，并仅对纬度建立索引。由于纬度等距，相差 0.09 度大约为 10 公里，且中国大城市纬度分布差异较大，这样能利用索引初步筛选，把 20 万筛选到 5000 以内。然后再用距离公式精确计算。

[dzdh]

1.mysql 8.x 已经支持了，直接 sql 能实现，加上空间索引搜索非常快

2. redis geo 除了 mysql 之外最快的方案

3. 以上两种方案仅限于单纯的范围检索，如果是社交类的场景比如 5 公里范围内的排序外加+女的+18 的+3 天内上线过的+兴趣爱好 in (a,b,c) 的。那就老老实实上 elasticsearch 类的搜索引擎，没有任何其他方法可以最低成本实现。

[yingqi1]

@249239432 典型的数据结构问题，关集群什么事情。 审题: 20 万行数据，产品 ID (int)、经纬度(geohash) 各 8 字节。撑死 10 多 M ，要个鸡毛集群。 再说说 spark 不是框架/软件吗？ 好好学习，请不要再使用“一群半吊子”的词汇了。

[249239432]

@yingqi1 这是计算量的问题，跟数据大小有什么关系，说不过就开始专牛角尖了？ spark 我还不知道是什么东西么

2. 求最新最快的半径 10 公里内的所有店铺查询算法, 最好支持 MYSQL.
你这叫审题？ 我用集群是不是比你用单机快？

[cI137]

有人不懂什么叫空间换时间，沙雕集群

[SimbaPeng]

果然半吊子叫的是最凶的

[SimbaPeng]

也不知道从哪听了个 spark ，见人都要叭叭两句，笑死我了

[flyz]

@249239432 相当于跑出来存表？每次查询都做表查询么。

[249239432]

@flyz 数据从表里面加载，在 spark 计算，结果你要存表或者干什么都行

[ffw5b7]

美团技术团队，2014 年的距离优化文档，希望能帮助你
https://tech.meituan.com/2014/09/05/lucene-distance.html

[encro]

你们这些人，

都当 mysql 开发团队是 SB ！！！

开发个简单的 geo 还比 pg 性能差一大截？

[shenjinpeng]

推荐改用 es 查, 附带搜索一起搞了


PS: 贴一下 MySql 代码

```PHP
// 6371000 地球半径, 距离查询
// 可以当作子查询字段排序,先计算距离再排序
$distance = "ROUND( 6371000 * 2 * ASIN(SQRT( POW(SIN(({$lat} * PI() / 180 - latitude * PI() / 180) / 2),2) + COS({$lat} * PI() / 180) * COS(latitude * PI() / 180) * POW(SIN(({$lng} * PI() / 180 - longitude * PI() / 180) / 2),2))) ) AS distance";

```


```mysql
-- 自己实现的 mysql 函数
CREATE DEFINER=`root`@`%` FUNCTION `calcStoreDistance`(lat double, lng double,latitude double,longitude double) RETURNS int(11)
BEGIN
RETURN ROUND(
12742000 * ASIN(SQRT(
POW(SIN((lat * PI() / 180 - latitude * PI() / 180) / 2),2) +
COS(lat * PI() / 180) *
COS(latitude * PI() / 180) *
POW(SIN((lng * PI() / 180 - longitude * PI() / 180) / 2),2)
)));
END


-- 使用 SELECT *,calcStoreDistance(25.028317,102.678467,store.latitude,store.longitude) as distance FROM `store` order by distance;
```


```mysql
-- 直接用 mysql 自带函数
ROUND(st_distance_sphere(point($lng,$lat),geo)) as distance
```

[Orlion]

https://blog.fanscore.cn/a/51/ 看下我这这篇文章吧，不知道对你有没有帮助，大概思路是取出一个坐标点附近九宫格所有坐标点，然后在程序中计算每个点距离该坐标点的距离，过滤掉不符合距离条件的点。

虽然文章中使用的是 redis ，但换成 mysql 应该是通用的吧。

[opengps]

这问题刚好我以前做围栏时候用过，办法就是一楼所说。按照纬度 1 度相差 111km 来算，10 公里刚好就是 0.1 度，然后你再根据需要二次筛选即可（甚至不筛选也够用了）

[QlanQ]

mysql 高版本的已经支持了，20w 数据 还是可以应付了，等公司有钱了，快上市了，流量起来了，有时间了你在改一版吧，改成 es ，把前端相关查询都走 es(es 真的很费钱，小公司单台服务器配置差点的，都跑不起来，比如 2G 内存的)

[summerLast]

1. 当前经纬度各加减 50 米
2. 35.35 米外 50 米内坐标转换算斜边长度大于 50 米的
1+2

[echoZero]

之前做过 根据用户位置查找多少米的商户，用 redis 的 GEO 算的

[Desdemor]

俺们用的 redis

[qsnow6]

GEO 是最佳实践，优化好索引速度很快，上集群纯粹没活硬整，集群间的通信不需要开销吗？

[wanniwa]

@ffw5b7 #44 感谢分享，收藏了

[tool2d]

我用 google 的 http://s2geometry.io/ ，查询效率很高。

这算法 mongodb 有内置空间索引，mysql 似乎没有。

[griffen]

neo4j 比较适用于这类数据吧？

[fengpan567]

我建议直接换 mongodb

[xz410236056]

@xmumiffy #1 范围是个圆形。。。

[eachann]

1. 使用 MySQL 的空间数据类型`POINT`存储位置经纬度是合适的。
2. 使用 MySQL 的空间索引和`ST_Distance_Sphere`函数可以快速查询半径 10 公里内的所有店铺。

解释：
1. MySQL 的空间数据类型`POINT`可以存储地理位置的经纬度信息。与传统的两个分开的字段相比，`POINT`类型可以让 MySQL 利用空间索引（ Spatial Index ），这样可以大大提高地理位置查询的效率。
2. `ST_Distance_Sphere`函数可以计算两个点之间的球面距离，适用于地球表面的距离计算。结合空间索引，这种方法可以快速筛选出指定半径内的店铺。

建议：
- 确保你的 MySQL 版本支持空间数据类型和函数。MySQL 5.7 及以上版本对空间数据的支持较好。
- 在包含经纬度的`POINT`字段上创建空间索引，以提高查询效率。
- 使用如下 SQL 示例进行查询：

```sql
SELECT shop_name, ST_AsText(location)
FROM shops
WHERE ST_Distance_Sphere(location, ST_GeomFromText('POINT(经度 纬度)')) <= 10000;
```
- 替换`经度`和`纬度`为你的指定坐标。这个查询会返回距离指定坐标 10 公里内的所有店铺的名称和位置。

[ElmerZhang]

我用 postgis 。不过我记得 mysql 5.7 开始就支持 geo 了吧？

[openmynet]

tile38

[sazima]

直接按距离查就行， 之前做过和 gis 相关的。

https://dev.mysql.com/blog-archive/geography-in-mysql-8-0/

[MoYi123]

@249239432 r-tree ,kd-tree 这些数据结构都不行, 还得是我最爱的集群 for 循环最高效

[freewind]

50w 数据直接用 mysql 查不用一秒就出来了

[jackerbauer]

感觉 geohash 应该可以的

[cI137]

@249239432 你们公司方便告诉一下是哪个公司吗，可以降本增效了

[ZeroDu]

大多数据库都有 geo 相关支持的。简单点 redis 就可以

[rrfeng]

600 万数据查询经纬度大于 50 米，跑一次查询 16 小时，笑死
可能是个好消息，这种公司还能活着说明市场还没差到那么惨？

[lianglianglee]

如果版本低，可以先从 MySQL 中取正方形的数据，10 公里可以取固定的经纬度差，然后再用代码计算哪些需要剔除。

10 公里范围内，只要不是南北极，不用算球的弧度，相差不会太大，可能有十几厘米的误差

[dyllen]

我之前用 decimal 类型存经纬度数据，精确到四位还是几位忘了，两个字段，查距离就比较经纬度数据了，能查个大概。

比较格子的四个点，在点里面的数据全取出来。

[zihuyishi]

东南西北各扩展 10 公里然后把正方形里的店铺全筛出来，然后再用代码算一下距离把不满足条件的过滤掉。

[0576coder]

geohash

[yjhatfdu2]

@249239432 你这也太离谱了，我给你看看 postgis 的测试结果，笔记本上运行（ m1max ）。
创建一个测试表，并用使用 WGS84 坐标系，创建 1000w 条测试数据，平均分布在经度 120-130 ，纬度 60-70
postgres=# create table geo(id serial primary key,point geography);
CREATE TABLE
Time: 8.159 ms
postgres=# insert into geo(point) select st_point(120+10*random(),60+10*random(),4326) from generate_series(1,10000000);
INSERT 0 10000000
Time: 22743.621 ms (00:22.744)
postgres=# select count(*) from geo;
count
----------
10000000
(1 row)

Time: 184.563 ms
直接查找 500m 内的点
postgres=# select id,st_astext(point) from geo where point<->st_point(121,61,4326) <500;
id | st_astext
---------+----------------------------------------------
462445 | POINT(120.99758165008446 60.99813696562379)
1438617 | POINT(121.00541966217078 61.00254115685877)
6427771 | POINT(121.0057518866478 60.99946005998968)
7239910 | POINT(121.00062919717045 61.00302782747821)
480378 | POINT(121.00686930870204 60.99929456226042)
6463221 | POINT(121.00448273536959 60.99901955735362)
7497972 | POINT(121.00128087999187 61.000266168985476)
9546292 | POINT(121.00044691737057 61.00368666618427)
9594039 | POINT(121.00070061094034 60.996584053665245)
(9 rows)

Time: 897.110 ms
创建 GIST 索引后使用 ST_DWithin 函数可以使用索引加速
postgres=# select id,st_astext(point) from geo where ST_DWithin(point,st_point(121,61,4326),500) ;
id | st_astext
---------+----------------------------------------------
7497972 | POINT(121.00128087999187 61.000266168985476)
9594039 | POINT(121.00070061094034 60.996584053665245)
6463221 | POINT(121.00448273536959 60.99901955735362)
9546292 | POINT(121.00044691737057 61.00368666618427)
1438617 | POINT(121.00541966217078 61.00254115685877)
7239910 | POINT(121.00062919717045 61.00302782747821)
462445 | POINT(120.99758165008446 60.99813696562379)
480378 | POINT(121.00686930870204 60.99929456226042)
6427771 | POINT(121.0057518866478 60.99946005998968)
(9 rows)

Time: 10.359 ms
只要 10 毫秒，比你们快至少 3 亿倍

只能说废公司是贵物

[leonhao]

这帖子太刷新下限了，没想到数据库水平如此之低，天天卷八股了

[xmumiffy]

@xz410236056 先限定范围在圆的外接正方形内，只对这个正方形继续搜索

[xmumiffy]

@lianglianglee 经度差要除纬度的余弦,不然北京就和赤道就差了 25%.
纬度 60 度时,每 1 度经度的长度是赤道的一半.
反正被搜索点的纬度是确定的,除以余弦还是常数子,不影响效率.

[lyz1990]

哈哈，为啥这种不涉及价值观和意识形态的纯技术问题也能吵起来

[niubee1]

圆形半径比较难算，如果是计算一个上下左右 5 公里范围的矩形就简单了。如果你不用索引的内置函数的话，可以计算出这个矩形的经度范围和纬度范围，然后根据这个范围过滤就行了，前提是经度纬度要分开用浮点字段存。这个方法适合没有用 GIS 索引的情况下。
如果你用了空间索引的话：

SELECT *
FROM locations
WHERE ST_Contains(
GeomFromText('Circle(Longitude Latitude radius)'),
position
);

[dbpe]

@lyz1990 因为楼里某位大佬举例的场景和使用的解决方案。。太离谱了

[dog82]

XX 年前知道 oracle spatial 是解决空间计算的扩展
看楼上的回复，mysql geo 应该类似

[lambdaq]

20 万条记录 。。。直接 where 经度 between a and b AND 纬度 between c AND d 然后拿到数据，代码里 Haversine 一把梭吧。。

啥时候 1000w 以上的数据再用各种 geo 库吧。

[xz410236056]

@xmumiffy #75 严格来说，应该是个球面（甚至除以余弦的方式也不严谨，地球又不是个球。应该用 Vincenty ），在空间中找个平面图形，误差会很大。经纬度中每度的距离并不是固定的，尤其是精度，会随着纬度变化而变化。有的地方会是个 22*22 的矩形（赤道）越靠近极点越小，这样就会有很多冗余数据和漏掉很多数据。

[mxT52CRuqR6o5]

啥 geo 索引相关的知识都不知道，就拿集群搁那儿硬算 5 个小时，还觉得自己可牛逼了😅

[xmumiffy]

@xz410236056
公里级精度不用考虑地球不是球的问题. 10 公里级也可以忽略在球面上取平面的误差.
#10 补充了经度需要除纬度的余弦

[yh7gdiaYW]

数据导入 MongoDB ，$geoWithin ，完事儿

[249239432]

@yjhatfdu2 没说清楚需求，600 万数据是要互相跟其他所有数据计算的，也就大概是 600 / 2 * （ 600 - 0.001 ） 万次查询，需要大量 cpu 资源

[shadowyue]

@yjhatfdu2 🤣3 亿倍也太强了，老哥。来一发都不一定有 3 亿。

[macttt]

美团有一篇文章可以参考,使用的 ES:https://tech.meituan.com/2022/11/17/elasicsearch-optimization-practice-based-on-run-length-encoding.html,我觉得用传统数据结构不太可行噢

[lambdaq]

@xz410236056 好像是个椭球。高纬度地区是扁的。。

[macttt]

@macttt 美团有一篇文章可以参考,使用的 ES:https://tech.meituan.com/2022/11/17/elasicsearch-optimization-practice-based-on-run-length-encoding.html ,我觉得用传统数据结构不太可行噢

[zhouxiyu]

还是用地理数据库吧

[jackerbauer]

每个店铺生成一个 geohash ，然后根据 geohash 找到一个点周围的店铺

https://zhuanlan.zhihu.com/p/35940647

[mxT52CRuqR6o5]

@lyz1990 #76 那个人到处传播错误知识还不自知得 diss 几句呀，不然别人信了学了去了可害人啊

[lijin7516]

我觉得大家讨论的非常精彩，笑出了猪叫声

[romisanic]

拿空间换时间
况且你这点数据也用不了多少控件

[ynxh]

好问题

[jimrok]

欧式距离可能会容易算一些，曼哈顿距离可能体验更好，如果是欧式距离，可以先把地图分割成区域，再通过 10 公里的半径计算一下有那些区域落入，把这些区域里面商户列出，优先中心区域，其他边缘区域的需要二次筛查，稍微耗费一些计算。

[Rickkkkkkk]

技术方案选型就被打回了...老老实实用 redis 吧.

[mmdsun]

“现在我用 sql 查询距离指定坐标半径 10 公里内的所有店铺, 发现查询速度奇慢。” op 贴下关键 SQL 看看，才 20 万不会慢的

[cherishfall]

美团技术-地理空间距离计算优化 https://tech.meituan.com/2014/09/05/lucene-distance.html 这篇博客应该是博主需要的。
现在我的做法（数据量较小）是在 mysql 创建一个 haversine 方法计算距离的函数，然后传入就好了。