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?