Database indexing, properly: B-trees, composite indexes, and why queries still go slow

                    ┌──────────────────┐
  root              │  40   |   80     │
                    └───┬───────┬──────┘
               ┌────────┘       └────────┐
        ┌──────▼──────┐           ┌──────▼──────┐
  inner │ 10 | 25     │           │ 55 | 70     │
        └──┬───────┬──┘           └──┬───────┬──┘
     ┌─────┘       └────┐            │       │
 ┌───▼───┐  ┌───────┐  ┌▼──────┐  ┌──▼────┐ ┌▼──────┐
 │ 1..9  │→ │ 10..24│→ │ 25..39│→ │ 40..54│→│ 55..69│→ …
 └───────┘  └───────┘  └───────┘  └───────┘ └───────┘
  leaves, in sorted order, linked left to right

index leaf:  (customer_id=42) → ctid (page 918, offset 3)
                                       ↓
heap page 918: [ … row 3: id, customer_id, status, total, … ]

secondary index leaf:  (customer_id=42, id=874)
                                          ↓
clustered index → descend by id=874 → the full row

CREATE INDEX orders_cust_status_placed_idx
    ON orders (customer_id, status, placed_at);

-- Wrong order: the range on placed_at blocks status from being used for seeking
CREATE INDEX bad_idx ON orders (customer_id, placed_at, status);

SELECT * FROM orders
WHERE customer_id = 42
  AND placed_at > now() - interval '30 days'
  AND status = 'paid';
-- Seeks on customer_id + placed_at range, then filters every row for status

-- Right order: both equalities seek, the range walks, no filtering
CREATE INDEX good_idx ON orders (customer_id, status, placed_at);

-- Index on email is useless here: the tree is sorted by email, not lower(email)
SELECT * FROM customers WHERE lower(email) = 'naiem@example.com';

-- Fix: index the expression the query actually uses
CREATE INDEX customers_email_lower_idx ON customers (lower(email));

-- Same problem, different disguise
WHERE date(placed_at) = '2026-08-14'           -- not sargable
WHERE placed_at >= '2026-08-14'                -- sargable
  AND placed_at <  '2026-08-15'

WHERE total_cents / 100 > 50                   -- not sargable
WHERE total_cents > 5000                       -- sargable

-- customer_id is bigint, the parameter arrives as text
SELECT * FROM orders WHERE customer_id = '42';

-- Postgres usually resolves this cleanly. MySQL comparing a VARCHAR column
-- to a number converts the COLUMN, not the literal, and the index is dropped.
SELECT * FROM users WHERE phone = 8801712345678;   -- phone is VARCHAR: full scan

WHERE name LIKE '%rahman'      -- no B-tree can help
WHERE name LIKE 'rahman%'      -- a prefix is a range; the index works

-- For genuine substring search, use trigrams
CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX customers_name_trgm_idx ON customers USING gin (name gin_trgm_ops);
-- now '%rahman%' can use an index

-- 40% of orders are 'paid'. An index on status alone will be ignored.
SELECT * FROM orders WHERE status = 'paid';

-- But this is selective, and a partial index is very effective
SELECT * FROM orders WHERE status = 'refund_pending';
CREATE INDEX orders_refund_pending_idx ON orders (placed_at)
    WHERE status = 'refund_pending';

ANALYZE orders;                                  -- refresh statistics

-- Increase the sample for a column with a skewed distribution
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 1000;
ANALYZE orders;

-- Correlated columns: the planner assumes independence and multiplies,
-- badly underestimating when the columns move together
CREATE STATISTICS orders_city_postcode (dependencies, ndistinct)
    ON city, postcode FROM orders;
ANALYZE orders;

-- Often cannot use one index efficiently
SELECT * FROM orders WHERE customer_id = 42 OR reference = 'REF-99';

-- A union of two indexed lookups usually plans much better
SELECT * FROM orders WHERE customer_id = 42
UNION
SELECT * FROM orders WHERE reference = 'REF-99';

CREATE INDEX orders_placed_idx ON orders (placed_at DESC);

-- Uses the index order: no sort node in the plan
SELECT * FROM orders ORDER BY placed_at DESC LIMIT 20;

-- Mixed directions: the single-column index no longer provides the order
SELECT * FROM orders ORDER BY customer_id ASC, placed_at DESC LIMIT 20;

-- Match the index to the sort exactly, including direction and null placement
CREATE INDEX orders_cust_placed_idx
    ON orders (customer_id ASC, placed_at DESC NULLS LAST);

-- Page 5,000: the engine walks and discards 100,000 rows to return 20
SELECT * FROM orders ORDER BY placed_at DESC LIMIT 20 OFFSET 100000;

-- Keyset pagination: constant time at any depth
SELECT * FROM orders
WHERE (placed_at, id) < ($1, $2)
ORDER BY placed_at DESC, id DESC
LIMIT 20;

-- In EXPLAIN ANALYZE output:
-- Index Only Scan using orders_cust_idx  (actual rows=1000 …)
--   Heap Fetches: 998        ← the visibility map is stale

VACUUM (ANALYZE) orders;

-- Watch for tables autovacuum is not keeping up with
SELECT relname, n_dead_tup, last_autovacuum
FROM pg_stat_user_tables
ORDER BY n_dead_tup DESC LIMIT 10;

-- Rebuild without blocking writes
REINDEX INDEX CONCURRENTLY orders_cust_placed_idx;

-- Compare index size against the table
SELECT indexrelname,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size,
       idx_scan
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY pg_relation_size(indexrelid) DESC;

-- Never scanned since statistics were last reset: candidates for removal
SELECT relname, indexrelname, idx_scan,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE idx_scan = 0
  AND indexrelid NOT IN (SELECT conindid FROM pg_constraint)
ORDER BY pg_relation_size(indexrelid) DESC;

-- Duplicates: an index on (a) is redundant if (a, b) exists
-- Check before dropping - a narrower index can still be worth keeping
-- if it is much smaller and heavily used.

-- The query
SELECT customer_id, total_cents
FROM orders
WHERE customer_id = 42 AND status = 'paid';

-- Key columns for seeking, INCLUDE columns just along for the ride
CREATE INDEX orders_cust_status_idx
    ON orders (customer_id, status) INCLUDE (total_cents);

-- MySQL has no INCLUDE; put the extra column in the key instead
CREATE INDEX orders_cust_status_idx
    ON orders (customer_id, status, total_cents);

EXPLAIN (ANALYZE, BUFFERS, SETTINGS)
SELECT o.id, o.total_cents, c.full_name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.placed_at > now() - interval '7 days'
ORDER BY o.placed_at DESC
LIMIT 50;

-- BRIN on a large append-only log: kilobytes of index for gigabytes of table
CREATE INDEX events_time_brin_idx ON events USING brin (created_at);

-- GIN for jsonb containment
CREATE INDEX orders_meta_idx ON orders USING gin (metadata);
SELECT * FROM orders WHERE metadata @> '{"channel": "mobile"}';

-- Always build indexes concurrently on a live table
CREATE INDEX CONCURRENTLY orders_new_idx ON orders (customer_id, placed_at DESC);

-- Test whether an index would help BEFORE paying to build it
CREATE EXTENSION IF NOT EXISTS hypopg;
SELECT * FROM hypopg_create_index(
    'CREATE INDEX ON orders (customer_id, status, placed_at)');
EXPLAIN SELECT … ;   -- the planner considers the hypothetical index