1. Field of the Invention
This invention relates generally to computer-implemented systems for optimal query execution in relational database processing systems and particularly to a system for optimizing query ordering requirements by normalization of relational order specifications to accommodate predicates and functional dependencies before order detection in a query compiler system.
2. Description of the Related Art
A relational database management system (RDBMS) is a computer-implemented database processing system that uses relational techniques for storing and retrieving data. Relational database management systems are computerized information storage and retrieval systems in which data in the form of tables (formally denominated "relations") are typically stored for use on disk drives or similar mass data stores. A "relation" includes a set of rows (formally denominated "tuples" or "records") spanning several columns (formally denominated "attributes"). Each "attribute" in a relation includes "restrictions" on the data contents thereof, which may include designation as a primary or foreign key. A "tuple" expresses a mathematical relation between its "attributes" (column elements), while a "record" does not. Reference is made to C. J. Date, An Introduction to Database Systems, 6th Edition, Addison-Wesley Publishing Company, Reading, Mass. (1994) for a general treatment of the relational database art.
A relational database processing system is structured to accept commands to store, retrieve and delete data using high-level query languages such as the Structured Query Language (SQL). As used herein, a "query" refers to a set of user commands for retrieving data from a stored database. The query language requires the return of a particular data set (relation) in response to a particular query but the method of query execution employed by the database management system is not specified by the query. The method of query execution is herein denominated the "Query Execution Plan (QEP)" and there are typically many different useful QEPs for any particular user query, each of which returns the required data set. For large databases, the execution plan selected to execute a query must provide the required data return at a reasonable cost in time and hardware resources. Most RDBPSs include a query compiler to translate queries into a QEP, which includes a query optimizer to select an efficiently executable QEP.
Among many well-known SQL commands, a SQL query may include the ORDER BY clause. For instance, the following SQL query example returns a list of movie titles, in alphabetical order, from a relation keyed to movie stars:
SELECT DISTINCT MOVIE.sub.-- TITLE
FROM MOVIE.sub.-- STARS PA1 ORDER BY MOVIE.sub.-- TITLE ASC;
In this example, only one attribute or column is used for ordering. ASC requires an ascending order, as opposed to DESC for descending order. This query imposes an "order requirement" that must be satisfied by the query compiler when it generates a QEP. Moreover, the query compiler itself may generate internal order requirements arising from combinations of other SQL operations. For example, the internal procedures used to satisfy GROUP BY and DISTINCT clauses generally require an input record stream with an "order property". The sort-merge join operation is known in the art to require an "order property" in each of its record stream inputs. Also, where VIEW specifications are used, an order requirement may arise for the intermediate results of a query as well as for the final query data return. As used herein, the terms "order property" and "order requirement" refer to two order specifications imposed on a group of records in a relation. Such order specifications list one or more "attributes" (columns) within each record on which the records are ordered.
A typical RDBPS puts records in order by either sorting the records on their "order requirement" attributes or, when possible, by scanning an existing index that already provides the required ordering. Sorting is a costly operation that is avoided when possible, so the typical query compiler first searches for an existing index that satisfies the order requirement. As used herein, an "index" is a user-defined relation that maintains a certain order of records. Each relation may be associated with any number of indexes or with no index. When no index can be found, sorting is unavoidable and the query compiler then attempts to minimize the number of sort "attributes" to optimize execution plan efficiency. Thus, as it generates an execution plan, a query compiler must detect whether a sort can be avoided and, if unavoidable, how many attributes in the "sort requirement" may be eliminated during actual sorting. This process is herein denominated "order detection". The following example illustrates the "order detection" problem known in the art:
SELECT SALARY, NAME
FROM EMP
WHERE SALARY=50,000
AND DEPTNO=:HV
ORDER BY 1,2;
In this SQL example, each execution plan must produce a stream of records in the order specified by the ORDER BY clause. Consequently, the query compiler must satisfy the order requirement (SALARY, NAME), with SALARY being the major ordering attribute. If an ascending index exists on attributes (SALARY, NAME), then an index scan produces the required "order property" without sorting. Alternatively, an unordered table scan followed by a sorting process may be employed to produce the required "order property" in the final relation. Typically, a query compiler considers both plans and chooses the less expensive to execute.
In the above example, if an ascending index also exists on the NAME attribute, then such index could also be used to produce the requisite order property without sorting. No sorting is actually then required because the SALARY attribute is bound to a constant by the predicate SALARY=50,000. Accordingly, the SALARY attribute does not affect the order property because all qualifying records have the same SALARY attribute (the same value in the SALARY column). Similarly, where an unordered table scan and sort are used, the sort need only be on the NAME attribute. Finally, if an index is found for (DEPTNO, NAME), it also satisfies the order requirement without sorting because, like the SALARY attribute, the DEPTNO attribute is bound to a constant (in this case to a host variable value).
The above-described example shows how the order detection process could improve execution efficiency if it could be aware of which relation attributes are "bound" to constants by way of predicates during execution plan generation. Order detection could also improve efficiency if it could be aware of keys and any functional dependencies arising therefrom, as illustrated by the following example:
SELECT E.EMPNO, E.NAME, D.DEPTNO
FROM EMP E, DEPT D
WHERE E.DEPTNO=D.DEPTNO
ORDER BY 1,2,3;
In this SQL query example, the query compiler must satisfy the order requirement vector (E.EMPNO, E.NAME, D.DEPTNO), which includes the first, second and third attributes in each record. If the EMPNO attribute is a key of the EMP relation, then sorting on EMPNO alone is sufficient to meet this order requirement. Alternatively, using an index ordered on EMPNO is sufficient without sorting. The skilled database practitioner can appreciate the reason for this sufficiency, which arises because the primary key EMPNO creates a "functional dependency" between the EMPNO attribute and all other attributes within the relation. This functional dependency combined with the predicate E.DEPTNO=D. DEPTNO means that E.EMPNO "functionally determines" both E.NAME and D.DEPTNO, which in turn implies that sorting on E.EMPNO is sufficient to create the three-attribute order property specified by the above example. Until now, the sort detection processes in the art have not been aware of these relationships.
Succinctly, a "functional dependency" herein denotes a relationship between two attributes where "A functionally determines B" when every record in a relation that has a particular value for attribute A has an unchanging value for attribute B. In the art, this functional dependency is denoted by the standard notation A.fwdarw.B. An attribute B is "functionally dependent" on a set of attributes or columns C={C.sub.1, C.sub.2, . . . , C.sub.n } if, for any two records with the same values for the columns C, the value of column B is the same. Equivalently, it is said B is functionally determined by C, which is denoted as C.fwdarw.B. As is known in the art, key attributes are actually a special case of functional dependency referred to as a "key dependency". A key dependency functionally determines all columns of the record stream for which it is a key. Any remaining dependencies are denoted "non-key dependencies". Functional dependencies usually arise from keys, whether primary or foreign. Joins and other relational operations can transform a key dependency into a non-key dependency. Relational operations such as DISTINCT and GROUP BY can add key dependencies to derived relations. For the purposes of this disclosure, it is assumed that means are available to determine whether C.fwdarw.B is true.
Reference is made to Hugh Darwen et al. (RELATIONAL DATABASE WRITINGS 1989-1991, C. J. Date with Hugh Darwen, Chapter 10: The Role of Functional Dependencies in Query Decomposition for a description of the semantic concept of functional dependencies. Darwen et al. suggest algorithms for deriving functional dependencies from base relations and for propagating functional dependencies across derived relations. Darwen et al. also consider a variety of uses for functional dependencies by a RDBMS query compiler, but they neither consider nor suggest how to accommodate functional dependencies during order detection.
As is known in the art, a query compiler for a relational database processing system translates a high-level query into a query execution plan (QEP), which is then interpreted by a database engine at run time. Conceptually, a QEP is viewed in the art as a data flow graph of operators, whese each node in the graph corresponds to a set of output records arising from a relational operation such as "join" or a lower-level operation such as "sort". FIG. 2 shows a query execution plan (QEP) for the following exemplary SQL qudry.
SELECT NAME, ADDRESS
FROM EMP E, DEPT D
WHERE E.DNO=D.DNO AND MGR=`Haas`
Note that the QEP in FIG. 2 is a directed graph of LOw LEvel Plan OPerators (LOLEPOPs), herein formally denominated "relation nodes". Note that the data-flow arcs exemplified by arc 12 point toward the source of the record stream and not in the direction of data-flow. For instance, the SORT node 14, representing a relational SORT operation, receives a record stream from the ACCESS node 16 along the directed data-flow arc 18 and produces a directed record stream along arc 12 to the JOIN node 20. For the purposes of this disclosure, notice that each relation node in FIG. 2 is coupled to one or more other relation nodes by data-flow arcs (herein formally denominated "directed record streams") exemplified by directed record streams 12 and 18. With the notation used herein, each relation node N.sub.i consumes one or more incoming record streams {R.sub.ji } and produces at least one output record stream R.sub.ik that is directed to one or more other nodes (k and j may each assume more than one value). In the example shown in FIG. 2, each relation node produces only one output record stream routed as an input record stream to one other relation node.
Reference is made to Guy M. Lohman ("Grammar-like Functional Rules for Representing Query Optimization Alternatives", A CM SIGMOD International Conference on Management of Data, 1988, pp. 18-27) for a detailed discussion of the "properties" associated with relation nodes or operators in a QEP. Every relation node is associated with a set of properties that summarizes the work accomplished in the relation thus far in the dataflow path from bottom (base-tables) to top (TOP node). Lohman et al. discuss these properties in terms of the query execution cost model and notes that all properties are handled uniformly as elements of a "property vector", which is easily extended to include more properties. The "property vector" includes the "attributes property", herein denominating the columns of a record stream, which may include columns from base-relations and those derived from expressions. The "attributes property" is used to track the record stream columns.
Examples of properties include the set of attributes that make up each record or tuple in the stream, represented by the head of each node. Other examples include the set of predicates that are applied to the incoming records within the node body, the specification of which attributes form unique keys and/or functional dependencies (if any), the order specification for the record stream, and the like. Each relational operator node in a QEP determines the properties of its output record stream.
The properties of an output record stream from a node are a function of the node input streams and the internal operations applied within the node. For example, a sort operation passes on all of the properties of its input stream unchanged except for the order property. A query compiler typically constructs a QEP from the bottom up, operator by operator, computing and updating properties as it proceeds. Depending on the implementation, some properties may be stored in QEP operators (within "nodes") while others may be recomputed when needed to save space.
Each node in a QEP receives one or more directed record streams each having an "order property". By virtue of operations within the node, each node produces an output record stream according to an "order requirement". As discussed above, the ORDER BY, GROUP BY, and DISTINCT specifications create order requirements. Moreover, the query compiler may generate order requirements, depending on the alternative execution plan characteristics. An example of an execution strategy is the "sort merge join" operation, which requires certain order properties in the incoming record streams. There may be multiple order requirements imposed within any given SQL query. Both order properties and order requirements are represented by an order specification and are herein referred to generally as order specifications. As a simple example, ORDER BY C.sub.1, C.sub.2, C.sub.3 gives rise to the order requirement vector (C.sub.1, C.sub.2, C.sub.3). In the case of the GROUP BY and DISTINCT clauses, any permutation of the order specification suffices. For example, GROUP BY C.sub.1, C.sub.2 is represented by either of the order requirements (C.sub.1, C.sub.2) and (C.sub.2, C.sub.1). The order requirement of the GROUP BY operation is satisfied if either order requirement is satisfied. In some query compilers, these two order requirement vectors can be represented as a single order requirement specification. For the purposes of this disclosure and without loss of generality, it is assumed that each record stream must satisfy only a single order requirement. In the general case, many order requirements may be imposed on a single record stream, which might benefit from additional procedures to "compact" multiple order requirements into a single order specification.
As a QEP is constructed, order requirements must be satisfied. That is, for instance, when an ORDER BY operator is added to the QEP, the "order detection" procedure examines the "order property" of the vector associated with the input stream to determine whether it satisfies the "order requirement" imposed by relational operations in the local relation node. If the "order property" of the incoming record stream does not satisfy the "order requirement" imposed by the receiving relation node, then the query compiler adds a sort operator to the QEP, representing an additional operation internal to the receiving relation node. This sort operator adds substantial cost to the resulting QEP and it is a desired function of the "order detection" procedure to avoid adding sort operators wherever possible.
Initially, the properties of stored base tables and access methods are determined from the system catalogs. At first, no predicates are applied and no cost has been incurred in the query. The "order property" is unknown unless the base relation is known to store records in some order or if an index is used to access the relation in which case the order is defined by the set of attributes on which the records are ordered.
During compilation, the predicates in a SQL query are usually broken down into conjunctive normal form. This permits each conjunct to be applied as an independent predicate. When a predicate or conjunct is applied to an input record stream, each record in the resulting output record stream is imprinted with the "property" that it satisfies the predicate. Herein, the term "predicate property" denominates the property used to track all predicates that have been applied to a record stream.
The "order property" for a record stream represents the physical ordering of the stream's records. An order property is denoted by listing the attributes or columns of the order in major to minor sequence. Such representation is herein denominated an "order specification vector". For example, (C.sub.1, C.sub.2, C.sub.3) is an "order specification vector" with C.sub.1 as the most major ordering column and C.sub.3 is the most minor ordering column. Column C.sub.2 is in a "more major" position relative to C.sub.3 and in a "more minor" position relative to C.sub.1. Two records are ordered with respect to an "order requirement" vector by comparing attribute values in most major to most minor sequence until order is determined (ISO-ANSI, "ISO-ANSI Working Draft: Database Language SQL2 and SQL3; X3H2; ISO/IEC/JTC1/SC21/WG3, 1993"). A record stream can acquire an "order property" because of an index access or a sort operation while other operations may preserve the order of an input record stream. For example, a nested-loop join operation preserves the order of the outer relation.
The "functional dependency" property specifies a collection of functional dependencies that hold for the attributes of the record stream. For base relations, these are typically the key dependencies of the base relations. Operations that remove duplicates can add key dependencies as described above. Key dependencies survive joins as non-key functional dependencies. The above-cited Darwen et al. reference describes the functional dependency derivation and propagation for relational operations. For the order detection process, the "functional dependency" property permits enumeration of all functional dependencies holding for the record stream.
There is an untilled need in the art for a sort detection process that permits the query compiler to understand and exploit the effects of both predicates and functional dependencies during order detection. The failure in the art to account for these effects causes the query compiler to inject unnecessary sorts or to sort on more attributes than necessary. This in turn causes the compiler to generate suboptimal query execution plans. The desire to reduce QEP cost in large database systems motivates the need for any useful method that avoids unnecessary sort operations during execution plan generation.
Practitioners in the relational database art generally appreciate the absence of a solution to this problem. For instance, Boykin et al. ("Order Class Detection", IBM Technical Disclosure Bulletin, Vol. 32, no. 52, pp. 283-285, October, 1989) discuss the continuing need to improve order detection during query optimization. Boykin et al. propose a process for recognizing when special combined order classes can be constructed to satisfy the order requirements arising from more than one order specification in a query. An order class is a list of attributes or columns, each having the attribute "ascending", "descending", or "either". The combined order classes are used to locate indexes or to specify the sorting operation necessary to satisfy the order requirements. As used herein, the "order class" is denominated an "order specification vector", which may be an "order property vector O.sub.Pi " or an "order requirement vector O.sub.Ri ". By combining the "order specification vectors" within a query, Boykin et al. permit the query compiler to insert a single sort to satisfy two separate ordering requirements, but do not consider the effects of functional dependencies or predicates on sort specifications.
L. W. Yongren ("Dynamic Ordering of Joined Rows using Fields from Multiple Tables", IBM Technical Disclosure Bulletin, Vol. 36, no. 11, pp. 363-366, November 1993) disclose a method for ordering joined "live" data (dynamic views) without producing a temporary result table. Yongren proposes maintaining indexes that can be updated responsive to updates to the underlying base-relations. By providing for a "composite index", Yongren is able to avoid resorting operations during the maintenance of dynamic VIEW tables, but he neither considers nor suggests methods for eliminating sort operations or index scans by exploiting functional dependencies.
Similarly, in U.S. Pat. No. 5,241,648, Cheng et al. propose a hybrid method for joining tables that relies on maintaining indexes to speed the nested join procedure. In U.S. Pat. No. 5,369,761, Conley et al. speed the table join operation by selectively "denormalizing" the base-relations to avoid joining unnecessary attributes. Neither Conley et al. nor Cheng et al. consider or suggest methods for eliminating sort operations by detecting redundancy arising from functional dependencies.
There is a need in the art for an order detection process that fully assimilates and exploits the effects of both predicates and functional dependencies to avoid sorting whenever possible. The absence in the art of any process for exploiting predicate and functional dependency effects during query order detection reduces query execution plan efficiencies. These unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.