Database Indexes — Fundamentals

An index is a separate data structure that maps column values to row locations, letting the database find rows without scanning every page. The single biggest performance lever in SQL. Get indexes right and a slow query becomes instant; get them wrong and they slow writes for no benefit.

For specific index types in Postgres (B-tree, GIN, GiST, BRIN, etc.) see 11_index_types.md. For verifying queries use them see 10_explain_analyze.md.

The mental model — B-tree

Most indexes are B-trees (or B+-trees). Think of a sorted file with a tree of “pointer pages” on top:

Without index — find user with email "alice@example.com":
  Scan every row: 10,000,000 rows = many seconds.

With B-tree on email:
  Root → "M" pointer → "Al-Az" branch → "alice" leaf → row pointer.
  ~4 disk reads regardless of table size.

A B-tree on 10M rows is ~4 levels deep. Lookup is O(log n) — ~4 page reads. Sequential scan is O(n) — millions of page reads.

Each leaf node holds (indexed value, row pointer). Range scans walk the sorted leaves; equality lookups descend the tree once.

When indexes help

The “yes” cases let the planner use the index. The “no” cases force a scan unless other indexes apply.

When indexes hurt

Every index:

1. Slows writes. INSERT, UPDATE, DELETE must maintain every index touching the affected columns. Rule of thumb: 5-10% slower per index.
2. Consumes storage. A B-tree on a 100 GB table can be 20-50 GB. Multiple indexes can exceed the table’s size.
3. Adds maintenance. VACUUM, REINDEX, autovacuum interactions.
4. Can bloat. Updates may leave dead tuples; indexes grow even when the table doesn’t.

The trade-off: more indexes = faster reads, slower writes + more disk. Index what you query, not every column.

Index selectivity

How many distinct values does the indexed column have, and how “selective” is a typical query?

Selectivity = matching rows / total rows

• gender (M/F) in a million-row table: 50% selective. Bad index candidate — the planner may prefer a full scan over reading 500k random rows.
• email (unique): 0.00001% selective. Excellent candidate.
• status (5 values, one common): selective only for rare values; consider a partial index.

Rule of thumb: index helps when typical queries return < 10% of rows. Less selective columns are still candidates IF combined with another column in a composite index.

Composite indexes and the left-prefix rule

A composite index on (a, b, c) can serve queries on:

Order matters. Put the most selective / most-frequently-queried column first. If you frequently query b alone, add a separate index on (b).

-- Order matters for composite indexes
CREATE INDEX idx_orders_user_status_date ON orders (user_id, status, created_at);

-- This uses the index:
SELECT * FROM orders WHERE user_id = 42 AND status = 'paid';

-- This does NOT use the index (no user_id):
SELECT * FROM orders WHERE status = 'paid';

For ORDER BY + WHERE, the index column order must match what the query wants. For WHERE a = ? ORDER BY b DESC, an index (a, b DESC) is ideal — a filters; b is already sorted.

Sargable conditions

“Sargable” = Search ARGument ABLE = a condition the index can use directly.

Sargable (index usable):

WHERE created_at >= '2026-01-01'
WHERE email = 'a@b.com'
WHERE id IN (1, 2, 3)
WHERE name LIKE 'al%'             -- prefix wildcard is OK

Non-sargable (index forced to be useless):

WHERE EXTRACT(year FROM created_at) = 2026     -- function on the column
WHERE created_at + interval '1 day' > now()    -- arithmetic on the column
WHERE LOWER(email) = 'a@b.com'                 -- function on the column
WHERE name LIKE '%alice%'                      -- leading wildcard
WHERE CAST(id AS text) = '42'                  -- type cast on the column

Move the function to the OTHER side:

-- Non-sargable
WHERE EXTRACT(year FROM created_at) = 2026

-- Sargable rewrite
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'

Or build an expression index that matches:

CREATE INDEX idx_email_lower ON users (LOWER(email));
-- Now WHERE LOWER(email) = ? uses the index

Type mismatches kill indexes

-- users.id is BIGINT; the query passes a string
SELECT * FROM users WHERE id = '42';
-- Implicit cast: WHERE id::text = '42' → index unusable

Always use the column’s declared type. ORMs sometimes coerce; check EXPLAIN to verify the index is hit.

Partial indexes — index a subset

