Avoiding Recursive CTE Materialization in SQLite for Tree Traversal Queries

Understanding Recursive CTE Materialization in Tree Traversal Queries

Issue Overview

The core issue revolves around the behavior of SQLite’s query planner when executing recursive Common Table Expressions (CTEs) for tree traversal queries. Specifically, the problem arises when attempting to traverse an adjacency list-style table (export) to find a specific entry that matches a condition. The table structure is as follows:

CREATE TABLE IF NOT EXISTS "export"
(
  "id" INTEGER NOT NULL,
  "parentId" INTEGER NOT NULL,
  "name" TEXT NOT NULL,
  PRIMARY KEY ("id")
);

The goal is to write a query that starts at a given entry and walks up the tree until it finds an entry that matches a certain condition. The initial query uses a recursive CTE to achieve this:

WITH RECURSIVE
  parents(id) AS NOT MATERIALIZED (
    SELECT parentId FROM export WHERE export.id = 60363923
    UNION ALL
    SELECT export.parentId FROM export JOIN parents ON export.id = parents.id
  )
SELECT export.id, export.parentId FROM parents JOIN export ON parents.id = export.parentId WHERE export.id > 60363923 LIMIT 1;

Despite the NOT MATERIALIZED hint, the query planner materializes the CTE, leading to inefficiencies. The query plan shows that the CTE is materialized, which contradicts the intention of lazy evaluation. The materialization of the CTE results in unnecessary computation and memory usage, especially when the query could theoretically stop early upon finding the desired condition.

The query plan is as follows:

QUERY PLAN
|--MATERIALIZE parents
| |--SETUP
| | `--SEARCH export USING INTEGER PRIMARY KEY (rowid=?)
| `--RECURSIVE STEP
|   |--SCAN parents
|   `--SEARCH export USING INTEGER PRIMARY KEY (rowid=?)
|--SCAN parents
`--SEARCH export USING COVERING INDEX export_parent_id_idx (parentId=? AND rowid>?)

The materialization of the CTE is problematic because it forces the entire recursive result set to be computed before the final SELECT statement can proceed. This behavior is particularly inefficient for large trees or when the desired condition is found early in the traversal.

Possible Causes of CTE Materialization

The materialization of the CTE can be attributed to several factors, including the query planner’s optimization strategies, the structure of the query, and the nature of recursive CTEs in SQLite.

1. Query Planner Optimization Strategies: SQLite’s query planner may choose to materialize the CTE if it determines that materialization will lead to better performance. This decision is based on the planner’s cost estimation, which may not always align with the developer’s expectations. In this case, the planner might believe that materializing the CTE will reduce the number of recursive steps or simplify the query execution.

2. Query Structure: The structure of the query itself can influence the planner’s decision to materialize the CTE. The use of UNION ALL in the recursive CTE can lead the planner to believe that materialization is necessary to avoid redundant computations. Additionally, the presence of a LIMIT clause in the final SELECT statement might not be sufficient to prevent materialization, as the planner may still prioritize computing the entire result set before applying the limit.

3. Nature of Recursive CTEs: Recursive CTEs in SQLite are inherently complex, and the query planner may not always be able to optimize them as efficiently as non-recursive queries. The recursive nature of the query can lead to unpredictable behavior, especially when dealing with large datasets or deep recursion depths. The planner may default to materialization as a way to manage the complexity and ensure correct results.

4. Index Usage: The presence or absence of indexes on the export table can also impact the planner’s decision. In this case, the query uses the primary key index (id) and a covering index (export_parent_id_idx). However, the planner may still choose to materialize the CTE if it believes that the indexes do not provide sufficient optimization for the recursive query.

5. SQLite Version and Configuration: The behavior of the query planner can vary depending on the version of SQLite and its configuration settings. Certain versions may have different optimization strategies or bugs that affect how recursive CTEs are handled. Additionally, configuration settings such as the query_only pragma or the temp_store setting can influence the planner’s decisions.

