Understanding SQL Indexes and Query Performance

Part 4 of 16 · ~3 min

Clustered vs. Non-Clustered Indexes

idx_emp_dept is a non-clustered index — a separate structure that points back at the table. Before we can make the pay-band screen faster, we need the other kind, because the difference determines what "points back at the table" actually costs.

• A clustered index dictates the actual on-disk order of the table's rows — its leaf level isn't a set of pointers back to anything; the leaf level is the row data. A table gets exactly one of these, and the reason is unavoidable: there's only a single sequence the rows can sit in at any given moment.
• A non-clustered index (a secondary index) is its own sorted structure — it holds the indexed columns and, for each one, a reference that leads back to where the real row lives. You can build as many of these as you're willing to pay for.

Which one your primary key gets is an engine decision, and it differs enough to matter:

• SQL Server and MySQL/InnoDB make the primary key clustered automatically. In InnoDB, Employees.id being the primary key means the table is a B-tree keyed on id.
• SQLite does the same thing for our schema, and the reason is a specific quirk worth knowing: a column declared exactly INTEGER PRIMARY KEY becomes an alias for the table's internal rowid, so Employees is physically stored ordered by id.
• Postgres skips this entirely. Its primary key is nothing more than a regular unique index, and the order rows happen to sit in on disk has nothing to do with it. Running CLUSTER will reorder the table once, as a one-off rewrite, but nothing keeps that order in place as rows keep changing. Left alone, a Postgres table's row order just reflects insertion history plus whatever vacuuming has since rearranged.

Now the consequence, which is where this stops being trivia. A non-clustered index only holds the columns you named. When a query needs a column that is not in there, the engine has to go and get it — one extra trip to the actual row, per row. That trip is a key lookup (SQL Server calls it a key lookup or bookmark lookup; Postgres surfaces the same idea in a bitmap heap scan's heap fetches).

The pay-band screen triggers exactly this, because it displays three columns and our index holds one:

CREATE INDEX idx_emp_dept ON Employees (dept);

-- Locate the matching rows      → the index does this well
-- Fetch name and salary for each → the index cannot do this at all
SELECT dept, name, salary FROM Employees WHERE dept = 'Facilities';

SQLite's plan for that, on the code lab schema, is:

SEARCH Employees USING INDEX idx_emp_dept (dept=?)

That reads like a clean win, and it is hiding something. SEARCH ... USING INDEX means the index found the rows. It does not mean the index answered the query. For each of the 6,200 matches, the engine now takes the row pointer from the index entry and goes and reads that row out of the table to collect name and salary.

Here is why that is worse than it sounds. The index walk is sequential — neighbouring entries sit on neighbouring pages. The lookups are not. The rows those 6,200 entries point to are scattered arbitrarily across the table, in id order, which has nothing to do with dept order. So the pattern is: read one index page sequentially, then jump to a random table page, then jump back, 6,200 times. Random reads are the expensive kind.

Past a certain number of matching rows, those lookups dominate the query so completely that the engine would have been better off ignoring the index and scanning the table start to finish. That is not a hypothetical — it is precisely the decision the optimizer makes for dept = 'Sales', and it is the answer to the surprise from chapter 1. Chapter 7 states it exactly; we need two more pieces of machinery first.

First, though, there is a way to make the lookups disappear entirely.