Query execution systems and methods

• US 8,886,631 B2
• Filed: 06/29/2012
• Issued: 11/11/2014
• Est. Priority Date: 06/04/2010
• Status: Active Grant

• Current Assignee: Yale University
• Original Assignee: Yale University
• Inventors: Abadi, Daniel, Huang, Jiewen
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US13/538,336
• Publication Number:
  US 20120310916A1
• Time in Patent Office: 865 Days
• Field of Search: 707/713, 707/714
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

System, method and computer program product for processing a query are disclosed. Query processing includes partitioning the stored data into a plurality of partitions based on at least one vertex in the plurality of vertexes, storing at least another triple in the plurality of triples on the at least one node, assigning, based on the triple containing the at least one vertex, at least one partition in the plurality of partitions corresponding to the triple to at least one node in the plurality of nodes, and processing, based on the assigning, the query by processing the plurality of partitions.

Claims

1. A computer-implemented method for processing a query, having at least one query parameter, of data stored on a plurality of nodes in accordance with a graph data model, each node including at least one of a processor and a memory, the graph data model includes a plurality of vertexes configured to be logically connected using a plurality of edges, each vertex in the plurality of vertexes is configured to correspond to a portion of data, wherein the portion of data is configured to be stored at a node in the plurality of nodes and at least one vertex in the plurality of vertexes is configured to be logically connected to at least another vertex in the plurality of vertexes using at least one edge in the plurality of edges, wherein two vertexes logically connected by an edge are configured to form a triple in a plurality of triples, the method comprising:

partitioning the stored data into a plurality of partitions based on at least one vertex in the plurality of vertexes and at least one logical connection of the at least one vertex to at least another vertex;

storing at least another triple in the plurality of triples on the at least one node;

determining other vertexes logically connected to the at least one vertex;

selectively replicating triples containing the determined vertex to the at least one node for processing;

assigning, based on the triple containing the at least one vertex, at least one partition in the plurality of partitions corresponding to the triple to at least one node in the plurality of nodes; and

processing, based on the assigning, the query by processing the plurality of partitions;

wherein at least one of the partitioning, the storing, the determining, the selectively replicating, the assigning, and the processing is performed on at least one processor.

2. The method according to claim 1, further comprising

determining whether triples already existing in the partition and the replicated triples include duplicative triples;

and

excluding duplicative triples from the processing.

3. The method according to claim 1, wherein the graph data model is a directed graph data model.

4. The method according to claim 3, wherein the graph data model includes a resource description framework data.

5. The method according to claim 1, wherein the processing further comprises excluding processing of triples contained within partitions wherein the triples have a predetermined type.

6. The method according to claim 1, further comprising

determining whether the at least one vertex is configured to be logically connected to other vertexes contained in the plurality of nodes using a plurality of logical connections, wherein the plurality of logical connections is configured to exceed a predetermined threshold;

and

excluding, based on the determining, the at least one other vertex having the plurality of logical connections exceeding the predetermined threshold from the partitioning.

7. The method according to claim 1, further comprising

determining whether the received query can be processed in parallel on the plurality of nodes;

and

dividing, based on the determining, the received query into a plurality of sub-queries.

8. The method according to claim 1, wherein the plurality of partitions includes a plurality of disjoint partitions.

9. The method according to claim 1, wherein the triple is stored in a memory of at least one node in the plurality of nodes.

10. The method according to claim 1, wherein the at least one query parameter includes at least one of the following:

at least one constant parameter and at least one variable parameter.

11. The method according to claim 10, further comprising

determining a sub-graph pattern of the query parameters, wherein two query parameters and a logical connection between the two query parameters are configured to form a query triple in a plurality of query triples;

comparing the sub-graph pattern of the query parameters to the graph data model containing the plurality of vertexes by comparing the plurality of triples in the graph data model to the plurality of query triples;

determining, based on the comparing,

whether an identical match exists between at least one triple in the plurality of triples in the graph data model and at least one query triple in the plurality of query triples when the query triple includes two constant parameters configured to match two vertexes in the at least one triple in the plurality of triples in the graph data model;

a vertex in the plurality of vertexes in the graph data model to match a variable parameter in a query triple in the plurality of query triples, the query triple including a constant parameter and the variable parameter and the constant parameter is configured to match another vertex in the plurality vertexes.

