Database Locks - Row-Level, Table-Level, Optimistic vs Pessimistic

▶

Steps

setup

Initialize Lock Tree

Initialize an empty lock tree representing no locks held. The root node represents the entire table with no keys locked yet.

💡 Starting with an empty lock tree is essential to visualize how locks are acquired and escalated.

Line:

lock_tree = BTree(order=3)
lock_tree.root = Node(id=1, keys=[], children=[], is_leaf=True, parent=null)

💡 The lock tree starts empty, showing no locks held at any level.

insert

Acquire Row-Level Lock on Row 101

Acquire a row-level lock on row 101 by inserting key 101 into the leaf node representing row locks.

💡 This step shows how a specific row lock is represented as a key in the leaf node.

Line:

lock_tree.insert(101)  # Acquire row-level lock

💡 Row-level locks are stored as keys in leaf nodes, allowing fine-grained concurrency control.

insert

Acquire Row-Level Lock on Row 102

Acquire another row-level lock on row 102 by inserting key 102 into the leaf node.

💡 Adding multiple row locks shows how the tree can hold multiple keys in a leaf node.

Line:

lock_tree.insert(102)  # Acquire row-level lock

💡 Multiple row-level locks coexist in the same leaf node, enabling concurrent access to different rows.

insert

Acquire Row-Level Lock on Row 103 - Trigger Split

Insert key 103 to acquire a row-level lock, causing the leaf node to exceed max keys and trigger a split.

💡 This step demonstrates how the tree structure adapts when a node overflows due to too many locks.

Line:

lock_tree.insert(103)  # Insert triggers split

💡 Node splitting maintains tree balance and efficient lock management as locks increase.

insert

Escalate to Table-Level Lock

Acquire a table-level lock by inserting a special key representing the entire table, causing lock escalation.

💡 This step shows how multiple row locks can escalate to a single table-level lock for efficiency.

Line:

lock_tree.insert('TABLE_LOCK')  # Escalate lock

💡 Lock escalation reduces overhead by replacing many row locks with a single table lock.

compare

Attempt Optimistic Lock on Row 104

Try to acquire an optimistic lock on row 104 by checking if the row is locked without blocking.

💡 Optimistic locking checks for conflicts without locking immediately, improving concurrency.

Line:

if not lock_tree.contains(104):
    proceed without lock

💡 Optimistic locking assumes no conflict and validates later, reducing lock contention.

compare

Optimistic Lock Conflict Detected on Row 105

Attempt optimistic lock on row 105 but detect conflict due to existing table-level lock.

💡 This step shows how optimistic locking fails when a conflicting lock exists.

Line:

if lock_tree.contains(105):
    conflict detected

💡 Optimistic locking requires validation; conflicts force fallback to blocking locks.

insert

Acquire Pessimistic Lock on Row 105

Fallback to acquiring a pessimistic lock on row 105, blocking other transactions until release.

💡 Pessimistic locking ensures exclusive access by blocking conflicting operations.

Line:

lock_tree.insert(105)  # Acquire pessimistic lock

💡 Pessimistic locking guarantees safety by preventing concurrent conflicting access.

delete

Release Row-Level Lock on Row 101

Release the lock on row 101 by removing key 101 from the tree.

💡 Releasing locks is essential to allow other transactions to proceed.

Line:

lock_tree.delete(101)  # Release lock

💡 Lock release updates the tree to reflect available resources.

traverse

Final Lock Tree State

Traverse the final lock tree to show all current locks held after acquisitions and releases.

💡 Final state shows the net effect of all locking operations.

Line:

lock_tree.traverse()  # Show final locks

💡 The final tree reflects the current lock state, useful for debugging and concurrency control.

class Node:
    def __init__(self, id, keys=None, children=None, is_leaf=True, parent=None):
        self.id = id
        self.keys = keys or []
        self.children = children or []
        self.is_leaf = is_leaf
        self.parent = parent

