Databases Reference
In-Depth Information
and plans is not surprising for the highly and least selective queries, as it is their standard
usage as explained in
Chapter 2, The Execution Engine
. What is new is the choice of Hash
Joins and bitmap filtering for medium selectivity queries, so that's what we'll look at next.
Bitmap filtering is an optimization for star join queries that was introduced with
SQL Server 2008 and it is only available on the Enterprise, Developer and Evaluation
editions. It is referred to as optimized bitmap filtering in order to differentiate it from
the standard bitmap filtering which was already available in previous versions of SQL
Server. Optimized bitmap filtering improves the performance of star join queries by
removing unnecessary rows from processing early in the query plan, so that subsequent
operators have fewer rows to process. In our case, it filters rows from the fact table to
avoid additional join processing.
This strategy is called "semi-join reduction" and relies on the fact that only the records
from the second table that qualify for the join with the first table are processed. SQL
Server bitmap filters are based on bloom filters, originally conceived by Burton Bloom in
1970. Other semi-join reduction technologies like bitmap indexes have been used by other
database vendors.
Optimized bitmap filtering works with Hash Joins which (as we saw in Chapter 2) use
two inputs, the smaller of which (the build table) is being completely read into memory.
Optimized bitmap filtering takes advantage of the fact that a Hash Join has to process
the build input anyway so, as SQL Server is processing the build table, it creates a bitmap
representation of the join key values found. Since SQL Server can reliably detect fact and
dimension tables, and the latter are almost always the smaller of the two, the build input
upon which the bitmap is based will be a dimension table. This bitmap representation
of the dimension table will be used to filter the second input of the Hash Join, the probe
input, which in this case will be the fact table. This basically means that only the rows in
the fact table that qualify for the join to the dimension table will be processed.
