Abstract:
A flexible query hints system and method for discovering and expressing query hints in a database management system. Embodiments of the flexible query hints system and method include a power hints (Phints) language that enables the specification of constraints to influence a query optimizer. Phints expressions are defined as tree patterns annotated with constraints. Embodiments of the flexible query hints system and method also include techniques to incorporate the power hints language expressions into an extended query optimizer. Theses techniques include computing a directed acyclic graph for Phints expression, deriving candidate matches using the Phints expression and the graph, computing candidate matches, and extracting a revised execution plan having a lowest cost and satisfying constraints of the Phints expression. Embodiments of the flexible query hints system and method include a flexible query hint user interface that allow users to interactively adjust query hints.

Description:
BACKGROUND 
       [0001]    Relational database management systems (DBMSs) allow a user to specify queries using high level declarative languages. These queries are specified in a declarative manner, where the query is set forth but no detailed algorithm of how to obtain the results is outlined. A query optimizer in DBMSs translates the declarative query in a specified algorithm called a query execution plan. An efficient query execution plan is select by query optimizers to evaluate an input query. Selection of the execution plan is performed using a cost model that estimates the resources that are needed for each alternative plan in consideration. 
         [0002]    Cost models for query optimizers typically are quite sophisticated and complex. While the cost model can often by used to select a good query execution plan for a given query, there are situations in which the cost model does not come up with a good execution plan. Because of its complexity, it is well known that cost models can be inherently inaccurate due to several factors. For example, factors such as erroneous cardinality estimates, inaccurate calibration constants used for costing, simplified cost formulas that miss some details, state runtime parameters that affect the execution costs of queries, and the effect of concurrent query executions all can lead to errors and inaccuracies in the optimizer cost model. 
         [0003]    It will thus be appreciated that query optimizers do not always produce optimal query execution plans. In fact, for complex queries, query optimizers may even return plans that are decisively poor In such situations, many DBMSs allow a user (typically a database administrator) to manually adjust and correct the wrong choices that led the query optimizer to select such a poor query execution plan. To aid the database administrator, DBMSs include (to varying degrees) a mechanism called query hinting. Query hinting allows database administrator to influence the choice of the best query execution plan through query hints. In general, query hints instruct the query optimizer to constrain its search space to a certain subset of execution plans. Two ways that this can be achieved by specifying an access path for a table (in other words, force the use of an index for a particular table) or by forcing the join order of the plan based on the order of the tables listed in a Structured Query Language (SQL) string. 
         [0004]    One problem is that there is not a unified abstraction of hints within any single DBMS. The existing set of hints supported by each DBMS is largely a toolkit of techniques that are considered important and that have been incorporated in its optimizers. This is because the hints do not express certain constraints of the structure of the execution plan, such as when trying to force an early pre-aggregation below a join. In many cases, the granularity at which hints constrain the search space is either too coarse, which effectively prevents experienced database administrators from fine-tuning a poorly optimized query, or instead requires a fully specified execution plan, which might be too inflexible and tedious for all but the simplest queries. 
       SUMMARY 
       [0005]    This Summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This Summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used to limit the scope of the claimed subject matter. 
         [0006]    Embodiments of the flexible query hints system and method use a query hints language that enables the specification of rich constraints to influence a query optimizer to select better query execution plans. As stated above, commercial database systems expose query hints to address situations in which the query optimizer selects a poor execution plan for a given query. However, current query hints are not flexible enough to deal with a variety of non-trivial scenarios. 
         [0007]    Embodiments of the flexible query hints system and method include a power hints (or “Phints”) language. The Phints language is a small language used to specify rich constraints over the query optimizer&#39;s search space of query execution plans. Phints expressions are defined as tree patterns annotated with constraints. A directed acyclic graph is used to graphically represent a Phints expression. A subplan in the graph matches a Phints tree pattern if certain conditions are met. In addition, each node in the tree pattern can be annotated with various constraints. These constraints include a “Self-Constraint”, which is a predicate that must be satisfied in the graph, and a “Subtree Constraint”, which is a predicate that must be satisfied by each descendant of a node mapping in the graph. Another constraint available in the Phints language is an “Order constraint”, which returns node mappings in a precise ordering. 
         [0008]    The Phints language also includes a concise syntax for specifying Phints expressions that is linearized and can be appended to a structured query language (SQL) query string in the same way as current query hints. A set of conventions are used, such that the tree pattern is written in infix order, using parenthesis to denote parent-child relationships, or square brackets if the order constraint is present in the parent node. Moreover, if there are no self constraints, the node is denoted with the “*” symbol. In addition, subtree constraints are written in curly braces next to the node description. 
         [0009]    Embodiments of the flexible query hints system and method also include techniques to incorporate the power hints language expressions into an extended query optimizer. This extended query optimizer uses these techniques to use the Phints expressions. Generally, the evaluation of a Phints expression can be done by enumerating all possible execution plans in the directed acyclic graph, filtering out any alternatives that do not match the Phints expression, and returning the matching query execution plan having with the smallest estimated cost. The cost is estimated using an optimizer cost model. 
         [0010]    Embodiments of the flexible query hints system and method also include a flexible query hint user interface. This interface allows a user to interactively adjust the query hints. The query execution plan is presented to the user on the user interface in a graphical manner, such that the user can quickly determining whether he is satisfied with the plan. If not, then the user can alter the constraints of the Phints expression using the user interface. In particular, constraints can be added or removed and the new execution plan can be executed on the user interface. All the while the current query execution plan is displayed graphically to help the user discover a satisfactory query execution plan. 
         [0011]    It should be noted that alternative embodiments are possible, and that steps and elements discussed herein may be changed, added, or eliminated, depending on the particular embodiment. These alternative embodiments include alternative steps and alternative elements that may be used, and structural changes that may be made, without departing from the scope of the invention. 
     
    
     
       DRAWINGS DESCRIPTION 
         [0012]    Referring now to the drawings in which like reference numbers represent corresponding parts throughout: 
           [0013]      FIG. 1  is a block diagram illustrating a general overview of embodiments of the flexible query hints system and method disclosed herein. 
           [0014]      FIG. 2  is a flow diagram illustrating the operation of embodiments of the flexible query hints system and method shown in  FIG. 1 . 
           [0015]      FIG. 3  is an exemplary example of a directed acyclic graph (or planSpace graph) of the search space. 
           [0016]      FIG. 4  illustrates a graphical representation of a pattern match in the Phints language. 
           [0017]      FIG. 5  is an exemplary example that illustrates a graphical representation of a Phints expression. 
           [0018]      FIG. 6  illustrates an exemplary example of a Phints expression S 
           [0019]      FIG. 7  illustrates the execution subplan P of the sub-expression shown in  FIG. 6 . 
           [0020]      FIG. 8  is a flow diagram illustrating the detailed operation of embodiments of the candidate match derivation module shown in  FIG. 1 . 
           [0021]      FIG. 9  is a flow diagram illustrating the detailed operation of embodiments of the candidate match computation module shown in  FIG. 1 . 
           [0022]      FIG. 10  is a flow diagram illustrating the detailed operation of embodiments of the extended optimizer shown in  FIG. 1 . 
           [0023]      FIG. 11  is an exemplary implementation of the flexible query hints user interface shown in  FIG. 1 . 
           [0024]      FIG. 12  illustrates an example of a suitable computing system environment in which embodiments of the flexible query hints system and method shown in  FIGS. 1-11  may be implemented. 
       
    
    
     DETAILED DESCRIPTION 
       [0025]    In the following description of embodiments of the flexible query hints system and method reference is made to the accompanying drawings, which form a part thereof, and in which is shown by way of illustration a specific example whereby embodiments of the flexible query hints system and method may be practiced. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the claimed subject matter. 
       I. System Overview 
       [0026]      FIG. 1  is a block diagram illustrating a general overview of embodiments of the flexible query hints system and method disclosed herein. It should be noted that the implementation shown in  FIG. 1  is only one of many implementations that are possible. Referring to  FIG. 1 , a flexible query hints system  100  is shown implemented on a server computing device  105  and a client computing device  110 . It should be noted that the computing devices  105 ,  110  may include a single processor (such as a desktop or laptop computer) or several processors and computers connected to each other. The server computing device  105  and the client computing device  110  communicate over a communications network  115 . 
         [0027]    In general, embodiments of the flexible query hints system  100  inputs a query  120 , processes the query  120 , and outputs an execution plan for the query that has a lowest cost and satisfies certain constraints  125 . The query typically is a query that a database administrator is unhappy with and would like to improve by using query hints. Embodiments of the flexible query hints system  100  provide a way for this to occur. 
         [0028]    Embodiments of the flexible query hints system  100  include an extended optimizer  130  and a planSpace graph module  135  located on the extended optimizer  130 . The planSpace graph module  135  takes the query  120  and returns its corresponding planSpace graph. As explained below, this planSpace graph is a directed acyclic graph. Note that the extended optimizer  130  and the planSpace graph module  135  reside on the serving computing device  105 . The planSpace graph is produced as a result of the query optimization, which occurs at the server computing device  105 . The client computing device  110  includes a Phints language specification module  140 , a candidate match derivation module  150 , and a candidate match computation module  160 . An extended optimizer  130  includes a planSpace graph module  135 , which takes the query  120  and returns its corresponding planSpace graph. As explained below, this planSpace graph is a directed acyclic graph. Note that the extended optimizer  130  and the planSpace graph module  135  reside on the serving computing device  105 . 
         [0029]    A session in the flexible query hints system  100  is typically initiated when the database administrator decides to tune the execution plan of a problematic query. At this point, the client computing device  110  the extended optimized a single time, and the planSpace graph module  135  in the extended optimizer  130  generates the planSpace graph corresponding to the query. 
         [0030]    The database administrator then uses the Phints language specification module  140  to constrain the query  120 . The Phints language is discussed in more detail below. Typically, the database administrator, based on knowledge about the application, the runtime system, and the current execution plan, decides to constrain the query  120  by creating Phints expressions or modifying previously submitted Phints expressions. 
         [0031]    Once a Phints expression has been created, the candidate match derivation module  150 , the candidate match computation module  160 , and the extended optimizer  130  are used to find the query execution plan having a lowest cost and that satisfies the Phints constraints  125 . The candidate match derivation module  150 , the candidate match computation module  160 , and the extended optimizer  130  are all discussed in detail below. 
         [0032]    The resulting execution plan  125  can optionally be sent to the server and executed to obtain feedback on cost, cardinality, and runtime characteristics. In addition, embodiments of the flexible query hints system  100  include a flexible query hints user interface  180 . Embodiments of the user interface  180  graphically displays the resulting plan, along with any optional feedback from an actual execution. Embodiments of the user interface  180  allow the side-by-side comparison of multiple execution trees resulting from previous Phints expressions. This comparison can help determine whether a good execution plan has been identified or whether additional iterations are needed. 
       II. Operational Overview 
       [0033]      FIG. 2  is a flow diagram illustrating the operation of embodiments of the flexible query hints system  100  and method shown in  FIG. 1 . In general, embodiments of the flexible query hints method input a query and output a query execution plan having a lowest cost and satisfying constraints of at least one Phints expression. Embodiments of the method use the methods of the planSpace graph module  135 , the Phints language specification module  140 , the candidate match derivation module  150 , the candidate match computation module  160 , the extended optimizer  130 , and the flexible query hints user interface  180 . 
         [0034]    Referring to  FIG. 2 , the method begins by inputting a query (box  200 ). The system  100  then computes a planSpace graph for the query (box  205 ). The planSpace graph is discussed in detail below. A user, typically a database administrator, then creates at least one Phints expression using the Phints language (box  210 ). The Phints language also is discussed in further detail below. 
         [0035]    Next, the user constrains the query using the Phints expression (box  215 ). The system  100  then uses the query and the Phints expression to generate the desired query execution plan. In particular, the system  100  first derives candidate matches for sub-plans of a given execution plan using the Phints expression and the planSpace graph (box  220 ). Next, candidate matches are computed for each operator in the execution plan (box  225 ). 
         [0036]    Several different execution plans are examined, and the system  100  extracts the query execution plan having a lowest cost while still satisfying the constraints given by the Phints expression (box  230 ). The extracted query execution plan ten is displayed to a user in a graphical fashion (box  235 ). This display enables a user to determine whether the plan meets the objectives of the user. A determination then is made as to whether the user is satisfied with the extracted execution plan (box  240 ). If not, then the user creates another Phints expression and the process begins again (box  245 ). If the user is satisfied, then the extracted query execution plan is output (box  250 ). In some embodiments the extracted execution plan is executed by the database management system. 
       III. Operational Details 
       [0037]    The operational details of embodiments of the flexible query hints system  100  and method now will be discussed. These embodiments include embodiments of the planspace graph module  135 , the Phints language specification module  140 , the candidate match derivation module  150 , the candidate match computation module  160 , the extended optimizer  130 , and the flexible query hints user interface  180 , all shown in  FIG. 1 . The operational details of each of these programs modules now will be discussed in detail. 
       III.A. PlanSpace Graph Module 
       [0038]    The details of the planSpace graph module  120  and its operation, along with some preliminary concepts and notation, will be discussed to make the subsequent discussion clearer. 
       III.A.1.PlanSpace Graph 
       [0039]    The flexible query hints system  100  and method models hints as constraints over the search space of execution plans considered by the query optimizer. Preparatory to discussing the details of the flexible query hints system  100  and method model, an abstract representation of such search space will be described. The general idea of the planspace graph module  135  is to compactly represent the very large set of possible execution plans by sharing as much structure as possible. 
         [0040]    Specifically, the space of plans of a given query can be modeled by using a directed acyclic graph. In this document, this type of directed acyclic graph is referred to as planSpace graph. A planSpace graph contains two kinds of nodes, which are denoted OP and OR nodes. Each OP node in a planSpace graph corresponds to a specific operator in an execution plan (such as a hash-join operator), and all of its children (if any) are OR nodes. In turn, each OR node in a planSpace graph corresponds to a set of equivalent alternatives that can be used interchangeably to form execution plans, and every one of its children (there is at least one) are OP nodes. 
         [0041]      FIG. 3  is an exemplary example of a directed acyclic graph (or planSpace graph) of the search space. In particular,  FIG. 3  illustrates a planSpace graph  300  for the query: 
         [0000]                                            SELECT * FROM R, S           WHERE R.x = S.y           ORDER BY R.x                        
