Traversal Engine Graph Combinator

[haikalpribadi]

Problem to Solve

The type-resolver performance is becoming a detrimental problem to the query engine. For larger "multi-hop" queries, such queries with 7 relationships or higher (that are quite common), the type-resolver may cause a significant slow-down if the schema it touches is diverse/complex. But this behaviour is not expected; the slow-down is caused by the "permutative" nature of traversal engine answers that type resolver depends on. But this is the wrong behaviour designed into type resolvers algorithm.

The fundamental problem with type-resolver is that it is not actually a traditional "graph traversal" in which most user queries are expected to be. The goal of the type-resolver algorithm, is to find "all possible (type) vertices that can form a valid query". Which means, it is actually looking for "all valid combinations of vertices" that can satisfy a given query, as opposed to all valid "permutations" of vertices that can satisfy a given query. This problem is actually a variant of the "connected-components" graph clustering problem, where the exception is that we need to map a vertex in the query to a set of vertices in the answer.

Current Workaround

None.

Proposed Solution

We should not have used GraphIterator engine to implement type-resolver algorithm. We should implement a "graph combinator" algorithm, specifically for type-resolver. In a big graph, we should implement it in a Pregel/BSP style algorithm. But in a small graph such as the schema graph in which the type-resolver operates on (only once for all queries with the same schema structure!), we just need to do a simple DFS!!! And the DFS is NOT equal to GraphIterator algorithm - GraphIterator is a permutation algorithm! The type-resolver is only a combination problem, so we just need to implement a "graph combinator" DFS algorithm in the TraversalEngine.

Additional Information

This feature will solve all the type-resolver performance issues that we see among our users, including those are captured in issue #6155, #6161, and #6183.

[lriuui0x0]

@haikalpribadi I don't have context on this one, why do we care about combination instead of permutation?

[thomaschristopherking]

I'm just commenting to up-vote this, because it's the most important feature for us right now. Currently, for #6304, we need to implement a workaround where we are matching addresses not by their attributes but by a "composite key" attribute that we will hack together.

[haikalpribadi]

Yes this is high on our list this right now @thomaschristopherking thanks for sharing!

[thomaschristopherking]

hi, @haikalpribadi @flyingsilverfin I noticed that the most recent release doesn't address this feature, as far as I know. Is this likely to come soon/is there any update on this one?

[haikalpribadi]

I believe this is next on @flyingsilverfin list of priorities, @thomaschristopherking. So I think it's fair to say it's highly likely to come out int the next release if there isn't any drastic blocker.

ps: correct me if I'm wrong here @flyingsilverfin

[flyingsilverfin]

@thomaschristopherking we're starting to design this now and get to work on the implementation. Given that the vacations are peppered around august it's unlikely to get done for some more weeks :)

[flyingsilverfin]

Solved with #6431 !!