Database Indexes and Query Performance: How to Make Reads Fast

Pixly's photos table passes 50 million rows. A user opens their profile, and the query "this user's photos, newest first" suddenly takes four seconds. Nothing in the code changed. The only difference is that the table grew. Add the right index and the same query takes a few milliseconds, whether the table has 50 million rows or 5 billion.

Indexes are the cheapest, most powerful performance tool in a database, and they are where you should look before reaching for caches, replicas or sharding. This article explains how they work, how to choose them, and what they cost.

• What happens when a query has no index to use.
• What a B-tree index is, and why it stays fast as data grows.
• Composite indexes and why column order matters.
• Covering, partial and expression indexes.
• Selectivity: when an index is not worth using.
• How to read a query plan at a high level, and why indexes are sometimes ignored.
• What indexes cost on writes and storage.
• The order in which to try performance fixes.

Without a suitable index, the database answers WHERE owner_id = 42 by reading every row and checking each one: a full table scan (PostgreSQL shows it as a "Seq Scan"). The work grows linearly with the table. That is fine for 2,000 rows and a disaster for 50 million, especially when the query runs hundreds of times per second, because each scan also pushes useful data out of memory.

The idea of an index is the same as the index at the back of a book, or the alphabetical order of your phone's contacts: keep the entries sorted by the thing you search for, so you can jump close to the answer instead of reading everything.

The default index type in most relational databases is the B-tree (strictly, usually a B+ tree). PostgreSQL's documentation lists it as the default among several index types (B-tree, hash, GiST, SP-GiST, GIN and BRIN), and describes it as handling equality and range queries on data that can be sorted (PostgreSQL: Indexes).

A B-tree is a balanced tree of pages (blocks of a few kilobytes). Each page holds many sorted keys. Inner pages point to child pages that cover ranges of keys; leaf pages hold the keys and a pointer to each row (or, in some databases, the row itself).

                     [ 1000 | 2000 | 3000 ]                 root page                    /        |       |      \        [100|300|...]   [1100|...]  [2100|...]  [3100|...]  inner pages          /   |   \   leaf: 1, 2, 3 ... 99 -> row pointers                     leaf pages (linked, in order)

To find key 2,345, the database reads the root, follows the pointer for the 2,000 to 3,000 range, and so on down to a leaf. Because leaves are linked in order, a range (created_at between two dates) or an ordered scan (ORDER BY created_at) is a walk along adjacent leaves.

Each page holds hundreds of keys, so each level multiplies the reach by hundreds. That is why indexes stay fast as tables grow: the depth grows with the logarithm of the row count, and with a large base. The program below compares a full scan with binary search over a million sorted values (the same idea a B-tree uses inside each page), then computes how many levels a B-tree needs for a billion rows at two plausible fan-outs.

// File: IndexMath.javapublic class IndexMath {    public static void main(String[] args) {        int n = 1_000_000;        int[] sorted = new int[n];        for (int i = 0; i < n; i++) {            sorted[i] = i * 2;          // even numbers, already in order        }        int target = 1_500_000;         // sits at position 750,000        int linear = 0;        for (int value : sorted) {            linear++;            if (value == target) {                break;            }        }        int binary = 0;        int lo = 0;        int hi = n - 1;        while (lo <= hi) {            binary++;            int mid = (lo + hi) >>> 1;            if (sorted[mid] == target) {                break;            }            if (sorted[mid] < target) {                lo = mid + 1;            } else {                hi = mid - 1;            }        }        System.out.println("Full scan comparisons:     " + linear);        System.out.println("Binary search comparisons: " + binary);        long rows = 1_000_000_000L;        for (int fanout : new int[] {100, 300}) {            int levels = 0;            long reach = 1;            while (reach < rows) {                reach *= fanout;                levels++;            }            System.out.println("B-tree, fanout " + fanout + ": " + levels + " levels for 1 billion rows");        }    }}

Full scan comparisons:     750001Binary search comparisons: 19B-tree, fanout 100: 5 levels for 1 billion rowsB-tree, fanout 300: 4 levels for 1 billion rows

Seven hundred and fifty thousand comparisons versus nineteen. And a B-tree over a billion rows needs only four or five page reads to reach any key, most of which (the upper levels) are almost always already in memory. The actual fan-out depends on key size and page size; the point is the shape of the numbers.

For full-text search at scale, a dedicated search engine built on inverted indexes is usually better than the database (articles 36 and 44).

A composite (multi-column) index sorts by the first column, then by the second within equal first values, and so on, like a phone book sorted by surname, then first name.

CREATE INDEX photos_by_owner ON photos (owner_id, created_at DESC);

This index serves:

