Deep Technical Analysis: Fast-Path Planning for OLTP Star Joins

The Core Problem

PostgreSQL's join order optimization uses dynamic programming (DP) to explore all possible join orderings, building up from pairs to the full N-way join. For a query joining N tables, this explores up to N! possible orderings. The key insight driving this thread is that star join queries represent a pathological worst case for this algorithm.

In a star join, one central "fact" table joins to N-1 "dimension" tables, but the dimensions have no join clauses connecting them to each other. This means there are no inter-dimension dependencies that would allow the optimizer to prune the search space — it must explore all (N-1)! orderings of the dimensions. With the default join_collapse_limit=8, this is manageable but already expensive. Bump it to 12 or 16 and planning time explodes.

The critical observation is that for many star joins, the join order of dimensions is irrelevant. When dimensions are joined via foreign keys (or LEFT JOIN to a unique key), the join cannot change the cardinality of the fact table side. Every dimension lookup returns exactly one row per fact row, making all orderings functionally equivalent. The planner wastes enormous effort discovering this.

Quantified Impact

• With 10 dimensions and join_collapse_limit=12: ~2,000 TPS on master
• With fast-path optimization: ~48,000 TPS (24x improvement)
• GEQO helps marginally (1 TPS → ~90 TPS for 15 dimensions), but is still far from optimal
• The optimization achieves ~80% of the throughput possible with join_collapse_limit=1 (which forces syntactic order)

Evolution of the Proposed Solution

Phase 1: The PoC (v1-v2, February 2025)

The initial patch worked by:

1. Detecting the largest relation as "fact" and relations joining only to it as "dimensions"
2. Building join relations directly in a fixed order, skipping the DP search for dimension orderings
3. Leaving non-dimension relations to the regular algorithm

This was crude but effective — it demonstrated the concept with a 3x throughput improvement.

Phase 2: Join List Manipulation (v3-v5, July-November 2025)

Tom Lane suggested a more architecturally sound approach: manipulate the joinlist structure before passing it to the join search algorithm. The idea was to "reverse the flattening" — if the joinlist is (A B C D) and C is a dimension, convert it to ((A B D) C), forcing C to be joined last.

Key design decisions in this phase:

• FK requirement: Tom Lane insisted on foreign keys to guarantee cardinality preservation. Without FKs, a dimension join might eliminate fact rows, making join order significant.
• Placement: The manipulation must happen after match_foreign_keys_to_quals() in query_planner(), since it relies on FK information built by that function.
• has_join_restriction(): Used as a safety check — if a candidate dimension has join order restrictions (typically from outer joins), it's unsafe to reorder.

The v5 patch added support for outer joins (0002 patch) by allowing relations with join restrictions to be moved to the dimension list, provided syntactic order is preserved among restricted relations.

Phase 3: Canonical Order Enforcement (v6, May 2026)

The final approach is architecturally the cleanest and most effective. Rather than manipulating the joinlist before search, it adds a new join order restriction that operates during the standard DP search:

1. starjoins_canonicalize() in query_planner(): Identifies star join clusters and picks a canonical dimension ordering (e.g., by relid).

2. starjoin_order_invalid() in join_search_one_level(): When constructing a new join rel, checks whether it would violate the canonical order. If the new rel contains a subset of the star cluster, it must contain the fact table plus a prefix of the canonical dimension list.

This elegantly integrates with the existing join search:

• Non-dimension relations (A, B) can appear anywhere in the join sequence
• Dimensions must appear in the fixed canonical order relative to each other
• The DP search still finds the optimal placement of the dimension "block" relative to cardinality-changing joins
• No new join tree entry types needed; no modifications to join_search_one_level()'s core logic

Why this works: If there are K dimensions and M other relations, instead of exploring (K+M)! orderings, we explore roughly M! × (M+1) orderings (the M other relations in all orders, with the dimension block tried at each insertion point). The K! factor is completely eliminated.

Key Technical Debates and Tradeoffs

1. FK Requirement vs. Broader Applicability

Tom Lane's position: FKs are essential for correctness. Without them, you can't guarantee the join won't eliminate rows, making order significant.

