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

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

  1. InnoDB支持Spatial Index，可以对空间数据类型建立索引
  2. 更丰富的功能，支持计算两点之间的球面距离函数st_distance_sphere，新增支持GeoHash和GeoJSON；
  3. 基于Boost.Geometry库实现GIS

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

常用函数

关于空间数据类型的分析计算函数，可以从官方文档上获得全部信息，以下是自己初次实验的记录。

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

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

mysql> SELECT ST_ASTEXT(ST_GEOMFROMTEXT("POINT(1 2)"));
+------------------------------------------+
| ST_ASTEXT(ST_GEOMFROMTEXT("POINT(1 2)")) |
+------------------------------------------+
| POINT(1 2)                               |
+------------------------------------------+
1 row in set (0.00 sec)

POINT

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

  • 两个坐标都用角度表示
  • 经度值的范围为(-180, 180)，正数表示本初子午线的东边
  • 纬度值的范围为[-90, 90]。整数表示赤道的北边。

通过POINT的结合，MySQL还支持了其他的空间数据类型，例如线性或多边形等(LineString, MultiLineString, MultiPoint, Polygon, MultiPolygon)

ST_DISTANCE_SPHERE

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

mysql> select st_distance_sphere(point(-78.7698947, 35.890334), point(122.38657, 37.60954)) as distance;
+--------------------+
| distance           |
+--------------------+
| 11556620.032685472 |
+--------------------+
1 row in set (0.00 sec)

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

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

ST_WITHIN
一个常见的应用需求是找出你周围的目的地（例如餐馆），可以使用该函数。
ST_WITHIN(g1, g2)： 如果g1在g2的范围内，则返回1，否则返回0

mysql> set @g1 =  ST_GeomFromText('POINT(1.558064 110.341903)');
Query OK, 0 rows affected (0.00 sec)

mysql> set @g2 = ST_GeomFromText('POLYGON((1.558467 110.341781, 1.558081 110.342317, 1.557764 110.34175, 1.558467 110.341781 ))');
Query OK, 0 rows affected (0.00 sec)

mysql> select st_within(@g1, @g2);
+---------------------+
| st_within(@g1, @g2) |
+---------------------+
|                   1 |
+---------------------+
1 row in set (0.00 sec)

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

mysql> select st_contains(@g2, @g1);
+-----------------------+
| st_contains(@g2, @g1) |
+-----------------------+
|                     1 |
+-----------------------+
1 row in set (0.00 sec)

ST_MakeEnvelope(pt1, pt2)

如果两点相同，返回点pt1
如果两点在经度或纬度上是垂直的，返回Linestring
否则，返回矩形

mysql> SET @pt1 = ST_GeomFromText('POINT(1 1)');
Query OK, 0 rows affected (0.00 sec)

mysql> SET @pt2 = ST_GeomFromText('POINT(1 1)');
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT ST_AsText(ST_MakeEnvelope(@pt1, @pt2));
+----------------------------------------+
| ST_AsText(ST_MakeEnvelope(@pt1, @pt2)) |
+----------------------------------------+
| POINT(1 1)                             |
+----------------------------------------+
1 row in set (0.00 sec)

mysql> SET @pt2 = ST_GeomFromText('POINT(2 1)');
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT ST_AsText(ST_MakeEnvelope(@pt1, @pt2));
+----------------------------------------+
| ST_AsText(ST_MakeEnvelope(@pt1, @pt2)) |
+----------------------------------------+
| LINESTRING(1 1,2 1)                    |
+----------------------------------------+
1 row in set (0.00 sec)

mysql> SET @pt2 = ST_GeomFromText('POINT(2 2)');
Query OK, 0 rows affected (0.00 sec)

mysql> SELECT ST_AsText(ST_MakeEnvelope(@pt1, @pt2));
+----------------------------------------+
| ST_AsText(ST_MakeEnvelope(@pt1, @pt2)) |
+----------------------------------------+
| POLYGON((1 1,2 1,2 2,1 2,1 1))         |
+----------------------------------------+
1 row in set (0.00 sec)

其他

函数名 描述
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类型转换成空间类型

mysql> SET @jdata = ST_AsGeoJSON(ST_GeomFromText('POINT(11.11111 12.22222)'),2);
Query OK, 0 rows affected (0.00 sec)

mysql> select @jdata;
+--------------------------------------------------+
| @jdata                                           |
+--------------------------------------------------+
| {"type": "Point", "coordinates": [11.11, 12.22]} |
+--------------------------------------------------+
1 row in set (0.00 sec)

