MySQL · 引擎特性 · 初识 MySQL GIS 及 InnoDB R-TREE

一直以来mysql在gis上的功能支持都比较弱，并且仅有myisam引擎支持。很高兴的看到mysql5.7将这个短板补上了，实现了innodb引擎的gis支持，现在对gis数据可以支持完整的mvcc和事务特性。在mysql5.7版本里，针对gis特性主要做了几点改进：

innodb支持spatial index，可以对空间数据类型建立索引

由于之前未玩过gis，本文以小白视角开始学习，并粗浅的记录了一些涉及到的代码函数，便于以后若涉及到相关工作，可快速检索到。 读者可以拉到文章最末尾，直接参阅附上的参考文档连接即可。

st_geomfromtext

用于将空间数据从可读的文本类型转换成内部存储的二进制类型

st_astext

将空间数据转换成可读的文本类型

point

point(arg1, arg2)函数用于代表地理空间上的某个点的位置，arg1为经度，arg2为纬度

两个坐标都用角度表示

经度值的范围为(-180, 180)，正数表示本初子午线的东边

纬度值的范围为[-90, 90]。整数表示赤道的北边。

通过point的结合，mysql还支持了其他的空间数据类型，例如线性或多边形等(linestring, multilinestring, multipoint, polygon, multipolygon)

st_distance_sphere

可以使用函数st_distance_sphere来计算两个地点的球面距离：

计算出来的距离单位为米.

另外st_distance(g1, g2)也可以算出两点间的距离，但单位为度，如要转换成米，需要乘以(地球半径6371000*pi/180)，或者直接用函数st_distance_sphere

st_within

一个常见的应用需求是找出你周围的目的地（例如餐馆），可以使用该函数。

st_within(g1, g2)： 如果g1在g2的范围内，则返回1，否则返回0

st_contains是st_within的反向操作，表示某个多边形内是否包含某个点。

st_makeenvelope(pt1, pt2)

如果两点相同，返回点pt1

如果两点在经度或纬度上是垂直的，返回linestring

否则，返回矩形

其他

函数名

描述

st_crosses(g1,g2)

当我们需要计算例如两条直线是否相交时，可以使用这个函数。当g1和g2空间上相交时，返回1；如果g1是multipolygon或者polygon，或者g2是point或者multipoint，返回null；其他情况返回0

st_intersects(g1,g2)

用于判断两个空间类型是否存在重叠或者交叉

st_disjoint(g1,g2)

如果不相交，返回1

st_overlaps(g1,g2)

当g1和g2存在重叠时，返回1；这里的重叠指的是两个空间类型的交叉部分产生相同维度的几何图形，但不等于g1或者g2

st_equals(g1,g2)

是否相等

st_touches(g1,g2)

存在重合但不相交时，返回1，例如某个点在一条直线上，返回1

mysql定义了相当完整的函数，以用于进行空间数据类型的比较判断。

geojson

支持将空间数据转换成json类型，或从json类型转换成空间类型

geohash

mysql支持的空间数据类型包括geometry， point， linestring， polygon。其中geometry可以表示任意一种空间类型。其他的几种则需要固定有效的存储格式。

可以使用两种标准来插入数据

wkt

也就是文本格式，在插入数据时直接用文本插入，例如point(1,2),linestring(0 0, 10 10, 20 25, 50 60)之类，内部会转换成特定的格式存储。

在从表中查取数据时，通过函数 st_astext() 转换成wkt的结果格式

wkb

另外一种是wkb标准的数据，可以通过函数st_geomfromwkb进行插入转换。

在从表中查取数据时，通过函数st_asbinary()将结果转换成wkb格式。

数据存储

wl#6455为innodb添加了新类型，server层统一的类型<code>mysql_type_geometry</code>在innodb层被转换成<code>data_geometry</code>（<code>get_innobase_type_from_mysql_type</code>）

相关代码:

<code>cmp_geometry_field</code>: 比较两个gis列的值是否相等

<code>sql/spatial.cc</code>定义了gis数据类型及相关操作

<code>sql/item_geofunc*</code>等文件定义了gis相关函数实现

对于大多数空间类型，mbr记录了能保卫这些空间的最小矩形；对于水平或垂直的直线，mbr实际上记录的是直线；对于point，mbr表示的是一个退化成点的矩形。

其中叶子节点记录包含了mbr以及指向的聚集索引记录，非叶子节点记录包含了指向叶子节点的指针，及对应叶子节点记录所组成的mbr。目前mysql只支持二维数据的索引。

新增相关文件在storage/innodb目录下

gis/gis0geo.cc: 包含r-tree上的底层操作函数

gis/gis0rtree.cc：包含所有r-tree上的操作的接口函数

gis/gis0sea.cc: r-tree的查询接口

lock/lock0prdt.cc: 为r-tree定义的predict lock

创建索引

通过如下sql创建spatial index:

注意作为spatial index的键值的列必须显式定义为not null, 并且目前不支持online 创建spatial index(ref <code>ha_innobase::check_if_supported_inplace_alter</code>). spatial index上只支持定义一个空间数据类型的列。

ssn号

fil_page_file_flush_lsn保留在每个page中，但只有系统页才会用到。在r-tree中被split seq num（ssn）重用，对应的宏为<code>fil_rtree_split_seq_num</code>

ssn实际上是一个索引级别的单调递增的序列号，每发生一次page分裂都进行一次递增。在内存中全局最大ssn存储到dict_index_t::rtr_ssn中，每次取一个新的ssn时对其递增(ref <code>rtr_get_new_ssn_id</code>)

在最初初始化一个page时，其ssn被设置成0(<code>btr_page_create</code>)

