Segmentation Fault in SQLite 3.36.0 Multi-Index OR with LEFT JOIN Optimization

Crash Context: Multi-Index OR Optimization in LEFT JOIN Queries with INDEXED BY Clause

Issue Overview

The crash occurs in SQLite 3.36.0 when executing a SELECT query that combines a LEFT JOIN with a WHERE clause containing an OR condition, indexed lookups via INDEXED BY, and a likely() function. The query leverages the multi-index OR optimization, a feature designed to accelerate queries with OR predicates by splitting them into separate index scans. However, under specific conditions involving cursor management during LEFT JOIN processing, this optimization leads to a segmentation fault due to improper initialization of index cursors.

Key Components of the Faulty Query

1. Schema Setup:

   • t1(a INT, b) with index i1 on a.
   • t2(e, d, f) with no explicit indexes.
   • The INDEXED BY i1 clause forces the query planner to use index i1 for the t1 table.

2. Query Structure:

   SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) 
   WHERE (b=5 AND e=12) OR (e=11 AND a=4) ORDER BY e;
   

   The WHERE clause contains two OR branches, each referencing columns from t1 and t2. The likely(a=e) hint in the LEFT JOIN condition biases the query planner toward specific index scans.

3. Crash Trigger:
   The segmentation fault occurs during bytecode execution at OP_ReopenIdx (addresses 10 and 23 in the bytecode dump). This opcode attempts to reopen an index cursor that was never properly initialized. The root cause lies in the interaction between the multi-index OR optimization and cursor lifecycle management for LEFT JOIN processing.

4. Query Plan Analysis:
   The plan uses MULTI-INDEX OR to split the WHERE clause into two index scans on i1, followed by a temporary B-tree for sorting. The SCAN t2 feeds rows into the OR branches, but the index cursor for i1 is not initialized before OP_ReopenIdx is called, leading to invalid memory access.

5. Bisecting History:
   The issue was traced to SQLite check-in ce35e39c5c, which introduced changes to cursor handling during covering index optimizations. Later optimizations (e.g., deferred seeks) exacerbated the problem when combined with INDEXED BY constraints.

Root Causes: Cursor Initialization Failures in Multi-Index OR with Forced Indexes

Cursor Lifecycle Mismanagement in LEFT JOINs

SQLite uses cursors (B-tree iterators) to traverse tables and indexes. In LEFT JOIN processing, cursors for the right-hand table (t1 in this case) must be initialized even when no matching rows exist. The OP_NullRow opcode (bytecode address 52) nullifies t1’s cursor if no match is found. However, the MULTI-INDEX OR optimization bypasses standard cursor initialization sequences when forced indexes (INDEXED BY) are present.

1. Forced Indexes and Covering Index Assumptions:
   The INDEXED BY i1 clause directs the query planner to treat i1 as a covering index. However, i1 only covers column a, not b, requiring additional table lookups. The planner incorrectly assumes i1 is fully covering, leading to incomplete cursor setup.

2. Deferred Seek and ReopenIdx Interactions:
   The OP_ReopenIdx opcode (addresses 10, 23) reuses an existing cursor to avoid reopening costs. However, in this query, the cursor for i1 is never opened prior to ReopenIdx due to:

   • The likely() function altering cost estimates, favoring a suboptimal plan.
   • The MULTI-INDEX OR splitting the index scan into two branches, each attempting to reuse the same cursor without proper initialization.

3. NullRow Handling in LEFT JOINs:
   When no rows match the LEFT JOIN condition, OP_NullRow nullifies t1’s cursor. However, if the cursor was never initialized (due to forced index assumptions), this opcode dereferences an invalid cursor handle, causing the crash.

4. Impact of likely() and Cost Adjustments:
   The likely(a=e) hint biases the planner to assume the a=e condition is true, influencing index selection. Combined with INDEXED BY, this creates a scenario where the planner skips cursor initialization steps normally required for non-covering indexes.

Resolution Strategy: Cursor Initialization Fixes and Query Plan Adjustments

Step 1: Apply Official SQLite Patches

The SQLite trunk fix (787c76a865dc51db) addresses the cursor initialization race condition. The patch ensures that cursors for forced indexes are properly initialized before OP_ReopenIdx is executed.

Key Changes in the Fix:

• Explicit Cursor Opening: Forces the cursor associated with i1 to be opened during query setup, even if the index is assumed to be covering.
• NullRow Safeguards: Adds checks to prevent OP_NullRow from operating on uninitialized cursors.

Verification:
After applying the patch, re-examine the bytecode for the query. The OP_ReopenIdx opcodes (addresses 10, 23) should now be preceded by OP_OpenRead or OP_OpenIdx instructions for i1.

Step 2: Query Rewrites to Avoid Risky Optimizations

If upgrading SQLite is not feasible, modify the query to bypass the problematic optimization:

Option 1: Remove INDEXED BY

SELECT e FROM t2 LEFT JOIN t1 ON likely(a=e) 
WHERE (b=5 AND e=12) OR (e=11 AND a=4) ORDER BY e;

This allows the query planner to choose indexes dynamically, avoiding forced index assumptions.

Option 2: Disable Multi-Index OR
Add a dummy + operator to prevent OR flattening:

SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) 
WHERE (b=5 AND e=12) OR (+(e=11) AND a=4) ORDER BY e;

The + inhibits the multi-index OR optimization, forcing a single index scan.

Option 3: Materialize Subqueries
Use UNION ALL to separate OR branches:

SELECT e FROM (
  SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) 
  WHERE b=5 AND e=12
  UNION ALL
  SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) 
  WHERE e=11 AND a=4
) ORDER BY e;

Step 3: Schema Adjustments for Safer Index Usage

• Drop Redundant Indexes: Ensure no unused indexes influence the planner.
• Add Covering Indexes: If i1 included b, it would qualify as covering, preventing the crash:

  CREATE INDEX i1 ON t1(a, b);  -- Now covers both a and b
  

Step 4: Monitor Query Plans with EXPLAIN

Use EXPLAIN and EXPLAIN QUERY PLAN to detect risky optimizations:

EXPLAIN QUERY PLAN
SELECT e FROM t2 LEFT JOIN t1 INDEXED BY i1 ON likely(a=e) ...;

Look for MULTI-INDEX OR and verify cursor initialization opcodes (OpenRead, OpenIdx).

Step 5: Regression Testing with Custom Bytecode Analysis

For advanced users, inspect the bytecode of suspect queries using sqlite3_stmt_status() or debugging builds. Validate that:

• OP_ReopenIdx is always preceded by OP_OpenRead for the same cursor.
• OP_NullRow operates only on initialized cursors.

This guide provides a comprehensive pathway to diagnose, resolve, and prevent crashes stemming from cursor mismanagement in complex SQLite queries. By addressing both the immediate bug and underlying planner assumptions, users can stabilize queries leveraging multi-index OR optimizations.