mysql> SELECT ST_AsText(ST_GeomFromGeoJson(@jdata));
+---------------------------------------+
| ST_AsText(ST_GeomFromGeoJson(@jdata)) |
+---------------------------------------+
| POINT(11.11 12.22)                    |
+---------------------------------------+
1 row in set (0.00 sec)

具体参考官方文档 及官方博客描述

GeoHash

Geohash用于将代表位置的经纬度编码成一个字符串，支持WGS 84 Coordinate System

mysql> SELECT ST_GeoHash(90,90,10);
+----------------------+
| ST_GeoHash(90,90,10) |
+----------------------+
| ypbpbpbpbp           |
+----------------------+
1 row in set (0.00 sec)

mysql> SELECT ST_GeoHash(POINT(90,90),10);
+-----------------------------+
| ST_GeoHash(POINT(90,90),10) |
+-----------------------------+
| ypbpbpbpbp                  |
+-----------------------------+
1 row in set (0.00 sec)

mysql> SELECT ST_GeoHash(POINT(90,90),5);
+----------------------------+
| ST_GeoHash(POINT(90,90),5) |
+----------------------------+
| ypbpb                      |
+----------------------------+
1 row in set (0.00 sec)

/ hash值转换为Point. /
mysql> SELECT ST_AsText(ST_PointFromGeoHash('ypbpb', 0));
+--------------------------------------------+
| ST_AsText(ST_PointFromGeoHash('ypbpb', 0)) |
+--------------------------------------------+
| POINT(90 90)                               |
+--------------------------------------------+
1 row in set (0.00 sec)

具体如何使用参阅官方文档及博客

GIS数据存储

MySQL支持的空间数据类型包括GEOMETRY， POINT， LINESTRING， POLYGON。其中GEOMETRY可以表示任意一种空间类型。其他的几种则需要固定有效的存储格式。

另外支持的几种格式，则是对应上述的类型集合，包括MULTIPOINT， MULTILINESTRING， MULTIPOLYGON， GEOMETRYCOLLECTION。具体参阅文档

可以使用两种标准来插入数据
WKT
也就是文本格式，在插入数据时直接用文本插入，例如POINT(1,2),LINESTRING(0 0, 10 10, 20 25, 50 60)之类，内部会转换成特定的格式存储。
在从表中查取数据时，通过函数 ST_AsText() 转换成WKT的结果格式

WKB
另外一种是WKB标准的数据，可以通过函数ST_GeomFromWKB进行插入转换。
例如POINT(1 1)包含21个字节

0101000000000000000000F03F000000000000F03F
The sequence consists of these components:

Byte order:   01            / little-endian or big-endian storage /
WKB type:     01000000      /* Values from 1 through 7 indicate Point, LineString,
                               Polygon, MultiPoint, MultiLineString, MultiPolygon,
                               and GeometryCollection. */
X coordinate: 000000000000F03F
Y coordinate: 000000000000F03F

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

数据存储

在WL#6455中完成了对InnoDB GIS数据类型的支持。

