UNION ALL with duplicates in SQL - Time & Space Complexity

Time Complexity: UNION ALL with duplicates

O(n + m)

Understanding Time Complexity

When combining results from two lists in a database, it is important to know how the time to do this grows as the lists get bigger.

We want to understand how the work changes when using UNION ALL, which keeps all duplicates.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column_name FROM table1
UNION ALL
SELECT column_name FROM table2;
    

This code combines all rows from two tables into one list, including any duplicates.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Reading all rows from both tables one by one.
• How many times: Once for each row in each table, no extra checks for duplicates.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 rows in each table	About 20 reads
100 rows in each table	About 200 reads
1000 rows in each table	About 2000 reads

Pattern observation: The work grows directly with the total number of rows combined.

Final Time Complexity

Time Complexity: O(n + m)

This means the time to run grows in a straight line with the total rows from both tables added together.

Common Mistake

[X] Wrong: "UNION ALL removes duplicates so it takes longer to check each row."

[OK] Correct: UNION ALL does not check for duplicates, it simply adds all rows, so it runs faster than UNION which removes duplicates.

Interview Connect

Understanding how UNION ALL works helps you explain how combining data sets affects performance, a useful skill when working with databases in real projects.

Self-Check

"What if we changed UNION ALL to UNION? How would the time complexity change?"