Index Concept

The Transactions topic completed the discipline a database needs in order to give the correct answer: commit boundaries, isolation levels, locks, and the implicit side effects of triggers. What that topic left in hand at its end was a query that produces the correct result.

This lesson does not ask the same query a second time. What it asks is: how many rows did the database look at while producing that correct result? A query that asks for a single member’s records in a two-million-row table can deliver the correct answer by reading all two million rows, or in about sixty steps. The difference between the two is not in how the query is written, but in how the data is organized.

A Measurable Data Set

Performance claims do not show up on small tables: every path is fast on a table of a hundred rows. For the measurement to rise above the noise, the table has to be large enough. The following script sets up a data set built from library loan records. The rows are generated with a recursive common table expression; no external file is required.

-- setup.sql — library data set
CREATE TABLE branch (
  branch_id INTEGER PRIMARY KEY,
  name      TEXT NOT NULL,
  city      TEXT NOT NULL
);
CREATE TABLE member (
  member_id         INTEGER PRIMARY KEY,
  name              TEXT NOT NULL,
  city              TEXT NOT NULL,
  registration_date TEXT NOT NULL
);
CREATE TABLE book (
  book_id   INTEGER PRIMARY KEY,
  title     TEXT NOT NULL,
  author    TEXT NOT NULL,
  year      INTEGER NOT NULL,
  branch_id INTEGER NOT NULL
);
CREATE TABLE loan (
  loan_id     INTEGER PRIMARY KEY,
  book_id     INTEGER NOT NULL,
  member_id   INTEGER NOT NULL,
  pickup_date TEXT NOT NULL,
  return_date TEXT
);

INSERT INTO branch (branch_id, name, city) VALUES
  (1,'Central','Ankara'),(2,'Bahcelievler','Ankara'),(3,'Kadikoy','Istanbul'),
  (4,'Beyoglu','Istanbul'),(5,'Konak','Izmir'),(6,'Nilufer','Bursa'),
  (7,'Selcuklu','Konya'),(8,'Cankaya','Ankara');

INSERT INTO member (member_id, name, city, registration_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 120000)
SELECT n, 'Member ' || n,
       CASE n % 5 WHEN 0 THEN 'Ankara' WHEN 1 THEN 'Istanbul' WHEN 2 THEN 'Izmir'
                  WHEN 3 THEN 'Bursa' ELSE 'Konya' END,
       date('2015-01-01', '+' || (n % 3200) || ' days')
FROM counter;

INSERT INTO book (book_id, title, author, year, branch_id)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 200000)
SELECT n, 'Book ' || n, 'Author ' || (n % 4000), 1950 + (n % 75), 1 + (n % 8)
FROM counter;

INSERT INTO loan (loan_id, book_id, member_id, pickup_date, return_date)
WITH RECURSIVE counter(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM counter WHERE n < 2000000)
SELECT n, 1 + ((n * 7) % 200000), 1 + ((n * 13) % 120000),
       date('2018-01-01', '+' || ((n * 37) % 2437) || ' days'),
       CASE WHEN n % 9 = 0 THEN NULL
            ELSE date('2018-01-01', '+' || (((n * 37) % 2437) + 14) || ' days') END
FROM counter;

The script is saved under the name setup.sql and run. Every measurement in this topic is made on this data set.

rm -f library.db
sqlite3 library.db < setup.sql
sqlite3 library.db "SELECT 'member', count(*) FROM member
  UNION ALL SELECT 'book', count(*) FROM book
  UNION ALL SELECT 'loan', count(*) FROM loan;"

member|120000
book|200000
loan|2000000

The Default Cost of a Search

A single member’s loan records are being asked for. How does the database meet this query? A query plan is the tree that shows which steps a query will be executed with; it is requested from the command line with the EXPLAIN QUERY PLAN prefix. Two more tools are used for measurement: .timer on prints the elapsed time, and .stats vmstep prints the number of virtual machine steps the query spent.

