Database system with methodology for reusing cost-based optimization decisions6618719Abstract A database system providing a methodology, implemented as an "Abstract Plan on Disc" technology (referred to herein as, "Ariadne"), is described for turning cost based optimization decisions into stored, reusable items. In particular, the present invention provides a novel language interface to the optimizer, through an Abstract Plan, through which it can be given a description of the desired query execution plan (QEP). The language interface defines a declarative language syntax that allows description of the QEP. It does not specify the sequence of operations the database system's optimizer and code generator should accomplish to generate the QEP, but rather describes the desired outcome. Such an approach provides an abstraction barrier between an optimizer directives language and some specific optimizer and code generator. In this manner, the present invention allows a database system the ability to generate a better execution plan, and thereby realize better query performance. Such a feature has particular utility in avoiding performance regressions on server release upgrade and in query optimization fine tuning. Claims What is claimed is: Description COPYRIGHT NOTICE
select distinct c.name, p.name
from parts p, customers c, orders o
where
p.part_id = o.part_id
and o.cust_id = c.cust_id
and c.country = "Fr"
and p.cost * o.no_items > 100000
and o.date > dateadd(day, -7, getdate())
order by c.name, p.name, o.no_items
returns the French customers that passed large orders on specific items during the last week, together with the items they ordered. However, it does not explicitly show how to process the three base relations to obtain the desired result. A relational algebra expression is an imperative description. It explicitly shows how to connect base and intermediate relations with relational operators, like join, restrict, project, union, and the like, to get the desired result. Conversely, the properties of the result set are not explicit, but implicit. A QEP interpreted by the execution engine of relational databases is isomorphic to a relational algebra expression. For instance, the expression:
(sort ()
(project (c.name p.name)
(join (p.part_id = o.part_id and p.cost * o.no_items > 100000)
(join (o.cust_id = c.cust_id)
(restrict (o.date > dateadd(day, -7, getdate()))
(table (orders o))
)
(restrict (c.country = "Fr")
(table (customers c))
)
)
(table (parts p))
)
)
)
precisely describes how to obtain the resulting derived table. A relational database code generator will be able to build a QEP for this expression, and a query execution engine that implements the join, restrict, project and sort relational operators will be able to interpret this QEP and return the desired results. Still, one has to deduce that orders issued by non-French customers, or French customers with only small amounts during the last week, despite being qualified at the base table scan level, will not be part of the final result. Note that there is always a canonical algebra expression giving the same result set as a calculus expression. Actually, the SQL language query semantics is given in terms of such an expression. It is obtained by projecting on the SELECT clause expressions the restriction on the WHERE clause predicate of the Cartesian product of the FROM clause base tables. For the SQL query above, the equivalent canonical algebra expression is:
(sort ()
(project (c.name p.name)
(restrict ( p.part_id = o.part_id
and o.cust_id = c.cust_id
and c.country = "Fr"
and p.cost * o.no_items > 100000
and o.date > dateadd(day, -7, getdate()))
(join
(join
(table (parts p))
(table (customers c))
(table (orders o))
)
)
)
)
The QEP obtained from this expression might be slow, but will be valid. Such canonical algebra expressions stay isomorphic with their initial calculus expression. They are the link between the two notations. 4. An Optimizer's Input and Output The optimizer's task is to chose among the many semantically equivalent QEPs the one it assumes to run faster, or, in general, complies the best to some optimization criteria. The input of the optimizer is the SQL query, or rather an isomorphic data structure obtained through parsing and some pre-optimization processing. For instance, ASE will normalize the query tree, then preprocess it, i.e., resolve the views, aggregates, subqueries, unions and RI constraints. Some of these operations are semantically implied by the information in the system catalogs, like adding RI constraints checks (but not resolving them too on the flight or deferred checks) and view replacement (but not resolution, i.e., associating to a view in the FROM clause its definition, but not also deciding about merging or materializing it). Note that both distinctions above are conceptual and not present in the ASE code, that atomically associates and resolves both views and RI constraints checks. Other operations imply flattening some nested statement constructs as parts of the statement's main join, like view resolution through merging, subquery resolution through flattening and on the flight RI checking. Such transformations are rule based algebraic rewrite optimizations. Hopefully, adding most items to the same join will result in a better QEP, as one increases the optimizer's search space, hence its chance to make a better choice. Yet others imply breaking the statement in several elementary joins, and storing intermediate results in work tables or CONSTANT nodes. This will be the case for view resolution through materialization, all aggregate resolution, subquery resolution through nesting or materialization, all union resolution and deferred RI checking. All of these last transformations are mandatory and reflect semantic necessities, like limitations of the execution model. Let us call the outcome of this transformations, i.e., the set of elementary joins (but not the processing of each of these joins) together with the work tables and CONSTANT nodes connecting them, the high level QEP structure. The ASE cost-based optimization per se has no impact on this high level QEP structure. It only chooses the join order and access path for each of the elementary joins. It also takes some limited decisions that affect the high level structure: reformatting and sort averting. The OR strategy would be of a similar nature, but ASE actually hides it more like an access method than as a work table operation. So, the input to the optimizer is the high level QEP structure described above, with each elementary join in a canonical form, i.e., isomorphic to both its initial declarative, calculus expression and to its canonical imperative, algebra expression. For ASE, it is the normalized and preprocessed query tree. The output of the optimizer is the QEP or an isomorphic data structure. For ASE, it is the JOINDATA data structure added to each elementary join, that describes the join order and access methods of that join. The actual QEP is obtained by code generation based on the above. As the QEP itself is isomorphic to a relational algebra, one may conclude that both the input and the output of the optimizer are isomorphic to two relational algebra expressions. The input is the canonical expression, let us call the output the cooked expression. 5. Relational Algebras as Abstract Plans Going back to language X, it should be able to instruct the optimizer to transform a canonical expression into a cooked one. Or, to be more precise, given the optimizer's input, that is isomorphic to the canonical expression, to instruct the optimizer about generating its output, that is isomorphic to the cooked one. To do that, an X expression will describe the desired optimizer output, i.e., a data structure isomorphic to the cooked expression. Then, both X's language processor and the native SQL optimizer will collaborate to generate an optimizer output that is compatible with the expression given in X. The natural choice for X will be a relational algebra. Nothing describes better something isomorphic to a relational algebra expression than the relational algebra expression itself. Language X will describe the desired QEP, but without going into the physical details that the optimizer and code generator are able to infer by themselves. Language X will have an abstract nature, and stay away of the implementation details of a specific query processing engine, like ASE. So, as X expressions are relational algebra expressions that describe QEPs, they are abstract plans. The true name of language X is thus Abstract Plan, or AP. It is a relational algebra that describes the required properties of the QEP. 6. Operator vs. Functional Notations As to the style of the notation to be used, there are several possibilities. Consider a two-table join, like:
select * from t1, t2
The algebra expression connecting the nested_loops binary relational operator to its two base relation arguments t1 and t2 could be: functional list (Lisp) style
(nested_loops t1 t2)
application style
nested_loops(t1, t2)
operator
t1 nested_loops t2
The three are identical in expressive power, the difference being in readability. Note that the operator style could imply parsing ambiguities that can be solved implicitly by associativity and precedence rules or explicitly by parenthesis. Also that the application style requires a construct for lists--as the list of projection expressions. Finally, the Lisp notation, if also applied to non relational expressions, like restrict and join operator predicates and project operator expressions, makes them look different of their SQL expression. AP uses the Lisp style functional notation. 7. Logical vs. Physical Algebra Relational algebras can be either logical or physical. Logical algebras are pure relational formalisms, i.e., their only operators are the mathematical (multiset) relational operators: join, outer-join, semijoin, restrict, project, delta-project, aggregation, union, intersection, difference, and the like. Non-relational elements, like algorithms implementing the operators, sorting, access methods to stored data, or the like, are not present. Such elements fill the gap between the mathematical formalism and actual engines implementing it. Each logical operator has an associated set of physical operators, that implement it. For instance, the join logical operator is associated to a set of physical operators describing the various join algorithms: nl_join, sm_join, hh_join, and so forth. Physical algebras contain only physical operators. The canonical algebra expression describing the optimizer's input is in general a logical one. No algorithms are chosen yet. The QEP description that the optimizer produces is in general a physical one, precisely instructing the code generator. The AP algebra needs to reach the physical level. It has to describe precise execution mechanisms, as join techniques and types of scans. So, the AP algebra needs to contain operators that describe specific join algorithm and access path. Thus, nested loops, merge join, index scan need to be present. To illustrate this with an example, let us consider the query (where cij is a column of table ti):
select c11, c21 + 1 from t1, t2 where c12 = c22 and c23 = 0
A semantically complete canonical expression of this query in a logical relational algebra would be:
(project
(c11 (+ c21 1))
(restric
(and
(= c12 c22)
(= c23 0)
)
(join
t1
t2
)
)
)
An optimizer could manipulate it to obtain an efficient plan, that pushed the restriction as down as possible, and uses the join order that takes best advantage of the join clauses, indices and relation cardinalities, as described by the following cooked expression:
(project
(c11 (+ c21 1))
(restrict
(= c12 c22)
(join
(restrict
(= c23 0)
t2
)
t1
)
)
)
Then, it would be the task of the compiler to generate an QEP that scans t2 with an index on c23, t1 on an index on c12 and uses nested loops for the join. But, this could actually be wrong! Maybe t2 should actually be scanned on an index on c22, without restricting the scan but only the qualifying rows, and merge join should be used instead. Clearly the above logical algebra does not provide a sufficient level of details. What is actually needed as an input to the code generation are the specific access methods and join algorithms. This is achieved by either of the following (suppose the indices of t1 and t2 are called i_c . . . ):
(merge_join
(index_scan
i_c22
t2
)
(index_scan
i_c12
t1)
)
)
(nested_loops
(index_scan
i_c23
t2
)
(index_scan
i_c12
t1)
)
)
One would thus expect to see in the AP algebra constructs that describe the query processing building blocks, as joins and the different join algorithms, indices, index and table access methods, derived table materialization and potentially even pure procedural ones, like sequencing several execution steps and holding intermediate results in work tables. 8. Semantic Completeness of an Abstract Plan Let us go back to the two physical algebra expressions above. At such a level, one can either rely on the code generator to identify the places where each clause should be used, or add them to the description:
(= c21 c22)
(restrict
(= c23 0)
(index_scan
i_c22
()
t2
)
)
(index_scan
i_c12
()
t1)
)
)
(nested_loops
(= c21 c22)
(index_scan
i_c23
(= c23 0)
t2
)
(index_scan
i_c12
()
t1)
)
)
In the merge join case, this formula indicates that the join should be done on "c21=c22", that both tables need a full index scan but that t2 can be filtered on "c23=0" before the join. For the nested loops plan, "c23=0" will be actually used to limit (position and stop) the index scan. An AP algebra is semantically complete when it conceptually allows the code generator to base the QEP of a SQL statement only on the corresponding AP expression and fully bypass the SQL statement and its previous processing, as parsing, normalization, preprocessing and optimization. If the SQL statement carries information that is not represented in the AP, then the AP algebra is not semantically complete. For instance, if the AP algebra only describes relational expressions but not scalar ones, it will be semantically incomplete, as it cannot describe the predicate in the WHERE clause and the expressions in the SELECT list. It is the responsibility of the optimizer and code generator to manage all the information in its input that is not described by the AP algebra. Note that the semantic completeness reaches further than its definition. For an embodiment in ASE, actually basing the query compilation on the semantic completeness of the AP would not be practically desirable, as the query tree contains data type normalization information obtained by catalog lookup, and throwing it away before code generation would require normalizing again. However, it is impossible to express complex algebraic transformations with a semantically incomplete AP, and optimizing with algebraic transformations is currently done based on heuristics rather than cost-based, a less flexible technology. Hence, the semantic completeness of the AP algebra is in principle a desirable feature even when the code generation is not based solely on the AP. Currently, the AP algebra is not semantically complete. The initial embodiment of Ariadne does not attempt to express algebraic transformations, so the restrict and project operators together with their non-relational expressions are not needed. 9. Full and Partial Plans Given an AP algebra, some QEP can get a full description within the limits of the model, or just a partial one. A partial one can be augmented to better describe the QEP, while a full description cannot, as all that can be said about the QEP (within the expressive limits of the AP algebra) is said. For instance, for an AP algebra that describes at the physical level joins and scans, consider the SQL query:
select *
from t1, t2
where c11 = 0 and c12 = c22
A full description would be:
(nl_join
(i_scan i11 t1)
(i_scan i22 t2)
)
Indeed, there is nothing more that can be said within the limits of the AP algebra at hand, except the join algorithm, the join order, and the access method for each stored table. Conversely, the following APs are all partial, less and less complete:
(nl_join
(i_scan t1)
(i_scan t2)
)
(nl_join t1 t2), (i_scan i11 t1)
(nl_join t1 t2), (i_scan t1)
(nl_join t1 t2)
(i_scan i11 t1), (i_scan i22 t2)
(i_scan t1), (i_scan t2)
(i_scan i11 t1)
(i_scan t1)
In general, a partial plan excludes only parts of the RAFSS leaving thus more freedom to the optimizer, while a full one tightly constraints the optimizer choices. Partial plans are lists of AP expressions and are called hints. Another way a plan may become partial is to use logical operators instead of physical ones. For instance, the following AP leaves to the optimizer the choice between the possible join algorithms:
(join
(i_scan i11 t1)
(i_scan i22 t2)
)
An important consequence is that, to allow partial plans, the AP algebra may not be a pure physical one, but a mixed algebra containing both the mathematical operators and the algorithm related operators. 10. Non Relational Elements Except for the physical and logical relational operators, the AP must describe non-relational elements. To start with, the physical operators have set of properties influencing their behavior. For instance, a scan can use LRU (least-recently used) or MRU (most-recently used), large IOs, can be serial or parallel, and the like. Traditional optimizer directives allow the specification of such properties, and so will the AP algebra. Then, a formula's usage will imply matching the formula's parts against the query at hand to identify to what query tree element a directive applies, then interpret the directive in the query's context to force the optimizer's behavior. The current version of AP algebra uses a simple solution, as it does not attempt to influence the high level QEP structure and it does not describe predicates and other scalar expressions. The AP algebra contains a high level, non-relational layer isomorphic to the high level QEP structure. It is required that an AP perfectly matches at the high level the optimizer's input (except for hints plans, when each hint in the list is tentatively applied to each elementary join). For each elementary QEP join tree, the participating stored tables allow a perfect match with the AP at the leaf level. Then, the tree structure described by the AP can be cloned into the QEP. There is a slight difficulty related to ambiguous usage of the same table name in a query. Correlation names are the SQL technique used to disambiguate such statements. However, there are cases when a SQL statement that uses several occurrences of the same table name is not ambiguous, while its corresponding AP is. For instance, it is legal in SQL to use the same table name in both the main query and a subquery or a view contained therein. If the subquery is flattened, or the view is merged, then the AP will be ambiguous. The AP algebra solves this by qualifying table names occurring in subqueries or views with the subquery number or view name. 11. Operator to Operand Glue When the AP language is not semantically complete, the QEP of a query will contain items not described by its AP. These QEP items have no AP counterpart and are interspread between the QEP items that do. For instance, even if the AP does not describe project and restrict operators, the QEP will contain them. Consider the query:
select *
from t1, t2
where c11 < c12
and c11 > 100
and c12 = c21
Its full (within the limits of a given AP language), but semantically incomplete AP would be:
(nl_join
(i_scan i_c11 t1)
(i_scan i_c21 t2)
)
However, in a semantically complete algebra (called SCA), the same query is described by:
(nl_join
(restrict (c11 < c12)
(i_scan i_c11 (c11 > 100) t1)
(i_scan i_c21 (c12 = c21) t2)
)
)
An extra operator, restrict, has stalked its way between the nl_join and t1's i_scan. One cannot say that the glue between AP operators and operands is strong, as the optimizer and code generator are allowed to insert extra relational operators between the AP operator that is a consumer of a derived table, and the producer of that derived table, that is an immediate operand in the AP expression of that operator. An AP operator is said to be tightly coupled to its operand when a compatible QEP is not allowed to have any intermediate items between the ones described in the AP by the operator and by the operand, or that in the SCA expression describing the QEP the corresponding operator is directly applied to the corresponding operand. An AP operator is said to be loosely coupled to its operands in the opposite case, when the only requirement is that, in the directed graph of the SCA expression describing the QEP, a path goes from the corresponding operator to the corresponding operand. When all operators in the AP language are tightly coupled, the AP is said to be tightly coupled. If all are loosely coupled, the AP is said to be loosely coupled. Note that a tightly couple AP is not necessarily a semantically complete one. The requirement is rather that it describes with relational operators all QEP relational algorithms. In a tightly coupled AP, the expression:
(join
(scan t1)
(scan t2)
)
represents an actual join between t1 and t2. In a loosely coupled one, it merely says that t1 is somewhere outer to t2 in the join graph (or join order for left deep tree engines). Likewise, a pair of hints:
(join
(scan t1)
(scan t2)
)
(join
(scan t1)
(scan t2)
)
mean, in a loosely coupled AP, just that t1 is placed in the join order somewhere outer to both t2 and t3. In a tightly coupled one its interpretation is less obvious. It is either an error, or (on query engines supporting it), a single n-way join operator (like a Star join) with at least three operands t1, t2 and t3, where t1 is outer to both t2 and t3. In the initial embodiment, the AP language is loosely coupled. In general, this leaves no explicit way to forbid the optimizer to take a decision. The only way to achieve that is to force an alternative that excludes the undesired one. For instance: to avoid an index scan of t, one must describe a table scan
(t_scan t) ==> not (i_scan t)
to avoid a table to be outer in a join, a set of hints should describe it as inner to all other tables
(join t2 t1) (join t3 t1) (join t4 t1) ==> not (join t1 . . . )
by convention, both reformatting and the OR strategy are forbidden when either a table scan or an index scan are forced
(i_scan t1) ==> not (scan (store (scan t1)))
and not (rid_join (union (scan_rid i1 t1) . . . ) t1)
(t_scan t1) ==> not (scan (store (scan t1)))
and not (rid_join (union (scan_rid i1 t1) . . . ) t1)
there is currently no way to avoid a sort, i.e., to require a sort avert path. 12. Associating an AP to its Corresponding Query Traditionally, optimizer directives are syntactically included in the statement's text. This is the case with ASE's forced options, as well as for other DBMS systems. Ariadne takes a different approach, as one of the requirements is to be able to influence the optimization of a statement without having to syntactically modify it. This requirement's importance is tantamount. Optimizer directives that are syntactically contained in the SQL statement text have two major shortcomings: in some cases they cannot be used This happens, for instance, when the SQL statement is not written by a human, but generated by a program generator. Most SQL generators do not give the user the possibility to modify the generated SQL code. Also, this happens with old production applications, that have the SQL code buried in the binary. Such applications are generally very stable, except when a RDBMS new version contains optimizer changes. in most cases they are not desirable SQL is a declarative language, and this is one of its major strengths. The same statement can be executed in many ways, depending on the cardinality and values distribution of the data. In its lifetime, a same statement will thus optimally be executed with different QEPs. However, optimizer directives are static. More, it is against the spirit of the language to expose the details of the query processing in the SQL statement. Form another perspective, a lot of software vendors who use SQL (and most of the CAPs) strive to keep their code RDBMS vendor independent, to be able to offer their products to organizations that have already made different RDBMS vendor choices. They will keep their SQL code compliant to the standard (currently SQL92), or will be even more conservative and will intersect the standard with the major commercial SQL dialects. However, in this greatest common denominator there is no common optimizer directives feature. Conversely, this requirement raises a major problem: how to identify an incoming SQL statement, to be able to recognize it and associate it to its corresponding AP. Identifying means naming. But, in general, SQL statements are anonymous; they stand for themselves. (A SQL statement that is part of a stored procedure may be identified by the stored procedure's name or ID and its position within the procedure, but this is a particular case.) It results that the identity of a SQL statement, in general, is given by the statement's textual contents. The AP association will thus be based on the SQL statement's text. Precisely, it will be based on a transformation of the statement's text. The purpose of this transformation is to eliminate parts of the statement that are irrelevant to the AP. Let us describe the Abstract Plan of SQL statements by an application abstract_plan(s).fwdarw.ap, defined on SQL statements and taking values in the AP algebra. This application associates to a statement its full AP and is functional. (Note that without the requirement of having full APs, the application is not functional, as a large number of partial plans, or hints, can describe a SQL statement). Consider a functional application canonical(s).fwdarw.t defined on strings (a SQL statement being ultimately a string of characters) and taking values in some set T. Note that the canonical form of a SQL statement defined by the canonical( ) transformation is completely unrelated to the canonical algebra expression into which a SQL statement may be transformed. It is just a coincidence of the canonical term usage, as both are representative instances for a set of related items: the canonical algebra expression stands for all the expressions having the same semantics, while the canonical form of a SQL statement, as will be seen below, stands for all the statements associated with the same AP. This application is undefined for strings that are not SQL statements. The first requirement on T is that it should be possible to base on it an efficient associative memory storage. This memory will be used to store sets of APs. Formally, this memory M implements the functional applications insert(M, T, AP).fwdarw.M and find(M, T).fwdarw.{AP}. This memory stores sets of APs associated to a specific t. Formally, if find(m, t)=S and m'=insert (m, t, ap) then find(m', t)=S U {ap}. This memory is filled through the composition add(s)=insert(m, canonical(s), abstract.sub.- plan(s)) and searched through the composition associate(s)=chose(find(m, canonical(s))) (where chose( ) is the mathematical selection operator that picks some random element in a set). The second requirement is that associate( ) is still a functional application for each s, i.e., that two statements that give different plans are mapped to different points in T, or that one can always find back the AP stored with add( ) for any statement s. Since associate( ) is functional, for all interesting points in T find( ) will either fail or find a single element set. Hence the definition are relaxed for M, insert( ) and find( ) to store and retrieve APs instead of sets of APs. Finally, while not being a requirement, the less injective canonical( ) is (provided it complies with the two requirements above), the better it is. Actually, the purpose of this transformation is that the set of statements giving the same AP map to the same point in T, reducing thus the size of M for a given set of statements to store. A first example of canonical( ) transformation is the identity transformation. Indeed, string comparison (and some hashing technique for performance) allow the implementation of an associative memory. Also, the identity guarantees the functional behavior of associate( ). However, it performs poorly on the third desiderata, as the identity is perfectly injective and thus performs no storage reduction at all. A better example would be the whitespace trimming transformation. However, the storage reduction is still modest. A transformation that returns the set of stored tables accessed by the statement does not obey to the second requirement. Indeed, lots of queries with very different QEPs, hence APs, may access the same tables. Finally, syntactic parsing, that associates to a statement its query tree does not obey, at first sight, to the first requirement: it is not obvious how to efficiently base an associative memory on a query tree, but not impossible though. The initial embodiment of Ariadne will use whitespace trimmed SQL text as a canonical SQL statement form. D. User Guide 1. General Abstract Plan is a novel language interface to the optimizer, through which it can be given a description of the desired QEP. Once an Abstract Plan expression is applied to a statement's optimization, the resulting QEP must be compliant to the given AP. The term Abstract Plan, and the abbreviation AP will be freely used hereafter for both the language itself, and for specific expressions of this language. A similar functionality exists in ASE: the forced options. For instance, it is possible to force the index used to scan a stored table with the following syntax:
select * from t1(index i_c11)
where c11 > 100 and c12 < 0
The optimizer is instructed to use the index i_c11 (on column c11) for the scan. It will therefore position the scan using the clause "c11>100" rather than the clause "c12<0". Also, it is possible to force the join order of an individual query:
set forceplan on
go
select * from t2, t1
where c11 = c21
and c12 > 100
and c22 < 0
go
set forceplan off
go
The optimizer is instructed to put t2 before ti in the join order. It will probably use an index on c22, if available, to scan t2 using the clause "c22<0", and chose between the join clause "c11=c21" and the search clause "c12>100" to scan t1 (in the typical case it will use the join clause, but in general this is a cost based decision and there are cases when the search clause performs better). There are, however, several optimization decisions impossible to force at all, or on a per statement item basis. The subquery attachment point cannot be forced. Neither can the join order of flattened subquery tables. Reformatting and the OR strategy can be forced with trace flags, but apply then to all elements of all queries of all connections that have at least one trace flag enabled, due to the design limitations of the ASE trace flags mechanism. Also, the forced options require syntactic changes in the statement, that is not always possible or desired. The two forced options examples above can also be described in AP:
(i_scan i_c11 t1)
(g_join (scan t2) (scan t1))
Abstract Plans are relational algebra expressions that are not syntactically included in the query text. They are stored in a system catalog and associated to the incoming queries based on the text of these queries. They overcome thus the shortcomings of forced options, by offering fine grained description capability and not requiring statement text modification. 2. Expressing Optimization Directives Through Abstract Plans This section describes how to use APs to influence the optimizer's behavior. To start with, let us focus on the language capabilities of the AP language, and accept that an AP expression is associated deus ex machina to its corresponding SQL query. The AP language is a relational algebra with the following relational operators: g_join: the generic join, a high level logical join operator. It describes inner, outer and existence joins, using any available join algorithm (only nested loops in ASE). union: a logical union operator. It describes both the UNION and the UNION ALL SQL constructs. scan: a logical operator, that transforms a stored table in a flow of rows, i.e., a derived table. It is needed to define g_join only on derived tables, and allow partial plans that do not restrict the access method. i_scan: a physical operator, implementing scan. It directs the optimizer to use an index scan of the specified stored table. t_scan: a physical operator, implementing scan. It directs the optimizer to use a full table scan of the specified stored table. store: a logical operator, describing the materialization of a derived table in a stored work table. nested: a filter, describing the placement and structure of some operation relevant to the optimizer. Currently only describes nested subqueries. The following database schema will be used throughout this section to illustrate AP usage:
create table t1 (c11 int, c12 int)
create table t2 (c21 int, c22 int)
create table t3 (c31 int, c32 int)
go
create index i_c11 on t1(c11)
create index i_c12 on t1(c12)
create index i_c11_c12 on t1(c11, c12)
create index i_c21 on t2(c21)
create index i_c22 on t2(c22)
create index i_c31 on t3(c31)
create index i_c32 on t3(c32)
go
(a) Access Methods A prime area for influencing an optimizer is the access path selection. For any specific table, there can be several access path that apply to a specific query: index scans using different indices, table scans, the OR strategy, reformatting. Take the query:
select * from t1 where c11 > 1000 and c12 < 0
The following APs can direct the optimizer's choice: use i_c11
(i_scan i_c11 t1)
use i_c12
(i_scan i_c12 t1)
use some index, it is up to the optimizer to chose among i_c11 and i_c12, but it should not do a full table scan
(i_scan t1)
do a full table scan
(t_scan t1)
Other access paths, like the reformatting and the OR strategy, will be described below, with the complex queries section. Also, the hints section will show how to give the access path for several tables of a query without forcing their join order too. (b) Join Order The other fundamental directive APs should be able to give is the join order. This is done by describing the join tree. Consider the query:
select *
from t1, t2, t3
where c11 = c21
and c12 = c31
and c22 = 0
and c32 = 100
Join operators are binary, so is AP's g_join. The t2-t1-t3 join order of the above query is described by:
(g_join
(g_join
(scan t2)
(scan t1)
)
(scan t3)
)
Note the usage of the logical scan operator, that gives the optimizer the freedom to chose the access methods. Therefore, the above plan is not a full plan, but a partial plan. In general, binary operators may create any binary expression tree, and are described by a tree structure rather than by an order. However, a lot of commercial RDBMS execution engines are limited to left deep trees. Such trees have the derived tables on the left hand, and the stored tables on the right hand (except for the deepest left leaf, that is itself a stored table). A left deep tree is a degenerated tree, that is equivalent to a list. Lists are characterized by the order of their elements, hence for lots of commercial RDBMSes, including ASE, discuss the join order. In general, a n-way join, executed as a n-1 levels left deep join tree with the order t1, t2, t3 . . . , tn-1, tn is described by:
(g_join
(g_join
. . .
(g_join
(g_join
(scan t1)
(scan t2)
)
(scan t3)
)
. . .
(scan tn-1)
)
(scan tn)
)
It is important to keep this notation, as it closely matches the relational algebra binary operator join, and is also useful to describe nested element attachment, as will be seen below. However, in most cases it is fastidious for a simple left deep tree, that is best described by its join order than by a degenerated tree. To enhance AP readability, a shorthand syntactic notation was introduced for the above join:
(g_join
(scan t1)
(scan t2)
(scan t3)
. . .
(scan tn-1)
(scan tn)
)
It must be clearly understood that the second, n-ary g_join, notation is purely syntactic sugar for the first, binary left deep g_join, tree. It does not describe a n-way join operator, but n-1 binary join operators applied to n operands. Going back to the three way join query, depending on cardinalities and data distribution, the optimizer could select among several plans: qualify t2 on c22, join with t1 on c11, then with t3 on c31
(g_join
(i_scan i_c22 t2)
(i_scan i_c11 t1)
(i_scan i_c31 t3)
)
also along the join clauses, but t3-t1-t2 this time
(g_join
(i_scan i_c32 t3)
(i_scan i_c12 t1)
(i_scan i_c21 t2)
)
or, maybe c21 being non-clustered and t2 fitting in the cache, it is better to do once a full table scan of t2
(g_join
(i_scan i_c32 t3)
(i_scan i_c12 t1)
(t_scan t2)
)
finally, a STAR join, when t1 is very large, t2 and t3 individually qualify a large part of it, but together a very small part, and the t2-t3 cross product (after restricting their scan) is reasonable small
(g_join
(i_scan i_c22 t2)
(i_scan i_c32 t3)
(i_scan i_c11_c12 t1)
)
Note that all the above are full plans that completely constrain the optimizer in its choices of join order and access path selection. The initial embodiment of Ariadne lets the optimizer decide, based on the query, the specific kind of join to use for a generic g_join operator. This is because AP explicitly avoids affecting the query's semantics, that is still fully given by the query tree. Now, logical join operators come in different flavors, with different semantics: inner joins, outer joins and semijoins. It is undesirable to instruct through the AP the optimizer to build a QEP that has a different semantics than the SQL query. Therefore it is left up to the optimizer to chose the join operator the corresponds to the query at hand and the given join order. Take, for instance, the existence subquery:
select * from t1
where c12 > 0
and exists (select * from t2
where t1.c11 = c21
and c22 < 100)
The semantics of the statement requires a semijoin between t1 and t2. A t1-t2 order will be interpreted by the optimizer as an existence join implementation of the semijoin:
(g_join
(scan t1)
(scan (table t2 (in (subq 1))))
)
where t2's scan will stop on the first row matching the current t1 row. Conversely, t2-t1 will be interpreted as a tuple filtering implementation of the semijoin:
(g_join
(scan (table t2 (in (subq 1))))
(scan t1)
)
where t2 will be scanned on i_c21 to enforce the unicity for inner correlation values. However, the search clause "c22<100" cannot be used to limit the scan. The "(table . . . (in (subq . . . ) . . . ))" notation is needed to disambiguate some specific subquery statements and will be explained later. For the time being, "(table t2 (in (subq 1)))" is perfectly equivalent to "t2" and can be thought of as a reminder on the syntactic containment of t2. Instantiations like the one of g_join can be left to the ASE optimizer, as its choices are rather limited. Note that tuple filtering is an on-the-flight form of delta-project, when the data comes ordered. If, for instance, the execution engine also implemented the general delta-project, then the above AP would be compatible with both plans below:
(inner_join
(tuple_filter (c21)
(i_scan i_c21 (table t2 (in (subq 1))))
)
(scan t1)
)
(delta_project (c11, c12)
(inner_join
(i_scan i_c22 (table t2 (in (subq 1))))
(scan t1)
)
)
Within the current ASE framework, the above query has no QEP for the AP:
(g_join
(i_scan i_c22 (table t2 (in (subq 1))))
(scan t1)
)
Provided the subquery table correlation columns are not known to have unique values (i_c21 is not declared unique), when the subquery table is joined outer to its correlated main query table and is not scanned on an index on the correlation column, then the ASE query engine can not eliminate subquery generated duplicates in the query result set. The same mishap occurs with outer joins:
select * from t1, t2
where c11 *= c21
There is no QEP for the AP:
(g_join
(scan t2)
(scan t1)
)
The ASE query engine's single outer join algorithm requires the inner table of the outer join to be also the inner table of the join, to substitute NULLs when no inner row qualifies for a given outer row. In the initial embodiment of Ariadne, such APs will raise an exception and 5 abort the compilation of the query. They are never generated by the ASE in AP capture mode (mode described further below), and their presence is related to a human error. Finally, note that the AP algebra allows the description of flattened subquery related join orders that can not be required with the traditional forceplan. For instance, given the query:
select *
from t1, t2
where c11 = c21
and c21 > 100
and exists (select * from t3 where c31 != t1.c11)
that can be flattened to an existence join, the "!=" correlation will make t3's scan rather expensive. If t1 is outer to t2, the best place for t3 depends on whether the join increases or decreases t1's scanned rows. Generally the optimizer should find the light position for t3. If it fails, the following AP should be used when the derived table's cardinality is decreased by the join:
(g_join
(scan t1)
(scan t2)
(scan (table t3 (in_subq 1)))
)
And the following when it is increased:
(g_join
(scan t1)
(scan (table t3 (in_subq 1)))
(scan t2)
)
APs and subqueries are also discussed later. The same applies to merged views:
create view v
as
select *
from t2, t3
where c22 = c32
When v is merged in a main query, the optimizer generally finds the right join order. Consider two queries over v:
select * from t1, v
where c11 = c21
and c22 = 0
select * from t1, v
where c11 = c31
and c32 = 100
Supposing the best join orders are respectively t2-t1-t3 and t3-t1-t2, and the optimizer fails to chose them, the following APs achieve what forceplan could not:
(g_join
(scan (table t2 (in (view v))))
(scan t1)
(scan (table t3 (in (view v))))
)
(g_join
(scan (table t3 (in (view v))))
(scan t1)
(scan (table t2 (in (view v))))
)
The "(table . . . (in (view . . . . ))" notation should be also taken, for the moment, as such. More on APs and views later. (c) Join Algorithm Currently ASE implements two join algorithms: nested loops join (NLU) and merge join (MJ). When the g_join operator is used, the optimizer is free to chose the best join algorithm, based on cost estimations. As this decision is as error prone as any other optimizer estimation, it is desirable to be able to force the join algorithm using an AP. This is achieved by adding to the logical g_join operator the couple of physical operators nl_join and m_j_join, that also specify the join algorithm. Note that "g" (generic) in g_join does not stand for the algorithm, but for the inner/outer/semi flavors of the join semantics, hence is kept in the physical operators. When an algorithm is forced, the FROM clause forced options internal machinery is used by the AP code. The APs generated by the system will use nl_join/m_join instead of g_join. g_join is still a legal operator, that lets the optimizer chose the join algorithm. For instance, given the query:
select * from t1, t2
where c12 = c21 and c11 = 0
the following AP describes a NLJ:
(n1_g_join
(i_scan i11 t1)
(i_scan i21 t2)
)
whereas the one below a MJ:
(m_g_join
(i_scan i12 t1)
(i_scan i21 t2)
)
Note that while the NLJ would use the index t1.i11 to limit the scan using the search clause, MJ would need to use t1.i12 for the ordering, to avoid a sort. Alternatively, it could still use t1.i11 and sort the filtered derived table:
(m_g_join
(i_scan i11 t1)
(i_scan i21 t2)
)
With this AP, the optimizer is expected to know that the outer table has the wrong ordering, and generate a sort on c12 on top of the index scan and below the MJ. The biggest issue brought by MJ is forcing the sorting behavior. It was purposely avoided in Ariadne to have the AP syntax affect the semantics of the query, i.e., the same query optimized with or without an AP may have different performance, but always has the same result set. If one allows the AP syntax to force the sorting behavior on the inputs of the MJ, this does not hold anymore. Indeed, the MJ algorithm applied to unsorted inputs gives a wrong result set. However, the current ASE optimizer is not that good in propagating the ordering information, specifically for the outer derived table, where it always assumes it must sort. As a consequence, the optimizer would generate sub-optimal plans that sort the outer data flow, even when it is not needed. It is clearly desirable to be able to use APs to indicate the optimal plans, when the outer sort may be averted. Still, there is nocode to check that such an AP indication is semantically valid. Hence, if the outer derived table is actually not ordered, such an AP would result in a wrong result set. The trade-off was to introduce the operators that force the sorting behavior (no sort, sort only outer/inner, sort both: fm_g_join/lm_g_join/rm_g_join/sm_g_join), but to let them undocumented (by now, unless the module that does the semantic check is written) and to generate the m_g_join operator, that does not constrain the sorting behavior. This way, APs can be used for benchmarks and other sensitive situations where people understand what they're doing, but the average user will not have the risks of giving a wrong sort averting directive. It is expected that on the side where the AP averts the sort, the scan of the table is an i_scan with the specific index that gives the right ordering, but Ariadne does not enforce this. Using again the query above, let us analyze the different possible APs.
(fm_g_join
(i_scan i12 t1)
(i_scan i21 t2)
)
The AP above averts both sorts, and forces the right indices.
(fm_g_join
(i_scan i11 t1)
(i_scan i21 t2)
)
The AP above is wrong. It forces no sorting, but the index on the outer table does not give the right ordering. A wrong result set will be produced.
(lm_g_join
(i_scan i11 t1)
(i_scan i21 t2)
)
The AP above forces the sort of the outer derived table, and forces the index that can use the search clause to limit the scan. It also forces not to sort the inner table, that is fine given the index used for the scan.
(rm_g_join
(i_scan i12 t1)
(i_scan i21 t2)
)
The AP above does an useless (and harmless) sort of the inner derived table, that had the right ordering due to the index scan. The outer derived table is not sorted, that is fine given the index used for the scan.
(sm_g_join
(i_scan i11 t1)
(t_scan t2)
)
The AP above forces the sort of both outer and inner derived tables. That was needed, given that the outer one uses an index that does not bring the right ordering, and the inner one does a table scan, that brings no ordering. (d) Hints There are cases when a full plan is not needed. Given a specific query, the NC index costing could have a pessimistic view on an index, and find a full table scan better, while in fact the index is better. However, the rest of the optimizer model could apply well to the query at hand. For instance, if in the following 3-way join the optimizer believes i_c31's order is highly non-correlated to t3's storage order, it might decide to do a full scan of t3 rather than using i_c31 (that is non-covering).
select *
from t1, t2, t3
where c11 = c21
and c12 < c31
and c22 = 0
and c32 = 100
(g_join
(i_scan i_c22 t2)
(i_scan i_c11 t1)
(t_scan t3)
But if the join is such that the assumption is proven wrong, the optimizer must be instructed to use i_c31 instead. In such a case, specifying only a partial AP is both an economic and a more flexible solution. One need not be concerned by all details of the full AP for that query. Also, as data in the other tables of that query evolves, the optimal QEP could change. And, as will be seen later, one of the shortcomings of the AP is its static nature. It is possible, within the current syntax, to express just one partial plan item. In this example, this would be: (i.sub.--scan i _c31 t3) However, it might be needed to express several plan fragments. For instance, if the cache is large enough, the optimizer might decide to do a full scan of the two inner tables of the join. If one wants to leave the optimizer the choice of the join order, but forbid table scans, one needs to be able to give it three hints:
(i_scan t1)
(i_scan t2)
(i_scan t3)
As a SQL query has a single associated AP, one needs a means to pack these three hints together. The hints operator allows this:
(hints
(i_scan t1)
(i_scan t2)
(i_scan t3)
)
Note that the hints AP operator is not a relational algebra operator. Its role is purely syntactic in the AP language, except for the special meaning it has with complex queries (described later). There are no limitations on what may be given as a hint. Partial join orders may be mixedwith partial access methods. Take:
(hints
(g_join
(scan t2)
(scan t1)
)
(i_scan t3)
)
where the optimizer is instructed to put t1 inner to t2 in the join order and to use an index on t3, but it is free to fill the rest of the QEP. However, this flexibility brings the shortcoming of being able to describe inconsistent plans:
(hints
(g_join
(scan t2)
(scan t1)
)
(g_join
(scan t1)
(scan t2)
)
)
Such plans are as illegal as the one above that required the inner table of an outer join to be on the outer position of the join, an exception will be raised and the compilation will be aborted. Other inconsistent hints will not raise an exception, but will have an undefined behavior in the initial embodiment of Ariadne:
(hints
(t_scan t3)
(i_scan t3)
)
When ASE generates and captures APs (as will be described later), it will never generate hints or partial plans. It will always generate full plans. (e) Subquery Attachment Subqueries are resolved in three ways in ASE: materialization, when they are non-correlated Part or all of the subquery is executed as an elementary join before the main query, and its results are stored in a CONSTANT node. flattening, when a correlated subquery is connected, through a semijoin, to the main query The semijoin is implemented either as an existence join, when the subquery table is inner to its correlated table of the main query, or as a tuple filtered inner join when it is outer. nesting This is the SQL92 semantics of a subquery. Whenever materialization and flattening are impossible, the subquery will be executed nested in the main query, once for each outer query row. Subquery materialization will be treated below, with the complex queries. A flattened subquery is not visible anymore at the AP level, except for naming its tables, as will be seen later. This section will focus on nested subqueries. Nested subqueries are explicitly described in the AP language, both to give their position and their own part of the QEP. The nested operator is introduced to describe items relevant to the optimizer that are inserted at a specific point in the join tree, i.e., nested over a specific derived table. The initial embodiment of Ariadne describes a single type of nested item, the nested subquery. The subq operator is introduced to describe a subquery. For example, the following SQL statement contains a correlated expression subquery, and its QEP will contain a nested subquery:
select *
from t1, t2
where c11 = c21
and c21 > 100
and c12 = (select c31 from t3 where c32 = t1.c11)
Its AP is:
( g_join
( nested
( i_scan 2 t1 )
( subq 1
( t_scan ( table t3 ( in ( subq 1 ) ) ) )
)
)
( i_scan 2 t2 )
)
Subqueries are named in the AP language with numbers, representing their syntactic order in the main query. In ASE parlance, this is the subquery number recorded in VRAGEs, SUBQNODEs, or the like. However, the AP subquery name is a well defined number, given by a statement's text and conceptually independent of the ASE implementation. Deep subquery nesting is not described by the subquery names. Rather, the subquery name is the numbering of the subqueries in a statement, in the order of their leading opened parenthesis "(". In both examples below, the subquery containing t1 is named "1" and the subquery containing t2 is named "2":
select
(select c11 from t1 where c12 = t3.c32),
c31
from t3
where c32 > (select c22 from t2 where c21 = t3.c31)
( nested
( nested
( t_scan t3 )
( subq 1
( t_scan ( table t1 ( in_subq 1 ) ) )
)
)
( subq 2
( t_scan ( table t2 ( in_subq 2 ) ) )
)
)
Both the subquery 1 and 2 are nested over the scan of t3.
select *
from t3
where c32 > (select c11 from t1
where c12 = (select c22 from t2 where c21 = t3.c31))
( nested
( t_scan t3 )
( subq 1
( nested
( t_scan ( table t1 ( in_subq 1 ) ) )
( subq 2
( t_scan ( table t2 ( in_subq 2 ) ) )
)
)
)
)
The subquery 2 is nested over t1's scan done in subquery 1, itself nested over the scan of t3 of the main query. Note that the syntax of nested operator, that has the derived table as the first operand and the nested item, i.e., the subquery, as the second operand, allows an easy vertical reading of the join order and subquery placement:
select *
from t1, t2, t3
where c12 = 0
and c11 = c21
and c22 = c32
and 0 < (select c21 from t2 where c22 = t1.c11)
( g_join
( nested
( i_scan 3 t1 )
( subq 1
( t_scan ( table t2 ( in_subq 1 ) ) )
)
)
( i_scan 2 t2 )
( i_scan 3 t3 )
)
At a glance, the join order is t1-t2-t3, with the subquery attached over t1.
select *
from t1, t2, t3
where c12 = 0
and c11 = c21
and c22 = c32
and 0 < (select c31 from t3 where c31 = t1_c11
and c32 = t2_c22)
( g_join
( nested
( g_join
( i_scan 3 t1 )
( i_scan 2 t2 )
)
( subq 1
( t_scan ( table t3 ( in_subq 1 ) ) )
)
)
( i_scan 3 t3 )
)
The join order is the same, but this time the subquery is attached over the t1-t2 join. (f) Name Conflicts To describe a QEP, an AP needs to connect the SQL query's stored tables with relational operators. To do that, it must be able to name them in an non-ambiguous way, such that a stored table named in then AP can be linked to its occurrence in the SQL query, hence in the query tree. Table names are the first choice for base tables. Indeed, a table name, maybe qualified by the database and owner name fully identify a table. However, a same table may occur several times in the same query:
select * from t1 a, t1 b
This case is solved by the SQL language by introducing correlation names, a and b in the example above. The most natural solution for the AP language is to use them too, whenever available. This is done by introducing the table operator, that is used whenever a base table needs to be named in an AP with more than its (potentially database and owner qualified) bare name. The AP of the query above is:
( g_join
( t_scan ( table ( a t1 ) ) )
( t_scan ( table ( b t1 ) ) )
)
Still, there are cases when correlation names are not mandatory in SQL, but the AP describing the QEP is ambiguous: merged views flattened subqueries In both cases, occurrences of the same base table are present in an elementary join without requiring correlation names at the SQL level. A subquery example:
select *
from t1
where c11 in (select c12 from t1 where c11 > 100)
The in and subq AP operators are introduced to qualify the name of the table with its syntactical containment by the subquery:
( g_join
( t_scan t1 )
( i_scan 3 ( table t1 ( in ( subq 1 ) ) ) )
)
Like for the correlation case, the table notation is used. As for the views:
create view v1
as
select * from t1 where c12 > 100
Select t1.c11 from t1, v1
where t1.c12 = v1.c11
Likewise, the in and view AP operators qualify the name of the table with its syntactical containment by the view:
( g_join
( t_scan t1 )
( i_scan 2 ( table t1 ( in ( view v1 ) ) ) )
)
In general, a table may be deeply nested, for instance in a view of a subquery of a view of a view of a view of a subquery of the main query. The table name will be accordingly (and recursively) qualified with the whole chain of syntactic containment. To give a (more complex) example:
create view v2
as
select *
from v1
where v1.c11 in (select c12 from v1 where c11 < 0)
select *
from t1, v1, v2
where t1.c11 = v1.c12
and v1.c11 = v2.c12
and t1.c12 in (select c11 from v2)
( g_join
( i_scan 3 t1 )
( i_scan 3 ( table t1 ( in ( view v1 ) ) )
( i_scan 3 ( table t1 ( in ( view v1 ) ( view v2 ) ) ) )
( i_scan 2 ( table t1 ( in ( view v1 ) ( view v2 ) ( subq 1 ) ) ) )
( i_scan 3 ( table t1 ( in ( view v1 ) ( subq 1 ) ( view v2 ) ) ) )
( i_scan 3 ( table t1 ( in ( view v1 ) ( subq i ) ( view v2 ) ( subq 1 ) )
) )
)
Unions are yet another case where several occurrences of the same base table occur, but in ASE they never occur in the same elementary join. As will be seen in the next section, one uses another technique to disambiguate them. (g) Complex Queries All the examples above used queries that had single elementary join QEPs. However, the SQL language has statements that certain query execution engines are not capable to execute as elementary joins. This applies to ASE too, that needs to break the processing of some types of queries in several steps, and store the intermediate results in work tables or CONSTANT nodes. It is not necessary apriori to do the same with a relational algebra. One has to introduce the store operator, that materializes a derived table in a work table. But one does not need to break a formula in a sequence of steps. An algebra formula describes how to compose relations with relational operators to obtain the desired result set, but gives no information on the order of touple at the time processing. To illustrate this, consider an AP that contains a store operator (with an optional system generated name):
(g_join
(scan t1)
(scan
(store Worktab1
(g_join
(scan t2)
(scan t3)
)
)
)
)
This AP is perfectly compatible with both a Volcano style consumer driven dataflow engine and with a producer driven ASE engine. The difference is that while the Volcano engine will materialize late the derived table resulting form t2 and t3's join by storing it in a work table, when the top join node will ask for its first row as an inner operand, the ASE engine will materialize it early, in a first step, and only afterwards, in a second step will use it in the top join. Still, it is just a matter of convention to apply the same AP to both QEPs. One could regard the following AP, that uses the plan operator to group together several chunks of a QEP description, as a convenient, syntactic variant of the previous monolithic AP:
(plan
(store Worktab1
(g_join
(scan t2)
(scan t3)
)
)
(g_join
(scan t1)
(scan (work_t Worktab1))
)
)
When using this syntax, it is mandatory to give a name to the work table. One could consider the stand-alone store operator as a macro definition introducing the worktable's name, and the work_t operator as a macro invocation of this symbol. A Volcano engine needs to add no semantic meaning to it. (Note that the work_t operator, that names the work table, also avoids any namespace conflicts between the sometimes arbitrary system generated worktable names and the base table names.) Ariadne uses this notation, and is perfectly compatible with its purely syntactic interpretation. DBMS systems that have a dataflow query engine will be able to use it as such. However, in Ariadne's initial embodiment there is an immediate advantage in requiring such a notation whenever the QEP has several steps: one can associate AP chunks with their corresponding elementary joins. More precisely, the requirement is related not to the QEP, but to the preprocessed query tree, as this is the optimizer's input against which the AP has to be matched. The AP should have enclosed in a plan operator exactly the same number of items, and in the same order, as the CMD nodes chain in the preprocessed query tree. This way an AP to query tree match is done, and the set of tables in each AP chunk is required to be included in the set of tables of its corresponding elementary join, i.e., it is illegal to describe with an AP tables that cannot be forced into a future QEP step. For a full AP the two sets are equal, i.e., each AP chunk mentions all the tables in its corresponding CMD node, and nothing but them. This requirement makes the match possible, whereas the monolithic AP cannot guarantee that some preestablished tree traversal gives the store operators within it in the same order as the CMD nodes chain, as the layout of the AP tree contains the optimization decisions, like the join order. To illustrate this, let us anticipate on the materialized views, and suppose ASE created the right index on the work table for the join in the main query (this is not the case):
create view v4
as
select distinct *
from t1, t2
where c12 = c21
create view v5
as
select distinct *
from t2, t3
where c22 = c31
Consider a first query that joins v4 work table outer to v5's one.
select * from v4, v5
where v4.c11 = 0
and v4.c22 = v5.c21
( plan
( store Worktab1
( g_join
( 1_scan 2 ( table t1 ( in_view v4 ) ) )
( i_scan 2 ( table t2 ( in_view v4 ) ) )
)
)
( store Worktab2
( g_join
( t_scan ( table t2 ( in_view v5 ) ) )
( i_scan 2 ( table t3 ( in_view v5 ) ) )
)
)
( g_join
( t_scan ( work_t Worktab1 ) )
( i_scan ( work_t Worktab2 ) )
)
)
Then, a second one whose QEP has the opposite join order.
select * from v4, v5
where v5.c32 = 0
and v4.c22 = v5.c21
( plan
( store Worktab1
( g-join
( t_scan ( table t1 ( in_view v4 ) ) )
( i_scan 2 ( table t2 ( in_view v4 ) ) )
)
)
( store Worktab2
( g_join
( i_scan 2( table t2 ( in_view v5 ) ) )
( i_scan 2 ( table t3 ( in_view v5 ) ) )
)
)
( g_join
( t_scan ( work_t Worktab2 ) )
( i_scan ( work_t Worktab1 ) )
)
)
Note that both QEPs create the work tables in the same order, first for v4, then for v5, actually in the main query's FROM clause order. However, the last step joins the two work tables in different orders for each query. If a monolithic AP was used, no preestablished tree traversal could give the store operators order that matches the CMD chain for both queries. The single exception to this high level QEP perfect match requirement is when a hints operator is the AP's top operator. Such a plan will be called a hints plan, and will be associated with each CMD node of the preprocessed query tree. The UNION implementation in ASE brings an extra complication for the high level QEP structure, that will be presented later. (h) Materialized Views The discussion above largely illustrated materialized views. Let us however give a simpler example:
create view v3
as
select distinct *
from t3
select *
from t1, v3
where c11 = c31
( plan
( store Worktab1
( t_scan ( table t3 ( in_view v3 ) ) )
)
( g_join
( t_scan t1 )
( t_scan ( work_t Worktab1 ) )
)
)
A first step materializes the view v3 in a work table, then the second joins it with the main query table t1. (i) Aggregates For scalar aggregates, consider the following:
select max(c11) from t1
( plan
( t_scan t1 )
( )
)
The first step computes the scalar aggregate in a CONSTANT node. The second step is empty, as it only returns this CONSTANT, there is nothing to optimize. Other cases of empty AP parts are given below. For vector aggregates, consider the following:
select max(c11)
from t1
group by c12
( plan
( store Worktab1
( t_scan t1 )
)
( t_scan ( work_t Worktab1 ) )
)
The first step processes the aggregate in a work table, the second scans it. For nested aggregates (TSQL extension), consider the following:
select max(count(*))
from t1
group by c11
( plan
( store Worktab1
( i_scan 2 t1 )
)
( t_scan ( work_t Worktab1 ) )
( )
)
The first step processes the vector aggregate into a work table, the second scans it to process the nested scalar one into a CONSTANT node, the third step returns this CONSTANT. For extended columns aggregates (TSQL extension), consider the following
select max(c11), c11
from t1
group by c12
( plan
( store Worktab1
( t_scan t1 )
)
( g_join
( t_scan t1 )
( i_scan 1 ( work_t Worktab1 ) )
)
)
The first step processes the vector aggregate, the second one joins it back to the main query table to process the extended columns. For aggregates in merged views, consider the following:
create view v6
as
select max(c11) as c61, c12 as c62
from t1
group by c12
select * from t2, v6
where c21 = 0
and c22 > c61
( plan
( store Worktab1
( t_scan ( table t1 ( in_view v6 ) ) )
)
( g_join
( i_scan 2 t2 )
( t_scan ( work_t Worktab1 ) )
)
)
The first step processes the vector aggregate, the second joins it to the main query table. For aggregates in materialized views, consider the following:
create view v7
as
select distinct max(c11) as c71, c12 as c72
from t1
group by c12
select * from t2, v7
where c21 = 0
and c22 > c71
( plan
( store Worktab1
( t_scan ( table t1 ( in_view v7 ) ) )
)
( store Worktab2
( t_scan ( work_t Worktab1 ) )
)
( g_join
( i_scan 2 t2 )
( t_scan ( work_t Worktab2 ) )
)
)
The first step processes the vector aggregate in a first work table, the second step scans it in a second work table to process the materialized view, the third step joins this second work table in the main query. Note en passant that ASE is not smart enough to notice that v7's result set is guaranteed to be distinct, so v7 could be merged. (j) Materialized Subqueries Flattened and nested subqueries were already exposed in previous sections. A non-correlated subquery will be completely materialized:
select *
from t1
where c11 = (select count(*) from t2)
( plan
( i_scan 3 ( table t2 ( in_subq 1 ) ) )
( i_scan 2 t1 )
)
The first step executes the scalar aggregate non-correlated subquery. The second one uses the result in scanning t1. Non-correlated parts of a correlated subquery could be materialized, while the correlated remaining part is flattened or nested:
select *
from t1
where c11 in (select max(c21)
from t2
group by c22)
( plan
( store Worktab1
( t_scan ( table t2 ( in_subq 1 ) ) )
)
( g_join
( t_scan t1 )
( t_scan ( work_t Worktab1 ) )
)
)
The first step executes the vector aggregate processing of the subquery, that is non-correlated, and stores it into a work table. The second semijoins it to t1. (k) Reformatting Reformatting is the optimizer decided materialization of a derived table, with the restriction that it cannot be the result of a join. Assume t2 has no index at all and is very
select *
from t1, t2
where c11 > 0
and c12 = c21
and c22 = 0
( g_join
(t_scan t1
(scan
(store Worktab1
(t_scan t2)
)
)
)
Worktab1 is an optimizer generated work table, that is not visible as a CMD node in the optimizer's input, the preprocessed query tree. This is the single case when the store operator is not the operand of a plan operator. Indeed, the exact match requirement between the plan operands and the CMD nodes sequence requires the store operator to be the operand of a scan operator. This is very opportune, as such an AP pattern may unambiguously identify the ASE reformatting. (l) OR Strategy The OR strategy was purposely left out of the initial embodiment of Ariadne. In a relational algebra, the OR strategy would be naturally described by the scan_rid and rid_join operators:
(rid_join
(union
(scan_rid i_i t1)
(scan_rid i_2 t1)
. . .
(scan_rid i_n t1)
)
t1
)
There were no cycles for the extra work to generate and apply this syntax. Note also the difficulty raised by the different meaning the union operator has at the ASE high level QEP structure. (m) Unions The ASE implementation of UNION brings an extra complication of the high level structure of the AP language. To match the UNION/CMD structure o | ||||||