Why set operations matter in PostgreSQL - Performance Analysis

Time Complexity: Why set operations matter

O(n log n)

Understanding Time Complexity

When working with databases, set operations like UNION or INTERSECT combine or compare groups of rows.

We want to know how the time to run these operations changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following SQL using UNION.

SELECT id FROM employees
UNION
SELECT id FROM managers;
    

This code combines two lists of IDs, removing duplicates to get unique IDs from both tables.

Identify Repeating Operations

Look for repeated work done by the database engine.

• Primary operation: Scanning each table's rows to collect IDs.
• How many times: Once per table, then comparing all collected rows to remove duplicates.

How Execution Grows With Input

As the number of rows in each table 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 run the UNION grows roughly in proportion to n log n as the total number of rows increases.

Common Mistake

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

[OK] Correct: The database must look at every row to combine and remove duplicates, so bigger tables take more time.

Interview Connect

Understanding how set operations scale helps you write efficient queries and explain your choices clearly.

Self-Check

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

Practice

1. What is the main purpose of set operations like UNION and INTERSECT in PostgreSQL?

easy

A. To delete rows from multiple tables

B. To create new tables from existing ones

C. To update data in a table

D. To combine or compare results from multiple SELECT queries

Solution

1. Step 1: Understand set operations

   Set operations like UNION and INTERSECT combine or compare results from multiple SELECT queries.

2. Step 2: Identify their purpose

   They help find unique, common, or different data across queries without modifying tables.

3. Final Answer:

   To combine or compare results from multiple SELECT queries -> Option D

4. Quick Check:

   Set operations = combine/compare SELECT results [OK]

Hint: Set operations combine query results, not modify tables [OK]

Common Mistakes:

• Thinking set operations modify tables
• Confusing set operations with DML commands
• Assuming set operations create new tables

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

easy

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

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

C. SELECT col1 FROM table1 + SELECT col1 FROM table2;

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

Solution

1. Step 1: Recall UNION syntax

   The correct syntax uses UNION keyword between two SELECT statements with matching columns.

2. Step 2: Check options

   Only SELECT col1 FROM table1 UNION SELECT col1 FROM table2; is correct. JOIN is for table joins; + is invalid syntax; INTERSECT is a different operation.

3. Final Answer:

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

4. Quick Check:

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

Hint: UNION joins SELECTs with UNION keyword, no + or JOIN [OK]

Common Mistakes:

• Using + instead of UNION
• Confusing JOIN with UNION
• Mixing INTERSECT with UNION syntax

3. Given these tables:
table1: (id) values (1), (2), (3);
table2: (id) values (2), (3), (4);
What is the result of this query?

SELECT id FROM table1 INTERSECT SELECT id FROM table2;

medium

A. [2, 3]

B. [1, 2, 3, 4]

C. [1]

D. [4]

Solution

1. Step 1: Understand INTERSECT operation

   INTERSECT returns only values present in both queries.

2. Step 2: Compare table1 and table2 ids

   table1 has 1,2,3; table2 has 2,3,4; common values are 2 and 3.

3. Final Answer:

   [2, 3] -> Option A

4. Quick Check:

   INTERSECT = common values [OK]

Hint: INTERSECT returns only common rows between queries [OK]

Common Mistakes:

• Including all values from both tables
• Confusing INTERSECT with UNION
• Returning values only from one table

4. Consider this query:

SELECT id FROM table1 UNION ALL SELECT id FROM table2;

It returns duplicate rows. How can you fix it to return only unique rows?

medium

A. Replace UNION ALL with UNION

B. Add DISTINCT inside each SELECT

C. Use INTERSECT instead of UNION ALL

D. Add GROUP BY id at the end

Solution

1. Step 1: Understand UNION ALL vs UNION

   UNION ALL returns all rows including duplicates; UNION removes duplicates.

2. Step 2: Fix query to remove duplicates

   Replacing UNION ALL with UNION removes duplicates automatically.

3. Final Answer:

   Replace UNION ALL with UNION -> Option A

4. Quick Check:

   UNION removes duplicates, UNION ALL does not [OK]

Hint: Use UNION (not UNION ALL) to remove duplicates [OK]

Common Mistakes:

• Using UNION ALL when duplicates are unwanted
• Adding DISTINCT inside each SELECT unnecessarily
• Using INTERSECT which returns only common rows

5. You want to find all unique customer IDs who made purchases in either 2022 or 2023 from two tables:
purchases_2022(customer_id) and purchases_2023(customer_id).
Which query correctly returns this list without duplicates?

hard

A. SELECT customer_id FROM purchases_2022 UNION ALL SELECT customer_id FROM purchases_2023;

B. SELECT customer_id FROM purchases_2022 INTERSECT SELECT customer_id FROM purchases_2023;

C. SELECT customer_id FROM purchases_2022 UNION SELECT customer_id FROM purchases_2023;

D. SELECT DISTINCT customer_id FROM purchases_2022, purchases_2023;

Solution

1. Step 1: Understand the goal

   We want all unique customer IDs from either year, combined without duplicates.

2. Step 2: Evaluate options

   SELECT customer_id FROM purchases_2022 INTERSECT SELECT customer_id FROM purchases_2023; returns only customers in both years (common). SELECT customer_id FROM purchases_2022 UNION SELECT customer_id FROM purchases_2023; returns all unique customers from both years. SELECT customer_id FROM purchases_2022 UNION ALL SELECT customer_id FROM purchases_2023; returns all including duplicates. SELECT DISTINCT customer_id FROM purchases_2022, purchases_2023; creates a cross join, not union.

3. Final Answer:

   SELECT customer_id FROM purchases_2022 UNION SELECT customer_id FROM purchases_2023; -> Option C

4. Quick Check:

   UNION = unique combined rows [OK]

Hint: Use UNION to combine unique rows from multiple tables [OK]

Common Mistakes:

• Using INTERSECT to get all customers
• Using UNION ALL causing duplicates
• Using cross join instead of union