sqlite3 library.db <<'SQL'
EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan WHERE member_id = 4242;
.timer on
.stats vmstep
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM loan WHERE member_id = 4242;
SQL

QUERY PLAN
`--SCAN loan
17
VM-steps: 6000028
Run Time: real 0.038 user 0.029739 sys 0.008274
17
VM-steps: 6000028
Run Time: real 0.036 user 0.027952 sys 0.007465
17
VM-steps: 6000028
Run Time: real 0.035 user 0.028067 sys 0.007407

The plan has a single node: SCAN loan. This means a full table scan — every row in the table is read, and the condition is tested separately for each row. Two million rows were visited in order to return seventeen rows.

The two measures have to be read together. Time depends on the environment: the same query comes out differently on a faster disk or a more loaded machine, so time is read not as an absolute value but as a ratio against another time in the same environment. Step count, by contrast, is independent of the environment: the same data and the same plan give the same step count on every machine. The source of the six million steps is also clear — an average of three virtual machine instructions for each of the two million rows.

This cost is directly proportional to table size. If the number of loans doubles, the scan doubles too: $O(n)$. This is the result from the Linear Search lesson in the Algorithms course; the only difference is that the array lives on disk.

What an Index Is

An index is a separate structure that keeps a column’s values in sorted order and records which row each value belongs to. The table data stays in place; the index opens a second access path to that data.

The library analogy applies directly: the books on the shelves are arranged in some order, but in a library with no catalog, the only way to find a given author’s books is to walk every shelf. Catalog cards sit in a separate box sorted by author name, and each card carries a shelf number. A search in the card box proceeds by opening the middle of the box and deciding which direction to go.

In relational databases, the counterpart to this box is most often a B-tree. This is the structure built in the B-Trees lesson in the Data Structures course: every node is wide enough to fit a disk page, the tree is balanced, and its height grows with the logarithm of the record count. Finding a key means descending from the root to a leaf; in an index of two million records, that means reading a handful of pages. When the table grows tenfold, the scan grows ten times more expensive, while the number of levels descended in the tree grows by one.

The Index’s Measured Effect

The same query is repeated with an index on member_id.

sqlite3 library.db <<'SQL'
.timer on
CREATE INDEX loan_member ON loan(member_id);
.timer off
EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan WHERE member_id = 4242;
.timer on
.stats vmstep
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM loan WHERE member_id = 4242;
SELECT count(*) FROM loan WHERE member_id = 4242;
SQL

Run Time: real 0.257 user 0.213982 sys 0.036173
QUERY PLAN
`--SEARCH loan USING INDEX loan_member (member_id=?)
17
VM-steps: 62
Run Time: real 0.000 user 0.000016 sys 0.000013
17
VM-steps: 62
Run Time: real 0.000 user 0.000007 sys 0.000005
17
VM-steps: 62
Run Time: real 0.000 user 0.000006 sys 0.000005

The plan node changed from SCAN to SEARCH ... USING INDEX. This is what should be read here: the database no longer reads the table from start to end; it descends the index to the member_id = 4242 key and looks only at the rows there.

Step count dropped from 6,000,028 to 62 — roughly a hundred thousand times. Time, in turn, became unmeasurable: a value of 0.000 does not mean “zero time,” it means falling below the timer’s resolution. This is a reminder of the first rule of measurement discipline: once a path becomes cheap enough, time stops carrying information, and what needs to be measured is the work done. Building the index is not free either; sorting two million rows took about a quarter second in this environment.

The Index’s Cost

While an index makes reading cheaper, it makes two things more expensive: space and writes. The following measurement adds the same two hundred thousand rows to two copies of the same data set; one copy has no index, the other has three indexes on loan.

