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