Indexes — the cost of making lookups faster

To find one row from a table of 1,000,000, without an index the database scans every row. With one, it takes about 20 comparisons.

Why is the difference so large? And why not put an index on every column? Understanding these two lets you decide where to add them.

What you'll learn in this chapter

• How indexes speed up lookups
• The relationship between composite indexes and column order
• What you give up by adding an index
• Patterns that stop indexes from being used
• The distinction from sharding and hashing

Prerequisites

Builds on O(log n) from Complexity and trees from Choosing data structures.

What this chapter does not cover

Concrete design steps, reading EXPLAIN, partial indexes, expression indexes, and compatibility with UUID primary keys are covered in depth by existing guides.

• Database Design Guide — Introduction to index design

How to write queries themselves is covered in Part 12. Joins and aggregation are in Joins and aggregation; subqueries and window functions in Subqueries and window functions.

This chapter focuses on why things behave the way they do.

Why they speed things up

Without an index, the database reads every row in order (full scan) to find matches. For 1,000,000 rows, that's 1,000,000 reads — O(n) in complexity.

An index is a separate structure that keeps the values of a specified column already sorted. Many databases use a B-Tree.

Each node holds "this range goes to this child", so lookup just picks a branch and descends. One level down slashes candidates dramatically, so the complexity is O(log n).

Same idea as binary search. What's different is that it's realized by connected nodes rather than on an array, and one node packs many keys to reduce disk reads.

Rows	Full scan	B-Tree
1,000	1,000	~10
1,000,000	1,000,000	~20
1,000,000,000	1,000,000,000	~30

The gap widens as data grows. A few hundred rows on a dev machine can't demonstrate it; it surfaces at millions of rows in production.

On string columns, "sorted" order is decided by the collation. Changing the collation changes the order, so the index needs to be rebuilt (Character encoding).

Composite indexes

Search conditions often span multiple columns.

SELECT * FROM orders WHERE user_id = 42 AND status = 'shipped';

Here, rather than separate indexes on user_id and status, a composite index that bundles both works better.

CREATE INDEX idx_orders_user_status ON orders (user_id, status);

With separate indexes, you narrow on one and inspect against the other. With a composite, one structure uses both conditions fully.

Order changes the result

The most important thing in a composite index is column order.

Think of a composite index as arranged like a phone book in the order you specified. A phone book ordered "last name → first name" gives:

Search condition	Usable?
By last name	Usable. Ordered by last name, so range narrows
By last name + first name	Usable. Narrow by last, then by first
By first name only	Not usable. First name is ordered only within last name

Same for the composite index on (user_id, status).

-- Works: uses the leftmost columns
WHERE user_id = 42
WHERE user_id = 42 AND status = 'shipped'

-- Doesn't work: skips the leftmost
WHERE status = 'shipped'

Only conditions that use the leftmost columns contiguously work. This is called the leftmost-prefix rule. Guides for choosing the order:

1. Equality comparisons (=) first, range comparisons (>, BETWEEN) after
2. Among equalities, columns with more distinct values (higher selectivity) first

Putting a range comparison first breaks the order for columns after it, making them unusable.

What you give up

Indexes aren't a free win. The more you add, the slower updates become.

The reason is simple: an index is also data, so it has to be updated.

Operation	Impact on the index
INSERT	Add a new entry to every index
UPDATE	Update indexes that include the affected column. Tree rebalancing may occur
DELETE	Remove entries from every index

With 10 indexes on a table, inserting one row means 11 writes (the table + 10 indexes).

Other things you give up:

Cost	Content
Write load	Indexes are rewritten on insert, update, and delete
Disk space	Indexes use space separate from the table data
Memory	Hot indexes want to fit in RAM. If they don't, the benefit drops
Planner distraction	Too many choices can lead to non-optimal plans

So the design is decided by the read/write ratio. More writes also feed into the wait time discussed in Locks and isolation levels.

• Read-heavy tables with few writes (product master, articles) → heavier indexing
• Write-heavy tables (logs, events) → minimal

