Advisory locks in PostgreSQL - Time & Space Complexity

Time Complexity: Advisory locks

O(n)

Understanding Time Complexity

When using advisory locks in PostgreSQL, it's important to understand how the time to acquire or release a lock changes as more locks are requested.

We want to know how the system behaves when many sessions try to get advisory locks at the same time.

Scenario Under Consideration

Analyze the time complexity of acquiring and releasing advisory locks.

-- Acquire an advisory lock with a key
SELECT pg_advisory_lock(12345);

-- Do some work while holding the lock

-- Release the advisory lock
SELECT pg_advisory_unlock(12345);
    

This code acquires a lock identified by a key, does some work, then releases the lock.

Identify Repeating Operations

Look for repeated actions that affect performance.

• Primary operation: Checking and managing lock state in the lock manager.
• How many times: Each lock request involves searching the lock table, which grows with the number of active locks.

How Execution Grows With Input

As more sessions request advisory locks, the system must check existing locks to avoid conflicts.

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

Pattern observation: The number of operations grows roughly in direct proportion to the number of active locks.

Final Time Complexity

Time Complexity: O(n)

This means the time to acquire or release a lock grows linearly with the number of locks currently held.

Common Mistake

[X] Wrong: "Acquiring an advisory lock always takes the same time no matter how many locks exist."

[OK] Correct: The system must check existing locks to avoid conflicts, so more locks mean more work and longer wait times.

Interview Connect

Understanding how advisory locks scale helps you design systems that handle concurrency well and avoid bottlenecks.

Self-Check

"What if advisory locks were replaced with session-level locks that do not check other locks? How would the time complexity change?"

Practice

1. What is the main purpose of advisory locks in PostgreSQL?

easy

A. To control access to resources using user-defined keys

B. To automatically manage table-level locks during transactions

C. To speed up query execution by caching results

D. To backup the database safely without downtime

Solution

1. Step 1: Understand advisory locks concept

   Advisory locks allow applications to coordinate access to resources by using custom keys, not automatic locks on tables or rows.

2. Step 2: Compare options

   The other options describe other database features unrelated to advisory locks.

3. Final Answer:

   To control access to resources using user-defined keys -> Option A

4. Quick Check:

   Advisory locks = user-defined resource control [OK]

Hint: Advisory locks use keys to manage resource access [OK]

Common Mistakes:

• Confusing advisory locks with automatic table locks
• Thinking advisory locks speed up queries
• Assuming advisory locks handle backups

2. Which of the following is the correct syntax to acquire a session-level advisory lock with key 12345?

easy

A. SELECT pg_advisory_lock(12345);

B. LOCK TABLE pg_advisory_lock(12345);

C. SELECT acquire_lock(12345);

D. BEGIN LOCK 12345;

Solution

1. Step 1: Recall advisory lock syntax

   PostgreSQL uses the function pg_advisory_lock(key) to acquire a session-level advisory lock.

2. Step 2: Evaluate options

   SELECT pg_advisory_lock(12345); is the correct function call. The other options use invalid syntax or non-existent functions.

3. Final Answer:

   SELECT pg_advisory_lock(12345); -> Option A

4. Quick Check:

   pg_advisory_lock(key) = correct syntax [OK]

Hint: Use SELECT pg_advisory_lock(key) to lock [OK]

Common Mistakes:

• Using LOCK TABLE instead of function call
• Calling non-existent functions like acquire_lock
• Trying to lock with BEGIN LOCK syntax

3. What will be the result of this query if the advisory lock with key 999 is already held by another session?

SELECT pg_try_advisory_lock(999);

medium

A. true

B. false

C. null

D. error

Solution

1. Step 1: Understand pg_try_advisory_lock behavior

   This function tries to acquire the lock immediately and returns true if successful, false if the lock is held by someone else.

2. Step 2: Analyze the scenario

   Since the lock with key 999 is already held, the function returns false without waiting.

3. Final Answer:

   false -> Option B

4. Quick Check:

   pg_try_advisory_lock returns false if lock busy [OK]

Hint: pg_try_advisory_lock returns false if lock busy [OK]

Common Mistakes:

• Expecting true even if lock is held
• Thinking it returns null or error
• Confusing pg_try_advisory_lock with pg_advisory_lock

4. You wrote this code:

SELECT pg_advisory_unlock(123);

But the lock was never acquired before. What will happen?

medium

A. The function returns true and releases the lock

B. The function blocks until the lock is acquired

C. The function throws an error

D. The function returns false because no lock was held

Solution

1. Step 1: Understand pg_advisory_unlock behavior

   This function releases a lock if held and returns true; if no lock was held, it returns false.

2. Step 2: Analyze the scenario

   Since the lock was never acquired, the function returns false without error or blocking.

3. Final Answer:

   The function returns false because no lock was held -> Option D

4. Quick Check:

   Unlock returns false if lock not held [OK]

Hint: Unlock returns false if no lock held [OK]

Common Mistakes:

• Expecting an error when unlocking unheld lock
• Thinking unlock blocks or waits
• Assuming unlock always returns true

5. You want to ensure two different sessions do not run a critical section simultaneously using advisory locks. Which approach is best?

-- Session 1 and 2 run this code:
SELECT pg_try_advisory_lock(42);
-- If true, run critical section, then
SELECT pg_advisory_unlock(42);

hard

A. Use pg_advisory_unlock before acquiring lock to clear old locks

B. Use pg_try_advisory_lock to attempt lock and skip if busy

C. Use pg_advisory_lock to wait until lock is available before running

D. Use random keys each time to avoid conflicts

Solution

1. Step 1: Understand locking strategies

   pg_try_advisory_lock returns immediately and may skip critical section if lock busy; pg_advisory_lock waits until lock is free.

2. Step 2: Choose best approach for critical section

   To ensure only one session runs critical section at a time, waiting for the lock is safer than skipping it.

3. Step 3: Evaluate other options

   Unlocking before acquiring is unsafe and random keys defeat locking purpose.

4. Final Answer:

   Use pg_advisory_lock to wait until lock is available before running -> Option C

5. Quick Check:

   Waiting lock ensures exclusive access [OK]

Hint: Use pg_advisory_lock to wait for exclusive access [OK]

Common Mistakes:

• Using try lock and skipping critical section silently
• Unlocking before locking without owning lock
• Using random keys causing no real locking