Optimization of a star join operation using a bitmap index structure

A computer-implemented system for performing a star join to retrieve data from a relational database stored in one or more data storage devices coupled to a computer, comprising:

• (a) means for generating a cross-product from a plurality of dimension tables referenced by the star join;
• (b) means for hashing one or more join columns of the cross-product to create a hash-row value;
• (c) means for using the hash-row value to probe a Star Map to determine whether a record exists in the fact table that corresponds to the cross-product, wherein a first portion of the hash-row value is used to select a row of the Star Map, a second portion of the hash-row value is used to select a column of the selected row of the Star Map, and a value stored at the selected row and column of the Star Map indicates whether the record may exist in the fact table that corresponds to the cross-product;
• and
• (d) means for accessing the fact table to perform a join with the cross-product when the selected column of the selected row of the Star Map indicates that the record may exist in the fact table.

An article of manufacture comprising logic embodying a method for performing a star join in a computer to retrieve data from a relational database stored in one or more data storage devices coupled to the computer, the method comprising:

• (a) generating a cross-product from a plurality of dimension tables referenced by the star join;
• (b) hashing one or more join columns of the cross-product to create a hash-row value;
• (c) using the hash-row value to probe a Star Map to determine whether a record exists in the fact table that corresponds to the cross-product, wherein a first portion of the hash-row value is used to select a row of the Star Map, a second portion of the hash-row value is used to select a column of the selected row of the Star Map, and a value stored at the selected row and column of the Star Map indicates whether the record may exist in the fact table that corresponds to the cross-product;
• and
• (d) accessing the fact table to perform a join with the cross-product when the selected column of the selected row of the Star Map indicates that the record may exist in the fact table.