Understanding SQL Indexes and Query Performance

Part 8 of 16 · ~3 min

Index Selectivity and Cardinality

This is the chapter that explains the surprise from chapter 1 — the one where we indexed dept, watched dept = 'Facilities' go from four seconds to eight milliseconds, and then watched dept = 'Sales' refuse to improve at all.

Two terms, because they get used interchangeably and are not the same thing.

Cardinality is a property of a column: how many distinct values it holds. Employees.id has 2.4 million distinct values — maximum cardinality. Employees.dept has 38. That is all cardinality means.

Selectivity is a property of a predicate: what fraction of the table it eliminates. WHERE id = 847213 eliminates everything but one row — about as selective as a condition can be. WHERE dept = 'Sales' eliminates 82% of the table and keeps 431,000 rows, which is not selective at all.

Indexes pay off in proportion to selectivity, and the reason is the key lookup from chapter 3. An index seek costs a descent plus a walk. But if the index is not covering, each matching row then costs a scattered random read back into the table. Multiply a small per-row cost by a large number of rows and you eventually pass the cost of just reading the whole table sequentially — and sequential reads are much cheaper per row than random ones, so the crossover arrives far sooner than you would guess. Most engines flip somewhere in the range of a few percent of the table.

Now hold the two departments up against that:

Same column. Same index. Same query shape. Opposite decisions. Nothing is broken in the second row; the optimizer costed both plans and the scan genuinely won. This is the single most useful thing to understand about indexes, and it is why "is this column indexed?" is not actually a well-formed performance question. The well-formed question is "is this predicate selective enough, on this data, for the index to pay for itself?"

It is also why a low-cardinality column is a poor index candidate on its own. A boolean, a three-value status column, our 38 departments — indexing one and querying it alone often buys nothing, because no single value is rare enough. But note the phrase "on its own," because it is doing real work: dept is the leftmost column of idx_emp_dept_salary_name and that index is the reason the pay-band screen is fast. A low-cardinality column can be an excellent leading column in a composite index, where its job is not to eliminate the whole table by itself but to group the rows so a more selective second column can finish the job. (dept, salary) gets the Sales block in one descent and then seeks within it on salary, which is selective. The composite index rescues exactly the case where the single-column index failed.

One caveat for anyone trying to reproduce any of this in the code lab: with five rows, the optimizer will pick a scan essentially no matter what indexes exist, because reading five rows is cheaper than anything else it could possibly do. The plans quoted throughout this reference are real SQLite output on that schema, and they show which access path the engine chose — but the seek-versus-scan crossover itself only becomes visible on a table large enough for the arithmetic to matter.