• WHERE owner_id = 42 (uses the first column);
• WHERE owner_id = 42 ORDER BY created_at DESC LIMIT 20 (finds owner 42's entries, already in order: no sort needed);
• WHERE owner_id = 42 AND created_at < '2026-09-01' (equality then range).

It does not efficiently serve WHERE created_at > '2026-09-01' for all owners, because the index is not sorted by created_at overall; it would be like finding everyone named "Priya" in a phone book sorted by surname. PostgreSQL's documentation makes the same point: a multicolumn B-tree index is most efficient when there are constraints on the leading (leftmost) columns (PostgreSQL: Multicolumn Indexes).

The practical rule for ordering columns:

1. Columns filtered by equality first (owner_id = ?, status = ?).
2. Then the column used for a range or for sorting (created_at).
3. Prefer more selective equality columns earlier when there are several, unless a query pattern needs a different prefix.

One composite index can replace several single-column ones: (owner_id, created_at) already serves "by owner", so a separate index on owner_id alone is redundant.

If the index contains every column the query needs, the database can answer from the index alone without visiting the table rows: an index-only scan. PostgreSQL, for example, lets you add non-key columns with INCLUDE:

CREATE INDEX photos_feed_cover ON photos (owner_id, created_at DESC) INCLUDE (photo_id, status);

A query selecting only photo_id, status and created_at for an owner never touches the table. This is a powerful trick for the hottest queries, at the cost of a larger index.

Index only the rows you query:

CREATE INDEX orders_pending ON orders (created_at) WHERE status = 'pending';

If 0.1% of orders are pending, this index is 1,000 times smaller than an index on all orders, and the "show pending orders" query reads only it. Article 12's library exercise used a partial unique index to enforce "one open loan per copy".

If queries search on a computed value, index that value:

CREATE INDEX users_email_lower ON users (lower(email));-- serves: WHERE lower(email) = lower('Asha@Example.com')

Selectivity is how much an index narrows the search. An index on user_id is highly selective: each value matches a few rows. An index on a boolean like is_active, where 95% of rows are true, is not: "find active users" still touches almost every row, and reading through an index then jumping to each row is slower than simply scanning the table.

Database query planners use table statistics to estimate this, and will (correctly) ignore an index that would not help. Low-cardinality columns are useful as the first column of a composite index only if queries always filter on them and the remaining columns narrow things further, or as the condition of a partial index.

Every relational database can tell you how it intends to run a query. In PostgreSQL, EXPLAIN shows the plan and EXPLAIN ANALYZE actually runs the query and reports real row counts and timings (PostgreSQL: Using EXPLAIN).

You do not need to master plans for system design, but you should recognise the main shapes. Here is an illustrative before-and-after for Pixly's profile query (simplified for teaching; real output contains costs, widths and timing details):

-- Before: no suitable indexLimit  -> Sort (by created_at desc)       -> Seq Scan on photos   (filter: owner_id = 42)      reads every row-- After: CREATE INDEX photos_by_owner ON photos (owner_id, created_at DESC)Limit  -> Index Scan using photos_by_owner on photos       (index condition: owner_id = 42)                      reads ~20 index entries and rows

A classic interview and production puzzle. Common causes:

Indexes are not free. Every INSERT must add an entry to every index on the table; every UPDATE of an indexed column must move entries; every DELETE must remove them. Each index also takes disk space and memory, and competes for the database's cache.

A table with 6 indexes does roughly 7 structure updates per inserted row (the table plus 6 indexes). For Pixly's likes table at 1,700 inserts per second at peak, adding an unneeded index adds 1,700 extra index writes per second. On write-heavy tables, every index must earn its place.

Guidelines:

• Index for measured or clearly expected access patterns, not for every column.
• Remove indexes nobody uses (most databases can report index usage).
• Keep write-heavy tables lean; move heavy read patterns to replicas, caches or a separate read model (article 27).

Creating an index on a large table can take minutes or hours, and some methods block writes while they run. Use the database's online option where available (PostgreSQL has CREATE INDEX CONCURRENTLY, which avoids blocking writes at the cost of a slower build), and create indexes during quieter periods. A missing index that is discovered at peak is a classic outage: the fix (building it) can itself be slow and risky.

When a query is slow, try fixes roughly in this order, cheapest first:

1. Fix the query: select only needed columns, remove N+1 patterns, avoid functions on indexed columns.
2. Add or adjust an index, verified with the query plan.
3. Denormalise or precompute the hot read path (article 12).
4. Cache the result (article 09).
5. Read replicas for read volume (article 15).
6. Partition or shard when data or write volume outgrows one machine (article 16).

Each step down adds more complexity. Interviewers notice when a candidate jumps straight to step 6.

Notice the "only if this feature exists" note on the likes index. likes is Pixly's most write-heavy table. Every extra index there costs thousands of writes per second at peak, so it is added only when a real access pattern needs it.

Index problems rarely announce themselves. They show up as a system that was fine last month and is slow today.

• Indexing every column "just in case".
• Composite indexes with the range column first.
• Assuming an index is used without checking the plan.
• Indexing low-selectivity flags on their own.
• Forgetting that indexes slow writes on write-heavy tables.
• Building a large index on a busy table with a blocking method.
• Reaching for caching or sharding before fixing a missing index.

• After listing access patterns, name the index for each hot one, with the column order and why.
• Mention that cursor pagination relies on the same index.
• For write-heavy tables, say you are deliberately keeping indexes minimal.
• If asked "the query is slow, what do you do?", answer in the order above, starting with the query plan.

• Next: Transactions, Isolation Levels and Concurrency Control: Preventing Race Conditions, where many fast queries meet at the same rows.
• Background: binary search is explained step by step in Searching and Sorting: Choose the Right Approach.
• Later: when one machine's indexes are no longer enough, replication (article 15) and sharding (article 16) take over.