Troubleshooting Steps, Solutions & Fixes

To address the issue of CTE materialization and achieve lazy evaluation, several approaches can be considered. These include restructuring the query, using alternative query techniques, and leveraging SQLite’s features to influence the query planner’s behavior.

1. Restructuring the Query: One approach is to restructure the query to make it more amenable to lazy evaluation. This can be achieved by modifying the CTE to store the results of interest and avoid redundant searches. For example:

WITH parents(pid, cid)
 AS (
     SELECT parentId,
        id
      FROM export
     WHERE export.id = 60363923
   UNION ALL
     SELECT export.parentId,
        export.id
      FROM parents, export
     WHERE export.id = parents.pid
   )
SELECT cid,
    pid
 FROM parents
 WHERE cid > 60363923
 LIMIT 1;

This query avoids materializing the CTE entirely up front, as indicated by the query plan:

QUERY PLAN
|--CO-ROUTINE parents
| |--SETUP
| | `--SEARCH export USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
| `--RECURSIVE STEP
|   |--SCAN parents (~1048576 rows)
|   `--SEARCH export USING INTEGER PRIMARY KEY (rowid=?) (~1 row)
`--SCAN parents (~983040 rows)

However, as noted in the discussion, this approach may still be less efficient due to the way the recursive steps are executed. Each recursive step is executed in its entirety, which can lead to inefficiencies, especially if the desired condition is not found early in the traversal.

2. Using CROSS JOIN to Force Evaluation Order: Another approach is to use CROSS JOIN to force the evaluation order of the query. This can help ensure that the recursive CTE is evaluated lazily, as intended. For example:

WITH RECURSIVE
  parents(id) AS NOT MATERIALIZED (
    SELECT parentId FROM export WHERE export.id = 60363923
    UNION ALL
    SELECT export.parentId FROM export CROSS JOIN parents ON export.id = parents.id
  )
SELECT export.id, export.parentId FROM parents CROSS JOIN export ON parents.id = export.parentId WHERE export.id > 60363923 LIMIT 1;

This approach produces a VDBE trace that aligns with the desired behavior, with fewer opcodes executed compared to the original query. The use of CROSS JOIN forces the query planner to evaluate the CTE lazily, resulting in more efficient execution.

3. Leveraging Indexes and Table Properties: Given the specific properties of the export table, it is possible to leverage these properties to optimize the query further. For example, since the rows are inserted in depth-first order with incrementing IDs, the query can be structured to take advantage of this ordering. This can help reduce the number of recursive steps required to find the desired condition.

4. Using Alternative Query Techniques: In some cases, it may be more efficient to use alternative query techniques, such as nested set models or closure tables, instead of recursive CTEs. These techniques can provide more predictable performance and avoid the pitfalls of recursive queries. However, they may require additional preprocessing or changes to the table structure.

5. Influencing the Query Planner: SQLite provides several ways to influence the query planner’s behavior, such as using the INDEXED BY clause or adjusting the ANALYZE statistics. These techniques can help guide the planner towards more efficient execution plans. Additionally, using the EXPLAIN and EXPLAIN QUERY PLAN commands can provide insights into the planner’s decisions and help identify potential optimizations.

6. Debugging and Tracing: To better understand why the query planner chooses to materialize the CTE, it is helpful to use SQLite’s debugging and tracing features. The VDBE trace can provide detailed information about the execution of the query, including the number of opcodes executed and the order of operations. This information can be used to identify inefficiencies and guide further optimizations.

7. Testing and Benchmarking: Finally, it is essential to test and benchmark different query structures and techniques to determine the most efficient approach for the specific use case. This can involve running the queries on representative datasets and measuring their performance in terms of execution time, memory usage, and resource consumption.

In conclusion, the issue of recursive CTE materialization in SQLite can be addressed through a combination of query restructuring, alternative techniques, and careful optimization. By understanding the underlying causes and leveraging SQLite’s features, it is possible to achieve efficient and lazy evaluation of recursive queries for tree traversal.