Method and system for utilizing a hierarchical bitmap structure to provide a fast and reliable mechanism to represent large deleted data sets in relational databases

• US 7,685,181 B2
• Filed: 02/26/2007
• Issued: 03/23/2010
• Est. Priority Date: 02/26/2007
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: International Business Machines Corporation
• Inventors: Malkemus, Timothy Ray, McKeough, Sean W., Kirton, Jo-anne Mona Louise, Lau, Sherman, Bhattacharjee, Bishwaranjan
• Primary Examiner(s): Jalil; Neveen Abel
• Assistant Examiner(s): PEACH, POLINA G
• Application Number:
  US11/679,076
• Publication Number:
  US 20080208802A1
• Time in Patent Office: 1,121 Days
• Field of Search: 707/206
• US Class Current: 707/813
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees

Abstract

A method and system utilizes a hierarchical bitmap structure to represent deleted data sets. Each level in the hierarchical bitmap structure may have progressively larger size and represent finer granularity of number of data blocks than its parent level. A method in one aspect may comprise allocating a first level bitmap having size equal to a register on a processor, each bit in the first level bitmap representing a plurality of blocks of data in a database, and allocating one or more pointers corresponding to said plurality of bits in the first level bitmap, said one or more pointers being allocated to point to a sub bitmap generated after a data block is deleted but before the index corresponding to the data block is cleaned.

Claims

1. A method for utilizing a hierarchical bitmap structure to represent deleted data in databases, comprising:

allocating by a processor a first level bitmap having size equal to a register on a processor, each bit in the first level bitmap representing a plurality of blocks of data in a database;

allocating by a processor a second level bitmap, said each bit in the first level bitmap corresponding to a plurality of bits in the second level bitmap;

allocating by a processor one or more pointers corresponding to said plurality of bits in the second level bitmap, said one or more pointers being allocated to point to a sub bitmap generated after a data block is deleted but before the index corresponding to the data block is cleaned;

each of the levels in the hierarchical bitmap structure being of size which fits in a corresponding level of memory hierarchy associated with a machine running the processor; and

each bit in the first level bitmap representing x/n blocks of data, wherein x is total number of blocks and n is the size of the first level bitmap, and wherein m number of sub bitmaps can be generated, each sub bitmap size equal to round((x/m)+0.5) bits;

allocating a temporary hierarchical bitmap structure corresponding to one or more local data deletes; and

merging the temporary hierarchical bitmap structure with a master hierarchical bitmap structure.

2. The method of claim 1, wherein a bit in the first level bitmap is turned on if any one of the plurality of blocks of data the bit represents is deleted.

3. The method of claim 1, further including:

querying whether a data block was deleted by determining whether a bit in the first level bitmap that represents the data block is turned on, and if the bit is not turned on, determining that the data block is not deleted;

in response to the bit in the first level bitmap that represents the data block being turned on, evaluating a bit in the second level bitmap that represents the data block;

in response to the bit in the second level bitmap not being turned on, determining that the data block is not deleted;

in response to the bit in the second level bitmap that represents the data block being turned on, repeating the evaluating step with a next level bitmap if the next level bitmap exists;

evaluating whether a pointer corresponding to a sub bitmap that represents the data block exists;

in response to the pointer corresponding to a sub bitmap that represents the data block not existing, determining that the data block is not deleted;

in response to the sub bitmap that represents the data block existing, determining whether a bit in the sub bitmap that represents the data block is turned on;

in response to the bit in the sub bitmap that represents the data block being turned on, determining that the data block is not deleted; and

in response to the bit in the sub bitmap that represents the data block not being turned on, determining that the data block is deleted.

4. The method of claim 1, wherein size of the second level bitmap corresponds to size of data cache in a machine the hierarchical bitmap structure is implemented.

5. A system for utilizing a hierarchical bitmap structure to represent deleted data in databases, comprising:

a plurality of bitmaps arranged in a hierarchy, each level of bitmaps in the hierarchy including a plurality of bits corresponding to one or more blocks of data, a level of bitmap in the hierarchy having bits representing a finer granularity of number of blocks than bits in its parent level, top most bitmap level having size that corresponds to size of a register of a machine in which the hierarchical bitmap structure is implemented; and

a processor operable to generate a sub bitmap when a data block is deleted that corresponds to the sub bitmap, the processor further operable to turn on a bit corresponding to the data block in said each level of bitmaps, the processor further operable to query whether a second data block is deleted by evaluating a bit representing said second data block in one or more levels of bitmaps;

each of the levels in the hierarchical bitmap structure being of size which fits in a corresponding level of memory hierarchy associated with a machine running the processor; and

each bit in the top most bitmap represents x/n blocks of data, wherein x is total number of blocks and n is the size of the top most bitmap, and wherein m number of sub bitmaps can be generated, each sub bitmap having size equal to round((x/m)+0.5) bits;

allocating a temporary hierarchical bitmap structure corresponding to one or more local data deletes; and

merging the temporary hierarchical bitmap structure with a master hierarchical bitmap structure.

6. A method for utilizing a hierarchical bitmap structure to represent deleted data in databases, comprising:

allocating by a processor a first level bitmap having size equal to a register on a processor, each bit in the first level bitmap representing a plurality of blocks of data in a database;

allocating by a processor one or more pointers corresponding to said plurality of bits in the first level bitmap, said one or more pointers being allocated to point to a sub bitmap generated after a data block is deleted but before the index corresponding to the data block is cleaned;

each of the levels in the hierarchical bitmap structure being of size which fits in a corresponding level of memory hierarchy associated with a machine running the processor; and

each bit in the first level bitmap representing x/n blocks of data, wherein x is total number of blocks and n is the size of the first level bitmap, and wherein m number of sub bitmaps can be generated, each sub bitmap having size equal to round((x/m)+0.5) bits;

allocating a temporary hierarchical bitmap structure corresponding to one or more local data deletes; and

merging the temporary hierarchical bitmap structure with a master hierarchical bitmap structure.