Systems and methods for optimizing performance of graph operations

• US 10,262,078 B2
• Filed: 02/10/2015
• Issued: 04/16/2019
• Est. Priority Date: 02/10/2014
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Gu, Haijie, Low, Yucheng, Guestrin, Carlos
• Primary Examiner(s): Gortayo, Dangelino N
• Application Number:
  US14/619,025
• Publication Number:
  US 20150227582A1
• Time in Patent Office: 1,526 Days
• Field of Search: 707713, 707703, 707798, 707802, 707812
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/958 Organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking

Abstract

A method of optimizing graph operations is performed by a computing system. The method comprises: (1) receiving a first request to perform a first operation on a first graph, where the first graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and each vertex having one or more associated properties; (2) logging the first request, but not performing the first operation; (3) receiving a second request to perform a second operation; (4) logging the second request, but not performing the second operation; (5) receiving a query for data from the first graph, where the data includes property values for one or more vertices; (6) in response to the query: (a) generating a second graph by optimizing and performing the first and second operations; and (b) returning data responsive to the query, where the returned data is based on the second graph.

Claims

1. A method of optimizing graph operations, performed by a computing system having one or more processors and memory, the method comprising:

receiving a first request to perform a first operation on a first graph, wherein the first graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and wherein each vertex has one or more associated properties;

logging the first request, but not performing the requested first operation;

receiving a second request to perform a second operation on the first graph;

logging the second request, but not performing the requested second operation;

receiving a query for data in the first graph including property values for one or more vertices in the first graph; and

in response to the query;

optimizing a performance of the first and second operations;

generating a second graph from the first graph, wherein the generation comprises performing the first and second requested operations on the first graph according to the optimization;

performing the query on the second graph to retrieve data responsive to the query contained in the second graph including property values for one or more vertices in the second graph; and

returning the data responsive to the query.

2. The method of claim 1, wherein performing the first and second requested operations comprises performing both the first and second operations at the same time.

3. The method of claim 1, wherein:

optimizing the performance of the first and second operations comprises generating a third operation by combining the first and second requested operations; and

generating the second graph comprises performing the third operation on the first graph, wherein the second graph is equivalent to a graph generated by sequentially performing the first operation and the second operation on the first graph.

4. The method of claim 1, wherein both the first graph and the second graph are immutable.

5. The method of claim 4, wherein the second graph represents a second version of the first graph in a version-control schema.

6. The method of claim 1, wherein the first graph comprises a first graph structure and a first set of properties;

wherein the first graph structure includes the set of vertices and the set of edges; and

wherein the first set of properties includes the one or more associated properties corresponding to each vertex in the set of vertices.

7. The method of claim 6, wherein the second graph utilizes the first graph structure;

and

wherein generating the second graph comprises generating a second set of properties by performing the first and second requested operations on the first set of properties.

8. The method of claim 6, the method further comprising storing the first graph.

9. The method of claim 8, wherein storing the first graph comprises storing the first graph structure separately from the first set of properties.

10. The method of claim 8, wherein storing the first graph comprises:

partitioning the first graph into a plurality of sections; and

storing each section separately.

11. The method of claim 10, wherein generating the second graph comprises performing the first and second requested operations on only a subset of the plurality of sections of the first graph.

12. The method of claim 1, wherein each edge in at least a subset of the set of edges has one or more associated properties;

and wherein the data further includes property values for one or more edges in the subset of edges.

13. A system, comprising:

one or more processors;

memory; and

one or more programs stored in the memory for execution by the one or more processors, the one or more programs comprising instructions for;

receiving a first request to perform a first operation on a first graph, wherein the first graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and wherein each vertex has one or more associated properties;

logging the first request, but not performing the requested first operation;

receiving a second request to perform a second operation on the first graph;

logging the second request, but not performing the requested second operation;

receiving a query for data from the first graph including property values for one or more vertices in the first graph; and

in response to the query;

optimizing a performance of the first and second operations;

generating a second graph, wherein the generation comprises performing the first and second requested operations on the first graph according to the optimization;

performing the query on the second graph to retrieve data responsive to the query contained in the second graph including property values for one or more vertices in the second graph; and

returning the data responsive to the query.

14. The system of claim 13, wherein the instructions for optimizing the performance of the first and second operations and generating the second graph comprise instructions for:

generating a third operation by combining the first and second requested operations; and

generating the second graph by performing the third operation on the first graph, wherein the second graph is equivalent to a graph generated by sequentially performing the first operation and the second operation on the first graph.

15. The system of claim 13, wherein both the first graph and the second graph are immutable.

16. The system of claim 13, the one or more programs further comprising instructions for storing the first graph, wherein storing the first graph comprises partitioning the first graph into a plurality of sections and storing each section separately.

17. The system of claim 13, wherein the first graph comprises a first graph structure and a first set of properties;

wherein the first graph structure includes the set of vertices and the set of edges; and

wherein the first set of properties includes the one or more associated properties corresponding to each vertex in the set of vertices.

18. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer system having one or more processors and memory storing one or more programs for execution by the one or more processors, the one or more programs comprising instructions for:

receiving a first request to perform a first operation on a first graph, wherein the first graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and wherein each vertex has one or more associated properties;

logging the first request, but not performing the requested first operation;

receiving a second request to perform a second operation on the first graph;

logging the second request, but not performing the requested second operation;

receiving a query for data from the first graph including property values for one or more vertices in the first graph;

in response to the query;

optimizing a performance of the first and second operations;

generating a second graph, wherein the generation comprises performing the first and second requested operations on the first graph according to the optimization;

performing the query on the second graph to retrieve data responsive to the query contained in the second graph including property values for one or more vertices in the second graph; and

returning the data responsive to the query.

19. The storage medium of claim 18, wherein the instructions for optimizing the performance of the first and second operations and generating the second graph comprise instructions for:

generating a third operation by combining the first and second requested operations; and

generating the second graph by performing the third operation on the first graph, wherein the second graph is equivalent to a graph generated by sequentially performing the first operation and the second operation on the first graph.

20. The storage medium of claim 18, wherein both the first graph and the second graph are immutable.