CREATE INDEX idx_active_users_email ON users (email) WHERE is_active = true;

If 95% of your queries filter is_active = true, the partial index is much smaller (5% of the rows) and uses less cache. Updates that don’t change is_active for inactive rows don’t touch the index.

The query MUST include the matching predicate exactly:

-- Uses the partial index
SELECT * FROM users WHERE email = 'a@b.com' AND is_active = true;

-- Does NOT use it (no is_active filter)
SELECT * FROM users WHERE email = 'a@b.com';

Common partial index targets: status flags (“active”, “pending”), soft-deletion (deleted_at IS NULL), feature flags.

Covering indexes — index-only scans

A covering index includes all columns the query needs, so the DB never reads the table.

-- Standard index: id pointer in the leaf
CREATE INDEX idx_users_email ON users (email);

-- Covering index: email + name + created_at all in the leaf
CREATE INDEX idx_users_email_covering ON users (email) INCLUDE (name, created_at);

Query:

SELECT email, name, created_at FROM users WHERE email = 'a@b.com';
-- Plan: Index Only Scan -- no heap fetch

Trade-off: bigger index, slower writes. Worth it for hot read paths where the index size is acceptable.

How to verify the index is used

EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'a@b.com';

Look for:

• Index Scan using idx_users_email — great, index used.
• Index Only Scan using ... — even better, no heap fetch.
• Seq Scan on users — index NOT used. Investigate why.
• Bitmap Index Scan + Bitmap Heap Scan — used multiple indexes, combined. Fine for low-selectivity queries.

For deep query plan reading see 10_explain_analyze.md.

Reasons the planner ignores your index

1. Query is non-sargable (function on column, type cast, etc.).
2. Table is too small — sequential scan is faster for tiny tables.
3. Column is non-selective for the query — full scan is cheaper than reading many random rows.
4. Statistics are stale — ANALYZE users; to refresh.
5. Wrong index — the index doesn’t match the query’s columns / order.

When in doubt, EXPLAIN ANALYZE. The planner usually knows better than humans; surprises here mean wrong stats, non-sargable queries, or a mistaken index.

Index maintenance

-- Rebuild bloated index (Postgres)
REINDEX INDEX idx_users_email;

-- Concurrent (online) rebuild
REINDEX INDEX CONCURRENTLY idx_users_email;

-- Find unused indexes (Postgres)
SELECT schemaname, relname, indexrelname, idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan ASC;

Indexes with idx_scan = 0 after weeks of normal traffic are candidates for removal. Their cost (writes, storage) isn’t paying off.

Run VACUUM regularly (autovacuum usually handles it). Watch index bloat: pg_stat_user_indexes and pgstattuple extension show details.

Common indexing pitfalls

Indexing everything

CREATE INDEX ix_a ON users(a);
CREATE INDEX ix_b ON users(b);
CREATE INDEX ix_c ON users(c);
CREATE INDEX ix_d ON users(d);
-- ... 10 single-column indexes

Result: writes slow by 50%. Composite indexes covering common queries are usually better than many single-column indexes.

Indexing low-cardinality columns

CREATE INDEX ix_status ON orders(status);   -- status has 4 values

For a million rows with 4 values, status=‘pending’ returns 250k rows — the planner does a sequential scan instead. The index sits unused but slows writes. Use a partial index instead:

CREATE INDEX ix_pending ON orders(created_at) WHERE status = 'pending';

Forgetting indexes for FK columns

Foreign keys do NOT automatically create indexes (Postgres). Without one:

DELETE FROM users WHERE id = 42;
-- Triggers FK check: scan orders WHERE user_id = 42 — sequential!

Always index FK columns:

CREATE INDEX ix_orders_user ON orders(user_id);

Wrong column order in composite

-- Bad: status first when user_id is what queries filter by
CREATE INDEX ix ON orders(status, user_id);

-- Good: leading column is what's most-queried
CREATE INDEX ix ON orders(user_id, status);

Functional mismatch

CREATE INDEX ix_email ON users(email);
-- Query:
SELECT * FROM users WHERE LOWER(email) = ?;
-- Index NOT used — function on the column.

Either use an expression index (LOWER(email)) or rewrite the query.

Implicit casts

-- email column is TEXT, query passes a number somehow
WHERE email = 42;
-- Postgres casts email to numeric — index unusable.

