Indexing

Without an index, finding a row means scanning every row in the table and checking whether it matches — a full table scan. An index is a separate data structure, sorted or organized specifically to make lookups on a column fast, at the cost of extra disk space and slower writes (every index has to be updated on every write, too).

The catch — and the thing most of this page is about — is that an index only helps the query shapes it was built for. The same index that turns one query from 800ms into 2ms does nothing for a slightly different query, and the cost of maintaining it is charged on every insert, update, and delete regardless.

Fig. 2 — Rows touched searching for one key, scan vs. index

Full Table ScanIndexed Lookup (B-Tree)

Searching for key 13: a full scan compares 14 of 16 rows, one by one, until it finds a match — O(n).

A mental model

Think of the index at the back of a textbook. The book itself is in page order (that’s the table). The index is a second, smaller thing, in alphabetical order, mapping each term to the pages it appears on. To find “b-tree” you don’t read the whole book — you jump into the alphabetical list, land on the term, and follow the page numbers it gives you.

A database B-tree index works the same way:

1. Descend the tree to find the key you’re looking for — a handful of page reads even in a billion-row table, because the tree is sorted and balanced.
2. Read the pointer stored next to that key. It points at the actual row (a physical location in the table, or the primary key).
3. Fetch the row from the table itself — a separate read, sometimes to a totally different part of the disk.

Step 3 is why indexes stop helping past a certain point: if a query matches half the table, doing millions of individual “look up pointer, jump to row” round-trips is slower than just reading the whole table front to back. Sequential reads are cheap; millions of random reads are not.

---

B-tree indexes: what they actually accelerate

The default index type in almost every relational database. Keys are held in sorted order across a balanced tree of fixed-size pages, so a lookup, insert, or range scan all take O(log n) page reads no matter how large the table gets.

CREATE INDEX idx_orders_customer_id ON orders (customer_id);

Because the keys are sorted, one B-tree on (customer_id) speeds up all of these:

Query shape	Example	Why the index helps
Equality	WHERE customer_id = 42	Descend to the key, done.
Range	WHERE customer_id BETWEEN 10 AND 20	Find the start, walk the leaves in order until the end.
Sorting	ORDER BY customer_id LIMIT 100	The index is the sorted order — no separate sort step.
Min / max	SELECT MIN(customer_id)	First leaf of the tree.
Prefix match	WHERE name LIKE 'Sm%'	'Sm%' is a range: everything from Sm to Sn.

---

Where indexing is wrong, useless, or actively harmful

This is the part that trips people up. Creating an index is easy; creating one that the planner will actually use for the queries you care about is the skill.

1. Low-selectivity columns — the classic mistake

Indexing students.student_id makes WHERE student_id = 90210 instant. But adding an index on students.is_active (a boolean) or students.enrollment_status (three possible values) is close to useless: a query like WHERE is_active = true might match 95% of the table, so the planner throws the index away and scans anyway — and now every write has to maintain an index nobody benefits from.

The rule: an index earns its place when the column has many distinct values and your queries ask for a small slice of them. email, user_id, order_id, sku — good. status, type, is_deleted, gender, country on their own — usually bad. (They can still be useful as the second column of a composite index, or in a partial index — see below.)

2. A function or expression wrapped around the column

An index on email stores the raw values. The moment you transform the column in the WHERE clause, the stored values don’t match what you’re comparing against, and the index is skipped:

CREATE INDEX idx_users_email ON users (email);

-- Uses the index:
SELECT * FROM users WHERE email = 'ada@example.com';

-- Does NOT use it — full table scan:
SELECT * FROM users WHERE LOWER(email) = 'ada@example.com';
SELECT * FROM users WHERE email || '!' = 'ada@example.com!';

The fix is an expression index that stores the transformed value:

CREATE INDEX idx_users_email_lower ON users (LOWER(email));

3. Implicit type mismatches

Same failure, sneakier cause. If phone is a VARCHAR column and you query WHERE phone = 5551234567, the database has to cast every stored phone to a number to compare — a function on the column — so the index on phone is skipped. Quote the literal (WHERE phone = '5551234567') and it works.

4. Leading wildcards

WHERE name LIKE 'Sm%'    -- index-friendly: it's a range scan
WHERE name LIKE '%smith' -- index useless: no known starting point
WHERE name LIKE '%mit%'  -- index useless

A B-tree is sorted left-to-right, like a phone book. “Everyone whose surname starts with Sm” is a contiguous slice. “Everyone whose surname ends in smith” is scattered through the whole book. For infix/suffix search you need a different tool — a trigram index (pg_trgm), a full-text index, or a dedicated search engine.

5. Negation and “not equal”

WHERE status != 'archived', WHERE deleted_at IS NOT NULL, NOT IN (...) — these typically match most of the table, so even with an index on the column, a scan is cheaper. Rewriting to a positive, selective condition (WHERE status IN ('open', 'pending')) lets an index back in.

6. OR across different columns

WHERE customer_id = 42 OR shipping_country = 'DE'

An index on customer_id can’t help the shipping_country half, so the planner often falls back to scanning. A UNION of two selective queries, or a carefully chosen pair of indexes the planner can combine (a “bitmap OR” in Postgres), does better.

7. Tiny tables

A 50-row lookup table lives on one or two pages. Reading all of it is faster than reading an index and then the table. The planner knows this and will ignore your index — which is fine, but don’t be surprised when EXPLAIN shows a seq scan on countries.

