A Combined Framework for Grouping and Order Optimization

This chapter presents a combined framework that allows a very efficient handling of order optimization and grouping optimization during plan generation. During plan generation, many operators require or produce certain orderings. To avoid redundant sorting it is required to keep track of the orderings that a certain plan satisfies. The orderings that are relevant for query optimization are called interesting orders. Grouping is similar to order optimization, it is beneficial to keep track of the groupings satisfied by a certain plan. Traditionally, group-by operators are applied after the rest of the query has been processed, or are scheduled using some heuristics. However, the plan generator could take advantage of grouping properties produced. The reasoning about orderings and groupings assumes that the set of functional dependencies is known. There are three sources of functional dependencies—key constraints, join predicates, and filter predicates. Integrating groupings in the order optimization framework allows the plan generator to easily exploit groupings and thus produce better plans. However, order optimization itself might become prohibitively expensive by considering groupings. The chapter evaluates the costs of including groupings for different queries. The experimental results show that with only a modest increase of the one-time costs, groupings can be exploited during plan generation at no additional costs.