UNION and UNION ALL in PostgreSQL - 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 queries, it's important to know how the time to get results grows as data grows.

We want to understand how using UNION and UNION ALL affects the work the database does.

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 rows from two tables, either removing duplicates (UNION) or keeping all rows (UNION ALL).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all rows from both tables.
• How many times: Once for each table's rows.
• Additional for UNION: Comparing rows to remove duplicates, which involves checking all combined rows.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations for UNION ALL	Approx. Operations for UNION
10	About 20 row reads	About 20 reads + some comparisons
100	About 200 row reads	About 200 reads + more comparisons
1000	About 2000 row reads	About 2000 reads + many comparisons

Pattern observation: UNION ALL grows linearly with input size, while UNION adds extra work to check for 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, while UNION must also sort or compare 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 removes duplicates, which needs extra work to compare rows, so it takes more time than UNION ALL.

Interview Connect

Understanding how UNION and UNION ALL scale helps you explain query performance clearly and shows you know how databases handle data combining.

Self-Check

"What if we added an index on the column used in UNION? How would the time complexity change?"

Practice

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

easy

A. UNION removes duplicate rows, while UNION ALL keeps all rows including duplicates.

B. UNION requires matching column names, UNION ALL does not.

C. UNION ALL removes duplicates, UNION keeps duplicates.

D. UNION can combine different numbers of columns, UNION ALL cannot.

Solution

1. Step 1: Understand the behavior of UNION

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

2. Step 2: Understand the behavior of UNION ALL

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

3. Final Answer:

   UNION removes duplicates, UNION ALL keeps duplicates. -> Option A

4. Quick Check:

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

Hint: UNION removes duplicates; UNION ALL keeps all rows [OK]

Common Mistakes:

• Thinking UNION ALL removes duplicates
• Believing UNION allows different column counts
• Confusing column name requirements

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

easy

A. SELECT name FROM students UNION ALL SELECT name FROM teachers;

B. SELECT name FROM students UNIONALL SELECT name FROM teachers;

C. SELECT name FROM students UNION ALL FROM teachers;

D. SELECT name FROM students UNION ALL SELECT name FROM teachers WHERE;

Solution

1. Step 1: Check the correct keyword spacing

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

2. Step 2: Verify the SELECT statements are complete

   Both queries must be valid SELECT statements with matching column counts and types.

3. Final Answer:

   SELECT name FROM students UNION ALL SELECT name FROM teachers; -> Option A

4. Quick Check:

   Correct syntax uses 'UNION ALL' with space [OK]

Hint: Use space between UNION and ALL, both queries must be valid [OK]

Common Mistakes:

• Writing UNIONALL as one word
• Missing SELECT in second query
• Adding WHERE without condition

3. Given two tables:
Table A:
id | value
1 | 'apple'
2 | 'banana'

Table B:
id | value
2 | 'banana'
3 | 'cherry'

What is the result of this query?

SELECT value FROM A UNION SELECT value FROM B ORDER BY value;

medium

A. apple, banana, banana, cherry

B. apple, banana, cherry, banana

C. banana, cherry

D. apple, banana, cherry

Solution

1. Step 1: Combine values from both tables using UNION

   UNION removes duplicates, so 'banana' appears only once.

2. Step 2: Order the combined results alphabetically

   Ordering by value gives: 'apple', 'banana', 'cherry'.

3. Final Answer:

   apple, banana, cherry -> Option D

4. Quick Check:

   UNION removes duplicates, so only one 'banana' [OK]

Hint: UNION removes duplicates; check ordering carefully [OK]

Common Mistakes:

• Including duplicate 'banana' with UNION
• Ignoring ORDER BY effect
• Confusing UNION with UNION ALL

4. Consider this query:

SELECT id FROM table1 UNION ALL SELECT id FROM table2;

It returns an error. What is the most likely cause?

medium

A. The tables have different names.

B. The two SELECT statements have different numbers of columns.

C. UNION ALL cannot be used with SELECT statements.

D. The query is missing a semicolon.

Solution

1. Step 1: Check column counts in both SELECT statements

   UNION ALL requires both SELECTs to have the same number of columns.

2. Step 2: Identify error cause

   If column counts differ, PostgreSQL throws an error.

3. Final Answer:

   The two SELECT statements have different numbers of columns. -> Option B

4. Quick Check:

   Column count mismatch causes UNION ALL error [OK]

Hint: Ensure both SELECTs have same column count for UNION ALL [OK]

Common Mistakes:

• Thinking table names must match
• Believing UNION ALL disallows SELECT
• Ignoring column count mismatch

5. You want to combine two queries:

SELECT id, name FROM employees WHERE department = 'Sales'
SELECT id, name FROM contractors WHERE department = 'Sales'

and keep all rows including duplicates. Which query correctly does this and why?

hard

A. SELECT id, name FROM employees UNION ALL SELECT id, name FROM contractors; Because WHERE is not needed in second query.

B. SELECT id, name FROM employees UNION SELECT id, name FROM contractors WHERE department = 'Sales'; Because UNION removes duplicates.

C. SELECT id, name FROM employees UNION ALL SELECT id, name FROM contractors WHERE department = 'Sales'; Because UNION ALL keeps duplicates.

D. SELECT id, name FROM employees UNION SELECT id, name FROM contractors; Because UNION ALL is invalid here.

Solution

1. Step 1: Understand requirement to keep duplicates

   To keep duplicates, use UNION ALL because UNION removes duplicates.

2. Step 2: Check WHERE clause usage

   Both queries filter department = 'Sales', so WHERE must be in both queries.

3. Final Answer:

   SELECT id, name FROM employees UNION ALL SELECT id, name FROM contractors WHERE department = 'Sales'; Because UNION ALL keeps duplicates. -> Option C

4. Quick Check:

   Keep duplicates = UNION ALL with correct WHERE clauses [OK]

Hint: Use UNION ALL to keep duplicates; apply WHERE in each SELECT [OK]

Common Mistakes:

• Using UNION instead of UNION ALL
• Omitting WHERE in second query
• Thinking UNION ALL is invalid