REPLACE INTO behavior in MySQL - Time & Space Complexity

Time Complexity: REPLACE INTO behavior

O(log n)

Understanding Time Complexity

We want to understand how the time it takes to run a REPLACE INTO query changes as the data grows.

Specifically, how does the database handle inserting or updating rows when using REPLACE INTO?

Scenario Under Consideration

Analyze the time complexity of the following REPLACE INTO query.

REPLACE INTO users (id, name, email) 
VALUES (5, 'Alice', '[e-mail]');
    

This query inserts a new row or replaces an existing row with the same primary key in the users table.

Identify Repeating Operations

Look for operations that repeat or scale with data size.

• Primary operation: Searching for an existing row with the same primary key.
• How many times: The database checks the index once per REPLACE INTO execution.

How Execution Grows With Input

As the table grows, finding the row to replace depends on the index size.

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

Pattern observation: The search steps grow slowly as the table grows, thanks to indexing.

Final Time Complexity

Time Complexity: O(log n)

This means the time to find and replace a row grows slowly as the table gets bigger, because it uses an index to find the row efficiently.

Common Mistake

[X] Wrong: "REPLACE INTO always scans the whole table to find a row to replace."

[OK] Correct: The database uses indexes to quickly find the row by primary key, so it does not scan the entire table.

Interview Connect

Understanding how REPLACE INTO works helps you explain how databases handle updates and inserts efficiently, a useful skill for real projects and interviews.

Self-Check

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