12. The method according to claim 10, wherein the variable parameter includes at least one of the following:

at least one edge in the plurality of edges and at least one vertex in the plurality of vertexes;

wherein a sub-graph query can be configured to include at least one of the following;

at least one constant vertex, at least one constant edge, at least one variable vertex, and at least one variable edge, wherein at least one constant vertex and at least one constant edge is configured to match at least one vertex and at least one edge in the graph data mode, respectively.

13. The method according to claim 1, wherein the processing is configured to be performed in parallel using Apache Hadoop.

14. A system for processing a query, having at least one query parameter, of data stored on a plurality of nodes in accordance with a graph data model, each node including at least one of a processor and a memory, the graph data model includes a plurality of vertexes configured to be logically connected using a plurality of edges, each vertex in the plurality of vertexes is configured to correspond to a portion of data, wherein the portion of data is configured to be stored at a node in the plurality of nodes and at least one vertex in the plurality of vertexes is configured to be logically connected to at least another vertex in the plurality of vertexes using at least one edge in the plurality of edges, wherein two vertexes logically connected by an edge are configured to form a triple in a plurality of triples, the system comprising:

at least one programmable processor; and

a non-transitory machine-readable medium storing instructions that, when executed by the at least one programmable processor, cause the at least one programmable processor to perform operations comprising;

partition the stored data into a plurality of partitions based on at least one vertex in the plurality of vertexes and at least one logical connection of the at least one vertex to at least another vertex;

storing at least another triple in the plurality of triples on the at least one node;

determining other vertexes logically connected to the at least one vertex;

selectively replicating triples containing the determined vertex to the at least one node for processing;

assigning, based on the triple containing the at least one vertex, at least one partition in the plurality of partitions corresponding to the triple to at least one node in the plurality of nodes; and

processing, based on the assigning, the query by processing the plurality of partitions.

15. The system according to claim 14, wherein the operations further comprise

determining whether triples already existing in the partition and the replicated triples include duplicative triples;

and

excluding duplicative triples from the processing.

16. The system according to claim 14, wherein the graph data model is a directed graph data model.

17. The system according to claim 16, wherein the graph data model includes a resource description framework data.

18. The system according to claim 14, wherein the processing further comprises excluding processing of triples contained within partitions wherein the triples have a predetermined type.

19. The system according to claim 14, wherein the operations further comprise

determining whether the at least one vertex is configured to be logically connected to other vertexes contained in the plurality of nodes using a plurality of logical connections, wherein the plurality of logical connections is configured to exceed a predetermined threshold;

and

excluding, based on the determining, the at least one other vertex having the plurality of logical connections exceeding the predetermined threshold from the partitioning.

20. The system according to claim 14, wherein the operations further comprise

determining whether the received query can be processed in parallel on the plurality of nodes;

and

dividing, based on the determining, the received query into a plurality of sub-queries.

21. The system according to claim 14, wherein the plurality of partitions includes a plurality of disjoint partitions.

22. The system according to claim 14, wherein the triple is stored in a memory of at least one node in the plurality of nodes.

23. The system according to claim 14, wherein the at least one query parameter includes at least one of the following:

at least one constant parameter and at least one variable parameter.

24. The system according to claim 23, wherein the operations further comprise

determining a sub-graph pattern of the query parameters, wherein two query parameters and a logical connection between the two query parameters are configured to form a query triple in a plurality of query triples;

comparing the sub-graph pattern of the query parameters to the graph data model containing the plurality of vertexes by comparing the plurality of triples in the graph data model to the plurality of query triples;

determining, based on the comparing,

whether an identical match exists between at least one triple in the plurality of triples in the graph data model and at least one query triple in the plurality of query triples when the query triple includes two constant parameters configured to match two vertexes in the at least one triple in the plurality of triples in the graph data model;

a vertex in the plurality of vertexes in the graph data model to match a variable parameter in a query triple in the plurality of query triples, the query triple including a constant parameter and the variable parameter and the constant parameter is configured to match another vertex in the plurality vertexes.

25. The system according to claim 23, wherein the variable parameter includes at least one of the following:

at least one edge in the plurality of edges and at least one vertex in the plurality of vertexes;

wherein a sub-graph query can be configured to include at least one of the following;

