Improved Unnesting Algorithms for Join Aggregate SQL Queries

Abstract

Abstract: The SQL language allows users to express queries that have nested subqueries in them. Optimi-zation of nested queries has received considerable attention over the last few years [Kim82, Ganski87, Daya187, Murali891. As pointed out in [Ganski87], the solution presented in [Kim821 for JA type queries has the COUNT bug. In order to avoid the COUNT bug, the more general strategy described in [Gan-ski871 and [Dayal87] is used. In this paper, we modify Kim’s algorithm so that it avoids the COUNT bug. The modified algorithm may be used when it is more efficient than the general strategy. In addition, we present a couple of enhancements that precompute aggregates and evaluate joins and outer joins in a top-down order. These enhancements eliminate Cartesian products when certain correlation predicates are ab-sent and enable us to employ Kim’s method for more blocks. Finally, we incorporate the above improve-merits into a new unnesting algorithm. 1.