Transaction isolation levels in PostgreSQL - Time & Space Complexity

Time Complexity: Transaction isolation levels

O(n)

Understanding Time Complexity

When using transaction isolation levels, we want to know how the time to complete transactions changes as more data or users are involved.

We ask: How does the choice of isolation level affect the time it takes to run transactions as the workload grows?

Scenario Under Consideration

Analyze the time complexity of transactions running under different isolation levels.

BEGIN TRANSACTION ISOLATION LEVEL SERIALIZABLE;
-- Read some rows
SELECT * FROM accounts WHERE user_id = 123;
-- Update a row
UPDATE accounts SET balance = balance - 100 WHERE user_id = 123;
COMMIT;

This code runs a transaction that reads and updates data with the strictest isolation level, ensuring no conflicts but possibly more waiting.

Identify Repeating Operations

Look for operations that repeat or cause waiting as workload grows.

• Primary operation: Accessing and locking rows during the transaction.
• How many times: Once per transaction, but many transactions may run concurrently.

How Execution Grows With Input

As more transactions run at the SERIALIZABLE level, they may wait for locks held by others, increasing total time.

Input Size (number of concurrent transactions)	Approx. Operations (waiting and locking)
10	Low waiting, mostly direct execution
100	More waiting due to conflicts, longer transaction times
1000	High waiting and retries, transactions take much longer

Pattern observation: As concurrent transactions increase, waiting and retries grow, slowing overall execution.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete transactions grows roughly in proportion to the number of concurrent transactions due to waiting and locking.

Common Mistake

[X] Wrong: "All isolation levels have the same speed regardless of workload."

[OK] Correct: Higher isolation levels like SERIALIZABLE cause more waiting and retries as concurrency grows, slowing transactions.

Interview Connect

Understanding how isolation levels affect transaction time helps you design systems that balance correctness and speed, a key skill in database work.

Self-Check

"What if we changed the isolation level from SERIALIZABLE to READ COMMITTED? How would the time complexity change?"