Performance Regression in SQLite 3.40.2/3.41.x with UNION ALL Views and Complex Joins

Issue Overview: Query Planner Fails to Use Indexes on UNION ALL Views and Multi-Table Joins

A critical performance regression was observed in SQLite versions 3.40.2 and 3.41.x when executing queries involving UNION ALL views built from indexed tables or multi-table joins with complex conditions. The regression manifests as full table scans instead of index-driven lookups, leading to execution time increases from milliseconds to hours in extreme cases. This behavior is directly tied to changes in the query planner’s ability to propagate search constraints through compound queries and optimize join order selection.

Key Symptoms

1. Index Ignorance in UNION ALL Views
   Queries against views defined via UNION ALL of tables with compatible indexes (e.g., index_objs_sp on objs(s,p) and index_datas_sp on datas(s,p)) fail to utilize those indexes in affected SQLite versions. For example:

   SELECT o,d FROM quads WHERE s=303 AND p=9;
   

   • Expected Behavior (3.40.1): Uses SEARCH with index_objs_sp and index_datas_sp
   • Regressed Behavior (3.40.2): Falls back to SCAN on objs and datas

2. Join Order Degradation in Complex Queries
   Multi-table joins with interdependent WHERE clauses and CASE statements experience catastrophic slowdowns. A real-world example involves an 8-table join that took 58 ms in SQLite 3.40 but failed to complete after 3 hours in 3.41.2. The query planner selects suboptimal join orders, often prioritizing tables without filtering conditions, leading to Cartesian product explosions.

3. Dependency on ANALYZE Statistics
   The regression is partially mitigated by running the ANALYZE command, which updates table statistics. In the 8-table join scenario, execution time dropped from >3 hours to 60 ms after ANALYZE, indicating the query planner relies heavily on statistical metadata for index selection and join ordering.

Affected Versions and Impact

• SQLite 3.40.2: Introduces the UNION ALL view regression.
• SQLite 3.41.1/3.41.2: Extends the issue to complex joins, likely due to refinements in join reordering algorithms.
• Impact: Queries that previously leveraged indexes or efficient join orders now risk full scans or combinatorial explosions. Performance degradation scales with table size, with reports of 300x–1000x slowdowns on medium-sized databases (300MB).

Possible Causes: Query Planner Algorithm Changes and Statistics Handling

1. Constraint Propagation Failure in Compound Queries

The UNION ALL view regression stems from a query planner bug where search constraints (s=303 AND p=9) are not propagated to the underlying tables in compound queries. Normally, SQLite’s flattening optimization pushes WHERE clauses into subqueries. In affected versions, this optimization fails for UNION ALL views, causing the outer WHERE to apply after the union, forcing full scans.

Technical Context:
SQLite’s SELECT processing uses a co-routine model for compound queries. When constraints are not pushed down, the co-routine materializes the entire UNION ALL result before applying filters, negating index benefits.

2. Join Ordering Heuristics and Cost Estimation

The complex join regression arises from changes in join reordering algorithms and cost estimation. SQLite uses a greedy algorithm with dynamic programming to limit computational overhead. Changes in 3.41.x altered how the planner prioritizes tables:

• Problem: Tables with no direct WHERE constraints (e.g., Etablissements) are scanned first, multiplying intermediate row counts.
• Root Cause: Inaccurate row count estimates for tables joined via CASE-dependent conditions. Without ANALYZE statistics, the planner assumes uniform data distribution, leading to unrealistic cost calculations.

3. Statistics Metadata Dependency

The effectiveness of ANALYZE highlights SQLite’s reliance on sqlite_stat1 table statistics for index selection. When statistics are stale:

• The planner underestimates the selectivity of indexed columns (e.g., s=303 AND p=9), deeming scans cheaper than index lookups.
• For joins, outdated statistics skew the estimated "cost" of joining tables in a particular order, favoring suboptimal paths.

4. Version-Specific Algorithmic Tweaks

The regressions correlate with two changes:

• Check-in aa6bd6dff751223e: Fixed the UNION ALL constraint propagation issue in trunk but was not backported to 3.41.x.
• Join Ordering Adjustments: Minor tweaks to the heuristic rules for reordering joins in 3.41.x inadvertently prioritized unselective tables when statistics were missing.