尽管MySQL支持这么多种空间数据格式，在Server层对应的列类型为Field_geom，继承自Field_blob。在InnoDB存储引擎中实际使用的存储为blob类型，存储的数据格式为WKB格式，再加上4字节的SRID。实际上之前版本曾支持过使用固定长度列来存储POINT数据，因为POINT具有固定格式，并且长度不大，没必要使用blob类型(WL#6942, commit)，但后来不知为何取消掉了

WL#6455为InnoDB添加了新类型，Server层统一的类型MYSQL_TYPE_GEOMETRY在InnoDB层被转换成DATA_GEOMETRY（get_innobase_type_from_mysql_type）

相关代码:
cmp_geometry_field: 比较两个GIS列的值是否相等
sql/spatial.cc定义了GIS数据类型及相关操作
sql/item_geofunc*等文件定义了GIS相关函数实现

R-TREE

和普通的BTREE不同，R-TREE专门用来表示空间数据类型，其存储的记录类型是该空间数据所能表示的最小边界的矩形，简称MBR

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

一颗R-TREE可用下图表示(R-TREE)

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

在官方WL#6968实现了对R-TREE的支持，代码见该Commit

新增相关文件在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:

mysql> CREATE TABLE t1 (a POINT, b GEOMETRY NOT NULL, SPATIAL INDEX(b));
Query OK, 0 rows affected (0.00 sec)

/ 只能在NOT NULL的列上创建SPATIAL INDEX /
mysql> ALTER TABLE t1 ADD SPATIAL INDEX(a);
ERROR 1252 (42000): All parts of a SPATIAL index must be NOT NULL

注意作为SPATIAL INDEX的键值的列必须显式定义为NOT NULL, 并且目前不支持ONLINE 创建SPATIAL INDEX(ref ha_innobase::check_if_supported_inplace_alter). spatial index上只支持定义一个空间数据类型的列。

SSN号

FIL_PAGE_FILE_FLUSH_LSN保留在每个PAGE中，但只有系统页才会用到。在R-TREE中被SPLIT SEQ NUM（SSN）重用，对应的宏为FIL_RTREE_SPLIT_SEQ_NUM

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

在最初初始化一个PAGE时，其SSN被设置成0(btr_page_create)

当R-RTREE发生索引分裂时(rtr_page_split_and_insert)，新创建的右节点继承当前结点的SSN，而当前节点的SSN递增并写到PAGE中。索引分裂完成后，新的SSN被写入到索引的根PAGE中。因此索引的ROOT页总是维护了当前索引上最大的SSN号

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

构建索引记录

由于R-TREE中存储的并不是真正的数据，而是基于键值列的数据构建的MBR，因此在插入数据前需要进行计算，根据传递过来的WKB格式计算出MBR(rtree_mbr_from_wkb)。

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

检索索引

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

/ These search mode is for search R-tree index. /
        PAGE_CUR_CONTAIN                = 7,
        PAGE_CUR_INTERSECT              = 8,
        PAGE_CUR_WITHIN                 = 9,
        PAGE_CUR_DISJOINT               = 10,
        PAGE_CUR_MBR_EQUAL              = 11,
        PAGE_CUR_RTREE_INSERT           = 12,
        PAGE_CUR_RTREE_LOCATE           = 13,
        PAGE_CUR_RTREE_GET_FATHER       = 14

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

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

BTREE/RTREE的检索入口函数均为btr_cur_search_to_nth_level

首先，创建了两个vector来存储扫描page的结果:
1. btr_cur_t::rtr_info->path: 存储符合条件的非叶子节点的记录，包括子节点号，r-tree level, 以及对应的SSN号 (ref node_visit)
2. btr_cur_t::rtr_info->matches: 用于叶子节点，Page内的记录会被拷贝到一个shadow buffer页中，并将指针push到该数组中 (ref struct matched_rec)

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

检索R-TREE Page内是否符合条件： rtr_cur_search_with_match

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

插入记录到非叶子节点： btr_insert_on_non_leaf_level_func

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

使用另外一个btr_cur_t::rtr_info->parent_path来存储当前的插入路径(rtr_store_parent_path)。这样如果插入叶子节点个改变了该节点的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 ibuf_should_try)

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

Predicate Lock

由于对于多维数据并没有严格的顺序概念，很难定义next-key，也就无法使用InnoDB传统的Next-key Lock来防止幻读。 InnoDB引入了Predicate Lock的概念。

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

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

插入操作需要检查Predicate Lock; 参考函数 btr_cur_ins_lock_and_undo --> lock_prdt_insert_check_and_lock

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

参考文档

WL#6745: InnoDB GIS: support DML operation for InnoDB R-tree Index
WL#6968: InnoDB GIS: R-tree index support
new-gis-features-in-mysql-5-7
官方系列博客
oralce开发介绍R-TREE的PPT

时间： 2024-10-29 03:17:32

MySQL · 引擎特性 · 初识 MySQL GIS 及 InnoDB R-TREE的相关文章

MySQL · 引擎特性 · InnoDB 文件系统之文件物理结构

综述 从上层的角度来看,InnoDB层的文件,除了redo日志外,基本上具有相当统一的结构,都是固定block大小,普遍使用的btree结构来管理数据.只是针对不同的block的应用场景会分配不同的页类型.通常默认情况下,每个block的大小为 UNIV_PAGE_SIZE,在不做任何配置时值为16kb,你还可以选择在安装实例时指定一个块的block大小.对于压缩表,可以在建表时指定block size,但在内存中表现的解压页依旧为统一的页大小. 从物理文件的分类来看,有日志文件.主系统表空间文

MySQL · 引擎特性 · InnoDB文件系统管理

综述 从上层的角度来看,InnoDB层的文件,除了redo日志外,基本上具有相当统一的结构,都是固定block大小,普遍使用的btree结构来管理数据.只是针对不同的block的应用场景会分配不同的页类型.通常默认情况下,每个block的大小为UNIV_PAGE_SIZE,在不做任何配置时值为16kb,你还可以选择在安装实例时指定一个块的block大小. 对于压缩表,可以在建表时指定block size,但在内存中表现的解压页依旧为统一的页大小. 从物理文件的分类来看,有日志文件,主系统表空间文

