How SQL communicates with the database engine - Performance & Efficiency

Time Complexity: How SQL communicates with the database engine

O(n)

Understanding Time Complexity

When SQL sends a command to the database engine, it asks the engine to find or change data. Understanding how long this takes helps us know how well the database will work as data grows.

We want to know: How does the time to run a SQL query change when the data gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following SQL query.

SELECT *
FROM employees
WHERE department_id = 5;
    

This query asks the database to find all employees who work in department number 5.

Identify Repeating Operations

Look at what repeats when the database runs this query.

• Primary operation: Checking each employee record to see if their department matches 5.
• How many times: Once for every employee in the table.

How Execution Grows With Input

As the number of employees grows, the work to check each one grows too.

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

Pattern observation: The number of checks grows directly with the number of employees.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows in a straight line as the number of records grows.

Common Mistake

[X] Wrong: "The query time stays the same no matter how many records there are."

[OK] Correct: The database must check each record unless it uses special shortcuts like indexes, so more records usually mean more work.

Interview Connect

Knowing how SQL queries grow with data size helps you explain how databases handle large amounts of data. This skill shows you understand what happens behind the scenes.

Self-Check

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