Compound indexes for graph databases

• US 10,445,370 B2
• Filed: 06/09/2017
• Issued: 10/15/2019
• Est. Priority Date: 06/09/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Rodriguez, Andrew, Meyer, Scott M., Carter, Andrew J., Moustafa, Walaa Eldin M.
• Primary Examiner(s): Chbouki, Tarek
• Application Number:
  US15/618,371
• Publication Number:
  US 20180357330A1
• Time in Patent Office: 858 Days
• Field of Search: None
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

The disclosed embodiments provide a system for processing queries of a graph database. During operation, the system executes 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. When a query of the graph database is received, the system performs a lookup of a hash map to obtain one or more offsets into a compound store for the graph database, which includes identity-giving nodes for a set of tuples in the graph database. Next, the system accesses the offset(s) in the compound store to obtain a subset of tuples matching the query. The system then uses the subset of tuples to generate a result of the query and provides the result in a response to the query.

Claims

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.