Implement naive relational engine

[szarnyasg]

• ire - incremental relational engine
• nre - naïve relational engine
• sre - search-based relational engine

nre should use Akka and utilise multiple CPU cores, but should not use expensive caching like Rete does.

There are relational algebra nodes that have no use of caching, e.g. selection and projection nodes. We call these stateless nodes (L). Others that can utilise caching called stateful nodes (F).

We currently have the following nodes:

• unary
  • MapperNode (L)
  • ProjectionNode (L)
  • SelectionNode (L)
  • UnwindNode (L)
  • [x] DuplicateElimination (F) -- but implementing this as a stateless node offers little benefits -- the size of the cache is linear to the size of the input O(n) (and potentially has less elements if there are many duplicates) :crown:
  • [ ] ProductionNode (F) :crown: :crown: :crown: :crown: :crown: :crown:
  • [x] SortAndTopNode (F) -- again, a stateless implementation does not offer a lot of advantages. Sidenote: we are using a TreeMap from Java collections, as the Scala treemap is only available from Scala 2.12, yet to be supported by Spark
  • [ ] AggregationNode (F) -- this is the place where big gains can be made in terms of memory consumption
• binary -- all of these use a lot of memory, so we can save a large amount with these nodes, but we also have to balance their performance.
  • [x] AntiJoinNode (F) :crown: :crown: :crown: :crown:
  • [x] JoinNode (F) :crown: :crown: :crown:
  • [x] LeftOuterJoinNode (F) :crown: :crown: :crown: :crown:
  • [ ] TransitiveClosureJoinNode (F) :crown: :crown: :crown: :crown: :crown:
  • [x] UnionNode (F) -- I think basic (non-distinct) union can be handled as stateless :crown: :crown:

There are many more to come: evaluating CASE expressions, creating list comprehensions, pattern comprehensions (!), etc.

[szarnyasg]

I my opinion, this task can be approached in many ways. To get the requirements straight, we would like to implement a non-incremental relational engine that

• Uses little memory: should be able to work for graph with 10M elements on a single machine.
• Is reasonably fast: it does not have to be super sophisticated but utilising multiple cores is an absolute must.
• Powerful: can evaluate relational algebra expressions compiled from complex openCypher queries, including aggregation, transitive closure, etc.

So we need a parallel, memory-efficient solution. I'd approach this like this:

1. Actor model: extend the current IRE implementation with stateless nodes. Note that these nodes will only send positive updates (as there is nothing to maintain). We have a termination protocol for the Rete nodes that will work for non-incremental ones as well. Once we get the results from the network, we can simply throw away the network.
2. Functional programming approach: create an immutable view of the data (the indexers) an use clever FP constructs for processing it.

[szarnyasg]

Postponing this into infinity.