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

Practice

1. What does an INNER JOIN do in PostgreSQL?

easy

A. Combines rows from two tables where matching column values exist in both tables.

B. Returns all rows from the first table, and matching rows from the second table.

C. Returns all rows from both tables, matching or not.

D. Deletes rows from both tables where values match.

Solution

1. Step 1: Understand INNER JOIN purpose

   INNER JOIN returns rows only when there is a match in both tables based on the join condition.

2. Step 2: Compare options with INNER JOIN behavior

   Combines rows from two tables where matching column values exist in both tables. correctly describes this behavior. Options B and C describe LEFT JOIN and FULL OUTER JOIN respectively, and D is unrelated.

3. Final Answer:

   Combines rows from two tables where matching column values exist in both tables. -> Option A

4. Quick Check:

   INNER JOIN = matched rows only [OK]

Hint: INNER JOIN returns only rows with matches in both tables [OK]

Common Mistakes:

• Confusing INNER JOIN with LEFT JOIN or FULL JOIN
• Thinking INNER JOIN returns unmatched rows
• Assuming INNER JOIN deletes data

2. Which of the following is the correct syntax for an INNER JOIN in PostgreSQL?

easy

A. SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id;

B. SELECT * FROM table1 INNER JOIN table2 WHERE table1.id = table2.id;

C. SELECT * FROM table1 INNER JOIN table2 USING (id);

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

Solution

1. Step 1: Review INNER JOIN syntax

   The correct syntax uses INNER JOIN with ON clause specifying the join condition using a single equals sign (=).

2. Step 2: Check each option

   SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id; uses correct INNER JOIN syntax with ON and =. SELECT * FROM table1 INNER JOIN table2 WHERE table1.id = table2.id; missing ON or USING clause, syntax error. SELECT * FROM table1 INNER JOIN table2 USING (id); uses correct USING syntax with parentheses. SELECT * FROM table1 JOIN table2 ON table1.id == table2.id; uses double equals (==) which is invalid in SQL.

3. Final Answer:

   SELECT * FROM table1 INNER JOIN table2 ON table1.id = table2.id; -> Option A

4. Quick Check:

   INNER JOIN uses ON with = [OK]

Hint: Use ON with single = for INNER JOIN conditions [OK]

Common Mistakes:

• Using WHERE instead of ON for join condition
• Using double equals (==) instead of single =
• Confusing USING clause applicability

3. Given the tables:
employees(id, name, dept_id)
departments(id, dept_name)
What will this query return?

SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id = d.id;

medium

A. All employees, even if they have no matching department.

B. An error because of alias usage.

C. All departments with employee names, even if no employees exist.

D. All employees with their department names, only if dept_id matches a department id.

Solution

1. Step 1: Understand INNER JOIN effect on employees and departments

   The INNER JOIN returns rows where employees.dept_id matches departments.id, so only employees with a valid department appear.

2. Step 2: Analyze query output

   The query selects employee names and their department names for matching rows only. Employees without a matching department are excluded.

3. Final Answer:

   All employees with their department names, only if dept_id matches a department id. -> Option D

4. Quick Check:

   INNER JOIN filters unmatched rows [OK]

Hint: INNER JOIN shows only matching rows from both tables [OK]

Common Mistakes:

• Assuming unmatched employees appear
• Confusing aliases causing errors
• Thinking departments without employees appear

4. Identify the error in this INNER JOIN query:

SELECT * FROM orders INNER JOIN customers ON orders.customer_id = customers.id WHERE orders.date > '2023-01-01'

medium

A. Missing table alias causing ambiguity.

B. WHERE clause cannot be used with INNER JOIN.

C. No error; query is valid and will run correctly.

D. Incorrect join condition syntax; should use USING instead of ON.

Solution

1. Step 1: Check JOIN syntax and WHERE clause

   The INNER JOIN uses ON with a valid condition. The WHERE clause filters rows after the join, which is allowed.

2. Step 2: Verify if any syntax or semantic errors exist

   There is no ambiguity or syntax error. Aliases are optional. USING is an alternative but not required.

3. Final Answer:

   No error; query is valid and will run correctly. -> Option C

4. Quick Check:

   INNER JOIN with ON and WHERE is valid [OK]

Hint: WHERE filters after JOIN; no syntax error here [OK]

Common Mistakes:

• Thinking WHERE cannot be used with JOIN
• Confusing USING and ON as mandatory
• Assuming aliases are always required

5. You have two tables:
products(id, name)
sales(product_id, quantity)
Write a query to find product names with total quantity sold, but only for products that have sales.
Which query correctly uses INNER JOIN to achieve this?

hard

A. SELECT p.name, SUM(s.quantity) FROM sales s LEFT JOIN products p ON s.product_id = p.id GROUP BY p.name;

B. SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id GROUP BY p.name;

C. SELECT p.name, SUM(s.quantity) FROM products p LEFT JOIN sales s ON p.id = s.product_id GROUP BY p.name;

D. SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id WHERE p.name > 0 GROUP BY p.name;

Solution

1. Step 1: Understand requirement for products with sales only

   INNER JOIN returns only products that have matching sales records, excluding products without sales.

2. Step 2: Analyze each query

   SELECT p.name, SUM(s.quantity) FROM sales s LEFT JOIN products p ON s.product_id = p.id GROUP BY p.name; uses LEFT JOIN, includes unmatched sales (NULL p.name). SELECT p.name, SUM(s.quantity) FROM products p LEFT JOIN sales s ON p.id = s.product_id GROUP BY p.name; uses LEFT JOIN, includes products without sales. SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id GROUP BY p.name; uses INNER JOIN correctly. SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id WHERE p.name > 0 GROUP BY p.name; WHERE p.name > 0 causes type error.

3. Step 3: Choose best answer matching INNER JOIN usage

   SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id GROUP BY p.name; is correct.

4. Final Answer:

   SELECT p.name, SUM(s.quantity) FROM products p INNER JOIN sales s ON p.id = s.product_id GROUP BY p.name; -> Option B

5. Quick Check:

   INNER JOIN + GROUP BY sums sales per product [OK]

Hint: Use INNER JOIN and GROUP BY to sum only matching sales [OK]

Common Mistakes:

• Using LEFT JOIN includes products without sales
• Forgetting GROUP BY causes errors
• Confusing table order in JOIN