Constructing balanced multidimensional range-based bitmap indices

• US 5,761,652 A
• Filed: 03/20/1996
• Issued: 06/02/1998
• Est. Priority Date: 03/20/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Yu, Philip Shi-lung
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): HOMERE, JEAN RAYMOND
• Application Number:
  US08/618,736
• Time in Patent Office: 804 Days
• Field of Search: 395/612, 395/611, 395/613, 395/621, 707/2, 707/100, 707/101, 707/102, 707/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A computerized method of building balanced ranges of attribute values for multiple attributes of a database simultaneously without requiring presorting of the database. The balanced ranges are used to construct balanced range-based multidimensional bitmap indexes for processing complex multipredicate queries against the database. A dynamic partition expansion and contraction method can construct balanced ranges for bitmap indexing of tuples having high cardinality attributes and even in the presence of highly skewed data.

Claims

1. A computerized method of constructing balanced multidimensional range-based bitmap indices associated with a database which includes a plurality of tuples, each tuple having a plurality of attributes, said method comprising the steps of:

partitioning each attribute in the database into partitions spanning contiguous ranges of attribute values, each partition having an occurrence count;

sequentially scanning each tuple in the database and incrementing the occurrence count of a partition associated with an attribute value of each of said attributes; and

when all tuples have been scanned once, combining partitions and balancing the occurrence count across combined partitions.

2. A computerized method as claimed in claim 1, further comprising the steps of:

constructing the balanced range-based bitmap indices according to the ranges of attribute values of the combined partitions; and

storing the balanced range-based bitmap indices on a computer readable memory.

3. A computerized method as claimed in claim 1, further comprising the step of splitting the partition into a plurality of partitions when the occurrence count exceeds a threshold, responsive to said step of incrementing the occurrence count.

4. A computerized method as claimed in claim 3, further comprising the step of dynamically adjusting the threshold as a function of a percentage of the database that has been scanned.

5. A computerized method as claimed in claim 1, wherein said step of sequentially scanning each tuple further comprises the steps of:

determining when the attribute value is an isolated skew value;

creating a special partition associated with said isolated skew value; and

incrementing the occurrence count associated with the special partition.

6. A computerized method for processing a multiattribute query using the balanced range based bitmap indices constructed according to the method of claim 2, comprising the steps of:

receiving a query including multiattribute predicates,

retrieving corresponding range-based bitmap indexes based on the attribute values specified in the predicates;

performing bitwise AND/OR operations on retrieved bitmap indexes;

retrieving the tuples corresponding to the one'"'"'s in the resulting bitmap index in response to the bitwise AND/OR operations; and

filtering out all tuples having attribute values that do not match the attribute values specified in the predicates.

7. A computerized method as claimed in claim 5, wherein said step of determining when the attribute value is said isolated skew value further comprises the steps of:

maintaining a primary stack prioritized by recency of occurrence and a secondary stack prioritized by frequency of occurrence;

searching the primary stack for a primary entry matching the attribute value and performing the following steps;

when the primary entry is found, moving the primary entry to the top of the primary stack;

when the primary entry is not found, obtaining a bottom primary entry from the bottom of the primary stack and associating the attribute value therewith, and moving the bottom primary entry to the top of the primary stack;

searching the secondary stack for a secondary entry matching the attribute value and performing the following steps;

when the secondary entry is found, incrementing a count associated with the secondary entry and moving the secondary entry to a location according to the count;

when the secondary entry is not found, associating the attribute value with a bottom secondary entry and initializing the count; and

identifying the attribute value as said isolated skew value when the count exceeds a skew threshold.

8. A computerized method as claimed in claim 7, further comprising the step of dynamically adjusting the skew threshold as a function of a percentage of the database that has been scanned.

9. A computerized method as claimed in claim 5 wherein said step of combining partitions and balancing the occurrence count across the combined partitions comprises the steps of:

assigning a separate partition for each isolated skew value as a function of the occurrence count exceeding an ideal mean;

allocating proportional partitions to each contiguous range of values bounded by the separate partition, responsive to said step of assigning; and

combining and balancing said each contiguous range of values into the proportional partitions.

10. A computerized method as claimed in claim 5 wherein said step of combining and balancing said each contiguous range of values into the proportional partitions comprises a one-pass zigzag heuristic.

11. A computerized method as claimed in claim 1, further comprising the step of pre-specifying a distribution of tuples in each partition.

13. A computer storage device readable by a computer, tangibly embodying a multidimensional range-based bitmap indexed data structure as created by the method steps claimed in claim 2.

12. A computerized method of constructing balanced multidimensional range-based bitmap indices associated with a database which includes a plurality of tuples, each tuple having a plurality of attributes, said method comprising the steps of:

