Query Planner and Physical Lowering

MemCP compiles SQL into executable Scheme code. The planner first converts SQL into a logical representation, decorrelates subqueries, and chooses a join order. Only after those semantic decisions are complete does the physical lowerer select scans, indexes, caches, RecSets, computed columns, and other storage-engine operators.

This separation is important: two queries that mean the same thing should reach the same logical representation even when they use different SQL spelling. The physical plan can then be chosen from statistics, parameters, ordering, limits, and the state of reusable intermediate relations.

Planner pipeline

 -> MySQL or PostgreSQL parser AST
 -> normalize_sql_syntax
 -> decorrelate_logical_query / untangle_query
 -> logical predicate placement and join_reorder / optimize
 -> build_queryplan
 -> Scheme optimizer and optional native JIT
 -> storage-engine scans</syntaxhighlight>

Each phase owns a different kind of decision:

Phase	Responsibility
Parser	Preserve SQL structure and produce neutral query terms.
Normalization	Remove parser-specific spelling and safe syntactic sugar while preserving SQL three-valued logic.
Decorrelation	Replace dependent subqueries with explicit domains, stages, keys, and joins.
Logical optimization	Place predicates across proven-safe boundaries, estimate cardinalities and selectivities, and choose the join tree.
Physical lowering	Select concrete scan sources and operators, bind predicates to scans, and emit Scheme code.
Scheme optimization/JIT	Optimize the emitted functional program and compile supported hot paths to native code.

Physical objects such as scan, scan_order, RecSets, keytables, ORC columns, and temporary tables must not leak into the logical representation. Conversely, the physical lowerer must not redo decorrelation or silently choose a different join order.

Logical representation

MemCP deliberately uses three coarse combined operator shapes instead of a long chain of textbook relational operators:

• query-block represents SELECT, JOIN, filter, projection, order, limit, and offset work.
• group-stage represents grouping, aggregates, correlated domains, EXISTS/IN/scalar helpers, HAVING, and window-partition work.
• union-block represents UNION and UNION ALL.

A stage-output describes the logical relation produced by a group or union stage. It is not a physical table and does not prescribe how the result will be stored or scanned.

This combined model keeps related operations together so the physical engine can fuse them into one scan where possible. Splitting every filter, projection, and limit into a separate logical node would introduce artificial materialization boundaries and make later rewrites more expensive.

Subquery decorrelation

MemCP does not execute a correlated subquery once for every outer row as a fallback. Supported correlated forms are decorrelated into relational stages. Unsupported shapes fail explicitly instead of silently selecting a slow or semantically weaker execution path.

The planner first tries simple unnesting:

1. collect equality classes;
2. choose safe representative expressions;
3. pull predicates and projections across valid boundaries;
4. convert trivial dependent joins into ordinary joins.

If dependencies remain, the planner builds Neumann's Domain D: the duplicate-free projection of the outer values actually read by the dependent subtree. Domain keys are carried through the inner stages and joined back to the outer query. This supports correlated scalar subqueries, EXISTS, IN, grouped subqueries, HAVING, derived tables, and window expressions without per-row recursive SQL execution.

The logical stage also preserves semantic details that must survive lowering:

• scalar subquery cardinality: ordinary relation, first row, or single row with an error on the second row;
• SQL NULL behavior for IN and NOT IN;
• empty correlated aggregate domains, including COUNT = 0 versus nullable aggregates;
• outer-join null-extension boundaries;
• ordering, limit, and window requirements.

Join ordering

Join ordering is a logical decision with one owner. After decorrelation exposes the complete join graph, join_reorder uses cardinality and selectivity facts to choose a join tree. The search can use exact DPHyp-style enumeration within the configured budget and fall back to bounded strategies for larger join graphs.

The selected tree can be bushy. Physical lowering consumes that tree structurally; it may not flatten the leaves and make a second order decision. Each join node retains:

• its left and right subtrees;
• join kind;
• bound aliases;
• ON-clause ownership;
• null-extension boundary;
• predicates already classified and costed for a leaf.

Independent subtrees may run in parallel. Dependent subtrees remain ordered by their bindings. This execution choice does not change the logical join order.

The exact-search budget can be inspected or changed through:

(settings "JoinReorderDPBudget") (settings "JoinReorderDPBudget" 256)

Cost-based physical lowering

The physical lowerer answers a different question from join ordering: given the chosen logical stage and join tree, which concrete storage-engine representation and operator is cheapest while preserving its semantics?

The cost model can consider:

• base-table, stage, and probe cardinality;
• filter selectivity and distinct key counts;
• scan and probe work estimates;
• order compatibility, offset, and limit;
• available and adaptive indexes;
• warm or cold state of reusable group caches;
• expected reuse count;
• build cost versus probe cost;
• memory footprint;
• compile-time cost;
• previous scan and intermediate-relation telemetry.

Depending on these facts, the same logical stage may lower differently:

Physical choice	Typical use
Fused scan	Unordered filter, projection, and aggregation in one pass.
scan_order	Ordered access, top-k, offset/limit ownership, or a bounded scalar probe.
scan_order_multi	Merge already streamable ordered inputs, especially UNION ALL.
scan_exists	Stop after proving that at least one matching row exists.
Direct nested scan	Cheap selective lookup driven by already bound join keys.
RecSet	Query-local set of matching record IDs for membership and boolean combinations.
RecSet projection	Move a selective candidate set through join keys to another base relation.
Group keytable	Reusable grouped key domain with computed aggregate columns.
FK-backed cached column	Reuse a foreign-key-shaped lookup or aggregate result on the referencing relation.
ORC computed column	Reusable order-dependent computation, including window work with dependency ranges.
Query-local temporary table	Last-resort relational barrier when streaming or reusable representations do not fit.

