Resolving Severe Query Performance Caused by Correlated Subquery and Index Selection Issues

Dynamic Main Row Selection with Correlated Subquery Leading to Exponential Performance Degradation

Issue Overview

The core problem revolves around a SQLite query designed to select one representative row per group from a large table (t1), dynamically determined by evaluating scoring criteria from a secondary table (t2). This query suffers from sporadic but severe performance degradation, escalating from milliseconds to tens of seconds under specific conditions. The root of the issue lies in the interaction between three critical components:

1. Correlated Subquery Execution: The query uses a correlated subquery to determine the "main row" for each group. This subquery is executed repeatedly—once for every row processed in the outer query. The subquery involves joins between t2 (aliased as t3) and t1, filtering on columns like c3, c4, c5, c2, group_id, and c8, followed by an ORDER BY c9 DESC, c10 to select the highest-scoring row. This structure forces SQLite to re-evaluate the subquery for every candidate row in the outer loop, leading to O(N²) complexity.

2. Index Misuse or Absence: The subquery’s performance hinges on efficient index usage. While an existing index i1 on t2 (group_id, c8, c2, c9, c1) improves performance when explicitly forced (INDEXED BY i1), this approach is brittle. The query planner may ignore optimal indexes due to outdated statistics, schema changes, or conflicting filtering conditions.

3. Outdated Query Planner Statistics: SQLite relies on stored statistics (collected via ANALYZE) to choose execution plans. When large datasets are added in bulk (e.g., initial app setup with thousands of rows), the planner’s decisions become suboptimal because statistics no longer reflect the true data distribution. This is exacerbated by the dynamic nature of the "main row" selection, which depends on real-time scoring rather than static flags.

Potential Causes of Degraded Performance

1. Correlated Subquery Overhead

   • Mechanism: The subquery t1.c1 = (SELECT ...) is correlated to the outer t2 table through t3.c2 IS t2.c2, t3.group_id = t2.group_id, and t3.c8 = t2.c8. For each row in the outer query, SQLite must execute the subquery, joining t3 (a copy of t2) with t1, applying filters, sorting, and selecting the top result.
   • Impact: With 50k+ rows in t1, even minor inefficiencies in the subquery (e.g., full scans instead of index seeks) compound exponentially. A 1ms subquery per row becomes 50 seconds for 50k rows.

2. Inefficient Index Utilization

   • Index Design: The existing index i1 on t2 includes group_id, c8, c2, c9, c1, but the subquery’s WHERE clause filters on t3.c2, group_id, c8, and t1.c3, c4, c5. Missing composite indexes covering these columns or misaligned index column order can force full scans.
   • Query Planner Misjudgment: Without up-to-date statistics, the planner may underestimate the selectivity of filters (e.g., t1.c3 = 0), leading to suboptimal index choices. Forcing an index (INDEXED BY) masks the problem but does not resolve underlying planner inaccuracies.

3. Statistics and Data Volatility

   • ANALYZE Neglect: If ANALYZE has not been run after bulk data changes, the planner uses default or stale statistics, causing incorrect assumptions about join cardinality and filter selectivity.
   • Data Skew: Scenarios like an initially empty t1 followed by rapid insertion of thousands of rows create skewed distributions. The planner’s default heuristics (e.g., assuming uniform distribution for c3, c4, c5) become invalid, leading to catastrophic plan choices.

Troubleshooting Steps, Solutions, and Fixes

Step 1: Update Query Planner Statistics

• Action: Execute ANALYZE to refresh statistics. This generates or updates the sqlite_stat1 table, which stores histogram data for indexes and tables.

  ANALYZE;
  

• Rationale: Modern SQLite versions (3.33.0+) use histograms for better selectivity estimates. Updated statistics help the planner recognize that t1.c3 = 0, c4 = 0, and c5 = 0 are highly selective (if true), favoring index usage.

Step 2: Analyze Query Execution Plans

• Action: Use EXPLAIN QUERY PLAN to compare plans with and without forced indexes.

  EXPLAIN QUERY PLAN
  SELECT ... [original query];
  

• Key Observations:
  • Check if the subquery uses an index for t3 (look for SEARCH t2 AS t3 USING INDEX ...).
  • Verify join order: The planner should prioritize indexed joins over full scans.
  • Identify nested loops vs. hash joins. Correlated subqueries often result in nested loops, which are inefficient at scale.

Step 3: Optimize Indexing Strategy

• Composite Index for t1: Create an index covering c3, c4, c5, and c1 to accelerate the subquery’s WHERE clause:

  CREATE INDEX idx_t1_filter ON t1(c3, c4, c5, c1);
  

• Revised Index for t2: Adjust i1 to match the subquery’s join and filter order:

  CREATE INDEX idx_t2_main_row ON t2(group_id, c8, c2, c9 DESC, c10 DESC, c1);
  

  This index aligns with the WHERE t3.group_id = t2.group_id AND t3.c8 = t2.c8 AND t3.c2 IS t2.c2 and ORDER BY c9 DESC, c10 clauses, allowing a single index seek per subquery.

Step 4: Rewrite the Correlated Subquery Using CTEs or Window Functions

• Problem: The correlated subquery forces repeated execution. Rewrite it using a Common Table Expression (CTE) to compute all "main rows" upfront.
• CTE-Based Approach:

  WITH RankedGroups AS (
    SELECT 
      t1._id,
      t1.c1,
      t2.group_id,
      t2.c8,
      t2.c2,
      ROW_NUMBER() OVER (
        PARTITION BY t2.group_id, t2.c8, t2.c2 
        ORDER BY t1.c9 DESC, t1.c10 DESC
      ) AS rank
    FROM t1
    JOIN t2 ON t1.c1 = t2.c1
    WHERE t1.c3 = 0 AND t1.c4 = 0 AND t1.c5 = 0
  )
  SELECT [various columns]
  FROM (
    SELECT _id
    FROM RankedGroups
    WHERE rank = 1
    AND ... [additional filters]
    ORDER BY c10 DESC, _id DESC
    LIMIT 225
  )
  LEFT JOIN ... [remaining joins];
  

• Advantages:
  • The ROW_NUMBER() window function computes ranks in a single pass, eliminating O(N²) subquery overhead.
  • Partitioning by group_id, c8, and c2 mirrors the original subquery’s grouping logic.

Step 5: Adjust Database Configuration

• Increase Cache Size: Set PRAGMA cache_size = -kibibytes; to allocate more memory for caching pages. For example, PRAGMA cache_size = -10000; reserves ~10MB.
• Enable Memory-Mapped I/O: If using multiple connections, configure PRAGMA mmap_size = ...; to reduce I/O contention.

Step 6: Monitor and Optimize Incrementally

• Profile with sqlite3_stmt Extension: Use sqlite3_stmt_status() to track subquery executions and page cache hits.
• Regular Maintenance: Schedule PRAGMA optimize; after significant data changes to automate index rebuilds and statistics updates.

Final Recommendations

• Replace correlated subqueries with set-based operations (CTEs, window functions).
• Ensure indexes are tailored to both filter and order-by clauses.
• Combine ANALYZE with proactive statistics maintenance.
• Test changes incrementally using real-world data distributions to validate planner decisions.

By systematically addressing correlated query execution, index alignment, and planner statistics, the sporadic performance degradation can be resolved, achieving consistent sub-100ms response times.