Non-equi joins in SQL - Time & Space Complexity

Time Complexity: Non-equi joins

O(n * m)

Understanding Time Complexity

When we use non-equi joins in SQL, the database compares rows based on conditions other than simple equality.

We want to understand how the time to run these joins grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query using a non-equi join.

SELECT a.id, b.value
FROM TableA a
JOIN TableB b
  ON a.score > b.min_score
  AND a.score < b.max_score;
    

This query joins two tables where the score in TableA falls between min_score and max_score in TableB.

Identify Repeating Operations

Look for repeated checks or loops in the join process.

• Primary operation: For each row in TableA, the database checks multiple rows in TableB to find matches.
• How many times: This check happens for every row in TableA against many rows in TableB.

How Execution Grows With Input

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

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The work grows much faster than the number of rows, roughly multiplying the sizes of both tables.

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 in the second.

Common Mistake

[X] Wrong: "Non-equi joins run as fast as simple equality joins."

[OK] Correct: Non-equi joins often require checking many rows against each other, which takes more time than matching exact values.

Interview Connect

Understanding how join conditions affect performance helps you write better queries and explain your reasoning clearly in interviews.

Self-Check

"What if we added an index on TableB's min_score and max_score columns? How would the time complexity change?"