ROADMAP.md

Roadmap — Vectorized SQL Query Engine

1. Parser, binder, logical algebra, and golden-query oracle.
2. Volcano/interpreted execution for correctness.
3. Columnar storage and vectorized operators.
4. Rule-based rewrites with equivalence tests.
5. Cascades memo, cost model, and join reordering. Delivered in Phase 5c: the memo now explores equivalent join orders, verifies all enumerated alternatives, and extracts a deterministic low-cost logical plan from catalog row-count statistics without changing semantics.
6. ORDER BY end-to-end. Delivered in Phase 6: parser and binder support FROM-scope column sort keys, logical and physical plans include a required-order root Sort, both engines implement deterministic stable sorting, and memo verification distinguishes same-plan exact equality from cross-plan ordered bag-plus-sortedness checks.
7. Table aliases and self-joins. Delivered in Phase 7: parser and binder support FROM t [AS] x and aliased join chains, bound column identities are binding-scoped, logical/physical scans carry physical table plus binding name, memo scan dedup includes aliases, cost stats look up physical tables while distinct keys remain binding-scoped, and both engines verify aliased self-joins through golden and differential memo alternatives.
8. GROUP BY and aggregate functions. Delivered in Phase 8: parser and binder support COUNT(*), COUNT(col), SUM, MIN, MAX, and GROUP BY column refs; Aggregate is a logical/physical/memo node between Filter/Join and Project; interpreted and vectorized aggregation preserve first-appearance group order; global empty COUNT returns zero while empty SUM/MIN/MAX fail loudly under the pre-16b aggregate NULL-result contract; SUM detects int64 overflow; join transforms still fire below Aggregate; aggregate queries are covered by golden, binder, cost-model, differential alternatives, and extract_best verification.
9. SELECT output aliases, HAVING, and output-name ORDER BY. Delivered in Phase 9: SELECT-item AS aliases define output names under the existing duplicate-output-name invariant; grouped HAVING binds grouping columns, integer literals, and canonical aggregate expressions as a Filter over Aggregate outputs; HAVING-only aggregates are computed internally and dropped by final Project; HAVING without GROUP BY is rejected; ORDER BY resolves exact SELECT output names before falling back to FROM scope, with grouped fallback limited to grouping columns; both engines and the memo/cost model verify the full shape through golden, binder, rewrite, memo, cost, differential alternatives, and extract_best coverage.
10. Predicate pushdown. Delivered in Phase 10: the memo now adds FilterIntoJoinRule and FilterThroughAggregateRule alternatives without deleting the original shape; one-side WHERE conjuncts can move to join children, both-side conjuncts can merge into Join predicates, and HAVING conjuncts over exact grouping-key identities can move below Aggregate while aggregate-output predicates remain above. Cost-based extraction can now choose lower-cost pushed plans through the existing filter cardinality math, and the differential corpus verifies all alternatives plus extract_best for WHERE-over-join and HAVING pushdown stress cases.
11. Disjunctions and boolean grouping. Delivered in Phase 11: WHERE, ON, and HAVING predicates now parse OR plus boolean-level parentheses with precedence OR < AND < comparison; Filter and Join still expose top-level conjunct lists, but each conjunct is a predicate tree with comparison, AND, and OR nodes. Binding resolves every comparison leaf through the existing scope rules, both engines evaluate trees deterministically without short-circuiting, memo structural identity includes tree shape, constant folding simplifies literal leaves plus boolean algebra, and the cost model estimates OR as s1 + s2 - s1*s2. Pushdown remains conservative: whole one-side OR trees can move, grouping-key-only HAVING trees can move below Aggregate, and mixed-side or aggregate-output trees stay pinned without OR splitting.
12. DISTINCT and LIMIT result shaping. Delivered in Phase 12: parser and binder support SELECT DISTINCT plus final LIMIT <non-negative integer> after optional ORDER BY; logical/physical/memo plans include Distinct and Limit nodes in the shape Project -> Distinct -> Sort -> Limit; both engines deduplicate complete projected rows in first-appearance order and apply top-level limits deterministically per plan; memo costing models Distinct as group-like input/output work and Limit as row-count clamping with pass-through cost; and the differential corpus verifies LIMIT with a validity contract instead of exact cross-plan prefix equality.
13. Seeded SQL differential fuzzing. Delivered in Phase 13: sql_fuzz_differential now generates deterministic schema-driven catalogs and full-slice bindable SQL with aliases/self-joins, nested WHERE/ON/HAVING predicates, aggregates, GROUP BY, DISTINCT, ORDER BY, and LIMIT. Each seed runs the unrewritten oracle, standalone rewritten oracle/vectorized paths, every extracted memo root alternative, and extract_best; accepted aggregate runtime failures are compared by error category so partial throws are reported as divergences.
14. Benchmarks and scan qualification. Delivered in Phase 14: sql_bench is a separate non-CTest executable with deterministic 100k+ row workloads, optimized-build instructions, min/median timing output, and row-count/checksum correctness cross-checks before timings. Vectorized scan qualification no longer copies row data when adding binding.column identities; Int64Column now shares immutable backing storage across copies and detaches on append. The benchmark record is in docs/benchmarks.md: scan/filter improved modestly but still trails the oracle, hash-join workloads win by large margins, and aggregation/sort remain mixed.
15. Batch-at-a-time vectorized kernels. Delivered in Phase 15: vectorized execution now pre-resolves bound scalar, predicate, projection, sort-key, aggregate, distinct, materialization, and straightforward join inputs to direct immutable column-vector pointers once per operator/batch. Filter, projection, sort, aggregate, distinct, join key/residual evaluation, join output append, and final materialization no longer do column-name map lookups inside row loops. Int64Column::reserve supports exact output reservation while preserving copy-on-write isolation. Release benchmark evidence in docs/benchmarks.md shows scan/filter now beating the interpreted oracle across 1%, 10%, and 50% selectivity, with no material regressions in the measured workloads.
16. NULL semantics. Delivered in Phase 16b: Int64Column now has an optional shared validity vector with copy-on-write; SQL supports NULL literals plus IS NULL/IS NOT NULL; interpreted and vectorized predicates use SQL three-valued logic with TRUE-only filtering; hash joins skip NULL equi keys so NULL never matches NULL; aggregates ignore NULL inputs with SUM/MIN/MAX returning NULL for empty or all-NULL groups while overflow still throws; GROUP BY and DISTINCT use distinct-style NULL equality without leaking it into joins/comparisons; ORDER BY treats NULL as larger than every value, giving NULLS LAST for ASC and NULLS FIRST for DESC; and the differential fuzzer now emits nullable aggregate arguments, grouping keys, DISTINCT outputs, and ORDER BY keys through the full memo/rewrite/extract_best verification stack.
17. VARCHAR/string execution. Delivered across Phase 17a/17b: catalog::ColumnType::String, storage::StringColumn, and typed ColumnarBatch storage establish the second column type while preserving the existing int64 accessor fast path. The parser accepts single-quoted string literals with doubled quote escaping, the binder assigns explicit types to every bound expression and rejects implicit int64/string coercions, and both the interpreted oracle and vectorized engine implement string scan/filter/project/join/group/distinct/order/limit plus lexicographic MIN/MAX and NULL-skipping aggregates. Vectorized execution now dispatches int64-only plans through the int64 compiled pointer path and mixed/string plans through typed compiled kernels. Memo structural identity, printers, and costing are type-aware; string costs intentionally reuse row-count math while value-width costing is deferred. The seeded differential fuzzer now generates string columns/literals type-correctly and runs them through rewrite, memo alternatives, and extract_best.
18. EXPLAIN and global HAVING polish. Delivered in Phase 18: EXPLAIN <select-statement> parses as an additive wrapper and returns a deterministic one-column plan string batch from a shared optimizer-side renderer used by both engines; the report includes the bound logical plan, memo group/rule summary, extract_best chosen plan with per-node row/cost estimates, and total cost. HAVING without GROUP BY is now legal over the single global group with the same aggregate-output and 3VL rules as grouped HAVING, including HAVING-only aggregates that are computed and dropped by final Project. Differential/fuzz alternative extraction caps were raised so the current string-widened corpus no longer hits the plan bound.
19. Boolean-mask filter kernels. Delivered in Phase 19: vectorized Filter now evaluates WHERE/HAVING predicate trees as paired is_true/is_known byte masks using SQL Kleene 3VL algebra, with comparison leaves scanning pre-resolved int64 or string values column-at-a-time and IS [NOT] NULL leaves reading validity directly. Scan-adjacent identity selections use a dense full-batch domain, while filtered/non-identity inputs use dense selection-position masks that map back to the immutable input selection. Join residual predicates deliberately remain on the existing row-pair path. Release benchmark evidence in docs/benchmarks.md shows the three scan/filter vectorized medians improving with byte-identical correctness checks and no material non-target regression.
20. LEFT/RIGHT OUTER JOIN arc. Delivered across Phase 20a/20b: the parser accepts LEFT [OUTER] JOIN and RIGHT [OUTER] JOIN; binding normalizes RIGHT to LEFT while stable identities preserve SQL-visible projection order; both interpreted and vectorized engines implement deterministic left-row-major NULL-extension, NULL-key non-matching, and residual-aware matchedness for hash and non-equi joins. LeftJoinToInnerRule additively simplifies a filtered LEFT join only under a proof-bearing conservative 3VL null-rejection test, unlocking the existing INNER commute/associate/pushdown exploration without weakening their guards. The deterministic fuzzer now mixes INNER/LEFT/RIGHT chains with actual NULL-bearing key data and verifies standalone rewrites, every memo alternative, and extract_best through both engines. The Phase 20a LEFT cardinality rule remains sufficient; no 20b cost-model change was required. The outer-join lowering guard and its verifier path are gone.
21. Complete subquery arc. Delivered across Phase 21a/21b/21c: scalar-comparison, IN/NOT IN, and EXISTS/NOT EXISTS use immutable bound subplans with explicit lexical-depth correlation metadata. Empty correlation retains the eager once-per-query 3VL/cardinality model; correlated forms use the per-outer-row interpreted specification with nested/grandparent frames and row-ordered scalar errors. Explicit left SEMI/ANTI algebra has left-only output identity, deterministic interpreted/vectorized hash/NLJ execution, memo identity/printers/EXPLAIN/costing, and conservative guards. Uncorrelated and immediate equality-correlated top-level EXISTS, NOT EXISTS, and IN decorrelate through proof-bearing memo rules. Residual correlated forms remain oracle-defined and fail once at physical lowering; uncorrelated residuals still run vectorized recursively. Exact EXPLAIN goldens, eager/per-row error equivalence, and deterministic uncorrelated/correlated fuzz lanes close the story.
22. Window functions arc. Delivered across Phase 22a/22b: whole-SELECT-item ROW_NUMBER, RANK, and DENSE_RANK plus whole-partition SUM, COUNT, MIN, and MAX parse and bind into one post-HAVING Window node; both interpreted and vectorized execution implement first-appearance partitioning, input-order preservation, stable ranking ties, NULL partition/peer equality, checked/NULL-skipping partition aggregates, and replicated results; Window participates in physical lowering, memo identity, EXPLAIN, extraction, conservative costing, golden coverage, deterministic fuzzing, and a Release benchmark workload while remaining a filter-pushdown barrier, with ROW_NUMBER and whole-partition checked SUM pinning order-changing child transforms because stable ties and intermediate overflow expose input order.
23. Running window frames. Delivered in Phase 23: aggregate OVER ORDER BY defaults to RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, and the same explicit RANGE spelling plus ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW bind as distinct frame modes. RANGE publishes one result through each complete peer group and canonically orders checked SUM arguments within peers, making output and overflow category independent of incidental tie order. ROWS publishes each stable input-order prefix and pins order-changing child transforms; a checked Aggregate SUM below any Window pins independently. The oracle, vectorized operator, memo alternatives, deterministic fuzzer, goldens, and standalone benchmark cover the new paths while whole-partition behavior remains unchanged. Every other frame bound or modifier fails as a positioned unsupported frame.
24. NULL-aware anti join. Delivered in Phase 24: explicit NullAwareAnti algebra separates equality-correlation candidate predicates from one structural membership equality and preserves left-only identity plus left-row-major output. The interpreted candidate-set oracle and vectorized grouped hash/NLJ kernels coincide with NOT IN 3VL for empty, NULL-bearing, NULL-left, match, and miss cases while ordinary Anti remains byte-identical. Proof-bearing memo rules add uncorrelated and immediate equality-correlated NOT IN alternatives without removing the materialized path; memo identity, EXPLAIN, deterministic costing, transform guards, checked-SUM order pins, trap-matrix goldens, 160-seed fuzz floors, and an optimized checksum-before-timing benchmark complete the arc.

