Learn

A query that runs in 5 milliseconds on a 100-row table can take 5 SECONDS on a 100,000-row table — and 5 MINUTES on a 100-million-row table. The difference is almost always indexes.

This lesson explains what an index is, what it costs, and how to know when to add one. By the end you'll be able to read an EXPLAIN and know whether a query is going to be fast or slow without ever running it.

The book index analogy

Imagine a 1000-page programming textbook. You want every page that mentions "closures."

Without an index — you flip every page, scan top-to-bottom, note matches. ~1000 pages × 5 seconds = ~80 minutes.

With the back-of-book index — you jump to "C", find closures: 142, 287, 408, go to those three pages. Maybe 30 seconds.

A database without an index on a column is the first scenario. The query engine has no choice but to read every row to check whether it matches your WHERE clause. That's a full table scan (SCAN in SQLite, Seq Scan in Postgres).

A database WITH an index is the second scenario. The index is a separate data structure — sorted by your column's values, with pointers back to each row. The engine jumps straight to the matching values in O(log n) time.

What's a B-tree, really?

Indexes are almost always stored as a B-tree: a balanced tree where each node holds many keys (not just 2 like a binary tree). For a million-row table, a typical B-tree has 3-4 levels of depth. Looking up a value means following 3-4 pointers — practically free, even for huge tables.

                  [ 50,  100 ]                ← root
                 /     |     \
          [10, 30]  [70, 90]  [200, 500]      ← internal
           / | \      ...        ...
        rows rows rows                         ← leaves point to rows

Looking up email = '[email protected]'? The DB walks the tree comparing strings, lands on the right leaf, follows the pointer, fetches the row. 3-4 string comparisons total — instead of a million.

Demonstrating it

CREATE TABLE users (id INTEGER PRIMARY KEY, email TEXT, age INTEGER);
-- imagine a million rows here

-- Before the index:
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = '[email protected]';
-- SCAN users           ← reads every row

CREATE INDEX idx_users_email ON users(email);

-- After the index:
EXPLAIN QUERY PLAN SELECT * FROM users WHERE email = '[email protected]';
-- SEARCH users USING INDEX idx_users_email (email=?)

SCAN is bad on big tables. SEARCH ... USING INDEX is what you want. That's the first thing to look for in any EXPLAIN output.

Note: every PRIMARY KEY is automatically indexed. Foreign keys are NOT (in most engines) — that's a common source of slow JOINs.

When the optimizer can use an index

• Equality: WHERE email = '[email protected]' ✓
• Prefix LIKE: WHERE email LIKE 'bob%' ✓ (anchored to start of string)
• Range: WHERE age > 30 AND age < 50 ✓
• ORDER BY on indexed column ✓ (no extra sort step)
• JOIN on indexed column ✓
• IN list: WHERE id IN (1, 2, 3) ✓

When it can't — and what to do instead

Leading wildcard: WHERE email LIKE '%@gmail.com'

• The B-tree is sorted alphabetically. It can't jump to "all strings ending in @gmail.com" — that's not a prefix.
• Fix: store the reversed string in a separate column and index that. Or use full-text search.

Function on the column: WHERE LOWER(email) = '[email protected]'

• The index stores raw values, not lowercase versions. The engine has to compute LOWER for every row.
• Fix: an expression index: CREATE INDEX idx_users_email_lower ON users(LOWER(email));

Arithmetic: WHERE price + 10 > 100

• Same problem — the index has price, not price + 10.
• Fix: rewrite the query as WHERE price > 90.

Type mismatch: WHERE id = '42' (string compared against integer column)

• The DB casts every row, defeating the index.
• Fix: pass the matching type — WHERE id = 42.

Composite indexes — the column-order rule

CREATE INDEX idx_users_age_country ON users(age, country);

This index is sorted by age first, then by country within each age group. It's like a phone book sorted by last name first, then first name within each last name.

• WHERE age = 30 AND country = 'US' → ✓ uses both columns
• WHERE age = 30 → ✓ uses just the leading column
• WHERE country = 'US' → ✗ cannot use the index — like searching a phone book by first name only

The rule: a composite index (A, B, C) is useful for queries that filter on A, (A, B), or (A, B, C). NOT for B, C, or (B, C) alone.

This is why composite indexes need to be designed with your query patterns in mind. The most-filtered column goes first.

Covering indexes — even faster

If your SELECT lists only columns that already exist inside the index, the engine never has to go fetch the row at all. The index alone answers the query.

CREATE INDEX idx_users_age_email ON users(age, email);

-- Covering query — needs only age & email, both in the index:
SELECT email FROM users WHERE age = 30;
-- EXPLAIN: SEARCH users USING COVERING INDEX idx_users_age_email

USING COVERING INDEX is the fastest path possible. For hot queries, it's often worth adding extra columns to an index purely to make it covering.

Partial indexes — index only what matters

CREATE INDEX idx_active_users ON users(email) WHERE deleted_at IS NULL;

This only indexes rows where deleted_at IS NULL. The result: a smaller index, faster writes, and faster lookups for queries that match the same WHERE clause. Massively useful for soft-deleted rows, status flags, or any "hot subset" of a table.

The cost of indexes

Indexes aren't free:

• Disk space — a B-tree typically takes 30-40% of the column's data size.
• Slower writes — every INSERT, UPDATE, or DELETE has to update every relevant index. A table with 20 indexes can have inserts 5-10x slower than the same table with 0 indexes.
• Optimizer overhead — more options means more thinking time, and occasionally wrong plans.

Rule of thumb: index every foreign key column, every column you frequently filter or sort by, and stop. Don't index columns nobody queries on.

ANALYZE — keep statistics fresh

ANALYZE;

The optimizer uses statistics about each column (min, max, value distribution) to PICK between possible indexes. Without recent stats, it can pick a bad plan even when great indexes exist. Run ANALYZE after large data changes (or rely on autovacuum / autoanalyze in Postgres).

Reading EXPLAIN

Always check the plan for slow queries:

EXPLAIN QUERY PLAN SELECT * FROM orders WHERE user_id = 42 AND status = 'paid';

What to look for:

• SCAN <table> — no index used. Bad on large tables.
• SEARCH <table> USING INDEX <name> — index used. Good.
• USING COVERING INDEX — index alone answered the query. Best.
• USE TEMP B-TREE FOR ORDER BY — couldn't use the index for sorting either. Consider an index that matches your ORDER BY.

The same query can be 10,000× faster with the right index. Knowing how to read EXPLAIN is what separates the engineer who guesses from the one who measures.