Last Minute SQL Interview Prep Kit: Finding Nth Highest Salaries & Transaction Analysis

This chapter demystifies one of the most common and tricky SQL interview topics: how different types of joins handle duplicate keys and non-matching records. Through step-by-step scenarios, mathematical formulations, and execution flows, we will analyze how INNER JOIN, LEFT JOIN, RIGHT JOIN, and FULL OUTER JOIN calculate output row counts when tables contain duplicate values and nulls.

1. The Core Problem: How SQL Joins Handle Duplicate Keys

In SQL interviews, candidates are frequently presented with two simple tables containing duplicate keys and asked to calculate the exact number of output records for various join types. This is a classic screening question designed to test whether you truly understand the underlying mechanics of relational database engines or if you merely memorize syntax.

The Machine vs. Human Mental Model

When a human looks at two tables and is asked to join them on a key, they might intuitively try to pair them one-to-one. However, a database engine is a machine. It cannot arbitrarily decide which duplicate key in Table A matches which duplicate key in Table B.

Structure & Concept Flow

Table T1 (Left) Table T2 (Right)

ID ID

---- ----

1 1

When the database engine processes the first record (1) from T1, it scans T2 and finds three matching records (1, 1, 1). Because it cannot differentiate between these three identical values, it must join with all three. When it processes the second record (1) from T1, it repeats this process, matching with all three records in T2 again.

2. Mental Model & Mathematical Formulas for Join Calculations

To accurately predict join outputs without running the queries, we can establish a set of mathematical formulas based on key frequencies.

Let:

$L_k$ be the number of times a join key $k$ appears in the Left Table ( $T_1$ ).
$R_k$ be the number of times a join key $k$ appears in the Right Table ( $T_2$ ).
$U_L$ be the number of unique non-matching keys in the Left Table ( $T_1$ ).
$U_R$ be the number of unique non-matching keys in the Right Table ( $T_2$ ).

Mathematical Formulas by Join Type

1. Inner Join

An inner join only returns records where the join key exists in both tables. For each matching key $k$ :

\text{Rows}_{\text{Inner}} = \sum (L_k \times R_k)

2. Left Join

