Compound indexes for graph databases

Patent metadata

Field	Value
Publication number	US-10445370-B2
Application number	US-201715618371-A
Country	US
Kind code	B2
Filing date	Jun 9, 2017
Priority date	Jun 9, 2017
Publication date	Oct 15, 2019
Grant date	Oct 15, 2019

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.

First claim

What is claimed is:

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 s

Assignees

• Linkedin Corp
• Microsoft Technology Licensing Llc

Inventors

• Rodriguez Andrew
• Meyer Scott M
• Carter Andrew J
• Moustafa Walaa Eldin M

Classifications

• G06F16/9024 Primary

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title

• G06F16/9014

  hash tables · CPC title

• G06F16/90335

  Query processing · CPC title