Improved query plans for unnesting SQL nested queries

Abstract

The SQL language allows users to express queries that have nested subqueries in them. Optimization of nested queries has received considerable attention over the last few years. The first algorithm for unnesting nested queries was Kim's algorithm, but this technique had a COUNT bug for JA type queries. Later few researchers gave more general strategies to avoid the COUNT bug. Finally to all this M. Muralikrishna modified Kim's algorithm so that it avoids the COUNT bug. The modified algorithm may be used when it is more e±cient than the general strategy. In addition, he presented a couple of enhancements that pre-compute aggregates and evaluate joins and outer joins in a top down order. These enhancements eliminated Cartesian products when certain correlation predicates are absent and enabled us to employ Kim's method for more blocks. Apart from this he proposed the Integrated algorithm for generating query plans for a given input query. In this thesis we have given a new solution for implementing the Kim's modified algorithm of unnesting nested queries and this also avoids the COUNT bug convincingly. Integrated algorithm generates °aws query plans, which has been modified in this thesis. We have also shown experimental results proving one query plan among the all other as computationally better one. These computations are in terms of elapsed time. We have carried out experiments for di®erent data sets of varying sizes from 100 to 1000 tuples in each relation. These results are taken as average of some possible iterative execution of each query plan. Finally, we incorporate the above improved merits into a new unnesting algorithm.