UNION and UNION ALL in MySQL - Time & Space Complexity

Time Complexity: UNION and UNION ALL

O(n) for UNION ALL, O(n log n) for UNION

Understanding Time Complexity

When combining results from two or more queries, it is important to understand how the time to get results grows as the data grows.

We want to know how the cost changes when using UNION versus UNION ALL in MySQL.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1 FROM tableA
UNION
SELECT column1 FROM tableB;

SELECT column1 FROM tableA
UNION ALL
SELECT column1 FROM tableB;
    

This code combines results from two tables, either removing duplicates (UNION) or keeping all rows (UNION ALL).

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Scanning all rows from both tables.
• How many times: Once for each table's rows.
• Additional operation for UNION: Comparing rows to remove duplicates.
• How many times for duplicate check: Depends on total rows combined.

How Execution Grows With Input

As the number of rows in each table grows, the work changes differently for UNION and UNION ALL.

Input Size (rows in each table)	Approx. Operations for UNION	Approx. Operations for UNION ALL
10	About 20 scans + some duplicate checks	About 20 scans only
100	About 200 scans + more duplicate checks	About 200 scans only
1000	About 2000 scans + many duplicate checks	About 2000 scans only

Pattern observation: UNION ALL grows linearly with input size, while UNION adds extra work to compare and remove duplicates, which grows faster.

Final Time Complexity

Time Complexity: O(n) for UNION ALL, O(n log n) for UNION

This means UNION ALL just reads all rows once, but UNION also sorts or compares rows to remove duplicates, which takes more time as data grows.

Common Mistake

[X] Wrong: "UNION and UNION ALL take the same time because they both combine rows."

[OK] Correct: UNION must check for duplicates, which adds extra work beyond just combining rows, making it slower as data grows.

Interview Connect

Understanding how UNION and UNION ALL scale helps you explain query performance clearly and choose the right tool for combining data efficiently.

Self-Check

"What if we added an ORDER BY clause after UNION? How would that affect the time complexity?"

Practice

1. What is the main difference between UNION and UNION ALL in MySQL?

easy

A. UNION sorts the result, UNION ALL does not.

B. UNION keeps all rows including duplicates, UNION ALL removes duplicates.

C. UNION only works with numeric columns, UNION ALL works with all data types.

D. UNION removes duplicate rows, UNION ALL keeps all rows including duplicates.

Solution

1. Step 1: Understand UNION behavior

   UNION combines results from two queries and removes duplicate rows to return only unique rows.

2. Step 2: Understand UNION ALL behavior

   UNION ALL combines results but keeps all rows, including duplicates, without filtering.

3. Final Answer:

   UNION removes duplicate rows, UNION ALL keeps all rows including duplicates. -> Option D

4. Quick Check:

   Duplicates removed = UNION, duplicates kept = UNION ALL [OK]

Hint: Remember: UNION = unique rows, UNION ALL = all rows [OK]

Common Mistakes:

• Thinking UNION ALL removes duplicates
• Confusing sorting behavior with UNION
• Assuming UNION only works on numeric data

2. Which of the following is the correct syntax to combine two SELECT queries using UNION ALL in MySQL?

easy

A. SELECT * FROM table1 UNION ALL SELECT * FROM table2;

B. SELECT * FROM table1 UNIONALL SELECT * FROM table2;

C. SELECT * FROM table1 UNION, ALL SELECT * FROM table2;

D. SELECT * FROM table1 UNION; ALL SELECT * FROM table2;

Solution

1. Step 1: Check correct keyword spacing

   The correct keyword is UNION ALL with a space between UNION and ALL.

2. Step 2: Validate SQL syntax

   The syntax must be: SELECT ... UNION ALL SELECT ...; without commas or semicolons between the two SELECTs.

3. Final Answer:

   SELECT * FROM table1 UNION ALL SELECT * FROM table2; -> Option A

4. Quick Check:

   Correct keyword and syntax = SELECT * FROM table1 UNION ALL SELECT * FROM table2; [OK]

