Optimizing SQLite Queries to Avoid Temporary B-Tree Sorting on Composite Indexes

Understanding the USE TEMP B-TREE Behavior in Composite Index Queries with ORDER BY and IN Clauses

Issue Overview: Composite Index Order Mismatch and Temporary Sorting Overhead

The core challenge involves optimizing a SQLite query that selects multiple itemId values with a range condition on eventTs, then orders results by eventTs while avoiding temporary sorting structures. The table entries is defined with a composite primary key (itemId ASC, eventTs ASC) in a WITHOUT ROWID configuration. The query in question filters rows where itemId is in a list of values (e.g., 1, 2) and eventTs exceeds a threshold, then sorts the results by eventTs with a LIMIT clause.

The execution plan reveals that SQLite uses the primary key index to SEARCH for qualifying rows but resorts to a USE TEMP B-TREE FOR ORDER BY step. This occurs despite the presence of an index that includes eventTs. The disconnect arises from the composite index’s ordering hierarchy: entries are grouped first by itemId, then sorted by eventTs within each itemId group. When querying multiple itemId values, SQLite retrieves ordered eventTs entries per itemId but must merge these disjoint ordered sequences into a single globally ordered sequence by eventTs. Without explicit optimization for merging sorted streams (like MongoDB’s SORT_MERGE), SQLite defaults to collecting all qualifying rows, sorting them in a temporary B-tree, and applying the LIMIT.

The temporary B-tree introduces overhead in two forms:

1. Memory/Storage Allocation: The temporary structure consumes resources proportional to the number of qualifying rows.
2. Latency: Full materialization and sorting occur before applying LIMIT, even if only a few rows are needed.

This behavior contradicts the user’s expectation that the composite index’s ordering could be directly leveraged for merge-style sorting. SQLite’s query planner lacks a built-in optimization to interleave ordered results from multiple index ranges (e.g., itemId=1 and itemId=2) into a single sorted stream without materialization. The issue is exacerbated when the IN clause contains non-contiguous or sparsely distributed itemId values, as the planner cannot assume logical adjacency in the index.

Possible Causes: Index Structure, Query Semantics, and Planner Limitations

1. Composite Index Ordering Hierarchy

The primary key (itemId, eventTs) orders rows first by itemId, then by eventTs within each itemId partition. For a query targeting a single itemId, the index naturally provides rows in eventTs order. However, when multiple itemId values are queried, the index returns rows grouped by itemId, each group internally ordered by eventTs, but the groups themselves are not interleaved by eventTs. To satisfy an ORDER BY eventTs across all groups, SQLite must collect all qualifying rows and sort them globally.

2. IN Clause vs. Range Scans

The IN (1, 2) predicate is semantically equivalent to itemId=1 OR itemId=2. SQLite treats this as two discrete index searches: one for itemId=1 and eventTs>..., another for itemId=2 and eventTs>.... These searches yield two separate streams of rows, each ordered by eventTs but not merged. By contrast, a BETWEEN 1 AND 2 clause represents a contiguous range of itemId values. If the table’s itemId values are densely packed (no gaps between 1 and 2), BETWEEN allows SQLite to scan a single index range, preserving eventTs order. However, this is not guaranteed unless the schema enforces such density.

3. Query Planner Statistics and ANALYZE

SQLite’s query planner relies on statistical metadata (stored in sqlite_stat1 tables) to estimate the cost of alternative query plans. Without up-to-date statistics (via the ANALYZE command), the planner may misjudge the number of rows matching itemId IN (1,2) and eventTs>..., leading to suboptimal choices. For instance, outdated statistics might underestimate the selectivity of eventTs, causing the planner to prefer a full index scan followed by sorting instead of leveraging the index for partial ordering.

4. LIMIT Clause Interaction

The presence of LIMIT 2 suggests that only the earliest two rows by eventTs are needed. An ideal optimization would involve scanning index segments for each itemId in parallel, maintaining a priority queue of the smallest eventTs values, and stopping once the queue contains enough entries. SQLite does not implement this optimization for composite indexes with IN clauses. Instead, it materializes all qualifying rows, sorts them, and then applies the LIMIT.

5. Covering Index Design

The existing primary key index covers all columns (itemId, eventTs, title, content) because the table is WITHOUT ROWID. However, the index’s ordering prioritizes itemId first. A secondary index on (eventTs, itemId) would prioritize eventTs order, but such an index would not cover the title and content columns unless explicitly included. Without a covering index, SQLite would need to perform lookups to retrieve title and content, negating any benefit from the alternative index order.

Troubleshooting Steps, Solutions & Fixes: Eliminating Temporary Sorting in Multi-Item Queries

1. Prefer Contiguous Ranges with BETWEEN over IN

Action: Replace itemId IN (1, 2) with itemId BETWEEN 1 AND 2 if the itemId values are contiguous and the query targets a range without gaps.
Rationale: The BETWEEN clause allows SQLite to perform a single range scan on the composite index, preserving eventTs order across all rows in the range. This avoids the need to merge multiple index lookups.
Verification:

EXPLAIN QUERY PLAN 
SELECT * FROM entries 
WHERE itemId BETWEEN 1 AND 2 AND eventTs > 1717654460 
ORDER BY eventTs ASC LIMIT 2;

Check if the USE TEMP B-TREE step disappears. If it does, the index is providing the required order.

Caveats:

• Ensure itemId values between 1 and 2 exist and are contiguous. Gaps (e.g., missing itemId=1.5) will not affect correctness but may reduce efficiency.
• Use ANALYZE to ensure the planner recognizes the density of itemId values.

