Last Minute SQL Interview Prep Kit: Calculating Join Output Sizes and Edge Cases

This chapter covers advanced window function partitioning, strategies for handling ties in ranking queries, and the foundational mechanics of self-joins. You will learn how to partition data across multiple dimensions, resolve ranking conflicts using business-driven tie-breakers, and structure self-joins to query hierarchical relationships within a single table.

1. Multi-Column Partitioning in Window Functions

When writing window functions, a single-column partition is often insufficient. SQL allows you to partition data across a combination of multiple columns. This creates highly granular logical subsets (partitions) of your dataset.

When you specify multiple columns in a PARTITION BY clause:

1. The SQL engine groups rows that share identical values across all specified partition columns.
2. The window function (e.g., RANK(), DENSE_RANK(), or ROW_NUMBER()) resets its counter for each unique combination.

SELECT 
    department_id,
    manager_id,
    employee_id,
    salary,
    ROW_NUMBER() OVER (PARTITION BY department_id, manager_id ORDER BY salary DESC) as row_num,
    RANK() OVER (PARTITION BY department_id, manager_id ORDER BY salary DESC) as rnk,
    DENSE_RANK() OVER (PARTITION BY department_id, manager_id ORDER BY salary DESC) as dense_rnk
FROM employees;

2. Execution Walkthrough: Multi-Column Partitions

To understand how the SQL engine processes multi-column partitions, let us trace the execution of the query above on a sample dataset.

Sample Dataset and Partition Boundaries

Output Analysis by Partition

• Partition A (102, 5): Contains only one row. All ranking functions (ROW_NUMBER, RANK, DENSE_RANK) output 1.
• Partition B (100, 4): Contains two rows with identical salaries ($15,000).
  • RANK() and DENSE_RANK() both assign 1 to both rows because of the tie.
  • ROW_NUMBER() assigns unique values (1 and 2) arbitrarily unless a secondary tie-breaker is specified in the ORDER BY clause.
• Partition D (200, 2): Contains three rows with distinct salaries ($14,000, \char36 12,000, $10,000). Because there are no duplicate salaries, ROW_NUMBER(), RANK(), and DENSE_RANK() yield identical, sequential outputs: 1, 2, and 3.

3. The "Top N Employees per Department" Pattern

A classic SQL interview question asks you to find the highest-paid employee (or top $N$ employees) within each department.

The Naive Approach vs. The Window Function Approach

A naive approach using GROUP BY and MAX(salary) only returns the maximum salary per department. It makes retrieving the corresponding employee's name or ID highly complex and prone to performance issues (requiring expensive subquery joins).

The optimal approach uses a Common Table Expression (CTE) combined with a window function to rank employees within their department, followed by an outer filter.

WITH RankedEmployees AS (
    SELECT 
        department_id,
        employee_id,
        salary,
        RANK() OVER (PARTITION BY department_id ORDER BY salary DESC) as rnk
    FROM employees
)
SELECT 
    department_id,
    employee_id,
    salary
FROM RankedEmployees
WHERE rnk = 1;

To find the top $N$ employees (e.g., top 2), you simply adjust the outer filter:

WHERE rnk <= 2;

4. Handling Ties: RANK vs. DENSE_RANK vs. ROW_NUMBER

When filtering for top-performing records, the choice of window function determines how ties are handled. This is a critical edge case that interviewers watch closely.

Visualizing the Difference

Assume Department 200 has two employees tied for the highest salary ($15,000), and a third employee earning $12,000.

5. The "Ask the Business" Interview Strategy

In an interview, if a ranking question involves potential ties, do not make assumptions. Proactively ask the interviewer how the business wants to handle ties. This demonstrates senior-level engineering maturity.

Tie-Breaking Scenarios to Propose

1. Deterministic Tie-Breaking (Using a Secondary Column): If two employees have the same salary, use a secondary attribute (such as employee_age or hire_date) to break the tie.
   SQL

   Copy

   -- Older employees get priority in a tie
   ROW_NUMBER() OVER (PARTITION BY department_id ORDER BY salary DESC, employee_age DESC)
   

2. Inclusive Ranking (Return All Tied Records): If there is a tie for the highest salary, return all tied employees. In this case, use RANK() or DENSE_RANK().
3. Arbitrary Selection: If the business does not care which record is returned in a tie, use ROW_NUMBER().

6. Introduction to Self-Joins

A Self-Join is not a distinct SQL command; it is a standard inner or left join where a table is joined to itself.

Why Do We Need Self-Joins?

We use self-joins when a single table contains a hierarchical relationship or a self-referential foreign key. The most common real-world example is an employee table where each employee row contains a manager_id pointing to another employee's employee_id within the same table.

The Mental Model

To write a self-join without getting confused, visualize the single physical table as two separate, logical tables in memory:

1. Table E (Employees): Represents the entity acting as the subordinate.
2. Table M (Managers): Represents the entity acting as the supervisor.

7. Step-by-Step Flow: Resolving Employee-Manager Relationships

Let us trace how a self-join resolves the classic interview question: "Find all employees who earn more than their direct managers."

Step 1: Analyze the Table Schema

Assume an employees table with the following structure:

• employee_id (Primary Key)
• employee_name
• salary
• manager_id (Foreign Key referencing employee_id)

Step 2: Map the Join Condition

To link each employee to their manager, we must match the employee's manager_id to the manager's employee_id:

Step 3: Write the Query

We perform an inner join on the self-referential keys and apply a filter in the WHERE clause to compare their salaries.

SELECT 
    e.employee_name AS employee_name,
    e.salary AS employee_salary,
    m.employee_name AS manager_name,
    m.salary AS manager_salary
FROM employees e
INNER JOIN employees m 
    ON e.manager_id = m.employee_id
WHERE e.salary > m.salary;

Step 4: Execution Flow Diagram

8. Summary and Key Takeaways

• Multi-Column Partitioning: You can partition window functions by multiple columns (e.g., PARTITION BY department_id, manager_id). The ranking calculations reset for every unique combination of those columns.
• Ties in Ranking: ROW_NUMBER() always returns unique values; RANK() leaves gaps after ties; DENSE_RANK() leaves no gaps.
• Interview Communication: Always ask the interviewer how to handle ties (e.g., return all tied rows, select one randomly, or use a secondary column like age to break the tie).
• Self-Joins: A self-join is a standard join where a table is joined to itself using logical aliases (e.g., FROM employees e JOIN employees m).
• Hierarchical Queries: Self-joins are the primary tool for querying parent-child or employee-manager relationships stored within a single table.
• Performance Considerations: When performing self-joins on large tables, ensure that the join columns (e.g., employee_id and manager_id) are indexed to avoid costly $O(N^2)$ nested loop operations.