Optimizing Star JoinQueriesforDataWarehousing

Asmainstream datawarehouses aregrowing intothe multi-terabyte range, adequate performance fordecision support queries remainschallenging fordatabase queryprocessors. Properchoice ofqueryplanisessential indatawarehouses wherefacttables oftenstorebillions ofrows.Thispaper discusses queryoptimization and execution strategies that Microsoft SQL Server employs fordecision support queries in dimensionally modeledrelational datawarehouses. Our approachisbasedonpattern matching todetect typical star querypatterns. When matching thepattern, theoptimizer generates additional queryplanalternatives specifically optimized fordatawarehouse performance. Forhighselectivity queries, theplansusenested loopsjoins andseeks. Medium selectivity queries inturnrelyonright-deep hashjoins with bitmapfilters. Bitmapfilters perform semi-join reductions to efficiently pruneoutnon-qualifying rowsearly. Final planchoice isleft forcost-based optimization whichalsocompares thedata warehouse specific plansagainst conventional queryplans. We conducted an extensive experimental investigation usingboth synthetic workloads andseveral customerworkloads. As our results show,thenewplanshapes andexecution strategies yield significant performance improvements acrossthetargeted workloads ascomparedtoearlier versions ofMicrosoft SQL Server. I:~~~~~~~~~~~~inishedGR rdsFiag ~~~~~~~~~~~~t d_ Colo4r