3.    Fundamental Concepts in Cascades

A query tree is a tree structure that corresponds to a query by having zero input operators (e.g. GET) as leaf nodes of the tree (representing the access of a stored relation) and arity one or more operators as internal nodes. An evaluation of the query tree consists of evaluating an internal node operation whenever its operands are available and the replacing that internal node by the table that results from evaluating the operation. The evaluation terminates when the root node is evaluated and replaced by the table that is the result of the query.

Figure 3.2a: Query Tree for Query 3.2

SELECT	  *
FROM 	  CUSTOMER AS C,  ORDER AS O,  LINEITEM AS L 
WHERE 	  C.C_CUSTKEY =  O.O_CUSTKEY	     AND 
	  O.O_ORDERKEY   =  L.L_ORDERKEY;

Figure 3.2b: Equivalent Query Tree

Groups and Expressions
           The group is the fundamental data structure in Cascades. Groups are the Cascades generalization of the relational model's concept of an intermediate table.

           In the typical processing of a query, many partial results are produced before the final result is produced. A partial result is a result of some of the operations being performed, with more needed in order to produce the final result. In Cascades, these partial⁷ results are called groups. In the pure relational model, the groups would always correspond to tables -- either an initial table (corresponding to a relation just read off of disk by the GET operator), or an intermediate or final table -- a logical expression of other groups. This is because, in the pure relational model, every logical operator produces a table.

           Each group in Cascades will contain one or more logical expressions which express (compute) the group's partial result. A logical expression consists of a logical operator and a fixed number (e.g. 0, 1 or 2, in Model D) of inputs. In Cascades the inputs to expressions are groups. The number of inputs to an expression is equal to its operator's arity.

           Note that the Cascades expression datatype is different from a general relational expression. Cascades expressions always contain exactly one operator. A general relational expression, for example,

_OOK ( _{CM="Building"} CUSTOMER || ORDER)

contains an arbitrary number of operators. Cascades expressions specify only the last operation to be performed, without specifying how the inputs (groups) of the expression are to be computed.

           More details can now be given about how Cascades defines and represents groups. In Cascades, a group is a set of logically equivalent expressions. As with query trees, all logically equivalent expressions return exactly the same logical result for any population of the database. Note that Cascades groups contain logically equivalent logical expressions and logically equivalent physical expressions -- which we discuss shortly. Because groups contain logically equivalent expressions, in the literature, groups are commonly called equivalence classes or just classes [Pellenkoft 96]. For now, we focus on groups that represent intermediate tables -- i.e. the pure relational case.

           Consider a group that contains several equivalent expressions. Specifically, consider the group representing the table resulting from the Cartesian product (written as X ) of the Customer and Lineitem relations. In Model D, Cartesian product is represented by the EQJOIN logical operator with no equality conditions. Because of the commutativity of join, the logical expression, Lineitem X Customer, is logically equivalent -- that is, results in the same table as, the logical expression Customer X Lineitem, and hence would be included in the set of logically equivalent expressions for this group. So the group would contain the following expressions:

	operator	inputs:		
	EQJOIN		0	3	(expression 1)
	EQJOIN		3	0	(expression 2)

Note that the inputs 0 and 3 above are designations (group numbers) for the groups representing the intermediate tables generated by the GET logical operator for the Customer and Lineitem stored relations, respectively. So group 0 would contain the the logical expression: GET 'CUSTOMER as C'.

           In addition to a set of logically equivalent expressions, each group also has logical properties. Certain properties hold for an intermediate result, regardless of exactly how (physically) the result is computed. If a group represents a table, all of the logical properties describing the table can be defined for the group. These include the cardinality (number of tuples), the schema, and other properties. The logical properties apply to (describe) all expressions in the group. Finally, note that the Cascades representation of groups and its representation of expressions also contain various state-of-the-optimization-process information.


