Indexes & performance

Chapter 11 4 code blocks 2724 words

On a 20-row table every query is instant, so nothing in this guide has been slow yet. On a 50-million-row table, the same query can take three milliseconds or three minutes depending on one thing: whether the database can find the rows without reading all of them.

Your students will not tune databases for a living. But they will one day write a query that never finishes, and they need to know why — and that the fix is usually one line.

Why a query is slow

There are really only a handful of causes, and they are worth naming up front:

1. Full table scan — the database reads every row because it has no faster way to find the ones you asked for.
2. Too much data returned — SELECT * on a wide table, or no LIMIT while exploring.
3. Fan-out in a JOIN — the intermediate result is far bigger than either input (Chapter 5).
4. Sorting or deduplicating a huge result — ORDER BY, DISTINCT, UNION on millions of rows.
5. A function wrapped around the filtered column — which disables any index that existed.

Number 1 is the big one, and the index is its cure.

How an index actually works

Technically most indexes are B-trees — a balanced tree kept in sorted order. The practical consequence is the one that matters:

Because the index is sorted, it also accelerates things beyond equality:

• WHERE city = 'Tashkent' — jump straight to the entry.
• WHERE grade BETWEEN 80 AND 90 — jump to 80 and read forward.
• ORDER BY enrolled_at — the data is already in that order; no sort needed.
• MAX(grade) — read the last entry and stop.
• WHERE name LIKE 'Kar%' — a known prefix is a range. '%ova' is not, which is Chapter 3's rule.

Creating indexes

CREATE INDEX idx_students_city ON students(city);

-- unique index: also enforces that no two rows share the value
CREATE UNIQUE INDEX idx_students_email ON students(email);

-- partial index: only index the rows you actually query (a big saving)
CREATE INDEX idx_active_enrollments
    ON enrollments(student_id) WHERE status = 'active';

DROP INDEX IF EXISTS idx_students_city;

-- SQLite: list what already exists
SELECT name, tbl_name, sql FROM sqlite_master WHERE type = 'index';

:::tip 💡 What you get for free A PRIMARY KEY and a UNIQUE constraint each create an index automatically — that is how they check uniqueness quickly. So WHERE student_id = 5 is already fast without you doing anything.

Foreign keys, however, are usually not indexed automatically. That surprises people: if you join enrollments to students constantly, index enrollments.student_id yourself. This is the single most commonly missing index in real schemas. :::

The columns worth indexing, in priority order:

1. Foreign key columns used in JOINs.
2. Columns that appear in WHERE on big tables.
3. Columns used in ORDER BY on big tables.
4. Columns in GROUP BY, sometimes.

Composite indexes and column order

An index can cover several columns. The order of the columns matters enormously, and this is a favourite interview question.

CREATE INDEX idx_enr_course_status ON enrollments(course_id, status); :::analogy 🧩 The phone book rule A phone book is sorted by (last name, first name). You can find "Karimov, Aziz" instantly. You can find everyone named Karimov instantly. But you cannot find everyone whose first name is Aziz without reading the whole book — because first name is only sorted within each last name. :::

Exactly the same is true of (course_id, status):

When NOT to index

Students who have just learned about indexes want to index everything. Indexes are not free.

Sargable predicates

A predicate is sargable (Search-ARGument-able) if the database can use an index for it. The rule is one sentence: keep the column bare on the left of the comparison.

If you genuinely need the function — say, "everyone born in March" — most databases let you index the expression itself:

CREATE INDEX idx_birth_month ON students(strftime('%m', birth_date)); This is a functional (expression) index, supported by SQLite 3.9+, PostgreSQL and others.

EXPLAIN QUERY PLAN

Never guess about performance. Ask the database what it intends to do.

EXPLAIN QUERY PLAN
SELECT * FROM enrollments WHERE course_id = 2;

1 row

1 ms

Before an index exists:

SCAN enrollments After CREATE INDEX idx_enr_course ON enrollments(course_id);:

SEARCH enrollments USING INDEX idx_enr_course (course_id=?) :::tip 💡 The one word to teach students to look for SCAN = reading the whole table. SEARCH ... USING INDEX = jumping straight to the rows. On a large table in a query that should return few rows, SCAN is the warning sign. (A SCAN is perfectly fine when you genuinely want most of the table — a full report, for example.) :::

A join plan shows one line per table, and reveals the join order the planner chose:

EXPLAIN QUERY PLAN
SELECT s.first_name, c.title
FROM enrollments e
JOIN students s ON e.student_id = s.student_id
JOIN courses  c ON e.course_id  = c.course_id;

-- SCAN e
-- SEARCH s USING INTEGER PRIMARY KEY (rowid=?)
-- SEARCH c USING INTEGER PRIMARY KEY (rowid=?)

3 rows

1 ms

That is the good shape: scan the big table once, and look each matching row up by primary key.

Making JOINs fast

Three rules cover almost every slow join:

1. Index both sides of the join condition. The primary key side is already indexed; the foreign key side usually is not. CREATE INDEX idx_enr_student ON enrollments(student_id);
2. Filter before joining, not after. Reducing a table from 10 million rows to 1,000 before the join is dramatically cheaper than joining 10 million and then filtering. A CTE makes this explicit: WITH recent AS ( SELECT * FROM enrollments WHERE enrolled_at >= '2026-01-01' ) SELECT s.first_name, r.grade FROM recent r JOIN students s USING (student_id);
3. Aggregate before joining when the many-side is large — this also happens to prevent the fan-out bug from Chapter 5. One fix, two problems solved.

