Index Design
▶ DRILLThe Three-Star Index
Lahdenmäki and Leach's Relational Database Index Design and the Optimizers (Wiley, 2005) defines an ideal index for a SELECT as one that earns three stars. The stars are awarded by satisfying three criteria:
| Star | Criterion |
|---|---|
| ★ First | All equality predicate columns are in the index. |
| ★★ Second | The range predicate column — or the ORDER BY column when there is no range predicate — immediately follows the equality columns. This both minimises the leaf-page scan and eliminates any explicit Sort operator from the plan. |
| ★★★ Third | All columns referenced in the SELECT are in the index (covering — no bookmark lookup). |
A three-star index does three things: it seeks to the exact starting row, scans the minimum possible slice of leaf pages, and returns all needed columns without touching the table. Zero wasted I/Os. As a bonus, when the ORDER BY column is that second-star column, rows emerge from the index already in sorted order — SQL Server can skip the blocking Sort operator entirely. A Sort is a blocking operator: it must consume every input row before it can emit the first output row. Eliminating it means the query can stream results to the client as each row is read off the index, rather than accumulating the entire result set in memory first. For large result sets this is the difference between a query that starts returning rows in milliseconds and one that makes the client wait for the full sort to complete.
Equality Predicates: Order Doesn't Matter
For a query with only equality predicates in the WHERE clause — WHERE a = 1 AND b = 2— both (a, b) and (b, a) allow the optimizer to seek to a single contiguous leaf-page range. The number of rows read is identical regardless of column order. Think of it as a phonebook: looking up "Smith, John" works the same whether you index by last name then first name, or the reverse — you land on the same entries.
When all predicates are equalities, column order in the index is irrelevant to seek efficiency. You can order by selectivity, update frequency, or string length — it won't change the I/O cost for this query.
Range Predicates: Order Matters Absolutely
Introduce one inequality — WHERE a = 1 AND b > 100 — and column order becomes critical. The B-tree is sorted by its key columns left-to-right. With index (a, b), all rows matching a = 1 are physically adjacent, and within them b is sorted. The engine seeks to [a=1, b>100] in a single operation and scans forward through only the qualifying rows.
With index (b, a), the engine can seek to b > 100 — but after that point, rows are sorted by b, not a. The predicate a = 1becomes a residual filter: every row in the range scan must be fetched and tested. On a large table with low selectivity for b, this is the difference between reading 4 rows and reading 4,000.
Rule: equality columns first, range column last among the matching columns. The range column marks the point where seeking ends and scanning begins — everything to its right in the key is unordered relative to the range condition and contributes nothing to the seek.
OR Predicates
An OR predicate breaks the single-seek model entirely. There is no contiguous key range in any single index that satisfies both a = 1 OR b = 2 — the matching rows are scattered across two different orderings. The optimizer's solution is to rewrite OR as UNION ALL: two separate index seeks (one per branch), results merged with duplicate removal. Each branch can use its own optimal index independently.
This is why OR conditions in hot query paths deserve explicit attention. Two index operations plus a merge step is more expensive than one — and on large tables with poorly selective OR branches, the optimizer may abandon the index plan entirely and fall back to a full scan.
dbo.sales_order from the shared South Park schema.↓ south-park-orders.sql— includes the order_status column added for this drill, plus all index candidates (ix_design_a through ix_design_f) and demo queries with SET STATISTICS IO ON.SELECT order_id, product_name, amount FROM dbo.sales_order WHERE customer_name = 'Cartman' AND order_status = 'pending'
Both predicates are equality conditions. Column order in the index is irrelevant — both orderings seek to the same slice. Add INCLUDE to earn the third star.
CREATE INDEX ix_a ON dbo.sales_order (customer_name, order_status)
| customer_name | order_status | product_name | amount | engine action |
|---|---|---|---|---|
| Butters | delivered | Marjorine Wig | $14.00 | |
| Butters | delivered | Prof Chaos Lab | $450.00 | |
| Butters | pending | Clyde Costume | $18.50 | |
| Butters | pending | Evil Laugh Track | $3.99 | |
| Butters | shipped | Chaos Costume | $28.00 | |
| Cartman | cancelled | Mint Babe | $6000.00 | |
| Cartman | cancelled | ManBearPig Trap | $300.00 | |
| Cartman | delivered | Cheesy Poofs XL | $12.99 | |
| Cartman | delivered | Cheesy Poofs 12-Pack | $89.99 | |
| Cartman | delivered | Cheesy Poofs Party Box | $199.99 | |
| Cartman | pending | Cheesy Poofs 3-Pack | $34.99 | ← qualify |
| Cartman | pending | Scott Tenorman Hair | $0.50 | ← qualify |
| Cartman | shipped | Asskicker 5000 | $149.99 | |
| Cartman | shipped | Conspiracy Board | $75.00 | |
| Kenny | cancelled | Coffin | $200.00 | |
| Kenny | delivered | Halloween Costume | $22.00 | |
| Kenny | delivered | Resurrection Potion | $999.00 | |
| Kenny | pending | Fake ID | $4.99 | |
| Kenny | pending | Life Insurance | $500.00 | |
| Kyle | cancelled | Ike Return Ticket | $350.00 | |
| Kyle | delivered | Ike Action Figure | $9.99 | |
| Kyle | delivered | Freedom Fireworks | $55.00 | |
| Kyle | pending | Bar Mitzvah Candles | $8.50 | |
| Kyle | shipped | Torah | $29.99 | |
| Stan | cancelled | Breakup Letter | $1.00 | |
| Stan | delivered | Dog Turd | $0.01 | |
| Stan | pending | Wendy Fanfic | $0.99 | |
| Stan | pending | Hippie Repellent | $12.00 | |
| Stan | shipped | Guitar Hero | $49.99 | |
| Stan | shipped | Skateboard | $89.00 |
How Column Order Shapes the Leaf Level
The rule — equality columns first, range column last — isn't an arbitrary convention. It's a consequence of how a B+tree physically stores its keys. The leaf level is a sorted sequence of pages. The tree can seek to any contiguous range within that sequence in a single operation. When you put the equality column first, all rows for that value cluster together on adjacent pages; the range column then sorts them within that cluster, so the qualifying slice is a single contiguous run.
Flip the column order and the equality column becomes a residual filter— it's applied after the seek, row by row, against every row the range scan returns. The explorer below makes this concrete: pick an index, observe which rows the engine touches, and compare the leaf-read count between the two orderings.
SELECT order_id, product_name, amount FROM dbo.sales_order WHERE customer_name = 'Cartman' AND order_date > '2024-06-01'
CREATE INDEX ix_cust_date ON dbo.sales_order (customer_name, order_date)