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

Angela2022 · 2024-03-10T09:50:59Z

我有 MYSQL 表含 20 万条记录, 每条记录有店铺和位置经纬度字段. 现在我用 sql 查询距离指定坐标半径 10 公里内的所有店铺, 发现查询速度奇慢, 做了 index 后也是如此. 问题: 1. 上述需求,用啥数据格式的字段存位置经纬度合适? 2. 求最新最快的半径 10 公里内的所有店铺查询算法, 最好支持 MYSQL. 谢谢

MySQL

查询

速度

108 replies • 2025-10-27 15:26:24 +08:00

1 2

❮

❯

106npo

Mar 10, 2024

1

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

leaflxh

Mar 10, 2024

2

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

dode

Mar 10, 2024

3

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

akira

Mar 10, 2024

4

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

wenber

Mar 10, 2024

1

5

HanSonJ

Mar 10, 2024

2

6

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

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

F281M6Dh8DXpD1g2

Mar 10, 2024 via iPhone

7

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

toneewang

Mar 10, 2024

8

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

toneewang

Mar 10, 2024

9

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

106npo

Mar 10, 2024

10

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

V2April

Mar 10, 2024

11

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

rabbbit

Mar 10, 2024

12

Redis geo 或者 PostGIS

laminux29

Mar 10, 2024

13

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

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

ZoR

Mar 10, 2024

14

redis

amon

Mar 10, 2024

2

15

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

aGVsbG93b3JsZA

Mar 10, 2024 via iPhone

16

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

BeiChuanAlex

Mar 10, 2024

17

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

Vegetable

Mar 10, 2024

1

18

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

mikewang

Mar 10, 2024

19

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

xiangyuecn

Mar 10, 2024

20

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

xiangyuecn

Mar 10, 2024

21

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

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

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

a1b2c3T

Mar 10, 2024 via iPhone

22

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

Thymolblue

Mar 10, 2024 via Android

2

23

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

iseki

Mar 10, 2024 via Android

24

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

iseki

Mar 10, 2024 via Android

25

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

tracymcladdy

Mar 10, 2024 via iPhone

26

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

sola97

Mar 10, 2024

27

用过 postgis

249239432

Mar 10, 2024

28

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

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

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

lshero

Mar 10, 2024

29

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

changdy

Mar 10, 2024

8

30

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

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

yingqi1

Mar 10, 2024

2

31

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

Fa11ingWood

Mar 10, 2024

32

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

249239432

Mar 10, 2024

33

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

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

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

249239432

Mar 10, 2024

34

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

lqs

Mar 10, 2024

35

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

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

dzdh

Mar 11, 2024

11

36

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

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

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

yingqi1

Mar 11, 2024

1

37

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

249239432

Mar 11, 2024

38

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

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

cI137

Mar 11, 2024 via iPhone

39

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

SimbaPeng

Mar 11, 2024

2

40

果然半吊子叫的是最凶的

SimbaPeng

Mar 11, 2024

1

41

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

fstab

Mar 11, 2024 via Android

42

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

249239432

Mar 11, 2024

43

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

ffw5b7

Mar 11, 2024 via Android

3

44

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

encro

Mar 11, 2024

45

你们这些人，

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

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

urlk

Mar 11, 2024

46

推荐改用 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

Mar 11, 2024

47

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

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

opengps

Mar 11, 2024

48

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

QlanQ

Mar 11, 2024

1

49

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

summerLast

Mar 11, 2024

50

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

echoZero

Mar 11, 2024

51

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

Desdemor

Mar 11, 2024

52

俺们用的 redis

qsnow6

Mar 11, 2024

53

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

wanniwa

Mar 11, 2024

54

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

tool2d

Mar 11, 2024

55

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

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

griffen

Mar 11, 2024

56

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

fengpan567

Mar 11, 2024

57

我建议直接换 mongodb

xz410236056

Mar 11, 2024

58

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

eachann

Mar 11, 2024

59

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

Mar 11, 2024

60

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

openmynet

Mar 11, 2024

61

tile38

sazima

Mar 11, 2024

62

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

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

MoYi123

Mar 11, 2024

1

63

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

freewind

Mar 11, 2024

64

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

jackerbauer

Mar 11, 2024

65

感觉 geohash 应该可以的

cI137

Mar 11, 2024 via iPhone

66

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

ZeroDu

Mar 11, 2024

67

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

rrfeng

Mar 11, 2024

68

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

lianglianglee

Mar 11, 2024

69

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

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

dyllen

Mar 11, 2024

70

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

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

zihuyishi

Mar 11, 2024

71

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

0576coder

Mar 11, 2024

72

geohash

yjhatfdu2

Mar 11, 2024

7

73

@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

Mar 11, 2024

74

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

106npo

Mar 11, 2024 via Android

75

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

106npo

Mar 11, 2024

76

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

lyz1990

Mar 11, 2024

77

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

niubee1

Mar 11, 2024

78

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

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

dbpe

Mar 11, 2024

79

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

dog82

Mar 11, 2024

80

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

tf2

Mar 11, 2024

81

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

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

xz410236056

Mar 11, 2024

82

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

mxT52CRuqR6o5

Mar 11, 2024

83

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

106npo

Mar 11, 2024

84

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

yh7gdiaYW

Mar 11, 2024

85

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

249239432

Mar 11, 2024

86

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

shadowyue

Mar 11, 2024

87

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

macttt

Mar 11, 2024

88

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

tf2

Mar 11, 2024

89

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

macttt

Mar 11, 2024

1

90

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

zhouxiyu

Mar 11, 2024

91

还是用地理数据库吧

jackerbauer

Mar 11, 2024

92

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

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

mxT52CRuqR6o5

Mar 11, 2024

93

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

lijin7516

Mar 11, 2024

94

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

romisanic

Mar 11, 2024

95

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

ynxh

Mar 11, 2024

96

好问题

jimrok

Mar 11, 2024

97

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

Rickkkkkkk

Mar 11, 2024

98

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

mmdsun

Mar 12, 2024 via iPhone

99

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

cherishfall

Mar 12, 2024

100

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

1 2

❮

❯