Redundant join elimination and sub-query elimination using subsumption

[0001] This application claims benefit under 35 USC 119 of Canadian Application No. 2,374,271, filed on Mar. 1, 2002.

[0002] This invention relates generally to systems for query optimization in relational database management systems and, more particularly, to redundant join elimination and sub-query elimination using subsumption.

[0003] One popular form of computerized record-keeping system is the relational database. Between the actual database (i.e., the data as stored for use by a computer) and the users of the system is a software layer known as the relational database management system (RDBMS). The RDBMS is responsible for handling all requests for access to the database, shielding the users from the details of any specific hardware implementation. Using relational techniques, the RDBMS stores, manipulates and retrieves data in the form of table-like relations typically defined by a set of columns or attributes of data types and a set of rows (i.e., records or tuples) of data. The columns may further include restrictions on their data content (i.e., valid domains) and may be designated as a primary key or unique identifier for the relation or a foreign key for one or more other relations.

[0004] The standard language for dealing with relational databases implemented by most commercial RDBMSs is the Structured Query Language or SQL. SQL includes both data definition operations and data manipulation operations. In order to maintain data independence a query (i.e., a set of SQL commands) instructs the RDBMS what to do but not how to do it. Thus, the RDBMS includes a query processor for generating various query plans of execution and choosing the cheapest plan. Due to the high-level nature of relational expressions and a variety of implementation techniques, automatic query optimization is possible and often necessary to ensure more efficient query processing.

[0005] In accordance with well known query translation processes, an SQL query is processed in stages. The initial stage casts the source query into an internal form such as the Query Graph Model (QGM) following the preliminary steps of lexing, parsing and semantic checking. The goal of the QGM is to provide a more powerful and conceptually more manageable representation of queries in order to reduce the complexity of query compilation and optimization. The internal QGM is a data structure for providing the semantic relationships of the query for use by query translator and optimizer components for rewriting the query in a canonical form. In a next phase, a plan optimizer produces a query execution plan such as by generating alternate plans and choosing a best plan based on estimated execution costs. Finally, a plan refinement stage may be employed to refine the optimum execution plan in accordance with run-time requirements.

[0006] SQL query compilation and optimization techniques using the Query Graph Model (QGM) are well known to those skilled in the art and include the teachings of Hamid Pirahesh, Joseph Hellerstein, and Waqar Hasan, Extensible/Rule Based Query Rewrite Optimization in STARBURST, Proceedings of ACM SIGMOD '92 International Conference on Management of Data, San Diego, Calif., 1992, incorporated by reference herein (hereinafter Pirahesh et al.). One QGM as discussed in Pirahesh et al. is described briefly herein.

[0007] The structure of the QGM is central to the query rewrite mechanism, since rewriting a query corresponds to transforming its QGM. The QGM is a graph of nodes (or boxes), each representing a table operation whose inputs and outputs are tables. Examples of such operations are SELECT, GROUPBY, UNION, LEFT JOIN, INTERSECT and EXCEPT. In our terminology, the operation SELECT incorporates selection, projection and join (i.e., the simple unnested SELECT, FROM and WHERE clauses in SQL). The number of QGM boxes in a query typically ranges from 2 to 40.

[0008] A useful QGM known in the art is described by example. FIG. 1 illustrates a graphical representation of a QGM for the following SQL query:

SELECT DISTINCT Q1.PARTNO, Q1.DESCR, Q2.SUPPNO
FROM INVENTORY Q1, QUOTATIONS Q2
WHERE Q1.PARTNO Q2.PARTNO AND Q1.DESCR ENGINE
AND Q2.PRICE < ALL (SELECT Q3.PRICE
	FROM QUOTATIONS Q3
	WHERE Q2.PARTNOQ3.PARTNO)

