UNION combining result sets in SQL - Time & Space Complexity

Time Complexity: UNION combining result sets

O(n log n)

Understanding Time Complexity

When we combine two lists of data using UNION, we want to know how the work grows as the lists get bigger.

How does the time to get the combined list change when the input lists grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1 FROM tableA
UNION
SELECT column1 FROM tableB;
    

This code combines unique values from two tables into one list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning each row in both tables and comparing to remove duplicates.
• How many times: Each row in tableA and tableB is checked once, then comparisons happen to find unique rows.

How Execution Grows With Input

As the number of rows in both tables grows, the work to scan and compare grows too.

Input Size (n)	Approx. Operations
10	About 20 scans and comparisons
100	About 200 scans and comparisons
1000	About 2000 scans and comparisons

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

Final Time Complexity

Time Complexity: O(n log n)

This means the time to combine grows roughly in proportion to n log n, where n is the total number of rows.

Common Mistake

[X] Wrong: "UNION runs in constant time no matter how big the tables are."

[OK] Correct: The database must look at every row to find unique values, so more rows mean more work.

Interview Connect

Understanding how combining data grows with size helps you explain query performance clearly and confidently.

Self-Check

"What if we used UNION ALL instead of UNION? How would the time complexity change?"

Practice

1. What does the SQL UNION operator do when combining results from two SELECT queries?

easy

A. Combines rows but keeps all duplicates

B. Combines rows from both queries and removes duplicate rows

C. Joins tables based on a common column

D. Filters rows based on a condition

Solution

1. Step 1: Understand UNION behavior

   The UNION operator combines rows from two or more SELECT queries into a single result set.

2. Step 2: Check duplicate handling

   By default, UNION removes duplicate rows to ensure unique results.

3. Final Answer:

   Combines rows from both queries and removes duplicate rows -> Option B

4. Quick Check:

   UNION removes duplicates = A [OK]

Hint: UNION removes duplicates by default, unlike UNION ALL [OK]

Common Mistakes:

• Confusing UNION with UNION ALL
• Thinking UNION joins tables by columns
• Assuming UNION filters rows

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

easy

A. SELECT col1 FROM table1 UNION ALL JOIN SELECT col1 FROM table2;

B. SELECT col1 FROM table1 JOIN SELECT col1 FROM table2;

C. SELECT col1 FROM table1 WHERE UNION SELECT col1 FROM table2;

D. SELECT col1 FROM table1 UNION SELECT col1 FROM table2;

Solution

1. Step 1: Review correct UNION syntax

   The correct syntax is to write two SELECT statements separated by the UNION keyword.

2. Step 2: Identify invalid options

   Options B, C, and D misuse JOIN or WHERE with UNION, which is incorrect syntax.

3. Final Answer:

   SELECT col1 FROM table1 UNION SELECT col1 FROM table2; -> Option D

4. Quick Check:

   UNION syntax = SELECT ... UNION SELECT ... [OK]

Hint: UNION joins SELECTs directly, no JOIN or WHERE needed [OK]

Common Mistakes:

• Using JOIN instead of UNION
• Placing WHERE before UNION
• Combining UNION ALL with JOIN incorrectly

3. Given two tables:
Table A: id
1
2
3
Table B: id
2
3
4
What is the result of:
SELECT id FROM A UNION SELECT id FROM B;

medium

A. [1, 2, 3, 4]

B. [1, 2, 2, 3, 3, 4]

C. [2, 3]

D. [1, 4]

Solution

1. Step 1: List rows from both tables

   Table A has ids 1, 2, 3; Table B has ids 2, 3, 4.

2. Step 2: Apply UNION behavior

   UNION combines all rows and removes duplicates, so final list is 1, 2, 3, 4.

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   UNION removes duplicates = [1, 2, 3, 4] [OK]

Hint: UNION removes duplicates, so no repeated ids appear [OK]

Common Mistakes:

• Expecting duplicates to appear
• Confusing UNION with UNION ALL
• Listing only common ids

4. Consider this SQL query:
SELECT name FROM employees UNION SELECT name, department FROM managers;
What is the issue with this query?

medium

A. The number of columns in both SELECT statements differ

B. UNION cannot be used with SELECT statements

C. The query will return duplicate rows

D. The query is missing a WHERE clause

Solution

1. Step 1: Check column counts in SELECTs

   The first SELECT returns 1 column (name), the second returns 2 columns (name, department).

2. Step 2: Understand UNION column rules

   UNION requires all SELECT statements to have the same number of columns with compatible types.

3. Final Answer:

   The number of columns in both SELECT statements differ -> Option A

4. Quick Check:

   UNION needs same columns = C [OK]

Hint: UNION needs same column count in all SELECTs [OK]

Common Mistakes:

• Ignoring column count mismatch
• Thinking UNION filters duplicates only
• Assuming WHERE clause is mandatory

5. You have two tables:
Sales2023(product, amount)
Apple, 100
Banana, 150
Sales2024(product, amount)
Banana, 200
Cherry, 300
Write a query using UNION to list all unique products sold in both years, sorted alphabetically.

hard

A. SELECT product, amount FROM Sales2023 UNION SELECT product, amount FROM Sales2024 ORDER BY amount;

B. SELECT product FROM Sales2023 UNION ALL SELECT product FROM Sales2024 ORDER BY product;

C. SELECT product FROM Sales2023 UNION SELECT product FROM Sales2024 ORDER BY product;

D. SELECT product FROM Sales2023 JOIN Sales2024 ON product ORDER BY product;

Solution

1. Step 1: Select product column from both tables

   We want unique products, so select only the product column from both tables.

2. Step 2: Use UNION to combine and remove duplicates

   UNION combines both lists and removes duplicates, giving unique products.

3. Step 3: Sort results alphabetically

   ORDER BY product sorts the final list alphabetically.

4. Final Answer:

   SELECT product FROM Sales2023 UNION SELECT product FROM Sales2024 ORDER BY product; -> Option C

5. Quick Check:

   UNION + ORDER BY product = B [OK]

Hint: Use UNION to remove duplicates, ORDER BY to sort [OK]

Common Mistakes:

• Using UNION ALL which keeps duplicates
• Selecting amount column when only product needed
• Using JOIN instead of UNION