DBMS

Storage And Indexing

Choosing Indexes

Indexes do not serve columns. They serve QUERIES.

JrCodex·7 min read

Jr Codex DBMS Notes

Level: Intermediate Prerequisites: Chapter 3: Hash and Specialised Indexes Time to complete: ~20 minutes

Table of Contents

  1. Start From the Queries
  2. Selectivity
  3. Sargability
  4. What to Index by Default
  5. What Not to Index
  6. Finding Missing and Unused Indexes
  7. Summary & Next Steps

1. Start From the Queries

The Wrong Question
─────────────────────────────────────────
  "Which columns should I index?"

  Indexes do not serve columns. They serve QUERIES.

  THE RIGHT QUESTION
  "What are my slowest and most frequent queries,
   and what would each one need?"
─────────────────────────────────────────

The Procedure
─────────────────────────────────────────
  1. LIST the queries — from the slow query log and
     from the application's hot paths
  2. For each, note the WHERE columns, JOIN columns,
     ORDER BY columns and SELECT columns
  3. DESIGN one index per query shape, applying
     Chapter 3's ordering rules
  4. MERGE indexes that share a leftmost prefix —
     (a) is redundant if (a, b) exists
  5. MEASURE with EXPLAIN before and after
     (Module 6, Chapter 4)
─────────────────────────────────────────

-- Step 4, made concrete: these three are redundant.
CREATE INDEX i1 ON orders (customer_id);                       -- ✗ drop
CREATE INDEX i2 ON orders (customer_id, status);               -- ✗ drop
CREATE INDEX i3 ON orders (customer_id, status, created_at);   -- ✓ keep
 
-- i3 serves every query i1 and i2 could, by the leftmost prefix rule.

2. Selectivity

The Definition
─────────────────────────────────────────
  SELECTIVITY = distinct values ÷ total rows

  HIGH (near 1.0)   nearly unique — email, id
                    ── excellent index candidate

  LOW (near 0)      few distinct values — gender,
                    is_active, status
                    ── usually a poor candidate
─────────────────────────────────────────

SELECT
    COUNT(DISTINCT city)::float / COUNT(*)   AS city_selectivity,
    COUNT(DISTINCT email)::float / COUNT(*)  AS email_selectivity,
    COUNT(DISTINCT status)::float / COUNT(*) AS status_selectivity
FROM students;
Why Low Selectivity Defeats an Index
─────────────────────────────────────────
  `status` has 3 values across 1,000,000 rows, so a
  lookup matches ~333,000 rows.

  Using the index means 333,000 RANDOM heap reads.
  A sequential scan reads the whole table in page
  order and is FASTER.

  The optimiser knows this from its statistics
  (Module 1, Chapter 3) and will correctly ignore
  your index.
─────────────────────────────────────────

The Two Important Exceptions
─────────────────────────────────────────
  SKEWED DISTRIBUTION
    status is 99.9% 'complete' and 0.1% 'failed'.
    Filtering on 'failed' is highly selective even
    though the column is not.
    ──► a PARTIAL index (Chapter 3) is ideal here.

  AS PART OF A COMPOSITE
    (status, created_at) is useful even though
    status alone is not — status narrows, then
    created_at orders within it.
─────────────────────────────────────────

3. Sargability

SARGable = "Search ARGument able" — a condition an index can seek on.

The Rule
─────────────────────────────────────────
  The indexed COLUMN must appear ALONE on one side
  of the comparison.

  The moment it is wrapped in a function or
  arithmetic, the index is unusable — the database
  cannot know which stored values produce the
  target result without checking all of them.
─────────────────────────────────────────

-- ✗ NON-SARGABLE                          -- ✓ SARGABLE equivalent
WHERE YEAR(created_at) = 2026              WHERE created_at >= '2026-01-01'
                                             AND created_at <  '2027-01-01'
 
WHERE LOWER(email) = 'a@b.com'             WHERE email = 'a@b.com'
                                           -- (or index LOWER(email), Chapter 3)
 
WHERE price * 1.2 > 100                    WHERE price > 100 / 1.2
 
WHERE name LIKE '%son'                     WHERE name LIKE 'son%'
                                           -- (or a full-text index)
 
WHERE id + 0 = 42                          WHERE id = 42
 
WHERE COALESCE(city,'') = 'Pune'           WHERE city = 'Pune'
                                           -- handle NULL separately
The Date Case Is the Most Common
─────────────────────────────────────────
  YEAR(created_at) = 2026 appears in an enormous
  amount of real code, and silently forces a full
  scan on the largest table in the system.

  The half-open range is exactly equivalent, uses
  the index, and is also correct across time zones
  and leap years.

  If you check one thing after reading this
  chapter, check for functions wrapped around date
  columns.
─────────────────────────────────────────

4. What to Index by Default

