Skip to content

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:

R⋈R.A=S.BS

this section uses:

SymbolMeaning
$R
bR, bSNumber of blocks occupied by R and S
bfrRSBlocking factor of the join-result records
xBNumber of levels in an index on S.B
sBExpected number of S records matching one value of B
nBNumber of memory buffer blocks available to the join
jsJoin selectivity
jcJoin cardinality

The join selectivity is the fraction of the Cartesian product that satisfies the join condition:

js=|R⋈S||R||S|,0≤js≤1

The estimated join cardinality is therefore:

jc=js|R||S|

For an equijoin under uniform-distribution and value-containment assumptions, a common estimate is:

js≈1max(NDV(A,R),NDV(B,S))

If B is a key of S and every foreign-key value in R.A has a match, the estimate becomes js=1/|S| and the result contains |R| records.

The number of blocks needed to materialize the result is estimated as:

bRS=⌈js|R||S|bfrRS⌉

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:

CJOIN=Read or prepare inputs+Find matching pairs+Write output

Equivalently, when R is the outer input:

CJOIN=Read R+Access matches in S+bRS

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:

MethodWhat changes in the middle term?
J1 nested loopRepeatedly scan S
J2 index joinProbe an index or hash structure on S for every record of R
J3 sort-mergeSort unordered inputs, then scan both inputs together
J4 partition-hashPartition both inputs, then build and probe hash tables

The output term is always estimated from join cardinality:

bRS=⌈js|R||S|bfrRS⌉

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 R as the outer relation, one outer block is read at a time and the entire inner relation is scanned for it:

CJ1=bR+bRbS+bRS

Reversing the inputs gives:

CJ1′=bS+bSbR+bRS

Although the product term is identical, the initial scan term differs. More importantly, additional buffers can change the cost substantially. With nB buffers, up to nB−2 outer blocks can be held at once:

CJ1(R,S)=bR+⌈bRnB−2⌉bS+bRS

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 S.B has a useful access structure, the optimizer scans R once and probes S for every record of R. The access cost depends on the inner structure.

For a nonclustered secondary index:

CJ2a=bR+|R|(xB+sB)+bRS

The sB term is a worst-case estimate in which matching records occupy different data blocks. A separate pointer-list block may add one access per probe depending on the index representation.

For a clustering index:

CJ2b=bR+|R|(xB+⌈sBbfrS⌉)+bRS

For a primary index whose search value identifies one data record:

CJ2c=bR+|R|(xB+1)+bRS

For a hash key on S.B:

CJ2d=bR+|R|h+bRS

Here h≥1 is the expected number of block accesses for one hash lookup. A simplified estimate uses h=1 for static or linear hashing and h=2 for extendible hashing, although collisions and overflow blocks can make the real value higher.

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:

CJ3=bR+bS+bRS

If either file is unordered, add its external-sorting cost:

CJ3=Sort(R)+Sort(S)+bR+bS+bRS

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:

CJ4=3(bR+bS)+bRS

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:

CJ4,memory=bR+bS+bRS

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 js makes the current output appear too cheap and gives the parent operator an input that is too small. In a multiway query, one inaccurate estimate can therefore change both the chosen join algorithm and the entire join order.

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:

sql
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:

jssemi=min(1,NDV(Y,T2)NDV(X,T1))

and:

jcsemi=|T1|jssemi

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:

sql
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:

jsanti=1−min(1,NDV(Y,T2)NDV(X,T1))jcanti=|T1|jsanti

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:

|E|=10,000,bE=2,000,|D|=125,bD=13

Consider:

OP6:EMPLOYEE⋈Dno=DnumberDEPARTMENT

Assume:

  • DEPARTMENT.Dnumber has a one-level primary index;
  • EMPLOYEE.Dno has a two-level secondary index and sDno=80;
  • Dnumber is a key, so jsOP6=1/125;
  • the result blocking factor is bfrED=4.

The estimated result contains:

jc=1125(10,000)(125)=10,000