The Memo
           In the process of optimization, Cascades will keep track of many of the intermediate tables that could be used in computing the final result table. Each of these corresponds to a group in the set of groups Cascades calls the memo structure. In Cascades, the memo structure⁸ is designed to represent⁹ all logical query trees and physical plans in the search space for a given initial query.

           The memo structure is a set of groups, with one group designated as the final (or top) group -- the group which corresponds to the table resulting from the evaluation of the initial query.

           To understand the memo data structure, consider how the initial query is represented. Each node of the initial query tree is a group. Figure 3.3a shows the memo structure after the query tree shown in figure 3.2b has been copied in.

Figure 3.3a: Initial Memo After Copy In of Query 3.2

           Figure 3.3b shows the fully expanded memo structure (of logical expressions only) for query 3.2.¹⁰ It represents the memo resulting from the application of associative and commutative join transformation rules to memo 3.3a.

Figure 3.3b: Logical Memo for Query 3.2: Join of 3 Tables

           Figures 3.3a and 3.3b are graphical representations¹¹ of the Cascades memo structure. Each box represents a group, with the arbitrary group number shown in the upper left hand corner. (The group numbers are assigned by the optimizer in order of group creation, with certain groups numbers missing due to merging with another group.) Across from the group number is a string of capital letters, representing the names of stored relations. This string is a shorthand (used in these diagrams only) for the schema logical property of the group. In this shorthand, the schema for Group 4 is the union of all the attributes from the three tables Customer, Order and Lineitem. Below the horizontal line in each box is a list of the equivalent (so far, just logical) expressions for the group.

Figure 3.3c: Key for Memo Structure: A Single Group

           Figure 3.3c summarizes the above paragraph: it annotates a single group diagram. Note that the parameters shown in the notation for equivalent expressions are parameters of the operator of the expression. In Cascades the expression datatype itself does not have parameters.

           The top group, group 4, is the final group of the query -- it corresponds to the final result -- the join of the three relations, as shown in figure 3.2a. Group 4 has 6 logically equivalent logical expressions, each an EQJOIN of two input groups (tables). The numbers following the name of the operator (EQJOIN) are the input group numbers. Group 7 contains the two equivalent logical expressions (expressions 1 and 2). Because they represent Cartesian products, the two expressions in this group have null join predicate parameters.

           Groups 3, 1 and 0 represent tables corresponding to the three stored relations involved in this query. The GET operator has no inputs -- the names in quotes are the stored relation name and the range variable name parameters. The range variable name (for example, "O" for the stored relation "Order") is then used in referring to attributes of tables which (transitively) include group 1 as input.

           For example, group 4 contains the logical expression

EQJOIN	6  0	'O.OCK = C.CCK'

The "O.OCK" in the equality conditions parameter of the EQJOIN operator, refers to an attribute in the schema for the table corresponding to group 6, as a result of the expression

GET		'Order as O'

           The memo structure represents the logical (and, next to be discussed, physical) search space for the given initial query. To put it another way, every query tree that will be considered by the optimizer can be found by examining the final memo for the particular query.¹²

           For query 3.2 there are 12 (logical) query trees in the search space, which is defined by the application of commutative and associative transformation rules for EQJOIN. The 12 query trees can be seen by examining each of the six logical expressions in the final group (group 4). Each of this group's six logical expressions references a group with 2 logical expressions and a group with 1 logical expression. So we have a choice of 6 logical expressions in group 4, each of which have a choice of 2 logical expressions in one of its inputs, resulting in 12 possible query trees for the initial query.

           Note that the query trees are not directly represented in the memo structure -- they are constructed by traversing the memo structure from the final group down, and, for each group, chosing an expression, then repeating this process for each input group of the chosen expression. The query tree shown in figure 3.2a is obtained from the memo structure shown in figure 3.3 by choosing the third logical expression in group 4, which uses groups 0 and 6 as inputs, and the second logical expression in group 6. The query tree shown in figure 3.2b is obtained from the memo structure shown in figure 3.3 by choosing the sixth logical expression in group 4, which uses groups 2 and 3 as inputs, and the second logical expression in group 2. I say, informally, that the memo structure includes a query tree (which is logically equivalent to the initial query) if the query tree can be constructed from the memo in the manner just described.

