Virtual Table xBestIndex Cost Estimation for ORDER BY Optimization

Virtual Table Query Planning: ORDER BY, Index Selection, and Cost Estimation Tradeoffs

The interaction between SQLite’s query planner and virtual table implementations hinges on accurate cost estimation within the xBestIndex method. A core challenge arises when optimizing queries involving ORDER BY clauses, where the virtual table must evaluate whether using an index that inherently satisfies the sort order (at a higher scan cost) is preferable to a lower-cost index scan that necessitates a subsequent sort operation. This dilemma becomes acute when no constraints (e.g., WHERE, LIMIT, OFFSET) are present to reduce the result set size, forcing the virtual table to estimate costs for full-table scans under competing access patterns.

Virtual Table Index Selection Mechanics and ORDER BY Cost Penalties

SQLite delegates index selection and cost estimation for virtual tables to the xBestIndex method. When a query includes an ORDER BY clause, SQLite communicates the desired sort order to the virtual table through the aOrderBy array in the sqlite3_index_info structure. Each entry in this array specifies a column index and sort direction (ascending/descending). The virtual table must then evaluate which of its available indexes can satisfy the requested order, either fully or partially, and calculate the cost of returning rows in that order.

The critical nuance lies in the fact that indexes inherently ordered by the ORDER BY columns eliminate the need for SQLite to perform a separate sorting step. However, if the virtual table chooses an index that does not match the ORDER BY order, SQLite must buffer the entire result set and sort it in-memory or via a temporary disk file. The cost of this sorting operation is not directly known to the virtual table, as it depends on factors like the number of rows returned, available memory, and the efficiency of SQLite’s internal sorting algorithms. Consequently, the virtual table must anticipate this penalty and incorporate it into its cost estimates when comparing index access paths.

A common pitfall occurs when the virtual table reports the raw scan cost of an index that satisfies the ORDER BY clause without accounting for the inherent benefit of avoiding a sort. For example, consider a virtual table with a primary index (unordered scan, cost C) and a secondary index (ordered by last_used, cost D). If D > C because the secondary index requires additional I/O to retrieve pload data from the primary index, the virtual table might erroneously select the primary index, assuming lower cost. However, this ignores the sorting penalty S that SQLite will incur. The effective cost of using the primary index becomes C + S, which may exceed D if S is significant. The virtual table must therefore estimate S and include it in the cost comparison.

Key Variables in Cost Estimation:

1. Index Scan Cost (C, D): The resource expenditure (CPU, I/O) to retrieve rows via a specific index. This often correlates with the index’s storage structure and the number of rows scanned.
2. Sorting Penalty (S): The overhead of sorting N rows in-memory or on disk. This grows superlinearly with N due to comparison and swapping operations.
3. Result Set Cardinality (N): The total number of rows the virtual table expects to return. Without constraints, N equals the table’s total row count.
4. LIMIT/OFFSET Constraints: When present, these reduce N to LIMIT (if OFFSET is small relative to total rows), allowing the virtual table to prioritize indexes that minimize scanned rows over those that avoid sorting.

Misaligned Cost Estimation Heuristics in xBestIndex

The root cause of suboptimal index selection in xBestIndex often stems from incomplete or misweighted cost factors. Specifically, the virtual table implementation may fail to:

1. Differentiate Between Ordered and Unordered Scan Costs: Treating the base scan cost of an index as the sole determinant without considering whether the index order matches the ORDER BY clause. An index that satisfies the sort order should have its cost compared against the sum of a cheaper index’s scan cost plus the estimated sorting penalty.

   Example: If Index A (unordered) has a scan cost of 100 units and Index B (ordered) has a scan cost of 150 units, but sorting 1000 rows via Index A incurs a penalty of 75 units, the effective cost of Index A becomes 175 units, making Index B preferable despite its higher raw scan cost.

2. Incorporate Sorting Penalties Proactively: Relying on SQLite to infer the need for sorting and adjust the plan accordingly. SQLite’s query planner lacks visibility into the virtual table’s internal data organization and assumes the xBestIndex cost reflects the total expenditure, including implicit sorting. If the virtual table does not inflate the cost of unordered scans by S, SQLite will erroneously favor them.

3. Leverage LIMIT/OFFSET Constraints to Mitigate Sorting Impact: When a LIMIT clause restricts the result set to a small subset of rows, the sorting penalty S becomes proportional to LIMIT (if the entire result can be sorted in-memory). The virtual table should reduce the estimated S in such cases, making unordered scans with low C more attractive even if they require sorting a small number of rows.

4. Handle Edge Cases with Large OFFSET Values: Queries with OFFSET exceeding the total row count return zero rows, rendering both scan and sorting costs moot. The virtual table should detect this scenario via SQLITE_INDEX_CONSTRAINT_OFFSET constraints and report a near-zero cost, as no rows need processing.

5. Account for Composite Indexes and Partial Order Matching: If an index provides partial order alignment with the ORDER BY clause (e.g., sorting by last_used DESC when ORDER BY last_used ASC is requested), the virtual table must compute the residual sorting cost for the mismatched portion and adjust the index’s total cost accordingly.

Strategic Adjustments to xBestIndex for Optimal ORDER BY Handling

To align virtual table cost estimates with SQLite’s query planning expectations, implement the following steps in the xBestIndex method:

Step 1: Evaluate Index Order Compatibility with ORDER BY

For each available index, determine whether it can satisfy the ORDER BY clause in whole or in part. An index matches the ORDER BY requirement if:

