Database Indexing

What it is

A database index is a data structure stored separately from the table that maps values of one or more columns to the physical location of matching rows, enabling the database to find rows without scanning the entire table. Without indexes, every query that filters on a non-primary-key column requires a sequential scan — O(N) in the number of rows. With an appropriate index, the same query runs in O(log N) (B-tree) or O(1) amortized (Hash), making the difference between a 10ms and a 30-second query on a 100M-row table.

PostgreSQL index types: B-tree (default) — balanced tree, supports =, <, >, BETWEEN, IN, LIKE 'prefix%', ORDER BY; the right choice for most situations; Hash — O(1) equality lookups, does not support range queries, rarely preferable to B-tree; GIN (Generalized Inverted Index) — maps each element of a composite value (array element, JSONB key, tsvector lexeme) to its containing rows; required for @> containment, ? key-exists, and full-text search; GiST (Generalized Search Tree) — extensible tree for geometric, range, and full-text data; used for PostGIS spatial queries, range type containment, and nearest-neighbor searches; BRIN (Block Range INdex) — stores min/max per block range, extremely small (10–1000x smaller than B-tree), effective only when column values are physically correlated with row insertion order (timestamps on append-only tables).

Why it exists

Sequential scans are the performance worst case for selective queries. A table with 100M rows and 10KB average row size is 1TB of data — a sequential scan reads all 1TB even if the query matches 10 rows. Indexes trade write overhead (updating the index on INSERT/UPDATE/DELETE) and storage (the index structure itself) for dramatically faster reads. The tradeoff is favorable for most read-heavy OLTP workloads. The art of indexing is matching index types to query access patterns: not every index improves performance, and too many indexes significantly slow writes and bloat storage.

When to use

• B-tree on foreign keys: Always index foreign key columns — without an index, deleting or updating a parent record requires a sequential scan of the child table to find dependent rows, causing surprising lock waits under concurrency.
• Covering index for hot queries: Add non-key columns to an index (PostgreSQL INCLUDE clause) so the query can be satisfied entirely from the index without a heap fetch — critical for high-frequency queries where even the heap lookup latency matters.
• Partial index for selective subsets: Index only the rows that match a common filter predicate: CREATE INDEX ON orders(user_id) WHERE status = 'pending' — smaller than a full index, faster to build and scan, used automatically when the WHERE clause matches the predicate.
• GIN for JSONB and array queries: Any query using @> (containment), ? (key existence), or @@ (full-text match) against JSONB, array, or tsvector columns requires a GIN index to avoid sequential scan.
• BRIN for time-series: Append-only log or event tables where timestamps are monotonically increasing benefit from BRIN indexes — they're 1000x smaller than B-tree, nearly free to maintain on writes, and fast for range queries on time ranges that align with block boundaries.

When not to use

• Don't index columns with very low cardinality (boolean, status columns with 2–3 distinct values) — the optimizer often prefers a sequential scan over an index when selectivity is poor (returning >5–10% of rows).
• Don't index every column defensively — each index adds overhead to every INSERT, UPDATE, and DELETE on the table; a table with 20 indexes on a high-write OLTP workload can be 5x slower on writes than a table with 3 targeted indexes.
• Don't assume an index is being used — always verify with EXPLAIN ANALYZE; the optimizer may ignore an index due to stale statistics, incorrect cardinality estimates, or selectivity thresholds.
• Don't create duplicate indexes — PostgreSQL will silently maintain both without using either one preferentially; query pg_stat_user_indexes for idx_scan = 0 to identify unused indexes.

Typical architecture

  Index type selection guide (PostgreSQL):

  Query Pattern                         → Index Type
  ─────────────────────────────────────────────────────
  col = $1 (equality)                   → B-tree (or Hash)
  col > $1, col BETWEEN $1 AND $2       → B-tree
  LIKE 'prefix%'                        → B-tree (text_pattern_ops)
  ORDER BY col LIMIT N                  → B-tree (same column)
  array @> '{value}'                    → GIN
  jsonb @> '{"key": "val"}'             → GIN (jsonb_path_ops)
  to_tsvector(col) @@ to_tsquery(q)     → GIN
  geometry && bbox / ST_DWithin         → GiST (PostGIS)
  tsrange @> timestamp                  → GiST (range types)
  timestamp on append-only log table    → BRIN

  Covering index (avoids heap fetch):
  CREATE INDEX ON orders(user_id)
    INCLUDE (created_at, total_amount, status);
  -- Query: SELECT created_at, total_amount, status FROM orders
  --        WHERE user_id = $1 ORDER BY created_at DESC LIMIT 10;
  -- Served entirely from index without table access.

  Partial index (reduces index size):
  CREATE INDEX ON orders(user_id) WHERE status = 'pending';
  -- Only indexes pending orders. 5% of rows vs 100%.
  -- Used automatically when query includes WHERE status = 'pending'.

  Composite key ordering (left-prefix rule):
  CREATE INDEX ON events(tenant_id, created_at, event_type);
  -- Supports: WHERE tenant_id = ?  ✓
  -- Supports: WHERE tenant_id = ? AND created_at > ?  ✓
  -- Supports: WHERE tenant_id = ? AND created_at > ? AND event_type = ?  ✓
  -- Does NOT support: WHERE created_at > ? (no tenant_id)  ✗
  -- Does NOT support: WHERE event_type = ? (skips columns)  ✗

  EXPLAIN ANALYZE output (critical metrics):
  Seq Scan on orders (cost=0.00..89432.10 rows=5000000 width=32)
    (actual time=0.025..4821.321 rows=5000000 loops=1)  ← BAD: full scan

  Index Scan using orders_user_id_idx on orders
    (cost=0.43..12.85 rows=3 width=32)
    (actual time=0.041..0.055 rows=3 loops=1)  ← GOOD: index used

  Unused index detection:
  SELECT schemaname, tablename, indexname, idx_scan
  FROM pg_stat_user_indexes
  WHERE idx_scan = 0
  ORDER BY pg_relation_size(indexrelid) DESC;
          

