Deadlock detection and prevention in MySQL - Time & Space Complexity

Time Complexity: Deadlock detection and prevention

O(n^2)

Understanding Time Complexity

When databases handle many tasks at once, sometimes they get stuck waiting for each other. This is called a deadlock.

We want to understand how the time to find and fix these deadlocks changes as more tasks run.

Scenario Under Consideration

Analyze the time complexity of deadlock detection in MySQL's InnoDB engine.

-- Simplified deadlock detection query
SELECT 
  waiting_trx_id AS waiting_trx,
  blocking_trx_id AS blocking_trx
FROM 
  information_schema.innodb_lock_waits;

-- This query helps find which transactions are waiting and blocking
    

This code checks which transactions are waiting for locks held by others to detect deadlocks.

Identify Repeating Operations

Look at what repeats as the database grows.

• Primary operation: Scanning lock wait and lock tables to find conflicts.
• How many times: For each waiting lock, the system checks matching locks held by other transactions.

How Execution Grows With Input

As more transactions run and hold locks, the system checks more pairs to find deadlocks.

Input Size (n)	Approx. Operations
10	About 100 checks
100	About 10,000 checks
1000	About 1,000,000 checks

Pattern observation: The number of checks grows quickly as the number of locks increases, roughly multiplying by itself.

Final Time Complexity

Time Complexity: O(n^2)

This means the time to detect deadlocks grows roughly with the square of the number of locks being checked.

Common Mistake

[X] Wrong: "Deadlock detection time grows linearly as more transactions run."

[OK] Correct: Because each waiting lock must be compared to many held locks, the checks multiply, not just add up.

Interview Connect

Understanding how deadlock detection scales helps you explain how databases keep data safe and responsive even with many users.

Self-Check

What if the database used a different method that only checked locks in a smaller group? How would that change the time complexity?

Practice

1. What is a deadlock in MySQL InnoDB storage engine?

easy

A. A type of backup failure during database replication.

B. A syntax error in SQL queries causing transaction failure.

C. A temporary network disconnection between client and server.

D. A situation where two or more transactions wait indefinitely for each other to release locks.

Solution

1. Step 1: Understand transaction locking

   Transactions acquire locks on data to ensure consistency. If two transactions wait for each other's locks, progress stops.

2. Step 2: Define deadlock

   This waiting cycle with no resolution is called a deadlock, causing transactions to block indefinitely.

3. Final Answer:

   A situation where two or more transactions wait indefinitely for each other to release locks. -> Option D

4. Quick Check:

   Deadlock = Transactions waiting on each other [OK]

Hint: Deadlock means transactions block each other forever [OK]

Common Mistakes:

• Confusing deadlock with syntax errors
• Thinking deadlock is a network issue
• Assuming deadlock is a backup problem

2. Which MySQL command helps you check the latest deadlock information in InnoDB?

easy

A. SHOW PROCESSLIST;

B. SHOW ENGINE INNODB STATUS;

C. SHOW TRANSACTION LOCKS;

D. SHOW DEADLOCKS;

Solution

1. Step 1: Identify command for deadlock info

   MySQL does not have a direct SHOW DEADLOCKS command, but SHOW ENGINE INNODB STATUS shows detailed InnoDB info including deadlocks.

2. Step 2: Confirm other options

   SHOW PROCESSLIST shows running threads, not deadlocks. SHOW TRANSACTION LOCKS is invalid syntax.

3. Final Answer:

   SHOW ENGINE INNODB STATUS; -> Option B

4. Quick Check:

   SHOW ENGINE INNODB STATUS = Deadlock info [OK]

Hint: Use SHOW ENGINE INNODB STATUS for deadlock details [OK]

Common Mistakes:

• Using non-existent SHOW DEADLOCKS command
• Confusing PROCESSLIST with deadlock info
• Trying SHOW TRANSACTION LOCKS which is invalid

3. Consider two transactions T1 and T2 running concurrently:
-- T1: START TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
-- T2: START TRANSACTION;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
What is the likely outcome if both run at the same time without deadlock prevention?

medium

A. A deadlock occurs causing one transaction to be rolled back.

B. Both transactions complete successfully without waiting.

C. Both transactions fail with syntax errors.

D. Transactions run sequentially without any lock conflicts.

Solution

1. Step 1: Analyze lock acquisition order

   T1 locks account id=1 first, then id=2. T2 locks id=2 first, then id=1. This creates a circular wait.

2. Step 2: Identify deadlock

   Because each transaction waits for the other's locked row, a deadlock occurs. MySQL detects this and rolls back one transaction.

3. Final Answer:

   A deadlock occurs causing one transaction to be rolled back. -> Option A

4. Quick Check:

   Opposite lock order = Deadlock and rollback [OK]

Hint: Opposite lock order in transactions causes deadlock [OK]

Common Mistakes:

• Assuming both transactions succeed without conflict
• Thinking syntax errors cause failure
• Believing transactions run sequentially automatically

4. You have this MySQL transaction code causing deadlocks:
START TRANSACTION;
UPDATE products SET stock = stock - 1 WHERE id = 10;
UPDATE orders SET status = 'processed' WHERE id = 100;
COMMIT;
How can you fix deadlocks by changing the transaction?

medium

A. Keep transactions short and access tables in the same order everywhere.

B. Add a LOCK TABLES statement before updates.

C. Use multiple COMMIT statements inside the transaction.

D. Disable autocommit mode.

Solution

1. Step 1: Understand deadlock causes

   Deadlocks often happen when transactions lock tables in different orders or run too long holding locks.

2. Step 2: Apply prevention best practice

   Keeping transactions short and always locking tables in the same order prevents circular waits and deadlocks.

3. Final Answer:

   Keep transactions short and access tables in the same order everywhere. -> Option A

4. Quick Check:

   Short, ordered transactions prevent deadlocks [OK]

Hint: Short, consistent lock order avoids deadlocks [OK]

Common Mistakes:

• Thinking LOCK TABLES solves deadlocks alone
• Using multiple COMMITs inside one transaction
• Confusing autocommit disabling with deadlock fix

5. You want to prevent deadlocks in a high-traffic MySQL application. Which combination of strategies is best?

• 1. Keep transactions short
• 2. Set innodb_lock_wait_timeout to a low value
• 3. Use consistent lock order in all transactions
• 4. Disable foreign key constraints

hard

A. 1 and 4 only

B. 2 and 4 only

C. 1, 2, and 3 only

D. All four strategies

Solution

1. Step 1: Evaluate each strategy

   Keeping transactions short and consistent lock order reduce deadlocks. Setting a low innodb_lock_wait_timeout helps detect and abort deadlocks quickly.

2. Step 2: Assess disabling foreign keys

   Disabling foreign keys can cause data integrity issues and does not prevent deadlocks effectively.

3. Final Answer:

   1, 2, and 3 only -> Option C

4. Quick Check:

   Short, timeout, order = Deadlock prevention [OK]

Hint: Short transactions + timeout + lock order prevent deadlocks [OK]

Common Mistakes:

• Disabling foreign keys to prevent deadlocks
• Ignoring lock wait timeout settings
• Not enforcing consistent lock order