JOIN with aggregate functions in MySQL - Time & Space Complexity

Time Complexity: JOIN with aggregate functions

O(n + m)

Understanding Time Complexity

When we use JOINs with aggregate functions in SQL, the database combines rows from two tables and then summarizes data.

We want to understand how the time to run this query grows as the tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT c.customer_id, COUNT(o.order_id) AS total_orders
FROM customers c
JOIN orders o ON c.customer_id = o.customer_id
GROUP BY c.customer_id;
    

This query joins customers with their orders and counts how many orders each customer has.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: For each order, the database finds the matching customer and counts the order.
• How many times: This happens once per order.

How Execution Grows With Input

As the number of customers and orders grows, the work to join and count grows too.

Input Size (customers n, orders m)	Approx. Operations
10 customers, 50 orders	About 50 matching checks and counts
100 customers, 500 orders	About 500 matching checks and counts
1000 customers, 5000 orders	About 5000 matching checks and counts

Pattern observation: The total work grows roughly with the number of orders, since each order must be matched and counted.

Final Time Complexity

Time Complexity: O(n + m)

This means the time grows roughly with the total number of customers plus orders, as the database processes both tables.

Common Mistake

[X] Wrong: "The time depends only on the number of customers because we group by customer."

[OK] Correct: The database must check all orders to find matches, so orders affect the time too.

Interview Connect

Understanding how JOINs with aggregates scale helps you explain query performance clearly and confidently in real situations.

Self-Check

"What if we added an index on the orders.customer_id column? How would the time complexity change?"

Practice

1. What does the following SQL query do?
SELECT department, COUNT(employee_id) FROM employees JOIN departments ON employees.dept_id = departments.id GROUP BY department;

easy

A. Counts employees in each department by joining employees and departments tables.

B. Lists all employees without grouping by department.

C. Calculates the average salary per department.

D. Deletes employees who are not assigned to any department.

Solution

1. Step 1: Understand the JOIN operation

   The query joins the employees and departments tables using the department ID to combine related data.

2. Step 2: Analyze the GROUP BY and COUNT

   It groups the results by department and counts the number of employees in each group.

3. Final Answer:

   Counts employees in each department by joining employees and departments tables. -> Option A

4. Quick Check:

   JOIN + GROUP BY + COUNT = Employee count per department [OK]

Hint: JOIN tables, GROUP BY key, then apply COUNT [OK]

Common Mistakes:

• Ignoring GROUP BY causes wrong aggregation
• Using COUNT without JOIN returns incomplete data
• Confusing COUNT with SUM or AVG

2. Which of the following is the correct syntax to get the total sales per customer using JOIN and SUM?
SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders ON customers.id = orders.customer_id GROUP BY customers.name;

easy

A. SELECT customers.name, SUM(orders.amount) FROM customers LEFT JOIN orders GROUP BY customers.name;

B. SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders WHERE customers.id = orders.customer_id GROUP BY customers.name;

C. SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders ON customers.id = orders.customer_id GROUP BY customers.name;

D. SELECT customers.name, SUM(orders.amount) FROM customers, orders GROUP BY customers.name;

Solution

1. Step 1: Check JOIN syntax

   SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders ON customers.id = orders.customer_id GROUP BY customers.name; uses correct INNER JOIN syntax with ON clause to link customers and orders.

2. Step 2: Verify GROUP BY and SUM usage

   SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders ON customers.id = orders.customer_id GROUP BY customers.name; correctly groups by customer name and sums order amounts.

3. Final Answer:

   SELECT customers.name, SUM(orders.amount) FROM customers JOIN orders ON customers.id = orders.customer_id GROUP BY customers.name; -> Option C

4. Quick Check:

   JOIN with ON + GROUP BY + SUM = Correct syntax [OK]

Hint: Use JOIN ... ON ... with GROUP BY for aggregates [OK]

Common Mistakes:

• Using WHERE instead of ON in JOIN
• Missing ON clause causes syntax error
• Grouping by wrong column

3. Given tables:
employees(id, name, dept_id)
departments(id, department)
What is the output of this query?

