Systems and Methods for Optimizing Performance of Graph Operations

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.

1 .- 20 . (canceled) 
     
     
         21 . A computer-implemented method, comprising:
 performing, by one or more computers that implement a graph dataflow processing system:
 storing an immutable graph, wherein the immutable graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and each vertex or edge has one or more associated properties; 
 responsive to a request to transform the immutable graph, logging the request without performing the request; 
 responsive to a query for data in the immutable graph:
 performing the request to generate another version of the immutable graph as transformed according to the request; 
 performing the query on the other version of the immutable graph to obtain query results; and 
 returning the query results. 
 
   
     
     
         22 . The computer-implemented method of  claim 21 , wherein:
 logging the request comprises adding an operation requested by the request to an operation queue for the immutable graph; and   performing the request to generate another version of the immutable graph comprises performing a plurality of operations in the operation queue on the immutable graph.   
     
     
         23 . The computer-implemented method of  claim 22 , wherein performing the plurality of operations comprises rearranging an ordering of the plurality of operations in the operation queue. 
     
     
         24 . The computer-implemented method of  claim 22 , wherein performing the plurality of operations comprises combining at least some of the plurality of operations into a compound operation to be performed on the immutable graph. 
     
     
         25 . The computer-implemented method of  claim 22 , wherein performing the plurality of operations comprises canceling at least some of the plurality of operations. 
     
     
         26 . The computer-implemented method of  claim 22 , wherein performing the plurality of operations comprises performing a subset of operations in the operation queue that is relevant to the query and not performing another subset of operations in the operation queue that is not relevant to the query. 
     
     
         27 . The computer-implemented method of  claim 21 , wherein:
 storing the immutable graph comprises storing a first version of a graph object in a version-controlled system; and   further comprising storing the other version of the immutable graph as a second version of the graph object in the version-controlled system.   
     
     
         28 . The computer-implemented method of  claim 27 , wherein storing the second version of the graph object comprises:
 storing a list of differences between the first version and the second version, and a reference to the first version.   
     
     
         29 . The computer-implemented method of  claim 21 , wherein:
 the immutable graph includes structure data that indicates connectivity between the vertices and property data that indicates values of the properties associated with the vertices or the edges; and   storing the immutable graph comprises storing a structure data of the immutable graph separately from property data.   
     
     
         30 . The computer-implemented method of  claim 21 , wherein storing the immutable graph comprises:
 partitioning the immutable graph into a plurality of segments; and   storing the individual ones of the plurality of segments separately.   
     
     
         31 . The computer-implemented method of  claim 30 , wherein:
 partitioning the immutable graph comprises assigning each edge in the immutable graph to a unique segment; and   storing the individual segments comprises storing reference data for the individual segments, wherein the reference data indicates where one or more edges that extend out an individual segment are stored.   
     
     
         32 . The computer-implemented method of  claim 31 , wherein the partitioning is performed to minimize a number of vertices in the immutable graph that are shared by multiple segments. 
     
     
         33 . The computer-implemented method of  claim 30 , wherein:
 storing the individual segments separately comprises storing the individual segments on respective database servers; and   performing the request comprises:
 determining a subset of the segments that are affected by the request; and 
 performing the request without accessing another subset of segments not affected by the request. 
   
     
     
         34 . The computer-implemented method of  claim 21 , wherein the query comprises one or more of: a print command, a copy command, and a view command. 
     
     
         35 . A system, comprising:
 one or more computers that implement a graph dataflow processing system, configured to:
 store an immutable graph, wherein the immutable graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and each vertex or edge has one or more associated properties; 
 responsive to a request to transform the immutable graph, log the request without performing the request; 
 responsive to a query for data in the immutable graph:
 perform the request to generate another version of the immutable graph as transformed according to the request; 
 perform the query on the other version of the immutable graph to obtain query results; and 
 return the query results. 
 
   
     
     
         36 . The system of  claim 35 , wherein:
 to store the immutable graph, the graph dataflow processing system is configured to store a first version of a graph object in a version-controlled system; and   the graph dataflow processing system is further configured to store the other version of the immutable graph as a second version of the graph object in the version-controlled system.   
     
     
         37 . The system of  claim 35 , wherein:
 the graph dataflow processing system includes a plurality of database servers; and   to store the immutable graph, the graph dataflow processing system is configured to:
 partition the immutable graph into a plurality of segments; and 
 store the individual ones of the plurality of segments separately on respective ones of the database servers. 
   
     
     
         38 . The system of  claim 37 , wherein, to perform the request, the graph dataflow processing system is configured to:
 determine a subset of the segments that are affected by the request; and   perform the request without accessing another subset of segments not affected by the request.   
     
     
         39 . One or more non-transitory computer readable storage media storing one or more program instructions that when executed on or across one or more processors that implement a graph dataflow processing system, cause the graph dataflow processing system to:
 store an immutable graph, wherein the immutable graph comprises a set of vertices and a set of edges, each edge connecting a pair of vertices, and each vertex or edge has one or more associated properties;   responsive to a request to transform the immutable graph, log the request without performing the request;   responsive to a query for data in the immutable graph:
 perform the request to generate another version of the immutable graph as transformed according to the request; 
 perform the query on the other version of the immutable graph to obtain query results; and 
 return the query results. 
   
     
     
         40 . The one or more non-transitory computer readable storage media of  claim 39 , wherein:
 to log the request, the one or more program instructions when executed on or across the one or more processors cause the graph dataflow processing system to add an operation requested by the request to an operation queue for the immutable graph; and   to perform the request to generate another version of the immutable graph, the one or more program instructions when executed on or across the one or more processors cause the graph dataflow processing system to perform a plurality of operations in the operation queue on the immutable graph.