Query Planner and Physical Lowering: Difference between revisions

From MemCP
Jump to navigation Jump to search
(Created page with "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...")
 
(Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference)
Line 1: Line 1:
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.
<!-- Copyright (C) 2026 Carl-Philip Haensch -->
<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
= Query Planner and Physical Lowering =


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.
<blockquote>'''Verified against commit <code>c42e19eba</code> on 27 August 2026.''' Planner details can change between releases.</blockquote>
==Planner pipeline==
 
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 ==
 
<syntaxhighlight lang="text">
SQL text
   -> MySQL or PostgreSQL parser AST
   -> MySQL or PostgreSQL parser AST
   -> normalize_sql_syntax
   -> normalize_sql_syntax
   -> decorrelate_logical_query / untangle_query
   -> decorrelate_logical_query / untangle_query
   -> logical predicate placement and join_reorder / optimize
   -> predicate placement and join_reorder / optimize
   -> build_queryplan
   -> build_queryplan
   -> Scheme optimizer and optional native JIT
   -> Scheme optimizer and optional native JIT
   -> storage-engine scans</syntaxhighlight>
   -> storage-engine scans
Each phase owns a different kind of decision:
</syntaxhighlight>
 
{| class="wikitable"
{| class="wikitable"
! Phase !! Responsibility
|-
|-
!Phase
| Parser || Preserve SQL structure and produce neutral query terms.
!Responsibility
|-
|-
|Parser
| Normalization || Remove frontend spelling differences and safe syntactic sugar while preserving three-valued logic.
|Preserve SQL structure and produce neutral query terms.
|-
|-
|Normalization
| Decorrelation || Replace dependent subqueries with explicit domains, stages, keys, and joins.
|Remove parser-specific spelling and safe syntactic sugar while preserving SQL three-valued logic.
|-
|-
|Decorrelation
| Logical optimization || Place predicates across proven-safe boundaries, estimate selectivity/cardinality, and choose the join tree.
|Replace dependent subqueries with explicit domains, stages, keys, and joins.
|-
|-
|Logical optimization
| Physical lowering || Select concrete scan sources and operators and emit Scheme code.
|Place predicates across proven-safe boundaries, estimate cardinalities and selectivities, and choose the join tree.
|-
|-
|Physical lowering
| Scheme optimization/JIT || Optimize the functional program and compile supported hot procedures to native x86-64 code.
|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 <code>scan</code>, <code>scan_order</code>, 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:
*<code>query-block</code> represents SELECT, JOIN, filter, projection, order, limit, and offset work.
*<code>group-stage</code> represents grouping, aggregates, correlated domains, EXISTS/IN/scalar helpers, HAVING, and window-partition work.
*<code>union-block</code> represents <code>UNION</code> and <code>UNION ALL</code>.
A <code>stage-output</code> 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.
Physical artifacts such as <code>scan</code>, 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.
==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:
== Logical operator model ==
#collect equality classes;
#choose safe representative expressions;
#pull predicates and projections across valid boundaries;
#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, <code>EXISTS</code>, <code>IN</code>, 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:
MemCP deliberately uses three broad logical shapes instead of splitting every clause into a long chain of tiny relational operators:
*scalar subquery cardinality: ordinary relation, first row, or single row with an error on the second row;
*SQL NULL behavior for <code>IN</code> and <code>NOT IN</code>;
*empty correlated aggregate domains, including <code>COUNT = 0</code> 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, <code>join_reorder</code> 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:
* <code>query-block</code> represents SELECT, JOIN, filtering, projection, ordering, LIMIT, and OFFSET;
*its left and right subtrees;
* <code>group-stage</code> represents grouping, aggregates, correlated domains, EXISTS/IN/scalar helpers, HAVING, and window partitions;
*join kind;
* <code>union-block</code> represents <code>UNION</code> and <code>UNION ALL</code>.
*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:
A <code>stage-output</code> 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.


<code>(settings "JoinReorderDPBudget") (settings "JoinReorderDPBudget" 256)</code>
== Subquery decorrelation ==
==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:
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.
*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:
{| class="wikitable"
|-
!Physical choice
!Typical use
|-
|Fused <code>scan</code>
|Unordered filter, projection, and aggregation in one pass.
|-
|<code>scan_order</code>
|Ordered access, top-k, offset/limit ownership, or a bounded scalar probe.
|-
|<code>scan_order_multi</code>
|Merge already streamable ordered inputs, especially <code>UNION ALL</code>.
|-
|<code>scan_exists</code>
|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:
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.


<code>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)</code> 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.
Decorrelation must retain:


SQL three-valued logic remains authoritative. In particular, complementing the TRUE rows of a nullable predicate is not generally equivalent to SQL <code>NOT</code>, and <code>NOT IN</code> must retain its distinction between a match, a NULL probe, and NULL on the right-hand side.
* scalar-subquery cardinality, including an error when a single-row subquery returns a second row;
==LIMIT, UNION, and window pipelines==
* SQL NULL behavior for <code>IN</code> and <code>NOT IN</code>;
<code>LIMIT</code> is owned by a physical scan boundary. A plan does not first materialize all qualifying rows into a Scheme list and slice it later. <code>scan_order</code> can own LIMIT even without an explicit <code>ORDER BY</code>, allowing early termination and top-k behavior.
* empty correlated aggregate groups, such as <code>COUNT = 0</code> versus a nullable aggregate;
* outer-join null extension;
* ordering, LIMIT, and window requirements.


For set operations, the preferred lowering is:
== Join ordering ==
*unordered <code>UNION ALL</code>: emit branches successively;
*unordered <code>UNION</code>: use a deduplication barrier;
*ordered, streamable <code>UNION ALL</code>: merge through <code>scan_order_multi</code>;
*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.
After decorrelation exposes the complete join graph, <code>join_reorder</code> 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.
==Inspecting plans with EXPLAIN==
Both MySQL and PostgreSQL syntax modes expose planner diagnostics:


<code>EXPLAIN SELECT ...; EXPLAIN IR SELECT ...; EXPLAIN REORDER SELECT ...; EXPLAIN COMPILE SELECT ...;</code>
<syntaxhighlight lang="scheme">
*<code>EXPLAIN</code> shows the optimized executable Scheme plan.
(settings "JoinReorderDPBudget")
*<code>EXPLAIN IR</code> shows the logical representation before physical emission.
(settings "JoinReorderDPBudget" 256)
*<code>EXPLAIN REORDER</code> exposes join-reordering information and selectivity facts.
</syntaxhighlight>
*<code>EXPLAIN COMPILE</code> reports compile-phase accounting, including parsing, logical work, reordering, physical preparation, emission, and optimization.
*<code>EXPLAIN PHYSICAL</code> 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:


<code>(settings "ExplainWidth" 80)</code>
The physical engine may decide how to execute each selected join edge, but not which logical relation order the query means.


For scan and adaptive-index diagnostics, development environments can also use:
== Cost-based physical lowering ==


<code>(settings "ScanDebugging" true)</code>
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.
==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 <code>NOT IN</code> as two-valued logic;
*reduce scalar cardinality checks to <code>LIMIT 1</code>;
*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==
{| class="wikitable"
{| class="wikitable"
! Physical choice !! Typical purpose
|-
|-
!Term
| Fused <code>scan</code> || Unordered filtering, projection, and aggregation in one pass.
!Meaning
|-
|-
|Logical stage
| <code>scan_order</code> || Ordered access, top-k, offset/LIMIT ownership, or a bounded scalar probe.
|Semantic query work independent of storage representation.
|-
|-
|Scan source
| <code>scan_order_multi</code> || Merge already ordered inputs, especially streamable <code>UNION ALL</code> branches.
|A storage-engine representation consumable by a physical scan.
|-
|-
|Intermediate relation
| <code>scan_exists</code> || Stop after proving that a matching row exists.
|A relational result materialized as a scan source between plan stages.
|-
|-
|Group cache
| Direct nested scan || Cheap selective probe driven by bound join keys.
|A reusable intermediate relation for group keys and aggregates.
|-
|-
|Group keytable
| RecSet || Query-local exact or candidate set of record IDs.
|The normal physical representation of a group cache.
|-
|-
|ORC
| Group keytable/cache || Reusable grouped key domain and computed aggregate columns.
|An order-dependent reusable computed column.
|-
|-
|RecSet
| FK-backed computed column || Reuse a lookup or aggregate shaped by a foreign key.
|A query-local set or candidate set of record IDs for one base relation.
|-
|-
|Physical lowering
| ORC || Reusable order-dependent computation, including window dependencies.
|Selection of concrete scan sources/operators after logical planning.
|-
|-
|Guarded specialization
| Query-local temporary relation || Relational barrier when streaming and reusable representations do not fit.
|Multiple cost-guarded physical plans for one normalized SELECT shape.
|}
|}
==Further reading==
 
*[[Data_Auto_Sharding_and_Auto_Indexing|Data Auto Sharding and Auto Indexing]]
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.
*[[Temporary_Computed_Columns|Temporary Computed Columns]]
 
*[[Columnar_Storage|Columnar Storage]]
== RecSets and residual predicates ==
*[[Parallel_Computing|Parallel Computing]]
 
*MemCP source: <code>INVARIANTS.md</code>, <code>lib/queryplan.scm</code>, <code>lib/sql-parser.scm</code>, <code>lib/psql-parser.scm</code>, <code>storage/scan.go</code>, <code>storage/scan_order.go</code>, and <code>storage/recset.go</code>
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 <code>T(p OR q) = T(p) union T(q)</code> and <code>T(p AND q) = T(p) intersect T(q)</code>. SQL three-valued logic remains authoritative: complementing TRUE rows is not generally SQL <code>NOT</code>, and nullable <code>NOT IN</code> 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 <code>UNION ALL</code> can emit branches successively; <code>UNION</code> needs deduplication. Ordered streamable inputs can merge through <code>scan_order_multi</code>; 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:
 
<syntaxhighlight lang="sql">
EXPLAIN SELECT ...;
EXPLAIN IR SELECT ...;
EXPLAIN REORDER SELECT ...;
EXPLAIN PHYSICAL SELECT ...;
EXPLAIN COMPILE SELECT ...;
</syntaxhighlight>
 
* <code>EXPLAIN</code> shows the optimized executable Scheme plan;
* <code>EXPLAIN IR</code> shows logical operators before physical emission;
* <code>EXPLAIN REORDER</code> exposes join-order and selectivity information;
* <code>EXPLAIN PHYSICAL</code> summarizes concrete access paths and reusable structures;
* <code>EXPLAIN COMPILE</code> reports time spent parsing, planning, preparing, emitting, and optimizing.
 
<syntaxhighlight lang="scheme">
(settings "ExplainWidth" 80)
(settings "ScanDebugging" true)
</syntaxhighlight>
 
== 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 <code>LIMIT 1</code>, 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]].

Revision as of 11:59, 28 August 2026

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

<syntaxhighlight lang="text"> 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

</syntaxhighlight>

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.

<syntaxhighlight lang="scheme"> (settings "JoinReorderDPBudget") (settings "JoinReorderDPBudget" 256) </syntaxhighlight>

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:

<syntaxhighlight lang="sql"> EXPLAIN SELECT ...; EXPLAIN IR SELECT ...; EXPLAIN REORDER SELECT ...; EXPLAIN PHYSICAL SELECT ...; EXPLAIN COMPILE SELECT ...; </syntaxhighlight>

  • 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.

<syntaxhighlight lang="scheme"> (settings "ExplainWidth" 80) (settings "ScanDebugging" true) </syntaxhighlight>

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.

Retrieved from "https://www.memcp.org/index.php?title=Query_Planner_and_Physical_Lowering&oldid=304"