Creating an Infinite Recursive Query in SQLite Without Memory Consumption for Interrupt Testing

Infinite Recursive Query Execution Without Result Accumulation

Issue Overview

The challenge involves designing a SQLite recursive Common Table Expression (CTE) query that runs indefinitely for testing the sqlite3_interrupt API while avoiding excessive memory allocation. The original attempt used a recursive CTE to generate an infinite sequence, but it suffered from unbounded memory growth due to result set accumulation. For example, the initial approach materialized all intermediate results in memory via SELECT 1 IN a, forcing SQLite to store every generated row. This creates a practical limitation for interrupt testing, as memory exhaustion occurs before the interrupt can be reliably triggered. The goal is to construct a query that keeps the SQLite virtual machine (VM) busy in a computational loop without storing intermediate results or exhausting system resources.

Recursive CTE Mechanics and Memory Constraints

SQLite’s recursive CTEs operate in two phases: the initial "seed" query and the iterative "recursive" query. Each iteration appends new rows to the CTE’s result set. By default, SQLite allows up to SQLITE_MAX_RECURSIVE_DEPTH (default: 1000) iterations. However, even with a high recursion limit, queries that materialize large result sets (e.g., UNION ALL SELECT * FROM a) will allocate memory proportional to the number of generated rows. The sqlite3_interrupt function halts long-running queries by setting a flag checked at strategic points in the VM’s instruction cycle. For interrupt testing to work predictably, the query must keep the VM in a tight computational loop without pausing for disk I/O, transaction locks, or memory allocation.

The solution proposed in the discussion uses a recursive CTE that generates an infinite sequence but discards all rows via a WHERE clause that never evaluates to true. This forces SQLite to repeatedly compute the recursive step without retaining rows in memory. The critical insight is that the VM remains occupied with query execution, while the result set remains empty, preventing memory bloat. However, subtle details in CTE structure, recursion limits, and VM optimizations influence whether this approach works as intended.

Solutions for Infinite Execution with Minimal Memory

Step 1: Use a Recursive CTE with a Contrived Termination Condition
The following query creates an infinite loop by defining a recursive CTE that generates incrementing values but filters out all rows in the final SELECT:

WITH RECURSIVE c(x) AS (
  VALUES(1) 
  UNION ALL 
  SELECT x+1 FROM c
)
SELECT x FROM c WHERE x < 0;

The WHERE x < 0 clause ensures no rows are emitted, but the recursive CTE continues generating values indefinitely. SQLite optimizes this by avoiding materializing the result set, as no rows match the filter. The VM executes the recursive steps in a loop, making it responsive to sqlite3_interrupt.

Step 2: Disable Recursion Depth Limits
By default, SQLite terminates recursive CTEs after 1000 iterations. To create an infinite loop, override this limit before executing the query:

PRAGMA recursive_triggers = 1; -- Enable deep recursion if needed
PRAGMA max_recursive_depth = 0; -- Set to 0 for unlimited recursion

Note that setting max_recursive_depth to 0 may not be supported in all SQLite builds. If recursion limits persist, use a loop that regenerates the CTE after hitting the limit.

Step 3: Validate VM Behavior with EXPLAIN
Use EXPLAIN to verify that the query plan avoids materializing intermediate results. The output should show a cyclic pattern in the program steps (e.g., Goto instructions looping back to earlier opcodes):

EXPLAIN WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c) SELECT x FROM c WHERE x < 0;

Look for opcodes like OpenEphemeral (creating temporary tables) or AggStep (aggregation). If present, revise the query to eliminate temporary storage.

Step 4: Cross-Join Recursive CTEs for Busy Loops
For more aggressive CPU utilization, cross-join multiple recursive CTEs. This increases the VM’s workload per iteration, reducing the interrupt latency:

WITH RECURSIVE
  c1(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c1),
  c2(y) AS (VALUES(1) UNION ALL SELECT y+1 FROM c2)
SELECT x, y FROM c1, c2 WHERE x = y AND x < 0;

The Cartesian product of c1 and c2 amplifies computational effort without producing output rows.

Step 5: Use Subqueries with No-Op Functions
Incorporate deterministic functions with minimal overhead to simulate work:

WITH RECURSIVE c(x) AS (
  VALUES(1) 
  UNION ALL 
  SELECT abs(x+1) FROM c
)
SELECT x FROM c WHERE x < 0;

The abs() function adds trivial computation, keeping the VM busy without altering the result.

Step 6: Benchmark Interrupt Latency
Measure the time between calling sqlite3_interrupt and query termination using system-specific timing tools. Adjust the query complexity (e.g., adding more recursive terms or mathematical operations) to achieve the desired interrupt responsiveness.

Final Query Template for Interrupt Testing

PRAGMA max_recursive_depth = 0;
WITH RECURSIVE c(x) AS (
  VALUES(1) 
  UNION ALL 
  SELECT (x + 1) % 1000000 FROM c
)
SELECT x FROM c WHERE x < 0;

This query avoids integer overflow and ensures the VM remains in a computational loop. The modulo operation (% 1000000) prevents arithmetic exceptions while maintaining a constant CPU load.