CROSS JOIN in MySQL - Time & Space Complexity

Time Complexity: CROSS JOIN

O(n x m)

Understanding Time Complexity

When we use a CROSS JOIN in SQL, we combine every row from one table with every row from another table.

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 employees
CROSS JOIN departments;
    

This query pairs each employee with every department, creating all possible combinations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Combining each row from the first table with each row from the second table.
• How many times: For every employee, the database pairs with every department.

How Execution Grows With Input

As the number of employees and departments grow, the total pairs grow much faster.

Input Size (employees x departments)	Approx. Operations
10 x 5	50
100 x 20	2,000
1,000 x 100	100,000

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

Final Time Complexity

Time Complexity: O(n x 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 amount of work, like adding rows together."

[OK] Correct: Actually, it multiplies the rows, so the work grows much faster than just adding.

Interview Connect

Understanding how CROSS JOIN scales helps you explain query costs clearly and shows you know how big data affects performance.

Self-Check

"What if we added a WHERE clause to filter rows after the CROSS JOIN? How would the time complexity change?"

Practice

1. What does a CROSS JOIN do in MySQL?

easy

A. Joins tables based on matching column values.

B. Joins tables using a condition on a specific column.

C. Returns only rows that exist in both tables.

D. Pairs every row from the first table with every row from the second table.

Solution

1. Step 1: Understand the definition of CROSS JOIN

   A CROSS JOIN returns the Cartesian product of two tables, pairing each row of the first table with every row of the second table.

2. Step 2: Compare with other join types

   Other joins like INNER JOIN or LEFT JOIN use matching conditions, but CROSS JOIN does not use any condition and pairs all rows.

3. Final Answer:

   Pairs every row from the first table with every row from the second table. -> Option D

4. Quick Check:

   CROSS JOIN = all combinations [OK]

Hint: CROSS JOIN = all possible pairs between tables [OK]

Common Mistakes:

• Confusing CROSS JOIN with INNER JOIN
• Thinking CROSS JOIN filters rows
• Assuming CROSS JOIN requires ON condition

2. Which of the following is the correct syntax for a CROSS JOIN in MySQL?

easy

A. SELECT * FROM table1 CROSS JOIN table2;

B. SELECT * FROM table1 JOIN table2 ON table1.id = table2.id;

C. SELECT * FROM table1 INNER JOIN table2 WHERE table1.id = table2.id;

D. SELECT * FROM table1 LEFT JOIN table2 USING (id);

Solution

1. Step 1: Identify the CROSS JOIN syntax

   The correct syntax for CROSS JOIN is: SELECT * FROM table1 CROSS JOIN table2;

2. Step 2: Differentiate from other join syntaxes

   Other options use INNER JOIN or LEFT JOIN with conditions, which are not CROSS JOIN syntax.

3. Final Answer:

   SELECT * FROM table1 CROSS JOIN table2; -> Option A

4. Quick Check:

   Use CROSS JOIN keyword for Cartesian product [OK]

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

Common Mistakes:

• Using ON clause with CROSS JOIN
• Confusing CROSS JOIN with INNER JOIN syntax
• Using WHERE instead of ON for joins

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

Table B: color
'Red'
'Blue'

What is the result of SELECT * FROM A CROSS JOIN B;?

medium

A. Four rows: (1, 'Red'), (1, 'Blue'), (2, 'Red'), (2, 'Blue')

B. Two rows: (1, 'Blue'), (2, 'Red')

C. No rows, because no join condition

D. Two rows: (1, 'Red'), (2, 'Blue')

Solution

1. Step 1: Understand CROSS JOIN output

   CROSS JOIN pairs every row from Table A with every row from Table B, creating all combinations.

2. Step 2: Calculate combinations

   Table A has 2 rows, Table B has 2 rows, so total rows = 2 * 2 = 4. The pairs are (1, 'Red'), (1, 'Blue'), (2, 'Red'), (2, 'Blue').

3. Final Answer:

   Four rows: (1, 'Red'), (1, 'Blue'), (2, 'Red'), (2, 'Blue') -> Option A

4. Quick Check:

   Rows = 2 * 2 = 4 [OK]

Hint: Multiply row counts of both tables for CROSS JOIN rows [OK]

Common Mistakes:

• Assuming CROSS JOIN filters rows
• Counting only matching rows
• Ignoring all combinations

4. Consider this query:
SELECT * FROM employees CROSS JOIN departments ON employees.id = departments.id;
What is the error in this query?

medium

A. The query will return only matching rows between employees and departments.

B. The ON clause is correct and filters rows properly.

C. CROSS JOIN cannot have an ON clause; it causes a syntax error.

D. The query will return no rows because of wrong ON condition.

Solution

1. Step 1: Check CROSS JOIN syntax rules

   CROSS JOIN does not accept an ON clause because it returns all combinations without filtering.

2. Step 2: Identify the error

   Using ON with CROSS JOIN causes a syntax error in MySQL.

3. Final Answer:

   CROSS JOIN cannot have an ON clause; it causes a syntax error. -> Option C

4. Quick Check:

   ON clause invalid with CROSS JOIN [OK]

Hint: No ON clause allowed with CROSS JOIN [OK]

Common Mistakes:

• Adding ON clause to CROSS JOIN
• Confusing CROSS JOIN with INNER JOIN
• Expecting filtered results from CROSS JOIN

5. You have two tables:
Products (product_id, name) with 3 rows,
Colors (color_id, color_name) with 4 rows.
You want to generate a list of all possible product-color combinations.
Which query correctly achieves this?

hard

A. SELECT product_id, color_name FROM Products INNER JOIN Colors ON Products.product_id = Colors.color_id;

B. SELECT product_id, color_name FROM Products CROSS JOIN Colors;

C. SELECT product_id, color_name FROM Products LEFT JOIN Colors ON Products.product_id = Colors.color_id;

D. SELECT product_id, color_name FROM Products JOIN Colors WHERE Products.product_id = Colors.color_id;

Solution

1. Step 1: Understand the goal

   We want all possible combinations of products and colors, which means pairing every product with every color.

2. Step 2: Choose the correct join type

   CROSS JOIN produces the Cartesian product, giving all combinations. INNER JOIN or LEFT JOIN with conditions only return matching rows, which is not desired here.

3. Final Answer:

   SELECT product_id, color_name FROM Products CROSS JOIN Colors; -> Option B

4. Quick Check:

   Use CROSS JOIN for all combinations [OK]

Hint: Use CROSS JOIN to get all product-color pairs [OK]

Common Mistakes:

• Using INNER JOIN expecting all combinations
• Adding ON condition that filters rows
• Using WHERE instead of CROSS JOIN