Indexes, Query Plans, Transactions and Isolation

Two questions dominate database interviews: "Why is this query slow?" and "What happens if two requests do this at the same time?" The first is about indexes and query plans; the second is about transactions and isolation. This chapter explains both from the inside, with runnable demonstrations on SQLite (the concepts carry over to PostgreSQL and MySQL; dialect differences are called out).

1. How an index works

An index is a separate, sorted data structure that maps column values to row locations, so the database can find rows without scanning the whole table. Most relational indexes are B-trees (or B+ trees): a balanced, shallow tree where each node holds many keys, so even a table of a hundred million rows needs only three to five page reads to locate a key.

• Lookup by key: $O(\log n)$ instead of $O(n)$.
• Range scans (BETWEEN, <, ORDER BY) are efficient because leaves are ordered.
• Cost: each index uses disk and memory, and every INSERT, UPDATE and DELETE must also update every index on the table. Indexes speed reads and slow writes.

Clustered versus non-clustered. A clustered index defines the physical order of the table's rows (the primary key in InnoDB/MySQL; SQL Server allows choosing one). A non-clustered (secondary) index stores the key plus a pointer (the primary key or a row ID) back to the row. In PostgreSQL, tables are heaps and all indexes are secondary.

Other index types: hash (equality only), GIN/inverted (full-text, arrays, JSON), GiST/R-tree (geospatial), bitmap (low-cardinality analytics), partial (index only some rows), expression (index on a computed value), covering (contains all columns the query needs).

2. Reading a query plan

EXPLAIN shows how the database will run a query: which indexes it will use, the join order and the estimated cost (EXPLAIN ANALYZE in PostgreSQL runs it and reports actual time). Watch for a full table scan on a large table, big sorts, and mismatches between estimated and actual row counts.

CREATE TABLE events (id INTEGER PRIMARY KEY, user_id INTEGER, kind TEXT, created_at INTEGER);
WITH RECURSIVE n(i) AS (SELECT 1 UNION ALL SELECT i + 1 FROM n WHERE i < 20000)
INSERT INTO events SELECT i, i % 500, CASE i % 3 WHEN 0 THEN 'click' WHEN 1 THEN 'view' ELSE 'buy' END, i FROM n;

def plan(sql):
    return " ".join(r[3] for r in q("EXPLAIN QUERY PLAN " + sql))

before = plan("SELECT * FROM events WHERE user_id = 42")
assert "SCAN" in before and "SEARCH" not in before                    # no index: the whole table is read
q("CREATE INDEX idx_events_user ON events(user_id)")
after = plan("SELECT * FROM events WHERE user_id = 42")
assert "SEARCH" in after and "idx_events_user" in after              # now an index lookup
assert len(q("SELECT * FROM events WHERE user_id = 42")) == 40         # the same rows either way

3. Designing composite indexes

A multi-column index is sorted by the first column, then the second within it, and so on. It is useful for a query only through its leftmost prefix.

An index on (user_id, kind, created_at) can serve:

• WHERE user_id = ?
• WHERE user_id = ? AND kind = ?
• WHERE user_id = ? AND kind = ? AND created_at > ?
• WHERE user_id = ? ORDER BY kind (the order comes free)

but not a query that filters only on kind or only on created_at.

Rule of thumb for column order: equality columns first, then the range or sort column. Put the more selective column first when both are equalities and queries use either prefix.

q("CREATE INDEX idx_user_kind_time ON events(user_id, kind, created_at)")
p1 = plan("SELECT * FROM events WHERE user_id = 7 AND kind = 'buy' AND created_at > 100")
assert "idx_user_kind_time" in p1
p2 = plan("SELECT * FROM events WHERE kind = 'buy'")
assert p2 == "SCAN events"                                          # kind is not a leftmost prefix, so the index cannot be searched by it

Covering indexes

If an index contains every column the query reads, the database can answer from the index alone with no table lookup (an index-only scan).

q("CREATE INDEX idx_cover ON events(kind, created_at)")
p = plan("SELECT created_at FROM events WHERE kind = 'click'")
assert "COVERING INDEX" in p                                       # the table itself is never touched

When an index will not be used

• A function on the column: WHERE LOWER(email) = 'a@x' or WHERE DATE(created_at) = ... cannot use a plain index on the column. Use an expression index, or rewrite as a range.
• Leading wildcard: LIKE '%abc' cannot use a B-tree; LIKE 'abc%' can.
• Implicit type conversion: comparing a string column to a number may defeat the index.
• Low selectivity: if a filter matches 40% of rows, scanning is cheaper than bouncing between index and table. Planners decide using statistics, so keep them fresh (ANALYZE).
• OR across different columns and NOT IN patterns can force scans.
• Leading column missing from a composite index.

