EXPLAIN query analysis in MySQL - Time & Space Complexity

Time Complexity: EXPLAIN query analysis

O(n)

Understanding Time Complexity

When we use EXPLAIN in MySQL, we want to see how the database plans to run a query.

We ask: How does the work grow as the data grows?

Scenario Under Consideration

Analyze the time complexity of the following query plan.

EXPLAIN SELECT * FROM orders WHERE customer_id = 123;

This query fetches all orders for one customer by filtering on customer_id.

Identify Repeating Operations

Look at what repeats when the query runs.

• Primary operation: Scanning rows in the orders table.
• How many times: Once for each row until matching rows are found.

How Execution Grows With Input

As the number of orders grows, the work to find matching rows changes.

Input Size (n)	Approx. Operations
10	10 rows checked
100	100 rows checked
1000	1000 rows checked

Pattern observation: The work grows directly with the number of rows if no index is used.

Final Time Complexity

Time Complexity: O(n)

This means the time to run the query grows linearly with the number of rows in the table.

Common Mistake

[X] Wrong: "EXPLAIN always shows the exact time the query will take."

[OK] Correct: EXPLAIN shows the plan and estimated steps, not the exact time, which depends on data and indexes.

Interview Connect

Understanding EXPLAIN helps you see how databases handle queries, a useful skill for writing fast queries and solving problems.

Self-Check

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