ORCA 101: How a Cascades-style optimizer actually works

PostgreSQL's planner is a finely tuned thing. It walks the join tree left-deep, uses dynamic programming up to geqo_threshold relations, and falls back to a genetic algorithm beyond that. For OLTP and most reporting queries, it produces near-optimal plans in microseconds.

ORCA takes a different approach. It is a Cascades-style cost-based optimizer: it doesn't generate one plan, it generates a space of equivalent plans, prices every one of them, and picks the cheapest. The search engine, the cost model, and the metadata access are decoupled from the host database — which is what made it possible to lift ORCA out of Greenplum and drop it into PostgreSQL 18 as pg_orca.

This post is a guided tour of how that optimizer actually works, framed for single-node PostgreSQL. No Greenplum knowledge required.

The big idea: optimizer as a separate process

PostgreSQL's planner lives inside the backend. It reads from pg_statistic directly, calls executor utilities, and emits a PlannedStmt that the executor consumes. The boundary between planner and executor is a struct.

ORCA's boundary is a serialization format called DXL — Data eXchange Language, an XML dialect that describes queries, metadata, and plans. The optimizer doesn't know what database it's optimizing for. It asks the host three things, over DXL:

1. Here is the query as a relational algebra tree. What's the cheapest plan?
2. I need statistics for these columns. Can you provide them?
3. Here is the plan I picked. Translate it back to your executor's format.

In pg_orca, this boundary survives intact. The PostgreSQL extension implements the three translator components — query-to-DXL, MD provider, DXL-to-plan — and ORCA itself runs in-process but logically isolated. When ORCA can't handle a query, the boundary makes fallback trivial: discard the DXL, hand the parse tree back to standard_planner, done.

The four steps of optimization

Every query that enters ORCA goes through four phases. The names below match the source code, so you can grep for them.

Step 1 — Exploration: enumerate equivalent plans

ORCA builds a structure called the Memo. The Memo is a forest of groups, where each group holds a set of operator expressions that all produce the same relation. Two expressions in the same group are by definition equivalent — they compute the same rows, just differently.

Start with this query:

SELECT * FROM t1 JOIN t2 ON t1.a = t2.b;

After parsing, the initial Memo has three groups:

GROUP 0: [ InnerJoin(t1.a = t2.b) [1, 2] ]
GROUP 1: [ Get(t1) ]
GROUP 2: [ Get(t2) ]

Group 0's only member references groups 1 and 2 as its inputs. Now ORCA applies transformation rules. The first one to fire is join commutativity: A ⋈ B ≡ B ⋈ A. After firing, group 0 has two members:

GROUP 0: [ InnerJoin [1, 2], InnerJoin [2, 1] ]
GROUP 1: [ Get(t1) ]
GROUP 2: [ Get(t2) ]

The Memo doesn't replace the old expression. It accumulates alternatives. For a five-way join, the Memo will end up holding hundreds of algebraically-equivalent join trees — left-deep, right-deep, bushy, reordered — without ever materializing them as separate plan trees.

This is the single biggest win over PostgreSQL's planner: ORCA considers bushy plans. PostgreSQL only generates left-deep joins, which leaves performance on the table for analytical queries where intermediate result sizes vary by orders of magnitude.

Step 2 — Statistics derivation: cardinality estimation

Plan enumeration is worthless without cardinality estimates. For every group, ORCA derives a CStatistics object containing row counts and per-column histograms. It does this lazily, asking the host (via the MD Provider) for base-table stats and then propagating them up through joins, filters, and aggregates.

The propagation logic is identical in spirit to what PostgreSQL does in clauselist_selectivity — but ORCA does it once per group, not once per candidate plan. Because groups are shared, an expensive subquery's cardinality is estimated exactly once even if it appears in fifty candidate plans.

Step 3 — Implementation: logical to physical

So far everything in the Memo is logical: InnerJoin, Get, GbAgg. Now ORCA applies a second class of transformation — implementation rules — that convert each logical operator into one or more physical alternatives.

InnerJoin [1, 2]
  ↓ implementation rules
