Cost-Based Optimization

Rule-Based vs Cost-Based

Before cost-based optimizers existed, Oracle ran a rule-based optimizer(RBO) — a fixed hierarchy of 15 access path ranks. A full table scan was rank 15 (worst); a single-row lookup by ROWID was rank 1 (best). The optimizer picked whichever access path had the lowest rank number, regardless of table size, data distribution, or whether the "better-ranked" path would actually read more data.

If you had an index on a column with two distinct values across 10 million rows and filtered on one of them, the RBO used the index — because seeks beat scans on the ranking table. It didn't know you were about to touch 5 million index leaves and 5 million key lookups instead of one sequential scan. It didn't care. The rules were the rules.

Oracle 9i Release 2 (2002) was the last version to fully support the RBO. Oracle 10g (2003) made it unsupported — present but receiving no bug fixes. Oracle 11g formally deprecated it. Modern Oracle has no RBO. SQL Server never shipped a ranked-rules optimizer like Oracle's RBO — it has used cost and statistics since the SQL Server 7.0 rewrite in 1998.

The trade-off was real: RBO was predictable. You knew exactly which plan it would pick because the rules were deterministic. CBO gives better plans on average but introduced a new failure mode: stale statistics → wrong cost estimates → wrong plan. The transition from RBO to CBO was famously painful for Oracle DBAs, who suddenly had to care about statistics freshness. SQL Server DBAs inherited that pain without the nostalgia.

How the Cost-Based Optimizer Works

The query optimizer's job is to take your SQL — a what, not a how — and produce an execution plan that implements it efficiently. It doesn't guarantee the best plan. It finds an acceptably good plan in an acceptably short time. The problem is NP-hard; the optimizer gives up after a while and runs with whatever it has.

The pipeline:

1. Parse: SQL text → abstract syntax tree. Syntax errors live here.
2. Algebrize: bind table and column names to catalog objects, resolve types, build a logical tree. Name resolution errors live here.
3. Simplify: algebraic rewrites — push filters down, flatten subqueries, normalize predicates to canonical form. Obviously bad plans are eliminated before costing begins.
4. Optimize: generate candidate physical plans, cost-estimate each operator, prune the search space, return the cheapest complete plan found before the timeout.

The Cost Formula

SQL Server doesn't publish its cost model, but the structure is straightforward:

Cost(operator) = pages_read × io_cost + rows_processed × cpu_cost

Two things to know about these constants: io_cost is higher for random reads (seeking a scattered page) than for sequential reads (scanning a run of pages), and cpu_cost is tiny compared to either — a row comparison is orders of magnitude cheaper than a disk operation. The optimizer is almost entirely optimizing for I/O.

For the specific decision of table scan vs index seek, the comparison looks like this:

Scan cost  ≈ total_pages × seq_io
Seek cost  ≈ index_levels × rnd_io + (matching_rows / rows_per_page) × rnd_io

The crossover point — where scan becomes cheaper than seek — lands roughly when the predicate matches more than 25–33% of rows. That's the oft-cited "30% rule" for index seek vs scan. The exact threshold varies by row size, index fill factor, and whether the pages are already in the buffer pool, which is why it's a rule of thumb rather than a constant. The optimizer computes it per-query using actual statistics; you get the rule of thumb for free.

Join Order and Cardinality

The optimizer's two main concerns once costing starts are join orderand cardinality. Join order matters exponentially —n tables can be joined in n! orderings, and only some are sane. The optimizer uses dynamic programming with memoization to prune this space. Cardinality — how many rows flow between operators — determines join type: few rows on the inner side → nested loops; large sorted sets → merge join; large unsorted sets → hash join. Get cardinality wrong and you get the wrong join type, which can be catastrophically slower. Getting cardinality wrong is easy, and the next topic explains why.