Query optimizers / personal lessonsLesson 4 of 5
SQLite · Lesson 4

How indexes change the options

An index can narrow a search, supply an order, and contain the values a query needs. The order of its keys determines which searches and sorts it can support.

You need SEARCH, SCAN, and covering access from lesson 1. Examples use ordinary rowid tables with id INTEGER PRIMARY KEY. WITHOUT ROWID tables organize their keys differently.

A composite index has a specific order

CREATE INDEX orders_customer_date_idx
ON orders (customer_id, created_at);

This index groups entries by customer, then sorts each group by date. It is not one global date order.

SELECT id, total FROM orders
WHERE customer_id = 42 AND created_at >= '2025-01-01';

Find the range in (customer_id, created_at)

Read down each customer's group, then move to the next customer. These nine entries show the order of keys at the leaf level of a small B-tree.

Condition: customer_id = 42 AND created_at >= Jan 2 (illustrative dates)

Customer 7

Jan 1Outside range
Jan 2Outside range
Jan 3Outside range

Customer 42

Jan 1Outside range
Jan 2✓ Match
Jan 3✓ Match

Customer 90

Jan 1Outside range
Jan 2Outside range
Jan 3Outside range

2 entries in the illustrated range · 2 matches

The customer equality selects one group. The date bound selects entries from Jan 2 onward within it. The picture shows key order and matching ranges. It does not trace page reads or predict whether SQLite will scan the full index, use a skip-scan, or choose another path. A later-key condition can still reject entries inside the index without fetching their table rows.

Equality before a range

An equality condition on the first key picks one customer's group. A range on the next key narrows the search within that group. The plan can show both bounds:

SEARCH orders USING INDEX orders_customer_date_idx
  (customer_id=? AND created_at>?)

The exact comparison spelling in EQP is an implementation detail. It shows that both columns narrow the search. It is not a literal rewrite of the SQL condition.

With no restriction on the leading key, a date predicate does not identify one small contiguous range. SQLite may use a skip-scan. It visits each distinct value of the first key and searches the later key within that group. This depends on statistics and whether the planner expects enough duplicates to make it worthwhile. A date-first index may work better for queries that search date ranges across all customers.

Putting the most selective column first is not a general rule. When both leading keys have equality conditions, either order may locate the pair. Choose an order that also supports the ranges, sorting, and other queries you need.

Predict which keys narrow the search

Explain the key interval before naming an index

Imagine the index entries written in customer order, with each customer's dates ordered inside that group. An equality on customer 42 locates one group. A lower date bound then selects a suffix within that group. The useful property is that the matching entries occupy a bounded interval of this ordered structure. SQLite can seek to its beginning rather than testing every other customer's records.

Change the query to customer_id greater than or equal to 42 and a recent-date condition. It now spans several customer groups. Each group contains old and recent dates, so the recent entries do not form one uninterrupted interval across all those customers. A range on an earlier key generally limits how much a later key can narrow one contiguous search. The later condition may still be checked, and more elaborate optimizations are possible, but merely listing both columns in an index does not make every combination equally efficient.

Compare this with two equality conditions, such as tenant_id and status, followed by a date range. Fixing both equalities can identify a single tenant/status group before traversing its dates. For that query, either equality key order may help locate the group. Other queries then matter: a tenant-only lookup can use a tenant-leading prefix, while a status-only lookup needs different consideration. Choose the index using a set of query requirements, not just one column's global rarity.

Use the range diagram to point to the first and last relevant entries. If you cannot describe one interval, explain which separate groups would have to be visited. That exercise makes the skip-scan possibility understandable without assuming that SQLite always chooses it. Repeating a later-key search for each leading-key value is worthwhile only under suitable costs and distributions.

This reasoning also distinguishes filtering from ordering. An index can organize candidates usefully even when it does not provide the final global order. A customer/date index is grouped by customer. Asking for the newest orders across all customers requires a date-first order or additional sorting work. The absence of one access capability does not make the index useless for every other query.

One index can filter and order

SELECT id, created_at, total FROM orders
WHERE customer_id = 42
ORDER BY created_at DESC LIMIT 20;

The customer/date index can find customer 42, walk that group's dates backward, and stop after the needed rows. It may avoid a separate temporary sorting B-tree.

A date-only index can also supply newest-first order, but SQLite may pass many other customers' entries before finding 20 matches. Ordinary EQP does not print how many were rejected. The animation shows these rejected entries with a small invented dataset.

Find a customer's two newest orders

The left index orders all customers' entries by date. The right index groups entries by customer, then date. Both return the same orders.

Changing the customer resets both scans.

Date index

  • #6 · C3 · Jan 6
  • #5 · C2 · Jan 5
  • #4 · C1 · Jan 4
  • #3 · C3 · Jan 3
  • #2 · C2 · Jan 2
  • #1 · C1 · Jan 1

0 entries read
0 returned

Customer, date index

  • #4 · C1 · Jan 4
  • #1 · C1 · Jan 1

