Multi-table joins through bitmapped join indices

This technical note shows how to combine some well-known techniques to create a method that will efficiently execute common multi-table joins. We concentrate on a commonly occurring type of join known as a star-join, although the method presented will generalize to any type of multi-table join. A star-join consists of a central detail table with large cardinality, such as an orders table (where an order row contains a single purchase) with foreign keys that join to descriptive tables, such as customers, products, and (sales) agents. The method presented in this note uses join indices with compressed bitmap representations, which allow predicates restricting columns of descriptive tables to determine an answer set (or foundset) in the central detail table; the method uses different predicates on different descriptive tables in combination to restrict the detail table through compressed bitmap representations of join indices, and easily completes the join of the fully restricted detail table rows back to the descriptive tables. We outline realistic examples where the combination of these techniques yields substantial performance improvements over alternative, more traditional query evaluation plans.