Orthogonal Optimization of Subqueries and Aggregation

There is considerable overlap between strategies proposed for subquery evaluation, and those for grouping and aggre-gation. In this paper we show how a number of small, inde-pendent primitives generate a rich set of efficient execution strategies —covering standard proposals for subquery evalu-ation suggested in earlier literature. These small primitives fall into two main, orthogonal areas: Correlation removal, and efficient processing of outerjoins and GroupBy. An op-timization approach based on these pieces provides syntax-independence of query processing with respect to subqueries, i. e. equivalent queries written with or without subquery produce the same efficient plan. We describe techniques implemented in Microsoft SQL Server (releases 7.0 and 8.0) for queries containing sub-queries and/or aggregations, based on a number of orthog-onal optimizations. We concentrate separately on removing correlated subqueries, also called “query flattening, ” and on efficient execution of queries with aggregations. The end re-sult is a modular, flexible implementation, 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 the time of writing (November 2000), SQL Server has the fastest results on those queries, even on a fraction of the processors used by other systems. 1