THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Page Free Space

See also my SQL Server technical articles on SQLperformance.com

Bitmap Magic (or… how SQL Server uses bitmap filters)

This article has permanently moved to https://sqlkiwi.blogspot.com/2011/07/bitmap-magic.html

Published Thursday, July 7, 2011 5:44 AM by Paul White

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

tobi said:

I wonder if it would be beneficial to generate parallel plans even on single-core machines to leverage the sub-linear scaling.

In fact, sub-linear scaling can never exist in any algorithm because you could just run the algorithm on N _simulated_ cores and get the sub-linear speedup even on a single physical core.

July 6, 2011 7:40 PM
 

Fabricio Catae said:

Wow, the estimated cost for the parallel version is lower than the serial plan. Simply unbelievable! I had some fun playing with the query, and tried to make it faster with MAXDOP 1. Gave up after 2 hours. This Bitmap operator does improve the Hash Join performance. I am still learning. Great article Paul.

July 6, 2011 10:27 PM
 

Paul White said:

Hi Tobi,

It's unsupported, but you could try starting SQL Server on a single-core test machine with the -P parameter to start more than one scheduler.  This will allow a 'parallel' plan to be generated, giving the benefit of bitmap elimination.

Paul

July 7, 2011 2:31 AM
 

Paul White said:

Fabrico,

Thank you - I love this bitmap thing and have been meaning to blog about it for a long time.  It's such a counter-intuitive result in some ways.  Perhaps one day SQL Server will be extended to allow a serial hash join to also push a bitmap?  Probably not - I guess if that were on the cards, they would have done it in SQL 2008, at the same time they introduced 'optimized' bitmap filtering...

Paul

July 7, 2011 2:34 AM
 

tobi said:

These detailed posts of internals are a joy to read.

July 7, 2011 6:30 AM
 

Fabiano Amorim said:

Holy shit, I didn't understood anything :-)... Loved the article... I'll read again and again and again...

Thanks for that Paul.

July 15, 2011 4:32 PM
 

Paul White: Page Free Space said:

You probably already know that it’s important to be aware of data types when writing queries, and that

July 18, 2011 7:17 AM
 

Thomas LeBlanc said:

Over the top. I have been wondering lately with some large Data Warehouse queries have been showing Extimated rows different from the Actual rows of the joins. Now I understand, thought there was a problem with Statistics.

Thanks Paul!!!

January 26, 2012 5:18 PM
 

Paul White said:

Thank you Thomas, I'm so glad you found this useful :)

Paul

January 26, 2012 5:40 PM
 

vikas said:

Hi experts

its realy fantastic article. It will more better if writer take some example on bitmap artitecture and using some picture if they explain.then it will easy to understatnd.

Regards

vikas

February 28, 2012 2:46 AM
 

Paul White: Page Free Space said:

This is a post for T-SQL Tuesday #43 hosted by my good friend Rob Farley . The topic this month is Plan

June 11, 2013 5:00 AM
 

Geoff Patterson said:

Great article, thanks (several years late, I know)!  My whole team has learned a lot about the importance of constructing queries to benefit from the in-row bitmap filter optimization (pushing down to the storage engine) especially.

Here is a new Connect issue I filed that might also be of interest; it seems that using a partitioned view (or otherwise hitting two or more fact tables via UNION ALL) is a situation in which the query optimizer cannot apply the optimization.

https://connect.microsoft.com/SQLServer/feedbackdetail/view/974909/push-bitmap-filters-into-storage-engine-through-a-concatentation-operator

It's hard to be "frustrated" when a new release of SQL Server (new since our data model was constructed, at least) provides such a powerful new benefit, but it certainly would be useful to allow the optimization to be pushed through a concatenation as well!

September 18, 2014 12:17 PM
 

Paul White said:

Thanks Geoff, I'll take a look at the Connect item. Were you hoping the filter would be applied to all tables below the union? I can imagine why that wouldn't happen. I expect the response will be to use partitioned tables (and therefore, Enterprise Edition!) instead...

September 18, 2014 1:14 PM
 

Geoff Patterson said:

Paul,

Yes, that's what I was hoping, and it doesn't happen.  We are using partitioned tables (by date) and partitioned views (by level of data granularity, e.g. item level data, department level aggregation, total store aggregation if you were to think of a retailer or grocery store as the data set) layered on top of them.

It is probably true that we could make some sort of compound column reflecting both the date and the level of data granularity and partition on that (especially with 15K partitions now), but it seems like this would be a useful change to SQL Server overall.  It seems like a pain to have to worry about a case where writing two separate queries could be an order of magnitude faster than performing the same work on a unioned (union all) data set!

I suspect that a possible answer might be to look into Clustered Columnstore Indexes, which to my understanding do perform this type of optimization (although it is not reflected in the query plan in precisely the same way), but that is obviously a pretty big change to the way someone is loading data.

September 18, 2014 2:14 PM
 

Kendra Little said:

Thanks for a great article, Paul! Very clear and well written, as usual. Love the detail on IN ROW.

August 12, 2016 2:42 PM

Leave a Comment

(required) 
(required) 
Submit
Privacy Statement