Indexes, Cardinality & EXPLAIN Plans

Overview

Indexes are the difference between a query that finishes in milliseconds and one that locks a primary under load for minutes. In production you diagnose regressions with EXPLAIN (ANALYZE, BUFFERS), not gut feel.

This lesson is Postgres-centric (the industry interview default) with concepts that transfer to MySQL/InnoDB and other engines.

Senior candidates are expected to:

• Explain B-tree vs hash and when each is usable.
• Reason about selectivity / cardinality and why the planner picks Seq Scan over Index Scan.
• Design composite / covering indexes using the leftmost-prefix rule.
• Read cost, rows, actual time, buffers, and join algorithms (nested loop / hash / merge).
• Name classic pitfalls: functions on indexed columns, leading-wildcard LIKE, low-selectivity indexes, and write amplification from over-indexing.

1. 1

   status, created_at, user_id → planner shrugs

   Spray single-column indexes

   Low-selectivity leading columns, no leftmost prefix for the real query, heap fetches on SELECT *. Writes pay for indexes nobody uses.

2. 2

   query shape → CREATE INDEX

   Winner: AM by operator, composite by equality-then-range

   B-tree for = / range / ORDER BY. GIN for arrays/JSONB/FTS. GiST for ranges/geometry/trigram. Drill: access methods and composites.

3. ?

   Prove it with stats + ANALYZE, not vibes

   Selectivity and n_distinct decide Seq vs Index (statistics). EXPLAIN (ANALYZE, BUFFERS) is truth (EXPLAIN). Sparse predicates and LOWER(email) belong on partial / expression indexes.

Index leaf → table heap

Leaf entries store the indexed key(s) plus a pointer to the heap tuple (ctid in Postgres). An Index Scan walks the tree, then fetches heap pages (random I/O unless the clustering factor is excellent). An Index-Only Scan can skip the heap when all needed columns are in the index and the visibility map says the page is all-visible.

flowchart TB
  root["Root page"]
  i1["Internal page"]
  i2["Internal page"]
  l1["Leaf: key to CTID"]
  root -->|Root page to Internal page| i1
  root -->|Root page to Internal page| i2
  i1 -->|Internal page to Leaf: key to CTID| l1

Planner choosing scan + join

The planner is a cost-based optimizer: it estimates I/O and CPU for candidate plans using table statistics (pg_statistic / ANALYZE), then picks the lowest total cost. Wrong stats → wrong plan.

B-tree indexes (the default)

Postgres B-trees are balanced multi-way trees. They support any type with a well-defined sort order and are the default for CREATE INDEX.

Range queries are the killer feature vs hash: the leaf level is sorted and doubly linked, so a range is a contiguous leaf walk.

Structure intuition:

1. Start at the root; each internal key guides which child page to follow.
2. Descend until a leaf; binary-search within the leaf page.
3. For equality: collect matching leaf entries → fetch heap via CTIDs.
4. For range: walk sibling leaves until the upper bound.

Typical fan-out is large (hundreds of keys per page), so tree height is usually 3–4 even for huge tables. Most I/O cost is leaf + heap, not root→leaf.

Hash indexes (narrow but useful)

Postgres hash indexes store a 32-bit hash of the value, not the value itself.

Capabilities:

• Only = (equality). No ranges, no ORDER BY, no uniqueness enforcement.
• Single-column only.
• Fully crash-safe since Postgres 10+.
• No size limit on the indexed value (only the hash is stored).

When to consider hash: pure equality lookups on large values (e.g. long tokens) where B-tree leaf entries would be huge. Default interview advice: prefer B-tree unless you have a measured reason; B-tree covers equality and ranges/sorts with one index type. GIN, GiST, BRIN, and operator classes: B-tree vs hash vs GIN vs GiST.

CREATE INDEX orders_token_hash ON orders USING hash (session_token);
-- Only helps: WHERE session_token = $1
-- Does NOT help: WHERE session_token > $1  OR  ORDER BY session_token

Selectivity, cardinality, and statistics

Definitions:

• Cardinality of a column: number of distinct values (n_distinct in Postgres stats).
• Selectivity of a predicate: fraction of rows expected to match (0..1). High selectivity = few rows = good for index seeks.
• Selectivity ≈ 1 / n_distinct for equality on uniform data (rough heuristic).

Example: status with values {active, inactive} → selectivity ~0.5. An index on status alone is often useless: half the table is not "few rows," and random heap fetches lose to a sequential scan.

Why the planner may ignore your index

Estimated cost of Index Scan ≈:

random_page_cost × (index_pages + heap_pages_fetched) + CPU

Estimated cost of Seq Scan ≈:

seq_page_cost × table_pages + CPU

If selectivity is poor or the table is small / mostly cached, Seq Scan wins. That is not a bug.

Keep stats fresh:

ANALYZE orders;
-- Or rely on autovacuum ANALYZE; check last_analyze in pg_stat_user_tables

Skewed data (e.g. 99% of rows share one value) needs good histograms / MCV lists; stale stats cause catastrophic row estimates. MCV vs histogram vs correlation, and why n_distinct = -1 matters: selectivity, cardinality & statistics.

The sandbox below is a toy cost model for interview intuition — not Postgres's real planner. No database required.

Press Run. Snippets must be self-contained — no network, files, or native modules.

Leftmost prefix, INCLUDE, and index-only scans in depth: composite & covering indexes. Partial WHERE deleted_at IS NULL and LOWER(email): partial & expression indexes.

Composite indexes and the leftmost-prefix rule

CREATE INDEX idx_orders_user_created
  ON orders (user_id, created_at);

This index efficiently supports:

1. WHERE user_id = $1
2. WHERE user_id = $1 AND created_at > $2
3. WHERE user_id = $1 ORDER BY created_at

It does not efficiently seek on WHERE created_at > $2 alone (not a leftmost prefix).

WHERE created_at = $2 AND user_id = $1 still works for both columns if equality on user_id is present — column order in the index definition matters for seek range, not order in the SQL WHERE clause.

Rule of thumb for column order: equality / high-selectivity leading columns first; range / sort columns after.

Good:  (tenant_id, status, created_at)   -- filter tenant + status, sort/range on time
Bad:   (created_at, tenant_id)           -- time-first wastes selectivity for tenant lookups

Press Run. Snippets must be self-contained — no network, files, or native modules.

Covering indexes and index-only scans

A covering index contains every column the query needs (filters + SELECT list), so the engine can answer from the index alone.

Postgres 11+ INCLUDE adds non-key columns stored only in leaves (cannot be used for seeking, but enable covering):

CREATE INDEX idx_orders_user_covering
  ON orders (user_id, created_at)
  INCLUDE (status, total_cents);

-- Index-only eligible (when visibility map cooperates):
SELECT status, total_cents
FROM orders
WHERE user_id = $1 AND created_at > $2;

In EXPLAIN, look for Index Only Scan and Heap Fetches: 0 (ideal). Non-zero heap fetches mean visibility checks still touched the heap.

Trade-off: wider indexes → more write amplification and disk. Cover hot read paths; do not INCLUDE everything "just in case." SELECT * is the enemy of index-only scans.

Scan types you must recognize

Bitmap scans reduce random I/O vs many scattered Index Scan heap fetches when selectivity is moderate.

Join algorithms

Nested Loop Join — for each outer row, probe the inner side. Excellent when the outer is small and the inner has a selective index on the join key (parameterized index scan). Terrible when both sides are large without indexes.

Hash Join — build a hash table on the smaller side, probe with the larger. Great for large equijoins without useful order. Needs memory (work_mem); spills to disk in batches if needed.

Merge Join — requires both inputs sorted on the join key (via Index Scan order or explicit Sort). Efficient for large sorted equijoins / range joins; can stream.

Interview cue: Nested loop + index on inner = OLTP point lookups. Hash join = analytics / large joins. Merge join = both sides already ordered (or cheap to sort).

Reading EXPLAIN and EXPLAIN ANALYZE

EXPLAIN SELECT ...;                                   -- plan + estimates only
EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) SELECT ...;   -- runs query; real timings + I/O
EXPLAIN (ANALYZE, BUFFERS, FORMAT JSON) SELECT ...;   -- machine-parseable

