Bitmap Filter (Star Join Query Optimisation)

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)