The Slow Catalog Query
A public library's catalog database has 2.4 million rows in a table with columns id, title, author, year, subject, and checked_out. The web catalog runs this query about 40 times per second: SELECT id, title FROM books WHERE author = ? AND year BETWEEN ? AND ? ORDER BY title LIMIT 20. The only index is on author. Average latency is 900 ms and the catalog times out under load. A volunteer proposes adding an index on every column, while a consultant proposes a composite index. The library can afford one schema change this quarter and cannot take the catalog offline for more than a few minutes.
1. Evaluate the two composite index orders: (author, year) and (year, author). Which supports the query better, and what does the leftmost-prefix rule have to do with it?
Read the worked answer
The query has equality on author and a range on year, so (author, year) is the better order. In a B-tree composite index, the leftmost column is the primary sort key. With author first, the engine can seek directly to the one author and then scan only the contiguous range of years for that author. With (year, author), the engine can seek to the year range but must then examine every author within those years; if the range spans many years, that is a large scan with weak filtering. The leftmost-prefix rule also means an index on (author, year) can serve queries that filter on author alone, while (year, author) cannot efficiently serve author-only queries. Neither order eliminates the ORDER BY title sort, because rows within the matched author-year range are ordered by year, not title.
2. The volunteer's 'index every column' plan: identify two concrete costs and one case where an index on checked_out would not be used.
Read the worked answer
Two costs:
- Write amplification. Every INSERT, UPDATE, and DELETE must maintain every index. With six extra indexes, a single row change can require many B-tree updates, slowing checkout and return transactions.
- Space and optimizer overhead. Indexes consume disk and memory, and the query planner must consider more access paths; a poor choice can increase planning time and produce worse plans.
An index on checked_out would rarely be used because it is likely a low-selectivity boolean column. If most books are checked in, a query for checked_out = false matches nearly the whole table, and a full scan is cheaper than following an index plus row lookups. Low-selectivity indexes also produce poor estimates and can mislead the optimizer.
3. Even with (author, year), the query may still be slow because of ORDER BY title LIMIT 20. Explain and propose one measurement and one schema or query change to address it.
Read the worked answer
The database must find all rows matching the author and year range, then sort them by title before it can return the first 20. The LIMIT does not avoid the sort unless the index already delivers rows in title order. With a prolific author and a wide year range, that sort can dominate the 900 ms latency.
Measure with EXPLAIN ANALYZE (or the equivalent slow-query plan) to confirm whether a filesort appears and how many rows are sorted. Then consider extending the index to (author, year, title). For a fixed author and a single year, this delivers rows already ordered by title and can support an index-only scan for id and title. For a multi-year range, the order is year-then-title, so a sort may remain; in that case, rewrite the query to fetch candidate ids in a narrow year range, or cache the most common author queries. The measurement must come first, because the right change depends on whether the plan shows sorting, row lookups, or both.