Garbage collection doesn't recycle tuple slots or clean indexes in all scenarios

[mbutrovich]

David and I completed our first comprehensive evaluation of the garbage collector. Based on the test suite we wrote here, we've identified the following tuple-related problem scenarios:

1. Primary key constraint violation (FailedInsertPrimaryKeyTest)

• Insert tuple (0,0), commit
• Insert tuple (0,1), commit (primary index abort due to non-unique primary key)
• Aborted insert still occupies a tuple slot in the table

2. Secondary index constraint violation (FailedInsertSecondaryKeyTest)

• Insert tuple (0,1), commit
• Insert tuple (1,1), commit (secondary index abort due to non-unique value)
• Aborted insert still occupies a tuple slot in the table

3. Committed update (CommitUpdateSecondaryKeyTest)

• Insert tuple (5,1), commit
• Update tuple to (5,2), commit
• Old version still present in secondary index

4. Aborted update (AbortUpdateSecondaryKeyTest)

• Insert tuple (0,1), commit
• Update tuple to (0,2), abort
• New version still present in secondary index

5. Insert and update in same transaction, commit (CommitInsertUpdateTest)

• Insert tuple (0,1), update to (0,2), commit
• Old version present in both indexes, new version only present in one

6. Insert and update in same transaction, abort (AbortInsertUpdateTest)

• Insert tuple (0,1), update to (0,2), abort
• Old version present in one index

7. Delete doesn't recycle tombstone, pollutes index (CommitDeleteTest)

• Insert tuple (0,1), commit
• Delete tuple (0,1), commit
• Number of recycled slots only 1 (tombstone still in table)
• Deleted tuple still present in both indexes

8. Update and delete in same transaction, commit (CommitUpdateDeleteTest)

• Insert tuple (0,1), commit
• Update to (0,2), delete, commit
• Number of recycled slots only 1
• Both versions of tuple present in both indexes

9. Update and delete in same transaction, abort (AbortUpdateDeleteTest)

• Insert tuple (0,1), commit
• Update to (0,2), delete, abort
• Aborted update present in both indexes

10. Update primary key (CommitUpdatePrimaryKeyTest)

• Insert tuple (3, 30), commit
• Update to (5, 40), commit
• Number of recycled slots only 1 (expect 2 due to delete, insert of PK update process)
• Old version present in both indexes