Reading Query Plans

The previous lesson looked at plan output twice and distinguished two words: SCAN and SEARCH. In a single-table, single-condition query, the plan is a single line and easy to read.

Real queries are not like this. The plan for a query that joins three tables, filters, groups, and sorts is a multi-node tree, and every node in that tree carries a decision. This lesson takes up reading that tree: what the nodes say, which table drives the others, and how sorting is reflected in the plan.

Data Set

Measurements are made on the library data set from the previous lesson. The following block sets up that data set from scratch; no other file is required.

rm -f library.db
cat > setup.sql <<'SQL'
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;
SQL
sqlite3 library.db < setup.sql

A Plan Is a Tree

A query asking who has borrowed a given author’s books touches three tables. Its plan is three lines too.

sqlite3 library.db <<'SQL'
CREATE INDEX loan_member ON loan(member_id);
CREATE INDEX loan_book   ON loan(book_id);
CREATE INDEX book_author ON book(author);
EXPLAIN QUERY PLAN
SELECT m.name, b.title, l.pickup_date
FROM loan l
JOIN member m ON m.member_id = l.member_id
JOIN book b   ON b.book_id   = l.book_id
WHERE b.author = 'Author 7';
SQL

QUERY PLAN
|--SEARCH b USING INDEX book_author (author=?)
|--SEARCH l USING INDEX loan_book (book_id=?)
`--SEARCH m USING INTEGER PRIMARY KEY (rowid=?)

Three lines are three table accesses, and their order carries meaning. The topmost node is the driving table: the database starts its work there. The nodes below it run once for each row coming from the driver. Here, the work starts from the book table, because that is where the only filter condition sits; author = 'Author 7' leaves fifty rows. For each of these fifty books, a book_id search is done inside loan, and for every loan record found, a single row is pulled from the member table by primary key.

In the query text, loan was written first. The plan paid no attention to this: the order in the FROM clause is not an execution order, it is a list of names. The planner decides the access order.

Scan and Search Nodes

The first distinction among plan nodes is whether the table is read from start to end or entered from a key.

SCAN says that every record in the table or index is read in sequence. SEARCH says that entry happens through a key and only the matching portion is read; the (member_id=?) in parentheses shows which condition was used as the key. A third distinction is the structure being searched itself: USING INTEGER PRIMARY KEY (rowid=?) is not a separate index but the table’s own primary key.

A fourth word says that the table was not touched at all.

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

QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)
QUERY PLAN
`--SEARCH loan USING INDEX loan_member (member_id=?)
17
VM-steps: 62
17
VM-steps: 97

Both queries use the same index, but the first one’s plan carries the word COVERING. A covering index is an index that holds every column the query asks for within itself: member_id is already in the index, no other column is needed for counting, so the table is never visited. The second query asks for the return_date column; since that column is not in the index, every matching index entry triggers a return to the table. For seventeen rows, the difference is thirty-five steps; this difference grows in direct proportion to the number of matching rows.

The Sort Node

Some nodes correspond not to a table but to an operation performed on data. Sorting is the most expensive of these.

sqlite3 library.db <<'SQL'
EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5;
.timer on
.stats vmstep
SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5;
.timer off
.stats off
CREATE INDEX loan_pickup ON loan(pickup_date);
EXPLAIN QUERY PLAN SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5;
.timer on
.stats vmstep
SELECT loan_id, pickup_date FROM loan ORDER BY pickup_date LIMIT 5;
SQL

QUERY PLAN
|--SCAN loan
`--USE TEMP B-TREE FOR ORDER BY
2437|2018-01-01
4874|2018-01-01
7311|2018-01-01
9748|2018-01-01
12185|2018-01-01
VM-steps: 12000130
Run Time: real 0.061 user 0.052669 sys 0.008248
QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_pickup
2437|2018-01-01
4874|2018-01-01
7311|2018-01-01
9748|2018-01-01
12185|2018-01-01
VM-steps: 32
Run Time: real 0.000 user 0.000015 sys 0.000015

The USE TEMP B-TREE FOR ORDER BY node says that sorting is done by building a temporary structure. Asking for only five rows does not make this cheaper: finding the five smallest dates requires seeing all two million rows, because the order is not known.

Once the index is created, the sort node disappears from the plan. The index is already sorted by date; the database reads five entries from the start and stops. Twelve million steps drop to thirty-two — this is the index’s second function: alongside making search cheaper, it offers a ready-made order. Time again falls below the measurement limit; what stays stable is not the time, which depends on the environment, but the direction of the ratios.

Column Order in a Composite Index

A composite index is an index defined over more than one column, and it sorts its entries by the first column first, and by the second column when the first is tied. Order is not a detail; it is the decision that determines what the index is good for. The following measurement runs the same query with two different column orders.

for order in "pickup_date, member_id" "member_id, pickup_date"; do
  rm -f order.db
  sqlite3 order.db < setup.sql
  sqlite3 order.db "CREATE INDEX loan_composite ON loan($order);"
  printf 'index: (%s)\n' "$order"
  sqlite3 order.db <<'SQL'
EXPLAIN QUERY PLAN
SELECT loan_id FROM loan WHERE member_id = 4242 ORDER BY pickup_date;
.stats vmstep
SELECT count(*) FROM
  (SELECT loan_id FROM loan WHERE member_id = 4242 ORDER BY pickup_date);
SQL
done

index: (pickup_date, member_id)
QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_composite
17
VM-steps: 6000101
index: (member_id, pickup_date)
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_composite (member_id=?)
17
VM-steps: 135

The two indexes contain the same two columns, take up the same space, and run the same query. The difference is forty-four thousand times. The reason is the sort order: if a phone book is sorted by surname, it cannot be searched by first name. In the (pickup_date, member_id) index, member_id values are spread across dates; finding one member requires reading the entire index — the plan says this by saying SCAN. In the (member_id, pickup_date) index, all of the same member’s records sit next to each other and are already in date order; the plan says SEARCH, and the sort node never appears.

The rule is this: columns filtered by equality go at the start of the index, and columns used for a range condition or for sorting come after them.

What Should Be Read Is the Decision, Not the Shape

The output here is the shape of a single engine. In other engines, the plan comes not as a tree but as an indented list, a table, or rows carrying an estimated row count and cost per node; node names change too — names like sequential scan, index scan, hash join are other names for the same concepts.

What does not change is the decisions read from the plan: was the table looked at from start to end or entered from a key, which table drove the others, was a return to the table required, and was a separate sort performed. Reading a plan’s output means extracting the answers to these four questions.

Summary

• A plan is a tree; the top node is the driving table, and the nodes below it run for every row coming from the driver. The order in the FROM clause does not determine execution order.
• SCAN shows reading from start to end, SEARCH shows entering from a key; the condition in parentheses says which column was used as the key.
• The word COVERING reports that the query was answered from the index alone, with no return to the table at all.
• The sort node is a separate cost; a suitable index removed sorting from the plan entirely, and the same query dropped from 12,000,130 steps to 32.
• Column order in a composite index determines which query the index is good for; reversing the order of the same two columns pushed the same query from 135 steps up to 6,000,101.

Next Step

In every measurement in this lesson, an index existed and was used. The situation commonly seen in practice is different: an index exists, the query filters on that column, and the plan still says SCAN. The next lesson takes up this situation — how a function applied to the column, a left-open pattern match, or a type mismatch disables the index, and which equivalent rewrite brings the index back.