Undo Phase - Learning Module

Loading content...

0/241

Nested Rollback

When Simple Undo Isn't Enough

So far, we've treated transactions as monolithic units: either all their changes commit, or all their changes are rolled back. But real-world transactions are often more complex. Applications use savepoints to create rollback points within a transaction, allowing partial undo while keeping earlier work intact.

Consider an e-commerce checkout:

Reserve inventory items
SAVEPOINT 'after_reserve'
Attempt payment processing
If payment fails: ROLLBACK TO SAVEPOINT 'after_reserve' (keep reservation, retry payment)
If payment succeeds: COMMIT

This introduces nested rollback—the ability to undo part of a transaction while preserving other parts. How does ARIES handle this complexity during recovery?

What You Will Learn

By the end of this page, you will understand how savepoints create rollback boundaries, how CLRs handle partial rollbacks during normal operation, how the undo phase processes transactions with savepoint history, and the interaction between nested rollback and recovery.

Understanding Savepoints

A savepoint is a named marker within a transaction that allows partial rollback. When you create a savepoint, the system records the current position in the transaction's log chain. Later, you can rollback to that savepoint, undoing all changes made after it while preserving changes before it.

Savepoint Operations:

SAVEPOINT name: Create a marker at the current point
ROLLBACK TO SAVEPOINT name: Undo all changes after the savepoint
RELEASE SAVEPOINT name: Discard the savepoint (changes become permanent within txn)

What Savepoints Do NOT Do:

Savepoints do not commit anything—the entire transaction can still be rolled back
Releasing a savepoint doesn't persist data—only COMMIT does that
Savepoints are internal to one transaction—they can't span transactions

savepoint_example.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
-- Example: E-commerce checkout with savepoints
 
BEGIN TRANSACTION;
 
-- Phase 1: Reserve inventory
UPDATE inventory SET reserved = reserved + 1 
WHERE product_id = 101 AND available > 0;
 
UPDATE inventory SET reserved = reserved + 1 
WHERE product_id = 102 AND available > 0;
 
-- Create savepoint after successful reservation
SAVEPOINT after_inventory;
 
-- Phase 2: Process payment (might fail)
INSERT INTO payment_attempts (order_id, amount, status)
VALUES (5001, 299.99, 'pending');
 
-- Simulate payment processing
-- If payment gateway returns failure...
 
-- Rollback just the payment, keep inventory reserved
ROLLBACK TO SAVEPOINT after_inventory;
 
-- Retry with different payment method
INSERT INTO payment_attempts (order_id, amount, status)
VALUES (5001, 299.99, 'pending');
 
-- This time payment succeeds
UPDATE payment_attempts SET status = 'success' 
WHERE order_id = 5001;
 
-- Complete the transaction
COMMIT;
 
-- Result: Inventory reserved, payment recorded, order complete
-- If we had done full ROLLBACK, we'd lose the inventory reservation

Log Structure with Savepoints:

When a savepoint is created, a SAVEPOINT log record is written. When rolling back to a savepoint, CLRs are written for each undone operation, and the rollback stops at the savepoint marker.

LSN	Record Type	Description
100	UPDATE	Reserve product 101
200	UPDATE	Reserve product 102
300	SAVEPOINT	'after_inventory' (saveLSN=200)
400	INSERT	Payment attempt
500	CLR	Undoing LSN 400 (rollback to savepoint)
600	INSERT	Second payment attempt
700	UPDATE	Mark payment success
800	COMMIT	Transaction complete

Savepoint Log Records

The SAVEPOINT log record typically stores: the savepoint name, the current lastLSN for the transaction (the 'saveLSN'), and possibly lock information needed to restore lock state if rolling back. The saveLSN is crucial—it tells the rollback where to stop.

Rollback to Savepoint Mechanism

When an application issues ROLLBACK TO SAVEPOINT, the database performs a partial undo that's conceptually similar to the recovery undo phase—but it operates on a running transaction rather than during crash recovery.

