Lesson browser Query optimizers lessons Previous: How estimates shape a plan Next: How indexes change the options

SQLite · Lesson 3

How joins are chosen

SQLite joins tables through nested loops. SQLite chooses which input comes first and how to find matches for each outer row.

Read loop order and statistics first. This lesson focuses on ordinary inner joins, not every subquery or compound-query optimization.

Repeat the inner lookup for each outer row

SELECT c.id, o.id
FROM customers c JOIN orders o ON o.customer_id = c.id
WHERE c.id <= 5;

-- One possible plan:
|--SEARCH c USING INTEGER PRIMARY KEY (rowid<?)
`--SEARCH o USING COVERING INDEX orders_customer_idx (customer_id=?)

The first access supplies customers. Each customer triggers an order lookup. If five customers each have two orders, there are five lookups and ten output pairs. A customer with no matching order contributes no result row to this inner join.

Without a useful index, the inner access may be a repeated full scan. Five scans of 2,000 orders can involve about 10,000 row checks. This count comes from the example data, not from EXPLAIN QUERY PLAN, or EQP.

Build a temporary lookup structure

SQLite may build an automatic index for a query if it expects the savings on repeated lookups to exceed the build cost. The structure is a temporary B-tree, not a permanent schema change. A plan may say USING AUTOMATIC COVERING INDEX, with wording varying by version.

Compare repeated scanning with a temporary index

There are six orders, two per customer. Without an index, the inner loop scans all six orders for each customer. With a temporary index, SQLite first stores the six orders in a B-tree, then looks up each customer's orders.

Customers to join 2

Changing the count resets both methods.

Nested loop

0 / 12 actions completed

0 joined rows

Ready to start.

Temporary index

0 / 8 actions completed

0 joined rows

Ready to start.

Speed Step 0 / 12

Each action represents one comparison, index insertion, or lookup. These have different costs, so fewer actions do not necessarily mean a faster query. Both methods use nested loops. Building or searching a B-tree takes several lower-level operations; the displayed counts are not SQLite virtual-machine step counts. A permanent index avoids rebuilding the lookup structure for each execution.

Building an automatic index has a cost too. For a query that runs often, a suitable permanent index can avoid that repeated build. For a one-off query, accepting a temporary index may be reasonable. Before adding a permanent index, check how often the query runs and how much work the index adds to writes.

Count what the join produces

Distinguish lookup attempts from matching pairs

An inner join produces a row for each pair that satisfies its conditions. It does not necessarily produce one row per customer. Consider three customers named A, B, and C, with zero, two, and five matching orders. A contributes no pair, B contributes two, and C contributes five. The result has seven pairs even though the outer input contains three customers.

With customers outside and orders inside, the execution needs an order lookup for each of the three customers. The lookup for A finds nothing. The other two find different numbers of entries. Three lookup attempts therefore produce seven matches. Do not multiply three by seven, because seven is already the total across customers, not a per-customer count. If you use an average, state that its denominator is the three qualifying outer customers.

Without an index, a simple full inner scan can compare each outer customer against every order. If the orders table contains two thousand records, three complete scans inspect six thousand order candidates in this model. Only seven become result pairs. The equality join condition discards the rest. A low result count does not prevent a high number of unsuccessful comparisons.

An indexed inner access can find the relevant customer group instead of repeating all two thousand candidates. It still performs a lookup for the empty group, reads the matching entries for B and C, and may retrieve table records for missing selected values. Index lookup cost is not zero. The benefit is avoiding irrelevant candidates, not avoiding the necessary output pairs.

In the join demonstration, distinguish the temporary-index construction from the later searches. Before playback, predict whether changing the number of outer rows should multiply the build work or the lookup work. The temporary structure is built for the statement and then reused during its inner lookups. More outer rows create more lookup opportunities, which can make the initial build worthwhile. They do not require building a fresh index for every customer in this example.

Now change the requirement to ask only whether each customer has any matching order. That is a different question from returning every customer/order pair. An existence test can stop after finding a qualifying match for a customer, whereas a pair-producing join must enumerate all the matches requested. Do not rewrite a report join as an existence check unless the caller needs only existence. The apparent speedup might otherwise come entirely from discarding valid result rows.

Finally, inspect which columns come from each input. Requesting an order amount absent from the lookup index can require table access even though the join key is indexed. The explanation of repeated work must include both how matches are located and how the output values are obtained. Join performance is not determined by counting indexes in the schema.

Filter early to reduce later lookups

SELECT c.id, o.id, i.product_id
FROM customers c
JOIN orders o ON o.customer_id = c.id
JOIN order_items i ON i.order_id = o.id
WHERE c.country = 'IS';

Suppose one million customers have ten million orders and thirty million order items. Only 100 customers match this filter, with 1,000 orders and 3,000 items.

Filter customers before looking up orders and items

● Input▧ Work✓ Match× Rejected◆ Result

This smaller example has three customers, two orders each, and two items per order. Only C1 passes the country filter.

Filter customers first

C1 ✓C2 ×C3 ×

C1 · I1C1 · I2C1 · I3C1 · I4————————

4 item pairs reached

◆ I1 ◆ I2 ◆ I3 ◆ I4

Join items before filtering

C1 ✓C2 C3

C1 · I1C1 · I2C1 · I3C1 · I4C2 · I5C2 · I6C2 · I7C2 · I8C3 · I9C3 · I10C3 · I11C3 · I12

12 item pairs reached; reject 8

◆ I1 ◆ I2 ◆ I3 ◆ I4

Both routes return the same four items. The left route skips the other customers' orders and items only if it has indexes to look up the matches. Empty slots mark items this route does not read. This is a row-count model, not memory usage or timing.

Starting with the 100 matching customers helps only if SQLite can look up their orders and items cheaply. Without suitable indexes, those lookups may become repeated scans of large tables.

SQLite can reorder ordinary inner joins. The table written first in SQL is not necessarily the outer loop. Read the order of the SCAN and SEARCH entries instead. Outer joins have restrictions because unmatched rows must be preserved; moving a condition between ON and WHERE can change the result.

Follow the intermediate rows through a longer join

A useful outer input is often the one that leaves a small, cheaply obtained set after filtering. That is different from the smallest table before filtering. A million-row customer table with an indexed condition matching one hundred rows can supply a smaller outer input than a ten-thousand-row table with no useful filter. The underlying table size still affects access cost, but it is not enough to choose an order by itself.

For the customer, order, and item example, write down the intermediate populations. The country filter supplies one hundred customers. Their orders supply one thousand customer/order pairs. Those orders then supply three thousand customer/order/item combinations. The item lookup is repeated for the relevant orders, not just once per original customer. Ignoring the intermediate pairs misses where later repetition comes from.

Compare that with an orders-first route that examines ten million orders and looks up a customer for each before applying the country restriction. In this stipulated scenario, most customer lookups do not lead to a qualifying order. Starting with the filtered customers avoids that irrelevant population if suitable order and item indexes exist. This is a mechanism-based prediction, not a claim that every real database must choose this exact plan.

Now remove the order lookup index while leaving the country index in place. Starting with only one hundred customers can still cause repeated scans of the ten-million-row orders table. A very selective first step cannot compensate automatically for an expensive repeated inner access. SQLite may consider another order or a temporary index. The question is the cost of the whole route, including preparation and subsequent lookups.

Many-to-many joins can expand intermediate rows even when every lookup uses an index. If a product has four qualifying tags and five qualifying suppliers, combining both independent lists for that product can produce twenty tag/supplier pairs. That multiplication can be required by the SQL. An index improves finding each list; it does not remove the twenty valid combinations. Check whether the intended report really asks for all combinations before trying to optimize that output away.

Use the join-order diagram to identify the population handed to each next access. Then change one assumption mentally: suppose the country matches almost every customer. The selective-start advantage shrinks. Or suppose each qualifying customer has far more orders than average. The later populations grow. A proposed loop order should be tested against these workload differences rather than justified by a slogan such as "filter first" without examining the actual access costs.

For ordinary inner joins, SQLite can explore alternative orders while preserving the result. The text order of tables is therefore a poor description of execution. Read the plan's nesting and connect each lookup value to the row that supplies it. This skill transfers to a new schema even when the table names and number of stages change.

Read a different order

|--SEARCH o USING COVERING INDEX orders_customer_idx (customer_id<?)
`--SEARCH c USING INTEGER PRIMARY KEY (rowid=?)

