Serializable isolation in PostgreSQL - Time & Space Complexity

Time Complexity: Serializable isolation

O(n * m)

Understanding Time Complexity

When using serializable isolation in databases, we want to understand how the cost of managing transactions grows as more data and transactions happen.

We ask: How does the system handle conflicts and checks as the workload increases?

Scenario Under Consideration

Analyze the time complexity of this transaction under serializable isolation:

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;

-- Read some rows
SELECT balance FROM accounts WHERE account_id = 123;

-- Update a row
UPDATE accounts SET balance = balance - 100 WHERE account_id = 123;

COMMIT;

This code reads and updates data in a transaction that uses serializable isolation to avoid conflicts.

Identify Repeating Operations

In serializable isolation, the database tracks conflicts between transactions.

• Primary operation: Checking for conflicts between transactions.
• How many times: For each transaction, the system compares its read and write sets against other concurrent transactions, which can grow with the number of transactions and rows accessed.

How Execution Grows With Input

As more transactions run and access more rows, the system must do more conflict checks.

Input Size (n)	Approx. Operations
10 transactions	Few conflict checks, fast commit.
100 transactions	More conflict checks, some delays possible.
1000 transactions	Many conflict checks, higher chance of retries.

Pattern observation: The work grows roughly with the number of transactions and the rows they touch, making conflict checking more expensive as load increases.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to check conflicts grows with the number of transactions (n) times the number of rows accessed per transaction (m).

Common Mistake

[X] Wrong: "Serializable isolation always runs as fast as lower isolation levels."

[OK] Correct: Serializable isolation does extra work to prevent conflicts, so as transactions and data grow, it can slow down due to more conflict checks and possible retries.

Interview Connect

Understanding how serializable isolation scales helps you explain database behavior clearly and shows you grasp how systems keep data safe under load.

Self-Check

"What if we changed from serializable to read committed isolation? How would the time complexity of conflict checking change?"

Practice

1.

What does Serializable isolation level guarantee in PostgreSQL?

easy

A. Transactions behave as if executed one after another, preventing anomalies.

B. Transactions can see uncommitted changes from others.

C. Transactions do not lock any rows during execution.

D. Transactions always run faster than other isolation levels.

Solution

1. Step 1: Understand Serializable Isolation Concept

   Serializable isolation ensures transactions appear to run sequentially, avoiding conflicts and anomalies.

2. Step 2: Compare Other Options

   Options B and C describe lower isolation levels or incorrect behavior; D is false as serializable can be slower due to locking.

3. Final Answer:

   Transactions behave as if executed one after another, preventing anomalies. -> Option A

4. Quick Check:

   Serializable isolation = sequential transaction behavior [OK]

Hint: Serializable means transactions act one by one, no surprises [OK]

Common Mistakes:

• Confusing Serializable with Read Committed
• Thinking Serializable allows dirty reads
• Assuming Serializable is always fastest

2.

Which of the following is the correct way to set the transaction isolation level to Serializable in PostgreSQL?

BEGIN;
-- What goes here?
COMMIT;

easy

A. SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

B. SET ISOLATION LEVEL TRANSACTION SERIALIZABLE;

C. SET TRANSACTION LEVEL SERIALIZABLE ISOLATION;

D. SET SERIALIZABLE TRANSACTION ISOLATION LEVEL;

Solution

1. Step 1: Recall Correct Syntax for Setting Isolation Level

   The correct syntax is SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; before running queries in the transaction.

2. Step 2: Eliminate Incorrect Syntax Options

   Options B, C, and D have incorrect word order or missing keywords, causing syntax errors.

3. Final Answer:

   SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; -> Option A

4. Quick Check:

   Correct syntax = SET TRANSACTION ISOLATION LEVEL SERIALIZABLE [OK]

Hint: Remember: SET TRANSACTION ISOLATION LEVEL SERIALIZABLE [OK]

Common Mistakes:

• Mixing word order in SET command
• Omitting 'TRANSACTION' keyword
• Using invalid keywords or order

3.

Consider two concurrent transactions running under Serializable isolation in PostgreSQL:

-- Transaction 1
BEGIN;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- waits here

-- Transaction 2
BEGIN;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
UPDATE accounts SET balance = balance + 100 WHERE id = 2;
COMMIT;

-- Transaction 1 continues
COMMIT;

What will happen when Transaction 1 tries to commit?

medium

A. Transaction 1 is rolled back due to serialization failure and must retry.

B. Transaction 1 blocks indefinitely waiting for Transaction 2.

C. Transaction 1 commits successfully without errors.

D. Transaction 1 commits but with dirty reads.

Solution

1. Step 1: Understand Serializable Isolation Behavior

   Under Serializable isolation, PostgreSQL uses SSI which allows non-conflicting concurrent transactions to commit successfully without blocking or failing.

2. Step 2: Analyze the Scenario

   Transaction 1 updates id=1, Transaction 2 updates id=2 (different rows). No read-write conflicts or serialization anomalies possible, so Transaction 1 commits successfully.

3. Final Answer:

   Transaction 1 commits successfully without errors. -> Option C

4. Quick Check:

   Non-conflicting updates in Serializable succeed [OK]

Hint: Serializable allows independent concurrent transactions [OK]

Common Mistakes:

• Thinking all concurrent updates cause serialization failure
• Assuming blocking like in stricter locking modes
• Believing dirty reads happen in Serializable

4.

Given this PostgreSQL transaction block:

BEGIN;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
UPDATE products SET stock = stock - 1 WHERE id = 10;
COMMIT;

After running this, you get an error: ERROR: could not serialize access due to concurrent update. What is the best way to fix this?

medium

A. Ignore the error and continue.

B. Remove the COMMIT statement.

C. Change isolation level to Read Uncommitted.

D. Retry the entire transaction from the beginning.

Solution

1. Step 1: Understand Serialization Failure Cause

   The error means a concurrent transaction caused a conflict; PostgreSQL aborts the transaction to maintain correctness.

2. Step 2: Apply Recommended Fix

   The correct fix is to retry the entire transaction, as the conflict may not happen again on retry.

3. Final Answer:

   Retry the entire transaction from the beginning. -> Option D

4. Quick Check:

   Serialization errors require transaction retry [OK]

Hint: On serialization error, retry transaction fully [OK]

Common Mistakes:

• Ignoring the error and proceeding
• Lowering isolation level unsafely
• Removing COMMIT causing open transactions

5.

You have a banking app using PostgreSQL with Serializable isolation. You want to transfer money between accounts safely. Which approach best handles serialization failures?

-- Pseudocode
BEGIN;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- debit from source account
-- credit to target account
COMMIT;

What is the best way to ensure the transfer completes reliably?

hard

A. Set isolation level to Read Committed to avoid errors.

B. Wrap the transaction in a retry loop that restarts on serialization failure.

C. Use explicit table locks to prevent conflicts.

D. Ignore serialization errors and log them only.

Solution

1. Step 1: Recognize Need for Reliable Transaction Completion

   Serializable isolation can cause serialization failures; to handle this, retrying the transaction is necessary.

2. Step 2: Evaluate Options for Handling Failures

   Lowering isolation risks data anomalies; explicit locks add complexity; ignoring errors risks data loss. Retrying is best practice.

3. Final Answer:

   Wrap the transaction in a retry loop that restarts on serialization failure. -> Option B

4. Quick Check:

   Retry loop ensures reliable serializable transactions [OK]

Hint: Use retry loops to handle serialization failures safely [OK]

Common Mistakes:

• Switching to lower isolation unsafely
• Relying on manual locks instead of retries
• Ignoring errors risking inconsistent data