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?"

Practice

1. What does the REPLACE INTO statement do in MySQL?

easy

A. Inserts a new row or replaces an existing row with the same unique key.

B. Only inserts a new row and never updates existing rows.

C. Deletes all rows in the table before inserting new data.

D. Updates all rows in the table without inserting new ones.

Solution

1. Step 1: Understand the purpose of REPLACE INTO

   The REPLACE INTO statement either inserts a new row or replaces an existing row if a unique key conflict occurs.

2. Step 2: Compare with other statements

   Unlike INSERT, it can replace rows, and unlike DELETE, it does not remove all rows before inserting.

3. Final Answer:

   Inserts a new row or replaces an existing row with the same unique key. -> Option A

4. Quick Check:

   REPLACE INTO = Insert or replace [OK]

Hint: REPLACE INTO inserts or updates by unique key conflict [OK]

Common Mistakes:

• Thinking REPLACE INTO only inserts without replacing
• Confusing REPLACE INTO with DELETE
• Assuming REPLACE INTO updates without deleting first

2. Which of the following is the correct syntax for using REPLACE INTO in MySQL?

easy

A. REPLACE INTO table_name (col1, col2) VALUES (val1, val2);

B. REPLACE table_name SET col1=val1, col2=val2;

C. REPLACE INTO table_name VALUES col1=val1, col2=val2;

D. REPLACE INTO table_name (col1, col2) SET (val1, val2);

Solution

1. Step 1: Recall REPLACE INTO syntax

   The correct syntax uses REPLACE INTO table_name (columns) VALUES (values); format.

2. Step 2: Identify incorrect options

   Options A, C, and D use invalid syntax like missing INTO, wrong SET usage, or wrong VALUES format.

3. Final Answer:

   REPLACE INTO table_name (col1, col2) VALUES (val1, val2); -> Option A

4. Quick Check:

   Correct syntax = REPLACE INTO table_name (col1, col2) VALUES (val1, val2); [OK]

Hint: Use REPLACE INTO table (cols) VALUES (vals) syntax [OK]

Common Mistakes:

• Omitting INTO keyword
• Using SET instead of VALUES
• Incorrect parentheses placement

3. Given a table users(id INT PRIMARY KEY, name VARCHAR(20)) with rows:
(1, 'Alice'), (2, 'Bob')
What will be the result after executing:
REPLACE INTO users VALUES (2, 'Charlie');
Then selecting all rows ordered by id?

medium

A. [(1, 'Alice')]

B. [(1, 'Alice'), (2, 'Bob'), (2, 'Charlie')]

C. [(2, 'Charlie')]

D. [(1, 'Alice'), (2, 'Charlie')]

Solution

1. Step 1: Understand REPLACE INTO effect on existing row

   Since id=2 exists, REPLACE deletes that row and inserts the new one with 'Charlie'.

2. Step 2: Check final table rows

   Row with id=1 remains unchanged, row with id=2 is replaced by (2, 'Charlie').

3. Final Answer:

   [(1, 'Alice'), (2, 'Charlie')] -> Option D

4. Quick Check:

   Row with id=2 replaced = [(1, 'Alice'), (2, 'Charlie')] [OK]

Hint: REPLACE deletes existing row with same key before insert [OK]

Common Mistakes:

• Expecting duplicate keys after REPLACE
• Thinking REPLACE only updates without deleting
• Assuming original row remains unchanged

4. You run this query:
REPLACE INTO products (id, name) VALUES (1, 'Pen');
But get an error: ERROR 1146 (42S02): Table 'products' doesn't exist
What is the likely cause?

medium

A. The id column is not a unique or primary key.

B. You forgot to specify the VALUES keyword.

C. The table products does not exist.

D. You used REPLACE INTO instead of INSERT INTO.

Solution

1. Step 1: Check syntax correctness

   The query syntax is correct with REPLACE INTO products (id, name) VALUES (1, 'Pen');.

2. Step 2: Identify cause of table error

   Error 1146 indicates the table products does not exist or is misspelled.

3. Final Answer:

   The table products does not exist. -> Option C

4. Quick Check:

   Table doesn't exist error (1146) means the table is missing [OK]

Hint: Syntax error often means missing or misspelled table [OK]

Common Mistakes:

• Assuming table error means wrong REPLACE INTO usage
• Ignoring table existence
• Confusing table error with syntax error

5. You have a table inventory(product_id INT PRIMARY KEY, quantity INT) with rows:
(101, 5), (102, 10)
You want to add 3 more units to product 101 or insert it if missing.
Which query correctly uses REPLACE INTO to do this?

hard

A. REPLACE INTO inventory VALUES (101, quantity + 3);

B. REPLACE INTO inventory VALUES (101, 8);

C. REPLACE INTO inventory (product_id, quantity) VALUES (101, (SELECT quantity + 3, 0 FROM inventory WHERE product_id=101));

D. REPLACE INTO inventory (product_id, quantity) VALUES (101, 3) ON DUPLICATE KEY UPDATE quantity = quantity + 3;

Solution

1. Step 1: Understand REPLACE INTO behavior

   REPLACE deletes existing row with product_id=101 and inserts new row with given quantity.

2. Step 2: Check options for correctness

   REPLACE INTO inventory VALUES (101, 8); replaces quantity with 8 (5+3). REPLACE INTO inventory VALUES (101, quantity + 3); is invalid syntax. REPLACE INTO inventory (product_id, quantity) VALUES (101, (SELECT quantity + 3, 0 FROM inventory WHERE product_id=101)); uses subquery in VALUES which is not allowed. REPLACE INTO inventory (product_id, quantity) VALUES (101, 3) ON DUPLICATE KEY UPDATE quantity = quantity + 3; mixes REPLACE and ON DUPLICATE KEY UPDATE which is invalid.

3. Final Answer:

   REPLACE INTO inventory VALUES (101, 8); -> Option B

4. Quick Check:

   REPLACE needs full new row, no expressions [OK]

Hint: REPLACE INTO needs full values, no expressions or subqueries [OK]

Common Mistakes:

• Using expressions like quantity + 3 directly in VALUES
• Mixing REPLACE INTO with ON DUPLICATE KEY UPDATE
• Using subqueries inside VALUES clause