背景

近期在开发一个需求的使用用到了 MYSQL 的空间索引，之前一般也用不上这个，这次第一次用倒是踩了不少的坑。

目前需求开发完成且稳定运行一段时间没有异常了，才来写这篇文章，主要就是介绍一下如何使用 MYSQL 的空间索引以及在使用中需要注意的一些坑。

问题引入

在 MYSQL 数据库中保存了上千万条记录，每条记录保存了一个地理坐标点。需求是传入一个坐标点的位置以及一个半径r，检索出该坐标点方圆r距离内的所有记录。

看起来有点小小的难度，上网检索了一下，MYSQL 中有个函数 ST_Distance_Sphere 能直接计算两个坐标点的距离。

那 easy 了，省略表中无关字段，表的 DDL 为：

1
2
3
4
5
create table `locations`
(
    id         bigint auto_increment primary key,
    coordinate point not null
)

查询 sql 则为：

1
2
3
4
5
SELECT * FROM `locations`
WHERE ST_Distance_Sphere(coordinate,ST_GeomFromText('POINT(lng lat)')) <= r;
-- lng 经度
-- lat 纬度
-- r 半径，单位为米

简单运行一下试试，随便检索一个坐标点 1km 范围内的记录并验证一下结果。

无索引直接运行结果

结果就是完全没问题，耗时600ms(测试表内存在约10w条数据)。ok，需求解决，提交！

但话又说回来，10w的数据量级跑出了 600ms 的耗时，这是很不合格的。所以，接下来的问题就是如何优化了。

MYSQL 的空间索引

innodb 以及 myisam 引擎均实现了地理空间索引，可以通过 SPATIAL INDEX 添加空间索引。

这两个引擎对于空间索引的实现方式是不同的，innodb 是通过 B-Tree 实现的，不过 B-Tree 主要是用于单维度的数据比较以及排序，对于空间这种多维数据的支持是比较有限的。而 myisam 是通过 R-Tree 实现的，这是专为处理多维空间数据而设计的索引结构，所以能够很好的支持多维数据的范围查询和空间交集查询。

简单来说就是在空间查询上，使用 R-Tree 实现的 myisam 引擎是比 innodb 更合适的。不过该需求也是集成在原项目上的，还需要考虑其他功能的需求，在其他需求中事务支持又是必须的，所以最终还是选择采用 innodb 的空间索引来优化上文中的查询。

添加空间索引

为上文中的表添加 SPATIAL INDEX：

1
2
ALTER TABLE `locations`
ADD SPATIAL INDEX `sp_idx_coordinate` (coordinate);

利用空间索引

此时，我们使用上文中的查询 SQL 进行查询分析，发现查询计划仍然是走的全表扫描。这是什么原因呢？这是因为在 MYSQL 中并不是使用到空间索引字段的查询条件就会自动利用空间索引，而是需要使用特定的函数，才会使用到空间索引。

空间索引的工作机制是基于 最小边界矩形（MBR），即每个几何对象的最小外包矩形。

经过测试（此处指的是趟过所有坑后测试的结果），以下几个函数都能利用空间索引进行查询优化：

  • MBRContains(g1, g2)：判断几何对象 g1 的 MBR 是否完全包含 g2 的 MBR;
  • MBRWithin(g1, g2)：判断几何对象 g1 的 MBR 是否在 g2 的 MBR 之内;
  • MBRIntersects(g1, g2)：判断 g1 和 g2 的 MBR 是否相交;
  • MBRTouches(g1, g2)：判断 g1 的 MBR 是否接触 g2 的 MBR 边界;
  • MBROverlaps(g1, g2)：判断 g1 和 g2 的 MBR 是否部分重叠;

为了能用利用上上述的索引，我们可以先过滤一下表中的数据，将不可能的结果先排除掉，只留下可能得结果进行距离的计算，得出最终的结果。

为了排查不可能的结果，我们可以先计算出圆的 bounding box(最小的包含矩形)，再使用上述的 MBRContains 函数，过滤出包含在该矩形中的记录。

此时，就涉及到了 bouding box 的计算方法了。

众所周知的，地球是一个类似椭圆的形状，不同经纬度时固定距离间经度的差值和纬度的差值是不一样的。

可以参考以下公式来计算一个经纬度移动指定距离后的经纬度(此处的 radius 单位为 km)：

纬度：lat ± (radius / 111)
经度：lng ± (radius / (111 * cos(lat)))

参考以下示意图，可以得出 bouding box 上下左右四个方向的坐标点与圆心偏移的偏移量为 √2r。

bouding-box示意图

计算出圆心向四个方向偏移 √2r 后的四个坐标点，再使用 POLYGON 函数生成多边形，将其作为参数1代入到 MBRContains 函数中，即可完成数据的初筛。

这里需要注意第一个坑：经纬度的最大值和最小值。

  • 对于计算后经度大于 180 的，需要减去 360；
  • 对于计算后经度小于 -180 的，需要加上 360；
  • 对于计算后纬度大于 90 的，需要减去 180；
  • 对于计算后纬度小于 -90 的，需要加上 180；

优化后的 sql 语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
SELECT *
FROM `locations` 
WHERE (MBRContains(ST_GeomFromText('POLYGON((lp,up,rp,dp,lp))'),coordinate)) 
  AND (ST_Distance_Sphere(coordinate,ST_GeomFromText('POINT(orip)')) <= ?);
