MVCC - Multi-Version Concurrency Control (PostgreSQL/MySQL)

▶

Steps

setup

Initialize empty B-tree for MVCC versions

Create an empty B-tree with order 3 to store versioned keys. The root node is initialized with no keys and no children.

💡 Starting with an empty B-tree is essential to observe how versions are inserted and managed step-by-step.

Line:

b_tree = BTree(order=3)
root = b_tree.create_node(is_leaf=True)

💡 The B-tree structure is ready to store versioned keys representing different transaction versions.

insert

Insert first version of key 10 (transaction 1)

Insert versioned key 10 with transaction ID 1 into the root node. Since the root is empty, the key is added directly.

💡 Inserting the first version shows how keys are added to leaf nodes in MVCC B-tree.

Line:

b_tree.insert(key=10, tx_id=1)

💡 The B-tree leaf node now contains the first version of key 10, representing data visible to transaction 1.

insert

Insert second version of key 10 (transaction 2)

Insert a new version of key 10 with transaction ID 2. Since the key exists, the new version is added as a separate version entry.

💡 MVCC stores multiple versions of the same key to support concurrent transactions.

Line:

b_tree.insert(key=10, tx_id=2)

💡 The B-tree leaf node now holds two versions of key 10, showing how MVCC tracks multiple versions.

insert

Insert version of key 20 (transaction 1)

Insert versioned key 20 with transaction ID 1 into the root node. The key is added after existing keys.

💡 Inserting a new distinct key shows how keys are ordered in the B-tree leaf node.

Line:

b_tree.insert(key=20, tx_id=1)

💡 The leaf node now contains keys 10 (two versions) and 20 (one version), maintaining sorted order.

insert

Insert version of key 30 (transaction 3) triggers node split

Insert versioned key 30 with transaction ID 3. The root node is full, so a split is triggered to maintain B-tree properties.

💡 Node splits keep the B-tree balanced and efficient for searches and inserts.

Line:

b_tree.insert(key=30, tx_id=3)  # triggers split

💡 The root node splits into two nodes, and a key is promoted to a new root, increasing tree height.

search

Search for visible version of key 10 for transaction 2

Traverse the B-tree to find the version of key 10 visible to transaction 2, checking version timestamps.

💡 MVCC visibility rules determine which version a transaction can see based on transaction IDs.

Line:

b_tree.search(key=10, tx_id=2)

💡 The search finds the latest version of key 10 with tx_id <= 2, ensuring correct visibility.

insert

Insert version of key 15 (transaction 4) into left child

Insert versioned key 15 with transaction ID 4 into the left child node. The key fits without splitting.

💡 Inserting a new key between existing keys tests insertion into non-root leaf nodes.

Line:

b_tree.insert(key=15, tx_id=4)

💡 The left child node now contains keys 10 (two versions) and 15, maintaining sorted order.

insert

Insert version of key 17 (transaction 5) triggers split in left child

Insert versioned key 17 with transaction ID 5 into left child node. Node is full, so it splits and promotes a key to the root.

💡 Splitting child nodes maintains B-tree balance and allows more keys to be inserted.

Line:

b_tree.insert(key=17, tx_id=5)  # triggers split in child

💡 The left child splits into two nodes; key 15 is promoted to root, increasing root keys.

prune

Prune obsolete versions of key 10 (transaction 1)

Remove version of key 10 with transaction ID 1 as it is no longer visible to active transactions, freeing space.

💡 Pruning old versions is essential to keep MVCC storage efficient.

Line:

b_tree.prune(key=10, tx_id=1)

💡 The B-tree leaf node now only holds visible versions of key 10, improving performance.

traverse

Final state: B-tree with multiple versions per key

Traverse the B-tree to list all keys and their visible versions after all inserts and pruning.

💡 The final traversal shows the MVCC B-tree state with versioned keys and their visibility.

Line:

b_tree.traverse_inorder()

💡 The B-tree maintains sorted keys with multiple versions, supporting concurrent transactions efficiently.

class BTreeNode:
    def __init__(self, id, is_leaf):
        self.id = id
        self.keys = []  # list of dicts {key, tx_id}
        self.children = [None]*4  # max 4 children for order 3
        self.is_leaf = is_leaf
        self.parent = None

class BTree:
    def __init__(self, order=3):
        self.order = order
        self.nodes = {}
        self.root_id = 1
        self.nodes[self.root_id] = BTreeNode(self.root_id, True)

    def insert(self, key, tx_id):
        # STEP 2-5,7,8: Insert versioned key into B-tree
        # Simplified: insert into leaf, split if needed
        pass

    def search(self, key, tx_id):
        # STEP 6: Search for visible version
        pass

    def prune(self, key, tx_id):
        # STEP 9: Remove obsolete versions
        pass

    def traverse_inorder(self):
        # STEP 10: Traverse and list all keys
        pass

