It's pretty easy to imagine how to represent relational algebra expressions as a tree—they are already structurally rooted trees where each operator

Not all Graphs are Trees

submited by

Style Pass

2024-04-30 06:00:03

It's pretty easy to imagine how to represent relational algebra expressions as a tree—they are already structurally rooted trees where each operator has its inputs as children.

Even in a language like Rust, which has not yet implemented mutable aliasing (an oft-requested feature stuck at the RFC stage) we can implement this easily:

This structure permits neither an easy textual representation nor an easy Rust representation (interestingly, these are sort of the same thing).

This works! But is non-ideal when the expression being referenced is complex, since we'll have a lot of duplicated expressions, and, if we recompute them each time, a lot of duplicated work. Even worse is that multiple nested occurrences of multiple references can result in an exponential blowup in the size of the tree:

This comes with its own set of problems, of course, for both query planning and query execution. See Why Are Query Plans Trees and Query Engines: Push vs. Pull. I have yet to see a satisfying solution to the optimization of query plans involving DAGs in this way. I think any real answer probably involves embedding an ILP solver in the optimizer.