当r-rtree发生索引分裂时(<code>rtr_page_split_and_insert</code>)，新创建的右节点继承当前结点的ssn，而当前节点的ssn递增并写到page中。索引分裂完成后，新的ssn被写入到索引的根page中。因此索引的root页总是维护了当前索引上最大的ssn号

r-tree采用了一种和b-tree截然不同的数据检索方式，在检索的过程中，主要通过ssn来判断是否有数据页发生了分裂。

构建索引记录

由于r-tree中存储的并不是真正的数据，而是基于键值列的数据构建的mbr，因此在插入数据前需要进行计算，根据传递过来的wkb格式计算出mbr(<code>rtree_mbr_from_wkb</code>)。

显而易见，通过r-tree检索到的数据，必然还需要回聚集索引获取到真正的地理数据。

检索索引

innodb为r-tree增加了几种新的检索模式，对于诸如“within”, “intersects”, “touches” 或者其他类型的检索请求，可以有效的利用r-tree来进行数据检索。

和b-tree检索不同的是，r-tree的检索更加复杂些，更像一个深度递归搜索。

由于无法通过已有的cursor结构store/restore其在page上的位点，即使是一个普通的查询，一旦touch到某个page，也需要扫描该page上的全部记录。

btree/rtree的检索入口函数均为<code>btr_cur_search_to_nth_level</code>

首先，创建了两个vector来存储扫描page的结果:

btr_cur_t::rtr_info-&gt;path: 存储符合条件的非叶子节点的记录，包括子节点号，r-tree level, 以及对应的ssn号 (ref <code>node_visit</code>)

btr_cur_t::rtr_info-&gt;matches: 用于叶子节点，page内的记录会被拷贝到一个shadow buffer页中，并将指针push到该数组中 (ref <code>struct matched_rec</code>)

因此，当调用row_search_for_mysql检索下一条记录时，不是跟传统btree一样通过cursor直接restore到一个position，，而是直接查阅matches数组去获取下一个符合条件的记录(<code>rtr_pcur_move_to_next</code>)。其中<code>btr_cur_t::rtr_info-&gt;mbr</code>中存储了查询的mbr条件，在定位到root节点时设置(<code>rtr_get_mbr_from_tuple</code>)。

检索r-tree page内是否符合条件： <code>rtr_cur_search_with_match</code>

当一个page上的记录全被检索完毕后，就会回到上一层去搜索更多满足条件的叶子或非叶子节点，相当于典型的深度遍历搜索。而传统的btree则是直接通过指针跳转到下一个叶子节点上。为了获取下一个page，需要从栈中pop出一个节点，然后根据记录的page no获得page，如果发现该page的ssn和存储的节点的值不符合，那一定有一次分裂发生了，右节点页会被加入到路径中 (ref <code>rtr_pcur_getnext_from_path</code>)

插入记录到非叶子节点： <code>btr_insert_on_non_leaf_level_func</code>

当插入新的纪录时，其检索模式为page_cur_rtree_insert。首先在非叶子节点使用page_cur_within模式进行检索。如果没有找到，表示新尝试插入的mbr不在已有的范围中，它会去尝试计算一个扩展已有mbr代价最小的区域

使用另外一个btr_cur_t::rtr_info-&gt;parent_path来存储当前的插入路径(<code>rtr_store_parent_path</code>)。这样如果插入叶子节点个改变了该节点的mbr，新的mbr被提升到其父节点，无须再次调用btr_cur_search_to_nth_level，直接从path中获取。

对于删除操作，使用page_cur_rtree_locate去找到对应的记录。在检索非叶子节点时会转换成page_cur_within，在检索叶子节点时转换成page_cur_le。 与插入记录不同的是，对于删除操作，不允许修改父节点的mbr值，这主要是出于性能考虑。真正的delete只发生在回滚或者purge操作时

change buffer

目前不支持缓存r-tree上的数据变更操作，ibuf被显式禁止了(ref <code>ibuf_should_try</code>)

另外也不支持在r-tree上创建自适应哈希

现有的记录锁系统被继续沿用，但实际上的锁并非锁在特定的记录上，而是默认设置在page的page_heap_no_infimum记录上。可以把predicate lock理解为一个page级别的锁

查询操作负责加predicate lock来防止幻读；通过当前查询的mbr初始化一个predicate lock（<code>lock_init_prdt_from_mbr</code>）并进行加锁操作(<code>lock_prdt_lock</code>)，锁对象类型为<code>lock_prdt_t</code>，其中存储了mbr的值。通过lock_t获取lock_prdt_t的方法参阅<code>lock_get_prdt_from_lock</code>。在查询时从上到下都会加上s predicate lock，但只有叶子节点的锁才被用于检测和插入操作的冲突。

插入操作需要检查predicate lock; 参考函数 <code>btr_cur_ins_lock_and_undo --&gt; lock_prdt_insert_check_and_lock</code>

新增文件lock/lock0prdt.cc定义了predicate lock的接口，还没时间细看，后面再深入理解下。

<a href="https://dev.mysql.com/worklog/task/?id=6745">wl#6745: innodb gis: support dml operation for innodb r-tree index</a>

<a href="https://dev.mysql.com/worklog/task/?id=6968">wl#6968: innodb gis: r-tree index support</a>

<a href="https://www.percona.com/blog/2016/02/03/new-gis-features-in-mysql-5-7/">new-gis-features-in-mysql-5-7</a>

<a href="http://mysqlserverteam.com/category/gis/">官方系列博客</a>

<a href="https://oracleus.activeevents.com/2014/connect/sessiondetail.ww?session_id=4337">oralce开发介绍r-tree的ppt</a>