SELECT with WHERE, ORDER BY, GROUP BY in DBMS Theory - Time & Space Complexity

Time Complexity: SELECT with WHERE, ORDER BY, GROUP BY

O(n + k log k)

Understanding Time Complexity

When we use SELECT queries with WHERE, ORDER BY, and GROUP BY, the database does several steps to get the result.

We want to understand how the time it takes grows as the data gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT department, COUNT(*)
FROM employees
WHERE salary > 50000
GROUP BY department
ORDER BY COUNT(*) DESC;
    

This query filters employees by salary, groups them by department, counts each group, and sorts the groups by count.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning all employee rows to check the salary condition.
• How many times: Once for each row in the employees table.
• Secondary operations: Grouping rows by department and counting them, then sorting the groups.

How Execution Grows With Input

As the number of employees grows, the database must check each one for the salary condition.

Input Size (n)	Approx. Operations
10	About 10 checks and grouping steps
100	About 100 checks and grouping steps
1000	About 1000 checks and grouping steps

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

Final Time Complexity

Time Complexity: O(n + k log k)

This means the time grows linearly with the number of rows scanned (n), plus the time to sort the grouped results (k groups), which is typically less than n.

Common Mistake

[X] Wrong: "The query only takes time proportional to the number of rows, so it is O(n)."

[OK] Correct: Sorting the grouped results adds extra work that grows faster than just scanning rows, depending on the number of groups.

Interview Connect

Understanding how filtering, grouping, and sorting affect query time helps you explain database performance clearly and confidently.

Self-Check

"What if we removed the ORDER BY clause? How would the time complexity change?"

Practice

1. What does the WHERE clause do in a SQL SELECT statement?

easy

A. Filters rows based on a condition

B. Groups rows with the same values

C. Sorts the result set

D. Joins two tables together

Solution

1. Step 1: Understand the role of WHERE clause

   The WHERE clause filters rows that meet a specific condition before any grouping or sorting.

2. Step 2: Differentiate from GROUP BY and ORDER BY

   GROUP BY groups rows, ORDER BY sorts rows, but WHERE filters rows.

3. Final Answer:

   Filters rows based on a condition -> Option A

4. Quick Check:

   WHERE = Filters rows [OK]

Hint: WHERE filters rows before grouping or sorting [OK]

Common Mistakes:

• Confusing WHERE with GROUP BY
• Thinking WHERE sorts data
• Assuming WHERE joins tables

2. Which of the following is the correct syntax to select all columns from a table named Employees where the Department is 'Sales'?

easy

A. SELECT * FROM Employees WHERE Department = 'Sales';

B. SELECT * Employees WHERE Department == 'Sales';

C. SELECT * FROM Employees WHERE Department := 'Sales';

D. SELECT * FROM Employees WHERE Department = Sales;

Solution

1. Step 1: Check correct SELECT syntax

   The correct syntax uses SELECT * FROM table WHERE condition with single equals and quotes around string values.

2. Step 2: Identify syntax errors in other options

   SELECT * Employees WHERE Department == 'Sales'; uses '==' which is invalid in SQL; SELECT * FROM Employees WHERE Department := 'Sales'; uses ':=' which is not standard; SELECT * FROM Employees WHERE Department = Sales; misses quotes around 'Sales'.

3. Final Answer:

   SELECT * FROM Employees WHERE Department = 'Sales'; -> Option A

4. Quick Check:

   Correct WHERE syntax uses = and quotes for strings [OK]

Hint: Use single = and quotes for string in WHERE [OK]

Common Mistakes:

• Using == instead of =
• Missing quotes around string values
• Wrong assignment operator :=

3. Given the table Sales with columns Region and Amount, what will this query return?

SELECT Region, SUM(Amount) FROM Sales WHERE Amount > 100 GROUP BY Region ORDER BY SUM(Amount) DESC;

medium

A. Sum of all sales amounts regardless of region

B. All sales records with amount over 100, sorted by region

C. Total sales amount per region for sales over 100, sorted highest to lowest

D. Syntax error due to ORDER BY on aggregate

Solution