# Usage example with step comments matching visualization
b_tree = BTree(order=3)  # STEP 1
b_tree.insert(10, 1)      # STEP 2
b_tree.insert(10, 2)      # STEP 3
b_tree.insert(20, 1)      # STEP 4
b_tree.insert(30, 3)      # STEP 5
b_tree.search(10, 2)      # STEP 6
b_tree.insert(15, 4)      # STEP 7
b_tree.insert(17, 5)      # STEP 8
b_tree.prune(10, 1)       # STEP 9
b_tree.traverse_inorder() # STEP 10

📊

MVCC - Multi-Version Concurrency Control (PostgreSQL/MySQL) - Watch the Algorithm Execute, Step by Step

Watching this step-by-step visualization reveals how MVCC uses B-tree structures to maintain data consistency and isolation without locking, which is difficult to grasp from code alone.

setup

leaf

Initialized empty B-tree with root node 1.

insertKey: 10

10

leaf

Inserted versioned key 10 with transaction 1 into root node.

insertKey: 10

1010

leaf

Inserted second version of key 10 with transaction 2 into root node.

insertKey: 20

101020

leaf

Inserted versioned key 20 with transaction 1 into root node.

splitKey: 30↑ promoted: 20

20

1010

leaf

30

leaf

Root node split; key 20 promoted to new root; inserted key 30 in new right child.

searchKey: 10

20

1010

leaf

30

leaf

Searching for key 10 visible to transaction 2; found version with tx_id 2.

insertKey: 15

20

101015

leaf

30

leaf

Inserted versioned key 15 with transaction 4 into left child node.

splitKey: 17↑ promoted: 15

1520

1010

leaf

30

leaf

17

leaf

Left child node split; key 15 promoted to root; inserted key 17 in new node.

pruneKey: 10

1520

10

leaf

30

leaf

17

leaf

Pruned obsolete version of key 10 with transaction 1 from left child node.

Key Takeaways

✓ MVCC uses B-tree nodes to store multiple versions of the same key, enabling concurrent transactions without locking.

This is hard to see from code alone because version management is embedded in data structures and concurrency logic.

✓ Node splits and key promotions maintain B-tree balance while accommodating new versions and keys.

Visualizing splits clarifies how the tree grows and remains efficient under concurrent version inserts.

✓ Pruning obsolete versions safely frees space without affecting active transactions' visibility.

Understanding pruning requires seeing which versions remain visible and which can be removed, which is clearer visually.

Practice

1. Trace the sequence of steps the query optimizer takes when generating an explain plan for a query with a filter predicate on a large table. What happens to the cardinality estimate after applying the filter?

easy

A. The optimizer first estimates the total rows, then reduces cardinality based on filter selectivity before choosing access paths

B. The optimizer ignores filter predicates during cardinality estimation and applies them only at execution time

C. The optimizer assumes filter predicates reduce cardinality to zero if any predicate exists

D. The optimizer estimates cardinality after choosing the access path, not before

Solution

1. Step 1: Initial cardinality estimation

   The optimizer starts by estimating the total number of rows in the table.

2. Step 2: Apply filter selectivity

   It adjusts cardinality by applying the estimated selectivity of the filter predicate, reducing the row count.

3. Step 3: Use adjusted cardinality for access path selection

   The reduced cardinality informs the choice of index scans or full scans.

4. Step 4: Why other options are incorrect

   The optimizer ignores filter predicates during cardinality estimation and applies them only at execution time: Ignoring filters during estimation leads to poor plans.
   The optimizer assumes filter predicates reduce cardinality to zero if any predicate exists: Assuming zero cardinality is unrealistic and would discard valid plans.
   The optimizer estimates cardinality after choosing the access path, not before: Cardinality estimation precedes access path selection to guide it.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Filter predicates reduce estimated rows before access path decisions.

Hint: Filter predicates reduce cardinality estimates before access path selection.

Common Mistakes:

• Thinking filters are ignored until execution
• Assuming filters eliminate all rows
• Believing cardinality is estimated after access path choice

2. Why might using the Serializable isolation level in a high-throughput OLTP system be problematic despite its strong anomaly prevention guarantees?

medium

A. Serializable requires locking or versioning that can cause significant contention and reduce throughput

B. Serializable allows dirty reads, which can corrupt data

C. Serializable does not prevent phantom reads, so anomalies still occur

