Modern database systems such as IBM Db2 have many configurable parameters (“knobs”) which must be precisely adjusted (“tuned”) to ensure optimal workload performance. Manual tuning of these settings is challenging, even for seasoned experts. We introduce the design of, and a demonstration plan for, Db2une, an automated, query-aware tuning system employing deep-learning techniques to enhance performance while also conserving resources. We showcase how Db2une interactively tunes data systems to boost performance, and how its query representation model, QBERT, aids users in understanding the query plans generated from complex analytical workloads.

Modern database systems, such as IBM Db2, rely on cost-based optimizers to improve workload performance. However, their decision-making processes are difficult to interpret. Tuning them for specific workloads remains challenging due to their complexity and numerous configuration options. Automatic tuning tools often rely on black-box machine-learning models, which lack interpretability, hindering expert trust and debugging. We present GEX, a system that provides interpretable insights into database optimizer behavior using explainable AI techniques. By employing saliency maps generated from surrogate models, GEX guides experts in system tuning tasks such as statistical view creation, configuration parameter adjustment, and query rewrite. Our experimental results demonstrate that GEX enhances performance and ensures transparency, addressing key challenges in data systems tuning.

Query optimizers in RDBMSs search for execution plans expected to be optimal for given queries. They use parameter estimates, often inaccurate, and make assumptions that may not hold in practice. Consequently, they may select plans that are suboptimal at runtime, if estimates and assumptions are not valid. Therefore, they do not sufficiently support robust query optimization. Using ML to improve data systems has shown promising results for query optimization. Inspired by this, we propose Robust Query Optimizer, (Roq), a holistic framework based on a risk-aware learning approach. Roq includes a novel formalization of the notion of robustness in the context of query optimization and a principled approach for its quantification and measurement based on approximate probabilistic ML. It also includes novel strategies and algorithms for query plan evaluation and selection. Roq includes a novel learned cost model that is designed to predict the cost of query execution and the associated risks and performs query optimization accordingly. We demonstrate that Roq provides significant improvements in robust query optimization compared with the state-of-the-art.

Join order selection is a sub-field of query optimization that aims to find the optimal join order for an SQL query with the minimum cost. The challenge lies in the exponentially growing search space as the number of tables increases, making exhaustive enumeration impractical. Traditional optimizers use static heuristics to prune the search space, but they often fail to adapt to changes or improve based on feedback from the DBMS. Recent research addresses these limitations with Deep Reinforcement Learning (DRL), allowing models to use feedback to dynamically search for better join orders and enhance performance over time. Existing research primarily focuses on capturing join order sequences and their representations at various levels, with limited comparative analysis of reinforcement learning methods. In this paper, we propose a novel framework, which integrates Graph Neural Networks (GNN), Tree-structured Long Short-Term Memory (Tree-LSTM), and dueling-DQN. We conduct a series of experiments to demonstrate the potential for improvement in DRL methods.

Query optimizers are an essential component of database management systems (DBMSs) as they search for an execution plan that is expected to be optimal for a given query. However, they commonly use parameter estimates that are often inaccurate and make assumptions that may not hold in practice. Consequently, the optimizer may select sub-optimal execution plans at runtime, when these estimates and assumptions are not valid, which may result in poor query performance. Therefore, query optimizers do not adequately support the robustness of the database system. In this tutorial, we explore the notion of robustness in the context of query optimization, as well as how it is evaluated or even further supported. Firstly, we provide a comprehensive definition for the notion of robustness in this context that accounts for risks associated with execution plans and inaccurate parameter estimates as well as the limitations of the cost models. Next, we review the approaches proposed in the literature to address the issue of robustness, including techniques that rely on query re-optimization, discovering parameters, quantifying robustness, as well as recent techniques that employ machine learning. We focus on comparing traditional cost-model-based methods with modern ML-based techniques in terms of their ability to tackle the challenge of robustness in query optimization. Finally, we discuss the limitations and gaps in the current literature and provide some recommendations for future research directions.

