Art of Codeartofcode
Lesson 3 of 15

9. Indexes

1
The picture to keep in your head
2
9.1 What is an index, exactly?
3
9.2 What's the difference between a full table scan and an index lookup?
4
9.3 What does an index look like inside?
5
9.4 How do composite indexes work, and what is the leftmost-prefix rule?
6
9.5 What is a covering index?
7
9.6 How do you know whether a query uses an index?
8
9.7 What does an index cost you?
9
9.8 When does an index not help, or even hurt?
10
Memory card and where the analogy breaks
11
Practice: five levels
12
Interview questions
13
Solutions
14
Sources
15
Code lab
9. Indexes

9.2 What's the difference between a full table scan and an index lookup?

3 min read+10 XP

In a book: Without an index, finding "caching" means reading every page: 600 pages. With the index, you jump to "C", find the word, read the page numbers, and open page 212: a handful of steps, however thick the book.

In the system:

  • A full table scan reads every row and checks the condition. The work grows with the table: 10 times more rows, 10 times slower.
  • An index lookup (an "index seek") jumps through the index to the matching entries, then fetches only those rows. The work grows with the logarithm of the table size, which is almost flat.

The numbers (assumed): an orders table with 10 million rows of about 100 bytes is about 1 GB. Scanning it from disk at 500 MB a second takes about 2 seconds. A B-tree index (9.3.1) with around 500 keys per page needs about 3 levels for 10 million keys (500³ = 125 million), so a lookup reads about 3 or 4 pages, well under a millisecond on an SSD.

In this chapter's test run (200,000 orders in SQLite), WHERE user_id = 7 took about 6.9 ms as a scan and about 0.017 ms with an index: roughly 400 times faster, on a small table. The gap grows as the table grows.

A scan isn't always bad: for a small table, or a query that needs most of the rows anyway, reading everything in order can be the cheapest plan (9.8).

Memory code: "Read every page, or jump to the page."