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.
["Patrick E. O'Neil", 'Goetz Graefe']
Multi-table joins through bitmapped join indices