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?"

Practice

1. Which transaction isolation level in PostgreSQL allows a transaction to see only committed data at the time each query starts, but can see different data if the same query is run again within the same transaction?

easy

A. SERIALIZABLE

B. REPEATABLE READ

C. READ COMMITTED

D. READ UNCOMMITTED

Solution

1. Step 1: Understand READ COMMITTED behavior

   READ COMMITTED shows only data committed before each query starts, so data can change between queries in the same transaction.

2. Step 2: Compare with other levels

   REPEATABLE READ and SERIALIZABLE keep a consistent snapshot for the whole transaction, so data does not change between queries.

3. Final Answer:

   READ COMMITTED -> Option C

4. Quick Check:

   READ COMMITTED = sees committed data per query [OK]

Hint: READ COMMITTED sees latest committed data per query [OK]

Common Mistakes:

• Confusing REPEATABLE READ with READ COMMITTED
• Thinking SERIALIZABLE allows data changes mid-transaction
• Assuming READ UNCOMMITTED exists in PostgreSQL

2. Which of the following is the correct SQL command to set the transaction isolation level to SERIALIZABLE in PostgreSQL?

easy

A. SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

B. SET ISOLATION LEVEL = SERIALIZABLE;

C. BEGIN TRANSACTION ISOLATION SERIALIZABLE;

D. SET TRANSACTION LEVEL SERIALIZABLE;

Solution

1. Step 1: Recall correct syntax for setting isolation level

   The correct syntax is SET TRANSACTION ISOLATION LEVEL followed by the level name.

2. Step 2: Check each option

   SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; matches the correct syntax exactly. Others have incorrect keywords or missing parts.

3. Final Answer:

   SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; -> Option A

4. Quick Check:

   Correct SET TRANSACTION syntax = SET TRANSACTION ISOLATION LEVEL SERIALIZABLE; [OK]

Hint: Use full phrase: SET TRANSACTION ISOLATION LEVEL [OK]

Common Mistakes:

• Omitting 'TRANSACTION' keyword
• Using '=' sign incorrectly
• Starting with BEGIN instead of SET

3. Consider two concurrent transactions in PostgreSQL using the REPEATABLE READ isolation level. Transaction A reads a row, then Transaction B updates and commits that row. What will Transaction A see if it reads the same row again before committing?

medium

A. The updated row from Transaction B

B. The original row before Transaction B's update

C. An error due to concurrent update

D. No row, because it is locked

Solution

1. Step 1: Understand REPEATABLE READ snapshot

   REPEATABLE READ provides a consistent snapshot for the whole transaction, so it sees data as it was at the start.

2. Step 2: Apply to scenario

   Transaction A will see the original row even after Transaction B commits an update, because its snapshot does not change.

3. Final Answer:

   The original row before Transaction B's update -> Option B

4. Quick Check:

   REPEATABLE READ = consistent snapshot [OK]

Hint: REPEATABLE READ shows data as of transaction start [OK]

Common Mistakes:

• Assuming it sees latest committed data mid-transaction
• Expecting an error or lock blocking read
• Confusing with READ COMMITTED behavior

4. You wrote this command to set the isolation level but get an error: SET TRANSACTION LEVEL = READ COMMITTED; What is the error and how to fix it?

medium

A. Syntax error: remove '=' and use 'ISOLATION' keyword

B. Wrong isolation level name, use 'READ COMMIT' instead

C. Missing semicolon at end of statement

D. SET TRANSACTION cannot be used inside a transaction

Solution

1. Step 1: Identify syntax error

   The command incorrectly uses '=' and omits 'ISOLATION' keyword.

2. Step 2: Correct syntax

   The correct command is SET TRANSACTION ISOLATION LEVEL READ COMMITTED; without '='.

3. Final Answer:

   Syntax error: remove '=' and use 'ISOLATION' keyword -> Option A

4. Quick Check:

   Correct syntax requires 'ISOLATION' and no '=' [OK]

Hint: No '=' sign; use 'ISOLATION' keyword in SET TRANSACTION [OK]

Common Mistakes:

• Using '=' sign in SET TRANSACTION
• Misspelling isolation level names
• Trying to set isolation level outside allowed scope

5. You want to ensure that two concurrent transactions in PostgreSQL never see inconsistent data and avoid phantom reads. Which isolation level should you choose and why?

hard

A. READ UNCOMMITTED, because it allows maximum concurrency

B. REPEATABLE READ, because it prevents non-repeatable reads but allows phantoms

C. READ COMMITTED, because it is fastest and avoids dirty reads

D. SERIALIZABLE, because it fully isolates transactions preventing phantoms

Solution

1. Step 1: Understand phantom reads and isolation levels

   Phantom reads occur when new rows appear in repeated queries within a transaction.

2. Step 2: Match isolation level to requirement

   SERIALIZABLE prevents phantom reads by fully isolating transactions, ensuring consistency.

3. Final Answer:

   SERIALIZABLE, because it fully isolates transactions preventing phantoms -> Option D

4. Quick Check:

   SERIALIZABLE = no phantoms, full isolation [OK]

Hint: Use SERIALIZABLE to prevent phantom reads fully [OK]

Common Mistakes:

• Choosing REPEATABLE READ and expecting no phantoms
• Thinking READ COMMITTED prevents phantoms
• Confusing READ UNCOMMITTED as safe option