Geospatial Data 在 Nebula Graph 中的实践

本文首发于 Nebula Graph Community 公众号

Geospatial Data 在 Nebula Graph 中的实践

本文主要介绍了地理空间数据(Geospatial Data)以及它在 Nebula Graph 中的具体实践。

Geospatial Data 在 Nebula Graph 中的实践

什么是 Geospatial Data

地理空间数据(Geospatial Data)是包含简单地理空间要素信息的数据,比如点(point)、线(linestring)、多边形(polygon),或是其他更复杂的形状。

Nebula Graph 在 2.6 版本中引入了对 Geospatial Data 完整的支持,包括地理空间数据的存储、计算,以及索引。Nebula Graph 目前支持 Geography 类型的地理空间数据,Geography 类型是建模在地球空间坐标系上由经纬度坐标对表示的地理位置信息。

Geospatial Data -- 地理空间数据使用

创建 Schema

这里仅以 Tag 为例,当然 Edgetype 上同样可以将 Geography 类型作为属性列。

Nebula 目前支持点、线、多边形三种空间数据类型。下面介绍一下如何如何创建 Geography 类型属性以及如何插入地理空间数据到 Nebula 中。

CREATE TAG any_shape(geo geography);
CREATE TAG only_point(geo geography(point));
CREATE TAG only_linestring(geo geography(linestring));
CREATE TAG only_polygon(geo geography(polygon));

geography 属性后面没有指定具体的地理形状信息时,代表该列可以存储任意地理形状的数据;当指定形状类型时,则代表只能存储该形状的地理数据,比如 geography(point),就代表该列只能存储 point 形状的地理位置信息。

插入数据

向 Tag any_shapegeo 列插入数据:

INSERT VERTEX any_shape(geo) VALUES "101":(ST_GeogFromText("POINT(120.12 30.16)"));
INSERT VERTEX any_shape(geo) VALUES "102":(ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));
INSERT VERTEX any_shape(geo) VALUES "103":(ST_GeogFromText("POLYGON((75.3 45.4, 112.5 53.6, 122.7 25.5, 93.9 28.6, 75.3 45.4))"));

向 Tag only_pointgeo 列插入数据:

INSERT VERTEX only_point(geo) VALUES "201":(ST_Point(120.12,30.16)"));;

向 Tag only_linestringgeo 插入数据:

INSERT VERTEX only_linestring(geo) VALUES "302":(ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));

向 Tag only_polygongeo 列插入数据:

INSERT VERTEX only_polygon(geo) VALUES "403":(ST_GeogFromText("POLYGON((75.3 45.4, 112.5 53.6, 122.7 25.5, 93.9 28.6, 75.3 45.4))"));

当插入地理数据形状不符合该列地理形状要求时,会报错无法插入:

(root@nebula) [geo]> INSERT VERTEX only_polygon(geo) VALUES "404":(ST_GeogFromText("POINT((75.3 45.4))"));
[ERROR (-1005)]: Wrong value type: ST_GeogFromText("POINT((75.3 45.4))")

我们可以看到地理空间数据插入方法比较奇特,和 int、string、bool 等基本类型的插入很不一样。

我们以 ST_GeogFromText("POINT(120.12 30.16)") 为例,ST_GeogFromText 是一个地理位置信息解析函数,它接受一个 string 类型的 WKT(Well-Known Text)标准格式表示的地理位置数据:

POINT(120.12 30.16) 代表一个东经 120°12′,北纬 30°16′ 的地理位置点。ST_GeogFromText 函数会从 wkt 参数中解析并构造一个 geography 数据对象,然后 INSERT 语句会将其以 WKB(Well-Known Binary)标准存储在 Nebula 中。

Geospatial functions -- 地理空间函数

