Indexes, transactions & query plans

How does a B-tree index work, and when will the database ignore yours?

A B-tree stores keys sorted in a shallow balanced tree, so lookups, range scans and ordered reads are O(log n). It can serve =, <, >, BETWEEN, IN, LIKE 'prefix%', and ORDER BY on the indexed columns.

It will not be used when:

WHERE lower(email) = 'a@b.com'      -- function on the column; needs an expression index
WHERE created_at::date = '2025-01-01'  -- same; use a range: >= '2025-01-01' AND < '2025-01-02'
WHERE name LIKE '%smith'            -- leading wildcard; needs trigram or full-text
WHERE amount + fee > 100            -- expression; index the expression or store it
WHERE user_id = '42'                -- type mismatch forcing a cast on the column side

It is also ignored when the planner estimates it would return a large fraction of the table — a sequential scan really is cheaper then, and "why isn't it using my index?" often has the answer "because it shouldn't".

What is a composite index, and why does column order matter?

A composite index on (a, b, c) is sorted by a, then b, then c — the leftmost prefix rule. It serves WHERE a=…, a=… AND b=…, a=… AND b=… AND c=…, but not WHERE b=… alone.

CREATE INDEX ON orders (tenant_id, status, created_at DESC);
-- serves: tenant + status + ordered by created_at  ← the exact shape of a paginated list view

Design rule: equality columns first, then the range/sort column last. An index on (created_at, tenant_id) is nearly useless for WHERE tenant_id = 5 ORDER BY created_at because the range column comes first and destroys the ordering within a tenant.

What is a covering index and an index-only scan?

If every column a query needs is in the index, the database never touches the heap — an index-only scan. In Postgres, INCLUDE adds payload columns to the leaf pages without making them part of the key:

CREATE INDEX ON orders (tenant_id, created_at DESC) INCLUDE (total, status);

Caveat worth mentioning: Postgres index-only scans still need the visibility map to be current, so they degrade after heavy writes until VACUUM runs. In MySQL/InnoDB the primary key is clustered and every secondary index implicitly contains it, which is why a large random primary key (UUIDv4) is expensive there — it bloats every index and destroys insert locality. UUIDv7 (time-ordered) fixes the locality problem.

Which other index types should you know?

• Hash — equality only; rarely worth it over a B-tree in Postgres.
• GIN — inverted index for arrays, jsonb containment (@>), and full-text search. Large and slower to update; fastupdate batches writes.
• GiST / SP-GiST — geometric, range and nearest-neighbour queries (PostGIS).
• BRIN — tiny; stores min/max per block range. Excellent for naturally-ordered append-only data (a time-series table), useless if the data is unordered.
• Partial — CREATE INDEX ON orders (created_at) WHERE status = 'pending' — small and hot when you always filter on the same predicate.
• Expression — CREATE INDEX ON users (lower(email)) to make the function-call query indexable.

Also know the costs: every index slows INSERT/UPDATE/DELETE, consumes cache memory, and unused indexes are pure overhead — find them with pg_stat_user_indexes where idx_scan = 0.

Explain the isolation levels and the anomalies they prevent.

• Dirty read — seeing another transaction's uncommitted data.
• Non-repeatable read — the same row read twice returns different values.
• Phantom — the same WHERE returns different rows on re-execution.
• Write skew — two transactions each read a consistent state and each write something that, together, violates an invariant (the classic: two doctors both go off-call because each sees one other on call).

Postgres defaults to Read Committed (each statement sees a fresh snapshot); MySQL/InnoDB defaults to Repeatable Read. Postgres implements Serializable with SSI, which detects conflicts and aborts one transaction with a serialisation failure — so your application must retry. Say that: choosing Serializable without a retry loop is a bug.

When do you use SELECT … FOR UPDATE?

To take a row lock so a read-modify-write is safe:

BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;   -- blocks other writers
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;

Variants: FOR NO KEY UPDATE (weaker, allows FK references), FOR SHARE, NOWAIT (fail immediately instead of waiting), and SKIP LOCKED — which is how you implement a work queue in a table:

UPDATE jobs SET status='running'
WHERE id IN (SELECT id FROM jobs WHERE status='queued'
             ORDER BY created_at FOR UPDATE SKIP LOCKED LIMIT 10)
RETURNING *;

But note: many read-modify-writes do not need a lock at all. UPDATE accounts SET balance = balance - 100 WHERE id = 1 AND balance >= 100 is atomic and checks the invariant in one statement.

What causes deadlocks and how do you prevent them?

Two transactions acquire the same locks in opposite orders and wait on each other; the database detects the cycle and kills one. Prevention: acquire locks in a consistent order (sort by primary key before updating a batch), keep transactions short, use a single statement where possible, lower the isolation level if you do not need the guarantee, and add a retry with backoff — deadlocks are a normal consequence of concurrency, not necessarily a bug. Diagnose with the database's deadlock log, which prints both statements involved.

How do you read an EXPLAIN ANALYZE plan?

EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) SELECT …;

Read the tree inside-out; each node shows cost=start..total rows=estimate width=bytes then actual time=… rows=… loops=….

What to look for:

1. Estimate vs actual row counts. A 100x discrepancy means stale statistics (ANALYZE) or a correlation the planner cannot see (consider extended statistics).
2. Seq Scan on a big table with a selective filter → missing index.
3. Nested Loop with a large outer row count → the inner side runs that many times; usually wants a hash join or a better index.
4. Sort with Sort Method: external merge Disk: … → raise work_mem or add an index that provides the ordering.
5. Buffers: shared read (from disk) vs shared hit (cache) tells you whether it is an I/O or a CPU problem.
6. Rows Removed by Filter — the work the database did and then threw away, which is the clearest sign of a missing index.

What is MVCC, and what is table bloat?

Under multi-version concurrency control, an UPDATE writes a new row version and marks the old one dead rather than overwriting in place — so readers never block writers and writers never block readers. The cost is dead tuples that VACUUM must reclaim, and autovacuum not keeping up on a write-heavy table causes bloat: the table and its indexes grow, cache hit rate falls, and scans get slower.

Related things to know: long-running transactions (and idle-in-transaction sessions) prevent vacuuming of anything newer than their snapshot — one forgotten BEGIN in a console can bloat a database; VACUUM FULL rewrites the table but takes an exclusive lock (use pg_repack instead); and transaction-ID wraparound is the emergency autovacuum exists to prevent.

How do you scale a relational database — in order?

1. Fix the queries. Indexes, N+1s, SELECT *, deep offsets. Most "we need to shard" conversations end here.
2. Cache the hot read paths, and use connection pooling (PgBouncer) — thousands of app connections against Postgres is itself a cause of collapse.
3. Read replicas for read-heavy traffic. Accept replication lag and route read-after-write to the primary.
4. Partition big tables by time or tenant (declarative partitioning) so old data can be dropped cheaply and scans stay small.
5. Vertical scale — often the cheapest real fix; hardware is less expensive than distributed-systems complexity.
6. Shard by tenant/user id, or move to a distributed SQL engine (CockroachDB, Vitess, Citus). Now you have cross-shard joins, distributed transactions and resharding to manage.

The point of the ordering is that steps 1-5 solve almost everything, and step 6 is where most of the operational pain lives. Say that out loud.