Database garbage collector

• US 7,849,110 B2
• Filed: 12/30/2006
• Issued: 12/07/2010
• Est. Priority Date: 12/30/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Garstecki, Lutz, Rossmann, Albert P.
• Primary Examiner(s): LeRoux; Etienne P
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/648,072
• Publication Number:
  US 20080162610A1
• Time in Patent Office: 1,438 Days
• Field of Search: None
• US Class Current: 707/813
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 16/24562 Pointer or reference processing operations

Abstract

A database garbage collector that removes appropriate database entries accessed during a recent transaction.

Claims

1. A method for garbage collection of a database, the method, comprising:

beginning a first transaction having a transaction context;

determining one or more creation contexts that belong to the transaction context, wherein the one or more creation contexts include objects accessed during the first transaction;

locking the one or more creation contexts for the transaction context in response to the determining;

updating a respective entry in a reference table for each object of the one or more locked creation contexts in the transaction context, each entry indicating any references to and from the object relative to other objects from the one or more locked creation contexts;

committing the first transaction;

responsive to committing the first transaction;

checking the reference table only for entries belonging to the first transaction context to determine for each such entry whether there are any references to the corresponding object from the other objects;

deleting from the reference table any checked entry belonging to the first transaction context for which there is no reference to the corresponding object from the other objects; and

reclaiming storage space, in the database associated with the corresponding object of the deleted entry.

2. The method of claim 1, further comprising, responsive to committing the first transaction, marking as “

to-delete”

from the reference table any entry corresponding to an object referenced by the deleted entry, wherein the deleted entry belonged to the object of the first transaction context, and wherein the marked entry is of an object that belongs to a creation context of a second transaction context.

3. The method of claim 2, further comprising:

beginning a second transaction having the second transaction context;

determining one or more creation contexts that belong to the second transaction context, wherein the one or more creation contexts include objects accessed during the second transaction;

locking the one or more creation contexts for the second transaction context in response to the determining;

updating the entry in the reference table for each object belonging to the one or more locked creation contexts of the second transaction context, each entry indicating any reference to and from the object relative to other objects from the one or more locked creation contexts for the second transaction context and from other creation contexts, wherein the other creation contexts include the one or more creation contexts belonging to the first transaction;

committing the second transaction;

responsive to committing the second transaction;

checking the reference table only for entries belonging to the second transaction to determine for each such entry whether there are any references to the corresponding object from the other objects;

deleting from the reference table any checked entry belonging to the second transaction context for which there is no reference to the corresponding object from the other objects; and

deleting the entry marked as “

to-delete”

from the reference table.

7. The method of claim 3, further comprising:

reclaiming storage space in the database for objection associated with the deleted entries in the reference table.

4. An article of manufacture comprising a computer readable medium having instructions stored thereon that when executed by a machine, cause the machine to perform a method for garbage collection of a database the method comprising:

beginning a first transaction having a transaction context;

determining one or more creation contexts that belong to the transaction context, wherein the one or more creation contexts include objects accessed during the first transaction;

locking the one or more creation contexts for the transaction context in response to the determining;

updating a respective entry in a reference table for each object of the one or more locked creation contexts in the transaction context, each entry indicating any references to and from the object relative to other objects from the one or more locked creation contexts and from other creation contexts;

committing the first transaction;

responsive to committing the first transaction;

checking the reference table only for entries belonging to the first transaction context to determine for each such entry whether there are any references to the corresponding object from the other objects;

deleting from the reference table any checked entry belonging to the first transaction context for which there is no reference to the corresponding object from the other objects; and

reclaiming storage space, in the database, associated with the corresponding object of the deleted entry.

5. The article of manufacture of claim 4, further comprising instructions that when executed cause the machine to perform, responsive to committing the first transaction, marking as “

to-delete”

from the reference table any entry corresponding to an object referenced by the deleted entry, wherein the deleted entry belonged to the object of the first transaction context. and wherein the marked entry is of an object that belongs to a creation context of a second transaction context.

6. The article of manufacture of claim 5, further comprising instructions that when executed by the machine cause the machine to further perform the method comprising:

beginning a second transaction having the second transaction context;

determining one or more creation contexts that belong to the second transaction context, wherein the one or more creation contexts include objects accessed during the second transaction;

locking the one or more creation contexts for the second transaction context in response to the determining;

updating the entry in the reference table for each object belonging to the one or more locked creation contexts of the second transaction context, each entry indicating any reference to and from the object relative to other objects from the one or more locked creation contexts for the second transaction context and from other creation contexts, wherein the other creation contexts include the one or more creation contexts belonging to the first transaction;

committing the second transaction;

responsive to committing the second transaction;

checking the reference table only for entries belonging to the second transaction to determine for each such entry whether there are any references to the corresponding object from the other objects;

deleting from the reference table any checked entry belonging to the second transaction context for which there is no reference to the corresponding object from the other objects; and

deleting the entry marked as “

to-delete”

from the reference table.

8. The article of manufacture of claim 6, further comprising instructions that when executed by the machine cause the machine to further perform the method comprising:

reclaiming storage space in the database for objection associated with the deleted entries in the reference table.