System Design · Data

Index Optimization Methods

Database Indexing explains what a B+ tree is. This note is the craft of shaping one: which columns, in which order, which rows, which payload, and when a second index is a liability. A with order, a , and a with are different optimizations of the same structure.

The goal is not “more indexes.” It is enough contiguous leaf range for the hot statements, without duplicating prefixes or turning every INSERT into a five-tree write.

Inbox query, one index

Name the statement

WHERE user_id = ? AND status = 'open' ORDER BY created_at DESC LIMIT 20.

Equality columns, then the sort column; range last if any.

Payload columns the SELECT needs; keep them out of the key.

If 97% of rows are closed, index the open slice only.

What actually happens

Start from statements, not from columns. For each hot query, ask: what equality slice, what order, what extra columns, what row subset? That maps onto one , optionally , optionally covering via key + . Then merge candidates: two queries that share a leftmost prefix can share one tree. A leftover single-column index that is a prefix of a composite is a .

Verify with the plan: index range scan vs bitmap vs seq scan; heap fetches remaining after a supposed ; write amplification on INSERT. Usage catalogs (pg_stat_user_indexes, sys.dm_db_index_usage_stats) tell you which shapes are decorative.

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  Q["Hot query shape"] --> Need{"Need ordered slice\nor covering?"}
  Need -->|Equality + ORDER BY| Comp["Composite: ESR order"]
  Need -->|SELECT extras only| Cover["Keys + INCLUDE payload"]
  Need -->|Tiny hot subset| Part["Partial predicate"]
  Comp --> Cost{"Write QPS high?"}
  Cover --> Cost
  Part --> Cost
  Cost -->|Yes| Slim["Drop redundant /\nkeep one composite"]
  Cost -->|No| Extra["Maybe second shape\nfor a second query"]
  Slim --> Explain["EXPLAIN ANALYZE + usage stats"]
  Extra --> Explain

Composite order: seek prefix versus residual filter

Diagram text: the exact Mermaid definition below preserves the nodes, labels, and connections. Enable JavaScript to view the rendered diagram.

Read the diagram definition

flowchart TD
  Idx["Index (user_id, status, created_at)"] --> A["user_id = 9"]
  A --> B["status = open"]
  B --> C["created_at DESC"]
  C --> Leaf["Tight leaf range\nalready ordered"]
  Idx2["Same index"] --> D["status = open only"]
  D --> Skip["Cannot seek; skip scan\nor ignore leading key"]
  Skip --> Wide["Wide scan or other index"]

sql

-- Target statement (inbox)
SELECT id, title, created_at
FROM tickets
WHERE user_id = $1 AND status = 'open'
ORDER BY created_at DESC
LIMIT 20;

-- Strong default (ESR): equality, equality, sort
CREATE INDEX tickets_inbox
  ON tickets (user_id, status, created_at DESC)
  INCLUDE (title);

-- Weaker: range too early
-- (created_at, user_id) → every user's time range, then filter user_id
-- Skip-scan engines may still probe, but density is worse.

-- Residual later-column filter still helps a little (CPU)
-- but the leaf range is sized by the seek prefix only.

is a heuristic, not physics. If almost every query is a range on created_at with a rare equality, you may lead with time and partition instead. If two equalities have very different cardinality, put the more selective equality first when both are always present — unless the less selective column is required for clustering with the sort key. Always test both orders with EXPLAIN ANALYZE on production-like skew.

DESC in the index definition matches ORDER BY created_at DESC so the engine walks the leaf backward (or stores the key already reversed) and can satisfy LIMIT without a sort node. Mismatched direction can inject a Sort on millions of rows that the index almost ordered.

Covering: keys versus INCLUDE versus heap

A is defined by the query, not by the table. The same table needs different covering sets for different statements. Every extra key column widens internal nodes and uniqueness semantics. payload sits in the leaf only, which is what wants without polluting fanout as badly.