q("CREATE TABLE people(id INTEGER PRIMARY KEY, email TEXT)")
q("CREATE INDEX idx_email ON people(email)")
assert "idx_email" in plan("SELECT * FROM people WHERE email = 'a@x'")
assert "idx_email" not in plan("SELECT * FROM people WHERE lower(email) = 'a@x'")      # function on the column defeats the index
q("CREATE INDEX idx_email_lower ON people(lower(email))")
assert "idx_email_lower" in plan("SELECT * FROM people WHERE lower(email) = 'a@x'")    # an expression index fixes it

4. The N+1 query problem

Loading a list and then issuing one query per item turns one request into hundreds. It is the most common performance bug with ORMs.

q("CREATE TABLE authors(id INTEGER PRIMARY KEY, name TEXT)")
q("CREATE TABLE books(id INTEGER PRIMARY KEY, author_id INTEGER, title TEXT)")
q("INSERT INTO authors VALUES (1,'A'),(2,'B'),(3,'C')")
q("INSERT INTO books VALUES (1,1,'x'),(2,1,'y'),(3,2,'z'),(4,3,'w')")

queries = []
def run(sql, params=()):
    queries.append(sql)
    return db.execute(sql, params).fetchall()

# N+1: one query for the authors, then one per author
for (aid, name) in run("SELECT id, name FROM authors"):
    run("SELECT title FROM books WHERE author_id = ?", (aid,))
assert len(queries) == 1 + 3

# fix: one join (or one IN query) for everything
queries.clear()
run("SELECT a.name, b.title FROM authors a LEFT JOIN books b ON b.author_id = a.id")
assert len(queries) == 1

Fixes: join, IN (...) batch loading, ORM eager loading (select_related, include, JOIN FETCH), or a data loader that batches per request.

5. Transactions and ACID

A transaction groups statements into one all-or-nothing unit.

q("CREATE TABLE accounts(id INTEGER PRIMARY KEY, balance INTEGER NOT NULL CHECK (balance >= 0))")
q("INSERT INTO accounts VALUES (1, 100), (2, 50)")
db.commit()

def transfer(src, dst, amount):
    try:
        db.execute("UPDATE accounts SET balance = balance - ? WHERE id = ?", (amount, src))
        db.execute("UPDATE accounts SET balance = balance + ? WHERE id = ?", (amount, dst))
        db.commit()
        return True
    except Exception:
        db.rollback()                                      # undo the partial work
        return False

assert transfer(1, 2, 30) is True
assert q("SELECT balance FROM accounts ORDER BY id") == [(70,), (80,)]
assert transfer(1, 2, 500) is False                         # the CHECK fails on the first update
assert q("SELECT balance FROM accounts ORDER BY id") == [(70,), (80,)]   # nothing moved: atomicity
assert sum(r[0] for r in q("SELECT balance FROM accounts")) == 150      # money is conserved

Keep transactions short. A long transaction holds locks, bloats the log, and blocks vacuum or purge. Do not hold a transaction open across a network call or user think time.

6. Concurrency anomalies

When transactions overlap, these things can go wrong.

Isolation levels (SQL standard)

Real engines differ from the table, so know your database's actual behaviour. Most use MVCC (multi-version concurrency control): readers see a consistent snapshot and do not block writers. PostgreSQL's "Repeatable Read" is snapshot isolation, which still permits write skew; only SERIALIZABLE (with retries on serialisation failure) prevents it.

Lost update, demonstrated

Two requests read a counter, add one in application code, and write it back.

import threading, sqlite3, tempfile, os

path = os.path.join(tempfile.mkdtemp(), "t.db")
setup = sqlite3.connect(path)
setup.execute("CREATE TABLE counter(id INTEGER PRIMARY KEY, n INTEGER)")
setup.execute("INSERT INTO counter VALUES (1, 0)")
setup.commit(); setup.close()

def read_modify_write(barrier):
    con = sqlite3.connect(path, timeout=10, isolation_level=None)
    n = con.execute("SELECT n FROM counter WHERE id = 1").fetchone()[0]
    barrier.wait()                                          # both threads have read the same value
    con.execute("UPDATE counter SET n = ? WHERE id = 1", (n + 1,))
    con.close()

