Set operation column matching rules in SQL - Time & Space Complexity

Time Complexity: Set operation column matching rules

O(n^2)

Understanding Time Complexity

When using set operations like UNION or INTERSECT, the database matches columns from each query to combine results.

We want to understand how the time to match columns grows as the data size increases.

Scenario Under Consideration

Analyze the time complexity of this SQL using UNION.

SELECT id, name FROM employees
UNION
SELECT id, name FROM managers;
    

This query combines two lists of people, matching columns by position to remove duplicates.

Identify Repeating Operations

Look at what repeats as the database processes the query.

• Primary operation: Comparing rows from both queries to find duplicates.
• How many times: Once for each row in the combined result sets.

How Execution Grows With Input

As the number of rows grows, the database must compare more rows to find matches.

Input Size (n)	Approx. Operations
10	About 100 comparisons
100	About 10,000 comparisons
1000	About 1,000,000 comparisons

Pattern observation: The work grows roughly in proportion to the square of the number of rows.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to match columns and combine rows grows quadratically with the total number of rows.

Common Mistake

[X] Wrong: "Matching columns in set operations takes constant time no matter how many rows there are."

[OK] Correct: The database must check each row against others to find duplicates, so more rows mean more work.

Interview Connect

Understanding how set operations scale helps you explain query performance clearly and confidently.

Self-Check

"What if the two queries had different numbers of columns? How would that affect the time complexity?"

Practice

1.

Which rule must be followed when using SQL set operations like UNION or INTERSECT?

easy

A. Both queries must have the same number of columns with compatible data types.

B. The second query must have more columns than the first.

C. Column names must be identical in both queries.

D. Set operations only work with numeric columns.

Solution

1. Step 1: Understand set operation requirements

   Set operations combine results from multiple queries, so columns must match in number and type to align data correctly.

2. Step 2: Check column name and type rules

   Column names do not need to match; only the first query's column names are used. Data types must be compatible, and the number of columns must be the same.

3. Final Answer:

   Both queries must have the same number of columns with compatible data types. -> Option A

4. Quick Check:

   Column count and type compatibility = A [OK]

Hint: Match column count and types for set operations [OK]

Common Mistakes:

• Assuming column names must match
• Using different number of columns
• Trying set operations on incompatible data types

2.

Which of the following SQL queries correctly uses UNION with matching columns?

-- Table A: (id INT, name VARCHAR)
-- Table B: (user_id INT, username VARCHAR)

A) SELECT id, name FROM A UNION SELECT user_id, username FROM B;
B) SELECT id FROM A UNION SELECT user_id, username FROM B;
C) SELECT id, name FROM A UNION SELECT user_id FROM B;
D) SELECT id, name FROM A UNION SELECT user_id, username, email FROM B;

easy

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

B. SELECT id FROM A UNION SELECT user_id, username FROM B;

C. SELECT id, name FROM A UNION SELECT user_id, username FROM B;

D. SELECT id, name FROM A UNION SELECT user_id, username, email FROM B;

Solution

1. Step 1: Check column counts in each query

   SELECT id, name FROM A UNION SELECT user_id, username FROM B; selects 2 columns from both queries, matching counts. Other options have mismatched column counts (1 vs 2, 2 vs 1, or 2 vs 3).

2. Step 2: Verify column types compatibility

   Columns in SELECT id, name FROM A UNION SELECT user_id, username FROM B; are INT and VARCHAR in both queries, which are compatible.

3. Final Answer:

   SELECT id, name FROM A UNION SELECT user_id, username FROM B; -> Option C

4. Quick Check:

   Equal columns and compatible types = A [OK]

Hint: Count columns and check types match in both queries [OK]

Common Mistakes:

• Mismatched column counts cause errors
• Ignoring column type compatibility
• Assuming extra columns are allowed

3.

Given the tables and query below, what will be the output?

