Eliminating Redundant Computations in Query Plans with Automatic CTE Detection

In analytical workloads, it is common to see repeated or near-repeated computations, like scans or big joins or aggregates, appearing more than once in the plan. These redundancies can inflate query execution significantly. Common Table Expressions (CTEs) provide a way to compute these once and reference the results multiple times, saving CPU cycles and I/O.

In this post, we will walk through how we implemented automatic detection of similar subgraphs within a query plan in our query optimizer. We will:

1. Show our approach to detect equivalent sub-plans in a query graph

2. Demonstrate pruning and cost-based decisions.

3. Generate and insert ephemeral CTEs in the final query plan.

4. Handle approximate matches by merging sub-plans that differ only slightly.

We take inspiration from a classic paper - Cost-based optimization of decision support queries using transient-views. Let us dig in. 

‍

Understanding Redundant Computations

Analytical workloads often involve complex queries that include repeated or near-repeated computations. These might involve multiple scans of large tables or big joins and aggregates appearing more than once in the plan. For instance, consider a market-basket or pricing analysis query that groups results into buckets based on certain price, coupon, or cost ranges. Instead of grouping all data in a single SELECT statement with CASE or grouping keys, the query might use multiple independent sub-selects. Each sub-select focuses on a distinct quantity band and numeric filter, combining them into a single row for side-by-side comparison of average prices, total counts, and distinct counts per bucket.

Without optimization, each sub-select re-applies filters to the same fact table in slightly different ranges. This redundancy is exactly what a cost-based optimizer or an automatic CTE detection mechanism can eliminate by computing a superset of filters once, storing results in a temporary table, and deriving each sub-bucket from that shared intermediate result.

Let us take a market-basket or pricing analysis TPC-DS query as an example. This query lumps the results for buckets based on certain ranges of price/coupon/cost side by side in one row.

Instead of grouping all in a single SELECT with a CASE or grouping key, the query uses six independent sub-selects. Each sub-select focuses on a distinct quantity band and numeric filter. They are then combined in a single row (or a small set of rows) to facilitate a side-by-side comparison of average price, total counts, and distinct counts per bucket.

‍

‍

Query Plan without Automatic CTE detection

As is seen in the plan below, there is repeated scanning or filtering of the large store_sales table—each sub-select re-applies filters to the same fact table in a slightly different range. That’s exactly the kind of redundancy that a cost-based optimizer or an automatic CTE detection mechanism can factor out, e.g., computing a superset of the filters once, storing results in a temporary table, and deriving each sub-bucket from that shared intermediate result.

‍

‍

High-level Implementation

‍

Step 1: Building a Directed Graph of the Query Plan

The first step in optimizing query plans involves constructing the logical plan as a directed acyclic graph (DAG). In this graph, each logical operator is represented as a vertex, and edges denote parent-child relationships between operators. This structure allows us to systematically analyze and optimize the query.

‍

Step 2: Level Assignment

To identify potential subgraphs that perform similar work, we assign levels to each vertex in the DAG. The level indicates how “far” a node is from the leaf nodes (typically table scans), which are at level 0. Their immediate parents are at level 1, and so on, until reaching the root of the graph. This level assignment helps group nodes that operate at the same stage of the pipeline, facilitating the identification of redundant computations.

‍

‍

Step 3: Detecting Equivalent (and Approximate) Subgraphs

This is the heart of the approach: for each level in the plan graph, we look for sets of nodes that are “equivalent” or “approximately equivalent.” Exact equivalence is straightforward (both sub-trees have the same operators, same inputs, same filters, same columns, etc.). Approximate equivalence means they match enough to be combined—maybe the filters or projections differ only slightly. 

At each level, we search for sub-plans that are:

• Exactly equivalent: The same operator type, same filters/expressions, same schema, etc.

• Approximately equivalent: Operators differ only in minor ways (e.g., a filter threshold). Under certain conditions, we can unify them if the cost model justifies it (e.g., merging filters with OR logic).

‍

‍

‍

Step 4: Pruning

Once equivalent sub-plans are identified, the optimizer must decide whether to prune redundant computations and replace them with CTEs. This decision is typically cost-based, meaning the optimizer evaluates whether the benefits of using a CTE (e.g., reduced CPU and I/O usage) outweigh the costs (e.g., additional memory for storing intermediate results).

After we find these candidate sets, we do additional checks:

• Cost Model: If computing a single shared sub-plan plus writing it to a temporary table is more expensive than letting each sub-plan run independently, we skip the CTE approach.

• Row Count Threshold: If the plan is extremely selective (or not selective enough), it might not be worth materializing into a CTE.

• Nested child sets: If a sub-tree is already captured at a higher level, we don’t want to generate redundant CTEs.

‍

Step 5: Generating CTEs and Rewriting the Plan

If the cost model says we’re better off factoring out the sub-plans, we create CTEs and rewrite all references to the repeated sub-plan to read from these newly created tables. This final step yields a single unified plan with minimal repeated work.

‍

‍

‍

Plan with Automatic CTE detection

Now let’s examine the query plan with automatic CTE detection

‍

‍

With automatic CTE detection, the query’s execution time reduced from 83 sec to 21 sec - ~75% performance improvement!

‍

Benefits of Automatic CTE

By automatically detecting repeated (or nearly repeated) sub-plan fragments and turning them into transient tables, we can drastically reduce redundant work in complex query plans. This approach:

• Improves Performance: Especially for expensive joins or aggregates, computing once can be much cheaper than computing multiple times.

• Is Transparent: The user doesn’t need to write those WITH cte AS ( ... ) statements by hand; the optimizer does it all automatically!!

• Handles Approximate Equivalence: We can unify sub-plan variants if the cost model says so, which is especially relevant in large queries with slightly different dimensional filters or projections

‍

Conclusion

Automatic CTE detection is a powerful tool for optimizing query performance by eliminating redundant computations. By constructing a directed graph of the query plan, assigning levels to identify similar subgraphs, detecting equivalent sub-plans, making cost-based decisions, generating ephemeral CTEs, and handling approximate matches, we can significantly improve query efficiency. This approach not only speeds up query execution but also reduces resource usage, making it an essential technique for database administrators and analysts working with complex analytical workloads.

‍

Reference

Subramanian, Subbu N., and Shivakumar Venkataraman. "Cost-based optimization of decision support queries using transient-views." Proceedings of the 1998 ACM SIGMOD international conference on Management of data, 1998.