[0009] This query provides information about suppliers and parts for which the supplier's price is less than that of ALL other suppliers. FIG. 1 shows five boxes or nodes on a QGM graph 10. Boxes 12 and 14 are associated with base tables INVENTORY and QUOTATIONS. Box 16 is a SELECT box associated with the main part of the query and box 18 is a SELECT box associated with the sub-query. Box 20 (i.e., Top node) represents the data output table requested by the query. Each box 12, 14, 16, 18 and 20 has two main components a head and a body. Each head (for example head 22 of box 16) describes the output table produced by the box and each body (for example body 24 of box 16) specifies the operation required to compute the output table. Base tables have empty or nonexistent bodies.

[0010] With reference to box 16, head 22 specifies output columns PARTNO, DESCR and SUPPNO, as specified in the SELECT list of the query. The specification of these columns includes column names, types, and output ordering information (not shown). The head 22 includes a Boolean attribute called DISTINCT that indicates whether the associated table contains only distinct tuples (head.distinctTRUE), or whether it may contain duplicates (head.distinctFALSE).

[0011] The body of a box contains a graph where the vertices represented by darkened circles in FIG. 1 represent quantified tuple variables, called QUANTIFIERS. Box 16 includes quantifiers q1, q2, and q4 (respectively 30, 32 and 34). Quantifiers q1 30 and q2 32 range over (i.e., read from) the base tables INVENTORY 12 and QUOTATIONS 14 respectively, and correspond to the table references in the FROM clause of the SQL query. Vertices q1 30 and q2 32 are connected via respective interbox edges 38 and 40 to the heads of the INVENTORY 12 and QUOTATIONS 14 boxes. The edge 42 between q1 30 and q2 32 specifies the join predicate. The loop edge 44 attached to q1 30 is the local predicate (Q1.DESCRENGINE) on q1 30. Each interquantifier edge represents a conjunct of the WHERE clause in the query block the conjuncts being represented in the diagram by the labeled rectangle along the edge. Such edges are also referred to as Boolean factors. Quantifier q4 is a UNIVERSAL quantifier, associated with the ALL sub-query in the WHERE clause. This represents that for ALL tuples associated with q4, the predicate represented by the edge between q2 32 and q4 34 is TRUE.

[0012] In Box 16, q1 30 and q2 32 participate in joins, and some of their columns are used in the output tuples. These quantifiers have type F (ForEach), since they come from the query's FROM clause. Quantifier q4 34 has type A, representing a UNIVERSAL (ALL) quantifier. SQL's predicates EXISTS, IN, ANY and SOME are true if at least one tuple of the sub-query satisfies the predicate. Hence, all of these predicates are EXISTENTIAL, and the quantifiers associated with such sub-queries have type E. Each inter-box edge is labeled with the quantifier columns that the edge provides from the table the quantifier ranges over. Additionally, quantifiers may be ordered within a box to support asymmetric operators, such as EXCEPT. In QGM, the quantifiers associated with existential and universal sub-queries are called COUNTING quantifiers. SCALAR sub-query quantifiers have the type S, requiring that (1) the sub-query returns at most one row and (2) if the sub-query does not produce any row, a null value will be returned via the S quantifier.

[0013] Box 18 represents the subquery SELECT Q3.PRICE FROM QUOTATIONS Q3 WHERE Q2.PARTNOQ3.PARTNO. Quantifier q3 46 is of type F and ranges over the base table QUOTATIONS 12. Box 18 includes a predicate 48 (Q2.PARTNOQ3.PARTNO) that refers to q2 32 and q3 46.

[0014] The body of every box has an attribute called DISTINCT that has a value of ENFORCE, PRESERVE or PERMIT.ENFORCE means that the operation must eliminate duplicates in order to enforce head.distinctTRUE. PRESERVE means that the operation must preserve the number of duplicates it generates. This could be because head.distinctFALSE, or because head.distinctTRUE and no duplicates could exist in the output of the operation even without duplicate elimination. PERMIT means that the operation is permitted to eliminate (or generate) duplicates arbitrarily. For example, the DISTINCT attribute of Box 18 can have the value PERMIT because its output is used in universal quantifier q4 34 of box 16, and universal quantifiers are insensitive to duplicate tuples.