Modern database systems including IBM Db2 have numerous parameters, "knobs," that require precise configuration to achieve optimal workload performance. Even for experts, manually "tuning" these knobs is a challenging process. We present Db2une, an automatic query-aware tuning system that leverages deep learning to maximize performance while minimizing resource usage. Via a specialized transformer-based query-embedding pipeline we name QBERT, Db2une generates context-aware representations of query workloads to feed as input to a stability-oriented, on-policy deep reinforcement learning model. In Db2une, we introduce a multi-phased, database meta-data driven training approach---which incorporates cost estimates, interpolation of these costs, and database statistics---to efficiently discover optimal tuning configurations without the need to execute queries. Thus, our model can scale to very large workloads, for which executing queries would be prohibitively expensive. Through experimental evaluation, we demonstrate Db2une's efficiency and effectiveness over a variety of workloads. We compare it against the state-of-the-art query-aware tuning systems and show that the system provides recommendations that surpass those of IBM experts.

Nowadays, data systems, including IBM Db2 have dozens of knobs (configuration parameters). These knobs significantly affect the runtime of queries. We present the design of and a demonstration plan for a query-informed, efficient tuning system, BLUTune, which utilizes deep reinforcement learning to tune configurations. Using synthetic and real workloads, we demonstrate how BLUTune can help users to understand the semantics of analytical queries, including their execution plans, and interactively tune data systems to improve performance.

Modern data systems such as IBM Db2 have hundreds of system configuration parameters, ''knobs", which heavily influence the performance of business queries. Manual configuration, ''tuning," by experts is painstaking and time consuming. We propose a query informed tuning system called BLUTune which uses machine learning (ML)-deep reinforcement learning based on advantage actor critic neural networks-to tune configurations within defined resource constraints. We translate high-dimensional query execution plans (QEPs) into a low-dimensional embedding space (QEP2Vec) for input into the ML models. To scale to complex and large workloads, we bootstrap the training process through transfer learning. We first train our model based on the estimated cost of queries; we then fine-tune it based on actual query execution times. We demonstrate by an experimental study over various synthetic and real-world workloads BLUTune's efficiency and effectiveness.

Query optimization has long been fundamental for database systems. There are cracks in the edifice, however, as the complexity of modern query workloads outpace what database systems can manage well. Automatic tools are needed for database vendors, such as IBM with Db2, to help customers troubleshoot their performance problems, as manual troubleshooting is painstaking. To manage complex and large workloads, we develop a distributed system called dGALO that learns recurring problem patterns in query plans over workloads. dGALO employs these problem patterns to build a RDF-based, SPARQL-queried knowledge-base of plan-rewrite remedies. We illustrate a distributed implementation of dGALO on Apache Spark with efficient partitioning strategies for load balancing. The system employs additional pruning strategies via clustering, which yields a fine-grained trade off between runtime and accuracy. dGALO uses its knowledge-base to re-optimize queries, often to dramatic effect, and is a valuable tool for the development team to refine the optimizer with new techniques. We demonstrate by an experimental study over the TPC-DS benchmark the efficiency and effectiveness of our techniques.

Query performance problem determination is usually performed manually in consultation with experts through the analysis of query plans. However, this is an excessively time consuming, human error-prone, and costly process. GALO is a novel system that automates this process. The tool automatically learns recurring problem patterns in query plans over workloads in an offline learning phase to build a knowledge base of plan rewrite remedies. GALO's knowledge base is built on RDF and SPARQL, which is well-suited for manipulating and querying over SQL query plans, which are graphs themselves. It then uses the knowledge base online to re-optimize queries queued for execution to improve performance, often quite dramatically.

