Time Complexity: Why query optimization reduces execution time
O(n * m)
0
0
Why query optimization reduces execution time in DBMS Theory - Performance Analysis
Understanding Time Complexity
When a database runs a query, it can do the work in many ways. Query optimization helps find the fastest way.
We want to understand how optimization affects the time the query takes to finish.
Scenario Under Consideration
Analyze the time complexity of this SQL query execution plan.
SELECT * FROM Orders
JOIN Customers ON Orders.CustomerID = Customers.ID
WHERE Customers.City = 'New York';
This query finds all orders from customers living in New York by joining two tables.
Identify Repeating Operations
Look at what repeats when running this query.
- Primary operation: Scanning rows in Orders and Customers tables.
- How many times: Each row in Orders is checked against matching Customers rows.
How Execution Grows With Input
As the number of rows grows, the work grows too.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 100 checks |
| 100 | About 10,000 checks |
| 1000 | About 1,000,000 checks |
Pattern observation: Without optimization, the work grows very fast as tables get bigger.
Final Time Complexity
Time Complexity: O(n * m)
This means the time grows roughly by multiplying the sizes of the two tables involved.
Common Mistake
[X] Wrong: "Query optimization just makes the computer faster, so time is shorter."
[OK] Correct: Optimization changes how the query runs, reducing repeated work, not just speeding up the machine.
Interview Connect
Understanding how query optimization reduces repeated work helps you explain how databases handle big data efficiently.
Self-Check
"What if we add an index on Customers.City? How would the time complexity change?"