Recursive CTE Performance: GROUP BY vs. DISTINCT Optimization in SQLite

Understanding Query Plan Divergence in Recursive CTEs with DISTINCT vs. GROUP BY

The core issue revolves around a recursive Common Table Expression (CTE) in SQLite where replacing SELECT DISTINCT with an equivalent GROUP BY clause drastically altered the query execution plan, improving performance. The original query used SELECT DISTINCT dst AS root FROM mandatory, which resulted in a cross join (Cartesian product) between the roots CTE and the internal table. When changed to GROUP BY dst, SQLite utilized an autoindex search for both parts of the recursive CTE, avoiding the cross join. This divergence in query plan behavior highlights subtle optimizer decisions that depend on syntactic choices even when the logical outcomes of DISTINCT and GROUP BY are identical.

Key Observations from the Scenario

• Recursive CTE Structure: The query defines a roots CTE to identify unique dst values from the mandatory table, followed by a rooted1 CTE that recursively traverses an internal table hierarchy starting from these roots.
• Materialization Hints: Both CTEs use the MATERIALIZED keyword, forcing SQLite to store intermediate results in temporary storage.
• Execution Plan Shift: With DISTINCT, the non-recursive part of rooted1 generated a cross join between roots and internal. With GROUP BY, SQLite employed autoindexes for efficient lookups in both the non-recursive and recursive parts of rooted1.

This behavior raises critical questions about how SQLite’s optimizer interprets uniqueness constraints, handles temporary result sets, and prioritizes join strategies in hierarchical queries. The distinction between DISTINCT and GROUP BY here is not merely academic—it directly impacts the physical execution steps, leading to orders-of-magnitude differences in performance.

Root Causes of Execution Plan Variance Between DISTINCT and GROUP BY

1. Optimizer’s Cost Estimation for Uniqueness Enforcement

SQLite’s query optimizer treats DISTINCT and GROUP BY differently when estimating the cost of enforcing uniqueness. While both clauses eliminate duplicates, their implementation pathways diverge:

• DISTINCT: Implicitly sorts the result set to identify and remove duplicates. This sorting operation may not always leverage existing indexes, especially if the column isn’t indexed or the optimizer deems a full scan cheaper.
• GROUP BY: Explicitly groups rows by the specified column(s), which can trigger the use of indexes if available. When an index exists on the grouping column, SQLite may perform an index scan instead of a full table scan, reducing I/O and computation.

In the roots CTE, GROUP BY dst likely allowed the optimizer to recognize that an index on mandatory.dst (if present) could be used for grouping, whereas DISTINCT dst was treated as a generic uniqueness constraint requiring a sort. This difference cascaded into the rooted1 CTE’s join strategy.

2. Temporary Result Set Materialization and Indexability

The MATERIALIZED keyword ensures that the CTE’s results are stored in a temporary table. However, the structure of this temporary table depends on how the data is processed:

• With DISTINCT: The temporary table may lack implicit ordering or indexable properties, forcing the optimizer to treat it as an unordered set. This leads to inefficient join strategies like cross joins when joining with other tables (e.g., internal).
• With GROUP BY: The grouping operation may implicitly order the results or create a structure that SQLite’s autoindexing mechanism can exploit. Autoindexes are transient indexes created on-the-fly for temporary tables, enabling faster lookups during joins.

The absence of an exploitable index on the roots CTE’s root column when using DISTINCT forced SQLite to resort to a cross join. With GROUP BY, the autoindex on root allowed indexed lookups when joining with internal.src.

3. Recursive CTE-Specific Optimization Constraints

Recursive CTEs in SQLite have unique optimization challenges:

• Non-Recursive vs. Recursive Term Handling: The non-recursive term (the first part of rooted1) is evaluated once, while the recursive term (the second part) iterates until no more rows are produced. The optimizer must choose a join strategy that balances initial computation cost with iterative efficiency.
• Dependency on Base CTE’s Structure: The execution plan for the recursive term is influenced by the schema and indexing of the base CTE (roots). If the base CTE’s results are not index-friendly, the recursive joins may default to nested loops or cross products.

