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

Practice

1. What is a non-equi join in SQL?

easy

A. A join that uses conditions other than equality, like <, >, or BETWEEN.

B. A join that only matches rows with equal values in both tables.

C. A join that combines all rows from both tables regardless of condition.

D. A join that uses only the AND logical operator in the ON clause.

Solution

1. Step 1: Understand join conditions

   Equi joins use equality (=) to match rows. Non-equi joins use other operators like <, >, or BETWEEN.

2. Step 2: Identify non-equi join definition

   Since non-equi joins match rows based on inequalities or ranges, A join that uses conditions other than equality, like <, >, or BETWEEN. correctly describes this.

3. Final Answer:

   A join that uses conditions other than equality, like <, >, or BETWEEN. -> Option A

4. Quick Check:

   Non-equi join = condition other than = [OK]

Hint: Non-equi joins use <, >, or BETWEEN, not just = [OK]

Common Mistakes:

• Confusing non-equi join with equi join
• Thinking non-equi join matches all rows
• Assuming only AND operator defines non-equi join

2. Which of the following is the correct syntax for a non-equi join using BETWEEN?

easy

A. SELECT * FROM A JOIN B ON A.value IN BETWEEN B.min AND B.max;

B. SELECT * FROM A JOIN B ON A.value = BETWEEN B.min AND B.max;

C. SELECT * FROM A JOIN B ON BETWEEN A.value AND B.min AND B.max;

D. SELECT * FROM A JOIN B ON A.value BETWEEN B.min AND B.max;

Solution

1. Step 1: Recall BETWEEN syntax

   BETWEEN is used as: column BETWEEN low AND high, without extra operators.

2. Step 2: Check each option

   SELECT * FROM A JOIN B ON A.value BETWEEN B.min AND B.max; uses correct syntax: A.value BETWEEN B.min AND B.max. Others misuse BETWEEN or add extra operators.

3. Final Answer:

   SELECT * FROM A JOIN B ON A.value BETWEEN B.min AND B.max; -> Option D

4. Quick Check:

   BETWEEN syntax = column BETWEEN low AND high [OK]

Hint: BETWEEN syntax: column BETWEEN low AND high, no extra operators [OK]

Common Mistakes:

• Adding = before BETWEEN
• Using IN BETWEEN instead of BETWEEN
• Placing BETWEEN incorrectly in ON clause

3. Given tables Products(product_id, price) and Discounts(min_price, max_price, discount_rate), what does this query return?

SELECT p.product_id, d.discount_rate
FROM Products p
JOIN Discounts d ON p.price >= d.min_price AND p.price < d.max_price;

medium

A. Only products with price exactly equal to min_price or max_price.

B. All products joined with all discounts regardless of price.

C. All products with their matching discount rate based on price ranges.

D. Syntax error due to invalid join condition.

Solution

1. Step 1: Analyze join condition

   The join matches products where price is between min_price (inclusive) and max_price (exclusive).

2. Step 2: Understand result

   This returns products with their discount rate if their price falls in the discount's price range.

3. Final Answer:

   All products with their matching discount rate based on price ranges. -> Option C

4. Quick Check:

   Non-equi join matches price ranges = All products with their matching discount rate based on price ranges. [OK]

Hint: Non-equi join matches ranges using >= and < [OK]

Common Mistakes:

• Thinking only exact matches are returned
• Assuming all products join with all discounts
• Believing the query has syntax errors

4. Identify the error in this non-equi join query:

SELECT e.name, s.salary_grade
FROM Employees e
JOIN SalaryGrades s ON e.salary => s.min_salary AND e.salary <= s.max_salary;

medium

A. The join condition should use OR instead of AND.

B. The operator => is invalid; it should be >=.

C. The table alias 's' is missing in the SELECT clause.

D. The query is missing a WHERE clause.

Solution

1. Step 1: Check operators in join condition

   The operator => is not valid SQL; the correct operator for 'greater than or equal' is >=.

2. Step 2: Verify other parts

   AND is correct to check salary between min and max. Aliases and WHERE clause are not errors here.

3. Final Answer:

   The operator => is invalid; it should be >=. -> Option B

4. Quick Check:

   Use >=, not => for greater or equal [OK]

Hint: Use >=, not =>, for greater or equal operator [OK]

Common Mistakes:

• Typing => instead of >=
• Replacing AND with OR incorrectly
• Confusing alias usage in SELECT

5. You have a table Scores(student_id, score) and a table Grades(grade, min_score, max_score). Write a query to assign each student their grade based on their score using a non-equi join.
Which query correctly implements this?

hard

A. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score >= g.min_score AND s.score < g.max_score;

B. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score <= g.min_score AND s.score >= g.max_score;

C. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score > g.min_score AND s.score <= g.max_score;

D. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score BETWEEN g.min_score AND g.max_score;

Solution

1. Step 1: Understand grading ranges

   Grades are assigned where score is between min_score (inclusive) and max_score (exclusive) to avoid overlap.

2. Step 2: Check each join condition

   SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score >= g.min_score AND s.score < g.max_score; uses s.score >= g.min_score AND s.score < g.max_score, correctly defining non-overlapping ranges.

3. Step 3: Verify other options

   SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score BETWEEN g.min_score AND g.max_score; includes max_score in BETWEEN (inclusive), which may cause overlap. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score > g.min_score AND s.score <= g.max_score; reverses inclusivity. SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score <= g.min_score AND s.score >= g.max_score; reverses logic incorrectly.

4. Final Answer:

   SELECT s.student_id, g.grade FROM Scores s JOIN Grades g ON s.score >= g.min_score AND s.score < g.max_score; -> Option A

5. Quick Check:

   Use >= min and < max for non-overlapping ranges [OK]

Hint: Use >= min_score and < max_score for clean grade ranges [OK]

Common Mistakes:

• Using BETWEEN which includes max_score causing overlap
• Swapping < and > operators
• Using incorrect inclusivity causing duplicate grades