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:
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:
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:
| Relation | Rows | Blocks | Rows per block |
|---|---|---|---|
PROJECT | 2,000 | 100 | 20 |
DEPARTMENT | 50 | 5 | 10 |
EMPLOYEE | 10,000 | 2,000 | 5 |
The access paths relevant to this plan are:
| Index | Attribute | Unique? | Levels used by a lookup | Relevant statistic |
|---|---|---|---|---|
PROJ_PLOC | PROJECT.Plocation | No | 2 | |
EMP_SSN | EMPLOYEE.Ssn | Yes | 2 |
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:
PROJECT ⋈ DEPARTMENT ⋈ EMPLOYEEDEPARTMENT ⋈ PROJECT ⋈ EMPLOYEEDEPARTMENT ⋈ EMPLOYEE ⋈ PROJECTEMPLOYEE ⋈ 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:
Under the uniform-distribution assumption, its selectivity is:
The estimated selection cardinality is therefore:
The optimizer compares two access paths.
Linear scan
Scanning the entire PROJECT relation costs:
Nonunique secondary index
Using PROJ_PLOC traverses two index levels and may retrieve each of the 10 records from a different data block:
Because
Step 2 — Materialize TEMP1
The 10 selected PROJECT records become TEMP1. The original blocking factor is:
Hence:
Writing TEMP1 costs one additional block access. The accumulated cost after selection and materialization is:
Step 3 — Join TEMP1 with DEPARTMENT
The first join is:
TEMP1 is the outer input and fits entirely in memory. Because DEPARTMENT has no useful index, its five blocks are scanned once:
Dnumber is the key of DEPARTMENT, so every TEMP1.Dnum value matches at most one department. The estimated cardinality remains 10 rows:
Assume the wider joined records have a blocking factor of five rows per block:
Materializing TEMP2 therefore costs two writes. The accumulated cost is now:
Step 4 — Join TEMP2 with EMPLOYEE
The final join is:
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:
All 10 probes cost:
Reading the two blocks of TEMP2 gives:
Because the final projection is pipelined, no extra temporary file is written.
Total Estimated Cost
The complete cost for join order 1 is:
| Stage | Estimated block accesses | Running total |
|---|---|---|
Select Stafford projects using PROJ_PLOC | 12 | 12 |
Materialize TEMP1 | 1 | 13 |
Join TEMP1 with DEPARTMENT | 6 | 19 |
Materialize TEMP2 | 2 | 21 |
Join TEMP2 with EMPLOYEE using EMP_SSN | 32 | 53 |
| Pipeline final projection | 0 | 53 |
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
PROJECTto five rows per block inTEMP2. - 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.