Reading order tip: start at the innermost / topmost leaf scans, then work up to joins. Check estimate vs actual at every node. Inner nested-loop costs are per iteration — multiply by loops.

Example annotated plan (illustrative)

Nested Loop  (cost=0.58..16.50 rows=5 width=40) (actual time=0.040..0.120 rows=5 loops=1)
  Buffers: shared hit=20
  ->  Index Scan using users_pkey on users
        Index Cond: (id = 42)
        (actual time=0.010..0.011 rows=1 loops=1)
  ->  Index Scan using idx_orders_user_created on orders
        Index Cond: (user_id = 42)
        (actual time=0.020..0.090 rows=5 loops=1)
Planning Time: 0.200 ms
Execution Time: 0.150 ms

This is the OLTP happy path: one user by primary key, then a parameterized index scan on orders. Estimates match actuals.

Flag bad estimates (in-memory EXPLAIN JSON)

Classic interview drill: walk the plan tree and flag 10× misestimates. Feed this after EXPLAIN (ANALYZE, FORMAT JSON) — here we stub the JSON.

Press Run. Snippets must be self-contained — no network, files, or native modules.

When indexes hurt

1. Write amplification: every INSERT/UPDATE/DELETE maintains every index. Hot write tables with 15 indexes die quietly.
2. Low-selectivity indexes: boolean / low-cardinality columns waste space and confuse juniors ("why isn't it used?").
3. Redundant indexes: (a,b) already covers lookups on (a); a separate (a) is often waste.
4. Wrong column order: composite that never matches query patterns.
5. Blocking index builds: use CREATE INDEX CONCURRENTLY in prod (longer, non-blocking).
6. Bloated indexes: heavy updates leave dead tuples; REINDEX / pg_repack when needed.

TypeScript sketches (same ideas)

Interview-friendly twins of the Python toys — for reviews and design docs, not a live database.

interface TableStats {
  nRows: number;
  pageCount: number;
  randomFetchFactor?: number;
}

function equalitySelectivity(nDistinct: number): number {
  return 1 / Math.max(nDistinct, 1);
}

function estimateSeqCost(stats: TableStats, seqPageCost = 1): number {
  return stats.pageCount * seqPageCost;
}

function estimateIndexCost(
  stats: TableStats,
  selectivity: number,
  randomPageCost = 4,
  indexLeafPages = 50,
): number {
  const matchingRows = stats.nRows * selectivity;
  const factor = stats.randomFetchFactor ?? 0.8;
  const heapPages = Math.min(
    stats.pageCount,
    (matchingRows / 100) * factor,
  );
  return (indexLeafPages + heapPages) * randomPageCost;
}

export function recommendScan(
  stats: TableStats,
  nDistinct: number,
): { selectivity: number; choose: "Index Scan" | "Seq Scan" } {
  const selectivity = equalitySelectivity(nDistinct);
  const seq = estimateSeqCost(stats);
  const idx = estimateIndexCost(stats, selectivity);
  return {
    selectivity,
    choose: idx < seq ? "Index Scan" : "Seq Scan",
  };
}

console.log("user_id", recommendScan({ nRows: 1e7, pageCount: 2e5 }, 1e6));
console.log("status", recommendScan({ nRows: 1e7, pageCount: 2e5, randomFetchFactor: 1 }, 2));

type PredKind = "eq" | "range";

export function canSeek(
  indexCols: string[],
  predicates: Record<string, PredKind>,
): boolean {
  let seenRange = false;
  let usedAny = false;
  for (const col of indexCols) {
    const kind = predicates[col];
    if (kind === undefined) break;
    if (seenRange) break;
    usedAny = true;
    if (kind === "range") seenRange = true;
  }
  return usedAny;
}

const IDX = ["user_id", "created_at"];
console.assert(canSeek(IDX, { user_id: "eq" }) === true);
console.assert(canSeek(IDX, { user_id: "eq", created_at: "range" }) === true);
console.assert(canSeek(IDX, { created_at: "range" }) === false);

SQL anti-patterns vs fixes

-- Function on column: index on email cannot seek
SELECT * FROM users WHERE lower(email) = lower($1);

