Optimizing Virtual Table Column Sorting After Base Table Filtering in SQLite

Virtual Table Rank Sorting Performance Degradation Under Base Table Filter Constraints

When executing a query that joins a virtual table responsible for computing a dynamic rank column with a base table containing filtering criteria, significant performance degradation can occur when sorting on the virtual table’s computed column after applying base table filters. This issue is particularly pronounced in datasets ranging from 500,000 to 1,000,000 rows, where SQLite’s default query planner behavior forces a full or partial scan of the virtual table, inefficient filtering via base table lookups, and a subsequent sorting phase that scales non-linearly. The problem manifests as execution times differing by orders of magnitude (e.g., 3 seconds vs. 50 milliseconds) depending on whether sorting is delegated to the virtual table or handled by SQLite’s temporary B-tree mechanism.

Root Causes of Sorting Inefficiency in Virtual Table Queries

1. Query Planner Execution Order Mismatch

SQLite’s query planner prioritizes scanning the virtual table first due to its role as the driver of the rank computation. However, the filtering predicates reside in the base table (b.name LIKE 'foo' and others). This forces the following sequence:

• Full or partial scan of the virtual table to compute v.rank.
• Repeated primary key lookups on base_table for each virtual_table row to evaluate filtering conditions.
• Post-filtering sorting of the result set using a temporary B-tree.

This execution order is suboptimal because:

• Unnecessary Base Table Lookups: Rows discarded by base table filters still incur the cost of primary key lookups.
• Late-Stage Sorting: The ORDER BY v.rank operation is applied after filtering, requiring SQLite to materialize a large intermediate result set before sorting.

2. Failure to Leverage Virtual Table Sorting Capabilities

Virtual tables can declare their ability to return rows in a specific order using the orderByConsumed flag in the xBestIndex method. If this flag is not set, SQLite assumes it must perform its own sorting, even if the virtual table could provide pre-sorted data. This leads to:

• Redundant sorting operations.
• Inefficient use of the virtual table’s internal optimizations (e.g., partial sorting or indexing).

3. Scalability of Temporary B-Tree Sorting

SQLite’s USE TEMP B-TREE FOR ORDER BY directive indicates that all qualifying rows are collected into an in-memory or disk-based B-tree before applying the LIMIT 500. This approach:

• Scales linearly with the number of filtered rows, not the final limit.
• Incurs overhead from row insertion and tree balancing.
• Fails to exploit early termination opportunities (stopping after 500 sorted rows).

Mitigation Strategies for Efficient Sorting and Filtering

1. Virtual Table Configuration for Pre-Sorted Output

Step 1: Implement xBestIndex to Signal Sorted Output
Modify the virtual table’s xBestIndex method to inspect the ORDER BY clause. If the sort order matches the virtual table’s natural output order (e.g., v.rank ASC), set the orderByConsumed flag to 1. This informs SQLite that no additional sorting is required.

Example Code Snippet for xBestIndex:

if (pOrderBy->nOrderBy == 1 && 
    pOrderBy->a[0].iColumn == COLUMN_RANK && 
    pOrderBy->a[0].desc == 0) {
    pIdxInfo->orderByConsumed = 1;
}

Step 2: Optimize Virtual Table Scans for Partial Sorting
If the virtual table can compute ranks incrementally or leverage indexed data, structure its xFilter method to return rows in v.rank order. Techniques include:

• Maintaining an internal index sorted by rank.
• Using a priority queue to yield the top N rows on-demand.

Step 3: Validate Sorting Behavior
Run EXPLAIN QUERY PLAN to confirm the absence of USE TEMP B-TREE FOR ORDER BY. The ideal plan should show:

SCAN TABLE virtual_table AS v VIRTUAL TABLE INDEX 3:  
SEARCH TABLE base_table AS b USING INTEGER PRIMARY KEY (rowid=?)  

2. Predicate Pushdown to Reduce Base Table Lookups

Step 1: Embed Filtering Logic in the Virtual Table
If the base table filters (b.name LIKE 'foo') can be translated into constraints on the virtual table, push these predicates into the virtual table’s scan phase. For example:

• Add a name_like hidden column to the virtual table that mirrors base_table.name.
• Modify xBestIndex to accept name_like as a constraint and filter rows internally.

Step 2: Use Covering Indexes on Base Table
Create a covering index on base_table that includes all filtered columns and the primary key:

CREATE INDEX idx_base_table_name ON base_table(name, id);  

This reduces the cost of primary key lookups by allowing SQLite to check filter conditions directly from the index.

Step 3: Reorder Query Execution via Subqueries
Force SQLite to filter the base table first by rewriting the query:

SELECT v.id, b.name, v.rank  
FROM (SELECT id FROM base_table WHERE name LIKE 'foo') AS b  
JOIN virtual_table v ON b.id = v.id  
ORDER BY v.rank  
LIMIT 500;  

This approach may not always work due to query planner optimizations, but it can help in some scenarios.

3. Hybrid Sorting with Application-Side Optimization

Step 1: Batch Processing with Window Functions
If the virtual table cannot be modified, use window functions to limit the sorting workload:

SELECT * FROM (  
  SELECT v.id, b.name, v.rank,  
         ROW_NUMBER() OVER (ORDER BY v.rank) AS rn  
  FROM virtual_table v  
  JOIN base_table b ON v.id = b.id  
  WHERE b.name LIKE 'foo'  
) WHERE rn <= 500;  

This still requires full sorting but can be faster due to reduced intermediate storage.

Step 2: Approximate Sorting with Probabilistic Algorithms
For applications tolerant of approximate results, use reservoir sampling or heuristic-based sorting to retrieve a "good enough" subset of rows.

Step 3: Materialize Ranked Results Periodically
Precompute and store the rank column in base_table if the ranking logic is static or updated infrequently. This eliminates the virtual table overhead entirely:

ALTER TABLE base_table ADD COLUMN rank INTEGER;  
UPDATE base_table SET rank = ...;  
CREATE INDEX idx_base_table_rank ON base_table(rank);  

Summary of Critical Fixes and Tradeoffs

By prioritizing virtual table sorting optimizations and predicate pushdown, developers can achieve sub-second query times on million-row datasets. Secondary strategies like covering indexes and query restructuring provide incremental gains but are less transformative. In mission-critical systems, a combination of orderByConsumed signaling and materialized ranks offers the best balance of performance and maintainability.