CROSS JOIN behavior in PostgreSQL - Time & Space Complexity

Time Complexity: CROSS JOIN behavior

O(n * m)

Understanding Time Complexity

When using CROSS JOIN in SQL, it combines every row from one table with every row from another. Understanding how this grows helps us know how long queries might take as tables get bigger.

We want to see how the work done increases when the tables have more rows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.name
FROM table_a a
CROSS JOIN table_b b;
    

This query pairs every row from table_a with every row from table_b, producing all possible combinations.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Combining each row of table_a with each row of table_b.
• How many times: For every row in table_a, the operation repeats for every row in table_b.

How Execution Grows With Input

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

Input Size (rows in each table)	Approx. Output Rows
10	10 x 10 = 100
100	100 x 100 = 10,000
1000	1000 x 1000 = 1,000,000

Pattern observation: The total combinations grow by multiplying the sizes, so doubling the size of both tables makes the work four times bigger.

Final Time Complexity

Time Complexity: O(n * m)

This means the work grows by multiplying the number of rows in the first table by the number of rows in the second table.

Common Mistake

[X] Wrong: "The time grows just like the bigger table's size."

[OK] Correct: Because CROSS JOIN pairs every row from one table with every row from the other, the total work depends on both tables multiplied, not just the bigger one.

Interview Connect

Knowing how CROSS JOIN scales helps you explain query performance clearly and shows you understand how databases handle combining data. This skill is useful when discussing query design and optimization.

Self-Check

"What if one table has an index or filter applied before the CROSS JOIN? How would that affect the time complexity?"