Skip to content

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 X and an attribute A, this section uses:

SymbolMeaning
CSiEstimated block accesses for selection method Si
rXNumber of records in X
bXNumber of blocks occupied by X
bfrXBlocking factor, or records per block
slASelectivity of a condition on A
sASelection cardinality, slArX
xANumber of levels in the index on A
bI1ANumber of first-level blocks in that index
NDV(A,X)Number of distinct values of A in X

Relation and attribute subscripts are omitted below when their meaning is clear.

Cost Formulas for Selection Methods ​

A file scan works for every selection condition. If all blocks must be examined, its cost is:

CS1a=b

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:

CS1b=b2

The unsuccessful-search cost remains b because the whole file must be checked.

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:

CS2=⌈log2⁡b⌉+⌈sbfr⌉−1

For equality on a unique key, s=1, so the estimate reduces to approximately ⌈log2⁡b⌉.

S3a — Primary Index for One Record ​

A primary index is traversed from its root to a leaf, after which one data block is read:

CS3a=x+1

S3b — Hash Key for One Record ​

Static or linear hashing usually retrieves the target bucket in one block access:

CS3b≈1

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 A>v on an ordering key, the index finds the first qualifying record and the ordered data file is scanned from there. If half of the file is assumed to qualify:

CS4=x+b2

This is only a rough average. A histogram can estimate the qualifying fraction and replace b/2 with a more realistic number of data blocks.

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:

CS5=x+⌈sbfr⌉

The formula assumes that the s qualifying records are packed according to the relation's blocking factor.

S6 — Secondary B⁺-Tree Index ​

For equality on a unique secondary key, the index identifies one record:

CS6,key=x+1

For equality on a nonkey attribute, qualifying records may be scattered across the file. A worst-case estimate is:

CS6a=x+1+s

Here the extra block contains the record-pointer list, and the estimate assumes every one of the s records occupies a different data block. Some examples simplify this to x+s when pointer-list I/O is ignored or stored with the leaf entry.

For a range that is expected to qualify half the records, the optimizer may estimate:

CS6b=x+bI12+r2

The three terms represent the index traversal, the qualifying part of the leaf level, and the potentially scattered data-record accesses. Because r/2 can be much larger than b, a sequential scan may be cheaper even though the index is usable.

For a bounded range v1<A<v2, a histogram should estimate s first. The optimizer then prices the index according to whether A is unique and whether the data is clustered on A.

S7 — Conjunctive Selection ​

For a condition c1∧c2∧⋯∧cn, the optimizer can use a scan or choose one indexed condition to retrieve candidate records. It checks the remaining conditions in memory:

text
use the cheapest access path for one condition
                 ↓
retrieve its candidate records
                 ↓
test every remaining condition in memory

If 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: S3a for a unique primary lookup, S5 for clustered matches, or S6a for nonclustered matches.

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 r records contains r bits, or r/8 bytes. After identifying the qualifying positions, a worst-case estimate may require up to s data-block accesses to retrieve s scattered records.

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 S6.

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:

rE=10,000,bE=2,000,bfrE=5

The available access paths and statistics are:

AttributeAccess pathStatistics
SalaryClustering indexxSalary=3, sSalary=20
SsnSecondary index on a keyxSsn=4, sSsn=1
DnoSecondary index on a nonkeyxDno=2, bI1,Dno=4, NDV(Dno,EMPLOYEE)=125
SexSecondary index on a nonkeyxSex=1, NDV(Sex,EMPLOYEE)=2

Assuming uniform distributions:

sDno=10,000125=80,sSex=10,0002=5,000

OP1 — Equality on a key ​

σSsn=′123456789′(EMPLOYEE)

An average linear search costs bE/2=1,000 block accesses. The unique secondary index costs:

CS6=xSsn+1=4+1=5

The optimizer therefore chooses the secondary index.

OP2 — Range on a nonclustering index ​

σDno>5(EMPLOYEE)

The scan costs 2,000. Under the rough assumption that half the records qualify, using the secondary index costs:

CS6b=xDno+bI1,Dno2+rE2=2+2+5,000=5,004

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 ​

σDno=5(EMPLOYEE)

The scan again costs 2,000. Ignoring a separate pointer-list block as the textbook example does, the secondary-index estimate is:

CS6a=xDno+sDno=2+80=82

The optimizer chooses the index.

OP4 — Conjunctive condition ​

σDno=5 ∧ Salary>30000 ∧ Sex=′F′(EMPLOYEE)

Each condition offers a possible first access path:

First access pathEstimated cost
Linear scan2,000
Secondary index for Dno = 52+80=82
Clustering index for Salary > 300003+(2,000/2)=1,003
Secondary index for Sex = 'F'1+5,000=5,001

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.

Built with ❤️ and curiosity