D. Serializable is the default isolation level in most databases, so it offers no advantage

Solution

1. Step 1: Understand Serializable Guarantees

   Serializable prevents all anomalies including dirty, non-repeatable, and phantom reads.

2. Step 2: Analyze Performance Impact

   To guarantee serializability, databases use strict locking or multi-version concurrency control with conflict detection, which can cause contention and reduce throughput.

3. Step 3: Evaluate Other Options

   Serializable allows dirty reads, which can corrupt data is false because Serializable prevents dirty reads. Serializable does not prevent phantom reads, so anomalies still occur is false because Serializable prevents phantom reads. Serializable is the default isolation level in most databases, so it offers no advantage is false; default levels vary.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Serializable trades off performance for correctness, which can be costly in high-throughput systems.

Hint: Serializable = safest but slowest due to locking/contention

Common Mistakes:

• Believing Serializable allows dirty reads
• Thinking phantom reads occur at Serializable
• Assuming Serializable is default everywhere

3. What is the time complexity of the SQL query using window functions to rank products within categories, assuming n sales records and m unique products?

medium

A. O(n * m) due to nested aggregation and ranking

B. O(n log n) due to sorting inside window function over all rows

C. O(m^2) because ranking requires pairwise comparisons of products

D. O(n) since aggregation and ranking are linear scans

Solution

1. Step 1: Identify operations in the query

   The query aggregates sales (O(n)) then applies window function with ORDER BY, which requires sorting.

2. Step 2: Analyze sorting cost in window function

   Sorting all rows by category and total_sales costs O(n log n), dominating the complexity.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting inside window function -> O(n log n) time [OK]

Hint: Window functions with ORDER BY require sorting -> O(n log n) [OK]

Common Mistakes:

• Assuming linear time ignoring sorting
• Confusing n and m in complexity

4. In a system that uses denormalization for performance, what is a robust strategy to handle updates to redundant data without sacrificing too much query speed?

hard

A. Use triggers or stored procedures to synchronously update all redundant copies during each write operation

B. Manually update redundant data only during off-peak hours to minimize performance impact

C. Avoid denormalization entirely and rely solely on normalized tables with optimized indexes

D. Accept eventual consistency by asynchronously propagating updates, allowing stale reads temporarily

Solution

1. Step 1: Understand update challenges in denormalization

   Synchronously updating all copies can degrade write performance and increase latency.

2. Step 2: Evaluate asynchronous update benefits

   Asynchronous propagation allows writes to complete quickly, trading immediate consistency for eventual consistency.

3. Step 3: Consider alternatives

   Avoid denormalization entirely and rely solely on normalized tables with optimized indexes avoids denormalization but sacrifices read speed. Manually update redundant data only during off-peak hours to minimize performance impact delays updates, risking long inconsistency windows.

4. Step 4: Assess triggers/stored procedures

   Use triggers or stored procedures to synchronously update all redundant copies during each write operation can cause write bottlenecks and complexity.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Eventual consistency balances performance and data freshness in denormalized systems [OK]

Hint: Eventual consistency enables fast writes with acceptable stale reads [OK]

Common Mistakes:

• Assuming synchronous updates are always best
• Ignoring the trade-off between consistency and performance
• Believing manual batch updates are practical for real-time systems

5. If a query involves highly skewed data distributions and correlated predicates, how should the query optimizer adjust its cardinality and cost estimations to avoid poor plan choices?

hard

A. Use advanced statistics like histograms and multi-column statistics to better estimate cardinality and costs

B. Ignore skew and correlations since they have minimal impact on cost estimation

C. Assume independence between predicates and use simple multiplication of selectivities for cardinality

D. Always choose a full table scan to avoid misestimation risks

Solution

1. Step 1: Recognize skew and correlation impact

   Skewed data and correlated predicates invalidate independence assumptions, causing cardinality errors.

2. Step 2: Advanced statistics usage

   Histograms and multi-column stats capture data distribution and predicate correlation, improving estimates.

3. Step 3: Why other options fail

   Assume independence between predicates and use simple multiplication of selectivities for cardinality: Multiplying selectivities assumes independence, leading to errors.
   Ignore skew and correlations since they have minimal impact on cost estimation: Ignoring skew/correlation causes poor plans.
   Always choose a full table scan to avoid misestimation risks: Full table scans are costly and not always optimal.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Advanced stats help the optimizer handle complex data distributions accurately.

Hint: Use advanced stats to handle skew and correlated predicates in cardinality estimation.

Common Mistakes:

• Assuming predicate independence always holds
• Ignoring data distribution effects on cost
• Defaulting to full scans to avoid estimation complexity