Hint: Use space between UNION and ALL, no commas [OK]

Common Mistakes:

• Writing UNIONALL as one word
• Adding commas between SELECT statements
• Using semicolons between SELECTs

3. Given two tables:
Table A:
id | name
1 | Alice
2 | Bob

Table B:
id | name
2 | Bob
3 | Carol

What will be the result of this query?

SELECT id, name FROM A UNION SELECT id, name FROM B;

medium

A. 2 | Bob3 | Carol

B. 1 | Alice2 | Bob2 | Bob3 | Carol

C. 1 | Alice2 | Bob3 | Carol

D. 1 | Alice3 | Carol

Solution

1. Step 1: Combine rows from both tables

   Table A has (1, Alice) and (2, Bob). Table B has (2, Bob) and (3, Carol).

2. Step 2: Apply UNION behavior

   UNION removes duplicates, so (2, Bob) appears only once in the result.

3. Final Answer:

   1 | Alice
   2 | Bob
   3 | Carol -> Option C

4. Quick Check:

   Duplicates removed, unique rows shown [OK]

Hint: UNION removes duplicates, so repeated rows appear once [OK]

Common Mistakes:

• Including duplicate rows with UNION
• Confusing UNION with UNION ALL output
• Ignoring duplicate row removal

4. Consider this query:

SELECT id FROM table1
UNION ALL
SELECT id FROM table2 ORDER BY id;

What is wrong with this query?

medium

A. ORDER BY must be applied only once at the end of the UNION ALL query.

B. UNION ALL cannot be used with ORDER BY.

C. Each SELECT must have its own ORDER BY clause.

D. ORDER BY should come before UNION ALL.

Solution

1. Step 1: Understand ORDER BY with UNION ALL

   ORDER BY applies to the entire combined result, not to individual SELECTs.

2. Step 2: Identify correct placement

   ORDER BY must be placed after the last SELECT and UNION ALL, not inside one SELECT.

3. Final Answer:

   ORDER BY must be applied only once at the end of the UNION ALL query. -> Option A

4. Quick Check:

   ORDER BY after UNION ALL, not inside SELECT [OK]

Hint: Place ORDER BY after all UNION ALL parts [OK]

Common Mistakes:

• Putting ORDER BY inside one SELECT only
• Trying ORDER BY before UNION ALL
• Assuming UNION ALL disallows ORDER BY

5. You have two tables:
Employees:
id | name
1 | John
2 | Jane
3 | Mike

Contractors:
id | name
2 | Jane
4 | Anna

You want to list all people from both tables, including duplicates, and sort by name ascending.
Which query achieves this correctly?

hard

A. SELECT id, name FROM Employees UNION SELECT id, name FROM Contractors ORDER BY name ASC;

B. SELECT id, name FROM Employees UNION ALL SELECT id, name FROM Contractors ORDER BY name ASC;

C. SELECT id, name FROM Employees UNION ALL SELECT id, name FROM Contractors ORDER BY id ASC;

D. SELECT id, name FROM Employees UNION ALL ORDER BY name ASC SELECT id, name FROM Contractors;

Solution

1. Step 1: Choose UNION ALL to keep duplicates

   Since duplicates like Jane (id 2) should appear twice, use UNION ALL.

2. Step 2: Apply ORDER BY after UNION ALL

   ORDER BY must come after the full UNION ALL to sort combined results by name ascending.

3. Final Answer:

   SELECT id, name FROM Employees UNION ALL SELECT id, name FROM Contractors ORDER BY name ASC; -> Option B

4. Quick Check:

   UNION ALL + ORDER BY at end = SELECT id, name FROM Employees UNION ALL SELECT id, name FROM Contractors ORDER BY name ASC; [OK]

Hint: Use UNION ALL for duplicates, ORDER BY after all SELECTs [OK]

Common Mistakes:

• Using UNION instead of UNION ALL (removes duplicates)
• Placing ORDER BY inside one SELECT
• Incorrect syntax with ORDER BY placement