Query optimization is a hallmark of database systems. When an SQL query runs more expensively than is viable or warranted, determination of the performance issues is usually performed manually in consultation with experts through the analysis of query's execution plan (QEP). However, this is an excessively time consuming, human error-prone, and costly process. GALO is a novel system that automates this process. The tool automatically learns recurring problem patterns in query plans over workloads in an offline learning phase, to build a knowledge base of plan-rewrite remedies. It then uses the knowledge base online to re-optimize queries often quite drastically. GALO's knowledge base is built on RDF and SPARQL, W3C graph database standards, which is well suited for manipulating and querying over SQL query plans, which are graphs themselves. GALO acts as a third-tier of re-optimization, after query rewrite and cost-based optimization, as a query plan rewrite . For generality, the context of knowledge base problem patterns, including table and column names, is abstracted with canonical symbol labels. Since the knowledge base is not tied to the context of supplied QEPs, table and column names are matched automatically during the re-optimization phase. Thus, problem patterns learned over a particular query workload can be applied in other query workloads. GALO's knowledge base is also an invaluable tool for database experts to debug query performance issues by tracking to known issues and solutions as well as refining the optimizer with new tuned techniques by the development team. We demonstrate an experimental study of the effectiveness of our techniques over synthetic TPC-DS and real IBM client query workloads.

query performance problem determination is often performed by analyzing query execution plans (QEPs) in addition to other performance data. As the query workloads that organizations run have become larger and more complex, analyzing QEPs manually even by experts has become a very time consuming and cumbersome task. Most performance diagnostic tools help with identifying problematic queries and most query tuning tools address a limited number of known problems and recommendations. We present the OptImatch system that offers a way to (a) look for varied user defined problem patterns in QEPs and (b) automatically get recommendations from an expert provided and user customizable knowledge base. Existing approaches do not provide the ability to perform workload analysis with flexible user defined patterns, as they lack the ability to impose a proper structure on QEPs. We introduce a novel semantic web system that allows a relatively naive user to search for arbitrary patterns and to get solution recommendations stored in a knowledge base. Our methodology includes transforming a QEP into an RDF graph and transforming a GUI based user-defined pattern into a SPARQL query through handlers. The SPARQL query is matched against the abstracted RDF graph, and any matched portion of the abstracted RDF graph is relayed back to the user. With the knowledge base, the OptImatch system automatically scans and matches interesting stored patterns in a statistical way as appropriate and returns the corresponding recommendations. Although the knowledge base patterns and solution recommendations are not in the context of the user supplied QEPs, the context is adapted automatically through the handler tagging interface. We test the performance and scalability of our framework to demonstrate its efficiency using a real query workload. We also perform a user study to quantify the benefits of the approach in terms of precision and time compared to manually searching for patterns.

Query performance problem determination is usually performed by analyzing query execution plans (QEPs). Analyzing complex QEPs is excessively time consuming and existing automatic problem determination tools do not provide ability to perform analysis with flexible user-defined problem patterns. We present the novel OptImatch system that allows a relatively naive user to search for patterns in QEPs and get recommendations from an expert and user customizable knowledge base. Our system transforms a QEP into an RDF graph. We provide a web graphical interface for the user to describe a pattern that is transformed with handlers into a SPARQL query. The SPARQL query is matched against the abstracted RDF graph and any matched parts of the graph are relayed back to the user. With the knowledge base the system automatically matches stored patterns to the QEPs by adapting dynamic context through developed tagging language and ranks recommendations using statistical correlation analysis.

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.

Dependencies play an important role in databases. We study order dependencies (ODs)--and unidirectional order dependencies (UODs), a proper sub-class of ODs--which describe the relationships among lexicographical orderings of sets of tuples. We consider lexicographical ordering, as by the order-by operator in SQL, because this is the notion of order used in SQL and within query optimization. Our main goal is to investigate the inference problem for ODs, both in theory and in practice. We show the usefulness of ODs in query optimization. We establish the following theoretical results: (i) a hierarchy of order dependency classes; (ii) a proof of co-NP-completeness of the inference problem for the subclass of UODs (and ODs); (iii) a proof of co-NP-completeness of the inference problem of functional dependencies (FDs) from ODs in general, but demonstrate linear time complexity for the inference of FDs from UODs; (iv) a sound and complete elimination procedure for inference over ODs; and (v) a sound and complete polynomial inference algorithm for sets of UODs over restricted domains.

