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

Practice

1. What does a CROSS JOIN do in PostgreSQL?

easy

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

B. Returns only matching rows based on a condition.

C. Joins tables based on a common column with duplicates removed.

D. Filters rows from the first table that exist in the second table.

Solution

1. Step 1: Understand CROSS JOIN concept

   A CROSS JOIN creates combinations of all rows from both tables without any condition.

2. Step 2: Compare with other JOIN types

   Unlike INNER JOIN or LEFT JOIN, CROSS JOIN does not filter or match rows but pairs all possible combinations.

3. Final Answer:

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

4. Quick Check:

   CROSS JOIN = all combinations [OK]

Hint: Remember: CROSS JOIN multiplies rows from both tables [OK]

Common Mistakes:

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

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

easy

A. SELECT * FROM table1 CROSS JOIN table2;

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

C. SELECT * FROM table1 INNER CROSS JOIN table2;

D. SELECT * FROM table1 CROSS JOIN ON table2;

Solution

1. Step 1: Recall CROSS JOIN syntax

   The correct syntax is SELECT * FROM table1 CROSS JOIN table2; without any ON clause.

2. Step 2: Identify incorrect options

   SELECT * FROM table1 JOIN table2 ON table1.id = table2.id; uses INNER JOIN with ON clause, C has invalid keyword INNER CROSS JOIN, A has misplaced ON keyword.

3. Final Answer:

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

4. Quick Check:

   Syntax for CROSS JOIN = SELECT * FROM table1 CROSS JOIN table2; [OK]

Hint: CROSS JOIN syntax has no ON clause [OK]

Common Mistakes:

• Adding ON clause with CROSS JOIN
• Using INNER CROSS JOIN which is invalid
• Misplacing keywords in the query

3. You have two tables:
Colors:
color_id | color_name
1 | Red
2 | Blue

Shapes:
shape_id | shape_name
1 | Circle
2 | Square
3 | Triangle

How many rows will this query return?
SELECT color_name, shape_name FROM Colors CROSS JOIN Shapes;

easy

A. 5

B. 3

C. 2

D. 6

Solution

1. Step 1: Count rows in each table

   Colors has 2 rows, Shapes has 3 rows.

2. Step 2: Calculate CROSS JOIN result size

   Result rows = 2 x 3 = 6 rows, all combinations of colors and shapes.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   2 x 3 = 6 rows [OK]

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

Common Mistakes:

• Adding rows instead of multiplying
• Ignoring one table's row count
• Confusing CROSS JOIN with INNER JOIN

4. Given two tables:
Table A:
id | name
1 | Alice
2 | Bob

Table B:
code
X
Y

What is the result of:
SELECT A.name, B.code FROM A CROSS JOIN B;

medium

A. [('Alice', 'X'), ('Bob', 'Y')]

B. [('Alice', 'X'), ('Alice', 'Y'), ('Bob', 'X'), ('Bob', 'Y')]

C. [('Alice', 'X'), ('Bob', 'X'), ('Alice', 'Y'), ('Bob', 'Y')]

D. [('Alice', 'X'), ('Bob', 'X')]

Solution

1. Step 1: Understand CROSS JOIN output

   Each row in A pairs with every row in B, so 2 rows in A x 2 rows in B = 4 rows total.

2. Step 2: List all combinations

   Pairs are (Alice, X), (Alice, Y), (Bob, X), (Bob, Y) in that order.

3. Final Answer:

   [('Alice', 'X'), ('Alice', 'Y'), ('Bob', 'X'), ('Bob', 'Y')] -> Option B

4. Quick Check:

   2 x 2 = 4 rows [OK]

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

Common Mistakes:

• Assuming CROSS JOIN filters rows
• Mixing order of pairs incorrectly
• Counting only matching rows instead of all combinations

5. Consider this query:
SELECT * FROM table1 CROSS JOIN table2 ON table1.id = table2.id;
What is the problem with this query?

medium

A. It behaves like INNER JOIN with ON condition.

B. It will return only matching rows based on id.

C. Syntax error because CROSS JOIN does not allow ON clause.

D. It returns all rows from table1 only.

Solution

1. Step 1: Check CROSS JOIN syntax rules

   CROSS JOIN syntax does not support ON clause; adding ON causes syntax error.

2. Step 2: Understand error cause

   ON clause is used with INNER or LEFT JOIN, not CROSS JOIN.

3. Final Answer:

   Syntax error because CROSS JOIN does not allow ON clause. -> Option C

4. Quick Check:

   CROSS JOIN + ON = syntax error [OK]

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

Common Mistakes:

• Thinking CROSS JOIN can have ON clause
• Confusing CROSS JOIN with INNER JOIN
• Expecting filtered results from CROSS JOIN