Time Complexity: Query execution plans
O(n)
0
0
Query execution plans in DBMS Theory - Time & Space Complexity
Understanding Time Complexity
When a database runs a query, it creates a plan to get the data efficiently.
We want to understand how the time to run the query grows as the data size increases.
Scenario Under Consideration
Analyze the time complexity of the following SQL query execution plan snippet.
EXPLAIN SELECT * FROM Orders WHERE CustomerID = 123;
-- The plan shows a table scan or an index seek
-- If no index, full scan of Orders table
-- If index on CustomerID, index seek used
This query fetches all orders for a specific customer using a filter on CustomerID.
Identify Repeating Operations
Look at how the database checks rows to find matches.
- Primary operation: Scanning rows in the Orders table.
- How many times: Once for each row in the table or index.
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: Without an index, the database checks each row one by one, so work grows directly with data size.
Final Time Complexity
Time Complexity: O(n)
This means the time to run the query grows in direct proportion to the number of rows in the table.
Common Mistake
[X] Wrong: "The query always runs fast regardless of table size."
[OK] Correct: Without an index, the database must check every row, so bigger tables take more time.
Interview Connect
Understanding how query plans affect time helps you explain how databases handle data efficiently in real projects.
Self-Check
"What if we add an index on CustomerID? How would the time complexity change?"