Tandem Computers Incorporated

Compaq Computer Corporation, Inc.

Compaq Information Technologies Group, L.p.

Compaq

Pedro Celis

Hansjorg Zeller

Jay Vaishnav

Harry Anthony Leslie

James H Troisi

Christopher M Farrar

Diana L Shak

Donald S Maier

Goetz Graefe

Michael John Skarpelos

Gary Martin Gilbert

Franco Putzolu

Roberta S Marton

Sunil Sharma

Richard A Meier

Louise M Madrid

Elizabeth G Davis

Jay H Vaishnav

Diana Shak

Thomas J O'Shea

In a system for executing database queries, a directed graph of logically interconnected tasks represents an execution plan for executing a specified database query. A pair of queues are stored in a computer memory for each pair of interconnected tasks in the directed graph. One of the queues in each pair is a down queue for sending requests from a parent task to a child task, and the other is an up queue for sending replies from the child task to the parent task. Each queue is a circular buffer and includes a head pointer that points to a next location in the queue to be read, and a tail pointer that points to a next location in the queue in which data can be written. Each task checks that a queue is not full before writing data into that queue, and checks that the sibling queue is not empty before reading data from the sibling queue. In addition, a task updates the tail pointer for a queue only after it has written data into the location in the queue to which the tail pointer is updated, to ensure that the other task does not attempt to read that queue location until the new data has been written into it. This queue protocol is sufficient, by itself, to ensure that tasks do not make conflicting use of the queues, despite the fact that the queues are in shared memory and are not protected by a synchronization mechanism.

Efficient inter-task queue protocol

A method and apparatus is disclosed for accurately estimating the cost of a database query, including the total computer resources used and estimated elapsed time for the production of a first row and last row of an operator involved in the query and/or the total resources used and elapsed time for returning the overall response to a database query. The method and apparatus accurately accounts for resources used and elapsed time associated with blocking operators, such as sorts and hash joins, which cannot produce a first row until they have completed their operations.

Database query cost model optimizer

The invention provides a mechanism for using statistics, in connection with various database query cost modeling techniques, to more accurately estimate the number of rows and UECs that will be produced by relational operators and predicates in database systems. The ability to accurately estimate the number of rows and UECs returned by a relational operator and/or a predicate is fundamental to computing the cost of a query execution plan. This, in turn, drives the optimizer's ability to select the query plan best suited for the desired performance goal. According to the present invention, histogram statistics are synthesized bottom up from the leaf nodes to the root node of a query tree. Given input statistics in the form of histograms for each operand of a relational operator or predicate, the present inventive method and apparatus merge the input statistics in a way that it simulates the effects of the run time operator on the actual data, so as to produce a predicted row count and UEC for each histogram interval representative of the data that actually will be produced by each such operator or predicate in the query tree. A database query optimizer may use these statistics to select and implement an optimal query plan.

Histogram synthesis modeler for a database query optimizer

A system and method for optimizing a database query with improved performance enhancements is herein disclosed. The database query consists of one or more logical expressions. Through the repeated application of one or more rules, the logical expressions are transformed into execution plans. The query optimizer partitions the database query into one or more subproblems with each subproblem consisting of one or more logical expressions. A plan is obtained for each subproblem with the plan for the database query including the plans for each subproblem. The query optimizer is cost-based and uses rules including transformation and implementation rules that are used to perform transformations on the logical expressions in a subproblem in order to produce a plan. The rules are classified into context-free and context-sensitive in order to avoid generating duplicate expressions. Context-free rules are applied once for each logical expression and context-sensitive rules are applied once for each logical expression for a particular optimization goal. In a preferred embodiment, the query optimizer performs several optimization passes over the database query in order to obtain an optimal plan. For each pass, if no optimal plan exists for the requested optimization goal, existing plans having the same optimization goal are utilized with each input reoptimized for a more cost effective plan.

System and method for optimizing database queries with improved

