ON DUPLICATE KEY UPDATE in MySQL - Time & Space Complexity

Time Complexity: ON DUPLICATE KEY UPDATE

O(log n)

Understanding Time Complexity

When using ON DUPLICATE KEY UPDATE in MySQL, it's important to understand how the time to run the query changes as the data grows.

We want to know how the database handles inserting or updating rows when keys conflict.

Scenario Under Consideration

Analyze the time complexity of the following query.

INSERT INTO users (id, name, score)
VALUES (1, 'Alice', 10)
ON DUPLICATE KEY UPDATE
score = score + 10;
    

This query tries to insert a user. If the user ID already exists, it updates the score instead.

Identify Repeating Operations

Look for operations that repeat or take time depending on data size.

• Primary operation: Checking if the key (user ID) exists in the table.
• How many times: This check happens once per query execution.

How Execution Grows With Input

The time to check if the key exists depends on how MySQL finds the key in the index.

Input Size (n)	Approx. Operations
10	About 3-4 steps to find key
100	About 7 steps to find key
1000	About 10 steps to find key

Pattern observation: The search steps grow slowly as data grows, because the database uses an index tree to find keys efficiently.

Final Time Complexity

Time Complexity: O(log n)

This means the time to insert or update grows slowly as the table gets bigger, thanks to efficient key lookup.

Common Mistake

[X] Wrong: "The query always scans the whole table to find duplicates."

[OK] Correct: The database uses indexes to quickly find keys, so it does not check every row.

Interview Connect

Understanding how ON DUPLICATE KEY UPDATE works helps you explain how databases handle conflicts efficiently, a useful skill in many real-world projects.

Self-Check

"What if the table has no index on the key column? How would the time complexity change?"