MySQL · 引擎特性 · InnoDB 崩溃恢复过程

在前面两篇文章中,我们详细介绍了 InnoDB redo log 和 undo log 的相关知识,本文将介绍 InnoDB 在崩溃恢复时的主要流程. 本文代码分析基于 MySQL 5.7.7-RC 版本,函数入口为 innobase_start_or_create_for_mysql,这是一个非常冗长的函数,本文只涉及和崩溃恢复相关的代码. 在阅读本文前,强烈建议翻阅下面两篇文章: 1. MySQL · 引擎特性 · InnoDB undo log 漫游 2. MySQL · 引擎特性 · I

MySQL · 引擎特性 · InnoDB 事务子系统介绍

前言 在前面几期关于 InnoDB Redo 和 Undo 实现的铺垫后,本节我们从上层的角度来阐述 InnoDB 的事务子系统是如何实现的,涉及的内容包括:InnoDB的事务相关模块.如何实现MVCC及ACID.如何进行事务的并发控制.事务系统如何进行管理等相关知识.本文的目的是让读者对事务系统有一个较全面的理解. 由于不同版本对事务系统都有改变,本文的所有分析基于当前GA的最新版本MySQL5.7.9,但也会在阐述的过程中,顺带描述之前版本的一些内容.本文也会介绍5.7版本对事务系统的一些优

MySQL · 引擎特性 · DROP TABLE之binlog解析

Drop Table的特殊之处 Drop Table乍一看,与其它DDL 也没什么区别,但当你深入去研究它的时候,发现还是有很多不同.最明显的地方就是DropTable后面可以紧跟多个表,并且可以是不同类型的表,这些表还不需要显式指明其类型,比如是普通表还是临时表,是支持事务的存储引擎的表还是不支持事务的存储引擎的表等.这些特殊之处对于代码实现有什么影响呢?对于普通表,无论是创建还是删除,数据库都会产生相应的binlog日志,而对于临时表来说,记录binlog日志就不是必须的.对于采用不同存储引

MySQL · 引擎特性 · 像NOSQL那样使用MySQL

前言 最近Release的MySQL5.7.12增加了新的协议支持,通过X Plugin实现,同时增加了新的客户端API,开发者可以通过API来把MySQL作为document store的服务端,可以完成和MongoDB类似的document操作,例如支持CRUD等操作,但底层存储依然支持传统数据库的ACID,操作本身在底层也被扩展成标准SQL.从目前的MySQL来看,NOSQL和传统数据库的界限越来越小.目前这个特性还未Production Ready,建议仅用于测试环境. 本文只是记录下学

MySQL · 引擎特性 · InnoDB undo log 漫游

本文是对整个Undo生命周期过程的阐述,代码分析基于当前最新的MySQL5.7版本.本文也可以作为了解整个Undo模块的代码导读.由于涉及到的模块众多,因此部分细节并未深入. 前言 Undo log是InnoDB MVCC事务特性的重要组成部分.当我们对记录做了变更操作时就会产生undo记录,Undo记录默认被记录到系统表空间(ibdata)中,但从5.6开始,也可以使用独立的Undo 表空间. Undo记录中存储的是老版本数据,当一个旧的事务需要读取数据时,为了能读取到老版本的数据,需要顺着u

MySQL · 引擎特性 · InnoDB Fulltext简介

前言 从MySQL5.6版本开始支持InnoDB引擎的全文索引,语法层面上大多数兼容之前MyISAM的全文索引模式. 所谓全文索引,是一种通过建立倒排索引,快速匹配文档的方式.MySQL支持三种模式的全文检索模式: 第一种是自然语言模式(IN NATURAL LANGUAGE MODE),即通过MATCH AGAINST 传递某个特定的字符串来进行检索. 第二种是布尔模式(IN BOOLEAN MODE),可以为检索的字符串增加操作符,例如"+"表示必须包含,"-"

MySQL · 引擎特性 · InnoDB 大字段压缩

前言 当用户的数据量比较大时,通常需要对数据进行压缩,以减少磁盘占用.InnoDB目前有两种方式来实现这一目的. 第一种是传统的数据压缩,通过指定row_format及key_block_size,能够将用户表压缩到指定的page size并进行存储,默认使用zlib.这种压缩方式使用比较简单,但也是诟病较多的, 代码陈旧,相关代码基本上几个大版本都没发生过变化,一些优化点还是从facebook移植过来的(集中在在5.6版本中, 不过现在fb已经放弃优化InnoDB压缩了,转而聚集在自家压缩更好