International Business Machines Corporation

Volker Gerhard Markl

Vijayshankar Raman

Peter Haas

Nimrod Megiddo

Guy Maring Lohman

Marcel Kutsch

Stephan Eberhard Ewen

Calisto Paul Zuzarte

Sam Sampson Lightstone

Holger Kache

Ivan Popivanov

Tam Minh Dai Tran

Ashraf Aboulnaga

Mokhtar Kandil

Wei Fan

Ihab Francis Ilyas

Kevin Scott Beyer

David Everett Simmen

Jun Rao

Daniele Costante Zilio

Latha S Colby

Minglong Shao

Paul Geoffrey Brown

Ihab F Ilyas

Quanzhong Li

Julia Stoyanovich

Wing Yan Lau

Amr El-Helw

Fabian Hueske

Ashraf Ismail Aboulnaga

Vijayashankar Raman

Felix Endres

Alberto Lerner

Michael Ortega-Binderberger

Utkarsh Srivastava

Michael Stillger

A method for approximating a validity range for a domain of cardinalities of input to an optimal query plan is provided. Such a validity range is iteratively approximated using a modified Newton-Raphson method to find roots of cost functions for optimal and alternative query plans, respectively. The Newton-Raphson method is combined with a method of incrementing roots of cost functions, known as input cardinalities, such that discontinuous and non-differentiable points in cost functions are avoided. In this manner, input cardinalities remain within a domain for which a valid range can be specified. Additionally, a robustness measure is determined by a sensitivity analysis performed on an approximated validity range. Using a robustness measure provided by a sensitivity analysis and resultant validity range and, query plan sub-optimality detection is simplified, re-optimization is selectively triggered, and robustness information is provided to a system or user performing corrective actions.

Determining validity ranges of query plans based on suboptimality

A method, system, and computer program product for managing database statistics are provided. The method, system, and computer program product provide for receiving a query for optimizing, collecting statistics specific to the query prior to generating any access plans for executing the query, and generating an access plan for executing the query based on the collected statistics.

Management of interesting database statistics

There is disclosed a data processing system implemented method, a data processing system, and an article of manufacture for directing a data processing system to maintain a database table associated with an initial maintenance scheduling interval. The data processing system implemented method includes selecting a randomizing factor, and selecting a new maintenance scheduling interval for the database table based on the initial maintenance scheduling interval and the selected randomizing factor.

Method, system and program for prioritizing maintenance of database tables

A method for consistent selectivity estimation based on the principle of maximum entropy (ME) is provided. The method efficiently exploits all available information and avoids the bias problem. In the absence of detailed knowledge, the ME approach reduces to standard uniformity and independence assumptions. The disclosed method, based on the principle of ME, is used to improve the optimizer's cardinality estimates by orders of magnitude, resulting in better plan quality and significantly reduced query execution times.

Selectivity estimation for conjunctive predicates in the presence of partial knowledge about multivariate data distributions

A method and system for automatically determining optimization frequencies of queries having one or more parameter markers. Execution plans for a query are generated and each plan is associated with one or more bind value sets. An optimization frequency is selected based on differences between pairs of execution costs where one execution cost of a pair is a cost of executing the query with a bind value set via a first execution plan and the other execution cost of the pair is a cost of optimally executing the query with the bind value set via a second execution plan. The differences are based on maximum selectivity or cardinality distances associated with the bind value sets. If none of the differences exceeds a predefined value, the query is optimized once. If at least one of the differences exceeds the predefined value, the query is reoptimized each time the query is executed.

Automatically determining optimization frequencies of queries with parameter markers

A method and system for automatically and adaptively determining query execution plans for parametric queries. A first classifier trained by an initial set of training points is generated. A query workload and/or database statistics are dynamically updated. A new set of training points is collected off-line. Using the new set of training points, the first classifier is modified into a second classifier. A database query is received at a runtime subsequent to the off-line phase. The query includes predicates having parameter markers bound to actual values. The predicates are associated with selectivities. A mapping of the selectivities into a plan determines the query execution plan. The determined query execution plan is included in an augmented set of training points, where the augmented set includes the initial set and the new set.

Automatically and adaptively determining execution plans for queries with parameter markers

A way for progressively refining a query execution plan during query execution in a federated data system is provided. Re-optimization constraints are placed in the query execution plan during query compilation. When a re-optimization constraint is violated during query execution, a model of the query execution plan is refined using a partially executed query to form a new query execution plan. The new query execution plan is compiled. The compiled new query execution plan is executed.

Progressive refinement of a federated query plan during query execution

