Indexes and how queries find rows

Introduction

To answer WHERE city = 'Sylhet', a DBMS with no help has only one choice: read every row and check it. That is a full table scan, and it takes time in proportion to the table's size: fine for 100 rows, slow for 100 million.

An index is a second structure, kept in sorted order, that maps a column's values to the rows that hold them, like the index at the back of a book. With it, the DBMS jumps straight to the right rows.

A query that is instant on 100 rows can take minutes on 100 million. Indexes are the main tool for keeping queries fast as data grows, and EXPLAIN shows whether one is being used.

How it works

B+ trees

Most indexes are B+ trees:

                 [ Dhaka | Rajshahi ]
               /          |           \
  [Barishal Comilla] [Dhaka Khulna] [Rajshahi Sylhet]  ← leaves, linked left to right

• Every path from the root to a leaf has the same length: the tree stays balanced as rows are added.
• Each node holds many keys (hundreds, one disk page), so the tree is very flat: about 3 or 4 levels for a million rows. Finding one row reads only that many pages, where a scan would read them all.
• The leaves are linked in order, so a range (WHERE marks BETWEEN 60 AND 80) finds the first leaf and then reads along.

A hash index is the other kind: faster still for =, useless for ranges and sorting.

Indexes are not free

• Each index takes space.
• Each INSERT, UPDATE and DELETE must change every index on the table too, so writes get slower.

So index the columns your queries search, join and sort on (WHERE, JOIN ... ON, ORDER BY), especially ones with many different values. An index on a column with two values (gender, say) rarely helps.

A composite index on (dept, marks) helps queries on dept, and on dept together with marks, but not on marks alone: like a phone book sorted by last name, then first name, it is no help for finding a first name. This is the leftmost prefix rule.

Syntax

CREATE INDEX idx_city ON people(city);
CREATE INDEX idx_dept_marks ON results(dept, marks);
EXPLAIN QUERY PLAN SELECT name FROM people WHERE city = 'Sylhet';
DROP INDEX idx_city;

Example

EXPLAIN QUERY PLAN shows how SQLite will run a query, without running it:

CREATE TABLE people (
  id INTEGER PRIMARY KEY,
  name TEXT,
  city TEXT
);
INSERT INTO people (name, city) VALUES
  ('Rahim', 'Dhaka'), ('Karim', 'Sylhet'), ('Nadia', 'Dhaka'), ('Tania', 'Khulna');

-- No index on city: read every row
EXPLAIN QUERY PLAN SELECT name FROM people WHERE city = 'Sylhet';

CREATE INDEX idx_city ON people(city);

-- Now the index finds the rows
EXPLAIN QUERY PLAN SELECT name FROM people WHERE city = 'Sylhet';

-- The primary key is always a search
EXPLAIN QUERY PLAN SELECT name FROM people WHERE id = 3;

SELECT name FROM people WHERE city = 'Sylhet';

• SCAN people is a full table scan.
• After CREATE INDEX idx_city ON people(city), the same query becomes SEARCH people USING INDEX idx_city (city=?): it finds the matching rows through the index.
• A search on the primary key always uses it: SQLite keeps every table sorted by its rowid, and INTEGER PRIMARY KEY is that rowid. Most DBMSs index primary keys and UNIQUE columns automatically.

MySQL and PostgreSQL write EXPLAIN SELECT ...; their output looks different, but tells the same story.

Line by line

1. people has four rows and no index on city.
2. The first EXPLAIN QUERY PLAN shows SCAN people: every row would be read.
3. CREATE INDEX idx_city ON people(city); builds an index on the city column.
4. The same query's plan now says SEARCH people USING INDEX idx_city (city=?).
5. A search on id uses the primary key, because INTEGER PRIMARY KEY is the table's own row number.
6. The last SELECT runs the query for real, and the answer is the same with or without the index: Karim.

Expected result

QUERY PLAN
-----------
SCAN people
(1 row)

QUERY PLAN
-------------------------------------------
SEARCH people USING INDEX idx_city (city=?)
(1 row)

QUERY PLAN
-------------------------------------------------
SEARCH people USING INTEGER PRIMARY KEY (rowid=?)
(1 row)

name
-----
Karim
(1 row)

In the real world

When a website suddenly slows down as it grows, a missing index is the most common cause. Database administrators read query plans every day, and a single well-chosen index can turn a query from minutes into milliseconds.

Common mistakes

• Indexing every column, which slows every insert and update.
• Expecting an index on (dept, marks) to help a search on marks alone.
• Assuming the index was used, instead of checking the plan.

Best practices

• Index the columns used in WHERE, JOIN and ORDER BY on large tables.
• Check the plan before and after adding an index.
• Remove indexes that no query uses.

Summary

Without an index, a DBMS scans every row. An index, usually a B+ tree, finds rows in a few page reads, at the cost of space and slower writes. EXPLAIN QUERY PLAN shows which is used, and composite indexes follow the leftmost prefix rule.

Mark lesson complete