Handheld and embedded devices are becoming increasingly popular and their uses are more versatile. Applications on these devices often need storing, retrieving and synchronizing of data. IBM DB2 Everyplace is a high performance small footprint DBMS that is targeted at this market segment. The authors describe the overall architecture, features and several design considerations.

The complexity of queries in relational DBMSs is increasing, particularly in the decision support area and interactive client sewer environments. This calls for a more powerful and flexible optimization of complex queries. H. Pirahesh et al. (1992) 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 subquery. 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. 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.

Complex queries used in decision support applications use multiple correlated subqueries and table expressions, possibly across several levels of nesting. It is usually inefficient to directly execute a correlated query; consequently, algorithms have been proposed to decorrelate the query, i.e. to eliminate the correlation by rewriting the query. This paper explains the issues involved in decorrelation, and surveys existing algorithms. It presents an efficient and flexible algorithm called magic decorrelation which is superior to existing algorithms both in terms of the generality of application, and the efficiency of the rewritten query. The algorithm is described in the context of its implementation in the Starburst Extensible Database System, and its performance is compared with other decorrelation techniques. The paper also explains why magic decorrelation is not merely applicable, but crucial in a parallel database system.

Magic sets rewriting is a well-known optimization heuristic for complex decision-support queries. There can be many variants of this rewriting even for a single query, which differ greatly in execution performance. We propose cost-based techniques for selecting an efficient variant from the many choices.Our first contribution is a practical scheme that models magic sets rewriting as a special join method that can be added to any cost-based query optimizer. We derive cost formulas that allow an optimizer to choose the best variant of the rewriting and to decide whether it is beneficial. The order of complexity of the optimization process is preserved by limiting the search space in a reasonable manner. We have implemented this technique in IBM's DB2 C/S V2 database system. Our performance measurements demonstrate that the cost-based magic optimization technique performs well, and that without it, several poor decisions could be made.Our second contribution is a formal algebraic model of magic sets rewriting, based on an extension of the multiset relational algebra, which cleanly defines the search space and can be used in a rule-based optimizer. We introduce the multiset θ-semijoin operator, and derive equivalence rules involving this operator. We demonstrate that magic sets rewriting for non-recursive SQL queries can be modeled as a sequential composition of these equivalence rules.

A stream processing approach for temporal query processing and optimization is discussed. Given properly sorted data, the implementation of temporal joins and semijoins as stream processors can be very effective. Also discussed are the tradeoffs among sort orders, the amount of local workspace, and multiple scans over input streams; in particular, the authors are interested in the effect of sort ordering on the local workspace. They present stream processing algorithms for various temporal joins and semijoins, and their workspace requirements for various data sort orderings. Finally, it is shown how semantic query optimization can play an important and natural role in optimization of temporal queries.>