LEFT JOIN Performance Regression in SQLite 3.41.1: Index Utilization Failure on View-Wrapped Right Tables

Scenario: Severe Query Slowdown When LEFT JOIN Uses View-Wrapped Right Table with Primary Key Index

Issue Overview
A critical performance degradation occurs in SQLite version 3.41.1 when executing LEFT JOIN operations where the right side of the join is wrapped in a view. The query planner fails to utilize the primary key index on the underlying table of the view, resulting in full table scans instead of indexed lookups. This regression manifests as a 100x-1000x slowdown in query execution time compared to SQLite 3.41.0 and earlier versions.

The problem is reproducible in environments where:

1. A recursive CTE generates a dataset (e.g., 10,000 rows).
2. A temporary table with an INTEGER PRIMARY KEY is populated from this dataset.
3. A temporary view is created as a SELECT * wrapper around the temporary table.
4. A LEFT JOIN combines the original table with the view using the primary key column.

For example:

CREATE TEMP VIEW G AS
  WITH RECURSIVE cnt(n) AS 
    (VALUES(1) UNION ALL SELECT n + 1 FROM cnt WHERE n < 10000)
  SELECT n FROM cnt;
CREATE TEMP TABLE T (pk INT PRIMARY KEY);
INSERT INTO T (pk) SELECT n FROM G;
CREATE TEMP VIEW V AS SELECT * FROM T;
SELECT * FROM T LEFT JOIN V ON V.pk = T.pk;  

In SQLite 3.41.0, this query completes in 25 milliseconds due to efficient index usage. In 3.41.1, execution time balloons to 10.59 seconds because the query planner scans the entire V view (effectively the T table) for each row in T, ignoring the primary key index.

Root Cause: Query Planner Optimization Failure Due to View Abstraction Layer

Possible Causes
The regression stems from changes introduced in SQLite check-in 198b3e33dcfd74c7, which addressed a correctness bug in the handling of LEFT JOIN operations (originally reported in forum thread 26387ea7ef). While resolving that issue, the modification inadvertently disrupted the query planner’s ability to recognize index availability when the right-hand table of a LEFT JOIN is accessed through a view.

Key Technical Factors:

1. View Abstraction Obscures Index Metadata:
   The CREATE VIEW V AS SELECT * FROM T statement creates an indirection layer. In SQLite 3.41.1, the query planner’s cost-based optimizer fails to propagate the T.pk index metadata through the view V. This prevents the planner from recognizing that V.pk (aliased from T.pk) is indexed, leading to a full scan of V for each row in the left table.

2. Incorrect Join Algorithm Selection:
   The optimizer selects a nested-loop join strategy where the right table (V) becomes the inner loop. Without index awareness, each iteration of the inner loop requires a linear scan of all rows in V (O(n²) complexity). With 10,000 rows, this results in 100,000,000 row comparisons.

3. Interaction with Temporary Objects:
   The use of temporary tables and views exacerbates the issue. SQLite’s query planner employs different optimization heuristics for temporary objects, which may bypass index analysis in certain contexts.

4. Query Simplifier Phase Regression:
   The problematic check-in modified logic in the query simplifier phase, which is responsible for transforming subqueries and views into efficient execution plans. The change disrupted the simplifier’s ability to "see through" the view to the underlying indexed table.

Resolution: Forcing Index Recognition and Mitigation Strategies

Troubleshooting Steps, Solutions & Fixes

Step 1: Confirm Index Utilization with EXPLAIN QUERY PLAN

Execute the query with .eqp on to reveal the execution strategy:

.eqp on
SELECT * FROM T LEFT JOIN V ON V.pk = T.pk;  

Expected Output in 3.41.0 (Healthy):

SCAN T  
SEARCH V USING INTEGER PRIMARY KEY (rowid=?)  

Observed Output in 3.41.1 (Degraded):

SCAN T  
SCAN V  

The absence of SEARCH indicates a full table scan on V.

Step 2: Apply Official Patch or Upgrade to Fixed Version

The SQLite team resolved the regression in subsequent releases. Two options:

1. Upgrade to SQLite ≥3.41.2 (or later), where the fix is included.
2. Backport the Patch to 3.41.1 by modifying the query planner logic related to view index propagation.

Step 3: Workarounds for Immediate Mitigation

If upgrading is impractical, employ these strategies:

A. Materialize the View as a CTE:
Rewrite the query to replace the view V with a CTE that directly references T:

WITH V AS (SELECT pk FROM T)
SELECT * FROM T LEFT JOIN V ON V.pk = T.pk;  

This bypasses the view abstraction layer, allowing index recognition.

B. Use SELECT DISTINCT on the View:
Adding DISTINCT forces the query planner to reevaluate the join strategy:

SELECT DISTINCT * FROM T LEFT JOIN V ON V.pk = T.pk;  

C. Explicit Index Hinting:
Force index usage with INDEXED BY:

SELECT * FROM T LEFT JOIN V INDEXED BY T_pk ON V.pk = T.pk;  

Note: Requires schema modification to name the primary key index.

D. Avoid Views for Join Operations:
Replace the view V with direct table references:

SELECT * FROM T LEFT JOIN T AS V ON V.pk = T.pk;  

Step 4: Monitor Byte-Code Execution Steps

Use .stat vmstep to count virtual machine operations:

.stat vmstep
SELECT * FROM T LEFT JOIN V ON V.pk = T.pk;  

A healthy execution uses ~729 steps (indexed). The degraded 3.41.1 plan requires ~51,445 steps (full scan).

Step 5: Validate Schema and Index Metadata

Ensure the view’s underlying table has a properly recognized index:

PRAGMA index_list(T);  

Verify output includes the implicit INTEGER PRIMARY KEY index.

Step 6: Downgrade to SQLite 3.41.0

If patching isn’t feasible, revert to 3.41.0 until the fixed version is available.

Technical Deep Dive: Query Planner Mechanics and Patch Analysis

The check-in 198b3e33dcfd74c7 altered how the query planner handles predicate pushdown through views. Previously, the planner would "flatten" the view into the main query, allowing direct access to T’s indexes. Post-patch, an overly conservative check prevented this flattening when the view contained a SELECT * without explicit column names.

The fix involved refining the view-flattening eligibility criteria to recognize implicit primary key columns even when propagated via SELECT *. This restored the optimizer’s ability to map V.pk to T.pk and leverage the index.

Lessons for Schema Design:

1. Avoid SELECT * in views used in joins; explicitly enumerate columns.
2. Prefer CTEs over views when index visibility is critical.
3. Use EXPLAIN QUERY PLAN proactively after SQLite upgrades.

By addressing the view-flattening regression and adopting defensive schema practices, developers can maintain optimal LEFT JOIN performance across SQLite versions.