The Process:

Find the savepoint record in the log (using savepoint name lookup)
Get the saveLSN from that record (the LSN before the savepoint)
Walk backward through the transaction's log chain from lastLSN
Undo each update record, writing CLRs as we go
Stop when we reach the saveLSN (or pass it)
Update the transaction's lastLSN to the latest CLR
Continue normal transaction processing

rollback_to_savepoint.pseudo

Rollback to Savepoint Algorithm

PROCEDURE RollbackToSavepoint(txn, savepointName):
    // Step 1: Find the savepoint record
    savepoint = txn.FindSavepoint(savepointName)
    IF savepoint == NULL:
        RAISE "Savepoint not found: " + savepointName
    
    saveLSN = savepoint.saveLSN  // LSN to stop at
    
    // Step 2: Start from transaction's current position
    currentLSN = txn.lastLSN
    
    Log.Debug("Rolling back from LSN {currentLSN} to savepoint at {saveLSN}")
    
    // Step 3: Walk backward, undoing updates
    WHILE currentLSN > saveLSN:
        logRecord = Log.Read(currentLSN)
        
        IF logRecord.type == UPDATE:
            // Undo this update
            page = BufferPool.Fetch(logRecord.pageId)
            page.ApplyBeforeImage(logRecord.beforeImage)
            
            // Write CLR with undoNextLSN pointing past this record
            clr = WriteCLR(
                transactionId: txn.id,
                pageId: logRecord.pageId,
                redoInfo: logRecord.beforeImage,
                undoNextLSN: logRecord.prevLSN,
                undoLSN: currentLSN
            )
            
            page.SetPageLSN(clr.lsn)
            txn.lastLSN = clr.lsn
            
            // Move to previous record
            currentLSN = logRecord.prevLSN
            
        ELSE IF logRecord.type == CLR:
            // A CLR from a previous partial rollback
            currentLSN = logRecord.undoNextLSN
            
        ELSE IF logRecord.type == SAVEPOINT:
            // We've reached or passed a savepoint record
            // If this is our target savepoint, stop; otherwise continue
            IF logRecord.lsn <= saveLSN:
                BREAK
            currentLSN = logRecord.prevLSN
            
        ELSE:
            // Other record types (like inner savepoints)
            currentLSN = logRecord.prevLSN
    
    // Step 4: Update transaction state
    txn.undoNextLSN = saveLSN  // For recovery purposes
    
    // Step 5: Optionally release locks acquired after savepoint
    IF config.RELEASE_LOCKS_ON_PARTIAL_ROLLBACK:
        txn.ReleaseLocksSince(saveLSN)
    
    Log.Info("Rollback to savepoint '{savepointName}' complete")

Key Observations:

CLRs are written just like full abort: The partial undo creates CLR records that document each undone operation.
The transaction continues: Unlike a full abort, the transaction remains active and can make more updates after the rollback to savepoint.
Chain navigation is the same: We follow PrevLSN pointers, skip CLRs using undoNextLSN, just like recovery undo.
Stop condition differs: Instead of reaching BEGIN, we stop when passing the saveLSN.

Lock Handling

Strict 2PL normally holds all locks until commit. Rollback to savepoint can optionally release locks acquired after the savepoint, allowing other transactions to access those resources. However, this is implementation-specific—some systems keep the locks to avoid cascading issues.

Nested Savepoints

Savepoints can be nested—you can create multiple savepoints at different points within a transaction. When rolling back, you can choose which savepoint to target, rolling back to any previously established point.

Example: Multiple Savepoints

Converting Mermaid diagram...

Nested Rollback Behavior:

Rollback Target	What Gets Undone	Transaction State After
ROLLBACK TO C	U6 only	At savepoint C position
ROLLBACK TO B	U4, U5, U6	At savepoint B position
ROLLBACK TO A	U2 through U6	At savepoint A position
ROLLBACK (full)	Everything	Transaction aborted

