Cartesian product and joins in DBMS Theory - Time & Space Complexity

Time Complexity: Cartesian product and joins

O(n × m)

Understanding Time Complexity

When working with database tables, it's important to know how the time to get results grows as tables get bigger.

We want to understand how the cost of combining tables changes with their size.

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM TableA
CROSS JOIN TableB;
    

This query returns every possible pair of rows from TableA and TableB, called the Cartesian product.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: For each row in TableA, the database pairs it with every row in TableB.
• How many times: If TableA has n rows and TableB has m rows, this pairing happens n × m times.

How Execution Grows With Input

As the number of rows grows, the total pairs grow much faster.

Input Size (n rows in TableA, m rows in TableB)	Approx. Operations (pairs)
10, 10	100
100, 100	10,000
1000, 1000	1,000,000

Pattern observation: Doubling the size of both tables causes the total pairs to grow by four times, showing a multiplication effect.

Final Time Complexity

Time Complexity: O(n × m)

This means the time to get results grows proportionally to the product of the number of rows in both tables.

Common Mistake

[X] Wrong: "The time grows only with the size of one table because we just scan one table at a time."

[OK] Correct: Because the query pairs every row from one table with every row from the other, both table sizes multiply the work, not just one.

Interview Connect

Understanding how joins and Cartesian products scale helps you explain query performance clearly and shows you can think about database efficiency in real situations.

Self-Check

What if we changed the CROSS JOIN to an INNER JOIN with a condition that matches only some rows? How would the time complexity change?

Practice

1. What does a Cartesian product between two tables produce?

easy

A. Only rows with matching values in both tables

B. All possible pairs of rows from both tables

C. Only rows from the first table

D. Only rows from the second table

Solution

1. Step 1: Understand Cartesian product definition

   A Cartesian product combines every row of the first table with every row of the second table.

2. Step 2: Identify the result of combining rows

   This means the total rows in the result equal the number of rows in the first table multiplied by the number of rows in the second table.

3. Final Answer:

   All possible pairs of rows from both tables -> Option B

4. Quick Check:

   Cartesian product = all pairs [OK]

Hint: Cartesian product pairs every row with every other row [OK]

Common Mistakes:

• Confusing Cartesian product with INNER JOIN
• Thinking it returns only matching rows
• Assuming it returns rows from only one table

2. Which SQL keyword is used to combine rows from two tables based on a matching condition?

easy

A. GROUP BY

B. CROSS JOIN

C. UNION

D. INNER JOIN

Solution

1. Step 1: Identify join types

   INNER JOIN combines rows from two tables where a specified condition matches.

2. Step 2: Match keyword to function

   CROSS JOIN produces Cartesian product, UNION combines result sets vertically, GROUP BY groups rows. Only INNER JOIN matches rows based on condition.

3. Final Answer:

   INNER JOIN -> Option D

4. Quick Check:

   Matching rows use INNER JOIN [OK]

Hint: INNER JOIN returns only matching rows [OK]

Common Mistakes:

• Choosing CROSS JOIN for matching rows
• Confusing UNION with JOIN
• Using GROUP BY to combine tables

3. Consider two tables:
Table A: IDs 1, 2
Table B: IDs 3, 4
What is the number of rows returned by SELECT * FROM A CROSS JOIN B;?

medium

A. 4

B. 0

C. 1

D. 2

Solution

1. Step 1: Count rows in each table

   Table A has 2 rows, Table B has 2 rows.

2. Step 2: Calculate Cartesian product size

   CROSS JOIN returns all pairs: 2 rows * 2 rows = 4 rows.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   2 * 2 = 4 rows [OK]

Hint: Multiply row counts for CROSS JOIN result size [OK]

Common Mistakes:

• Counting only rows from one table
• Confusing CROSS JOIN with INNER JOIN
• Assuming zero rows if no matching IDs

4. Identify the error in this SQL query:
SELECT * FROM Employees INNER JOIN Departments;

medium

A. SELECT * is invalid syntax

B. INNER JOIN cannot be used with two tables

C. Missing ON clause for join condition

D. Departments table does not exist

Solution

1. Step 1: Review INNER JOIN syntax

   INNER JOIN requires an ON clause to specify how tables relate.

2. Step 2: Check query for ON clause

   The query lacks ON condition, so SQL cannot match rows properly.

3. Final Answer:

   Missing ON clause for join condition -> Option C

4. Quick Check:

   INNER JOIN needs ON clause [OK]

Hint: Always include ON clause with INNER JOIN [OK]

Common Mistakes:

• Omitting ON clause in JOIN
• Thinking INNER JOIN works without condition
• Assuming SELECT * is incorrect

5. You have two tables:
Students (id, name)
Grades (student_id, score)
Which join will return all students and their scores, showing NULL if a student has no grade?

hard

A. LEFT JOIN

B. INNER JOIN

C. RIGHT JOIN

D. CROSS JOIN

Solution

1. Step 1: Understand join types and requirements

   LEFT JOIN returns all rows from the left table (Students) and matching rows from the right (Grades). If no match, NULL appears.

2. Step 2: Match requirement to join type

   We want all students even if they have no grades, so LEFT JOIN is correct.

3. Final Answer:

   LEFT JOIN -> Option A

4. Quick Check:

   All left table rows with NULL for no match = LEFT JOIN [OK]

Hint: LEFT JOIN keeps all left table rows, fills NULL if no match [OK]

Common Mistakes:

• Using INNER JOIN which excludes unmatched rows
• Choosing RIGHT JOIN which keeps right table rows
• Confusing CROSS JOIN with conditional joins