Constructing balanced multidimensional range-based bitmap indices

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 9

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.

Claim 10

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.

Claim 11

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.

Claim 12

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

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.

Claim 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, 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.

Claim 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 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.

Claim 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 16, further comprising the step of dynamically adjusting the threshold as a function of a percentage of the database that has been scanned.

Claim 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 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.

Claim 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, 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.

Claim 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 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.

Claim 24

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.

Claim 25

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.

Claim 26

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.

Claim 27

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.

Claim 28

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.