.sh 1 "DESIGN OF THE OPTIMIZER" 3 .pp This section will first describe the optimization algorithm chosen for POSTGRES, focusing on features specifically incorporated to handle extendibility in POSTGRES. The rest of the section will then indicate how this algorithm is used in optimizing nested-attribute queries. Algorithms are described in high-level detail with special attention given to the design rationale behind various features. Plans produced by these algorithms are also described to indicate how the query processor interprets optimizer plans. .sh 2 "Choice of Optimization Algorithm" .pp In selecting an optimization algorithm to work with, there were two choices \*- query decomposition [WONG76] or exhaustive search. Query decomposition is a heuristic \*(lqgreedy\*(rq algorithm that proceeds in a stepwise fashion. If a query has three or more variables, heuristics are first used to subdivide the query into two smaller subqueries. This process is applied recursively to any subqueries that contain at least three variables. For subqueries containing less than three variables, tuple substitution is used to process the join, while a component known as the one-variable query processor determines the path used to scan individual relations. .pp Once the first step of a query plan has been constructed using this decomposition algorithm, the step is executed. By doing this, the optimizer has information on the sizes of intermediate results, which can be used to its advantage in making subsequent decisions. Furthermore, the search space is reduced substantially because only a single path is considered. However, as a result, potentially good plans are ignored during early stages of the algorithm. .pp The SYSTEM-R designers took a dramatically different approach by essentially doing an exhaustive search of the plan space. All possible ways of scanning each relation appearing within a query are found. Using these paths, all plans for processing two-way joins are considered. Then, single relations are joined to form three-way joins, and from here, the algorithm iterates in a similar manner. The cost of executing each of these paths is estimated, and the cheapest is selected as the desired plan. .pp Although exhaustive search inevitably requires more planning time, good plans are not overlooked. This is especially important when optimizing complicated queries because for these queries the difference in the amount of processing required by two plans can be quite significant. Thus, the extra planning overhead is more than compensated by savings that result from executing a better plan. For simple queries, although the selected plan may not be significantly better than another, the extra overhead is likely to be inconsequential. For queries embedded within data fields, the extra overhead of enumerative planning is especially unimportant because these queries will be preexecuted in background mode and POSTGRES will cache the execution results as well as the compiled query plans. In these cases, the time spent optimizing will be amortized over several executions. .pp The SYSTEM-R optimizer only considers linear joins, e.g., .(l ((A join B) join C) join D .)l for a 4-way join. The optimizer could be improved to consider joins between pairs of composite relations, e.g., .(l (A join B) join (C join D). .)l This would allow the optimizer to examine further plans, and on occasion, these plans may be significantly better than plans that only utilize linear joins. .pp Another enhancement to the SYSTEM-R optimizer is to consider plans that will dynamically create indices on join attributes if they are not already available. If the cost of building the index is small compared to the savings that result from using the index in a join, such a strategy can be advantageous. .pp The POSTGRES optimizer does not consider these enhancements either. Although they would undoubtedly result in a better optimizer, the main goal of POSTGRES is to illustrate the feasibility of the novel features that it will support. Therefore, for simplicity, the POSTGRES optimizer will adhere fairly closely to the algorithm as described in [SELI79]. .sh 2 "Pipelining of Tuples" .pp Ignoring nested attributes for the moment, the query plan created by the optimizer is a tree of scan and join nodes. Relations are either scanned sequentially or via primary or secondary indices. Joins are processed using nested iteration, merge-sorts, or hash-joins. Each of these join strategies will be discussed further in section 3.3.3. .pp Every join involves two components. The component that is scanned first will be referred from hereon as the \*(lqouter join relation,\*(rq while the other component is the \*(lqinner join relation.\*(rq For a query containing \fIn\fR variables, the plan is constructed in such a way that the \fIn\fR-way composite join appears at the top of the tree. (See figure 3.1.) .(z .hl .GS file figure3.1 .GE .sp .ce .sz \n(ep (((A1 join A2) join A3) join ... A(n-1)) join An .sz \n(pp .sp .ce 2 \fBFigure 3.1\fR Plan tree for an \fIn\fR-way join .hl .)z The left subtree is a plan for processing the outer join relation, and the right subtree corresponds to a plan for processing the inner join relation. Because the optimizer only considers linear joins (see section 3.1), the right subtree is always a scan node while the left subtree is a plan for an \fI(n-1)\fR-way join, or scan if \fIn\fR = 2. These characteristics apply recursively to the rest of the tree. .pp To process such a plan, the query processor walks through the tree starting at the root. If the node is a join, depending on the join strategy, calls are made on either the left or right subtrees to retrieve tuples from either the outer or inner join relations. If the node is a scan node, the appropriate relation is scanned using the selected strategy. When scanning a relation, restriction clauses specified on the relation are examined. Once a single tuple has been found satisfying these qualifications, the tuple is returned to the node that initiated the scan. If the higher node was a join node and this tuple originated from the left subtree of the join node, then a call is made on the right subtree. Otherwise, this tuple originated from the right subtree and thus can be joined with the tuple passed back by the left subtree. Provided all corresponding join clauses are satisfied, a composite tuple is formed. If the join clauses are not satisfied, calls are made on either the right or left subtrees until a qualifying composite tuple can be constructed. Once this composite tuple is formed, it is passed upward to the node that called this join node, and the process is repeated. .pp If tuples must be sorted or hashed prior to join processing (see figure 3.2), all tuples returned from a lower node must first be stored in a temporary relation. .(z .hl .GS file figure3.2 .GE .sp .ce 2 \fBFigure 3.2\fR Sort node in a plan tree .hl .)z Once the lower node has passed all relevant tuples into the temporary, the sort or hash is performed. From here, the temporary relation is scanned like any other relation, and its tuples are also pipelined upward. In summary, calls are made on lower nodes in the tree when tuples are needed at higher nodes to continue processing, and tuples originating from scan nodes at the leaves of the plan tree are pipelined bottom-up to form composite tuples, which also are pipelined upward. .pp As an alternative to pipelining, the query executor could have processed nodes to completion, stored the intermediate subresults in temporary relations, and then passed groups of tuples upwards rather than a tuple at a time. This may be advantageous when there are many duplicate tuples in a subresult. The duplicates could be removed from the temporary, reducing the time required to process later joins. However, for simplicity, we chose to focus on a pipeline processing scheme for now. Implementation of temporaries will be reserved for future extensions. .pp .sh 2 "Generating Possible Plans" .pp The SYSTEM-R optimizer decides which plans should be generated based upon the types of indices defined on relations appearing in a query as well operators that also appear in the query. For example, suppose a B-tree index is defined on a relation, and a query contains the following restriction clause: .(l \fIrelation.field OPR constant\fR. .)l Using Selinger's notation, clauses of this form will be referred from hereon as \*(lqsargable\*(rq clauses [SELI79]. If \fIrelation.field\fR within a sargable clause happens to match the key of the B-tree index and the restriction operator, \fIOPR\fR, is anything but $!=$, then an index path should be considered because a B-tree provides efficient access when used with the following operators: .(l =, <, $<=$, >, $>=$. .)l The criteria for decisions like this can easily be incorporated into the SYSTEM-R optimization code because a conventional database only has a fixed number of operators and access methods; so there are only a fixed number of possibilities. Clearly the POSTGRES optimizer cannot use such a strategy due to POSTGRES's provision for extendibility. Therefore, we resorted to storing operator and access method characteristics in database system catalogs, and we coded the optimizer to access and use this information in generating possible plans. The rest of this subsection will discuss in greater detail the steps taken in creating access plans in order to focus on the type of information the optimizer and other relevant parts of the system will need in making decisions. .sh 3 "Transforming Queries Into Standard Form" .pp Prior to optimizing a query, the parser must take the user's ascii request, parse it for valid syntax, perform semantic checks, and finally generate a tree representing information within the query. To make optimization simpler and to produce more efficient query plans, the parser must place the qualification portion of every query in conjunctive normal form. This entails pushing all \*(lqor\*(rq clauses to the innermost levels of a qualification using the following distributive rule: .(l a or ( b and c ) $==$ ( a or b ) and ( a or c ). .)l The optimizer also requires that \*(lqnot's\*(rq be pushed to the innermost levels using DeMorgan's law: .(l not ( a and b ) $==$ not ( a ) or not ( b ) not ( a or b ) $==$ not ( a ) and not ( b ) .)l and if possible, removed from the query. For example, the qualification in figure 3.3 is equivalent to the qualification in figure 3.5, which is in conjunctive normal form with \*(lqnot's\*(rq removed. .(z .hl .(l C .sz \n(ep not ( r.f = 1 ) or ( not ( r.f2 > 1 or r.f2 < 3 )) .sz \n(pp .sp \fBFigure 3.3\fR Qualification in non-standard form .sp 2 .sz \n(ep ( not ( r.f = 1 ) or not ( r.f2 > 1 )) and ( not ( r.f = 1 ) or not ( r.f2 < 3 )) .sz \n(pp .sp \fBFigure 3.4\fR Equivalent qualification in conjunctive normal form .sp 2 .sz \n(ep ( r.f $!=$ 1 or r.f2 $<=$ 1 ) and ( r.f $!=$ 1 or r.f2 $>=$ 3 ) .sz \n(pp .sp \fBFigure 3.5\fR Equivalent qualification in conjunctive normal form with \*(lqnot's\*(rq removed .)l .hl .)z .pp Removing \*(lqnot's\*(rq from a qualification requires substituting operators with their respective negations. For example, \*(lq=\*(rq would be replaced by \*(lq$!=$,\*(rq while \*(lqAREAGT\*(rq would be replaced by \*(lqAREALE.\*(rq For the parser to make these substitutions, users must specify an operator's corresponding negation, in addition to other information, when defining a new operator. The information is specified as follows: .(l \fBdefine operator\fR (\fBopname is\fR =, $...$, \fBnegator is\fR $!=$, $...$) .)l and is stored in an operator catalog, accessible by the parser. .pp There are, however, problems associated with this requirement. First of all, this \fIforces\fR users to define operators corresponding to negators. In other words, having specified \*(lqAREANEQ\*(rq as a negator, it is also necessary to define an operator called \*(lqAREANEQ.\*(rq Although this definition is not difficult, since a negator is the logical opposite of an already defined operator, users may have no need for the negator, and therefore would rather not have defined the extraneous operator. Secondly, because every negator is also a user-defined operator, an operator's negator may be specified before the negation operator has been defined. In other words, depending on whether the operator \*(lqAREAEQ\*(rq or \*(lqAREANEQ\*(rq is defined first, the other operator will not have been defined yet when the negator of the first is specified. This means there is no guarantee that the specified negator is actually a valid operator; a user could specify the negator of \*(lqAREAEQ\*(rq to be \*(lqfoobar,\*(rq or he may specify the correct negator, \*(lqAREANEQ,\*(rq but forget to define the \fIoperator\fR \*(lqAREANEQ.\*(rq .pp We have addressed both issues by implementing the optimizer so it allows \*(lqnot's\*(rq to appear within qualifications. Therefore, if a user defines a negator that happens to be a nonexistent operator (e.g., \*(lqfoobar\*(rq) or doesn't specify one, the parser has no choice but to push the \*(lqnot's\*(rq as far as possible into the qualification without actually removing them. (See figure 3.4.) The only problem with this is that the optimizer may not produce optimal plans when \*(lqnot's\*(rq are left within clauses. For example, the following query: .(l (1) \fBretrieve\fR (foo.bar) \fBwhere not\fR(foo.f1 AREANEQ 1) .)l is equivalent to this query: .(l (2) \fBretrieve\fR (foo.bar) \fBwhere\fR foo.f1 AREAEQ 1 .)l because \fBnot\fR(AREANEQ) $==$ AREAEQ. If an area B-tree index is defined on the field \*(lqf1,\*(rq then the optimizer would definitely consider an index scan because the operator, \*(lqAREAEQ,\*(rq in query (2) can be used with an area B-tree. However, if a user had not specified the negation of \*(lqAREANEQ,\*(rq then the transformation from (1) to (2) would not have been possible, and the optimizer could not have considered an index scan. In this case, the index scan probably would have been the optimal path. Therefore, it is to the user's advantage to specify and define negators. .pp Another desirable transformation is that variables in qualifications appear on the left-hand side of an operator and constants on the right (e.g., \fIr.field OPR constant\fR). To make this transformation, operands must be reversed and operators must be replaced with their respective \*(lqcommutators,\*(rq which again the user must specify. For example, the commutator of \*(lq<\*(rq is \*(lq>,\*(rq while the commutator of \*(lqAREAEQ\*(rq is also \*(lqAREAEQ.\*(rq The issues and solution discussed in the previous paragraphs in reference to negators also apply here, and again, it is to the user's advantage to specify commutators. The reasoning behind this will be discussed further in section 3.3.2. Basically, it enables the optimizer to consider index paths it could not have considered had a variable appeared on the right hand side of an operator. .sh 3 "Index Scans" .pp Once a query tree has been transformed as close as possible to standard form, it is passed to the optimizer. The first step the optimizer takes is to find all feasible paths for scanning each relation appearing in the query. Relations can always be scanned sequentially; therefore, a sequential scan path is always considered. Generally when sargable clauses (i.e., clauses of the form \fIrelation.field OPR constant\fR) appear within queries, indices will restrict the amount of search required. Therefore, if a user has a primary index or secondary indices defined on a relation, all viable index paths are also considered. .pp For an index to be considered, its keys must match variables that appear within sargable restrictions. The optimizer also needs to insure the usability of the operator within the sargable clause with the index under consideration. For example, an area B-tree, whose records are sorted in \*(lqAREALT\*(rq order, can be used with sargable clauses for which \fIOPR\fR is: .(l AREAEQ, AREAGT, AREAGE, AREALT, or AREALE, .)l while a standard B-tree can be used with sargable clauses containing: .(l =, >, $>=$, <, or $<=$. .)l To distinguish the two cases, POSTGRES introduces the notion of a \*(lqclass.\*(rq Associated with every class is a particular access method and the set of operators that can be used with it. For example, the class \*(lqintops\*(rq refers to a standard B-tree. The operators associated with it are: .(l =, >, $>=$, <, and $<=$. .)l The class \*(lqareaops\*(rq is an area B-tree. Therefore, the operators associated with it are: .(l AREAEQ, AREAGT, AREAGE, AREALT, and AREALE. .)l Moreover, another class \*(lqhashops\*(rq is a standard hash table that can only be used with \*(lq=\*(rq. This information is stored as specified in table 3.1. .(z .hl .sz \n(ep .TS center; |c||c|c|c|c| c ||c|c|c|c|. _ AMOP access-method class operator $...$ other information $...$ _ B-tree intops = B-tree intops < B-tree intops \(<= B-tree intops > B-tree intops \(>= B-tree areaops AREAEQ B-tree areaops AREALT B-tree areaops AREALE B-tree areaops AREAGT B-tree areaops AREAGE hash hashops = _ _ _ _ .TE .sz \n(pp .sp .ce 2 \fBTable 3.1\fR Index and operator classes .hl .)z To determine the usability of an index, whose key matches the variable within a sargable clause, table 3.1 is scanned using the class of the index and the operator within the sargable clause as a search key. If the pair is found, then the index can be used; otherwise, it cannot. .pp Determining index usability, therefore, involves matching operators that appear within sargable restriction clauses with the operators associated with an index's class. By requiring that qualifications be transformed so variables are on the left-hand side and constants are on the right-hand side, the optimizer is insured that an operator appearing within a clause is semantically equivalent to the actual operator that appears in table 3.1. For example, suppose the operator \*(lqfoo\*(rq is usable with index \*(lqfoobar,\*(rq but its commutator \*(lqbar\*(rq is not. If we have the following restriction: .(l 10 foo relation.field, .)l the optimizer should not consider using index \*(lqfoobar\*(rq because the above restriction is equivalent to: .(l relation.field bar 10. .)l .pp Currently, only a single clause can be used with an index defined on a single key. For example, if the following two clauses are contained in a query: .(l r.foo > 100 \fBand\fR r.foo < 150, .)l and a B-tree index is defined on the field \*(lqfoo,\*(rq then only one of the two clauses can be used with the index. In other words, either \fIall\fR values foo > 100 are located using the index, or \fIall\fR values < 150, but \fInot\fR both. Had both clauses been used with the index, only those values between 100 and 150 would have to be examined. This has the possibility of reducing the scope of an index scan substantially. However, such an optimization is being reserved for future extensions of POSTGRES. It will not only require a a redefinition of the access method interface but also extra information from the user establishing which operator should be used at the low end of a scan (e.g., >) and which corresponds to the high end (e.g., <). The first requirement is necessary because currently the access method interface is only designed to work with one clause per index key. .pp In the case where an index is defined on multiple keys, the ideas discussed above simply generalize. In other words, for every key of an index, there must be a corresponding sargable restriction clause, and in addition to all operators in these clauses being usable by the index, they all must be identical. A more flexible approach would have allowed partial matching of keys and multiple operators to be used in a single scan. This would have required that POSTGRES store further information about operators and access methods in system catalogs. Namely, for every access method, the optimizer would need an indication as to whether partial key matching is possible, and it also would need some way of establishing that the following clause: .(l r.field1 = 1 \fBand\fR r.field2 > 5 .)l can be used with a B-tree index defined on \*(lqfield1\*(rq and \*(lqfield2,\*(rq but the following cannot: .(l r.field1 > 1 \fBand\fR r.field2 < 10. .)l The benefits of this extra information is not significant enough to justify the extra complexity that would be required when defining new operators and access methods; therefore, POSTGRES does not implement these features. .pp One optimization that the POSTGRES planner does support is use of multiple indices to process \*(lqor\*(rq clauses. Normally, it would not be possible to use an index scan with the following clause: .(l r.field = 1 \fBor\fR r.field = 2 .)l because there are two key values, 1 and 2. However, it is possible to use an index scan keyed on 1 followed by another index scan keyed on 2. Since two index scans may be much less expensive than a single sequential scan, the optimizer will consider using multiple index scans. .pp In addition to restricting the scope of a search, index paths are also considered for another reason. During query processing, it may be necessary to sort an intermediate result prior to a merge-sort join (see figure 3.2), or the user may specify that the results of a retrieve query be sorted on certain fields. However, these sorts do not have to performed explicitly at all times. Some access methods maintain their tuples sorted on the keys used to define the structure. Thus, scanning a relation via such an index may yield tuples sorted in a desired order. For example, a standard B-tree stores its tuples sorted either in ascending (<) or descending (>) order, while an area B-tree maintains its tuples sorted in either \*(lqAREALT\*(rq or \*(lqAREAGT\*(rq order. .pp To make use of an index with this sort characteristic, the index keys must either match variables within join clauses, which correspond to relations that will later be merge-sorted, or attribute fields on which a query's resulting tuples will be sorted. To determine whether an index's implicit sort order is that which is needed, POSTGRES requires that users specify an access method's sort order (if it exists) when defining a new access method. If the implicit ordering matches a desired ordering and the keys are usable, a path that takes advantage of the index will be considered. The next two subsections will elaborate on further uses of this sort information. .sh 3 "Join Paths" .pp Once all feasible paths have been found for scanning single relations, paths are found for joining relations. Joins are first considered between every two relations for which there exists a corresponding join clause. For example, for the following query: .(l \fBretrieve\fR (A.a, B.b, C.c) \fBwhere\fR A.d = B.e, .)l during the first level of join processing, the only pairs considered are: .(l A join B B join A .)l All feasible paths are found for processing joins between these relation pairs. Having done this, all paths are then found for processing 3-way joins, using available 2-way join paths for the outer path and relation scan paths for the inner path. Again, the optimizer only considers those join pairs for which there is a corresponding join clause. If this heuristic results in no further relations being joined, all remaining possibilities are considered. For the above query, at the second level of join processing, no relations should be joined according to the heuristic. Therefore, the remaining possibilities are: .(l (A join B) join C (B join A) join C .)l From here, these steps are repeated until no further join levels need to be processed. .pp All possible join paths are generated for every join pair considered. The simplest join strategy is nested iteration. In a nested iteration join, the inner join relation is scanned once for every tuple found in the outer join relation. All available paths on the outer join relation are possibilities for the outer path. On the other hand, since the inner join path is independent of the outer in a nested iteration join, only the least expensive path for the inner join relation is a possibility for the inner path. .pp Nested iteration is simple, but it can be a time-consuming join strategy, especially if the inner join relation is not indexed on join variables. A join strategy that is much more attractive in these situations is merge-sort. A merge-sort join can be used to process a join between \fIrelation1\fR and \fIrelation2\fR, provided there is a merge join clause of the form: .(l \fIrelation1.field1 OPR relation2.field2\fR. .)l During the first phase of a merge-sort, each relation is sorted on appropriate join attributes. During the second phase, the merge phase, the two relations are merged together, taking advantage of the fact that both relations are ordered on join attributes. .pp For a merge-sort join to be advantageous, the operator within a merge join clause must be \*(lqsimilar to\*(rq an equality operator, e.g. \*(lqAREAEQ\*(rq. Therefore, in the most ideal situation, when both join relations contain unique values in the merge join fields, the merge phase will only require a sequential scan of both sorted relations. So when defining new operators, POSTGRES requires that users indicate whether an operator is \*(lqmergesortable\*(rq by specifying the operator that must be used to sort the two join relations prior to the merge. For example, \*(lq=\*(rq is mergesortable, provided the sort is made in \*(lq<\*(rq order, while \*(lqAREAEQ\*(rq is also mergesortable, provided the sort is in \*(lqAREALT\*(rq order. Therefore, if a join clause in the form specified above contains a mergesortable operator, then a merge-sort join path between the two relations in the clause is considered in addition to paths that process the join using nested iteration. .pp As alluded to earlier, relations may not always have to be explicitly sorted prior to a merge. If the keys of an index match join attributes and the index's implicit sort order matches the sort operator required for the merge, the relation need not be sorted; unless, of course, it is cheaper to scan a relation into a temporary via its least expensive path, sort the temporary, and then read the sort result. .pp A second join strategy that may be useful when indices are not available is hash-join. To process a join using this strategy, the inner join relation is first hashed on its join attributes. Then, the outer relation is scanned. For every tuple found, values within outer join attributes are used as hash keys to locate tuples in the inner join relation. Thus, to use such a strategy, the join operator also must be \*(lqsimilar to\*(rq an equality operator. Users will indicate this by simply specifying whether an operator is \*(lqhashjoinable\*(rq when defining a new operator. .sh 3 "Pruning The Plan Space" .pp In generating possible plans for a query, many paths are considered. In fact, the plan space is exponential because plans at lower levels are used in creating plans at higher levels. Furthermore, when indices and multiple join strategies can be used, there are a number of ways of processing scans and joins on identical relations. Moreover, some of these paths may be redundant. .pp Two paths are redundant if they scan identical relations, and their resulting tuples are sorted on identical fields. The latter is determined by making use of index sort information. For example, suppose the outer relation of a join is scanned using an index that sorts its tuples in ascending order, and the relation is joined with another relation using nested iteration. This join path is equivalent to another path where the outer relation is explicitly sorted into ascending order and merge-sorted with the same inner join relation. Although these two paths are different, they will yield identical results because both outer join relations are sorted in identical order, and joins preserve the sort order of the outer relation. Therefore, after generating plans for each level of joins, if two redundant join plans are found, the optimizer can eliminate the more expensive of the two, thereby reducing the size of the plan space. .sh 2 "Estimating Costs and Sizes" .pp To prune the plan space as well as determine the optimal plan, the optimizer must estimate the cost of executing every plan it generates. In the SYSTEM-R optimizer, both CPU and I/O time are accounted for in estimating costs. Every cost factor is of the form: .(l cost = P + W * T, .)l where \fIP\fR is the number of pages examined at runtime by a plan and \fIT\fR is the number of tuples examined. \fIP\fR reflects I/O cost, \fIT\fR reflects CPU cost, and \fIW\fR is a weighting factor that indicates the relative importance of I/O to CPU in terms of processing cost. Thus, for a sequential scan of a relation, since every page and tuple must be examined, \fIP\fR equals the number of pages in the relation and \fIT\fR equals the number of tuples. For a secondary index scan, the number of pages and tuples touched also depends on the number of pages and tuples in the index relation because index pages and tuples must be read first to determine where to scan in the main relation. .pp For every index, the number of pages and tuples touched is also determined by the fraction of tuples in a relation that one would expect to satisfy restriction clauses specified on the relation. This fractional quantity is called a \*(lqselectivity.\*(rq Selectivities are functions of a variety of parameters, including the operator in the restriction clause, the restriction constant, the number of records in an index, and the maximum and minimum values of entries stored in an attribute. In SYSTEM-R, every possible selectivity factor is hardwired into the cost estimation code. See table 3.2 for a sampling of selectivity factors. .(z .hl .sz \n(ep .TS center box; c|c l|l. qualification selectivity factor = r.field = value 1/(number of tuples in the index relation defined on r.field) _ r.field > value ((high value of r.field) - value) / ((high value of r.field) - (low value of r.field)) _ r.field < value (value - (low value of r.field))/ ((high value of r.field) - (low value of on r.field)) .TE .sz \n(pp .sp .ce 2 \fBTable 3.2\fR Examples of selectivity factors for SYSTEM-R .hl .)z .pp Cost estimation formulas for all join strategies are functions of the sizes, in pages and tuples, of the outer and inner join relations. To estimate the size of either an outer or inner join relation, the optimizer simply multiplies the original size of the relation by the selectivity of every restriction clause applicable to the relation. If the clause can be used with an index, the selectivity is computed as described earlier. If it cannot, SYSTEM-R resorts to an \*(lqelse case,\*(rq associating constants with these factors. The SYSTEM-R designers justify this simplification by stating that if an index is not defined on a relation, this implies that the relation is small; so if the selectivity is not accurate, the difference is insignificant. If the outer join relation is a composite relation, the desired selectivity is that of a join operation. Such a selectivity indicates the fraction from among the cross product of an outer and inner join relation one would expect to satisfy a join clause. Again, SYSTEM-R hardwires this information into the optimizer code. For a summary of the different cost formulas required, see table 3.3. .(z .hl .sz \n(ep .TS center box; c s s c|c|c l|l|l. Cost of Scans = P T _ Sequential Scan NumPages NumTuples _ Primary Index Scan NumPages*F NumTuples*F _ Secondary Index Scan NumPages*F + ITuples*F ITuples*F + NumTuples*F .TE .sp \fIwhere\fR .in +0.5i .nf NumPages = the number of pages in a relation NumTuples = the number of tuples in a relation ITuples = the number of tuples in an index relation F = combined selectivity factor of applicable restriction clauses .fi .in -0.5i .sp .ce .TS center box; c s l|l. Cost of Joins = Nested Iteration $C sub outer + N sub outer * C sub inner$ _ Merge-sort $C sub outer + C sub sortouter + C sub inner + C sub sortinner$ _ Hash-join $C sub outer + C sub createhash + N sub outer * C sub hash$ .TE .sp \fIwhere\fR .in +0.5i .nf $C sub outer$ = the cost of scanning the outer join relation $C sub inner$ = the cost of scanning the inner join relation $C sub sortouter$ = the cost of sorting the outer join relation into a temporary$" " sup \(dg$ $C sub sortinner$ = the cost of sorting the inner join relation into a temporary$" " sup \(dg$ $C sub createhash$ = the cost of hashing the inner join relation into a temporary $C sub hash$ = the cost of a single hash $N sub outer$ = the size of the outer join relation .fi .in -0.5i .sp 2 .nf .sz \n(fp $" " sup \(dg$ equals 0 if sort is not required .sz \n(pp .fi .sp .ce 2 \fBTable 3.3\fR Summary of cost formulas .hl .)z .pp The POSTGRES optimizer uses this same basic idea in estimating costs. As in SYSTEM-R, the system stores statistical information that cost formulas depend upon in database system catalogs. However, POSTGRES takes the novel approach of updating certain statistics, like the number of pages and tuples in relations, using demons, which execute in background mode. These demons are implemented using triggers, a feature POSTGRES supports. Another new idea is that other statistics, e.g., the high and low values of an attribute, are stored in the form of queries embedded within data fields. These queries will retrieve appropriate information from elsewhere in the database, and the system will cache the result so the optimizer need not repeatedly execute the same query. These two provisions alleviate problems other systems encountered when updating database statistics. INGRES updated statistics immediately, resulting in loss of concurrency because it blocked other users access to information in system catalogs. SYSTEM-R chose not to update statistics at runtime, instead requiring that a data base administrator run a special command to explicitly do the update. This, however, meant that statistics were not always up-to-date, possibly yielding incorrect cost estimations. .pp To account for all possible selectivities, the approach of storing information in catalogs is used again. One difference between selectivity information and other operator and access method information seen thus far is that selectivities are parameter dependent, as illustrated in table 3.2. An earlier approach suggested storing simple formulas within data fields and writing a parser to interpret the formula, substituting appropriate values for a fixed set of possible parameters [STON85a]. This is fairly straightforward, but not very flexible. Instead, our optimizer capitalizes on an inherent feature of POSTGRES. As already mentioned, POSTGRES supports embedding of queries within data fields. Generalizing on this idea, POSTGRES also allows users to define arbitrary procedures written in general purpose programming languages, like C and LISP, which can then be registered into the system and stored within data fields [STON86c]. Therefore, in POSTGRES every selectivity formula is expressed using a parameterized procedure. Each procedure accepts as its arguments the relations, attributes, and constants appearing within restrictions and the index identifier and number of index keys, if an index is used. The routine then retrieves necessary information from elsewhere in the database and returns a computed selectivity. .pp As discussed in reference to SYSTEM-R selectivities, selectivities come in three flavors. Therefore, there will be a selectivity routine associated with every feasible operator-class pair shown in table 3.1, and every operator will have two selectivitiy routines associated with it \*- one for ordinary restrictions, which are not used with index scans, and the other for joins. Each of these procedures is stored within appropriate tuple entries. .pp Thus, by executing the appropriate procedure with the appropriate parameters, selectivity computation is flexible and simple. A procedure written in pseudo C code that computes the selectivity of the operator \*(lq>\*(rq for a B-tree index is shown in figure 3.6. .(z .hl .(l .sz \n(ep .ft I /* * Procedure to compute the selectivity of the \*(lq>\*(rq operator * when it is used with a B-tree index defined on integer fields. */ .ft R float greater_btree (opid, relid, attnos, values, flags, indexid, nkeys) int opid; \fI/* contains unique id of operator \*(lq>\*(rq */\fR int relid; int attnos[]; int values[]; int flags[]; \fI/* equals 1 if clause is of the form `var > constant,' * else clause is of the form `constant > var' */\fR int indexid; \fI/* parameter isn't used by this particular routine */\fR int nkeys; { int i; int high; int low; float s; s = 1.0; \fBfor\fR (i = 0; i < nkeys; ++i) { high = retrieve high value of attribute `attnos[i]' in relation `relid'; low = retrieve low value of attribute `attnos[i]' in relation `relid'; \fI/* * the selectivity of multiple clauses is the product of the * selectivity of each individual clause */\fR \fBif\fR (flags[i] == 1) s = s * (high - values[i]) / (high - low); \fBelse\fR s = s * (values[i] - low) / (high - low); } \fBreturn\fR(s); } .sz \n(pp .)l .sp .ce 2 \fBFigure 3.6\fR Code to compute selectivity .hl .)z .sh 2 "Nested-attribute Queries" .pp The last several subsections have described optimization of simple queries, i.e. those without nested attributes. Figure 3.7 summarizes information the optimizer uses in generating possible query plans. .(z .hl .sz \n(fp .TS center; |c||c|c|c|c|c|c|c| c ||c|c|c|c|c|c|c|. _ OPER operator negator commutator msortop hash selectivity join-selec _ = \(!= = < yes \fIprocedures\fR \fIprocedures\fR < \(>= > no no \fIto compute\fR \fIto compute\fR \(<= > \(>= no no \fIselectivity\fR \fIselectivity\fR > \(<= < no no \fIof\fR \fIof\fR \(>= < \(<= no no \fI1-variable\fR \fIjoin\fR AREAEQ AREANEQ AREAEQ AREALT yes \fIclauses\fR \fIclauses\fR AREALT AREAGE AREAGT no no \fIcontaining\fR \fIcontaining\fR AREALE AREAGT AREAGE no no \fI\*(lqoperator\*(rq\fR \fI\*(lqoperator\*(rq\fR AREAGT AREALE AREALT no no AREAGE AREALT AREALE no no _ _ _ _ _ _ _ .TE .sp 2 .TS center; |c||c|c|c|c|c| c ||c|c|c|c|c|. _ AMOP access-method class operator selectivity strategy \(dg _ B-tree intops = \fIprocedures\fR = B-tree intops < \fIto compute\fR < B-tree intops \(<= \fIselectivity\fR \(<= B-tree intops > \fIof clauses\fR > B-tree intops \(>= \fIcontaining\fR \(>= B-tree areaops AREAEQ \fI\*(lqoperator\*(rq\fR = B-tree areaops AREALT \fIwhen used\fR < B-tree areaops AREALE \fIwith index\fR \(<= B-tree areaops AREAGT \fI\*(lqclass\*(rq\fR > B-tree areaops AREAGE \(>= hash hashops = = B-tree intops < sort B-tree areaops AREALT sort _ _ _ _ _ .TE .sp .nf $" " sup \(dg$ used in determining which operator corresponds to each generic operation (e.g., sorting) .fi .sz \n(pp .sp .ce 2 \fBFigure 3.7\fR Summary of optimizer information stored in system catalogs .hl .)z .pp From here on, the module implementing the algorithms just described will be called the \*(lqsubplanner,\*(rq while the entire optimizer will be labeled the \*(lqplanner\*(rq. To create access plans for queries containing nested attributes, the planner simply applies the subplanner algorithm once for each nesting level of attributes in a query. In other words, for any query, the number of times the subplanner is called is equal to the maximum nesting of attributes in the query. Once all subplanner calls have completed, the planner then builds a final plan that indicates how these subpieces fit together. Thus, given a query, the planner first modifies it to consider only top level attributes. This new query is passed to the subplanner to create a \fIsubplan\fR. The planner then modifies the original query to consider only nested attributes. This is recursively processed by the planner to create a \fIplan\fR, and the resulting access plan simply indicates which attributes from \fIsubplan\fR and \fIplan\fR should be returned to the user. .pp An example will illustrate these ideas more clearly. Suppose we have the following relation: .(l EMP ( name, dept, hobbies ), .)l where hobbies contains POSTQUEL queries to retrieve information about the different hobbies each employee participates in. One of these relations may be: .(l SOFTBALL ( empname, position, batting-history ), .)l where batting-history contains a POSTQUEL query retrieving information about an employee's past batting averages from the relation: .(l BATTING-HIST ( empname, year, avg ). .)l Given the following query: .(l \fIQ1\fR: \fBretrieve\fR (EMP.name, EMP.hobbies.batting-history.avg) \fBwhere\fR EMP.hobbies.batting-history.year = \*(lq1986\*(rq \fBand\fR EMP.hobbies.position = \*(lqcatcher\*(rq \fBand\fR EMP.dept = DEPT.dname \fBand\fR DEPT.floor = 1, .)l which finds the current batting average of employees who are catchers and work on the first floor, the planner will first consider the top level of attributes by passing the following query to subplanner: .(l \fIS1\fR: \fBretrieve\fR (EMP.name, EMP.hobbies) \fBwhere\fR EMP.dept = DEPT.dname \fBand\fR DEPT.floor = 1. .)l After the subplanner has optimized the above query, the planner then only considers attributes beyond the top level nesting: .(l \fIQ2\fR: \fBretrieve\fR (EMP.hobbies.batting-history.avg) \fBwhere\fR EMP.hobbies.batting-history.year = \*(lq1986\*(rq \fBand\fR EMP.hobbies.position = \*(lqcatcher\*(rq .)l and passes this query to itself recursively. This process is repeated, and in the process, the subplanner optimizes the following two queries: .(l \fIS2\fR: \fBretrieve\fR (EMP.hobbies.batting-history) \fBwhere\fR EMP.hobbies.position = \*(lqcatcher\*(rq \fIS3\fR: \fBretrieve\fR (EMP.hobbies.batting-history.avg) \fBwhere\fR EMP.hobbies.batting-history.year =\*(lq1986\*(rq .)l Since the maximum attribute nesting is three, recursion ends. The final plan is constructed as shown in figure 3.8, where \fIPn\fR is a subplan for executing subquery \fISn\fR. \fIR2\fR is a node corresponding to \fIQ2\fR that indicates that EMP.hobbies.batting-history.avg should be retrieved from \fIP3\fR, and \fIR1\fR corresponds to \fIQ1\fR, indicating that EMP.name should be retrieved from \fIP1\fR and EMP.hobbies.batting-history.avg originates from \fIR2\fR. .(z .hl .GS file figure3.8 .GE .sp .ce 2 \fBFigure 3.8\fR Structure of a query plan .hl .)z .pp To process this plan, the query executor first executes \fIP1\fR. As soon as execution of \fIP1\fR returns a single tuple, \fIT\fR, EMP.hobbies in that tuple is materialized into a temporary relation, if that has not already been done by POSTGRES's facility for preexecuting embedded queries. The executor then processes the subtree whose root is \fIR2\fR in a recursive manner for that instance of EMP.hobbies. Each EMP.hobbies.batting-history.avg value returned from this execution is combined with EMP.name from \fIT\fR to create a result tuple that is passed to the user. When execution of \fIR2\fR has completed, \fIP1\fR is reexecuted to retrieve another EMP.hobbies value that is used to process another instance of the \fIR2\fR subtree. This is repeated until all tuples from \fIP1\fR have been found. The subtree \fIR2\fR is processed similarly. \fIP2\fR is processed first, and \fIP3\fR is processed once for each instance of a qualifying \fIP2\fR tuple. .pp Processing nested-attribute queries in this way is attractive because it only requires a very clean extension of the basic optimization algorithm, and nested attributes are transparent to the subplanner. As a result, the code for query processing is also simpler. Furthermore, entire query plans are generated a priori, eliminating the need to optimize subqueries at runtime. .pp Optimizing nested-attribute queries a priori, however, does suffer because of its simplicity. In generating plans for higher nesting levels, the contents of relations that will be materialized from embedded queries are not known in advance. Therefore, the optimizer does not know the sizes of these relations or the distribution of values within nested attributes; this information or some estimate is normally required in computing subplan costs. To work around this problem, the optimizer simply assumes that materialized relations are all of the same size, and if a nested attribute appears within a clause, rather than return a parameter-dependent value for the selectivity, the selectivity code instead returns a constant that reflects the relative selectivities of various operators. For example, \*(lq=\*(rq is more selective than \*(lq>.\*(rq So a clause containing \*(lq=\*(rq may have a selectivity of $1 over 10$, while a clause with \*(lq>\*(rq has a selectivity of $1 over 4$. Although this may be an oversimplification, usually relations materialized from embedded queries will be small. So if the resulting plan is not the overall best choice in actuality, the chosen plan will not be a bad plan. .pp As an alternative, pieces of nested-attribute queries can be optimized at runtime. This can be advantageous not only because relation sizes and attribute distributions are known, but also because it enables the optimizer to consider special paths. For example, it may be possible to process an embedded query using a B-tree index that sorts its records in ascending order. If the tuples materialized from this query are later merge-sorted using an ascending sort, due to the available index path, the query processor need not explicitly sort the relation. A runtime optimizer would be able to note this. .pp Although more intelligent query plans are generated, there is a great deal of planning overhead associated with runtime optimization. For every tuple generated by \fIP1\fR, a subquery of the form: .(l \fBretrieve\fR (TEMP.batting-history.avg) \fBwhere\fR TEMP.batting-history.year = \*(lq1986\*(rq \fBand\fR TEMP.position = \*(lqcatcher\*(rq .)l must be optimized, where TEMP is the relation materialized from EMP.hobbies. Subsequently, for every tuple generated by the above query, the following query: .(l \fBretrieve\fR ($TEMP prime$.avg) \fBwhere\fR $TEMP prime$.year = \*(lq1986\*(rq .)l must also be optimized, where $TEMP prime$ is materialized from TEMP.batting-history. Due to this extra overhead, the efficiency of runtime optimization is questionable. .sh 2 "Query Plans" .pp The plan created by the optimizer is a tree of nodes. Each node corresponds to some scan, join, sort, or hash, or creation of a subresult. Scan and join nodes contain information indicating which attributes should be retrieved, which qualifications must be satisfied, and any other information relevant to the particular type of scan or join. Sort and hash nodes indicate which attributes should be placed into a temporary and the operator used to perform the sort or hash. A subresult node interconnects subplans and plans, indicating which attributes should be retrieved and from where. As an optimization, the topmost result node contains constant qualifications, i.e. those without variables, so these clauses can be examined prior to any other processing. .pp A possible (not necessarily the optimal) plan for the query introduced in the previous subsection is shown in figure 3.9. .(z .hl .GS file figure3.9 .GE .sp .ce 2 \fBFigure 3.9\fR Sample query plan tree .hl .)z There are a few things about the tree that should be elaborated on to avoid misconceptions. First of all, the materialization steps shown are not executed at runtime if the necessary embedded queries have already been preexecuted, and their results remain valid. Furthermore, as will become apparent later, these materialization steps are actually implicit in the plan tree. .pp From the figure, it would appear that throughout the plan tree, relation entries are explicitly identified using relation and attribute names. This would imply that the query processor would have to match identifiers to locate values that originate from nodes elsewhere in the tree. For example, references to TEMP1 and EMP attributes in the mergesort node would be found by searching for an appropriate identifier within tuples that originate from the two nodes below the mergesort node. This, however, is not the case. Explicit references are shown only for readability. Rather, an attribute is identified by its relative position within a specified tuple. By using this relative value and a descriptor associated with tuples returned by each node, the query processor can locate a desired attribute instantaneously. .pp The names of temporaries associated with materialized relations, again, are shown only for readability. In the actual plan tree, these relations are identified by the attribute containing the queries that will be used to build the temporary. For example, TEMP2 would be identified by the relative attribute identifier of TEMP1.hobbies, while TEMP3 would be identified by TEMP2.batting-history. By examining the contents of these referenced attribute entries, the query executor can determine whether materialization is necessary. Thus, the materialization step is implicit in these attribute references. .pp For temporaries associated with sorts and hashes, the name of the temporary shown in the tree serves merely as an identifier. It is left to the runtime executor to create the actual name.