SQL text -> parser -> binder/type checker -> logical plan -> optimizer memo -> physical plan -> vectorized execution
EXPLAIN SQL text -> parser wrapper -> binder/type checker -> shared optimizer report -> one-column string batch
sql::parse_selectimplements a small, explicit SQL slice for golden tests and rejects unsupported syntax with position-bearing parse errors. The slice includesEXPLAIN <select-statement>as a wrapper,SELECT [DISTINCT] expr [AS name] ... FROM t1 [AS] x [INNER|LEFT [OUTER]|RIGHT [OUTER]] JOIN t2 [AS] y ON ...chains with booleanONandWHEREpredicates, aggregate callsCOUNT(*),COUNT(col),SUM(col),MIN(col),MAX(col)in the SELECT list and HAVING/ORDER BY positions,GROUP BY <col> [, ...] [HAVING boolean-predicate], global-aggregateHAVINGwithout GROUP BY, tail-positionORDER BY <col-or-output-name-or-aggregate> [ASC|DESC]lists, and finalLIMIT <non-negative integer>after optional ORDER BY. Scalar expressions support column refs, int64 literals, single-quoted string literals with doubled''escaping, and theNULLliteral in projections and predicate comparisons; comparison operands additionally accept parenthesized scalar SELECT subqueries. Predicate leaves include[NOT] IN (SELECT ...)and[NOT] EXISTS (SELECT ...), and nested subqueries reuse the complete SELECT grammar. TheNULLliteral follows the existing literal output-name policy and prints asNULL. Unterminated string literals report the opening quote position. Boolean predicates support comparison leaves,IS NULL,IS NOT NULL,AND,OR, and boolean-level parentheses with precedenceOR < AND < comparison/null-check; non-subquery parenthesized scalar expressions remain out of scope. Table aliases are optional; SELECT-item aliases requireAS; reserved keywords are rejected as explicit aliases. Negative and non-integer LIMIT values are parse errors at the offending token. Phases 22-23 also accept whole-SELECT-item Window calls for ranking, whole-partition aggregates, and the exact cumulative aggregate frames documented below.catalog::Catalogis the neutral schema boundary between SQL binding and execution. It exposes table names, column names, row counts, and explicit column types without table data.catalog::ColumnTypecurrently hasInt64andString.sql::bind_selectresolves parsed column references against catalog table schema scopes, assigns a type to every bound expression, and rejects binding errors before logical planning. Scope resolution is lexical and innermost-first: a subquery's own level wins, then enclosing levels are searched outward; ambiguity is reported within the first level containing matches. Qualified aliases shadow the same alias in outer levels.BoundColumnRef::outer_depthis zero for the current query block, one for its parent, and so on, allowing supported nested/grandparent correlation without name inference. The scope identity is otherwise the binding name: alias if present, otherwise the physical table name. Once a table is aliased, the physical table name is not also a qualifier. Duplicate binding names within one query block are rejected, sot JOIN tremains invalid whilet AS x JOIN t AS yis valid. SELECT-item aliases become output names and are deduplicated by the same duplicate-output-name rule as canonical expression names. Comparison operands must have the same bound type, withNULLadopting the opposite operand type when one exists; int64/string comparisons are bind errors and no implicit coercion exists after binding.IS [NOT] NULLaccepts any type.SUMrequires int64,MIN/MAXaccept int64 or string, andCOUNT(*)/COUNT(col)accept any type.GROUP BY,DISTINCT,ORDER BY, and join keys are legal on strings.RIGHT JOINis normalized during binding intoLEFT JOINby swapping the accumulated left-deep input with the new right table scan; downstream plans consume stable bound identities, and the final Project pins SQL-visible column names and order. The raw normalized Join node still exposes left-child identities before right-child identities, so a RIGHT join's internal identity order changes relative to SQL text.ORDER BYresolves each key by exact SELECT output-name match first, then falls back to FROM-scope binding; in aggregate queries, fallback FROM-scope keys must be grouping columns. WithSELECT DISTINCT, ORDER BY fallback to non-output FROM-scope columns is rejected because DISTINCT has already reduced the projected row set before sorting. Aggregate queries reject non-grouped local projected or HAVING column refs outside aggregates and reject nested aggregates; correlated outer refs are constants for one subquery invocation.HAVINGwithoutGROUP BYis a legal global-aggregate query over one group; HAVING-only aggregate expressions are added to the Aggregate node and dropped by the final Project. The sql layer does not include execution headers.plan::LogicalPlanis the post-binding algebra handoff boundary. Expressions in logical plans carry bound column identities (binding,column) plus their boundcatalog::ColumnType, so downstream layers never re-resolve parsed SQL names or re-infer types. Bound scalar expressions are typed column refs, int64 literals, string literals, NULL literals, or immutable already-bound scalar subplans; IN/EXISTS predicate leaves likewise own immutable bound subplans. Filter and Join nodes still store top-level conjunct lists, but each conjunct is a typed bound predicate tree: comparison, null-check, IN, EXISTS, AND, or OR; Join nodes carryInner, normalizedLeft,Semi,Anti, orNullAwareAnti. INNER/LEFT expose left identities followed by right identities. SEMI/ANTI/NULL-AWARE-ANTI expose exactly the left child's identities and order; right identities exist only while evaluating match predicates. NULL-AWARE-ANTI structurally separates its candidate/correlation predicate list from one required typed equality membership predicate, preventing ordinary anti-match semantics from being confused with SQLNOT IN3VL. The parser splits only root-levelANDnodes that are not protected by boolean parentheses, soa=1 AND (b=2 OR c=3)becomes two conjuncts whilea=1 OR b=2stays one conjunct.Scannodes separately carry the physical table to read and the binding name used to qualify emitted column identities. Aggregate nodes carry typed grouping keys plus typed aggregate output definitions and sit between Filter/Join and Project; HAVING is a normalFilterover Aggregate output columns before the final Project. Global HAVING uses the same shape with an empty grouping-key list, so the Aggregate emits the single global group before the HAVING Filter either keeps or rejects it under TRUE-only 3VL. Result shaping is explicit and ordered: final SELECT projection is followed by optionalDistinct, optionalSort, then optional top-levelLimit, so the full shape is... -> Project -> Distinct -> Sort -> Limitwhen all three are present. Logical plans also carry an explicit order permission. A SELECT withoutORDER BYis still marked as permitting arbitrary row order. A SELECT withORDER BYhas a required-orderSortabove arbitrary-order input, and a top-levelLimitinherits that order permission without blocking legal join transforms below the ordering boundary.EXPLAINis represented as a wrapper logical node around the bound SELECT plan; it is intercepted before physical lowering and never executes its child query.- Phase 21c extends each bound column identity with lexical
outer_depthand records a deterministic correlation set on every immutable subplan root. Empty correlation means no outer row is required and preserves the Phase 21a structural path. optimizer::rewrite_to_fixpointapplies a deterministic ordered list of pureLogicalPlan -> optional<LogicalPlan>rewrite rules before physical lowering. The same rule proofs are also hosted by the memo exploration driver.optimizer::Memostores logical equivalence groups. Group expressions reference child group ids, not nested plan objects. Ingest copies a bound logical tree bottom-up, assigns deterministic 1-based group ids, and deduplicates structurally identical expressions through structural hash/equality lookup.plan::PhysicalPlanis a structure-preserving lowering of the logical tree. Physical scans preserve both the physical table and binding name from logical scans. INNER, normalized LEFT, SEMI, ANTI, and NULL-AWARE-ANTI joins plus Aggregate, Window, Distinct, Sort, and Limit lower without changing their logical fields. Lowering does not optimize, cost, or reorder. Lowering rejects any residual correlated subquery with the stable positioned errorvectorized execution does not support residual correlated subqueries at position N; uncorrelated embedded subqueries and proof-decorrelated plans lower normally.execution::execute_interpretedis the correctness oracle, including inner, LEFT, SEMI, ANTI, and NULL-AWARE-ANTI join, predicate three-valued logic, aggregation, Window, DISTINCT, stable sort, and LIMIT semantics. Predicate evaluation returns TRUE, FALSE, or UNKNOWN. Comparisons with any NULL operand return UNKNOWN;IS NULLandIS NOT NULLalways return TRUE or FALSE; AND/OR use SQL 3VL truth tables; Filter, Join, WHERE, ON, and HAVING keep only TRUE rows/pairs/groups and reject FALSE and UNKNOWN. LEFT JOIN visits preserved left rows in order and candidate right rows in order; if no ON predicate is TRUE for a left row, the oracle emits that left row once with every right column NULL. SEMI stops at the first TRUE right match and emits the left row once; ANTI emits it once only after no TRUE match. NULL-AWARE-ANTI follows the separate candidate-set specification below. All three left-only joins expose left columns only. String comparisons use exactstd::stringbyte-sequence ordering/equality (operator<andoperator==) with no collation or coercion. Aggregates ignore NULL inputs exceptCOUNT(*); stringMIN/MAXuse the same lexicographic ordering. Grouping, window partitioning, and DISTINCT use distinct-style NULL equality across typed key slots, and ORDER BY treats NULL as larger than every non-NULL value for both int64 and string.execution::execute_vectorizedlowers to the physical tree and runs scan/filter/join/aggregate/window/project/distinct/sort/limit with immutable selection vectors until final materialization. INNER and LEFT join materialize a deterministic joined batch boundary; SEMI/ANTI/NULL-AWARE-ANTI materialize selected left rows only. Aggregate materializes a deterministic grouped batch boundary before downstream projections or sorts run. Window materializes a deterministic row-preserving batch boundary: child columns and each Window output are gathered through the Window input selection order, while per-row Window values are stored by original physical row id. Distinct uses a hash set only to test whether the complete output row has appeared before; output order comes from the input selection order. Limit slices the current selection to the firstnrows. Sort usesstd::stable_sortover row ids with a comparator that reads typed bound key columns, places NULLS LAST for ASC and NULLS FIRST for DESC, compares strings by exactstd::stringbyte ordering, and returns false for full-key ties. ForSort(Project(child)), both engines build a private sort batch containing projected output columns plus any missing source-scope sort keys, then emit only the Project outputs.storage::ColumnarBatchenforces equal-length column vectors, including equal value and validity lengths inside each nullable column. It stores typed columns in insertion order; the legacycolumn(name)accessor remains the int64 fast-path accessor, whilecolumn_type(name)andstring_column(name)expose the typed surface.storage::Int64Columnandstorage::StringColumnboth have value semantics backed by shared immutable value-vector storage plus an optional shared validity vector. The validity representation isstd::vector<std::uint8_t>with1for present and0for NULL; an all-present column keepsvalidity_ == nullptr, so the NULL-free fast path is a single null-pointer check and existing value-vector sharing remains cheap. Append and reserve detach both shared buffers when needed,append_null()creates and backfills the validity vector only on first NULL, and materializers reserve exact output column capacity when the output row count is known.execution::Catalogimplementscatalog::Catalogfor binding and separately owns table batches for execution.
The Phase 5 memo is a correctness-only Cascades core. A MemoGroup is a set of semantically equivalent MemoExpressions. Expressions are normalized into operator kind plus operator fields plus order permission plus child group ids: scans carry both a physical table name and binding name; joins carry join kind and predicates, with NULL-AWARE-ANTI additionally carrying its structural membership equality; projects carry bound projections; aggregates carry bound grouping keys and aggregate outputs; windows carry their complete ordered bound definition list; distinct nodes carry one child; sorts carry bound sort keys and directions; limits carry their row count; and GroupRef explicitly records the checked case where a rule proves a group is equivalent to an existing child group. Join kind, membership equality, and every node's order permission participate in structural hash/equality, dumps, group reconstruction, alternative extraction, and winner reconstruction. Scan structural hash/equality includes both physical table and binding name; two self-join scans of the same physical table under different aliases are distinct memo groups.
Memo ids are deterministic because ingest is bottom-up and group ids are assigned from insertion order. Structural hash/equality includes bound scalar type, column type, projection type, aggregate output type, and literal kind/value, so an int64 literal and a string literal with the same text never collide structurally. When a new equivalent expression is structurally identical to an expression already owned by another group, the groups are merged rather than rejected. Merging uses stable representatives with the smaller group id as the deterministic winner; losing group ids remain valid aliases and are printed as group N -> representative M. Expressions move to the winner, all child references are canonicalized to representatives, and the structural index is rebuilt over representative groups only. The structural dedup table is a hash lookup only; observable behavior never depends on hash table iteration. Dumps print groups by id and expressions by insertion index.
Canonical extraction chooses the first-inserted expression in each group and recursively reconstructs a LogicalPlan, intentionally preserving the original ingested shape for deterministic no-cost-model tests. Rule exploration still records additional equivalent expressions in the memo, and the differential corpus executes extracted alternatives through both engines to prove every represented alternative preserves semantics.
Phase 5b also exposes deterministic alternative extraction for verification. The extractor walks representative groups and expressions in insertion order, recursively enumerates child alternatives, and stops at explicit per-group and total-plan caps while recording whether either cap was hit. Canonical extraction remains first-expression extraction for the no-cost-model path.
The Phase 5c cost model is deterministic and logical. It consumes only the neutral catalog::Catalog interface; execution::Catalog feeds exact table row counts into catalog::TableSchema::row_count, and the SQL layer does not include execution headers. Missing row-count statistics are a fail-loud cost-model error rather than an implicit guess. Scan row-count statistics are looked up by physical table name, while distinct-count keys are binding-scoped (binding.column) so aliased self-joins share table statistics without sharing semantic column identities. Distinct counts are deliberately heuristic in this slice: each scan column starts with distinct=row_count, and filters and joins clamp distinct estimates to the estimated output rows.
Cardinality formulas are fixed and documented in code next to the estimator. Scan(table) returns the catalog row count. Filter multiplies input rows by the product of top-level conjunct selectivities. Comparison leaves use fixed selectivities: equality 0.10, not-equal 0.90, and inequalities <, <=, >, >= as 1/3; int64-literal-vs-int64-literal leaves are evaluated exactly to selectivity 1.0 or 0.0, while NULL literals are not constant-folded into two-valued results. IS NULL reuses equality selectivity and IS NOT NULL reuses not-equal selectivity until nullable column statistics are added. Predicate-tree AND multiplies child selectivities, and OR uses deterministic inclusion-exclusion s1 + s2 - s1*s2. INNER Join uses the first usable top-level bound column equality leaf whose columns come from opposite children: |L| * |R| / max(distinct(left_key), distinct(right_key)). If no usable equi key exists, join cardinality starts as |L| * |R|; residual predicate trees then apply the same recursive selectivity formulas. A normalized LEFT join estimates rows as max(inner_join_estimate, left_rows) so the preserved side never costs below its input cardinality. SEMI uses the documented match heuristic |L| * s with s=0.5; ANTI uses its complement |L| * (1-s). NULL-AWARE-ANTI deliberately reuses the deterministic 0.5 * |L| anti-style estimate: without nullable statistics the cost model must not guess whether a right NULL makes the true output zero. All three propagate only left-side distinct identities and clamp them to output rows. Aggregate estimates one row for global aggregation, including empty input, and otherwise estimates min(input_rows, product(distinct(group_key))). All rows, distinct counts, and costs are clamped to finite non-negative doubles.
Cost formulas mirror the logical amount of vectorized work for this phase. Scan cost is output rows. Filter cost is child cost plus input rows. An equi-join is costed as child costs plus left_rows + right_rows, modeling linear right-build/left-probe work. A keyless SEMI/ANTI existence join uses the same linear formula because the right is materialized once and only emptiness is tested. A NULL-AWARE-ANTI with a hashable membership equality and only equality correlation candidates uses the same linear build/probe formula; otherwise its deterministic semantic fallback costs left_rows * right_rows, as does every residual-only join with no usable equi shape. Aggregate is costed as input_cost + input_rows + group_rows, modeling one input pass and one output-group pass. Window preserves child cardinality and costs one linear input pass per independent window definition plus rows * log2(rows) for each ordered definition; the whole-input sort term is a conservative upper bound for the sum of actual per-partition sorts. Project is cost-neutral because it does not affect join-order choice. Distinct estimates output rows with a group-like product over projected expression distinct counts clamped to input rows, and costs input_cost + input_rows + distinct_rows. Sort preserves the input row estimate and costs input_cost + rows * log2(rows), with zero local sort cost for empty or single-row inputs. Limit estimates min(limit_count, input_rows) rows and keeps child cost because it only trims the already-produced stream in this logical model. GroupRef has the referenced group's cost. String columns intentionally use the same row-count math as int64 columns in Phase 17a; value-width, collation, and string-comparison CPU costing are future work and must not affect semantics.
Memo::extract_best(root, catalog) performs classic winner tracking over representative memo groups. The extractor memoizes one winner per group after exploration, where a winner contains the chosen expression, estimated rows, estimated cost, propagated distinct estimates, and reconstructed LogicalPlan. It walks only expressions already present in the memo, so costing can choose among equivalents but cannot create semantics. Lower estimated cost wins. Ties use exact double equality and are broken by the lowest expression insertion index in the group, which is deterministic because memo exploration already walks groups, expressions, and rules in stable order.
Memo boundaries fail loud. Insert, equivalent insertion, merging, extraction, alternative extraction, and dump validate that child group ids exist, expression arity matches operator kind, representative chains are rooted at deterministic winners, representative expressions use canonical child refs, losing groups are non-empty aliases, the structural index points back to representative owners, and group references do not introduce cycles.
EXPLAIN <select-statement> returns a deterministic storage::ColumnarBatch with one VARCHAR column named plan; each row is one line of the report. The child SELECT is parsed, bound, explored, and costed, but it is not executed. Both execution::execute_interpreted and execution::execute_vectorized intercept the LogicalKind::Explain wrapper and call the same optimizer::explain helper, so engine choice cannot change EXPLAIN output.
The report contains the bound logical plan, a memo exploration summary (groups, iterations, reached_fixpoint, and fired rule names in firing order), the extract_best chosen plan with rows= and cost= annotations beside every node, and the total estimated cost. Formatting is fixed: no addresses, timings, unordered iteration, or locale-sensitive floating output; estimates use fixed two-decimal formatting. The chosen-plan annotations are produced by the logical plan printer with an estimate callback, so the printed tree shape remains the same deterministic syntax used by existing plan goldens.
Phase 21a introduced three uncorrelated forms in WHERE, JOIN ON, and HAVING predicate trees: scalar subqueries as either operand of a comparison, expr [NOT] IN (SELECT ...), and [NOT] EXISTS (SELECT ...). Every parenthesized subquery reuses the full SELECT grammar, including joins, aggregation, nested subqueries, ORDER BY, and LIMIT. Parser failures retain source positions. In 21a a subquery received none of its owner's scopes and a would-be correlated name produced the temporary correlated subqueries are unsupported bind error. Phase 21c supersedes that binding restriction with the explicit lexical model below. Scalar and IN subqueries still expose exactly one projected column. Its bound type must match the comparison operand or IN left operand under the existing exact same-type rule; EXISTS permits any projection width.
Bound representation is deliberately explicit and immutable. BoundScalarSubquery and the IN/EXISTS predicate leaves own shared_ptr<const LogicalPlan> values produced by binding. Downstream layers consume these already-bound plans and never rebind names or infer types. The logical printer renders each embedded plan as an indented Subquery[...] pseudo-child below its owning Filter, Join, or Project; EXPLAIN uses that same printer for both the bound and chosen plans.
The interpreted engine is the Phase 21a semantics oracle. Before executing outer row loops, one query-scoped context walks the logical tree, recursively executes each embedded plan once, and caches its materialized batch by immutable plan identity. A scalar subquery returning no rows yields a typed NULL; one row yields its sole value, including a stored NULL; more than one row throws scalar subquery at position N returned more than one row. Eager preparation means the cardinality error is still observed when the outer input is empty. Ordinary comparisons then apply the existing SQL 3VL rules.
IN semantics are pinned as follows:
| Right-hand set | Left value | Membership condition | IN |
NOT IN |
|---|---|---|---|---|
| empty | any value, including NULL | no candidates | FALSE | TRUE |
| non-empty | NULL | any members | UNKNOWN | UNKNOWN |
| non-empty | non-NULL | some non-NULL member equals it | TRUE | FALSE |
| non-empty | non-NULL | no match and at least one NULL member | UNKNOWN | UNKNOWN |
| non-empty | non-NULL | no match and no NULL member | FALSE | TRUE |
The empty-set result follows the existential definition of IN: the disjunction over zero equality candidates is FALSE before the left value can introduce UNKNOWN. NOT IN is exact 3VL negation, so empty-set NOT IN is TRUE even for a NULL left value. Conversely, an unmatched NULL-bearing set makes IN UNKNOWN and therefore NOT IN UNKNOWN; NOT IN over such a set cannot become TRUE. EXISTS is TRUE exactly when the materialized subplan has at least one row, with row values and NULLs irrelevant. NOT EXISTS negates that boolean, and a LIMIT 0 subquery therefore makes EXISTS FALSE and NOT EXISTS TRUE.
Embedded subplans participate in memo structural identity through recursive logical-tree hash and equality. Separately bound but structurally identical subplans deduplicate; different subplan trees do not. They are opaque fields rather than memo child groups in 21a, so memo exploration and standalone rewrites never descend into them. Decorrelation is intentionally deferred to 21b. Boolean simplification also refuses to erase a subquery-bearing branch: eager scalar-cardinality and subplan runtime errors are observable and must survive every equivalent plan. Referenced-column analysis otherwise inspects only the owning expression's outer operands: an independently bound subplan contributes no outer binding identities. Existing whole-conjunct pushdown and join-mobility proofs therefore remain sound and classify a subquery-bearing conjunct by its actual outer references.
Costing adds each embedded subplan's complete logical cost exactly once to the operator that owns its predicate or scalar, never once per estimated outer row and never again as a memo child. Nested subquery cost is naturally included once at each owning boundary. Selectivity remains heuristic and cannot create semantics.
Phase 21a intentionally stopped at the interpreted boundary: its physical-lowering guard and oracle-only differential route were temporary scaffolding. Phase 21b removes that guard and supersedes the execution limitations below while retaining the 21a truth tables and scalar-error contract unchanged.
JoinKind::Semi and JoinKind::Anti are left semi/anti joins. Their logical, physical, memo, printer, EXPLAIN, costing, interpreted, and vectorized representations expose exactly the left child's schema; right identities are predicate-only and never become output identity. For each left row in input order, SEMI emits it once on the first TRUE match, while ANTI emits it once only after no TRUE match. FALSE and UNKNOWN are non-matches. A NULL equality key therefore cannot make a SEMI match and causes a left NULL-key row to be emitted by ANTI. Right duplicates never multiply output. The vectorized equi implementation builds the right hash table, skips every NULL-containing key, probes left in order, and stops on the first residual-TRUE candidate. Hash iteration is never observable. Keyless and non-equi joins use a deterministic nested-loop fallback; an empty predicate list is TRUE, so keyless SEMI/ANTI implements EXISTS/NOT EXISTS by testing whether the materialized right has any row.
Three memo-only rules decorrelate only whole top-level Filter conjuncts. ExistsToSemiJoinRule maps Filter[..., EXISTS(Q)](P) to residual Filter over SemiJoin(P,Q,TRUE). NotExistsToAntiJoinRule uses keyless Anti and is NULL-insensitive because existence observes rows, not values. InToSemiJoinRule maps x IN (SELECT c FROM Q) to equi-Semi on x=c. Under TRUE-only filtering, IN survives exactly when some non-NULL c makes equality TRUE; a NULL x and an unmatched value with a NULL-bearing right set both produce UNKNOWN in IN and a non-match in Semi, so both reject the row. The rules never descend into AND/OR trees, so an eligible-looking leaf inside OR remains materialized. Phase 21b deliberately left NOT IN materialized because ordinary Anti would incorrectly emit unmatched rows when the set contains NULL; Phase 24 supplies the distinct NULL-aware algebra below without changing ordinary Anti. Scalar subqueries stay materialized. Every application removes one eligible owner leaf; structural memo deduplication closes repeated exploration.
SEMI/ANTI/NULL-AWARE-ANTI never commute or associate, and LeftJoinToInnerRule never applies to them. FilterIntoJoinRule has one proof-bearing exception to its INNER guard: a whole left-only conjunct may move into the preserved child of any of these left-only joins because filtering a left row before the right-side test keeps exactly the rows that would pass the same predicate afterward. Right-only, mixed-side, empty-reference, and literal-only conjuncts remain above; no predicate moves into a match/candidate condition or right child. Memo output-schema validation derives only the left binding set for all three, preventing a right identity from leaking into an equivalent group.
Residual subqueries execute through a query-scoped vectorized preparation context before any outer row loop. It walks projections and predicates in deterministic owner order, recursively executes each immutable embedded logical plan through vectorized lowering/execution exactly once by plan identity, and caches its materialized batch. Scalar preparation checks cardinality eagerly and throws the same scalar subquery at position N returned more than one row runtime category even when the outer input is empty or a boolean branch would otherwise erase it. A scalar result becomes one typed nullable compiled constant. IN/NOT IN preparation builds a typed lookup-only unordered_set of non-NULL int64 or string values plus explicit is_empty and has_null flags; compiled mask and join-residual leaves implement the complete 21a truth table from those flags. No output depends on hash iteration. Independently executed subplans select their own int64-only or typed dispatch, so subquery-free roots keep their existing fast paths.
The 160-seed differential fuzzer now emits every Phase 21a form through a deterministic ten-mode cycle: safe scalar aggregates, IN, NULL-bearing NOT IN, empty EXISTS, NOT EXISTS over joins, nested IN/EXISTS, IN over joins, scalar join+aggregate, and IN/EXISTS below OR. Generated scalar subqueries are cardinality-safe by construction (MAX global aggregate); targeted deterministic tests own multi-row scalar error equivalence. Every query still runs unrewritten, standalone rewrite, all memo alternatives, and extract_best through both engines. The Phase 21b run covered 5,087 alternatives and 11,036 execution paths with rule firings ExistsToSemiJoin=51, NotExistsToAntiJoin=25, and InToSemiJoin=121, without hitting extraction bounds.
Every immutable bound subplan root carries a deterministic correlation set of the outer BoundColumnRef identities required to execute it. Direct references retain their lexical outer_depth; dependencies of nested subplans are rebased into their owner, so a middle subquery that contains a grandchild reference to the top query is itself correctly classified as correlated. An empty correlation set is the exact structural Phase 21a dispatch—never a name or plan-shape heuristic—and therefore retains eager once-per-query preparation byte-for-byte. Grandparent correlation is supported by the binder and oracle; decorrelation deliberately accepts only immediate-parent equality keys.
The interpreted engine is the correlated semantics specification. A non-empty correlation set bypasses the eager cache, pushes the current owner row as an immutable outer-row frame, and executes the subplan once for that row. Nested evaluation stacks frames, and a depth-aware column read selects the corresponding lexical frame. Scalar cardinality is checked per invocation: zero rows yields typed NULL, one row yields its value (including NULL), and more than one row throws the existing positioned scalar-cardinality error when that offending owner row is evaluated. The oracle's deterministic operator/row order therefore defines error timing. IN/NOT IN and EXISTS/NOT EXISTS feed each per-row materialization into the unchanged Phase 21a 3VL matrices. In particular, a NULL correlation equality is UNKNOWN and removes every candidate row; EXISTS/IN do not match it, while NOT EXISTS is TRUE. Uncorrelated subqueries remain eagerly prepared even for empty outer inputs or boolean branches.
Three memo-only rules implement the proven payoff. CorrelatedExistsToSemiJoinRule, CorrelatedNotExistsToAntiJoinRule, and CorrelatedInToSemiJoinRule accept only Project(Filter(Scan|Join)) subplans where every correlation use is a whole top-level WHERE conjunct of the exact outer_col = inner_col form with depth one/local operands. The rule removes those conjuncts, retains all uncorrelated WHERE conjuncts, appends deterministic hidden projections for the inner keys, clears the proven-empty correlation set, and creates an equi Semi/Anti join. IN adds its original operand-to-selected-output equality. Per outer row, equality substitution and equi-join TRUE matching select the same inner rows; duplicates cannot multiply Semi/Anti output, and NULL on either equality side is UNKNOWN/non-match in both representations. Anti therefore retains a NULL-correlated row exactly when per-row NOT EXISTS is true. Phase 21c left NOT IN residual because ordinary Anti cannot represent the NULL-bearing-set UNKNOWN case; Phase 24 adds the guarded correlated NULL-aware rule below.
The rules fail closed for non-equality comparisons, correlation below AND/OR, projection expressions, aggregate arguments, HAVING, join ON, nested/transitive correlation, and any subplan with Aggregate, DISTINCT, Sort, or Limit above the candidate WHERE. These forms remain fully defined by the per-row oracle and hit the physical-lowering guard. This conservative boundary avoids moving equality across result shaping or aggregation, where per-key emptiness or cardinality can change.
Costing mirrors the specification: an embedded correlated subplan contributes subplan_cost * owner_rows_estimate; an empty-correlation subplan still contributes its complete cost exactly once. Once a rule removes correlation, existing semi/anti linear build/probe costing applies, which makes the proven alternative win on skewed EXPLAIN fixtures. Plan printers show correlation=[outer(N):col(binding.column)] on owned subplans, while chosen decorrelated plans contain only native joins.
The deterministic fuzzer adds a five-mode correlated lane alongside the Phase 21b corpus: equality-correlated EXISTS, NOT EXISTS, and IN run every oracle/memo/native-vector path; correlated MAX and OR-contained correlation run oracle alternatives while asserting the exact physical guard. Coverage reports the three new rule counts and residual-guard path count. Targeted goldens own per-row scalar 0/1/>1 behavior, error-path equivalence, NULL keys, joined/aggregate subqueries, nested grandparent correlation, and every blocked rule shape.
JoinKind::NullAwareAnti is an explicit left-only algebra operator, not an
ordinary Anti mode. A node owns two structurally distinct fields: predicates
select the right candidate set for a left row, while exactly one
null_aware_predicate is a typed equality between the left membership value
and the right membership value. Factories, physical lowering, memo validation,
and execution reject a missing, extra, or non-equality membership field. The
printer and EXPLAIN spell the fields as candidates=[...] and membership=....
For left row l, let C(l) be the right rows for which every candidate
predicate is TRUE under SQL 3VL. The interpreted specification emits l iff
C(l) is empty, or every membership comparison against C(l) is FALSE. This
is exactly Filter's l.x NOT IN (SELECT r.x FROM C(l)) result for every input:
- If
C(l)is empty, IN is FALSE and NOT IN is TRUE before the left value is inspected, so even a NULL left membership value is emitted. - If
C(l)is non-empty and the left value is NULL, every comparison is UNKNOWN, so NOT IN is UNKNOWN and the row is rejected. - If any non-NULL right value equals a non-NULL left value, IN is TRUE and NOT IN is FALSE, so the row is rejected regardless of duplicates or other NULLs.
- Otherwise, any NULL right value contributes UNKNOWN, making IN and NOT IN UNKNOWN; the row is rejected.
- The only remaining case is a non-NULL left value, a non-empty NULL-free candidate set, and no match. Every comparison is FALSE, IN is FALSE, and NOT IN is TRUE, so the row is emitted.
These cases are exhaustive, prove the 3VL coincidence, and pin the intentional difference from ordinary Anti: Anti treats UNKNOWN as a non-match and therefore emits a NULL-key left row, whereas NULL-aware Anti rejects it whenever the candidate set is non-empty. The oracle visits left rows and candidate right rows in input order; its selected-left output is therefore left-row-major.
The vectorized equality kernel evaluates the right child once and builds lookup-only state per equality-correlation key: candidate-set non-emptiness, right-membership NULL presence, and the typed set of non-NULL membership values. The uncorrelated case is the single global bucket. It then probes left rows in input order and implements the five oracle cases directly; no hash iteration produces output. NULL correlation keys have no TRUE candidate equality and therefore select the empty bucket. Shapes outside that exact hashable equality form use a deterministic left-row-major nested-loop semantic fallback rather than a skip or guard path. NULL-aware execution evaluates the right child before the left child, matching eager materialized uncorrelated subquery error observability while still building the right only once.
NotInToNullAwareAntiJoinRule matches only a whole top-level uncorrelated NOT
IN Filter conjunct and adds NullAwareAnti(P,Q,membership=x=q) plus any
residual Filter conjuncts to the same memo group. The original materialized
Filter remains first-class, so EXPLAIN shows both rule exploration and the
cost-selected winner. The proof is the exhaustive candidate-set argument
above with C(l)=Q; bag duplicates cannot change whether an equality is TRUE,
FALSE, or UNKNOWN, and the left-only join emits at most one copy per input left
row in the same order. When Q's projected identity can collide with a left
identity, a deterministic hidden right Project alias removes side ambiguity
without changing Q's values, order, or errors.
CorrelatedNotInToNullAwareAntiJoinRule accepts the Phase 21c equality-only
shape: every outer use is an immediate-depth, whole WHERE conjunct
outer_key = inner_key inside Project(Filter(Scan|Join)). It removes those
correlated conjuncts, appends deterministic __corr_key_N projections, clears
the proven-empty correlation set, and stores the key equalities as candidate
predicates; the original NOT IN equality remains the separate membership
predicate. For each fixed l, the candidate predicates are TRUE for exactly
the rows the per-invocation Filter retained, including the rule that a NULL on
either correlation side is UNKNOWN and selects no row. Thus the rewritten
C(l) is identical to the materialized C(l), after which the exhaustive 3VL
proof applies unchanged. Projection order, duplicates, left multiplicity, and
left-row-major output are preserved. Hidden correlation and membership names
are selected against the left output and existing right outputs, so even
shadowed self-scope identities remain side-unambiguous.
Both rules fail closed for leaves below AND/OR, scalar-subquery operands,
non-equality or non-immediate correlation, correlation in projection,
Aggregate/HAVING, JOIN ON, nested/transitive correlation, and result-shaping
operators. The uncorrelated rule also blocks sibling subquery predicates and a
left input containing embedded subqueries, preserving Q's eager-error order;
the correlated rule blocks sibling subquery predicates and nested subqueries
inside its right plan, preventing per-row errors from becoming eager build
errors. Any residual correlated shape remains oracle-defined and physical
lowering fails once with its source position. NULL-aware Anti never commutes or
associates, and LeftJoinToInnerRule is inapplicable. FilterIntoJoinRule may
move only a whole left-referencing conjunct into its preserved child; right,
mixed, empty-reference, and literal-only conjuncts stay above. Memo output
validation exposes only left identities.
Subquery blocks arrive from binding with checked-SUM input order permissions already pinned. Correlated splicing copies the existing nodes and their permissions, including the right Aggregate's pinned descendants; order permission is part of memo structural identity, so exploration cannot merge a pinned node with an order-relaxed one. A targeted checked-SUM-in-NOT-IN regression executes both materialized and NULL-aware alternatives and verifies that no commute/associate rule appears below the Aggregate.
Rules live as proof-bearing classes with two hosts. The standalone host remains a pure transform from a plan::LogicalPlan to either an equivalent replacement plan or std::nullopt; tests that exercise that path continue to use it. The memo host applies the same proofs to MemoExpressions and inserts equivalent expressions into the same group. When DropAlwaysTrueFilterRule proves that a filter is equivalent to its child, it inserts an explicit GroupRef rather than silently merging parent and child groups, preserving the acyclic memo invariant.
The driver traverses child-first, tries rules in vector order, applies at most one rewrite per pass, records the fired rule name, and repeats to a fixpoint with a hard max-pass bound. For the shipped default rules, termination is monotonic: constant folding removes non-canonical literal comparison leaves by replacing them with canonical booleans, then boolean algebra strictly reduces predicate tree size for TRUE OR x, FALSE OR x, TRUE AND x, and FALSE AND x; adjacent-filter merge removes a filter node while preserving predicate order; the always-false rule collapses a predicate list to one canonical false predicate; and the always-true rule removes predicates or an entire filter. No default rule reintroduces a non-canonical literal comparison, adjacent filter pair, canonical true predicate, or larger predicate list after simplification, so the bounded fixpoint is a guard against future cyclic rules rather than part of the proof.
Rewrite equivalence is tested in targeted rule tests by comparing unrewritten plans, standalone rewritten plans, and vectorized execution of the rewritten plans. The generated differential corpus now ingests each bound query into the memo, explores rules to fixpoint, extracts the deterministic canonical plan, and runs that plan through both engines against the unrewritten interpreted oracle. This protects the invariants that memo rules only add equivalent expressions and that vectorized execution matches the oracle for the same extracted logical plan.
Memo exploration walks groups by id, expressions by insertion index, and rules in default_memo_rules() order. It repeats until an iteration inserts no new expression. For the filter rules, termination follows from structural dedup plus monotonic simplification: constant folding only introduces canonical literal booleans, adjacent-filter merge removes a filter boundary, always-false canonicalization shortens a predicate list to canonical false, and always-true elimination removes true predicates or inserts a child GroupRef. Predicate pushdown only creates alternatives where a conjunct moves strictly downward to a child Filter, moves from Filter into a Join predicate list, or removes the original Filter by a GroupRef to the pushed expression group; it never pulls predicates back upward. For join transformations, termination follows from the finite set of table identities in the bound query, finite binary join trees over those identities, finite predicate placements, structural deduplication, and representative merging. Join commute/associate can regenerate shapes that expose pushdown again, but the memo closes those loops through structural deduplication and the max-iteration bound remains a fail-loud guard.
Join reordering rules are memo-only in Phase 5b; the standalone rewrite host does not include them because a pure tree rewrite commute rule would oscillate without a memo. JoinCommuteRule inserts Join(B, A, predicates) for Join(A, B, predicates) only in arbitrary-order INNER memo expressions. Inner join is symmetric under bag semantics, and bound predicates reference stable column identities rather than child positions. LEFT join does not commute because swapping children changes which side is preserved and which side is NULL-extended. The raw join node's internal column identity order flips, so this rule is admitted only for identity-addressed bound SQL contexts where the final Project fixes user-visible output names and order.
JoinAssociateRule rotates left-deep and right-deep three-way join fragments only when every join involved is INNER and every conjunct can be placed at a join node where all referenced tables are available. The new inner join must receive at least one predicate that connects its left and right child table sets; rotations that would require a new cross-product-shaped intermediate are skipped. INNER/LEFT and LEFT/LEFT associativity are invalid in general because NULL-extension timing and the preserved side can change. This is conservative: some valid SQL inner-join associations are intentionally not represented until the algebra has a more explicit cross-product/property model.
FilterIntoJoinRule is memo-only. For INNER Filter(P, Join(L, R, J)), each whole conjunct tree whose referenced binding identities are wholly contained in L becomes a Filter over L, each conjunct tree wholly contained in R becomes a Filter over R, and each comparison-leaf conjunct referencing both sides appends to the Join predicate list. Mixed-side OR/AND trees stay above the Join; this phase deliberately does not split OR trees or distribute predicates. Literal-only, unknown-scope, aggregate-output, and mixed-side non-leaf predicates stay above the Join. The proof relies on inner-join bag semantics and TRUE-only 3VL filtering: a one-side predicate that is TRUE keeps exactly the same candidate pairs before or after the join, while FALSE and UNKNOWN reject those pairs in either placement. A comparison leaf that reads both inputs is semantically a join predicate evaluated over the same row pair; NULL operands yield UNKNOWN and are rejected in both placements. For SEMI, ANTI, and NULL-AWARE-ANTI, the rule admits only the whole left-only move proved above; it never changes the right child, match/candidate predicates, or membership equality. For LEFT joins, pushing into the null-supplying side or converting WHERE predicates into ON predicates can preserve rows that the original WHERE would reject, so FilterIntoJoin remains disabled until a separate proof changes the join kind.
LeftJoinToInnerRule is the one Phase 20b outer-join simplification. It matches Filter(P, LeftJoin(L, R, J)) and adds Filter(P, InnerJoin(L, R, J)) to the Filter group only when a whole top-level conjunct is provably null-rejecting for the null-supplying right bindings. A comparison leaf qualifies when either operand is a right-side column: that operand is NULL on every extended row, so the comparison is UNKNOWN and Filter rejects it. Recursively, AND qualifies when either child qualifies, because the conjunction cannot be TRUE; OR qualifies only when every disjunct qualifies, because one non-rejecting disjunct could make the OR TRUE. IS NULL does not qualify because right_col IS NULL is TRUE on the exact extended row that distinguishes LEFT from INNER; null-check leaves are conservatively excluded from this comparison-rooted proof. Predicate trees stay intact. The new INNER join lives in its own group, the filtered INNER expression is inserted additively into the original Filter group, and the bare LEFT/INNER joins are never declared equivalent. Existing INNER-only commute, associate, and filter-pushdown rules can then explore the unlocked alternative.
FilterThroughAggregateRule is memo-only. For Filter(P, Aggregate(group_keys, aggregates, input)), a whole conjunct tree may move below Aggregate only when every column reference in every leaf exactly matches a grouping-key identity. The current binder represents HAVING grouping-key predicates as the original input identity, for example BoundColumnRef{"t1", "a"}, while aggregate outputs such as COUNT(*) and SUM(b) are BoundColumnRef{"", output_name}; any aggregate-output leaf therefore fails the exact grouping-key match and pins the whole tree above Aggregate. The proof is the grouping-key argument under 3VL TRUE-only filtering: group key values are constant across a group, so a key predicate that is TRUE keeps the same group/input rows in both shapes, while FALSE and UNKNOWN reject the group or input rows in both shapes. Aggregate-output predicates are computed after grouping and cannot move below their required scope. The fuzzer now covers NULL-affected grouping keys and HAVING predicates, and the rule proof does not rely on two-valued predicates.
Filter simplification rules and FilterThroughAggregateRule are unaffected by outer joins. Simplification rules rewrite predicate truth trees inside an existing Filter without crossing a Join boundary. FilterThroughAggregateRule matches Filter over Aggregate and moves only grouping-key predicates, so it does not reinterpret Join ON/WHERE placement or null-extension.
Order-relaxed comparison is a verification policy, not an execution behavior. The interpreted and vectorized engines must still produce the same deterministic result for the same logical plan, including stable-sort tie order and LIMIT prefix choice. When comparing different memo alternatives for the same unordered join query whose plan carries arbitrary-order permission, tests compare canonical row-sorted bags by output identity. For ordered cross-plan alternatives, stable sort preserves each alternative's input order for equal keys, and different join orders can have different tie order. The honest non-LIMIT contract is therefore: identical output column identities, bag equality, and explicit sortedness by the ORDER BY keys for each result. Non-join, non-ordered corpus queries keep exact-order equality.
LIMIT has a separate cross-plan verification contract because equivalent alternatives may legitimately choose different rows when the cut falls inside an unordered bag or an ORDER BY tie run. Same-plan interpreted vs vectorized execution remains exact byte equality. Cross-plan comparisons against alternatives, extract_best, or rewritten plans validate that a limited result is a valid answer rather than a specific prefix: row count must equal min(n, full_unlimited_count); the result row multiset must be contained in the full unlimited oracle result multiset; and with ORDER BY, the limited result must be sorted by the ORDER BY keys and its key-tuple multiset must equal the first min(n, full_unlimited_count) key tuples from the fully sorted unlimited oracle result. DISTINCT without LIMIT keeps the standard contracts: exact same-plan equality and cross-plan bag/sortedness equality, which is exact set equality because duplicate output rows have been removed.
sql_fuzz_differential is the Phase 13 correctness capstone, extended in Phase 16a for predicate-core NULLs. It is test-side only and uses fixed std::mt19937_64 seeds in ctest, with an optional single-seed command-line replay path for failures. Each seed builds a catalog with 2-4 int64 tables, 2-4 columns, and 0-12 rows per table. Values come from a skew-heavy pool containing duplicates, negatives, zero, one, int64 extremes, and NULLs in nullable columns, so joins, predicates, DISTINCT, and aggregate overflow paths collide often.
The fuzzer generates bindable SQL by construction. It chooses table aliases before emitting references, always uses unique range aliases so self-joins are legal, draws predicates and projections from schema-derived column pools, and emits NULL literals plus IS NULL/IS NOT NULL predicate leaves. It restricts aggregate queries to binder-valid shapes: non-grouped columns appear only inside aggregates, HAVING uses grouping keys and aggregate calls, DISTINCT orders by output names, and GROUP BY fallback ORDER BY keys are only sampled when the emitted output exposes the same key value needed by the sortedness verifier. Phases 22b-23 add binder-valid Window generation: all seven functions appear as whole SELECT items; aggregate Window calls mix whole-partition definitions with ordered default RANGE, explicit RANGE, and explicit ROWS cumulative frames; grouped inputs use grouping keys or aggregate calls such as SUM(SUM(x)) OVER (...); and final ORDER BY may use Window output aliases. Phase 16b removes the earlier nullable-column exclusion, so generated aggregate arguments, GROUP BY keys, DISTINCT outputs, ORDER BY keys, Window partition keys, and Window order keys can all contain NULLs. A parse or bind error from a generated query is therefore a generator bug and fails with the seed, SQL text, and full catalog dump.
Every generated query runs the full verification stack: unrewritten interpreted oracle, standalone rewritten interpreted and vectorized execution, all memo root alternatives through both engines, and extract_best through both engines. Result comparison reuses the established contracts and compares validity as well as typed payloads: exact byte/cell equality for same-plan interpreted/vectorized execution, sorted-bag equality plus sortedness for ordered or join cross-plan alternatives, and the LIMIT valid-answer contract for top-level LIMIT. The sortedness verifier uses the engine ORDER BY rule: NULL compares larger than every typed non-NULL value, so ASC places NULLS LAST and DESC places NULLS FIRST. Runtime error equivalence remains for signed int64 SUM overflow; empty-input and all-NULL-input SUM/MIN/MAX now produce NULL results instead of accepted errors. Phase 17b widens generated catalogs with string columns using duplicate-heavy pools, empty strings, and NULLs. Query generation is type-correct by construction: comparison operands come from same-type expression pools, string literals are only compared with string expressions, SUM samples only int64 columns, and string columns can appear in joins, GROUP BY, DISTINCT outputs, ORDER BY keys, Window partition/order keys, Window COUNT, and Window MIN/MAX. Phase 20b generates INNER, LEFT, and RIGHT edges in the same chains, biases equality keys toward columns whose generated data actually contains NULL, and reports join-kind, mixed-chain, NULL-key, simplification, commute, and association coverage. Phase 22b additionally reports Window function, partitioning, ordered/unordered rank, NULL-key, string-key/string-argument, joined/grouped/HAVING, multi-window, and outer ORDER BY coverage; Phase 23 adds whole-partition/default-RANGE/explicit-RANGE/explicit-ROWS frame-path coverage. All outer and Window plans use the same interpreted/vectorized, alternatives, and extract_best verifier paths; accepted overflow paths are compared by error category rather than text. The fuzzer intentionally does not generate EXPLAIN because EXPLAIN observes planner diagnostics rather than query semantics; if an EXPLAIN query is supplied to the shared differential verifier, it is treated as a terminal statement and the interpreted/vectorized EXPLAIN batches are compared exactly.
Phase 24 retains the fixed 160 seeds and widens the NOT IN lanes with equality-correlated shapes plus one guaranteed empty and one guaranteed NULL-bearing right candidate set per seed. Default-corpus assertions require nonzero uncorrelated and correlated NULL-aware rule firings, native NULL-aware execution, and both trap paths. The delivered run reports 195 uncorrelated firings, 27 correlated firings, 1,130 native NULL-aware execution paths, 160 empty-right paths, 160 NULL-bearing-right paths, 5,381 memo alternatives, and 13,223 total execution paths without hitting extraction bounds.
Phase 22 adds Window to the parser, binder, logical and physical algebra, interpreted oracle, vectorized execution, memo, costing, printers, EXPLAIN, differential fuzzer, and benchmark suite; Phase 23 adds cumulative aggregate frames. A window expression is a whole SELECT item with an optional alias; it cannot appear in WHERE, HAVING, GROUP BY, a nested expression, or another function argument. The grammar is func(...) OVER ([PARTITION BY keys] [ORDER BY keys [ASC|DESC] [, ...]] [frame]). ROW_NUMBER, RANK, and DENSE_RANK retain their Phase 22 ordering semantics; either supported explicit frame may be spelled on them, but ranking remains frame-insensitive. For SUM, COUNT, MIN, and MAX, omitting both OVER ORDER BY and an explicit frame selects WholePartition, preserving Phase 22 byte-for-byte behavior. OVER ORDER BY with no explicit frame selects the SQL-standard RangeCumulative default. The only explicit frame spellings accepted are RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW and ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, bound as RangeCumulative and RowsCumulative respectively. An explicit frame is also meaningful without OVER ORDER BY: all partition rows are one RANGE peer group, while ROWS follows partition input order. Every other frame spelling fails with positioned unsupported frame at the first token that makes the supported phrase impossible. In particular, bounded PRECEDING/FOLLOWING, UNBOUNDED FOLLOWING, BETWEEN CURRENT ROW AND CURRENT ROW, GROUPS, shorthand bounds, and frame exclusions are unsupported. OVER, PARTITION, ROWS, RANGE, and BETWEEN remain contextual grammar words rather than globally reserved identifiers, preserving the pre-window identifier and alias surface outside recognized window syntax.
Window follows SQL evaluation placement: Scan/Join -> WHERE Filter -> Aggregate -> HAVING Filter -> Window -> Project -> Distinct -> final Sort -> Limit. A grouped query therefore exposes only grouping keys and Aggregate output identities to Window. A direct non-grouped input such as SUM(b) OVER (...) is legal only in a non-aggregate query; after grouping, the equivalent legal input is a grouping key or an aggregate output such as SUM(SUM(b)) OVER (...). Window output identity is the child schema followed by one unqualified typed identity per canonical window spelling. The final Project maps those identities to aliases and SELECT-list order. Identical canonical definitions may share the same internal result identity, as ordinary aggregate definitions already do.
All window definitions in one SELECT share one unary Window node but evaluate independently against the same immutable child batch. Different partition and order specifications do not feed one another. Window never changes row order: its output row i is child row i with additional values. Final ORDER BY is the only ordering operator above it.
Partition construction reuses GROUP BY's distinct-style typed key equality. NULL key slots equal NULL key slots, so all rows with the same NULL pattern belong to one partition. Partition state is created in first-appearance order, and rows enter each partition in child input order. This deliberate reuse does not change predicate or join equality, where NULL comparisons remain UNKNOWN.
Within each partition, ROW_NUMBER assigns 1..n in the OVER ordering. A stable sort makes child input order the deterministic tie-break for equal keys. With no OVER ORDER BY, input order is the ordering. RANK and DENSE_RANK use standard gap and no-gap peer numbering. Peer equality compares all typed order-key values; two NULL values are peers. NULL is the largest key value before direction is applied, so ASC places NULL last and DESC places NULL first. With no OVER ORDER BY every row is a peer: both rank functions return 1. Ranking output is INT64.
Aggregate windows reuse the ordinary aggregate state machine. COUNT(*) counts all frame rows; COUNT(col) counts non-NULL values; SUM, MIN, and MAX ignore NULL. A whole-partition result is copied to every row in that partition. A ROWS result is finalized after each row in stable window order, so equal-key rows can receive different prefixes. A RANGE result is finalized only after scanning an entire peer group and copied to every row in that group: its frame contains every preceding peer group plus the complete current group, through the last peer. Peer equality uses all typed OVER ORDER BY key values and the same shared comparator as ranking; equal NULL slots are peers, and NULL remains the largest value before ASC/DESC direction is applied. Empty input produces no Window rows. A prefix with no non-NULL aggregate argument yields zero for COUNT and typed NULL for SUM/MIN/MAX, including leading-NULL running prefixes. String MIN/MAX retain exact byte-sequence ordering; SUM remains INT64-only with no implicit coercion. SUM, COUNT, and ranking-ordinal overflow remain loud categorized INT64 runtime errors.
RANGE peer-boundary publication is load-bearing for optimizer correctness. For a row, the visible frame is determined by its complete ORDER BY key and the partition's key-ordered rows; equal-key rows cannot reveal their incidental input order because all peers receive the same value. Thus join commute/associate may reorder equal-key rows without changing a RANGE result. Checked RANGE SUM additionally sorts each peer group's non-NULL INT64 arguments ascending before applying __builtin_add_overflow at each prefix step. Key order fixes the order between peer groups, and this canonical within-peer order makes both the value and overflow category a function of key-group contents rather than stable tie order. Canonical checked accumulation can therefore report overflow on an intermediate even when a differently ordered mathematical sum would fit; that canonical outcome is the specification for both engines and every memo alternative.
ROWS deliberately makes peer order observable. Its stable sort retains child input order as the tie-break for equal OVER keys, the same deterministic contract as ROW_NUMBER, and every ROWS aggregate therefore pins its complete child subtree against order-changing transforms. Checked ROWS SUM uses __builtin_add_overflow for each input-ordered prefix step, so both its values and its possible intermediate overflow follow that pinned order. Whole-partition SUM keeps its Phase 22 pin because its checked accumulation is likewise input-order-sensitive.
Every ordinary Aggregate containing checked SUM independently pins its complete relational input subtree at the end of binding that query block. This rule applies to a main block, a Window child, and every predicate-owned or scalar-expression-owned subquery before that subplan becomes opaque to its owner or is later spliced into the memo by decorrelation. The soundness reason is direct: join commute or association can change SUM's input sequence, and checked intermediate overflow makes success versus error observable even when the mathematical total is unchanged. Pinning the Aggregate input is sufficient because all order-changing joins that can affect its accumulation are descendants of that input; the Aggregate and its ancestors need no additional pin. COUNT/MIN/MAX Aggregate inputs and direct RANGE window aggregates therefore retain their verified alternatives, while predicate-placement rewrites that preserve stream order remain available. Binding asserts this invariant before returning each independently bound query block, so memo insertion never has to rediscover expression-owned subplans to repair their permissions.
The vectorized Window operator mirrors the oracle instead of introducing a fallback path. Physical Window carries each definition's bound frame enum unchanged from logical lowering. For each definition, vectorized execution compiles partition keys, order keys, and any aggregate argument once against the child batch. Partitions are built by probing a validity-aware HashKey map that uses GROUP BY/DISTINCT-style typed NULL equality; the map is lookup-only, while a separate vector records partitions in first-appearance order and rows in Window input order. Ranking and cumulative frames copy each partition's physical row ids and use the shared stable sort-key comparator. ROWS publishes after each ordered row; RANGE detects typed peers, updates through the peer boundary, and then publishes the shared result. Aggregate windows reuse the existing checked, NULL-skipping kernels, including the canonical RANGE SUM peer update. The operator stores Window values by original physical row id and gathers both child columns and Window columns through the immutable input selection vector, so output rows remain in the Window node's input order even after upstream filters or sorts.
Window is a rewrite barrier. No filter rule pushes a Filter through it, including filters that reference a window output; partition-key-only pushdown remains future proof work. Memo exploration still descends into an order-safe Window child, so already-proven join transformations remain available below RANK, DENSE_RANK, RANGE COUNT/SUM/MIN/MAX, and whole-partition COUNT/MIN/MAX until it reaches any independently pinned ordinary Aggregate SUM input. ROW_NUMBER, every ROWS aggregate, and whole-partition SUM trigger the Window-specific deterministic-input pins described above. This is a fail-closed proof boundary, not a general ban on optimizing below Window.
The memo hashes and compares every Window definition field, including the effective frame enum, and reconstructs Window in canonical, alternative, and best extraction. Costing preserves input cardinality and uses the documented conservative per-definition formula above. The deterministic SQL fuzzer generates Window queries across all seven functions, whole-partition and cumulative frame variants, partition/order variants, NULL-heavy and string keys, joined/grouped/HAVING inputs, multiple Window definitions, and final ORDER BY aliases; these queries run through unrewritten, rewritten, memo-alternative, and extract_best interpreted/vectorized verification. The remaining unsupported frame surface is every bound other than unbounded-preceding through current-row, plus GROUPS, exclusions, and other SQL frame modifiers.
The aggregate SQL slice supports COUNT(*), COUNT(col), SUM(col), MIN(col), and MAX(col) in the SELECT list and HAVING/ORDER BY positions, plus GROUP BY over bound column references. Output names are explicit SELECT aliases when present, otherwise canonical expression spellings such as COUNT(*), SUM(a), or SUM(t.a), and they are deduplicated by the projection output-name policy. Aggregate output identities use canonical aggregate spellings directly; grouping keys keep their binding-qualified column identities. A projected aggregate alias therefore becomes a Project output over the canonical aggregate output column, for example total=col(SUM(b)).
Binding owns aggregate grammar constraints. With GROUP BY, every projected or HAVING column reference outside an aggregate must be a grouping column. With an aggregate or HAVING and no GROUP BY, projected and HAVING column references outside aggregates are rejected because the query has one global group. Nested aggregates are rejected as bind errors. HAVING aggregate expressions are bound to canonical aggregate output columns. If HAVING references an aggregate that is not projected, the binder adds that aggregate to the Aggregate node and the final Project drops it.
The grouped or global HAVING logical shape is Project(Filter(HAVING, Aggregate(input))), optionally wrapped by Sort. Without HAVING it remains Project(Aggregate(input)). The Aggregate node is placed after Scan/Join/Filter and before Project. It emits one row per distinct grouping-key combination, in the first-appearance order of the group in the input. Grouping uses distinct-style equality: two key tuples are the same when every present value matches and every NULL slot appears in the same position. This is intentionally separate from comparison and join equality, where NULL = NULL is UNKNOWN and never a TRUE join match. Global aggregation has one group over the whole input, including empty input, before HAVING applies. A global HAVING predicate keeps that one group only when the predicate evaluates TRUE; FALSE and UNKNOWN reject it, including UNKNOWN from NULL aggregate results. COUNT(*) counts rows, COUNT(col) counts only non-NULL inputs, and SUM, MIN, and MAX ignore NULL inputs. Grouped empty input emits zero rows; global COUNT over empty input emits 0; SUM, MIN, and MAX over empty input or over a group with zero non-NULL inputs emit NULL. This revises the Phase 8 throw policy, which existed only because the NULL-free slice had no missing-result value. SUM still detects signed int64 overflow and raises a runtime error rather than wrapping.
The interpreted oracle uses an insertion-order vector of group states and a deterministic lookup keyed by group values. The vectorized aggregate uses an unordered lookup only to find existing groups; output order is emitted exclusively from the separate group-state vector populated in selected input order. Hash table iteration is never observable.
SELECT DISTINCT is a result-shaping operation over complete projected rows. The logical placement is after Project, and after Aggregate/HAVING when aggregation is present. It is legal with GROUP BY and legal over global aggregate output. DISTINCT uses the same distinct-style equality as GROUP BY, so matching NULL slots compare equal for deduplication. The interpreted oracle and vectorized engine both preserve the first appearance of each complete output row and use lookup structures only to detect prior rows; lookup iteration order is never observable.
LIMIT n is a top-level result-shaping operation after optional Sort. It keeps the first n rows of its input and preserves the input schema, so LIMIT 0 returns zero rows with the projected output columns. Without ORDER BY the selected prefix is deterministic for a specific plan but is not a cross-plan semantic commitment. With ORDER BY the limit is applied after sorting.
The frontend supports inner join chains with optional table aliases:
SELECT select_list
FROM t1 [AS] x [INNER] JOIN t2 [AS] y ON boolean-predicate
[JOIN t3 [AS] z ON boolean-predicate ...]
[WHERE boolean-predicate]
Join chains bind as left-deep logical plans. Join predicates live on the Join node. A join node's output identity and order are deterministic: all left child columns, followed by all right child columns. Scans materialize internal identities as binding.column; projection output names are separate user-visible names. For unaliased tables, binding equals physical table name, so existing query identities remain unchanged.
Qualified projected columns use their qualified spelling as the output name, so SELECT x.a, y.a ... produces output columns x.a and y.a. Unqualified projected columns use the bare column name, so duplicate output names are still rejected by name.
The interpreted oracle implements nested-loop inner join with bag semantics. The row order is part of the SQL engine contract: for each left row in input order, visit each right row in input order, emitting every pair whose ON conjuncts are TRUE under SQL 3VL. FALSE and UNKNOWN pairs are rejected. Duplicate matches multiply, and an empty side yields zero output rows with the deterministic joined column order. Equality on NULL join keys is UNKNOWN, so NULL never matches anything, including another NULL.
The vectorized join implements the same contract. It extracts usable equi-key conjuncts where BoundColumnRef = BoundColumnRef has exactly one side in each input. When such keys exist, it builds a hash table on the right input and stores selected right row ids in per-key vectors in right-input order, but it skips any build or probe row with a NULL in any equi-key column. This prevents sentinel-style hashing from making NULL equal NULL. The unordered hash table is lookup-only: output is produced only by probing selected left rows in left-input order, then walking the matched right-row vector in insertion order. Hash bucket or table iteration must never influence result order. Non-equi, literal, same-side, IS NULL, IS NOT NULL, or otherwise complex conjuncts remain residual predicates evaluated after a key match with the same TRUE-only 3VL rule. If no usable equi conjunct exists, vectorized execution falls back to a nested-loop join with the oracle's left-row-major visitation order.
The Phase 20 outer-join arc supports LEFT [OUTER] JOIN and RIGHT [OUTER] JOIN from SQL through both engines. Binding normalizes RIGHT joins to LEFT joins by swapping the accumulated left-deep input with the new right table scan. This is legal because bound predicates, projections, aggregates, filters, and sort keys consume stable binding-qualified column identities rather than child positions. The normalized Join node's raw output identity order remains left child then right child, so RIGHT join normalization changes internal identity order; the final Project is responsible for SQL-visible column order, and goldens pin projected RIGHT join output exactly.
The interpreted LEFT JOIN oracle is deterministic and left-row-major. For each left row in input order, it visits right rows in input order and emits every pair whose ON predicate list evaluates TRUE under existing SQL 3VL. FALSE and UNKNOWN do not match. If no right row matches, the oracle emits the left row once and appends NULL for every right column. A left row with a NULL join key is therefore unmatched for equality predicates and is NULL-extended. WHERE, GROUP BY, aggregates, DISTINCT, ORDER BY, and LIMIT consume those NULL-extended rows through their existing semantics; notably, a predicate placed in ON can preserve an unmatched left row while the same predicate in WHERE can reject the NULL-extended row.
The vectorized LEFT hash join retains the existing right-side build and skips NULL key rows. It probes selected left rows in order, visits each per-key right-row vector in build-insertion order, and marks a left row matched only after every residual ON conjunct evaluates TRUE for a candidate. If no candidate passes residuals, it appends the real left cells once plus one typed NULL for every right column through validity-aware builders. A NULL probe key therefore takes the same unmatched path. With no usable equi key, the vectorized nested-loop kernel performs the same matched-flag logic over right rows in order. INNER uses compile-time-specialized versions of the same loops with unmatched-state work removed, preserving its existing output and hash lookup-only ordering.
Optimizer discipline remains conservative. JoinCommuteRule, JoinAssociateRule, and FilterIntoJoinRule require INNER joins and never fire directly on a LEFT node. LEFT joins do not commute, inner/outer associativity is invalid in general, and WHERE-to-ON or null-supplying-side pushdown can change which NULL-extended rows survive. LeftJoinToInnerRule is the sole proof-bearing bridge described above. Memo structural identity, dumps, extraction, and costing include join kind so INNER and LEFT expressions cannot share an equivalence group by accident. The Phase 20a LEFT cardinality formula max(inner_join_estimate, left_rows) remains unchanged in 20b; vectorized implementation and contextual simplification require no cost-model adjustment.
Scan reads storage by physical table name and creates binding-qualified column identities plus an identity selection vector in table row order. Scan qualification does not copy row values or validity: the qualified scan batch reuses the source columns' shared immutable storage, and any later append or reserve on a copied column detaches first. Filter compiles predicate trees once against the input batch, evaluates each tree to a pair of aligned byte masks over the filter domain, and returns a newly allocated shared_ptr<const vector<size_t>>; downstream operators cannot mutate a handed-off selection. The mask pair is is_true plus is_known: TRUE is (1,1), FALSE is (0,1), and UNKNOWN is (0,0). Comparison leaves set is_known = left_present & right_present and is_true = is_known & comparison_result, with both int64 and string leaves reading pre-resolved contiguous values directly and string comparisons using exact lexicographic std::string ordering. IS NULL and IS NOT NULL leaves are always known and derive is_true from scalar validity or literal nullness. Kleene AND uses true = lt & rt, false = (lk & !lt) | (rk & !rt), and known = true | false; Kleene OR uses true = lt | rt, false = (lk & !lt) & (rk & !rt), and known = true | false. Top-level conjuncts fold with the same AND algebra before converting the final is_true mask back to row ids, preserving input order and keeping only TRUE rows. The filter domain is the full batch when the input selection is the scan-adjacent identity/full-row selection; otherwise masks are dense over selection positions and each position maps back through the input selection vector. Join validates both child views, materializes a joined ColumnarBatch, then returns a fresh identity selection over that batch so downstream filters and projections cannot mutate child state. Join residual predicates still use the row-pair evaluator because their domain is a pair stream rather than one contiguous batch selection. Project walks the selected row ids in order, evaluates scalar expressions including NULL literals, and builds output columns through ColumnarBatch::add_column, preserving equal row counts, validity, type, and SELECT-list order. Sort creates a new row-id order with std::stable_sort; NULL sort keys compare larger than every int64 or string, yielding NULLS LAST for ASC and NULLS FIRST for DESC. Because the logical shape is Sort(Project(child)) and the slice permits both projected output-name keys and unprojected FROM-scope keys, Sort executes Project-shaped children by building a private sort batch from Project outputs plus any missing source key columns, sorting that batch, and materializing only the Project output columns in sorted row order.
Before row loops, vectorized operators compile bound expressions against the current batch view. Physical execution selects an Int64Only dispatch for plans whose scanned schemas and bound expressions are int64-only, and a general typed dispatch when any scanned column, expression, key, aggregate, sort key, or predicate can be string. Both dispatches share the same deterministic operator traversal; int64-only compiled columns still hold direct int64 vector pointers, while typed compiled columns additionally carry string vector pointers and a ColumnType tag. A compiled scalar stores an int64/string/NULL literal or direct pointers to immutable typed column values plus optional validity vectors; compiled predicate, join predicate, projection, sort-key, group-key, aggregate-argument, distinct-key, and materialization structures reuse those pointers. An all-present column carries a null validity pointer, preserving the NULL-free fast path. The only column-name lookups happen while compiling at operator boundaries, after validate_view has checked selection rows. Filter mask leaves, projection, sort comparison, distinct key building, aggregate key/argument reads, hash-join key/residual evaluation, join output append, and final materialization then index contiguous column vectors directly in deterministic selection order. Hash join keys contain typed values and skip any build or probe row with a NULL key slot; GROUP BY and DISTINCT keys contain typed values with distinct-style NULL slots. Hash tables remain lookup-only for join/group/distinct; output order still comes from existing selected-row, group-state, or join-probe traversal, never from unordered iteration.
sql_bench is a standalone benchmark executable, not a CTest test. It uses deterministic generated tables, parses and binds each SQL query once, runs interpreted and vectorized execution on the same bound logical plan, prints a row-count/checksum correctness cross-check before trusting timings, and reports min/median wall-clock timings from std::chrono::steady_clock. Benchmark evidence must come from an optimized Release build, for example cmake -S . -B build-bench-o2 -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS_RELEASE="-O2 -DNDEBUG" followed by cmake --build build-bench-o2 --target sql_bench; the default smoke build remains timing-free.
The vectorized engine should never outrun the oracle. Add interpreted semantics first, then prove vectorized operators match it.