NULLs in JOIN conditions in SQL - Time & Space Complexity

Time Complexity: NULLs in JOIN conditions

O(n * m)

Understanding Time Complexity

When we join tables in a database, the time it takes depends on how many rows we compare. NULL values in join conditions can affect which rows match, but how does this impact the work done?

We want to understand how the presence of NULLs in join conditions affects the number of operations the database performs.

Scenario Under Consideration

Analyze the time complexity of the following SQL join with NULLs in the condition.

SELECT a.id, b.id
FROM tableA a
LEFT JOIN tableB b
  ON a.key = b.key
  OR (a.key IS NULL AND b.key IS NULL);
    

This query joins two tables on a key column, treating NULLs as equal to each other in the join condition.

Identify Repeating Operations

Look for repeated comparisons between rows.

• Primary operation: Comparing each row in tableA to rows in tableB to find matches.
• How many times: Potentially every row in tableA checks against many rows in tableB, especially if no indexes help.

How Execution Grows With Input

As the number of rows grows, the comparisons increase.

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 quickly as the tables get bigger, roughly multiplying the number of rows in both tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of rows in the first table by the number of rows in the second table.

Common Mistake

[X] Wrong: "Adding NULL checks in the join condition makes the query faster because it filters rows early."

[OK] Correct: The NULL checks add complexity to each comparison and do not reduce the number of comparisons, so the total work can stay the same or increase.

Interview Connect

Understanding how NULLs affect join conditions helps you explain query performance clearly. This skill shows you can think about how databases work behind the scenes, which is valuable in many real projects.

Self-Check

What if we replaced the OR condition with a COALESCE function to handle NULLs? How would that change the time complexity?

Practice

1. What happens when you use an INNER JOIN on columns that contain NULL values in SQL?

easy

A. Rows with NULL in join columns are always included.

B. Rows with NULL in join columns are excluded from the result.

C. The query returns an error due to NULL values.

D. Rows with NULL are treated as equal and joined together.

Solution

1. Step 1: Understand how INNER JOIN works with = condition

   When joining tables, SQL compares join columns using =. If a column has NULL, it means unknown, so comparison fails.

2. Step 2: Effect of NULL in join columns

   Since NULL = NULL is not true, rows with NULL in join columns do not match and are excluded.

3. Final Answer:

   Rows with NULL in join columns are excluded from the result. -> Option B

4. Quick Check:

   NULL means unknown, so no match [OK]

Hint: Remember: NULL never equals NULL in joins [OK]

Common Mistakes:

• Assuming NULL equals NULL in join conditions
• Expecting NULL rows to appear in INNER JOIN results
• Thinking NULL causes query errors in JOIN

2. Which of the following SQL JOIN syntaxes correctly includes rows with NULL values in the join column from the left table?

easy

A. SELECT * FROM A INNER JOIN B ON A.id = B.id;

B. SELECT * FROM A RIGHT JOIN B ON A.id = B.id;

C. SELECT * FROM A LEFT JOIN B ON A.id = B.id;

D. SELECT * FROM A FULL JOIN B ON A.id = B.id WHERE A.id IS NOT NULL;

Solution

1. Step 1: Identify JOIN types that keep left table rows

   LEFT JOIN keeps all rows from the left table, including those with NULL in join columns.

2. Step 2: Check other options

   INNER JOIN excludes unmatched rows; RIGHT JOIN keeps right table rows; FULL JOIN keeps all but filtering with WHERE A.id IS NOT NULL removes left table NULLs.

3. Final Answer:

   SELECT * FROM A LEFT JOIN B ON A.id = B.id; -> Option C

4. Quick Check:

   LEFT JOIN keeps left rows even if join column is NULL [OK]

Hint: Use LEFT JOIN to keep left table NULL rows [OK]

Common Mistakes:

• Using INNER JOIN expecting NULL rows to appear
• Filtering NULLs after FULL JOIN with WHERE clause
• Confusing RIGHT JOIN with LEFT JOIN behavior

3. Given tables:
Table A: id
1
2
NULL

Table B: id
2
NULL

What is the result of this query?

