Rule engine for query transformation in Starburst and IBM DB2 C/S DBMS

Abstract

The complexity of queries in relational DBMSs is increasing particularly in the decision support area and interactive client server environments. This calls for a more powerful and flexible optimization of complex queries. In [19] we introduced query rewrite as a distinct query optimization phase mainly targeted to responding to this requirement. This approach has enabled us to extensively enrich the optimization rules in our system. Further, it has made it easier to incrementally enrich and adapt the system as need arises. Examples of such query optimizations are predicate pushdown, subquery and magic sets transformations, and decorrelating subqueries. In this paper we describe the design and implementation of a rule engine for query rewrite optimization. Each transformation is implemented as a rule which consists of a pair of rule condition and action [19]. Rules can be grouped into rule classes for higher efficiency, better understandability and more extensibility. The rule engine has a number of novelties in that it supports a full spectrum of control - from totally data-driven to totally procedural. Furthermore, it incorporates a budget control scheme for controlling the resources taken for query optimization as well as guaranteeing the termination of rule execution. The rule engine and a suite of query rewrite rules have been implemented in Starburst relational DBMS prototype and a significant portion of this technology has been integrated into IBM DB2 Common Server relational DBMS.