Slow Performance in SQLite UNION ALL with CTEs and Joins

Issue Overview: Slow Execution of UNION ALL with Common Table Expressions (CTEs) and Indexed Joins

The core issue revolves around the unexpected performance degradation observed when combining the results of two queries using UNION ALL in SQLite. Both individual queries execute in a fraction of a second, but their combination using UNION ALL results in significantly slower execution, taking minutes or more. This behavior is counterintuitive, as one would expect the combined query to execute in approximately the sum of the durations of the individual queries.

The individual queries involve Common Table Expressions (CTEs) and indexed joins. The first query (w_c) joins the rel_mem table with the tag table on way_id, while the second query (n_c) joins the same rel_mem table with the tag table on nod_id. Both queries group their results by the k column and return aggregated counts. The execution plans for the individual queries show efficient use of indexes and temporary B-trees for grouping.

However, when these queries are combined using UNION ALL, the execution plan changes significantly. The combined query plan indicates that the rel CTE is materialized, and the w_c subquery scans the tag table using an index on k and v, which is not optimal for the join condition. This suggests that the query planner is not able to maintain the same level of optimization when the queries are combined, leading to the observed performance degradation.

Possible Causes: Query Planner Behavior, Index Usage, and Materialization of CTEs

The primary cause of the performance issue lies in the behavior of the SQLite query planner when handling UNION ALL with CTEs and indexed joins. The query planner’s decisions regarding index usage, materialization of CTEs, and the order of operations can significantly impact performance.

One possible cause is the materialization of the rel CTE in the combined query. In the individual queries, the rel CTE is not materialized, and the joins are performed directly using the appropriate indexes. However, in the combined query, the rel CTE is materialized, which may lead to additional overhead, especially if the rel_mem table contains a large number of rows.

Another potential cause is the change in index usage in the combined query. The execution plan for the combined query shows that the w_c subquery scans the tag table using an index on k and v, rather than the index on way_id used in the individual query. This suggests that the query planner is not able to maintain the same index usage strategy when the queries are combined, leading to less efficient joins.

Additionally, the query planner may be making suboptimal decisions regarding the order of operations in the combined query. The execution plan indicates that the rel CTE is scanned before the joins are performed, which may result in a larger intermediate result set and increased processing time.

Troubleshooting Steps, Solutions & Fixes: Optimizing Query Structure, Indexes, and Query Planner Hints

To address the performance issue, several troubleshooting steps and potential solutions can be considered. These include optimizing the query structure, ensuring proper index usage, and providing hints to the query planner.

1. Optimizing Query Structure:

One approach is to restructure the combined query to minimize the impact of materialization and improve index usage. This can be achieved by breaking down the query into smaller parts and ensuring that each part is optimized individually.

For example, the rel CTE can be materialized explicitly before the combined query, and the results can be stored in a temporary table. This allows the subsequent joins to be performed directly on the temporary table, reducing the overhead associated with materialization during query execution.

-- Materialize the rel CTE into a temporary table
CREATE TEMP TABLE temp_rel AS
SELECT * FROM rel_mem WHERE rel_of = 12120978;

-- Perform the combined query using the temporary table
WITH n_c AS (
    SELECT
        'nod' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        temp_rel
        JOIN tag n_t ON temp_rel.nod_id = n_t.nod_id
    GROUP BY
        k
),
w_c AS (
    SELECT
        'way' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        temp_rel
        JOIN tag w_t ON temp_rel.way_id = w_t.way_id
    GROUP BY
        k
)
SELECT * FROM n_c
UNION ALL
SELECT * FROM w_c;

-- Drop the temporary table
DROP TABLE temp_rel;

2. Ensuring Proper Index Usage:

Another approach is to ensure that the query planner uses the appropriate indexes for the joins. This can be achieved by providing explicit hints to the query planner or by restructuring the query to encourage the use of the desired indexes.

For example, the w_c subquery can be rewritten to explicitly use the index on way_id:

WITH rel AS (
    SELECT * FROM rel_mem WHERE rel_of = 12120978
),
n_c AS (
    SELECT
        'nod' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        rel
        JOIN tag n_t ON rel.nod_id = n_t.nod_id
    GROUP BY
        k
),
w_c AS (
    SELECT
        'way' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        rel
        JOIN tag w_t ON rel.way_id = w_t.way_id
    WHERE
        w_t.way_id IS NOT NULL  -- Encourage the use of the index on way_id
    GROUP BY
        k
)
SELECT * FROM n_c
UNION ALL
SELECT * FROM w_c;

3. Providing Query Planner Hints:

SQLite does not support explicit query planner hints, but certain techniques can be used to influence the query planner’s decisions. For example, the use of subqueries or additional conditions can encourage the query planner to use specific indexes or execution strategies.

In this case, the w_c subquery can be rewritten to use a subquery that explicitly references the way_id index:

WITH rel AS (
    SELECT * FROM rel_mem WHERE rel_of = 12120978
),
n_c AS (
    SELECT
        'nod' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        rel
        JOIN tag n_t ON rel.nod_id = n_t.nod_id
    GROUP BY
        k
),
w_c AS (
    SELECT
        'way' AS el,
        COUNT(*) AS cnt,
        k
    FROM
        (SELECT * FROM rel WHERE way_id IS NOT NULL) AS rel_filtered
        JOIN tag w_t ON rel_filtered.way_id = w_t.way_id
    GROUP BY
        k
)
SELECT * FROM n_c
UNION ALL
SELECT * FROM w_c;

4. Analyzing and Optimizing Indexes:

Finally, it is important to ensure that the indexes on the tag table are optimized for the queries being executed. The current schema includes indexes on nod_id, way_id, and rel_id, as well as a composite index on k and v. However, the query planner may not always choose the most efficient index for a given query.

To optimize index usage, consider creating covering indexes that include all columns required by the query. For example, a covering index for the w_c subquery could include both way_id and k:

CREATE INDEX tag_ix_way_id_k ON tag(way_id, k);

Similarly, a covering index for the n_c subquery could include both nod_id and k:

CREATE INDEX tag_ix_nod_id_k ON tag(nod_id, k);

These covering indexes can help the query planner avoid additional table lookups and improve the overall performance of the queries.

5. Monitoring and Profiling Query Performance:

To further diagnose and optimize the performance of the combined query, it is important to monitor and profile the query execution. SQLite provides several tools for this purpose, including the EXPLAIN QUERY PLAN statement and the .timer command in the SQLite shell.

By analyzing the query plans and execution times, it is possible to identify bottlenecks and make informed decisions about query optimization. For example, if the materialization of the rel CTE is identified as a bottleneck, alternative approaches such as temporary tables or subqueries can be considered.

Conclusion:

The performance issue with the UNION ALL query in SQLite is primarily caused by the query planner’s behavior when handling CTEs and indexed joins. By optimizing the query structure, ensuring proper index usage, and providing hints to the query planner, it is possible to significantly improve the performance of the combined query. Additionally, monitoring and profiling query execution can help identify and address any remaining bottlenecks. With these techniques, the combined query can be optimized to execute in a time comparable to the sum of the durations of the individual queries.