Database Indexing for Web Applications

## Part 1: Why Do We Need Indexes in Web Databases?

Relational databases are remarkably good at answering questions, but by default they answer them the hard way — by reading every row and checking it against your predicate. Even a fast disk and a warm buffer pool cannot save a query that examines ten million rows to return twenty. Indexing — the practice of maintaining auxiliary ordered structures so the database can seek directly to the rows that matter — is where we bridge the gap between how data is stored and how it is asked for.

In this section we'll talk about how full-table scans, read replicas, and B-tree indexes differ — and why letting the database seek instead of scan makes indexing essential for building responsive, scalable web applications.

### The Full-Table Scan: Intuition

The simplest execution strategy is the sequential scan. The database reads the table from beginning to end, evaluates the WHERE clause on every row, and keeps the survivors:

> Query → read all N rows → filter → return k matches

This works when tables are small or when the query genuinely needs most rows. But it assumes:

- The table fits comfortably in memory, or you can afford the I/O.
- The cost of reading everything is acceptable at your request rate.
- Query latency may grow linearly with data volume forever.

For a 5,000-row lookup table, these assumptions often hold. For the orders table of a growing product, they never do.

### Read Replicas: Guiding with More Copies

An obvious fix is to scale out reads: add replicas and spread the queries. If one database scans too slowly, why not have five databases scan in parallel?

> Same slow query × more machines → more slow queries per second?

This approach adds throughput, but it breaks down quickly:

- Each replica still scans all N rows — you multiplied capacity, not efficiency; every query is exactly as slow as before.
- Replication lag introduces staleness that the application must now reason about.
- Cost scales with traffic, while a single well-placed index would have removed the work entirely.

Replicas are a throughput tool, not a latency tool. The question becomes: why is each query reading a million rows to return twenty?

### B-Tree Indexes: Seek First, Then Fetch

A B-tree index [1] answers that question with a two-stage strategy. Instead of scanning the table, the database:

1. **Seek**: descend the balanced tree of sorted key values to locate the first matching entry — a handful of page reads, regardless of table size.
2. **Fetch**: follow the index entries to the actual rows (or, for covering indexes, skip the table entirely).

This approach:

- Replaces O(N) scanning with O(log N) seeking — the difference between milliseconds and minutes at scale.
- Keeps entries sorted, so range predicates and ORDER BY come almost for free.
- Stays balanced under inserts and deletes, so performance does not decay as the table grows [2].

### The Common Feeling: "Isn't This Just a Sorted Copy?"

Many developers (myself included, at first) find indexing underwhelming. If you squint, it looks like we just:

- Kept a sorted list of one column's values.
- Attached a row pointer to each entry.

Isn't that just the index at the back of a book?

In practice, yes — that is exactly the right mental model. But conceptually, there are two crucial differences:

1. **Unit of access:**
- Scan: the database touches every row and asks "is this one relevant?"
- Index: the database touches only the entries that *are* relevant, plus a few tree pages to find them.
2. **Cost contract:**
- A scan's cost is set by how much data you have.
- An index's read cost is set by how much data you *ask for* — and you pay for that privilege on every write, which is now an explicit trade.

It's a subtle but important shift: from paying for the size of the table to paying for the size of the answer.

### Why the Distinction Matters in Real Applications

This difference is especially sharp for the bread-and-butter queries of web applications: "this user's orders," "recent posts in this thread," "active sessions for this account."

- **Scan setup:** The orders table holds 10 million rows. Fetching one customer's 20 recent orders reads all 10 million — at every page view.
- **Index setup:** A B-tree on (customer_id, created_at) descends three or four levels, lands on that customer's entries, and reads 20 of them. Done.

Formally, the page-read costs compare as:

> cost_scan ≈ N / rows_per_page   vs   cost_index ≈ log_B(N) + k

Where N is table rows, B is the tree's branching factor (hundreds, in practice), and k is the number of matching entries. For N = 10⁷ and k = 20, that is roughly 100,000 page reads versus about 25.

This is why a single missing index can dominate a system's entire performance profile — no amount of hardware closes a four-orders-of-magnitude gap.

### Advanced Variants: Beyond the Single-Column Index

When queries filter on several columns or need to avoid touching the table at all, single-column indexes stop being enough. Richer designs address this:

- **Composite indexes**: index (a, b, c) so equality on a and b plus a range on c is answered by one contiguous slice of the tree [5].
- **Covering indexes**: include every column the query needs, so the plan never visits the table — an index-only scan.
- **Partial indexes**: index only the rows that matter (e.g., WHERE status = 'active'), keeping the tree small and the writes cheap [6].