Use the right types end-to-end.

When NOT to index

• Tiny tables (<1000 rows). Full scan is fine.
• Columns with very few distinct values (boolean status). Unless used in a partial index.
• Write-heavy table with many indexes that don’t pay back. Drop unused ones.
• Columns rarely queried. Index based on actual query patterns, not theoretical needs.

Indexes in ORMs (Django / SQLAlchemy)

# Django
class User(models.Model):
    email = models.CharField(max_length=255, db_index=True, unique=True)
    created_at = models.DateTimeField(auto_now_add=True, db_index=True)

    class Meta:
        indexes = [
            models.Index(fields=["last_name", "first_name"]),
            models.Index(
                fields=["status"],
                name="idx_active_users",
                condition=models.Q(is_active=True),     # partial index
            ),
        ]

# SQLAlchemy
class User(Base):
    __tablename__ = "users"
    id: Mapped[int] = mapped_column(primary_key=True)
    email: Mapped[str] = mapped_column(unique=True, index=True)
    last_name: Mapped[str]
    first_name: Mapped[str]

    __table_args__ = (
        Index("ix_name", "last_name", "first_name"),
        Index("ix_email_lower", func.lower("email")),       # expression index
    )

Both ORMs let you declare indexes; migrations generate the CREATE INDEX statements. Migration tools (Alembic, Django migrations) wrap CREATE INDEX CONCURRENTLY in PG for zero-downtime.

Concurrent index creation

-- Standard: locks the table for writes during creation
CREATE INDEX idx_email ON users(email);

-- Concurrent: no write lock; takes longer; can fail and leave a partial index
CREATE INDEX CONCURRENTLY idx_email ON users(email);

In production, always CONCURRENTLY. The price is slower creation; the benefit is no downtime.

If a CONCURRENTLY index fails: it’s left as INVALID. Drop and retry:

DROP INDEX idx_email;
CREATE INDEX CONCURRENTLY idx_email ON users(email);

Common interview confusions

• “More indexes = better.” — every index slows writes. Index what matters; drop the rest.
• “Primary key creates a magic index.” — yes, but on the PK column only. FK columns are NOT auto-indexed in Postgres.
• “Indexes work for any WHERE.” — only sargable conditions. Functions and type mismatches break index usage.
• “Order doesn’t matter in composite indexes.” — left-prefix rule. The leftmost column must appear in the WHERE for the index to apply.

Interview angle

• “What is a database index and how does it work?” — separate data structure (typically B-tree) mapping column values to row locations. Allows O(log n) lookup instead of O(n) table scan. Trade-off: speeds reads, slows writes, consumes storage.
• “When does an index help and when does it hurt?” — helps for selective filters, equality, range, ordering, joins. Hurts when columns have low cardinality (full scan is cheaper), the table is small, or writes are very frequent and the index isn’t read.
• “What’s the left-prefix rule for composite indexes?” — a composite index (a, b, c) serves queries filtering by a, (a, b), or (a, b, c). Not b alone, not c alone. The leftmost column must appear in WHERE.
• “What’s a sargable condition?” — a query condition the index can use directly. Non-sargable conditions (functions on the column, type casts, leading wildcards) defeat the index. Move functions to the other side or use expression indexes.
• “What’s a covering index?” — an index that includes all columns the query needs, enabling an index-only scan with no heap fetch. Use INCLUDE (col1, col2) in Postgres for non-key included columns.
• “What’s a partial index?” — index on a subset of rows matching a WHERE clause. Smaller and faster; useful for status flags (WHERE active = true) or soft-delete patterns.
• “How do you check if your index is being used?” — EXPLAIN ANALYZE. Look for Index Scan (good) or Seq Scan (no index). For Postgres, pg_stat_user_indexes.idx_scan shows real usage over time.
• “Why is WHERE LOWER(email) = ? slow even with an index on email?” — function on the indexed column makes the query non-sargable. Solutions: expression index on LOWER(email), or store the lowered value in a separate column.
• “Why must FK columns be indexed?” — Postgres doesn’t auto-create indexes on FK columns. Deletes / updates of the referenced parent trigger an FK check that becomes a sequential scan without one.
• “What’s CREATE INDEX CONCURRENTLY?” — Postgres mode for building an index without locking writes. Takes longer; can fail and leave invalid index. Standard for production.