Bitmap Operator
Bitmap Operator
By : Kasim Wirama, MCDBA
This posting, I would like to dissect other operator that might show up in query execution plan of SQL Server, i.e. bitmap filtering. As the name implies, bitmap filtering will use bitmap as the way to mark rows from left input sets in order to get filtered right input sets. Let’s look at next example, with script creation taken from http://geeks.netindonesia.net/blogs/kasim.wirama/archive/2008/07/12/parallelism-in-nested-loop.aspx.
After you create bigtable and anotherbigtable, I issue this query :
SELECT t1.col1, t1.col2, t1.col3
FROM bigtable AS t1
JOIN anotherbigtable AS t2
ON t1.col2 = t2.col2
WHERE t1.col1 < 1000
Execution plan for the query above is :
|--Parallelism(Gather Streams)
|--Hash Match(Inner Join, HASH:([t1].[col2])=([t2].[col2]), RESIDUAL:([Northwind].[dbo].[anotherbigtable].[col2] as [t2].[col2]=[Northwind].[dbo].[bigtable].[col2] as [t1].[col2]))
|--Bitmap(HASH:([t1].[col2]), DEFINE:([Bitmap1004]))
| |--Parallelism(Repartition Streams, Hash Partitioning, PARTITION COLUMNS:([t1].[col2]))
| |--Clustered Index Seek(OBJECT:([Northwind].[dbo].[bigtable].[PK__bigtable__5CD6CB2B] AS [t1]), SEEK:([t1].[col1] < (1000)) ORDERED FORWARD)
|--Parallelism(Repartition Streams, Hash Partitioning, PARTITION COLUMNS:([t2].[col2]), WHERE:(PROBE([Bitmap1004])=TRUE))
|--Clustered Index Scan(OBJECT:([Northwind].[dbo].[anotherbigtable].[pk_1] AS [t2]))
Optimizer implement creative technique to get only filtered rows from anotherbigtable during probe phase (as right input) through bitmap operator on build rows (bigtable) after build phase completes; so that parallel scan will scan right input rows during probe phase with bitmap value is true. 2 things will influence optimizer to implement bitmap operator; left input has limited enough number of rows and second thing is that operator knows beforehand that there will be a limited number of right input as well as left input is. I say “limited enough”, what does it mean? If you put filtering WHERE the value is too small so that left input sets is extremely limited, optimizer will generate execution plan with broadcast partitioning in parallel hash join or the value is too large so that left input sets is not in a limited number of rows, optimizer will generate execution plan with hash partitioning.
Bitmap operator might exist not only on parallel hash join but also on parallel merge join.