Deadlock detection and prevention in PostgreSQL - Time & Space Complexity

Time Complexity: Deadlock detection and prevention

O(n + e)

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 system finds and stops these deadlocks as more tasks run.

Scenario Under Consideration

Analyze the time complexity of PostgreSQL's deadlock detection query.

WITH RECURSIVE waiting_graph AS (
  SELECT
    blocked.pid AS blocked_pid,
    blocking.pid AS blocking_pid
  FROM pg_locks blocked
  JOIN pg_locks blocking ON blocked.locktype = blocking.locktype
    AND blocked.database IS NOT DISTINCT FROM blocking.database
    AND blocked.relation IS NOT DISTINCT FROM blocking.relation
    AND blocked.page IS NOT DISTINCT FROM blocking.page
    AND blocked.tuple IS NOT DISTINCT FROM blocking.tuple
    AND blocked.virtualxid IS NOT DISTINCT FROM blocking.virtualxid
    AND blocked.transactionid IS NOT DISTINCT FROM blocking.transactionid
    AND blocked.classid IS NOT DISTINCT FROM blocking.classid
    AND blocked.objid IS NOT DISTINCT FROM blocking.objid
    AND blocked.objsubid IS NOT DISTINCT FROM blocking.objsubid
  WHERE blocked.granted = false AND blocking.granted = true
),
search_cycle AS (
  SELECT blocked_pid, blocking_pid, ARRAY[blocked_pid] AS path
  FROM waiting_graph
  UNION ALL
  SELECT wg.blocked_pid, wg.blocking_pid, path || wg.blocked_pid
  FROM waiting_graph wg
  JOIN search_cycle sc ON wg.blocked_pid = sc.blocking_pid
  WHERE NOT wg.blocked_pid = ANY(path)
)
SELECT * FROM search_cycle WHERE blocking_pid = ANY(path[1:array_length(path,1)-1]);
    

This query looks for cycles in the waiting graph to detect deadlocks among transactions.

Identify Repeating Operations

Look for repeated checks and traversals in the query.

• Primary operation: Recursive search through the waiting graph to find cycles.
• How many times: The recursion repeats for each edge in the graph until a cycle is found or all paths are checked.

How Execution Grows With Input

The more transactions and locks there are, the bigger the waiting graph becomes.

Input Size (n)	Approx. Operations
10	About 20-30 recursive checks
100	Hundreds of recursive checks
1000	Thousands to tens of thousands of checks

Pattern observation: The work grows quickly as the number of waiting relationships grows, because the system must explore many paths to find cycles.

Final Time Complexity

Time Complexity: O(n + e)

This means the detection time grows roughly with the number of transactions and their waiting connections.

Common Mistake

[X] Wrong: "Deadlock detection only checks a fixed number of transactions, so it always runs fast."

[OK] Correct: The detection must explore all waiting links between transactions, which can grow a lot as more transactions wait on each other.

Interview Connect

Understanding how deadlock detection scales helps you explain how databases keep running smoothly even with many users.

Self-Check

"What if the database used a simpler method that only checked direct waits, not recursive cycles? How would the time complexity change?"

Practice

1. What is a deadlock in PostgreSQL?

easy

A. A performance optimization technique for faster queries.

B. A syntax error in SQL statements causing query failure.

C. A backup process that locks tables during data export.

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 resources to maintain data integrity.

2. Step 2: Define deadlock

   A deadlock occurs when transactions wait on each other in a cycle, causing indefinite waiting.

3. Final Answer:

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

4. Quick Check:

   Deadlock = cyclic waiting [OK]

Hint: Deadlock means transactions wait forever on each other [OK]

Common Mistakes:

• Confusing deadlock with syntax errors
• Thinking deadlock improves performance
• Mixing deadlock with backup locking

2. Which of the following is the correct way to acquire locks to prevent deadlocks in PostgreSQL?

easy

A. Acquire locks on resources in random order.

B. Acquire locks on resources in the same order in all transactions.

C. Never acquire any locks in transactions.

