A Combined Framework for Grouping and Order Optimization

Since the introduction of cost-based query op-timization by Selinger et al. in their semi-nal paper, the performance-critical role of in-teresting orders has been recognized. Some algebraic operators change interesting orders (e.g. sort and select), while others exploit them (e.g. merge join). Likewise, Wang and Cherniack (VLDB 2003) showed that existing groupings should be exploited to avoid redun-dant grouping operations. Ideally, the reason-ing about interesting orderings and groupings should be integrated into one framework. So far, no complete, correct, and ecient algo-rithm for ordering and grouping inference has been proposed. We ll this gap by propos-ing a general two-phase approach that e-ciently integrates the reasoning about order-ings and groupings. Our experimental results show that with a modest increase of the time and space requirements of the preprocessing phase both orderings and groupings can be handled at the same time. More importantly, there is no additional cost for the second phase during which the plan generator changes and exploits orderings and groupings by adding operators to subplans.