Nested Savepoint Considerations:

Rolling back destroys inner savepoints: If you ROLLBACK TO A, savepoints B and C are invalidated—the work they marked is now gone.
Savepoint names can be reused: After rolling back, you can create a new savepoint with the same name at the current position.
Stack-like behavior: Savepoints are often managed as a stack. RELEASE SAVEPOINT pops the top savepoint; ROLLBACK TO pops back to a named point.

nested_savepoints.sql
SQL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
-- Example: Nested savepoints for complex operation
 
BEGIN TRANSACTION;
 
-- Phase 1: Setup
INSERT INTO orders (id, customer) VALUES (1001, 'Alice');
SAVEPOINT phase1_complete;
 
-- Phase 2: Add items (with sub-savepoints)
INSERT INTO order_items (order_id, product) VALUES (1001, 'Widget');
SAVEPOINT item1_added;
 
INSERT INTO order_items (order_id, product) VALUES (1001, 'Gadget');
SAVEPOINT item2_added;
 
INSERT INTO order_items (order_id, product) VALUES (1001, 'Gizmo');
-- Oops, Gizmo is out of stock!
 
ROLLBACK TO SAVEPOINT item2_added;  -- Remove just Gizmo
 
-- Continue with shipping
UPDATE orders SET status = 'shipping' WHERE id = 1001;
SAVEPOINT ready_to_ship;
 
-- Payment attempt fails
-- ROLLBACK TO SAVEPOINT phase1_complete would remove all items!
-- Instead, just cancel shipping:
ROLLBACK TO SAVEPOINT item2_added;
 
-- Fix and retry
UPDATE orders SET status = 'payment_pending' WHERE id = 1001;
 
COMMIT;  -- Order created with 2 items, status is payment_pending

Savepoint Scope

After ROLLBACK TO a savepoint, any savepoints created after it no longer exist. The log records for those savepoints are still in the log, but they're logically invalidated. Attempting to reference a destroyed savepoint will fail.

Recovery with Savepoint History

When a crash occurs, the undo phase must handle transactions that have savepoint history—including partial rollbacks that created CLRs. The good news: ARIES already handles this correctly through its standard CLR processing.

Scenario: Crash After Partial Rollback

Consider this sequence:

