EDGE STORE DESIGNS FOR GRAPH DATABASES

1 . A method, comprising:

executing a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and

when a query of the graph database is received, using one or more of the processes to process the query by:

performing a lookup of a hash map to obtain one or more offsets into an edge store for the graph database, wherein the edge store comprises a one-linkage structure and a two-linkage structure;

accessing the one or more offsets in the edge store to obtain a subset of the edges matching the query;

using the subset of the edges to generate a result of the query; and

providing the result in a response to the query.

2 . The method of claim 1 , wherein accessing the one or more offsets into the edge store to obtain the subset of edges matching the query comprises:

obtaining, from the lookup of the index, a first offset in the edge store; and

using the first offset in the edge store to access the subset of the edges matching the query in the edge store.

3 . The method of claim 2 , wherein using the first offset in the edge store to access the subset of the edges matching the query in the edge store comprises:

obtaining, from a record at the first offset in a first one-linkage structure in the edge store, a second offset in a second one-linkage structure in the edge store; and

accessing the subset of the edges at the second offset in the second one-linkage structure.

4 . The method of claim 3 , wherein the first one-linkage structure comprises:

a second linkage associated with the second one-linkage structure; and

the second offset.

5 . The method of claim 4 , wherein the second one-linkage structure comprises:

one or more offsets of the subset of the edges in a log-based representation of the graph database;

a third linkage for the subset of the edges; and

an add/delete indication.

6 . The method of claim 2 , wherein using the first offset in the edge store to access the subset of the edges matching the query in the edge store comprises:

accessing the subset of the edges at the first offset in a two-linkage structure in the edge store.

7 . The method of claim 6 , wherein the two-linkage structure comprises:

one or more offsets of the subset of the edges in a log-based representation of the graph database;

one or more additional linkages for the subset of the edges; and

an add/delete indication.

8 . The method of claim 1 , wherein using the subset of the edges to generate the result of the query comprises:

upon determining that a page in the edge store cannot accommodate an edge in the subset of the edges:

allocating an additional page at a front of the edge store;

writing the edge to the additional page; and

including, in the additional page, a reference to the page.

9 . The method of claim 1 , wherein performing the lookup of the hash map comprises:

matching a hash of one or more keys from the query to a hash map entry in the hash map; and

obtaining, from the hash map entry, an offset into the edge store.

10 . The method of claim 1 , wherein the edges in the edge store are stored in order of increasing offset in a log-based representation of the graph database.

11 . The method of claim 1 , wherein the subset of the edges comprises:

a subject;

a predicate;

an object; and

an offset.

12 . An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to:

execute a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and

when a query of the graph database is received, use one or more of the processes to process the query by:

performing a lookup of a hash map to obtain one or more offsets into an edge store for the graph database, wherein the edge store comprises a one-linkage structure and a two-linkage structure; and

accessing the one or more offsets in the edge store to obtain a subset of the edges matching the query;

using the subset of the edges to generate a result of the query; and

providing the result in a response to the query.

13 . The apparatus of claim 12 , wherein accessing the one or more offsets into the edge store to obtain the subset of edges matching the query comprises:

obtaining, from the lookup of the index, a first offset in the edge store; and

using the first offset in the edge store to access the subset of the edges matching the query in the edge store.

14 . The apparatus of claim 13 , wherein using the first offset in the edge store to access the subset of the edges matching the query in the edge store comprises:

obtaining, from a record at the first offset in a first one-linkage structure in the edge store, a second offset in a second one-linkage structure in the edge store; and

accessing the subset of the edges at the second offset in the second one-linkage structure.

15 . The apparatus of claim 13 , wherein using the first offset in the edge store to access the subset of the edges matching the query in the edge store comprises:

accessing the subset of the edges at the first offset in a two-linkage structure in the edge store.

16 . The apparatus of claim 12 , wherein using the subset of the edges to generate the result of the query comprises:

upon determining that a page in the edge store cannot accommodate an edge in the subset of the edges:

allocating an additional page at a front of the edge store;

writing the edge to the additional page; and

including, in the additional page, a reference to the page.

17 . The apparatus of claim 12 , wherein performing the lookup of the hash map comprises:

matching a hash of one or more keys from the query to a hash map entry in the hash map; and

obtaining, from the hash map entry, an offset into the edge store.

18 . The apparatus of claim 12 , wherein the edges in the edge store are stored in order of increasing offset in a log-based representation of the graph database.

19 . A system, comprising:

a management module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to execute a set of processes for processing queries of a graph database storing a graph, wherein the graph comprises a set of nodes, a set of edges between pairs of nodes in the set of nodes, and a set of predicates; and

a processing module comprising a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to use one or more of the processes to process the query by:

performing a lookup of a hash map to obtain one or more offsets into an edge store for the graph database, wherein the edge store comprises a one-linkage structure and a two-linkage structure; and

accessing the one or more offsets in the edge store to obtain a subset of the edges matching the query;

using the subset of the edges to generate a result of the query; and

providing the result in a response to the query

20 . The system of claim 19 , wherein accessing the one or more offsets into the edge store to obtain the subset of edges matching the query comprises:

obtaining, from the lookup of the index, a first offset in the edge store; and

using the first offset in the edge store to access the subset of the edges matching the query in the edge store.