Figure 3.4: Complexity of Join of n Relations

           To get an idea of the size of the search space involved in join queries,¹³ figure 3.4 lists number of groups, the number of (logical) expressions and the number of (logical) query trees in the final (logical) memo for a join of n relations. The second row in the table (join of 3 relations) corresponds to the logical memo structure of figure 3.3, which has 7 groups, 15 logical expressions and includes 12 query trees.

           As can be seen from this table, the size of the search space increases dramatically as the number of relations to be joined increases.

           Again, each group represents an intermediate table that could be computed in the process of evaluating the join query. Note particularly the dramatic rise in the number of query trees, as the number of relations to be joined increases.

           Table 3.4 motivates some of the decisions in how Cascades represents the memo structure. The very large number of query trees is a primary motivation for not storing each query tree -- a large search space can be considered without explicitly representing every query tree in the model's search space. The smaller, but still considerably large, number of expressions is motivation for not storing a lot of information in expressions. Specifically, expressions have neither logical nor (defined later) physical properties.¹⁴ The (relatively) small number of groups allows us to store a lot of information (e.g. logical properties) with each group.

           The search space of most concern is the physical search space. To explore that, we look at physical models under the Cascades Framework.


The Physical Model
           The physical model relates to the query execution environment. It is based on the details of the Query Execution Engine -- the software that executes the overall algorithm, produced by the optimizer, using the stored data of a database. The basic element of the physical model is the physical operator. Physical operators represent specific algorithms that implement particular database operations. In some cases they correspond one to one with a logical operator -- but this is not typical.

           Like logical operators, each physical operator takes a fixed number (0 or more) of inputs and can have parameters. Taken together the physical operators form a physical algebra.

           Analogous to logical expressions, a physical expression consists of a physical operator and a fixed number of inputs equal to the operator's arity. An example of a physical expression is:

	physical operator:	inputs:		parameters:
	MERGE_JOIN		1	0	'O.OCK = C.CCK'

where 1 and 0 are group numbers representing tables (i.e. groups) (whose schema must contain attributes C.CCK and O.OCK, respectively).

Figure 3.5: Memo Structure for Query 3.2: Join of 3 Relations

           Figure 3.5 shows the memo structure from figure 3.3, including the physical expressions. In this simple case, most logical expressions have a single corresponding physical expression. In group 4, each logical expression with the logical operator EQJOIN has a corresponding physical expression with the physical operator HASH_JOIN. In general, this simple correspondence will not hold. For example, each logical expression could result in multiple physical expressions, each corresponding to a different algorithm for implementing the logical operation. Groups 0, 1 and 2 illustrate this.

           A query tree comprised entirely of nodes with physical operators is called a plan. It is a complete description of how the query is to be physically executed. It tells the Query Execution Engine which algorithms to use, which access paths to use and in what order to apply (that is, perform the algorithms represented by) the different physical operators. If the physical query tree computes a partial result, it is called a subplan because it is part of at least one plan for producing the final result.

           Plans differ from physical expressions in that a plan is a complete tree (with each node containing a physical operator), while a physical expression contains a single physical operator and a number of inputs (groups). Plans differ from logical query trees in that plans have costs (discussed below).

           To evaluate query 3.2, different join algorithms (e.g. a MERGE_JOIN, if the two input tables were sorted appropriately, LOOPS_JOIN or HASH_JOIN, etc.) could be used. Also, different access paths (using an index of some kind on certain relations, a direct access of the entire table for others) could be utilized. In addition, we could change the order in which the joins of the three tables are performed.

