Optimizing Recursive CTE Termination in SQLite Piece Table Queries

Understanding Recursive Query Termination in Piece Table Position Lookups

Core Challenge: Efficiently Locating Document Range Boundaries in a Piece Table

The primary challenge revolves around determining whether a recursive common table expression (CTE) in SQLite terminates early when searching for specific document position ranges within a piece table structure. The piece table contains fragments ("pieces") of text from original and append buffers, ordered by a keyOrder array stored in a separate mapping table. Each piece’s document position is derived from the cumulative sum of lengths of preceding pieces. The goal is to identify the minimal set of pieces that span a target document range (e.g., positions 500–800) without computing cumulative sums for all pieces, mimicking an application-level loop that exits early once the range boundaries are found.

Key entities:

1. Piece Table (pt_pieces): Stores individual text fragments with metadata (key, buffer source, buffer start, length).
2. Mapping Table (pt_map): Defines active pieces and their order via a JSON array (keyOrder).
3. Recursive CTE Queries: Four variants that traverse the keyOrder array to compute cumulative lengths and locate range boundaries.

Why Recursive CTE Termination Behavior Matters

Recursive CTEs in SQLite operate as iterative loops, with each iteration processing rows generated in the previous step. Termination occurs when no new rows are added. Inefficient termination leads to:

• Unnecessary traversal of the entire keyOrder array.
• Redundant computation of cumulative lengths for irrelevant pieces.
• Performance degradation as the piece table grows (common in text editors with frequent edits).

The provided recursive queries include termination conditions (e.g., pieces.len + pieces.bgn <= 800). However, ambiguity exists about whether these conditions halt iteration immediately upon satisfying the target range or process additional rows.

Diagnosing Premature or Delayed CTE Termination

1. Misaligned Termination Conditions in Recursive CTE Logic

Recursive CTEs consist of an initial anchor member and a recursive member. The anchor starts the iteration, while the recursive member references the CTE itself. SQLite executes these steps:

1. Run the anchor query.
2. Repeatedly run the recursive query using the prior iteration’s results until no new rows are produced.

Example Analysis (Method 1 Query):

WITH RECURSIVE pieces(orderIdx, key, buffer, start, len, bgn) AS (
  SELECT 0, pt_pieces.*, 0 
  FROM pt_pieces
  WHERE pt_pieces.key = (SELECT keyOrder->>0 FROM pt_map)
  UNION ALL
  SELECT orderIdx + 1, pt.*, pieces.len + pieces.bgn
  FROM pt_pieces AS pt, pieces
  WHERE pt.key = (SELECT keyOrder->>(orderIdx+1) FROM pt_map)
    AND pieces.len + pieces.bgn <= 800  -- Termination condition
)
SELECT * FROM pieces WHERE 500 BETWEEN bgn AND bgn + len - 1 OR 800 BETWEEN bgn AND bgn + len - 1;

• Anchor Member: Fetches the first piece (keyOrder[0]) with bgn=0.
• Recursive Member: Joins the current piece with the next piece in keyOrder, accumulating bgn (cumulative length).
• Termination Condition: pieces.len + pieces.bgn <= 800 stops iteration once the cumulative length exceeds 800.

Problem: The condition pieces.len + pieces.bgn <= 800 controls whether the next piece is added to the CTE. However, the final SELECT applies an additional filter (WHERE 500 BETWEEN ... OR 800 BETWEEN ...), which may suggest that the CTE processes more rows than necessary.

Critical Questions:

• Does the recursive member stop iterating as soon as bgn exceeds 800, or does it continue until no more rows match the join condition?
• How does SQLite optimize the subquery (SELECT keyOrder->>(orderIdx+1) FROM pt_map) during recursion?

2. Indexing and Subquery Overhead in KeyOrder Traversal

The recursive member joins pt_pieces using a dynamically computed key from pt_map’s JSON array. Each iteration requires:

1. Extracting keyOrder->>(orderIdx+1) from the JSON array.
2. Searching pt_pieces for the corresponding key.

Without an index on pt_pieces.key, this search becomes a full table scan, degrading performance. Even with an index, repeated JSON extraction may introduce overhead.

3. Directional Traversal and Range Proximity Assumptions

The four query variants attempt to optimize traversal by starting near the target range (e.g., "last edit" positions). For example:

• Method 2: Starts at orderIdx=9 (bgn=339) and traverses upward.
• Method 3: Starts at orderIdx=42 (bgn=1351) and traverses downward.