[0015] Like each box body, each quantifier q1, q2, q3, and q4 (30, 32, 46 and 34 respectively) also has an attribute called DISTINCT (not shown) that has a value of ENFORCE, PRESERVE or PERMIT. ENFORCE means that the quantifier requires the table over which it ranges to enforce duplicate elimination. PRESERVE means that the quantifier requires that the exact number of duplicates in the lower table be preserved. PERMIT means that the table below may have an arbitrary number of duplicates. Existential and universal quantifiers can always have distinctPERMIT, since they are insensitive to duplicates.

[0016] In the body, each output column may have an associated expression corresponding to expressions allowed in the select list of the query. These expressions are called head expressions. In FIG. 1, all of these expressions are simply identity functions over the referenced quantifier columns.

[0017] DB2 from IBM Corporation supports derived tables, which are similar to VIEW definitions, and can be defined anywhere a table can be used. In DB2, derived tables and VIEWs, just like queries and sub-queries, have a QGM, with one or many boxes. When a derived table or VIEW is referenced in a query, its QGM becomes part of the QGM graph of the query.

[0018] The output of a box can be used multiple times (e.g., a VIEW may be used multiple times in the same query), creating common sub-expressions.

[0019] A particular QGM optimization technique termed subsumption has been discussed extensively in many research literature and has been widely used. Subsumption is particularly useful for the rewriting of a query to use an existing materialized view, as disclosed in the following publications incorporated herein by reference: L. S. Colby, R. L. Cole, E. Haslam, N. Jazaeri, G. Johnson, W. J. McKenna, L. Schumacher, D. Wilhite, Red Brick Vista: Aggregate Computation and Management, Proceedings of the 14th Int'l, Conference on Data Engineering, Orlando, Fla., 1998. R. Bello, K. Dias, A. Downing, J. Feenan, J. Finnerty, W. Norcott, H. Sun, A. Witkowski, M. Ziauddin, Materialized Views In Oracle, Proceedings of the 24th VLDB Conference, New York, 1998, D. Srivastava, S. Dar, H. Jagadish, A. Levy, Answering Queries with Aggregation Using Views, Proceedings of the 22nd VLDB Conference, Mumbai, India, 1996.

[0020] In accordance with a query represented by a QGM graph, SELECT box X is said to be subsumed by another SELECT box Y, if the result set of X is a subset of the result set of Y and if the output column set of X is a subset of the output column set of Y. In other words, the result set of X can be rederived using the result set of Y. A simple subsumption situation arises when the predicate set in box X is a superset of the predicate set in Y. The SELECT box X will filter out more rows since it has more predicates than the box Y. For example, consider the following queries L1 and M1:

	L1: SELECT * FROM T WHERE C1 >0 AND C2>0
	M1: SELECT * FROM T WHERE C1 >0

[0021] The result set produced by L1 is a subset of the result set produced by M1. The reason is that both queries select rows from the same table T (i.e., T is a common sub-expression), and all predicates in M1 appear in L1. Hence, M1 subsumes L1.

[0022] Another simple situation is when the predicate set in box X is more restrictive than the predicate set in Y. For example, consider the following additional query L2:

	L2: SELECT * FROM T WHERE C1 > 10

[0023] The result set produced by L2 is a subset of the result set produced by M1, and therefore M1 subsumes L2 in addition to subsuming L1.

[0024] Query subsumption, in terms of predicate sets, can be defined as follows using query blocks. Assume that a SELECT box L with a single quantifier Q ranges over a common sub-expression (e.g., a table) T, and another SELECT box M with a quantifier Q ranges over the same table T, wherein the quantifiers Q and Q comprise the table references of the SELECT boxes. In the above example, the predicate sets in L1, L2 and M1 are:

[0025] A predicate can be mapped into another predicate by mapping the column references between two quantifier sets. For example, the predicate set in M1 can be mapped from Q) to Q resulting in:

[0026] Now, subsumption can be defined precisely on predicates mapped via quantifiers:

[0027] If the predicate set in M mapped from Q) to Q) is less restrictive than the predicate set in L, then L is subsumed by M. That is L is a subsumee and M is a subsumer.

[0028] In other words, all the rows produced by L can be found in the result set produced by M.

[0029] As mentioned above, the result set by the subsumee can be rederived from the subsumer. In the above examples, in order to obtain the result sets of L1 and L2, one must apply the respective compensation predicates C2>0 and C1>10 on the result set of M1.

[0030] A query optimization technique for redundant join elimination has also been disclosed in Query Rewrite Optimization in STARBURST, Proceedings of ACM SIGMOD '92 International Conference on Management of Data, San Diego, Calif., 1992 referred to above. Essentially, if a self join on a table and the join condition involves the primary key of the table, then the join can be removed because the join is really always one-to-one tuple matching between the two references of the given table.

[0031] Despite these known optimization techniques of subsumption and redundant join elimination, there is further need to optimize queries by eliminating redundant joins when the join conditions do not involve the primary keys.

[0032] It is the object of the invention to provide a query rewrite optimization technique for a computer-implemented database management system. It is a further object to provide such a technique that eliminates a redundant join and equivalent sub-query using subsumption techniques.

[0033] In accordance with an aspect of the present invention, there is provided a method for optimizing a query in a relational database processing system. The method includes the steps of (a) evaluating the query to identify a join predicate joining a sub-expression of the query to itself where the join predicate includes an equality test between a same quantifier column of the sub-expression; (b) determining whether a row set producible from a first set of references of the query to the sub-expression is subsumed by a row set producible from a second set of references of the query to the sub-expression; and (c) reforming the query to eliminate the join predicate in response to the steps of evaluating and determining. Additionally, the method may further include the step of determining the removability of the second set of references from the query, wherein the step of reforming is further responsive to the step of determining the removability.

[0034] In accordance with yet another aspect of the present invention, where the query includes first and second quantifiers each ranging over the sub-expression, the step of determining the removability is responsive to the step of detecting, as an output of the query, a reference to one or more quantifier columns relative to said second quantifier. Preferably, in response to said detecting, the query may be reformed to replace the reference to the one or more quantifier columns relative to the second quantifier. In accordance with yet another aspect of the present invention, the step of determining the removability is responsive to the step of detecting a cardinality condition of an output of the query.

[0035] Preferably, in accordance with yet another aspect of the invention where the query includes first and second quantifiers each ranging over the common sub-expression, the step of reforming the query includes the step of removing the second quantifier from the query. Moreover, the step of reforming may include the step of rewriting the first set of references in response to the elimination of the join predicate.

[0036] In accordance with yet another aspect of the present invention, the sub-expression may consist of a base table, materialized view or a derived table.

[0037] In accordance with further aspects of the present invention there is provided an apparatus such as a query optimizer system and a database system as well as articles of manufacture such as a computer readable medium having program instructions recorded thereon for practicing the method of the invention.

[0038] Further features and advantages of the embodiments of the present invention will become apparent from the following detailed description, taken in combination with the appended drawings, in which:

[0039] FIG. 1 is a block diagram of a Query Graph Model (QGM) for an exemplary SQL query in accordance with the prior art; and

[0040] FIG. 2 is flow chart for a sequence of steps according to the method of the invention.

[0041] It will be noted that throughout the appended drawings, like features are identified by like reference numerals.

