Lookup Acceleration

Everything we've discussed about indexes—their definition, search keys, and entries—serves a single purpose: accelerating data lookup. An index that cannot find data faster than a table scan is worthless. Understanding exactly how indexes achieve lookup acceleration is fundamental to leveraging them effectively.

Lookup acceleration isn't magic. It follows from well-understood computer science principles: reducing search space, exploiting ordering, and trading space for time. By the end of this page, you'll understand precisely why an index lookup completes in milliseconds while a table scan takes minutes—not as a mysterious database optimization, but as the predictable outcome of algorithmic design.

To appreciate what indexes provide, we must first understand what happens without them. Consider a table with N rows stored as a heap file (unsorted, unindexed). To find a specific record:

SELECT * FROM employees WHERE employee_id = 12345;

Without an index, the database must:

1. Start at the first page of the table
2. Read each page into memory
3. Examine every record on each page
4. Check if employee_id = 12345
5. Continue until the record is found or all pages are exhausted

This is fundamentally O(N) — the time grows linearly with data size.

The Scale Problem:

Linear time sounds acceptable until you consider real-world scale:

The Impossibility of Linear Scale:

For interactive applications, queries must complete in tens or hundreds of milliseconds. At 10 million rows, a 100-second table scan is unacceptable. At 1 billion rows, a 2.8-hour table scan is absurd.

Moreover, linear scan has no parallelization benefit for selectivity. Whether you're looking for 1 row or 1 million rows, you must still examine every page. The only parallel optimization is reading multiple pages simultaneously—which improves throughput but not latency for single queries.

Indexes break this linear dependency completely.

The most common index structure—the B+-tree—achieves O(log N) lookup time by organizing entries in a balanced tree. This is the fundamental acceleration mechanism that makes modern databases possible.

The Key Insight: Divide and Conquer

Instead of examining all N entries, a tree structure allows us to:

1. Examine a root node with M pointers to child subtrees
2. Determine which child subtree contains our target
3. Move to that child (eliminating N - N/M entries from consideration)
4. Repeat until we reach a leaf containing the actual entry

With each step, we eliminate a fraction of the search space. The number of steps needed is the tree's height, which is log(N) for a balanced tree.

B+-Tree Height Calculation:

For a B+-tree with:

• Page size P (typically 8-16 KB)
• Internal node fanout F (typically 200-500 for integer keys)
• N total records

The height H is approximately:

H = ⌈log_F(N)⌉

Example:

• 100 million records (N = 10⁸)
• Fanout of 300 (F = 300)
• Height = log₃₀₀(10⁸) = log(10⁸)/log(300) ≈ 3.23

This means 4 page reads to locate any record among 100 million. And because root and high-level internal nodes are frequently accessed, they're typically cached in memory, reducing I/O further.

The Fanout Advantage:

B+-trees achieve high fanout (branching factor) because:

• Each internal node contains many keys and pointers (not just 2 like binary trees)
• Large page sizes (8-16 KB) hold many small entries
• Keys in internal nodes can be truncated to separators

A binary tree with 100 million nodes is 27 levels deep. A B+-tree with 100 million entries is 4 levels deep. This difference—enabled by fanout—is why B+-trees dominate in databases.

Let's trace exactly what happens during an index lookup. Understanding this process helps diagnose performance issues and reason about expected costs.

Query:

SELECT name, salary FROM employees WHERE employee_id = 5042;

Assumptions:

• B+-tree index on employee_id (primary clustered index)
• Tree height = 3 (root + 2 internal levels + leaves)
• Root and level-1 pages cached in buffer pool
• Target record exists

Cost Analysis:

Compare this to a table scan that would read 100,000 pages at 1ms each: 100 seconds. The index reduced latency by a factor of 5,000-50,000.

Key Observations:

• Most lookups cost only 1-2 disk I/Os (upper levels cached)
• The number of I/Os is predictable: approximately height - (cached levels)
• Each I/O retrieves exactly one page (no unnecessary data read)
• Within-page search uses binary search (O(log entries_per_page))

Indexes accelerate not just point lookups but also range queries. The mechanism differs slightly but remains fundamentally efficient.

Query:

SELECT * FROM orders 
WHERE order_date BETWEEN '2024-01-01' AND '2024-01-31';

Range Scan Algorithm:

1. Find Start Point: Use tree traversal to locate the first entry where order_date >= '2024-01-01'