The guidance is structural: the index is designed around the query's shape, not around the table's columns.

### Intuition

- Scan: "Read everything, keep what matches."
- Replicas: "Read everything, on more machines."
- Index: "Open the book to the right page — the table of contents already knows where it is."

### Conclusion

Indexing in web databases can feel, at first, like we're just keeping sorted copies of columns. But the shift in cost contract — paying for the answer instead of the table — is what makes it different from throwing hardware at slow queries. For tiny tables, scans are sufficient. For selective queries on growing tables, B-trees unlock logarithmic access. For hot query paths, composite and covering indexes show the full potential: the database answers from the index alone and the table becomes almost incidental.

That's why indexing — in one form or another — remains central to shaping how databases not only store data, but also answer for it at scale.

## Part 2: How to Design Effective Indexes

This is a recap of my working notes from tuning query plans on several production schemas, cross-checked against Markus Winand's SQL Performance Explained [5] and Graefe's survey of modern B-tree techniques [4]. If you find this interesting, I highly recommend going through both.

### Indexing Setup in the Database Context

- Table (T): the heap of rows, in no useful order
- Query (q): the SQL statement whose latency we care about
- Predicate (p): the WHERE/JOIN/ORDER BY conditions that define which rows matter
- Selectivity (s): the fraction of rows a predicate keeps — lower is better for indexes
- Index (I): the ordered auxiliary structure the optimizer may use
- Plan (P): the execution strategy the optimizer picks given T, q, and available indexes [3]

Unlike rewriting the application, indexing modifies the access path instead of the query — a CREATE INDEX changes the plan without touching a line of code, which makes it the cheapest big win in performance work.

### Naive Indexing: One Index per Column

The simplest strategy is reflexive: whenever a column shows up in a WHERE clause, index it. The implied objective is:

> min cost(P) by indexing every referenced column independently

Interpretation: hope the optimizer combines single-column indexes into a fast plan for every query shape.

- If queries filter on one selective column at a time (e.g., a unique email lookup), this works.
- If queries combine filters, sort, and paginate — which is every real listing page — this often fails.

This is like indexing a book one letter at a time and hoping readers cross-reference. The problems:

- **Write amplification**: every INSERT and UPDATE must maintain every index — ten indexes means ten extra tree updates per write.
- **Weak combination**: merging two single-column indexes is far less efficient than one composite index matching the query's shape.
- **Low-selectivity traps**: an index on status with three distinct values filters almost nothing; the optimizer rightly ignores it, but you still pay its write cost.

As I noted in my tuning logs: unused indexes are pure liability — they slow every write and speed no read. Audit them like you audit dependencies.

### Query-Driven Indexing: Designing from the Predicate

To index effectively, start from the query and derive the index. The design rules:

- **Leftmost prefix**: a composite index on (a, b, c) serves queries filtering on (a), (a, b), or (a, b, c) — but not (b, c) alone. Column order is the design [5].
- **Equality first, range last**: place equality-tested columns before range-tested ones, so matches form one contiguous slice of the tree.
- **Sort into the index**: if the index order matches ORDER BY, the database skips the sort entirely — pagination becomes a pure seek.
- **Cover when hot**: for the hottest queries, include the selected columns so the plan never touches the table.

Intuition: don't index columns; index queries. The index should read like a description of your WHERE clause.

### The Index Design Algorithm

Algorithm: Index Design Workflow

1. Collect the slowest and most frequent queries from the query log — frequency × cost, not gut feeling
2. For each query, write down the predicate shape: equality columns, range columns, sort order, selected columns
3. Draft a composite index: equality columns first (most selective first), then the range or sort column
4. Check the leftmost-prefix rule against other queries — one good composite often replaces several single-column indexes
5. Verify with EXPLAIN: confirm the plan uses the index and estimate rows touched
6. Measure write impact: benchmark INSERT/UPDATE latency with the new index in place
7. Audit quarterly: drop indexes with zero scans — they cost writes and buy nothing

#### Key insights:

- Step 3: Column order is the whole game — (customer_id, created_at) and (created_at, customer_id) are entirely different indexes.
- Step 5: EXPLAIN is your ground truth — an index the optimizer won't use is indistinguishable from no index, except on writes.
- Step 7: Every index is a standing tax on writes; collect rent from it in reads, or evict it.

### The Role of Selectivity and Index Count

In index design, selectivity and count each serve distinct roles in balancing read speed against write cost:

**Selectivity**

- Defined by the fraction of rows a predicate keeps: an email lookup keeps one row in millions; a status filter keeps a third of the table.
- Used to decide what deserves to lead an index — high-selectivity columns concentrate the tree's power where it pays.
- Intuition: "Index the questions with sharp answers, not the ones half the table satisfies."