[0042] A method according to an embodiment of the present invention may be incorporated in a relational database management system (RDBMS) that employs a process for query optimization, such as QGM based optimizations, for directing a computer-implemented database processing system to achieve desired functions and tasks as will be explained below. The computer implementation includes a computer processing unit (CPU) coupled to interfacing devices for receiving user queries and for displaying results of the user queries. User queries typically include a combination of SQL commands for requesting the computer system to produce tabular output data. The CPU is coupled to storage space for containing programs and data such as base tables or virtual tables such as views or derived tables (i.e., tables determined from one or more base tables according to VIEW or other definitions). The storage space may comprise a variety of storage devices including internal memory and external mass storage typically arranged in a hierarchy of storage as understood to those skilled in the art.

[0043] The database processing system includes a control program stored in memory for directing the CPU to manage components related to the database processing system. The components include a component having instructions for directing the CPU to receive a query from a user, and a component having instructions for directing the CPU to process the user query in accordance with a Query Graph Model including query optimization process. Additional components have instructions for directing the CPU to perform query plan determination including generating, costing and selecting a query plan as well as executing a preferred query plan. The foregoing description is exemplary only and the method of the present invention may be incorporated in any RDBMS that employs the process of query optimization, particularly QGM-based optimization.

[0044] In accordance with a method provided by an aspect of the present invention, queries including particular join operations may be optimized using the subsumption technique. Consider a query including a join predicate joining first and second quantifiers that each range over the same sub-expression in a QGM graph, such as a base table, materialized view or derived table. In the query, each quantifier has a respective predicate set for determining the resulting row set of the query. If the join condition is an equality test between the same quantifier columns of the common table, the query may be reformed to eliminate the second quantifier. The query may be reformed when the row set determined by query predicates for the first quantifier is subsumed by the row set determined by query predicates for the second quantifier.

[0045] Consider the following user query command for creating a table:

[0046] CREATE TABLE T (KEY int not null primary key, C1 int, C2 int, C3 int)

[0047] Without a loss of generality, it is assumed that table T has a primary key column (KEY) and all column data types are integer. In accordance with other embodiments of the present invention, the optimization techniques can be applied to other data types or tables that lack a key column (that is, the key column is not present).

[0048] Consider a query which selects the rows in table T whose column values C2 and C3 are greater than 10 and wherein the IN sub-query is satisfied:

	SELECT DISTINCT P.KEY, P.C1, P.C2, P.C3
	FROM TABLE P
	WHERE P.C2 > 10 AND P.C3 > 10
	AND P.C1 IN (SELECT Q.C1
	FROM TABLE Q
	WHERE Q.C2 > 0)

[0049] The above sub-query can be flattened into a join. The equivalent flattened query becomes:

	SELECT DISTINCT P.KEY, P.C1, P.C2, P.C3
	FROM TABLE P, TABLE Q
	WHERE P.C2 > 10 AND P.C3 > 10
	AND P.C1 Q.C1 AND Q.C2 > 0

[0050] The join from the query can be removed to further optimize the query. That is, the quantifier Q can be removed because the following observations can be made:

[0051] 1. the join is based on the same quantifier column of the common table (C1), i.e., the join condition resolves to P.C1P.C1;

[0052] 2. the set of rows that satisfy the predicates P.C2>10 AND P.C3>10 is a subset of the rows that satisfy the predicate Q.C2>0, or equivalently for the sub-query case, every outer row must also appear in the sub-query, and thus the sub-query is always true (except when P.C1 value is NULL);

[0053] 3. moreover, the removability of Q can be assured because:

[0054] a) eliminating Q neither increases nor decreases the output cardinality of the result set due to the presence of the DISTINCT operator; and

[0055] b) columns from Q are not selected for output.

[0056] Based on the above observations, the sub-query (or equivalent join) may be safely removed with the result:

	SELECT DISTINCT P.KEY, P.C1, P.C2, P.C3
	FROM TABLE P
	WHERE P.C2 > 10 AND P.C3 > 10
	AND P.C1 IS NOT NULL

[0057] In the situation where P.C1 is declared as not nullable in the create table statement, as above, the query can further be simplified as is understood to persons skilled in the art. Additional query optimization techniques can be further applied without changing the correctness of this rewritten query.

