Query Planner and Physical Lowering

Query Planner and Physical Lowering

Verified against commit c42e19eba on 27 August 2026. Planner details can change between releases.

MemCP compiles SQL into executable Scheme code. It first establishes the relational meaning of a query, decorrelates supported subqueries, and selects a join order. Only then does physical lowering choose scans, indexes, RecSets, caches, computed columns, and storage representations. Keeping those phases separate prevents a storage shortcut from silently changing SQL semantics.

Planner pipeline

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

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

Physical artifacts such as scan, RecSets, keytables, ORC columns, and temporary tables must not leak into logical planning. Conversely, physical lowering consumes the selected join tree; it must not flatten it and choose a second join order.

Logical operator model

MemCP deliberately uses three broad logical shapes instead of splitting every clause into a long chain of tiny relational operators:

• query-block represents SELECT, JOIN, filtering, projection, ordering, LIMIT, and OFFSET;
• group-stage represents grouping, aggregates, correlated domains, EXISTS/IN/scalar helpers, HAVING, and window partitions;
• union-block represents UNION and UNION ALL.

A stage-output is a logical relation, not a physical table. This combined model lets the physical engine fuse filter, projection, and aggregation into one scan when their semantics and order requirements allow it.

Subquery decorrelation

MemCP does not use “run the correlated subquery once per outer row” as a fallback. Supported correlated forms are transformed into relational stages; unsupported shapes fail explicitly.

The simple path collects equality classes, chooses safe representatives, pulls expressions across valid boundaries, and turns trivial dependent joins into ordinary joins. If dependencies remain, the planner constructs Neumann's Domain D: the duplicate-free projection of the outer values actually read by the inner query. Domain keys pass through inner stages and join back to the outer result.

Decorrelation must retain:

• scalar-subquery cardinality, including an error when a single-row subquery returns a second row;
• SQL NULL behavior for IN and NOT IN;
• empty correlated aggregate groups, such as COUNT = 0 versus a nullable aggregate;
• outer-join null extension;
• ordering, LIMIT, and window requirements.

Join ordering

After decorrelation exposes the complete join graph, join_reorder uses relation cardinalities and predicate selectivities to select a tree. Exact DPHyp-style enumeration is available within a configurable budget; larger graphs use bounded strategies. Bushy trees are possible, and independent subtrees may execute in parallel.

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

The physical engine may decide how to execute each selected join edge, but not which logical relation order the query means.

Cost-based physical lowering

Physical lowering compares concrete ways to execute the already selected logical plan. Inputs include cardinality and distinct-count estimates, selectivity, scan and probe work, order compatibility, offset and LIMIT, available/adaptive indexes, group-cache state, expected reuse, build cost, memory, compilation cost, and collected telemetry.

Physical choice	Typical purpose
Fused scan	Unordered filtering, 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 ordered inputs, especially streamable UNION ALL branches.
scan_exists	Stop after proving that a matching row exists.
Direct nested scan	Cheap selective probe driven by bound join keys.
RecSet	Query-local exact or candidate set of record IDs.
Group keytable/cache	Reusable grouped key domain and computed aggregate columns.
FK-backed computed column	Reuse a lookup or aggregate shaped by a foreign key.
ORC	Reusable order-dependent computation, including window dependencies.
Query-local temporary relation	Relational barrier when streaming and reusable representations do not fit.

Intermediate results remain storage-engine scan sources instead of becoming Scheme row lists. That preserves batch reads, indexing, statistics, range braking, late materialization, visibility, and bounded memory behavior.

RecSets and residual predicates

A RecSet belongs to one base relation and visibility snapshot. It can contain the exact TRUE rows of a predicate or only a safe candidate superset. Candidate sets retain the original predicate as a residual filter. The storage engine supports sparse IDs and ranges plus union, intersection, complement, difference, and projection through join keys.

The representation is adaptive per shard (ranges, sorted positive IDs, or bitmap), and construction, algebra, and join projection can run shard-parallel without materializing complete rows. See RecSets for the data structure, scan/filter pipeline, ordered iterators, join projection, cost decisions, and low-level examples.

For truth-filtering contexts the planner can exploit T(p OR q) = T(p) union T(q) and T(p AND q) = T(p) intersect T(q). SQL three-valued logic remains authoritative: complementing TRUE rows is not generally SQL NOT, and nullable NOT IN needs special handling.

LIMIT, UNION, and windows

LIMIT belongs to a physical scan boundary, allowing scans to stop early instead of always materializing all matches. Ordered scans can use top-k thresholds and range braking when the next keys cannot improve the result.

Unordered UNION ALL can emit branches successively; UNION needs deduplication. Ordered streamable inputs can merge through scan_order_multi; incompatible orders materialize only the narrow relation required by the barrier.

A window expression does not automatically require a temporary table. If one order satisfies the base query and all partitions/orders, MemCP can fuse window work into that scan. Conflicting orders or shared order-dependent values can use a stage or ORC computed column.

Plan cache and guarded specialization

The query-plan cache stores compiled Scheme formulas for normalized SQL shapes. A group cache is different: it is a reusable storage-engine relation. When parameters or statistics move the cost-model optimum, one cached SELECT can contain several guarded physical variants. A guard repeats cost comparisons; it does not scan data, build an index, or redo logical planning.

Inspecting optimizer decisions

Both SQL frontends expose complementary views:

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

• EXPLAIN shows the optimized executable Scheme plan;
• EXPLAIN IR shows logical operators before physical emission;
• EXPLAIN REORDER exposes join-order and selectivity information;
• EXPLAIN PHYSICAL summarizes concrete access paths and reusable structures;
• EXPLAIN COMPILE reports time spent parsing, planning, preparing, emitting, and optimizing.

(settings "ExplainWidth" 80)
(settings "ScanDebugging" true)

Correctness boundaries

An unsupported planner shape should report a limitation. It must not silently discard residual predicates, turn an equijoin into a cross product, collapse SQL NULL semantics, replace scalar cardinality checks with LIMIT 1, materialize an unbounded relation as a Scheme list, or introduce per-outer-row correlated execution.

For practical query patterns see Advanced SQL Tutorial. Related internals are covered by RecSets, Data Auto Sharding and Auto Indexing, Temporary Computed Columns, Columnar Storage, Scan, and Parallel Computing.