Data warehouses are repositories of electronically stored data which are designed to support reporting and analysis. The analysis of historical data often involves aggregation over time. Thus, time is critical in the design of a data warehouse. We describe novel techniques for storing date information and optimization of queries that reference the date dimension. We show how to embed intelligence into the date key and how to exploit monotonic dependencies. We present the value of these techniques for the improvement of performance when combined with partitioning and indexes. We evaluate these techniques on our prototype implemented in IBM® DB2® V9.7 over the current draft version of the TPC-DS benchmark.

Many scenarios impose a heavy update load on B-tree indexes in modern databases. A typical case is when B-trees are used for indexing all the keywords of a text field. For example upon the insertion of a new text record (e.g. a new document arrives), a barrage of new keywords has to be inserted into the index causing many random disk I/Os and interrupting the normal operation of the database. The common approach has been to collect the updates in a separate structure and then perform a batch update of the index. This update "freezes" the database. Many applications, however, require the immediate availability of the new updates without any interruption of the normal database operation. In this paper we present a novel online B-tree update method based on a new buffering data structure we introduce - Dynamic Bucket Tree (DBT). The DBT-buffer serves as a differential index for new updates. The grouping of keys in DBT-buffer is based on the longest common prefixes (LCP) of their binary representations. The LCP is used as a measure of the locality of keys to be transferred to the main B-tree. Our online update system does not slow down concurrent user transactions or lead to degradation of search performance. Experiments confirm that our DBT buffer can be efficiently used for online updates of text fields. As such it represents an effective solution to the notorious problem of handling updates to an Inverted Index.

There is much effort to develop comprehensive support for the storage and querying of XML data in database management systems. The major developers have extended their systems to handle XML data natively. These have the advantage over stand-alone XML database systems that relational and XML data can be queried mutually. Indeed, recent SQL standards specify means to query relational and XML data together (called SQL/XML). These systems also now support XQuery, in addition to SQL. It is thus possible to mix the processing of relational and XML data via either query language. While there has been significant progress in efficient native storage systems for XML, there remain numerous challenges to handle efficiently queries over XML. There are efforts to adapt the strong optimization techniques used for relational ("SQL") queries for XML (and mixed) queries as well. One such technique, the materialized view, has been well studied, and well adopted, over the last decade as an effective technique for optimizing relational queries. Our work extends the use of materialized views for SQL/XML, and could be applied to XQuery. Within IBM DB2 9 (Viper), we implement query rewrite rules that enable the use of materialized views in the evaluation of queries over XML. % (We enable views over queries that employ XMLTable.) To accomplish this, it was necessary to extend the existing query matching and compensation framework in DB2 with new functionality. We consider what types of query rewrites based on XMLTable are possible, and which are feasible. We present a linear-time algorithm to determine the locality (self-containment) of XPath expressions within a schema-unaware environment, which we have implemented. We demonstrate the efficacy of our techniques via an experimental evaluation over a representative suite of SQL/XML queries and materialized views, executed over our DB2 prototype.

Database statistics are crucial to cost-based optimizers for estimating the execution cost of a query plan. Using traditional basic statistics on base tables requires adopting unrealistic assumptions to estimate the cardinalities of intermediate results, which usually causes large estimation errors that can be several orders of magnitude. Modern commercial database systems support statistical or sample views, which give more accurate statistics on intermediate results and query sub-expressions. While previous research focused on creating and maintaining these advanced statistics, only little effort has been done towards automatically recommending the most beneficial statistical views to construct. In this paper, we present StatAdvisor , a system for recommending statistical views for a given SQL workload. The StatAdvisor addresses the special characteristics of statistical views with respect to view matching and benefit estimation, and introduces a novel plan-based candidate enumeration method, and a benefit-based analysis to determine the most useful statistical views. We present the basic concepts, architecture, and key features of StatAdvisor , and demonstrate its validity and benefits through an extensive experimental study using a prototype that we built in the IBM® DB2® database system as part of the DB2 Design Advisor tools.

