Time Complexity: EXPLAIN plan for query analysis
O(n)
0
0
EXPLAIN plan for query analysis in SQL - Time & Space Complexity
Understanding Time Complexity
When we use EXPLAIN plans, we want to understand how a database query will perform as data grows.
We ask: How does the work needed change when the data size increases?
Scenario Under Consideration
Analyze the time complexity of this SQL query using EXPLAIN.
EXPLAIN
SELECT * FROM orders
WHERE customer_id = 12345;
This query fetches all orders for one customer by filtering on customer_id.
Identify Repeating Operations
Look at what the database does repeatedly to answer this query.
- Primary operation: Scanning rows to find matches for customer_id.
- How many times: Depends on number of rows in orders table.
How Execution Grows With Input
As the orders table grows, the database must check more rows if no index is used.
| 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.
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 query always runs fast no matter the data size."
[OK] Correct: Without indexes, the database must check every row, so bigger tables take longer.
Interview Connect
Understanding how queries scale helps you write better database code and explain your thinking clearly.
Self-Check
"What if we add an index on customer_id? How would the time complexity change?"