Issue Overview: SQLite Query Planner’s Automatic Index Cost Model and Join Order Optimization

SQLite’s query planner is a sophisticated component responsible for determining the most efficient way to execute SQL statements. A critical aspect of its operation involves deciding whether to create automatic indexes during query execution, particularly in JOIN operations. This decision hinges on a cost-based model that evaluates multiple execution strategies. The core challenge lies in understanding three interrelated concepts:

1. The cost calculation formula for different join orders and access patterns
2. Row count estimation (N) and its role in computational complexity
3. The interaction between automatic indexing decisions and cross join optimizations

At the heart of these calculations is SQLite’s use of asymptotic complexity analysis (O-notation) to model the relative costs of different query execution strategies. For a table with N rows, the planner compares:

• O(N) cost for full table scans
• O(N log N) cost for index creation + indexed lookups

The paradox arises in scenarios where SQLite chooses to create temporary indexes for cross joins despite the apparent higher complexity class. This requires deep analysis of how N is quantified, how multiple tables influence cost calculations, and what real-world factors make O(N log N) preferable to O(N) in specific join configurations.

Possible Causes: Misinterpretation of Complexity Classes, Hidden Cost Factors, and Multi-Table Join Combinatorics

1. Misunderstanding Big-O Notation in Context

Many confusion stems from interpreting O(N log N) vs O(N) as absolute performance metrics rather than growth rate comparisons. SQLite’s query planner uses these complexity classes as relative weights, not absolute time measurements. A full table scan (O(N)) might have a base cost of N units, while an index-based lookup could be modeled as 10N log N units. For small N values (e.g., N=100), 10100*2 = 2,000 could still be cheaper than a cross join’s multiplicative costs.

2. Undocumented Heuristics in Row Count Estimation

SQLite estimates table sizes (N) using:

• sqlite_stat1 statistics (if available)
• Default heuristics (e.g., 1 million rows for unknown tables)
• Dynamic sampling during ANALYZE

When joining three tables (A, B, C) with sizes N, M, P, the cross join cost escalates to O(NMP). The planner might create automatic indexes to reduce intermediate result sets, even if individual index creation seems expensive. This is particularly crucial when join predicate selectivity is low – a factor not explicitly captured in basic O-notation models.

3. Hidden Cost Components in Join Order Selection

The query planner evaluates permutation trees for join orders. For 5 tables, there are 5! (120) possible join orders. SQLite uses a greedy algorithm with pruning to avoid combinatorial explosion. Each join permutation’s cost includes:

• Access method costs (table scan vs index)
• Temporary storage costs for intermediate results
• CPU operation costs for comparisons

Automatic indexes alter these costs by:

• Reducing row comparisons via sorted access
• Enabling merge joins instead of nested loops
• Minimizing repeated full scans in multi-join queries

Troubleshooting Steps, Solutions & Fixes: Practical Analysis of Query Plans and Cost Model Adjustments

1. Decoding O(N log N) vs O(N) in Real-World Scenarios

Step 1: Quantify N for Specific Tables
Run ANALYZE to populate sqlite_stat1, then query:

SELECT tbl, stat FROM sqlite_stat1 WHERE idx = 'sqlite_autoindex_*';

For tables without statistics, SQLite uses heuristics based on:

• Database page counts
• Average rows per page
• Default assumptions (e.g., 1e6 rows)

Step 2: Calculate Relative Costs
Given table X with N=10,000 rows:

• Full scan cost = N = 10,000
• Index creation cost = 10N log N ≈ 1010,000*13.3 ≈ 1,330,000
  But when joining X to Y (M=100 rows):
• Cross join scan cost = N*M = 1,000,000
• Indexed join cost = 1,330,000 + (10*M log M) ≈ 1,330,000 + 6,644 ≈ 1,336,644

Here, the cross join (1M) is cheaper than indexed join (1.33M) – SQLite would avoid the index. If Y grows to M=10,000:

