🗄️Databases
Foundations · Lesson 4/8

Indexes & Query Performance

45 min 1 quiz Graded labs: 3

The cookbook with no index at the back 📖

You own a 500-page cookbook and want every recipe with saffron. With no index you must read every page from the first to the last. With an index at the back, you look up "saffron" in an alphabetical list, read "pages 41, 187, 302" and jump straight there.

A database index is exactly that: a small, sorted side structure that tells the database where rows live, so it can jump instead of reading everything. It comes with a price too: when the cookbook gets a new recipe, the index at the back must be updated as well.

Until now your queries were correct. This lesson is about making them fast, and about proving it instead of guessing.

What you'll learn

  • How an index works (a sorted tree) and why it turns a million steps into a handful
  • CREATE INDEX, and how to read a query plan with EXPLAIN QUERY PLAN
  • Composite indexes and why column order matters
  • Writing queries an index can actually use ("sargable" conditions)
  • What indexes cost, and when not to add one

In the labs you work with SQLite from Python and check the query plan with your own eyes.

Scan or search?

With no index, answering WHERE customer_id = 7 forces a full table scan: the database reads every row and keeps the matching ones. Ten rows, no problem. Ten million rows, every query reads ten million rows.

An index stores the values of one or more columns in sorted order, each with a pointer to its row. Sorted data can be searched like a dictionary: open in the middle, decide left or right, repeat. Searching a million sorted values takes about 20 comparisons (log2 of a million). Real databases use a B-tree: a shallow, wide tree of pages where each page narrows the search a lot, so even a table with millions of rows is usually reached in 3-4 page reads.

CREATE INDEX idx_orders_customer ON orders (customer_id);
CREATE UNIQUE INDEX idx_users_email ON users (email);   -- also forbids duplicates
DROP INDEX idx_orders_customer;

Because the entries are sorted, one index helps with several jobs: equality (= 7), ranges (BETWEEN, >=, <) and ORDER BY on the same column.