records and occupies:

bED=10,0004=2,500

blocks.

Candidate 1 — J1 with EMPLOYEE outer ​

CJ1=2,000+(2,000)(13)+2,500=30,500

Candidate 2 — J1 with DEPARTMENT outer ​

CJ1=13+(13)(2,000)+2,500=28,513

Candidate 3 — J2 with EMPLOYEE outer ​

Each employee probes the primary index on Dnumber:

CJ2c=2,000+10,000(1+1)+2,500=24,500

Candidate 4 — J2 with DEPARTMENT outer ​

Each department probes the secondary index on EMPLOYEE.Dno:

CJ2a=13+125(2+80)+2,500=12,763

Candidate 5 — J4 partition-hash join ​

CJ4=3(13+2,000)+2,500=8,539

With only these estimates, the optimizer chooses J4.

CandidateEstimated block accesses
J1, EMPLOYEE outer30,500
J1, DEPARTMENT outer28,513
J2, EMPLOYEE outer24,500
J2, DEPARTMENT outer12,763
J4, partition-hash8,539

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:

CJ1=13+2,000+2,500=4,513

With nB=10, eight outer blocks fit in each chunk:

CJ1=13+⌈1310−2⌉(2,000)+2,500=6,513

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 n relations normally contains n−1 binary joins. Commutativity and associativity allow many equivalent trees, but their intermediate results—and therefore their execution costs—can differ dramatically.

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, n labeled relations have n! left-deep orders. Allowing every bushy shape expands the space to:

n!Cn−1=(2n−2)!(n−1)!

where Cn−1 is a Catalan number. The growth is rapid:

Relations nLeft-deep ordersBushy ordered trees
222
3612
424120
51201,680
672030,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:

ApproachTraversalDecision process
Top-downFrom the root toward the leavesChoose implementations while decomposing the required result into its inputs
Bottom-upFrom the leaves toward the rootBuild 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:

  1. Use an index scan for a selection when its estimated retrieval cost is lower than a file scan.
  2. For conjunctive selections, begin with the condition expected to produce the smallest cardinality.
  3. Prefer sort-merge join when both inputs already have compatible ordering.
  4. For multi-input UNION or INTERSECTION, use associativity and process inputs in ascending order of estimated cardinality.
  5. When one join input has an index on the join attribute, consider it as the inner relation of an index nested-loop join.
  6. In particular, when the left input is small and the indexed right input is large, test an index nested-loop plan.
  7. 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 5!=120 left-deep orders and 1,680 ordered bushy trees. Most traditional optimizers therefore restrict the search to left-deep trees. They suit nested-loop and index nested-loop joins, preserve access to indexes on each newly introduced base relation, and can form fully pipelined plans.

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:

text
best one-relation access paths
              ↓
best connected two-relation joins
              ↓
best connected three-relation joins
              ↓
         complete plan

Let Best(S) be the cheapest retained plan for a subset S of the query's relations. For a left-deep plan, a recurrence can extend the best plan for S−{R} with one base relation R:

Best(S)=minR∈S(Cost(Best(S−{R})⋈R))

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 r1,r2,r3,r4,r5, an exhaustive left-deep search compares 120 orders. The textbook illustrates decomposition around a three-relation subproblem:

r1⋈r2⋈r3⋈r4⋈r5=(r1⋈r2⋈r3)⋈r4⋈r5

There are 3!=6 orders for the first three relations. After the best plan for that subproblem has been retained as temp1, only the six orders involving temp1, r4, and r5 need to be examined in the simplified illustration. The search compares 6+6=12 alternatives instead of all 120 complete orders.

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 n relations there are 2n relation subsets—32 for n=5 and 1,024 for n=10. With a small number of interesting orders, this remains far smaller than enumerating every ordered bushy tree. The extended dynamic-programming search for an optimal left-deep order has complexity on the order of:

O(3n)

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 R×S 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 3(bR+bS) 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.

Built with ❤️ and curiosity