[0058] Consider a more general query case with the following sub-query:

	SELECT DISTINCT P.KEY, P.*
	FROM T P
	WHERE Pred(P)
	AND P.C1 IN (SELECT Q.C1
	FROM T Q
	WHERE Pred(Q))

[0059] In the example, Pred(P) is a set of predicates on table T in the main query block and Pred(Q) is a set of predicates on table T in the sub-query. Equivalently, this sub-query may be flattened to:

	SELECT DISTINCT P.KEY, P.*
	FROM T P,T Q
	WHERE P.C1 Q.C1 AND Pred(P) AND Pred(Q)

[0060] If, after quantifier mapping, the predicate set Pred(Q) subsumes Pred(P) in terms of row set produced, the query can be simplified, removing the join predicate and the references to quantifier Q and rewriting the predicate set for quantifier P:

	SELECT DISTINCT P.KEY, P.*
	FROM T P
	WHERE Pred(P) AND P.C1 IS NOT NULL

[0061] FIG. 2 is a flow chart illustrating one sequence of operations that is useful in accordance with an embodiment of the present invention for determining conditions for a redundant join elimination using subsumption to optimize a query. It is understood that the sequence of operations may be performed in association with one or more query re-writes performed in accordance with other optimization techniques.

[0062] At block 80, a query is evaluated to identify the presence of a join predicate condition joining a sub-expression of the query to itself. The sub-expression (e.g., a base table or virtual table such as a materialized view or derived table) is referenced by two regular F quantifiers ranging over the sub-expression. The exemplary quantifiers are denoted P and Q. The join predicate condition is evaluated to determine whether the join predicate condition is an equality test between the same quantifier columns of the sub-expression. That is, the join columns must be the same, for example, P.C₁Q.C₁.

[0063] At block 82, a determination is made whether a row set producible by predicate set Pred(P) (i.e., a first set of references to the sub-expression) is subsumed by the row set producible by the predicate set Pred(Q) (i.e., a second set of references to the sub-expression), as discussed previously. In accordance with an embodiment of the present invention, the query may be reformed to remove the join predicate and the references to the quantifier Q (in block 86) if the result set of Pred(Q) subsumes the result set of Pred(P).

[0064] Occasionally, as denoted by dashed lines around block 84, the ability to remove a quantifier (e.g., Q) from the query may require further determination. For example, the query may be evaluated to detect whether one or more quantifier columns of the sub-expression referenced relative to the quantifier to be removed (Q) are selected as an output of the query. If necessary, the query may be reformed to replace the selection of the one or more quantifier columns with like columns referenced relative to quantifier P.

[0065] Further, the presence of the predicate set Pred(Q) in a query may affect query output cardinality. In order to ensure that the removal of a set of references to the sub-expression neither increases nor decreases the output cardinality, in those instances where output cardinality is material, the query may be examined for the presence of the DISTINCT operator. If maintenance of the output cardinality is material, the query may be reformed to remove a quantifier and, hence, the set of references relative to the quantifier, only if the DISTINCT operator is present.

[0066] As is further apparent to those skilled in the art, when reforming the query, it may be necessary to rewrite the set of references for the remaining quantifier to maintain cardinality or otherwise. In the example provided above, the set of references was rewritten to provide the additional predicate P1.C1 IS NOT NULL.

[0067] While this invention is primarily discussed as a method, a person of ordinary skill in the art understands that the apparatus discussed above with reference to a computer-implemented database processing system may be programmed or configured to enable the practice of the method of embodiments of the present invention. Moreover, an article of manufacture for use with a data processing system, such as a prerecorded storage device or other similar computer readable medium including program instructions recorded thereon may direct the data processing system to facilitate the practice of the method of embodiments of the present invention. It is understood that such apparatus and articles of manufacture also come within the scope of the invention.