Inside SQLite’s Frontend: Join Table Ordering

Source: Dev.to

Overview

Even if your WHERE clause is perfectly optimized, a bad join order can still make a query slow. SQLite uses a simple but effective strategy for joins: it always executes them as nested loops. The order of tables in the FROM clause determines how these loops are nested.

Join Execution Model

For a query like:

SELECT * FROM A JOIN B;

SQLite processes it roughly as:

for each row in A:          # outer loop
    for each row in B:      # inner loop
        process the combination

• First table → outer loop
• Last table → inner loop

The number of iterations grows quickly if the outer loop contains many rows. For example, with 1 million rows in each table:

• A outer → B inner → 1 M × 1 M operations
• B outer → A inner → also large, but the cost may differ depending on indexes.

The goal is to reduce the number of iterations as early as possible.

Automatic Reordering

By default SQLite follows the order written in the query, but it can reorder tables when it finds a cheaper execution plan. SQLite uses a greedy algorithm:

1. Pick the cheapest table to process first.
2. Repeatedly add the next cheapest table.
3. Continue until all tables are placed.

If two options have equal cost, SQLite falls back to the original query order.

Cost Factors

SQLite estimates cost using several factors:

• Availability of indexes
• Selectivity of those indexes
• Whether sorting can be avoided
• Estimated number of rows to scan

An index that reduces 1 million rows to 1 row is extremely valuable, whereas an index that reduces 1 million rows to 900 000 rows provides little benefit.

Running ANALYZE is important because it gathers statistics that improve SQLite’s cost estimates.

Index Nested Loop Join

When a table has an index on the join column, SQLite often places that table as the inner loop. This enables efficient lookups for each row from the outer loop, a technique known as an index nested loop join.

Instead of scanning the entire inner table, SQLite uses the index to quickly find matching rows.

Reordering Rules for Different Join Types

• Inner joins: SQLite can freely reorder tables because the result does not depend on order.
• Outer joins (LEFT OUTER JOIN, RIGHT OUTER JOIN): Order matters for correctness, so SQLite does not reorder outer joins. However, tables involved in inner joins that surround an outer join may still be reordered if it improves performance.

When you use ON or USING clauses, SQLite internally converts them into additional WHERE conditions before optimization, so all WHERE‑clause optimizations still apply.

Forcing a Specific Order

If you need explicit control over the join order, use a CROSS JOIN. The tables appear exactly in the order you write them:

SELECT * 
FROM table1 
CROSS JOIN table2;

• table1 → outer loop
• table2 → inner loop

This technique lets you enforce the desired nesting when automatic reordering is not suitable.

Next Steps

The next topic is index selection, where SQLite decides which index to use when multiple candidates exist. Understanding both join ordering and index selection helps you write queries that run efficiently on SQLite.