A practical tuning checklist

When a query is slow, work down this list in order:

1. Run EXPLAIN QUERY PLAN. Is there a SCAN on a big table?
2. Is the filtered column indexed? If not, index it and re-check the plan.
3. Is a function wrapped around the filtered column? Rewrite it as a range.
4. Do the join columns have the same type, and is the foreign-key side indexed?
5. Are you selecting columns you do not need? Name them; SELECT * blocks covering indexes.
6. Did COUNT(*) grow after a JOIN? That is fan-out — aggregate first.
7. Is there a DISTINCT hiding duplicate rows from a join? Fix the join instead.
8. Can you filter earlier — push WHERE down into a CTE before the join?
9. Still slow, and the query runs constantly? Consider a summary table refreshed on a schedule.

Practice set

-- 1. See the plan before any index exists
EXPLAIN QUERY PLAN SELECT * FROM enrollments WHERE course_id = 2;

-- 2. Add the index and look again
CREATE INDEX idx_enr_course ON enrollments(course_id);
EXPLAIN QUERY PLAN SELECT * FROM enrollments WHERE course_id = 2;

-- 3. Index the foreign keys used in joins
CREATE INDEX idx_enr_student ON enrollments(student_id);
CREATE INDEX idx_enr_teacher ON enrollments(teacher_id);

-- 4. A composite index, then test the leftmost-prefix rule
CREATE INDEX idx_enr_course_status ON enrollments(course_id, status);
EXPLAIN QUERY PLAN SELECT * FROM enrollments WHERE course_id = 2 AND status = 'active';  -- uses it
EXPLAIN QUERY PLAN SELECT * FROM enrollments WHERE status = 'active';                    -- does not

-- 5. Non-sargable vs sargable, same answer
EXPLAIN QUERY PLAN SELECT * FROM enrollments WHERE strftime('%Y', enrolled_at) = '2025';
EXPLAIN QUERY PLAN SELECT * FROM enrollments
    WHERE enrolled_at >= '2025-01-01' AND enrolled_at < '2026-01-01';

-- 6. A partial index for a common filter
CREATE INDEX idx_active_only ON enrollments(student_id) WHERE status = 'active';

-- 7. List every index in the database
SELECT name, tbl_name FROM sqlite_master WHERE type = 'index' ORDER BY tbl_name;

-- 8. Clean up
DROP INDEX IF EXISTS idx_enr_course;
DROP INDEX IF EXISTS idx_enr_student;
DROP INDEX IF EXISTS idx_enr_teacher;
DROP INDEX IF EXISTS idx_enr_course_status;
DROP INDEX IF EXISTS idx_active_only;

Result 1

1 row

Result 2

1 row

Result 3

1 row

Result 4

1 row

Result 5

1 row

Result 6

1 row

Result 7

5 rows

4 ms

Interview questions

Q: What is an index and how does it speed up a query?

A sorted auxiliary structure (usually a B-tree) that maps values to row locations. It turns an O(n) full scan into an O(log n) lookup, and also serves ranges, sorts and MIN/MAX because it is ordered.

Q: What are the downsides of an index?

Disk space, and slower writes — every insert, update and delete must maintain every index on the table.

Q: Does the column order in a composite index matter?

Yes. Only leftmost prefixes can be used: an index on (A, B) serves A and (A, B), but not B alone. Think of a phone book sorted by last name then first name.

Q: What is a covering index?

One that contains every column the query needs, so the database answers from the index without reading the table at all.

Q: What does "sargable" mean?

That a predicate can use an index. Wrapping the column in a function or arithmetic makes it non-sargable and forces a scan; rewrite it so the column stands alone.

Q: Would you index a gender column?

Usually not — very low cardinality means the index points at a huge fraction of the table, and the planner will often scan anyway. It can help as the second column of a composite index, or in a partial index.

Q: A JOIN is unexpectedly slow. What do you check?

Whether the join columns are indexed (especially the foreign-key side), whether they have the same data type, whether filters could be applied before the join, and whether fan-out is inflating the intermediate result.

Q: How do you find out why a query is slow?

EXPLAIN QUERY PLAN (SQLite) or EXPLAIN ANALYZE (PostgreSQL). Look for a SCAN on a large table where a SEARCH ... USING INDEX was expected.

Summary

• An index is the index at the back of a book: it turns "read everything" into "look it up". O(n) → O(log n).
• PRIMARY KEY and UNIQUE create indexes automatically. Foreign keys usually do not — that is the most commonly missing index in real schemas.
• Composite indexes obey the leftmost-prefix rule. (A, B) serves A, not B. Put the most-filtered, equality-tested column first.
• A covering index answers a query without touching the table — another reason not to SELECT *.
• Do not index small tables, low-cardinality columns, or write-heavy tables. Add an index because a specific query needs it.
• Sargable = the column stands alone on the left. Functions, arithmetic, casts and leading % all disable the index.
• EXPLAIN QUERY PLAN: SCAN = whole table, SEARCH ... USING INDEX = targeted.
• Fast joins: index the foreign key, match the column types, filter early, aggregate before joining.
• Measure with .timer on or EXPLAIN ANALYZE. Change one thing at a time.

Next: Chapter 12 — connecting SQL to Python, and the handover from a query result to a pandas DataFrame.