IBM® DB2® 9 is a truly hybrid commercial database system that combines XML and relational data. It provides native support for XML storage and indexing, and query evaluation support for XQuery. By building a hybrid system, the designers of DB2 9 were able to use the existing SQL query evaluation and optimization techniques to develop similar methods for XQuery. However, SQL and XQuery are sufficiently different that new optimization techniques can and are being developed in the new XQuery domain. This paper describes a few such techniques, all based on static rewrites of XQuery expressions.

XML database systems are expected to handle increasingly complex queries over increasingly large and highly structured XML databases. An important problem that needs to be solved for these systems is how to choose the best set of indexes for a given workload. In this paper, we present an XML Index Advisor that solves this XML index recommendation problem and has the key characteristic of being tightly coupled with the query optimizer. We rely on the optimizer to enumerate index candidates and to estimate the benefit gained from potential index configurations. We expand the set of candidate indexes obtained from the query optimizer to include more general indexes that can be useful for queries other than those in the training workload. To recommend an index configuration, we introduce two new search algorithms. The first algorithm finds the best set of indexes for the specific training workload, and the second algorithm finds a general set of indexes that can benefit the training workload as well as other similar workloads. We have implemented our XML Index Advisor in a prototype version of IBMregDB2reg9, which supports both relational and XML data, and we experimentally demonstrate the effectiveness of our advisor using this implementation.

XML database systems are expected to handle increasingly complex queries over increasingly large and highly structured XML databases. An important problem that needs to be solved for these systems is how to choose the best set of indexes for a given workload. We have developed an XML Index Advisor that solves this XML index recommendation problem and is tightly coupled with the query optimizer of the database system. We have implemented our XML Index Advisor for DB2. In this demonstration we showcase the new query optimizer modes that we added to DB2, the index recommendation process, and the effectiveness of the recommended indexes.

Tools for generating test queries for databases do not explicitly take into account the actual data in the database. As a consequence, such tools cannot guarantee suitable coverage of test cases commonly required for database testing. In this paper, we investigate the problem of generating queries that satisfy cardinality constraints on intermediate subexpressions when executed on a given test database. Such queries are required to test the performance of a database system under different operating conditions.

Traditional DBMSs decouple statistics collection and query optimization both in space and time. Decoupling in time may lead to outdated statistics. Decoupling in space may cause statistics not to be available at the desired granularity needed to optimize a particular query, or some important statistics may not be available at all. Overall, this decoupling often leads to large cardinality estimation errors and, in consequence, to the selection of suboptimal plans for query execution. In this paper, we present JITS, a system for proactively collecting query-specific statistics during query compilation. The system employs a lightweight sensitivity analysis to choose which statistics to collect by making use of previously collected statistics and database activity patterns. The collected statistics are materialized and incrementally updated for later reuse. We present the basic concepts, architecture, and key features of JITS. We demonstrate its benefits through an extensive experimental study on a prototype inside the IBM DB2 engine.

Selecting a set of views for materialization is a required task in many current database and data warehousing applications including the design of a data warehouse, and the maintenance of multiple materialized views. The selected views can be materialized permanently or transiently depending on the specific view selection problem. The view selection algorithms are expensive due to the size of the search space of the problem.In this paper we propose an approach for generating candidate views for materialization for view selection problems based on the definition of the input queries. We also provide rewritings of the input queries using the generated candidate views. In generating candidate views, we do not apply costbased techniques but we try to maximize the operations in the views. Subsequently, view selection algorithms can exploit problem dependent cost functions to choose among the generated candidate views. Our approach is not restricted to a specific view selection problem. Compared to a previous one, it generates views that involve more relation occurrences (or operations) and can reduce the size of the search space which can be very large. We implement our approach and we report some experimental evaluation with comparison to previous works.

