1Show the Level 1 solution
2**A.**
31. **Yes:** an index (usually unique) on `email`. Finds one row among 5 million.
42. **Probably not:** 80% of rows match, so a scan is cheaper. An index helps only for the rare statuses.
53. **No** (B-tree): the leading `%` means no prefix to jump to. Use a full-text or search index (Chapter 19).
64. **Yes:** a composite index on `(user_id, created_at)`. It finds the user's orders already in date order, so `LIMIT 20` stops after 20 entries.
75. **Not needed:** 250 rows scan instantly. (The primary key on `code` would already cover it.)
8
9**B.**
101. **Yes** (leftmost column).
112. **No.** `created_at` is the second column; the index can only be scanned in full, not sought.
123. **Yes**, both columns.
134. **Yes.** The order of conditions in the query doesn't matter; the order of columns in the index does.
Show the Level 2 solution
1. 500² = 250,000 < 10 million ≤ 500³ = 125 million → **3 levels**. For 1 billion: 500³ = 125 million < 1 billion ≤ 500⁴ → **4 levels**.
2. Scan: 10 million × 100 bytes = 1 GB ÷ 500 MB/s = **about 2 seconds**. Index: 4 × 0.1 ms = **about 0.4 ms**, roughly 5,000 times faster.
3. Each insert writes the table row + the primary key index (in many databases they're the same structure) + 5 indexes. Counting the table and 5 extra indexes: **about 6,000 writes a second** (more if the primary key is a separate index).
4. About 200,000 ÷ 3 ≈ **67,000 rows**. Fetching a third of the table through an index means many scattered row lookups; reading the table once in order can be cheaper, so the planner may choose a scan.
1Show the Level 3 solution
2Tested solution (Python 3, `sqlite3`), the key parts:
3
4```python
5def plan(db, sql, params=()):
6 return " | ".join(row[-1] for row in db.execute("EXPLAIN QUERY PLAN " + sql, params))
7
8q_user = "SELECT id, total FROM orders WHERE user_id = ?"
9assert plan(db, q_user, (7,)).startswith("SCAN orders") # no index yet
10db.execute("CREATE INDEX idx_orders_user ON orders(user_id)")
11assert "SEARCH orders USING INDEX idx_orders_user" in plan(db, q_user, (7,))
12
13db.execute("DROP INDEX idx_orders_user")
14db.execute("CREATE INDEX idx_user_time ON orders(user_id, created_at)")
15assert "(user_id=? AND created_at>?)" in plan(
16 db, "SELECT id FROM orders WHERE user_id = ? AND created_at > ?", (7, 0))
17assert "COVERING INDEX" in plan(db, "SELECT created_at FROM orders WHERE user_id = ?", (7,))
18
19
20def index_lookup(sorted_keys, sorted_rowids, key):
21 lo, hi, comparisons = 0, len(sorted_keys), 0
22 while lo < hi: # binary search: about log2(n) steps
23 comparisons += 1
24 mid = (lo + hi) // 2
25 if sorted_keys[mid] < key:
26 lo = mid + 1
27 else:
28 hi = mid
29 found = lo < len(sorted_keys) and sorted_keys[lo] == key
30 return (sorted_rowids[lo] if found else None), comparisons
31```
32
33All checks pass. In the test run: the user lookup took **6.93 ms** scanning vs **0.017 ms** with an index; the toy index needed **20** comparisons vs **1,000,000** for a scan; 20,000 inserts took **19 ms** with no indexes vs **91 ms** with 5 (timings vary by machine). The full file is in `code/ch09_indexes.py`.
1Show the Level 4 solution
2**The bug:** the query wraps the indexed column in a function. The index is sorted by `email`, but the query asks about `lower(email)`, a different value the index knows nothing about. So the database computes `lower(email)` for **every row**: a full scan, which gets slower as users grow.
3
4`EXPLAIN QUERY PLAN` shows `SCAN users`.
5
6**Fix 1: an expression index** on exactly what you search:
7
8```sql
9CREATE INDEX idx_users_email_lower ON users (lower(email));
10-- plan: SEARCH users USING INDEX idx_users_email_lower (<expr>=?)
11```
12
13**Fix 2: store emails already normalised.** Lowercase the email when the user signs up, keep a unique index on `email`, and query `WHERE email = ?` with the lowercased input. (Some databases also offer case-insensitive column types or collations, like PostgreSQL's `citext`.)
1Show the Level 5 (sketch) solution
21. **Indexes:**
3 - `(user_id, created_at)` for **A**: seek by user, already in date order, `LIMIT 20` stops early. Add `INCLUDE (total, status)` if the list shows them, to make it covering.
4 - `(status, created_at)` for **B**: equality on status first, range on date second.
5 - **C** is already served by the primary key on `id`.
62. **No index for D.** It reads a whole year of orders, a large share of the table, once a night; a scan (ideally on a read replica, or a separate analytics copy) is fine. Better still, keep a small daily-totals table updated as orders come in.
73. **Check:** EXPLAIN (ANALYZE) each query before and after; watch the slow-query log; check index usage statistics after a week.
84. **Add safely:** build indexes online (for example `CREATE INDEX CONCURRENTLY` in PostgreSQL), one at a time, at a quiet hour, watching database load and replication lag.
95. **Write cost:** two new indexes means two more index writes per order. During a sale, watch insert latency, disk and CPU on the primary, and replication lag. If writes struggle, drop the admin index B during the sale, since it's not customer-facing.