SQL Indexing & Query Optimization Explained

A 1,000-page book. I ask: "find every page that mentions 'normalization'." Would you read all 1,000 pages? Of course not — you'd flip to the index at the back, find the word, and jump straight to the listed pages. A database index is exactly that idea — and it's the difference between the query that takes 2 seconds and the same query taking 2 milliseconds. This lesson is about earning that speed, and about what it quietly costs you.

What an index is — and what it speeds up

CREATE INDEX idx_orders_customer_id ON orders(customer_id);

One statement, and the engine builds a separate sorted structure over customer_id, each entry pointing back at its row. Now WHERE customer_id = 501 stops being "check every row" (a full table scan, O(n)) and becomes a few hops down a sorted tree (O(log n)). Indexes accelerate the four row-finding jobs: WHERE filters, JOIN matching, ORDER BY sorting, and GROUP BY grouping — whenever they involve the indexed column(s).

The B-tree, gently

Under the hood sits a B+tree: a short, balanced tree whose internal nodes are signposts and whose leaf nodes hold the sorted values (plus row pointers), linked together like a chain. Two consequences fall out of that picture:

• Equality is fast — descend 3–4 levels even for crores of rows, because the tree stays balanced and shallow.
• Ranges are fast too — BETWEEN 100 AND 900 descends once to the start, then just walks sideways along the linked leaves. This is also why an index can satisfy ORDER BY without sorting.

(Hash indexes are the other family — brilliant for equality, useless for ranges. When an interviewer asks "why B-tree and not hash?", ranges-and-sorting is the answer.)

Clustered vs non-clustered — where the rows actually live

A clustered index IS the table: the rows are physically stored in the index's order. That's why a table gets exactly one — the same books can't be shelved two ways at once. In MySQL's InnoDB, the primary key is the clustered index. A non-clustered (secondary) index is a separate structure whose leaves point back at the row — in InnoDB, via the primary-key value, meaning a secondary-index lookup often does two hops: secondary tree → PK → row. You can have as many secondary indexes as you're willing to pay for (next section).

Composite and covering indexes — the pro move

Watch a frequent reporting query get the royal treatment:

-- The query:
SELECT customer_id, order_date, total_amount
FROM orders
WHERE customer_id = ?
ORDER BY order_date;

-- The index designed FOR it:
CREATE INDEX idx_orders_covering
    ON orders(customer_id, order_date, total_amount);

Column order tells the story: customer_id first serves the equality filter; order_date second means each customer's entries are already sorted — ORDER BY costs nothing; and total_amount tags along so every selected column lives in the index itself. The engine never touches the table — an index-only scan, and the index is said to cover the query. One rule to keep forever: a composite index on (a, b) serves queries on a and on a, b — but NOT on b alone. Leftmost prefix wins.

Wait — indexes are not free speed

What do we pay? Three bills arrive:

• Every write pays a tax. Each INSERT/UPDATE/DELETE must also update every index on the table. Ten indexes on a write-heavy table can be a net loss.
• Low-cardinality columns waste it. Index an is_active flag and half the table matches — hopping index→table per row costs more than one clean scan, so the optimizer ignores your index anyway.
• Storage and memory. Indexes are real data structures competing for the same RAM your hot rows want.

This is the trade-off answer interviewers fish for: indexes buy read speed with write speed and memory — say it exactly like that.

Sargable queries — don't blindfold your index

Here's a heartbreaker: the index exists, and the query still crawls.

-- SLOW: the function hides order_date from the index
SELECT * FROM orders WHERE YEAR(order_date) = 2024;

-- FAST: same rows, expressed as a range the index can walk
SELECT * FROM orders
WHERE order_date >= '2024-01-01' AND order_date < '2025-01-01';

Wrapping an indexed column in a function (YEAR(), UPPER(), arithmetic, implicit type casts) forces the engine to compute it per row — the sorted tree can't help. Keep the raw column alone on one side of the comparison; such predicates are called sargable. Same villain in disguise: LIKE '%gmail.com' — a leading wildcard has no prefix to descend the tree with.

Reading EXPLAIN — asking the optimizer to show its work

EXPLAIN SELECT * FROM orders WHERE customer_id = 501;

type: ref   key: idx_orders_customer_id   rows: 2   ← index at work
type: ALL   key: NULL                     rows: 40000  ← full scan, investigate!

EXPLAIN prints the optimizer's chosen plan. The debugging loop of every slow query: run EXPLAIN → spot the full scan or huge row estimate → fix with an index or a sargable rewrite → EXPLAIN again. Mentioning this loop, unprompted, reads as real experience.

Common mistakes

• Indexing every column "to be safe" — each one taxes every write forever.
• Wrapping indexed columns in functions inside WHERE — non-sargable, index blinded.
• Expecting an (a, b) composite index to serve WHERE b = ? — leftmost prefix rule.
• Indexing boolean/low-cardinality flags on big tables.
• Never running EXPLAIN — guessing where the time goes instead of asking.

Quick recap

Practice Zone — PYQs from real selection rounds

Q1What an index doeseasy

Without an index, finding one row in a crore-row table means checking every row. What does a B-tree index turn that cost into, roughly?

Asked in

AO(log n) — a few hops down a sorted treeBO(1) — always instantCO(n/2) — half the rows on averageDNothing changes for SELECT queries

Q2Clustered vs non-clusteredmedium

How many clustered indexes can one table have?

Asked in

AOne — the data itself can only be physically ordered one wayBAs many as you likeCTwo — one ascending, one descendingDZero — clustering is automatic and hidden

Q3When indexes hurtmedium

Which column is the WORST candidate for an index?

Asked in

AAn is_active boolean flag on a huge tableBThe email column used in login lookupsCThe foreign key used in every joinDThe order_date column used in range reports

Q4Covering indexmedium

What makes an index a covering index for a given query?

Asked in

AIt contains every column the query touches, so the table is never visitedBIt covers all rows of the tableCIt's built on the primary keyDIt includes a WHERE condition in its definition

Q5B-tree behaviourhard

Why does one B-tree index efficiently serve both WHERE id = 500 and WHERE id BETWEEN 100 AND 900?

Asked in

ALeaves are sorted and linked — descend once, then walk the rangeBThe engine builds a second hash index automaticallyCIt doesn't — ranges always need a full scanDB-trees store every query's result in advance

FAQ

Next lesson: money must never vanish between two UPDATEs — Lesson 10: Transactions & ACID →