Computer automated system and method for optimizing the processing of a query in a relational database system by merging subqueries with the query
AssigneeInternational Business Machines Corporation
InventorsJosephine M.-K. Cheng, Sheldon J. Finkelstein, Donald J. Haderle, Mir H. Pirahesh, Yun Wang
Life of this patent
Estimating the term…
Abstract
An automated method is provided for optimizing a query for retrieving data from a relational database in a computer relational database management system. The method uses rules for identifying queries for which duplicates are a factor in retrieving the proper data from the database. The method then merges queries with table expressions, views and subqueries when possible without causing duplicates to be unnecessarily retrieved.
Claims18
In a relational database management system using a data processor for storing data in the form of a plurality of tables comprised of a plurality of tuples having one or more columns of predicates, and having key columns for unique identification of the tuples and wherein the data is retrievable by means of SQL queries which include at least one subquery, a query output table of at least one tuple being produced by the processing of the query, a data processor implemented method for optimizing the processing of a query, comprising the steps of:
- (a) determining whether the existence of duplicate tuples in the output of the subquery affect the integrity of the tuples output by the query with respect to requested distinct tuples or an accurate number of duplicated tuples in the query output table;
- and
- (b) merging the subquery with the query during the processing of the query while the integrity of the tuples output by the query is maintained with respect to requested distinct tuples or an accurate number of duplicated tuples in the query output table.
In a relational database management system using a data processor for storing data in the form of a plurality of tables comprised of a plurality of tuples having one or more columns of predicates, and having key columns for unique identification of the tuples and wherein the data is retrievable by means of SQL queries which include at least one subquery, a data processor implemented method for optimizing the processing of a query, comprising the steps of:
- (a) determining whether a subquery has a requirement of retrieving distinct tuples;
- (b) performing a merge of said query and said subquery when all tuples in the query output table are distinct, or the query output table can have an arbitrary number of duplicate tuples, or there is no requirement that all of the tuples in the subquery output table be distinct;
- (c) when no merge was performed by step (b), adding a unique value to each tuple in the query output table so that all tuples in the query output table are distinct;
- and
- (d) repeating steps (a), (b), and (c) until said query is no longer changed by these steps.
In a relational database management system using a data processor for storing a plurality of tables of data comprised of a plurality of tuples having one or more columns of predicates, wherein key columns provide unique identification of the tuples, and data is retrievable by means of SQL queries that can be represented by QGM structures comprising:
- a plurality of boxes, each of said boxes having a head and a body, said body containing a plurality of iterators and edges, wherein iterators range over tables, upper boxes contain iterators, lower boxes contain tables ranged over by iterators, said head comprising output from said body, and at least one box being a SELECT box, a method for optimizing the processing of said queries, comprising the steps of:
- (a) associating an attribute with each of said heads which can take a first or a second value,
- said first value indicating that said head does not contain duplicates;
- and
- said second value indicating that said head may contain duplicates,
- (b) associating an attribute with each of said bodies which take on a first, a second, and a third value,
- said first value indicating that duplicates in said body table must be eliminated;
- said second value indicating that the operation performed by said box does not effect duplicates in the tables:
- said third value indicating that duplicate elimination may be performed arbitrarily;
- and
- (c) associating an attribute with a plurality of iterators which take on a first, a second, and a third value,
- said first value indicating that duplicates must be eliminated after a projection over the columns of said tables;
- said second value indicating that the exact number of duplicates generated by lower boxes must be preserved;
- and
- said third value indicating that duplicates may be performed arbitrarily;
- (d) performing a set of rules on said queries for optimizing the processing of distinct attributes in queries, comprising:
- for each SELECT box, where for each iterator in said SELECT box, at most one tuple ranged over by said SELECT box iterator satisfies a set of predicates in said SELECT box, or a key of the table ranged over by said iterator appears in said head.
- setting said SELECT box head attribute to said first value;
- and
- setting said SELECT box body attribute to said second value:
- for each SELECT box where a quantifier is of a type designated as existential or universal,
- setting said iterator attribute to said third value;
- for each SELECT box where said body attribute has said first value or said third value,
- for each iterator in said SELECT box,
- setting said iterator attribute to said third value;
- for each SELECT box, where all iterators ranging over said box have said iterator attribute set to said third value,
- setting said body attribute to said third value;
- (e) merging each lower box into an upper SELECT box having a setformer ranging over said lower SELECT box and said head attribute of said upper SELECT box has said first value;
- (f) merging each lower box into an upper SELECT box having a setformer ranging over said lower SELECT box and said body attribute of said upper SELECT box has said third value;
- (g) merging each lower box into an upper SELECT box having a setformer ranging over said lower SELECT box and said body attribute of said lower SELECT box does not have said first value;
- (h) for each of said merged boxes, if said body attribute of said former lower box had said first value and said body attribute of said upper SELECT box does not have said third value, setting said body attribute of said upper SELECT box to said first value;
- (i) for SELECT boxes where said head attribute has said second value and said key column of said table is not present in the output, adding a unique identifier to said head and setting said head attribute to said first value.
In a relational database management system using a data processor for storing data in the form of a plurality of tables comprised of a plurality of tuples having one or more columns of predicates, and having key columns for unique identification of the tuples and wherein the data is retrievable by means of SQL queries which include at least one subquery, a system for processing a query, comprising:
- means for merging subqueries with queries when all of the tuples in the query output table will be distinct;
- means for merging subqueries with queries when an arbitrary number of duplicates are allowed to be present in the query output table;
- means for merging subqueries with queries when the subquery does not require that the ruffles in the subquery output table be distinct;
- means for eliminating duplicate tuples from the query output table of merged queries where the operation performed by the query does not effect duplicate elimination;
- and
- means for adding a unique identifier to each tuple in the query output table for queries where duplicates may be in the query output table.
Dependencies are inferred from the claim text.