Row-level locking (FOR UPDATE, FOR SHARE) in PostgreSQL - Time & Space Complexity

Time Complexity: Row-level locking (FOR UPDATE, FOR SHARE)

O(n)

Understanding Time Complexity

When using row-level locking in a database, it is important to understand how the time to lock rows grows as the number of rows increases.

We want to know how the locking operation scales when more rows are involved.

Scenario Under Consideration

Analyze the time complexity of the following PostgreSQL query using row-level locking.

SELECT * FROM orders
WHERE status = 'pending'
FOR UPDATE;
    

This query selects all rows with status 'pending' and locks them to prevent other transactions from modifying them until this transaction finishes.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Scanning rows that match the condition and locking each one.
• How many times: Once for each matching row in the table.

How Execution Grows With Input

As the number of rows with status 'pending' grows, the database must lock more rows one by one.

Input Size (n)	Approx. Operations
10	Locks 10 rows
100	Locks 100 rows
1000	Locks 1000 rows

Pattern observation: The number of locking operations grows directly with the number of rows locked.

Final Time Complexity

Time Complexity: O(n)

This means the time to lock rows grows linearly with the number of rows matched and locked.

Common Mistake

[X] Wrong: "Locking rows happens all at once, so time does not depend on how many rows are locked."

[OK] Correct: Each row must be locked individually, so more rows mean more work and more time.

Interview Connect

Understanding how row-level locking scales helps you reason about database performance and concurrency control in real applications.

Self-Check

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

Practice

1. What does the FOR UPDATE clause do in a PostgreSQL query?

easy

A. Locks selected rows to prevent other transactions from modifying them until the current transaction ends.

B. Locks the entire table to prevent any access by other transactions.

C. Allows other transactions to read but not modify the selected rows.

D. Unlocks rows that were previously locked by another transaction.

Solution

1. Step 1: Understand the purpose of FOR UPDATE

   The FOR UPDATE clause locks the rows returned by the query to prevent other transactions from modifying them.

2. Step 2: Compare with other locking types

   Unlike FOR SHARE, which allows reading but prevents writing, FOR UPDATE blocks other transactions from modifying the locked rows until the current transaction ends.

3. Final Answer:

   Locks selected rows to prevent other transactions from modifying them until the current transaction ends. -> Option A

4. Quick Check:

   FOR UPDATE = exclusive row lock [OK]

Hint: FOR UPDATE locks rows for writing, blocking others [OK]

Common Mistakes:

• Confusing FOR UPDATE with table-level locks
• Thinking FOR UPDATE allows other writes
• Mixing FOR UPDATE with FOR SHARE behavior

2. Which of the following is the correct syntax to lock rows for reading using row-level locking in PostgreSQL?

easy

A. SELECT * FROM orders FOR UPDATE;

B. SELECT * FROM orders FOR SHARE;

C. SELECT * FROM orders LOCK ROW;

D. SELECT * FROM orders WITH LOCK;

Solution

1. Step 1: Identify the clause for read locks

   In PostgreSQL, FOR SHARE is used to lock rows for reading, allowing other transactions to read but not modify.

2. Step 2: Check syntax correctness

   Options B and C are invalid syntax. SELECT * FROM orders FOR UPDATE; locks rows for writing, not reading.

3. Final Answer:

   SELECT * FROM orders FOR SHARE; -> Option B

4. Quick Check:

   Read lock = FOR SHARE [OK]

Hint: FOR SHARE locks rows for reading, syntax: SELECT ... FOR SHARE [OK]

Common Mistakes:

• Using FOR UPDATE instead of FOR SHARE for read locks
• Using non-existent LOCK ROW or WITH LOCK syntax
• Confusing table-level locks with row-level locks

3. Consider the following two transactions running concurrently:

-- Transaction 1
BEGIN;
SELECT * FROM products WHERE id = 10 FOR UPDATE;
-- Transaction 2
BEGIN;
SELECT * FROM products WHERE id = 10 FOR SHARE;

