Execution plan

[jenmud]

Hi There,

I have been working on the ruruki in-memory graph db implementation of opencypher based on the ebnf (see cypher_parser on my fork or ruruki ) which is working quite nicely at this stage. Now that I have parsing results, I am trying to figure out the execution plan. Is there information that I can read on how to go about implementing the execution plan for cypher. I have looked at the EXPLAIN and PROFILE diagrams which gave me a simple overview but I need more detailed information about the rules and etc...

Your assistance is appreciated.

Jenda

[Mats-SX]

Hello @jenmud

We have unfortunately not been able to start working on the reference implementation of the query planner, which we intend to provide open source via this project. The idea is for this to serve as the go-to place for questions like yours above.

Until such time, the best we can offer is Cypher as it is implemented in Neo4j. Here are the logical plan operators, all of which you need not support, but some of which will likely be necessary. Neo4j comes with two planning algorithms, one rule-based (which is being phased out) and one cost-based dynamic programming algorithm. You're of course free to choose any level of complexity for your implementation, but I should point out that implementation of the cost-based planner was a very time-consuming effort.

You can also look in the Neo4j Developer's manual for documentation on the semantics of the language, as well as descriptions of some plan operators. It is not exhaustive, but could be a start.

For correctness there's the TCK, which we've spent some effort on. The TCK specifies the semantics of the language by asserting that an implementation behaves as expected in variety of scenarios. We're about to release a milestone of the TCK to Maven very soon, which means you could use that as a starting point as well, scenario by scenario.