Choice	Helps	Hurts
Key columns	Seek, order, uniqueness	Fanout, split rate, comparator cost
INCLUDE columns	Covering SELECT list	Leaf size; updates of those columns still maintain the index
Heap / clustered row	Wide JSON, rarely selected text	Random heap fetch after a non-covering scan

In PostgreSQL, covering is incomplete without the . VACUUM (and HOT updates that keep the tuple on the same heap page) determine whether the index-only scan actually skips the heap. Measure heap fetches in EXPLAIN, not only the node name Index Only Scan.

sql

-- Covering without bloating the search key
CREATE INDEX tickets_inbox
  ON tickets (user_id, status, created_at DESC)
  INCLUDE (title);          -- selected, not filtered

-- Do NOT INCLUDE a 20 KB description column
-- unless that statement is both hot and always selects it.

-- InnoDB: secondary leaf already has PK.
-- INCLUDE-equivalent: extra columns in the index definition
-- still stored in the secondary leaf; clustered lookup skipped
-- when the query is covered.

Partial indexes: match the predicate, not the table

sql

-- Open tickets only (status is low cardinality globally)
CREATE INDEX tickets_open_by_user
  ON tickets (user_id, created_at DESC)
  WHERE status = 'open';

-- Planner uses it when the query repeats the idea:
WHERE user_id = $1 AND status = 'open' ...

-- Misses if the app sends:
WHERE user_id = $1 AND status <> 'closed'   -- different predicate
WHERE user_id = $1                          -- no status filter

-- Soft-delete pattern
CREATE INDEX users_email_live ON users (email) WHERE deleted_at IS NULL;

Partial indexes also cut write amplification: closing a ticket removes it from the open index and does not insert into a giant closed index. The closed archive path, if rare, can seq-scan or use a different shape. Document the predicate next to the query in the app so an ORM refactor does not silently drop the match.

Expression indexes are the cousin: CREATE INDEX ON users (LOWER(email)) only helps WHERE LOWER(email) = LOWER($1) (or an equivalent the planner proves). They are optimizations of representation, not a second table type.

One composite versus several singles

Prefer one composite

Same WHERE + ORDER BY every time (inbox, session by user, “latest 20”).
Need ordered LIMIT without a Sort.
Need covering of a small payload.
Write budget allows one extra tree, not four.

Consider

Admin search: optional filters on 8 columns, none dominant.
Cannot store C(8,3) composites.
Bitmap AND/OR of a few selective singles, then heap.
Accept residual heap I/O; do not expect covering.

Unique constraints still need their own supporting index. A composite unique (tenant_id, email) is both integrity and lookup. Do not add a second unique(email) unless email is globally unique — that is a product rule, not an optimization.

Tuning what you already created

Drop redundant prefixes

List indexes by table, sort by column list. If (a,b,c) exists, (a) and (a,b) are usually unless they are UNIQUE with a different constraint or a different partial predicate. Removing them cuts every write and frees cache for leaves you actually seek.

Fill factor, bloat, rebuild

on CREATE/REINDEX leaves slack for HOT-ish updates of indexed columns. Monitor bloat (pgstattuple, unused page density). Online rebuilds restore density without a long exclusive lock where the engine supports them. Bloat looks like “the index is slow” when it is simply twice as many leaf pages.

Unused and write-only indexes

idx_scan = 0 for a month on a busy table is a candidate drop — after checking replica-only workloads, monthly jobs, and constraint indexes. A write-only index still costs WAL. Staging drops behind a feature flag / not-valid constraint where needed.

Updates that should not touch the index

If a column is updated on every request (last_seen_at), putting it in a composite used by a rare report taxes the hot path. Keep volatile columns out of keys; INCLUDE them only if covering is mandatory and the update rate is acceptable. Heap-only tuple updates (Postgres) skip index maintenance when indexed columns do not change — another reason not to index chattery fields.

How you build matters

CREATE INDEX CONCURRENTLY / ONLINE avoids blocking writes. Sorted bulk build packs leaves tightly. Building during a backfill without a fill-factor plan can leave a perfect-packed right-growing index that immediately splits in production. Match fill factor to the insert pattern you will have after the build.

