Time Complexity: INSERT ON CONFLICT (upsert)
O(log n)
0
0
INSERT ON CONFLICT (upsert) in PostgreSQL - Time & Space Complexity
Understanding Time Complexity
When we use INSERT ON CONFLICT in PostgreSQL, we want to add new data or update existing data without duplicates.
We ask: How does the time to do this grow as the data gets bigger?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
INSERT INTO users (id, name, email)
VALUES (1, 'Alice', 'alice@example.com')
ON CONFLICT (id) DO UPDATE
SET name = EXCLUDED.name, email = EXCLUDED.email;
This code tries to insert a user. If the user id already exists, it updates the name and email instead.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Searching for a matching row by the conflict key (id).
- How many times: Once per insert or update operation.
How Execution Grows With Input
As the table grows, finding if the id exists takes longer if no index is used.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 checks if no index |
| 100 | About 100 checks if no index |
| 1000 | About 1000 checks if no index |
Pattern observation: Without an index, the search grows linearly with table size. With an index, it stays fast.
Final Time Complexity
Time Complexity: O(log n)
This means the time to insert or update grows slowly as the table grows, thanks to the index.
Common Mistake
[X] Wrong: "INSERT ON CONFLICT always takes the same time no matter the table size."
[OK] Correct: Without an index on the conflict column, the database must scan more rows as the table grows, making it slower.
Interview Connect
Understanding how upsert works and its time cost shows you know how databases handle data efficiently, a useful skill in many projects.
Self-Check
"What if we removed the index on the conflict column? How would the time complexity change?"