Skip Navigation
York U: Redefine the PossibleHOME | Current Students | Faculty & Staff | Research | International
Search »FacultiesLibrariesCampus MapsYork U OrganizationDirectorySite Index
Future Students, Alumni & Visitors
2012 Technical Reports

Business-Intelligence Queries in DB2 with Order Dependencies

Jaroslaw Szlichta, Parke Godfrey, Jarek Gryz, Wenbin Ma, Weinan Qiu and Calisto Zuzarte

Technical Report CSE-2012-04

York University

July 24 2012


Abstract-Business-intelligence queries often involve SQL functions and algebraic expressions. There can be clear semanticrelationships 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 has come to be called an order dependency (OD). Queries can be ran faster when the query optimizer uses order dependencies. They can be ran 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 inferred 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 and eliminate or simplify potentially expensive sorts in the query plan. We evaluate these techniques over our implementation in IBM DB2 V10 using TPC-DS benchmark. 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 is sound and complete over sets of ODs over natural domains. This enables the optimizer to infer useful ODs from known ODs.

Download paper in PDF format.

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.