Time Complexity: Why table design affects performance
O(n) without index, O(log n) with index
0
0
Why table design affects performance in MySQL - Performance Analysis
Understanding Time Complexity
Good table design helps databases work faster. We want to see how design choices change the work needed when data grows.
How does the way we build tables affect the time to run queries?
Scenario Under Consideration
Analyze the time complexity of this simple query on two different table designs.
-- Query to find a user by email
SELECT * FROM users WHERE email = 'example@example.com';
-- Table design 1: email is not indexed
-- Table design 2: email has an index
This query looks for a user by email. The difference is if the email column has an index or not.
Identify Repeating Operations
Look at what repeats when searching for the email.
- Primary operation: Checking rows to find matching email.
- How many times: Without index, it checks every row one by one. With index, it uses a fast lookup.
How Execution Grows With Input
As the number of rows grows, the work changes differently depending on design.
| Input Size (n) | Approx. Operations Without Index | Approx. Operations With Index |
|---|---|---|
| 10 | 10 checks | About 4 checks |
| 100 | 100 checks | About 7 checks |
| 1000 | 1000 checks | About 10 checks |
Pattern observation: Without index, checks grow directly with rows. With index, checks grow slowly even if rows grow a lot.
Final Time Complexity
Time Complexity: O(n) without index, O(log n) with index
This means searching without an index takes longer as the table grows, but with an index it stays much faster.
Common Mistake
[X] Wrong: "Adding more columns to a table always slows down queries equally."
[OK] Correct: Only columns used in search or joins affect query speed much. Extra columns stored don't slow down searches if not used.
Interview Connect
Understanding how table design affects query speed shows you know how databases handle data. This skill helps you write faster queries and design better systems.
Self-Check
"What if we added a composite index on email and username? How would the time complexity change when searching by email only?"