Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-17
2003-03-04
Homere, Jean R. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06529896
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular to the optimization of SQL queries in a relational database management system having an EXISTS subquery and a NOT EXISTS subquery.
2. Description of Related Art
Databases are computerized information storage and retrieval systems. A Relational Database Management System (RDBMS) is a database management system (DBMS) which uses relational techniques for storing and retrieving data. RDBMS software using a Structured Query Language (SQL) interface is well known in the art. The SQL interface has evolved into a standard language for RDBMS software and has been adopted as such by both the American National Standards Organization (ANSI) and the International Standards Organization (ISO).
In RDBMS software all data is externally structured into tables. The SQL interface allows users to formulate relational operations on the tables either interactively, in batch files, or embedded in host language, such as C, COBOL, etc. Operators are provided in SQL that allow the user to manipulate the data, wherein each operator operates on either one or two tables and produces a new table as a result. The power of SQL lies on its ability to link information from multiple tables or views together to perform complex sets of procedures with a single statement.
One of the most common SQL queries executed by RDBMS software is the SELECT statement. In the SQL standard, the SELECT statement generally has the format: “SELECT<clause>FROM<clause>WHERE<clause>GROUP BY<clause>HAVING<clause>ORDER BY<clause>.” The clauses generally must follow this sequence. Only the SELECT and FROM clauses are required and all other clauses are optional.
Generally, the result of a SELECT statement is a subset of data retrieved by the RDBMS software from one or more existing tables stored in the relational database, wherein the FROM clause identifies the name of the table or tables from which data is being selected. The subset of data is treated as a new table, termed the result table. The WHERE clause determines which rows should be returned in the result table. Generally, the WHERE clause contains a search condition that must be satisfied by each row returned in the result table. The rows that meet the search condition form an intermediate set, which is then processed further according to specifications in the SELECT clause.
The search condition typically comprises one or more predicates, each of which specifies a comparison between two values from certain columns, constants or correlated values. Multiple predicates in the WHERE clause are typically connected by Boolean operators.
The SELECT statement may also include a grouping function indicated by the GROUP BY clause. The GROUP BY clause causes the rows in the intermediate result set to be grouped according to the values specified in the clause. A number of column or aggregate functions are also built into SQL, such as MAX (maximum value in column), MIN (minimum value in column), AVG (average of values in column), SUM (sum of values in column), and COUNT (number of rows).
Queries using aggregate expressions return as many result rows as there exist unique “result groups” in the source of the aggregation. A result group is defined as the set of values contained in the fields of a row corresponding to the list of columns or expressions specified in the GROUP BY clause of the query. The value of the aggregate function is the cumulative result of applying the function to the result of the contained expression for each row having the same result group.
Another operation permitted by SQL is the JOIN operation, which concatenates horizontally all or parts of two or more tables to create a new resulting table. The JOIN operation is implied by naming more than one table in the FROM clause of a SELECT statement.
An SQL query generally includes at least one predicate, which is an SQL expression that can assume a logical value of TRUE, FALSE, or UNKNOWN. A predicate typically either specifies a data range, tests for an existence condition, tests for equivalence, or performs a similar table comparison operation.
In RDBMSs, columns of any type can assume NULL (i.e., unknown) values. In RDBMS software, NULL values are properly handled using tri-value logic (i.e., TRUE, FALSE or UNKNOWN) for predicates, and SQL-based RDBMSs employ such logic.
SQL queries and their resulting table operations can be nested through several levels of predicates such that a higher nested predicate, or level of operation, cannot be evaluated until after a lower level predicate, or operation, has been evaluated. A lower level of SQL operation in an SQL statement is generally referred to as a subquery.
Nested SQL statements may require tuple-by-tuple data manipulation in each subquery for evaluation of the complete statement. For example, each entry of a table column may need to be compared against each entry of a corresponding column in another table to determine if a SELECT operation should retrieve a table row. Such tuple-by-tuple operations are very inefficient and requires simplification and optimization.
In an RDBMS system, users submit SQL queries. The optimizer in the RDBMS optimizes the SQL query and generates an efficient execution plan. Typically, the optimizer adopts a cost-based approach wherein the optimizer generates many possible alternative execution plans, and selects the best/cheapest plan among those generated plans.
Graphical Representation of SQL Queries by Query Graph Model (QGM)
A useful tool in describing SQL queries and their evaluation is a graphical representation of SQL statements known as Query Box Representation (QBR). Known SQL optimizers employ various types of QBR to facilitate their processing and optimization efforts. QBR provides a powerful and manageable representation of queries used to reduce the complexity of query compilation and optimization procedures. Additionally, QBR provides a tool for optimizing queries by facilitating rewriting the QBR components in efficient arrangements.
Generally, a QBR representation employs hierarchically arranged “boxes” to represent subquery operations, such as SELECT and GROUP BY. The interconnections between the boxes define the relationship between different items of data from different subquery operations.
Various techniques may be used to store a complex query in computer memory in accordance with a QBR format. Specifically, multiple data structures in the memory are used to represent the QBR boxes and interrelationships. These data structures may comprise, for example, records and associated pointers, strings, stack arrangements, doubly linked lists, hashing arrangements, or other suitable formats. Preferably, records and pointers are used, where each record represents a QBR box, and the pointers represent the relationships between the boxes. Each record also includes a listing of various properties associated with the corresponding QBR box.
A number of different types of QBR are known in the art. One of the more popular types of QBR is known as the Query Graph Model (QGM), well known in the art, and described in the following reference, which is incorporated by reference in its entirety: Pirahesh et al., “Extensible/Rule Based Query Rewrite Optimization in Starburst,” Proceedings of ACM SIGMOD '92 International Conference on Management of Data, San Diego, Calif., U.S.A., 1992.
The query graph model supports arbitrary table operations where the inputs are tables and outputs are tables. Such operations are SELECT, GROUP BY, UNION, INTERSECT, and EXCEPT operations, as defined in the SQL standard, and the restriction, projection and join operations performed by the SELECT operation.
When a query is represented by the query graph model, each operation of the query may be graphically represented by a box having a head and body. The body of a query graph model box may include “quantifiers”, corresponding to table references or derived tables.
Leung Ting Yu
Truong Tuong Chanh
Urata Monica Sachiye
Ali Mohammad
Homere Jean R.
International Business Machines - Corporation
Parker Esq. Sandra M.
LandOfFree
Method of optimizing a query having an existi subquery and a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of optimizing a query having an existi subquery and a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of optimizing a query having an existi subquery and a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3047259