Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Parsing, the logical plan and the physical plan

Why are there three intermediate representations, and where does SQL resist becoming an algebra?

Parsing, the AST, the logical plan and the physical plan

The interesting question is not how parsing works but why there are three intermediate representations instead of one. Each exists because it has a property (a "closure" property) that the others lack.

  • The (abstract syntax tree, the parsed form of the SQL text) is faithful to the syntax and supports almost no reasoning, because SQL is not an algebra.
  • The is relational algebra (a set of operations on tables, such as select, project, join) extended for the realities of SQL. Its defining property is that it is closed under a set of equivalence-preserving transformations: you can apply a rewrite and still have a valid plan with the same answer. That is the whole point. A rule engine needs a form in which "this rewrite preserves the meaning" is a local check on a small pattern, not a global proof about the whole query.
  • The names concrete algorithms ( with this build side, index scan on that index). It is not closed under the same transformations. Once you have chosen a hash join with a build side, you have destroyed the symmetry that made swapping the two inputs free.

So the real work of the front end is not parsing. It is turning a language with bag semantics, and correlation into an algebra in which the legality of a rewrite can be decided locally. The gap between SQL and textbook algebra is where this area's bugs live:

  • Textbook relational algebra works on sets; SQL works on bags (duplicates allowed). A projection does not remove duplicates, and pushing a DISTINCT through a plan is not free.
  • Outer joins do not freely commute or associate with inner joins. Re-ordering them is legal only under conditions (a later condition that cannot be true for a NULL-padded row), and those must be proved, not assumed.
  • Three-valued logic breaks identities you would like to use: p OR NOT p is not always TRUE (it is UNKNOWN when p is UNKNOWN), and NOT (x > 5) is not the same as x <= 5 when x is .

So the algebra an really works in is a weakened algebra with strictly fewer valid rewrites than the textbook one, and each weakening traces back to one SQL feature.

After , "the table" means an object ID with a specific schema version. That is why plan caches must be keyed on the version, and why a schema change invalidates saved plans. This is binding arriving at the very top of the pipeline.

Lowering is where the space explodes. The explosion is multiplicative across three independent dimensions: join order × implementation choice for each join × physical property at each operator (such as sort order or data distribution). For ten relations this is roughly 10⁹ to 10¹² candidates before any .

There is a fork here, and it is the biggest structural difference between real optimizers.

  • Phase-ordered optimizers (PostgreSQL, and classic Spark Catalyst) run all rewrite rules until nothing changes (to a ), and only then do the planning. Lowering is a phase.
  • Unified-search optimizers (/Cascades and its descendants: SQL Server, Calcite's Volcano , CockroachDB, Greenplum's Orca) put logical and physical alternatives into one structure. There, lowering is just one more rule application, and everything is costed together. The memo is a graph of equivalence groups; each group holds all expressions known to produce the same result. It serves at once as memoization for (each sub-result is solved once), as sharing for common-subexpression elimination (Rewrites), and as a place to attach physical properties. The memo is the substrate three other mechanisms sit on, and its absence is why structurally cannot do some of them.

In one sentence: the number of intermediate forms equals the number of distinct closure properties the optimizer needs; the front end's real job is to turn SQL's non-algebraic features into an algebra, and every feature that resists becomes a rewrite that is illegal in some corner.