A computer-implemented method for performing traversal of a data graph , comprising: receiving a set of start vertices and a set of path step descriptions setting criteria for the data graph traversal; recursively traversing an edge table associated with the data graph, the data graph stored in column oriented tables in a cache memory, based on the start vertices and path step descriptions; identifying a set of traversed vertices (A-F) during the traversing; and returning the set of traversed vertices; wherein the method further comprises optimizing the traversing, the optimizing comprising grouping edges in the edge table by their source vertex by writing edges sharing the same source vertex consecutively to memory; and wherein the traversing comprises repeating for each path step description the steps of: identifying a path predicate included in the path step description, wherein the path predicate is an expression evaluated to identify a reduced set of edges; generating a set of valid edges based on the path predicate by evaluating the path predicate against the edge table; generating the set of traversed vertices by iteratively scanning the set of valid edges against a set of vertices 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 in a previous iteration; and terminating the generating of the set of traversed vertices for the current path step description when the terminating condition is met. receiving a set of start vertices and a set of path step descriptions setting criteria for the data graph traversal; recursively traversing an edge table associated with the data graph, the data graph stored in column oriented tables in a cache memory, based on the start vertices and path step descriptions; identifying a set of traversed vertices (A-F) during the traversing; and returning the set of traversed vertices; wherein the method further comprises optimizing the traversing, the optimizing comprising grouping edges in the edge table by their source vertex by writing edges sharing the same source vertex consecutively to memory; and wherein the traversing comprises repeating for each path step description the steps of: identifying a path predicate included in the path step description, wherein the path predicate is an expression evaluated to identify a reduced set of edges; generating a set of valid edges based on the path predicate by evaluating the path predicate against the edge table; generating the set of traversed vertices by iteratively scanning the set of valid edges against a set of vertices 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 in a previous iteration; and terminating the generating of the set of traversed vertices for the current path step description when the terminating condition is met. identifying a path predicate included in the path step description, wherein the path predicate is an expression evaluated to identify a reduced set of edges; generating a set of valid edges based on the path predicate by evaluating the path predicate against the edge table; generating the set of traversed vertices by iteratively scanning the set of valid edges against a set of vertices 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 in a previous iteration; and terminating the generating of the set of traversed vertices for the current path step description when the terminating condition is met. <EOS>