Cost Functions for the JOIN Operation
A cost-based optimizer must estimate both the work needed to execute a join and the size of the join result. The result-size estimate matters twice: it contributes to the cost of writing the current result, and it becomes an input statistic for every operator above the join.
For a join:
this section uses:
| Symbol | Meaning |
|---|---|
| $ | R |
| Number of blocks occupied by | |
| Blocking factor of the join-result records | |
| Number of levels in an index on | |
| Expected number of | |
| Number of memory buffer blocks available to the join | |
| Join selectivity | |
| Join cardinality |
The join selectivity is the fraction of the Cartesian product that satisfies the join condition:
The estimated join cardinality is therefore:
For an equijoin under uniform-distribution and value-containment assumptions, a common estimate is:
If
The number of blocks needed to materialize the result is estimated as:
The formulas below include this output-write term. An optimizer may omit it when comparing alternatives that produce exactly the same materialized result, but it cannot omit it when pipelining or different intermediate-result sizes make the alternatives behave differently.
Mental model for JOIN cost
The general idea is:
Equivalently, when
The second form is especially useful for nested-loop and index joins. For sort-merge and hash joins, “access matches” also includes preparing both inputs:
| Method | What changes in the middle term? |
|---|---|
| J1 nested loop | Repeatedly scan |
| J2 index join | Probe an index or hash structure on |
| J3 sort-merge | Sort unordered inputs, then scan both inputs together |
| J4 partition-hash | Partition both inputs, then build and probe hash tables |
The output term is always estimated from join cardinality:
If the result is pipelined directly into the next operator instead of materialized, the explicit write cost may be reduced or removed.
Cost Formulas for Join Methods
J1 — Nested-Loop Join
With three buffers and
Reversing the inputs gives:
Although the product term is identical, the initial scan term differs. More importantly, additional buffers can change the cost substantially. With
The optimizer should calculate both orientations. The better outer input is the one that minimizes the number of inner scans, which is usually—but not unconditionally—the smaller relation in blocks.
J2 — Single-Loop Join Using an Access Structure
If
For a nonclustered secondary index:
The
For a clustering index:
For a primary index whose search value identifies one data record:
For a hash key on
Here
J2 is especially attractive when the outer input is small, the inner probe is selective, and the matching data is clustered. A large outer input can make thousands of random probes more expensive than scanning or partitioning both relations.
J3 — Sort-Merge Join
If both inputs are already ordered on compatible join attributes, the merge reads them once:
If either file is unordered, add its external-sorting cost:
An existing physical order or an order required by a later ORDER BY, grouping, or duplicate-elimination operation can make sort-merge more valuable than its local join cost alone suggests.
J4 — Partition-Hash Join
For inputs that must first be partitioned to disk, the usual two-pass estimate is:
The first two passes read and write the partitions; the third reads them to build and probe the in-memory hash tables. If the smaller input already fits in memory, partition files are unnecessary and the estimate approaches:
These formulas assume an equijoin, reasonably balanced hash partitions, and enough memory for every build partition. Skew or recursive repartitioning increases the cost.
Cardinality errors propagate
Underestimating
19.5.1 Join Selectivity and Cardinality for Semi-Join and Anti-Join
Semi-joins and anti-joins commonly appear after a subquery is unnested. Unlike an ordinary join, they return records from only one input and do not multiply the output by every matching record on the other side.
Semi-Join
Consider:
SELECT COUNT(*)
FROM T1
WHERE T1.X IN (SELECT T2.Y FROM T2);The semi-join keeps a T1 record when its X value appears among the T2.Y values. Under the uniform-distribution and containment assumptions:
and:
The MIN caps selectivity at 1 because a semi-join cannot return more records than its preserved input.
Anti-Join
For non-null join attributes, the corresponding anti-join keeps the T1 records whose values do not appear in T2:
SELECT COUNT(*)
FROM T1
WHERE T1.X NOT IN (SELECT T2.Y FROM T2);Its simplified estimate is the complement of the semi-join estimate:
NOT IN and NULL
SQL's three-valued logic makes NOT IN behave differently when either side can contain NULL. Rewriting it as an anti-join requires the optimizer to preserve the query's null semantics; the simple complement formula assumes non-null join values.
19.5.2 Example of Join Optimization Based on Cost Formulas
Reuse the EMPLOYEE statistics from Section 19.4 and add DEPARTMENT:
Consider:
Assume:
DEPARTMENT.Dnumberhas a one-level primary index;EMPLOYEE.Dnohas a two-level secondary index and; is a key, so ; - the result blocking factor is
.
The estimated result contains:
records and occupies:
blocks.
Candidate 1 — J1 with EMPLOYEE outer
Candidate 2 — J1 with DEPARTMENT outer
Candidate 3 — J2 with EMPLOYEE outer
Each employee probes the primary index on Dnumber:
Candidate 4 — J2 with DEPARTMENT outer
Each department probes the secondary index on EMPLOYEE.Dno:
Candidate 5 — J4 partition-hash join
With only these estimates, the optimizer chooses J4.
| Candidate | Estimated block accesses |
|---|---|
J1, EMPLOYEE outer | |
J1, DEPARTMENT outer | |
J2, EMPLOYEE outer | |
J2, DEPARTMENT outer | |
| J4, partition-hash |
Memory can reverse the result. With at least 15 buffers, all 13 DEPARTMENT blocks fit in memory, leaving one input buffer and one output buffer. J1 then reads each input once:
With
Both buffered variants beat the earlier J4 estimate. Cost formulas must therefore use the buffers available to the operator rather than treating the join algorithm's name as a complete plan.
19.5.3 Multirelation Queries and JOIN Ordering Choices
A query that joins
For four relations, the principal tree shapes are:
- A left-deep tree joins the current intermediate result with one base relation at each step.
- A right-deep tree places the intermediate subtree on the inner side.
- A bushy tree permits two intermediate results to be joined.
If Cartesian-product alternatives are allowed,
where
| Relations | Left-deep orders | Bushy ordered trees |
|---|---|---|
| 2 | 2 | 2 |
| 3 | 6 | 12 |
| 4 | 24 | 120 |
| 5 | 120 | 1,680 |
| 6 | 720 | 30,240 |
Optimizers often favor left-deep trees because they work naturally with common join algorithms and can pipeline one intermediate result through the remaining joins. Bushy trees can still win when independent subjoins sharply reduce both sides before they meet, or when those subjoins can run in parallel.
The main objective of join ordering is to keep intermediate results small. Whether an intermediate relation is materialized or pipelined, its cardinality affects the cost of every operator that consumes it.
19.5.4 Physical Optimization
After heuristic transformations produce a logical query plan, the optimizer must choose a concrete implementation for every operator. This second step is called physical optimization. Examples of physical decisions include:
- whether a selection uses a table scan, an index scan, or hashing;
- which relation is the outer or inner input of a join;
- whether a join uses nested loops, an index, sort-merge, or partition hashing;
- whether an intermediate result is pipelined or materialized;
- how much buffer memory each operator receives.
When these choices are compared through their estimated costs, the process is called cost-based physical optimization.
Two broad exploration directions are possible:
| Approach | Traversal | Decision process |
|---|---|---|
| Top-down | From the root toward the leaves | Choose implementations while decomposing the required result into its inputs |
| Bottom-up | From the leaves toward the root | Build physical alternatives for small inputs, then combine the best alternatives into larger plans |
Both approaches conceptually search the space of physical implementations. Bottom-up exploration fits naturally with pipelining and with dynamic programming because the cost and physical properties of a smaller plan are known before that plan becomes an input to a larger operator.
An optimizer can also apply physical heuristics to avoid unnecessary cost calculations:
- Use an index scan for a selection when its estimated retrieval cost is lower than a file scan.
- For conjunctive selections, begin with the condition expected to produce the smallest cardinality.
- Prefer sort-merge join when both inputs already have compatible ordering.
- For multi-input
UNIONorINTERSECTION, use associativity and process inputs in ascending order of estimated cardinality. - When one join input has an index on the join attribute, consider it as the inner relation of an index nested-loop join.
- In particular, when the left input is small and the indexed right input is large, test an index nested-loop plan.
- Avoid join orders containing Cartesian products, or postpone unavoidable Cartesian products until after applicable joins.
Heuristics versus direct costing
For a small join—typically fewer than six relations in the textbook's discussion—the candidate space may be small enough to cost directly. For larger joins, heuristics and pruning prevent the optimization phase itself from becoming excessively expensive.
19.5.5 Dynamic Programming Approach to JOIN Ordering
For five relations, exhaustive enumeration already gives
Dynamic programming reduces repeated work by solving each smaller join-ordering subproblem once and reusing its best plan. A bottom-up search proceeds as follows:
best one-relation access paths
↓
best connected two-relation joins
↓
best connected three-relation joins
↓
complete planLet
Only connected alternatives whose join predicates are available need to be considered; this normally eliminates Cartesian products. Each candidate cost includes the retained subplan's cost, the chosen join method, and the estimated size of its intermediate result.
Five-Relation Illustration
For relations
There are temp1, only the six orders involving temp1,
This pruning is valid only with respect to the state the optimizer retains. Keeping a single cheapest plan per subset can discard a slightly more expensive subplan whose output order makes a later sort-merge join much cheaper. Optimizers address this by preserving additional plans that provide useful interesting orders, such as:
- ordering on an attribute needed by a later join;
- ordering required by a later
GROUP BY; - the final ordering requested by the query.
Thus, the optimizer may keep the cheapest plan for each relevant pair of (relation subset, physical property) rather than only one plan per subset.
For
The result is optimal within the optimizer's chosen search space and cost model, not necessarily the absolute best plan under every possible tree shape, physical property, or runtime condition.
JOIN Cost Estimation — Summary
- Join selectivity estimates the fraction of
that survives; join cardinality estimates the number of result records. - J1 prices repeated inner scans and is highly sensitive to buffer allocation and input orientation.
- J2 replaces inner scans with index or hash probes; it works best with a small outer input and selective inner access.
- J3 adds sorting cost unless compatible input orders already exist.
- J4 commonly costs about
before output when partition files are required. - Semi-joins and anti-joins preserve only one input, so their cardinalities are capped by that input's size.
- For multiway joins, intermediate-result cardinalities drive both join ordering and the choice of algorithm at every node.