Nebula 支持的地理空间函数可以分为以下几大类:

  • 构造函数
    • ST_Point(longitude, latitude),根据一对经纬度构造一个 geography point 对象
  • 解析函数
    • ST_GeogFromText(wkt_string),从 wkt 文本中解析 geography 对象
    • ST_GeogFromWKB(wkb_string),从 wkb 文本中解析 geography 对象 # 尚未正式支持,因为 Nebula还未支持二进制字符串
  • 格式设置函数
    • ST_AsText(geogrpahy),将 geogrpahy 对象以 wkt 文本格式输出
    • ST_AsBinary(geography),将 geography 对象以 wkb 文本格式输出 # 尚未正式支持,因为 Nebula 还未支持二进制字符串
  • 转换函数
    • ST_Centroid(geography),计算 geography 对象的重心,重心是一个 geography point 对象
  • 谓词函数
    • ST_Intersects(geography_1, geography_2),判断两个 geography 对象是否相交
    • ST_Covers(geography_1, geography_2),判断第一个 geography 对象是否完全覆盖第二个
    • ST_CoveredBy(geography_1, geography_2),ST_Covers 的反义词
    • ST_DWithin(geography_1, geography_2, distance_in_meters),判断两个 geography 对象的最短距离是否小于给定距离
  • 度量函数
    • ST_Distance(geography_1, geography_2),计算两个 geography 对象之间的距离

这些函数接口遵循 OpenGIS Simple Feature Access 以及 ISO SQL/MM 标准,具体用法参见Nebula 文档

Geospatial index -- 地理空间索引

什么是地理空间索引?

地理空间索引用于基于空间谓词函数的的地理形状的快速过滤,如:ST_Intersects、ST_Covers 等。

Nebula 使用Google S2库做空间索引。

S2 库将地球表面投影到一个外切的正方体上,然后对正方体的每一个正方形表面递归地进行 n 次四等,最后使用一条空间填充曲线--希尔伯特曲线去连接这些小正方格子的中心。

当 n 无穷大时,这条希尔伯特曲线就几乎填满了正方形。

S2 库使用的是 30 阶的希尔伯特曲线。

Geospatial Data 在 Nebula Graph 中的实践

如下图, 是用希尔伯特曲线填充地地球表面的示意图:

Geospatial Data 在 Nebula Graph 中的实践

可以看到,地球表面最终被这些希尔伯特曲线划分成了一个个单元格。对于地球表面的任意地理形状,比如一个城市、一条河流、一个人的位置我们都可以用若干个这样的格子去完全覆盖住这个地理形状。

每个格子都有一个唯一的 int64 的 CellID 来标识。因此,地理对象的空间索引就是构建完全覆盖该地理形状的 S2 格子的集合。

当构建地理空间对象的索引时,会构造一个完全覆盖被索引对象的不同 S2 单元格的集合。基于空间谓词函数的索引查询通过查找覆盖所查询对象的 S2 单元格的集合与覆盖被索引对象的 S2 单元格之间的交集,来快速过滤掉大量不相关的地理对象。

创建 geography 索引

CREATE TAG any_shape_geo_index on any_shape(geo)

对于形状为 point 的地理数据,可以用一个 level 为 30 的 S2 单元格来表示它,因此一个 point 对应一个索引条目;对于形状为 linestring 和 polygon 的地理数据,我们使用多个不同 level 的 S2 单元格来覆盖,因此会对应多个索引条目;

空间索引会用来加速所有 geo 谓词的查找速度,比如对于如下语句

LOOKUP ON any_shape WHERE ST_Intersects(any_shape.geo, ST_GeogFromText("LINESTRING(3 8, 4.7 73.23)"));

当 any_shape 的 geo 列上没有空间索引时,该语句会先将 any_shape 的所有数据读到内存,然后用来计算是否和点(3.0, 8.0)相交,这个计算的开销一般是比较昂贵的。当 any_shape 的数据量较大时,计算开销将难以接受。

而当 any_shape 的 geo 列有空间索引时,该语句会首先用空间索引过滤掉绝大部分和该线绝对不相交的数据,最终读到内存的还是会有部分可能相交的,因此还需要进行一次计算。这样空间索引就以很小的代价快速过滤掉了大部分不可能相交的数据,最终进行精确过滤的只有少部分,极大的降低了计算开销。


交流图数据库技术?加入 Nebula 交流群请先填写下你的 Nebula 名片,Nebula 小助手会拉你进群~~

上一篇:AndroidManifest.xml文件报Activity supporting ACTION_VIEW is not set as BROWSABLE


下一篇:No.18 Is It a Tree