Understanding SQL Indexes and Query Performance

Part 6 of 16 · ~6 min

Composite Indexes: Column Order Matters

An index on more than one column — a composite or compound index — is still one sorted structure. The thing people underestimate is what "sorted" means when there is more than one column, and getting it wrong is exactly what happened at the end of the last chapter.

Concretely, on the code lab's five rows, here is what idx_emp_dept_covering ON Employees (dept, name, salary) contains:

'HR'    | 'Eve'   | 55000
'IT'    | 'Carol' | 70000
'IT'    | 'Dave'  | NULL
'Sales' | 'Alice' | 50000
'Sales' | 'Bob'   | 60000

Sorted by dept first. Then, within each department, by name. Then, within each identical (dept, name) pair, by salary. It is a single ordering, and the columns are not peers — the first column is the primary sort and every later one only breaks ties inside it.

Think of what the HR team had before this tool existed: a printed roster, grouped into a section per department, and inside each section the people listed alphabetically. That is (dept, name). It is genuinely useful and genuinely limited, and the limits are the same ones the index has.

The leftmost-prefix rule falls straight out of that ordering. An index can only seek on a prefix of its columns, starting from the left:

CREATE INDEX idx_emp_dept_covering ON Employees (dept, name, salary);

-- Seeks efficiently — anchored on the leftmost column
SELECT * FROM Employees WHERE dept = 'Sales';
SELECT * FROM Employees WHERE dept = 'Sales' AND name = 'Bob';

-- Cannot seek — skips the leftmost column
SELECT * FROM Employees WHERE name = 'Bob';
SELECT * FROM Employees WHERE salary > 60000;

With that index in place and no other, those are the plans SQLite produces:

dept = 'Sales'              → SEARCH ... USING COVERING INDEX idx_emp_dept_covering (dept=?)
dept = 'Sales' AND name=... → SEARCH ... USING COVERING INDEX idx_emp_dept_covering (dept=? AND name=?)
name = 'Bob'                → SCAN Employees
salary > 60000              → SCAN Employees

The third line is the roster problem exactly. Somebody says "find Bob" and you know his name but not his department — the roster is no help, because the Bobs are scattered one per section across all 38 departments. Nothing groups them, so you read the whole thing. The index has the identical shape and makes the identical non-choice: a full scan, with a three-column index on the table that happens to contain name.

This is the trap people fall into: you build one composite index across two columns hoping it will accelerate queries on either of them, but only queries anchored on the leading column actually benefit. When both columns genuinely need to stand alone as lookup targets, the fix isn't a composite at all — build two separate indexes instead. Optimizers in most modern engines are smart enough to reach for both of those single-column indexes at once on a query that filters by both — Postgres, for instance, runs a bitmap index scan against each one and intersects the resulting row sets. The result trails a well-chosen composite index in speed, but it still beats a scan by a wide margin.

Now back to our actual problem, because the leftmost-prefix rule is not the whole story. dept is leftmost in idx_emp_dept_covering, and the query still could not seek the salary range or skip the sort. The reason is one level more subtle, and it is the most valuable thing in this chapter:

A composite index can seek through equality columns freely, but the moment it hits a range, the ordering of everything after it stops being usable.

Walk it through on (dept, name, salary) with WHERE dept = 'Facilities' AND salary BETWEEN 60000 AND 90000:

1. dept = 'Facilities' is an equality. The engine descends to where the Facilities entries start. Fine.
2. Inside that block, entries are sorted by name. The query says nothing about name.
3. salary is sorted only inside each (dept, name) pair — meaning inside each individual person. Across the Facilities block as a whole, salary is in no order at all.

So the engine seeks to the department and then has to walk all 6,200 Facilities entries, checking salary on each. It stays covering, so no key lookups — but the range is a filter, not a seek. And because those entries arrive in name order, the ORDER BY salary cannot come along for free either. Hence the temp B-tree.

Swap two columns:

CREATE INDEX idx_emp_dept_salary_name ON Employees (dept, salary, name);

'HR'    | 55000 | 'Eve'
'IT'    | NULL  | 'Dave'
'IT'    | 70000 | 'Carol'
'Sales' | 50000 | 'Alice'
'Sales' | 60000 | 'Bob'

Now, within each department, entries are ordered by salary — and the same query plans like this:

SEARCH Employees USING COVERING INDEX idx_emp_dept_salary_name
  (dept=? AND salary>? AND salary<?)

One line. The seek condition now contains all three predicates: the engine descends to (Facilities, 60000), walks the leaves until salary passes 90000, and stops. The rows come out in salary order because that is the order they are stored in, so ORDER BY salary costs nothing and the temp B-tree is gone. name rides along in the leaf so nothing goes back to the table.

That is the query from the introduction, and that is the four milliseconds. One index, doing four jobs at once: it seeks the department, it seeks the range, it supplies the sort order, and it covers the output.

(One detail in that listing, since salary is the only nullable column in the schema: NULL sorts before every number in SQLite, MySQL, and SQL Server, and after them in Postgres and Oracle. It is a stable, documented ordering in each engine rather than an accident — but it is not the same ordering, so an index-supplied sort involving a nullable column is one of the few places a query can legitimately return rows in a different order on a different engine.)

Choosing column order in a composite index

Generalise what just happened into a rule you can apply without re-deriving it each time. Order the columns of a composite index like this:

1. Equality predicates first — every column your queries compare with =. These can be chained through, each one narrowing inside the last.
2. Then the range or ORDER BY column — the one compared with >, <, BETWEEN, or used for sorting. Exactly one column gets this benefit, because a range destroys the usable ordering of everything after it.
3. Then any remaining columns needed only for covering — they contribute nothing to seeking, they are there so the engine never has to touch the table. If your engine supports INCLUDE, these belong there instead of in the key.

(dept, salary, name) is that rule applied: equality on dept, range-and-sort on salary, name along for coverage.

The common advice is "put the most selective column first," and it is worth being precise about why that is a weaker rule than it looks. Selectivity ordering is a genuine tiebreaker among the equality columns — narrowing hardest first means fewer entries examined at each subsequent step. But it says nothing about ranges, and it actively misleads when applied across the equality/range boundary. salary is far more selective than dept here. Leading with it would be a worse index, because then dept would sit after a range and be unusable for seeking.

And one override that beats both rules: if some queries filter on only one of the columns, that column must go first, selectivity regardless. An index is useless to a query that cannot reach its leftmost column, so a column that needs to work alone has to be the one that works alone.