SELECT d.department, COUNT(e.id) AS emp_count FROM employees e LEFT JOIN departments d ON e.dept_id = d.id GROUP BY d.department ORDER BY emp_count DESC;

medium

A. Syntax error due to missing GROUP BY column.

B. List of departments with employee counts, including departments with zero employees.

C. List of employees with their department names.

D. List of departments with employee counts, excluding departments with zero employees.

Solution

1. Step 1: Understand LEFT JOIN effect

   FROM employees e LEFT JOIN departments d ON e.dept_id = d.id includes all employees and matching departments if they exist. Departments with no employees do not appear because no employee row matches them.

2. Step 2: GROUP BY and COUNT behavior

   Grouping by d.department counts employees only for departments that have at least one employee (count >=1). Departments with zero employees are excluded.

3. Final Answer:

   List of departments with employee counts, excluding departments with zero employees. -> Option D

4. Quick Check:

   LEFT JOIN from employees + GROUP BY department excludes zero counts [OK]

Hint: LEFT JOIN keeps all left rows, COUNT counts matches [OK]

Common Mistakes:

• Assuming INNER JOIN behavior excludes zero counts
• Confusing COUNT(*) with COUNT(column)
• Ignoring NULL values in grouping

4. Identify the error in this query:

SELECT d.department, COUNT(e.id) FROM employees e JOIN departments d ON e.dept_id = d.id WHERE e.salary > 50000 GROUP BY e.dept_id;

medium

A. GROUP BY should use d.department instead of e.dept_id.

B. Missing HAVING clause for salary filter.

C. COUNT(e.id) cannot be used with JOIN.

D. ON clause is incorrect syntax.

Solution

1. Step 1: Check GROUP BY columns

   The SELECT lists d.department but GROUP BY uses e.dept_id, causing mismatch.

2. Step 2: Fix GROUP BY to match SELECT

   GROUP BY should use d.department or include it to avoid errors.

3. Final Answer:

   GROUP BY should use d.department instead of e.dept_id. -> Option A

4. Quick Check:

   GROUP BY columns must match SELECT non-aggregates [OK]

Hint: GROUP BY columns must match SELECT non-aggregates [OK]

Common Mistakes:

• Grouping by wrong or missing columns
• Using WHERE instead of HAVING for aggregates
• Incorrect JOIN ON syntax

5. You have tables:
orders(order_id, customer_id, amount)
customers(customer_id, name)
Write a query to find customers who have total orders amount greater than 1000, including customers with no orders showing zero total.
Which query is correct?

hard

A. SELECT c.name, SUM(o.amount) AS total FROM customers c LEFT JOIN orders o ON c.customer_id = o.customer_id WHERE total > 1000 GROUP BY c.name;

B. SELECT c.name, COALESCE(SUM(o.amount), 0) AS total FROM customers c LEFT JOIN orders o ON c.customer_id = o.customer_id GROUP BY c.name HAVING total > 1000;

C. SELECT c.name, SUM(o.amount) AS total FROM customers c JOIN orders o ON c.customer_id = o.customer_id GROUP BY c.name HAVING total > 1000;

D. SELECT c.name, SUM(o.amount) AS total FROM customers c LEFT JOIN orders o ON c.customer_id = o.customer_id GROUP BY c.name WHERE total > 1000;

Solution

1. Step 1: Use LEFT JOIN to include customers without orders

   LEFT JOIN ensures all customers appear, even if no matching orders exist.

2. Step 2: Use COALESCE to convert NULL sums to zero and HAVING to filter totals

   COALESCE replaces NULL with 0; HAVING filters groups by aggregate result.

3. Final Answer:

   SELECT c.name, COALESCE(SUM(o.amount), 0) AS total FROM customers c LEFT JOIN orders o ON c.customer_id = o.customer_id GROUP BY c.name HAVING total > 1000; -> Option B

4. Quick Check:

   LEFT JOIN + COALESCE + HAVING filters totals correctly [OK]

Hint: Use LEFT JOIN + COALESCE + HAVING for conditional aggregates [OK]

Common Mistakes:

• Using WHERE instead of HAVING for aggregate filters
• Ignoring NULL sums for customers without orders
• Using INNER JOIN excludes customers with zero orders