Figure 3.6: A Plan for Query 3.2

           For example, figure 3.6 shows a particular plan for the join of the three tables. It specifies that CUSTOMER and ORDER be joined first using MERGE_JOIN and that the result be joined with LINEITEM using HASH_JOIN. This plan is obtained from the memo of figure 3.5 by taking the last expression from each of the groups 4, 3, 2, 1 and 0.

           Because a plan describes a sequence of specific algorithms to be applied to stored relations, many more detailed properties about the intermediate results can be determined. These are called physical properties. The most important physical property is cost.

           Cost is some measure of the resources required to execute the query and/or the time the user will wait before the results of the query are available. Note that plans have physical properties, but expressions (either logical or physical) and groups do not have physical properties -- and therefore do not have costs. This is because only a plan corresponds to a fully specified algorithm that can be "costed".

           The cost of a plan will depend on several factors. First, it will depend on the order that the operations are performed and the order of the operands (inputs) to a particular operator. It will also depend on the access paths and particular algorithms (physical operators) used to perform the operations.




Item Operators
           In addition to logical and physical operators, the Cascades Framework has item operators. Item operators are distinguished from bulk operators (the logical and physical operators) in that they operate on a fixed number (usually one) of tuples, while bulk operators operate on an arbitrary number of tuples. In the relational context, item operators are frequently functions of a single tuple (as opposed to functions of an entire relation). Expressions in which the operator is an item operator are called item expressions.

           In Model D, item operators are used primarily as predicates or as the building blocks of predicates. Predicates are functions that return a boolean. Item operators are used, for example, as predicates for the SELECT logical operator.

           More generally, item operators can be thought of as functions either of a fixed number of tuples, or of a fixed number of (atomic) values. They can return a boolean, an attribute of a relation (scaler value of one of the base types (int, double, string, etc)) or, in one case, CONST_SET_OP, a set of scalers.

           Examples of item operators are attribute operators (which retrieve a value from a single tuple), comparison operators (which compare two values), boolean operators (functions of two boolean values) and constant operators (functions with no arguments).

           In the text of this section up until now, groups have represented intermediate tables. One of the unique aspects of Cascades is that it treats the elements of predicates as groups. That is, groups can correspond to item expressions as well as logical expressions.

           Groups which contain (a set of equivalent) item expressions are called item groups, in contrast to bulk groups, which in Model D always correspond to intermediate tables (i.e. collections of tuples). Item groups represent functions. They can be the input to logical and physical expressions. For example, an expression containing the SELECT logical operator, arity 2, has a bulk group (collections of tuples) as one input, and an item group (a function, in this case a predicate that takes a single tuple and returns TRUE or FALSE) as the other input.

Figure 3.7: Query Tree With Select Operator and Predicate

           Figure 3.7 shows a SELECT operator and its predicate input (the right input). The SELECT and GET nodes contain logical operators. Every node in the subtree with root AND contains an item operator. The leaves labeled C.C_MKTSEGMENT and C.C_NAME are instances of a class of item operators called attribute operators. The leaf labeled "retail" is a constant string item operator and the leaf labeled {"Wal-Mart", "Target"} is a CONST_SET_OP item operator. Representing predicates as query trees of item operators allows a Cascades optimizer to apply rule-based transformations to predicates.

           As the GET logical operator forms the "bulk leaves" of query trees, attribute operators and constants form the "item leaves" of query trees -- i.e. they take no inputs. Since predicates ultimately are applied to tuples in a table (by a select operator), clearly the predicate tree must include only attributes that are listed in the schema of the input table to the select operator.

           Item operators are considered to be both logical and physical. In other words, they do not have separate logical and physical versions -- each particular item operator functions in both capacities. They are logical in that they can compute logical (item) properties. They are physical in that they can be part of a plan and thus can be used in computing physical properties, including costs.

Table 3.8: Types of Operators

           Table 3.8 shows the types of operators in terms of the type of properties they compute and whether (in Model D) they take item or bulk inputs. While item groups can be the input to (bulk) logical operators (e.g. SELECT), bulk groups cannot be the input to an item expression.