• The index columns are a prefix of the ORDER BY columns.
• The sort directions (ASC/DESC) for these columns match exactly.

Example: For ORDER BY last_used ASC, hash ASC, an index on (last_used ASC, hash ASC) provides a full match, while an index on (last_used ASC) offers a partial match (requiring additional sorting on hash).

Step 2: Compute Base Scan Cost for Each Index

Calculate the raw cost of scanning the index and retrieving required columns. This should reflect:

• Sequential vs. random I/O patterns.
• The number of rows scanned (full table scan vs. constrained by WHERE).
• Overhead of fetching out-of-index columns (e.g., using the primary index to retrieve pload when scanning a secondary index).

For the pcache table example:

• Scanning the primary index (hash) involves reading all N rows in primary key order, with direct access to pload and last_used (cost C).
• Scanning the secondary index (last_used) requires reading N index entries, then fetching pload from the primary index for each row (cost D).

Step 3: Estimate Sorting Penalty for Non-Matching Indexes

If an index does not satisfy the ORDER BY clause, estimate the penalty S for SQLite to sort the result set. Use the following heuristic:

S = (N * log2(N)) * sort_cost_per_row

Where sort_cost_per_row is an empirical constant representing the CPU and memory overhead per row during sorting. For simplicity, assume sort_cost_per_row = 0.1 (adjust based on benchmarking).

Example: For N = 1000, S = 1000 * log2(1000) * 0.1 ≈ 1000 * 10 * 0.1 = 1000 units.

Add S to the base scan cost of indexes that do not satisfy ORDER BY.

Step 4: Apply LIMIT/OFFSET Adjustments

If the query includes LIMIT L and OFFSET O constraints:

• Adjust the estimated number of rows processed (N' = L + O).
• If O >= total_rows, set N' = 0.
• Recompute the sorting penalty using N' instead of N.

Example: With LIMIT 10 and OFFSET 5, N' = 15. Sorting penalty becomes 15 * log2(15) * 0.1 ≈ 15 * 4 * 0.1 = 6 units.

Step 5: Select the Index with the Lowest Effective Cost

Compare the effective costs (base cost + sorting penalty if applicable) of all indexes. Choose the index with the minimum effective cost and populate the sqlite3_index_info structure accordingly:

// Example xBestIndex implementation snippet
double effective_cost;
for (each index) {
  if (index_matches_order_by) {
    effective_cost = base_cost;
  } else {
    effective_cost = base_cost + sorting_penalty;
  }
  if (effective_cost < best_cost) {
    best_cost = effective_cost;
    best_index = current_index;
  }
}
sqlite3_index_info.idxNum = best_index;
sqlite3_index_info.estimatedCost = best_cost;

Step 6: Signal ORDER BY Satisfaction to SQLite

If the chosen index satisfies the ORDER BY clause, set the sqlite3_index_info.orderByConsumed flag to 1. This informs SQLite that no additional sorting is needed.

if (best_index_matches_order_by) {
  sqlite3_index_info.orderByConsumed = 1;
}

Step 7: Benchmark and Calibrate Cost Constants

Empirically determine the sort_cost_per_row and index scan cost ratios by running representative queries and comparing execution times. Adjust the cost formulas to reflect observed behavior, ensuring that the virtual table’s cost estimates correlate with actual performance.

Example calibration process:

1. Execute SELECT * FROM pcache ORDER BY last_used; with forced primary index usage.
2. Measure execution time T1 (scan + sort).
3. Execute the same query with forced secondary index usage.
4. Measure execution time T2 (scan without sort).
5. Set sort_cost_per_row = (T1 - T_primary_scan) / (N * log2(N)).

Step 8: Handle Edge Cases and Constraints

• Large OFFSET Values: If OFFSET exceeds the total row count, set estimatedRows to 0 and estimatedCost to a minimal value (e.g., 1e-6).
• Composite ORDER BY Requirements: For partial index matches, compute the residual sorting penalty based on the unmatched suffix of the ORDER BY clause.
• Mixed ASC/DESC Orders: Apply sorting penalties even if the index column order matches but the sort directions differ (e.g., index on last_used ASC vs. ORDER BY last_used DESC).

Step 9: Integrate with SQLite’s Cost Model

SQLite’s query planner uses the estimatedCost value to compare virtual table access paths with native B-tree scans. Ensure the virtual table’s cost units are consistent with SQLite’s internal cost model, where a cost of N represents the estimated number of disk access operations. Scale sort_cost_per_row accordingly (e.g., treat one disk access as 100 units).

Step 10: Validate with EXPLAIN QUERY PLAN

After implementing the adjustments, use EXPLAIN QUERY PLAN to verify that SQLite selects the expected index and avoids sorting when orderByConsumed is set.

EXPLAIN QUERY PLAN
SELECT * FROM pcache ORDER BY last_used;

-- Expected output with correct xBestIndex:
-- SCAN TABLE pcache VIRTUAL TABLE INDEX 2:last_used

If the output shows USE TEMP B-TREE FOR ORDER BY, the virtual table failed to signal that the index satisfies the ORDER BY.

Conclusion

Optimizing xBestIndex cost estimation for ORDER BY clauses requires a holistic approach that balances index scan efficiency with the hidden costs of post-processing. By explicitly modeling sorting penalties and leveraging query constraints, virtual table implementations can guide SQLite’s query planner toward optimal access paths. Regular benchmarking against real-world workloads ensures cost heuristics remain aligned with actual performance characteristics, preventing suboptimal plans in production environments.