CMU 15445 Project 4

Garbage Collection

The following example comes from the test case TxnExecutorTest_GarbageCollection:

Before the first garbage collection,

• When txn_watermark_at_0 is not committed, the watermark is 1.
• When txn_watermark_at_0 is committed, the watermark changes to 7, i.e. the earlist running transaction is txn_watermark_at_1. At this time, for the first tuple in the table heap, txn_watermark_at_1 should read the undo log chain to ts=4.
• When txn_watermark_at_1 is committed, the watermark changes to 12, i.e. the earlist running transaction is txn_watermark_at_2. At this time, for the first tuple in the table heap, txn_watermark_at_2 should read the undo log chain to ts=10. Hence, the tuple at 'ts=4' is eligible for deletion. For the third tuple in the table heap, transaction txn_watermark_at_2 should only read the tuple at 'ts=10'. Hence, the tuple at 'ts=5' is eligible for deletion. Therefore, we could know all undo logs in txn2 should be removed and txn2 also need be removed from txn_map_ when GarbageCollection is invoked.
• When txn_watermark_at_2 is committed, the watermark changes to 17, i.e. the earlist running transaction is txn_watermark_at_3. At this time, txn_watermark_at_3 do not traverse the undo log chain. Hence, txn3 should be removed from txn_map_ when GarbageCollection is invoked.