Data Warehousing and Business Intelligence

15 March 2010

Bitmap Filter (Star Join Query Optimisation)

Filed under: Data Warehousing,SQL Server — Vincent Rainardi @ 9:54 pm
Tags: ,

Bitmap Filter is an in-memory structure that uses a compact representation of a set of values from one table in one part of a query to filter the rows on the second table located in another part of the query.

In SQL Server data warehousing, Bitmap Filter is used to reduce the number of fact rows involved in a star join query by eliminating fact rows that does not satisfy the dimension where clause, before the fact table enters the join. This improves the query performance.

A star join query is SQL query where a large fact table is joined to dimension tables, filtered on dimension attributes and grouped by a set of dimension attributes to get an aggregate of the measures.

Bitmap filter works on:

  • select statements
  • read-only part of update, delete, insert and merge
  • when creating Indexed views (materialised views)
  • reduce query compilation time

Example/demo:

select d1.attr2, d3.attr2, d1.attr1, sum(f.measure1)
from FactNoPK f
inner join dim1 d1 on d1.dimkey1 = f.dimkey1
inner join dim2 d2 on d2.dimkey2 = f.dimkey2
inner join dim3 d3 on d3.dimkey3 = f.dimkey3
where d2.attr2 between ‘Value100’ and ‘Value120’
group by d1.attr2, d3.attr2, d1.attr1

With Bitmap Filter:
PROBE([Opt_Bitmap1005], [Test].[dbo].[FactNoPK] as [f].dimkey1, N’[IN ROW]’) AND
PROBE([Opt_Bitmap1006]. [Test].[dbo].[FactNoPK] as [f].dimkey2, N’[IN ROW]’) AND
PROBE([Opt_Bitmap1007]. [Test].[dbo].[FactNoPK] as [f].dimkey3, N’[IN ROW]’)

Notes:

  • Bitmap filter only works on inner join. It doesn’t work on outer or cross join.
  • Bitmap filter only works on hash joins. It doesn’t work on merge or nested lookup joins.
  • The fact table need to be > 100 pages.
  • The join must be on a single column.
  • Bitmap filter can slow down queries

About joins:

  • Nested loop join: table1 is small and table2 is big, e.g. 5 & 50k rows, and join columns are indexed
  • Merge join: both tables are equally big e.g. 400k & 500k rows and join columns indexed.
  • Hash join: both tables are big but 1 is much bigger e.g. 100k & 1m rows, join columns unindexed.

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)
Advertisements

3 Comments »

  1. […] Star join query/bitmap filter: faster reports […]

    Pingback by SQL 2008 Data Warehousing Features « Data Warehousing and Business Intelligence — 15 March 2010 @ 10:05 pm | Reply

  2. Hello, MSDN (https://technet.microsoft.com/en-us/library/bb522541(v=sql.105).aspx) states, “Bitmap filtering is applied only in parallel query plans in which hash or merge joins are used.” but you stated only available in hash joins…

    Comment by mickey mouse — 13 February 2016 @ 3:16 pm | Reply

    • Yes you are right, SQL Server 2008R2 and above applies bitmap filter to both hash and merge joins, but the optimized bitmap filtering is only applicable to parallel query plans which uses hash joins. Hence practically speaking, bitmap filter doesn’t work with merge joins.

      Comment by Vincent Rainardi — 14 February 2016 @ 7:09 am | Reply


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at WordPress.com.

%d bloggers like this: