Inside ORCA's Cascades Engine: Groups and Jobs

ORCA is a Cascades optimizer, which means it works nothing like the Postgres planner. This chapter explains the engine on its own terms.

PostgreSQL’s planner searches bottom-up over paths: for every RelOptInfo it builds concrete Path nodes and lets add_path throw away the dominated ones (§15.1, §15.3). ORCA searches top-down over a memo. A memo is a set of numbered groups; each group is an equivalence class of expressions that all compute the same logical result, and each member of a group is a group expression — an operator plus a list of child group ids rather than child expressions. Because children are groups, one group expression stands for an entire family of subplans, and a memo of a few dozen entries can encode thousands of plans. Nothing is ever assembled into a plan tree during the search; the winner is reconstructed from the memo at the very end.

The search is driven by required properties flowing down (output columns, sort order, distribution, rewindability, partition propagation) and derived properties flowing back up. When a physical operator cannot deliver what was required, the engine does not reject it — it stacks an enforcer on top: a CPhysicalMotion… for distribution, a CPhysicalSort for order. That single sentence is the deepest difference from Chapters 15–16: where cdbpath_create_motion_path (§16.2) is called by the distributed planner when it notices a locus mismatch, ORCA’s Motion simply appears in the group as one more costed alternative. The whole engine lives in src/backend/gporca/libgpopt/src/engine/CEngine.cpp (2407 lines) plus libgpopt/src/search/; CMemo’s own class comment calls it what it is — a Dynamic programming table (libgpopt/include/gpopt/search/CMemo.h:41).

Prefix / suffix	What it means, with real examples
P…	Returns or holds a pointer. Pexpr = CExpression *, Pgexpr = CGroupExpression *, Pgroup = CGroup *, Poc = COptimizationContext *, Pcc = CCostContext *, Prpp = CReqdPropPlan *, Pdp = CDrvdProp *, Pop = COperator *, Pss = CSearchStage *, Pdxln = CDXLNode * (§17.5).
F…	Returns a BOOL: FSafeToPrune, FSearchTerminated, FScalar, FExplored, FCheckEnfdProps.
Ul… / Ull…	A ULONG / ULLONG count: UlpGroups, UlGrpExprs, UllCount, ulJobs, ulSearchStages.
Os…	Prints to an ostream: OsPrint, OsPrintMemoryConsumption. Every memo dump in this section is an OsPrint.
Pdrgp…	A dynamic array of pointers: pdrgpexpr (expressions), pdrgpoc (child optimization contexts), pdrgpgroup (child groups).
Exf… / Eop… / Eol… / Est… / Epet…	Enum members: xform id (ExfExpandNAryJoinDPv2, ExfInvalid), operator id, optimization level (EolHigh), state (estExplored), property-enforcing type (EpetRequired).
m_…	A member field: m_pmemo, m_pqc, m_search_stage_array, m_eol, m_estate.

17.2.1 Reading a real memo

The whole memo for a two-table self-join, printed by the optimizer itself. This build is --enable-cassert, so GPOS_DEBUG is defined (pg_config.h) and ORCA’s developer print traceflags actually emit — they are this chapter’s main instrument.

CREATE TABLE m172_t(a int);   -- distributed by a
INSERT INTO m172_t SELECT g FROM generate_series(1,1000) g;
ANALYZE m172_t;

SET client_min_messages=log;
SET optimizer_print_memo_after_optimization=on;
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