8. The query returns most of the table anyway

SELECT * FROM orders WHERE created_at > now() - interval '10 years';

If that’s 99% of your orders, the index on created_at is worse than useless — the planner will scan, and you’ve paid write cost for nothing. Indexes are for needles, not haystacks.

---

Composite (multi-column) indexes

An index can span several columns: CREATE INDEX ON orders (customer_id, created_at). It’s sorted by customer_id first, then by created_at within each customer — exactly like sorting a spreadsheet by column A, then column B.

The leftmost-prefix rule

That sort order means the index helps queries that use a prefix of its columns, left to right:

Query filters on	Index (customer_id, created_at) helps?
customer_id	Yes
customer_id and created_at	Yes — best case
customer_id and sorts by created_at	Yes — filter and sort from one index
created_at alone	No — created_at isn’t the leading column

An index on (a, b) is like a phone book sorted by last name then first name. Finding “everyone named Grace” means reading the whole book — first names aren’t the sort key.

Column order: equality first, then the range, then the sort

The practical recipe for ordering columns in a composite index:

1. Columns compared with = go first (most selective one leading).
2. Then one column used in a range (>, <, BETWEEN) or the ORDER BY.
3. Ranges after the first one can’t be used efficiently — the index can only “narrow” once.

-- Query: open orders for a customer, newest first
SELECT * FROM orders
WHERE customer_id = 42 AND status = 'open'
ORDER BY created_at DESC;

-- Good: two equalities, then the sort column
CREATE INDEX idx_orders_cust_status_created
  ON orders (customer_id, status, created_at);

---

Covering indexes and index-only scans

If an index contains every column a query needs — both the filtered columns and the selected ones — the database can answer from the index alone and skip step 3 (fetching the row). Postgres calls this an index-only scan.

-- This query only ever needs customer_id and total
SELECT total FROM orders WHERE customer_id = 42;

-- Covering index: total comes along for the ride via INCLUDE
CREATE INDEX idx_orders_cust_covering
  ON orders (customer_id) INCLUDE (total);

This is a genuine speedup for hot queries, but it’s a trade: you’re duplicating column data into the index, so it’s bigger and slower to write. Reserve it for queries that run constantly and touch few columns.

---

Clustered vs. secondary indexes (why the primary key matters)

• InnoDB (MySQL) physically stores the whole table as a B-tree keyed on the primary key — the clustered index. Every secondary index’s leaf entries store the primary key, not a row pointer, so a secondary-index lookup does two descents: one in the secondary index to get the PK, one in the clustered index to get the row.
• Postgres keeps the table as an unordered heap and every index (PK included) points at physical row locations.

Practical consequences:

• A random primary key hurts on InnoDB. A UUIDv4 PK means every insert lands at a random spot in the clustered index, fragmenting pages and bloating every secondary index (which all carry that fat random key). An auto-increment BIGINT or a time-ordered UUID (v7) inserts at the end — far cheaper.
• Keep the primary key narrow. On InnoDB it’s copied into every other index on the table.

---

Write cost, bloat, and having too many indexes

Other maintenance realities:

• UPDATEs touch indexes too. Updating an indexed column means deleting the old index entry and inserting a new one. Updating a non-indexed column is much cheaper (and on Postgres can be a HOT update that skips index maintenance entirely).
• Indexes bloat. Churn leaves dead entries. Postgres REINDEX (or pg_repack), MySQL OPTIMIZE TABLE rebuild them. Watch index size vs. table size over time.
• Build indexes without locking writes. CREATE INDEX CONCURRENTLY (Postgres) / online DDL (MySQL 5.6+) — a plain CREATE INDEX on a large production table can block writes for minutes.

---

Other index types worth knowing

Type	Good for	Notes
Hash	Exact-match only: WHERE id = 5	O(1) point lookups, but no ranges, no sorting, no prefix — hashing destroys key order. Rarely worth choosing over a B-tree.
Partial / filtered	Indexing only the rows you query	CREATE INDEX ON orders (created_at) WHERE status = 'open' — tiny index, since 99% of orders aren’t open. Great for “hot subset” queries.
Expression / functional	Queries that transform a column	CREATE INDEX ON users (LOWER(email)) — see mistake #2 above.
GIN / GiST (Postgres)	Full-text search, jsonb, arrays, ranges, geometry	WHERE tags @> '{urgent}', WHERE doc @@ to_tsquery('...'). A plain B-tree can’t do containment.
Trigram (pg_trgm)	LIKE '%mit%', fuzzy matching	Makes infix wildcard search indexable.

---

How to decide what to index — a checklist

Add an index when:

1. It’s a foreign key / join column. orders.customer_id, enrollments.course_id. Unindexed FKs make joins and cascading deletes slow, and many databases don’t index FKs automatically.
2. A hot query filters, joins, or sorts on it and the condition is selective (returns a small fraction of rows).
3. A composite fits better than singles. If your common query filters on (a, b) together, one index on (a, b) beats separate indexes on a and b. Order: equality columns first, then one range/sort column.
4. A covering index removes a hot round-trip. Only for constantly-run, few-column queries.

Don’t add an index when:

• The column has few distinct values and you query it alone (status, is_active, type) — use a partial index or make it the trailing column of a composite instead.
• The table is small, or the query returns most of the table.
• Nothing queries the column — an index you “might need later” is cost now for benefit never.
• The table is write-dominated and the read is rare — sometimes a slow occasional read is the right trade.

Then verify with EXPLAIN: