A database index is a data structure used to improve the speed of data retrieval within a database at the cost of additional writes and storage space for maintaining the index data structure.
Armed with deep understanding of their data model and use-case, users can decide which data to index and, by doing so, significantly improve their data retrieval efficiency
At Memgraph, we support two types of indexes:
- label index
- label-property index
Label indexing is NOT enabled by default in Memgraph, i.e., Memgraph will not automatically index labeled data. Therefore, it is up to the user to perform the indexing explicitly. By doing so, one can optimize queries that fetch nodes by label:
Indexes can also be created on data with a specific combination of label and property, hence the name label-property index. This operation needs to be specified by the user and should be used with a specific data model and use-case in mind.
For example, suppose we are storing information about certain people in our
database and we are often interested in retrieving their age. In that case,
it might be beneficial to create an index on nodes labeled as
have a property named
age. We can do so by using the following language
After the creation of that index, those queries will be more efficient due to
the fact that Memgraph's query engine will not have to fetch each
and check whether the property exists. Moreover, even if all nodes labeled as
:Person had an
age property, creating such index might still prove to be
beneficial. The main reason is that entries within that index are kept sorted
by property value. Queries such as the following are therefore more efficient:
Index based retrieval can also be invoked on queries with
For instance, the following query will have the same effect as the previous
Naturally, indexes will also be used when filtering based on less than or greater than comparisons. For example, filtering all minors (persons under 18 years of age under Croatian law) using the following query will use index based retrieval:
Bear in mind that
WHERE filters could contain arbitrarily complex expressions
and index based retrieval might not be used. Nevertheless, we are continually
improving our index usage recognition algorithms.
Information about available indexes can be retrieved by using the following syntax:
The results of this query will be all of the labels and label-property pairs that Memgraph currently indexes.
Created indexes can also be deleted by using the following syntax:
Dropping an index will instruct all active transactions to abort as soon as possible, and it will wait for them to finish. Once all transaction have finished, it will drop the index.
The central part of our index data structure is a highly-concurrent skip list. Skip lists are probabilistic data structures that allow fast search within an ordered sequence of elements. The structure itself is built in layers where the bottom layer is an ordinary linked list that preserves the order. Each higher level can be imagined as a highway for layers below.
The implementation details behind skip list operations are well documented
in the literature and are out of scope for this article. Nevertheless, we
believe that it is important for more advanced users to understand the following
implications of this data structure (
n denotes the current number of elements
in a skip list):
- Average insertion time is
- Average deletion time is
- Average search time is
- Average memory consumption is