This plan begins with orders and looks up each order's customer. The equality join tells SQLite that both customer IDs must match. SQLite can sometimes use a bound on one to narrow the search on the other. Do not assume that reversing two table names in the SQL forces a different execution plan.

Test one explanation at a time

If the inner access is a SCAN, ask whether a useful index exists on its join key. If it is a SEARCH, ask how many entries match each outer row and whether additional conditions still discard many candidates.

SQLite's ordinary plan output supplies neither actual loop counts nor elapsed times. The shell's optional .scanstats on requires a build with statement scan-status support. If your shell reports that it is unavailable, use separate counts and repeated timings. These will not give you per-loop measurements.

Hold the join order fixed for a test

PRAGMA automatic_index = OFF;
EXPLAIN QUERY PLAN
SELECT c.id, o.id
FROM customers c CROSS JOIN orders o
WHERE o.customer_id = c.id AND c.id <= 5;
PRAGMA automatic_index = ON;

For this SQLite experiment, CROSS JOIN prevents reordering of these tables, and disabling automatic indexes exposes the repeated full scan when no permanent lookup index exists. This is a diagnostic setup, not a recommendation for normal queries. The equality in WHERE still selects matching pairs.

The downloadable experiment repeats the constrained query after adding an orders(customer_id) index. With the loop order fixed, you can compare the inner scan with an indexed lookup. It then re-enables automatic indexes and shows a normal JOIN where SQLite can choose the loop order. Changing a connection setting in an application requires recording and restoring its previous value rather than assuming the default.

Keep the required rows

Preserve unmatched rows and isolate a join experiment