**Index Count**

- Typically 3-6 indexes per busy table; more may help read-heavy tables, but diminishing returns apply.
- Why? Because every index is maintained on every write — index count is a direct multiplier on write latency and storage.
- Intuition: "Give the optimizer enough paths to answer well, but not so many that every write pays for paths nobody takes."

**Why Both Matter**

- Selective, well-ordered indexes ensure reads are logarithmic; a disciplined count ensures writes stay flat.
- A low-selectivity index is worse than none: it costs writes while the optimizer ignores it.
- Too few indexes force scans on hot paths; too many turn a busy table's writes into a tour of a dozen trees.

### Analogy to Caching

Caching (see Caching Strategies for Web Applications) also precomputes work to speed reads, but with key differences:

- **Caching**: stores full answers outside the database — fast, but stale by contract and scoped to exact keys.
- **Indexing**: stores ordered access paths inside the database — always transactionally current, and composable across arbitrary predicates.

In practice they are complements, not competitors: index so the truth is cheap to compute, cache so the popular truths are free to serve.

### TL;DR:

- Selectivity: Determines whether an index concentrates or wastes the tree's power → lead with the sharpest columns.
- Index Count: A standing tax on every write → 3-6 well-designed composites beat a dozen reflexive singles.

### A Toy Example: The Orders Listing Query

Let's walk through a simple toy environment: a 10-million-row orders table, and the account page query that every customer hits.

#### Schema and Query

```sql
CREATE TABLE orders (
id bigint PRIMARY KEY,
customer_id bigint NOT NULL,
status text NOT NULL,
total_cents integer NOT NULL,
created_at timestamptz NOT NULL
);

-- The hot query on the account page:
SELECT id, status, total_cents, created_at
FROM orders
WHERE customer_id = 42
AND status = 'shipped'
ORDER BY created_at DESC
LIMIT 20;
```

#### Index Design

Equality columns first (customer_id, status), then the sort column (created_at):

```sql
CREATE INDEX idx_orders_customer_status_created
ON orders (customer_id, status, created_at DESC);

-- Covering variant for the hottest path: no table visit at all
CREATE INDEX idx_orders_listing
ON orders (customer_id, status, created_at DESC)
INCLUDE (total_cents);
```

#### Verifying the Plan

```sql
EXPLAIN (ANALYZE, BUFFERS)
SELECT id, status, total_cents, created_at
FROM orders
WHERE customer_id = 42 AND status = 'shipped'
ORDER BY created_at DESC LIMIT 20;

-- Before: Seq Scan on orders
-- rows=10,000,000 scanned, ~2,400 ms, sort required
-- After: Index Only Scan using idx_orders_listing
-- rows=20 fetched, ~0.4 ms, no sort (index order matches)
```

The plan tells the whole story: same query, same data, four orders of magnitude less work — because the index was shaped like the question.

### Conclusions

- Index shape vs performance: One composite index matching the predicate beats any pile of single-column indexes the optimizer must merge.
- Plan verification: EXPLAIN is the contract — design from the query log, confirm with the plan, and never assume an index is used.
- Flexibility: CREATE INDEX changes the access path without touching application code, making it the highest-leverage fix in the database toolbox.
- Scaling: The toy example is one table, but production indexing involves query-log-driven audits, write-latency budgets, partial indexes for skewed data, and dropping what the optimizer no longer uses.

Read replicas can only multiply the machines doing wasteful scans. Indexes remove the waste itself, for every machine at once. While toy demos like "the orders listing" are simple, the mechanics mirror how query-driven index design keeps real web databases answering in milliseconds as tables grow a thousandfold.

## References

1. Bayer, R., and McCreight, E. "Organization and Maintenance of Large Ordered Indexes." Acta Informatica (1972).
2. Comer, D. "The Ubiquitous B-Tree." ACM Computing Surveys (1979).
3. Selinger, P., et al. "Access Path Selection in a Relational Database Management System." SIGMOD (1979).
4. Graefe, G. "Modern B-Tree Techniques." Foundations and Trends in Databases (2011).
5. Winand, M. "SQL Performance Explained: Everything Developers Need to Know about SQL Performance." (2012).
6. PostgreSQL Global Development Group. "PostgreSQL Documentation: Indexes." (2024).
7. O'Neil, P., et al. "The Log-Structured Merge-Tree (LSM-Tree)." Acta Informatica (1996).
8. Stonebraker, M., and Rowe, L. "The Design of POSTGRES." SIGMOD (1986).