class BTree:
    def __init__(self, order=3):
        self.order = order
        self.root = Node(1)

    def insert(self, key):
        # STEP 2-5: Insert key representing lock acquisition
        # Simplified insert logic for demonstration
        node = self.root
        if len(node.keys) < self.order - 1:
            node.keys.append(key)  # STEP 2-3
            node.keys.sort()
        else:
            # STEP 4: Node split
            self.split(node, key)

    def split(self, node, key):
        # STEP 4: Split node and promote middle key
        keys = node.keys + [key]
        keys.sort()
        mid = len(keys) // 2
        left_keys = keys[:mid]
        right_keys = keys[mid+1:]
        promoted = keys[mid]

        node.keys = [promoted]
        node.is_leaf = False
        left_node = Node(id=2, keys=left_keys, is_leaf=True, parent=node.id)
        right_node = Node(id=3, keys=right_keys, is_leaf=True, parent=node.id)
        node.children = [left_node.id, right_node.id]

    def contains(self, key):
        # STEP 6-7: Check if key exists
        return key in self.root.keys

    def delete(self, key):
        # STEP 9: Remove key representing lock release
        if key in self.root.keys:
            self.root.keys.remove(key)

    def traverse(self):
        # STEP 10: Return all keys
        return self.root.keys

📊

Database Locks - Row-Level, Table-Level, Optimistic vs Pessimistic - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization helps you understand the dynamic behavior of database locks and their interactions, which is difficult to grasp from static code or text alone.

setup

leaf

Starting with an empty lock tree representing no locks held.

insertKey: 101

101

leaf

Acquired row-level lock on row 101 by inserting key 101.

insertKey: 102

101102

leaf

Acquired row-level lock on row 102 by inserting key 102.

splitKey: 103↑ promoted: 102

102

101

leaf

103

leaf

Leaf node split after inserting key 103; promoted key 102 to root.

insertKey: TABLE_LOCK

TABLE_LOCK

leaf

Escalated locks to table-level by inserting 'TABLE_LOCK' key.

compareKey: 104

TABLE_LOCK

leaf

Checked for optimistic lock on row 104; no conflict found.

compareKey: 105

TABLE_LOCK

leaf

Optimistic lock on row 105 failed due to existing table-level lock.

insertKey: 105

TABLE_LOCK105

leaf

Acquired pessimistic lock on row 105 by inserting key 105.

deleteKey: 101

TABLE_LOCK105

leaf

Released row-level lock on row 101 by deleting key 101.

traverse

TABLE_LOCK105

leaf

Final lock tree state showing table-level lock and pessimistic lock on row 105.

Key Takeaways

✓ Lock escalation from row-level to table-level reduces overhead by consolidating many locks into one.

This is hard to see from code alone because the dynamic restructuring of locks is abstracted away.

✓ Optimistic locking attempts to avoid blocking by checking conflicts before acquiring locks.

Visualizing the conflict detection step clarifies why optimistic locking can fail and fallback is needed.

✓ Pessimistic locking guarantees exclusive access by blocking conflicting transactions, represented as keys in the tree.

Seeing the lock keys inserted and removed helps understand how locks control concurrency.

Practice

1. You have a large table frequently queried by range conditions on a date column and occasionally updated. Which indexing strategy is most appropriate to optimize query performance?

easy

A. Use a clustered index on the date column to store rows physically sorted by date.

B. Use a non-clustered index on the date column to avoid physical reordering on updates.

C. Use no index and rely on full table scans since updates are frequent.

D. Use a clustered index on a unique ID column and a non-clustered index on the date column.

Solution

1. Step 1: Understand query pattern for range scans on date

   Range queries on the date column benefit from data physically sorted by date, enabling efficient range scans.

2. Step 2: Consider clustered index effect on physical ordering

   A clustered index stores rows physically ordered by the indexed column, making range queries faster.

3. Step 3: Evaluate update impact tradeoff

   Although updates cause some overhead due to physical reordering, occasional updates are an acceptable tradeoff for query speed.

4. Step 4: Analyze other options

   Non-clustered index avoids physical reordering but range queries require extra lookups; no index leads to slow scans; clustered on unique ID doesn't optimize date range queries.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Range queries -> clustered index on date column [OK]

Hint: Range queries -> clustered index on that column [OK]

Common Mistakes:

• Assuming non-clustered index always better for updates
• Ignoring physical data order benefits for range queries
• Believing no index is better if updates exist

2. Given the following Python code simulating a JOIN to find customers with orders, what is the output of the print statement?

easy

A. ['Alice', 'Bob', 'Charlie']

B. ['Bob', 'Charlie']

C. ['Alice']

D. ['Alice', 'Bob']

Solution

1. Step 1: Trace order_customer_ids set

   Extract customer IDs from orders: {1, 2}.

2. Step 2: Filter customers by IDs in order_customer_ids

   Customers with id 1 and 2 are Alice and Bob; Charlie (id 3) is excluded.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Only Alice and Bob have orders, matching output [OK]

Hint: Set membership filters customers with orders correctly [OK]

Common Mistakes:

• Including customers without orders
• Off-by-one errors in filtering
• Confusing customer IDs with order IDs

3. Which of the following statements about the trade-offs of clustered indexes is TRUE?

medium

A. Clustered indexes always improve insert performance because data is stored sequentially.

B. Clustered indexes can degrade update performance if the indexed column changes frequently due to physical row movement.

C. Clustered indexes reduce storage space because they eliminate the need for separate index structures.

D. Clustered indexes are ideal for columns with high cardinality and random access patterns.

Solution

1. Step 1: Analyze insert performance claim

   Clustered indexes may slow inserts if rows must be inserted in the middle, causing page splits.

2. Step 2: Evaluate storage space claim

   Clustered indexes do not eliminate index structures; non-clustered indexes still exist and clustered index is part of data storage.

3. Step 3: Understand update impact

   Updating clustered index key causes physical row movement, which can degrade performance.

4. Step 4: Assess suitability for high cardinality random access

   Clustered indexes are less beneficial for random access on high cardinality columns; non-clustered indexes often better.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Frequent updates on clustered key -> performance hit due to physical row moves [OK]

Hint: Clustered index updates on key -> physical row moves -> slower updates [OK]

Common Mistakes:

• Assuming clustered indexes always speed inserts
• Believing clustered indexes save storage by removing indexes
• Thinking clustered indexes are best for random access on high cardinality columns

4. What is the time complexity of using a correlated subquery with EXISTS to find all customers who have orders, assuming n customers and m orders?

medium

A. O(n * m) because for each customer the orders table is scanned

B. O(n + m) because each table is scanned once

C. O(m) because only orders are scanned

D. O(n log m) because of index lookups on orders

Solution

1. Step 1: Understand correlated subquery execution

   For each of the n customers, the subquery scans orders (m rows) to check existence.

2. Step 2: Calculate total complexity

   This leads to O(n * m) time complexity, as the orders table is scanned repeatedly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Repeated scans cause multiplicative complexity [OK]

Hint: Correlated subqueries scan inner table per outer row [OK]

Common Mistakes:

• Assuming single scan of orders
• Confusing correlated with non-correlated subqueries
• Ignoring repeated scans in correlated subqueries

5. What is a common trade-off or limitation of using strict Two-Phase Locking (2PL) in high-concurrency database systems?

medium

A. Strict 2PL can cause increased waiting and deadlocks, reducing concurrency

B. Strict 2PL eliminates deadlocks entirely, improving throughput

C. Strict 2PL allows transactions to release locks early, improving performance

D. Strict 2PL requires no lock compatibility checks, simplifying implementation

Solution

1. Step 1: Understand strict 2PL behavior

   Strict 2PL holds exclusive locks until commit, which can increase waiting times.

2. Step 2: Analyze deadlock potential

   Because locks are held longer, deadlocks can occur more frequently, reducing concurrency.

3. Step 3: Evaluate options

   B is incorrect; strict 2PL does not eliminate deadlocks. C is incorrect; locks are not released early. D is wrong; lock compatibility checks are essential. A correctly identifies the trade-off.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Strict 2PL trades off concurrency for serializability, increasing deadlock risk.

Hint: Strict 2PL trades concurrency for serializability, risking deadlocks [OK]

Common Mistakes:

• Believing strict 2PL prevents deadlocks
• Thinking locks can be released early in strict 2PL
• Ignoring lock compatibility checks