An outer join changes which rows must survive. Suppose customer A has no orders and customer B has one pending order. An inner join returns B's customer/order pair and no row for A. A left join that preserves customers also returns A, with missing order values represented by NULL. That unmatched row is part of the requirement, not wasted work that can be discarded to make a plan faster.

A pending-status condition in the ON clause of that left join restricts which orders count as matches while still preserving customers with no pending match. Put the condition in WHERE instead, and rows whose order status is NULL fail the ordinary equality test. The unmatched customer disappears. This explains why moving conditions around an outer join can change results even when a similar move is harmless for a simple inner join.

When checking a join rewrite, include a customer with no order, one with several orders, and one whose orders all fail the extra condition. A test containing only customers with one qualifying order cannot reveal either duplicate handling or unmatched-row mistakes. Compare complete result rows, including NULL values and multiplicities. Matching only the number of returned rows is not enough to establish equivalence.

The CROSS JOIN experiment deliberately restricts the planner's freedom so that you can study one inner access. With customer order fixed and automatic indexes disabled, adding a permanent order-key index changes the available inner route. That setup helps isolate a mechanism. It is not evidence that forcing the same order in the application will outperform the planner on other customer selections.

Restore connection settings after the experiment. In an existing application, first record their original values instead of assuming automatic indexes were initially enabled. Connection-local changes can affect later statements on the same connection. A test that accidentally leaves a restriction in place can create the very performance problem you were trying to diagnose. Use a disposable database and connection when possible.

An automatic index is evidence that SQLite found a potential benefit in constructing a temporary lookup for this statement. It is a reason to investigate, not a universal command to create a permanent index. A query executed once may not justify ongoing write maintenance. A query executed thousands of times may repeatedly pay construction cost. Compare those uses with actual execution frequency and the changes imposed on inserts, deletes, and relevant updates.

After you remove the diagnostic restrictions, capture the ordinary JOIN plan again. If its loop order differs from the controlled example, interpret that new plan on its own terms. Report separately what the controlled test demonstrated and what the unrestricted workload measured. A conclusion about one inner lookup does not automatically establish the best complete join strategy.

Exercises

Find the repeated access

|--SEARCH c USING INTEGER PRIMARY KEY (rowid<?)
`--SCAN o

Which input repeats? If 5 customers qualify and each causes a full scan of 2,000 orders, how many order rows does SQLite check?

Hint

The first table access is the outer loop.

Worked answer

Scan the same 2,000 orders five times

● Input▧ Work✓ Match× Rejected◆ Result

2,000 rows

0 completed scans × 2,000 = 0 row checks

Speed Step 0 / 5

Every sweep crosses the same 2,000 orders again. Each segment represents 200 row checks. Five complete scans check 5 × 2,000 = 10,000 order rows. Animation duration does not represent query time.

The customers search is outer. The orders scan is repeated for qualifying customers. With 5 customers and a complete 2,000-row inner scan each time, the model checks 10,000 order rows. EQP alone does not tell us those data counts or the elapsed time.

An automatic index appears

A plan includes USING AUTOMATIC COVERING INDEX. What does it mean, and what could you investigate if this query runs thousands of times?

Hint

Does an automatic index remain available after the statement finishes?

Worked answer

An automatic index is rebuilt for each execution

● Input▧ Work✓ Match× Rejected◆ Result

Automatic query-time index

Run 1▧ Build✓ Lookups

Run 2▧ Build✓ Lookups

Run 3▧ Build✓ Lookups

Permanent index

⌘ Index built beforehand

Run 1✓ Reuse index

Run 2✓ Reuse index

Run 3✓ Reuse index

The segments show work, not elapsed time. Each execution shown here builds its own automatic B-tree index. A permanent index remains available between executions but takes storage and adds work to writes.

SQLite decided to build a temporary lookup structure for this execution. Check whether a permanent index on the lookup columns helps a frequently repeated query, but include its storage and write cost. The automatic index does not remain in the schema after the statement finishes.

Should the smallest table always come first?

A colleague proposes forcing the smallest underlying table to be the outer loop for every join. Is that a sound rule?

Hint

How many rows remain after filtering? What does each inner lookup cost?

Worked answer

Compare row counts after filtering

● Input▧ Work✓ Match× Rejected◆ Result

Small table · 1,000 rows

1,000 expensive inner scans

Large table · 1,000,000 rows

5 cheap inner lookups

This invented example shows why table size alone is not enough. Funnel areas are not proportional to row counts. Compare the rows left after filtering and the cost of each inner lookup.

No. Count the rows left after filtering, and check how SQLite will find their matches in the next table. A large table narrowed to a few indexed entries may be a better outer input than a smaller table that forces expensive repeated scans. Test with representative data rather than forcing an order based only on table size.

Experiment and sources

Use a new file: sqlite3 joins.db < joins.sql. Download the join experiment. It compares a repeated scan with an indexed lookup, then lets SQLite choose the loop order again.

Next: design the keys that make those lookups useful.

Lesson browser Query optimizers lessons Previous: How estimates shape a plan Next: How indexes change the options