Practice of geospatial data in Nepal graph

This article was first published in Nebula Graph Community official account

This paper mainly introduces geospatial data （Geospatial Data） And it's in Nebula Graph Specific practices in .

Geospatial Data stay Nebula Graph Practice in

What is? Geospatial Data

Geospatial data （Geospatial Data） It is data containing simple geospatial feature information , For example （point）、 Line （linestring）、 polygon （polygon）, Or other more complex shapes .

Nebula Graph stay 2.6 The version introduces the right Geospatial Data Full support , Including the storage of geospatial data 、 Calculation , And index .Nebula Graph At present, we support Geography Type of geospatial data ,Geography Type refers to the geographic location information represented by longitude and latitude coordinate pairs on the earth space coordinate system .

Geospatial Data -- Geospatial data use

establish Schema

Here is just Tag For example , Of course Edgetype It can also be used to Geography Type as attribute column .

Nebula Current support points 、 Line 、 Three types of spatial data for polygons . Here is how to create Geography Type properties and how to insert geospatial data into Nebula in .

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));

When geography When no specific geographic shape information is specified after the attribute , Represents that the column can store data of any geographical shape ; When specifying the shape type , It means that only the geographic data of the shape can be stored , such as geography(point), This means that the column can only store point Geographic location information of shapes .

insert data

towards Tag any_shape Of geo Insert data into columns ：

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))"));

towards Tag only_point Of geo Insert data into columns ：

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

towards Tag only_linestring Of geo insert data ：

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

towards Tag only_polygon Of geo Insert data into columns ：

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))"));

When the inserted geographic data shape does not meet the geographic shape requirements of the column , An error will be reported and cannot be inserted :

([email protected]) [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))")

We can see that the geospatial data insertion method is quite strange , and int、string、bool And other basic types .

We use ST_GeogFromText("POINT(120.12 30.16)") For example ,ST_GeogFromText Is a geographic location information analysis function , It accepts a string Type of WKT（Well-Known Text） Geographic location data in standard format ：

POINT(120.12 30.16) Represents an Eastern longitude 120°12′, North latitude 30°16′ The geographical location of .ST_GeogFromText The function will start from wkt Parameter and construct a geography Data objects , then INSERT Statement will replace it with WKB（Well-Known Binary） Standards are stored in Nebula in .

Geospatial functions -- Geospatial functions

Nebula The supported geospatial functions can be divided into the following categories :

• Constructors

- ST\_Point(longitude, latitude), Construct a according to a pair of longitude and latitude  geography point  Object parsing function 

- ST\_GeogFromText(wkt\_string), from  wkt  Parsing in text  geography  object 
- ST\_GeogFromWKB(wkb\_string), from  wkb  Parsing in text  geography  object  #  There is no formal support for , because  Nebula Binary string formatting functions are not yet supported 

- ST\_AsText(geogrpahy), take  geogrpahy  Object to  wkt  Output in text format 
- ST\_AsBinary(geography), take  geography  Object to  wkb  Output in text format  #  There is no formal support for , because  Nebula  Binary string conversion functions are not yet supported 

- ST\_Centroid(geography), Calculation  geography  The center of gravity of the object , The center of gravity is a  geography point  Object predicate function 

- ST\_Intersects(geography\_1, geography\_2), Whether two  geography  Whether objects intersect 
- ST\_Covers(geography\_1, geography\_2), Judge the first  geography  Whether the object completely covers the second 
- ST\_CoveredBy(geography\_1, geography\_2),ST\_Covers  The antonym of 
- ST\_DWithin(geography\_1, geography\_2, distance\_in\_meters), Whether two  geography  Whether the shortest distance of the object is less than the given distance measurement function 

- ST\_Distance(geography\_1, geography\_2), Calculate two  geography  The distance between objects 

These function interfaces follow OpenGIS Simple Feature Access as well as ISO SQL/MM standard , Please refer to Nebula file

Geospatial index -- Geospatial index

What is a geospatial index ?

Geospatial index is used for fast filtering of geographical shapes based on spatial predicate function , Such as ：ST_Intersects、ST_Covers etc. .

Nebula Use Google S2 library Do spatial indexing .

S2 The library projects the earth's surface onto an circumscribed Cube , And then recursively on each square surface of the cube n Fourth order , Finally, use a space filling curve -- Hilbert curve To connect the centers of these little squares .

When n At infinity , This Hilbert curve almost fills the square .

S2 The library uses 30 Hilbert curve of order .

Here's the picture , It is a schematic diagram of the earth's surface filled with Hilbert curve ：

You can see , The earth's surface is finally divided into cells by these Hilbert curves . For any geographical shape of the earth's surface , Like a city 、 A river 、 We can use several such grids to completely cover the geographical shape of a person's position .

Each grid has a unique int64 Of CellID To mark . therefore , The spatial index of geographical objects is to build a spatial index that completely covers the geographical shape S2 A collection of lattices .

When building an index of geospatial objects , Will construct a different... That completely covers the indexed object S2 Set of cells . The index query based on spatial predicate function finds the S2 The collection of cells and the S2 The intersection between cells , To quickly filter out a large number of unrelated geographical objects .

establish geography Indexes

CREATE TAG any_shape_geo_index on any_shape(geo)

For shapes like point Geographic data for , You can use a level by 30 Of S2 Cells to represent it , So a point Corresponding to an index entry ; For shapes like linestring and polygon Geographic data for , We use several different level Of S2 Cells to cover , Therefore, it will correspond to multiple index entries ;

Spatial indexes will be used to speed up all geo Predicate lookup speed , For example, for the following statement

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

When any_shape Of geo When there is no spatial index on the column , This statement will first put any_shape All data read to memory , Then it is used to calculate whether it is connected with the point (3.0, 8.0) The intersection , The cost of this calculation is usually expensive . When any_shape When the amount of data is large , Computational overhead will be unacceptable .

And when any_shape Of geo When a spatial index is listed , The statement will first filter out most of the data that is absolutely disjoint with the line by using the spatial index , In the end, some of those that read into the memory may intersect , Therefore, a calculation is required . In this way, the spatial index can quickly filter out most of the data that cannot be intersected at a very small cost , Finally, only a few of them are accurately filtered , It greatly reduces the computing cost .