Phase 1 first tasks

• Extend the tiny SELECT ... FROM ... WHERE col = literal parser with golden tests.
• Add binder checks for unknown columns and duplicate output names.
• Keep interpreted execution as the oracle before adding more vectorized kernels.
• Add equivalence tests for every rewrite rule.

Phase discipline

Do not optimize before correctness. Every phase should end with an executable deterministic test or replay artifact.

Follow-on ideas

• Add sort elimination or sort pushdown only after required physical properties are represented in the memo.
• Add real per-column statistics behind the catalog boundary, such as exact distinct counts or histograms, while preserving deterministic collection.
• Split logical and physical costing once physical join implementations expose build/probe choices explicitly.
• Add an explicit cross-product algebra/property model so association can represent more valid inner-join reorderings without weakening proof comments.
• Add top-N physical planning only after physical properties can prove the same LIMIT contract under ties and unordered inputs.
• Broaden fuzz coverage when the verifier can prove sortedness for ORDER BY keys that are not emitted in the final output.
• Add value-width-aware string costing and string-specific performance work after collecting more benchmark evidence.
• Investigate aggregation and sort kernels with benchmark evidence before changing their implementations.
• Add bounded, following, GROUPS, and exclusion window frames only after their endpoints and exclusion rules are represented explicitly in the algebra and their order/error observability is proved across memo alternatives.