Rules
           The model's rule set can be thought of as defining the logical and physical search space of the optimizer. The memo is expanded to encompass the full logical and physical search space through the application of rules. The application of rules is a multistep process of finding a binding in the memo, evaluating a rule condition (if the rule has one) and (if the condition is satisfied) firing the rule -- putting new expressions in the memo. When the optimizer is done applying rules, the memo structure will have been expanded to the point that it conceptually represents the entire search space.¹⁵

           Cascades rules come in three types: transformation rules, implementation rules and enforcement rules. In simple terms, transformation rules expand the logical search space, implementation rules expand the physical search space and enforcement rules, which are similar to implementation rules, insert physical operators to supply inputs that satisfy certain physical properties.

           Rules always represent logical equivalence relationships [McKenna 93]. Recall that figure 3.2a and 3.2b are logically equivalent. This is because the relational join operator is associative. Hence a rule, in this case the left-associative transformation rule, could be used to transform a memo that included the query tree in figure 3.2a to a memo structure that now included the query tree in figure 3.2b.

           Rules are specified with an antecedent (before pattern), a consequent (resulting partial query tree) and a condition. The antecedent specifies the pattern of operators required for there to be a binding of the rule. The consequent describes the new expressions that will be inserted into the memo structure if the condition is satisfied.

           The condition is any requirement(s) (other than matching the before pattern) that must be satisfied before the rule is applied. Conditions usually pertain to the logical properties of the groups in the memo structure corresponding to the expressions matched and to the parameters of the operators of these expressions.

Figure 3.9: EQJOIN Left to Right Associativity Rule

           Figure 3.9 shows a picture of the left to right EQJOIN associativity rule. Both the antecedent and consequent are specified using a special form of query tree. On the left is the antecedent (before pattern) and on the right is the consequent.

           The before pattern contains two join operators. The rule application code of the optimizer will look for a sequence of joins in this pattern in the memo structure. Note that even though the EQJOIN parameters (i.e. the join predicate) are shown in the before pattern of figure 3.9, they are not considered in searching for this pattern in the memo. However, these parameters will be accessible in evaluating the condition and in creating the consequent.

           Notice also the leaf designations in the before pattern. These are like wildcard indicators -- they indicate that any group will match at this particular location in the pattern. The consequent will also usually contain leaves. The group matching a particular leaf in the antecedent will generally become a group at one of the leaf positions in the consequent.

           When part of the memo structure matches this pattern a binding is made -- to the particular expressions in the memo structure that match the pattern. The binding is used to evaluate the condition and to form the consequent. After the binding is made the condition (if any) is evaluated. If the condition is satisfied, or there is no condition, the rule is fired. Based on the binding and the consequent query tree, new expressions are created and inserted into the memo structure.

           In the memo of figure 3.3, consider the left associativity rule. This rule would have six bindings -- two each for the first, fourth and sixth expression in group 4. Let's look at the binding that consists of the first expression in group 4 (EQJOIN 7 1) and the first expression in group 7 (EQJOIN 0 3). Any binding of the left associativity rule will result in the firing of the rule, since the rule has no condition that must be satisfied. The firing of the rule would result in the generation of the third expression in group 4 (EQJOIN 0 6) and the first expression in group 6 (EQJOIN 3 1). The expression corresponding to the the top node of the consequent will always be inserted in the group which contains the expression corresponding to the top node of the antecedent.

           Note that firing the associative rule on the six bindings results in expressions which are already in the memo shown in figure 3.3 (because it is already fully logically expanded). In general, it is possible for rules to generate expressions which are already in the memo. Efforts to design rule sets to avoid this are discussed in section 5, Related Work.

           Now consider an implementation rule that says that a physical operator called INDEXED_FILTER implements the logical operator SELECT. This rule would likely include the condition that an index which matches the select predicate must exist in the stored database. This implementation rule will fire only if this condition is met. This condition would help to assure that the optimizer only produces legal, well-formed plans. After the consequent is formed, the corresponding expressions are inserted into the memo and, in effect, the represented search space (of all possible plans) is increased.

           The logical search space of an initial query is all possible logical query trees that could be generated by the application of transformation rules to the initial query. The physical search space of a query is all possible plans that could be generated by the application of implementation and enforcement rules to the fully expanded logical search space.

           Based on this understanding of rule application, the stages of Cascades optimization can be looked at in a little more detail.


