Business-Intelligence Queries with Order Dependencies in DB2

Abstract

Business-intelligence queries often involve SQL functions and algebraic expressions. There can be clear semantic relationships between a column’s values and the values of a function over that column. A common property is monotonicity: as the column’s values ascend, so do the function’s values. This we call an order dependency (OD). Queries can be evaluated more efficiently when the query optimizer uses order dependencies. They can be run even faster when the optimizer can also reason over known ODs to infer new ones. Order dependencies can be declared as integrity constraints, and they can be detected automatically for many types of SQL functions and algebraic expressions. We present optimization techniques using ODs for queries that involve join, order by, group by, partition by, and distinct. Essentially, ODs can further exploit interesting orders to eliminate or simplify potentially expensive sorts in the query plan. We evaluate these techniques over our implementation in IBM R ° DB2 R ° V10 using the TPC-DS R ° benchmark schema and some IBM customer inspired queries. Our experimental results demonstrate a significant performance gain. We additionally devise an algorithm for testing logical implication for ODs which is polynomial over the size of the set of given ODs. We show that the inference algorithm which we have implemented in DB2 is sound and complete over sets of ODs over natural domains. This enables the optimizer to infer useful ODs from known ODs.