LOG:  2026-08-14 00:28:26:507616 CST,THD000,TRACE,"MEMO after optimization (stage 0):
",
2026-08-14 00:28:26:507954 CST,THD000,TRACE,"
ROOT
Group 5 (#GExprs: 6):
  0: CLogicalNAryJoin [ 0 1 4 ]
  1: CLogicalInnerJoin [ 0 1 4 ]
  2: CLogicalInnerJoin [ 1 0 4 ]
  3: CPhysicalInnerHashJoin (High) [ 1 0 4 ]
  4: CPhysicalInnerHashJoin (High) [ 0 1 4 ]
  5: CPhysicalMotionGather(master) [ 5 ]

Group 4 ():
  0: CScalarCmp (=) [ 2 3 ]
Group 3 ():
  0: CScalarIdent "a" (9,Used) [ ]
Group 2 ():
  0: CScalarIdent "a" (0,Used) [ ]

Group 1 (#GExprs: 4):
  0: CLogicalGet "t2" ("t2"), Columns: ["a" (9,Used), … ] Key sets: {[1,7]} [ ]
  1: CPhysicalTableScan "t2" ("t2"), Columns: [ … ] [ ]
  2: CPhysicalMotionGather(master) [ 1 ]
  3: CPhysicalMotionBroadcast  [ 1 ]

Group 0 (#GExprs: 4):
  0: CLogicalGet "t1" ("t1"), Columns: ["a" (0,Used), … ] Key sets: {[1,7]} [ ]
  1: CPhysicalTableScan "t1" ("t1"), Columns: [ … ] [ ]
  2: CPhysicalMotionGather(master) [ 0 ]
  3: CPhysicalMotionBroadcast  [ 0 ]
",
                                   QUERY PLAN
 Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..862.18 rows=1000 width=8)
   ->  Hash Join  (cost=0.00..862.15 rows=334 width=8)
         Hash Cond: (t1.a = t2.a)
         ->  Seq Scan on m172_t t1  (cost=0.00..431.01 rows=334 width=4)
         ->  Hash  (cost=431.01..431.01 rows=334 width=4)
               ->  Seq Scan on m172_t t2  (cost=0.00..431.01 rows=334 width=4)
 Optimizer: GPORCA

Read it from the ROOT label down. Group 5 (#GExprs: 6) is the root equivalence class and it holds six group expressions, numbered within the group. The bracketed list after each operator is child group ids, in operator order: CPhysicalInnerHashJoin (High) [ 0 1 4 ] means outer = Group 0, inner = Group 1, scalar predicate = Group 4. Groups 2, 3 and 4 print with an empty () instead of a #GExprs count — they are scalar groups, hold exactly one expression, are never costed, and their child links are what wire CScalarIdent "a" (0) back to the CLogicalGet that produced column 0 (compare README.memo.md, which walks the same shape by hand). (High) is the EOptimizationLevel from libgpopt/include/gpopt/search/CGroup.h:57: CGroupExpression::SetOptimizationLevel (libgpopt/src/search/CGroupExpression.cpp:177) promotes hash joins and hash aggregates to EolHigh so they are optimized before their rivals and establish a cheap cost bound early.

Now look at what shares Group 5. CLogicalNAryJoin, two CLogicalInnerJoins with swapped children, two CPhysicalInnerHashJoins and a CPhysicalMotionGather(master) all sit in one group, because they are all logically the same relation. There is no separate “path list” and no separate “plan tree”: logical alternatives, physical implementations and enforcers are interleaved in the same container, distinguished only by their operator class. And in Groups 0 and 1 — the two scans — the physical alternatives are CPhysicalTableScan, CPhysicalMotionGather(master) and CPhysicalMotionBroadcast. A Motion is a memo entry. In §16.2 the distributed planner inserted a MotionPath when it saw a locus mismatch; here ORCA merely records that a broadcast of Group 0 is another way to be Group 0, prices it, and lets the search decide. Entry 5 of Group 5 makes the trick explicit: the Gather’s only child is [ 5 ] — Group 5 itself.

The one-line tell that you are looking at ORCA at all is the EXPLAIN footer: Optimizer: GPORCA. Chapters 15 and 16 ran every demo under SET optimizer=off and got Optimizer: Postgres query optimizer; this chapter runs at the cluster default, which is on. §17.1 covers how control reaches ORCA and how it falls back.

17.2.2 Memo mechanics: groups, group expressions, hashing

Three classes carry the structure. CGroup (libgpopt/src/search/CGroup.cpp, 2163 lines) is the “group of equivalent expressions in the Memo structure”: an id, a state, derived relational properties, statistics, its list of group expressions, and its map of optimization contexts. CGroupExpression (1232 lines) is a COperator *m_pop plus CGroupArray *m_pdrgpgroup, and it also remembers which xform made it (m_exfidOrigin) and a partial-plan cost map used for pruning (libgpopt/include/gpopt/search/CGroupExpression.h:95–:125). CGroupProxy is a scoped accessor — its class comment is simply “Exclusive access to a given group” (CGroupProxy.h:33) — and every mutation of a group in the engine happens inside a { CGroupProxy gp(pgroup); … } block, which is why the code reads as a sequence of tiny braced scopes.

src/backend/gporca/libgpopt/src/search/CMemo.cpp:168

	ShtAcc shta(m_sht, *pgexpr);

	// we do a lookup since group expression may have been already inserted
	CGroupExpression *pgexprFound = shta.Find();
	if (nullptr == pgexprFound)
	{
		shta.Insert(pgexpr);
		// group proxy scope: gp.Insert(pgexpr), then Add() if this is a new group
		…
		return pgexpr->Pgroup();
	}

	return pgexprFound->Pgroup();

That is the heart of the memo: one hash table of all group expressions, m_sht. Insertion is a lookup; if the expression is already there, insertion “fails” and the caller is handed back the group that already contains it. CEngine::PgroupInsert (CEngine.cpp:293) inserts children first and then the parent, so an xform result that rediscovers a known subtree costs nothing but hashes. And the hash is cheap precisely because children are groups:

src/backend/gporca/libgpopt/src/search/CGroupExpression.cpp:948

	ULONG ulHash = pop->HashValue();

	ULONG arity = pdrgpgroup->Size();
	for (ULONG i = 0; i < arity; i++)
	{
		ulHash = CombineHashes(ulHash, (*pdrgpgroup)[i]->HashValue());
	}

Hashing an operator plus its child group ids is O(arity), not O(subtree). “Logically equivalent” therefore becomes a hash-table hit rather than a tree comparison — the property that makes Cascades affordable. Two groups can still turn out to be duplicates after the fact: CEngine::InsertXformResult (CEngine.cpp:355) notices when an xform result lands in a group other than the origin group, checks FPossibleDuplicateGroups (:405, which today compares output columns only), and calls CMemo::MarkDuplicates (CMemo.cpp:445). The bookkeeping is settled once, at the end of exploration, by CMemo::GroupMerge (:567), which keeps merging and re-hashing (FRehash, :478) until no new duplicates appear — and re-points the root if the root itself was merged away.

optimizer_print_optimization_stats reports the memo the engine actually built, plus which transformations fired. Six groups, seventeen group expressions — that is the entire search space for this join.

SET client_min_messages=log;
SET optimizer_print_optimization_stats=on;
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

LOG:  2026-08-14 00:29:19:430966 CST,THD000,TRACE,"timer:
[OPT]: Group Merge Time: 0ms",
2026-08-14 00:29:19:434291 CST,THD000,TRACE,"timer:
[OPT]: Statistics Derivation Time (stage 0) : 3ms",
…
2026-08-14 00:29:19:437005 CST,THD000,TRACE,"
[OPT]: Memo (stage 0): [6 groups, 0 duplicate groups, 17 group expressions, 4 activated xforms]
[OPT]: stage 0 completed in 12ms,  plan with cost 862.180385 was found
[OPT]: <Begin Xforms - stage 0>
CXformGet2TableScan: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
CXformInnerJoinCommutativity: 1 calls, 1 total bindings, 1 alternatives generated, 0ms
CXformExpandNAryJoinDPv2: 1 calls, 1 total bindings, 3 alternatives generated, 5ms
CXformImplementInnerJoin: 2 calls, 2 total bindings, 2 alternatives generated, 0ms
[OPT]: <End Xforms - stage 0>
",
2026-08-14 00:29:19:437027 CST,THD000,TRACE,"[OPT]: Search terminated at stage 1/1",

17.2.3 Three phases: exploration, implementation, optimization

Every group walks the same state ladder — estUnexplored, estExploring, estExplored, estImplementing, estImplemented, estOptimizing, estOptimized (CGroup.h:82). Exploration applies only logical xforms and grows the logical alternatives; implementation applies only implementation xforms and turns logical operators into physical ones; optimization costs the physical alternatives under required properties and adds enforcers. The phase is selected by intersecting three xform sets — the phase’s set, the operator’s candidate set, and the current search stage’s set (CEngine.cpp:785–:798): PxfsExploration() or PxfsImplementation(), then CLogical::PxfsCandidates, then PxfsCurrentStage(). Between phases, FinalizeExploration (:1444) runs GroupMerge and derives statistics for every group, and FinalizeImplementation (:1493) exists mainly to print. Which transformations live in which set is §17.3’s subject.

The same query with one print traceflag each, in three sessions. Group 5 grows 3 → 5 → 6 entries and Group 0 grows 1 → 2 → 4; the Motions show up only in the last dump.

-- three separate sessions, one traceflag each, same query
SET optimizer_print_memo_after_exploration=on;    -- (1)
SET optimizer_print_memo_after_implementation=on; -- (2)
SET optimizer_print_memo_after_optimization=on;   -- (3)
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

(1) MEMO after exploration (stage 0)
ROOT
Group 5 (#GExprs: 3):
  0: CLogicalNAryJoin [ 0 1 4 ]
  1: CLogicalInnerJoin [ 0 1 4 ]
  2: CLogicalInnerJoin [ 1 0 4 ]
…
Group 0 (#GExprs: 1):
  0: CLogicalGet "t1" ("t1"), … [ ]

(2) MEMO after implementation (stage 0)
Group 5 (#GExprs: 5):
  …
  3: CPhysicalInnerHashJoin (High) [ 1 0 4 ]
  4: CPhysicalInnerHashJoin (High) [ 0 1 4 ]
…
Group 0 (#GExprs: 2):
  0: CLogicalGet "t1" ("t1"), … [ ]
  1: CPhysicalTableScan "t1" ("t1"), … [ ]

(3) MEMO after optimization (stage 0):
Group 5 (#GExprs: 6):
  …
  5: CPhysicalMotionGather(master) [ 5 ]
…
Group 0 (#GExprs: 4):
  0: CLogicalGet "t1" ("t1"), … [ ]
  1: CPhysicalTableScan "t1" ("t1"), … [ ]
  2: CPhysicalMotionGather(master) [ 0 ]
  3: CPhysicalMotionBroadcast  [ 0 ]

This is the cleanest possible proof that Motion is not an implementation rule. After implementation, Group 0 knows only how to scan t1; the Gather and the Broadcast appear during optimization, and CEngine::AddEnforcers (CEngine.cpp:217) inserts them with CXform::ExfInvalid as their origin xform — they were produced by no transformation at all, but by a required property that the scan could not satisfy. The engine also keeps a debuggable non-scheduler path for exactly this walk: CEngine::Explore (:1242), Implement (:1264) and RecursiveOptimize (:1286) run the three phases as plain recursion over TransitionGroup/TransitionGroupExpression (:814/:753). The whole block CEngine.cpp:704–:1378 is compiled only under GPOS_DEBUG, so it exists on this assert-enabled build and not in a release one.

17.2.4 Jobs and the scheduler

In production ORCA does not recurse. CEngine::Optimize sizes a job pool from the memo, then runs a queue:

src/backend/gporca/libgpopt/src/engine/CEngine.cpp:1682

	const ULONG ulJobs =
		std::min((ULONG) GPOPT_JOBS_CAP,
				 (ULONG)(m_pmemo->UlpGroups() * GPOPT_JOBS_PER_GROUP));
	CJobFactory jf(m_mp, ulJobs);
	CScheduler sched(m_mp, ulJobs);

	CSchedulerContext sc;
	sc.Init(m_mp, &jf, &sched, this);

	const ULONG ulSearchStages = m_search_stage_array->Size();
	for (ULONG ul = 0; !FSearchTerminated() && ul < ulSearchStages; ul++)
	{
		… ScheduleMainJob(&sc, poc); CScheduler::Run(&sc); …

GPOPT_JOBS_CAP is 5000 and GPOPT_JOBS_PER_GROUP is 20 (CEngine.cpp:59–:61), so the pre-allocation is min(5000, groups × 20) — a pure memory-pool sizing hint, not a limit on work done. CJobFactory hands out jobs from per-type object pools (CJobFactory.cpp:82) and CScheduler::ExecuteJobs (CScheduler.cpp:108) is a flat loop: retrieve a job, execute it, and classify the result as EjrCompleted, EjrRunnable or EjrSuspended. The suspension is where the recursion went. A job that needs its children optimized first schedules child jobs and suspends (CScheduler::Add, :181; Suspend, :433); when the last child completes, ResumeParent (:526) puts it back on the queue. Job dependencies are the call stack, made explicit — and this decomposition into one job per group, per group expression and per transformation is exactly Cascades’ “tasks” design.

Job class	What one instance does
CJobGroupExploration / …Implementation / …Optimization	Drive one group to estExplored / estImplemented / optimized-under-a-context. The exploration and implementation jobs are what call FinalizeExploration / FinalizeImplementation on the root group (CJobGroupExploration.cpp:229, CJobGroupImplementation.cpp:251).
CJobGroupExpressionExploration / …Implementation	Drive one group expression: first transition its child groups, then schedule a transformation job per applicable xform.
CJobGroupExpressionOptimization	The big one (807 lines). Per group expression and optimization context: compute child requirements, optimize children, add enforcers, cost itself.
CJobTransformation	Apply exactly one xform to exactly one group expression and insert the results (CEngine::InsertXformResult).
CJobQueue	Lets several jobs wait on one shared piece of work instead of duplicating it — the same group is never explored twice concurrently.

17.2.5 Required properties, enforcers and optimization contexts

An optimization context is a (group, required-plan-properties) pair, and it is the unit the search actually optimizes. CEngine::Optimize builds the root one directly from the query context’s Prpp() — the properties the query as a whole must deliver, which on a coordinator means SINGLETON (master). Each CJobGroupExpressionOptimization then derives child requirements and recursively asks the child groups for a plan under those. A group therefore accumulates several contexts, and remembers the best group expression for each one. Turn on optimizer_print_optimization_context and the memo dump grows a Grp OptCtxts section that spells this out:

Group 0 — the scan of t1 — was asked for seven different property requirements. Two of them can only be met by stacking a Motion on top of the scan.

SET client_min_messages=log;
SET optimizer_print_memo_after_optimization=on;
SET optimizer_print_optimization_context=on;
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

Group 0 (#GExprs: 4):
  0: CLogicalGet "t1" ("t1"), … [ ]
  1: CPhysicalTableScan "t1" ("t1"), … [ ]
    Cost Ctxts:
      main ctxt (stage 0)3.0, child ctxts:[], rows:1000.000000 (group), cost: 431.006967
      …
  2: CPhysicalMotionGather(master) [ 0 ]
    Cost Ctxts:
      main ctxt (stage 0)0.0, child ctxts:[1], rows:1000.000000 (group), cost: 431.024353
  3: CPhysicalMotionBroadcast  [ 0 ]
    Cost Ctxts:
      main ctxt (stage 0)5.0, child ctxts:[1], rows:1000.000000 (group), cost: 431.081047
  Grp OptCtxts:
    0 (stage 0): (… req order: [<empty> match: satisfy ], req dist: [SINGLETON (master) match: exact], …) => Best Expr:2
    1 (stage 0): (… req dist: [ANY  EOperatorId: 133  match: satisfy], …) => Best Expr:1
    2 (stage 0): (… req dist: [NON-SINGLETON  match: satisfy], …) => Best Expr:1
    3 (stage 0): (… req dist: [HASHED: [ CScalarIdent "a" (0,Used), nulls colocated ], opfamilies: (0.1977.1.0), match: exact], …) => Best Expr:1
    4 (stage 0): (… req dist: [SINGLETON (master) match: satisfy], …) => Best Expr:2
    5 (stage 0): (… req dist: [REPLICATED match: satisfy], …) => Best Expr:3
    6 (stage 0): (… req dist: [HASHED: … match: satisfy], …) => Best Expr:1

The decision is made by CEngine::FCheckEnfdProps (CEngine.cpp:2048), called from the optimization job’s EevtAddEnforcers state (CJobGroupExpressionOptimization.cpp:568). For each enforceable property — order, distribution, rewindability, partition propagation — it asks the physical operator to classify the requirement as EpetRequired (the operator cannot deliver it: stack an enforcer), EpetOptional (pass the requirement to the children and preserve it), EpetUnnecessary (already delivered) or EpetProhibited (libgpopt/include/gpopt/base/CEnfdProp.h:67, whose comment documents all four with examples). One EpetProhibited vetoes all enforcers for that expression and context. Then AppendEnforcers builds the enforcer expressions and AddEnforcers drops them into the group. Note what the header comment stresses: once inserted, the enforcer has no tie to the operator that motivated it — during costing the Gather may well pick a different group expression as its child, because everything in a group is equivalent. This is ORCA’s answer to §16.1’s CdbPathLocus: the same idea — a relation’s distribution is a property that must be requested, delivered or repaired — implemented as a required/derived property pair in a search engine rather than as a field on a Path.

17.2.6 Search stages, termination and cost-based pruning

The for loop in CEngine::Optimize iterates over a CSearchStageArray. A stage is a triple: a set of xforms, a time threshold and a cost threshold (CSearchStage.cpp:29). The default strategy — CSearchStage::PdrgpssDefault (:120) — is a single stage containing every exploration xform, with no thresholds, which is why the stats above read Search terminated at stage 1/1. A non-default strategy is loaded from a DXL file named by optimizer_search_strategy_path (COptTasks::LoadSearchStrategy, src/backend/gpopt/utils/COptTasks.cpp:341, called at :924); the repository ships examples under src/backend/gporca/data/dxl/search/. Between stages the state is reset (FinalizeSearchStage, CEngine.cpp:1526) but the memo is kept, and the loop condition !FSearchTerminated() (CEngine.h:161) means only one thing: stop as soon as some completed stage found a plan at or below its cost threshold (CSearchStage::FAchievedReqdCost, CSearchStage.h:102). A stage that runs out of time simply stops applying xforms (FTimedOut, :85) and lets the next one try.

A two-stage strategy whose first stage has a generous cost threshold. Stage 0 finds a plan below it, so stage 1 is never entered — and the stage’s restricted xform set left only 14 group expressions in the memo instead of 17.

-- /tmp/cbdb-two-stage.xml declares two dxl:SearchStage elements,
-- the first with TimeThreshold=1000 CostThreshold=10E6
SET client_min_messages=log;
SET optimizer_print_optimization_stats=on;
SET optimizer_search_strategy_path='/tmp/cbdb-two-stage.xml';
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

LOG:  … TRACE,"
[OPT]: Memo (stage 0): [6 groups, 0 duplicate groups, 14 group expressions, 3 activated xforms]
[OPT]: stage 0 completed in 5ms,  plan with cost 862.180385 was found
…
",
2026-08-14 00:35:48:950477 CST,THD000,TRACE,"[OPT]: Search terminated at stage 1/2",
 Optimizer: GPORCA

src/backend/gporca/libgpopt/src/engine/CEngine.cpp:646

	// check if container group has a plan for given properties
	CGroup *pgroup = pgexpr->Pgroup();
	COptimizationContext *pocGroup =
		pgroup->PocLookupBest(m_mp, UlSearchStages(), prpp);
	if (nullptr != pocGroup && nullptr != pocGroup->PccBest())
	{
		CCost costLowerBound =
			pgexpr->CostLowerBound(m_mp, prpp, pccChild, child_index);
		*pcostLowerBound = costLowerBound;
		if (costLowerBound > pocGroup->PccBest()->Cost())
		{
			// group expression cannot deliver a better plan … can be safely pruned
			return true;

Branch-and-bound in the memo. Two index nested-loop joins are abandoned on a lower bound of 65.0, because the group already holds a hash join costed at 12.0 — their subtrees are never optimized at all.

CREATE INDEX m172_t_a_idx ON m172_t(a);
SET optimizer_print_memo_after_optimization=on;
SET optimizer_print_optimization_context=on;
EXPLAIN SELECT * FROM m172_t t1, m172_t t2 WHERE t1.a=t2.a AND t1.a < 10;

ROOT
Group 10 (#GExprs: 14):
  …
  7: CPhysicalInnerIndexNLJoin [ 8 18 14 ]
    Cost Ctxts:
      main ctxt (stage 0)0.3, cost lower bound: 65.002316   PRUNED
      main ctxt (stage 0)1.3, cost lower bound: 65.002130   PRUNED
  8: CPhysicalInnerIndexNLJoin [ 8 17 14 ]
    Cost Ctxts:
      main ctxt (stage 0)0.3, cost lower bound: 65.002315   PRUNED
      main ctxt (stage 0)1.3, cost lower bound: 65.002129   PRUNED
  9: CPhysicalInnerHashJoin (High) [ 8 4 9 ]
    Cost Ctxts:
      main ctxt (stage 0)0.3, child ctxts:[4, 4], rows:10.000000 (group), cost: 12.006325
      main ctxt (stage 0)1.0, child ctxts:[6, 6], rows:10.000000 (group), cost: 12.003394
  …
  13: CPhysicalMotionGather(master) [ 10 ]
  Grp OptCtxts:
    0 (stage 0): (… req dist: [SINGLETON (master) match: satisfy], …) => Best Expr:13

FSafeToPrune is the Cascades counterpart of add_path’s dominance test (§15.3) — but it is strictly stronger in one respect and weaker in another. add_path compares two fully built paths on cost and pathkeys and discards the loser; the work of building the loser is already spent. FSafeToPrune compares a lower bound on a plan that was never built against the group’s current best for the same required properties, and when the bound loses, the entire subtree below that group expression is never optimized. That is why the (High) optimization level matters: getting a hash join costed first gives the bound something to beat. Pruning can be switched off (optimizer_enable_space_pruning, mapped to the EopttraceEnableSpacePruning traceflag — the GUC-to-traceflag bridge is §17.6), and it is deliberately disabled for partitioned plans whose statistics depend on dynamic partition elimination (FSafeToPruneWithDPEStats, CEngine.cpp:573), since a cost bound there would not be trustworthy.

17.2.7 Extraction, and the size of the plan space

Nothing in the memo is a plan. At the end of each stage CMemo::PexprExtractPlan walks the memo once and builds one:

src/backend/gporca/libgpopt/src/search/CMemo.cpp:322

	poc = pgroupRoot->PocLookupBest(mp, ulSearchStages, prppInput);
	pgexprBest = pgroupRoot->PgexprBest(poc);
	…
	ULONG arity = pgexprBest->Arity();
	for (ULONG i = 0; i < arity; i++)
	{
		CGroup *pgroupChild = (*pgexprBest)[i];
		COptimizationContext *pocChild = (*poc->PccBest()->Pdrgpoc())[i];
		CExpression *pexprChild = PexprExtractPlan(
			mp, pgroupChild, pocChild->Prpp(), ulSearchStages);
		pdrgpexpr->Append(pexprChild);
	}

For the root group, look up the best context for the required properties, take its winning group expression, then recurse into each child group under the child context that this cost context recorded. Extraction is therefore a join between the group table and the context table — precisely the traversal README.memo.md teaches by hand, and precisely why the memo print includes child ctxts:[3, 3] next to each cost. If the reconstructed expression turns out not to satisfy its requirements, CMemo.cpp raises ExmiUnsatisfiedRequiredProperties and the query falls back to the PostgreSQL planner. From here the winner leaves ORCA’s world: it is serialized to DXL and translated into a PlannedStmt with a slice table by CTranslatorDXLToPlStmt (§17.5), which is ORCA’s create_plan (§15.4).

The plan space, counted and then indexed. optimizer_plan_id=3 extracts the third-ranked plan instead of the cheapest — the same hash join with its inputs swapped.

SET client_min_messages=log;
SET optimizer_enumerate_plans=on;
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;
SET optimizer_plan_id=3;
EXPLAIN SELECT * FROM m172_t t1 JOIN m172_t t2 ON t1.a=t2.a;

LOG:  2026-08-14 00:29:05:168647 CST,THD000,TRACE,"[OPT]: Number of plan alternatives: 8
",
 Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..862.18 rows=1000 width=8)
   ->  Hash Join  (cost=0.00..862.15 rows=334 width=8)
         Hash Cond: (t1.a = t2.a)
         ->  Seq Scan on m172_t t1  (cost=0.00..431.01 rows=334 width=4)
         ->  Hash  (cost=431.01..431.01 rows=334 width=4)
               ->  Seq Scan on m172_t t2  (cost=0.00..431.01 rows=334 width=4)
 Optimizer: GPORCA

LOG:  statement: SET optimizer_plan_id=3;
2026-08-14 00:29:05:216635 CST,THD000,TRACE,"[OPT]: Number of plan alternatives: 8
",
2026-08-14 00:29:05:216739 CST,THD000,TRACE,"[OPT]: Successfully generated plan: 3
",
 Gather Motion 3:1  (slice1; segments: 3)  (cost=0.00..862.18 rows=1000 width=8)
   ->  Hash Join  (cost=0.00..862.15 rows=334 width=8)
         Hash Cond: (t2.a = t1.a)
         ->  Seq Scan on m172_t t2  (cost=0.00..431.01 rows=334 width=4)
         ->  Hash  (cost=431.01..431.01 rows=334 width=4)
               ->  Seq Scan on m172_t t1  (cost=0.00..431.01 rows=334 width=4)
 Optimizer: GPORCA

That count is not a metaphor. CEngine::Pmemotmap (:676) builds a MemoTreeMap — a CTreeMap over cost contexts (CMemo.h:31) — in which every valid combination of winning children is assigned an ordinal, so UllCount() is the exact size of the plan space and PexprUnrank(plan_id) materializes the n-th plan (CEngine.cpp:1749, :1785). The space grows the way you would fear:

Query on m172_t (self-joins)	Groups	Group expressions	Plan alternatives
2-way: t1 JOIN t2 ON t1.a=t2.a	6	17	8
3-way: t1.a=t2.a AND t2.a=t3.a	14	57	156
4-way: adds t3.a=t4.a	25	128	2016

Twenty-five groups and 128 group expressions stand in for 2016 plans — the compression that makes the memo worth having, and the reason branch-and-bound is not optional. For very large spaces ORCA can also sample it: optimizer_sample_plans makes CEngine::SamplePlans (:1928) draw optimizer_samples_number plans uniformly at random around the best cost, which is how cost-model calibration data is collected. Finally, a warning about these knobs: they are developer instruments, not tuning. Asking for optimizer_plan_id=5 in the space above printed an INVALID EXPRESSION trace — a plan whose derived rewindability did not match the requirement — followed by Falling back to Postgres-based planner because plan does not satisfy required properties, which is a fine illustration of the property checks but not something to leave set in a session. Each entry in that trace carries an origin: [Grp:5, GrpExpr:5] annotation, the clearest possible reminder that a plan, here, is a projection of the memo. What actually fills those groups — the 130-odd xform classes and the join-order enumerators behind CXformExpandNAryJoinDPv2 — is §17.3; where the cardinalities and costs come from is §17.4.

Housekeeping for the demos in this section: DROP TABLE m172_t; (the index goes with it). All the print GUCs used here are session-level and hidden from pg_settings; they emit at LOG level, hence SET client_min_messages=log; in every recipe.