Why concurrency control matters in PostgreSQL - Performance Analysis

Time Complexity: Why concurrency control matters

O(n)

Understanding Time Complexity

When many users access a database at the same time, the system must manage their actions carefully.

We want to understand how handling multiple users affects the time it takes to complete tasks.

Scenario Under Consideration

Analyze the time complexity of this simple transaction with concurrency control.

BEGIN;
SELECT balance FROM accounts WHERE id = 1 FOR UPDATE;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
COMMIT;
    

This code locks a row to safely update an account balance when multiple users try to change it.

Identify Repeating Operations

Look for repeated actions that affect time.

• Primary operation: Locking and updating a single row.
• How many times: Once per transaction, but many transactions may wait if others hold locks.

How Execution Grows With Input

As more users try to update the same row, waiting time grows.

Input Size (n)	Approx. Operations
10 users	10 lock attempts, some waiting
100 users	100 lock attempts, longer waits
1000 users	1000 lock attempts, significant waiting

Pattern observation: More users cause more waiting, so total time grows roughly linearly with users competing for the same data.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete all transactions grows roughly in direct proportion to the number of users trying to update the same data.

Common Mistake

[X] Wrong: "Concurrency control has no impact on performance because each query runs fast."

[OK] Correct: Even if each query is fast alone, waiting for locks when many users act at once adds up and slows overall processing.

Interview Connect

Understanding how concurrency control affects time helps you explain real database behavior and shows you grasp how systems handle many users safely and efficiently.

Self-Check

"What if the transactions updated different rows instead of the same one? How would the time complexity change?"