Skip to content

optimizer-rules.md

Latest commit

 

History

History
66 lines (52 loc) · 55.5 KB

optimizer-rules.md

File metadata and controls

66 lines (52 loc) · 55.5 KB
Raw

Optimizer Rules

Stability: Internal — see Stability Tiers.

The catalog of optimizer rewrite rules — one entry per rule, grouped by the src/planner/rules/ subdirectory it lives in. Deep-dives on the materialized-view, constant-folding, predicate and cardinality families live in Optimizer Rule Families; the pass framework these rules register into, and the audit discipline every rule declares, live in the optimizer hub.

Optimization Rules

Rules are organized by optimization family in src/planner/rules/:

Access Path Selection (access/)

  • ruleSelectAccessPath: Chooses between sequential scan, index scan, and index seek for both primary and secondary indexes. Collation cover: an index seek is only a complete substitute for a predicate when the index column's collation equals the predicate's effective comparison collation, resolved at plan time exactly as the runtime comparison emitters resolve it (the symmetric provenance lattice — explicit COLLATE > declared column collation > defaults; each BETWEEN bound resolves independently by the constraint's op). On an equality mismatch the rule classifies the cover per consumed seek constraint: a coarser index (BINARY predicate over a NOCASE/RTRIM index) over-fetches a provable superset, so the seek is kept and the predicate re-applied as a residual Filter; a finer index (which under-fetches) declines the seek entirely — SeqScan with the full predicate as a residual. Range / prefix-range / OR_RANGE seeks are stricter: a collation mismatch reorders the walked window rather than producing a superset, so any mismatch declines. A BINARY range over a BINARY index always reproduces the predicate; a collation-matched non-BINARY range does so only when the module's runtime filters and early-terminates the walk under that same index collation, advertised via BestAccessPlanResult.honorsCollatedRangeBounds — both the in-memory vtab and the store module set it, so matching-collation ranges seek on both backends, while a module that bound-filters BINARY keeps the conservative decline. The cover logic lives in the rule so it covers every index-style module uniformly (a module that matches constraints to index columns by position alone never sees collation). See tickets/complete/index-collation-mismatch-residual-filter, tickets/complete/memory-range-seek-collation-bounds, and tickets/complete/store-range-seek-collation-bounds.

Aggregation (aggregate/)

  • ruleAggregatePhysical: Cost-based selection between StreamAggregateNode and HashAggregateNode. Scalar aggregates (no GROUP BY) always use stream. Already-sorted input always uses stream (preserves ordering). Unsorted input compares sort+stream cost vs hash cost and picks the cheaper option.
  • ruleGroupByFdSimplification: Drops GROUP BY columns that are functionally determined by other GROUP BY columns under the aggregate-output FDs and equivalence classes (PK / UNIQUE / EC bridges; FK-derived FDs when that ticket lands). Each dropped column is re-emitted as a MIN(<original-column>) picker aggregate, with the original output attribute ID preserved via AggregateNode.preserveAttributeIds so downstream Filter/Sort/Project bindings survive untouched. A picker lands in the aggregate block, behind the surviving group keys, so the rewrite can permute the output positions; when it does, the rule caps the new aggregate with a ProjectNode re-emitting the same attribute IDs in their original order — positions matter to the consumers that bind by position (the statement result when the aggregate is the query root, insert … select, a union arm). Targets the common FK-join-then-aggregate shape (e.g. GROUP BY c.id, c.name, c.email where id is the PK) — cuts hash-key width and sort-key width before ruleAggregatePhysical makes its stream/hash choice. Runs in the Structural pass (after aggregate-predicate-pushdown so filter-derived ECs are on the source, before ruleAggregatePhysical in the Physical pass). Skips when fewer than two GROUP BY columns are bare ColumnReferenceNodes. See Functional Dependency Tracking for the propagation rules the rule consumes.

Caching (cache/)

  • ruleCteOptimization: Adds caching to frequently-accessed CTEs
  • MaterializationAdvisory: Global cache-injection analysis; a dedicated custom-execute pass (PassId.Materialization, order 35) over the whole plan, not a per-node rule.
  • ruleMaterializedViewRewrite: Automatic materialized-view query rewrite (read side). Rewrites an arbitrary scan-projection-filter, 1:1-join, or grouped-aggregate query that never names an MV to scan (and, for an aggregate rollup, re-aggregate) the MV's backing table when a covering MV answers it — including eliminating a 1:1 inner/cross join at read time. Registered on both Project (projection-filter + join arms) and Aggregate. See Rule Families § Materialized-view query rewrite (read side).
  • ruleMutatingSubqueryCache: Ensures mutating subqueries execute once
  • ruleScalarCSE: Scalar common subexpression elimination. Detects duplicate deterministic scalar expressions across a ProjectNode and its child chain (Filter, Sort), injects a lower ProjectNode that computes each deduplicated expression once, and replaces duplicates with column references. Skips bare column references, literals, and non-deterministic expressions. Runs in the Structural pass.

Retrieve (retrieve/)

  • ruleProjectionPruning: Prunes unused inner projections in Project-on-Project patterns (common after view expansion). Collects attribute IDs referenced by the outer project's scalar expressions, then filters the inner project to only those projections whose output attributes are referenced. Skips when all inner projections are used or pruning would yield zero projections. Runs in the Structural pass (between distinct-elimination and predicate-pushdown).

Sort (sort/)

  • ruleOrderByFdPruning: Drops trailing ORDER BY keys functionally determined by the leading bare-column keys under the source's FDs and equivalence classes (PK-driven, EC-driven via WHERE a = b, etc.). Walks the keys front-to-back maintaining determined = closure({leading bare-column source-indices}, fds, ECs); drops any subsequent bare-column key whose source-attribute index is already in determined. Non-bare-column keys (expressions) are opaque — they neither contribute to nor consume the determined set, and are never droppable. The rule reasons in source-attribute-INDEX space (positions in source.getAttributes()) since node.source.physical.fds / equivClasses are indexed that way. Direction and NULL placement of the dropped trailing key are irrelevant — once a preceding key pins every value of that column to a single value per equivalence group, the trailing key cannot reorder anything. Skips when fewer than two keys are present, or when no keys are droppable. Runs in the Structural pass, which is automatically before monotonic-limit-pushdown (PostOptimization) so single-key reductions enable the pushdown. See Monotonic LIMIT/OFFSET pushdown for the load-bearing interaction.

Join (join/)

  • ruleJoinPhysicalSelection: Selects hash join, merge join, or index-nested-loop over the plain nested loop for equi-joins when cheaper. Four-way cost comparison (nested-loop vs hash vs merge vs index-NL). Supports INNER, LEFT, SEMI, and ANTI join types; declines outright when either side reads columns produced by the other (e.g. JOIN LATERAL, which must keep the nested-loop driver — correlation to a scope outside the join is safe and does not decline; the guard doubles as the index-NL rewrite's idempotence check). The index-NL candidate (join/index-nested-loop.ts) keeps the logical JoinNode and its nested-loop emitter but replaces the right side's unconstrained access leaf with a correlated IndexSeekNode seeking on outer-row column references — one module-answered equality seek per outer row; because the JoinNode survives, exists … as existence joins can take this path (hash/merge still decline them). See Optimizer Joins § Index-Nested-Loop Join. Merge-join recognition here is positional on physical.ordering.
  • ruleMonotonicMergeJoin: Recognises merge-join opportunities whenever both sides advertise MonotonicOn on the equi-pair attributes — strictly broader than ordering-based recognition. Picks up cases the ordering-based rule misses (notably parent joins on a child MergeJoin's right-side equi-pair attribute, where the child's physical.ordering reflects only the left side but monotonicOn covers both). Single driving equi-pair in v1; remaining equi-pairs become residual conjuncts. Defers to ruleJoinPhysicalSelection whenever ordering already covers all pairs (so multi-key merge joins keep full unique-key propagation), and shares its sibling-reference guard (a side reading the other's columns must keep the nested-loop driver). Runs in PostOptimization, ahead of ruleJoinPhysicalSelection.
  • ruleKeySetSeek (access/rule-key-set-seek.ts; registered twice — id key-set-seek anchored on the hash semi join, id key-set-seek-merge anchored on the merge semi join, which is where the common IN-on-primary-key shape lands because both sides advertise a key walk): Replaces a single-equi-pair, no-residual SEMI join whose probe side peels (through Alias / trivial Project / Filter) to an unconstrained every-row leaf — or to an IndexSeek carrying pushedConstraints, whose recorded predicate is re-applied as a Filter directly above the new node — with a KeySetSemiJoinNode. The node drains the key source once and always probes every target row against the set — the hash semi join equivalent — and, when the distinct key count is ≤ min(1000, module break-even), rewrites the leaf's FilterInfo into an ordinary single-column plan=5 multi-seek over just the matching index windows. The unconditional probe means a seek can only over-fetch (trimmed), never change the answer; the gates prevent an under-fetch: the target and key types sharing one seek key space (sharesSeekKeySpace — identical types, or any two of INTEGER / REAL / NUMERIC, whose keys are identified by value rather than by JS representation at the probe, in the memory BTree comparators and in the store's byte encoding; the key value is never coerced), no semantic-ordering type, collation cover not MISMATCH_UNSAFE, the module claiming a runtime-set IN on one resolvable single-column index with no residualFilter, and a break-even ≥ 1 interpolated from its own costs at engine-synthesized probes (an invalid answer declines rather than throwing). Also declines on side effects, a correlated or non-deterministic key source, a leaf with a pushed limit/offset, and a leaf whose emission order absorbed a SortNode (orderingLoadBearing from grow-retrieve's sort absorption) unless the seek reproduces that order (seekPreservesTargetOrder, exported next to the node: the seek index IS the walk index, single key column, and the leaf's advertised order matches that key column — then a multi-seek emits a subsequence of the walk, which is still in walk order, so the absorbed Sort stays served; false for every IndexSeek target, so an absorbed-Sort seek leaf always declines). The IndexSeek arm adds its own gates: recorded pushedConstraints must exist and combine to a predicate (a seek the rule cannot describe must not be displaced), that predicate must contain no relational node (the rule runs PostOptimization — a re-inserted subquery would reach emit unphysicalized), and the seek's subtree must be uncorrelated (an index-nested-loop per-outer-row seek would drain the key source once per outer row, turning a linear plan quadratic); the break-even for a seek target solves the module's runtime-set cost line against the leaf's own recorded seek cost — the plan actually displaced — rather than the plain-scan cost. Under the same predicate KeySetSemiJoinNode.computePhysical claims the target's ordering / monotonicOn (derived per call, never a stored flag, so a leaf rebuild through withChildren cannot leave it stale); otherwise it claims neither, matching BloomJoinNode. The merge anchor adds two gates the hash anchor does not need: seekPreservesTargetOrder must hold (a merge semi join propagates the probe side's ordering upward, so an ancestor — or an already-dropped Sort — may depend on it; the hash join propagates none, so nothing above it can), and the key source's physical row estimate, when present, must not exceed min(maxKeys, breakEvenKeys) — past the runtime's own seek threshold the pushdown is very unlikely to fire and the rewrite would trade a streaming merge for a pointless key-set materialization. That second gate is a heuristic in both directions (the estimate is advisory, and it counts rows where the runtime counts distinct non-null keys), so it can only cost an optimization, never a row; it is inert on the memory backend, whose row estimates read 0, and exists for modules reporting real cardinality. Runs in PostOptimization after monotonic-merge-join, join-physical-selection and monotonic-limit-pushdown.
  • ruleJoinElimination: Drops a JOIN whose non-preserved side is never referenced above the join and is at-most-one-matching per a declared FK→PK relationship. Fires on ProjectNode, walks down through Filter / Sort / LimitOffset / Distinct / Alias collecting demanded attribute IDs; when the walk reaches a JoinNode, the demanded set is final for that chain. Requires an AND-of-column-equalities ON-clause and an FK→PK alignment verified via checkFkPkAlignment (same helper that drives FK-aware key/row-count reduction in analyzeJoinKeyCoverage). LEFT/RIGHT outer joins may only drop the non-preserved side; INNER joins may drop either side but additionally require (a) every FK column to be NOT NULL (otherwise NULL FK rows that wouldn't have matched would now survive) and (b) the eliminable side to be a row-preserving path to its base table — only TableReference / Retrieve (bare-source) / Alias / Sort wrappers are permitted, since a Filter / LimitOffset / Distinct / Project between the join and the table would either drop rows the FK→PK guarantee assumes are present or break the table-column-index→attribute-index mapping checkFkPkAlignment relies on. Most commonly fires on views that join a parent table for FK-side selects the outer caller never references. Runs in the Structural pass (after predicate-pushdown, so right-side residual predicates have already landed below the join and protect themselves from elimination). Since join-predicate-pushdown landed, a single-side WHERE conjunct protects its side a second way: that branch is now a Filter, which is not in the row-preserving whitelist above, so the eliminable-side check declines on shape as well as on demand.
  • ruleJoinExistencePruning / ruleJoinExistencePruningUnderAggregate: Demand-gated drop of an unused outer-join exists … as existence flag, with two entrypoints that mirror ruleJoinElimination / ruleJoinEliminationUnderAggregate. ruleJoinExistencePruning fires on ProjectNode (id join-existence-pruning); ruleJoinExistencePruningUnderAggregate fires on AggregateNode (id join-existence-pruning-aggregate) for a flag-bearing join that sits under a count(*) / group by with no enclosing Project. Both reuse ruleJoinElimination's demand analysis verbatim (the exported collectAttrIds / walkChain / rebuildChain / rebuildProject helpers): collect the attr ids the anchor demands (the Project's projections, or the Aggregate's group-by + aggregate expressions — its only scalar children), walk the Filter / Sort / LimitOffset / Distinct / Alias pass-through chain to the first JoinNode, then rebuild that join without any ExistenceColumnSpec whose output attribute id is absent from the demanded set (the Aggregate variant rebuilds the AggregateNode with preserveAttributeIds so its output ids stay stable). HAVING is a FilterNode above the Aggregate that can only reference the Aggregate's outputs, never the raw flag, so it needs no special handling. When the last spec is dropped, existence becomes undefined, hasExistenceColumns flips false, and the five flag-guarded join rules (join-elimination, fanout-lookup-join, join-physical-selection, monotonic-merge-join, lateral-top1-asof) re-enable on the now flag-free join. Both run in the Structural pass — after projection-pruning / predicate-pushdown / scalar-cse so demand is settled, and before fanout-lookup-join and join-elimination / join-elimination-aggregate so the freshly-pruned anchor threads through them in the same applyRules loop; the PostOptimization join rules and the top-down-visited lateral-top1-asof see the flag-free join automatically. sideEffectMode: 'safe': it drops only a derived, read-only {true,false} column and preserves both join sides verbatim. Pure optimization — no correctness defect today; a flag-bearing join was simply pinned to nested-loop purely to compute a column no one read. Dropping even a middle flag is runtime-safe because column resolution is by attribute id (the RowDescriptor rebuilt from getAttributes()), not the build-time columnIndex. The write half is unaffected: a writable flag is always SELECTed by its view's projection, so the demand gate retains it. Note on the aggregate anchor (cascade): exists … as is only valid on an outer join (the parser rejects it on inner). Pruning the unused flag under an aggregate yields a flag-free outer join, which ruleJoinEliminationUnderAggregate — now that it eliminates FK→PK left/right joins, not just inner — eliminates entirely. So an undemanded count(*) … left join … exists right as collapses to zero join ops (prune → eliminate, same applyRules pass), not merely to physical join selection.
  • ruleSemijoinExistenceRecovery / ruleSemijoinExistenceRecoveryUnderAggregate (ids semijoin-existence-recovery / semijoin-existence-recovery-aggregate): The demand-SHAPE complement of join-existence-pruning's demand-PRESENCE prune. Where pruning drops a flag nothing reads, this recovers a semi/anti join when the sole exists … as flag on a left join is demanded but only as a top-level boolean probe — where flag ⇒ semi, where not flag ⇒ anti (also not not flag, flag = true/false, and the IS forms flag is true / flag is not false ⇒ semi, flag is false / flag is not true ⇒ anti, each normalized via normalizePredicate). The is not … collapses (is not false ≡ = true, is not true ≡ = false) are exact only because the flag is provably non-null (EXISTENCE_FLAG_TYPE.nullable === false); for the same reason flag is [not] null is a constant over the non-null flag (not a probe) and the matcher abstains. Fires on ProjectNode (the anchor must bound everything any ancestor can reference; a Filter anchor would be unsound because rewriting the join to semi drops the right columns + flag, which only the Project's projection list can prove unreferenced). Two entrypoints (mirroring join-existence-pruning / …UnderAggregate): the second entrypoint ruleSemijoinExistenceRecoveryUnderAggregate (id semijoin-existence-recovery-aggregate, also Structural pass, but nodeType: Aggregate) anchors on AggregateNode for the bare count(*) … where flag / group by shape that plans with no enclosing Project (the probe Filter + flag-bearing join sit under the Aggregate, so the Project entrypoint walks past them). It shares ALL of the probe-detection + chain-rewrite machinery — the exported analyzeChain now takes a pre-seeded demand set so both anchors reuse it — differing only in the demand seed (the Aggregate's group-by + aggregate expressions vs a Project's projections) and the rebuild epilogue (reconstruct the AggregateNode with preserveAttributeIds so its output ids stay stable). The aggregate anchor has no inner-join fallback: a right-column-demanded or fan-out positive probe under an aggregate stays a flag-bearing left join (sound, just unoptimized) — the count(*) … where flag shape is the target — unlike the Project anchor, which hands those off to inner-join-existence-recovery. HAVING is a FilterNode above the Aggregate that can reference only the aggregate output (group keys / aggregate results), never the raw flag, so it never appears in walkChain and does not block. Reuses ruleJoinElimination's walkChain / collectAttrIds / rebuildChain / rebuildProject; builds the demand set conjunct-by-conjunct so the single probe conjunct is excluded, then requires (a) exactly one flag-referencing conjunct, in probe normal form; (b) the flag absent from the residual demand set (a selected or sorted-on flag lands there and abstains); (c) no right-side column demanded (select * / select c.*, p.col … where flag abstain here and hand off to inner-join-existence-recovery, which rewrites that shape to an inner join — it is not a semi-join); (d) existence.length === 1 (a semi join collapses the right side and cannot also emit other flags — when a sibling flag is merely undemanded, join-existence-pruning drops it first, leaving a sole flag this rule then recovers in a later applyRules iteration); and (e) subtreeHasSideEffects(right) === false (a semi join short-circuits the right scan at the first match, changing R's execution count); and (f, SEMI only) the right side matches at most one row per left row — rightMatchesAtMostOne, i.e. the equi-join columns cover a unique key of R via isUnique. The fan-out guard (f) is the soundness crux: a plain left join … exists right as is a normal left join with an appended flag bit, so emitLoopJoin yields one output row per matching right row — where flag keeps K rows for a left row with K matches, whereas semi(L,R,cond) keeps one. They agree only when every left row matches ≤1 R row (FK→PK, or a ≤1-row R); a non-unique / non-equi condition makes the SEMI shape unsound and the rule abstains — inner-join-existence-recovery then recovers a fan-out-safe inner join from that abstention point (a positive no-right-col probe over a fan-out R), so the two rules partition the entire positive-probe space and, consulting the same rightMatchesAtMostOne, are disjoint independent of registration order. The anti path needs no such guard: an unmatched left row yields exactly one null-extension regardless of fan-out, and matched rows are filtered out, so anti(L,R,cond) equals left join … where not flag for arbitrary cond. The recovered join carries the full ON condition verbatim; a residual conjunct over a covered unique key only narrows the ≤1 match further (still ≤1), so the downstream IND folders gate on AND-of-equalities and abstain on any residual, leaving a plain semi/anti (hash semi-join still beats nested-loop+flag). The probe Filter is rebuilt with its non-probe conjuncts (or omitted when the probe was its only conjunct). Runs in the Structural pass — after join-existence-pruning so an undemanded sibling flag is gone first, and (in registration order) before fanout-lookup-join, join-elimination, and the Join-typed IND folders anti-join-fk-empty / semi-join-fk-trivial so the recovered semi/anti threads into them in the same top-down descent (exactly why subquery-decorrelation precedes those folders). sideEffectMode: 'aware' (the impure-R guard). Pure optimization: rows are byte-identical to the nested-loop+flag baseline. Write-half safe by construction — a flag writable through a view is always SELECTed by its routing Project, so it lands in demanded and check (b) abstains, and the write path never reaches this rewrite. Only left join … exists right as is reachable (the parser rejects exists … as on inner/cross, the runtime rejects RIGHT/FULL), so the rule is guarded by joinType === 'left' && spec.side === 'right'. Deferred: case-wrapped probe forms (truthiness-of-integer, not a boolean probe — file a backlog ticket if a real workload produces them) and an aggregate-anchored inner fallback (the right-col-demanded / fan-out positive-probe cases the aggregate anchor leaves as a left join — out of scope, file a follow-up if a real workload wants it). The positive-probe cases the SEMI rule abstains on — a right column demanded, OR a fan-out (non-unique) R — are both handled by inner-join-existence-recovery (next bullet).
  • ruleInnerJoinExistenceRecovery (id inner-join-existence-recovery): The fallback complement of semijoin-existence-recovery — same probe machinery, covering both positive-probe shapes the semi rule abstains on. When the sole exists … as flag on a left join is a positive top-level probe (where flag / flag = true / flag is true / flag is not false / not not flag — all the 'semi'-polarity forms) and EITHER ≥1 right-side column is demanded above the join OR R fans out (is non-unique on the join column), it rewrites the flag-bearing JoinNode to a plain inner join (drop the flag, keep both sides) instead of a semi join (which would either drop the right columns the caller needs, or collapse the fanned-out duplicates K→1). Fires on ProjectNode; reuses walkChain / rebuildProject from join-elimination and the sibling's exported analyzeChain / rebuildChainStrippingProbe / ProbeMatch (added export; no logic change), so the demand SHAPE proof and probe normalization are shared verbatim. Guards: joinType === 'left' && spec.side === 'right', existence.length === 1, condition present, probe.polarity === 'semi' (a negative/anti probe with a right column must stay a left join — an anti row has an all-NULL right side, so an inner join would drop the rows anti keeps), !demanded.has(flagId) (a selected/sorted-on flag abstains), the gate !(!rightColDemanded && rightMatchesAtMostOne(join)) — fire when a right column is demanded OR R fans out, deferring to the semi rule ONLY where it can actually fire (no right column AND unique R, the ≤1-match case where the leaner semi join is sound) — and subtreeHasSideEffects(right) === false. Soundness (and why it is simpler than the semi rule): emitLoopJoin drives a left join … exists right as as a normal left join with one appended flag bit — a matched left row with K right matches yields K rows each flag=true, an unmatched left row yields one null-extended row flag=false. A positive where flag keeps exactly the K matched rows per left row; an inner join on the same condition yields exactly those K rows — identical row-for-row for ANY condition. So unlike the semi rule there is no fan-out guard for soundness (an inner join does not collapse K→1, so the conversion is sound under any fan-out — rightMatchesAtMostOne is consulted only to locate the abstention boundary, never as a correctness precondition — and this rule therefore does convert the fan-out case the semi rule cannot), no condition-shape restriction (the ON condition is carried verbatim, non-equi / residual conditions included), and no NOT-NULL FK requirement (a NULL FK is unmatched under both the flag and the inner join, so no orphan leaks). buildJoinAttributes emits the same [left…, right…] ids for left and inner (only the right columns' nullable flag differs), so right columns resolve by attribute id at the same ids and dropping the appended flag shifts nothing; the inner join's non-nullable right typing is a sound strengthening (after where flag only matched rows survive, on which the right side is fully present) that re-enables downstream FD/key/IND reasoning. The probe conjunct is subsumed by the inner join and stripped via rebuildChainStrippingProbe (residual conjuncts retained above the join; Filter omitted when the probe was its sole conjunct). Note join-elimination does not fire on the recovered inner join within this rule's domain: while a right column is demanded it requires the non-preserved side unreferenced, and in the no-right-col fan-out domain it requires an at-most-one unique FK→PK alignment that the non-unique R contradicts; the in-scope win is physical join selection + non-nullable typing + FD/IND reasoning, not elimination. sideEffectMode: 'aware' (the impure-R guard): the logical inner join scans R the same number of times as the flag-bearing left join, but dropping the flag re-enables join-physical-selection, which can pick a hash join that scans R once total — changing an impure R's execution count. Pure optimization: rows are byte-identical to the nested-loop+flag baseline. Write-half safe by construction (a flag writable through a view is always SELECTed by its routing Project → lands in demanded → abstains). Runs in the Structural pass. The two recovery rules consult the same rightMatchesAtMostOne and so are provably disjoint on the positive-probe space independent of registration order (semi fires iff !rightColDemanded && unique-R; inner iff rightColDemanded || !unique-R; the intersection is empty), making registration order (semi then inner) merely conventional. Registered (in registration order) before fanout-lookup-join, join-elimination, and the Join-typed IND folders. Termination: the output inner join has no existence spec, so re-running sees joinType !== 'left' and no-ops.
  • ruleLateralTop1Asof: Recognizes the lateral-top-1 idiom and rewrites it to a streaming AsofScanNode (see Streaming asof scan).

Predicate (predicate/)

  • ruleAggregatePredicatePushdown: Splits Filter(predicate, Aggregate|StreamAggregate|HashAggregate) so that conjuncts referencing only GROUP-BY-determined columns are rewritten onto the aggregate's source attribute IDs and moved below the aggregate; conjuncts referencing aggregate outputs (sum/count/etc.) or non-column GROUP-BY expressions stay above. Subsumes the WHERE-on-group-by-column and HAVING-on-group-by-column cases. Uses computeClosure over the aggregate's physical.fds so composite GROUP BYs whose members FD-determine each other widen the pushable set (see the FD framework section). Runs in the Structural pass, ahead of rulePredicatePushdown so anything it places below an aggregate can propagate further.
  • rulePredicatePushdown: Pushes filter predicates down across safe commuting nodes (Sort, Distinct, Alias, eligible Project) and into RetrieveNode boundaries where the virtual table module supports them, reducing rows processed upstream.
  • ruleFilterMerge: Merges adjacent Filter nodes into a single Filter with an AND-combined predicate. Iteratively absorbs entire chains of adjacent filters in one visit. Runs in the Structural pass (after predicate pushdown).
  • rulePredicateInferenceEquivalence: Materializes inferred equality predicates from the cross of predicate-derived constant bindings and the source's equivalence classes. For a Filter(predicate, source) where predicate pins t.k = V (literal or parameter) and source.physical.equivClasses includes a class containing t.k's column index, the rule emits col = V for every other class member not already pinned by the predicate. The augmented predicate is ANDed into the outer Filter and nothing else — ruleJoinPredicatePushdown (registered immediately after) is what moves the single-side conjuncts, inferred and original alike, onto their branches. The rule used to inject those branch Filters itself, back when nothing could cross a join; doing both now materializes the same conjunct twice on one branch. LEFT/RIGHT/FULL joins need no special case here — propagateJoinFds has already stripped NULL-padded sides' bindings/ECs from the join's output, so no conjunct over such a side can be inferred. sideEffectMode: 'safe' since it only rewrites a predicate. Idempotent: a second invocation finds every EC member already in the predicate's bound set and emits nothing. Runs in the Structural pass; no collision with scalar-cse since they target different node types. Worked example: t INNER JOIN u ON t.k = u.k WHERE t.k = 5 augments the predicate to t.k = 5 and u.k = 5, which join-predicate-pushdown then splits one conjunct per branch, letting the vtab answer each as an index seek instead of a sequential scan. Range and IS NULL inference are intentionally out of scope.
  • ruleJoinPredicatePushdown: Splits Filter(predicate, Join) so each conjunct whose column references all land on ONE side of the join is moved onto that side's branch (FilterNode around join.left / join.right); cross-side conjuncts stay in a residual Filter above the rebuilt join. rulePredicatePushdown then carries each branch Filter across that branch's Alias into its Retrieve, which is what turns a full scan into an index seek. A side may receive a conjunct exactly when it is never null-extended in the output (read off buildJoinAttributes): inner/cross → both sides; left/semi/anti → left only; right → right only; full → the rule declines. Attribution is a plain attribute-id set test over the conjunct's WHOLE subtree, descending through relational children as well as scalar ones — so a conjunct carrying any subquery sees ids belonging to neither side and is declined (conservative but sound; it is what stops e.amount > (select … where x.c < t.id) from landing on the e branch where t.id does not resolve). Also declined: a conjunct with no column references (where :p > 0), a non-functional one (random() < e.amount), and — per branch, so the other side still benefits — any conjunct destined for a branch whose subtree carries a write. The join is rebuilt with withChildren so existence specs and usingColumns survive. Conjuncts are moved, never copied: a copy left above would re-evaluate per output row and make the rule non-idempotent. Registered in the Structural pass immediately AFTER predicate-inference-equivalence — running it first would leave no Filter over the join for inference to read, losing the cross-side t.id = 'x' fact and its branch's seek.
  • ruleSargableRangeRewrite: Rewrites f(col) = c into col >= lower(c) AND col < upper(c) using LogicalType.bucketBounds, restoring sargability for bare-column equality on lossy-monotone transforms (notably date(ts) = D). Structural pass — ahead of aggregate-predicate-pushdown / predicate-pushdown so the rewritten range flows through the rest of the predicate pipeline. See Rule Families § Sargable range rewrites for the wiring (function-schema rangeRewriteOnArg trait + per-type bucketBounds) and the identity/null/parameter guards.
  • ruleFilterContradiction: Recognises when a Filter's predicate, conjoined with the source's domainConstraints and literal constantBindings, is provably unsatisfiable and emits EmptyRelationNode carrying the Filter's own attribute IDs / RelationType. Structural pass, downstream of rule-empty-relation-folding so the cascade can collapse the surrounding subtree. Reasoning is per-column range/enum intersection (planner/analysis/sat-checker.ts); OR / CASE / cross-column arithmetic stay out of scope. See Rule Families § Predicate contradiction detection.
  • ruleEmptyRelationFolding: Cascades EmptyRelationNode up through immediate Filter / Project / Sort / LimitOffset / Distinct / inner-or-cross-or-semi-anti joins, lifting the host's attribute IDs / RelationType onto the new empty result. Also folds Filter(_, false|null|0) directly. Structural pass — after the IND rules so anti-join-to-empty rewrites can cascade in the same visit. See Rule Families § Empty-relation folding.
  • ruleFilterSelectivity (ids filter-selectivity, filter-selectivity-restamp and filter-selectivity-final): Stamps a stats-derived selectivity onto a Filter so estimatedRows reflects real column statistics instead of the flat DEFAULT_FILTER_SELECTIVITY (0.5). Node accessors carry no OptContext, so the lookup is done by a context-holding rule and cached on the optional FilterNode.selectivity field. Two paths: single-table (the strict extractRowSourceTableSchema walk found one base table whose rows are the ones arriving at the Filter → hand the whole predicate to the provider, which decomposes its boolean structure itself) and multi-relation (a join source, or the strict walk declined → split into conjuncts, attribute each to the relation(s) its columns come from via collectColumnOrigins, estimate per conjunct with the shared stats/conjunct-selectivity.ts estimator, and combine with exponential backoff). Registered in three passes, all bottom-up. filter-selectivity (Physical) is the primary stamp — what the physical and PostOptimization cost readers (join-physical-selection, monotonic-limit-pushdown, key-set-seek, the materialization advisory) consult. filter-selectivity-restamp (PostOptimization, registered first in that pass) recovers the estimate for a Filter whose stamp FilterNode.withChildren dropped because PostOptimization rewrote something inside its predicate — scalar-subquery-cache wrapping an uncorrelated scalar subquery's inner re-mints every scalar ancestor up to the predicate, so without it any query with a subquery in its WHERE reaches emission unstamped and every consumer falls back to 0.5; it must run inside that pass rather than after it because the cost readers later in the pass consult the stamp. filter-selectivity-final (Final Estimates, order 37) is the backstop behind every plan-mutating pass: the Materialization advisory (order 35) re-mints predicates too, whenever it marks a with clause for shared materialization or injects a CacheNode inside one, and nothing else runs behind it. The rule declines immediately on an already-stamped Filter, so the second and third registrations only ever fill in a dropped estimate — re-deriving it against the new predicate rather than carrying the stale one forward. sideEffectMode: 'safe' on all three (it rebuilds the identical Filter with only an added estimate). See Cost Model Integration, "Filter row estimates".
  • ruleFilterConjunctOrdering (id filter-conjunct-ordering): Sorts a Filter's top-level AND conjuncts on a (cost tier, statistics-estimated benefit/cost descending, subtree cost) key (Cost Model Integration) so early exit skips expensive conjuncts for rows an earlier one rejects. Per-conjunct selectivity comes from the shared stats/conjunct-selectivity.ts estimator, gated on statsOnlySelectivity; when no conjunct has a real estimate the rule sorts by cost alone, bit-identically to the pre-selectivity behaviour, and in the mixed case unknowns take the neutral 0.5. Stable sort (ties keep source order). Sound: AND commutes under three-valued logic and a Filter rejects false and NULL alike. Refuses side-effecting subtrees, returns null when already ordered (the fixed point), preserves the stamped selectivity. PostOptimization, registered last — after all Structural predicate reshapes, filter-selectivity, and (bottom-up) scalar-subquery-cache. Within PostOptimization it also runs after filter-selectivity-restamp, which is registered first in that pass precisely so a Filter whose predicate was re-minted there already carries its estimate by the time this rule copies it forward.

Subquery (subquery/)

  • ruleSubqueryDecorrelation: Transforms EXISTS/IN subqueries in WHERE-clause filters into semi/anti joins, enabling hash join selection. Handles: correlated EXISTS → semi join, NOT EXISTS → anti join, correlated IN → semi join (correlation lifted out of the inner filter), and uncorrelated filter-position IN → semi join with the inner tree used verbatim as the right side (no descent — inner LIMIT / DISTINCT / set-ops / CTE bodies / computed columns preserved). Sound under WHERE only: x IN S is three-valued (NULL when x is NULL, or unmatched with a NULL in S), but a Filter collapses NULL to "drop the row" — exactly what a semi join does. Every gate declines back to the runtime set-probe path (docs/runtime-caching.md § IN-subquery set probe): bare outer column, deterministic side-effect-free inner, exactly one hashable equi-pair per extractEquiPairs (folding in the collation-conflict and semantic-ordering declines), agreeing IN/= collation resolutions. Projection-position IN (keeps its three-valued answer) and NOT IN (parsed as NOT over the InNode) never rewrite. Correlated-IN arm's inner-shape gates (extractInCorrelation): the join condition compares against the subquery's first output column, so the descent through Project/Alias runs before the condition is built and the join's right side is derived from wherever that descent lands (current instanceof FilterNode ? current.source : current) — never a stale, independently-chosen node. Three checks then guard it: (1) a LimitOffset reached by the descent sits above the correlated filter, applying per outer row, which one semi join cannot express — decline (an inner LIMIT below the correlated filter, inside an uncorrelated derived table, is never reached by the descent and still decorrelates); (2) the chosen right side must actually expose the comparison column's attribute id (getAttributes().findIndex) — a computed inner projection (select b.x + 0 …) mints a fresh id nothing below defines, so it declines rather than building a join condition against a phantom attribute; (3) after the right side is fully assembled, collectExternalReferences on it must be empty — a backstop that also declines DISTINCT / set-ops / ORDER BY / anything else the descent cannot step through and that would otherwise leave the correlation predicate buried inside the join's right side, driven as if uncorrelated. A decline is always safe: the InNode simply stays on the runtime set-probe path (emitIn). Both arms synthesize their membership = as a raw BinaryOpNode, bypassing the coercion buildExpression gives a hand-written =; both arms therefore reconcile their operands through coerceComparisonSet (planner/building/coercion.ts) first, so a correlated json_col in (select text_col …) compares JSON-to-JSON rather than object-to-string and int_col in (select text_col …) compares on the numeric reading rather than by storage class. The resulting CastNode wrapper demotes the conjunct out of extractEquiPairs (which requires two bare column references). In extractInCorrelation it lands in the join's residual, which is where ='s own semantics apply, and the join still keys on the genuine correlation pair. In extractUncorrelatedIn the equi-pair gate is the rewrite's own precondition, so a coerced pair declines the rewrite entirely and stays on the set-probe path, whose inMembershipKeys performs the same conversion per row — the same answer either way. Structural pass (after predicate pushdown).
  • ruleExistsInSelectDecorrelation (id exists-in-select-decorrelation, nodeType: Project, same file): The SELECT-list anchor for the same subqueries. A correlated EXISTS / NOT EXISTS / IN in a projection expression cannot become a semi/anti join (every outer row must survive, with the match reported as a column), so each recognized subquery becomes a LEFT join carrying an exists right as match flag (ExistenceColumnSpec), and the subquery node in the projection is replaced by a reference to the flag column — Project[o.id, <flag> AS f](LeftJoin[c.fk = o.k] exists right as <flag>(o, Distinct(Project[keys](Filter(residual, c))))). NOT EXISTS / NOT IN need no special casing: the rewrite fires on the inner Exists/In node and the enclosing NOT survives over the two-valued flag. Fan-out guard: emitLoopJoin drives a flag join as a plain left join (K matching inner rows would duplicate the outer row K times), so the inner side is collapsed to at most one row per correlation key — an attribute-id-preserving projection onto the key columns under a Distinct (distinct-elimination drops it again when the key is already unique, and nested-loop-right-cache materializes the now-uncorrelated right side once). IN three-valued-logic gate: a projected x IN S yields NULL (not FALSE) when there is no match but x is NULL or S contains a NULL; the flag is two-valued, so the rewrite fires only when both comparison sides are statically non-nullable — otherwise the subquery stays on the per-row path (this gate is also what makes the NOT IN form exact). Reuses the WHERE anchor's extractExistsCorrelation / extractInCorrelation splitters (same equi-correlation-only, residual-must-be-inner-only bails), requires correlation resolving entirely to the immediate outer, and refuses side-effecting inners. Flags stack left-deep for multiple subqueries in one SELECT; the rebuilt Project preserves output attribute ids and caps the flag/join columns from leaking. Downstream, the produced flag join plugs into the existing existence-flag cascade (join-existence-pruning strips a flag a later rewrite orphans; the recovery rules re-shape a flag that ends up as a pure WHERE probe). Structural pass, registered adjacent to its decorrelation siblings; ordering relative to the earlier-registered Project-typed flag rules is not load-bearing (the per-node applyRules fixpoint re-offers all rules on each newly minted node). sideEffectMode: 'aware'.
  • ruleScalarAggDecorrelation (id scalar-agg-decorrelation): The SELECT-list sibling of ruleSubqueryDecorrelation. A correlated scalar-aggregate subquery in a projection — (select agg(x) from c where c.fk = o.k), bare or wrapped (coalesce((subq), 0)) — becomes a grouped LEFT join: left join (select fk, agg(x) from c group by fk) g on g.fk = o.k, so the inner table is scanned and hash-aggregated once instead of re-executed per outer row. Recognition requires: correlation resolving entirely to the immediate outer; a zero-group single-aggregate root beneath bare pass-through Project/Alias wrappers (Sort/LimitOffset wrappers, GROUP BY, composite expressions over aggregates, and non-aggregate … limit 1 shapes all bail and keep the correlated per-row plan, including the >1-row scalar-subquery error); a Filter directly under the aggregate whose predicate splits into outer.col = inner.col equi-conjuncts plus inner-only residuals (non-equi correlation bails); and a side-effect-free inner subtree (per-row DML firing is observable). The grouped aggregate preserves the inner correlation attribute ids as its group-output ids, so the original correlation conjuncts serve verbatim as the join condition and hash-join equi-pair extraction applies unchanged. Empty-group semantics (the "count bug"): the aggregate's empty-input value is computed at plan time by the exact runtime zero-row path (finalizeFunction(cloneInitialValue(initialValue))); a NULL empty value (sum/min/max/avg) needs no guard (join miss ⇒ NULL), while a non-NULL one (count → 0, total → 0.0) wraps the read in CASE WHEN <group key> IS NULL THEN <empty literal> ELSE <value> END — the group key is a sound join-miss marker because a matched row always has a non-NULL key and a NULL-keyed inner group can never match. Outer references outside the conjuncts (e.g. in aggregate arguments) are remapped to the equated inner column, gated on value-faithful equality (value-discriminating collation + same logical type); an unremappable reference bails. Each recognized subquery becomes its own stacked left join; multiple subqueries per SELECT are independent. Registered in the Structural pass after fanout-lookup-join (which consumes the same shape first on remote-latency plans and is inert locally) and adjacent to subquery-decorrelation; unconditional (no cost gate) — the tiny-outer/huge-inner tradeoff is tracked in backlog/feat-decorrelation-cost-model. sideEffectMode: 'aware'. Aggregate-argument site (ruleScalarAggDecorrelationAggregate, id scalar-agg-decorrelation-aggregate, nodeType: Aggregate, same file): the identical per-subquery rewrite for a scalar-aggregate subquery embedded in an AggregateNode's aggregate-argument (or group-by) expressions — the shape a nested aggregate subquery takes after the Project-site rewrite of its enclosing level (whose outer-reference remap makes a two-level correlation, e.g. qv.entry_id = e.id AND qv.item_id = i.id, local to the new grouped aggregate's source). The join stack lands below the enclosing aggregate, between it and its source; the rebuilt aggregate preserves its output attribute ids, so group-by references and HAVING (a Filter above the aggregate, referencing only its outputs) resolve unchanged. Cardinality safety for inserting a join below an aggregate: the grouped subtree's GROUP BY keys are a unique key on its output, so the LEFT join matches at most one row per source row — group contents (row count and multiplicity, hence DISTINCT-aggregate sets too) are preserved exactly. Multi-level nesting converges level by level within one Structural pass: the pass is top-down with rules firing before descent, so the grouped aggregate built by one level's rewrite is itself visited later in the same traversal, where the aggregate site fires on the next level. The site also fires on a top-level user-written GROUP BY aggregate whose argument carries a correlated subquery — nesting is the motivation, not a precondition. A remap-bailed enclosing level simply leaves the nested subquery correlated to a non-immediate outer, which the correlation gate rejects — both levels keep the correlated per-row plan and stay correct. A DML-bearing branch is refused at every level that contains it (any level's rewrite would change the write's firing count); pure sibling subqueries still rewrite independently. Filter site (ruleScalarAggDecorrelationFilter, id scalar-agg-decorrelation-filter, nodeType: Filter, same file): the identical per-subquery rewrite for a scalar-aggregate subquery used anywhere in a Filter predicate — a WHERE comparison (where o.total > (select avg(c.amount) from c where c.fk = o.k)) or a HAVING comparison (group by o.k having sum(o.v) > (select …), which plans as a Filter whose source is the group AggregateNode, so the aggregate's group-key / aggregate-result attributes are the outer attributes the subquery correlates to — no HAVING special-casing). The join stack lands between the Filter and its source, and the subquery reference in the predicate is substituted with the guarded value read; the LEFT join is load-bearing so a no-match outer row survives carrying the empty-input value, preserving three-valued predicate logic (o.total > NULL → NULL → row excluded) with no new code. Because a FilterNode publishes its source's attributes verbatim, the rewritten result is capped with a bare pass-through Project that re-exposes exactly the original Filter attributes — without it the LEFT join's appended grouped-aggregate columns leak to the query output whenever the Filter is not already under a projection (the common HAVING shape, where the SELECT list is fused into the Aggregate below the filter). Registered after subquery-decorrelation (both nodeType: Filter; pass rules fire in registration order) so EXISTS/IN materialize their semi/anti joins first and this rule then decorrelates any scalar-agg comparison over the already-rewritten source; the two Filter rules target disjoint subquery node types (ExistsNode/InNode conjuncts vs ScalarSubqueryNode anywhere in the predicate) so there is no match collision. sideEffectMode: 'aware'. Sort site (ruleScalarAggDecorrelationSort, id scalar-agg-decorrelation-sort, nodeType: Sort, same file): the identical per-subquery rewrite for a scalar-aggregate subquery used in an ORDER BY key — order by (select count(*) from c where c.fk = o.k). The join stack lands below the Sort so the sort key can read the grouped value column, and each recognized subquery reference in the keys is substituted with the guarded value read (direction/nulls copied verbatim). A SortNode publishes its source's attributes verbatim (it never consumes/hides columns the way a Project does), so the LEFT join's appended columns would leak upward and change the row shape every ancestor sees — the result is therefore capped with the same bare pass-through Project as the Filter site (capToAttributes), giving an invariant output shape whether or not an enclosing Project exists (a view body, a compound-select arm, or a bare top-level Sort). Ordering is stable: the substituted value is byte-identical to the scalar the subquery would return, and the LEFT join matches at most one row per outer row (unique group keys), so row count, multiplicity, and per-row sort-key values are all unchanged. Sort is not otherwise a decorrelation anchor, so there is no registration-order coupling with the other sites; placed adjacent for locality. Scope: like every site, the rewrite needs the correlation columns in the Sort's own source — true for identity select o.* projections and any query that also selects the correlation column. When the SELECT list projects the correlation column away (select o.id from o order by (select … where c.fk = o.k)), the Sort sits above a stripping Project whose output no longer carries o.k, so the rule bails and the subquery stays correlated (still correct — the runtime resolves o.k from the still-live base-scan row context below the Project; it is merely not decorrelated). Threading the grouped value column up through a stripping Project is tracked in backlog/feat-decorrelate-order-by-subquery-nonselected-column. An ORDER BY over a GROUP BY aggregate query (an aggregate scalar subquery in the ORDER BY of a grouped query) used to throw spuriously — the subquery's inner aggregate mis-resolved to the outer aggregate's output alias; that pre-existing planner scope-leak (independent of decorrelation — it reproduced uncorrelated and with all decorrelation disabled) was fixed in planner/building/select.ts, where a nested SELECT no longer inherits its enclosing query's aggregate context, and the case is now pinned in 07.7-scalar-agg-decorrelation.sqllogic. sideEffectMode: 'aware'.
  • ruleSemiJoinFkTrivial: SemiJoin(L, R) whose equi-pairs cover a non-null FK on L referencing R's PK (with R a row-preserving path to its base table, projections included) rewrites to L when every FK column is NOT NULL, otherwise to Filter(L, fk_col IS NOT NULL AND …). Structural pass, after rule-subquery-decorrelation has materialized EXISTS / IN as semi joins. Because that rule's uncorrelated-IN arm hands the join the subquery verbatim, R is normally Project(parent); the fold peels it and translates both sides' equi columns back to base-table column indices via resolveTableColumnMapping before consulting the FK (a raw output index that coincides with the referenced column's index would otherwise fold a join that was never redundant). See Rule Families § Key-driven row-count reduction.
  • ruleAntiJoinFkEmpty: AntiJoin(L, R) with the same preconditions rewrites to EmptyRelationNode carrying L's attribute IDs and RelationType — every (non-null) L row is guaranteed a parent in R, so the anti-join is empty. Structural pass; the empty result then feeds rule-empty-relation-folding for further cascade. See Rule Families § Key-driven row-count reduction.

Constant Folding (pass): evaluates constant expressions at plan time