Troubleshooting Steps, Solutions & Fixes

1. Immediate Workarounds for Affected Versions

A. Rewrite UNION ALL Views as Materialized Subqueries

Force constraint propagation by inlining the view definition:

-- Original query using view
SELECT o,d FROM quads WHERE s=303 AND p=9;

-- Rewritten to inline UNION ALL
SELECT o,d FROM (
  SELECT c,s,p,o,NULL AS d FROM objs WHERE s=303 AND p=9
  UNION ALL
  SELECT c,s,p,o,d FROM datas WHERE s=303 AND p=9
);

This bypasses the co-routine materialization, allowing the WHERE clause to push into the subqueries.

B. Use Index Hints via CROSS JOIN

For complex joins, replace comma-style joins with CROSS JOIN to influence join order:

-- Problematic comma join
SELECT ... FROM Tsal, LiaisonRubriquesAssiettesCotis, ...;

-- Force join order with CROSS JOIN
SELECT ... FROM Tsal
CROSS JOIN LiaisonRubriquesAssiettesCotis
CROSS JOIN RecapMens2 ...;

CROSS JOIN disallows reordering, letting you manually prioritize selective tables.

C. Run ANALYZE to Update Statistics

Generate fresh statistics for the query planner:

ANALYZE;
ANALYZE sqlite_schema;  -- For schema-wide analysis

This populates/updates the sqlite_stat1 table with histogram data, improving row count estimates.

2. Upgrade to SQLite Trunk or 3.42.0+

The root fix for the UNION ALL regression is available in SQLite’s trunk and will ship in 3.42.0. To test the fix:

1. Download Trunk:
   Visit SQLite Timeline and download the latest amalgamation (e.g., sqlite3.c, sqlite3.h).
2. Compile from Source:

   gcc -DSQLITE_ENABLE_EXPLAIN_COMMENTS -o sqlite3 sqlite3.c shell.c
   

3. Verify Fix:
   Re-run the problematic query and confirm the query plan uses SEARCH with indexes.

3. Monitor and Adjust Query Plans

A. Explain Query Plans

Use EXPLAIN QUERY PLAN to diagnose index usage:

EXPLAIN QUERY PLAN
SELECT o,d FROM quads WHERE s=303 AND p=9;

• Healthy Plan: SEARCH using indexes on objs and datas.
• Regressed Plan: SCAN on both tables.

B. Force Index Usage

Override the planner’s index selection with INDEXED BY:

SELECT o,d FROM (
  SELECT c,s,p,o,NULL AS d FROM objs INDEXED BY index_objs_sp WHERE s=303 AND p=9
  UNION ALL
  SELECT c,s,p,o,d FROM datas INDEXED BY index_datas_sp WHERE s=303 AND p=9
);

Use sparingly, as this bypasses the planner’s adaptability.

4. Long-Term Mitigations

A. Schema Design Adjustments

• Avoid Overusing Views: Materialize frequently queried views as tables with triggers for updates.
• Composite Indexes: Ensure indexes cover all WHERE and JOIN columns. For objs(s,p), add o if frequently selected:

  CREATE INDEX index_objs_spo ON objs(s,p,o);
  

B. Query Tuning

• Simplify CASE Statements: Move conditional logic to application code or temp tables.
• Limit Join Arity: Break complex joins into subqueries or CTEs to reduce planner complexity.

C. Automated Statistics Maintenance

Schedule periodic ANALYZE jobs, especially after bulk data changes:

-- Daily analysis for active databases
PRAGMA analysis_limit=1000;
ANALYZE;

5. Reporting and Collaboration

Contribute to SQLite’s stability by:

1. Submitting Test Cases: Share minimal reproductions of regressions via SQLite Forum.
2. Beta Testing Trunk: Validate fixes in development environments and report anomalies.

By methodically applying these solutions—whether through query rewrites, statistical updates, or upgrades—developers can neutralize the performance regressions while awaiting official patches. The key is to recognize the interplay between query planner algorithms, index design, and statistical metadata in SQLite’s optimization pipeline.