In  FIG. 3 , OR nodes are represented by shaded circles (numbered  1  to  6 ), and OP nodes are represented by boxes that contain the specific operators in the tree. At the bottom of  FIG. 3  there are two OP nodes that return tuples from R. The first OP node, Scan(R)  310 , traverses the primary index in the relation and returns tuples in a non-specific order. The second OP node, Sorted Scan(R)  320 , traverses a covering index with clustering key column x and therefore returns tuples sorted by x. The OR node that is labeled # 5  in  FIG. 3  represents all alternative ways to return tuples from R. In turn, the OR node that is labeled # 3  represents alternative ways of returning tuples of R in x order. The rationale for considering such OR node is that the left-most merge join operator in  FIG. 3  requires tuples sorted by the join columns, and thus cannot be directly connected with the OR node # 5 . OR node # 3  then has two children: an explicit Sort operator whose child is OR node # 5 , and the original Sorted Scan(R) operator that already returns tuples in the right order and for which the additional sort would be redundant. The remainder of the graph can be analyzed similarly up to the root, which is an OR node that compactly represents all possible execution plans for the input query.
 
         [0042]    Note that this graph model is general enough to be mapped to the search space of different optimizers that are commonly used in commercial systems. Given a planSpace graph, it is possible to generate any execution plan by traversing the graph and picking one child for each OR node and all children for each OP node. The role of the optimizer is then to consider all execution plans induced by the planSpace graph and to pick the query execution plan with the least execution cost. 
       III.A.2.Cost Model 
       [0043]    Consider an OP node N. Each of N&#39;s children (if any) are OR nodes whose children by definition return the same result. Therefore, the cost of any query execution sub-plan rooted at N is the sum of costs of its children plus a local processing cost, which is independent of the choices below N. Consider the Merge Join node  330  on the left side of  FIG. 3 . No matter what choice is made for the left input (OR node # 3 ) or the right input (OR node # 4 ), the Merge Join  330  operator locally does the same amount of work. 
         [0044]    The cost model of an optimizer therefore approximates the local processing time for each possible operator in the graph. It essentially associates, with each OP node N, a real number LC(N), that corresponds to the local execution time of the corresponding operator. Obtaining the cost of the best execution sub-plan rooted at each node N in the planSpace, denoted BC(N), can be done using the equation: 
         [0000]    
       
         
           
             
               BC 
                
               
                 ( 
                 N 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         LC 
                          
                         
                           ( 
                           N 
                           ) 
                         
                       
                       + 
                       
                         
                           ∑ 
                           
                             N 
                             i 
                           
                         
                          
                         
                           BC 
                            
                           
                             ( 
                             
                               N 
                               i 
                             
                             ) 
                           
                         
                       
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         N 
                       
                       = 
                       
                         OP 
                          
                         
                           ( 
                           
                             
                               N 
                               1 
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               N 
                               k 
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         min 
                         
                           N 
                           i 
                         
                       
                        
                       
                         BC 
                          
                         
                           ( 
                           
                             N 
                             i 
                           
                           ) 
                         
                       
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         N 
                       
                       = 
                       
                         
                           OR 
                            
                           
                             ( 
                             
                               
                                 N 
                                 1 
                               
                               , 
                               … 
                                
                               
                                   
                               
                               , 
                               
                                 N 
                                 k 
                               
                             
                             ) 
                           
                         
                         . 
                       
                     
                   
                 
               
             
           
         
       
     
         [0045]    The definition of BC satisfies the well-known principle of optimality, which states that every sub-plan of an optimal plan is itself optimal. The best node N is obtained using the equation: 
         [0000]    
       
         
           
             
               BP 
                
               
                 ( 
                 N 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       
                         OP 
                         N 
                       
                        
                       
                         ( 
                         
                           
                             BP 
                              
                             
                               ( 
                               
                                 N 
                                 1 
                               
                               ) 
                             
                           
                           , 
                           … 
                            
                           
                               
                           
                           , 
                           
                             BP 
                              
                             
                               ( 
                               
                                 N 
                                 k 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         N 
                       
                       = 
                       
                         OP 
                          
                         
                           ( 
                           
                             
                               N 
                               1 
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               N 
                               k 
                             
                           
                           ) 
                         
                       
                     
                   
                 
                 
                   
                     
                       BP 
                        
                       
                         ( 
                         
                           min 
                            
                           
                               
                           
                            
                           
                             arg 
                             
                               N 
                               i 
                             
                           
                            
                           
                             BC 
                              
                             
                               ( 
                               
                                 N 
                                 i 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                   
                     
                       
                         if 
                          
                         
                             
                         
                          
                         N 
                       
                       = 
                       
                         OR 
                          
                         
                           ( 
                           
                             
                               N 
                               1 
                             
                             , 
                             … 
                              
                             
                                 
                             
                             , 
                             
                               N 
                               k 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    where OP N  is the operator associated with an OP node N, and minarg returns the N i  that minimizes value BC(N i ). 
         [0046]    In this conceptual model, current query hints can be seen as constraining the search space of plans (or the planSpace graph) that is considered by the optimizer. By way of example, the hint OPTION (HASH JOIN) would essentially remove from the original planSpace graph any OP node that is associated with a non hash-based join implementation, and would return the best execution plan out of that subgraph (if at least one such alternative exists). 
       III.B. Power Hints (Phints) Language Specification Module 
       [0047]    As discussed earlier, there is no uniform abstraction that can cover the set of query hints in current systems. The Phints language specification module  140  includes a simple query hinting language that can provide such an abstraction and at the same time is richer than existing query hints. The language is designated as Power Hints, or Phints for short. 
       III.B.1.Phints Expressions 
       [0048]    Phints expressions are defined as tree patterns annotated with constraints. Conceptually, the evaluation of Phints expressions can be done by enumerating all possible execution plans in the planSpace graph, filtering out the alternatives that do not match Phints expressions, and finally returning the matching query execution plan with the smallest estimated cost. 
         [0049]      FIG. 4  illustrates a graphical representation  400  of a pattern match in the Phints language. In particular, a subplan P in the planSpace graph matches a Phints tree pattern S  410  if there is a mapping M  420  between nodes in S  410  and distinct OP nodes in P such that:
       1) For each leaf node s in S  410 , M(s)  420  is a leaf node in P (and those are the only leaf nodes in P);   2) For each internal node s in S  410  with children {s i , . . . , s k }, every M(s i ) is a descendant of M(s)  420 , and no M(s i ) is a descendant of M(s j ) for i≠j; and,   3) For each node s in S  410 , M(s)  420 , and its descendants in P, must satisfy the constraints defined on s.         
         [0053]    Specifically, each node s in a tree pattern S  410  can be optionally annotated with various constraints. One of the constraints is called a “Self-Constraint”, which is a predicate that must be satisfied in the planSpace graph. Another constraint is called a “Subtree Constraint”, which is a predicate that must be satisfied by each descendant of M(s)  420  in the planSpace graph. Yet another constraint available in the Phints language is called an “Order constraint”, where, if an order constraint is present, an in-order traversal of the planSpace graph returns M(s 1 ), . . . , M(s k ) in that precise order. 
         [0054]    Predicates in self-constraints and subtree-constraints for node s include a “force(A)”, which specifies that the matching M(s)  420  must have A as the associated implementation algorithm (such as force(Hash Join)). Another predicate is “disable(A)”, which specifies that the matching M(s)  420  cannot have A as the implementation algorithm. Another predicate is “condForce(A L , A P ), which specifies that the matching M(s)  420  must use A P  as the implementation algorithm but only if M(s)  420  is of type A L . By way of example, a join operator can be forced to be hash-based by condForce(Join, Hash Join)). Another predicate is “forceTable(T)”, where T is a table, which specifies that the matching node M(s)  420  must be a leaf node that operates over T 3 . 
       III.B.2.Concisely Expressing Phints Expressions 
       [0055]    This section describes a concise syntax for specifying Phints expressions that is linearized and can be appended to a structured query language (SQL) query string in the same way as current query hints. Note that the following conventions are used. First, the tree pattern is written in infix order, using parenthesis to denote parent-child relationships, or square brackets if the order constraint is present in the parent node. Second, if there are no self constraints, the node is denoted with the symbol *. Otherwise, the node is denoted with A for a force(A) self-constraint, !A for a disable(A) self-constraint, T for a forceTable(T) constraint, and L=&gt;P for a CondForce(L,P) constraint. Third, subtree constraints are written in curly braces next to the node description. 
         [0056]      FIG. 5  is an exemplary example that illustrates a graphical representation of a Phints expression. In particular,  FIG. 5  shows a sample tree expression  500  that illustrates the features of the language, and would match any execution subplan that: (1) is a three-way join between tables R  510 , S  520 , and some other table in the query  530 ; (2) has no join that is hash-based; (3) the inner join is merge-based between S and the remaining table in that order; and, (iv) there is an early pre-aggregation on table R. Using the above notation, The Phints expression shown in  FIG. 5  can be written as:
       *{!HashJoin}(HashAggregate(R), MergeJoin[S,*])         
         [0058]    In other embodiments, it is possible that alternative linearized representations can be generated, such as the following XML-based representation for the constraint above: 
         [0000]    
       
         
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 &lt;Op SubTree=“!HashJoin”&gt; 
               
               
                   
                  &lt;Op Self=“HashAggregate”&gt; 
               
               
                   
                   &lt;Op Table=“R”/&gt; 
               
               
                   
                  &lt;/Op&gt; 
               
               
                   
                  &lt;Op Self=“Merge Join” Ordered=“True”&gt; 
               
               
                   
                   &lt;Op Table=“S”/&gt; 
               
               
                   
                   &lt;Op Table=“*”/&gt; 
               
               
                   
                  &lt;/Op&gt; 
               
               
                   
                 &lt;/Op&gt; 
               
               
                   
                   
               
             
          
         
       
     
       IlI.B.3.Additional Examples 
       [0059]    Additional examples that further illustrate the capabilities of Phints expressions will now be introduced. First, it will be shown how some of the common hints supported by the current systems fit naturally in the framework of the flexible query hints system  100  and method. Next, more complex scenarios are outlined that can be easily specified in Phints, but may not be supported by most current systems. 
         [0060]    As a first exemplary example, consider the OPTION(HASH JOIN) hint used in above to force all joins to be hash based. This can easily be specified in the Phints language as: 
         [0000]      *{Join=&gt;Hash Join}( R,S,T ). 
         [0061]    As a second exemplary example, consider a join of four tables R, S, T and U. Moreover, suppose that it is required that the tables to be joined in that particular order. Some commercial systems support the ability to specify a join order in the final plan based on the syntactic order of the tables in the input SQL statement (such as OPTION(FORCE ORDER)). Any arbitrary join tree can easily be specified using Phints expressions, such as: 
         [0000]      *[R,*[*[S,T], U]]. 
         [0062]    Note, however, that there are two interesting generalizations of this pattern. First, certain join implementations can be forced for some nodes, others can be disabled, and a third group can be left unspecified (so that the optimizer finds the best alternative). This can be expressed as a Phints expression as: 
         [0000]      HashJoin[R,*[!NLJoin[S,T],U]]. 
         [0000]    Second, by specifying the expression *[R,S,T,U], any execution plan P can be matched that joins only these four tables, and for which an in-order traversal of the nodes returns the tables in the correct order, is valid (such as (R,(S,T),U), (R,(S, (T, U))), (((R,S),T), U)). 
         [0063]    As a third exemplary example, note that some systems support the specification of a table to be the first one in the join order. For instance, if it is desired that the optimizer pick a plan that uses R as the initial joined table, the following Phints expression can be used: 
         [0000]      *[R,*,*, 8 ]. 
         [0000]    Again, note that more complex interactions can be specified with Phints expressions, such as: 
         [0000]      *[*(R,S),*,*], 
         [0000]    which instructs the optimizer to pick a join order that “begins” with tables R and S (in some order), and then joins the result with the remaining tables. 
         [0064]    As a fourth exemplary example, suppose that in the previous example R is a fact table and the remaining tables are dimension tables. Further, suppose that a user wants to force a plan that joins the dimension tables first (possibly using Cartesian products) and then uses an index to access the fact table. This plan is interesting since it avoids scanning the large fact table R. At the same time, however, it is not desirable to explicitly specify the ordering of the dimension tables. This type of plan can be specified using the following Phints expression: 
         [0000]      IndexNestedLoops[*(*,*,*),R]. 
       III.C. Evaluating Phints Expressions 
       [0065]    This section discusses the way in which the flexible query hints system  100  and method obtain the most efficient execution plan in a planSpace graph subject to Phints constraints. First, the notion of a candidate match is introduced, which keeps track of partial matches between nodes in Phints expressions and those in the planSpace graph. Next, it is shown how a candidate matches are computed bottom-up in a planSpace graph. As used in this document, the phrase “bottom up” means that the computation of candidate matches proceeds from the leaf nodes in the planSpace towards the root note. Next, original dynamic programming algorithm is reviewed to obtain the best execution plan under no constraints, and then a discussion of why the principle of optimality, which is valid in the original formulation, does not hold under such constraints. Finally, the notion of interesting matches is introduced to address this problem along with the way in which Phints expressions are evaluated. 
       III.C.1.Candidate Matches 
       [0066]    Consider a Phints expression *[R,S,T] and an execution subplan, 
         [0000]      P=R         S. 
         [0000]    Although the subplan does not match the full expression, it does so “partially,” since further joining P with table T would result in a match as described in the previous section. It should be noted that, 
         [0000]      R         T 
         [0000]    is not a partial match. A mechanism, therefore, is needed to refer to and reason with such partial matches. Consider a tree pattern S and a subplan P. A candidate match between P and S is defined as (s, c), where s is a node in S and c={s 1 , . . . , s k } is an ordered subset of children of s, such that:
       1) There exist k disjoint subtrees of P, {p 1 , . . . , p k }, such that each p i  matches s i  as in the definition set forth above.   2) If s has an order constraint, then an in-order traversal of P returns p 1 , . . . , p k  in this order, and {s 1 , . . . , s k } is a subsequence of children(s), and there are no “gaps” in s i .   3) If {s 1 , . . . , s k } cover all of s′ children, then P matches s as in the definition set forth above.       
 
         [0070]      FIGS. 6 and 7  illustrate an exemplary example of candidate matches in Phints.  FIG. 6  illustrates an exemplary example of a Phints expression S. In this exemplary example shown in  FIG. 6 , the sub-expression is HashJoin[R,*,T].  FIG. 7  illustrates the execution subplan P of the sub-expression shown in  FIG. 6 . As shown in  FIG. 7 , below each node in the execution plan are shown the candidate matches of the operator. For instance, the candidate matches for Scan(R)  700  are both (s 4 , {}) and (s 5 , {}). In general, the candidate matches for a leaf node L in an execution plan are all (s i , {}) for leaf nodes s 1  in the Phints expression for which: (i) L satisfies s 1 &#39;s self-constraints; and, (ii) the subtree-constraints of all s 1 &#39;s ancestors. 
         [0071]    Referring to  FIGS. 6 and 7 , the Merge Join  710  operator matches (s 3 , {s 4 , s 5 }) because: (i) subtrees Scan(R)  700  and Scan(S)  720  match s 4  and s 5 , respectively; (ii) the order of children is preserved without gaps; and, (iii) since s 6  is not a match, it is not necessary to additionally satisfy the Hash Join self-constraint on s 3 . By a similar reasoning, it can also be shown that the Hash Join operator  730  matches both s 3  and all its children {s 4 , s 5 , s 6 }. 
       III.C.2.Computing Candidate Matches 
       [0072]    This section describes how to compute all candidate matches in a planSpace graph bottom up using the candidate match derivation module  150 , the candidate match computation module  160 , and the extended optimizer  130 . First, it is shown a candidate match for a node can be derived given matches for each of its children. Next, it is shown how to compute all candidate matches. 
         [0000]    III.C.2.a. Candidate Match Derivation Module 
         [0073]    In general, embodiments of the candidate match derivation module  150  derive candidate matches of a given query execution subplan. Note that for a node n in a tree, parent(n), children(n), and isRoot(n) are used to denote, respectively, the parent of n, the children of n, and whether n is the root of the tree. To further simplify the notation, the operation of deriving a candidate match uses m.s and m.c to denote the node and ordered set of children of a given candidate match m. 
         [0074]    Consider an OP node A with arity k in a given execution plan, and suppose that each m i (i≦k) is a candidate match of the i-th child of A. Then, the candidate match derivation module  150  returns the corresponding match for A (if any) based on matches of A&#39;s children. In particular,  FIG. 8  is a flow diagram illustrating the detailed operation of embodiments of the candidate match derivation module  150  shown in  FIG. 1 . The operation begins by inputting an operator in a given execution plan (box  800 ). In other words, an OP node of arity k is input. Next, the module  150  inputs matches for the children of the input OP node (box  805 ). 
         [0075]    The module  150  then promotes of the fully matched children into an equivalent form in terms of the parent node (box  810 ). For the exemplary example of  FIGS. 6 and 7 , this process action would convert (s 3 , {s 4 , s 5 , s 6 }) into (s 1 , {s 3 }), but would keep (s 3 , {s 5 , s 6 }) unchanged. The module  150  then determines whether all transformed matches (m i ) at least partially match the same tree pattern (mi.s) (box  815 ). If not, then no candidate match can be derived (box  820 ). 
         [0076]    If all transformed matches do at least partially match the same tree pattern, then the module  150  determines whether the same candidate match is returned by multiple children (box  825 ). If not, then no unique mapping is possible (box  830 ), and no candidate match can be derived (box  820 ). Otherwise, the mapping is a unique mapping. 
         [0077]    Next, the module  150  assembles the result (rm) by concatenating the candidate matches of each OP node child (m i ) (box  830 ). Next, the module  150  determines whether the OP node satisfies subtree constraints of a tree pattern (rm.s) of the result (box  840 ). If not, then there is no candidate match that can be derived (box  820 ). If the subtree constraints are satisfied, then the tree pattern of the results does have an order constraint (box  845 ). 
         [0078]    The module  150  then determines whether an order is satisfied by the OP node and its subtrees (box  850 ). If not, then there is no candidate match that can be derived (box  820 ). Otherwise, the result is a full match (box  855 ). The module  150  then makes a determination as to whether the self-constraints of the tree pattern of the result are satisfied (box  860 ). If not, then there is no candidate match that can be derived (box  820 ). If so, then the output of the candidate match derivation module  150  is a valid candidate match for the input OP node (box  865 ). 
         [0079]    By way of example, consider matches (s 3 , {s 4 , s 5 }) and (s 6 , {}) for the Merge Join  710  and Scan(T)  740  operators in  FIG. 7 . Processing by the module  150 , where the OP node is the Hash Join node  730  in  FIG. 7 , would first promote (s 6 , {}) into (s 3 , {s 6 }) but would leave (s 3 , {s 4 , s 5 }) unchanged. Both matches then would share the same tree node (s 3 ) and would have disjoint children subsets. The new match is assembled as (s 3 , {s 4 , s 5 , s 6 }), and since it satisfies all self-constraints and subtree constraints, is therefore returned as a match for the OP node itself. 
         [0000]    III.C.2.b. Candidate Match Computation Module 
         [0080]    Each operator in an execution plan may have multiple candidate matches (such as the Scan(R) node  700  in  FIG. 7 ). The candidate match computation module  160  can be used to propagate candidate matches bottom up in an execution plan.  FIG. 9  is a flow diagram illustrating the detailed operation of embodiments of the candidate match computation module  160  shown in  FIG. 1 . In particular, the operation of embodiments of the candidate match computation module  160  initially input an OP node of arity K (box  900 ). Note that K is rarely larger than two. In addition, the module  160  inputs set of matches from each of the OP node children (box  905 ). A match then is selected from an input match set (box  910 ). The module  160  then determines whether the match under consideration is a full candidate match (box  915 ). If so, then the module  160  adds the full candidate match to a set of candidate match results (box  920 ). 
         [0081]    If not, then module  160  determines whether there are additional matches to test (box  925 ). If so, then another match is selected from a match set (box  930 ) and the process actions  915 ,  920 , and  925  are iterated over again. Otherwise, the module selects a combination of input candidate matches (box  935 ). For each combination of input candidate matches, the module  160  uses the candidate match derivation module  150  to extend partial matches with respect to the input OP node (box  940 ). These extended partial matches are added to the set of candidate match results (box  945 ). A determination is made as to whether there are additional combinations to be examined (box  950 ). If so, then another combination is selected (box  955 ) and the process action  940 ,  945 , and  950  are iterated over again. 
         [0082]    The module  160  then makes the determination as to whether the value of the OP node arity K is one (box  960 ). If not, then the set of candidate match results is output (box  965 ). If so, this means that the OP node is a unary OP node (box  970 ). It should be noted that even if a unary operator in the execution plan can be extended by the candidate match derivation module  150 , the same operator can still share its child matches. However, this is not the case for non-unary operators, since the resulting execution plan would contain additional leaf nodes. 
         [0083]    The module  160  then checks whether the candidate match of a single child of the unary OP node is still valid for the OP node (box  975 ). If not, then the set of candidate match results is output (box  965 ). If so, then the candidate match of the single child is added to the set of candidate match results (box  980 ). Then the set of candidate match results is output (box  965 ). 
       III.C.3.Extended Optimizer 
       [0084]    This section describes how the candidate match derivation module  150  and the candidate match computation module  160  are used by the extended optimizer  130  to find a query execution plan that has the lowest cost while still satisfying the constraints of the Phints expression. 
         [0000]    III.C.3.a. Interesting Candidate Matches 
         [0085]    In general, the system  100  keeps a set of equivalent query execution plans that are non-comparable with respect to their respective matches. Specifically, the system  100  desires an operator which, given a set of execution plans associated with a given OR node, returns the subset of “non-comparable” alternatives. This is known as the “skyline” operator. For a set P and a partial order ≦, is defined as {pεP such that for all p j εP: p j ≦p}. The system  100  uses the following partial order for comparing plans P 1  and P 2 : 
         [0000]                                            P 1  ≦ P 2  if P 1 .matches ≦ P 2 .matches OR             ( P 1 .matches = P 2 .matches AND              P 1 .cost ≦ P 2 .cost ),                        
which in turn depends on a partial order for candidate matches.
 
         [0086]    Consider sets of matches M 1  and M 2 . It is said that M 1 ≦M 2  if for each match m 1 εM 1  there exists a match m 2 εM 2  such that m 1 &lt;m 2 . In turn, this definition is based on a third partial order between individual matches. Given two matches m 1 =(s 1 , c 1 ) and m 2 =(s 2 , c 2 ) it can be said that m 1 ≦m 2  if the following are true: (i) s 1  is an ancestor of s 2 ; or, (ii) s 1 =s 2  and c 1   ⊂ c 2 . 
         [0087]    The partial order described above requires the system  100  to keep track of multiple execution plans for a given root OP node. For that purpose, the system  100  uses the concept of an extended OP node. The extended OP node is a special kind of OP node that has the following properties: (i) it is additionally associated with a set of candidate matches; and, (ii) its children are extended OP nodes themselves. The same OP node A in the original planSpace graph might now be associated with multiple extended OP nodes, each one binding to different execution plans (with the same root A) and different sets of candidate matches. 
         [0000]    III.C.3.b. Operation of the Extended Optimizer 
         [0088]    In general, embodiments of the extended optimizer  130  takes as input an OR node in the planSpace graph and return a set of extended OP nodes, where each one extended OP nodes is incomparable with respect to the set of candidate matches they satisfy.  FIG. 10  is a flow diagram illustrating the detailed operation of embodiments of the extended optimizer  130  shown in  FIG. 1 . Embodiments of the operation of the optimizer  130  begin by input OR nodes from the planSpace graph (box  1000 ). 
         [0089]    Next, the optimizer  130  implements a first memorization to guarantee that each OR node is computed once (box  1005 ). An OR node then is selected for processing (box  1010 ). In addition, a child alternative is selected for the selected OR node (box  1015 ). The optimizer  130  then implements a second memorization and guarantees that each OP node in the child alternative is processed once (box  1020 ). 
         [0090]    The optimizer  130  then creates an extended OP node from the selected OP node (box  1030 ). The optimizer  130  then sets any children of the extended OP node (box  1035 ), and determines a cost for the extended OP node (box  1040 ). In addition, the optimizer  130  determines matches for the extended OP node using the candidate match computation module  160  (box  1045 ). 
         [0091]    A determination then is made as to whether the extended OP node is non-dominated (box  1050 ). If so, then the extended OP node is added to the set of extended OP nodes (box  1055 ). Next, a determination is made as to whether there are more OP nodes to process (box  1060 ). If so, then another OP node is selected for processing (box  1065 ), and the process action  1030 ,  1035 ,  1040 ,  1045 ,  1050 ,  1055 , and  1060  are iterated over again. Otherwise, the optimizer  130  determines whether there are more OR nodes to process (box  1070 ). If so, then another OR node is selected for processing (box  1075 ) and process actions  1015 ,  1020 ,  1025 ,  1030 ,  1035 ,  1040 ,  1045 ,  1050 ,  1055 ,  1060 ,  1065 , and  1070  are iterated over again. Otherwise, the optimizer  130  outputs a set of extended OP nodes (box  1080 ). 
       III.D. Flexible Query Hints User Interface 
       [0092]    When the user (typically a database administrator is satisfied with a query execution plan for the problematic query, the system  100  generates a description of such plan to be passed to the optimizer  130 . The plan is presented to the user in a graphical manner. 
         [0093]      FIG. 11  is a exemplary implementation of the flexible query hints user interface  180  shown in  FIG. 1 . In particular,  FIG. 11  illustrates a graphical user interface  1100  that uses a visual paradigm to create constraints, which are then translated into Phints expressions. For instance, the execution subplan in  FIG. 11  that is circle by the dotted line  1110  corresponds to the Phints tree expression: 
         [0000]      StreamGBAgg(MergeJoin[orders, lineitem]). 
         [0000]    Resulting execution plans can be evaluated and compared, and the system  100  has the ability to generate fully specified hints for use in production environments. 
       III.E. Alternate Embodiments 
       [0094]    Alternate embodiments of the flexible query hints system  100  and method now will be discussed. 
       III.E.1. Extensions to Matching Semantics 
       [0095]    The matching semantics for Phints expressions discussed above required that each leaf node in an execution subplan P matches a leaf node in the tree pattern S. In fact, any leaf node in an execution plan that satisfies the self-constraint and the subtree constraints of an expression leaf node is deemed a valid match. 
         [0096]    In alternate embodiments, this notion is relaxed, which allows increased flexibility in the Phints language. Specifically, this allows the possibility of matching whole execution subplans, as well as the ability to support access-path related hints. Suppose that, at least conceptually, an explicit set of candidate nodes in the planSpace (not necessarily leaf nodes) is associated with a leaf node in a Phints expression. Further, denote such set of candidate nodes for a pattern S as the virtual leaf nodes for S. Then, this embodiments changes the first condition in the matching semantics of Phints expressions from:
       1) For each leaf node s in S, M(s) is a leaf node in P   (and those are the only leaf nodes in P);   to:   1) For each leaf node s in S, M(s) is a virtual leaf node in P for s, and if we remove any subtree of a virtual leaf node in the execution plan, those virtual leaf nodes become the only leaf nodes in P.       
 
         [0101]    Now, the implementation of the candidate match computation module  160  shown in  FIG. 9  needs to be slightly modified by adding, to the resulting set of matches of an OP node n, leaf candidate matches for all nodes s in Phints expressions for which the following is true: (i) n is a virtual leaf node of s; and, (ii) n satisfies all self-constraint and subtree-constraints of s. Of course, if all leaf nodes in the planSpace graph are associated as virtual leaf nodes of every leaf node in Phints expressions, the this is the same as the embodiments previously described above. However, virtual leaf nodes enable additional functionality to the basic query model, as is discussed next. 
       III.E.2.Access-Path Hints 
       [0102]    Virtual leaf nodes are important when additionally dealing with index strategies. As a simple example, consider the Phints expression: 
         [0000]      HashJoin[R, S]. 
         [0000]    Suppose that there is an execution plan that uses an index intersection to obtain the required tuples in R, and therefore looks like: 
         [0000]      HashJoin(Intersection(I R   1 , I R   2 ), S). 
         [0103]    Unfortunately, this plan would not match the Phints expression because there would be an additional leaf node (either I R   1  or I R   2 ) which would violate the first matching condition as given above. To address these scenarios, some embodiments rely on the concept of virtual leaf nodes as follows. Consider a leaf node s in a Phints expression that has a self-constraint of the type forceTable(T). In this situation, all nodes in the planspace graph are obtained that correspond to execution subplans over T alone, and those nodes are associated as the virtual leaf nodes for s. This concept makes possible to match any execution plan p that returns tuples from a table T (using sequential scans, index intersections, or other alternatives) to a leaf expression node s that has a constraint of type forceTable(T). 
         [0104]    To fully enable access-path hints, some embodiments add another predicate to the self-constraints of an expression node. In particular, by specifying forceIndex(I), where I is an index name, an expression node s would only match nodes that exploit such index in the plan. The following examples will help clarify these issues:
       1. *(R, S) would match any single-table subplan over R joining any single-table subplan over S.   2. *(Intersection [I R   1 , R], S)would additionally require that the subplan over R is an intersection plan that uses index I R   1  (note the concise representation of forceIndex constraints, similar to those for forceTable constraints). The second child of the Intersection node is again R, meaning that any single-table execution plan over R would match, such as another index scan to intersect with I R   1 , or even the result of intersecting multiple such indexes.       
 
       III.E.3.Matching Subexpressions 
       [0107]    Consider the Phints expression HashJoin[R,*], which matches a binary join between R and a single additional table. If it is desirable to have R truly be a prefix in the execution plan, the expression as HashJoin[R,*, . . . ,*] needs to be extended with as many * symbols as remaining tables in the query. 
         [0108]    Alternatively, some embodiments express this more concisely as: 
         [0000]      HashJoin[R, *], 
         [0000]    where the special symbol {circumflex over (*)} allows matching of an arbitrary execution subplan. To enable such scenarios, some embodiments of the system  100  assign to an expression leaf node marked as {circumflex over (*)} all nodes in the planSpace graph as its virtual leaf nodes, which results in the desired matches. 
       IV. Exemplary Operating Environment 
       [0109]    Embodiments of the flexible query hints system  100  and method are designed to operate in a computing environment. The following discussion is intended to provide a brief, general description of a suitable computing environment in which embodiments of the flexible query hints system  100  and method may be implemented. 
         [0110]      FIG. 12  illustrates an example of a suitable computing system environment in which embodiments of the flexible query hints system and method shown in  FIGS. 1-11  may be implemented. The computing system environment  1200  is only one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the invention. Neither should the computing environment  1200  be interpreted as having any dependency or requirement relating to any one or combination of components illustrated in the exemplary operating environment. 
         [0111]    Embodiments of the flexible query hints system  100  and method are operational with numerous other general purpose or special purpose computing system environments or configurations. Examples of well known computing systems, environments, and/or configurations that may be suitable for use with embodiments of the flexible query hints system  100  and method include, but are not limited to, personal computers, server computers, hand-held (including smartphones), laptop or mobile computer or communications devices such as cell phones and PDA&#39;s, multiprocessor systems, microprocessor-based systems, set top boxes, programmable consumer electronics, network PCs, minicomputers, mainframe computers, distributed computing environments that include any of the above systems or devices, and the like. 
         [0112]    Embodiments of the flexible query hints system  100  and method may be described in the general context of computer-executable instructions, such as program modules, being executed by a computer. Generally, program modules include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types. Embodiments of the flexible query hints system  100  and method may also be practiced in distributed computing environments where tasks are performed by remote processing devices that are linked through a communications network. In a distributed computing environment, program modules may be located in both local and remote computer storage media including memory storage devices. With reference to  FIG. 12 , an exemplary system for embodiments of the flexible query hints system  100  and method includes a general-purpose computing device in the form of a computer  1210 . 
         [0113]    Components of the computer  1210  may include, but are not limited to, a processing unit  1220  (such as a central processing unit, CPU), a system memory  1230 , and a system bus  1221  that couples various system components including the system memory to the processing unit  1220 . The system bus  1221  may be any of several types of bus structures including a memory bus or memory controller, a peripheral bus, and a local bus using any of a variety of bus architectures. By way of example, and not limitation, such architectures include Industry Standard Architecture (ISA) bus, Micro Channel Architecture (MCA) bus, Enhanced ISA (EISA) bus, Video Electronics Standards Association (VESA) local bus, and Peripheral Component Interconnect (PCI) bus also known as Mezzanine bus. 
         [0114]    The computer  1210  typically includes a variety of computer readable media. Computer readable media can be any available media that can be accessed by the computer  1210  and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer readable media may comprise computer storage media and communication media. Computer storage media includes volatile and nonvolatile removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data. 
         [0115]    Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by the computer  1210 . By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer readable media. 
         [0116]    The system memory  1240  includes computer storage media in the form of volatile and/or nonvolatile memory such as read only memory (ROM)  1231  and random access memory (RAM)  1232 . A basic input/output system  1233  (BIOS), containing the basic routines that help to transfer information between elements within the computer  1210 , such as during start-up, is typically stored in ROM  1231 . RAM  1232  typically contains data and/or program modules that are immediately accessible to and/or presently being operated on by processing unit  1220 . By way of example, and not limitation,  FIG. 12  illustrates operating system  1234 , application programs  1235 , other program modules  1236 , and program data  1237 . 
         [0117]    The computer  1210  may also include other removable/non-removable, volatile/nonvolatile computer storage media. By way of example only,  FIG. 12  illustrates a hard disk drive  1241  that reads from or writes to non-removable, nonvolatile magnetic media, a magnetic disk drive  1251  that reads from or writes to a removable, nonvolatile magnetic disk  1252 , and an optical disk drive  1255  that reads from or writes to a removable, nonvolatile optical disk  1256  such as a CD ROM or other optical media. 
         [0118]    Other removable/non-removable, volatile/nonvolatile computer storage media that can be used in the exemplary operating environment include, but are not limited to, magnetic tape cassettes, flash memory cards, digital versatile disks, digital video tape, solid state RAM, solid state ROM, and the like. The hard disk drive  1241  is typically connected to the system bus  1221  through a non-removable memory interface such as interface  1240 , and magnetic disk drive  1251  and optical disk drive  1255  are typically connected to the system bus  1221  by a removable memory interface, such as interface  1250 . 
         [0119]    The drives and their associated computer storage media discussed above and illustrated in  FIG. 12 , provide storage of computer readable instructions, data structures, program modules and other data for the computer  1210 . In  FIG. 12 , for example, hard disk drive  1241  is illustrated as storing operating system  1244 , application programs  1245 , other program modules  1246 , and program data  1247 . Note that these components can either be the same as or different from operating system  1234 , application programs  1235 , other program modules  1236 , and program data  1237 . Operating system  1244 , application programs  1245 , other program modules  1246 , and program data  1247  are given different numbers here to illustrate that, at a minimum, they are different copies. A user may enter commands and information (or data) into the computer  1210  through input devices such as a keyboard  1262 , pointing device  1261 , commonly referred to as a mouse, trackball or touch pad, and a touch panel or touch screen (not shown). 
         [0120]    Other input devices (not shown) may include a microphone, joystick, game pad, satellite dish, scanner, radio receiver, or a television or broadcast video receiver, or the like. These and other input devices are often connected to the processing unit  1220  through a user input interface  1260  that is coupled to the system bus  1221 , but may be connected by other interface and bus structures, such as, for example, a parallel port, game port or a universal serial bus (USB). A monitor  1291  or other type of display device is also connected to the system bus  1221  via an interface, such as a video interface  1290 . In addition to the monitor, computers may also include other peripheral output devices such as speakers  1297  and printer  1296 , which may be connected through an output peripheral interface  1295 . 
         [0121]    The computer  1210  may operate in a networked environment using logical connections to one or more remote computers, such as a remote computer  1280 . The remote computer  1280  may be a personal computer, a server, a router, a network PC, a peer device or other common network node, and typically includes many or all of the elements described above relative to the computer  1210 , although only a memory storage device  1281  has been illustrated in  FIG. 12 . The logical connections depicted in  FIG. 12  include a local area network (LAN)  1271  and a wide area network (WAN)  1273 , but may also include other networks. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets and the Internet. 
         [0122]    When used in a LAN networking environment, the computer  1210  is connected to the LAN  1271  through a network interface or adapter  1270 . When used in a WAN networking environment, the computer  1210  typically includes a modem  1272  or other means for establishing communications over the WAN  1273 , such as the Internet. The modem  1272 , which may be internal or external, may be connected to the system bus  1221  via the user input interface  1260 , or other appropriate mechanism. In a networked environment, program modules depicted relative to the computer  1210 , or portions thereof, may be stored in the remote memory storage device. By way of example, and not limitation,  FIG. 12  illustrates remote application programs  1285  as residing on memory device  1281 . It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used. 
         [0123]    The foregoing Detailed Description has been presented for the purposes of illustration and description. Many modifications and variations are possible in light of the above teaching. It is not intended to be exhaustive or to limit the subject matter described herein to the precise form disclosed. Although the subject matter has been described in language specific to structural features and/or methodological acts, it is to be understood that the subject matter defined in the appended claims is not necessarily limited to the specific features or acts described above. Rather, the specific features and acts described above are disclosed as example forms of implementing the claims appended hereto.