"Just add one to every column" makes reads marginally faster at the cost of certainly slower writes.

Patterns that stop them from being used

Even with an index in place, the way you write the query can stop it from being used.

-- Doesn't work: applying a function to the column
WHERE DATE(created_at) = '2026-08-17'
-- Works: leave the column as-is; use a range (make the boundary time zone explicit; example is PostgreSQL)
WHERE created_at >= '2026-08-17 00:00:00+09:00'
  AND created_at <  '2026-08-18 00:00:00+09:00'

-- Doesn't work: leading wildcard
WHERE name LIKE '%san'
-- Works: prefix match uses the ordering
WHERE name LIKE 'san%'

-- Doesn't work: computing on the column
WHERE price * 1.1 > 1000
-- Works: move the computation to the other side
WHERE price > 1000 / 1.1

The shared principle is put the indexed column in the condition as-is. Applying a function or computation to the column breaks the match against the sorted values.

That said, you can index the expression itself (an expression index). With an index on lower(email), WHERE lower(email) = ? becomes indexable too. What stops working is the index on the bare column. The Database Design Guide — Introduction to index design covers how to build one and which expressions qualify.

In the first example, the boundary uses +09:00 because '2026-08-17' without a time zone refers to the 0 o'clock of what place depends on the column type and connection settings. PostgreSQL's timestamp with time zone stores in UTC and interprets input strings without a time zone as the session's TimeZone setting (PostgreSQL — Date/Time Types). If a connection stays UTC while counting a day of Japan time, it aggregates a range shifted by 9 hours. Types without a time zone (MySQL's DATETIME, for example) don't preserve which local time the stored value was. The interpretation rules depend on the database and the column type, so verify in your environment. Either way, making the time zone explicit on the boundary conveys intent to readers. Datetime representation itself is covered by Datetimes and time zones.

Put the offset on the boundary value, not on the column. Wrapping the column with AT TIME ZONE and then reducing to a date has the same effect as the first example — the index becomes unusable.

Leading wildcards don't work for the same reason as looking up "people whose name ends in 'san'" in a phone book: the ordering can't be used, so everything has to be scanned. If this really is required, use a dedicated full-text search mechanism.

The same principle affects join conditions. Wrapping the column in ON orders.customer_id = customers.id with a function or computation makes the index on that column unusable. The plan that indexes the join partner becomes unavailable, changing behavior as rows grow. Which plan is chosen depends on data distribution; check with EXPLAIN. How joins change row counts is covered in Joins and aggregation.

Distinctions from similar terms

Some terms are commonly confused with indexes. Different purposes, different layers.

Term	What it does	Main purpose
Index	Build a sorted lookup structure for a specific column	Speed up lookup
Composite index	One index bundling several columns	Speed up multi-condition lookup
Hashing	Convert a key to a position via a hash function	Speed up equality lookup. Can't do range lookup
Sharding	Split data across multiple servers	Exceed the limits of one machine. Distribute capacity and load
Partitioning	Internally split one table into several	Manage huge tables and limit search range

These three are not substitutes for indexes. What sharding solves is the scale problem of "won't fit on one machine"; it doesn't speed up lookup itself. Partitioning can narrow the search to a specific partition, but only when narrowing by the partition key — not for arbitrary columns. Hashing can be used as a hash index, but it doesn't support range lookup or ordering, so it isn't the general first choice.

When you want to speed up lookup, the starting point is an index, and the cost is write load. That's the center of the trade-off. Skew (concentrated access on a specific node) in distribution design is a separate concern. How to spot skewed keys and what distribution makes harder is covered by Data distribution.

Common misconceptions

"The more indexes, the faster." — Lookups get faster; writes definitely get slower. Disk and memory are consumed. Decide by read/write ratio.

"Column order in a composite index doesn't matter." — Order changes the outcome. Only conditions using the leftmost columns contiguously work.

"An index is always used when it exists." — Not when a function is applied to the column, or when a leading wildcard is used.

"Sharding speeds up lookups." — Sharding distributes across servers; its purpose is exceeding the limits of one machine. Speeding up single-table lookups is what indexes do.

