Chapter 14 · Indexes and Query Execution
Why Indexes Work: Search Structures and Selectivity
An index is a second, deliberately ordered representation of table data. It can replace broad scanning with a small number of tree searches—but only when the query, data distribution, and index order align.
Learning outcomes
Connect physical access work to query performance
Explain why an ordered B-tree can avoid examining most table rows.
Estimate index search depth with logarithmic reasoning rather than assuming constant-time lookup.
Compute predicate selectivity and distinguish selective from nonselective filters.
Recognize when a full table scan is cheaper than an index lookup.
Use SQLite EXPLAIN QUERY PLAN to observe scan-to-search changes after creating an index.
An index is a second access structure
A table stores complete rows. An index stores ordered key values plus a row locator or primary-key reference. A lookup first navigates the index, then—unless the index already contains every required output column—uses the locator to fetch the table row.
The optimizer chooses this route only when its estimated total work is cheaper than scanning the table.
Why tree search scales
If an index page has an effective branching factor b and contains N keys, the idealized search depth is approximately:
Real costs also include cache behavior, page reads, row lookups, comparison cost, and concurrency. The important result is that a balanced tree grows in height slowly even when the row count grows rapidly.
| Rows | Illustrative branching factor | Approximate levels |
|---|---|---|
| 1,000 | 100 | 2 |
| 1,000,000 | 100 | 3 |
| 1,000,000,000 | 100 | 5 |
A scan can read pages sequentially, while many scattered index-to-table lookups can be random. For a predicate that returns most rows, the scan may be faster despite its linear row count.
Build the Chapter 14 laboratory
PRAGMA foreign_keys = ON;DROP TABLE IF EXISTS sales_order;DROP TABLE IF EXISTS customer;CREATE TABLE customer ( customer_id INTEGER PRIMARY KEY, email TEXT NOT NULL UNIQUE, region TEXT NOT NULL CHECK (region IN ('north','south','east','west')), joined_at TEXT NOT NULL) STRICT;CREATE TABLE sales_order ( order_id INTEGER PRIMARY KEY, customer_id INTEGER NOT NULL REFERENCES customer(customer_id), status TEXT NOT NULL CHECK (status IN ('pending','processing','paid','cancelled')), ordered_at TEXT NOT NULL, total_cents INTEGER NOT NULL CHECK (total_cents >= 0), channel TEXT NOT NULL CHECK (channel IN ('web','mobile','partner'))) STRICT;WITH RECURSIVE seq(n) AS ( VALUES (1) UNION ALL SELECT n + 1 FROM seq WHERE n < 1000)INSERT INTO customer (customer_id, email, region, joined_at)SELECT n, printf('customer%04d@example.com', n), CASE n % 4 WHEN 0 THEN 'north' WHEN 1 THEN 'south' WHEN 2 THEN 'east' ELSE 'west' END, date('2023-01-01', printf('+%d days', n % 730))FROM seq;WITH RECURSIVE seq(n) AS ( VALUES (1) UNION ALL SELECT n + 1 FROM seq WHERE n < 20000)INSERT INTO sales_order (order_id, customer_id, status, ordered_at, total_cents, channel)SELECT n, ((n * 37) % 1000) + 1, CASE n % 20 WHEN 0 THEN 'pending' WHEN 1 THEN 'processing' WHEN 2 THEN 'cancelled' ELSE 'paid' END, datetime('2025-01-01', printf('+%d hours', n % 8760)), 1000 + ((n * 7919) % 90000), CASE n % 3 WHEN 0 THEN 'web' WHEN 1 THEN 'mobile' ELSE 'partner' ENDFROM seq;The generated data intentionally has two very different distributions: each customer owns about 20 of 20,000 orders, while approximately 85% of orders have status paid. That contrast makes selectivity visible.
Selectivity predicts pruning power
For a predicate P, selectivity is the fraction of rows expected to match:
SELECT COUNT(*) AS total_orders, SUM(customer_id = 417) AS customer_417_rows, SUM(status = 'paid') AS paid_rows, ROUND(1.0 * SUM(customer_id = 417) / COUNT(*), 5) AS customer_selectivity, ROUND(1.0 * SUM(status = 'paid') / COUNT(*), 5) AS paid_selectivityFROM sales_order;A customer equality predicate is highly selective. The paid-status predicate is not. An index on status may still help some queries, especially with ordering or covering, but it is not automatically superior to a scan.
Observe a scan, then an indexed search
EXPLAIN QUERY PLANSELECT order_id, ordered_at, total_centsFROM sales_orderWHERE customer_id = 417 AND ordered_at >= '2025-06-01'ORDER BY ordered_at;Plan: SCAN sales_orderPlan: USE TEMP B-TREE FOR ORDER BYCREATE INDEX IF NOT EXISTS idx_order_customer_dateON sales_order (customer_id, ordered_at);EXPLAIN QUERY PLANSELECT order_id, ordered_at, total_centsFROM sales_orderWHERE customer_id = 417 AND ordered_at >= '2025-06-01'ORDER BY ordered_at;Plan: SEARCH sales_order USING INDEX idx_order_customer_dateConstraint: customer_id = ? AND ordered_at > ?Sort: avoided because index order matches ORDER BYWhat the index actually saves
Candidate reduction
The index narrows 20,000 rows to the small customer/date range before table-row retrieval.
Pre-sorted output
The composite key can emit one customer’s rows in ordered_at order, removing a temporary sort.
Fewer relevant pages
Selective navigation can touch far fewer pages than a full scan.
Fewer predicate checks
Most table rows never reach expression evaluation.
Not free
Each INSERT, UPDATE of an indexed key, and DELETE must also maintain the tree.
When a scan is rational
| Situation | Why scanning can win |
|---|---|
| Predicate returns a large share of the table | Index navigation plus many table lookups can cost more than one sequential pass. |
| Table is tiny | The entire table may fit in a few cached pages. |
| Query needs nearly every column | A noncovering index still requires row fetches for most matches. |
| Statistics are stale or absent | The optimizer may misestimate the match count and choose poorly. |
| Index key does not align with the predicate | The engine may have to scan the index broadly, gaining little. |
Checkpoint
Reason about search work
- Why does an index contain row locators instead of necessarily storing the whole row?
- What does low selectivity mean numerically?
- Why might an index on a Boolean-like status column be weak for a broad report?
- How can one composite index remove both filtering and sorting work?
- Why is “an index is O(log N)” insufficient to prove that it is the fastest plan?
Review the answers
The row locator keeps the ordinary index compact while allowing a table fetch. Low selectivity means a large fraction of rows match. A low-cardinality status often returns too many rows to prune much. A key ordered by the equality columns followed by the range/order column can satisfy both tasks. Real plan cost also includes page access, row fetches, caching, output size, and maintenance—not only tree depth.
Summary and references
- Indexes trade storage and write work for alternative read paths.
- Balanced trees reduce navigation depth logarithmically.
- Selectivity estimates how aggressively a predicate can prune rows.
- Scans remain correct and often optimal for small or broad reads.
- Use query plans to verify the chosen access path.