Transaction T1 makes updates at LSN 100, 200, 300, 400
T1 creates savepoint at LSN 250 (saveLSN = 200)
T1 rolls back to savepoint → CLRs at 500 (undo 400), 600 (undo 300)
T1 makes new update at LSN 700
CRASH (T1 hasn't committed)

Log State at Crash Time
LSN	Type	PrevLSN	UndoNextLSN	Description
100	UPDATE	null		T1's first update
200	UPDATE	100		T1's second update
250	SAVEPOINT	200		Savepoint 'X' (saveLSN=200)
300	UPDATE	250		T1's third update
400	UPDATE	300		T1's fourth update
500	CLR	400	300	Undid LSN 400
600	CLR	500	200	Undid LSN 300 (hit savepoint)
700	UPDATE	600		T1's new update after savepoint rollback
—	CRASH	—	—	System crash here

Recovery Processing:

Analysis Phase: T1 is in ACTIVE state, lastLSN = 700, undoNextLSN = 700
Redo Phase: Replays all records including CLRs 500 and 600. After redo:
- Updates 100, 200 are applied
- Updates 300, 400 are applied, then CLRs 500, 600 reverse them
- Update 700 is applied
- Net effect: Updates 100, 200, 700 are active
Undo Phase:
- Start with ToUndo = {700 → T1}
- Undo 700 → write CLR (undoNextLSN = 600)
- Next LSN is 600 (a CLR), follow undoNextLSN = 200
- Undo 200 → write CLR (undoNextLSN = 100)
- Undo 100 → write CLR (undoNextLSN = null)
- T1 fully undone → write END

The Key Insight: CLRs from the previous partial rollback automatically guide the undo phase to skip LSNs 300 and 400. The CLR chain "remembers" that those updates were already undone!

recovery_with_savepoints.pseudo

Undo Phase Trace

// Trace of undo phase processing for the scenario above
 
UNDO PHASE:
ToUndo initialized: {700 → T1}
 
Step 1:
  Extract max: (700, T1)
  Read LSN 700: UPDATE, prevLSN=600
  → Undo update 700
  → Write CLR@800 (undoNextLSN=600)
  → Update ToUndo: {600 → T1}
 
Step 2:
  Extract max: (600, T1)
  Read LSN 600: CLR, undoNextLSN=200
  → It's a CLR, don't undo it!
  → Follow undoNextLSN to 200
  → Update ToUndo: {200 → T1}
  
  // Notice: We skipped LSNs 500, 400, 300, 250 entirely!
  // The CLR chain from the partial rollback guides us.
 
Step 3:
  Extract max: (200, T1)
  Read LSN 200: UPDATE, prevLSN=100
  → Undo update 200
  → Write CLR@801 (undoNextLSN=100)
  → Update ToUndo: {100 → T1}
 
Step 4:
  Extract max: (100, T1)
  Read LSN 100: UPDATE, prevLSN=null
  → Undo update 100
  → Write CLR@802 (undoNextLSN=null)
  → prevLSN is NULL, T1 fully undone
  → Write END@803
  → Remove T1 from ToUndo
 
ToUndo is empty → Undo complete!
 
Final state: All of T1's effects have been removed.

Automatic Handling

ARIES doesn't need special logic for savepoints during recovery! The CLR chain from partial rollbacks naturally encodes what was already undone. Recovery simply follows CLR undoNextLSN pointers like any other CLR, and everything works correctly.

Subtransactions and Nested Transactions

Some database systems support subtransactions or nested transactions, which provide stronger semantics than savepoints. While savepoints are just rollback markers, subtransactions can have their own commit/abort status.

Savepoints vs Subtransactions:

Feature	Savepoints	Subtransactions
Rollback granularity	To any named point	Individual subtransaction
Commit semantics	Only parent commits	Subtransaction can "commit" (results visible to parent)
Abort semantics	Rolls back work	Subtransaction aborts, parent continues
Duration	Until rollback or end	Until subtransaction commits/aborts
Lock handling	Implementation-specific	Subtransaction may hold/release locks

How Subtransactions Affect Recovery:

Subtransactions introduce independent units within a parent transaction. Each subtransaction has its own:

Begin record
Log chain (via PrevLSN within the subtransaction)
Potentially its own savepoints
Commit or abort record

subtransaction_concept.pseudo

Subtransaction Model

-- Conceptual example (not standard SQL)
-- Some systems support this via nested transaction syntax
 
BEGIN TRANSACTION T1;
    
    INSERT INTO log VALUES ('T1 started');
    
    BEGIN SUBTRANSACTION S1;
        INSERT INTO audit VALUES ('S1 attempt');
        -- S1 work here
        IF [condition]:
            COMMIT SUBTRANSACTION S1;  -- S1 results survive if T1 commits
        ELSE:
            ABORT SUBTRANSACTION S1;   -- S1 results discarded, T1 continues
    END SUBTRANSACTION;
    
    -- T1 continues regardless of S1 outcome
    INSERT INTO log VALUES ('After S1');
    
    BEGIN SUBTRANSACTION S2;
        -- More work
        COMMIT SUBTRANSACTION S2;
    END SUBTRANSACTION;
    
COMMIT TRANSACTION T1;  -- All committed subtransactions become durable
 
-- If T1 aborts instead, all subtransaction work is lost
-- even if the subtransactions individually "committed"

Recovery Implications:

Subtransaction commit is provisional: A subtransaction's commit is only durable if the parent transaction commits. If the parent aborts, all subtransaction work is undone.
Undo must track hierarchy: The undo phase needs to understand parent-child relationships:
- If parent is loser, undo all children regardless of their commit status
- If child aborted before crash, its work is already undone via CLRs
Log structure becomes more complex: Each subtransaction has its own PrevLSN chain, nested within the parent's chain.

ARIES Support:

Standard ARIES handles savepoints naturally but needs extensions for full nested transactions. Extensions include:

Hierarchical transaction IDs (T1.S1, T1.S2, etc.)
Modified commit protocol (subtransaction commit logs don't force)
Parent-child relationship tracking in transaction table

Implementation Varies

Most production databases (PostgreSQL, Oracle, SQL Server) support savepoints extensively but have limited or no nested transaction support. Full nested transactions are more common in research systems and specialized domains like long-lived transactions.

Complex Rollback Scenarios

Let's examine some complex scenarios that combine savepoints, partial rollbacks, and crash recovery to solidify our understanding.

Scenario 1: Multiple Partial Rollbacks Before Crash

complex_scenario_1.pseudo

Multiple Partial Rollbacks

TIMELINE:
 
LSN 100: BEGIN T1
LSN 200: UPDATE P1 (A→B)
LSN 300: SAVEPOINT X (saveLSN=200)
LSN 400: UPDATE P2 (M→N)
LSN 500: SAVEPOINT Y (saveLSN=400)
LSN 600: UPDATE P3 (X→Y)
LSN 700: ROLLBACK TO Y → CLR@700 (undo 600, undoNextLSN=400)
LSN 800: UPDATE P4 (J→K)
LSN 900: ROLLBACK TO X → CLR@900 (undo 800, undoNextLSN=700)
                             CLR@901 is NOT written because we hit 700 which points to 400
                             Actually, we need to undo 700's work...wait, CLR@700 isn't undone!
                             CLR@900 (undo 800, undoNextLSN=700)
                             Follow 700 (CLR) → undoNextLSN=400
                             CLR@901 (undo 400, undoNextLSN=300)
                             Hit savepoint X at 300, stop.
LSN 1000: UPDATE P5 (Q→R)
--- CRASH ---
 
RECOVERY:
- Analysis sees T1 active, lastLSN=1000
- Redo replays all records
- Undo starts with ToUndo = {1000}
 
Trace:
  Undo 1000 → CLR@1100 (undoNextLSN=901)
  Read 901 (CLR) → undoNextLSN=300
  Read 300 (SAVEPOINT) → prevLSN=200
  Undo 200 → CLR@1101 (undoNextLSN=100)
  Read 100 (BEGIN) → T1 complete, write END

Wait, the above scenario has an error in reasoning. Let me correct it:

Corrected Scenario 1 Analysis:

When rolling back to savepoint X (at LSN 300, saveLSN=200), we undo:

LSN 800 (update P4) → CLR with undoNextLSN pointing to 700
LSN 700 is a CLR → follow its undoNextLSN = 400 (but wait, we need to check where 400 is relative to savepoint)
LSN 400 > saveLSN (200), so undo 400 → CLR with undoNextLSN pointing to 300 (the savepoint record)
LSN 300 is SAVEPOINT with saveLSN=200, we've reached the target

The CLR chain correctly encodes this. During recovery, following the CLR pointers skips precisely the right records.

Scenario 1: Log State After Multiple Rollbacks
LSN	Type	What It Represents	Part of Active Transaction?
100	BEGIN	T1 started	✓
200	UPDATE	P1: A→B	✓ (not rolled back)
300	SAVEPOINT X	Marker	✓
400	UPDATE	P2: M→N	✗ (rolled back to X)
500	SAVEPOINT Y	Marker (invalidated)	✗
600	UPDATE	P3: X→Y	✗ (rolled back to Y, then X)
700	CLR	Undo of 600	✓
800	UPDATE	P4: J→K	✗ (rolled back to X)
900-901	CLRs	Undo of 800, 400	✓
1000	UPDATE	P5: Q→R	✓ (not rolled back before crash)

Tracing Through Complex Scenarios

When analyzing complex scenarios, trace the PrevLSN and undoNextLSN chains carefully. Draw the chains on paper if needed. The key insight is that CLR undoNextLSN pointers create 'shortcuts' that skip exactly the operations that were already undone by partial rollbacks.

Implementation Considerations

Implementing nested rollback support requires careful design decisions. Here are key considerations:

Savepoint Storage:

Databases need to track active savepoints for each transaction:

class Transaction {
    id: TransactionId
    status: ACTIVE | COMMITTING | ABORTING
    lastLSN: LogSequenceNumber
    savepoints: Map<SavepointName, SavepointInfo>
}

class SavepointInfo {
    name: string
    saveLSN: LogSequenceNumber  // Log position at creation
    lockState?: LockSnapshot    // Optional: for lock restoration
    cursorsState?: CursorInfo   // Optional: for cursor restoration
}

Design Best Practices

•Validate savepoint names early: Check existence before starting rollback
•Handle duplicate names: Define policy (error, or overwrite)
•Limit savepoint count: Prevent resource exhaustion attacks
•Clean up on commit/abort: Release savepoint metadata
•Log savepoint records: Enable recovery of savepoint state if needed

Common Pitfalls

•Forgetting to invalidate nested savepoints: After rollback, inner savepoints are gone
•Lock state mismatch: Releasing wrong locks during partial rollback
•Recovery ignoring savepoints: Savepoint log records must be parsed correctly
•Memory leaks: Not freeing savepoint metadata on transaction end
•Incorrect CLR undoNextLSN: Must point past the undone record, not to it

Performance Implications:

Savepoint overhead is minimal: Creating a savepoint is just logging a record and updating in-memory state.
Rollback cost depends on work to undo: More updates after the savepoint = more CLRs = more time.
Recovery doesn't pay extra: The undo phase processes CLRs the same way whether they came from partial rollbacks or full recovery.

SQL Standard Compliance:

SQL:1999 defined savepoint semantics. Key requirements:

SAVEPOINT savepointname
ROLLBACK TO SAVEPOINT savepointname
RELEASE SAVEPOINT savepointname

Most databases implement these, though details (like lock behavior) vary.

Testing Nested Rollback

Nested rollback is notoriously tricky to test. Create test cases for: multiple savepoints with interleaved rollbacks, crashes at various points during partial rollback, very long transactions with many savepoints, and savepoint at exact page boundaries in the log.

Summary: Nested Rollback

Nested rollback adds flexibility to transaction processing, allowing applications to implement sophisticated error handling and retry logic. The ARIES recovery system handles this elegantly through its CLR mechanism. Let's consolidate the key insights:

Key Takeaways

•Savepoints create rollback boundaries — Applications can undo partial work while preserving earlier progress within the same transaction.
•Partial rollback writes CLRs — Rolling back to a savepoint uses the same CLR mechanism as full transaction abort.
•CLR chains encode partial rollback history — The undoNextLSN pointers skip records that were already undone.
•Recovery is automatic — ARIES doesn't need special logic; following CLR chains during undo correctly handles savepoint history.
•Nested savepoints work recursively — Rolling back invalidates inner savepoints; CLR chains remain correct.
•Subtransactions extend the model — Full nested transactions add hierarchical commit semantics, requiring extended ARIES support.
•Implementation requires careful design — Savepoint metadata, lock handling, and CLR generation must work together correctly.

What's Next:

With nested rollback understood, we're ready to explore the completion of the undo phase. The next page covers how ARIES determines when undo is complete, writes END records, prepares for normal operation, and handles any final cleanup tasks.

Page Complete

You now understand nested rollback—how savepoints work, how partial rollbacks create CLR chains, and how recovery automatically handles transactions with savepoint history. The elegance of ARIES is that complex nested rollback scenarios are handled by the same CLR processing that handles simple transaction abort.