Assumptions here include:

• The "last edit" position is closer to the target range than the start/end of the document.
• Traversal in one direction (up/down) will encounter the target range sooner.

However, if the traversal direction is incorrect (e.g., starting below the range and moving upward when the target is far above), the CTE may still process many rows.

Resolving Inefficient Recursive CTE Execution

Step 1: Verify Termination Conditions with EXPLAIN and Intermediate Output

Use EXPLAIN QUERY PLAN to analyze how SQLite executes the recursive CTE:

EXPLAIN QUERY PLAN
WITH RECURSIVE ... -- Insert CTE here

Look for:

• Loops: The number of iterations performed.
• Index Usage: Whether pt_pieces.key is indexed.
• Early Termination: If the WHERE clause in the recursive member limits iterations.

Practical Test:
Modify the CTE to include a debug column showing iteration count:

WITH RECURSIVE pieces(iter, orderIdx, key, ..., bgn) AS (
  SELECT 1 AS iter, 0, ...  -- Anchor
  UNION ALL
  SELECT iter + 1, orderIdx + 1, ...  -- Recursive
)
SELECT MAX(iter) AS total_iterations FROM pieces;

Run this for each query variant to compare iteration counts.

Step 2: Optimize KeyOrder Access with Materialized JSON Arrays

Repeated JSON parsing in keyOrder->>(orderIdx+N) is inefficient. Materialize the keyOrder array into a temporary indexed table:

CREATE TEMP TABLE key_order AS 
SELECT key, value AS keyOrder_idx
FROM pt_map, json_each(pt_map.keyOrder);
CREATE INDEX idx_key_order ON key_order(keyOrder_idx);

Rewrite the CTE to use this table:

WITH RECURSIVE pieces(...) AS (
  SELECT ... 
  FROM pt_pieces 
  WHERE pt_pieces.key = (SELECT key FROM key_order WHERE keyOrder_idx = 0)
  UNION ALL
  SELECT ...
  FROM pt_pieces AS pt
  JOIN key_order ON pt.key = key_order.key
  WHERE keyOrder_idx = pieces.orderIdx + 1
)

This reduces JSON parsing overhead and leverages indexing.

Step 3: Implement Bidirectional Search with Early Exit

Combine upward and downward traversals into a single CTE that halts once both range boundaries are found:

WITH RECURSIVE pieces(...) AS (
  -- Anchor: Start at last edit position
  UNION ALL
  -- Recursive Up
  UNION ALL
  -- Recursive Down
)
SELECT * FROM pieces 
WHERE (500 BETWEEN bgn AND bgn + len - 1)
   OR (800 BETWEEN bgn AND bgn + len - 1)
LIMIT 2;  -- Stop after finding two pieces

Note: SQLite does not support LIMIT in recursive CTEs, but you can track found pieces using a flag:

WITH RECURSIVE pieces(..., found) AS (
  SELECT ..., 0 AS found
  UNION ALL
  SELECT ..., 
    CASE WHEN (new_bgn BETWEEN 500 AND 800) THEN 1 ELSE 0 END
  FROM ...
  WHERE found < 2
)

Step 4: Benchmark Against Window Function Approach

Compare the performance of the recursive CTE against the window function approach using EXPLAIN QUERY PLAN and runtime measurements. For large datasets, the recursive CTE should outperform the window function if termination occurs early.

Step 5: Index pt_pieces.key and pt_map.keyOrder

Ensure pt_pieces.key has an index:

CREATE INDEX idx_pt_pieces_key ON pt_pieces(key);

For pt_map, consider storing keyOrder as a separate table with pre-split keys and indexes:

CREATE TABLE pt_map_order (
  doc_id INTEGER,  -- If multiple documents
  ord INTEGER PRIMARY KEY,
  key INTEGER,
  FOREIGN KEY(key) REFERENCES pt_pieces(key)
);

Final Recommendations

1. Use Materialized KeyOrder Arrays: Avoid repeated JSON parsing.
2. Index Critical Columns: Ensure pt_pieces.key and keyOrder ordinals are indexed.
3. Bidirectional Search with State Tracking: Implement logic to terminate recursion once both start and end pieces are found.
4. Benchmark and Profile: Use EXPLAIN QUERY PLAN and iteration counting to verify early termination.

By aligning termination conditions with traversal logic and optimizing data access patterns, recursive CTEs can efficiently locate document ranges in piece tables without scanning the entire dataset.