Counter-arguments (Jim Nasby, Corey Huinker): Many installations remove FKs due to the overhead of RI checks (especially delete cascades causing sequential scans of large fact tables). Requiring FKs would limit applicability.

Resolution: The patch requires FKs for inner joins but could accept LEFT JOIN + UNIQUE for outer joins (since left joins preserve all fact rows regardless). This balances correctness with practical applicability.

2. Dimensions with Restriction Clauses

Tom Lane raised (November 2025): It's unrealistic to assume dimensions won't have WHERE clauses. A typical query filters on dimension attributes (e.g., WHERE c.customer_name = 'Wile E Coyote').

Robert Haas confirmed: Restriction clauses on dimension tables are very common in real workloads.

Impact: Dimensions with restrictions DO change cardinality (they reduce it). Their join order matters — more selective dimensions should be joined first. The v5/v6 patches handle this by only treating unrestricted FK-joined dimensions as candidates for the fast path, leaving restricted dimensions to the normal DP search.

Open question: Could we extend the optimization to restricted dimensions by ordering them by selectivity? This would capture a much larger class of real-world queries.

3. Row-Count-Inflating Joins

Robert Haas's concern: If non-dimension joins inflate cardinality, pushing dimensions to the end is suboptimal. The dimension joins should happen at the point of minimum cardinality.

Example: With fact F, neutral dimensions S1/S2, restrictive joins D1/D2, and inflating joins I1/I2, optimal order is F-D1-D2-S1-S2-I1-I2. But if dimensions are forced to the end: F-D1-D2-I1-I2-S1-S2 — now S1 and S2 process inflated cardinality.

v6 solution: The canonical order restriction only constrains the relative order of dimensions. Non-dimension joins can appear anywhere, and the DP search finds the optimal placement. This naturally handles the inflating-join case.

4. Interaction with join_collapse_limit

The optimization operates within the groups created by join_collapse_limit. With the default of 8, if a query has 20 tables split into groups of 8, the optimization only helps within each group. This limits benefit for very large queries where dimensions span multiple groups.

5. Secondary Bottleneck: get_actual_variable_range()

Tomas identified that even with fast-path planning enabled, ~40% of remaining planning time is spent in initial_cost_mergejoin → get_actual_variable_range(), doing B-tree lookups for range estimation. Disabling merge join doubles throughput further. This suggests a caching opportunity for range statistics, orthogonal to the join ordering optimization.

Architectural Implications

Relation to GEQO

GEQO (Genetic Query Optimization) is PostgreSQL's existing fallback for large join problems, but:

• Default thresholds (join_collapse_limit=8, geqo_threshold=12) mean most queries never hit GEQO
• GEQO only improves from 1 TPS to ~90 TPS for 15-dimension star joins (vs. ~4200 TPS with the fast path)
• GEQO is a general-purpose heuristic; the star join optimization exploits structural knowledge

Relation to Greedy Join Search

A parallel thread discusses greedy join search as an alternative to DP. The star join optimization is complementary — it reduces the problem size before DP (or greedy) search begins. Both could coexist.

Relation to Joel's Foreign Key Joins Patch

Another patch proving facts about FK joins (e.g., which joins preserve cardinality) could provide infrastructure this patch could leverage, potentially extending it to more cases.

Future Extensions

• Snowflake schemas: Leaf dimensions work, but "inner" dimensions (connecting to other dimensions) need transitive FK reasoning
• Inverse star joins: Many small tables with FKs pointing TO a central table (rather than from it)
• Partitionwise joins: Could the canonical ordering prevent partition-wise join opportunities? This remains an open concern.

Current Status (May 2026)

The v6 patch demonstrates a clean architectural approach (canonical order enforcement) that achieves ~80% of theoretical maximum throughput while fitting naturally into the existing DP join search. Key remaining work:

• Handling dimensions with restriction clauses (ordering by selectivity)
• Snowflake schema support
• Verification that no partition-wise join or interesting-order opportunities are missed
• Robustness testing for edge cases and potential regressions