Skip to content

Example to Illustrate Cost-Based Query Optimization ​

This section combines the ideas from the previous sections into one optimization example. The optimizer must estimate selection cardinality, choose an access path, determine a join order and join methods, estimate intermediate-result sizes, and account for materialization or pipelining.

Consider query Q2:

sql
SELECT Pnumber, Dnum, Lname, Address, Bdate
FROM PROJECT, DEPARTMENT, EMPLOYEE
WHERE Dnum = Dnumber
  AND Mgr_ssn = Ssn
  AND Plocation = 'Stafford';

The query asks for every project in Stafford, its controlling department, and information about that department's manager. Its logical expression is:

πPnumber,Dnum,Lname,Address,Bdate((σPlocation=′Stafford′(PROJECT)⋈Dnum=DnumberDEPARTMENT)⋈Mgr_ssn=SsnEMPLOYEE)

The corresponding left-deep plan is:

The example assumes that heuristic optimization has already pushed the selection on PROJECT below the joins, but has not pushed projections down the tree. Cost-based optimization begins from this logical plan.

Catalog Statistics ​

The optimizer has the following table statistics:

RelationRowsBlocksRows per block
PROJECT2,00010020
DEPARTMENT50510
EMPLOYEE10,0002,0005

The access paths relevant to this plan are:

IndexAttributeUnique?Levels used by a lookupRelevant statistic
PROJ_PLOCPROJECT.PlocationNo2NDV(Plocation,PROJECT)=200
EMP_SSNEMPLOYEE.SsnYes2NDV(Ssn,EMPLOYEE)=10,000

DEPARTMENT has no index useful to this example. The optimizer must access it through a table scan.

Simplifying assumptions

The estimates assume uniform value distributions, materialized intermediate results, and enough buffer space to hold the small temporary input during the first join. The final projection is pipelined and therefore adds no block I/O.

Candidate JOIN Orders ​

Restricting the search to left-deep trees and excluding Cartesian products leaves four valid orders:

  1. PROJECT ⋈ DEPARTMENT ⋈ EMPLOYEE
  2. DEPARTMENT ⋈ PROJECT ⋈ EMPLOYEE
  3. DEPARTMENT ⋈ EMPLOYEE ⋈ PROJECT
  4. EMPLOYEE ⋈ DEPARTMENT ⋈ PROJECT

Orders beginning with PROJECT ⋈ EMPLOYEE or EMPLOYEE ⋈ PROJECT are excluded because those two relations have no direct join predicate. Joining them first would create a Cartesian product.

The textbook calculates the first order in detail. A real optimizer repeats the same process for every remaining order and retains the plan with the smallest estimated cost.

Step 1 — Optimize the PROJECT Selection ​

The selection is:

σPlocation=′Stafford′(PROJECT)

Under the uniform-distribution assumption, its selectivity is:

slPlocation=1NDV(Plocation,PROJECT)=1200

The estimated selection cardinality is therefore:

sPlocation=2,000(1200)=10 rows

The optimizer compares two access paths.

Linear scan ​

Scanning the entire PROJECT relation costs:

Cscan=bPROJECT=100

Nonunique secondary index ​

Using PROJ_PLOC traverses two index levels and may retrieve each of the 10 records from a different data block:

Cindex=xPlocation+sPlocation=2+10=12

Because 12<100, the optimizer chooses the index.

Step 2 — Materialize TEMP1 ​

The 10 selected PROJECT records become TEMP1. The original blocking factor is:

bfrPROJECT=2,000100=20 rows per block

Hence:

bTEMP1=⌈1020⌉=1 block

Writing TEMP1 costs one additional block access. The accumulated cost after selection and materialization is:

C1=12+1=13

Step 3 — Join TEMP1 with DEPARTMENT ​

The first join is:

TEMP1⋈Dnum=DnumberDEPARTMENT

TEMP1 is the outer input and fits entirely in memory. Because DEPARTMENT has no useful index, its five blocks are scanned once:

Cjoin1=bTEMP1+bDEPARTMENT=1+5=6

Dnumber is the key of DEPARTMENT, so every TEMP1.Dnum value matches at most one department. The estimated cardinality remains 10 rows:

|TEMP2|=|TEMP1|=10

Assume the wider joined records have a blocking factor of five rows per block:

bTEMP2=⌈105⌉=2

Materializing TEMP2 therefore costs two writes. The accumulated cost is now:

C2=13+6+2=21

Step 4 — Join TEMP2 with EMPLOYEE ​

The final join is:

TEMP2⋈Mgr_ssn=SsnEMPLOYEE

The unique EMP_SSN index lets the optimizer use a single-loop index join. Each of the 10 TEMP2 rows performs one lookup consisting of two index-block accesses and one employee data-block access:

Clookup=xSsn+1=2+1=3

All 10 probes cost:

10(3)=30

Reading the two blocks of TEMP2 gives:

Cjoin2=bTEMP2+30=2+30=32

Because the final projection is pipelined, no extra temporary file is written.

Total Estimated Cost ​

The complete cost for join order 1 is:

\begin{aligned} C_{total} &=\underbrace{12}_{\text{select through PROJ_PLOC}} +\underbrace{1}_{\text{write TEMP1}} \\ &\quad+\underbrace{6}_{\text{read TEMP1 and DEPARTMENT}} +\underbrace{2}_{\text{write TEMP2}} \\ &\quad+\underbrace{32}_{\text{read TEMP2 and probe EMP_SSN}} \\ &=53\text{ block accesses} \end{aligned}
StageEstimated block accessesRunning total
Select Stafford projects using PROJ_PLOC1212
Materialize TEMP1113
Join TEMP1 with DEPARTMENT619
Materialize TEMP2221
Join TEMP2 with EMPLOYEE using EMP_SSN3253
Pipeline final projection053

The value 53 is not yet proof that this is the best plan. It is one candidate's estimated cost. The optimizer must cost the other three legal join orders under the same assumptions and compare them.

Lessons from the Example ​

  • Cardinality estimation converts catalog statistics into the expected 10 Stafford projects.
  • An applicable index is useful only after its estimated cost is compared with a scan: 12 accesses versus 100 here.
  • Key information prevents the first join cardinality from growing beyond 10 rows.
  • Intermediate tuple width matters because it changes the blocking factor from 20 rows per block in PROJECT to five rows per block in TEMP2.
  • Join ordering determines which intermediate results and access paths are available to the next operator.
  • Materialization adds explicit writes and later reads; pipelining can remove those costs.
  • A cost estimate is meaningful only together with its assumptions about distributions, indexes, buffers, and physical algorithms.

Built with ❤️ and curiosity