• Cross join cost = 100,000,000
• Indexed cost = 1,330,000 + 1,330,000 = 2,660,000 → Index preferred

Step 3: Force Index Usage for Testing

-- Disable automatic indexes
PRAGMA automatic_index = OFF;

-- Compare EXPLAIN QUERY PLAN outputs
EXPLAIN QUERY PLAN SELECT * FROM X, Y WHERE X.a = Y.b;

2. Analyzing Multi-Table Join Order Costs

For a 3-table join (A, B, C), SQLite evaluates these strategies:

Option 1: ((A JOIN B) JOIN C)

• Cost = Cost(A⋈B) + Cost((A⋈B)⋈C)
• Depends on join order and intermediate result sizes

Option 2: Automatic Index on A.a

• Cost = Index_A creation + Index_A lookup cost + subsequent joins

Use EXPLAIN and EXPLAIN QUERY PLAN to see:

EXPLAIN QUERY PLAN
SELECT * FROM A, B, C
WHERE A.x = B.y AND B.z = C.w;

Look for lines containing:

• USING AUTOMATIC COVERING INDEX
• SCAN TABLE A vs SEARCH TABLE A USING INDEX

Troubleshooting Tip: For complex joins, temporary tables may outperform automatic indexes. Test with:

PRAGMA temp_store = MEMORY; -- vs FILE

3. Advanced Configuration of the Query Planner

Adjust Cost Constants:
SQLite’s cost model uses compile-time constants (sqlite3.c):

#define SQLITE_COST_INDEX_LOOKUP 10
#define SQLITE_COST_TABLE_SCAN 20

Rebuild SQLite with modified constants to favor/hinder automatic indexes.

Statistics Maintenance:

-- Collect detailed statistics
ANALYZE;
-- Manually adjust stats (expert only)
UPDATE sqlite_stat1 SET stat = '10000 500' WHERE tbl = 'X';

Query Hints:
Use CROSS JOIN syntax to enforce join order:

SELECT * FROM A CROSS JOIN B ON (A.x = B.y); -- Disables reordering

Permanent Index Strategy:
For recurring query patterns, create manual indexes:

CREATE INDEX idx_x ON A(x);
-- Makes automatic index creation unnecessary

4. Cross Join Edge Cases and Workarounds

When SQLite creates automatic indexes for cross joins despite O(N log N) costs:

Scenario:

SELECT * FROM X, Y WHERE X.a = Y.b;
-- Automatic index on X.a created even for small tables

**Diagnosis:**
Check if: 
- One table has significantly more rows
- WHERE clause contains additional filters
- Implicit conversions affect index usability

**Solution:**
Force table scan order with:
```sql
SELECT * FROM X NOT INDEXED, Y WHERE X.a = Y.b;

5. Scaling to 5+ Table Joins

For complex joins, SQLite’s greedy algorithm may:

1. Start with the smallest table (lowest N)
2. Choose join order minimizing intermediate rows

Example:
Tables A(1M), B(100), C(500), D(10K), E(200)

Likely Join Order:
B → E → C → D → A

Troubleshooting Steps:

1. Use EXPLAIN QUERY PLAN to see chosen order
2. Compare with manual join order hints
3. Check for missing indexes on large tables

Critical Fix:
For 5+ table joins, ensure:

• Large tables have proper indexes
• Statistics are up-to-date
• Temporary storage is sufficient (configure with PRAGMA temp_store)

Final Recommendations

1. Always run ANALYZE after significant data changes
2. Use EXPLAIN QUERY PLAN religiously – it reveals automatic index decisions
3. Monitor sqlite_stat1 for skewed statistics
4. Consider permanent indexes for frequent join columns
5. Test with PRAGMA automatic_index=OFF to compare performance

The exact cost formulas remain SQLite-internal, but through empirical testing and understanding of complexity classes, developers can reliably predict and optimize automatic index behavior across various join scenarios.