2. Sequential Scan: From that point, scan forward through leaf pages (they're linked!) until order_date > '2024-01-31'

3. Terminate: Stop when the range is exhausted

The beauty of B+-trees: leaf pages are linked in a doubly-linked list. Once we find the range start, we scan sequentially—no more tree traversals needed.

Cost Analysis for Range Queries:

If the range contains K matching records spread across P pages:

Why This Beats Table Scan:

A table scan reads ALL pages regardless of how few records match. A range scan reads:

• A few pages to find the start (log N)
• Only the pages containing matching records (P)

If your range is 1% of the table, you read ~1% of the pages (plus the initial lookup cost). This scales beautifully.

Example:

• Table has 10 million orders across 100,000 pages
• January 2024 has 100,000 orders across 1,000 pages
• Table scan: 100,000 page reads
• Range scan: 4 pages (tree traversal) + 1,000 pages (range) = 1,004 page reads
• 100× improvement

While B+-trees achieve O(log N) lookup, hash indexes can achieve O(1) average-case lookup—constant time regardless of data size. This seems miraculous but comes with significant trade-offs.

Hash Index Mechanism:

1. Apply hash function to search key: bucket = hash(key) mod bucket_count
2. Read the bucket page(s)
3. Scan entries within bucket for exact match
4. Return matching record location(s)

Why O(1)?

The hash function directly computes where to look—no traversal needed. Regardless of whether the table has 1,000 or 1 billion rows, the same number of steps (1-2 page reads) finds the target bucket.

When to Use Hash Indexes:

Hash indexes are ideal for:

• Pure equality lookups on high-cardinality columns
• Primary key lookups (when range queries aren't needed)
• Join key lookups in hash join algorithms
• In-memory databases (where random access has no penalty)

They are poor choices for:

• Range queries of any kind
• Ordered access requirements
• Low-cardinality columns (many collisions per bucket)
• Prefix or pattern matching

PostgreSQL Example:

-- Create a hash index (PostgreSQL syntax)
CREATE INDEX idx_user_email_hash ON users USING hash (email);

-- This query uses the hash index
SELECT * FROM users WHERE email = 'user@example.com';

-- This query CANNOT use the hash index (range predicate)
SELECT * FROM users WHERE email > 'a' AND email < 'b';

The ultimate acceleration is avoiding table access entirely. If the index contains all columns the query needs, the database can answer the query from the index alone—an index-only scan (also called a covering index scenario).

Traditional Index Access:

1. Search index → Find RID(s)
2. Use RID to fetch record from table → One I/O per record potentially
3. Extract requested columns

Index-Only Scan:

1. Search index → Find matching entries
2. Extract columns directly from index entries
3. Done (no table access)

The savings can be enormous, especially when:

• Many records match the predicate
• Records are scattered across many pages
• Only a few columns are needed in the result

Creating Covering Indexes:

-- Query we want to optimize
SELECT order_id, total_amount 
FROM orders 
WHERE customer_id = 12345;

-- Index that enables index-only scan
CREATE INDEX idx_orders_covering 
ON orders (customer_id) 
INCLUDE (order_id, total_amount);

The INCLUDE clause (or equivalent) adds columns to the leaf entries without making them part of the search key. This means:

• The index is still ordered by customer_id only
• But leaf entries include order_id and total_amount
• Queries selecting only these columns can be answered from the index

Space-Performance Trade-off:

Covering indexes increase index size. Each leaf entry now includes additional columns. For a heavily-used query pattern, this trade-off is usually worthwhile. For rarely-used queries, the space cost may not justify the benefit.

Indexes are powerful but not omnipotent. Understanding when indexes cannot help—or actively hurt—is as important as understanding when they help.

Low Selectivity Predicates:

When a predicate matches most rows, index lookup is slower than table scan:

• Each matching row requires a separate pointer chase (random I/O)
• Table scan reads pages sequentially (faster I/O pattern)
• The "breakeven point" is typically 10-30% of rows

Example:

-- Index probably helps (assuming 'suspended' is rare)
SELECT * FROM accounts WHERE status = 'suspended';

-- Index probably hurts (most accounts are active)
SELECT * FROM accounts WHERE status = 'active';

Non-Sargable Predicates:

Some predicates cannot use indexes regardless of selectivity. These are called non-sargable (not Search ARGument ABLE):

-- Non-sargable: Function applied to column
WHERE UPPER(email) = 'USER@EXAMPLE.COM'

-- Sargable alternative (if stored in uppercase) 
WHERE email = 'USER@EXAMPLE.COM'

-- Non-sargable: Leading wildcard
WHERE name LIKE '%smith'

-- Sargable: Trailing wildcard
WHERE name LIKE 'smith%'

-- Non-sargable: Expression on column
WHERE salary * 1.1 > 100000

-- Sargable alternative
WHERE salary > 100000 / 1.1

Wrong Column Order (Composite Index):

A composite index on (A, B, C) cannot accelerate queries that filter only on B or C.