1992 · 88 citations · 6 references
ComputingComputer ScienceData StructuresDatabasesNatural Language ProcessingDatabase ManagementQuery OptimizationQuery ProcessingRelational AlgebraRelational DatabasesStructured Query LanguageJoinJoin AlgorithmsOuter JoinRelational Query ProcessingSql Query LanguagesSubquery OptimizationSubquery ProcessingSubquery Unnesting
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.
6
On optimizing an SQL-like nested query
Won Bae Kim · ACM Transactions on Database Systems · 1982 · 393 citations · Full text
Optimization of nested SQL queries revisited
Richard A. Ganski, Harry K. T. Wong · 1987 · 177 citations · Full text