Join-order enumeration

For n distinct labeled inputs and one fixed left-associated binary tree shape, there are n factorial leaf permutations before considering equivalence or restrictions. Allowing every ordered full binary tree shape adds a Catalan-number factor. These counts deliberately distinguish left and right children and allow arrangements that a real planner may reject, including unnecessary Cartesian products. Commutative equivalent expressions and unsupported join forms can reduce the useful search. State the counting convention instead of quoting one dramatic number as the exact number of physical plans in a particular database.

A join graph records which inputs have connecting predicates. Searching connected subproblems can avoid many Cartesian combinations. Outer joins, lateral dependencies, semijoins, and other semantic constraints can restrict legal reorderings further. The optimizer must preserve those dependencies even if another order looks smaller under a naïve cardinality formula. A three-table inner-join identity is not a license to rotate an arbitrary mixed outer-join tree. Correctness determines the feasible candidates before estimated intermediate size determines which are attractive.

Dynamic programming can build plans for smaller input subsets and reuse them while constructing larger subsets. There are exponentially many possible subsets even before partitioning each subset into children. A simple scalar recurrence chooses the cheapest combination under an assumed additive cost model. That illustrates optimal substructure, but a production optimizer needs richer state. The cheapest unordered result for a subset may lose to a slightly more expensive ordered result once a parent can avoid sorting. Parameterization and parallel properties create further distinctions.

Pruning is justified only relative to the retained state and cost assumptions. If two subplans provide the same required properties and one has no advantage under the model, the dominated one may be unnecessary. Discarding every higher scalar cost regardless of properties is different. Cardinality errors then affect both the cost of a candidate and which alternatives survive exploration. Improving statistics can consequently help more than increasing search effort, while an excellent search still cannot recover a genuinely unavailable access path or an illegal transformation.

PostgreSQL uses configurable join collapsing and can switch to genetic search beyond a configured relation-count threshold. Heuristic search reduces explored candidates and need not find the globally best modeled plan. Constraining explicit join order can reduce planning time or direct a known useful shape, but it can also prevent a better alternative. Evaluate representative parameters and include planning time in an end-to-end objective. A millisecond saved in execution does not justify seconds of repeated planning for a high-frequency short query without examining reuse and amortization.

The cache lab offers a limited memo-reuse analogy. Reset, set both C=4 and s=4, predict twelve hits among the initial sixteen requests, then Play or Step. Separately Reset, set both C=3 and s=4, predict zero initial hits, then Play or Step. The address stream repeats four fixed identities and the cache is ordinary toy LRU. It is not a join enumerator or an optimizer memo and contains no physical properties. Use it only to explain why losing reusable subproblem state can recreate work, then describe which richer keys a real planner would need.