partitioning each attribute in the database into partitions spanning contiguous ranges of attribute values, each partition having an occurrence count;

sequentially scanning each tuple in the database and incrementing the occurrence count of a partition associated with an attribute value of each of said attributes;

determining when the attribute value is an isolated skew value;

creating a special partition associated with said isolated skew value;

incrementing the occurrence count associated with the special partition;

splitting the partition into a plurality of partitions when the occurrence count exceeds a threshold, responsive to said step of incrementing the occurrence count;

dynamically adjusting the threshold as a function of a percentage of the database that has been scanned;

when all tuples have been scanned once, combining partitions and balancing the occurrence count across combined partitions;

constructing the balanced range-based bitmap indices according to the ranges of attribute values of the combined partitions, responsive to said steps of combining partitions and balancing; and

storing the balanced range-based bitmap indices on a computer readable memory, responsive to said step of constructing the balanced range-based bitmap indices.

14. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform a computerized method of constructing balanced range-based bitmap indices associated with a database which includes a plurality of tuples, each tuple having a plurality of attributes, said method comprising the steps of:

partitioning each attribute in the database into partitions spanning contiguous ranges of attribute values, each partition having an occurrence count;

sequentially scanning each tuple in the database and incrementing the occurrence count of a partition associated with an attribute value of each of said attributes; and

when all tuples have been scanned once, combining partitions and balancing the occurrence count across combined partitions.

15. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 14, further comprising the steps of:

constructing the balanced range-based bitmap indices according to the ranges of attribute values of the combined partitions; and

storing the balanced range-based bitmap indices on a computer readable memory.

16. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 14, further comprising the step of splitting the partition into a plurality of partitions when the occurrence count exceeds a threshold, responsive to said step of incrementing the occurrence count.

17. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 16, further comprising the step of dynamically adjusting the threshold as a function of a percentage of the database that has been scanned.

18. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 14, wherein said step of sequentially scanning each tuple further comprises the steps of:

determining when the attribute value is an isolated skew value;

creating a special partition associated with said isolated skew value; and

incrementing the occurrence count associated with the special partition.

19. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 18, further comprising the step of splitting the partition into a plurality of partitions when the occurrence count exceeds a threshold, responsive to said step of incrementing the occurrence count.

20. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 18, wherein said step of determining when the attribute value is said isolated skew value further comprises the steps of:

maintaining a primary stack prioritized by recency of occurrence and a secondary stack prioritized by frequency of occurrence;

searching the primary stack for a primary entry matching the attribute value and performing the following steps;

when the primary entry is found, moving the primary entry to the top of the primary stack;

when the primary entry is not found, obtaining a bottom primary entry from the bottom of the primary stack and associating the attribute value therewith, and moving the bottom primary entry to the top of the primary stack;

searching the secondary stack for a secondary entry matching the attribute value and performing the following steps;

when the secondary entry is found, incrementing a count associated with the secondary entry and moving the secondary entry to a location according to the count;

when the secondary entry is not found, associating the attribute value with a bottom secondary entry and initializing the count; and

identifying the attribute value as said isolated skew value when the count exceeds a skew threshold.

21. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 20, further comprising the step of dynamically adjusting the skew threshold as a function of a percentage of the database that has been scanned.

22. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 18 wherein said step of combining partitions and balancing the occurrence count across the combined partitions comprises the steps of:

assigning a separate partition for each isolated skew value as a function of the occurrence count exceeding an ideal mean;

allocating proportional partitions to each contiguous range of values bounded by the separate partition, responsive to said step of assigning; and

combining and balancing said each contiguous range of values into the proportional partitions.

23. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps as claimed in claim 18 wherein said step of combining and balancing said each contiguous range of values into the proportional partitions comprises a one-pass zigzag heuristic.

24. A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to construct balanced range-based bitmap indices associated with a database which includes a plurality of tuples, each tuple having a plurality of attributes, said method comprising the steps of:

partitioning each attribute in the database into partitions spanning contiguous ranges of attribute values, each partition having an occurrence count;

sequentially scanning each tuple in the database and incrementing the occurrence of a partition associated with an attribute value of each of said attributes;

determining when the attribute value is an isolated skew value;

creating a special partition associated with said isolated skew value;

incrementing the occurrence count associated with the special partition;

splitting the partition into a plurality of partitions when the occurrence count exceeds a threshold, responsive to said step of incrementing the occurrence count;

dynamically adjusting the threshold as a function of a percentage of the database that has been scanned;

when all tuples have been scanned once, combining partitions and balancing the occurrence count across combined partitions;

constructing the balanced range-based bitmap indices according to the ranges of attribute values of the combined partitions, responsive to said steps of combining partitions and balancing; and

storing the balanced range-based bitmap indices on a computer readable memory, responsive to said step of constructing the balanced range-based bitmap indices.