Chapter 17.3 · Query Planning and Execution · 21 min read
ORCA Transformation Rules and the Search Space
How xforms rewrite expressions into alternatives, which rules fire for joins and aggregates, and how to disable a transformation to test its effect.
By Tushar Pednekar · · Verified against the Apache Cloudberry source tree, read September 2026
Every alternative plan ORCA considers came from a transformation rule. You can list them, and you can turn them off one at a time.
§17.2 described the search: a memo of groups, a scheduler, jobs that push each group through exploration, implementation and optimization. What it deliberately left out is what the search actually applies. ORCA has no hard-coded plan shapes at all — no create_hashjoin_path(), no make_agg() decision tree. Every expression that ever enters the memo, logical or physical, arrives through a transformation rule: a CXform. The optimizer is therefore a small engine plus a large rule library, and almost everything you can steer about an ORCA plan is really a statement about which rules are live. This section is the rule library: the anatomy of one rule, the shape of the catalogue, how a rule finds work to do, how to see which rules fired, and the two families that dominate real plans — join-order enumeration and subquery decorrelation.
17.3.1 The anatomy of one rule
CXform (libgpopt/include/gpopt/xforms/CXform.h:48) is a tiny abstract class. A concrete rule must supply four things: an id (Exfid(), one of the CXform::Exf* enum constants), a name (SzId(), the string disable_xform and the trace output use), a promise (Exfp(), returning ExfpNone / ExfpLow / ExfpMedium / ExfpHigh — a cheap veto so the engine can skip a rule that cannot possibly apply), and Transform(), the only place a new expression is ever built. It also carries one piece of data: m_pexpr, the pattern, handed to the base constructor and returned by PexprPattern(). Two virtual predicates classify it: FExploration() means logical→logical, FImplementation() means logical→physical; the subclasses CXformExploration and CXformImplementation just answer those. Nothing else — no apply order, no priority list, no cost hook. A rule is a pattern plus a function. Take the smallest interesting exploration rule, inner-join commutativity: its whole applicability is that pattern, built in the constructor as a CLogicalInnerJoin whose three children are CPatternLeaf wildcards (outer, inner, predicate).
src/backend/gporca/libgpopt/src/xforms/CXformInnerJoinCommutativity.cpp:33
CXformInnerJoinCommutativity::CXformInnerJoinCommutativity(CMemoryPool *mp)
: CXformExploration(
// pattern
GPOS_NEW(mp) CExpression(
mp, GPOS_NEW(mp) CLogicalInnerJoin(mp),
GPOS_NEW(mp)
CExpression(mp, GPOS_NEW(mp) CPatternLeaf(mp)), // left child
GPOS_NEW(mp) CExpression(
mp, GPOS_NEW(mp) CPatternLeaf(mp)), // right child
GPOS_NEW(mp)
CExpression(mp, GPOS_NEW(mp) CPatternLeaf(mp))) // predicate
)
{
}
Transform() then does the obvious thing — pull the three children out of the matched expression, rebuild the join with them swapped, and hand the result to the CXformResult accumulator. Note that it adds; it never mutates, never chooses, never costs. A rule that produces two alternatives simply calls pxfres->Add() twice, and a rule that decides it has nothing to offer adds nothing and returns. The implementation kind is structurally identical and differs only in what it emits: CXformImplementInnerJoin (libgpopt/src/xforms/CXformImplementInnerJoin.cpp:34) binds the same CLogicalInnerJoin pattern — with a CPatternTree in the predicate position, because it needs to look inside the predicate — and produces a CPhysicalInnerHashJoin, falling back to CPhysicalInnerNLJoin when the hash join yields nothing (:83). One logical operator, two possible physical operators, one rule. That is the whole of “choose a join method” in ORCA; which of the two survives is settled later, by cost (§17.4), just as add_path settles between equivalent Path nodes in §15.3 — except that here the alternatives had to be generated by a rule first.
src/backend/gporca/libgpopt/src/xforms/CXformInnerJoinCommutativity.cpp:95
CExpression *pexprLeft = (*pexpr)[0];
CExpression *pexprRight = (*pexpr)[1];
CExpression *pexprScalar = (*pexpr)[2];
...
// assemble transformed expression
CExpression *pexprAlt = CUtils::PexprLogicalJoin<CLogicalInnerJoin>(
mp, pexprRight, pexprLeft, pexprScalar);
...
// add alternative to transformation result
pxfres->Add(pexprAlt);
Both kinds firing, live — commutativity rewriting the join, then CXformImplementInnerJoin turning one of the results into a physical operator. This build is --enable-cassert, so ORCA’s developer print flags emit; optimizer_print_xform needs optimizer_print_xform_results set as well (CGroupExpression.cpp:1028). Output trimmed: long Columns: [...] lists elided, one full TRACE header kept.
SET client_min_messages=log;
SET optimizer_print_xform=on;
SET optimizer_print_xform_results=on;
EXPLAIN SELECT * FROM m173_a x JOIN m173_b y ON x.id=y.id;
LOG: 2026-08-14 00:30:29:910742 CST,THD000,TRACE,"Xform: CXformExpandNAryJoinDPv2
Input:
+--CLogicalNAryJoin rows:20000 width:84 rebinds:1 origin: [Grp:5, GrpExpr:0]
...
2026-08-14 00:30:29:911471 CST,THD000,TRACE,"Xform: CXformInnerJoinCommutativity
Input:
+--CLogicalInnerJoin origin: [Grp:5, GrpExpr:1]
|--CLogicalGet "x" ("x"), Columns: [ ... ] origin: [Grp:0, GrpExpr:0]
|--CLogicalGet "y" ("y"), Columns: [ ... ] origin: [Grp:1, GrpExpr:0]
+--CScalarCmp (=) origin: [Grp:4, GrpExpr:0]
Output:
Alternatives:
0:
+--CLogicalInnerJoin
|--CLogicalGet "y" ("y"), Columns: [ ... ] origin: [Grp:1, GrpExpr:0]
|--CLogicalGet "x" ("x"), Columns: [ ... ] origin: [Grp:0, GrpExpr:0]
+--CScalarCmp (=) origin: [Grp:4, GrpExpr:0]
",
...
2026-08-14 00:30:29:913767 CST,THD000,TRACE,"Xform: CXformImplementInnerJoin
Input:
+--CLogicalInnerJoin rows:20000 width:84 rebinds:1 origin: [Grp:5, GrpExpr:2]
...
Output:
Alternatives:
0:
+--CPhysicalInnerHashJoin cost:-0.500000
|--CLogicalGet "y" ("y"), Columns: [ ... ] origin: [Grp:1, GrpExpr:0]
|--CLogicalGet "x" ("x"), Columns: [ ... ] origin: [Grp:0, GrpExpr:0]
+--CScalarCmp (=) origin: [Grp:4, GrpExpr:0]
",
17.3.2 The catalogue, and why it is a bitset
libgpopt/src/xforms/ holds 133 .cpp files (269 directory entries once objects are counted) and CXform.h enumerates 177 Exf* ids, from ExfProject2ComputeScalar = 0 (:67) to ExfSplitWindowFunc (:243), closed by ExfInvalid and ExfSentinel = ExfInvalid (:245). Twenty-four of those ids are retired placeholders spelled ____removed — the header explains why they cannot simply be deleted (:59): ids are referenced positionally by the traceflags that disable them, so shifting them would silently disable the wrong rule. CXformFactory::Instantiate() (CXformFactory.cpp:139) therefore makes exactly 152 Add() calls and steps over the 25 dead slots with SkipUnused(), asserting on every one that the id it is adding equals the next expected position. Add() is also where the three indexes over the rule set get built: an array by id, a hash map by name (the one disable_xform('CXform...') looks in), and — the important one — two CXformSet bitsets partitioning the catalogue into exploration and implementation rules. CXformSet is CEnumSet<CXform::EXformId, CXform::ExfSentinel> (CXform.h:378): the enabled rule set is literally a bitset over rule ids, which is why every knob in this chapter, from optimizer_join_order to disable_xform, ultimately just flips bits.
src/backend/gporca/libgpopt/src/xforms/CXformFactory.cpp:102
m_rgpxf[exfid] = pxform;
// create name -> xform mapping
ULONG length = clib::Strlen(pxform->SzId());
CHAR *szXformName = GPOS_NEW_ARRAY(m_mp, CHAR, length + 1);
clib::Strncpy(szXformName, pxform->SzId(), length + 1);
... m_phmszxform->Insert(szXformName, pxform);
CXformSet *xform_set = m_pxfsExploration;
if (pxform->FImplementation())
{
xform_set = m_pxfsImplementation;
}
... xform_set->ExchangeSet(exfid);
| family | what it rewrites | representative rules |
|---|---|---|
| join enumeration (exploration) | expands the n-ary join staging operator into binary trees, and reorders existing binary joins | CXformExpandNAryJoin, CXformExpandNAryJoinDPv2, CXformInnerJoinCommutativity, CXformJoinAssociativity |
| join implementation | logical join → physical join operator | CXformImplementInnerJoin, CXformLeftOuterJoin2HashJoin, CXformLeftAntiSemiJoin2NLJoin, CXformImplementFullOuterMergeJoin |
| join-type rewriting | turns one join flavour into another when semantics allow it | CXformLeftSemiJoin2InnerJoin, CXformLeftJoin2RightJoin, CXformExpandFullOuterJoin, CXformLeftAntiSemiJoin2CrossProduct |
| subquery unnesting | subquery → Apply → join (§17.3.6) | CXformSimplifySelectWithSubquery, CXformSelect2Apply, CXformLeftSemiApply2LeftSemiJoin, CXformInnerApply2InnerJoin |
| aggregate splitting and pushdown | two-stage aggregation, DQA rewriting, pushing a GbAgg below a join or union | CXformSplitGbAgg, CXformSplitDQA, CXformPushGbBelowJoin, CXformEagerAgg, CXformGbAgg2HashAgg |
| scan, index and bitmap selection | choosing an access path for a base relation | CXformGet2TableScan, CXformSelect2IndexGet, CXformSelect2IndexOnlyGet, CXformSelect2BitmapBoolOp, CXformJoin2IndexGetApply, CXformMinMax2IndexGet |
| partitioned tables and DPE | dynamic scans and partition selectors, i.e. runtime partition elimination | CXformDynamicGet2DynamicTableScan, CXformDynamicIndexGet2DynamicIndexScan, ExfImplementPartitionSelector, CXformExpandDynamicGetWithForeignPartitions |
| set operations | rewriting UNION/INTERSECT/EXCEPT into joins and union-alls | CXformUnion2UnionAll, CXformIntersect2Join, CXformDifference2LeftAntiSemiJoin, CXformPushJoinBelowUnionAll |
| CTE | inline a consumer, or materialize the producer as a Sequence | CXformCTEAnchor2Sequence, CXformInlineCTEConsumer, CXformImplementCTEProducer, CXformImplementCTEConsumer |
| DML and windowing | the remaining top-level shapes | CXformInsert2DML, CXformImplementDML, CXformImplementSplit, CXformSplitWindowFunc, CXformImplementSequenceProject, CXformSplitLimit |
| (none) — Motion | there is no Motion xform. No Exf* id and no file in src/xforms/ mentions Motion | Motion is added by CEngine::AddEnforcers (CEngine.cpp:217) as an enforcer of a required distribution property — the ORCA counterpart of cdbpath_create_motion_path in §16.2, and the reason Motion shows up as a physical alternative inside a group in the memo dumps of §17.2 |
17.3.3 Binding: a pattern matches a group, not a tree
A rule is applied not to an expression but to a group expression, and its pattern is matched against the memo. That distinction is the whole reason a Cascades optimizer scales. When the commutativity pattern’s CPatternLeaf sits over a child group, it stands for every logical expression that group contains, now and later. CBinding (libgpopt/src/search/CBinding.cpp) walks the memo and enumerates those matches one at a time: PexprExtract(mp, pgexpr, pattern, pexprLast) returns the next concrete expression matching the pattern, threading a cursor through the child groups (FInitChildCursors / FAdvanceChildCursors). Each returned expression is one binding, and a single (group expression, rule) pair can produce many. Three guards keep the loop below from exploding: IsApplyOnce() lets a rule declare that one binding is enough; FCompatible(m_exfidOrigin) — checked before binding even starts, at CGroupExpression.cpp:781 — lets a rule refuse to run on expressions it or a sibling produced, and commutativity declares itself incompatible with ExfInnerJoinCommutativity (CXformInnerJoinCommutativity.cpp:58), which is what stops it swapping a join back and forth forever; and optimizer_xform_bind_threshold (0 = unlimited, the default here) caps bindings per call. That counter is reset for every call in CEngine::ApplyTransformations (CEngine.cpp:730), so it is a per-rule-per-group-expression budget, not a global one; the same counters are what CEngine::GetNumberOfBindings (:2343) exposes and what the total bindings column below reports.
src/backend/gporca/libgpopt/src/search/CGroupExpression.cpp:814
CExpression *pexprPattern = pxform->PexprPattern();
CExpression *pexpr = binding.PexprExtract(mp, this, pexprPattern, nullptr);
while (nullptr != pexpr)
{
++(*pulNumberOfBindings);
ULONG ulNumResults = pxfres->Pdrgpexpr()->Size();
pxform->Transform(pxfctxt, pxfres, pexpr);
...
if ((bindThreshold != 0 && (*pulNumberOfBindings) > bindThreshold) ||
pxform->IsApplyOnce() || ...)
{
// do not apply xform to other possible patterns
pexpr->Release(); break;
}
pexpr = binding.PexprExtract(mp, this, pexprPattern, pexpr);
}
1: CLogicalInnerJoin [ b a p ]
2: CLogicalNAryJoin [ a b p ]
the NAryJoin does not match the
pattern's inner CLogicalInnerJoin
alternatives to one CXformResult
17.3.4 Which rules actually fired
optimizer_print_optimization_stats=on reaches CEngine::PrintActivatedXforms (CEngine.cpp:1548), which prints, per search stage, every rule that was activated with its call count, binding count, alternatives produced and time. Output trimmed; the timer TRACE lines and the memory lines are elided.
SET client_min_messages=log;
SET optimizer_print_optimization_stats=on;
EXPLAIN SELECT count(*) FROM m173_t t1 JOIN m173_t t2 ON t1.a=t2.a WHERE t1.b=5;
LOG: 2026-08-14 00:30:15:020892 CST,THD000,TRACE,"timer:
[OPT]: Query To DXL Translation Time: 3ms",
...
[OPT]: Memo (stage 0): [24 groups, 0 duplicate groups, 42 group expressions, 7 activated xforms]
[OPT]: stage 0 completed in 9ms, plan with cost 863.809816 was found
[OPT]: <Begin Xforms - stage 0>
CXformGet2TableScan: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
CXformSelect2Filter: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformGbAgg2ScalarAgg: 3 calls, 3 total bindings, 3 alternatives generated, 0ms
CXformInnerJoinCommutativity: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformSplitGbAgg: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformExpandNAryJoinDPv2: 1 calls, 1 total bindings, 3 alternatives generated, 2ms
CXformImplementInnerJoin: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
[OPT]: <End Xforms - stage 0>
...
[OPT]: Total Optimization Time: 20ms",
Finalize Aggregate (cost=0.00..863.81 rows=1 width=8)
-> Gather Motion 3:1 (slice1; segments: 3) (cost=0.00..863.81 rows=1 width=8)
-> Partial Aggregate (cost=0.00..863.81 rows=1 width=8)
-> Hash Join (cost=0.00..863.81 rows=67 width=1)
Hash Cond: (t2.a = t1.a)
Optimizer: GPORCA
Seven rules, eleven calls, thirteen alternatives — and that is the entire derivation of this plan. Read top to bottom it is a complete account: Get2TableScan gave each base relation a physical scan, Select2Filter turned the b = 5 predicate into a Filter, ExpandNAryJoinDPv2 expanded the n-ary join staging operator into three binary alternatives, InnerJoinCommutativity added the mirrored order, ImplementInnerJoin turned two of the surviving logical joins into hash joins, and SplitGbAgg + GbAgg2ScalarAgg produced the Partial/Finalize pair you can see in the plan (ORCA’s own two-stage aggregation, the counterpart of §16.4). Nothing in the plan came from anywhere else. When an ORCA plan surprises you, this list is the first thing to look at — and note the 7 activated xforms against 152 available. Nothing like the whole catalogue is ever tried: each logical operator publishes its own candidate set (CLogicalInnerJoin::PxfsCandidates, libgpopt/src/operators/CLogicalInnerJoin.cpp:67, names eleven rules and no others), and that set is intersected with the factory’s exploration-or-implementation bitset and again with the current search stage’s bitset before anything is scheduled (CJobGroupExpressionExploration.cpp:176). Three bitset intersections; only what survives them is even asked for a promise.
17.3.5 Join order: the same query, four rule sets
Join enumeration deserves its own treatment because it is the one family whose size is user-visible. Preprocessing collapses a contiguous run of inner joins into a single n-ary staging operator: CExpressionPreprocessor::PexprCollapseJoins (libgpopt/src/operators/CExpressionPreprocessor.cpp:852) builds a CLogicalNAryJoin whose last child is the conjunction of all the join predicates (:953). Nothing can execute a CLogicalNAryJoin — it exists purely so that one rule can see the whole join at once and propose an order for it. Five rules do that, and optimizer_join_order chooses between them. Not by naming one, but by disabling the others: CConfigParamMapping.cpp:522 switches on the GUC and unions in one of four precomputed bitsets, CXform::PbsJoinOrderInQueryXforms and friends (libgpopt/src/xforms/CXform.cpp:222–:287), each of which is a list of rules to switch off.
| optimizer_join_order | enumerator rules left live | commutativity / associativity | group exprs | stage 0 | plan cost |
|---|---|---|---|---|---|
query | CXformExpandNAryJoin only — keeps the order written in the SQL | both switched off by the mode | 74 | 27 ms | 2162.03 |
greedy | + ...MinCard, + ...Greedy | both switched off by the mode | 109 | 63 ms | 2160.42 |
exhaustive | + ...DP (bounded by optimizer_join_order_threshold) | left live; associativity then gated by optimizer_enable_associativity | 221 | 340 ms | 2160.29 |
exhaustive2 (default) | CXformExpandNAryJoinDPv2 only; also switches off ExfPushDownLeftOuterJoin and sets EopttraceEnableLOJInNAryJoin so outer joins join the enumeration | same | 236 | 179 ms | 2160.29 |
The same 5-way chain join under the extreme settings. Real output, trimmed to the enumerator rules, the memo summary and the join skeleton of the plan.
-- five tables of 50k / 20k / 5k / 1k / 200 rows, joined a-b-c-d-e in that order
SET optimizer_join_order='query'; -- then 'exhaustive2'
SET optimizer_print_optimization_stats=on;
EXPLAIN SELECT count(*) FROM m173_a a, m173_b b, m173_c c, m173_d d, m173_e e
WHERE a.id=b.id AND b.id=c.id AND c.id=d.id AND d.id=e.id;
--------------------------- optimizer_join_order = query
[OPT]: Memo (stage 0): [39 groups, 0 duplicate groups, 74 group expressions, 5 activated xforms]
[OPT]: stage 0 completed in 27ms, plan with cost 2162.032356 was found
CXformExpandNAryJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformImplementInnerJoin: 4 calls, 4 total bindings, 4 alternatives generated, 0ms
-> Hash Join (cost=0.00..2162.03 rows=72 width=1)
Hash Cond: (d.id = e.id)
-> Hash Join (cost=0.00..1730.96 rows=342 width=4)
Hash Cond: (c.id = d.id)
-> Hash Join (cost=0.00..1299.58 rows=1680 width=4)
Hash Cond: (b.id = c.id)
-> Hash Join (cost=0.00..867.02 rows=6667 width=4)
Hash Cond: (a.id = b.id)
-> Seq Scan on m173_a a (cost=0.00..431.38 rows=16667 width=4)
-> Hash (cost=431.15..431.15 rows=6667 width=4)
-> Seq Scan on m173_b b (cost=0.00..431.15 rows=6667 width=4)
--------------------------- optimizer_join_order = exhaustive2
[OPT]: Memo (stage 0): [53 groups, 0 duplicate groups, 236 group expressions, 6 activated xforms]
[OPT]: stage 0 completed in 179ms, plan with cost 2160.294322 was found
CXformInnerJoinCommutativity: 26 calls, 26 total bindings, 26 alternatives generated, 0ms
CXformExpandNAryJoinDPv2: 1 calls, 1 total bindings, 10 alternatives generated, 34ms
CXformImplementInnerJoin: 52 calls, 52 total bindings, 52 alternatives generated, 0ms
-> Hash Join (cost=0.00..2160.29 rows=72 width=1)
Hash Cond: (d.id = c.id)
-> Seq Scan on m173_d d (cost=0.00..431.01 rows=334 width=4)
-> Hash (cost=1729.21..1729.21 rows=67 width=4)
-> Hash Join (cost=0.00..1729.21 rows=67 width=4)
Hash Cond: (c.id = b.id)
-> Seq Scan on m173_c c (cost=0.00..431.04 rows=1667 width=4)
-> Hash (cost=1297.85..1297.85 rows=67 width=4)
-> Hash Join (cost=0.00..1297.85 rows=67 width=4)
Hash Cond: (b.id = a.id)
-> Seq Scan on m173_b b (cost=0.00..431.15 rows=6667 width=4)
-> Hash (cost=865.46..865.46 rows=67 width=4)
-> Hash Join (cost=0.00..865.46 rows=67 width=4)
Hash Cond: (a.id = e.id)
-> Seq Scan on m173_a a (cost=0.00..431.38 rows=16667 width=4)
-> Hash (cost=431.00..431.00 rows=67 width=4)
-> Seq Scan on m173_e e (cost=0.00..431.00 rows=67 width=4)
optimizer_enable_associativity is off by default on this cluster. Switching it on for the same 5-way join under exhaustive shows what it costs — and that CXformJoinAssociativity is one of the few rules where bindings exceed calls (§17.3.3). Single runs; stage timings jitter by some tens of milliseconds between runs.
SET optimizer_join_order='exhaustive';
SET optimizer_enable_associativity=off; -- default; then on
EXPLAIN SELECT count(*) FROM m173_a a, m173_b b, m173_c c, m173_d d, m173_e e
WHERE a.id=b.id AND b.id=c.id AND c.id=d.id AND d.id=e.id;
--------------------------- optimizer_enable_associativity = off (default)
[OPT]: Memo (stage 0): [66 groups, 3 duplicate groups, 221 group expressions, 9 activated xforms]
[OPT]: stage 0 completed in 384ms, plan with cost 2160.294305 was found
CXformInnerJoinCommutativity: 30 calls, 30 total bindings, 30 alternatives generated, 0ms
CXformImplementInnerJoin: 44 calls, 44 total bindings, 44 alternatives generated, 0ms
--------------------------- optimizer_enable_associativity = on
[OPT]: Memo (stage 0): [106 groups, 5 duplicate groups, 501 group expressions, 10 activated xforms]
[OPT]: stage 0 completed in 1107ms, plan with cost 2160.294305 was found
CXformInnerJoinCommutativity: 77 calls, 77 total bindings, 77 alternatives generated, 0ms
CXformJoinAssociativity: 59 calls, 69 total bindings, 59 alternatives generated, 0ms
CXformImplementInnerJoin: 136 calls, 136 total bindings, 136 alternatives generated, 0ms
Together those two runs are the section’s real lesson, and it is not in the cost column. In query mode one rule fires once, the join is built exactly as written, and the very first join already carries an estimated 6667 rows per segment; in exhaustive2, DPv2 proposes ten orders, commutativity mirrors twenty-six of the resulting joins, ImplementInnerJoin is called fifty-two times instead of four — and the plan now starts from the 200-row table, so the first join carries 67 rows. That cost 3.2× the group expressions and 6.6× the stage time to buy a 0.08% cost improvement, because on a five-table chain over uniform toy data ORCA’s estimate is dominated by the five scans. Associativity is the same story taken one step further: one extra rule turns 221 group expressions into 501 and 384 ms into 1107 ms, and the winning plan is bit-for-bit the same cost, because CXformJoinAssociativity mostly re-derives orders DP and DPv2 already reach by construction and the memo’s duplicate detection (§17.2) absorbs the surplus. That is why it ships off. In a Cascades optimizer “add a rule” is never free — the rule set is the search space — which is also why two hard limits bound the damage on wide joins: optimizer_join_order_threshold (10) is the point past which DPv2 stops doing full DP per level and keeps a single group per level (CJoinOrderDPv2.cpp:1539), and optimizer_join_arity_for_associativity_commutativity (18) makes preprocessing switch commutativity and associativity off outright for joins wider than that (CExpressionPreprocessor.cpp:965).
17.3.6 Subquery decorrelation, done with rules
The other headline family is decorrelation, and here the rule-driven design shows its leverage most clearly. §15.2 described the PostgreSQL planner’s approach: two hand-written recursive passes, pull_up_sublinks and pull_up_subqueries, that rewrite the parse tree in place before planning proper begins, and that give up on anything they do not have a case for. ORCA reaches the same goal through the ordinary rule machinery, in three stages, each stage its own family of rules. First a simplify rule tries to hoist the subquery out of the scalar expression (CXformSimplifySelectWithSubquery, CXformSimplifyProjectWithSubquery). Then an Apply rule replaces the subquery with a CLogicalApply variant — ORCA’s explicit correlated-join operator — by calling the shared helper CSubqueryHandler (libgpopt/include/gpopt/xforms/CSubqueryHandler.h:32, “helper class for transforming subquery expressions to Apply expressions”) from CXformSubqueryUnnest::PexprSubqueryUnnest (libgpopt/src/xforms/CXformSubqueryUnnest.cpp:84); CXformSelect2Apply, CXformProject2Apply, CXformGbAgg2Apply and CXformSubqJoin2Apply are all thin subclasses of it. Finally a de-Apply rule turns the Apply into a real join once the correlation has been analysed: CXformLeftSemiApply2LeftSemiJoin, CXformInnerApply2InnerJoin, CXformLeftOuterApply2LeftOuterJoin, and the ...NoCorrelations variants for the easy cases. Only if none of those apply does an ExfImplement...CorrelatedApply rule keep the correlated form and let the executor re-run the inner side per outer row.
A correlated EXISTS decorrelated into a Hash Semi Join. The three-stage chain is visible in the fired-rules list; 21 rules were activated for a two-table query.
SET client_min_messages=log;
SET optimizer_print_optimization_stats=on;
EXPLAIN SELECT count(*) FROM m173_a a
WHERE EXISTS (SELECT 1 FROM m173_b b WHERE b.id = a.id AND b.y = 3);
[OPT]: Memo (stage 0): [96 groups, 0 duplicate groups, 196 group expressions, 21 activated xforms]
[OPT]: <Begin Xforms - stage 0>
...
CXformSimplifySelectWithSubquery: 1 calls, 1 total bindings, 3 alternatives generated, 0ms
CXformSelect2Apply: 3 calls, 3 total bindings, 6 alternatives generated, 0ms
CXformLeftOuterApply2LeftOuterJoin: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
CXformImplementLeftOuterCorrelatedApply: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
CXformLeftSemiApply2LeftSemiJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformLeftSemiJoin2NLJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformLeftSemiJoin2HashJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformLeftSemiJoin2InnerJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
...
[OPT]: <End Xforms - stage 0>
-> Hash Semi Join (cost=0.00..866.50 rows=606 width=1)
Hash Cond: (a.id = b.id)
-> Seq Scan on m173_a a (cost=0.00..432.06 rows=16667 width=4)
Filter: (NOT (id IS NULL))
-> Hash (cost=431.38..431.38 rows=606 width=4)
-> Seq Scan on m173_b b (cost=0.00..431.38 rows=606 width=4)
Filter: (y = 3)
Optimizer: GPORCA
The harder case: a correlated scalar subquery in the target list. ORCA decorrelates it into a Hash Left Join over a pre-aggregated inner side; the PostgreSQL planner leaves a SubPlan that is re-executed per outer row over a broadcast copy of the inner table. The two cost numbers are on different scales and are not comparable — the plan shapes are.
EXPLAIN SELECT a.id, (SELECT max(b.y) FROM m173_b b WHERE b.id = a.id)
FROM m173_a a WHERE a.x = 3; -- default: optimizer=on
SET optimizer=off; -- same query, PostgreSQL planner
--------------------------- Optimizer: GPORCA
CXformSimplifyProjectWithSubquery: 1 calls, 1 total bindings, 3 alternatives generated, 0ms
CXformProject2Apply: 1 calls, 1 total bindings, 2 alternatives generated, 0ms
CXformLeftOuterApply2LeftOuterJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformLeftOuterJoin2HashJoin: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
Gather Motion 3:1 (slice1; segments: 3) (cost=0.00..866.70 rows=7135 width=8)
-> Hash Left Join (cost=0.00..866.47 rows=4001 width=8)
Hash Cond: (a.id = b.id)
-> Seq Scan on m173_a a (cost=0.00..431.97 rows=2379 width=4)
Filter: (x = 3)
-> Hash (cost=432.09..432.09 rows=6667 width=8)
-> HashAggregate (cost=0.00..432.09 rows=6667 width=8)
Group Key: b.id
-> Seq Scan on m173_b b (cost=0.00..431.15 rows=6667 width=8)
Optimizer: GPORCA
--------------------------- Optimizer: Postgres query optimizer
Gather Motion 3:1 (slice1; segments: 3) (cost=0.00..1644567.38 rows=7135 width=8)
-> Seq Scan on m173_a a (cost=0.00..1644472.25 rows=2378 width=8)
Filter: (x = 3)
SubPlan 1
-> Aggregate (cost=691.33..691.34 rows=1 width=4)
-> Result (cost=0.00..641.33 rows=20000 width=4)
Filter: (b.id = a.id)
-> Materialize (cost=0.00..441.33 rows=20000 width=8)
-> Broadcast Motion 3:3 (slice2; segments: 3) (cost=0.00..341.33 rows=20000 width=8)
-> Seq Scan on m173_b b (cost=0.00..74.67 rows=6667 width=8)
Optimizer: Postgres query optimizer
Ordering matters between the two headline families: decorrelation must finish before join enumeration can start.
CXformUtils::ExfpExpandJoinOrder(libgpopt/src/xforms/CXformUtils.cpp:143) returnsExfpNone— “subqueries must be unnested before applying xform” — if any child of the n-ary join still derives a subquery. There is no decorrelation phase in the engine to express that ordering; it is stated by the rules themselves, in their promise functions. That is the Cascades bargain: no pass order to maintain, but every rule must know when to stand down.
17.3.7 Turning a single rule off
Because the enabled rule set is a bitset over rule ids, the most precise debugging tool in ORCA is switching off exactly one rule. Two SQL functions do it: disable_xform(text) and enable_xform(text) (src/include/catalog/pg_proc.dat:12625/:12628, C implementations DisableXform/EnableXform at src/backend/gpopt/utils/funcs.cpp:44/:76). Both look the name up in the factory’s name map and set a flag in the backend-global optimizer_xforms[] array — COptTasks::SetXform (src/backend/gpopt/utils/COptTasks.cpp:1204) is four lines long. On the next optimization the GUC-to-traceflag bridge walks that array and sets one disable bit per flagged rule, at EopttraceDisableXformBase + id (the macro is CXform.h:28; §17.6 covers the bridge as a whole). CGroupExpression::Transform then checks GPOPT_FDISABLED_XFORM before it does anything else — before the promise, before binding — and returns immediately (CGroupExpression.cpp:781). One array entry, one bit, one early return: that is the entire mechanism.
Switching off one rule that we watched fire in §17.3.6. The functions return a text confirmation and take effect for the rest of the session (the array is per backend, not a GUC — a new connection starts clean, and RESET ALL will not undo it).
SELECT disable_xform('CXformLeftSemiJoin2HashJoin');
EXPLAIN SELECT count(*) FROM m173_a a
WHERE EXISTS (SELECT 1 FROM m173_b b WHERE b.id = a.id AND b.y = 3);
SELECT disable_xform('CXformNoSuchRule');
SELECT enable_xform('CXformLeftSemiJoin2HashJoin');
disable_xform
-----------------------------------------
CXformLeftSemiJoin2HashJoin is disabled
-> Hash Join (cost=0.00..866.57 rows=606 width=1)
Hash Cond: (a.id = b.id)
-> Seq Scan on m173_a a (cost=0.00..432.06 rows=16667 width=4)
Filter: (NOT (id IS NULL))
-> Hash (cost=431.46..431.46 rows=606 width=4)
-> HashAggregate (cost=0.00..431.46 rows=606 width=4)
Group Key: b.id
-> Seq Scan on m173_b b (cost=0.00..431.38 rows=606 width=4)
Filter: (y = 3)
Optimizer: GPORCA
disable_xform
------------------------------------
CXformNoSuchRule is not recognized
enable_xform
----------------------------------------
CXformLeftSemiJoin2HashJoin is enabled
The result is more interesting than a simple loss of a plan. Deprived of the semi-join-to-hash-join rule, ORCA does not fall back to a nested loop and it does not fail: it reaches a plan by a different route through the rule set, using CXformLeftSemiJoin2InnerJoin — which fired in §17.3.6’s list too, and produced an alternative that lost on cost — to rewrite the semi join into a de-duplicating HashAggregate on b.id followed by an ordinary hash join, at a cost of 866.57 against the semi join’s 866.50. The rule set is a lattice, not a pipeline; that redundancy is what makes an unfamiliar plan diagnosable one rule at a time. Note also the shape of the experiment: disable_xform is a diagnostic, not a plan hint. It says “show me the best plan reachable without this rewrite”, and the honest use of it is to find out which rewrite is responsible for a plan you did not expect — then fix the statistics, the distribution or the query, rather than shipping the switch.
More in Query Planning and Execution
- From SQL to Segments: Cloudberry Query Processing
- Statistics and Selectivity Estimation in Cloudberry
- The Postgres Planner in Cloudberry, Step by Step
- Distributed Planning: Locus, Motion and Direct Dispatch
- ORCA Optimizer: Entry Points and Fallback Rules
- Inside ORCA's Cascades Engine: Groups and Jobs