Worked merge: three queries, two indexes

plaintext

Q1 inbox:     WHERE user_id=? AND status='open' ORDER BY created_at DESC LIMIT 20
Q2 history:   WHERE user_id=? ORDER BY created_at DESC LIMIT 20
Q3 by status: WHERE status='open' AND created_at > now() - interval '1 day'

Attempt 1 (naive): three indexes
  (user_id, status, created_at DESC)
  (user_id, created_at DESC)
  (status, created_at)

Better:
  idx_user_created (user_id, created_at DESC) INCLUDE (title, status)
    -- Q2 fully; Q1 uses prefix user_id then residual status filter
    -- if open-per-user is small, residual is fine
  idx_open_recent (created_at) WHERE status='open'   -- Q3 partial

If Q1 is the true firehose and residual status is 90% open (bad):
  keep tickets_inbox (user_id, status, created_at DESC) INCLUDE (title)
  drop (user_id, created_at) only if Q2 can scan the inbox index
  with a different status or a skip. Measure both.

The residual-filter question is quantitative: if each user has 10,000 tickets and 9,900 are closed, a (user_id, created_at) index plus residual status = open walks a lot of closed leaves. Then the extra status key (or a partial) earns its write cost. If each user has 12 tickets, residual is cheaper than another tree.

Trade-offs to state clearly

Covering completeness vs leaf width. Index-only scans remove heap I/O until INCLUDE columns are so wide the index no longer fits in cache. Cover the narrow hot path, not SELECT *.

Partial precision vs planner match. A tight WHERE clause makes a tiny index that zero queries hit if the SQL drifts. Prefer predicates the application already sends.

Composite vs intersection. One ordered tree for a known query; several singles for a combinatorial filter UI. Mixing both without dropping leftovers is how OLTP tables grow 12 indexes.

Fill factor vs cache density. Slack prevents split storms on random keys; packed leaves win on append-only and read-mostly catalogs.

Redundant prefixes vs dedicated UNIQUE. Do not drop an index that enforces a constraint you still need. Do drop a non-unique prefix of a longer non-unique composite after usage stats agree.

Choosing and explaining index optimization

A complete explanation connects the mechanism to a requirement. Describe what improves when you introduce it, which new failure cases become possible, and how you would know that the trade-off is worthwhile.

Explain the core idea

Shape indexes from hot statements: equality prefix, sort columns, then optional INCLUDE payload, optionally partial.

ESR and covering are query-specific. A second index is justified only if residual filters or a second shape stay expensive.

Maintenance — visibility map, fill factor, dropping redundant prefixes — is part of the optimization, not ops trivia.

When it belongs

You already know B-trees and need to choose column order and covering for a concrete API.

Write latency rose after “we added indexes for every WHERE.”

EXPLAIN shows Index Scan plus huge heap fetches, or a Sort under a LIMIT.

How it fails

Non-matching partial predicates; ORMs that omit the filter.

Covering JSON blobs that blow up leaf pages.

Redundant prefix indexes doubling WAL on every insert.

Trade-offs to weigh

Residual filter on a shared composite versus a dedicated (user_id, status, created_at) tree.

INCLUDE covering versus heap fetch when the visibility map is dirty.

Index intersection for ad-hoc admin search versus composites for the product path.

Common misunderstandings

Cloning a single-column index per filter because “indexes are good.”

Putting SELECT-only columns in the key instead of INCLUDE.

Trusting Index Only Scan in the plan without checking heap fetches.

Wrap-up

Overlay the hot SQL, keep shared prefixes, cover with INCLUDE, shrink with partial predicates, and delete redundant trees. Then re-read heap fetches and write rates — that is index optimization as practiced.

Primary sources

Key takeaway

Optimization is column order, covering payload, and row subset — verified by plans and usage stats — not a larger catalog of single-column indexes. One composite that matches the statement beats three that almost do.