Phase 3. A LogicalPlan -> LogicalPlan rewrite that runs before lowering.
It never touches physical operators or ExecutionContext - it reshapes the
logical tree, which then lowers 1:1 exactly as in v0/v1. This is the payoff of
the plan/lowering split kept since 0001: the
optimizer slots in without a single change to execution code.
Lives in src/optimizer.hpp, namespace optimizer.
An optimized plan produces results identical to the unoptimized plan - same
row count and same order-independent checksum, at batch_size = 1 and 1024.
The optimizer changes how much work is done, never what comes out. The
benchmark enforces this as a hard gate: it runs both plans at both batch sizes
and exits non-zero on any mismatch. Everything below is subordinate to this.
No column statistics exist yet, so estimation uses the classic textbook defaults. Every constant is named and commented in the source; reproduced here so the two can be cross-checked:
| Constant | Value | Meaning |
|---|---|---|
DEFAULT_NDV |
100 | assumed distinct values per column (no histogram) |
EQ_SELECTIVITY |
1/100 | col = k under uniformity: one of NDV values matches |
| (NE) | 1 - 1/100 | col <> k: complement of equality |
DEFAULT_RANGE_SELECTIVITY |
1/3 | col <,<=,>,>= k: System-R open-range default |
AGGREGATE_MAX_GROUPS_FACTOR |
1.0 | GROUP BY can only shrink; cap at child cardinality |
MIN_CARDINALITY |
1 | floor on every estimate; guards divide-by-zero |
Per-node estimate (estimate_cardinality, floored at MIN_CARDINALITY):
- Scan -> exact
table->num_rows. - Filter ->
child_est x selectivity(cmp). - Project ->
child_est(row-preserving). - Join ->
|probe| x |build| / DEFAULT_NDV(inner equi-join, keys assumed uniform over NDV distinct values on both sides). - Aggregate ->
min(child_est, child_est x AGGREGATE_MAX_GROUPS_FACTOR).
explain(node, os) prints the tree with these estimates so the numbers are
hand-checkable against the formulas.
One honest caveat about the demo query in main.cpp: its dimension table
happens to have exactly 100 rows, the same number as DEFAULT_NDV, so the
printed join estimate lands suspiciously close to the true build-side size.
That is a coincidence of this particular demo's table design, not evidence the
model is precise. A dimension table of a different size would show the usual
textbook-default error.
Applied bottom-up. When a LogicalFilter sits directly above a LogicalJoin,
push it onto whichever join input owns the referenced column, then re-parent the
join above the pushed result. This shrinks a join input before the join runs.
The index remapping is the subtle part. Join output columns are
[probe cols][build cols], so with p = probe->output_columns():
column < p-> the filter references a probe column -> push onto the probe subtree with the same index.column >= p-> the filter references a build column -> push onto the build subtree with indexcolumn - p(undo the concatenation offset).
Why this preserves results: pushing a single-column predicate below an inner join is valid because the predicate depends only on that one input's columns, and an inner join emits a row only when both inputs contribute - so filtering an input before the join removes exactly the output rows the filter would have removed after the join, no more, no less. The index adjustment re-expresses the same column in the child's own (un-concatenated) schema, so the same predicate on the same values is evaluated. Output shape and column order above the join are untouched. After a push, the rule re-optimizes the join so the filter keeps travelling toward the scan; unpushable filters stay put.
Children are optimized before their parent is checked, not after, so a stacked
case such as Filter(Filter(Join)) works correctly: the inner filter pushes
away first (as part of optimizing the child), which leaves the outer filter
sitting directly above the now-modified join, where it gets checked and pushed
in turn. Checking a node before recursing into its children would miss this
and leave the outer filter stranded.
For each join the optimizer estimates both sides and notes on the explain
line whether the current build side is the smaller one ([side: build optimal])
or a swap would help ([side: recommend swap - REPORT ONLY]).
It does not swap. Swapping probe and build changes output order from
[probe][build] to [build][probe], which silently breaks every parent column
reference - Aggregate group columns, Project expressions, any downstream
Filter - unless all parent indices are remapped up the tree. That remapping is
a correctness landmine disproportionate to this phase's value, so side selection
is advisory only. (It becomes worthwhile alongside multi-table join ordering,
where a proper column-provenance layer is needed anyway.)
Join reordering (needs 3+ table joins to matter and a column-provenance
layer), histogram-based cardinality, and any physical-plan costing. The
framework - a LogicalPlan -> LogicalPlan pass with an estimator and an EXPLAIN
- is the reusable part; more rules bolt on without touching execution.