Relational results stay inside the storage engine. They are not copied into Scheme lists merely to join, sort, limit, or probe them. Keeping them as scan sources preserves indexing, statistics, batch reads, range braking, late materialization, concurrency, and bounded memory behavior.

RecSets and boolean predicates

A RecSet is a query-local set of physical record IDs for one base relation and visibility snapshot. RecSets can represent exact truth sets or safe candidate sets that still require a residual SQL predicate.

For truth-filtering contexts, the planner can use ordinary set identities:

T(false) = empty T(true) = all visible rows T(p OR q) = T(p) union T(q) T(p AND q) = T(p) intersect T(q) Current physical representations include sparse IDs and ranges, with optimized union, intersection, complement, difference, and cross-relation projection. The planner still compares RecSet work with direct scans, indexes, keytables, and ordered drivers; deriving a valid set expression does not force RecSet execution.

SQL three-valued logic remains authoritative. In particular, complementing the TRUE rows of a nullable predicate is not generally equivalent to SQL NOT, and NOT IN must retain its distinction between a match, a NULL probe, and NULL on the right-hand side.

LIMIT, UNION, and window pipelines

LIMIT is owned by a physical scan boundary. A plan does not first materialize all qualifying rows into a Scheme list and slice it later. scan_order can own LIMIT even without an explicit ORDER BY, allowing early termination and top-k behavior.

For set operations, the preferred lowering is:

• unordered UNION ALL: emit branches successively;
• unordered UNION: use a deduplication barrier;
• ordered, streamable UNION ALL: merge through scan_order_multi;
• non-streamable ordered unions: materialize only the narrow relation required by the ordering barrier.

A window expression does not automatically force materialization. If one scan order satisfies the base query and every window partition/order, MemCP can fuse the window computation into that ordered scan. ORC or a window stage is used when orders conflict, results are shared, or an order-dependent value must be cached as a computed column.

Planner cache and guarded specialization

The query-plan cache and storage-engine group caches are separate:

• The query-plan cache stores compiled Scheme plan formulas for normalized SQL shapes.
• A group cache is a reusable storage-engine relation, normally represented by a group keytable with computed aggregate columns.

For a SELECT whose optimal physical plan depends on parameters or changing statistics, one cache entry may contain several guarded physical variants. A guard records the condition under which its plan remains valid. On a guard miss, MemCP compiles one new variant for the current parameter/statistics regime and places it before older variants.

Guards repeat cost comparisons, not query planning. They do not scan tables, build indexes or caches, or materialize data. Queries without a cost-model tipping decision keep the smaller exact-cache path.

Inspecting plans with EXPLAIN

Both MySQL and PostgreSQL syntax modes expose planner diagnostics:

EXPLAIN SELECT ...; EXPLAIN IR SELECT ...; EXPLAIN REORDER SELECT ...; EXPLAIN COMPILE SELECT ...;

• EXPLAIN shows the optimized executable Scheme plan.
• EXPLAIN IR shows the logical representation before physical emission.
• EXPLAIN REORDER exposes join-reordering information and selectivity facts.
• EXPLAIN COMPILE reports compile-phase accounting, including parsing, logical work, reordering, physical preparation, emission, and optimization.
• EXPLAIN PHYSICAL reports plan operator decisions along with query runtime predictions.

Important physical choices should be visible in EXPLAIN output so plan-shape tests can protect them against regressions. Pretty-print width is controlled by:

(settings "ExplainWidth" 80)

For scan and adaptive-index diagnostics, development environments can also use:

(settings "ScanDebugging" true)

Adaptive indexes and physical plans

Adaptive indexing belongs to storage access, not logical planning. Scan boundaries describe the desired equality, range, pattern, and ordering prefix. The storage engine can reuse a compatible longer index, avoid creating indexes for tiny shards, accumulate expected savings, and build an index when its cost is amortized.

Main-storage and delta rows participate in ordered index scans. Delta rows are kept in an index-local ordered structure and merged with the compressed main permutation during iteration, so an ordered physical plan does not append delta rows out of order.

Failure behavior and correctness boundaries

The planner favors explicit failure over hidden fallback behavior. An unsupported correlated or physical shape should report that limitation. It must not silently:

• execute a correlated subquery once per outer row;
• discard residual predicates;
• turn an equijoin into a cross product;
• treat NOT IN as two-valued logic;
• reduce scalar cardinality checks to LIMIT 1;
• materialize an unbounded relation in a Scheme list;
• choose a second join order during physical lowering.

This rule keeps performance decisions separate from SQL correctness and makes missing optimizer cases visible in tests and issue reports.

Terminology

Term	Meaning
Logical stage	Semantic query work independent of storage representation.
Scan source	A storage-engine representation consumable by a physical scan.
Intermediate relation	A relational result materialized as a scan source between plan stages.
Group cache	A reusable intermediate relation for group keys and aggregates.
Group keytable	The normal physical representation of a group cache.
ORC	An order-dependent reusable computed column.
RecSet	A query-local set or candidate set of record IDs for one base relation.
Physical lowering	Selection of concrete scan sources/operators after logical planning.
Guarded specialization	Multiple cost-guarded physical plans for one normalized SELECT shape.

Further reading

• Data Auto Sharding and Auto Indexing
• Temporary Computed Columns
• Columnar Storage
• Parallel Computing
• MemCP source: INVARIANTS.md, lib/queryplan.scm, lib/sql-parser.scm, lib/psql-parser.scm, storage/scan.go, storage/scan_order.go, and storage/recset.go