INNER JOIN execution in PostgreSQL - Time & Space Complexity

Time Complexity: INNER JOIN execution

O(n * m)

Understanding Time Complexity

When we use INNER JOIN in a database, we combine rows from two tables based on matching values. Understanding how the time it takes grows as the tables get bigger helps us write better queries.

We want to know: How does the work needed change when the tables have more rows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT a.id, b.value
FROM table_a a
INNER JOIN table_b b
ON a.key = b.key;
    

This query finds all pairs of rows from two tables where the key values match.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each row in the first table, the database looks for matching rows in the second table.
• How many times: This happens for every row in the first table, and for each, it may check multiple rows in the second table.

How Execution Grows With Input

As the number of rows in both tables grows, the number of comparisons grows too.

Input Size (rows in each table)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows roughly proportional to the product of the number of rows; doubling the rows makes the work about four times bigger.

Final Time Complexity

Time Complexity: O(n * m)

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

Common Mistake

[X] Wrong: "INNER JOIN always runs quickly no matter how big the tables are."

[OK] Correct: Without indexes or optimizations, the database may check many pairs of rows, making the query slower as tables grow.

Interview Connect

Knowing how INNER JOIN scales helps you explain query performance clearly and shows you understand how databases handle data behind the scenes.

Self-Check

"What if we added an index on the join key in one table? How would the time complexity change?"