"Hash indexes are always faster than B-Tree." — Faster on equality sometimes, but unusable for range and ordering. B-Tree is the default for versatility.

Exercises

Q1. An orders table with tens of millions of rows has slow lookups for a specific customer's orders. A colleague proposes three plans. Which do you pick?

Plan A: Add an index on customer_id
Plan B: Split the table across 4 servers by hash of customer ID
Plan C: Add indexes on every column to be ready for any query

Answer and explanation

Answer: Plan A. Plans B and C don't fit the purpose.

Why A is right — the reason it's slow is scanning the whole table to find rows matching the condition. Indexing customer_id drops it from O(n) to O(log n). Direct fit for "I want to narrow by this column".

Why B doesn't fit — sharding is a method for distributing capacity and load that don't fit on one machine across multiple. Different purpose. And sharding by customer ID makes big-customer traffic concentrate on one server, making that server hot. The problem in distribution design is this skew — a different concern from index design.

Why C doesn't fit — lookups might get marginally faster, but INSERT / UPDATE / DELETE all rewrite every index, so writes definitely get slower. The orders table is also write-heavy, so it doesn't pay off.

If the actual condition is a combination of customer_id and ordered_at, a composite index bundling both works better. The cost of index design is consistently write load, so add only for conditions actually used.

Q2. Given the composite index (user_id, created_at), which of these queries use it?

A: WHERE user_id = 42
B: WHERE created_at > '2026-01-01'
C: WHERE user_id = 42 AND created_at > '2026-01-01'
D: WHERE created_at > '2026-01-01' AND user_id = 42

Answer and explanation

Answer: A, C, and D work; B doesn't.

The criterion is "does it use the leftmost columns contiguously" (the boundary time zone isn't the point of this question and is omitted; in practice, make it explicit as above).

• A — user_id is leftmost. Works
• B — created_at alone skips the leftmost. created_at is only ordered within each user_id, so it can't be used
• C — uses both leftmost columns. Works best
• D — same as C. The order in the WHERE clause doesn't matter. The database interprets conditions and rearranges into a usable form

D is the tricky one. What matters is the column order in the index definition, not the order written in SQL.

If searches like B are frequent, consider a standalone (created_at) index or a (created_at, user_id) composite separately.

Q3. A log table gained 8 search indexes, and writes became slow. What to do?

Answer and explanation

Answer: Keep only indexes actually used and drop the rest.

Log tables have the property of overwhelmingly write-heavy, reads limited to investigation. With 8 indexes, inserting one row makes 9 writes.

Order of action:

1. Measure usage — many databases record per-index usage counts. Identify those with zero use
2. Consolidate duplicates — with (a) and (a, b), (a) is often replaceable by the leftmost prefix of (a, b) and becomes a removal candidate
3. Narrow to what's needed — leave only those that match conditions actually used in investigation (time range, log level, etc.)

Options that revisit the design itself:

• Partition by time to limit the search range
• Move old logs to a separate table to keep the write target small
• Route to a dedicated search platform if full-text search is needed

"Fast lookups and fast writes" isn't simultaneously possible. Deciding what that table should prioritize comes first.

Summary

• Indexes drop lookup from O(n) to O(log n) by keeping a separate sorted structure
• Composite indexes serve multi-condition queries. They only apply to conditions using the leftmost columns contiguously
• Column order: equality first, range after. Among equalities, higher-selectivity columns first
• Order in the WHERE clause doesn't matter. Whether it works is decided by the index definition's order
• The cost is write load. Every index adds writes
• Applying functions or arithmetic to the column disables the index. Leading wildcards don't work either
• Sharding is distribution; hashing is equality lookup; indexes speed up lookup. Different purposes

Related references

• Database Design Guide — Introduction to index design — Design steps, reading EXPLAIN, partial indexes, UUID primary key compatibility
• Laravel API Development Guide — Listing APIs — N+1 problem and pagination

What to read next

• Shell basics — Moving into the execution-environment layer from here