A left join returns all matching records plus all non-matching records from the left table (padded with NULL values for the right table's columns):

\text{Rows}_{\text{Left}} = \text{Rows}_{\text{Inner}} + U_L

3. Right Join

A right join returns all matching records plus all non-matching records from the right table (padded with NULL values for the left table's columns):

\text{Rows}_{\text{Right}} = \text{Rows}_{\text{Inner}} + U_R

4. Full Outer Join

A full outer join returns all matching records plus all non-matching records from both the left and right tables:

\text{Rows}_{\text{Full}} = \text{Rows}_{\text{Inner}} + U_L + U_R

Rule of Thumb: If all keys in both tables are matching (i.e., there are no non-matching keys, meaning $U_L = 0$ and $U_R = 0$ ), then the output row count for all four join types will be exactly the same as the INNER JOIN.

3. Scenario 1: Pure Duplicate Keys (No Non-Matching Records)

Let's begin with the first scenario demonstrated in the lecture, where both tables contain only matching keys with duplicate values.

Database Setup

SQL

CREATE TABLE t1 (
    id INT
);

CREATE TABLE t2 (
    id INT
);

-- Insert duplicate matching keys
INSERT INTO t1 (id) VALUES (1), (1);
INSERT INTO t2 (id) VALUES (1), (1), (1);

Table State

t1 (Left Table): Contains two records of value 1 ( $L_1 = 2$ ).
t2 (Right Table): Contains three records of value 1 ( $R_1 = 3$ ).
Non-matching keys in t1 ( $U_L$ ): $0$
Non-matching keys in t2 ( $U_R$ ): $0$

Join Calculations

Inner Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
INNER JOIN t2 ON t1.id = t2.id;

Calculation: $L_1 \times R_1 = 2 \times 3 = 6$ records.
Output Row Count: $6$

Left Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
LEFT JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_L = 6 + 0 = 6$ records.
Output Row Count: $6$

Right Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
RIGHT JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_R = 6 + 0 = 6$ records.
Output Row Count: $6$

Full Outer Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
FULL OUTER JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_L + U_R = 6 + 0 + 0 = 6$ records.
Output Row Count: $6$

4. Scenario 2: Introducing Non-Matching Keys

Now, we introduce non-matching records to both tables to see how the join behaviors diverge. We add a value of 2 to t1 and a value of 3 to t2.

Database Setup

SQL

-- Add non-matching record to t1
INSERT INTO t1 (id) VALUES (2);

-- Add non-matching record to t2
INSERT INTO t2 (id) VALUES (3);

Table State

t1 (Left Table): Contains [1, 1, 2]
- $L_1 = 2$
- $L_2 = 1$ (Non-matching, as 2 does not exist in t2)
- $U_L = 1$ (The record with value 2)
t2 (Right Table): Contains [1, 1, 1, 3]
- $R_1 = 3$
- $R_3 = 1$ (Non-matching, as 3 does not exist in t1)
- $U_R = 1$ (The record with value 3)

Join Calculations

Inner Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
INNER JOIN t2 ON t1.id = t2.id;

Calculation: Only the matching key 1 is processed.

\text{Rows}_{\text{Inner}} = L_1 \times R_1 = 2 \times 3 = 6 \text{ records.}

Output Row Count: $6$

Left Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
LEFT JOIN t2 ON t1.id = t2.id;

Calculation: Matching records ( $6$ ) + non-matching records from t1 ( $1$ record with value 2).

\text{Rows}_{\text{Left}} = 6 + 1 = 7 \text{ records.}

Output Row Count: $7$
Visualizing the Output Data:
Structure & Concept Flow
t1_id | t2_id
------+------
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
2 | NULL

Right Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
RIGHT JOIN t2 ON t1.id = t2.id;

Calculation: Matching records ( $6$ ) + non-matching records from t2 ( $1$ record with value 3).

\text{Rows}_{\text{Right}} = 6 + 1 = 7 \text{ records.}

Output Row Count: $7$
Visualizing the Output Data:
Structure & Concept Flow
t1_id | t2_id
------+------
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
NULL | 3

Full Outer Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
FULL OUTER JOIN t2 ON t1.id = t2.id;

Calculation: Matching records ( $6$ ) + non-matching from t1 ( $1$ ) + non-matching from t2 ( $1$ ).

\text{Rows}_{\text{Full}} = 6 + 1 + 1 = 8 \text{ records.}

Output Row Count: $8$
Visualizing the Output Data:
Structure & Concept Flow
t1_id | t2_id
------+------
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
1 | 1
2 | NULL
NULL | 3

5. Scenario 3: Complex Duplicates on Multiple Keys

To further solidify this concept, let's add another layer of complexity by inserting another duplicate key 2 into t1, and a matching key 2 into t2.

Database Setup

SQL

-- Add another 2 to t1
INSERT INTO t1 (id) VALUES (2);

-- Add a matching 2 to t2
INSERT INTO t2 (id) VALUES (2);

Table State

t1 (Left Table): Contains [1, 1, 2, 2]
- $L_1 = 2$
- $L_2 = 2$
- $U_L = 0$ (All keys in t1 now have matches in t2)
t2 (Right Table): Contains [1, 1, 1, 2, 3]
- $R_1 = 3$
- $R_2 = 1$
- $R_3 = 1$ (Non-matching key)
- $U_R = 1$ (The record with value 3)

Join Calculations

Inner Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
INNER JOIN t2 ON t1.id = t2.id;

Calculation: We sum the products of all matching keys.
- For key 1: $L_1 \times R_1 = 2 \times 3 = 6$ records.
- For key 2: $L_2 \times R_2 = 2 \times 1 = 2$ records.

\text{Rows}_{\text{Inner}} = 6 + 2 = 8 \text{ records.}

Output Row Count: $8$

Left Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
LEFT JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_L = 8 + 0 = 8$ records.
Output Row Count: $8$

Right Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
RIGHT JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_R = 8 + 1 = 9$ records (the non-matching 3 from t2 is appended).
Output Row Count: $9$

Full Outer Join

SQL

SELECT t1.id AS t1_id, t2.id AS t2_id 
FROM t1 
FULL OUTER JOIN t2 ON t1.id = t2.id;

Calculation: $\text{Rows}_{\text{Inner}} + U_L + U_R = 8 + 0 + 1 = 9$ records.
Output Row Count: $9$

6. Tabular Synthesis of Join Behaviors

The following table synthesizes the three scenarios discussed in the lecture, showing the direct relationship between table states, join types, and output row counts.

Scenario	Left Table (`t1`) State	Right Table (`t2`) State	Join Type	Calculation Formula	Output Rows
Scenario 1	`[1, 1]`	`[1, 1, 1]`	Inner	$2 \times 3$	6
			Left	$(2 \times 3) + 0$	6
			Right	$(2 \times 3) + 0$	6
			Full Outer	$(2 \times 3) + 0 + 0$	6
Scenario 2	`[1, 1, 2]`	`[1, 1, 1, 3]`	Inner	$2 \times 3$	6
			Left	$(2 \times 3) + 1 \text{ (for key 2)}$	7
			Right	$(2 \times 3) + 1 \text{ (for key 3)}$	7
			Full Outer	$(2 \times 3) + 1 \text{ (key 2)} + 1 \text{ (key 3)}$	8
Scenario 3	`[1, 1, 2, 2]`	`[1, 1, 1, 2, 3]`	Inner	$(2 \times 3) + (2 \times 1)$	8
			Left	$((2 \times 3) + (2 \times 1)) + 0$	8
			Right	$((2 \times 3) + (2 \times 1)) + 1 \text{ (for key 3)}$	9
			Full Outer	$((2 \times 3) + (2 \times 1)) + 0 + 1 \text{ (key 3)}$	9

7. Step-by-Step Execution Flow Visualizations

To understand how the database engine processes these joins row-by-row, let us trace the execution flows.

Execution Flow: Scenario 2 Left Join

This flow shows how the database evaluates each row in the Left Table (t1 containing [1, 1, 2]) against the Right Table (t2 containing [1, 1, 1, 3]).

Structure & Concept Flow

t1 Row 1 (Value: 1)

+--> Scans t2 -> Finds Row 1 (Value: 1) ----> Output: (1, 1)

+--> Scans t2 -> Finds Row 2 (Value: 1) ----> Output: (1, 1)

+--> Scans t2 -> Finds Row 3 (Value: 1) ----> Output: (1, 1)

t1 Row 2 (Value: 1)

+--> Scans t2 -> Finds Row 1 (Value: 1) ----> Output: (1, 1)

+--> Scans t2 -> Finds Row 2 (Value: 1) ----> Output: (1, 1)

+--> Scans t2 -> Finds Row 3 (Value: 1) ----> Output: (1, 1)

t1 Row 3 (Value: 2)

+--> Scans t2 -> No match found

+--> Left Join Rule: Keep row, pad right with NULL -> Output: (2, NULL)

Execution Flow: Scenario 3 Inner Join

This flow shows how the database evaluates the updated tables (t1 containing [1, 1, 2, 2] and t2 containing [1, 1, 1, 2, 3]) under an INNER JOIN constraint.

Structure & Concept Flow

t1 Row 1 & 2 (Value: 1)

+--> Matches 3 instances of key '1' in t2

+--> Calculation: 2 rows * 3 rows

+--> Output: 6 records of (1, 1)

t1 Row 3 & 4 (Value: 2)

+--> Matches 1 instance of key '2' in t2

+--> Calculation: 2 rows * 1 row

+--> Output: 2 records of (2, 2)

t2 Row 5 (Value: 3)

+--> No match in t1

+--> Inner Join Rule: Discard non-matching keys

Total Output: 6 + 2 = 8 records

8. Summary and Key Takeaways

The Cartesian Effect on Duplicate Keys: When joining on duplicate keys, the database engine performs a Cartesian product for that specific key. If key $k$ appears $M$ times in the left table and $N$ times in the right table, the join will produce $M \times N$ records for that key.
The "All-Matching" Rule of Thumb: If every key in the left table has at least one match in the right table, and every key in the right table has at least one match in the left table, then INNER JOIN, LEFT JOIN, RIGHT JOIN, and FULL OUTER JOIN will all return the exact same number of records.
Left Join Row Count Mechanics: The row count of a LEFT JOIN is always equal to the INNER JOIN row count plus the number of non-matching records in the left table.
Right Join Row Count Mechanics: The row count of a RIGHT JOIN is always equal to the INNER JOIN row count plus the number of non-matching records in the right table.
Full Outer Join Row Count Mechanics: The row count of a FULL OUTER JOIN is the sum of the INNER JOIN row count, the non-matching left table records, and the non-matching right table records.
Handling Nulls in Joins: Non-matching records in outer joins are preserved and padded with NULL values for the columns of the opposing table.
Interview Strategy: When asked this question in an interview, do not guess. Immediately write down the frequency of each key in both tables, apply the $M \times N$ formula for each matching key, and then add the non-matching records based on the join type requested.