SELECT A.id, B.id FROM A INNER JOIN B ON A.id = B.id;

medium

A. (1, 2), (2, 2), (NULL, NULL)

B. (NULL, NULL)

C. (1, 2), (2, 2)

D. (2, 2)

Solution

1. Step 1: Understand INNER JOIN with NULLs

   INNER JOIN matches rows where A.id = B.id. NULLs do not match anything, even NULL.

2. Step 2: Check matching rows

   Only A.id = 2 matches B.id = 2. Rows with NULL do not match.

3. Final Answer:

   (2, 2) -> Option D

4. Quick Check:

   NULLs do not match, only 2 joins [OK]

Hint: NULLs never match in INNER JOIN conditions [OK]

Common Mistakes:

• Including NULL = NULL as a match
• Assuming all rows join regardless of NULL
• Confusing INNER JOIN with OUTER JOIN behavior

4. You wrote this query:

SELECT * FROM A LEFT JOIN B ON A.id = B.id WHERE B.id IS NOT NULL;

But it returns no rows, even though you expect rows from A with NULL id. What is the likely problem?

medium

A. The WHERE B.id IS NOT NULL filters out all rows including those with NULL in A.id.

B. LEFT JOIN does not include rows with NULL in join columns.

C. You should use INNER JOIN instead of LEFT JOIN.

D. The join condition A.id = B.id causes a syntax error.

Solution

1. Step 1: Understand LEFT JOIN with WHERE filter

   LEFT JOIN keeps all A rows, but WHERE B.id IS NOT NULL filters only rows where B.id is NOT NULL after join.

2. Step 2: Effect on rows with NULL in A.id

   Rows with NULL in A.id do not match B.id, so B.id is NULL after the join. The WHERE B.id IS NOT NULL condition excludes these rows.

3. Final Answer:

   The WHERE B.id IS NOT NULL filters out all rows including those with NULL in A.id. -> Option A

4. Quick Check:

   WHERE filters after join, can exclude expected rows [OK]

Hint: Remember WHERE filters after JOIN, can exclude NULL rows [OK]

Common Mistakes:

• Thinking LEFT JOIN excludes NULL join columns
• Using INNER JOIN expecting NULL rows
• Assuming join condition causes syntax error

5. You want to join tables A and B on id columns, but include rows where id is NULL in either table. Which query correctly returns all rows from both tables, matching on id including NULLs treated as equal?

hard

A. SELECT * FROM A FULL JOIN B ON A.id = B.id OR (A.id IS NULL AND B.id IS NULL);

B. SELECT * FROM A FULL JOIN B ON A.id = B.id;

C. SELECT * FROM A INNER JOIN B ON A.id = B.id OR (A.id IS NULL AND B.id IS NULL);

D. SELECT * FROM A LEFT JOIN B ON A.id = B.id WHERE A.id IS NOT NULL;

Solution

1. Step 1: Understand FULL JOIN and NULL behavior

   FULL JOIN returns all rows from both tables, but A.id = B.id excludes NULL matches because NULL = NULL is false.

2. Step 2: Add explicit NULL check in join condition

   Using OR (A.id IS NULL AND B.id IS NULL) treats NULLs as equal, including those rows in join results.

3. Step 3: Check other options

   SELECT * FROM A FULL JOIN B ON A.id = B.id;

   excludes NULL matches;

   SELECT * FROM A INNER JOIN B ON A.id = B.id OR (A.id IS NULL AND B.id IS NULL);

   uses INNER JOIN, excluding unmatched rows;

   SELECT * FROM A LEFT JOIN B ON A.id = B.id WHERE A.id IS NOT NULL;

   filters out NULLs.

4. Final Answer:

   SELECT * FROM A FULL JOIN B ON A.id = B.id OR (A.id IS NULL AND B.id IS NULL); -> Option A

5. Quick Check:

   Explicit NULL checks in JOIN condition include NULL matches [OK]

Hint: Add IS NULL checks in JOIN to match NULLs explicitly [OK]

Common Mistakes:

• Assuming NULL = NULL matches automatically
• Using INNER JOIN instead of FULL JOIN for all rows
• Filtering NULLs unintentionally with WHERE clause