Compound indexes 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 a compound store for the graph database, wherein the compound store comprises a set of identity-giving nodes for a set of tuples in the graph database;

accessing the one or more offsets in the compound store to obtain a subset of the tuples matching the query by:

obtaining, from the lookup of the hash map, a first offset in the compound store by matching a key in the query to an entry in the hash map which stores the first offset;

obtaining, from a record at the first offset in an offset store in the compound store, a second offset in the compound structure; and

accessing the subset of the tuples at the second offset in the compound structure;

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

providing the result in a response to the query.

2. The method of claim 1 , wherein the offset store comprises:

a compound type associated with the compound structure; and

the second offset which specifies a storage location in the compound structure.

3. The method of claim 1 , wherein using the first offset in the compound store to access the subset of the tuples matching the query in the compound structure comprises:

accessing the subset of the tuples at the first offset in the compound structure.

4. The method of claim 1 , wherein the compound structure comprises:

an additional offset of a tuple in a log-based representation of the graph database;

the set of identity-giving nodes in the tuple, wherein each identity-giving node in the set of identity-giving nodes contains a predicate-object pair that represents a corresponding attribute used to define the tuple; and

an add/delete indication in the tuple that identifies the tuple as an addition of the tuple to the graph database or a deletion of the tuple from the graph database.

5. The method of claim 4 , wherein the compound structure further comprises:

one or more attributes that reference the tuple.

6. The method of claim 5 , wherein each node in the set of identity-giving nodes comprises a predicate-object pair.

7. The method of claim 1 , wherein a header of the compound structure comprises:

a second offset of a next page in the compound structure; and

a third offset of an edge store in the graph database.

8. 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 compound store.

9. The method of claim 8 , wherein the one or more keys comprise at least one of:

an identity-giving node; and

a compound type.

10. The method of claim 1 , wherein prior to obtaining the second offset from the record, the method further includes using the first offset to identify the record in the offset store, wherein the record includes an identity-giving node and a set of compound types.

11. The method of claim 10 , wherein obtaining, from the record in the offset store in the compound store, the second offset in the compound structure includes:

identifying from the set of compound types, a compound type which matches a value in the query; and

obtaining the second offset in the offset store based on the identified compound type which is mapped to the second offset, wherein the second offset is mapped to the subset of the tuples.

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 one or more processes for providing 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 a compound store for the graph database, wherein the compound store comprises a set of identity-giving nodes for a set of tuples in the graph database;

accessing the one or more offsets in the compound store to obtain a subset of the tuples matching the query by:

obtaining, from the lookup of the hash map, a first offset in the compound store by matching a key in the query to an entry in the hash map which stores the first offset;

obtaining, from a record at the first offset in an offset store in the compound store, a second offset in the compound structure; and

accessing the subset of the tuples at the second offset in the compound structure;

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

providing the result in a response to the query.

13. The apparatus of claim 12 , wherein the offset store comprises:

a compound type associated with the compound structure; and

the second offset which specifies a storage location in the compound structure.

14. The apparatus of claim 12 , wherein using the first offset in the compound store to access the subset of the tuples matching the query in the compound structure comprises:

accessing the subset of the tuples at the first offset in the compound structure.

15. The apparatus of claim 12 , wherein the compound structure comprises:

an additional offset of a tuple in a log-based representation of the graph database;

the set of identity-giving nodes in the tuple, wherein each identity-giving node in the set of identity-giving nodes contains a predicate-object pair that represents a corresponding attribute used to define the tuple; and

an add/delete indication in the tuple that identifies the tuple as an addition of the tuple to the graph database or a deletion of the tuple from the graph database.

16. 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 compound store.

17. A system, comprising:

one or more processors;

a management module comprising instructions that, when executed by the one or more processors, 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 instructions that, when executed by the one or more processors, 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 a compound store for the graph database, wherein the compound store comprises a set of identity-giving nodes for a set of tuples in the graph database;

accessing the one or more offsets in the compound store to obtain a subset of the tuples matching the query by:

obtaining, from the lookup of the hash map, a first offset in the compound store by matching a key in the query to an entry in the hash map which stores the first offset;

obtaining, from a record at the first offset in an offset store in the compound store, a second offset in the compound structure; and

accessing the subset of the tuples at the second offset in the compound structure;

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

providing the result in a response to the query.