InnerHashJoin [1, 2]
InnerNLJoin   [1, 2]
InnerMergeJoin[1, 2]

All three live in the same group. They're equivalent (same rows), but they have different costs and different physical properties — sort order, locality, parallelism — which matters for the next step.

Step 4 — Optimization: properties, costing, enforcement

The final step walks the Memo top-down, asking each group: what is the cheapest plan that satisfies these required properties?

For a top-level ORDER BY a, the root demands sorted output on a. A MergeJoin on a provides that property for free. A HashJoin doesn't — so ORCA inserts a Sort enforcer above it and adds its cost.

The same mechanism handles every kind of plan property — sort order, NULL ordering, even partition awareness. Because requirements flow down the tree and best plans bubble up, ORCA never has to enumerate full physical plans. It picks the winning physical expression in each group, glues them together, and emits the final tree.

Transformation rules: where the search power comes from

A Cascades optimizer's behavior is almost entirely defined by its rule library. ORCA ships about 130 rules; each one is a small object with two pieces:

• A pattern — the shape of the expression it matches (e.g. "a GbAgg on top of any relational child")
• A transform — the new expression it produces

Some examples of what these rules do:

• JoinCommutativity — A ⋈ B ≡ B ⋈ A
• JoinAssociativity — (A ⋈ B) ⋈ C ≡ A ⋈ (B ⋈ C)
• PushDownFilter — move predicates closer to scans
• SplitGbAgg — split a global aggregate into local + global
• Decorrelate* — pull correlated subqueries up into joins
• ImplementInnerJoinAsHashJoin — pick a physical operator

Rules can fire on each other's output. Join commutativity plus associativity together generate the full space of n-ary join orderings, bushy plans included. The search engine keeps firing rules until the Memo is closed under all applicable rules, then costs the result.

Decorrelation deserves a special mention: it is the source of most of the dramatic speedups you see in our TPC-DS benchmarks. A correlated EXISTS subquery that PostgreSQL evaluates row-by-row becomes, under ORCA, a single semi-join — orders of magnitude faster on large inputs.

Reading the source tree

If you want to dive into the code, here's a 30-second tour of the top-level libraries. The relevant headers live under gporca/:

• libgpos — the foundation layer. Memory pools, exceptions, threading primitives, the unit-test harness. You rarely need to touch this.
• libnaucrates — DXL, metadata, statistics. This is the wire format and the cardinality estimator. When stats look wrong, this is where to look.
• libgpopt — the optimizer itself. Operators, the Memo, the search engine, the transformation rules. The xforms/ directory is one file per rule.
• libgpdbcost — the cost model. Number-of-rows × cost-per-row, with knobs for hash buildup, sort spill, index lookup latency.

The PostgreSQL integration lives outside of these libraries, in pg_orca's top-level src/ — that's where the planner_hook, the DXL translators, and the fallback machinery live. We'll cover that layer in a future post.

What this means for pg_orca

The four-step pipeline is exactly the same on a single-node PostgreSQL as it was on a 32-segment Greenplum cluster. The Memo, the rules, the statistics derivation, the property framework — all of it runs unchanged.

What's different is what the cost model prices. The Greenplum cost model has a term for redistribution — the cost of shuffling tuples between segments. On a single node, that term is zero. The MPP-specific enforcement rules (Gather, Redistribute, Broadcast) still exist in the rule library, but they never fire because the property framework never demands the distribution properties they satisfy.

In other words: ORCA on PostgreSQL is the same optimizer with a tighter cost model. The bushy plans, the decorrelation, the exhaustive join search — that's all still there. That's why pg_orca can find plans the PostgreSQL planner can't, even on a laptop.

Next: configuring it

Now that you know what's happening inside the optimizer, the natural follow-up is what you can tune from the outside. See Configuring pg_orca: a guide to the GUCs you'll actually use for the master switch, cost-model selector, join-order algorithms, and the debug prints that surface every step of the four-step pipeline described above.

---

Adapted from the GPORCA OSS 101 wiki and the SIGMOD 2014 paper.