CROSS JOIN cartesian product in SQL - Time & Space Complexity

Time Complexity: CROSS JOIN cartesian product

O(n * m)

Understanding Time Complexity

When we use a CROSS JOIN in SQL, it combines every row from one table with every row from another. This can create a lot of results.

We want to understand how the work grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT *
FROM Products
CROSS JOIN Colors;
    

This query pairs each product with every color, creating all possible combinations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Combining each row from Products with each row from Colors.
• How many times: For every product row, the query pairs it with all color rows.

How Execution Grows With Input

As the number of products or colors grows, the total pairs grow quickly.

Input Size (Products x Colors)	Approx. Operations
10 x 5	50
100 x 50	5,000
1,000 x 500	500,000

Pattern observation: The total work grows by multiplying the sizes of both tables.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows by multiplying the number of rows in the first table (n) by the number of rows in the second table (m).

Common Mistake

[X] Wrong: "The CROSS JOIN only adds a small number of rows, so it's almost like a simple list."

[OK] Correct: Actually, the number of rows grows very fast because every row from one table pairs with every row from the other, making the result much larger than either table alone.

Interview Connect

Understanding how CROSS JOIN scales helps you explain query costs clearly and shows you can think about how data size affects performance.

Self-Check

"What if we replaced CROSS JOIN with INNER JOIN on a condition that matches fewer rows? How would the time complexity change?"

Practice

1. What does a CROSS JOIN do in SQL?

easy

A. It returns all possible combinations of rows from two tables.

B. It returns only matching rows based on a condition.

C. It deletes rows from both tables.

D. It updates rows in one table based on another.

Solution

1. Step 1: Understand the definition of CROSS JOIN

   A CROSS JOIN combines every row from the first table with every row from the second table, creating all possible pairs.

2. Step 2: Compare with other join types

   Unlike INNER JOIN or LEFT JOIN, CROSS JOIN does not require a matching condition and returns the Cartesian product.

3. Final Answer:

   It returns all possible combinations of rows from two tables. -> Option A

4. Quick Check:

   CROSS JOIN = all combinations [OK]

Hint: CROSS JOIN = multiply rows from both tables [OK]

Common Mistakes:

• Confusing CROSS JOIN with INNER JOIN
• Thinking CROSS JOIN filters rows
• Assuming CROSS JOIN deletes or updates data

2. Which of the following is the correct syntax to perform a CROSS JOIN between tables Employees and Departments?

easy

A. SELECT * FROM Employees INNER JOIN Departments;

B. SELECT * FROM Employees JOIN Departments ON Employees.id = Departments.id;

C. SELECT * FROM Employees CROSS JOIN Departments;

D. SELECT * FROM Employees WHERE CROSS JOIN Departments;

Solution

1. Step 1: Identify correct CROSS JOIN syntax

   The correct syntax uses the keyword CROSS JOIN between two table names without any ON condition.

2. Step 2: Eliminate incorrect options

   SELECT * FROM Employees JOIN Departments ON Employees.id = Departments.id; uses JOIN with ON condition (not CROSS JOIN). SELECT * FROM Employees INNER JOIN Departments; uses INNER JOIN without ON, which is invalid. SELECT * FROM Employees WHERE CROSS JOIN Departments; uses WHERE incorrectly.

3. Final Answer:

   SELECT * FROM Employees CROSS JOIN Departments; -> Option C

4. Quick Check:

   Correct CROSS JOIN syntax = SELECT * FROM Employees CROSS JOIN Departments; [OK]

Hint: CROSS JOIN uses keyword CROSS JOIN without ON clause [OK]

Common Mistakes:

• Using JOIN without ON for CROSS JOIN
• Trying to use WHERE for joining tables
• Confusing INNER JOIN with CROSS JOIN syntax

3. Given two tables:
Colors with rows: Red, Blue
Shapes with rows: Circle, Square, Triangle
What will be the result of:
SELECT Colors.color, Shapes.shape FROM Colors CROSS JOIN Shapes;

medium

A. [('Red', 'Circle'), ('Red', 'Square'), ('Red', 'Triangle'), ('Blue', 'Circle'), ('Blue', 'Square'), ('Blue', 'Triangle')]