In this case, the cross join in the non-recursive term with DISTINCT created a combinatorial explosion, as every row in roots was paired with every row in internal before filtering. The autoindex-enabled plan with GROUP BY allowed direct lookups, drastically reducing the number of processed rows.

Diagnosing and Resolving Suboptimal Join Strategies in Hierarchical Queries

Step 1: Analyze Query Plans with EXPLAIN and EXPLAIN QUERY PLAN

Use SQLite’s built-in query plan visualization tools to compare the execution steps for both DISTINCT and GROUP BY variants:

-- For DISTINCT variant
EXPLAIN QUERY PLAN
WITH RECURSIVE
  roots AS MATERIALIZED (SELECT DISTINCT dst AS root FROM mandatory),
  rooted1 AS MATERIALIZED (...)
SELECT * FROM rooted1;

-- For GROUP BY variant
EXPLAIN QUERY PLAN
WITH RECURSIVE
  roots AS MATERIALIZED (SELECT dst AS root FROM mandatory GROUP BY dst),
  rooted1 AS MATERIALIZED (...)
SELECT * FROM rooted1;

• Cross Join Detection: Look for SCAN TABLE or CROSS JOIN in the non-recursive term’s plan, indicating a lack of index usage.
• Autoindex Identification: Check for USING AUTOMATIC COVERING INDEX or SEARCH TABLE USING INDEX in the GROUP BY plan, confirming indexed lookups.

Step 2: Force Index Usage on Critical Columns

Ensure that the mandatory.dst and internal.src columns are indexed:

CREATE INDEX idx_mandatory_dst ON mandatory(dst);
CREATE INDEX idx_internal_src ON internal(src);

Indexes on these columns allow the optimizer to:

• Accelerate Grouping: Use idx_mandatory_dst for the GROUP BY operation in roots.
• Optimize Joins: Perform indexed nested loop joins between roots.root and internal.src.

Step 3: Evaluate Materialization Necessity

The MATERIALIZED keyword forces CTE result storage but can sometimes hinder optimization. Test without materialization:

WITH RECURSIVE
  roots AS (SELECT dst AS root FROM mandatory GROUP BY dst),
  rooted1 AS (...)
SELECT * FROM rooted1;

If the query plan remains efficient, materialization may not be necessary. However, in complex recursive queries, materialization prevents repeated computation of the base CTE.

Step 4: Syntactic Transformations to Guide the Optimizer

• Prefer GROUP BY Over DISTINCT: When possible, use GROUP BY for uniqueness enforcement, as it provides explicit grouping semantics that the optimizer can exploit.
• Leverage Covering Indexes: Include all columns referenced in the CTE’s SELECT clause to create covering indexes, eliminating table accesses:

  CREATE INDEX idx_mandatory_dst_covering ON mandatory(dst, src, representative);
  

Step 5: Monitor and Adjust Optimizer Heuristics

SQLite’s optimizer relies on cost estimates based on table statistics. Outdated or missing statistics can lead to poor plan choices. Use ANALYZE to refresh statistics:

ANALYZE;

This updates the sqlite_stat1 table, providing the optimizer with accurate row count and distribution data.

Step 6: Consider Query Structure Refactoring

If performance remains suboptimal, restructure the recursive CTE:

• Pre-Filter Redundant Rows: Add WHERE clauses in the non-recursive term to reduce the initial row set.
• Limit Recursion Depth: Use LIMIT clauses (if logically permissible) to cap iteration counts.

Final Recommendations

1. Index Critical Join Columns: Ensure dst in mandatory and src in internal are indexed.
2. Use GROUP BY for Uniqueness in CTEs: Prefer GROUP BY over DISTINCT when working with hierarchical or recursive queries.
3. Validate Materialization Impact: Test CTEs with and without MATERIALIZED to determine if temporary storage aids or hinders performance.
4. Regular Statistics Updates: Run ANALYZE periodically to keep the optimizer informed of data distribution changes.

By systematically applying these steps, developers can mitigate the risk of suboptimal join strategies in recursive CTEs and harness SQLite’s autoindexing capabilities to achieve efficient query execution.