How the database engine processes a SELECT in SQL - Performance & Efficiency

Time Complexity: How the database engine processes a SELECT

O(n)

Understanding Time Complexity

When you run a SELECT query, the database engine works to find and return the data you asked for.

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 *
FROM employees
WHERE department = 'Sales';

This query finds all employees who work in the Sales department.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each row in the employees table to see if the department is 'Sales'.
• How many times: Once for every row in the table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows one by one.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The work grows directly with the number of rows.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the table gets bigger.

Common Mistake

[X] Wrong: "The database instantly finds the rows without checking each one."

[OK] Correct: Without special help like indexes, the database must look at every row to be sure.

Interview Connect

Understanding how queries scale helps you explain your thinking clearly and shows you know what happens behind the scenes.

Self-Check

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

Practice

1. Which step does the database engine perform first when processing a SELECT query?

easy

A. It sorts the results according to the ORDER BY clause.

B. It groups rows using the GROUP BY clause.

C. It reads the table and filters rows based on the WHERE clause.

D. It picks which columns to show based on the SELECT list.

Solution

1. Step 1: Understand the role of the WHERE clause

   The WHERE clause filters rows early to reduce data for later steps.

2. Step 2: Recognize the order of operations in SELECT

   The database first filters rows, then picks columns, groups, and sorts.

3. Final Answer:

   It reads the table and filters rows based on the WHERE clause. -> Option C

4. Quick Check:

   Filtering rows happens before selecting columns [OK]

Hint: Filtering rows happens before picking columns or sorting [OK]

Common Mistakes:

• Thinking ORDER BY happens before filtering
• Assuming columns are picked before filtering rows
• Confusing grouping with filtering order

2. Which of the following is the correct syntax to select only the name and age columns from a table called people?

easy

A. SELECT name age FROM people;

B. SELECT * FROM people WHERE name, age;

C. SELECT name AND age FROM people;

D. SELECT name, age FROM people;

Solution

1. Step 1: Recall correct SELECT syntax for columns

   Columns are listed separated by commas after SELECT.

2. Step 2: Check each option's syntax

   SELECT name, age FROM people; uses commas correctly; others use wrong keywords or miss commas.

3. Final Answer:

   SELECT name, age FROM people; -> Option D

4. Quick Check:

   Columns separated by commas in SELECT [OK]

Hint: Use commas to separate columns in SELECT [OK]

Common Mistakes:

• Using AND instead of commas between columns
• Trying to filter columns in WHERE clause
• Omitting commas between column names

3. Given the table employees with columns id, name, and salary, what will this query return?

SELECT name FROM employees WHERE salary > 50000 ORDER BY name;

medium

A. All employee names sorted alphabetically regardless of salary.

B. All employee names sorted alphabetically with salary above 50000.

C. All employee names with salary below 50000, unsorted.

D. Syntax error due to missing GROUP BY clause.

Solution

1. Step 1: Analyze the WHERE clause

   The query filters employees with salary greater than 50000.

2. Step 2: Understand ORDER BY effect

   Results are sorted by name alphabetically.

3. Final Answer:

   All employee names sorted alphabetically with salary above 50000. -> Option B

4. Quick Check:

   Filter then sort results [OK]

Hint: Filter rows first, then sort results [OK]

Common Mistakes:

• Ignoring the salary filter
• Thinking GROUP BY is needed for ORDER BY
• Assuming all rows are returned

4. What is wrong with this query?

SELECT id, name FROM users WHERE age > 18 ORDER BY;

medium

A. Missing column name after ORDER BY causes syntax error.

B. WHERE clause should come after ORDER BY.

C. SELECT must include all columns in ORDER BY.

D. ORDER BY cannot be used with WHERE.

Solution

1. Step 1: Check ORDER BY syntax

   ORDER BY must specify at least one column to sort by.

2. Step 2: Identify error in query

   The query ends ORDER BY; without column name, causing syntax error.

3. Final Answer:

   Missing column name after ORDER BY causes syntax error. -> Option A

4. Quick Check:

   ORDER BY needs a column name [OK]

Hint: Always specify column after ORDER BY [OK]

Common Mistakes:

• Placing WHERE after ORDER BY
• Thinking ORDER BY needs all SELECT columns
• Believing ORDER BY can't be used with WHERE

5. You want to find the average salary for each department but only for employees earning more than 40000. Which query correctly processes this?

hard

A. SELECT department, AVG(salary) FROM employees WHERE salary > 40000 GROUP BY department;

B. SELECT department, AVG(salary) FROM employees GROUP BY department WHERE salary > 40000;

C. SELECT department, AVG(salary) FROM employees GROUP BY salary > 40000;

D. SELECT department, AVG(salary) FROM employees HAVING salary > 40000 GROUP BY department;

Solution

1. Step 1: Apply WHERE before grouping

   Filter employees with salary > 40000 before grouping by department.

2. Step 2: Use GROUP BY on department and calculate average salary

   Group filtered rows by department and compute average salary.

3. Final Answer:

   SELECT department, AVG(salary) FROM employees WHERE salary > 40000 GROUP BY department; -> Option A

4. Quick Check:

   Filter rows before grouping for correct average [OK]

Hint: Use WHERE before GROUP BY to filter rows [OK]

Common Mistakes:

• Placing WHERE after GROUP BY
• Using HAVING without aggregation condition
• Grouping by a condition instead of column