A materialized view or Materialized Query Table (MQT) is an auxiliary table with precomputed data that can be used to significantly improve the performance of a database query. AMaterialized Query Table Advisor (MQTA) is often used to recommend and create MQTs. The state-of-the-art MQTA works in a standalone database server where MQTs are placed on the same server as that in which the base tables are located. The MQTA does not apply to a federated or scaleout scenario in which MQTs need to be placed on other servers close to applications (i.e. a frontend database server) for offloading the workload on the backend database server. In this paper, we propose a Data Placement Advisor (DPA) and load balancing strategies for multi-tiered database systems. Built on top of the MQTA, DPA recommends MQTs and advises placement strategies for minimizing the response time for a query workload. To demonstrate the benefit of the data placement advising, we implemented a prototype of DPA that works with theMQTA in the IBM® DB2® Universal Database^TM (DB2 UDB) and the IBM WebSphere® Information Integrator (WebSphere II). The evaluation results showed substantial improvements of workload response times when MQTs are intelligently recommended and placed at a frontend database server subject to space and load characteristics for TPC-H and OLAP type workloads.

The use of evolutionary algorithms has been proposed as a powerful random search strategy to solve the join order problem. Specifically, genetic programming used in query optimization has been proposed as an alternative to the limitations of dynamic programming with large join queries. However, very little is known about the impact and behavior of the genetic operations used in this type of algorithms. In this paper, we present an analysis that helps us to understand the effect of these operations during the optimization execution. Specifically, we study five different aspects: the age of the members in the population in terms of generations, the number of query execution plans (QEP) discarded without producing new offsprings, the average QEP life time in generations, the efficiency of the genetic operations and the evolution of the best cost. All in all, our analysis allows us to understand the impact of crossovers compared to mutation operations and the dynamically changing effects of these operations.

Accurate estimation of the sizes of intermediate query results (cardinality estimation) is of critical importance to plan costing in query optimization. The common practice in current commercial database systems such as IBM DB2 Universal Database (DB2 UDB) is to derive the cardinality estimates from base-table statistics. However, this approach often suffers from simplifying yet unrealistic assumptions that have to be made about the underlying data (for example, different attributes are independently distributed).Ways for exploiting statistics on query expressions (or, statistics on views, or SITs) have been proposed to improve the accuracy of cardinality estimation. We propose a novel method for efficient computation of SITs for joins. In particular, we are concerned with statistics on join queries involving large fact tables and relatively small dimension tables. Rather than materializing the views, we make use of the frequency statistics that are available on the fact tables to obtain an approximate estimate of the statistics on various attributes in the join results. The dimension tables are generally much smaller than the fact table, and therefore we can afford to closely examine the dimension table, while at the same time avoid accessing the fact table. By closely examining the dimension table, we are able to capture the correlations between the attributes in the dimension table as well as the skew and domain range of the fact table join column values. This leads to reasonably accurate statistics on the join result. We prototyped this idea as a module on top of DB2 UDB, and our experience shows that employment of this technique results in a very significant speed-up in the computation of SITs, at the expense of only slight degradation in accuracy compared with the full-materialization method.

Accurately and efficiently estimating the number of distinct values for some attribute(s) or sets of attributes in a data set is of critical importance to many database operations, such as query optimization and approximation query answering. Previous work has focused on the estimation of the number of distinct values for a single attribute and most existing work adopts a data sampling approach. This paper addresses the equally important issue of estimating the number of distinct value combinations for multiple attributes which we call COLSCARD (for COLumn Set CARDinality). It also takes a different approach that uses existing statistical information (e.g., histograms) available on the individual attributes to assist estimation. We start with cases where exact frequency information on individual attributes is available, and present a pair of lower and upper bounds on COLSCARD that are consistent with the available information, as well as an estimator of COLSCARD based on probability. We then proceed to study the case where only partial information (in the form of histograms) is available on individual attributes, and show how the proposed estimator can be adapted to this case. We consider two types of widely used histograms and show how they can be constructed in order to obtain optimal approximation. An experimental evaluation of the proposed estimation method on synthetic as well as two real data sets is provided.