Almost Always
─────────────────────────────────────────
  PRIMARY KEYS
    Indexed automatically by every database.

  FOREIGN KEYS
    NOT automatic in PostgreSQL or SQLite.
    Without it, every join on that key scans, and
    every parent DELETE scans the child table to
    check references.
    ── the single most commonly missing index

  UNIQUE CONSTRAINTS
    Automatic — the index is how uniqueness is
    enforced.

  ORDER BY / pagination columns
    Sorting a large result without an index means a
    full sort, possibly spilling to disk.
─────────────────────────────────────────

-- Find foreign keys with no index (PostgreSQL).
SELECT c.conrelid::regclass AS table_name, a.attname AS column_name
FROM pg_constraint c
JOIN unnest(c.conkey) AS k(attnum) ON true
JOIN pg_attribute a ON a.attrelid = c.conrelid AND a.attnum = k.attnum
WHERE c.contype = 'f'
  AND NOT EXISTS (
      SELECT 1 FROM pg_index i
      WHERE i.indrelid = c.conrelid AND a.attnum = i.indkey[0]      -- leftmost column
  );

5. What Not to Index

Skip These
─────────────────────────────────────────
  SMALL TABLES
    Under a few hundred rows, a full scan is one or
    two pages. The index costs more than it saves.

  LOW-SELECTIVITY COLUMNS ALONE
    Section 2. Consider partial or composite
    instead.

  FREQUENTLY UPDATED COLUMNS
    Every update rewrites the index entry — and if
    the value changes, that means a delete plus an
    insert, potentially in a different page.

  WIDE TEXT COLUMNS
    A 500-byte key destroys the fanout (Chapter 2)
    and produces a huge, deep index. Index a hash
    or a prefix instead.

  COLUMNS NEVER FILTERED, JOINED OR SORTED ON
    An index on a column that only ever appears in
    SELECT is pure cost.

  ANYTHING WITH NO MEASURED QUERY BEHIND IT
    The most common mistake: indexing speculatively,
    then never removing what did not help.
─────────────────────────────────────────

6. Finding Missing and Unused Indexes

-- 1. Slowest queries by total time (PostgreSQL, needs pg_stat_statements).
SELECT calls, ROUND(mean_exec_time::numeric,2) AS avg_ms,
       ROUND(total_exec_time::numeric,0) AS total_ms, query
FROM pg_stat_statements
ORDER BY total_exec_time DESC
LIMIT 20;
-- 2. Tables doing a lot of sequential scanning.
SELECT relname, seq_scan, seq_tup_read, idx_scan,
       seq_tup_read / GREATEST(seq_scan,1) AS avg_rows_per_scan
FROM pg_stat_user_tables
WHERE seq_scan > idx_scan AND seq_tup_read > 100000
ORDER BY seq_tup_read DESC;
-- 3. Indexes nobody uses — pure write cost.
SELECT relname AS table_name, indexrelname AS index_name,
       pg_size_pretty(pg_relation_size(indexrelid)) AS size
FROM pg_stat_user_indexes
WHERE idx_scan = 0 AND indexrelid NOT IN (
    SELECT indexrelid FROM pg_index WHERE indisunique OR indisprimary)
ORDER BY pg_relation_size(indexrelid) DESC;
Order Total Time, Not Average
─────────────────────────────────────────
  A query taking 5 seconds, run once a day, costs
  5 seconds.

  A query taking 20 milliseconds, run 2,000 times a
  second, costs 40 seconds PER SECOND.

  The second is the real problem, and it never
  appears in a "slowest queries" list sorted by
  average duration. Sort by total.
─────────────────────────────────────────

Before Dropping an Unused Index
─────────────────────────────────────────
  - Check statistics have been collecting long
    enough to include monthly or quarterly jobs
  - Confirm it is not enforcing a UNIQUE constraint
  - Check every replica, not just the primary —
    read replicas serve different queries
─────────────────────────────────────────

7. Summary & Next Steps

Key Takeaways

  • Indexes serve queries, not columns — start from the slow query log and design one index per query shape, then merge those sharing a leftmost prefix.
  • Low-selectivity columns defeat indexes because matching many rows means many random heap reads, which a sequential scan beats; skew and composites are the exceptions.
  • Wrapping an indexed column in a function makes the condition non-sargable, and a function around a date column is the most common instance in real code.
  • Foreign keys are not indexed automatically in PostgreSQL or SQLite, making them the most frequently missing index.

Concept Check

  1. Why will the optimiser correctly ignore an index on a status column with three values across a million rows?
  2. Rewrite WHERE YEAR(created_at) = 2026 to be sargable, and explain why the original is not.
  3. Why should a slow-query list be sorted by total time rather than average?

Next Chapter

→ Chapter 5: The Buffer Pool

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index | Back to DBMS Index