Infinite Loop in SQLite 3.38 Due to Bloom Filter Optimization Bug

Issue Overview: Query Execution Hangs Indefinitely in SQLite 3.38

The core problem revolves around a regression introduced in SQLite versions 3.38.0 through 3.38.3, where certain queries involving complex joins, NULL values, and ORDER BY clauses trigger an infinite loop during execution. This manifests as a 100% CPU utilization hang with no results returned. The regression is traced to the Bloom filter pull-down optimization introduced in SQLite 3.38.0, which attempts to accelerate query execution by pre-filtering rows using probabilistic data structures. However, under specific conditions—particularly when NULL values are present in columns used for joins—the optimization generates incorrect byte-code, causing the query to restart indefinitely.

The issue is exacerbated in queries that combine INNER JOIN, LEFT JOIN, and ORDER BY clauses. For example, the user’s query joins four tables (Assignment, Order, AssignmentWorkflowStatus, Workunit, and AssignmentPoolStatus) with mixed join types and filters. The presence of a NULL in the Workunit.role column (or similar columns) triggers a misrouted jump instruction in the byte-code generator. This sends execution back to instruction 0 (the start of the query), creating an infinite loop. The problem disappears if the query structure is simplified (e.g., removing the ORDER BY clause or converting INNER JOIN to LEFT JOIN) or if the database schema lacks NULL values in critical columns.

A critical clue is that running ANALYZE resolves the issue in some cases. This is because ANALYZE updates the database statistics, which may alter the query planner’s decisions and bypass the faulty optimization. The bug is not merely theoretical: it is reproducible with a minimal test case involving NULLs, OUTER JOINs, and Bloom filter optimizations.

Possible Causes: Bloom Filter Logic, NULL Handling, and Query Planner Interactions

1. Bloom Filter Pull-Down Optimization Flaw

The Bloom filter pull-down optimization is designed to reduce query execution time by pre-evaluating conditions that can eliminate entire branches of the query plan early. For instance, if a Bloom filter (a probabilistic data structure) determines that a row cannot match a subsequent join condition, the query planner skips processing that row. However, in SQLite 3.38, this optimization mishandles NULL values. Specifically, when a NOT NULL check on a column containing NULLs is performed early in the byte-code sequence, the jump instruction intended to exit a loop instead points to instruction 0, restarting the query. This occurs because the byte-code generator assigns the jump destination label after generating the Bloom filter logic, leading to an invalid target.

2. NULL Values in Join Columns

NULLs in columns used for joins (e.g., Workunit.role in the user’s query) are a key catalyst. The Bloom filter optimization attempts to evaluate whether a row can satisfy a join condition before processing it. If the column contains NULL, the NOT NULL check fails, and the byte-code generator incorrectly routes execution to the start of the query. This creates a loop because the same NULL value persists across iterations, causing the same misrouted jump. The problem does not manifest if the column is guaranteed to be non-NULL (e.g., via a NOT NULL constraint) or if the query avoids columns with NULLs.

3. Query Structure and Planner Heuristics

Queries with multiple joins (especially a mix of INNER and LEFT JOINs), ORDER BY clauses, and complex WHERE conditions are more likely to trigger the bug. The SQLite query planner’s heuristics for selecting join order and optimization flags play a role. For example, the presence of an ORDER BY clause forces the planner to prioritize certain indexes or join orders that inadvertently expose the Bloom filter bug. Additionally, databases without up-to-date statistics (via ANALYZE) may cause the planner to choose suboptimal paths that rely on the faulty optimization.

Troubleshooting Steps, Solutions & Fixes

1. Immediate Workarounds

• Disable the Bloom Filter Optimization:
  For the affected database connection, disable the Bloom filter pull-down optimization using the sqlite3_test_control API or CLI command:

  .testctrl optimizations 0x100000  -- In SQLite CLI
  

  Programmatically in C:

  sqlite3_test_control(SQLITE_TESTCTRL_OPTIMIZATIONS, db, 0x100000);
  

  This disables the specific optimization (bitmask 0x100000) without affecting other query planner features.

• Run ANALYZE:
  Execute ANALYZE; to refresh the database statistics. This may prompt the query planner to choose a different execution plan that avoids the bug.

• Modify the Query:
  Simplify the query by removing the ORDER BY clause, converting INNER JOINs to LEFT JOINs, or eliminating unnecessary joins. For example, removing the ORDER BY Assignment.plannedStart clause in the user’s query resolves the issue.

2. Permanent Fixes

• Upgrade to SQLite 3.38.5 or Later:
  The bug was patched in subsequent releases. Versions 3.38.4+ include fixes for the byte-code generator’s handling of jump destinations in Bloom filter logic.

• Schema Adjustments:
  Add NOT NULL constraints to columns involved in joins where NULLs are not expected. For example, if Workunit.role should never be NULL, alter the table:

  ALTER TABLE Workunit ADD CHECK (role IS NOT NULL);
  

  This prevents NULLs from entering the column and sidesteps the optimization flaw.

3. Diagnostic and Debugging Techniques

• Use Debug Builds:
  Compile SQLite with -DSQLITE_DEBUG and run the query. The debug build includes assertions that catch invalid jump destinations, providing a stack trace to identify the faulty optimization step.

• EXPLAIN Output Analysis:
  Run EXPLAIN on the query to inspect the generated byte-code. Look for Jump instructions with a target of 0 or unusually early positions. For example:

  EXPLAIN SELECT ... [rest of the query];
  

  Correlate the byte-code with the SQLite documentation to identify misrouted jumps.

• Minimal Test Case Isolation:
  Reduce the query and schema to the simplest form that reproduces the issue. The test case provided by Richard Hipp demonstrates this:

  CREATE TABLE t1(a INT, b INT, c INT);
  INSERT INTO t1(a,b,c) VALUES(200, 200000, NULL);  -- Critical NULL
  

  This isolates the interaction between NULLs, joins, and the Bloom filter optimization.

4. Preventative Measures

• Regression Testing:
  After upgrading SQLite, run regression tests on complex queries, especially those involving OUTER JOINs and NULLable columns.

• Monitor Query Planner Changes:
  Review the SQLite changelog for query planner adjustments in new releases. Use the SQLITE_ENABLE_STAT4 compile-time option to enable advanced statistics for the query planner.

• Avoid Over-Optimization Flags:
  In performance-critical applications, selectively disable optimizations that have caused issues in the past using sqlite3_test_control.

By combining these strategies, developers can mitigate the infinite loop issue while maintaining the performance benefits of SQLite’s query optimizations. The root cause—incorrect jump destinations in Bloom filter logic—is a cautionary example of how NULL handling and optimization heuristics can interact in subtle ways, underscoring the importance of rigorous testing for database engine upgrades.