Joining more than two tables in SQL - Time & Space Complexity

Time Complexity: Joining more than two tables

O(n^k)

Understanding Time Complexity

When we join more than two tables in a database query, the time it takes to get results can change a lot.

We want to understand how the work grows as we add more tables and data.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT orders.id, customers.name, products.title
FROM orders
JOIN customers ON orders.customer_id = customers.id
JOIN products ON orders.product_id = products.id;
    

This query joins three tables: orders, customers, and products to get order details with customer and product info.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Matching rows between tables using join conditions.
• How many times: For each row in the first table, the database looks for matching rows in the second, then for each of those matches, it looks in the third table.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Approx. Operations
10 rows per table	About 10 x 10 x 10 = 1,000 checks
100 rows per table	About 100 x 100 x 100 = 1,000,000 checks
1,000 rows per table	About 1,000 x 1,000 x 1,000 = 1,000,000,000 checks

Pattern observation: The work grows very fast as we add more rows because each join multiplies the checks needed.

Final Time Complexity

Time Complexity: O(n^k)

This means the time grows roughly by the number of rows to the power of how many tables we join.

Common Mistake

[X] Wrong: "Joining more tables just adds a little more time, like adding numbers."

[OK] Correct: Actually, each join multiplies the work because the database checks combinations of rows, not just adds them.

Interview Connect

Understanding how joining multiple tables affects time helps you write better queries and explain your thinking clearly in interviews.

Self-Check

"What if we added an index on the join columns? How would the time complexity change?"

Practice

1. What is the main purpose of joining more than two tables in SQL?

easy

A. To combine related data from multiple tables into one result set

B. To delete data from multiple tables at once

C. To create new tables automatically

D. To backup tables in the database

Solution

1. Step 1: Understand the concept of JOIN

   JOIN is used to combine rows from two or more tables based on related columns.

2. Step 2: Apply to multiple tables

   Joining more than two tables extends this idea to combine data from several tables into one result.

3. Final Answer:

   To combine related data from multiple tables into one result set -> Option A

4. Quick Check:

   Joining multiple tables = combine data [OK]

Hint: Joining means combining data from tables step-by-step [OK]

Common Mistakes:

• Thinking JOIN deletes or creates tables
• Confusing JOIN with backup or delete operations
• Assuming JOIN works without conditions

2. Which of the following is the correct syntax to join three tables A, B, and C on columns A.id = B.a_id and B.id = C.b_id?

easy

A. SELECT * FROM A, B, C WHERE A.id = B.a_id, B.id = C.b_id;

B. SELECT * FROM A JOIN B ON A.id = B.a_id, C ON B.id = C.b_id;

C. SELECT * FROM A JOIN B JOIN C ON A.id = B.a_id AND B.id = C.b_id;

D. SELECT * FROM A JOIN B ON A.id = B.a_id JOIN C ON B.id = C.b_id;

Solution

1. Step 1: Check JOIN syntax for multiple tables

   Each JOIN must have its own ON condition to specify how tables connect.

2. Step 2: Validate SELECT * FROM A JOIN B ON A.id = B.a_id JOIN C ON B.id = C.b_id;

   SELECT * FROM A JOIN B ON A.id = B.a_id JOIN C ON B.id = C.b_id; correctly joins A to B with ON, then B to C with ON separately.

3. Final Answer:

   SELECT * FROM A JOIN B ON A.id = B.a_id JOIN C ON B.id = C.b_id; -> Option D

4. Quick Check:

   Each JOIN needs its own ON condition [OK]

Hint: Use separate ON for each JOIN clause [OK]

Common Mistakes:

• Combining multiple ON conditions in one JOIN
• Using commas with JOIN incorrectly
• Missing ON clause for a JOIN

3. Given tables:
Students(id, name),
Enrollments(student_id, course_id),
Courses(id, title)
What will the query below return?

SELECT Students.name, Courses.title FROM Students JOIN Enrollments ON Students.id = Enrollments.student_id JOIN Courses ON Enrollments.course_id = Courses.id;

medium

A. List of all students and all courses regardless of enrollment

B. List of student names with the titles of courses they are enrolled in

C. List of courses with no students enrolled

D. Syntax error due to missing WHERE clause

Solution

