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?"