Composite & Covering Indexes: Maximizing Index-Only Scans and Avoiding Table Lookups

A high-traffic e-commerce search service runs the following query 2,000 times per second:

SELECT id, status, total_amount 
FROM orders 
WHERE customer_id = 45012 AND status = 'SHIPPED';

The database administrator created a single-column index on customer_id.

Despite the index, database disk I/O metrics show thousands of random NVMe block reads per second, and API response times hover around 350 milliseconds.

When the team updates the index strategy to a Composite Covering Index:

CREATE INDEX idx_cust_status_amt ON orders (customer_id, status, total_amount);

Latency drops instantly from 350 milliseconds down to 1.8 milliseconds, and disk read I/O falls to zero.

What internal B+ Tree mechanisms explain this 200x performance difference?

---

1. Anatomy of a Composite Index

A single-column index builds a B+ Tree ordered by one value. A Composite Index (multi-column index) creates a single B+ Tree whose search keys contain an ordered tuple of multiple column values—for example, (customer_id, status, total_amount).

Lexicographical Sorting Order

Inside the B+ Tree index page, keys are stored in strict Lexicographical Order:

1. Keys are sorted primarily by Column 1 (customer_id).
2. If two records share the exact same Column 1 value, they are sorted secondarily by Column 2 (status).
3. If Column 1 and Column 2 are identical, records are sorted tertiarily by Column 3 (total_amount).

B+ Tree Leaf Node Entry Structure:
+-------------------+-------------------+-------------------+-------------------+
| customer_id (INT) | status (VARCHAR)  | total_amount(DEC) | PRIMARY KEY (id)  |
+-------------------+-------------------+-------------------+-------------------+
| 45012             | 'CANCELLED'       | 45.00             | 1002              |
| 45012             | 'SHIPPED'         | 120.50            | 8401              |
| 45012             | 'SHIPPED'         | 310.00            | 9104              |
| 45013             | 'PENDING'         | 15.00             | 1003              |
+-------------------+-------------------+-------------------+-------------------+

Notice that within the subset where customer_id = 45012, the status values 'CANCELLED' and 'SHIPPED' are arranged in sorted sequence.

---

2. The Leftmost Prefix Rule

Because B+ Tree search navigation begins at the root node and compares keys sequentially from left to right, a composite index on (A, B, C) can only be used if the query predicate contains the Leftmost Columns of the index definition.

Valid vs Invalid Index Usages for KEY (A, B, C)

Query Predicate	Can Use Index (A, B, C)?	Index Range Columns Used
WHERE A = 1	Yes	Uses column A
WHERE A = 1 AND B = 2	Yes	Uses columns A, B
WHERE A = 1 AND B = 2 AND C = 3	Yes	Uses columns A, B, C
WHERE B = 2 AND C = 3	No (Full Table/Index Scan)	None (Missing leftmost column A)
WHERE C = 3	No (Full Table/Index Scan)	None (Missing leftmost column A)
WHERE A = 1 AND C = 3	Partial	Uses column A (Cannot use C directly for index search)

The Range Condition Trap

A critical rule in multi-column indexing: If a query predicate uses a range comparison (>, <, BETWEEN, LIKE 'prefix%'), the B+ Tree index search stops using subsequent index columns to the right!

Consider an index defined as KEY (dept_id, salary, age) and the query:

SELECT * FROM employees 
WHERE dept_id = 10 AND salary > 80000 AND age = 35;

1. dept_id = 10: Exact equality. The engine navigates to dept_id = 10 in the tree.
2. salary > 80000: Range query. The engine finds the starting point where salary exceeds 80,000.
3. age = 35: Trapped! Because salary values span a range across leaf pages, age is no longer sorted sequentially across those pages. The engine cannot use the B+ Tree to jump directly to age = 35. It must scan all leaf nodes where salary > 80000 and evaluate age = 35 row by row.

Optimization Rule: Place exact equality columns (=) first in the composite index definition, and place range columns (>, <) last!

---

3. Covering Indexes: Eliminating Clustered Index Lookups

When a secondary index does not contain all columns requested by a SELECT statement, the storage engine must execute a Secondary Index Lookup followed by a Clustered Index Lookup (Bookmark Lookup):

Step 1: Navigate Secondary Index (idx_customer_id)
        Find PK id = 8401
             |
             v  (Random Disk I/O Access!)
Step 2: Navigate Primary Clustered Index B+ Tree
        Fetch full row page for id = 8401 to read 'status' and 'total_amount'

If a query matches 10,000 secondary index entries, the engine performs 10,000 separate clustered index point lookups—causing thousands of random memory page reads.

The Covering Index Solution

A Covering Index is a secondary index that contains every single column referenced by the SQL query (in the SELECT, WHERE, JOIN, and GROUP BY clauses).

When a query is satisfied by a covering index, the storage engine reads requested values directly from the secondary index leaf node and skips the clustered index lookup entirely!

-- Query:
SELECT customer_id, status, total_amount 
FROM orders 
WHERE customer_id = 45012 AND status = 'SHIPPED';

-- Covered by Index:
CREATE INDEX idx_cust_stat_amt ON orders(customer_id, status, total_amount);

[ Secondary Index Leaf Node ]
  Key: (customer_id=45012, status='SHIPPED', total_amount=120.50)
        |
        v  (All data present directly in secondary leaf node!)
  [ Return Result Immediately to Server Layer ]

Verifying Covering Indexes in EXPLAIN

Run EXPLAIN on your query and check the Extra column:

EXPLAIN SELECT customer_id, status, total_amount 
FROM orders WHERE customer_id = 45012 AND status = 'SHIPPED';

• If Extra displays Using index, the query executed an Index-Only Scan (Covering Index). Zero clustered table page lookups were performed!
• If Extra displays Using index condition, Index Condition Pushdown (ICP) was used (evaluating filters inside the secondary index before fetching table rows).
• If Extra is blank, the engine performed full clustered table page lookups for every matching row.

---

Summary & Next Steps

Composite and covering indexes are among the most effective query tuning mechanisms in relational databases:

• Composite index entries are sorted lexicographically from left to right.
• The Leftmost Prefix Rule requires queries to reference columns in exact index definition order.
• Range predicates (>, <) break prefix matching for all trailing index columns.
• Covering Indexes allow engines to serve queries entirely within secondary index pages, eliminating random disk I/O from clustered table lookups.

In the next article, we open Module 5 with a deep dive into MySQL Architecture: Server Layer vs Pluggable Storage Engines.

References & Further Reading

1. Schwartz, B., Zaitsev, P., & Tkachenko, V. (2021). High Performance MySQL: Optimization, Backups, and Replication (4th Edition). O’Reilly Media.
2. O’Neil, P., & Qu, D. (1997). Improved Query Performance with Variant Indexes (Bitmap Indexes). ACM SIGMOD Record, 26(2), 38–49.

---