D. Acquire locks only after committing the transaction.

Solution

1. Step 1: Understand lock acquisition order

   Acquiring locks in a consistent order prevents circular waiting.

2. Step 2: Identify correct practice

   All transactions should acquire locks on resources in the same order to avoid deadlocks.

3. Final Answer:

   Acquire locks on resources in the same order in all transactions. -> Option B

4. Quick Check:

   Consistent lock order = no deadlock [OK]

Hint: Always lock resources in the same order [OK]

Common Mistakes:

• Locking resources randomly
• Not locking resources at all
• Locking after commit

3. Consider two transactions in PostgreSQL:
-- Transaction 1
BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
UPDATE accounts SET balance = balance + 50 WHERE id = 2;
-- waits here

-- Transaction 2
BEGIN;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
UPDATE accounts SET balance = balance - 50 WHERE id = 1;
-- waits here
What will PostgreSQL do when both transactions wait for each other?

medium

A. Both transactions will wait forever causing a deadlock.

B. Both transactions will succeed without any issue.

C. PostgreSQL will detect the deadlock and abort one transaction automatically.

D. PostgreSQL will merge both transactions into one.

Solution

1. Step 1: Identify deadlock scenario

   Both transactions hold locks and wait for the other's lock, creating a cycle.

2. Step 2: PostgreSQL deadlock detection

   PostgreSQL automatically detects deadlocks and aborts one transaction to break the cycle.

3. Final Answer:

   PostgreSQL will detect the deadlock and abort one transaction automatically. -> Option C

4. Quick Check:

   Deadlock detected = abort one transaction [OK]

Hint: PostgreSQL aborts one transaction on deadlock detection [OK]

Common Mistakes:

• Assuming infinite waiting without abort
• Thinking transactions merge automatically
• Believing both succeed without conflict

4. You have the following PostgreSQL code causing a deadlock:

BEGIN;
LOCK TABLE orders IN ACCESS EXCLUSIVE MODE;
UPDATE customers SET name = 'Alice' WHERE id = 1;
-- Transaction 2 starts here
BEGIN;
LOCK TABLE customers IN ACCESS EXCLUSIVE MODE;
UPDATE orders SET status = 'shipped' WHERE id = 10;

What is the main issue causing the deadlock?

medium

A. Transactions lock tables in different orders causing circular wait.

B. Using SHARE MODE lock instead of EXCLUSIVE MODE.

C. Updating different tables in the same transaction.

D. Missing COMMIT statements after updates.

Solution

1. Step 1: Analyze lock order

   Transaction 1 locks orders first, then updates customers; Transaction 2 locks customers first, then updates orders.

2. Step 2: Identify circular wait

   Each transaction waits for the other's locked table, causing deadlock due to different lock order.

3. Final Answer:

   Transactions lock tables in different orders causing circular wait. -> Option A

4. Quick Check:

   Different lock order = deadlock risk [OK]

Hint: Lock tables in same order to avoid deadlock [OK]

Common Mistakes:

• Blaming lock mode instead of order
• Thinking updating different tables causes deadlock
• Ignoring missing COMMIT as cause

5. You want to prevent deadlocks in a multi-user PostgreSQL system updating inventory and sales tables. Which strategy is best?

hard

A. Keep transactions short and acquire locks on inventory then sales in all transactions.

B. Acquire locks on sales first, then inventory, but only in some transactions.

C. Avoid using transactions to prevent locking.

D. Use long transactions to batch updates and reduce lock frequency.

Solution

1. Step 1: Understand deadlock prevention

   Keeping transactions short reduces lock time; consistent lock order prevents cycles.

2. Step 2: Apply best practice

   Always lock inventory first, then sales, in all transactions to avoid deadlocks.

3. Final Answer:

   Keep transactions short and acquire locks on inventory then sales in all transactions. -> Option A

4. Quick Check:

   Short transactions + consistent lock order = deadlock prevention [OK]

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

Common Mistakes:

• Locking in inconsistent order
• Avoiding transactions entirely
• Using long transactions increasing lock time