International Business Machines Corporation

Monica Sachiye Urata

Mir Hamid Pirahesh

David Everett Simmen

Guy Maring Lohman

Ting Yu Leung

Roberta Jo Cochrane

George Lapis

Eugene Jon Shekita

Richard Sefton Sidle

Tuong Chanh Truong

Calisto Paul Zuzarte

Bruce Gilbert Lindsay

Yang Sun

Bernhard K Schiefer

Markos Zaharioudakis

Mark A Paskin

Swati Vora

A method, apparatus, and article of manufacture for optimizing database queries using a derived summary table, wherein a definition of the summary table is based on a full select statement, including, but not limited to, a derived table involving nested GROUP BY operations and complex HAVING clauses with subqueries or joins, that is materialized in the table and describes how the summary table was derived. A query is analyzed using matching/compensation tests between the query and the definition of the summary table (that is, a query by itself) to determine whether expressions occurring anywhere in the query, but not in the summary table, can be derived using either the content in the summary table alone, or after combining (through some relational operator) the content of the summary table with other base tables, and hence the query is subsumed by or overlaps with the summary table definition.

Analyzing, optimizing and rewriting queries using matching and compensation between query and automatic summary tables

An optimization technique for SQL queries, a program storage device storing the optimization program, and an apparatus for optimizing a query is provided. A query is analyzed to determine whether it includes subselect expressions that return exactly or at most one tuple. If so, the quantifier merger or elimination is performed, if possible, to allow query to perform more efficiently than that of the original query while providing same results. The query is then executed in the computer to efficiently retrieve data from the database.

Method of simplifying and optimizing scalar subqueries and derived tables that return exactly or at most one tuple

An optimization technique for SQL queries, a program storage device storing the optimization program, and an apparatus for optimizing a query is provided. A query is analyzed to determine whether it includes the WHERE clause which contains an &ldquo;EXISTS&rdquo; subquery and a &ldquo;NOT EXISTS&rdquo; subquery, or EXISTS-equivalent subqueries, in Boolean factor. If so, the subsumption test is performed on two subqueries. Then, the compensation predicate is applied to one of them, to perform the QGM transformation of the query. One subquery block is stacked on top of the other subquery block, in order to eliminate one subquery. This procedure allows the transformed query to perform more efficiently than the original query while providing same results. The query is then executed in the computer to efficiently retrieve data from the relational database.

Method of optimizing a query having an existi subquery and a not-exists subquery

A method, apparatus, and article of manufacture for optimizing database queries uses a derived summary table, wherein a definition of the summary table is based on a full select statement that is materialized in the table and describes how the summary table was derived. The summary table definition can be a complex query involving nested GROUP BY operations as well as complex HAVING clauses with subqueries or join operations. A query is analyzed using subsumption tests between the query and the definition of the summary table to determine whether expressions occurring anywhere in the query, but not in the summary table, can be subsumed in the summary table. In performing the query, an expression in the query is subsumed in the summary table when the expression can be re-derived from one or more of the columns of the summary table.

Automatic recognition and rerouting of queries for optimal performance

A relational data base management system includes a query processor that uses a query operator partition property to perform QEP pruning and to ensure that data input to a query operator is partitioned appropriately for the operation. The partition property indicates the group of network nodes across which a table is distributed. The query processor also makes use of partition classes that are designated &ldquo;interesting classes&rdquo; to perform preoptimization planning and query pruning, and to perform look-ahead partitioning based on partition classes that are identified as being of interest to future operations, thereby more efficiently evaluating complex query statements in an MPP, shared-nothing environment.

Method and system for look ahead query evaluation planning based on interesting partition properties

A method, apparatus, and article of manufacture for optimizing database queries using a materialized view for a table referenced in the query, wherein the materialized view has different properties than the referenced table. The materialized view may be replicated across multiple processors of the computer system, so that some or all of the query can be executed in a local fashion wherein there is no data movement required to perform the operations. The materialized view also may be partitioned across multiple processors of the computer system using a different partitioning key than the referenced table. The materialized view may be a vertical and/or horizontal subset of the table, so that only selected columns and/or tuples from the table are present therein. Columns may be added to the materialized view to contain pre-computed results of complex expressions, and indices may be created on the columns of the materialized view.

Query optimization by transparently altering properties of relational tables using materialized views

