Deadlock concept and prevention in SQL - Time & Space Complexity

Time Complexity: Deadlock concept and prevention

O(n)

Understanding Time Complexity

Deadlocks happen when two or more database operations wait for each other to finish, causing a standstill.

We want to understand how the waiting time grows as more transactions compete for resources.

Scenario Under Consideration

Analyze the time complexity of this simple deadlock-prone transaction sequence.

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

BEGIN TRANSACTION;
UPDATE accounts SET balance = balance - 200 WHERE id = 2;
UPDATE accounts SET balance = balance + 200 WHERE id = 1;
COMMIT;

This code shows two transactions updating the same rows but in reverse order, which can cause a deadlock.

Identify Repeating Operations

Look for operations that wait or retry due to deadlock.

• Primary operation: Lock acquisition on rows during UPDATE statements.
• How many times: Each transaction tries to lock two rows; if deadlock occurs, one retries.

How Execution Grows With Input

As more transactions try to update overlapping rows in conflicting order, waiting and retries increase.

Input Size (n transactions)	Approx. Operations (lock attempts + retries)
2	Few retries if deadlock occurs
10	More retries as conflicts rise
100	Many retries, longer waits, possible cascading delays

Pattern observation: Waiting and retries grow quickly as more transactions compete for the same resources.

Final Time Complexity

Time Complexity: O(n)

This means the waiting and retry time grows roughly in proportion to the number of competing transactions.

Common Mistake

[X] Wrong: "Deadlocks only happen rarely and don't affect performance much."

[OK] Correct: Even a few deadlocks cause retries and waiting, which add up as more transactions run concurrently.

Interview Connect

Understanding deadlocks helps you design safer database operations and shows you can think about how systems behave under load.

Self-Check

"What if transactions always locked rows in the same order? How would the time complexity change?"

Practice

1. What is a deadlock in a database system?

easy

A. A backup process that locks the entire database

B. A syntax error in SQL queries causing failure

C. A method to speed up query execution

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

Solution

1. Step 1: Understand transaction locking

   Transactions lock resources to maintain data integrity during operations.

2. Step 2: Identify deadlock condition

   Deadlock occurs when transactions wait on each other's locked resources indefinitely, causing a standstill.

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 forever [OK]

Hint: Deadlock means waiting forever for each other's locked resource [OK]

Common Mistakes:

• Confusing deadlock with syntax errors
• Thinking deadlock speeds up queries
• Assuming deadlock is a backup process

2. Which SQL statement is best to prevent deadlocks by controlling transaction order?

easy

A. Run transactions without COMMIT statements

B. Use SELECT * without WHERE clause

C. Always access tables in the same order in all transactions

D. Use DROP TABLE before INSERT

Solution

1. Step 1: Understand deadlock prevention strategy

   Accessing resources in a consistent order prevents circular waiting among transactions.

2. Step 2: Evaluate options

   Only accessing tables in the same order avoids deadlocks; other options cause errors or do not help.

3. Final Answer:

   Always access tables in the same order in all transactions -> Option C

4. Quick Check:

   Consistent access order = Deadlock prevention [OK]

Hint: Access tables in same order to avoid deadlocks [OK]

Common Mistakes:

• Ignoring transaction commit timing
• Using SELECT * without filters causes performance issues, not deadlocks
• Dropping tables is unrelated to deadlock prevention

3. Consider two transactions:
Transaction 1: LOCK table A; LOCK table B;
Transaction 2: LOCK table B; LOCK table A;
What is the likely outcome?

medium

A. Deadlock occurs because each waits for the other's locked table

B. Transaction 2 commits immediately

C. Transaction 1 fails due to syntax error

D. Both transactions complete successfully without waiting

Solution

1. Step 1: Analyze lock order in transactions

   Transaction 1 locks table A then B; Transaction 2 locks table B then A, creating circular wait.

2. Step 2: Identify deadlock condition

   Each transaction waits for the other's locked resource, causing deadlock.

3. Final Answer:

   Deadlock occurs because each waits for the other's locked table -> Option A

4. Quick Check:

   Opposite lock order = Deadlock [OK]

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

Common Mistakes:

• Assuming transactions run without waiting
• Confusing deadlock with syntax errors
• Thinking one transaction commits immediately

4. You have a deadlock error in your SQL transactions. Which fix will most likely resolve it?

medium

A. Remove all COMMIT statements

B. Change transactions to lock tables in the same order

C. Use SELECT without WHERE clause to avoid locks

D. Increase transaction isolation level to SERIALIZABLE

Solution

1. Step 1: Identify cause of deadlock

   Deadlocks often happen due to inconsistent lock order in transactions.

2. Step 2: Apply fix by ordering locks

   Changing transactions to lock tables in the same order prevents circular waiting and deadlocks.

3. Final Answer:

   Change transactions to lock tables in the same order -> Option B

4. Quick Check:

   Consistent lock order fixes deadlocks [OK]

Hint: Fix deadlocks by ordering locks consistently [OK]

Common Mistakes:

• Removing COMMIT causes longer locks, worsening deadlocks
• SELECT without WHERE does not prevent locks
• Higher isolation can increase deadlocks

5. You want to prevent deadlocks in a system where multiple transactions update two tables, Orders and Customers. Which approach is best?

hard

A. Ensure all transactions update Customers first, then Orders, and keep transactions short

B. Allow transactions to update tables in any order but increase isolation level to SERIALIZABLE

C. Use long transactions with many updates to reduce lock frequency

D. Disable locking to speed up updates

Solution

1. Step 1: Understand deadlock prevention principles

   Accessing resources in the same order and keeping transactions short reduces deadlocks.

2. Step 2: Evaluate options for best practice

   Ensure all transactions update Customers first, then Orders, and keep transactions short enforces consistent order and short transactions, preventing deadlocks effectively.

3. Step 3: Analyze other options

   Allow transactions to update tables in any order but increase isolation level to SERIALIZABLE may increase deadlocks; Use long transactions with many updates to reduce lock frequency lengthens locks; Disable locking to speed up updates is unsafe and invalid.

4. Final Answer:

   Ensure all transactions update Customers first, then Orders, and keep transactions short -> Option A

5. Quick Check:

   Consistent order + short transactions = Deadlock prevention [OK]

Hint: Use same update order and short transactions to prevent deadlocks [OK]

Common Mistakes:

• Increasing isolation level can cause more deadlocks
• Long transactions hold locks longer, increasing deadlock risk
• Disabling locking breaks data integrity