SQLite fixes Bloom filtering across a LEFT JOIN

A LEFT JOIN can produce a row containing NULL values even when no stored row contains them. That distinction places restrictions on optimizations that try to eliminate work before evaluating the join. SQLite 3.38.2, released on March 26, repairs a Bloom-filter optimization that violated those restrictions. The affected query has a LEFT JOIN and a WHERE constraint requiring a column of the right-hand table to be NULL.

The optimization arrived in 3.38.0 to accelerate large analytic queries. This patch concerns the answer a query returns, so its significance extends beyond execution speed. I value SQLite's ability to put relational queries inside an application without introducing a database service. That arrangement still depends on the planner preserving SQL semantics when it changes the work performed internally.

A filter can change the join it was meant to accelerate

In the original report, Dieter Schmeer described a query that returned every left-hand row under 3.38.1 when it should have returned none. Richard Hipp traced the error to using a WHERE predicate to restrict the right-hand table's Bloom filter. The predicate was false for stored rows, making the filter empty. The join then behaved as though no matches existed, supplied NULL values, and passed the same WHERE test.

This sequence explains why a seemingly conservative filter can create extra output. Rejecting a candidate match in an outer join does not necessarily reject the left-hand row. It can change that row's associated values to NULL. A later predicate may accept the changed result. The following small example illustrates the semantic distinction, without claiming to reproduce the affected planner choice on a tiny dataset.

CREATE TABLE account(id INTEGER PRIMARY KEY);
CREATE TABLE profile(account_id INTEGER PRIMARY KEY, birthday TEXT);
INSERT INTO account VALUES(1);
INSERT INTO profile VALUES(1, '1900-01-01');

SELECT account.id
FROM account
LEFT JOIN profile ON profile.account_id = account.id
WHERE profile.birthday IS NULL;

The matching profile has a non-NULL birthday, so this query has no result row. Removing that profile before matching changes the outcome. The left join would supply a NULL-valued right-hand side, which satisfies profile.birthday IS NULL. Moving the predicate into an early filtering step therefore changes the meaning of this query.

The filter sits before a B-tree lookup

The released planner implementation describes Bloom filtering as a way to avoid a subsequent B-tree seek when the filter indicates that no matching rows exist. A register holds a blob representing the filter. Initialization scans the selected table and adds values derived from its row identifier or the equality columns of an index.

This makes construction a separate phase of the optimization. The planner has to decide which stored rows contribute keys before it can use the filter to reject lookups. If construction excludes a key that a valid match requires, later lookup avoidance is incorrect. Evaluating the remaining query faithfully cannot recover a match that the earlier filter has already prevented.

The code derives the blob size from the estimated row count. It sets a lower bound of 10,000 bytes and an upper bound of 10,000,000 bytes. Its comments explain that using the estimate makes testing easier than measuring table size during execution. This is one reason a small illustrative query and a production-sized query need not select the same execution strategy, even though their join semantics are identical.

Construction also considers expressions that are constant for an individual table row. The expression implementation defines that property by excluding references to other tables and nondeterministic functions. That check addresses whether an expression can be evaluated from one table's row. Whether using it at a particular join stage preserves the result is a further concern.

For outer joins, a column reference can describe either a stored value or a NULL value supplied because matching failed. An optimization must retain the distinction between those contexts. A predicate that can be evaluated using one table's columns is not automatically a valid restriction on every earlier scan of that table.

Reproducing a plan requires its assumptions

The forum investigation used a deliberately controlled setup, including table statistics, to exercise the problematic plan. This matters when interpreting a report that only occurs with many rows. The SQL statement describes the required result, while estimated costs help determine which internal program SQLite generates. A bug in one generated program can remain absent from another plan for the same logical query.

That observation also explains why rewriting an expression can appear to repair a wrong answer. A changed expression may prevent a particular optimization without correcting the engine that generated it. The relevant result from the investigation is the planner repair incorporated into this release. Applications should retain SQL that states their intended relationship, rather than depend on incidental syntax changes to avoid one execution strategy.

I regard the distinction between ON and WHERE as central to understanding this patch. The join condition determines matching, and the WHERE predicate evaluates the resulting rows. The failure arose when an early optimization used information from the latter stage to alter the former. A LEFT JOIN query looking for missing or NULL-associated data needs those stages to retain their different meanings, regardless of whether SQLite chooses a Bloom filter or performs the underlying lookups directly.