Syntax That Prevents Index Usage

In the previous two lessons, an index existed and was used. The situation commonly seen in practice is the reverse: an index exists, the query filters exactly on that column, the plan still says SCAN, and time does not drop.

The reason for this usually lies not in the index or the data, but in how the condition is written. An index keeps a given column’s values sorted in the form they are stored. When the condition asks not for that value itself but for another value computed from it, the index becomes useless. This lesson takes up these forms of writing and the equivalents that give the same result.

Data Set

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 Function Applied to the Column

Two columns carry an index. The same two questions are asked, one applying a function to the column, the other without.

sqlite3 library.db <<'SQL'
CREATE INDEX book_author ON book(author);
CREATE INDEX loan_member ON loan(member_id);
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7';
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE author = 'Author 7';
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id + 0 = 4242;
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE member_id = 4242;
.timer on
.stats vmstep
SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7';
SELECT count(*) FROM book WHERE author = 'Author 7';
SELECT count(*) FROM loan WHERE member_id + 0 = 4242;
SELECT count(*) FROM loan WHERE member_id = 4242;
SQL

QUERY PLAN
`--SCAN book USING COVERING INDEX book_author
QUERY PLAN
`--SEARCH book USING COVERING INDEX book_author (author=?)
QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_member
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_member (member_id=?)
50
VM-steps: 800061
Run Time: real 0.012 user 0.011517 sys 0.000696
50
VM-steps: 161
Run Time: real 0.000 user 0.000011 sys 0.000007
17
VM-steps: 8000029
Run Time: real 0.029 user 0.026113 sys 0.002210
17
VM-steps: 62
Run Time: real 0.000 user 0.000017 sys 0.000013

Two of the four plans are SCAN, two are SEARCH. The results are the same: fifty and seventeen. The step counts are 800,061 against 161, and 8,000,029 against 62, respectively.

The reason can be said in one sentence: the index keeps author values sorted, not upper(author) values. Since the database has no sorted structure for upper(author), it has to compute the function separately for every row and compare the result. The same holds for arithmetic: member_id + 0 is not an index key. Even though + 0 looks like it changes nothing, it is enough to disable the index.

The Date Form of the Same Mistake

The most common form of this mistake is date filtering: when a year’s records are requested, extracting the year from the date looks natural.

sqlite3 library.db <<'SQL'
CREATE INDEX loan_pickup ON loan(pickup_date);
EXPLAIN QUERY PLAN SELECT count(*) FROM loan WHERE strftime('%Y', pickup_date) = '2019';
EXPLAIN QUERY PLAN
SELECT count(*) FROM loan
WHERE pickup_date >= '2019-01-01' AND pickup_date < '2020-01-01';
.timer on
.stats vmstep
SELECT count(*) FROM loan WHERE strftime('%Y', pickup_date) = '2019';
SELECT count(*) FROM loan
WHERE pickup_date >= '2019-01-01' AND pickup_date < '2020-01-01';
SQL

QUERY PLAN
`--SCAN loan USING COVERING INDEX loan_pickup
QUERY PLAN
`--SEARCH loan USING COVERING INDEX loan_pickup (pickup_date>? AND pickup_date<?)
299551
VM-steps: 8299563
Run Time: real 0.209 user 0.204322 sys 0.004516
299551
VM-steps: 898666
Run Time: real 0.005 user 0.004278 sys 0.000684

Both queries return 299,551: the rewrite is equivalent. Step count dropped ninefold, and time dropped by more than forty times in this environment.

The logic of the rewrite is this: a year’s records form an unbroken range in a sorted date index. The range is written with the lower end closed and the upper end open — the form < '2020-01-01', unlike <= '2019-12-31', correctly covers values that also carry time-of-day information. The same conversion can be built for month, week, and day filters; in every case, the function moves to the right side of the condition, into the constant values.

The Left End in Pattern Matching

In a sorted structure, a search can be done by prefix, not by suffix.

