UPDATE Performance Regression in SQLite 3.42.0 Due to Subquery Materialization and Index Plan Changes

Understanding Query Plan Shifts in Subquery-Driven UPDATE Operations Between SQLite Versions 3.36.0 and 3.42.0

The core issue revolves around a significant performance regression observed in an UPDATE...FROM...WHERE query when migrating from SQLite 3.36.0 to 3.42.0. The query leverages a window function (LEAD) within a subquery to compute values for updating columns in the NewItem table. In SQLite 3.36.0, the query planner utilized an automatic covering index on the subquery-generated temporary table (tempT) to efficiently join NewItem and tempT using a SEARCH strategy. After upgrading to SQLite 3.42.0, the query plan changed to a full SCAN of both tempT and NewItem, resulting in a 1,900x slowdown for 75,000 records.

Schema and Query Context

• Tables:
  • NewItem: Stores item sequences with ItemId as a non-primary key.
  • Item: A WITHOUT ROWID table with composite primary key (ItemId, CategoryIdx) and an index on (CategoryIdx, SequenceInCategory).
• Query Logic:
  The subquery tempT computes StartIndex and EndIndex values for items in CategoryIdx=1 using the LEAD window function. These values are then used to update NewItem via an ItemId join.

Key Performance Regression Indicators

• SQLite 3.36.0 Plan:
  MATERIALIZE tempT → SEARCH Item USING INDEX IndexOnItemT → SEARCH tempT USING AUTOMATIC COVERING INDEX (ItemId=?).
  The automatic index on tempT.ItemId enabled efficient lookups during the join.
• SQLite 3.42.0 Plan:
  MATERIALIZE tempT → SCAN (subquery-3) → SCAN tempT → SCAN NewItem.
  The absence of an automatic index forced full scans, resulting in O(N*M) complexity.

Critical Observations

• The Item table’s IndexOnItemT was utilized in both versions for filtering CategoryIdx=1.
• The regression stems from SQLite 3.42.0’s failure to create an automatic covering index on tempT.ItemId, which is essential for efficient joins.
• Window functions like LEAD complicate subquery materialization, potentially influencing index eligibility in newer SQLite versions.

Root Causes of Automatic Index Suppression and Subquery Materialization Inefficiencies

1. Changes in SQLite’s Cost-Based Optimizer (CBO)

SQLite 3.42.0 introduced refinements to the query planner’s cost estimation logic, particularly for subqueries involving window functions. The CBO may now prioritize materializing subqueries with window functions as ephemeral tables without automatic indexing due to:

• Misestimated Join Costs: The planner might incorrectly assume that scanning tempT is cheaper than creating an automatic index, especially if statistics (e.g., sqlite_stat1) are outdated.
• Materialization of Window Functions: The LEAD function forces full materialization of tempT before processing. In SQLite 3.42.0, this materialization may bypass optimizations that detect join-key eligibility for automatic indexing.

2. Implicit Index Eligibility Rules for Subquery Results

Automatic covering indexes are created only when the query planner deems them cost-effective. Key factors include:

• Subquery Column Cardinality: If tempT.ItemId has low cardinality (many duplicates), the planner might opt for a scan.
• Join Selectivity: The absence of explicit indexes on NewItem.ItemId reduces the planner’s confidence in creating an automatic index on tempT.ItemId, as it cannot guarantee a balanced join.

3. Impact of Schema Design on Query Plans

• Missing Index on NewItem.ItemId: Without an explicit index, the planner in SQLite 3.42.0 defaults to scanning NewItem, exacerbating the join’s inefficiency.
• Composite Primary Key in Item: The WITHOUT ROWID design optimizes storage but does not inherently improve join performance for non-primary-key columns like ItemId.

Resolving Subquery Materialization and Join Inefficiencies in SQLite 3.42.0

Step 1: Create an Explicit Index on NewItem.ItemId

Solution:

CREATE INDEX NewItemId ON NewItem(ItemId);

Rationale:
This index converts the SCAN NewItem operation into a SEARCH, reducing the join complexity from O(N*M) to O(N log M).

Tradeoffs:

• Insertion Overhead: Index maintenance adds ~10%–15% latency to INSERT operations on NewItem. Mitigate this by batching inserts or using PRAGMA synchronous=OFF during bulk loads.
• Storage Impact: The index consumes additional space proportional to the table’s row count.

Step 2: Rewrite the Query to Bypass Window Function Materialization

Solution: Replace the LEAD window function with a self-join:

UPDATE NewItem  
SET StartIndex = curr.StartIndex,  
    EndIndex = COALESCE(next.StartIndex, curr.EndIndex)  
FROM Item curr  
LEFT JOIN Item next  
  ON next.CategoryIdx = curr.CategoryIdx  
  AND next.SequenceInCategory = curr.SequenceInCategory + 1  
WHERE NewItem.ItemId = curr.ItemId  
  AND curr.CategoryIdx = 1;

Rationale:

• Eliminates the subquery, allowing the planner to leverage IndexOnItemT directly.
• Uses a self-join to compute EndIndex, which is more likely to utilize existing indexes.

Step 3: Materialize tempT with an Explicit Temporary Table

Solution:

CREATE TEMP TABLE TempUpdates AS  
SELECT 
  ItemId, 
  StartIndex, 
  LEAD(StartIndex, 1, EndIndex) OVER (ORDER BY SequenceInCategory) AS EndIndex  
FROM Item  
WHERE CategoryIdx = 1;

CREATE INDEX TempUpdatesIdx ON TempUpdates(ItemId);

UPDATE NewItem  
SET StartIndex = TempUpdates.StartIndex,  
    EndIndex = TempUpdates.EndIndex  
FROM TempUpdates  
WHERE NewItem.ItemId = TempUpdates.ItemId;

Rationale:

• The temporary table’s explicit index guarantees an efficient join.
• Separating computation and update phases simplifies query optimization.

Step 4: Update Statistics with ANALYZE

Solution:

ANALYZE;

Rationale:

• Populates sqlite_stat1 with up-to-date cardinality and distribution data for all indexed columns.
• Helps the CBO accurately estimate the cost of automatic indexes versus full scans.

Step 5: Force Automatic Indexing with Query Planner Hints

Solution: Use NOT INDEXED and INDEXED hints to override the planner’s decisions (experimental):

UPDATE NewItem  
SET StartIndex = tempT.StartIndex,  
    EndIndex = tempT.EndIndex  
FROM (  
  SELECT /*+ INDEXED(ItemByCategory IndexOnItemT) */  
    ItemId,  
    StartIndex,  
    LEAD(StartIndex, 1, EndIndex) OVER (ORDER BY SequenceInCategory) AS EndIndex  
  FROM Item AS ItemByCategory  
  WHERE CategoryIdx = 1  
) AS tempT  
WHERE NewItem.ItemId = tempT.ItemId  
  AND NOT INDEXED(tempT);

Rationale:

• The INDEXED hint ensures IndexOnItemT is used for the subquery.
• NOT INDEXED(tempT) forces the planner to reconsider automatic indexing for the subquery result.

Step 6: Downgrade to SQLite 3.36.0 with Caution

Fallback Solution:
If immediate query/schema changes are impractical, revert to SQLite 3.36.0 while auditing other features for compatibility.

Risks:

• Forgoes security patches and optimizations introduced in later versions.
• Requires thorough testing to ensure no regressions in other queries.

Final Recommendation

Prioritize Step 1 (CREATE INDEX NewItemId) for immediate performance recovery, then implement Step 3 (temporary table materialization) to reduce reliance on automatic indexing. Combine with ANALYZE to maintain plan stability across upgrades.