at least one constant vertex, at least one constant edge, at least one variable vertex, and at least one variable edge, wherein at least one constant vertex and at least one constant edge is configured to match at least one vertex and at least one edge in the graph data mode, respectively.

26. The system according to claim 14, wherein the processing is configured to be performed in parallel using Apache Hadoop.

27. A computer program product for processing a query, having at least one query parameter, of data stored on a plurality of nodes in accordance with a graph data model, each node including at least one of a processor and a memory, the graph data model includes a plurality of vertexes configured to be logically connected using a plurality of edges, each vertex in the plurality of vertexes is configured to correspond to a portion of data, wherein the portion of data is configured to be stored at a node in the plurality of nodes and at least one vertex in the plurality of vertexes is configured to be logically connected to at least another vertex in the plurality of vertexes using at least one edge in the plurality of edges, wherein two vertexes logically connected by an edge are configured to form a triple in a plurality of triples, the computer program product comprising a non-transitory machine-readable medium storing instructions that, when executed by at least one programmable processor, cause the at least one programmable processor to perform operations comprising:

partitioning the stored data into a plurality of partitions based on at least one vertex in the plurality of vertexes and at least one logical connection of the at least one vertex to at least another vertex;

storing at least another triple in the plurality of triples on the at least one node;

determining other vertexes logically connected to the at least one vertex;

selectively replicating triples containing the determined vertex to the at least one node for processing;

assigning, based on the triple containing the at least one vertex, at least one partition in the plurality of partitions corresponding to the triple to at least one node in the plurality of nodes; and

processing, based on the assigning, the query by processing the plurality of partitions.

28. The computer program product according to claim 27, wherein the operations further comprise

determining whether triples already existing in the partition and the replicated triples include duplicative triples;

and

excluding duplicative triples from the processing.

29. The computer program product according to claim 27, wherein the graph data model is a directed graph data model.

30. The computer program product according to claim 29, wherein the graph data model includes a resource description framework data.

31. The computer program product according to claim 27, wherein the processing further comprises excluding processing of triples contained within partitions wherein the triples have a predetermined type.

32. The computer program product according to claim 27, wherein the operations further comprise

determining whether the at least one vertex is configured to be logically connected to other vertexes contained in the plurality of nodes using a plurality of logical connections, wherein the plurality of logical connections is configured to exceed a predetermined threshold;

and

excluding, based on the determining, the at least one other vertex having the plurality of logical connections exceeding the predetermined threshold from the partitioning.

33. The computer program product according to claim 27, wherein the operations further comprise

determining whether the received query can be processed in parallel on the plurality of nodes;

and

dividing, based on the determining, the received query into a plurality of sub-queries.

34. The computer program product according to claim 27, wherein the plurality of partitions includes a plurality of disjoint partitions.

35. The computer program product according to claim 27, wherein the triple is stored in a memory of at least one node in the plurality of nodes.

36. The computer program product according to claim 27, wherein the at least one query parameter includes at least one of the following:

at least one constant parameter and at least one variable parameter.

37. The computer program product according to claim 36, wherein the operations further comprise

determining a sub-graph pattern of the query parameters, wherein two query parameters and a logical connection between the two query parameters are configured to form a query triple in a plurality of query triples;

comparing the sub-graph pattern of the query parameters to the graph data model containing the plurality of vertexes by comparing the plurality of triples in the graph data model to the plurality of query triples;

determining, based on the comparing,

whether an identical match exists between at least one triple in the plurality of triples in the graph data model and at least one query triple in the plurality of query triples when the query triple includes two constant parameters configured to match two vertexes in the at least one triple in the plurality of triples in the graph data model;

a vertex in the plurality of vertexes in the graph data model to match a variable parameter in a query triple in the plurality of query triples, the query triple including a constant parameter and the variable parameter and the constant parameter is configured to match another vertex in the plurality vertexes.

38. The computer program product according to claim 36, wherein the variable parameter includes at least one of the following:

at least one edge in the plurality of edges and at least one vertex in the plurality of vertexes;

wherein a sub-graph query can be configured to include at least one of the following;

at least one constant vertex, at least one constant edge, at least one variable vertex, and at least one variable edge, wherein at least one constant vertex and at least one constant edge is configured to match at least one vertex and at least one edge in the graph data mode, respectively.

39. The computer program product according to claim 27, wherein the processing is configured to be performed in parallel using Apache Hadoop.