SyntaxPilot
Courses/System Design/Lesson 10

System Design · Lesson 10 of 40 · 11 min

Indexing

queued

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.

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 (id is the rowid, stored in every index entry), so "SQLite never needs to consult the original table".
  • lower(email) = ... → SCAN: the index is sorted by email, not by lower(email). Store emails already lowercased (or create an index on the expression lower(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

  1. One phone among a million rows → full table scan (SCAN users).
  2. A small sorted copy of one column with each row's location → index, searched by binary search (20 steps).
  3. Inserts must stay cheap → B-tree, which also serves ranges and ORDER BY.
  4. Every write updates every index → index only what you search.
  5. Two columns → composite index, left-most rule.
  6. lower() and LIKE '%...' → 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

  1. In Demo 1, add LIMIT 1 and search for the first user. Why is it fast, and why doesn't that help the last user?
  2. In Demo 6, add an index on name. What does the name-only query's plan say now?
  3. Make binary_search look for a number that isn't in the list. What does it return, and in how many steps?
  4. Run CREATE INDEX idx_phone ... twice. What's the error, and how do you avoid it?
  5. Explain why WHERE created_at > '2026-10-01' can't use an index on (customer_id, created_at).
  6. 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 INDEX turned SCAN into SEARCH ... 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) and LIKE '%...' skip the index. Check with EXPLAIN.

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.