What will happen when Transaction 2 tries to execute its SELECT statement?

medium

A. Transaction 2 will immediately acquire the FOR SHARE lock and proceed.

B. Transaction 2 will cause a deadlock error immediately.

C. Transaction 2 will wait until Transaction 1 commits or rolls back before proceeding.

D. Transaction 2 will ignore the lock and read the row without waiting.

Solution

1. Step 1: Understand locking conflict between FOR UPDATE and FOR SHARE

   A FOR UPDATE lock is exclusive and blocks other transactions from acquiring conflicting locks, including FOR SHARE.

2. Step 2: Analyze Transaction 2 behavior

   Transaction 2's FOR SHARE lock request conflicts with Transaction 1's FOR UPDATE lock, so it must wait until Transaction 1 finishes.

3. Final Answer:

   Transaction 2 will wait until Transaction 1 commits or rolls back before proceeding. -> Option C

4. Quick Check:

   FOR UPDATE blocks FOR SHARE until commit [OK]

Hint: FOR UPDATE blocks FOR SHARE until transaction ends [OK]

Common Mistakes:

• Assuming FOR SHARE can proceed during FOR UPDATE lock
• Expecting deadlock without waiting
• Ignoring lock conflicts between FOR UPDATE and FOR SHARE

4. You wrote this query to lock rows for update:

SELECT * FROM customers FOR SHARE;

But you want to prevent other transactions from modifying these rows. What is wrong and how to fix it?

medium

A. FOR SHARE locks the entire table; use WHERE clause to limit rows.

B. FOR SHARE is deprecated; use LOCK TABLE instead.

C. FOR SHARE requires an explicit NOWAIT clause to lock rows.

D. FOR SHARE locks rows only for reading; replace it with FOR UPDATE to lock for writing.

Solution

1. Step 1: Identify the locking behavior of FOR SHARE

   FOR SHARE locks rows to allow reading but does not prevent other transactions from modifying them.

2. Step 2: Choose correct clause to prevent modifications

   To block other transactions from modifying rows, use FOR UPDATE instead of FOR SHARE.

3. Final Answer:

   FOR SHARE locks rows only for reading; replace it with FOR UPDATE to lock for writing. -> Option D

4. Quick Check:

   Prevent writes = use FOR UPDATE [OK]

Hint: Use FOR UPDATE to block writes, not FOR SHARE [OK]

Common Mistakes:

• Thinking FOR SHARE blocks writes
• Using LOCK TABLE unnecessarily
• Missing WHERE clause but unrelated to locking type

5. You want to update multiple rows in a table but ensure no other transaction can read or modify these rows until your transaction finishes. Which locking clause should you use in your SELECT statement before updating?

hard

A. SELECT * FROM table_name FOR UPDATE;

B. SELECT * FROM table_name FOR SHARE;

C. SELECT * FROM table_name FOR NO KEY UPDATE;

D. SELECT * FROM table_name FOR KEY SHARE;

Solution

1. Step 1: Understand the locking levels

   FOR UPDATE locks rows exclusively, blocking writes by others until commit, but does not block reads.

2. Step 2: Compare with other lock types

   FOR SHARE and FOR KEY SHARE allow reads; FOR NO KEY UPDATE is less restrictive and allows some concurrent updates.

3. Step 3: Choose the strictest lock to block writes

   Only FOR UPDATE fully blocks other transactions from modifying the rows, but it does not block reads.

4. Final Answer:

   SELECT * FROM table_name FOR UPDATE; -> Option A

5. Quick Check:

   Block writes = FOR UPDATE [OK]

Hint: FOR UPDATE blocks writes until commit [OK]

Common Mistakes:

• Choosing FOR SHARE or KEY SHARE which allow writes
• Using NO KEY UPDATE which is less strict
• Not understanding lock levels and their effects