Stages of Optimization
           Cascades optimizes a query in three major steps: copy-in (to the memo), expanding the memo and copy-out (of the memo).

           As shown in figure 2.1, after the original SQL query is parsed into a logical algebra query tree this initial query tree is copied in¹⁶ to the memo data structure. At this point the memo has a set of groups, each one corresponding to a node of the initial query tree. Each group will contain a single logical (or item) expression which contains the operator from the corresponding node in the initial query tree. This is figure 3.3a (the initial memo for the query in figure 3.2b).

           Then the optimization process proceeds by performing various optimization tasks such as applying rules, optimizing expressions and optimizing groups. The order in which these tasks are performed is controlled by the search engine. The optimization tasks are performed primarily by applying rules (which we described above) and finding the best plan for each group,¹⁷ a procedure called find best, which we describe below. When rules are applied, new expressions are created and inserted into the memo structure and new groups are formed -- the memo structure is expanded.

           After the optimizer has finished expanding the memo, the best plan is extracted from (copied out of) the memo structure. This plan is the optimizer output and, like the optimizer input, is represented as a tree. The best plan is selected by applying the procedure find best to the final group. Among all of the plans represented in the final group, this should be the plan of lowest cost.


Find Best
           For each intermediate table (i.e. group), there will be, in general, many possible plans capable of producing it. Find best is the procedure for finding the optimal plan for any given group.¹⁸

           Ignoring contexts and physical properties for a second, find best works by selecting a physical expression from a specified group, and then recursively selecting a physical expression for each input (group) of the selected expression. When an expression is chosen, it is copied into a query tree that is built¹⁹ as the memo is traversed. Eventually find best finds physical expressions with no input groups, and the recursive descent ends. Since physical expressions always contain physical operators, the resulting query tree contains only physical operators -- i.e. its a plan.

           When more than one physical expression is available in a group, the optimizer will try to choose the one with the least cost. In finding the best plan in a group, we may specify that the plan satisfy a certain context -- i.e. a certain combination of physical properties. For example, a context may require that the plan produce a table sorted on a particular attribute and/or that the plan have a cost below a certain threshold. It is possible that no plan satisfying the context can be found. Find best will either produce the least cost plan included in this group which satisfies the context, or it will indicate failure.

           Because find best is actually called throughout the optimization process, and the results of its search are stored in the memo structure, much of the work in finding a best plan will already be done for calls to find best in the later stages of optimization.


Complexity of Optimization
           While the complexity of the algorithms corresponding to the physical operators is generally linear, n log (n) or at worst n² (in n, the number of tuples), the optimization algorithms can be much more complex. For example, one aspect of query optimization is determining the optimal order in which to do the joins. This problem has been shown in [Ibaraki 84] to be NP-hard in the number of relations involved in the joins. Since the search space is represented by the number of query trees, the last column in figure 3.4 illustrates this complexity.²⁰

           In the execution of a TPC-D query, n might be the number of LINEITEM tuples, 6,000,000. To sort these tuples would take on the order of n log(n) comparisons. (Roughly, around a billion comparisons.) In the optimization of a TPC-D query, n might be the number of relations for which a join order must be chosen. Referring back to figure 3.4, the number of expressions needed to represent the logical search space is 3ⁿ - (2ⁿ⁺¹ - 1) + n. In TPC-D query 8, there are seven relations, so n=7, and 1939 expressions are needed. (The actual size of the logical search space, i.e. the number of logical query trees, is 665280.)

---

