The Bitmap operator is used to build a bitmap that, based on a hash, represents which values may be present in a data flow. Due to the chance of hash collisions in the hash function used, the Bitmap process can produce false positives but not false negatives – so a match based on a bitmap is not guaranteed to be a match to the actual data, but a non-match based on a bitmap is guaranteed to not be a match in the actual data.
The generated bitmap is typically used in other operators to remove rows for which there is no match in the bitmap, and hence guaranteed no match in the original set of data processed by the Bitmap operator. The use of Bitmap operators is most common in execution plans for star join queries in large data warehouses. An example can be seen here.
Visual appearance in execution plans
Depending on the tool being used, a Bitmap operator is displayed in a graphical execution plan as shown below:
|SQL Server Management Studio||Azure Data Studio|
|(until version 17.3)||(version 17.4 and up)|
The basic algorithm for the Bitmap operator is as shown below:
It is unknown how exactly the bitmap is stored. I assume that it uses a contiguous array of N bytes, with N being the range of the hash function used divided by 8. I also assume that all bits are initialized to 0 (for false). Then when a row is processed, the hash function results in a number which is divided by 8 to find the byte position (dividend) and bit position within the byte (remainder); that bit is then set to 1 (for true). If it is already 1, it is probably just set to 1 again as testing before writing would be more expensive than overwriting a value with the same value. However, all of the above are speculations (and none are crucial to understanding how the Bitmap operator works).
The properties below are specific to the Bitmap operator, or have a specific meaning when appearing on it. For all other properties, see Common properties.
|Defined Values||This property lists the name of the created bitmap. This is especially important in execution plans that use multiple Bitmap operators. There is no definition explicitly given for the listed column (not needed, it is always a bitmap). Unlike other operators that have a Defined Values property, the defined column is not added to the rows returned and hence not included in the Output List property. The bitmap is instead stored in a centrally accessible location in memory and stores information about all rows processed.|
|Hash Keys||The property lists the column(s) that are hashed in order to find the location of a bit within the bitmap.|
|Logical Operation||Always equal to Bitmap Create.|
This table below lists the behavior of the implicit properties for the Bitmap operator.
|Batch Mode enabled||The Bitmap operator supports row mode execution only. In batch mode execution plans in SQL Server 2012, Batch Hash Table Build operator fulfills a similar role. As of SQL Server 2014, batch mode execution plans can now build hash tables while processing a Hash Match or Adaptive Join operator, by setting the BitmapCreator property to True.|
|Blocking||The Bitmap operator is non-blocking.|
|Memory requirement||The Bitmap operator does not have any special memory requirement, except for the memory to store the bitmap itself (which arguably can be considered part of the plan as a whole, not of this operator only).|
|Order-preserving||The Bitmap operator is fully order-preserving.|
|Parallelism aware||The Bitmap operator is only used in parallel execution plans. However, its operation is not parallelism aware. There is a separate instance of the bitmap for each thread, and the optimizer has to use Parallelism operators to force all rows to the “correct” thread to ensure that the bitmaps work as expected.|
|Segment aware||The Bitmap operator is not segment aware.|