A system and method for optimizing a database query is herein disclosed. The system consists of a search engine and a database implementor that determines an optimal plan for executing a SQL query. The SQL query is represented as a query tree consisting of a number of nested expressions. The search engine generates a number of plans from which an optimal plan is selected. Plans are generated through the application of a set of rules consisting of implementation and transformation rules. Implementation rules are used to obtain plans. Transformation rules are used to determine equivalent expressions. A plan for the query tree entails finding plans for each expression within the tree where each plan is generated in accordance with a prescribed set of rules. The database implementor selects the set of rules such that more promising plans are generated rather than generating all possible plans. In a preferred embodiment of the invention, multiple passes are made by the search engine in order to determine the optimal plan. In a first pass, implementation rules are used in order to generate a first plan having a cost that is used as a threshold when generating for additional plans. In each subsequent pass, a set of implementation and transformation rules is used to generate one or more plans whose cost does not exceed the threshold. An optimal plan is selected from the generated plans as the one having the lowest cost.

System and method for optimizing database queries

A system and method for optimizing a database query with improved performance enhancements is herein disclosed. The database query consists of one or more logical expressions. Through the repeated application of one or more rules, the logical expressions are transformed into physical expressions and in some cases, execution plans that implement the database query. Each expression has associated with it a set of group attributes that specifies its characteristic inputs and outputs and a cost that estimates the computational expense for executing the expression. The group attributes are used to categorize similar expressions into groups that are stored in a search data structure. They are also used to track duplicate expressions. The cost associated with an expression is used to guide the search process to consider those expressions that will produce low cost plans. The cost is estimated in accordance with a six-fold criteria with each criterion weighted to account for the context of the expression and the application's particular computing environment. The query optimizer is rule-based including transformation and implementation rules that are used to perform transformations on the logical expressions in a subproblem in order to produce a plan. A OnceGuidance guidance method is used to select a set of rules in certain cases that prevent the regeneration of an existing expression.

System and method for database query optimization

A method for subquery elimination for a relational model database based on the SQL language running a database management system (DBMS) under the TANDEM NONSTOP (tm) operating kernel. A series of seven transformation rules are applied to eliminate nested queries in the SQL language. The method and teachings of the present invention generalizes to all types of nested subqueries in SQL, allowing for more efficient computations, allocation and maintenance of system resources.

Method and apparatus for a complete SQL subquery elimination process

An SQL program executor and an SOL compiler both include options for avoiding recompilations of execution plans whenever the runtime object and the compile time object referenced by an execution plan meet predefined schema similarity criteria. Thus, recompilation is sometimes avoided even though the compile time object has been altered or the run time object is not the same object as the compile time object. To enable late binding, schema information is stored in each execution plan for each object to be accessed by the execution plan. The stored schema information is a subset of the full object schema, and includes information about all the aspects of the objects to be accessed which must remain unchanged in order for the execution plan to be operable. While executing a compiled program, the SQL executor avoids recompilations of execution plans whenever the runtime object and the compile time object referenced by an execution plan meet predefined schema similarity criteria. When a recompilation of an SQL program is required, only the execution plans which do not meet the schema similarity criteria are recompiled if the compiled program has been assigned appropriate runtime parameters. The late binding features of the SQL executor also enable a compiled program to access objects distinct from the objects referenced by the program at compile time. Similarly, the SQL compiler includes the ability to recompile only those execution plans which do not meet the schema similarity criteria and thus are inoperable.

Relational database system and method with high availability compliation

A database computer system includes memory, residing in a plurality of interconnected computer nodes, for storing database tables. Each database table has a plurality of columns, a primary key index based on a specified subset of the columns, and an associated table schema. At least a subset of the database tables are partitioned into a plurality of partitions, each partition storing records having primary key values in a primary key range distinct from the other partitions. A transaction manager generates and stores an audit trail, each audit entry denoting a database table record event, such as an addition, deletion or alteration of a specified database table record in a specified one of said database tables. Four online data definition procedures allow the structure of a database table to be altered while the database table remains available to execution of transactions, with minimal impact of the availability of the database table for transaction execution. The four online data definition procedures are a move partition procedure, a split partition procedure, a move partition boundary procedure, and a create new index procedure. Each of these online procedures has three or four phases of execution. In a first phase, records of a table partition or the entire table are accessed using read only access, so as to generate a new partition, move records between two partitions, or to create a new index. In a second phase, audit trail entries are used to clean up the data structures created during the first phase. In a third phase, access to the database table is briefly locked while audit trail entries created after the second phase are used to make final changes to the data structures created during the first phase, and while the database table schema is updated to reflect the changes to the database table produced.

Growing community of inventors

Austin, TX, United States of America

Pedro Celis