1. Step 1: Analyze JOINs in the query

   Students join Enrollments on student ID, then Enrollments join Courses on course ID, linking students to their courses.

2. Step 2: Understand SELECT output

   The query selects student names and course titles for matching enrollments, showing which student is in which course.

3. Final Answer:

   List of student names with the titles of courses they are enrolled in -> Option B

4. Quick Check:

   JOINs link students to their courses [OK]

Hint: JOIN chains link related data stepwise [OK]

Common Mistakes:

• Thinking JOIN returns all combinations without conditions
• Expecting courses without students to appear
• Assuming WHERE is required for JOIN

4. Identify the error in the following SQL query joining three tables:

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

medium

A. Missing WHERE clause for filtering

B. No error, query is correct

C. JOIN condition for table C should use B's columns, not A's

D. JOIN keyword is missing before table C

Solution

1. Step 1: Review JOIN conditions

   First JOIN connects A and B on A.id = B.a_id, which is correct.

2. Step 2: Check second JOIN condition

   Second JOIN connects C using A.id = C.a_id, but logically C should join via B, not A, to maintain correct relationships.

3. Final Answer:

   JOIN condition for table C should use B's columns, not A's -> Option C

4. Quick Check:

   JOIN conditions must link correct tables [OK]

Hint: Check JOIN ON uses correct table columns [OK]

Common Mistakes:

• Using wrong table columns in JOIN condition
• Assuming WHERE is needed for JOIN
• Ignoring logical table relationships

5. You have tables:
Orders(order_id, customer_id),
Customers(customer_id, name),
Payments(payment_id, order_id, amount).
Write a query to find each customer's name and the total amount they paid across all orders. Which query is correct?

hard

A. SELECT Customers.name, SUM(Payments.amount) FROM Customers JOIN Orders ON Customers.customer_id = Orders.customer_id JOIN Payments ON Orders.order_id = Payments.order_id GROUP BY Customers.name;

B. SELECT Customers.name, Payments.amount FROM Customers JOIN Orders ON Customers.customer_id = Orders.customer_id JOIN Payments ON Orders.order_id = Payments.order_id;

C. SELECT Customers.name, SUM(Payments.amount) FROM Customers, Orders, Payments WHERE Customers.customer_id = Orders.customer_id AND Orders.order_id = Payments.order_id;

D. SELECT Customers.name, SUM(Payments.amount) FROM Customers JOIN Payments ON Customers.customer_id = Payments.order_id GROUP BY Customers.name;

Solution

1. Step 1: Understand the relationships

   Customers link to Orders by customer_id; Orders link to Payments by order_id.

2. Step 2: Check aggregation and grouping

   We need total payment per customer, so SUM and GROUP BY Customers.name are required.

3. Step 3: Validate options

   SELECT Customers.name, SUM(Payments.amount) FROM Customers JOIN Orders ON Customers.customer_id = Orders.customer_id JOIN Payments ON Orders.order_id = Payments.order_id GROUP BY Customers.name; correctly joins tables and groups by customer name with SUM of payments. SELECT Customers.name, Payments.amount FROM Customers JOIN Orders ON Customers.customer_id = Orders.customer_id JOIN Payments ON Orders.order_id = Payments.order_id; lacks aggregation. SELECT Customers.name, SUM(Payments.amount) FROM Customers, Orders, Payments WHERE Customers.customer_id = Orders.customer_id AND Orders.order_id = Payments.order_id; misses GROUP BY. SELECT Customers.name, SUM(Payments.amount) FROM Customers JOIN Payments ON Customers.customer_id = Payments.order_id GROUP BY Customers.name; joins wrong columns.

4. Final Answer:

   SELECT Customers.name, SUM(Payments.amount) FROM Customers JOIN Orders ON Customers.customer_id = Orders.customer_id JOIN Payments ON Orders.order_id = Payments.order_id GROUP BY Customers.name; -> Option A

5. Quick Check:

   JOIN + SUM + GROUP BY = correct total per customer [OK]

Hint: Use JOINs with GROUP BY and SUM for totals [OK]

Common Mistakes:

• Missing GROUP BY when using SUM
• Joining tables on wrong columns
• Selecting aggregated and non-aggregated columns without GROUP BY