Graph traversal operator inside a column store

1. A computer-implemented method comprising:

receiving an input parameter, wherein the input parameter includes at least a set of path step descriptions that set criteria for a data graph traversal and a set of start vertices;

recursively traversing an edge table in a data graph that is stored in a column oriented table in a cache memory, based on the input parameter, wherein the traversing identifies a set of traversed vertices and further comprises:

identifying a path predicate included in a path step description;

generating a set of valid edges based on the path predicate, wherein the set of valid edges reduces a scan range during the traversing;

determining a direction for scanning the set of valid edges, based on the path set description, wherein the direction determines whether the scan begins at a vertex source column or a vertex target column in the edge table;

generating the set of traversed vertices by scanning the set of valid edges against a set of vertices in the edge table until at least one terminating condition is met, wherein the set of vertices includes at least the set of start vertices or vertices identified when scanning with a previous path step description; and

terminating the generating of the set of traversed vertices when the at least one terminating condition is met;

and

returning the set of traversed vertices.

2. The computer-implemented method of claim 1 , wherein the at least one terminating condition is specified in the path step description.

3. The computer-implemented method of claim 1 , wherein the at least one terminating condition is met when no vertices were identified during the scanning with the previous path step description.

4. The computer-implemented method of claim 1 , wherein generating the set of traversed vertices further comprises:

generating a set of traversed edges by scanning the set of vertices and the set of valid edges in the edge table;

eliminating the set of traversed edges from the set of the valid edges;

generating a set of visited vertices from the set of the traversed edges; and

merging the set of visited vertices into the set of traversed vertices, wherein the set of traversed vertices includes vertices from multiple path step descriptions.

5. The method of claim 1 , further comprising:

optimizing the traversing, wherein the optimizing comprises:

identifying edge types in the data graph;

generating a plurality of sub graphs, wherein the sub graph is associated with an edge type; and

traversing the plurality of sub graphs in parallel to determine the set of traversed vertices.

6. The method of claim 1 , further comprising:

optimizing the traversing, wherein the optimizing further comprises:

determining a topological ordering for a vertex in a set of vertices in the data graph;

for the vertex, identifying a subset of vertices that includes vertices reachable from each vertex based on the topological ordering; and

rearranging the edges in the edge table based on the subset of vertices, such that the edges associated with the subset of vertices are traversed during the traversing.

7. The method of claim 1 , further comprising:

optimizing the traversing, wherein the optimizing further comprises:

determining a subset of vertices that includes vertices a predetermined path step away from a vertex; and

storing the determined subset of vertices in a location in memory, such that the subset of vertices and the vertex are retrieved using a request for a single memory block during the traversing.

8. A system, comprising:

a graph traversal operator stored in memory and executing on a processor and causes the processor to:

receive an input parameter, wherein the input parameter includes at least a set of path step descriptions that set criteria for a data graph traversal and a set of start vertices;

recursively traverse an edge table in a data graph that is stored in a column oriented table in a cache memory, based on the input parameter, wherein the traversing identifies a set of traversed vertices and to traverse the edge table the graph traversal operator is further configured to:

identify a path predicate included in a path step description;

generate a set of valid edges based on the path predicate, wherein the set of valid edges reduces a scan range during the traversing;

determine a direction for scanning the set of valid edges, based on the path set description, wherein the direction determines whether the scan begins at a vertex source column or a vertex target column in the edge table;

generate the set of traversed vertices by scanning the set of valid edges against a set of vertices in the edge table until at least one terminating condition is met, wherein the set of vertices includes at least the set of start vertices or vertices identified when scanning with a previous path step description; and

terminate the generating of the set of traversed vertices when the at least one terminating condition is met;

and

return the set of traversed vertices.

9. The system of claim 8 , wherein the at least one terminating condition is specified in the path step description.

10. The system of claim 8 , wherein the at least one terminating condition is met when no vertices were identified during the scanning with the previous path step description.

11. The system of claim 8 , wherein to generate the set of traversed vertices the graph traversal operator is further configured to:

generate a set of traversed edges by scanning the set of vertices and the set of valid edges in the edge table;

eliminate the set of traversed edges from the set of the valid edges;

generate a set of visited vertices from the set of the traversed edges; and

merge the set of visited vertices into the set of traversed vertices, wherein the set of traversed vertices includes vertices from multiple path step descriptions.

12. The system of claim 8 , further comprising an optimization module configured to optimize the traversal and configured to:

identify edge types in the data graph;

generate a plurality of sub graphs, wherein the sub graph is associated with an edge type; and

traverse the plurality of sub graphs in parallel to determine the set of traversed vertices.

13. The system of claim 8 , further comprising an optimization module configured to optimize the traversal and configured to:

determine a topological ordering for a vertex in a set of vertices in the data graph;

for the vertex, identify a subset of vertices that includes vertices reachable from each vertex based on the topological ordering; and

rearrange the edges in the edge table based on the subset of vertices, such that the edges associated with the subset of vertices are traversed during the traversal.

14. The system of claim 8 , further comprising an optimization module configured to optimize the traversal and configured to:

determine a subset of vertices that includes vertices a predetermined path step away from a vertex; and

store the determined subset of vertices in a location in memory, such that the subset of vertices and the vertex are retrieved using a request for a single memory block during the traversal.

15. A non-transitory computer-readable storage device having instructions stored thereon, execution of which by a processor cause the processor to perform the operations comprising:

receiving an input parameter, wherein the input parameter includes at least a set of path step descriptions that set criteria for a data graph traversal and a set of start vertices;

recursively traversing an edge table in a data graph that is stored in a column oriented table in a cache memory, based on the input parameter, wherein the traversing identifies a set of traversed vertices and further comprises:

identifying a path predicate included in a path step description;

generating a set of valid edges based on the path predicate, wherein the set of valid edges reduces a scan range during the traversing;

determining a direction for scanning the set of valid edges, based on the path set description, wherein the direction determines whether the scan begins at a vertex source column or a vertex target column in the edge table;

generating the set of traversed vertices by scanning the set of valid edges against a set of vertices in the edge table until at least one terminating condition is met, wherein the set of vertices includes at least the set of start vertices or vertices identified when scanning with a previous path step description; and

terminating the generating of the set of traversed vertices when the at least one terminating condition is met;

and

returning the set of traversed vertices.