Databases
Intermediate 15 min read Databases

Indexing

The single highest-leverage database lever

An index is an auxiliary structure that turns a full scan into a pointed lookup. B-trees dominate, but composite, partial, covering, and expression indexes each trade write cost against a specific read.

B-treecomposite indexcovering indexpartial indexGINselectivity
Prerequisites: Indexes and Query Performance Explain and Query Plans
Before we start

What you will learn

  • Design a composite index whose column order matches the query's predicates
  • Differentiate covering, partial, and expression indexes
  • Measure the read/write trade-off rather than guess
Introduction

What is this?

An index maintains a small, sorted structure keyed on chosen columns so the query engine can jump to matching entries instead of scanning every row. B-tree indexes serve equality and range lookups; composite indexes serve multi-column predicates in column order; GIN/BRIN cover arrays, JSON, and huge ordered keysets.

Motivation

Why do you need it?

  • Index design is where a slow query becomes a 10x speedup with one statement.
  • REQUIRED slug: de-foundations links here as the canonical reference on indexing.
  • Every misdesigned index wastes write throughput, disk, and buffer-pool cache on every insert.
Think about it

Mental model

Imagine

A phone book sorted by last name

Think of

A B-tree index on last_name

A lookup on last_name is O(log n); a lookup by city is not in the book's order at all. That is exactly why composite indexes specify which column goes in which position.

Mechanics

How it works

  • A B-tree keeps keys in sorted order with fan-out pages; a search reads O(log n) pages from cache.
  • Composite index (a, b): useful for orderings and ranges on a, then filtered equality by b.
  • Indexes covering the whole SELECT let the engine answer without a table access (index-only scan).
  • Partial index WHERE active filters rows at build time, cutting size and write cost.
  • Don't forget: every index is a separate structure the engine must maintain on WRITE.
  • B-tree, GiST, and GIN indexes exist depending on value type arrays, geometry, and JSONB materialization.

From predicate to index strategy.

WHERE a = ? AND b = ?
WHERE a BETWEEN ? AND ?
WHERE lower(email) = ?
SELECT only indexed cols
Verify with EXPLAIN
Reference

Key commands

CREATE INDEX CONCURRENTLY idx_orders_region ON orders (region);

Build without locking the table against writes.

DROP INDEX idx_orders_region;

Rip out an index that is hurting writes and cache.

EXPLAIN (ANALYZE, BUFFERS) SELECT ...;

Prove Index Scan vs Seq Scan and count shared buffers.

Hands-on

Examples

Designing for the predicate, not the column list

Designing for the predicate, not the column list
-- Works well for: WHERE region='US' AND status='active' AND ts >= '2026-01-01'
CREATE INDEX idx_orders ON orders (region, status, ts);
 
-- Index-only possible for: SELECT region, status FROM orders WHERE ts >= ...
CREATE INDEX idx_orders_covering ON orders (region, status, ts) INCLUDE (total);
 
-- Partial: only ever index the hot slice
CREATE INDEX idx_orders_active ON orders (status) WHERE status = 'active';

Leftmost prefix: equality columns first, range column last; INCLUDE avoids a table fetch for returned columns.

Real world

In production

  • A reporting table adds a partial index on 'status=active' to keep the hot query on a thin structure.
  • A key-finding job creates a covering index for a lookup shape so no table I/O occurs on the path.
  • While adding an index on a 2B-row table, CONCURRENTLY keeps the pipeline serving writes.
Guidelines

Best practices

  • Start from the query: write predicates in order, put equality first, range column last.
  • Prefer few, wide, intended indexes over many narrow ones.
  • Measure with EXPLAIN; one misordered composite key beats any unverified theory.
  • Use index-only/covering indexes for the hottest read shapes.
Watch out

Common mistakes

  • Creating (b, a) while the query filters on a then b, defeating the leftmost-prefix.
  • Indexing every column of a hot INSERT table, multiplying write cost and bloating cache.
  • Wrapping a column in a function (WHERE lower(email) = ...) so a plain email index is never used without a matching expression index.
When things break

Debugging tips

  • Run EXPLAIN (ANALYZE, BUFFERS) before and after adding an index; if the plan still Seq Scans, the optimizer ignores you (or the index is wrong).
  • Compare 'Index Scan', 'Index Only Scan', and 'Bitmap Index Scan' to see if a covering setup is possible.
  • Check index size with pg_total_relation_size and dashboards for write latency after shipping new indexes.
Interviews

Interview checkpoint

Practice

Hands-on lab

Prove an Index With an SQLite Plan
25 min · intermediate
In progress
Objectives
  • Generate a million rows in SQLite
  • Compare SEQ SCAN vs INDEX SCAN on the same predicate
  • Build a composite and a covering index and test each

Prove an Index With an SQLite Plan

25 min · intermediate

0/5 steps
0%
sandbox · Linux sandbox
$
Try these commands
Test yourself

Quick quiz

0/2
1

Which index best serves WHERE region='US' AND ts BETWEEN ? AND ??

2

An index speeds reads but sets a baseline write cost on every INSERT/UPDATE/DELETE.

Go deeper

Official documentation

PostgreSQL indexes
docs
MySQL CREATE INDEX
docs
SQLite query planner & indexes
docs