Executing ad hoc queries against large databases can be prohibitively expensive. Exploratory analysis of data may not require exact answers to queries, however: results based on sampling the data are often satisfactory. Supporting sampling as a primitive SQL operator turns out to be difficult because sampling does not commute with many SQL operators.In this paper, we describe an implementation in IBM® DB2® Universal Database (UDB) of a sampling operator that commutes with some SQL operators. As a result, the query with the sampling operator always returns a random sample of the answers and in many cases runs faster than it would have without such an operator.

Outerjoins are an important class of joins and are widely used in various kinds of applications. It is challenging to optimize queries that contain outerjoins because outerjoins do not always commute with inner joins. Previous work has studied this problem and provided techniques that allow certain reordering of the join sequences. However, the optimization of outerjoin queries is still not as powerful as that of inner joins.An inner join query can always be canonically represented as a sequence of Cartesian products of all relations, followed by a sequence of selection operations, each applying a conjunct in the join predicates. This canonical abstraction is very powerful because it enables the optimizer to use any join sequence for plan generation. Unfortunately, such a canonical abstraction for outerjoin queries has not been developed. As a result, existing techniques always exclude certain join sequences from planning, which can lead to a severe performance penalty.Given a query consisting of a sequence of inner and outer joins, we, for the first time, present a canonical abstraction based on three operations: outer Cartesian products, nullification, and best match. Like the inner join abstraction, our outerjoin abstraction permits all join sequences, and preserves the property of both commutativity and transitivity among predicates. This allows us to generate plans that are very desirable for performance reasons but that couldn't be done before. We present an algorithm that produces such a canonical abstraction, and a method that extends an inner-join optimizer to generate plans in an expanded search space. We also describe an efficient implementation of the best match operation using the OLAP functionalities in SQL:1999. Our experimental results show that our technique can significantly improve the performance of outerjoin queries.

Database queries often take the form of correlated SQL queries. Correlation refers to the use of values from the outer query block to compute the inner subquery. This is a convenient paradigm for SQL programmers and closely mimics a function invocation paradigm in a typical computer programming language. Queries with correlated subqueries are also often created by SQL generators that translate queries from application domain-specific languages into SQL. Another significant class of queries that use this correlated subquery form is that involving temporal databases using SQL. Performance of these queries is an important consideration particularly in large databases. Several proposals to improve the performance of SQL queries containing correlated subqueries can be found in database literature. One of the main ideas in many of these proposals is to suitably decorrelate the subquery internally to avoid a tuple-at-a-time invocation of the subquery. Magic decorrelation is one method that has been successfully used. Another proposal is to cache the portion of the subquery that is invariant with the changing values of the outer query block. What we propose here is a new technique to handle some typical correlated queries. We go a step further than to simply decorrelate the subquery. By making use of extended window aggregation capabilities, we eliminate redundant access to common tables referenced in the outer query block and the subquery. This technique can be exploited even for non-correlated subqueries. It is possible to get a huge boost in performance for queries that can exploit this technique, which we call WinMagic. This technique was implemented in IBM® DB2® Universal Database" Version 7 and Version 8. In addition to improving DB2 customer queries that contain aggregation subqueries, it has provided significant improvements in a number of TPCH benchmarks that IBM has published since late in 2001.

The traditional role of integrity constraints is to protect the integrity of data, but integrity constraints can and do play other roles in databases; for example, they can be used for query optimization. In this role, they do not need to model the domain; it is sufficient that they describe regularities that are true about the data currently stored in a database. In this paper, we describe two algorithms for finding such regularities (in the syntactic form of check constraints) and discuss some of their applications in DB2. In particular, we show their use in query optimization.

Query optimizers nowadays draw upon many sources of information about the database to optimize queries. They employ runtime statistics in cost-based estimation of query plans. They employ integrity constraints in the query rewrite process. Primary and foreign key constraints have long played a role in the optimizer, both for rewrite opportunities and for providing more accurate cost predictions. More recently, other types of integrity constraints are being exploited by optimizers in commercial systems, for which certain semantic query optimization techniques have now been implemented.