Table X:
id | value
1  | 'A'
2  | 'B'

Table Y:
code | val
2    | 'B'
3    | 'C'

Query:
SELECT id, value FROM X
UNION
SELECT code, val FROM Y;

medium

A. Syntax error due to column name mismatch

B. [ (1, 'A'), (2, 'B'), (3, 'C') ]

C. [ (1, 'A'), (3, 'C') ]

D. [ (1, 'A'), (2, 'B'), (2, 'B'), (3, 'C') ]

Solution

1. Step 1: Check column counts and types

   Both queries select 2 columns with compatible types (INT and VARCHAR). Column names differ but that is allowed.

2. Step 2: Understand UNION behavior

   UNION removes duplicates. Rows (2, 'B') appear in both tables, so only one copy appears in result.

3. Final Answer:

   [ (1, 'A'), (2, 'B'), (3, 'C') ] -> Option B

4. Quick Check:

   UNION removes duplicates = D [OK]

Hint: UNION removes duplicates, column names don't matter [OK]

Common Mistakes:

• Expecting duplicate rows in UNION result
• Thinking column names must match
• Confusing UNION with UNION ALL

4.

Identify the error in the following SQL set operation:

SELECT id, name FROM Customers
UNION
SELECT customer_id FROM Orders;

medium

A. Column names do not match between queries.

B. UNION cannot be used with SELECT statements.

C. Data types of columns are incompatible.

D. The second query has fewer columns than the first.

Solution

1. Step 1: Compare column counts in both queries

   The first query selects 2 columns (id, name), the second selects only 1 column (customer_id). This mismatch causes an error.

2. Step 2: Check other possible errors

   Column names do not need to match, and UNION works with SELECT statements. Data types are unknown but column count mismatch is enough to cause error.

3. Final Answer:

   The second query has fewer columns than the first. -> Option D

4. Quick Check:

   Column count mismatch = B [OK]

Hint: Ensure both queries select same number of columns [OK]

Common Mistakes:

• Thinking column names must match
• Ignoring column count mismatch
• Assuming UNION works with different column counts

5.

You have two tables:

Employees(emp_id INT, emp_name VARCHAR, dept VARCHAR)
Managers(manager_id INT, manager_name VARCHAR)

You want to combine employee and manager names into one list using a set operation. Which query correctly applies set operation column matching rules?

A) SELECT emp_id, emp_name FROM Employees UNION SELECT manager_id, manager_name FROM Managers;
B) SELECT emp_name FROM Employees UNION SELECT manager_name FROM Managers;
C) SELECT emp_name, dept FROM Employees UNION SELECT manager_name, manager_id FROM Managers;
D) SELECT emp_id, emp_name, dept FROM Employees UNION SELECT manager_id, manager_name FROM Managers;

hard

A. SELECT emp_name FROM Employees UNION SELECT manager_name FROM Managers;

B. SELECT emp_id, emp_name FROM Employees UNION SELECT manager_id, manager_name FROM Managers;

C. SELECT emp_name, dept FROM Employees UNION SELECT manager_name, manager_id FROM Managers;

D. SELECT emp_id, emp_name, dept FROM Employees UNION SELECT manager_id, manager_name FROM Managers;

Solution

1. Step 1: Identify columns to combine

   You want a list of names only, so selecting one column (name) from each table is appropriate.

2. Step 2: Check column counts and types

   SELECT emp_name FROM Employees UNION SELECT manager_name FROM Managers; selects one VARCHAR column from each table, matching count and compatible types. Other options have mismatched column counts or incompatible columns.

3. Final Answer:

   SELECT emp_name FROM Employees UNION SELECT manager_name FROM Managers; -> Option A

4. Quick Check:

   Same column count and type for names = B [OK]

Hint: Select same number and type of columns to combine [OK]

Common Mistakes:

• Selecting different numbers of columns
• Mixing incompatible column types
• Including unrelated columns in set operation