-- Expression index (or store normalized email) restores seek
CREATE INDEX users_email_lower ON users (lower(email));
SELECT * FROM users WHERE lower(email) = lower($1);

-- Leading wildcard: cannot use B-tree seek
SELECT * FROM products WHERE name LIKE '%' || $1 || '%';

-- Prefix match can use B-tree (watch collation / varchar_pattern_ops)
SELECT * FROM products WHERE name LIKE $1 || '%';

-- Low-selectivity alone is often useless
CREATE INDEX orders_status ON orders (status);

-- Partial index: only the rare / hot slice
CREATE INDEX orders_open ON orders (created_at)
  WHERE status = 'open';

interface PlanNode {
  "Node Type": string;
  "Plan Rows"?: number;
  "Actual Rows"?: number;
  "Actual Loops"?: number;
  Plans?: PlanNode[];
}

function* walkPlan(node: PlanNode, path = "root"): Generator<{
  path: string;
  node: string;
  estimated: number;
  actualTotal: number;
  ratio: number;
}> {
  const planRows = node["Plan Rows"];
  const actualRows = node["Actual Rows"];
  const loops = node["Actual Loops"] ?? 1;
  if (planRows != null && actualRows != null) {
    const actualTotal = actualRows * loops;
    const ratio = actualTotal / Math.max(planRows, 1);
    if (ratio >= 10 || ratio <= 0.1) {
      yield {
        path,
        node: node["Node Type"],
        estimated: planRows,
        actualTotal,
        ratio: Math.round(ratio * 100) / 100,
      };
    }
  }
  (node.Plans ?? []).forEach((child, i) => {
    const gen = walkPlan(child, `${path}/${node["Node Type"]}[${i}]`);
    for (const hit of gen) yield hit;
  });
}

Interview Q&A

Pitfalls

1. Function / cast on indexed column — lower(col), col::text, DATE(ts) defeat seeks; use ranges or expression indexes.
2. Leading-wildcard LIKE '%x' / regex — B-tree cannot seek; consider pg_trgm GIN for substring search.
3. Low-selectivity indexes — gender, boolean, status alone; prefer composite or partial indexes.
4. Over-indexing — write latency, bloat, vacuum cost; audit with pg_stat_user_indexes.idx_scan.
5. SELECT * blocking index-only scans — fetch only needed columns.
6. Stale statistics — after bulk loads, run ANALYZE; watch estimate vs actual.
7. OR conditions — may need bitmap scans or rewrite to UNION ALL.
8. Assuming MySQL/Postgres identical EXPLAIN — learn your engine's nodes; concepts transfer, names differ.
9. Running EXPLAIN ANALYZE on writes without a transaction — it executes the DML.
10. Ignoring loops — inner nested-loop costs are per iteration; multiply.

Go Deeper

• PostgreSQL Docs — Using EXPLAIN — plan nodes, ANALYZE, and buffers
• PostgreSQL Docs — EXPLAIN command — options (ANALYZE, BUFFERS, FORMAT)
• PostgreSQL Docs — Index Types — B-tree and hash, when each AM applies
• PostgreSQL Docs — Multicolumn Indexes — leftmost prefix and skip-scan notes
• PostgreSQL Docs — Hash Indexes — equality-only hash AM details
• Use The Index Luke — Covering Indexes / Index-Only Scan — Markus Winand's cross-engine classic
• Use The Index Luke — The Where Clause — predicates, selectivity, access vs filter
• pganalyze — How Postgres Chooses Which Index — parameterized scans and join interaction
• Reading plans without guessing: EXPLAIN & EXPLAIN ANALYZE

Cluster: access methods · composites · stats · EXPLAIN · partial / expression

One-page cheat sheet

Selectivity high + random_page_cost matters → Index Scan / Index-Only
Selectivity low / fat result → Seq Scan or Bitmap Heap Scan
Equality only, huge keys → consider HASH (rare)
Composite: put equality cols left, range/sort right
Cover hot reads with INCLUDE; don't cover everything
EXPLAIN = estimates; EXPLAIN ANALYZE = truth + time
Always compare Plan Rows vs Actual Rows
Indexes speed reads, tax writes — measure both