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