Transform the SQL AST into separate logical plan data structures

[jussisaurio]

Talked with @PThorpe92 about this and we both strongly agree that propagating ast::Exprs all the way down is bad.

TODO: add more context and reasoning here. Just trust me bro, it's true. Almost all DBs do it.

[PThorpe92]

Benefits from proposed changes:

Removal of invariants

Currently ast::Expr can represent many more variants than can be actually used internally for a given value.

We currently do several passes/traversals of segments of the ast at different times in the translator to remove or rewrite such invariants. This includes things like breaking up conditions at expr::Binary lines, folding parenthesized expressions, and removal of constant expressions. It would be ideal to do this in one pass, or at least fewer passes.

Schema-aware context

Currently we rewrite ast nodes such as Expr::Id into Expr::Column, injecting context/data about the existing schema and query into the node. It would be ideal to do one schema-aware pass traversing the ast to build the logical data structures that will be needed at the VDBE layer.

A recent attempt has been made to use a data structure similar to Cow that works with mutable references, in place of storing owned ast::Expr directly on things like WhereTerm, Column, etc.. in an effort to reduce the amount of clones we are doing. But the amount of refactoring that would be required to do this was pretty tremendous, so we are storing owned (cloned) values anyway, I don't see this proposed change causing much in the way of performance issues.

Using owned values definitely simplifies this considerably.

[jussisaurio]

Most DB systems (with SQLite being an exception) have some form of this model, and I think we can generally just emulate stuff from DataFusion to get started.

The advantage to this kind of abstraction is that it's very composable and you can model pretty much any statement as an operator tree, even DML and DDL statements are just operators that have an input operator, e.g. an INSERT operator node will have a VALUES node or a SELECT node as its input, and so on. Although we have "Plan" data structures, our current code generation is very adhoc-tailored to each separate statement type, although there is some attempt at unification between SELECT/DELETE/UPDATE, but it's still not very thought out and doesn't compose as well as I'd like it to.

Another advantage is that you can apply rule-based logical plan rewriting. E.g. CockroachDB has a vast set of rewrite/optimization rules that they can apply at the logical plan level without fiddling with individual AST nodes as we unfortunately do. This is not to say we need or even want to go as far as this, but you can obviously see that optimizations become both easier and more understandable when you operate on this level of abstraction.

And ofc, the transform from a tree of logical operators to DBSP circuit should be quite straightforward. (#2530 )

Main challenges are:

1. Making the logical plan to VDBE compilation ergonomic and equally composable as the AST to Logical Plan transformation is -- i.e. demonstrable improvement in the translation step code quality and extensibility
2. Not incurring excessive statement preparation performance penalties as we want to remain competitive with SQLite there, and sqlite does very minimal transformations
3. This will necessarily be a big change, so the best strategy is probably to write this purely additively alongside the existing system and only swap it in once it reaches functional parity with the old one and there is broad agreement about the benefits over the old one.