Indexes

Why Sorted Order Is Fast

Because the index is sorted, the database never has to look at most of it.

Think about finding a value in a sorted list of one million entries. You look in the middle and ask whether your value is before or after. One question removes half the list. After 20 questions, one entry is left.

That is the whole reason an index works. A full scan of a million rows reads a million rows. The same lookup through an index reads about 20 entries.

Most databases store indexes as a B-tree. It is a tree that stays sorted and stays balanced, so every value costs the same small number of steps to reach. It also supports range queries well, because values that are near each other are stored near each other. A query for all orders between two dates walks a short part of the tree instead of scanning the table.

What an Index Costs

An index is not free, and this is the part candidates usually miss.

Every write to the table must also update every index on that table. Inserting one row into a table with three indexes means four writes, not one. The same is true for updates that change an indexed column, and for deletes.

Indexes also take space on disk, and they take memory when the database keeps them cached.

So the rule needs care. Indexes make reads faster, and they make inserts slower, because every index on the table must be maintained. Updates and deletes sit in the middle: maintaining the index costs extra work, but the statement has to find the rows it will change, so an index on the column in the WHERE clause can make it far faster. Add them for the columns you actually search on, and remove the ones nobody uses. A table that is written constantly and read rarely may be better with almost no indexes at all.

Indexes on More Than One Column

An index can cover several columns. This is called a composite index, and the order of the columns matters.

An index on (last_name, first_name) is sorted by last name first. Rows with the same last name are then sorted by first name.

This index helps a query that searches by last name. It also helps a query that searches by last name and first name together.

It does not help a query that searches only by first name. The index is not sorted by first name, so the database would have to read all of it.

This is called the leftmost prefix rule. A composite index can be used for the first column, the first two columns, the first three, and so on. It can never be used for a middle column on its own.

A printed phone book works the same way. It is sorted by last name and then first name. Finding everyone called Smith is easy. Finding everyone called Maria means reading the whole book.

When an Index Does Not Help

Adding an index does not always make a query faster. The database decides for itself whether to use one, and it often refuses.

The query returns most of the table. If a query matches 60 percent of the rows, using the index means jumping back and forth between the index and the rows. Reading the table straight through is faster, so the database does that.

The searched value matches most of the rows. An index on a status column holding active and inactive splits the table in two, so a query for either value is not selective enough to be worth it. When the values are uneven, say one percent of rows marked failed, an index still helps the query that looks for the rare value. A column where almost every value is different, such as an email address, is the ideal case.

The query hides the column inside a function. WHERE LOWER(email) = 'a@b.com' cannot use an index on email, because the index stores the original values, not the lowercased ones. Comparing the column directly can use the index.

The search starts with a wildcard. LIKE 'john%' can use an index, because it fixes the beginning of the value. LIKE '%son' cannot, because the index is sorted from the left.

The table is small. For a few hundred rows, reading everything is already fast.

Every database has a command that shows which plan it chose. In most SQL databases it is EXPLAIN. It is the only reliable way to know whether your index is being used.

Primary and Secondary Indexes

The primary index is built on the primary key. In many databases the table itself is stored in this order. That is why looking a row up by primary key is the fastest lookup there is.

A secondary index is any other index. It stores the indexed value and a pointer back to the row. A lookup through a secondary index therefore has two steps: find the pointer in the index, then read the row.

If an index happens to contain every column that a query asks for, the second step is not needed. The database answers from the index alone. This is called a covering index, and it is one of the most effective tuning tricks there is.

Key Takeaways

• An index is a sorted structure holding column values and pointers to rows. It lets the database avoid reading the whole table.
• Sorted order is the reason it is fast. A lookup in a million-row index takes about 20 steps instead of a million.
• Most indexes are B-trees, which support both single lookups and range queries.
• Every index makes inserts slower, because each one must be maintained. An update or a delete pays that cost too, but an index on the column it searches by can still make it much faster. Add the indexes you need and remove the rest.
• In a composite index the column order matters. An index on (last_name, first_name) helps a search on last name, but not a search on first name alone.
• An index is ignored when the query returns most of the table, or when the column has few distinct values. It is also ignored when the column is wrapped in a function, or when a LIKE pattern starts with a wildcard.
• A covering index answers the query without reading the row at all.

The first answer to a slow query is almost always an index on the columns in the WHERE clause. The better answer adds what that index will cost on every write.