0 entries read
0 returned

Step 0 / 6

The date index reads 6 entries before it has two matches. The composite index locates this customer's range, then reads its two entries. The diagram omits the initial tree search and any table-page fetches. A check marks a returned row; a cross marks a row discarded by the customer filter.

If timestamps tie and the application needs stable ordering, specify a tie-breaker such as ORDER BY created_at DESC, id DESC in both versions of a comparison. Check that the index supports the full requested order. Without a tie-breaker, rows with the same timestamp can appear in either order.

Across multiple customers, a (customer_id, created_at) index still does not provide global date order. Also, reversing an all-ascending multicolumn index reverses every key direction; it does not produce customer ascending and date descending simultaneously. Mixed-direction indexes can support that requirement.

Check what happens before the twentieth accepted row

Suppose a date-only index begins with two hundred recent orders from other customers before the first order for customer 42. It provides the requested date order, but that order does not isolate customer 42. SQLite must reject the unrelated entries as it traverses them. If the customer has fewer than twenty orders, the scan may have to exhaust the relevant route before it can establish that there are no more matches.

The customer/date index changes the starting population. It locates customer 42's group and reads that group's dates backward. Unrelated customers no longer lie between the matching entries. Before changing the visualizer, predict which entries disappear from the candidate route and which result rows remain. The optimization concerns rejected candidates, so returning the same newest rows is part of the prediction.

A remaining status condition can make the story less simple. If the query asks for the newest twenty pending orders, a customer/date route may pass many completed orders inside the customer's group. Adding status to an appropriate equality prefix, or using a suitable partial index, might help this particular requirement. Neither choice follows automatically from the presence of LIMIT. State the filter and ordering requirements together before designing the keys.

Ties also belong to the requirement. If several orders share the boundary timestamp, a query ordered only by timestamp permits more than one valid selection among those tied rows. Different access routes can expose that freedom. Add an explicit tie-breaker when stable pagination or repeatable comparison requires it. In these rowid-table examples, id supplies a unique tie-breaker, but check that the chosen index supports its position and direction in the requested ordering.

Finally, do not compare a query that reads twenty rows with another that reads every order and discards all but twenty in application code unless you explicitly intend to change that interface. Moving a legitimate limit into SQL can avoid unnecessary work, but the caller must not need the omitted rows for totals, exports, or later processing. Correctness defines which reductions in work are allowed.

Separate indexes are not one composite index

For AND-connected conditions on a table, SQLite generally chooses one index for that table access rather than intersecting two single-column indexes. OR optimization is a different case. A customer/date index can both narrow the search by customer and supply date order. Separate customer and date indexes do not combine to do this.

Cover the requested values

CREATE INDEX orders_cover_idx
ON orders (customer_id, created_at, total);

SQLite has no INCLUDE clause. To carry total in this index, put it in the key list. Because it follows customer and date, it does not disrupt their ordering. It also makes entries larger.

Where do the selected values come from?

● Input▧ Work✓ Match× Rejected◆ Result

This query selects id, created_at, and total for customer 42. The table declares id INTEGER PRIMARY KEY.

One covering index entry · customer 42
customer_id42created_atJan 6total750rowid = id104
id104created_atJan 6total750

◆ The index contains all three requested values.

Table rows not fetched
Without total in this index, SQLite must look up the table row to obtain it. With total present, SQLite can report USING COVERING INDEX. The id comes from rowid, already carried by a secondary index in this schema. Wider entries use more storage and add work to writes.

In these rowid-table examples, id is an INTEGER PRIMARY KEY alias for rowid. Secondary indexes already carry rowid, so selecting id does not require adding another id key merely for coverage. Do not generalize that detail to every primary-key declaration or to WITHOUT ROWID tables.

Index only a useful subset

CREATE INDEX pending_orders_date_idx
ON orders(created_at)
WHERE status = 'pending';

This partial index stores pending rows only. A query can use this index only if SQLite can prove that every row it needs is pending. An explicit pending-status condition makes this possible. SQLite uses limited rules to check the condition, so a logically equivalent expression or an unknown parameter value may prevent use of the index.

Index an expression

CREATE INDEX customers_lower_email_idx
ON customers(lower(email));

SELECT id FROM customers WHERE lower(email) = '[email protected]';

The indexed expression must match the query expression closely; SQLite does not generally infer algebraic equivalence. Functions in the index must be deterministic, meaning they return the same result for the same inputs. The text comparison rules, called collation, also matter. SQLite's built-in lower() handles ASCII letters by default, not full Unicode case folding. Check whether that matches your application's email rules.

Predict a plan change, then measure

Before creating an index, state what it should remove: a full scan, checks of unrelated candidates, table lookups, or a temporary sort. Compare EXPLAIN QUERY PLAN before and after, then time the actual query with the same data and values.

Indexes take disk space and add work to inserts and relevant updates. Building an index writes to the database and can block other work. Test on a copy before building it in production. Run PRAGMA optimize after schema changes according to the maintenance guidance.

