Share via

Intro to Query Execution Bitmap Filters

  • Article

One of the least understood Query Execution operators is the Bitmap.  I'd like to give a fairly brief overview of how Bitmap filters are used, as well as some technical details about their limitations and functionality.  Bitmap filters are often mistaken as Bitmap indexes.  The two are actually very distinct concepts -- Bitmap indexes are physical structures that are persisted on disk and are used for data access while Bitmap filters are an in-memory structure that is used for enhancing performance during the execution of a query.  This article refers exclusively to Bitmap filters.  Bitmaps are visible in ShowplanXML (see attachment) and will in the XML plan similar to this:

<RelOp NodeId="5" PhysicalOp="Bitmap" LogicalOp="Bitmap Create" EstimateRows="10" EstimateIO="0" EstimateCPU="0.028506" AvgRowSize="11" EstimatedTotalSubtreeCost="0.0317319" Parallel="1" EstimateRebinds="0" EstimateRewinds="0" xmlns="**https://schemas.microsoft.com/sqlserver/2004/07/showplan**"\>

Also in Showplan, the columns that are used for filtering by the bitmap are visible:

<OutputList>

        <ColumnReference Database=" [QEWorkingDB] " Schema=" [dbo] " Table=" [MJ_BMAP_1] " Alias=" [A] " Column="c_int" />

</OutputList>

 

The primary role of the Bitmap is to speed up parallel plans by doing semijoin reduction early on in the query, before rows are passed through the Parallelism operator.  Bitmaps are not used in serial plans.  The Bitmap itself gets created on the build side of a Hash Join (this is where the Iterator will appear in the plan), but the actual bitmap checks (filtering of rows) is done within the Parallelism operator that is on the probe side of the Hash Join.  Note that not every Hash Join in a parallel plan will use a Bitmap for filtering rows -- it is a decision that is made by the Optimizer if it thinks that the Bitmap will be selective enough to be useful.  Hash Joins are not the only type of join where Bitmaps can be used -- in some cases, Bitmaps can be used with Merge Joins as well.

 

Another interesting thing to make note of is that since Bitmaps filter out rows flowing through a query plan, they will affect the accuracy of the Showplan estimations (Estimated Number of Rows) for other operators above them in the query plan.  Since the Optimizer can never be 100% certain how many rows the Bitmap will filter out, the Actual Rows (visible through Statistics Profile after a query has run) will usually differ somewhat from the estimates.  This is normal and to be expected.

 

Internally, Bitmaps are implemented as a relatively simple bit array.  When building the bitmap, we assign a hash value to each row in the build-side table and set the bits in the array to correspond with hash values that contain at least one row.  When we check the bitmap from the probe side, we again hash each row and check whether the bit is set or not in the array.  If the bit is not set, then we immediately know that the row will not qualify in the join (since there is no match from the other table) and we can drop the row.  This provides a low-cost approach of quickly eliminating rows without the overhead of doing a full join algorithm.

 

One optimization that allows us to check the Bitmap and eliminate rows even earlier on in a query's execution is called In-Row Optimization.  This option is available only when certain conditions are met, specifically the Bitmap must be used on not-nullable INT or BIGINT columns.  If this is true, then this optimization involves pushing the Bitmap check down as a Filter into the actual Table/Index Scan (where we retrieve the data from disk).  One can check whether this optimization is being used by looking at the Showplan and examining the Parallelism operator directly above the Table/Index scan on the probe side of the join.  To tell whether In-Row is being used, you should look for the InRow tag (bolded) in the ShowplanXML.  This will be found on the Parallelism operator directly above the Table/Index scan on the probe side of the Hash Join

 

<

RelOp NodeId="79" PhysicalOp="Parallelism" LogicalOp="Repartition Streams" EstimateRows="100000" EstimateIO="0" EstimateCPU="0.0884062" AvgRowSize="11" EstimatedTotalSubtreeCost="2.67314" Parallel="1" EstimateRebinds="0" EstimateRewinds="0"> <Parallelism PartitioningType="Hash" InRow="1" >

- Steve Herbert

Query Execution

QE_Bitmap_Filters.jpg

Comments

  • Anonymous
    November 16, 2006
    The comment has been removed

  • Anonymous
    April 09, 2007
    The star join optimization technique is an index based optimization designed for data warehousing scenarios

  • Anonymous
    June 20, 2007
    Prior to my SQL Server 2008 "Katmai" session (tommorrow) I'd like to share some nice resource explaining