2. Create a Secondary Index on (eventTs, itemId)

Action: Add an index that prioritizes eventTs first, enabling direct ordering without temporary structures:

CREATE INDEX idx_entries_eventTs_itemId ON entries(eventTs ASC, itemId ASC);
ANALYZE;

Rationale: This index allows SQLite to scan rows in eventTs order while filtering on itemId and eventTs. Since eventTs is the leading column, the ORDER BY eventTs clause can be satisfied without additional sorting.

Verification:

EXPLAIN QUERY PLAN 
SELECT * FROM entries 
WHERE itemId IN (1, 2) AND eventTs > 1717654460 
ORDER BY eventTs ASC LIMIT 2;

If the plan shows SCAN entries USING INDEX idx_entries_eventTs_itemId without USE TEMP B-TREE, the index is effective.

Caveats:

• The index does not cover title and content unless explicitly included (not supported in SQLite). Thus, each qualifying row requires a lookup to the main table (the WITHOUT ROWID table itself), which may offset sorting gains.
• Index maintenance overhead increases with write operations.

3. Use UNION ALL for Discrete itemId Values

Action: For a small, fixed set of itemId values, decompose the query into per-itemId subqueries and combine results:

SELECT * FROM (
  SELECT * FROM entries WHERE itemId=1 AND eventTs > 1717654460
  UNION ALL
  SELECT * FROM entries WHERE itemId=2 AND eventTs > 1717654460
) 
ORDER BY eventTs ASC LIMIT 2;

Rationale: Each subquery leverages the composite index to retrieve rows in eventTs order for a specific itemId. The UNION ALL concatenates these ordered streams, and the outer ORDER BY sorts the combined results. SQLite may optimize this by scanning each subquery’s index range and using a priority queue for the LIMIT.

Verification:

EXPLAIN QUERY PLAN ...; -- Check for per-itemId SEARCH steps and absence of TEMP B-TREE.

Caveats:

• Manual query decomposition becomes unwieldy for large or variable itemId sets.
• The outer ORDER BY still requires sorting, but the input is partially ordered, which may reduce overhead.

4. Leverage Partial Indexes for High-Volume itemId Values

Action: If certain itemId values are queried more frequently, create partial indexes targeting those values:

CREATE INDEX idx_entries_item1_eventTs ON entries(eventTs) WHERE itemId=1;
CREATE INDEX idx_entries_item2_eventTs ON entries(eventTs) WHERE itemId=2;

Rationale: Each partial index contains only rows for a specific itemId, ordered by eventTs. Queries targeting these itemId values can merge the pre-sorted streams.

Verification:

EXPLAIN QUERY PLAN 
SELECT * FROM entries 
WHERE itemId IN (1, 2) AND eventTs > 1717654460 
ORDER BY eventTs ASC LIMIT 2;

Check if the plan uses the partial indexes.

Caveats:

• Proliferation of partial indexes increases storage and write overhead.
• Only practical for a small, stable set of high-frequency itemId values.

5. Schema Redesign for eventTs-Centric Queries

Action: If most queries order by eventTs across multiple itemId values, consider restructuring the schema to prioritize eventTs as the leading column in the primary key:

CREATE TABLE entries (
  itemId INTEGER NOT NULL,
  eventTs INTEGER NOT NULL,
  title TEXT,
  content TEXT,
  PRIMARY KEY (eventTs ASC, itemId ASC)
) WITHOUT ROWID;

Rationale: The composite index now orders rows by eventTs first, allowing direct range scans on eventTs with itemId filtering.

Verification:

EXPLAIN QUERY PLAN 
SELECT * FROM entries 
WHERE itemId IN (1, 2) AND eventTs > 1717654460 
ORDER BY eventTs ASC LIMIT 2;

The plan should show SEARCH using the primary key without temporary sorting.

Caveats:

• Alters the fundamental row organization, impacting all queries on the table.
• May degrade performance for queries that filter or group by itemId.

6. Utilize Scan Status and Query Planner Hints

Action: Use SQLite’s .scanstats and EXPLAIN features to diagnose row processing:

-- Enable scan statistics
.scanstats on

-- Run the query
SELECT * FROM entries WHERE itemId IN (1, 2) AND eventTs > 0 ORDER BY eventTs ASC LIMIT 1;

-- Interpret output

Rationale: .scanstats reveals how many rows were scanned from each index and the main table. If the SEARCH steps process fewer rows than expected, SQLite may be short-circuiting the scan due to LIMIT.

Key Observations:

• rows=4 in SEARCH indicates that 4 rows were read from the index.
• rows=4 in USE TEMP B-TREE suggests all 4 rows were sorted, but only 1 was returned due to LIMIT.

Caveats:

• Scan statistics reflect the number of rows processed, not necessarily the total qualifying rows.
• SQLite may abort scanning early if the LIMIT is satisfied, even if more rows exist.

7. Forcing Index Usage with Manual Hints

Action: Use INDEXED BY to coerce SQLite into using a specific index, though this is generally discouraged:

SELECT * FROM entries INDEXED BY (primary_key_index_name) 
WHERE itemId IN (1, 2) AND eventTs > 1717654460 
ORDER BY eventTs ASC LIMIT 2;

Rationale: Overrides the planner’s index selection, which may help in edge cases where statistics are misleading.

Caveats:

• Risks suboptimal plans if data distribution changes.
• Requires hardcoding index names, reducing portability.

By systematically addressing the composite index ordering, query structure, and SQLite’s planner behavior, developers can eliminate temporary sorting overhead in multi-item queries. The optimal solution depends on the specific access patterns, data distribution, and performance trade-offs acceptable in the application.