Database Indexing

An index is an extra access path that trades storage and write work for less read work. It is not a general “make queries fast” switch. Explain which rows a query needs, which order it needs them in, and how the index lets the database avoid visiting unrelated data. Then account for the cost of maintaining that access path on every change.

Learning goals

B-tree intuition; selectivity; composite key ordering; covering and partial indexes; query plans; write amplification; pagination; maintenance cost.

The mechanism at a glance

Figure — Query tenant + cursor → B-tree root (seek); B-tree root → Tenant range (narrow); Tenant range → Recent failed keys (ordered scan); Recent failed keys → Table rows (fetch if needed); Table rows → 50 results (limit)

The numbered components identify responsibilities. Follow the labeled arrows rather than treating the numbers as a global execution order. The scenario later in this lesson shows one concrete sequence.

Step-by-step reasoning

1. Think in ordered keys

A B-tree organizes keys so a search can narrow to a range instead of scanning every row. Equality and ordered range queries are natural uses. The actual cost also includes fetching table pages, cache behavior, and the number of qualifying rows. If a predicate matches most of the table, a sequential scan may be cheaper than many scattered lookups.

2. Match the common query

For a tenant’s newest failed deliveries, start with tenant equality, then the relevant status and time ordering. Add id as a deterministic tie-breaker. Composite key order matters because it controls which contiguous ranges are easy to find. Do not assume an index designed for tenant-first queries is equally effective for a global time-only query.

3. Use specialized indexes deliberately

A partial index can include only failed rows when that predicate matches the workload. A covering index includes selected values to reduce table visits, although visibility and engine details still matter. Both increase write and maintenance costs. Avoid adding every column just to make a hypothetical query index-only; large indexes reduce cache efficiency.

4. Read plans and measure

Use an execution plan to compare estimated and actual rows, scan type, sort work, and buffer access. EXPLAIN ANALYZE actually runs the statement, so use a safe environment for mutations. Test representative tenant sizes and skew rather than a tiny uniform fixture. Revisit indexes when the data distribution or dominant query changes.

Contracts and state

The following sketch makes the decision boundary concrete. Field names and capacity assumptions are illustrative; adapt them to the stated product contract.

CREATE INDEX delivery_failed_recent
ON delivery (tenant_id, created_at DESC, id DESC)
WHERE state = 'failed';

SELECT id, created_at FROM delivery
WHERE tenant_id = :tenant AND state = 'failed'
  AND (created_at, id) < (:cursor_time, :cursor_id)
ORDER BY created_at DESC, id DESC LIMIT 50;

Worked example

A table has 100 million delivery rows, but one tenant has 200,000 and only 2,000 failed. An index on state alone first finds failed rows across every tenant. A tenant-scoped partial index can navigate directly to the relevant ordered range. These are illustrative counts, not a guaranteed speedup: confirm the plan, selected columns, data locality, and actual I/O. The cursor avoids walking through all prior pages just to reach the next 50 results.

Failure walkthrough

Indexes can make an overloaded write path worse. Updating a frequently indexed state column requires index maintenance, and building a large new index consumes resources. Plan the rollout and observe write latency, disk space, replication lag, and lock behavior. Remove unused indexes only after checking occasional operational queries and constraints that depend on them.

Figure — Receive stable cursor → Seek tenant and time range → Read next ordered keys → Fetch required columns → Return last key as cursor

Decisions and trade-offs

Check your understanding

Why might a status-only index be ignored when nearly every record is active?

Transfer to a new scenario

Serve a tenant's newest failed deliveries with an ordered composite index and a stable cursor.

Why might an index on status alone fail to improve a large table's common query?

Primary documentation

Read the first-party engineering account or official technical reference. Company engineering posts describe the scope and date of that publication; the interview reconstruction and scenarios here are original teaching examples.

Read an access path before adding an index

For a tenant inbox ordered newest first, an index on (tenant_id,created_at,id) can constrain the tenant and walk the desired range. An index on created_at alone may inspect many other tenants before finding enough rows. Column order is about predicates and ordering, not simply putting the most unique column first.

Use EXPLAIN and measured execution to inspect rows scanned, filtering, sorts and heap access. A planner may correctly choose a sequential scan when the query touches much of the table. A covering index can reduce table access but increases size and write work; visibility rules can still require heap checks in PostgreSQL.

Think of a B-tree as ordered pages that narrow a range, not a magic O(1) lookup. Inserts can split pages, updates maintain indexes and dead versions need cleanup. Each additional index consumes storage and write bandwidth. Test with realistic data distribution, including a very large tenant, because averages hide skew.

Figure — A decision worksheet for Database Indexing: read the mechanism and its guarantee together.

Operational sketch

CREATE INDEX inbox_recent ON delivery
 (tenant_id, created_at DESC, id DESC);
SELECT id,state FROM delivery
WHERE tenant_id = $1
  AND (created_at,id) < ($2,$3)
ORDER BY created_at DESC,id DESC LIMIT 50;

A tempting mistake

An index cannot fix a query that asks for an unbounded result. Running EXPLAIN ANALYZE executes the query, so use care for mutating statements and production load. Index creation also has operational cost and needs a rollout plan.

Transfer exercise

Why might an index on (tenant_id,created_at) not efficiently answer all tenants for one date?

Figure — A simplified B-tree range lookup. Real pages contain more entries and can have additional levels.