Why CTEs are needed in SQL - Performance Analysis

Time Complexity: Why CTEs are needed

O(n)

Understanding Time Complexity

We want to understand how using Common Table Expressions (CTEs) affects the time it takes for a database to run queries.

Specifically, we ask: How does the work grow when we use CTEs compared to other ways?

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a CTE.

WITH RecentOrders AS (
  SELECT * FROM Orders WHERE OrderDate > CURRENT_DATE - INTERVAL '30 days'
)
SELECT CustomerID, COUNT(*) AS OrderCount
FROM RecentOrders
GROUP BY CustomerID;
    

This query first selects recent orders using a CTE, then counts orders per customer.

Identify Repeating Operations

Look for repeated work in the query.

• Primary operation: Scanning the Orders table to find recent orders.
• How many times: Once for the CTE, then grouping over the filtered results.

How Execution Grows With Input

As the number of orders grows, the database must check more rows to find recent ones.

Input Size (n)	Approx. Operations
10	About 10 row checks and grouping
100	About 100 row checks and grouping
1000	About 1000 row checks and grouping

Pattern observation: The work grows roughly in direct proportion to the number of rows scanned.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows roughly in a straight line as the number of orders increases.

Common Mistake

[X] Wrong: "Using a CTE always makes queries faster because it stores results temporarily."

[OK] Correct: CTEs don't always speed things up; sometimes the database runs the CTE query each time it's referenced, so the work can be repeated.

Interview Connect

Understanding how CTEs affect query time helps you write clear and efficient database queries, a useful skill in many real projects.

Self-Check

"What if we replaced the CTE with a subquery used multiple times? How would that change the time complexity?"