Join-Order Optimization (Dynamic Programming)

For 3 or more tables, the ORDER you join them in changes query cost dramatically -- join two huge tables first and you build an enormous intermediate result before ever applying a filter that would have shrunk it. System R's classic dynamic-programming algorithm finds the provably cheapest order: build up from single tables to the full join, reusing the best-known plan for every smaller subset along the way, rather than trying every possible ordering from scratch (which is factorial in the number of tables).

combined_selectivity (given) computes how selective a join between two GROUPS of tables is, by multiplying every known pairwise selectivity between a table in left and a table in right. If NO such predicate exists at all, it returns None -- that split can't be joined without an (unwanted) cross product, so it must be skipped entirely.

Implement plan(subset, cardinalities, selectivities, memo)'s recursive case (2+ relations -- the 1-relation base case is done for you):

Try every way to split subset into two non-empty, disjoint parts (left, right).
For each split where combined_selectivity isn't None, recursively plan() each side. If EITHER side has no valid plan (None), skip this split too.
Otherwise compute this join's estimated cardinality (left_card * right_card * selectivity) and total cost (left_cost + right_cost + this join's cardinality).
Keep the cheapest total cost found across all valid splits. Store (best_cost, best_cardinality) in memo[subset] and return it. If NO split was valid at all, store/return None.

Example

# R -- S -- T (no direct R-T predicate) -- must route through S
optimal_join_plan(
    {"R": 1000, "S": 10, "T": 1000},
    {frozenset({"R","S"}): 0.01, frozenset({"S","T"}): 0.01},
)
# -> (1100, 1000)

Constraints

memo must be checked and updated so repeated recursive calls for the same subset don't redo work -- that's what makes this dynamic programming instead of exponential brute force.
A relation pair with no join predicate at all must never be silently treated as a (very expensive) cross product -- it must be excluded from consideration entirely.

Real-world grounding

Postgres's join order search (geqo/dynamic programming join planner): src/backend/optimizer/path/joinrels.c

Real optimizers add cost models far more detailed than "cardinality times selectivity" (index availability, sort order, memory pressure) and switch to a genetic/heuristic search (Postgres's GEQO) once the number of tables gets too large for exhaustive DP -- but "try every split, keep the cheapest, memoize by subset" is the core algorithm underneath the exhaustive case.