1. Step 1: Analyze WHERE and GROUP BY

   WHERE filters rows with Amount > 100, GROUP BY groups rows by Region, SUM(Amount) calculates total per group.

2. Step 2: Understand ORDER BY with aggregate

   ORDER BY SUM(Amount) DESC sorts groups by total sales descending.

3. Final Answer:

   Total sales amount per region for sales over 100, sorted highest to lowest -> Option C

4. Quick Check:

   WHERE filters, GROUP BY groups, ORDER BY sorts aggregates [OK]

Hint: ORDER BY can sort aggregates after GROUP BY [OK]

Common Mistakes:

• Thinking ORDER BY on aggregate causes error
• Ignoring WHERE filter before grouping
• Confusing sorting by region instead of sum

4. Identify the error in this SQL query:

SELECT Department, COUNT(*) FROM Employees ORDER BY Department WHERE COUNT(*) > 5 GROUP BY Department;

medium

A. Missing semicolon at the end

B. ORDER BY appears before WHERE and GROUP BY, causing syntax error

C. WHERE cannot filter on aggregate functions like COUNT(*)

D. COUNT(*) cannot be used with GROUP BY

Solution

1. Step 1: Check SQL clause order

   The correct order is SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY. ORDER BY before WHERE is invalid.

2. Step 2: Confirm other clauses

   COUNT(*) with GROUP BY is valid; filtering on aggregates requires HAVING, not WHERE; but main syntax error is clause order.

3. Final Answer:

   ORDER BY appears before WHERE and GROUP BY, causing syntax error -> Option B

4. Quick Check:

   Clause order matters: WHERE before GROUP BY, ORDER BY last [OK]

Hint: Remember SQL clause order: WHERE, GROUP BY, HAVING, ORDER BY [OK]

Common Mistakes:

• Placing ORDER BY before WHERE
• Using WHERE to filter aggregates instead of HAVING
• Ignoring clause order rules

5. You have a table Orders with columns CustomerID, OrderDate, and Total. Write a query to find customers who placed more than 3 orders in 2023, showing their CustomerID and total number of orders, sorted by number of orders descending.

hard

A. SELECT CustomerID, COUNT(*) FROM Orders WHERE YEAR(OrderDate) == 2023 GROUP BY CustomerID HAVING COUNT(*) > 3 ORDER BY COUNT(*) DESC;

B. SELECT CustomerID, COUNT(*) FROM Orders GROUP BY CustomerID WHERE YEAR(OrderDate) = 2023 HAVING COUNT(*) > 3 ORDER BY COUNT(*) DESC;

C. SELECT CustomerID, COUNT(*) FROM Orders WHERE OrderDate >= '2023-01-01' AND OrderDate <= '2023-12-31' GROUP BY CustomerID HAVING COUNT(*) >= 3 ORDER BY COUNT(*) DESC;

D. SELECT CustomerID, COUNT(*) FROM Orders WHERE OrderDate BETWEEN '2023-01-01' AND '2023-12-31' GROUP BY CustomerID HAVING COUNT(*) > 3 ORDER BY COUNT(*) DESC;

Solution

1. Step 1: Filter orders in 2023

   Use WHERE with OrderDate between '2023-01-01' and '2023-12-31' to select orders in 2023.

2. Step 2: Group by CustomerID and filter groups

   GROUP BY CustomerID groups orders per customer; HAVING COUNT(*) > 3 filters customers with more than 3 orders.

3. Step 3: Sort results

   ORDER BY COUNT(*) DESC sorts customers by number of orders from highest to lowest.

4. Final Answer:

   SELECT CustomerID, COUNT(*) FROM Orders WHERE OrderDate BETWEEN '2023-01-01' AND '2023-12-31' GROUP BY CustomerID HAVING COUNT(*) > 3 ORDER BY COUNT(*) DESC; -> Option D

5. Quick Check:

   Filter dates, group, HAVING filter, then ORDER BY count desc [OK]

Hint: Use HAVING to filter groups after GROUP BY [OK]

Common Mistakes:

• Using WHERE to filter aggregates instead of HAVING
• Incorrect date filtering syntax
• Using >= 3 instead of > 3 for count condition