Set operations with ORDER BY in SQL - Time & Space Complexity

Time Complexity: Set operations with ORDER BY

O(n log n)

Understanding Time Complexity

We want to understand how the time needed to run a SQL query with set operations and ordering changes as the data grows.

Specifically, how does combining results and sorting them affect performance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT column1 FROM tableA
UNION
SELECT column1 FROM tableB
ORDER BY column1;
    

This query combines unique values from two tables and then sorts the final list by column1.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning both tables to collect rows, then sorting the combined results.
• How many times: Each row in both tables is processed once; sorting compares rows multiple times depending on total rows.

How Execution Grows With Input

As the number of rows in both tables grows, the time to scan grows linearly, but sorting takes more time as the combined data grows.

Input Size (n)	Approx. Operations
10	About 20 scans + sorting 20 rows
100	About 200 scans + sorting 200 rows
1000	About 2000 scans + sorting 2000 rows

Pattern observation: Scanning grows straight with input size, sorting grows faster but not as fast as scanning squared.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the number of rows because sorting takes more steps as data grows.

Common Mistake

[X] Wrong: "The query runs in straight linear time because it just reads rows once."

[OK] Correct: Sorting the combined results requires extra comparisons, so the time grows faster than just reading rows.

Interview Connect

Understanding how set operations and sorting affect query time helps you explain performance in real projects and shows you can think about data size impact.

Self-Check

"What if we replaced UNION with UNION ALL (which does not remove duplicates)? How would the time complexity change?"

Practice

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

easy

A. Sorts the results in ascending order

B. Combines results and removes duplicate rows

C. Combines results and keeps all duplicate rows

D. Joins tables based on a common column

Solution

1. Step 1: Understand UNION operation

   The UNION operation combines results from two SELECT queries into one result set.

2. Step 2: Check duplicate handling

   UNION removes duplicate rows, unlike UNION ALL which keeps duplicates.

3. Final Answer:

   Combines results and removes duplicate rows -> Option B

4. Quick Check:

   UNION removes duplicates = C [OK]

Hint: UNION removes duplicates; UNION ALL keeps them [OK]

Common Mistakes:

• Confusing UNION with UNION ALL
• Thinking UNION sorts results automatically
• Mixing UNION with JOIN operations

2. Which of the following is the correct syntax to combine two SELECT queries with UNION and sort the final result by column name?

easy

A. SELECT name FROM table1 UNION ORDER BY name SELECT name FROM table2;

B. SELECT name FROM table1 ORDER BY name UNION SELECT name FROM table2;

C. SELECT name FROM table1 UNION SELECT name FROM table2 ORDER BY name;

D. SELECT name FROM table1 UNION SELECT name FROM table2 SORT BY name;

Solution

1. Step 1: Understand correct UNION syntax

   The UNION combines two SELECT queries; ORDER BY applies after the last SELECT.

2. Step 2: Check placement of ORDER BY

   ORDER BY must come after the entire UNION, not between or before queries.

3. Final Answer:

   SELECT name FROM table1 UNION SELECT name FROM table2 ORDER BY name; -> Option C

4. Quick Check:

   ORDER BY after UNION = A [OK]

Hint: Place ORDER BY after all UNION queries [OK]

Common Mistakes:

• Putting ORDER BY before UNION
• Using SORT BY instead of ORDER BY
• Placing ORDER BY between SELECTs

3. Given two tables:
table1 with values (1, 'Alice'), (2, 'Bob')
table2 with values (2, 'Bob'), (3, 'Charlie')
What is the result of this query?

SELECT id, name FROM table1 UNION SELECT id, name FROM table2 ORDER BY id;

medium

A. (1, 'Alice'), (2, 'Bob'), (3, 'Charlie')

B. (1, 'Alice'), (2, 'Bob'), (2, 'Bob'), (3, 'Charlie')

C. (2, 'Bob'), (3, 'Charlie')

D. (1, 'Alice'), (3, 'Charlie')

Solution

1. Step 1: Combine rows with UNION

   UNION merges rows from both tables and removes duplicates, so (2, 'Bob') appears once.

2. Step 2: Sort combined results by id

   Ordering by id gives rows in order: 1, 2, 3.

3. Final Answer:

   (1, 'Alice'), (2, 'Bob'), (3, 'Charlie') -> Option A

4. Quick Check:

   UNION removes duplicates, ORDER BY sorts = B [OK]

Hint: UNION removes duplicates; ORDER BY sorts final list [OK]

Common Mistakes:

• Expecting duplicates with UNION
• Ignoring ORDER BY sorting
• Confusing UNION with UNION ALL

4. Identify the error in this SQL query:

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

medium

A. SELECT statements must have different column names

B. UNION ALL cannot be used with ORDER BY

C. Missing semicolon after first SELECT

D. ORDER BY is placed incorrectly between UNION ALL and second SELECT

Solution

1. Step 1: Check UNION ALL syntax

   UNION ALL combines two SELECT queries; ORDER BY must come after both queries, not between.

2. Step 2: Identify ORDER BY placement error

   ORDER BY is incorrectly placed between UNION ALL and second SELECT, causing syntax error.

3. Final Answer:

   ORDER BY is placed incorrectly between UNION ALL and second SELECT -> Option D

4. Quick Check:

   ORDER BY after UNION ALL queries = D [OK]

Hint: ORDER BY must follow all UNION ALL queries [OK]

Common Mistakes:

• Placing ORDER BY between UNION ALL and second SELECT
• Thinking UNION ALL disallows ORDER BY
• Assuming column names must differ

5. You have two tables:
employees with columns (id, name, department)
contractors with columns (id, name, department)
Write a query to list all unique names from both tables sorted alphabetically, but include duplicates if the same name appears in both tables.
Which query achieves this?

hard

A. SELECT name FROM employees UNION ALL SELECT name FROM contractors ORDER BY name;

B. SELECT name FROM employees UNION SELECT name FROM contractors ORDER BY name;

C. SELECT name FROM employees INTERSECT SELECT name FROM contractors ORDER BY name;

D. SELECT name FROM employees EXCEPT SELECT name FROM contractors ORDER BY name;

Solution

1. Step 1: Understand requirement for duplicates

   The query should include duplicates if the same name appears in both tables, so duplicates must be kept.

2. Step 2: Choose correct set operation

   UNION removes duplicates, so it is not suitable. UNION ALL keeps duplicates from both tables.

3. Step 3: Confirm sorting

   ORDER BY name sorts the combined result alphabetically.

4. Final Answer:

   SELECT name FROM employees UNION ALL SELECT name FROM contractors ORDER BY name; -> Option A

5. Quick Check:

   UNION ALL keeps duplicates, ORDER BY sorts = A [OK]

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

Common Mistakes:

• Using UNION which removes duplicates
• Confusing INTERSECT or EXCEPT with UNION
• Placing ORDER BY incorrectly