Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers
Umeshwar Dayal · Very Large Data Bases · 1987
Existing query optimizers focus on Restrict-Project-Join queries. In practice, however, query languages such as SQL and DAPLEX have many powerful features (eg., control over duplicates, nested subqueries, grouping, aggregates, and quantifiers) that are not expressible as sequences of Restrict, Project, and Join operations. Existing optimizers are severely limited in their strategies for processing such queries; typically they use only tuple substitution, and process nested subquery blocks top down. Tuple substitution, however, is generally inefficient and especially so when the database is distributed. Hence, it is imperative to develop alternative strategies. This paper introduces new operations for these difficult features, and describes implementation methods for them. From the algebraic properties of these operations, new query processing tactics are derived. It is shown how these new tactics can be deployed to greatly increase the space of interesting strategies for optimisa tion, without seriously altering the architecture of existing optimisers. The contribution of the paper is in demonstrating the feasibility and desirability of developing an integrated framework for optimising all of SQL or other query languages that have similiar features.