Set Operations: Deep Dive into UNION vs. UNION ALL

In relational database management systems, comparing datasets and extracting specific subsets of data are core operations. This chapter explores two classic SQL interview problems that test your understanding of set-based operations, relational exclusions, and analytical partitioning:

1. Set Exclusion (Set Difference): Identifying records in one table that do not exist in another (e.g., finding orphaned employees whose departments do not exist in the master department table).
2. Intra-Group Partitioning: Finding the $N$-th highest value within distinct categories (e.g., finding the employee with the second-highest salary in each department).

1. The Problem of Set Exclusion

In database design, referential integrity ensures that foreign keys point to valid primary keys. However, in real-world legacy systems, data migrations, or staging environments, orphaned records frequently occur.

Consider two tables: emp (Employees) and dept (Departments).

The emp Table

The dept Table

The Goal

Identify all employees whose department_id is not present in the dept table. Looking at the data, departments 100 and 300 exist in the master table, but departments 200 and 900 do not. The query must return employees belonging to departments 200 and 900.

2. Core Mental Model: Set Difference ($A \setminus B$)

To find records in Table $A$ that do not exist in Table $B$, we are performing a Set Difference operation ($A \setminus B$ or $A - B$).

The resulting set must contain only the elements of $A$ that have no corresponding match in $B$. In SQL, this can be achieved using two primary strategies:

1. Subquery Exclusion (NOT IN or NOT EXISTS)
2. Relational Join Exclusion (LEFT JOIN combined with a NULL filter)

3. Naive vs. Optimized Approach

The Naive Approach: NOT IN Subquery

The most intuitive way to write this query is using a subquery with the NOT IN operator.

SELECT * 
FROM emp 
WHERE department_id NOT IN (
    SELECT department_id 
    FROM dept
);

Why This is Suboptimal (Performance Pitfalls)

• Execution Complexity: For every row in the outer table (emp), the database engine may have to evaluate the subquery list, resulting in an $O(N \times M)$ worst-case time complexity if not optimized by the query planner.
• The Null Trap: If the subquery returns even a single NULL value, the NOT IN condition evaluates to UNKNOWN for all rows, and the query returns zero results.

The Optimized Approach: LEFT JOIN with IS NULL

A highly performant alternative preferred in production environments is the LEFT JOIN exclusion pattern.

SELECT e.*
FROM emp e
LEFT JOIN dept d ON e.department_id = d.department_id
WHERE d.department_id IS NULL;

Why This is Better

• Query Optimizer Friendliness: Modern query planners can optimize joins using hash joins or merge joins, reducing the execution complexity to $O(N + M)$.
• Null Safety: It avoids the logical pitfalls of the NOT IN operator when handling nullable columns.

4. Step-by-Step Evolution of the Exclusion Query

Let's trace how the database processes the LEFT JOIN exclusion query step-by-step.

Step 1: Perform the LEFT JOIN

The database joins the two tables on department_id. Because it is a LEFT JOIN, all rows from emp are retained. If there is no match in dept, the columns from dept are populated with NULL.

Step 2: Apply the WHERE Filter

The WHERE d.department_id IS NULL clause filters out any rows where a match was found, leaving only the orphaned records.

5. Finding the N-th Highest Record (The Partitioning Challenge)

The second common interview problem is finding the second-highest salary within each department. This requires grouping data dynamically without collapsing the individual rows (which rules out a simple GROUP BY with MAX()).

The Data Distribution

• Department 100: Salaries are 15000, 10000, 10000, and 8000.
• Department 200: Salaries are 12000, 12000, 9000, and 7000.
• Department 900: Salary is 11000.

To solve this, we must partition the dataset by department_id and rank the salaries within each partition in descending order.

6. Deep Dive into Window Functions: RANK() vs. DENSE_RANK()

To assign ranks to rows within a partition, SQL provides three primary window functions: ROW_NUMBER(), RANK(), and DENSE_RANK(). Choosing the correct one is critical when dealing with duplicate values (ties).

Comparison of Ranking Functions

The Impact of Ties on Our Goal

If we want the second-highest salary:

• In Department 100, the salaries are: 15000 (Rank 1), 10000 (Rank 2), 10000 (Rank 2), 8000 (Rank 3).
• In Department 200, the salaries are: 12000 (Rank 1), 12000 (Rank 1), 9000 (Rank 2), 7000 (Rank 3).

If we use RANK() in Department 200:

• 12000 gets Rank 1
• 12000 gets Rank 1
• 9000 gets Rank 3 (Rank 2 is skipped!)

If we query for WHERE rank_val = 2 using RANK(), Department 200 will return no records, even though 9000 is logically the second-highest distinct salary. Therefore, DENSE_RANK() is the correct function to use.

7. Complete Flow Walkthrough

Step 1: Write the Window Query

We write a Common Table Expression (CTE) or subquery to assign dense ranks to each employee's salary partitioned by department.

WITH RankedSalaries AS (
    SELECT 
        emp_id,
        emp_name,
        department_id,
        salary,
        DENSE_RANK() OVER (
            PARTITION BY department_id 
            ORDER BY salary DESC
        ) AS salary_rank
    FROM emp
)
SELECT * 
FROM RankedSalaries
WHERE salary_rank = 2;

Step 2: Execution Flow Visualized

Final Output

The query correctly identifies the employees with the second-highest salary in each department, handling ties gracefully:

8. Summary and Key Takeaways

• Set Difference Optimization: When tasked with finding records in Table A that are missing from Table B, avoid naive NOT IN subqueries on large datasets. Use a LEFT JOIN combined with a WHERE right_table.key IS NULL filter to allow the query optimizer to use faster join algorithms.
• Beware of NULLs in Subqueries: A NOT IN subquery will return zero rows if the subquery result set contains a NULL value.
• Window Functions for Ranking: Use ROW_NUMBER(), RANK(), or DENSE_RANK() depending on how ties should be handled.
• Handling Ties with DENSE_RANK(): When searching for the $N$-th highest value (e.g., second-highest salary), always use DENSE_RANK(). Unlike RANK(), it does not skip rank numbers when duplicate values share a rank, ensuring that subsequent ranks are not lost.
• Partitioning vs. Grouping: PARTITION BY allows you to perform calculations across groups of rows while still retaining the individual identity of each row in the final output.