B. [('Red', 'Circle'), ('Blue', 'Square'), ('Red', 'Triangle')]

C. [('Red', 'Circle'), ('Blue', 'Circle'), ('Red', 'Square'), ('Blue', 'Square')]

D. Empty result set

Solution

1. Step 1: Count rows in each table

   Colors has 2 rows, Shapes has 3 rows.

2. Step 2: Calculate CROSS JOIN result

   CROSS JOIN returns all pairs: 2 * 3 = 6 rows combining each color with each shape.

3. Final Answer:

   [('Red', 'Circle'), ('Red', 'Square'), ('Red', 'Triangle'), ('Blue', 'Circle'), ('Blue', 'Square'), ('Blue', 'Triangle')] -> Option A

4. Quick Check:

   2 colors * 3 shapes = 6 pairs [OK]

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

Common Mistakes:

• Listing only matching pairs instead of all combinations
• Confusing CROSS JOIN with INNER JOIN
• Ignoring total number of rows in result

4. Consider this SQL query:
SELECT * FROM A CROSS JOIN B WHERE A.id = B.id;
What is the main issue with this query?

medium

A. It will cause a syntax error because CROSS JOIN cannot have WHERE clause.

B. It updates tables A and B unintentionally.

C. It returns no rows because CROSS JOIN filters all rows.

D. It produces the same result as INNER JOIN but less efficiently.

Solution

1. Step 1: Understand CROSS JOIN with WHERE filter

   CROSS JOIN creates all pairs, then WHERE filters pairs where A.id = B.id.

2. Step 2: Compare with INNER JOIN

   This is equivalent to INNER JOIN on A.id = B.id but less efficient because CROSS JOIN generates many unnecessary pairs first.

3. Final Answer:

   It produces the same result as INNER JOIN but less efficiently. -> Option D

4. Quick Check:

   CROSS JOIN + WHERE = INNER JOIN behavior [OK]

Hint: CROSS JOIN + WHERE = INNER JOIN but slower [OK]

Common Mistakes:

• Thinking WHERE is invalid with CROSS JOIN
• Assuming CROSS JOIN filters rows automatically
• Confusing SELECT with UPDATE statements

5. You have two tables:
Products with 4 rows and Colors with 5 rows.
You want to generate a list of all product-color combinations but exclude combinations where the product is discontinued.
Which query correctly uses CROSS JOIN and filtering?

hard

A. SELECT p.name, c.color FROM Products p INNER JOIN Colors c ON p.discontinued = FALSE;

B. SELECT p.name, c.color FROM Products p CROSS JOIN Colors c WHERE p.discontinued = FALSE;

C. SELECT p.name, c.color FROM Products p CROSS JOIN Colors c ON p.discontinued = FALSE;

D. SELECT p.name, c.color FROM Products p, Colors c WHERE p.discontinued = TRUE;

Solution

1. Step 1: Use CROSS JOIN to get all combinations

   Use CROSS JOIN between Products and Colors to get every product-color pair.

2. Step 2: Filter out discontinued products

   Apply WHERE clause to keep only products where discontinued = FALSE.

3. Step 3: Check other options for errors

   SELECT p.name, c.color FROM Products p INNER JOIN Colors c ON p.discontinued = FALSE; uses INNER JOIN incorrectly with ON condition unrelated to join keys. SELECT p.name, c.color FROM Products p CROSS JOIN Colors c ON p.discontinued = FALSE; uses ON with CROSS JOIN, which is invalid syntax. SELECT p.name, c.color FROM Products p, Colors c WHERE p.discontinued = TRUE; filters discontinued = TRUE, opposite of requirement.

4. Final Answer:

   SELECT p.name, c.color FROM Products p CROSS JOIN Colors c WHERE p.discontinued = FALSE; -> Option B

5. Quick Check:

   CROSS JOIN + WHERE filters correctly [OK]

Hint: Filter after CROSS JOIN with WHERE clause [OK]

Common Mistakes:

• Using ON clause with CROSS JOIN
• Filtering with wrong discontinued value
• Confusing INNER JOIN with CROSS JOIN usage