Cost Functions for the SELECT Operation
A cost-based optimizer compares the access methods for a relational SELECT operation by estimating how many blocks each method transfers between disk and memory. These estimates deliberately omit CPU time, temporary-storage cost, caching effects, and device-specific I/O behavior so that alternative plans can be compared with a simple common metric.
For a relation
| Symbol | Meaning |
|---|---|
| Estimated block accesses for selection method | |
| Number of records in | |
| Number of blocks occupied by | |
| Blocking factor, or records per block | |
| Selectivity of a condition on | |
| Selection cardinality, | |
| Number of levels in the index on | |
| Number of first-level blocks in that index | |
| Number of distinct values of |
Relation and attribute subscripts are omitted below when their meaning is clear.
Cost Formulas for Selection Methods
S1 — Linear Search
A file scan works for every selection condition. If all blocks must be examined, its cost is:
For equality on a key, the scan stops when it finds the unique record. Assuming the record exists and is equally likely to occur anywhere in the file, the average cost is:
The unsuccessful-search cost remains
S2 — Binary Search on an Ordered File
If the data file is ordered on the selection attribute, binary search locates a matching block and the adjacent blocks containing the rest of the matching records:
For equality on a unique key,
S3a — Primary Index for One Record
A primary index is traversed from its root to a leaf, after which one data block is read:
S3b — Hash Key for One Record
Static or linear hashing usually retrieves the target bucket in one block access:
Extendible hashing generally needs one additional directory access, giving an estimate of two block accesses. Collisions and overflow blocks can make the actual cost higher.
S4 — Ordering Index for a Range
For a range condition such as
This is only a rough average. A histogram can estimate the qualifying fraction and replace
S5 — Clustering Index for Multiple Records
When a nonkey attribute has a clustering index, records with the same value occupy a cluster of consecutive blocks. The index traversal and cluster scan cost:
The formula assumes that the
S6 — Secondary B⁺-Tree Index
For equality on a unique secondary key, the index identifies one record:
For equality on a nonkey attribute, qualifying records may be scattered across the file. A worst-case estimate is:
Here the extra block contains the record-pointer list, and the estimate assumes every one of the
For a range that is expected to qualify half the records, the optimizer may estimate:
The three terms represent the index traversal, the qualifying part of the leaf level, and the potentially scattered data-record accesses. Because
For a bounded range
S7 — Conjunctive Selection
For a condition
use the cheapest access path for one condition
↓
retrieve its candidate records
↓
test every remaining condition in memoryIf several secondary indexes exist, each can produce a set of record IDs. Intersecting those sets before reading data pages can reduce the number of records retrieved, although the optimizer must include all index and data-page accesses in its estimate.
S8 — Composite Index
A composite index can serve a conjunction when its indexed attribute sequence matches the predicates. Its cost follows the corresponding index type:
S9 — Bitmap Index
For low-cardinality attributes, the optimizer reads a bitmap for each equality value and combines the bit vectors in memory. A bitmap for a relation of
Bitmap access is particularly useful when several conditions can be combined with fast bitwise AND, OR, or NOT operations before any data record is fetched.
S10 — Functional Index
A functional index stores the result of an expression over one or more attributes. If a query predicate uses the same expression, its access cost is estimated like the corresponding secondary index in
Estimates are comparisons, not guarantees
The formulas describe simplified worst-case or average behavior. Buffer contents, correlation between predicates, record clustering, pointer-list organization, skew, and current table size can all change the actual number of I/O operations.
19.4.1 Example of Selection Optimization
Suppose EMPLOYEE has:
The available access paths and statistics are:
| Attribute | Access path | Statistics |
|---|---|---|
Salary | Clustering index | |
Ssn | Secondary index on a key | |
Dno | Secondary index on a nonkey | |
Sex | Secondary index on a nonkey |
Assuming uniform distributions:
OP1 — Equality on a key
An average linear search costs
The optimizer therefore chooses the secondary index.
OP2 — Range on a nonclustering index
The scan costs
The optimizer chooses the linear scan. This illustrates why a range-capable B⁺-tree is not necessarily the cheapest access path.
OP3 — Equality on a nonkey
The scan again costs
The optimizer chooses the index.
OP4 — Conjunctive condition
Each condition offers a possible first access path:
| First access path | Estimated cost |
|---|---|
| Linear scan | |
Secondary index for Dno = 5 | |
Clustering index for Salary > 30000 | |
Secondary index for Sex = 'F' |
The optimizer retrieves the 80 expected candidates through the Dno index, then checks Salary > 30000 and Sex = 'F' in memory. Choosing the predicate with the smallest estimated retrieval cost avoids both a full scan and thousands of scattered accesses through the low-selectivity Sex index.
The estimate for Sex also shows why uniform-distribution assumptions can be misleading. If the proportions differ substantially, a histogram is needed to estimate each value accurately.
Cost-Based Choice
A query optimizer enumerates applicable access paths, computes their estimated costs, and retains the cheapest candidate. For a single selection this comparison is small; for multi-relation queries, the same idea produces a much larger search space of access paths, join algorithms, and join orders. Dynamic programming can avoid solving the same subproblem repeatedly and will become especially important when optimizing join order.