I recently learned a performance optimization in SQL Server I did not know about ("Bitmap Filter On (Clustered) Non-Nullable Column Hash Semi-join Reduction via Scan + Probe IN-ROW" - a real mouthful), and am looking for data sets that can defeat my optimization, as this same query will be used in a nearly identical database schema in a different database with different customer use cases.
- Specify OPTION(Hash Join, MAXDOP = 8)
- MAXDOP effectively tells the query optimizer to look for plans that can exploit parallelism
- HASH JOIN is what tells the query optimizer to consider a Bitmap Filter
- Non-nullable column filtered on EXISTS clause
- When the column is non-nullable, the semi-join (EXISTS clause) guides the optimizer to choose a clustered index scan with a predicate that says something like PROBE(NonNullableColumn, 'IN-ROW')
- Combined with the bitmap filter, the PROBE is highly efficient because it uses a bitmap filter. This is, in effect, equivalent to a perfect Index Seek. It's like a bookmark lookup on steroids.
However, in thinking through this cleverly constructed query I just made, I'm a little scared I don't know how to break it and when to expect it to stop working and the cost-based optimizer will choose a different plan.
Suppose I have 3000 unique values for NonNullableColumn, each with 30 million rows binned to those unique values. In my performance tests so far, I passed in a set containing 15 as a unique test value. This works great and I'm pretty confident this is the optimal plan. What happens if I pass in a set containing random numbers - will SQL Server stop using the bitmap filter? What's the "worst case" scenario here?
I've attached a picture of the query plan to re-inforce what I'm trying to test and how I can defeat (or anticipate) Murphy's Law.
In thinking through "what could go wrong", I found this in SQL Server Docs:
The Repartition Streams operator (or exchange iterator) consumes multiple streams and produces multiple streams of records. The record contents and format are not changed. If the query optimizer uses a bitmap filter, the number of rows in the output stream is reduced.
SQL Server uses the Bitmap operator to implement bitmap filtering in parallel query plans. Bitmap filtering speeds up query execution by eliminating rows with key values that cannot produce any join records before passing rows through another operator such as the Parallelism operator. A bitmap filter uses a compact representation of a set of values from a table in one part of the operator tree to filter rows from a second table in another part of the tree. By removing unnecessary rows early in the query, subsequent operators have fewer rows to work with, and the overall performance of the query improves. The optimizer determines when a bitmap is selective enough to be useful and in which operators to apply the filter. Bitmap is a physical operator.
According to Bitmap Filter (Star Join Query Optimization):
Bitmap filter doesn’t work if:
- It’s not a hash join
- Out of date stats/missing indexes (cardinality/rows)
- Not enough memory
- Not enough threads (BF only works in parallel query – you need more than 1 CPU)
In my case, 1, 2 and 4 are not problems. 3 is evidently not a problem, at least in my example test. The memory requirement essentially means my StarJoinInfo table (Build table) must be smaller enough to fit in main memory; I wish I had a formula that gave me a upper bounds on how many unique values I could create a BitMap for.