Subqueries and nested queries in DBMS Theory - Time & Space Complexity

Time Complexity: Subqueries and nested queries

O(n)

Understanding Time Complexity

When using subqueries or nested queries in a database, it is important to understand how the time to run the query grows as the data size increases.

We want to know how the number of operations changes when the input tables get bigger.

Scenario Under Consideration

Analyze the time complexity of the following SQL query with a nested subquery.

SELECT employee_id, name
FROM employees
WHERE department_id IN (
  SELECT department_id
  FROM departments
  WHERE location = 'New York'
);
    

This query finds employees who work in departments located in New York by using a subquery to filter departments first.

Identify Repeating Operations

Look for repeated steps in the query execution.

• Primary operation: Scanning the employees table and checking each employee's department against the list from the subquery.
• How many times: The employees table is scanned once; the subquery runs once and its result is used for all checks.

How Execution Grows With Input

As the number of employees (n) grows, the query must check more rows. The subquery result size depends on departments but is usually smaller.

Input Size (n)	Approx. Operations
10 employees	About 10 checks against the subquery result
100 employees	About 100 checks against the subquery result
1000 employees	About 1000 checks against the subquery result

Pattern observation: The work grows roughly in direct proportion to the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of employees.

Common Mistake

[X] Wrong: "The subquery runs once and does not affect the total time much."

[OK] Correct: Depending on the database, the subquery might be executed repeatedly or its result scanned many times, affecting performance.

Interview Connect

Understanding how nested queries affect performance helps you write efficient database queries and shows you can think about real-world data growth.

Self-Check

What if the subquery was correlated, referencing the outer query? How would the time complexity change?

Practice

1. What is a subquery in a database query?

easy

A. A query nested inside another query

B. A query that updates data

C. A query that deletes tables

D. A query that creates indexes

Solution

1. Step 1: Understand the definition of subquery

   A subquery is a query written inside another query to help filter or calculate data.

2. Step 2: Identify the correct description

   Among the options, only "A query nested inside another query" matches the definition of a subquery.

3. Final Answer:

   A query nested inside another query -> Option A

4. Quick Check:

   Subquery = Nested query [OK]

Hint: Subquery means query inside another query [OK]

Common Mistakes:

• Confusing subquery with update or delete operations
• Thinking subquery creates indexes
• Mixing subquery with table creation

2. Which of the following is the correct syntax to use a subquery in the WHERE clause?

easy

A. SELECT * FROM table WHERE column = (SELECT value FROM other_table);

B. SELECT * FROM table WHERE SELECT value FROM other_table = column;

C. SELECT * FROM table WHERE column IN SELECT value FROM other_table;

D. SELECT * FROM table WHERE column = SELECT value FROM other_table;

Solution

1. Step 1: Review correct subquery syntax in WHERE clause

   The subquery must be enclosed in parentheses and used as a value to compare with a column.

2. Step 2: Check each option

   SELECT * FROM table WHERE column = (SELECT value FROM other_table); correctly uses parentheses around the subquery. Options A, B, and D have syntax errors or missing parentheses.

3. Final Answer:

   SELECT * FROM table WHERE column = (SELECT value FROM other_table); -> Option A

4. Quick Check:

   Subquery in WHERE uses parentheses [OK]

Hint: Subquery in WHERE must be inside parentheses [OK]

Common Mistakes:

• Omitting parentheses around subquery
• Placing subquery before column
• Using IN without parentheses

3. Consider the tables:
Employees(emp_id, name, dept_id)
Departments(dept_id, dept_name)
What does this query return?

SELECT name FROM Employees WHERE dept_id = (SELECT dept_id FROM Departments WHERE dept_name = 'Sales');

medium

A. Names of employees who do not work in Sales

B. Names of all employees regardless of department

C. Names of employees who work in the Sales department

D. Department names of all employees

Solution

1. Step 1: Understand the subquery

   The subquery finds the dept_id for the department named 'Sales'.

2. Step 2: Apply the subquery result in the main query

   The main query selects employee names whose dept_id matches the Sales dept_id.

3. Final Answer:

   Names of employees who work in the Sales department -> Option C

4. Quick Check:

   Subquery filters Sales dept_id, main query filters employees [OK]

Hint: Subquery finds Sales dept_id, main query filters employees [OK]

Common Mistakes:

• Thinking it returns all employees
• Confusing employee names with department names
• Ignoring subquery filtering

4. Identify the error in this query:

SELECT name FROM Employees WHERE dept_id = SELECT dept_id FROM Departments WHERE dept_name = 'HR';

medium

A. Wrong table name used

B. Missing parentheses around the subquery

C. Using = instead of IN

D. Missing WHERE clause in subquery

Solution

1. Step 1: Check subquery syntax

   The subquery must be enclosed in parentheses when used in WHERE clause comparisons.

2. Step 2: Identify the error in the query

   The query misses parentheses around the subquery, causing a syntax error.

3. Final Answer:

   Missing parentheses around the subquery -> Option B

4. Quick Check:

   Subquery needs parentheses [OK]

Hint: Always put subqueries in parentheses [OK]

Common Mistakes:

• Omitting parentheses
• Confusing = with IN unnecessarily
• Incorrect table names

5. You want to find all employees who earn more than the average salary in their department. Which query correctly uses a subquery to achieve this?

hard

A. SELECT emp_name FROM Employees WHERE salary > (SELECT MAX(salary) FROM Employees);

B. SELECT emp_name FROM Employees WHERE salary > AVG(salary);

C. SELECT emp_name FROM Employees WHERE salary > (SELECT salary FROM Employees);

D. SELECT emp_name FROM Employees WHERE salary > (SELECT AVG(salary) FROM Employees WHERE dept_id = Employees.dept_id);

Solution

1. Step 1: Understand the requirement

   We need to compare each employee's salary to the average salary of their own department.

2. Step 2: Analyze each option

   SELECT emp_name FROM Employees WHERE salary > (SELECT AVG(salary) FROM Employees WHERE dept_id = Employees.dept_id); uses a correlated subquery that calculates the average salary for the employee's department. Options A, B, and C do not correctly calculate the average per department or use wrong aggregates.

3. Final Answer:

   SELECT emp_name FROM Employees WHERE salary > (SELECT AVG(salary) FROM Employees WHERE dept_id = Employees.dept_id); -> Option D

4. Quick Check:

   Correlated subquery compares salary to dept average [OK]

Hint: Use correlated subquery with dept_id to get average salary [OK]

Common Mistakes:

• Using global average instead of per department
• Using MAX instead of AVG
• Not correlating subquery with outer query