The term Index in Nebula Graph is quite similar to the same term in relational databases, but they are not exactly the same. I noticed that some Nebula Graph users are often confused when getting started with Nebula Graph. Typically, people want to know what exactly Nebula Graph Index is, when should they use it, and how it impacts the performance of Nebula Graph.
Today I’m going to walk you through the Index concept in Nebula Graph and hopefully, this article will answer these questions.
Let’s get started!
What Is Nebula Graph Index Exactly
To put it short, Nebula Graph Index is only used when the vertextID is not specified, or only when properties of vertices or edges are defined in the query conditions.
An index is only used in a starting entry of a graph query. If a query is in the pattern: (a->b->c, where c is with the condition “foobar”) since the only filter
condition-foobar is on
c, this query under the hood will start to look for
c, and then it walks reversely through the
b, and finally to
a. Thus, the Nebula Graph Index will be used and only be possibly used when locating c.
The Index Is Used Only To Seek Starting Points
We know that in RDBMS, indexing is to create a duplicate of sorted data to enable QUERY with conditional filtering on the sorted data, in order to accelerate the query in reads and it also brings additional data writes.
Note: in RDBMS/Tabular DB, indexing some columns means to create extra data that are sorted on those columns to make a query with those columns’ conditions to be scanned faster, rather than scanning from the original table data sorted based on the key only.
In Nebula Graph, the index is to create a duplicate of sorted Vertex/Edge PROP DATA to locate the starting point of a QUERY.
Not all queries relied on the index, here are some example queries, where the starting points are only defined using conditions, rather than VertextIDs. Let’s call them
pure property condition starting queries:
#### Queries relying on Nebula Graph Index # query 0 pure-property-condition-start query LOOKUP ON tag1 WHERE col1 > 1 AND col2 == "foo" YIELD tag1.col1 as col1, tag1.col3 as col3; # query 1 pure-property-condition-start query MATCH (v:player name: 'Tim Duncan' )-->(v2:player) RETURN v2.player.name AS Name;
query 0 and
query 1, the pattern is to “Find VID/EDGE only based on given property conditions”.
On the contrary, the starting point is VertexID based instead in
query 2 and
#### Queries not based on Nebula Graph Index # query 2, walk query starting from given vertex VID: "player100" GO FROM "player100" OVER follow REVERSELY YIELD src(edge) AS id | GO FROM $-.id OVER serve WHERE properties($^).age > 20 YIELD properties($^).name AS FriendOf, properties($$).name AS Team; # query 3, walk query starting from given vertex VID: "player101" or "player102" MATCH (v:player name: 'Tim Duncan' )--(v2) WHERE id(v2) IN ["player101", "player102"] RETURN v2.player.name AS Name;
If we look into
query 1 and
query 3, which shared the same condition on vertices on
tag:player, which are both
name: 'Tim Duncan' , they are differentiated in starting points:
query 3, the index is not required as the query will start from the known vertex ID in
["player101", "player102"] and thus:
- It’ll directly fetch vertex data from
v2‘s vertex IDs
- then to
GetNeighbors():walkthrough edges of
v2, GetVertices() for the next hop:
vand filter based on the property:
query 1, the query has to start from
v due to no known vertex IDs being provided:
- It’ll do IndexScan() first to find all vertices only with the property condition of
name: 'Tim Duncan'
- Then, GetNeighbors(): walkthrough edges of
v, GetVertices() for the next hop:
Now, we know the whole point that matters here is whether we know the
vertexID. And the above differences could be shown in their execution plans with PROFILE or EXPLAIN like the following:
Why Nebula Graph Index Is an Enabler Rather than an Accelerator
Can’t those queries be done without indexes?
It’s possible in theory with a full scan but disabled without an index.
The reason is that Nebula Graph stores data in a distributed and graph-oriented way, the full scan of data was considered too expensive to be allowed.
Note: from v3.0, it’s possible to do TopN Scan without index, where the
LIMIT <n>is used, this is different from the full scan case(index is a must), which will be explained later.
MATCH (v:player name: 'Tim Duncan' )-->(v2:player) RETURN v2.player.name AS Name LIMIT 3;
Why Starting Point Only
Index data is not used in the traversal. It could confuse us to think of an index as sorting data based on properties, does it accelerate the traversal with property condition filtering? The answer is no.
In Nebula Graph, the data is structured in a way to enable fast graph-traversal, which is already indexed/sorted on vertex ID(for both vertex and edge) in the raw data, where traversal(underlying in storage, it’s calling
GetNeighbors interface) of the given vertex is cheap and fast due to the persistent storage.
So in summary:
Nebula Graph Index is sorted property data to find the starting vertex or edge on given pure property conditions.
Facts on Nebula Graph Index
To understand more details/limitations/cost of Nebula, let’s reveal more about its design. Here are some facts in short:
- Index Data is stored and shared together with Vertex Data
- It’s Left Match based only: It’s RocksDB Prefix Scan under the hood
- Effect on write and read path(to see its cost):
- Write Path: Extra Data written + Extra Read request introduced
- Read Path: RBO(Rule-based optimization), Fan-Out(to all shards)
- Data Full Scan LIMIT Sample(not full scan) is supported without index
The key info can be seen in one of my sketch notes:
We should notice that only the left match is supported in pure-property-condition-start queries. For queries like wildcard or regular expression, Full-text Index/Search is to be used, where an external elastic search is integrated with Nebula: please check Nebula Graph Full text index for more.
Within this sketch note, more highlights are:
- Use index only when we have to, as it’s costly in write cases and if the limit N sample is the only needed case and it’s fast enough, we can use that instead.
- The index is left to match
- composite index order matters and should be created carefully.
- for a full-text search use case, use a full-text index instead.
How To Use the Index
We should always refer to the documentation, and I just put some highlights on this here:
To create an index on a tag or edge type to specify a list of props in the order that we need.
If an index was created after existing data was inserted, we need to trigger an index asynchronously to rebuild the job, as the index data will be written in a synchronous way only when the index is created.
We can see the index status after
REBUILD INDEXis issued.
Queries levering index could be LOOKUP, and with the pipeline, in most cases, we will do follow-up graph-walk queries like:
LOOKUP ON player WHERE player.name == "Kobe Bryant" YIELD id(vertex) AS VertexID, properties(vertex).name AS name | GO FROM $-.VertexID OVER serve YIELD $-.name, properties(edge).start_year, properties(edge).end_year, properties($$).name;
Or in a MATCH query like this, under the hood, v will be searched on index and v2 will be walked by default graph data structure without involving index.
MATCH (v:playername:"Tim Duncan")-->(v2:player) RETURN v2.player.name AS Name;
Finally, Let’s Recap
- The index is to sort Property DATA to enable finding starting point on a given Pure Property Condition(no VertexID provided)
- The index is not for traversal
- The index is left match, not for full-text search
- The index has cost on WRITE
- Remember to REBUILD after
CREATE INDEXon existing data