Database Indexing

Also Known As

TL;DR

Explanation

Without an index, a database must perform a full table scan (O(n)) to find matching rows. B-tree indexes (the default in MySQL/PostgreSQL) enable O(log n) lookups. Index design principles: index columns used in WHERE, JOIN ON, and ORDER BY clauses; use composite indexes for multi-column filters; avoid indexing low-cardinality columns (boolean, gender); cover frequently-read queries with covering indexes. Indexes have write overhead — over-indexing slows inserts and updates. Use EXPLAIN / EXPLAIN ANALYZE to verify index usage.

Diagram

flowchart TD
    QUERY[SELECT * FROM orders<br/>WHERE user_id = 42] --> CHECK{Index on
user_id?}
    CHECK -->|No| SEQ[Sequential Scan<br/>read ALL rows O of n]
    CHECK -->|Yes| IDX[B-Tree Index Lookup<br/>O of log n]
    IDX --> ROWS[Fetch matching rows<br/>directly]
    SEQ --> SLOW[Slow on large tables]
    ROWS --> FAST[Fast regardless of<br/>table size]
style FAST fill:#238636,color:#fff
style SLOW fill:#f85149,color:#fff
style IDX fill:#238636,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Not indexing foreign key columns — JOIN and cascade operations do full table scans without them.
• Over-indexing write-heavy tables — every INSERT/UPDATE must maintain all indexes, slowing writes.
• Indexing low-cardinality columns (boolean, status with 3 values) — the optimizer often ignores them.
• Not using composite indexes in the correct column order — (status, created_at) is different from (created_at, status).

Avoid When

• Indexing every column — unused indexes slow down writes and waste storage without benefiting reads.
• Indexing low-cardinality columns (boolean, status with 3 values) — the query planner may ignore the index anyway.
• Adding indexes during peak traffic — index builds lock tables or consume I/O and can cause outages.
• Indexing columns that are only used in non-selective WHERE clauses that return most of the table.

When To Use

• Columns used in WHERE, JOIN ON, ORDER BY, or GROUP BY clauses on large tables.
• Foreign key columns — without an index, deletes and updates on the parent table require full child table scans.
• Columns used in high-frequency queries identified by EXPLAIN or slow query log analysis.
• Composite indexes for queries that filter on multiple columns together — column order matters.

Code Examples

-- Slow: full table scan on 1M rows:
SELECT * FROM orders WHERE customer_id = 42 ORDER BY created_at DESC;
-- No index on customer_id — scans all rows

-- Fast: composite index serves filter + sort:
CREATE INDEX idx_orders_customer_date ON orders (customer_id, created_at DESC);

-- Add index on frequently-filtered foreign key
CREATE INDEX idx_orders_user_id ON orders(user_id);

-- Composite index — order matters: equality first, range last
CREATE INDEX idx_orders_status_created ON orders(status, created_at);

-- Partial index (PostgreSQL) — only index relevant subset
CREATE INDEX idx_orders_pending ON orders(created_at)
    WHERE status = 'pending';

-- EXPLAIN confirms index is used
EXPLAIN SELECT * FROM orders WHERE user_id = 42 AND status = 'paid';

References

• ↗ https://use-the-index-luke.com/sql/anatomy

Tags

Related Terms