An autonomic tool that supervises the collection and maintenance of database statistics for query optimization by transparently deciding what statistics to gather, when and in what detail to gather them. Feedback from data-driven statistics collection is simultaneously combined with feedback from query-driven learning-based statistics collection, to better process both rapidly changing data and data that is queried frequently. The invention monitors table activity and decides if the data in a table has changed sufficiently to require a refresh of invalid statistics. The invention determines if the invalidity is due to correlation between purportedly independent data, outdated statistics, or statistics that have too few frequent values. Tables and column groups are ranked in order of statistical invalidity, and a limited computational budget is prioritized by ranking subsequent gathering of improved statistics. Multiple tables can have their statistics refreshed over time, and the maintenance effort is concentrated on the most important tables.

System and method for updating database statistics according to query feedback

A method is disclosed for executing a predetermined query plan, the method comprising: executing a portion of the query plan; providing a reordered query plan; comparing ranking metrics for the query plans; and executing the query plan having the lower ranking metric.

Adaptively reordering joins during query execution

A method and system for query problem determination have been disclosed. The method includes receiving a database query; creating a query execution plan for the database query comprising a plurality of query plan operators; and executing the query execution plan, wherein a progress indicator is displayed for each query plan operator. The system includes a query progress monitor, which collects progress information for each query plan operator during the execution of the query execution plan. This progress information is then communicated to a query progress visualizer and a query progress analyzer, which graphically displays the progress information as a progress indicator for each query plan operator and performs debugger type operations, respectively. In this manner, information concerning the progress of the query execution is provided at a query operator level, such that the information may be used to more efficiently debug any problems with the query.

SQL query problem determination tool

A method, computer program product, and system for managing statistical views in a database system are provided. The method, computer program product, and system provide for collecting data relating to optimization and execution of a workload in the database system and automatically generating a set of one or more statistical views based on the collected optimization and execution data.

Management of statistical views in a database system

A system and method of discovering dependencies between relational database column pairs and application of discoveries to query optimization is provided. For each candidate column pair remaining after simultaneously generating column pairs, pruning pairs not satisfying specified heuristic constraints, and eliminating pairs with trivial instances of correlation, a random sample of data values is collected. A candidate column pair is tested for the existence of a soft functional dependency (FD), and if a dependency is not found, statistically tested for correlation using a robust chi-squared statistic. Column pairs for which either a soft FD or a statistical correlation exists are prioritized for recommendation to a query optimizer, based on any of: strength of dependency, degree of correlation, or adjustment factor; statistics for recommended columns pairs are tracked to improve selectivity estimates. Additionally, a dependency graph representing correlations and dependencies as edges and column pairs as nodes is provided.

Detecting correlation from data

A method and system for accelerating execution of a query on a federated database system. The federated database system is associated with an external data source, which is used by the query. The query is performed based upon a query execution plan. The method and system include generating an optimizer query for the external data source utilized by the query. The optimizer query is based on the query and obtains data related to the external data source. The method and system further include providing the optimizer query to the external data source and collecting at least one resultant from the optimizer query for use in generating a future query execution plan.

Method and system for providing a learning optimizer for federated database systems

The present invention provides a method of selectivity estimation in which preprocessing steps improve the feasibility and efficiency of the estimation. The preprocessing steps are partitioning (to make iterative scaling estimation terminate in a reasonable time for even large sets of predicates), forced partitioning (to enable partitioning in case there are no 'natural' partitions, by finding the subsets of predicates to create partitions that least impact the overall solution); inconsistency resolution (in order to ensure that there always is a correct and feasible solution), and implied zero elimination (to ensure convergence of the iterative scaling computation under all circumstances). All of these preprocessing steps make a maximum entropy method of selectivity estimation produce a correct cardinality model, for any kind of query with conjuncts of predicates. In addition, the preprocessing steps can also be used in conjunction with prior art methods for building a cardinality model.

Consistent and unbiased cardinality estimation for complex queries with conjuncts of predicates

A novel method is employed for collecting optimizer statistics for optimizing database queries by gathering feedback from the query execution engine about the observed cardinality of predicates and constructing and maintaining multidimensional histograms. This makes use of the correlation between data columns without employing an inefficient data scan. The maximum entropy principle is used to approximate the true data distribution by a histogram distribution that is as 'simple' as possible while being consistent with the observed predicate cardinalities. Changes in the underlying data are readily adapted to, automatically detecting and eliminating inconsistent feedback information in an efficient manner. The size of the histogram is controlled by retaining only the most 'important' feedback.

Growing community of inventors

San Jose, CA, United States of America

Volker Gerhard Markl