A covering scan can be a good plan even when it says SCAN. A SEARCH that finds most of the table may still be expensive. Check the returned rows and timings rather than judging the label alone.

Compare read and write requirements

Evaluate an index as part of a workload

Coverage is a tradeoff between read work and stored information. Adding total to the customer/date index makes the entries wider but can avoid table lookups for the illustrated query. Add a large notes field as well, and the storage increase may be substantial. More data in each entry can mean more pages and more cache pressure. Do not cover every selected column by default; measure whether the saved lookups justify the wider structure for the important queries.

Write costs depend on what changes. Inserting an order must maintain indexes that include that row. Changing a value used in an index key can require updating that index. A partial index also depends on whether the row satisfies its predicate. An order moving from pending to completed leaves a pending-only index. That smaller index can save work for pending-order queries, but it is still a maintained structure rather than a free cached answer.

A partial index must contain every row the query might need. An index restricted to pending orders cannot answer an unrestricted query for all orders by itself. The question is logical coverage of the required rows, followed by whether SQLite recognizes the implication. A mathematically equivalent reformulation may not match the planner's limited proof rules. Test the actual application statement rather than a simpler literal example that happens to use the index.

Expression indexes impose another matching requirement. If the indexed expression is x+y, do not assume a query written as y+x will use it merely because addition is commutative in the intended domain. SQLite requires a close expression match. Application functions must also obey the determinism promise used by the index. An index that records function results relies on those results remaining valid for the same inputs.

When evaluating a proposed index, list the reads it should improve and the writes it will affect. Keep older indexes until you understand the other queries they serve. The global date index may still be useful for a cross-customer report even after the customer/date index improves an individual customer's screen. Compare storage, representative read timings, and relevant write timings on a test copy. One faster SELECT does not establish that the overall workload improved.

Exercises

Choose an index for one tenant's newest events

SELECT id, created_at FROM events
WHERE tenant_id = 7
ORDER BY created_at DESC LIMIT 50;

Which key order would you test, and what plan change do you predict?

Hint

Fix the tenant first, then consider the date order inside that group.

Worked answer

Search only tenant 7's entries

● Input▧ Work✓ Match× Rejected◆ Result
Tenant 3
JAN6—
JAN5—
JAN4—
JAN3—
Not searched
Tenant 7
JAN6✓
JAN5✓
JAN4✓
JAN3✓
↓ Newest first · stop at 50
Tenant 9
JAN6—
JAN5—
JAN4—
JAN3—
Not searched
A small excerpt from a (tenant_id, created_at) index. Reading the selected group backward gives the newest dates first. Stop after 50 qualifying events, or at the end of the group if there are fewer. Other tenants lie outside this bounded search.

Test (tenant_id, created_at). Look for a SEARCH bounded by tenant_id and no separate temporary B-tree for the requested date order. Check timings and the returned rows too. This index may suit the query without being the best choice for other queries.

Recognize covering access

Given id INTEGER PRIMARY KEY and an index on (customer_id, created_at, total), why might selecting id, created_at, and total need no table-row fetch?

Hint

Where can SQLite get total and id?

Worked answer

Get all requested values from the index

● Input▧ Work✓ Match× Rejected◆ Result
One covering index entry · customer 42
customer_id42created_atJan 6total750rowid = id104
id104created_atJan 6total750

◆ The index contains all three requested values.

Table rows not fetched
The values shown are illustrative. For id INTEGER PRIMARY KEY in an ordinary rowid table, id comes from the rowid already carried in the secondary index. Adding total makes the index larger and adds work to writes.

The index contains total, while id aliases rowid and is already carried by a secondary index in this ordinary rowid table. SQLite can report USING COVERING INDEX and avoid separate table-row lookups for these values. This depends on the stated schema and selected columns.

A date-only index still does too much work

The newest-20 query for a rare customer uses SCAN orders USING INDEX orders_date_idx and is slow. What would you test?

Hint

Are the entries grouped by customer or only sorted by date?

Worked answer

Same result, fewer irrelevant entries

● Input▧ Work✓ Match× Rejected◆ Result
Date index: check all 6
  1. #6C3×
  2. #5C2×
  3. #4C1✓
  4. #3C3×
  5. #2C2×
  6. #1C1✓

◆ Same result: orders #4 and #1

Customer/date: read 2
  1. #4C1✓
  2. #1C1✓

◆ Same result: orders #4 and #1

This smaller example finds customer 1's two newest orders rather than 20. The customer/date index groups this customer's entries together. The date-only index reads other customers' entries before finding both matches.

The index supplies date order but does not isolate a customer. Test a customer/date index for this workload. Expect a SEARCH bounded by customer_id that still supplies date order. EQP does not count rejected candidates, so time the query to check whether the change helped.

Experiment and sources

Run sqlite3 indexes.db < indexes.sql against a new file. The experiment compares a date index, a customer/date index, and a covering variant.