Good to know: PRIMARY KEY and UNIQUE constraints already create an index for you. Most databases do not index a foreign-key column automatically (MySQL's InnoDB is an exception), so the customer_id in orders usually needs your own index.

Reading a query plan

You never guess whether an index is used: you ask the database. In SQLite put EXPLAIN QUERY PLAN in front of the query (PostgreSQL and MySQL have EXPLAIN, and PostgreSQL's EXPLAIN ANALYZE also runs the query and reports real timings).

EXPLAIN QUERY PLAN
SELECT id, total_cents FROM orders WHERE customer_id = 7;

-- no index:       SCAN orders
-- with an index:  SEARCH orders USING INDEX idx_orders_customer (customer_id=?)

The two key words:

  • SCAN: every row (or every index entry) is visited. Cost grows with the table.
  • SEARCH: the database jumps to the matching entries through an index. The part in parentheses shows which conditions the index handled.

Careful with one look-alike: SCAN orders USING COVERING INDEX ... still walks the whole index. It is cheaper than reading the table, but it is a scan, not a jump. The exact wording of plans differs between versions and databases, so read them for the idea (scan versus search), not as a stable text format.

A plan can also say USE TEMP B-TREE FOR ORDER BY: the database had to collect rows and sort them itself. An index whose order already matches the ORDER BY removes that step, which matters a lot for "latest 10 orders" style queries.

Why not index everything?

Every index must be updated by every INSERT, DELETE, and by an UPDATE of an indexed column, and it takes disk space. Reads get faster, writes get slower. The art is to index what your real queries filter, join, and sort on, and to verify with the plan.

The scan visits all 1,000,000 values before finding the last one, while binary search needs about 20 steps because the data is sorted. That sortedness is what an index buys you, and it is also why the index must be kept in order when rows change.

# Finding one id among a million sorted ids: scanning versus binary search.
# A B-tree is a wider, disk-friendly cousin of binary search.
ids = list(range(0, 2_000_000, 2))  # 1,000,000 sorted ids
target = 1_999_998                  # the very last one: worst case for a scan


def scan(items, wanted):
    steps = 0
    for value in items:
        steps += 1
        if value == wanted:
            break
    return steps


def binary_search(items, wanted):
    low, high, steps = 0, len(items) - 1, 0
    while low <= high:
        steps += 1
        mid = (low + high) // 2
        if items[mid] == wanted:
            break
        if items[mid] < wanted:
            low = mid + 1
        else:
            high = mid - 1
    return steps


print("full scan steps:   ", scan(ids, target))
print("binary search steps:", binary_search(ids, target))
Open in Code Lab

Lab exercise 1

PythonGraded in Code Lab

A table orders with 3,000 rows exists, with columns id, customer_id, reference (like ORD-000500, unique per order), status, created_at and total_cents. The program looks up orders either by customer_id or by reference, then asks SQLite for the query plan.

Write index_sql (one or more CREATE INDEX statements) so that both lookups become an index search instead of a full table scan. Make the index on reference UNIQUE, since a reference identifies exactly one order.

Input: one line: customer_id <number> or reference <text>.

Output: rows: N (how many orders match) and access: index search or access: full table scan.

Example: customer_id 7 prints rows: 15 and access: index search.

Visible tests (5)
  • Customer 7: 15 orders found by index
  • Last customer id (boundary)
  • Unknown customer: no rows, still an index search
  • Exact reference: one row
  • Missing reference: zero rows
Example run
Input
customer_id 7
Expected output
rows: 15
access: index search
Starter code
import sqlite3
import sys

db = sqlite3.connect(":memory:")
db.executescript("""
    CREATE TABLE orders (
        id          INTEGER PRIMARY KEY,
        customer_id INTEGER NOT NULL,
        reference   TEXT NOT NULL,
        status      TEXT NOT NULL,
        created_at  TEXT NOT NULL,      -- ISO 8601 date: YYYY-MM-DD
        total_cents INTEGER NOT NULL

More lines in Code Lab: 34

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Composite indexes: column order matters

An index can cover several columns. Think of a phone book sorted by last name, then first name. It finds "Haddad" instantly, and "Haddad, Amal" instantly, but "everyone called Amal" is hopeless: Amals are scattered through every letter.

CREATE INDEX idx_people_name ON people (last_name, first_name);

-- uses the index (leftmost column first):
WHERE last_name = 'Haddad'
WHERE last_name = 'Haddad' AND first_name = 'Amal'
-- cannot jump (skips the leftmost column):
WHERE first_name = 'Amal'

This is the leftmost prefix rule: a composite index helps queries that use its columns from the left, without gaps.

Equality first, then the sort or range column

Take the common query "the 5 latest orders with status X":

SELECT id, created_at FROM orders
WHERE status = 'paid'
ORDER BY created_at DESC, id DESC
LIMIT 5;
  • An index on (status) finds the paid orders, but the database must then sort them all to find the latest 5 (USE TEMP B-TREE FOR ORDER BY).
  • An index on (status, created_at) finds the paid orders already sorted by date. It reads the last 5 entries and stops: no sorting, no matter how many paid orders exist.
  • An index on (created_at, status) is the wrong order: it cannot jump to one status.

Rule of thumb: put the columns tested with = first, then the column you range over or sort by. The primary key (here id) is implicitly the last part of every index in SQLite, which is why ORDER BY created_at DESC, id DESC costs nothing extra.

A covering index contains every column a query needs, so the database never visits the table at all. That is faster again, but it makes the index bigger.

Lab exercise 2

PythonGraded in Code Lab

The program shows the 5 latest orders (by created_at, ties broken by larger id) for a status read from stdin, then prints how SQLite ran the query.

The starter has only an index on status. That finds the right orders but still needs an extra sorting step. Write index_sql with one composite index so the query is an index search and the plan has no sort step.

Input: one status: new, paid, shipped, cancelled (or any other word).

Output: up to 5 lines order ID on DATE, then access: ... and sort: none or sort: extra sort step.

Example: status paid prints five order lines, then access: index search and sort: none.

Visible tests (5)
  • Latest paid orders
  • Latest shipped orders
  • Another status: new
  • Cancelled orders
  • Unknown status: no rows, still a clean index plan
Example run
Input
paid
Expected output
order 1877 on 2025-12-30
order 417 on 2025-12-30
order 1981 on 2025-12-28
order 521 on 2025-12-28
order 2085 on 2025-12-26
access: index search
sort: none
Starter code
import sqlite3
import sys

db = sqlite3.connect(":memory:")
db.executescript("""
    CREATE TABLE orders (
        id          INTEGER PRIMARY KEY,
        customer_id INTEGER NOT NULL,
        reference   TEXT NOT NULL,
        status      TEXT NOT NULL,
        created_at  TEXT NOT NULL,      -- ISO 8601 date: YYYY-MM-DD
        total_cents INTEGER NOT NULL

More lines in Code Lab: 36

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Writing queries an index can use

An index stores the raw column values. If the query wraps the column in a function or an expression, the database can no longer compare it with the sorted entries, so it falls back to a scan. Conditions an index can use are called sargable (search-ARGument-able).

-- Not sargable: the function hides the column from the index
WHERE substr(created_at, 1, 4) = '2025'
WHERE lower(email) = 'amal@example.com'
WHERE total_cents + 100 > 5000

-- Sargable: the bare column is compared with a constant
WHERE created_at >= '2025-01-01' AND created_at < '2026-01-01'
WHERE email = 'amal@example.com'     -- and store emails normalised to lower case
WHERE total_cents > 4900

Rewrite recipes:

  • Move the work to the other side of the comparison: total_cents > 4900 instead of total_cents + 100 > 5000.
  • Use a half-open range for dates: >= start AND < next_start. It also avoids bugs with the last day. ISO 8601 text (YYYY-MM-DD) sorts in date order, which is why such ranges work.
  • A pattern that starts with a wildcard (LIKE '%saffron') cannot use a normal B-tree, because the sorted order does not help when you do not know the first letters. LIKE 'saff%' can in many databases. Searching inside text at scale needs a full-text index instead.
  • Many databases also support an expression index, such as CREATE INDEX ... ON users (lower(email)), when you really need to search by a computed value.

When the planner ignores your index

The planner picks the cheapest plan it estimates. If a condition matches most of the table (a column with two values, half the rows each), reading the table directly can be cheaper than hopping through an index, so a plan with SCAN is not always a mistake. An index pays off on selective conditions: ones that keep a small fraction of the rows. Run ANALYZE (SQLite and PostgreSQL) so the planner has fresh statistics.

The scan examines all 5,000 rows to find 25 matches; the index jumps straight to those 25. Notice the cost side: building the lookup needs a pass over the data, and every insert has to maintain it. A real B-tree index is more capable than this Map (it also supports ranges and ordering), but the trade-off is the same.

// A toy "index" in JavaScript: a lookup built once, then used for every query.
const orders = [];
for (let i = 1; i <= 5000; i++) {
  orders.push({ id: i, customerId: ((i * 37) % 200) + 1 });
}

// Without an index: look at every row.
let examined = 0;
const scanned = orders.filter((o) => {
  examined++;
  return o.customerId === 7;
});
console.log("scan:  examined", examined, "rows, found", scanned.length);

// With an index: building it costs one pass, then lookups jump straight to the rows.
const byCustomer = new Map();
for (const o of orders) {
  if (!byCustomer.has(o.customerId)) byCustomer.set(o.customerId, []);
  byCustomer.get(o.customerId).push(o);
}
const hits = byCustomer.get(7) ?? [];
console.log("index: examined", hits.length, "rows, found", hits.length);

// The price: every insert must now update the table AND the index.
function insertOrder(order) {
  orders.push(order);
  const bucket = byCustomer.get(order.customerId) ?? [];
  bucket.push(order);
  byCustomer.set(order.customerId, bucket);
}
insertOrder({ id: 5001, customerId: 7 });
console.log("after one insert:", byCustomer.get(7).length, "orders for customer 7");
Open in Code Lab

Lab exercise 3

PythonGraded in Code Lab

An index on orders (created_at) exists. The program counts the orders created in a given year, but the query wraps created_at in substr(...), so SQLite scans every entry.

Rewrite count_sql so that it returns the same count but is an index search. Use the named parameters :year_start (YYYY-01-01 of the year) and :year_end (01-01 of the next year). Remember the upper bound must be exclusive.

Input: one year, for example 2025.

Output: orders in YEAR: N and access: index search or access: full table scan.

Example: 2024 prints orders in 2024: 1516 and access: index search.

Visible tests (4)
  • 2024: the upper bound must exclude 2025-01-01
  • 2025
  • A year before the data: zero rows
  • A year after the data: zero rows
Example run
Input
2024
Expected output
orders in 2024: 1516
access: index search
Starter code
import sqlite3
import sys

db = sqlite3.connect(":memory:")
db.executescript("""
    CREATE TABLE orders (
        id          INTEGER PRIMARY KEY,
        customer_id INTEGER NOT NULL,
        reference   TEXT NOT NULL,
        status      TEXT NOT NULL,
        created_at  TEXT NOT NULL,      -- ISO 8601 date: YYYY-MM-DD
        total_cents INTEGER NOT NULL

More lines in Code Lab: 33

Try in Code Lab

Hints and instant feedback are in Code Lab. Optional practice: it does not block finishing the lesson.

JavaScript and Python also run in your browser without an account; other languages use the secure server runner and need a free account.

Quick quiz

Question 1 of 5

Why does an index make WHERE email = ? fast on a big table?

Question 2 of 5

There is an index on people (last_name, first_name). Which query cannot use it to jump straight to its rows?

Question 3 of 5

There is a plain index on created_at. Which condition can use it to jump to the 2025 rows?

Question 4 of 5

A teammate wants to add an index on every column "to be safe". What is the real downside?

Question 5 of 5

Half of all rows have status = 'active'. You index status and run WHERE status = 'active'. What will the planner most likely do?

Recap and what to practice next

  • An index is a sorted side structure (usually a B-tree) that lets the database search instead of scan. It costs disk space and slows writes.
  • Check, do not guess: EXPLAIN QUERY PLAN (or EXPLAIN / EXPLAIN ANALYZE). SEARCH means a jump; SCAN reads everything, even SCAN ... USING COVERING INDEX.
  • Composite indexes follow the leftmost prefix rule: equality columns first, then the range or ORDER BY column. The right order can remove a sort step completely.
  • Keep conditions sargable: compare the bare column with constants, use half-open ranges for dates, avoid leading wildcards.
  • Index selective conditions and the columns your real queries use. Foreign keys usually need a manual index.

Practice next: in the first lab, add a third lookup (by status and total_cents) and watch the plan. Try a composite index in the wrong column order and see the plan change. Then read about transactions: indexes and constraints are only trustworthy if concurrent changes are applied safely, which is the next topic on the roadmap.

Practice

Reading is not learning until you run something. Pick one.

Graded lab exercises

Open an example in Code Lab

Blank Code Lab in Python
Previous
Joins, Aggregation & Subqueries
Next lesson
Transactions, ACID & Concurrency