Transaction isolation levels in SQL - Time & Space Complexity

Time Complexity: Transaction isolation levels

O(n)

Understanding Time Complexity

When working with transactions in databases, it's important to understand how the isolation level affects performance.

We want to know how the cost of running transactions changes as more data or concurrent users increase.

Scenario Under Consideration

Analyze the time complexity of this transaction with a specific isolation level.

BEGIN TRANSACTION;
SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
SELECT * FROM orders WHERE customer_id = 123;
UPDATE orders SET status = 'shipped' WHERE order_id = 456;
COMMIT;
    

This code runs a transaction that reads and updates orders with the strictest isolation level.

Identify Repeating Operations

Look for repeated work that affects performance.

• Primary operation: Scanning and locking rows in the orders table.
• How many times: Depends on the number of rows matching the query and concurrent transactions.

How Execution Grows With Input

As more rows match or more users run transactions, the work grows.

Input Size (n)	Approx. Operations
10	Locks and checks on about 10 rows
100	Locks and checks on about 100 rows
1000	Locks and checks on about 1000 rows

Pattern observation: The work grows roughly in proportion to the number of rows involved and concurrent transactions.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete the transaction grows linearly with the number of rows it processes and locks.

Common Mistake

[X] Wrong: "Higher isolation levels always have the same speed as lower ones."

[OK] Correct: Higher isolation levels add more locking and checks, so they usually take more time as data or users grow.

Interview Connect

Understanding how isolation levels affect performance helps you explain trade-offs in real database systems.

Self-Check

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