CSE Roadmap

Core tier · about 3 hours · 8 parts

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 on email?