rm -f noindex.db indexed.db
sqlite3 noindex.db < setup.sql
cp noindex.db indexed.db
sqlite3 indexed.db 'CREATE INDEX l_member ON loan(member_id);
CREATE INDEX l_book ON loan(book_id);
CREATE INDEX l_pickup ON loan(pickup_date);'

for db in noindex.db indexed.db; do
  printf '%s ' "$db"
  sqlite3 "$db" <<'SQL'
.timer on
INSERT INTO loan (book_id, member_id, pickup_date, return_date)
WITH RECURSIVE s(n) AS (SELECT 1 UNION ALL SELECT n+1 FROM s WHERE n < 200000)
SELECT 1 + ((n*7) % 200000), 1 + ((n*13) % 120000),
       date('2024-01-01','+'||(n%300)||' days'), NULL
FROM s;
SQL
done
ls -l noindex.db indexed.db | awk '{print $9, $5}'

noindex.db Run Time: real 0.060 user 0.056476 sys 0.003023
indexed.db Run Time: real 0.396 user 0.281373 sys 0.096411
indexed.db 192196608
noindex.db 91459584

With three indexes in place, the same insert took about six and a half times longer in this environment, and the file grew to more than double its size. The reason is direct: for every row inserted, a key is written into each of the three trees, and the balance of those trees is maintained. The same cost applies to deletes and to UPDATE statements that change a key column. An index is therefore not the kind of option that is only nice to have — it is a deliberate trade-off between reading and writing.

Selectivity

Opening an index on every column multiplies the cost while usually not paying off. The deciding measure is selectivity: how small a fraction of the table a condition selects. In the book table, branch_id takes eight distinct values, while author takes four thousand. The following measurement runs the same query shape for both columns, without an index and then with one.

rm -f selectivity.db
sqlite3 selectivity.db < setup.sql

echo "without index:"
sqlite3 selectivity.db <<'SQL'
.stats vmstep
SELECT sum(year) FROM book WHERE branch_id = 3;
SELECT sum(year) FROM book WHERE author = 'Author 7';
SQL

sqlite3 selectivity.db 'CREATE INDEX book_branch ON book(branch_id);
CREATE INDEX book_author ON book(author);'

echo "with index:"
sqlite3 selectivity.db <<'SQL'
.stats vmstep
SELECT sum(year) FROM book WHERE branch_id = 3;
SELECT sum(year) FROM book WHERE author = 'Author 7';
SQL

without index:
49674950
VM-steps: 650011
99075
VM-steps: 600111
with index:
49674950
VM-steps: 125012
99075
VM-steps: 262

The author condition got roughly twenty-three hundred times cheaper; the branch condition only about five times cheaper. The split comes from selectivity: author = 'Author 7' selects fifty of two hundred thousand books, while branch_id = 3 selects twenty-five thousand of them. In the second case, the database still has to fetch twenty-five thousand rows from the table after reading twenty-five thousand index entries — work that is not much cheaper than reading the table in sequence. An index opened on a column with low selectivity pays the write cost without returning it on the read side.

Summary

• A condition on a column with no index is met with a full table scan; the cost is directly proportional to row count.
• An index is a separate structure that keeps column values sorted; in a B-tree-shaped index, search cost grows with the logarithm of row count.
• The same query in this data set dropped from 6,000,028 steps to 62; because time fell below the timer’s resolution, step count was used as the measure.
• An index takes up space and makes every insert, delete, and key update more expensive; inserting into a table with three indexes took about six and a half times longer in this environment.
• The payoff is determined by selectivity: an index pays off greatly on conditions that select few rows, and the payoff disappears on conditions that select a large fraction of the table.

Next Step

This lesson looked at plan output twice and distinguished two words: SCAN and SEARCH. Real queries do not have a single node — joins, sorting, grouping, and subqueries turn the plan into a multi-row tree. The next lesson takes up reading that tree: the order in which nodes run, which node drives which table, and how sorting shows up in the plan. The shape of plan output changes from engine to engine; what needs to be read is not the shape but the decision inside the plan.