INNER JOIN with multiple conditions in SQL - Time & Space Complexity

Time Complexity: INNER JOIN with multiple conditions

O(n * m)

Understanding Time Complexity

When we use INNER JOIN with multiple conditions, we want to know how the work grows as the tables get bigger.

We ask: How does the time to join tables change when there are more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.name
FROM tableA a
INNER JOIN tableB b
  ON a.key1 = b.key1
  AND a.key2 = b.key2
  AND a.status = b.status;
    

This query joins two tables using three conditions to match rows.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Comparing rows from tableA to rows in tableB to find matches.
• How many times: Potentially every row in tableA is compared to every row in tableB.

How Execution Grows With Input

As the number of rows in each table grows, the number of comparisons grows quickly.

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

Pattern observation: Doubling the rows causes the work to grow much faster, because each row in one table checks many rows in the other.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows roughly by multiplying the number of rows in both tables.

Common Mistake

[X] Wrong: "Adding more conditions in the JOIN makes it faster because it narrows matches early."

[OK] Correct: More conditions do not reduce the number of comparisons by themselves; the database still checks pairs of rows. The conditions just filter matches after comparing.

Interview Connect

Understanding how JOINs scale helps you explain query performance clearly and shows you can think about data size effects in real projects.

Self-Check

"What if one of the tables has an index on the join keys? How would the time complexity change?"

Practice

1. What does an INNER JOIN with multiple conditions do in SQL?

easy

A. It returns rows where all join conditions are true.

B. It returns rows where any one of the join conditions is true.

C. It returns all rows from both tables regardless of conditions.

D. It returns rows only from the first table.

Solution

1. Step 1: Understand INNER JOIN basics

   INNER JOIN returns rows that have matching values in both tables based on join conditions.

2. Step 2: Analyze multiple conditions with AND

   When multiple conditions are combined with AND, all must be true for a row to be included.

3. Final Answer:

   It returns rows where all join conditions are true. -> Option A

4. Quick Check:

   INNER JOIN + AND = all conditions true [OK]

Hint: All join conditions must be true with AND in INNER JOIN [OK]

Common Mistakes:

• Thinking any one condition is enough
• Confusing INNER JOIN with OUTER JOIN
• Ignoring the AND operator effect

2. Which of the following is the correct syntax for an INNER JOIN with two conditions on tables Orders and Customers?

easy

A. SELECT * FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.ID AND Orders.Status = Customers.Status;

B. SELECT * FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.ID OR Orders.Status = Customers.Status;

C. SELECT * FROM Orders INNER JOIN Customers WHERE Orders.CustomerID = Customers.ID AND Orders.Status = Customers.Status;

D. SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.ID, Orders.Status = Customers.Status;

Solution

1. Step 1: Identify correct JOIN syntax

   INNER JOIN requires ON keyword followed by conditions combined with AND for multiple matches.

2. Step 2: Check each option's syntax

   SELECT * FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.ID AND Orders.Status = Customers.Status; correctly uses ON with two conditions joined by AND. SELECT * FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.ID OR Orders.Status = Customers.Status; uses OR which is incorrect for multiple conditions requiring all true. SELECT * FROM Orders INNER JOIN Customers WHERE Orders.CustomerID = Customers.ID AND Orders.Status = Customers.Status; wrongly uses WHERE instead of ON. SELECT * FROM Orders JOIN Customers ON Orders.CustomerID = Customers.ID, Orders.Status = Customers.Status; has invalid syntax with comma.

3. Final Answer:

   SELECT * FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.ID AND Orders.Status = Customers.Status; -> Option A

4. Quick Check:

   INNER JOIN + ON + AND = correct syntax [OK]

Hint: Use ON with AND for multiple join conditions [OK]

Common Mistakes:

• Using OR instead of AND in ON clause
• Replacing ON with WHERE for join conditions
• Separating conditions with commas

3. Given tables Employees and Departments with columns Employees.DeptID, Departments.ID, and Departments.Location, what will this query return?