-- lp 向左偏移 √2r 后的坐标点 
-- rp 向右偏移 √2r 后的坐标点 
-- up 向上偏移 √2r 后的坐标点  
-- dp 向下偏移 √2r 后的坐标点 
-- orip 原点
-- 例如查找北京方圆十公里的记录：
SELECT *
FROM `locations`
WHERE (MBRContains(ST_GeomFromText('POLYGON((116.605682 39.906217,116.176870 39.906217,116.391276 39.778810,116.391276 40.033624,116.605682 39.906217))'),coordinate))
  AND (ST_Distance_Sphere(coordinate,ST_GeomFromText('POINT(116.391276 39.906217)')) <= 10000);

指定 SRID

介绍到这里，你以为结束了吗？nonono，这里面的坑还是不少的。对上述的语句查询分析，可以发现该查询还是没能利用索引，走的是全表扫描。再又翻阅了一些文档和别人写的文章后发现，要想空间索引生效，空间索引所在的字段必须满足两个条件：

  1. NOT NULL
  2. 指定了 SRID

这里简单介绍一下 SRID：

SRID 指定的是 spatial 数据的坐标系，这个坐标系定义了一些诸如大地基准、海平面、地球形状、球心、球心偏移等等数据，在不同地区这些值都是不同的。
SRID 的存在就是为了尽量消除误差，以接近真实的地理信息。

我们可以看到，上文中的建表语句以及 ST_GeomFromText 函数中都没有指定 SRID。其实这时候将会采用默认的 SRID，即 0。

而通常情况下，我们在服务端存储数据时，采用的都是 4326 的 SRID。

平常我们见到的 84坐标系、高德坐标系、百度坐标系、国测、火星等乱糟糟的都是基于 4326 坐标系的定义的。

所以，对于上述表以及查询，我们需要改一改：

1
2
3
4
5
6
7
-- 修改表的 SRID
ALTER TABLE `locations` 
    MODIFY `coordinate` POINT SRID 4326;
-- 更新现有数据的 SRID
UPDATE locations
SET coordinate = ST_Transform(coordinate, 4326)
WHERE ST_SRID(coordinate) != 4326;
1
2
3
4
SELECT *
FROM `locations` 
WHERE (MBRContains(ST_GeomFromText('POLYGON((lp,up,rp,dp,lp))',4326),coordinate)) 
  AND (ST_Distance_Sphere(coordinate,ST_GeomFromText('POINT(orip)',4326)) <= ?);

运行上述查询，不出意外的，报错了~这时候就遇到第二个坑了：不同 SRID 的坐标点使用的坐标轴顺序是不同的。

SRID 除了定义上述提到的大地基准，球体，水准面等，他还会定义坐标轴的单位和顺序，例如是度，还是公里，是 lng/lat 还是 lat/lng。

而 4326 SRID 采用的坐标轴顺序是 lat/lng，而上文中我们使用默认的 0 SRID，其坐标轴顺序是 lng/lat。

所以，我们还需要调转一下坐标点的经纬度。也可以在 ST_GeomFromText 函数中添加一个参数指定一下坐标轴顺序，如：

1
st_geomfromtext('POINT(116.391276 39.906217)',4326,'axis-order=long-lat')

对于我来说还是比较建议直接在代码层面解决这个问题，直接传入 lat/lng 格式的坐标点，不把复杂度传递到数据库。这点大家见仁见智。

调转完经纬度之后，再使用上述语句进行查询分析，就可以看到查询类型为 range，能成功利用索引了。

更多小细节优化

1.冗余字段

以上的查询语句，使用的是 SELECT *，但是 point 类型在数据库中存储的是一个二进制数据，查询出来的结果是其二进制表示，是没办法直接看出其经纬度信息的。

可以通过 ST_X、ST_Y、ST_AsText 等函数来将其转换为可观察的数据。

我的做法是在存储数据的时候直接冗余两个字段 lng 和 lat，而在查询的时候直接查询 lng 和 lat 的值得到其经纬度，避免额外的数据库函数开销。

2.计算更精确的 bounding box

上文中介绍的计算 bounding box 的方式是比较粗糙的，有需要的可以自行采用更精确的方案去计算 bounding box，达到过滤掉更多数据的目的。

3.使用变量保存函数结果

可以使用变量保存上述查询语句中的函数结果，避免重复的函数计算。

一步到位 DDL

贴一个在建表时直接指定 SRID 并创建空间索引的 DDL 供大家参考：

1
2
3
4
5
6
7
8
CREATE TABLE `locations`
(
    id          BIGINT AUTO_INCREMENT  PRIMARY KEY,
    lng         DOUBLE   DEFAULT 0  NOT NULL,
    lat         DOUBLE   DEFAULT 0  NOT NULL,
    coordinate  POINT    NOT NULL   SRID 4326,
    SPATIAL INDEX `sp_idx_coordinate` (`coordinate`)
);

总结

这边文章主要介绍的是在运用 MYSQL 进行空间索引优化时踩的一些坑和解决方案，文章的描述顺序与我开发的顺序基本是一致的，希望大家看完这篇文章都能有所收获，有任何问题也欢迎在评论区评论交流。