Avoiding Sorting and Grouping In Processing Queries Xiaoyu Wang and Mitch Cherniack   View Paper (PDF)   Return to Advanced Query Processing (Session C5) Abstract used simple inference strategies to determine orderings held of intermediate relations to avoid unnecessary sorting, and to influence join plan selection. Since then, others have pro- posed using integrity constraint information to in- fer orderings of intermediate query results. How- ever, these proposals do not consider how to avoid grouping operations by inferring groupings, nor do they consider secondary orderings (where records in the same group satisfy some ordering). In this paper, we introduce a formalism for express- ing and reasoning about order properties: order- ing and grouping constraints that hold of physi- cal representations of relations. In so doing, we can reason about how the relation is ordered or grouped, both in terms of primary and secondary orders. After formally defining order properties, we introduce a plan refinement algorithm that in- fers order properties for intermediate and final query results on the basis of those known to hold of query inputs, and then exploits these infer- ences to avoid unnecessary sorting and grouping. We then show empirical results demonstrating the benefits of plan refinement, and show that the overhead that our algorithm adds to query op- timization is low. ©2004 Association for Computing Machinery