Time Complexity: PostgreSQL vs MySQL key differences
O(log n)
0
0
PostgreSQL vs MySQL key differences - Performance Comparison
Understanding Time Complexity
When comparing PostgreSQL and MySQL, it's important to understand how their operations scale with data size.
We want to see how query execution time grows as the amount of data increases in each system.
Scenario Under Consideration
Analyze the time complexity of a simple SELECT query with a WHERE condition on an indexed column.
SELECT * FROM users WHERE email = 'example@example.com';
This query looks up a user by email using an index to speed up the search.
Identify Repeating Operations
In this query, the main repeated operation is scanning the index to find matching rows.
- Primary operation: Index lookup on the email column.
- How many times: Depends on the number of matching entries, usually very few due to uniqueness.
How Execution Grows With Input
As the number of users grows, the index helps keep the search fast by avoiding full table scans.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 3-4 index steps |
| 100 | About 5-6 index steps |
| 1000 | About 7-8 index steps |
Pattern observation: The number of steps grows slowly, roughly with the logarithm of data size.
Final Time Complexity
Time Complexity: O(log n)
This means the query time grows slowly as the data grows, thanks to the index.
Common Mistake
[X] Wrong: "Using an index means the query always takes the same time no matter how big the data is."
[OK] Correct: Even with an index, the search time grows slowly as data grows, but much slower than scanning all rows.
Interview Connect
Understanding how indexes affect query time in PostgreSQL and MySQL helps you explain database performance clearly and confidently.
Self-Check
"What if the email column was not indexed? How would the time complexity change?"