b = threading.Barrier(2)
ts = [threading.Thread(target=read_modify_write, args=(b,)) for _ in range(2)]
[t.start() for t in ts]; [t.join() for t in ts]
con = sqlite3.connect(path)
assert con.execute("SELECT n FROM counter").fetchone()[0] == 1       # two increments, one result: a lost update

Ways to prevent it

1. Atomic update in SQL: UPDATE counter SET n = n + 1 WHERE id = 1. The database applies it under a lock.
2. Pessimistic locking: SELECT ... FOR UPDATE locks the row until commit (PostgreSQL, MySQL, Oracle; SQLite locks the whole database for writes).
3. Optimistic concurrency: keep a version column; update with WHERE version = :seen and check that one row changed, else retry.
4. Higher isolation (SERIALIZABLE) plus retry on failure.

def atomic_increment():
    c = sqlite3.connect(path, timeout=10, isolation_level=None)
    c.execute("UPDATE counter SET n = n + 1 WHERE id = 1")
    c.close()

ts = [threading.Thread(target=atomic_increment) for _ in range(20)]
[t.start() for t in ts]; [t.join() for t in ts]
assert sqlite3.connect(path).execute("SELECT n FROM counter").fetchone()[0] == 21     # 1 + 20: no updates lost

# optimistic concurrency with a version column
q("CREATE TABLE doc(id INTEGER PRIMARY KEY, body TEXT, version INTEGER)")
q("INSERT INTO doc VALUES (1, 'v1 text', 1)")
def save(body, seen_version):
    cur = db.execute("UPDATE doc SET body = ?, version = version + 1 WHERE id = 1 AND version = ?", (body, seen_version))
    db.commit()
    return cur.rowcount == 1                                  # zero rows means someone else got there first
assert save("alice", 1) is True
assert save("bob", 1) is False                                # bob read version 1 but it is now 2: he must re-read and retry
assert q("SELECT body, version FROM doc") == [("alice", 2)]

7. Locks and deadlocks

Writers take exclusive locks on rows (or pages, or tables), readers under locking schemes take shared locks. Deadlock: transaction A holds row 1 and wants row 2, while B holds row 2 and wants row 1. Engines detect cycles and abort one transaction (the application must retry). Prevent with a consistent lock order (always update accounts in ascending ID order), short transactions, and proper indexes (a missing index can make a statement lock far more rows than needed).

def lock_order(a, b):
    return tuple(sorted((a, b)))                               # always touch the lower id first, whatever the direction of the transfer
assert lock_order(7, 3) == lock_order(3, 7) == (3, 7)

8. Schema changes without downtime

• Add columns as nullable (or with a cheap default), backfill in batches, then add constraints.
• Expand and contract: add the new column or table, write to both, migrate readers, stop writing the old, then drop it in a later release.
• Index creation can lock writes; use CREATE INDEX CONCURRENTLY (PostgreSQL) or online DDL (MySQL).
• Never run a long, locking migration at peak traffic; test on production-sized data.
• Keep migrations versioned, reviewed, and reversible when possible.

9. Connection management

Opening a database connection is expensive and servers allow only a limited number. Use a connection pool sized from the database's capacity, not from the number of requests; too large a pool overwhelms the database. Set timeouts on acquiring a connection, on queries and on idle transactions. A pool that is exhausted looks like a mysterious application slowdown, so monitor pool usage.

10. Common mistakes

• Indexing every column (slow writes, wasted memory) or none (full scans).
• Composite index in the wrong order, or one that duplicates another.
• Functions on indexed columns and leading wildcards.
• SELECT * that prevents covering indexes and ships wasted bytes.
• N+1 queries.
• Read-modify-write in application code without a lock, version check or atomic SQL.
• Long transactions and transactions spanning remote calls.
• Assuming the default isolation level prevents all anomalies.
• Inconsistent lock ordering causing deadlocks.
• Running migrations that lock a hot table.

11. Practice questions

1. How does a B-tree index speed up queries? What does it cost?
2. You have (a, b, c) indexed. Which of these can use it: WHERE b = 1, WHERE a = 1 AND c = 2, WHERE a = 1 ORDER BY b?
3. A query is slow. Walk through your diagnosis, from EXPLAIN to a fix.
4. Define ACID and explain how a database provides durability.
5. Explain dirty reads, non-repeatable reads, phantoms and write skew, and which isolation level prevents each.
6. How do you avoid a lost update on an inventory counter? Give three techniques.
7. What causes a deadlock and how do you reduce them?
8. How would you add a NOT NULL column to a table with 500 million rows without downtime?