Part 3 of 8 · 3 min read
How a lookup uses an index
Following a query to its index, and when the database chooses not to use one.
Think of a library catalogue. A reader who knows the author looks at the author drawer and gets a shelf number. A reader who wants "all books with a red cover" has no drawer to open, and must walk the shelves.
A database picks, for each query, which index to use or whether to scan. The relational model leaves this choice to the query planner (the book calls it the query optimizer, module 1). A programmer can ask it to explain its choice. In PostgreSQL and MySQL the command is EXPLAIN.
EXPLAIN SELECT * FROM orders WHERE user_id = 7;
-- Index Scan using orders_user_id_idx on orders (rows=12)
Two shapes of answer appear.
- Index scan or seek. The database used an index to jump to matching rows.
- Sequential scan. The database read the whole table.
Selectivity
Selectivity is how few rows a condition matches compared with the whole table. A condition that matches 12 rows out of 10 million is very selective. One that matches half the table is not.
Example: user_id = 7 is selective if each user has about a dozen orders. status = 'paid' is not selective if 90 percent of orders are paid.
A worked example. The orders table has 10 million rows.
| Column | Distinct values | Rows per value | Index useful? |
|---|---|---|---|
user_id |
1,000,000 | about 10 | Yes, very selective |
created_at (date) |
1,000 days | about 10,000 | For narrow ranges, yes |
status |
3 | about 3,300,000 | No, the planner scans instead |
is_deleted (true or false) |
2 | about 5,000,000 | No |
Why is the index on status poor? A lookup of status = 'paid' finds 3.3 million index entries and then needs 3.3 million jumps to the rows, one at a time, which is slower than reading the table from start to end in order. So the planner skips the index. This is not a bug.
A column with few distinct values can still help in combination with others (section 4), or when the wanted value is rare. If only 1 order in 1,000 is status = 'failed', an index lookup for failed finds 10,000 rows and wins.
The planner estimates costs from statistics the database keeps about each column. If the statistics are old, it can choose badly. Most databases refresh them automatically, and offer a command such as ANALYZE to do so by hand.
Another case where an index is not used: a condition that changes the column before comparing.
SELECT * FROM users WHERE LOWER(email) = '[email protected]'; -- index on email is not used
SELECT * FROM users WHERE email = '[email protected]'; -- index on email is used
The index holds the original values, not their lower-case form. Fixes: store the email lower-case, or create an index on the expression LOWER(email).
Also, a search for words that end with a pattern cannot use an ordinary index:
SELECT * FROM users WHERE name LIKE '%sha'; -- scans
SELECT * FROM users WHERE name LIKE 'As%'; -- can use an index: the start is fixed
An index is sorted from the start of the value, so a fixed beginning narrows the search. A wildcard at the start does not.
Common mistake
Adding an index and assuming it is used. Run EXPLAIN on the real query with realistic data. A query that looks indexed may scan, because of a function, a mismatch of types or poor selectivity.
Check yourself:
- Why would a planner ignore an index on a column with three distinct values?
- Why does
LOWER(email) = ...not use a plain index onemail?