SELECT Employees.Name, Departments.Name FROM Employees INNER JOIN Departments ON Employees.DeptID = Departments.ID AND Departments.Location = 'NY';

medium

A. Syntax error due to multiple conditions in JOIN.

B. All employees with their department names regardless of location.

C. Departments located in NY with all employees listed multiple times.

D. Employees working only in departments located in NY with their department names.

Solution

1. Step 1: Understand the JOIN conditions

   The query joins Employees and Departments where DeptID matches ID and the department location is 'NY'.

2. Step 2: Analyze the result rows

   Only employees whose department is in NY will appear with their department names. Others are excluded.

3. Final Answer:

   Employees working only in departments located in NY with their department names. -> Option D

4. Quick Check:

   INNER JOIN + multiple conditions filters rows precisely [OK]

Hint: Multiple conditions filter rows strictly in INNER JOIN [OK]

Common Mistakes:

• Assuming all employees appear regardless of location
• Thinking multiple conditions cause syntax error
• Confusing join condition with WHERE clause

4. Identify the error in this SQL query:

SELECT * FROM Products INNER JOIN Suppliers ON Products.SupplierID = Suppliers.ID, Products.Category = Suppliers.Category;

medium

A. Using ON instead of WHERE for join conditions.

B. Missing WHERE clause for the second condition.

C. Using comma instead of AND to combine join conditions.

D. INNER JOIN cannot have multiple conditions.

Solution

1. Step 1: Review JOIN condition syntax

   Multiple join conditions must be combined with AND inside the ON clause.

2. Step 2: Identify the error in the query

   The query incorrectly uses a comma to separate conditions, which is invalid syntax.

3. Final Answer:

   Using comma instead of AND to combine join conditions. -> Option C

4. Quick Check:

   Multiple conditions joined by AND, not comma [OK]

Hint: Use AND, not comma, to join multiple ON conditions [OK]

Common Mistakes:

• Separating conditions with commas
• Confusing WHERE and ON clauses
• Believing INNER JOIN allows only one condition

5. You have two tables: Orders(OrderID, CustomerID, Status) and Customers(CustomerID, Country, Status). You want to find orders where the customer is from 'USA' and both order and customer have the same status. Which query correctly uses INNER JOIN with multiple conditions?

hard

A. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID WHERE Customers.Country = 'USA' AND Orders.Status = Customers.Status;

B. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID AND Customers.Country = 'USA' AND Orders.Status = Customers.Status;

C. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID OR Customers.Country = 'USA' AND Orders.Status = Customers.Status;

D. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID, Customers.Country = 'USA', Orders.Status = Customers.Status;

Solution

1. Step 1: Understand the filtering requirements

   We need to join on CustomerID and filter where customer is from USA and order status matches customer status.

2. Step 2: Check correct use of multiple conditions in INNER JOIN

   SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID AND Customers.Country = 'USA' AND Orders.Status = Customers.Status; correctly uses AND to combine all conditions inside ON clause. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID OR Customers.Country = 'USA' AND Orders.Status = Customers.Status; wrongly uses OR which changes logic. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID WHERE Customers.Country = 'USA' AND Orders.Status = Customers.Status; moves conditions to WHERE, which is valid but not the question's focus on multiple ON conditions. SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID, Customers.Country = 'USA', Orders.Status = Customers.Status; uses commas incorrectly.

3. Final Answer:

   SELECT Orders.OrderID FROM Orders INNER JOIN Customers ON Orders.CustomerID = Customers.CustomerID AND Customers.Country = 'USA' AND Orders.Status = Customers.Status; -> Option B

4. Quick Check:

   Multiple AND conditions inside ON for precise join [OK]

Hint: Combine all join filters with AND inside ON clause [OK]

Common Mistakes:

• Using OR instead of AND in join conditions
• Placing join filters in WHERE instead of ON
• Separating conditions with commas