Pros and cons

Implementation notes

Use EXPLAIN (ANALYZE, BUFFERS, FORMAT TEXT) — not just EXPLAIN — to see actual execution times, row count estimates vs. actual, and buffer hit/miss statistics. Key signals: Seq Scan on large tables with a selective WHERE clause is the primary indicator of a missing index; cost estimates wildly different from actual time indicate stale statistics — run ANALYZE tablename; high Buffers: read vs. Buffers: hit ratio indicates cache thrashing that an index may not solve without also tuning shared_buffers and effective_cache_size. For large tables, use CREATE INDEX CONCURRENTLY to build indexes without locking writes — the index build takes longer but doesn't block production traffic.

For composite indexes, the column order follows a rule: put equality predicates first, then range predicates, then ORDER BY columns. For a query WHERE tenant_id = $1 AND created_at > $2 ORDER BY created_at, the optimal index is (tenant_id, created_at) — equality filter first (tenant_id reduces the scan to a single tenant's data), range scan second (created_at traversal within that partition). Placing the range column first wastes the index because the range scan can't then use the equality column to filter. Monitor index bloat periodically: SELECT pg_size_pretty(pg_relation_size(indexrelid)) AS index_size, indexrelname FROM pg_stat_user_indexes ORDER BY pg_relation_size(indexrelid) DESC — indexes significantly larger than expected for their row count indicate bloat requiring REINDEX CONCURRENTLY.

Common failure modes

• Function wrapping defeats index: WHERE LOWER(email) = 'alice@example.com' cannot use a plain B-tree index on email; the function prevents index usage; fix with a functional index: CREATE INDEX ON users (LOWER(email)).
• Leading wildcard prevents B-tree use: WHERE name LIKE '%smith' cannot use a B-tree index (the leading wildcard means no prefix is known); a full-text GIN index or a trigram index (pg_trgm extension) is needed for substring matching.
• Type mismatch implicit cast: A column is BIGINT but the query parameter is passed as VARCHAR; implicit type conversion prevents index use; the optimizer falls back to a sequential scan; fix by ensuring parameter types match column types.
• Index on low-cardinality column: An index on a status column with values ('active', 'inactive') is ignored by the optimizer for queries returning 40%+ of rows; a partial index on WHERE status = 'active' (if active is a small minority) is more effective.
• Missing index on FK column: A FOREIGN KEY from orders.customer_id to customers.id has no index on orders.customer_id; deleting a customer triggers a sequential scan of the entire orders table to verify no dependent orders exist — causing seconds-long lock contention on every customer deletion.

Decision checklist

• Are all foreign key columns indexed to prevent sequential scans on cascading deletes and join operations from the child table?
• Are composite index columns ordered with equality predicates first and range predicates last to maximize left-prefix usage?
• Are JSONB containment queries and full-text queries backed by GIN indexes (using jsonb_path_ops for containment, gin_trgm_ops for trigram, tsvector for FTS)?
• Are hot read queries verified with EXPLAIN ANALYZE to confirm index usage and estimate vs. actual row count accuracy?
• Are unused indexes periodically identified via pg_stat_user_indexes (idx_scan = 0) and dropped to reduce write overhead?
• Are new indexes created using CREATE INDEX CONCURRENTLY in production to avoid table write locks during build?

Example use cases

• E-commerce order lookup (covering index): The orders list page queries SELECT id, created_at, total, status FROM orders WHERE user_id = $1 ORDER BY created_at DESC LIMIT 20. A covering index CREATE INDEX ON orders(user_id, created_at DESC) INCLUDE (total, status) serves the entire query from the index with zero heap fetches — latency drops from 80ms to 3ms at the p99 for active users with large order histories.
• Append-only audit log (BRIN): An audit_events table receives 50,000 inserts per second and holds 10 billion rows. A BRIN index on the timestamp column is 3MB vs. 120GB for a B-tree, with essentially zero write overhead. Time-range queries for compliance audits (last 7 days of events) use the BRIN index efficiently because rows are physically inserted in timestamp order.
• Multi-tenant SaaS (partial index): A notifications table has 500M rows but at any time only 2M are unread. A partial index CREATE INDEX ON notifications(user_id, created_at) WHERE read = false is 250x smaller than a full index. The inbox query WHERE user_id = $1 AND read = false ORDER BY created_at DESC is served by the tiny partial index rather than the massive full table index.

Related patterns

• Normalization vs Denormalization — Denormalization reduces join complexity, often complementing indexes; the right level of normalization shapes which columns need indexing.
• Data Modeling Patterns — Each modeling pattern has characteristic index requirements (GIN for JSONB hybrid, GiST for ltree, composite B-tree for Cassandra-like access patterns).
• OLTP vs OLAP — OLTP systems require selective B-tree and partial indexes; OLAP columnar stores use different structures (zone maps, bitmap indexes) optimized for full-column scans.

Further reading

• PostgreSQL Documentation: Indexes
• Use The Index, Luke — SQL Indexing and Tuning Guide
• PostgreSQL: Using EXPLAIN