First query execution in MySQL - Time & Space Complexity

Time Complexity: First query execution

O(n)

Understanding Time Complexity

When a database runs a query for the first time, it needs to do some extra work to prepare. This affects how long the query takes.

We want to understand how the time to run the first query changes as the data grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

SELECT * FROM employees WHERE department_id = 5;
    

This query fetches all employees who work in department 5. It runs for the first time after the database starts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning the employees table rows to find matches.
• How many times: Once for each row in the employees table.

How Execution Grows With Input

As the number of employees grows, the database checks more rows to find matches.

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

Pattern observation: The work grows directly with the number of rows. More rows mean more checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the first query grows in a straight line with the number of rows in the table.

Common Mistake

[X] Wrong: "The first query always runs instantly no matter the data size."

[OK] Correct: The database must check each row to find matches, so more data means more work and longer time.

Interview Connect

Understanding how the first query runs helps you explain how databases handle data and why some queries take longer. This shows you think about real-world data sizes and performance.

Self-Check

"What if the employees table had an index on department_id? How would the time complexity change?"