US 6,330,552 B1Grant
Database query cost model optimizer
Issue Date:2001-12-11
•8 Claims
•7 Drawing Sheets
Abstract
A method and apparatus is disclosed for accurately estimating the cost of a database query, including the total computer resources used and estimated elapsed time for the production of a first row and last row of an operator involved in the query and/or the total resources used and elapsed time for returning the overall response to a database query. The method and apparatus accurately accounts for resources used and elapsed time associated with blocking operators, such as sorts and hash joins, which cannot produce a first row until they have completed their operations.
Metadata
Assignee
- Compaq
Inventors
- Christopher M. Farrar
- Harry A. Leslie
- Pedro Celis
- Diana L. Shak
- Jay H. Vaishnav
- Michael J. Skarpelos
Application Information
Application Number:US 09/162,638
Filing Date:1998-09-28
Priority Date:1998-09-28
Art Unit:7
Classifications
IPC:
G06F 1760
Field of Search:
705400707 1707 2
Patent Drawings (7 sheets)
Description
Cross-Reference to Related Application
[0002] This application is related to the co-pending U.S. patent application Ser. No. 09/162,245 of Christopher M. Farrar, Harry A. Leslie, Pedro Celis and Diana L. Shak, entitled “Histogram Synthesis Modeler for a Database Query Optimizer,” filed Sep. 28, 1998. This patent application is incorporated herein by reference.
Background of the Invention
[0003] This invention relates to the field of database query optimizers, and more particularly, to an improved database query optimizer that can select a query plan based upon different performance goals, such as returning the first or last row of a query in the minimum amount of time, or minimizing the use of computer resources such as computer memory.
[0004] Computers have the capability of storing vast amounts of data. For example, computers can store and retain data related to thousands of employees of large multi-national corporations, including the departments in which they work, their employee numbers, salaries, job descriptions, geographical locations, etc. In order to extract selected pieces of that data from such large computerized databases, users can present a query to the database system in the form of an SQL statement. For example, an SQL statement may ask the database system to list the names of all employees having employee numbers 1001 to 2000. A properly structured SQL statement will result in a list of records that satisfy the question or “query.” In this example, the query would produce the names of 1000 employees, assuming that the employees had sequential employee numbers.
[0005] Once the user inputs a query into the computer, an SQL compiler operates on the query to develop an efficient way to extract the desired information from the database. Typically, the compiler generates a large number of different, but logically equivalent, plans for executing the same query. These “plans” are typically represented in computer memory as query trees, wherein each node of the tree includes a relational operator, such as a “sort” or “merge” operator. “Relational operators” are operators that receive one or more tables as input and produce a new table as an output. Join, Union and Union All are examples of operators that receive two tables as inputs. Group-by and Sort are examples of relational operators that receive only one table as input, such as a “sort” or “merge” operator. The optimizer program selects the query tree with the lowest estimated cost to respond to the query. In database parlance, “cost” is usually measured in terms of the amount of computer resources utilized by the computer in executing the SQL statement, for example, the number of I/O's or CPU instructions.
[0006] A major problem with existing optimizers is that, in many cases, they do not properly estimate the cost of carrying out the query. For example, known optimizers first estimate the number of CPU instructions, I/O operations and, in distributed systems, the number of messages that would be needed to carry out the SQL statement. See, e.g., P. G. Selinger, et al., “Access Path Selection in a Relational Database Management System,” Proceedings of the ACM-SIGMOD International Conference on Management of Data, June 1979, and L. F. Mackert and G. M. Lohman, “R* Optimizer Validation and Performance Evaluation for Distributed Queries,” Proceeding of the Twelfth International Conference on Very Large Data Bases, Kyoto, Japan, August, 1986. Once the number of such instructions, I/O operators and messages is predicted, such optimizers assign a cost to each operator, add up the cost associated with the execution of each operator and thus produce a total predicted cost for the particular plan. The cost of various plans are calculated and compared. Then, the operator can select the lowest cost plan for execution.
[0007] Unfortunately, because the computer can conduct some operations in parallel while others must be conducted serially, these optimizers cannot properly predict which plan will produce the first row or the last row in a minimum amount of time. Minimizing the amount of time needed to produce the first or last row of a query is often more important than the cost of the query in terms of the physical resources utilized in executing the query. Thus, there is a need for an improved database cost model that accurately accounts for speed in returning an answer to a query as well as the resources utilized. In short, time may be the most important “cost” associated with a query.
[0008] Known prior art optimizers also do not properly account for memory utilization. In situations where the memory of the computer is limited and/or where the algorithm utilizes large amounts of data, memory utilization is an important parameter to consider in determining the cost of the query. It will be recognized that the execution of an SQL statement will cause the computer to utilize certain resources such as, for example, CPU instructions and disk seeks. These types of resources clearly have some elapsed time associated with their execution. Therefore, one can predict that, all else being equal, an SQL statement that requires more instructions and more seeks than another statement will take longer to return a row than the other statement. However, the relationship between memory utilization and elapsed time is much more complicated and not at all intuitive. For example, a statement that uses more memory may actually execute faster than one which uses less memory. This complicated relationship between memory utilization and elapsed time may be one of the reasons that prior art optimizers have failed to account for memory utilization.
[0009] In view of all of the above, there is a need for an improved optimizer. In particular, there is a need for an optimizer that can consider and account for flexible performance goals, such as how quickly a plan returns a first row, or a last row, or selecting a plan that will minimize the usage of certain types of computer resources, and one that properly accounts for memory utilization.
Summary of the Invention
[0010] For most database queries, the requested information can be obtained in various ways. Each way of obtaining the information involves a series of operations on the database called a “plan.” The present invention is directed to a method, and related software and devices, for use with database query optimizers, for calculating the cost of implementing various plans and selecting the plan that best accommodates the particular desired performance goals. For example, the optimizer of the present invention can choose plans based on one of at least three performance goals: elapsed time to produce the first row of a query, elapsed time to produce the last row of a query and total resource usage based on a user supplied weighting of resource components.
[0011] When a user inputs a query into the computer, the SQL compiler operates on the query statement to produce an executable query plan. The compiling process typically includes a number of discrete steps which are handled by different components of the compiler. First, a “parser” component verifies the syntax of the original SQL statement. If the syntax is correct, it produces a syntactically correct query tree. A “binder” component then checks the semantic content of the tree. Then, a “normalizer” component transforms the semantically correct query tree into canonical form. The canonical tree represents, typically, a very large number of logically equivalent ways of processing the query posed by the SQL statement. The “optimizer” component then operates on the canonical tree to generate a set of the logically equivalent query trees. According to the present invention, the optimizer then estimates the cost associated with carrying out each plan and selects the plan that best achieves the desired goal.
[0012] For the sake of clarity of explanation, the cost estimating process can be viewed as involving two phases. In the first phase, the downward portion of a depth-first query tree traversal, the optimizer assigns a “cost” to each operator in the query tree. A “cost” consists of a set of “resource vectors” which in turn represent resources utilized by the operator to satisfy a particular performance goal. The resources include CPU instructions, number of disk seeks, kilobytes of I/O transfers, normal and persistent memory utilized, number of messages and kilobytes transferred by those messages, temporary disk storage space used, the number of times the operator will be executed, and the amount of time the operator spends (i) waiting for results from descendent operators in the query tree and (ii) waiting caused by the use of multiple resources that can not be used concurrently. This last value, which measures types of waiting time, is called “blocking/idle time”.
[0013] In the second phase of the process, known as cost roll-up, during the upward traversal of the query tree, the optimizer combines the costs associated with each node of the plan. The present invention includes a sophisticated vector algebra designed to accurately model the interaction between operators in the query tree when performing cost roll-up. Specifically, the roll-up formulas of the present invention use the sophisticated vector algebra to model the blocking behavior of some operators and also how operators in the query tree overlap. (A blocking operator must wait, i.e. “block”, until it receives all rows from all its children before it can return a single row to its parent.) The cost roll-up formulas and the underlying vector algebra on which they are based are described below.
[0014] The present invention also includes various formula that allow elapsed time to be computed from the resource vectors, so that various plans can be evaluated, not only in terms of resource usage, but also in terms of elapsed time to produce a first or last row.
Brief Description of the Drawings
[0015] FIG. 1 is a block diagram of a computer system for implementing a preferred embodiment of the present invention.
[0016] FIG. 2 is a flow chart illustrating the steps of a preferred embodiment of the present invention.
[0017] FIG. 3 is an illustration of a generalized cost roll-up from grandchild to child to parent operator.
[0018] FIG. 4 is an illustration of the merging of child costs and the roll-up of the merged costs with the parent's costs.
[0019] FIG. 5 is an illustration of a unary roll-up involving a non-blocking parent.
[0020] FIG. 6 is an illustration of a unary roll-up involving a blocking parent.
[0021] FIG. 7 is an illustration of a transformation in which, in a Nested Loops Join (“NLJ”), the left child is treated as a unary child of the NLJ operator's right child.
Detailed Description of the Preferred Embodiments
[0022] An execution plan for a particular database query consists of relational operators forming the nodes of a query tree. Each operator in such a query tree has an associated cost. The optimizer of the present invention combines the costs associated with each operator in the query tree to produce the total cost of the query plan. The optimizer then uses these costs to determine, amongst many logically equivalent plans, the plan which best accommodates the desired goal. The optimizer selects this plan, and it may then be executed. As previously mentioned, the cost of the various operators is combined according to a special vector calculus. The “cost” of a plan may be described in terms of the total physical resources of the computer engaged in implementing the query, or it may be measured in terms of the time required to produce the first or last row of data resulting from the query.
[0023] Overview of the Computer System
[0024] The present invention may be implemented on a computer system, such as that illustrated in FIG. 1. FIG. 1 is a block diagram of a data processing system 100. The data processing system 100 has at least one processor 102 and associated computer memory 104. The memory 104 includes at least the “parser” 106, “binder” 108, “normalizer” 110 and “optimizer” 112 software components of the SQL compiler for implementing the tasks described herein. The steps of the described embodiments of the present invention may be performed when instructions contained in memory 104 are executed by processor 102.
[0025] System 100 also includes a network connection 114, such as a connection to a LAN or a WAN. System 100 includes an input device(s) 118 such as a keyboard, touch screen, or the like. System 100 includes an output device(s) 120 such as a printer, display screen or the like. System 100 also includes a computer readable medium input device 122 and a computer readable medium 124. Computer readable medium 124 can be any appropriate medium that has instructions and data stored thereon. These instructions are loaded from computer readable medium 124 into computer memory 104. Instructions can also be loaded into memory in the form of a carrier wave over network connection 114. Thus, the instructions and data in computer memory 104 can be loaded into memory via an input device, such as a network, a LAN or a WAN, or can be loaded from a computer readable medium such as a disk, tape or other appropriate computer readable media. The instructions comprising each of the software programs described herein can also be downloaded in the form of a carrier wave over a network connection.
[0026] System 100 includes an operating system (not shown). A person of ordinary skill in the art will understand that the memory 104 and computer readable media 124 may also contain additional information, such as other application programs, operating systems, other data, etc., which are not shown in the figure for the sake of clarity. It also will be understood that data processing system 100 (or any other data processing system described herein) can include numerous elements not shown in FIG. 1, such as additional data, software, and/or information in memory, disk drives, keyboards, display devices, network connections, additional memory, additional CPUs, LANs, input/output lines, etc.
[0027] Overview of the Inventive Process
[0028] FIG. 2 illustrates a presently preferred process according to the subject invention. As shown in FIG. 2, a query in SQL format is first presented to the database system 210, for example via input device 118. The parser 106, binder 108, normalizer 110 and optimizer software 112 operate on the query statement, as set forth above and as illustrated at 212, 216 and 218, respectively, to generate a set of logically equivalent trees. Each node of these query trees represents a relational operator. Based upon the type of operator represented, the optimizer 112 assigns a preliminary cost 220 to that operator. The preliminary cost consists of a set of vectors that each represent the amount of resources the operator will use with respect to a particular performance goal while executing on behalf of the query. The optimizer combines the cost objects of all operators in the query tree according to the “roll-up” formulas described below and thus produces a cost for the overall query plan (222). After the optimizer compares the cost of logically equivalent plans and chooses the least expensive plan with respect to a specified performance goal 224 it delivers the selected plan to the database execution program which in turn implements 226 the selected plan.
[0029] Costing Primitives
[0030] This section describes the underlying costing primitives necessary for understanding subsequent roll-up formulas.
[0031] A Cost object consists of four SimpleCostVector objects which in turn each contain ten CostScalar objects as vector components. Each SimpleCostVector object measures an amount of resource usage. To determine the less expensive of two Cost objects, one must specify, not only the two Cost objects, but also a performance goal; two costs may compare differently depending on the specified performance goal.
[0032] A SimpleCostVector object consists of ten scalar components which respectively measure the following resource usage associated with a query operator:
[0033] 1) CPU (cpu)
[0034] A count of CPU instructions. In the presently preferred embodiment, each unit value equates to 1000 machine instructions. Therefore, a value of 1 means 1000 machine instructions, 2 mean 2000 machine instructions, etc..
[0035] 2) Seeks (s)
[0036] Number of random I/O's, e.g., the number of head positionings of a disk drive for sequential reads.
[0037] 3) I/O Transfer (k)
[0038] Kilobytes of I/O transferred.
[0039] 4) Normal Memory (nm)
[0040] Amount of memory (in Kilobytes) needed to hold working buffers, hash tables, etc., during the execution of an operator.
[0041] 5) Persistent Memory (pm)
[0042] Amount of memory (in Kilobytes) which persists after operator completion.
[0043] 6) Messages (m)
[0044] A count of the number of messages between processes running on different nodes in a cluster.
[0045] 7) Message Transfer (mkb)
[0046] Number of Kilobytes transferred for all messages.
[0047] 8) Temporary Disk Space (tds)
[0048] Amount of disk space (in Kilobytes) used for temporary files.
[0049] 9) Repeat Count (rcount)
[0050] Also known as number of “probes.” This value represents the number of times the operator will be executed. Typically, this value will be 1 (one), but in some cases (e.g. the inner scan of a nested loops join) it can be greater than one.
[0051] 10) Blocking/Idle Time (blk_idlt)
[0052] The amount of time spent waiting for child operators in the expression tree.
[0053] Computing Elapsed Times for SimpleCostVector Objects
[0054] Given a resource vector, the formulas below may be used to compute the estimated elapsed time associated with a SimpleCostVector. In these formulas, FF(x) represents the weighting assigned to component x. FF(x) multiplied by x yields the elapsed time for component x. In the present embodiment of the invention, for each component x, FF(x) is determined empirically through a calibration process. The calibration process is performed by executing a query to determine its actual elapsed time and then adjusting the value of FF(x) until the cost model predicts the actual elapsed time for the execution of the query.
[0055] Page Fault Time
[0056] pft=max(0, nm−physical_memory)*FF(normal_memory_page_faults)
[0057] The elapsed time for page faults, pft, depends on available physical memory and the amount of normal memory used to execute the query. The term nm−physical_memory indicates the amount of normal memory which does not have physical memory underneath it and is thus subject to page faults. Of course, if available physical memory exceeds normal memory, then the formula should not result in a negative elapsed time. Therefore, max(0, nm−physical_memory) selects the maximum of zero or the value for nm−physical_memory to ensure that pft will always be non-negative.
[0058] CPU Elapsed Time
[0059] cput=cpu*FF(cpu)+pft
[0060] CPU elapsed time, cput, consists of both the elapsed time for the CPU component and elapsed time for page faults.
[0061] I/O Elapsed Time
[0062] sit(s,k)=FF(s)*s+FF(k)*k
[0063] I/O elapsed time, sit(s,k), consists of both the elapsed time for seeks and elapsed time for Kilobyte transfers.
[0064] Message Elapsed Time
[0065] mt(m,mkb)=FF(m)*m+FF(mkb)*mkb
[0066] Message elapsed time, mt(m,mbk), consists of the elapsed time for messages, taking into consideration the number of messages and the number of kilobytes transferred for all messages.
[0067] Elapsed Time for a Vector
[0068] Given a vector, the following formula yields the elapsed time for the execution of the associated operator:
[0069] elapsedTime=max(sit(s,k), mt(m,mkb), cput)+blk—idlt.
[0070] This formula relies on the assumption that, for a given resource vector, I/O, messaging and CPU can overlap. Therefore, the formula takes the maximum of their associated elapsed times and adds that value to the blocking/idle time.
[0071] Total Resource Usage
[0072] Given a resource vector and a performance goal of optimizing for minimal resource usage, the total resource usage may be calculated as a weighted sum of each component in the resource vector. A database administrator may provide these weights through a user interface.
[0073] Cost Object
[0074] A cost object consists of the four SimpleCostVector objects set forth below. In this context, “current process,” as used in connection with the second, third and fourth objects listed below, refers to the operator whose cost is being considered.
[0075] 1) Total Cost (TC)
[0076] This vector represents the resource usage necessary for the associated operator in the expression tree to execute in its entirety. Query parallelism typically has no effect on TC. For repeat counts greater than one, this vector represents cumulative usage for all probes.
[0077] 2) Current Process First Row (CPFR)
[0078] This vector represents resource usage necessary for the associated operator in the expression tree to produce its first row after any blocking activity has occurred. For repeat counts greater than one, this vector represents the resource usage necessary to produce the first row in an average probe, not the first row of the first probe.
[0079] 3) Current Process Last Row (CPLR)
[0080] This vector represents resource usage necessary for the associated operator in the expression tree to produce its last row after any blocking activity has occurred. Thus, for repeat counts greater than one, this vector represents cumulative usage for all probes.
[0081] 4) Current Process Total Blocking (CPTB)
[0082] If an operator must wait for one or more of its descendants to fully complete before it can produce its first row, it is called a “blocking” operator. Examples of blocking operators include sort and hash-group-by operators. Typically, a blocking operator consists of a blocking phase when it builds some data structure (e.g. a sorted temporary file in the case of sort, a hash table in the case of hash-group-by, etc.) and an output phase in which it uses the data structure from the blocking phase to produce its output rows. CPTB represents resources used by a blocking operator and its descendants during the blocking operator's blocking phase. CPTB will equal the zero vector for non-blocking operators having no blocking descendants. For repeat counts greater than one, CPTB represents the average usage per probe.
[0083] Computing Elapsed Times for Cost Objects
[0084] Given a Cost object and a performance goal specifying either first row or last row optimization, a presently preferred embodiment of the present invention computes the elapsed time for the Cost object in question, as follows:
[0085] Elapsed Time for a First Row Performance Goal
[0086] The following formula may be used to calculate the elapsed time for a plan to produce the first row:
[0087] elapsedTime=ET(CPFR)+ET(CPTB)
[0088] In this formula, ET(CPTB) and ET(CPFR) represent the elapsed times of the CPTB vector and the CPFR vector respectively for the Cost object in question. The formula takes into account the elapsed time to produce the first row plus the elapsed time of any preceding blocking activity.
[0089] Elapsed Time for a Last Row Performance Goal
[0090] The following formula may be used to calculate the elapsed time for a plan to produce the last row:
[0091] elapsedTime=ET(CPLR)+ET(CPTB)*RC(CPTB)
[0092] In this formula, ET(CPTB) and ET(CPLR) represent the elapsed times of the CPTB vector and the CPLR vector respectively for the Cost object in question. RC(CPTB) represents the repeat count for the CPTB vector. The term ET(CPTB)*RC(CPTB) represents the cumulative blocking time of all probes. This formula takes into account the elapsed time to produce the last row of the last probe, plus the elapsed time of any blocking activity over all probes.
[0093] Minimal Resource Performance Goal
[0094] When optimizing for a performance goal of minimal resource usage, the optimizer does not calculate an elapsed time, but instead calculates a weighted sum of each component in the TC vector. In a presently preferred embodiment, a database administrator may assign the relative weights to each component of the TC vector. If the administrator wants to limit the usage of a particular resource, the administrator can assign a greater relative weight to the component of the TC vector that reflects the usage of that resource.
[0095] Algebra for SimpleCostVector Objects
[0096] In order to roll up Cost objects associated with physical operators in a query tree, the following algebra is used for SimpleCostVector objects.
[0097] Zero Vectors
[0098] A vector with zeros in all components (except repeat count) is called a zero vector and is represented as “Z.” A vector having a non-zero Blocking/Idle time component of x and zeros in all other components (except repeat count) is called a blocking/idle vector. It is represented as I(x).
[0099] Vector Arithmetic
[0100] SimpleCostVector objects can be added and subtracted. SimpleCostVectors can be multiplied and divided by scalars. These operations are denoted as +V, −V, *Vand /Vrespectively. Vector addition (+V) involves adding the corresponding components (except repeat count) of two vectors, as in traditional linear algebra. The repeat count component of the result vector retains the repeat count of the first vector specified. (When adding average resource usage vectors, i.e. CPTB, the repeat counts for both vectors should be the same. Similarly, vector subtraction (−V) involves subtracting the corresponding components (except repeat count) of two vectors. Since the present invention does not allow negative resource usage, any resulting negative component is converted to zero. The repeat count component of the result vector retains the repeat count of the first vector specified.
[0101] Multiplying a SimpleCostVector object by a scalar involves multiplying each component, except Normal Memory, Persistent Memory and repeat count, by the specified scalar. Normal Memory and Persistent Memory remain unchanged because memory is reused. Thus, the number of times an operator executes does not affect its memory consumption. Similarly, dividing a SimpleCostVectorobject by a scalar involves dividing each component (except Normal Memory, Persistent Memory and repeat count) by the specified scalar.
[0102] The present invention involves two additional forms of vector addition: overlapped vector addition (denoted +O), and blocking vector addition (denoted +B). Overlapped vector addition takes into account that in some cases I/O and messaging partially overlap, i.e., they can occur at the same time. Thus, the CPU, Normal Memory, Persistent Memory and Temporary Disk Space components get added together according to the vector addition described above, but the I/O and message related components use the following formulas for overlapped addition:
[0103] sresult=MAX(sv1, sv2)+FF(io)*MIN(sv1, sv2)
[0104] kresult=MAX(kv1, kv2)+FF(io)*MIN(kv1, kv2)
[0105] mresult=MAX(mv1, mv2)+FF(msg)*MIN(mv1, mv2)
[0106] mkbresult=MAX(mkbv1, mkbv2)+FF(msg)*MIN(mkbv1, mkbv2)
[0107] In the formulas above, the “result” subscript refers to components in the resulting vector, and the subscripts “v1” and “v2” refer to components of the two vectors being added with overlapped addition.
[0108] The same basic formula applies to each component, so a single explanation will suffice. If the two vectors pertain to completely overlapped activity, then the larger of the two components will become the resulting component, hence the term MAX(sv1, sv2). Typically, however, the overlap will not be complete. The extent to which the overlap occurs is inversely proportional to the size of the smaller component. Hence, the term FF(x)*MIN(sv1, sv2). Thus, FF(x)=0 results in complete overlap while FF(x)=1 results in no overlap at all.
[0109] Overlapped addition for the Blocking/Idle time component requires a more sophisticated formula; two Blocking/Idle time components cannot simply be added together. Consider two vectors v1 and v2 each potentially having a non-zero Blocking/Idle time component. The time the operator associated with v1 is active effectively reduces the Blocking/Idle time of v2 and vice versa. Only after Blocking/Idle time components of both v1 and v2 have been reduced by the elapsed time of the other vector (but not below zero) can we add the two components together. To determine the elapsed time of a vector, we use the formula presented above. Here is the formula for adding Blocking/Idle time components:
[0110] blk—idltresult=MAX(0, blk—idlev1−(ET(v2)−blk—idlev2))+MAX(0,blk—idlev2−(ET(v1)−blk—idlev1))
[0111] where ET(v) represents the elapsed time of vector v.
[0112] The term (ET(v2)−blk_idlev2) is the amount of time the operator associated with vector v2 was active. The term blk_idlev1−(ET(v2)−blk_idlev2) represents the amount of time the operator associated with vector v1 was idle less the amount of time the operator associated with vector v2 was active. The MAX functions in this case merely ensure a non-negative result.
[0113] Consider the following simplified example. Assume v1 has an elapsed time 20 of which 8 is idle. Assume also that vector v2 has an elapsed time of 15 of which 10 is idle time. The resulting idle time of v1+Ov2 is
[0114] MAX(0,8 −(15−10))+MAX(0,10−(20−8))=MAX(0,3)+MAX(0,−2)=3+0=3.
[0115] Repeated overlapped addition involves adding a vector to itself a repeated number of times using overlapped addition. We denote this with the symbol *O. For example, given vector v and scalar c, the term c *Ov represents vector v added to itself c times using overlapped addition. Normal memory, persistent memory and repeat count remain unchanged.
[0116] Blocking Vector Addition
[0117] Consider two vectors v1 and v2 in which v2 pertains to a blocking operator3. Since v2 is blocking, the following formula must hold:
[0118] 3 A blocking operator (e.g., sort) can not return a row to its parent until it has received all rows from one or more of its children. The hash join can not return a row to its parent until it has received all rows from its right child, so strictly speaking only its first phase is blocking.
[0119] ET(v1)+ET(v2)=ET(v1+v2).
[0120] However, neither traditional vector addition nor overlapped vector addition has this property. Therefore, the present invention defines blocking vector addition, +B, which has the appropriate characteristic:
[0121] v1+Bv2=v1+Vv2+VI(ET(v1)+ET(v2)−ET(v1+Vv2)).
[0122] Recall that I(x) represents a vector having a Blocking/Idle time component of x and zeros in all other components (except repeat count).
[0123] Table 1 below illustrates blocking vector addition. To simplify the presentation, assume that each vector has only 3 components—CPU, I/O and Blocking/Idle time—and that elapsed time is MAX(CPU, I/O)+Blocking/Idle time. In other words, for a given operator, its CPU and I/O overlap.
[0124] Vector v1 has a CPU of 10 and an I/O of 5 and a Blocking/Idle time of 1, so its elapsed time is 11 (Blocking/Idle time plus the maximum of CPU and I/O). Vector v2 has a CPU of 2 and an I/O of 15 and a Blocking/Idle time of 2, so its elapsed time is 17 (Blocking/Idle time plus the maximum of CPU and I/O). Adding v1 and v2 using vector addition involves adding each respective component resulting in a CPU of 12, an I/O of 20 and a Blocking/Idle time of 3. Thus, the elapsed time of this resulting vector is 23 (Blocking/Idle time plus the maximum of CPU and I/O).
[0125] Notice that the elapsed times for v1 and v2 do not add up to the elapsed time of v1+Vv2. This comes about because, with normal vector addition, we implicitly overlap v1's I/O with v2's CPU and vice versa, but this is inappropriate since v2 represents resources used by a blocking operator.
[0126] Blocking vector addition accurately takes into account disallowing overlap. First a vector having a Blocking/Idle time of ET(v1)+ET(v2)−ET(v1+Vv2)=11+17−23=5 is created. All other components (except repeat count) have a value of zero.
[0127] Finally, we calculate the blocking sum, v1+Bv2=v1+Vv2+VI(ET(v1)+ET(v2)−ET(v1+Vv2)), where ET(v1)+ET(v2)=ET(v1+Bv2)=28.
[0128] Vector Comparison Functions
[0129] The function etMIN takes two vectors and returns the one having minimum elapsed time; etMAX takes two vectors and returns the one having maximum elapsed time. The function vecMIN takes two vectors and produces a resulting vector that represents minimum resource usage from the two input vectors. Similarly, vecMAX takes two vectors and produces a resulting vector that represents maximum resource usage from the two input vectors.
[0130] Table 2 below explains how vecMIN and vecMAX produce each component in the resulting vector, respectively.
[0131] Vector Normalization
[0132] The repeat count (also called number of probes) indicates the number of times an operator associated with a particular vector will execute. Typically an operator executes only once, but in some cases (e.g. the inner scan of a nested loops join) an operator can execute multiple times. Given a vector v, the abbreviation RC(v) represents its repeat count.
[0133] Recall that for a Cost object, the vector CPTB represents average resource usage per probe rather than cumulative resource usage. Whenever such “average usage per probe” vectors are added together, both vectors should pertain to the same number of probes (i.e. have the same repeat count). “Vector normalization” refers to the conversion of a vector from one repeat count to another. Given a vector v and a target repeat count rc, the abbreviation N(v,rc) is used to represent normalizing v to a repeat count rc. When normalizing a vector v to a repeat count rc, its Normal Memory and Persistent Memory components remain unchanged since an operator's memory consumption does not change when it executes repeatedly. The repeat count of the normalized vector becomes rc by definition of normalization. All other components are calculated with the following formula:
[0134] CN(v,rc)=Cv*RC(v)/rc
[0135] where Cvrepresents a component in vector v and CN(v,rc)represents the corresponding component in the normalized vector.
[0136] The term Cv*RC(v) represents the cumulative amount of component Cvover all probes. Dividing the result by rc makes it an average amount over rc number of probes. Table 3 below summarizes the vector algebra abbreviations used throughout this patent:
[0137] Rolling Up Cost Objects
[0138] FIG. 3 illustrates a generalized cost roll-up procedure 300. Each operator 310, 312, 314, in the query tree keeps cost information (i.e. a Cost object) about itself independent of its children, called its preliminaryCost 316. Each operator also keeps track of the cost information it reported up to its parent, called rollUpCost 318. For leaf nodes in a query tree, preliminaryCost=rollUpCost. From the perspective of a given operator in a query tree, rolling up a cost vector involves combining a rollUpCost received from the operator's child with the operator's own preliminaryCost to produce its own rollUpCost which the operator will in turn report up to its parent. The parent operator will in turn combine its preliminaryCost with the rollUpCost it receives to produce a rollUpCost for its parent. The roll up proceeds recursively up the query tree in this manner until it reaches the root node in the query tree. Thus, a given operator's rollUpCost reflects the cost of the entire subtree rooted at that operator.
[0139] FIG. 3 shows a parent operator 310 having only a single child 312. The child 312, in turn, has only a single grandchild 314. When an operator has multiple children (e.g., join or union), the present process first combines all child roll-up costs into a single merged roll-up cost and then uses that merged cost with the unary roll-up scheme depicted in FIG. 3.
[0140] FIG. 4 illustrates the merging of child costs 410, 412 and rolling up the merged cost 414 with the parent's preliminary cost 416. As explained below, the particular details of child cost merging and cost roll-up depend on the characteristics of the operators involved. Table 4 below lists the cost object abbreviations used throughout this document:
[0141] Non-blocking Unary Roll-up
[0142] FIG. 5 depicts a unary roll-up involving a non-blocking parent having a preliminaryCost 510 and receiving a roll-up cost 512 from its descendent operators. The preliminaryCost 510 and the child rollUpCost 512 are combined to yield a parent rollUpCost 514. The roll-up formulas for this case are, as follows:
[0143] TCPR=TCPP+VTCCR
[0144] CPFRPR=CPFRPP+BCPFRCR
[0145] CPLRPR=(CPLRPP+O(CPLRCR−VCPFRCR))+VCPFRCR
[0146] CPTBPR=N(CPTBCR,RC(CPLRPP))
[0147] Since TC represents an accumulation of all resources, we use vector addition. However, the formula for CPFR involves adding the parent's preliminary cost with the child's roll-up cost. Blocking addition is used because a parent can not produce its first row until it receives at least one row from its child.
[0148] The formula for CPLR is more involved. The term (CPLRCR−VCPFRCR) represents the child's cumulative cost except for its first row. The work associated with this term overlaps with the parent's activity, so it is added to the parent's preliminary cost using overlapped addition, hence the term (CPLRPP+O(CPLRCR−VCPFRCR)). Finally CPFRCRis added using vector addition since the activity for the child to produce its first row does not overlap with the parent.
[0149] Since the parent does not block, the parent simply reports the blocking activity reported up from its child. Thus, we normalize the blocking vector (CPTB) to the parent's repeat count but otherwise leave CPTB unchanged.
[0150] Blocking Unary Roll-up
[0151] FIG. 6 depicts a unary roll-up involving a blocking parent. As illustrated in this figure, the child rollUpCost 610 is combined with the blocking parent's preliminaryCost 612 to yield the parent rollUpCost. The roll-up formulas for this case are:
[0152] TCPR=TCPP+VTCCR
[0153] CPFRPR=CPFRPP
[0154] CPLRPR=CPLRPP
[0155] CPTBPR=(CPTBPP+O(CPLRCR/VRC(CPTBPP)))+BN(CPTBCR,RC(CPTBPP))
[0156] The formula for TCPRuses vector addition to accumulate all resource usage.
[0157] For a blocking operator, CPFRPPrepresents the cost of generating the first row once the blocking activity has completed. (For example, in the case of a sort, CPFRPPrepresents the cost to read the first row from the sorted result set and send it to the parent.) CPLRPPfor a blocking operator represents the cost of generating the last row once the blocking activity has completed. (For example, in the case of a sort, CPLRPPrepresents the cost to read all rows from the sorted result set and send them to the parent.) CPTBPPrepresents the cost of the actual blocking activity (e.g. in the case of a sort, the cost of producing the sorted result set).
[0158] With a blocking parent operator, the last row and first row costs rolled up from the child reflect blocking activity since they took place during the parent operator's blocking phase, so they are combined with the parent's blocking cost. Thus, for its first and last row costs, the parent rolls up only its preliminary costs: CPFRPPand CPLRPP.
[0159] When calculating the cost roll-up for total blocking, the child's blocking and last row costs are added to the parent's blocking cost, since all of the child's activity took place during the parent's blocking phase. The term (CPLRCR/VRC(CPTBPP)) converts the child's rolled up last row cost to an average cost per probe to make the addition with the parent's blocking vector meaningful. The term (CPTBPP+O(CPLRCR/VRC(CPTBCR))) involves adding parent's blocking activity with the child's non-blocking activity, hence the overlapped addition. The term normalize(CPTBCR, RC(CPTBPP)) represents the child's blocking activity (normalized to the parent's repeat count), so we add it in using blocking addition.
[0160] Union Operator
[0161] Since a union operator has two children, the roll-up costs for each child are merged into a single roll-up cost before using the unary roll-up formulas described earlier.
[0162] Two Non-blocking Legs
[0163] The formulas below indicate how a union operator's left and right children can be merged when neither leg has any blocking operators:
[0164] TCM=TCL+VTCR
[0165] CPFRM=etMIN(CPFRL, CPFRR)+OvecMIN(CPFRL, CPFRR)
[0166] CPLRM=CPLRL+OCPLRR
[0167] The formula for TCM, as for all total cost computations, involves normal vector addition.
[0168] To determine CPFRM, we need to recognize that the first row produced by either of the two legs becomes the first row produced by the union operator itself, hence the term etMIN(CPFRL, CPFRR). Unfortunately, the two legs do not act in isolation; they interfere with one another at least to some degree. The term vecMIN(CPFRL, CPFRR) measures this interference. Consider any component of a vector, say CPU. If the left child uses 100 units of CPU to produce its first row and the right child used 75 units of CPU to produce its first row, then CPU interference only occurs during the first 75 units.
[0169] Overlapped addition is used when computing CPFRMbecause the left and right child of a union act independently (logically speaking), so when one has issued an I/O, the other can utilize the CPU or send a message.
[0170] To determine CPLRMwe need to recognize that both its children must complete before a union operator can produce its last row. Since the left and right child of a union act independently, we simply use an overlapped add.
[0171] Two Blocking Legs
[0172] The formulas below indicate how to merge a union operator's left and right children when both legs have blocking operators:
[0173] TCM=TCL+VTCR
[0174] CPFRM=etMIN(CPFRL, CPFRR)+OvecMIN(CPFRL, CPFRR)
[0175] if (ET(CPTBL)<ET(N(CPTBR, RC(CPTBL))))
[0176] CPLRM=CPLRL+O(CPLRR+V(RC(CPTBR)*O(CPTBR−VvecMIN(CPTBR, N(CPTBL, RC(CPTBR))))))
[0177] else
[0178] CPLRM=CPLRR+O(CPLRL+V(RC(CPTBL)*O(CPTBL−VvecMIN(CPTBL, N(CPTBR, RC(CPTBL))))))
[0179] end
[0180] CPTBM=etMIN(CPTBL, N(CPTBR, RC(CPTBL)))+OvecMIN(CPTBL, N(CPTBR, RC(CPTBL)))
[0181] The formula for TCM, as a total cost computation, involves regular vector addition.
[0182] The formula for CPFRMremains unchanged from the previous case of two non-blocking legs.
[0183] The formula for CPTBMresembles that of CPFRMwith the added complication of normalizing the right leg's blocking vectors to the repeat count of the left leg. (Remember, blocking vectors represent average usage per probe, so they need to be normalized to the appropriate repeat count before proceeding.) Since a simple union can begin processing rows as soon as one of its blocking legs has begun sending rows, we make the merged blocking vector the child blocking vector with minimum elapsed time adjusted upwards to account for interference between the two blocking legs. (An alternative formula, CPTBL+OCPTBR, involves an implicit assumption that no activity can begin until both blocking children have completed their work. Since, typically, a union operator does not wait until both blocking children have completed their work, this alternative formula is usually too conservative and provides a worst case cost.)
[0184] There is a very complicated formula for CPLRM. First, ET(CPTBL) and ET(N(CPTBR, RC(CPTBL))) are compared to determine which leg had the slowest total blocking vector. (Again, the right leg's blocking vector is normalized to the left leg's repeat count since blocking vectors represent average usage per probe.) Assuming a faster left leg, the term CPTBR−VvecMIN(CPTBR, N(CPTBL, RC(CPTBR))) is a good estimate of the amount of CPTBRnot reflected in CPTBM. If we encounter a faster right leg, then the term CPTBL−VvecMIN(CPTBL, N(CPTBR, RC(CPTBL))) represents the amount of CPTBLnot reflected in CPTBM. The appropriate result vector is then added to CPLRMand thus, in the final costing, we avoid losing the resource usage that the result vector represents.
[0185] Finally, recall that CPTB reflects an average usage per probe, whereas CPLR reflects cumulative usage. The term RC(CPTBR)*O(CPTBR−VvecMIN(CPTBL, N(CPTBR, RC(CPTBL)))) (or RC(CPTBL)*O(CPTBL−VvecMIN(CPTBL, N(CPTBR, RC(CPTBL)))) if we encounter a slower left leg) converts average usage to cumulative usage. Overlapped multiplication is used since successive probes can overlap with each other.
[0186] One Blocking Leg and One Non-blocking Leg
[0187] In the case of a union with exactly one blocking leg, the non-blocking child's cost is converted to look like a set of blocking vectors and then the two children are combined using the formulas for both legs blocking described earlier. The transformation of a non-blocking leg into a blocking leg uses the following formulas:
[0188] TCC=TCN
[0189] CPFRC=Z
[0190] CPLRC=CPLRN−VCPFRN
[0191] CPTBC=CPFRN
[0192] These formulas simply move CPFR into the blocking vector. Since last row elapsed time combines CPTB and CPLR, CPFR is subtracted from CPLR. This reflects the fact that waiting for a first row from a child operator is a form of blocking.
[0193] Merge Join Operator
[0194] Since a merge join (MJ) operator has two children, there is a need to merge the roll-up costs for each child into a single roll-up cost before using the unary roll-up formulas described earlier.
[0195] Two Non-blocking Legs
[0196] The formulas below indicate how to combine an MJ operator's left and right children when neither leg has any blocking operators:
[0197] TCM=TCL+VTCR
[0198] CPFRM=CPFRL+OCPFRR
[0199] CPLRM=CPLRL+OCPLRR
[0200] The formula for TCM, as a total cost computation, involves regular vector addition.
[0201] Since both its legs must produce their respective first rows before an MJ operator can produce its first row, CPFRMis simply the overlapped add of CPFR for both legs.
[0202] The computation for CPLRMis the same as for the Union operator.
[0203] Two Blocking Legs
[0204] The formulas below indicate how to combine an MJ operator's left and right child when both children have blocking operators:
[0205] TCM=TCL+VTCR
[0206] CPFRM=CPFRL+OCPFRR
[0207] if (ET(CPTBL)<ET(N(CPTBR, RC(CPTBL))))
[0208] CPLRM=CPLRL+O(CPLRR+V(RC(CPTBR)*O(CPTBR−VvecMIN(CPTBL, CPTBR))))
[0209] else
[0210] CPLRM=CPLRR+O(CPLRL+V(RC(CPTBL)*O(CPTBL−VvecMIN(CPTBL,CPTBR))))
[0211] end
[0212] CPTBM=(etMIN(CPTBL,N(CPTBRRC(CPTBL)))+OvecMIN(CPTBL, N(CPTBR, RC(CPTBL)))
[0213] The formula for TCM, as a total cost computation, involves regular vector addition.
[0214] Since an MJ requires rows from both its children before it can produce a row itself, CPFRMis simply the overlapped sum of CPFR for each of its children. We use overlapped addition on the assumption that when one child has issued an I/O the other can send messages or utilize CPU.
[0215] Both a union operator and an MJ operator must receive their slower child's last row before they can produce their own last row. Thus, the union operator's formulas for CPLRMand CPTBMalso apply to an MJ operator.
[0216] One Blocking Leg and One Non-blocking Leg
[0217] When exactly one of an MJ operator's children has a blocking leg, the MJ operator combines the two legs using the same strategy as the union operator: i.e. converting the non-blocking leg to a blocking leg (using the exact same transformation rules as the union operator) and then proceeding as if it had two blocking legs using the formulas described above.
[0218] Nested Loops Join Operator
[0219] As illustrated in FIG. 7, since a nested loops join (NLJ) operator 710 has two children 712, 714, the roll-up costs for each child 712, 714 are merged into a single roll-up cost before using the unary roll-up formulas described earlier.
[0220] All output rows from an NLJ operator's left child 712 eventually get sent to the right child 714, so the NLJ operator's left child 712 can be viewed as providing rows directly to the right child 714. Thus, for purposes of merging the children, one can treat the left child 712 as a unary child of the NLJ operator's right child 714. By making this transformation, one can use the unary roll-up formulas to merge the two legs.
[0221] Both Legs Non-blocking
[0222] The formulas below indicate how to merge an NLJ operator's left and right child when neither leg has any blocking operators:
[0223] TCM=TCL+VTCR
[0224] CPFRMCPFRL+BCPFRR
[0225] CPLRM=(CPLRR+O(CPLRL−VCPFRL))+VCPFRL
[0226] The formulas for TCM, CPFRMand CPLRMcome directly from the unary non-blocking roll-up formulas. By assumption, neither leg blocks, so CPTBMis a zero vector.
[0227] The formula for CPFRMrelies on the assumption that the first probe in the right child produces the actual first row. When the first row requires multiple probes, all probes after the first probe may overlap with the previous probe, which suggests using overlapped addition (CPFRL+OCPFRR) instead of blocking addition. One could also choose to use regular vector addition (CPFRL+VCPFRR) as a compromise. In the majority of cases, however, the first probe will result in the first row. Therefore, in the presently preferred embodiment, use of the blocking version of the formula is preferred.
[0228] Left Leg Blocking, Right Leg Non-blocking
[0229] The formulas below indicate how to merge an NLJ operator's left and right child when only the left leg has at least one blocking operator:
[0230] TCM=TCL+VTCR
[0231] CPFRM=CPFRL+BCPFRR
[0232] CPLRM=(CPLRR+O(CPLRL−VCPFRL))+VCPFRL
[0233] CPTBM=N(CPTBL, RC(CPLRR))
[0234] The formulas for TCM, CPFRMand CPLRMcome directly from the unary non-blocking roll-up formulas.
[0235] The left leg may be viewed as logically coming underneath the right leg, and by assumption only the left leg blocks, so CPTBLbecomes CPTBMafter normalizing CPTBLto the right leg's repeat count.
[0236] Left Leg Non-Blocking, Right Leg Blocking
[0237] The formulas below indicate how to merge an NLJ operator's left and right children when only the right leg has at least one blocking operator:
[0238] TCM=TCL+VTCR
[0239] CPFRM=CPFRR
[0240] CPLRM=CPLRR
[0241] CPTBM=CPTBR+O(CPLRL/VRC(CPTBR))
[0242] The formulas for TCM, CPFRMand CPLRMcome directly from the unary blocking roll-up formulas.
[0243] The formula for CPTBMis a simplification of the unary blocking roll-up formula taking into account that the left leg has no blocking activity.
[0244] Both Legs Blocking
[0245] The formulas below indicate how to merge an NLJ operator's left and right children when both legs have at least one blocking operator:
[0246] TCM=TCL+VTCR
[0247] CPFRM=CPFRR
[0248] CPLRM=CPLRR
[0249] CPTBM=(CPTBR+O(CPLRL/VRC(CPTBR)))+BN(CPTBL, RC(CPTBR))
[0250] The formulas for TCM, CPFRM, CPLRM, and CPTBMall come directly from the unary blocking roll-up formulas.
[0251] Hash Join Operator
[0252] Unlike binary operators described earlier, the hash join (HJ) operator does not merge the roll-up costs of its two children and then use a unary roll-up formula to produce its own roll-up cost. Instead, it uses intermediate cost vectors and values calculated and saved off during preliminary costing and combines these directly with the roll-up costs of its two children to produce its own roll-up cost.
[0253] Hash Join Specific Vectors and Values
[0254] A hash join consists of potentially three stages. Stage 1 involves taking rows produced by the right (inner) child, building a main memory hash table out of a cluster of rows that fits in memory and writing the remaining overflow clusters to disk. Stage 2 involves taking rows produced by the left (outer) child and, if the row in question belongs to a main memory cluster, probing the hash table built in stage 1; if the row in question belongs to an overflow cluster, it gets written to an overflow cluster on disk. Stage 3 joins corresponding overflow clusters produced in stages 1 and 2. If stages 1 and 2 did not produce overflow clusters, stage 3 does not need to execute.
[0255] Since no activity above the HJ operator can proceed until stage 1 completes, we regard stage 1 as blocking activity, so we place its resource usage in the blocking vector of the HJ preliminary cost:, i.e., CPTBPP.
[0256] Preliminary costing produces separate vectors for resource usage in stage 2 and stage 3. We denote these two vectors as STG2 and STG3, respectively. For repeat counts greater than one, both vectors represent cumulative usage over all probes.
[0257] Preliminary costing also determines what fraction of STG2 pertains to first row production and what fraction of STG3 pertains to first row production. We denote these two fractions as frFrac2 and frFrac3 respectively. Preliminary costing produces its preliminary first and last row costs using the following formulas:
[0258] CPFRPP=frFrac2*STG2+BfrFrac3*STG3
[0259] CPLRPP=STG2+BSTG3
[0260] For HJ roll-up, however, we do not use CPFRPPand CPLRPPdirectly. Instead we use their constituent parts—frFrac1, frFrac2, STG1 and STG2—which preliminary costing has stored along with the traditional vectors of the preliminary cost.
[0261] Hash Join Roll-up Formulas
[0262] The formulas below indicate how to perform final cost roll-up for an HJ operator:
[0263] TCPR=(TCL+VTCR)+VTCPP
[0264] CPFRPR=(frFrac2*V((CPLRL−VCPFRL)+OSTG2))+B(frFrac3*VSTG3)
[0265] CPLRPR=((CPLRL−VCPFRL)+OSTG2)+BSTG3
[0266] CPTBPR=(CPFRL+VCPTBL)+O(((((CPLRR−VCPFRR)/VRC(CPLRR))+OCPTBPP)+VCPFRR)+BCPTBR)
[0267] The formula for TCPR, as a total cost computation, involves regular vector addition.
[0268] In the computation of CPLRPR, no ancestor activity can begin until the left child has produced at least one row, so the left child's first row cost belongs with the total blocking roll-up cost: CPTBPR. The remaining portion of the left child's last row activity overlaps with stage 2, hence the term ((CPLRL−VCPFRL)+OSTG2). Stage 3, however, can not proceed until stage 2 finishes, so blocking addition is used when adding its resource usage.
[0269] The computation for CPFRPRfollows the same approach as the computation for CPLRPRwith the additional complication of multiplying the stage 2 resource usage (including the left child's last row activity) and the stage 3 resource usage by the corresponding first row fractions—frFrac2 and frFrac3 respectively.
[0270] To compute CPTBPR, one first recognizes that all of the right child's last row activity, except the portion necessary to produce the first row, overlaps with the HJ operator's blocking activity, hence the term ((CPLRR−VCPFRR)/VRC(CPLRR))+OCPTBPP. (Note that dividing by RC(CPLRR) converts last row resource usage from a cumulative cost over all probes to an average cost per probe, and also note that the HJ operator's blocking activity, CPTBPP, represents stage 1.) Next, CPFRRis added back, which was subtracted out earlier, and then the right child's blocking cost, CPTBR, is added using blocking addition. As mentioned earlier, the left child's blocking activity includes the activity necessary to produce its first row, hence the term CPFRL+VCPTBL. Since the left leg's blocking activity overlaps with the with the HJ operator, it is added using overlapped addition.
[0271] Several preferred embodiments of the present invention have been described. Nevertheless, it will be understood that various other modifications may be made without departing from the spirit and scope of the present invention. It will be understood, for example, that the invention is not limited to any particular implementation or programming technique and that the invention may be implemented using various techniques for implementing the functionality described herein. The invention may be implemented in any appropriate operating system using the appropriate programming languages and/or programming techniques. Thus, the present invention is not limited to the presently preferred embodiments described herein, but may be altered in a variety of ways which will be apparent to persons skilled in the art based on the present description.
Claims
We claim:
1. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators forming a query tree and at least one operator is a blocking operator, comprising:
assigning a preliminary cost to each operator;
combining the costs of at least some of the operators, including the at least one blocking operator; and
converting the combined costs into a predicted elapsed time to execute the plan;
wherein the predicted elapsed time is the time predicted for returning the first row of the query's response.
2. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators forming a query tree and at least one operator is a blocking operator, comprising:
assigning a preliminary cost to each operator;
combining the costs of at least some of the operators, including the at least one blocking operator; and
converting the combined costs into a predicted elapsed time to execute the plan;
wherein the predicted elapsed time is the time predicted for returning the last row of the query's response.
3. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators that will utilize resources during their execution, wherein the operators form a query tree and wherein at least two of the operators compete for the same resources, comprising:
assigning a preliminary cost to each operator;
combining the costs of at least the operators that compete for the same resources; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the competition for resources on the predicted elapsed time;
wherein the predicted elapsed time is the time predicted for returning the first row of the query's response.
4. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators that will utilize resources during their execution, wherein the operators form a query tree and wherein at least two of the operators compete for the same resources, comprising:
assigning a preliminary cost to each operator;
combining the costs of at least the operators that compete for the same resources; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the competition for resources on the predicted elapsed time;
wherein the predicted elapsed time is the time predicted for returning the last row of the query's response.
5. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators that will utilize resources during their execution, the operators form a query tree and at least one of the operators utilizes two of the resources in a non-concurrent manner, comprising:
assigning preliminary costs to the operators;
combining the costs of at least one of the operators that utilize resources in a non-concurrent manner with at least one other operator; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the non-concurrent utilization of resources;
wherein the predicted elapsed time is the time predicted for returning the first row of the query's response.
6. A process for predicting an elapsed time for executing a query, wherein a plan for executing the query includes a plurality of operators that will utilize resources during their execution, the operators form a query tree and at least one of the operators utilizes two of the resources in a non-concurrent manner, comprising:
assigning preliminary costs to the operators;
combining the costs of at least one of the operators that utilize resources in a non-concurrent manner with at least one other operator; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the non-concurrent utilization of resources;
wherein the predicted elapsed time is the time predicted for returning the last row of the query's response.
7. A process for predicting an elapsed time for executing a query in a database system having memory, wherein a plan for executing the query will use more of the memory than is physically available for the execution, and wherein the plan includes a plurality of operators forming a query tree, comprising:
assigning preliminary costs to the operators;
combining the costs of a plurality of the operators; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the insufficient memory on the predicted elapsed time;
wherein the predicted elapsed time is the time predicted for returning the first row of the query's response.
8. A process for predicting an elapsed time for executing a query in a database system having memory, wherein a plan for executing the query will use more of the memory than is physically available for the execution, and wherein the plan includes a plurality of operators forming a query tree, comprising:
assigning preliminary costs to the operators;
combining the costs of a plurality of the operators; and
converting the combined costs into a predicted elapsed time to execute the plan while accounting for the effect of the insufficient memory on the predicted elapsed time;
wherein the predicted elapsed time is the time predicted for returning the last row of the query's response.
Patent Citations (15)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US5301317 | 1994-04-01 | Lohman et al. | Examiner |
| US5367675 | 1994-11-01 | Cheng et al. | Applicant |
| US5546570 | 1996-08-01 | McPherson, Jr. et al. | Applicant |
| US5548755 | 1996-08-01 | Leung et al. | Applicant |
| US5619692 | 1997-04-01 | Malkemus et al. | Applicant |
| US5630120 | 1997-05-01 | Vachey | Applicant |
| US5689696 | 1997-11-01 | Gibbons et al. | Applicant |
| US5689708 | 1997-11-01 | Regnier et al. | Examiner |
| US5761654 | 1998-06-01 | Tow | Applicant |
| US5765146 | 1998-06-01 | Wolf et al. | Examiner |
| US5875445 | 1999-02-01 | Antonshenkov | Examiner |
| US6023695 | 2000-02-01 | Osborn et al. | Examiner |
| US6026391 | 2000-02-01 | Osbourn et al. | Examiner |
| US6212514 | 2001-04-01 | Eberhard et al. | Examiner |
| JP11-203288 | 1999-07-01 | Examiner |
Non-Patent Literature (13)
- IBM Technical Disclosure Bulletin: “Effective Approach to Query I/O Parallelism Using Sequential Prefetch and Horizontal Data Partitions”; Sep. 1993, vol. 36, No. 9A, pp. 541-544.Applicant
- Batabase Searcher: “Advance cost estimates on DIALOG for search results. (Price Watch)”; Jul.-Aug. 1991, v7, n6, p. 38.Applicant
- Spiliopulou et al: “A cost model for the estimation of query execution time in parallel environment supporting pipelines”; Computers ans Artificial Intelligence, 1996, vol. 15, No. 4, pp. 341-368, (Abstract Only).Applicant
- Subramanian et al: “Query optimization in multidatabase systems”; Distributed and Parallel Databases, Apr. 1998, vol. 6, No. 2, pp. 183-210, (Abstract Only).Applicant
- Article by Clifford A. Lynch entitled “Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values” published by University of California dated 1988 pp. 240-251.Applicant
- Article by Piatetsky-Shapiro et al. entitled “Accurate Estimation of the Number of Tuples Satisfying a Condition” published by ACM dated 1984 pp. 256-276.Applicant
- Article by Haas et al. entitled “Sampling-Based Estimation of the Number of Distinct Values of an Attribute” published by Proceedings of the 21st VLDB Conference dated 1995 pp. 311-321.Applicant
- Article by Yannis E. Ioannidis entitled “University of Serial Histograms” published by Proceedings of the 19th VLDB Conference dated 1993 pp. 256-267.Applicant
- Article by Mackert et al. entitled “R* Optimizer Validation and Performance Evaluation for Distributed Queries” published by Proceedings of the 12th International Conference on Very Large Databases, dated 1986 pp. 149-159.Applicant
- Article by Leonard D. Shapiro entitled “Join Processing in Database Systems with Large Main Memories” published by ACM Transactions on Database Systems dated 1986, vol. 11, No. 3, pp. 239-264.Applicant
- Article by Selinger et al., entitled “Access Path Selection in a Relational Database Management System” published by ACM dated 1979, pp. 23-34.Applicant
- Article by Sun et al. entitled: “An Instant and Accurate Size Estimation Method for Joins and Selection in a Retrieval-Intensive Environment.” SIGMOD, May 1993, pp. 79-88.Applicant
- Article by Poosala et al. entitled: “Improved Histograms for Selectivity Estimation of Range Predicates” SIGMOD Jun. 1996, pp. 294-305.Applicant