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>