sqlite3 library.db <<'SQL'
CREATE INDEX book_title ON book(title);
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE title LIKE 'Book 1234%';
CREATE INDEX book_title_nc ON book(title COLLATE NOCASE);
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE title LIKE 'Book 1234%';
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE title LIKE '%1234';
.timer on
.stats vmstep
SELECT count(*) FROM book WHERE title LIKE 'Book 1234%';
SELECT count(*) FROM book WHERE title LIKE '%1234';
SQL

QUERY PLAN
`--SCAN book USING COVERING INDEX book_title
QUERY PLAN
`--SEARCH book USING COVERING INDEX book_title_nc (title>? AND title<?)
QUERY PLAN
`--SCAN book USING COVERING INDEX book_title_nc
111
VM-steps: 463
Run Time: real 0.000 user 0.000016 sys 0.000013
20
VM-steps: 800031
Run Time: real 0.006 user 0.006109 sys 0.000031

The output says two separate things. First: the LIKE '%1234' condition is met with a scan no matter what index exists. A left-open pattern cannot take advantage of sort order; the only way to find words that “end with” something in a dictionary is to read the dictionary from start to end. In this case, the solution is not to rewrite the query but to change the structure — a full-text index, or a prefix search over a reversed copy of the column.

The second is subtler: the prefix pattern did not work with the first index either, but it did work with the second index, defined with COLLATE NOCASE. The reason is a mismatch in collation. In this engine, LIKE is case-insensitive by default, while the first index is sorted with a case-sensitive comparison; because the two sort orders are not the same, the index cannot be used. The rule is engine-independent: the index’s sort rule and the condition’s comparison rule must be the same. Letter case, locale-sensitive sorting, and whitespace behavior all fall under this rule.

When the Function Cannot Be Given Up

In some cases, the computed value itself has to be searched for. The answer to this is not to remove the computation from the query but to put it into the index: an expression index keeps not a column’s values sorted, but the values of an expression computed from that column.

sqlite3 library.db <<'SQL'
CREATE INDEX book_author_upper ON book(upper(author));
EXPLAIN QUERY PLAN SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7';
.timer on
.stats vmstep
SELECT count(*) FROM book WHERE upper(author) = 'AUTHOR 7';
SQL

QUERY PLAN
`--SEARCH book USING COVERING INDEX book_author_upper (<expr>=?)
50
VM-steps: 212
Run Time: real 0.000 user 0.000015 sys 0.000011

The same query, unchanged, dropped from 800,061 steps to 212. The plan showing <expr> in place of a key column name indicates that the index is keyed not on a column but on an expression.

An expression index has two conditions. The expression must be deterministic: it must always produce the same value for the same row; an expression that reads the current time or a session setting cannot be indexed, because the value in the index goes stale the moment it is written. Second, the expression in the query must match the expression in the index; an upper(author) index is no use for a lower(author) condition.

The General Shape of the Rule

This lesson examined four separate forms of writing; all of them reduce to a single rule. For a condition to take advantage of an index, the indexed column must sit on one side of the comparison with no computation applied to it. In the literature, conditions of this shape are called a sargable predicate.

In practice, this means bringing the condition into one of three forms: comparing the column against a constant, putting the column into a range, or moving the computation into the index’s definition. The computation does not have to disappear from the query entirely — it can stay on the right side of the condition, over constant values. The condition pickup_date >= date('2019-01-01', '-7 days') uses the index, because the computation is done once at the start of the query and its result is a constant value.

Summary

• An index keeps a column’s values sorted in the form they are stored; any function or arithmetic applied to the column makes that order unusable, and the plan becomes SCAN.
• A strftime condition asking for a year’s records, once converted into an equivalent half-open range condition, spent nine times fewer steps and forty times less time in this environment.
• A left-open pattern match cannot take advantage of any sorted index; the solution is not to rewrite the query but to build a different index structure.
• The index’s sort rule and the condition’s comparison rule must be the same; a difference in letter case alone can disable the index.
• If a computed value must be searched for, an expression index is used; the expression must be deterministic and must match its form in the query exactly.

Next Step

All the measurements up to this point were on a single table, and the decision was a single one: index or scan. When more than one table is joined, the number of decisions grows — which table to read first, which access path to use at each step, and which method to use to match rows are chosen separately. The next lesson takes up the plan’s counterpart to join order and join algorithm, and their measured effect.