Duplication elimination in depth based searches for distributed systems
A node of a multi-node computing system determines, in a particular instance of evaluating the graph query, that a vertex that is to be evaluated next is stored on a second node separate from the first node and generates a first message based on one or more first results of the particular instance of evaluating the graph query. The node determines, in a subsequent instance of evaluating the graph query, that a vertex to be evaluated next is stored on the second node. The node generates a merged message based on the first message and one or more subsequent results of the second instance of evaluating the graph query. The node sends the merged message to the second node.
1 . A method comprising:
evaluating against graph data a graph query that specifies a particular pattern to match, wherein said graph data is accessible on a multi-node computing system, wherein said graph data comprises a plurality of vertices and a plurality of edges, wherein said evaluating the graph query comprises:
determining, at a first node of the multi-node computing system, in a particular instance of evaluating the graph query, that one or more first vertices on the first node match a first portion of the graph query and that a second vertex that is to be evaluated next is stored on a second node separate from the first node, wherein first results of the particular instance of evaluating the graph query identify the one or more first vertices as a first set of matching vertices and the second vertex as a next vertex to be evaluated;
generating a first message based on the first results;
determining, at the first node in a subsequent instance of evaluating the graph query, that one or more third vertices on the first node match the first portion of the graph query and that a fourth vertex to be evaluated next is stored on the second node, wherein subsequent results of the subsequent instance of evaluating the graph query identify the one or more third vertices as a set of matching vertices and the fourth vertex as a next vertex to be evaluated;
in response to determining that the fourth vertex to be evaluated next is stored on the second node, merging, by the first node, the subsequent results with the first results in the first message to form merged results, wherein merging the subsequent results with the first results in the first message results in generating a merged message; and
sending the merged message from the first node to the second node; and
providing a graph query result based at least in part on evaluation of the graph query by the second node based on the merged results.
2 . The method of claim 1 , wherein:
generating the first message comprises storing the second vertex in a next vertex field of the first message and storing the one or more first vertices in a matched vertices field of the first message,
the one or more third vertices are different vertices from the one or more first vertices,
the fourth vertex is a same vertex as the second vertex, and
merging the subsequent results with the first results comprises adding the one or more third vertices to the matched vertices field of the first message.
3 . The method of claim 1 , wherein:
generating the first message comprises storing the second vertex in a next vertex field of the first message and storing the one or more first vertices in a matched vertices field of the first message,
the one or more third vertices are the same vertices as the one or more first vertices,
the fourth vertex is a different vertex than the second vertex, and
merging the subsequent results with the first results comprises adding the fourth vertex to the next vertex field of the first message.
4 . The method of claim 1 , wherein:
the particular instance of evaluating the graph query evaluates a first stage of a depth-first traversal of the graph data,
the subsequent instance of evaluating the graph query evaluates a second stage of the depth-first traversal of the graph data,
merging the subsequent results with the first results is performed in response to the first stage being the same stage as the second stage.
5 . The method of claim 1 , wherein the merged message comprises a stage field, a next vertex field, and a matched vertices field.
6 . The method of claim 1 , further comprising:
after generating the merged message, determining that a size of the merged message is greater than or equal to a threshold value and, in response, sending the merged message to the second node.
7 . The method of claim 1 , wherein:
the particular instance of evaluating the graph query and the subsequent instance of evaluating the graph query are performed by a first thread in the first node of the multi-node computing system,
the merged message is a first thread-level merged message associated with the first thread,
said evaluating the graph query further comprises:
generating, by the first node, a second thread-level merged message based on one or more second results of evaluating the graph query by a second thread in the first node of the multi-node computing system; and
generating a node-level merged message based on the first thread-level merged message and the second thread-level merged message.
8 . The method of claim 7 , wherein generating the node-level merged message comprises performing deduplication of fields in the node-level merged message.
9 . The method of claim 1 , wherein:
the graph query is an aggregation query comprising a COUNT aggregation, and
merging the subsequent results with the first results comprises incrementing a COUNT value in the merged message.
10 . The method of claim 1 , wherein:
the graph query is an aggregation query comprising a MAX aggregation, and
merging the subsequent results with the first results comprises determining that the subsequent results of the first portion of the graph query comprise a first value for the MAX aggregation that is greater than a second value for the MAX aggregation from the first results of the first portion of the graph query and, in response, replacing the second value in the merged message with the first value.
11 . The method of claim 1 , wherein:
the graph query is an aggregation query comprising a MIN aggregation, and
merging the subsequent results with the first results comprises determining that the subsequent results of the first portion of the graph query comprise a first value for the MIN aggregation that is less than a second value for the MIN aggregation from the first results of the first portion of the graph query and, in response, replacing the second value in the merged message with the first value.
12 . The method of claim 1 , wherein:
the graph query is an aggregation query comprising a SUM aggregation, and
merging the subsequent results with the first results comprises adding a value for the SUM aggregation from the subsequent results of the first portion of the graph query to a value for the SUM aggregation from the first results of the first portion of the graph query.
13 . The method of claim 1 , wherein:
the graph query is an aggregation query comprising an AVG aggregation, and
merging the subsequent results with the first results comprises:
adding a SUM value for the AVG aggregation from the second results of the first portion of the graph query to a SUM value for the AVG aggregation from the first results of the first portion of the graph query; and
incrementing a counter for the merged message.
14 . The method of claim 1 , wherein:
the graph query is an aggregation query, and
generating the merged message comprises adding a partial aggregation value to the merged message based on:
a particular partial aggregation result of the particular instance of evaluating the graph query, and
a subsequent partial aggregation result of the subsequent instance of evaluating the graph query.
15 . A method comprising:
evaluating against graph data a graph query that specifies a particular pattern to match, wherein said graph data is accessible on a multi-node computing system, wherein said graph data comprises a plurality of vertices and a plurality of edges, wherein said evaluating the graph query comprises:
generating, at a first node of the multi-node computing system, a first thread-level merged message based on first results of one or more instances of evaluating the graph query by a first thread at the first node, wherein the first results identify one or more first matching vertices, an identifier of at least one first next vertex on a second node separate from the first node, and a current stage of evaluating the graph query;
generating, at the first node, a second thread-level merged message based on results of one or more instances of evaluating the graph query by a second thread at the first node, wherein the subsequent results identify one or more second matching vertices, an identifier of at least one second next vertex on the second node, and the current stage of evaluating the graph query;
generating, at the first node, a node-level merged message based on the first thread-level merged message and the second thread-level merged message, wherein the node-level merged message comprises merged results based on the first results and the second results; and
sending the node-level merged message from the first node to the second node; and
providing a graph query result based at least in part on evaluation of the graph query by the second node based on the merged results.
16 . One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause:
evaluating against graph data a graph query that specifies a particular pattern to match, wherein said graph data is accessible on a multi-node computing system, wherein said graph data comprises a plurality of vertices and a plurality of edges, wherein said evaluating the graph query comprises:
determining, at a first node of the multi-node computing system, in a particular instance of evaluating the graph query, that one or more first vertices on the first node match a first portion of the graph query and that a second vertex that is to be evaluated next is stored on a second node separate from the first node, wherein first results of the particular instance of evaluating the graph query identify the one or more first vertices as a first set of matching vertices and the second vertex as a next vertex to be evaluated;
generating a first message based on the first results;
determining, at the first node in a subsequent instance of evaluating the graph query, that one or more third vertices on the first node match the first portion of the graph query and that a fourth vertex to be evaluated next is stored on the second node, wherein subsequent results of the subsequent instance of evaluating the graph query identify the one or more third vertices as a set of matching vertices and the fourth vertex as a next vertex to be evaluated;
in response to determining that the fourth vertex to be evaluated next is stored on the second node, merging, by the first node, the subsequent results with the first results in the first message to form merged results, wherein merging the subsequent results with the first results in the first message results in generating a merged message; and
sending the merged message from the first node to the second node; and
providing a graph query result based at least in part on evaluation of the graph query by the second node based on the merged results.
17 . The one or more non-transitory computer-readable media of claim 16 , wherein:
generating the first message comprises storing the second vertex in a next vertex field of the first message and storing the one or more first vertices in a matched vertices field of the first message,
the one or more third vertices are different vertices from the one or more first vertices,
the fourth vertex is a same vertex as the second vertex, and
merging the subsequent results with the first results comprises adding the one or more third vertices to the matched vertices field of the first message.
18 . The one or more non-transitory computer-readable media of claim 16 , wherein:
generating the first message comprises storing the second vertex in a next vertex field of the first message and storing the one or more first vertices in a matched vertices field of the first message,
the one or more third vertices are the same vertices as the one or more first vertices,
the fourth vertex is a different vertex than the second vertex, and
merging the subsequent results with the first results comprises adding the fourth vertex to the next vertex field of the first message.
19 . The one or more non-transitory computer-readable media of claim 16 , wherein:
after generating the merged message, determining that a size of the merged message is greater than or equal to a threshold value and, in response, sending the merged message to the second node.
20 . The one or more non-transitory computer-readable media of claim 16 , wherein:
the particular instance of evaluating the graph query and the subsequent instance of evaluating the graph query are performed by a first thread in the first node of the multi-node computing system,
the merged message is a first thread-level merged message associated with the first thread,
said evaluating the graph query further comprises:
generating, by the first node, a second thread-level merged message based on one or more second results of evaluating the graph query by a second thread in the first node of the multi-node computing system; and
generating a node-level merged message based on the first thread-level merged message and the second thread-level merged message.