Read committed behavior in PostgreSQL - Time & Space Complexity

Time Complexity: Read committed behavior

O(n)

Understanding Time Complexity

When using read committed behavior in PostgreSQL, we want to understand how the time to read data changes as the amount of data grows.

We ask: How does the database handle reading data when other transactions are changing it?

Scenario Under Consideration

Analyze the time complexity of the following SQL query under read committed isolation.

BEGIN;
SELECT * FROM orders WHERE status = 'pending';
-- Other transactions may update orders concurrently
COMMIT;

This code reads all orders with status 'pending' while other transactions might be updating the table.

Identify Repeating Operations

Look for repeated work done during the query execution.

• Primary operation: Scanning rows in the orders table to find those with status 'pending'.
• How many times: Once per query execution, scanning all relevant rows.

How Execution Grows With Input

As the number of orders grows, the time to scan and read pending orders grows roughly in proportion.

Input Size (n)	Approx. Operations
10	About 10 row checks
100	About 100 row checks
1000	About 1000 row checks

Pattern observation: The work grows linearly with the number of rows scanned.

Final Time Complexity

Time Complexity: O(n)

This means the time to read pending orders grows roughly in direct proportion to the number of rows checked.

Common Mistake

[X] Wrong: "Read committed means the query always reads a fixed small number of rows quickly regardless of table size."

[OK] Correct: The query still scans rows to find matching data, so more rows mean more work, even if it sees only committed data.

Interview Connect

Understanding how read committed isolation affects query time helps you explain database behavior clearly and shows you grasp how transactions impact performance.

Self-Check

What if we added an index on the status column? How would the time complexity change?