1. Volcano, the predecessor of Cascades, and Exodus, the predecessor of Volcano, are discussed in Section 5.
2. Model D doesn't actually implement all of the relational algebra operators -- the model has no union, difference, intersection or division. These were not needed to represent the TPC-D queries.
3. We say that an operator takes an input. Strictly speaking, the Cascades operator datatype doesn't have inputs, rather, expressions (defined later), which contain operators, have inputs. This distinction between the operator and expression datatypes, somewhat unique to Cascades, provides a cleaner way to transform expressions, where the inputs of one expression may be "transferred" to another expression. Each operator has an arity -- this arity will determine the number of inputs expected in an expression containing this operator.
4. In Model D, stored relations must be relations (-- no duplicates allowed), but tables, to support the SQL extensions to the relational model, are allowed to have duplicates.
5. The same is true of physical operators: the names of stored relations are parameters to the physical operators FILESCAN and INDEXED_FILTER. The output of each of these (and of all logical and physical operators) is a table. The specifics of the internal representation of tables (i.e. whether they are stored on disk, in memory or are just streams of tuples, etc.) are in the domain of the physical model and are discussed in section 6.
6. The initial SQL query is parsed into the initial query tree -- sometimes called the parse tree. In the rest of the thesis, the term initial query refers to the initial query tree.
7. The final result (the table produced by evaluating the initial query) is also a group (called the final group).
8. We use the term "memo structure" and "memo" interchangeably.
9. The Cascades memo structure does not explicitly represent (i.e. store in memory) the query trees (for reasons discussed below) but rather stores expressions. Because Cascades expressions use groups as inputs, and each group, in general, contains several logical expressions, each logical expression actually represents many distinct query trees.
10. By figure 3.2 we mean either figure 3.2a or figure 3.2b, both of which represent query 3.2. The query trees in 3.2a and 3.2b are logically equivalent -- they represent the same logical query.
11. Figures 3.3a, 3.3b and 3.5 are representations of the memo structure based on the output of COVE, the Cascades Optimizer Visualization Engine [Wu 96]. Note that figure 3.3b does not represent an actual state of the memo (at a particular point) during an actual optimization. Under the current Cascades search strategy and Model D, physical expressions would be generated long before all of the logical expressions were generated. Figure 3.5 could represent the memo near the end of an optimization.
12. Actually this is an over-simplification: it may only be true if the search engine doesn't do any pruning along the way. For example, the memo structure may not include query subtrees that the optimizer has determined cannot possibly be part of the optimal plan.
13. The numbers shown in figure 3.4 are for bushy joins where Cartesian products are allowed -- that is they are for the complete (largest possible) join order search space. This is the logical search space in that only the logical join operator is considered.
14. In Cascades, expressions have the logical properties of the group they are in. Expressions cannot have physical properties because only plans (physical query trees) have physical properties.
15. Due to algorithmic pruning, certain parts of the search space might not end up actually being represented in the memo structure. (Heuristic pruning, in contrast, will effectively reduce the search space considered by the optimizer.)
16. Note that this procedure involves converting the nodes of the query tree into expressions in the memo structure.
17. In fact, under either algorithmic or heuristic pruning, the optimizer may not need to optimize every group in the memo.
18. Find best is called with a context which must be satisfied as well as the group from which to find the best plan. This forms part of the the enforcement mechanism to assure that plans are well-formed -- that the inputs to a merge join are sorted appropriately, for example.
19. In fact, only the very last call to find best (on the final group) will output a plan. For calls to find best during the optimization, find best will report various optimization information such as whether a legal plan satisfying the input context can be found and, if so, what physical expression corresponds to the cheapest plan and what the cheapest cost is.
20. The number of query trees in figure 3.4 represent the search space complexity of the join order optimization problem -- that is the size of the search space. The actual running time of the optimizer and the memory required is closer to the number of expressions or the number of groups, since only a tiny fraction of all possible query trees are generated and none (except the initial query tree and the final plan) are stored. This is true for both Cascades and for the bottom-up optimizers discussed in section 4, Related Work.