3

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.

  1. Specify OPTION(Hash Join, MAXDOP = 8)
    1. MAXDOP effectively tells the query optimizer to look for plans that can exploit parallelism
    2. HASH JOIN is what tells the query optimizer to consider a Bitmap Filter
  2. Non-nullable column filtered on EXISTS clause
    1. 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')
    2. 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.

and:

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.

Showplan Logical and Physical Operators Reference

enter image description here

According to Bitmap Filter (Star Join Query Optimization):

Bitmap filter doesn’t work if:

  1. It’s not a hash join
  2. Out of date stats/missing indexes (cardinality/rows)
  3. Not enough memory
  4. 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.

5
  • I used FluentMigrator to seed a database with 300M rows partitioned across 10 partitions. The schema is a lot like an Entity-Attribute-Value schema. I cannot share work product, though. Nov 21, 2018 at 16:55
  • My customer is probably one of the more challenging and doesn't really want future bills for maintenance, so I tend to try to put these scenarios in up front. I can always come up with workarounds in the C# side, such as precomputing a set of values to create an efficient bitmap filter for. I just can't find full explanation of how SQL Server builds the bitmap given my "StarJoinInfo" table (A) and the partitions in my "Probe" table (B). I had never really thought about the problem this way but this seems like the optimal way to do it, given I have full control over table A. Nov 21, 2018 at 22:17
  • Right now, on a 300M row sample, I have a 1 year of minutely data StarJoinInfo table bringing back 525,600 data points in 6 seconds on SQL Server 2017 Standard Edition. Compared to what they were doing in R, this is a huge success. Now I just want to make it bulletproof and avoid non-deterministic performance as much as possible. Nov 21, 2018 at 22:35
  • In reading Microsoft Sql Server 2012 Internals, Delaney explains that in order to build the bitmap table, the build table (StarJoinInfo) has to fit in memory. This explains at least half of what I wanted to know. Nov 25, 2018 at 0:54
  • Surprise, Murphy and his cousins moved into my SQL Server and broke my query's performance. I found this article very helpful, but I'm still at a loss as to why the "optimized bitmap filter" is no longer working. sqlserverfast.com/blog/hugo/2018/05/… Feb 1, 2019 at 21:26

1 Answer 1

-2

I figured out the answer to my question - sort of.

When you specify MAXDOP(8), the optimized bitmap filter optimization will create 8 hash buckets. The exact spread of integers across those hash buckets is probably Pearson hashing. I am curious if anyone in the comments knows the exact hashing technique, though.

Quoting: https://sqlserverfast.com/blog/hugo/2018/05/plansplaining-part-5-bitmaps/

Simple example: Let’s say that only three stores in our database have less than 30 employees. These stores have StoreKey 17, 38, and 82. The first row the Bitmap operator receives is for StoreKey 17; it hashes the number 17 and the result is 29, so bit 29 in the bitmap is set to one. It then reads the next row, for StoreKey 38; hashes the number 38 which results in 15; and sets bit 15 to one. The third row it reads is for StoreKey 82; due to a hash collision this number also hashes to 29 so it will once more set bit 29 to one (effectively not changing anything). There are no more rows so the end result will be a bitmap with bits 15 and 29 set to one and all other bits set to zero.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.