Evaluating SQL subqueries

Details Evaluating SQL subqueries Evaluating SQL subqueries

1998-12-16

2002-06-25

Jung, David (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C717S140000

Reexamination Certificate

active

06411951

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to relational databases, and more particularly to evaluating subqueries in the SQL language used by relational database management systems.
COPYRIGHT
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright© 1996, Microsoft Corporation, All Rights Reserved.
BACKGROUND OF THE INVENTION
Under certain conditions, the SQL language allows the use of a basic block Select/from/Where relational expression, which is a table-valued, inside scalar expressions. Such a relational expression inside a scalar expression is called a subquery. The SQL2 standard specifies three basic forms of subqueries.
In a scalar-valued subquery, the result must be a table with at most one row and one column, whose value is used in the scalar expression. For example,
2 * (Select Avg(Salary) from Employees).
An existential subquery returns a boolean value based on whether the subquery returns any rows. For example,
Case When Exists(select * from shippers where shipperid=20) Then 1 Else 0 End.
The third form, the quantified comparison, also returns a boolean value, which is obtained by comparing a scalar value with a list of values returned by the subquery. For example,
Case When X<>ALL(Select Customerid from Customers) Then 1 Else 0 End.
Scalar expressions containing subqueries will often be used in larger relational expressions, and can use columns or variables from its environment. A use of such an “outer” variable is called a correlation. For example, the following query uses a subquery to find customers who have placed an order:
Select * from Customers c
where Exists(Select * From Orders o where o.customerid=c.customerid).
Database engines typically separate a query executor (QE) component from an expression service component (ES). The QE deals with execution of the relational parts of queries, and it calls a simpler ES module that deals with evaluation of scalar expressions, as needed. For example, in applying a filter on a table, the QE would consider each row in turn, call the ES to evaluate the filter condition and, based on the scalar result, either discard the row or pass it to a consumer. Thus, even the most straightforward evaluation of subqueries requires the ES to call back into the QE to resolve the relational expression.
There is a potentially large amount of processor state associated with the QE, and requiring the ES to call back requires the use of conceptually separate instances of the QE that get activated in a recursive fashion. This requires setting up and removing a context for each instantiation of the QE. Since scalar expressions are usually called once per row to process the expression, this expensive recursive invocation will be done many times for large databases. Additionally, this approach to the processing of subqueries requires complex implementation for the database engine.
In some cases, the use of a subquery can be replaced by a relation join as observed by W. Kim in “On optimizing an SQL-like nested query,”
ACM Transactions on Database Systems
, Vol. 7, No. 3, September 1982, pp. 443-469. Such a substitution removes the need for recursive calls between QE and SE, and allows the use of any join algorithm, for example a hash join, or merge join as discussed by G. Graefe in “Query evaluation techniques for large databases,” ACM
Computing Surveys
, Vol. 25, No. 2, 1993, pp. 73-170. Additional cases of subqueries which can be removed in this fashion have been proposed by U. Dayal in “Of nests and trees: A unified approach to processing queries that contain nested subqueries,”
Proceedings of the International Conference on Very Large Databases
'87, pp. 197-208, R. A. Ganski, and H. K. T. Wong in “Optimization of nested SQL queries revisited,”
Proceedings of ACM SIGMOD
'87
Internaltional Conference on Management of Data
, San Francisco, Calif., pp. 23-33, and M. Muralikrishna in “Improved unnesting algorithms for join aggregate SQL queries,”
Proceedings of the International Conference of Very Large Databases
'92, pp. 91-102.
There is a need in the art for a relational database management system that utilizes subquery substitution for relational queries and extends the capabilities of the substitution structure.
SUMMARY OF THE INVENTION
The above-mentioned shortcomings, disadvantages and problems are addressed by the resent invention, which will be understood by reading and studying the following specification.
SQL subqueries are converted into equivalent expressions having a special relational operator. The special relational operator assumes properties based on the type of the expression containing the subquery. The context of the subquery is also factored into the special relational operation. The relational operator itself is optimized, when possible, into a standard join operation. The conversion process maintains a list of parameter dependencies within the query and the relational operator utilizes this list at execution time to decrease the amount of processing required to produce the query output.
The special relational operator and processing of the present invention enables more efficient query execution because the properties of the special relational operator optimize the execution flow, and omit both unnecessary and redundant processes. Furthermore, the absence of subqueries in the converted query permits the implementation of a less complex database execution engine.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.


REFERENCES:
patent: 5724570 (1998-03-01), Zeller et al.
patent: 5956704 (1999-09-01), Gautam et L.
patent: 5970490 (1999-10-01), Morgenstern
patent: 6021405 (2000-02-01), Celis et al.
www.informix.com/answers/oldsite/answers/pubs/html/dbdk/extend/04.fm.1.html, 1998.*
Srinivasan et al., “Extensible Indexing: A Framework for Integrating Domain-Specific Indexing Schemes into Oracle 8i”, Data Engineering, 2000, Proceedings, 16th International Conference on, pp. 91-100, Feb. 2000.*
Informix Software, “Extending Informix: Universal Server: Data Types”, Version 9.1, Mar. 1997.*
Chaudhuri, “An Overview of Query Optimization in Relational Systems”, ACM PODS 1998, Seattle, Washington, pp. 34-43, Jun. 1998.*
PODS '98 Technical Program, 1998, Seattle Washington, Jun. 1998.*
www.informix.com/answers/oldsite/answers/pubs/html/dbdk/extend/02.fm.1.html, 1998.*
Dayal, U., “Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregate, and Quantifiers”,Proceedings of the Thirteenth International Conference on Very Large Data Bases, Brighton, England, 197-208, (1987).
Ganski, R.A., et al., “Optimization of Nested SQL Queries Revisited”,Proceedings of Association for Computing Machinery Special Interest Group on Management Data, 22-33, (May 1987).
Graefe, G., “Query Evaluation Techniques for Large Databases”,ACM Computing Surveys, 25 (2), 73-170, (Jun., 1993).
KIm, W., “On Optimizing an SQL—like Nested Query”,ACM Transactions on Database Systems, 7(3), pp. 443-469, (Sep. 1982).
Melton, J., et al., “Predicates”,In: Understanding the New SQL: A Complete Guide, Morgan Kaufmann Publishers, San Francisco, CA, 125-147.
Muralikrishna, M., “Improved Unnesting Algorithms for Join Aggregate SQL Queries”,Proceedings of the 18th International Conference on Very Large Data Bases, Vancouver, British Columbia, Canada, pp. 91-102

Affiliated with

Also associated with

Rating

Evaluating SQL subqueries does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Evaluating SQL subqueries, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Evaluating SQL subqueries will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2913019