These are the notes for System Design episode 10. Last episode you invented tables. Here we fill one with a million users, look up one phone number, and watch the database read every row: a full table scan. Then you invent the fix: an index, searched by binary search and stored as a B-tree. We measure what it costs (slower writes), meet composite indexes and the left-most rule, and see queries that quietly ignore your index. Every demo uses Python's built-in sqlite3 and runs as-is; outputs are real (Python 3.13, SQLite 3.53). Timings vary from run to run and machine to machine; the ratios are what matter.
The six problems
| Problem | What it teaches |
|---|---|
| 1 phone in 1,000,000 rows | The full table scan (SCAN) |
| The back of a textbook | Index, binary search (SEARCH ... USING INDEX) |
| Keep it sorted, cheaply | B-tree: equality, ranges, ORDER BY |
| Writes got slower | The cost of every index |
| Two columns | Composite index, the left-most rule |
| The index is ignored | Functions and leading wildcards skip the index |
Problem 1: one phone in a million rows (the full table scan)
ChaiNow gets a missed call from 9006999993. Which customer was it? The users table has a million customers, stored in the order they signed up. Nothing about that order helps find a phone number, so the database has one choice: start at row one and check every row.
Demo 1: SCAN users
EXPLAIN QUERY PLAN in front of a query asks SQLite how it would run it, without changing the answer. Each row it returns describes one step; the text is in the fourth column ([3]).
import sqlite3, time
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE users
(id INTEGER PRIMARY KEY, name TEXT, phone TEXT)""")
rows = ((f"user{i}", str(9000000000 + i * 7)) for i in range(1_000_000))
db.executemany("INSERT INTO users (name, phone) VALUES (?, ?)", rows)
Q = "SELECT name FROM users WHERE phone = ?"
start = time.perf_counter()
for _ in range(10): # 10 lookups of the last user
row = db.execute(Q, ("9006999993",)).fetchone()
ms = (time.perf_counter() - start) * 1000 / 10
print(row, f"found in {ms:.1f} ms per lookup")
print(db.execute("EXPLAIN QUERY PLAN " + Q, ("x",)).fetchone()[3])
Output:
('user999999',) found in 37.0 ms per lookup
SCAN users
SCAN users means: read every row. SQLite's documentation calls this a full table scan, "since the entire content of the table must be read and examined". 40 milliseconds sounds small, but a thousand lookups a second would need 40 seconds of work every second.
Why not just sort the table by phone? Rows can only be stored in one order. Sort by phone, and tomorrow's search by name is a full scan again. Keeping a second full copy sorted by name doubles the storage. We need something smaller.
Problem 2: the index (and binary search)
| In a textbook | In a database |
|---|---|
| 500 pages, in chapter order | The table: rows in their own order |
| The index at the back: topics A–Z with page numbers | An index: one column, sorted, with each row's location |
| Flip to the middle: M? go left. B? go right. | Binary search: halve the range each step |
SQLite's docs put it simply: "An index is another table similar to the original", holding the indexed column in sorted order plus the rowid (the row's id) that points back to the full row.
users (in signup order) idx_phone (sorted by phone)
rowid name phone phone rowid
1 user0 9000000000 9000000000 1
2 user1 9000000007 9000000007 2
... ...
1000000 user999999 9006999993 9006999993 1000000
│
binary search ───────┘ then jump to rowid 1000000
Demo 2: 20 steps for a million
phones = [9000000000 + i * 7 for i in range(1_000_000)] # sorted
def binary_search(items, target):
lo, hi, steps = 0, len(items) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2 # open the book in the middle
if items[mid] == target:
return mid, steps
if items[mid] < target:
lo = mid + 1 # throw away the left half
else:
hi = mid - 1 # throw away the right half
return -1, steps
print("position, steps:", binary_search(phones, 9006999993))
Output:
position, steps: (999999, 20)
Each step halves the range: 1,000,000 → 500,000 → 250,000 → ... → 1. That takes about 20 halvings (2²⁰ ≈ 1,048,576), so lookups are "proportional to log N" (SQLite docs). Double the table to two million rows, and it costs one more step.
Demo 3: CREATE INDEX
import sqlite3, time
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE users
(id INTEGER PRIMARY KEY, name TEXT, phone TEXT)""")
rows = ((f"user{i}", str(9000000000 + i * 7)) for i in range(1_000_000))
db.executemany("INSERT INTO users (name, phone) VALUES (?, ?)", rows)
Q = "SELECT name FROM users WHERE phone = ?"
db.execute("CREATE INDEX idx_phone ON users (phone)") # the one line
start = time.perf_counter()
for _ in range(10): # 10 lookups of the last user
row = db.execute(Q, ("9006999993",)).fetchone()
ms = (time.perf_counter() - start) * 1000 / 10
print(row, f"found in {ms:.3f} ms per lookup")
print(db.execute("EXPLAIN QUERY PLAN " + Q, ("x",)).fetchone()[3])
Output:
('user999999',) found in 0.008 ms per lookup
SEARCH users USING INDEX idx_phone (phone=?)
About 40 ms became about a hundredth of a millisecond: thousands of times faster. The plan changed from SCAN (read everything) to SEARCH ... USING INDEX (jump to the right place). The answer didn't change, only the speed: as SQLite's docs say, indices "should never change the answer, only help SQLite to get to the answer more quickly".
Problem 3: keep it sorted, cheaply (the B-tree)
If the index were one long sorted list, inserting a phone number near the front would push a million entries along by one place, on every insert. So databases store an index as a B-tree: a tree of small pages.
| In a library | In a B-tree |
|---|---|
| Floor signs: A–H, I–P, Q–Z | Root page: a few keys that split the whole range |
| Shelf labels on that floor | Inner pages: each narrows the range |
| The book, with its exact location | Leaf page: the key and where the row lives |
Each page holds many keys, so a few levels cover millions of rows, and adding a key only changes the page it lands in (a full page splits into two). PostgreSQL's docs: "By default, the CREATE INDEX command creates B-tree indexes, which fit the most common situations." Because a B-tree is sorted, it also helps with ranges and sorting: "B-trees can handle equality and range queries on data that can be sorted", and "can also be used to retrieve data in sorted order".
Demo 4: equality, ranges and ORDER BY
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders
(id INTEGER PRIMARY KEY, amount INTEGER, item TEXT)""")
db.execute("CREATE INDEX idx_amount ON orders (amount)")
db.executemany("INSERT INTO orders (amount, item) VALUES (?, ?)",
((i % 5000, "chai") for i in range(100_000)))
for q in ["SELECT * FROM orders WHERE amount = 499",
"SELECT * FROM orders WHERE amount BETWEEN 1000 AND 1200",
"SELECT * FROM orders ORDER BY amount LIMIT 3"]:
print(db.execute("EXPLAIN QUERY PLAN " + q).fetchone()[3])
Output:
SEARCH orders USING INDEX idx_amount (amount=?)
SEARCH orders USING INDEX idx_amount (amount>? AND amount<?)
SCAN orders USING INDEX idx_amount
An equal match, a range (BETWEEN becomes amount>? AND amount<?), and a scan in index order so nothing needs sorting. Without the index, SQLite would sort with a temporary B-tree (see practice 6).
Problem 4: writes got slower (the cost of an index)
Every index is another sorted structure to update on every INSERT, UPDATE and DELETE, and it takes space.
Demo 5: 300,000 inserts with 0, 1 and 3 indexes
import sqlite3, time
def insert_time(n_indexes):
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (name TEXT, phone TEXT, city TEXT)")
for col in ["name", "phone", "city"][:n_indexes]:
db.execute(f"CREATE INDEX idx_{col} ON users ({col})")
rows = ((f"user{i}", str(9999999999 - i * 7), f"city{i % 500}")
for i in range(300_000))
start = time.perf_counter()
db.executemany("INSERT INTO users VALUES (?, ?, ?)", rows)
return (time.perf_counter() - start) * 1000
for n in [0, 1, 3]:
print(f"{n} indexes -> 300,000 inserts in {insert_time(n):.0f} ms")
Output:
0 indexes -> 300,000 inserts in 282 ms
1 indexes -> 300,000 inserts in 463 ms
3 indexes -> 300,000 inserts in 1168 ms
Your numbers will differ, but the pattern holds: each index makes inserts slower. So index the columns you actually search by, and nothing else. A table written all the time (an event log) wants very few indexes.
Problem 5: two columns (composite index, left-most rule)
A composite index covers several columns, sorted by the first, then the second within it, like a phone directory sorted by city, then name.
Demo 6: the left-most rule
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (city TEXT, name TEXT, phone TEXT)")
db.execute("CREATE INDEX idx_city_name ON users (city, name)") # 2 columns
for where in ["city = 'Pune' AND name = 'Priya'",
"city = 'Pune'",
"name = 'Priya'"]:
q = "EXPLAIN QUERY PLAN SELECT phone FROM users WHERE " + where
print("WHERE", where)
print(" ->", db.execute(q).fetchone()[3])
Output:
WHERE city = 'Pune' AND name = 'Priya'
-> SEARCH users USING INDEX idx_city_name (city=? AND name=?)
WHERE city = 'Pune'
-> SEARCH users USING INDEX idx_city_name (city=?)
WHERE name = 'Priya'
-> SCAN users
City and name: both columns used. City only: still used. Name only: SCAN, because the Priyas are spread across every city in the index. A composite index helps only when the query uses its left-most column (and then the next ones, in order). SQLite's docs add that "multi-column indices only work if the constraint terms in the WHERE clause of the query are connected by AND".
Problem 6: the index is ignored
Demo 7: functions and leading wildcards
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT)")
db.execute("CREATE INDEX idx_email ON users (email)")
for where in ["email = 'priya@mail.in'",
"lower(email) = 'priya@mail.in'",
"email LIKE '%@mail.in'"]:
q = "EXPLAIN QUERY PLAN SELECT id FROM users WHERE " + where
print("WHERE", where)
print(" ->", db.execute(q).fetchone()[3])
Output:
WHERE email = 'priya@mail.in'
-> SEARCH users USING COVERING INDEX idx_email (email=?)
WHERE lower(email) = 'priya@mail.in'
-> SCAN users
WHERE email LIKE '%@mail.in'
-> SCAN users
email = ...uses the index. It's even a covering index: the index alone contains every column the query needs (idis the rowid, stored in every index entry), so "SQLite never needs to consult the original table".lower(email) = ...→SCAN: the index is sorted byemail, not bylower(email). Store emails already lowercased (or create an index on the expressionlower(email), which SQLite and PostgreSQL support).LIKE '%@mail.in'→SCAN: a pattern that starts with a wildcard can match anything at the start, so the sorted order can't help. A search that starts from the beginning of the text can be helped by an index; one that starts in the middle can't.
Which columns deserve an index?
| Index it | Example |
|---|---|
Columns in WHERE clauses you run often |
phone, email, order_id |
| Foreign keys you JOIN on | orders.customer_id |
| Columns you sort by or search in ranges | created_at, amount |
| Values that must be unique | a UNIQUE index on email |
| Skip: columns nobody searches by | every index costs every write |
Always: check with EXPLAIN |
SCAN or SEARCH? |
The whole chain
- One phone among a million rows → full table scan (
SCAN users). - A small sorted copy of one column with each row's location → index, searched by binary search (20 steps).
- Inserts must stay cheap → B-tree, which also serves ranges and
ORDER BY. - Every write updates every index → index only what you search.
- Two columns → composite index, left-most rule.
lower()andLIKE '%...'→ the index is ignored.
Common mistakes (and the real errors)
| Mistake | Code | Error / plan | Fix |
|---|---|---|---|
| Duplicate in a UNIQUE index | CREATE UNIQUE INDEX idx_email ..., insert 'priya@mail.in' twice |
sqlite3.IntegrityError: UNIQUE constraint failed: users.email |
Check first, or catch it and say "email taken" |
| Creating the same index twice | CREATE INDEX idx_phone ... run twice |
sqlite3.OperationalError: index idx_phone already exists |
CREATE INDEX IF NOT EXISTS idx_phone ... |
| A function on the indexed column | WHERE lower(email) = ... |
SCAN users (no error) |
Store lowercased values, or index the expression |
| Leading wildcard | WHERE email LIKE '%@mail.in' |
SCAN users |
Search from the start of the text, or use a search index (later episode) |
| Skipping the left-most column | index on (city, name), WHERE name = ... |
SCAN users |
Put the most-searched column first, or add an index on name |
| Indexing every column | 10 indexes on a busy table | slow inserts | Index only what queries search by |
The two errors in full:
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT)")
db.execute("CREATE UNIQUE INDEX idx_email ON users (email)")
db.execute("INSERT INTO users (email) VALUES ('priya@mail.in')")
db.execute("INSERT INTO users (email) VALUES ('priya@mail.in')")
Output:
Traceback (most recent call last):
File "main.py", line 6, in <module>
db.execute("INSERT INTO users (email) VALUES ('priya@mail.in')")
~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
sqlite3.IntegrityError: UNIQUE constraint failed: users.email
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (id INTEGER PRIMARY KEY, phone TEXT)")
db.execute("CREATE INDEX idx_phone ON users (phone)")
db.execute("CREATE INDEX idx_phone ON users (phone)")
Output:
Traceback (most recent call last):
File "main.py", line 5, in <module>
db.execute("CREATE INDEX idx_phone ON users (phone)")
~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
sqlite3.OperationalError: index idx_phone already exists
Misconceptions
- "More indexes = faster database." Faster reads on those columns, slower writes everywhere, and more space.
- "An index changes the results." Never. It only changes how fast the database finds them.
- "An index on (a, b) also works for b alone." Not normally: the left-most rule.
- "The primary key needs an index." It already has one: in SQLite the rowid table itself is ordered by its integer primary key.
- "The index is always used once it exists." Functions on the column, leading wildcards and skipped left-most columns make the database scan anyway. Check with
EXPLAIN.
Mini project: the slow-query detective
Run EXPLAIN QUERY PLAN on an app's queries, find the SCANs, add the missing indexes, and measure.
# Slow-query detective: run EXPLAIN on the app's queries, find the SCANs,
# add the missing index, and measure the difference.
import sqlite3, time, random
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders (id INTEGER PRIMARY KEY, customer_id INTEGER,
city TEXT, amount INTEGER)""")
random.seed(1)
cities = ["Pune", "Delhi", "Chennai", "Kolkata", "Jaipur"]
db.executemany("INSERT INTO orders (customer_id, city, amount) VALUES (?, ?, ?)",
((random.randint(1, 50_000), random.choice(cities),
random.randint(20, 900)) for _ in range(500_000)))
QUERIES = {
"orders of one customer": "SELECT * FROM orders WHERE customer_id = 4242",
"big orders": "SELECT * FROM orders WHERE amount > 895",
}
def check(label, sql):
plan = db.execute("EXPLAIN QUERY PLAN " + sql).fetchone()[3]
start = time.perf_counter()
n = len(db.execute(sql).fetchall())
ms = (time.perf_counter() - start) * 1000
print(f"{label:<24} {n:>5} rows {ms:7.2f} ms {plan}")
return plan
for label, sql in QUERIES.items():
check(label, sql)
db.execute("CREATE INDEX idx_customer ON orders (customer_id)")
db.execute("CREATE INDEX idx_amount ON orders (amount)")
print("-- after adding 2 indexes --")
for label, sql in QUERIES.items():
check(label, sql)
Output:
orders of one customer 10 rows 18.13 ms SCAN orders
big orders 2892 rows 17.93 ms SCAN orders
-- after adding 2 indexes --
orders of one customer 10 rows 0.05 ms SEARCH orders USING INDEX idx_customer (customer_id=?)
big orders 2892 rows 4.58 ms SEARCH orders USING INDEX idx_amount (amount>?)
The customer lookup went from a scan to a search. The range query improved less, because it still returns thousands of rows: an index helps most when a query picks out a small part of the table. Try adding a query for city = 'Pune': about a fifth of all rows match, so an index helps far less.
Practice
- In Demo 1, add
LIMIT 1and search for the first user. Why is it fast, and why doesn't that help the last user? - In Demo 6, add an index on
name. What does the name-only query's plan say now? - Make
binary_searchlook for a number that isn't in the list. What does it return, and in how many steps? - Run
CREATE INDEX idx_phone ...twice. What's the error, and how do you avoid it? - Explain why
WHERE created_at > '2026-10-01'can't use an index on(customer_id, created_at). - Which index serves "this customer's orders, newest first"? Check the plan before and after.
Solutions and hints
1. A scan stops at the first match when you only ask for one row. The first user is row 1, so it's found at once; the last user is still a million checks away. Real lookups land anywhere, so on average a scan reads half the table, and a missing value reads all of it.
import sqlite3, time
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE users
(id INTEGER PRIMARY KEY, name TEXT, phone TEXT)""")
rows = ((f"user{i}", str(9000000000 + i * 7)) for i in range(1_000_000))
db.executemany("INSERT INTO users (name, phone) VALUES (?, ?)", rows)
Q = "SELECT name FROM users WHERE phone = ? LIMIT 1" # stop at the first match
for phone in ["9000000000", "9006999993"]: # first user, last user
start = time.perf_counter()
row = db.execute(Q, (phone,)).fetchone()
print(phone, row, f"{(time.perf_counter() - start) * 1000:.3f} ms")
Output:
9000000000 ('user0',) 0.063 ms
9006999993 ('user999999',) 39.371 ms
(Without LIMIT 1, Python's sqlite3 looks ahead for a second matching row, so even the first user takes a full scan. That's why Demo 1 is slow either way.)
2.
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("CREATE TABLE users (city TEXT, name TEXT, phone TEXT)")
db.execute("CREATE INDEX idx_city_name ON users (city, name)")
db.execute("CREATE INDEX idx_name ON users (name)") # new
q = "EXPLAIN QUERY PLAN SELECT phone FROM users WHERE name = 'Priya'"
print(db.execute(q).fetchone()[3])
Output:
SEARCH users USING INDEX idx_name (name=?)
3. It returns -1 after about 20 steps: a missing value costs the same log N as a found one.
phones = [9000000000 + i * 7 for i in range(1_000_000)]
def binary_search(items, target):
lo, hi, steps = 0, len(items) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if items[mid] == target:
return mid, steps
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
print(binary_search(phones, 9000000001)) # not a multiple of 7 away
Output:
(-1, 20)
4. Use CREATE INDEX IF NOT EXISTS.
Traceback (most recent call last):
File "main.py", line 5, in <module>
db.execute("CREATE INDEX idx_phone ON users (phone)")
~~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
sqlite3.OperationalError: index idx_phone already exists
5. The index is sorted by customer_id first. Dates are only in order within each customer, so all of them must be read: SCAN.
6. A composite index on (customer_id, created_at): it finds the customer, and the rows are already in date order. Before, SQLite scans and sorts with a temporary B-tree:
import sqlite3
db = sqlite3.connect(":memory:")
db.execute("""CREATE TABLE orders (id INTEGER PRIMARY KEY,
customer_id INTEGER, created_at TEXT, item TEXT)""")
q = """EXPLAIN QUERY PLAN SELECT * FROM orders
WHERE customer_id = 7 ORDER BY created_at DESC LIMIT 10"""
print("before:", [r[3] for r in db.execute(q)])
db.execute("CREATE INDEX idx_cust_time ON orders (customer_id, created_at)")
print("after: ", [r[3] for r in db.execute(q)])
Output:
before: ['SCAN orders', 'USE TEMP B-TREE FOR ORDER BY']
after: ['SEARCH orders USING INDEX idx_cust_time (customer_id=?)']
Quick quiz
-- INDEX ON orders (customer_id, created_at)
SELECT * FROM orders
WHERE created_at > '2026-10-01';
-- SEARCH or SCAN?
- A. SEARCH, using both columns
- B. SEARCH, using created_at only
- C. SCAN
- D. Error
Answer
C, SCAN. The query skips customer_id, the left-most column, so the index can't narrow it down. (Checked in SQLite 3.53: the plan is SCAN orders.)
Interview questions
- What is a full table scan? When is it acceptable?
- What is an index, and why does it make lookups faster? How many steps does binary search need for a billion rows? (About 30.)
- Why do databases store indexes as B-trees rather than sorted arrays?
- What queries can a B-tree index help with? (Equality, ranges, sorting, prefix matches.)
- What does an index cost? When would you not add one?
- What is a composite index? Explain the left-most rule with an example.
- What is a covering index?
- Give two ways a query can accidentally stop using an index.
- How do you find out whether a query uses an index? (
EXPLAIN/EXPLAIN QUERY PLAN.)
Glossary
| Term | Meaning |
|---|---|
| Table / row / column | A grid of one kind of thing / one record / one field (episode 9) |
| Query | A question to the database, like SELECT name FROM users WHERE phone = ? |
? placeholder |
A slot in SQL filled by a value passed separately, safely |
Full table scan (SCAN) |
Reading every row of a table to answer a query |
EXPLAIN QUERY PLAN |
SQLite command that shows how a query will be run |
| Query plan | The steps the database chooses to answer a query |
| Index | A sorted copy of one or more columns, with each row's location |
| rowid | SQLite's unique integer id for each row; indexes point to rows by it |
CREATE INDEX |
SQL command to build an index on a table's columns |
SEARCH ... USING INDEX |
The plan uses an index to jump to matching rows |
| Binary search | Find a value in sorted data by halving the range each step |
| log N | The number of halvings to get from N down to 1 (about 20 for a million) |
| B-tree | A sorted tree of pages; the default index structure in most databases |
| Page | A fixed-size block of storage; a B-tree node |
| Root / inner / leaf page | The top page / middle pages / bottom pages holding keys and row locations |
| Range query | A query for values between limits: BETWEEN, >, < |
ORDER BY / LIMIT |
Sort the result / return only the first N rows |
| Temporary B-tree | A sorted structure SQLite builds on the fly to sort without an index |
| Write cost | The extra work every insert, update and delete does to keep indexes up to date |
| Composite index | An index on several columns, sorted by the first, then the next |
| Left-most rule | A composite index helps only when the query uses its first column(s) |
| Covering index | An index containing every column a query needs, so the table isn't read |
UNIQUE index |
An index that refuses duplicate values |
IF NOT EXISTS |
Skip creating something that's already there |
LIKE / % |
SQL pattern match / wildcard for "any text" |
lower() |
SQL function that lowercases text |
IntegrityError / OperationalError |
sqlite3 errors for a broken constraint / a bad statement |
time.perf_counter() |
A precise clock for measuring elapsed time |
| Generator expression | (x for x in ...): produces values one at a time without building a list |
Summary
- Without an index, the database reads every row: a full table scan (
SCAN users, about 40 ms for a million rows). - An index is a sorted copy of a column with each row's location. Binary search finds a value in about 20 steps for a million rows.
CREATE INDEXturnedSCANintoSEARCH ... USING INDEX: thousands of times faster. - Indexes are stored as B-trees: sorted, cheap to update, and useful for equality, ranges and
ORDER BY. - Every index slows every write and takes space: index what you search by.
- A composite index follows the left-most rule;
lower(column)andLIKE '%...'skip the index. Check withEXPLAIN.
Next episode: our database is fast, but it's still one machine. What happens when it dies at lunch rush? Replication: copy the database, and discover the trouble copies always bring.