Query evaluation is optimized using parallel optimization techniques to make repartitioning more efficient. Efficiency is improved by recognizing the possible partitioning requirements for achieving parallelism for a query operation, and by recognizing when the partitioning property of data satisfies the partitioning requirements of a query operation. A data base management system in accordance with the invention uses parallel query processing techniques to optimize data repartitioning, or to avoid it altogether.

Optimization of data repartitioning during parallel query optimization

A relational data base management system includes a query processor that uses a query operator partition property to perform QEP pruning and to ensure that data input to a query operator is partitioned appropriately for the operation. The partition property indicates the group of network nodes across which a table is distributed. The query processor also makes use of partition classes that are designated 'interesting classes' to perform preoptimization planning and query pruning, and to perform look-ahead partitioning based on partition classes that are identified as being of interest to future operations, thereby more efficiently evaluating complex query statements in an MPP, shared-nothing environment.

Relational database query optimization to perform query evaluation plan,

An automated methodology, and an apparatus for practicing the methodology, which enables the power and flexibility inherent in shared nothing parallel database systems (MPP) to be utilized on complex queries which have, heretofore, contained query elements requiring local computation or local coordination of data computation performed across the nodes of the distributed system. The present invention provides these features and advantages by identifying and marking the subgraphs containing these types of query elements as 'no TQ zones' in the preparation phase prior to optimization. When the optimizer sees the markings, it builds a plan that will force the computation of the marked subgraphs to be in the same section. This preparation phase also provides the partitioning information for all inputs to the 'no TQ zones'. This allows the bottom-up optimizer to correctly plan the partitioning for the 'no TQ zones'. These partitionings can force the operation to a single-node, the coordinator node, the catalog node, or to a particular partition class on multiple nodes, or nodegroups.

Shared nothing parallel execution of procedural constructs in SQL

Unwieldy star/join queries are performed more efficiently using a filtered fact table. Suitable queries include star/join queries with a large fact table joined with multiple subsidiary dimension tables, where indices exist over fact table join columns. The query is analyzed to prepare a query plan for the dimension table accesses. This plan is supplemented by adding nested loop join operations, where the inner table is a dimension table plan and the outer table is an index scan performed over a fact table index of the join column with the dimension table. The plan is also supplemented by filtering records resulting from the nested loop joins using a sequence of dynamic bit vectors, ultimately yielding a list of probable fact table records. The plan is further supplemented by fetching these records to construct a distilled fact which is used, instead of the large original table, to execute the query in considerably less time. If desired, the supplemented query plan and other competing approaches may studied to provide cost estimates, with the least costly approach being actually implemented.

Star/join query optimization

A join optimizer and method for a relational database management system including a data processor, a stored database, and a plurality of database relations, wherein one or more of the relations are retrieved by the processor by means of query commands by performing a plurality of join operations on the relations, the system employing a general purpose heuristic algorithm which excludes or defers Cartesian products as late in the join sequence as possible, the method includes the steps of determining, in association with the execution of, or preferably prior to executing the general purpose algorithm, whether tables referenced in a query command includes a hub table and at least two encoding tables related to the hub table and, when the query command references a hub table and at least two encoding tables, determining the best access plan for the hub table, determining whether the best access plan utilizes an index used to access the hub table and, if so, constructing a plan to join the encoding tables as Cartesian products, constructing a plan to join the hub table and the encoding tables and storing the plans in the data structures of the optimizer for enumeration with other access plans constructed by the optimizer.

Method for detecting and optimizing queries with encoding/decoding tables

An automated system for detecting and preventing mutating table violations of database integrity in a SQL query before generation and selection of an optimal query execution plan (QEP). This system modifies the query graph model (QGM) to restrict the choice of execution plans to those that avoid mutating table integrity (MTI) violations, thereby forcing database integrity during table mutation when executing the optimal QEP. Mutating table integrity violations are detected by evaluating the position in the QGM of each write-node referencing a particular base table with respect to each of the positions of all other read- and write-nodes referencing of the same base table. Every common-referencing node pair is tested for sequencing conflicts and a data-flow dam is inserted in the QGM where necessary or a poke query is inserted between the nodes to force the completion of the execution of one node before initiating execution of the other common-referencing node. The system of this invention allows processing of all non-cyclic and most cyclic SQL queries known to cause mutating table integrity violations, such as queries having searched and positioned inserts, deletes and updates, and row-level triggers.

Growing community of inventors

Saratoga, CA, United States of America

Monica Sachiye Urata