Query Optimization: Cardinality Before Cost

The optimizer cannot measure every possible plan before running a query. It estimates intermediate result sizes, assigns costs, and chooses the cheapest plan under its model.

Logical rewrites reduce work early

Relational-algebra equivalences allow the optimizer to:

• push selections toward scans;
• remove unused columns early;
• reorder inner joins;
• replace a Cartesian product plus filter with a join.

Pushing topic = 'databases' below a join can shrink the input before an expensive operator. Outer joins, limits, volatile functions, and NULL semantics restrict which rewrites are legal.

Cardinality drives every later choice

For equality selection under a uniformity assumption:

T(σ A=c (R)) ≈ T(R) / V(R,A)

For an equality join:

T(R ⋈ S) ≈ T(R) × T(S) / max(V(R,A), V(S,A))

T is tuple count and V is the number of distinct values. These formulas are useful models, not promises. Skew, correlated columns, missing values, and stale statistics violate their assumptions.

In plain terms: the optimizer chooses a route using a map of expected row counts. If one intersection is marked as ten cars but actually has ten thousand, every route decision after it may be wrong.

Join order changes intermediate size

With three tables, the final result can be identical while intermediate results differ by orders of magnitude. Joining two large tables first may create a huge temporary result; joining a selective relation first may reduce the rest of the plan.

Dynamic programming can compare subplans for smaller join sets, but the search space grows quickly. Optimizers prune alternatives and use heuristics for large queries.

Cost is more than elapsed time

The model combines sequential and random page access, CPU work, memory, parallelism, and expected output. Its cost units are for comparing plans; they are not milliseconds.

EXPLAIN (ANALYZE, BUFFERS, VERBOSE, TIMING OFF)
SELECT t.name, count(*)
FROM topic t
JOIN paper_topic pt ON pt.topic_id = t.topic_id
JOIN paper p ON p.paper_id = pt.paper_id
WHERE p.year >= 2024
GROUP BY t.name;

Read bottom-up and compare estimated rows with actual rows at the first point they diverge. A bad top-level estimate is often caused by an earlier scan or join, not the top node itself.

Fix evidence, not symptoms

When estimates are wrong, check:

1. Were statistics collected after loading representative data?
2. Is the test distribution realistic?
3. Are predicates correlated while the model assumes independence?
4. Is a cast or function hiding an indexed column?
5. Is the query returning so much data that a scan is correct?

Hints can force a plan, but they freeze a decision that may become wrong as data changes. Improve statistics, query shape, and indexes first.

Review card

• Rewrites must preserve semantics.
• Intermediate cardinality determines downstream cost.
• Uniformity and independence are assumptions, not facts.
• Join order matters because intermediate results differ.
• Planner cost is a comparison unit, not elapsed time.
• Find the first estimate/actual divergence.
• Prefer fixing evidence over forcing plans.

T(σ A=c (R)) ≈ T(R) / V(R,A)

T(R ⋈ S) ≈ T(R) × T(S) / max(V(R,A), V(S,A))

EXPLAIN (ANALYZE, BUFFERS, VERBOSE, TIMING OFF)
SELECT t.name, count(*)
FROM topic t
JOIN paper_topic pt ON pt.topic_id = t.topic_id
JOIN paper p ON p.paper_id = pt.paper_id
WHERE p.year >= 2024
GROUP BY t.name;