Indexes and Query Performance

Indexes and Query Performance

An index is a data structure that lets the database find rows quickly without scanning every row in a table. Think of it like a book's index — instead of reading every page, you look up the term and jump directly to the page.

How B-Tree Indexes Work

Most database indexes (PostgreSQL, MySQL, SQLite) use a B-Tree (Balanced Tree). The tree keeps keys in sorted order, allowing:

• Point lookups: O(log n)
• Range scans: O(log n + k) where k = matching rows
• Sorted output: free (data is already ordered)

            [30]
           /    \
       [10,20]   [40,50]
      /  |  \    /  |  \
    [5][15][25][35][45][55]

Creating Indexes

-- Single column index
CREATE INDEX idx_users_email ON users(email);

-- Composite index (order matters!)
CREATE INDEX idx_orders_user_date ON orders(user_id, created_at);

-- Partial index (index only active users)
CREATE INDEX idx_active_users ON users(email) WHERE active = true;

-- Covering index (includes extra columns to avoid table lookup)
CREATE INDEX idx_orders_cover ON orders(user_id) INCLUDE (total, status);

Composite Index Column Order Rule

For a composite index (user_id, created_at), the index is useful for:

• WHERE user_id = 5 ✅
• WHERE user_id = 5 AND created_at > '2024-01-01' ✅
• WHERE created_at > '2024-01-01' ❌ (cannot use index — leading column missing)

Rule: The index can be used only if you filter on a prefix of the index columns.

EXPLAIN / EXPLAIN ANALYZE

EXPLAIN ANALYZE
SELECT * FROM orders WHERE user_id = 42 AND created_at > '2024-01-01';

-- Output:
-- Index Scan using idx_orders_user_date on orders
--   Index Cond: ((user_id = 42) AND (created_at > '2024-01-01'))
--   Actual rows=150, Execution Time=0.8ms

Watch for Seq Scan on large tables — that usually means a missing or unused index.

Index Types

When NOT to Index

• Small tables — sequential scan is faster below ~1000 rows
• High-write, low-read tables — indexes slow down INSERTs/UPDATEs
• Low-cardinality columns — indexing gender (M/F) rarely helps
• Over-indexing — every index adds write overhead and storage

Interview Tips

1. Explain the difference between a clustered index (determines physical row order; one per table in MySQL InnoDB) and a non-clustered index (separate structure with pointers).
2. Explain index selectivity — an index on email (nearly unique) is far more selective than one on country.
3. Know that LIKE 'abc%' can use a B-Tree index, but LIKE '%abc' cannot (leading wildcard).