Orthogonal optimization of subqueries and aggregation

There is considerable overlap between strategies proposed for subquery eval uation, and those for grouping and aggregation. In this paper we show how a number of small, independent primitives generate a rich set of efficient e xecution strategies-covering standard proposals for subquery evaluation sug gested in earlier literature. These small primitives fall into two main, or thogonal areas: Correlation removal, and efficient processing of outerjoins and GroupBy. An optimization approach based on these:pieces provides synta x-independence of query processing with respect to subqueries, i. e, equiva lent queries written with or without subquery produce the same efficient pl an. We describe techniques implemented in Microsoft SQL Server (releases 7.0 an d 8.0) for queries containing subqueries and/or aggregations', based on a n umber of orthogonal optimizations. We concentrate separately on removing co rrelated subqueries, also called "query flattening," and on efficient execu tion of queries with aggregations. The end result is a modular, flexible im plementation, which produces very efficient execution plans. To demonstrate the validity of our approach, we present results for some queries from the TPC-H benchmark. From all published TPC-H results in the 300GB scale, at t he time of writing (November 2000), SQL Server has the fastest results on t hose queries, even on a fraction of the processors used by other systems.