Patent Description:
Query optimization refers to the overall process of attempting to choose a most efficient query plan, among many candidate query plans, to execute a query. For cost-based query optimization schemes, a query optimizer can rank the candidate query plans from the lowest cost to the highest cost (e.g., in terms of usage of system resources, such as I/O, CPU, memory, etc.), and select the query plan with the lowest cost for execution. The cost-based query optimization often collects and/or estimates statistics on tables and indexes involved in a query and uses those statistics to estimate costs of query plans. However, errors can be introduced when estimating data statistics, especially for result tables of intermediate operations of query plans. As a result, the query plan generated by the query optimizer may not be optimal after all or even close. Thus, there remains a need for an improved technology for more accurately determining data statistics associated with query plans.

<CIT> describes a computer-implemented method, apparatus and article of manufacture for optimizing a database query. A query execution plan for the database query is generated using estimated cost information; one or more steps of the query execution plan are executed to retrieve data from a database stored on the computer system. Actual cost information is generated for each of the executed steps, and the estimated cost information is re-calculated using the actual cost information. One or more resource allocation rules defined on one or more steps of the query execution plan are executed, based on the estimated cost information, wherein the resource allocation rules include one or more defined actions. The estimated cost information may be re-calculated using the actual cost information when confidence in the estimated cost information is low, but the estimated cost information may not be re-calculated when confidence in the estimated cost information is high. In addition, the estimated cost information may be re-calculated using the actual cost information, only when the step has one or more resource allocation rules defined thereon.

<CIT> describes a query optimizer comprising a query tuner that performs actual execution of query fragments to obtain actual results during compilation time, and uses those actual results to select a query plan. The actual results may be combined with estimates for fragments that were not executed. The tree may be traversed in a top-down traversal, processing every node. Alternatively, the tree may be traversed in a bottom-up traversal, re-deriving data for higher nodes as each lower level is completed. A limit, such as a time limit or level limit, may be used to control how much time is taken to determine the execution plan.

The underlying technical problem is solved by the subject-matter having the features of the independent claims. Additional embodiments are defined in the dependent claims.

After receiving a query, the query optimizer can create an internal representation of the query as a query tree including a plurality of nodes and edges linking the nodes. The nodes can include leaf nodes and one or more internal nodes. A leaf node has no child nodes. In contrast, an internal node has one or more child nodes. The root of the query tree, or root node, can be regarded as a special internal node.

The query tree denotes a relational algebra expression. Specifically, tables involved in the query can be represented as leaf nodes. The relational algebra operations can be represented as internal nodes. The root node represents the query as a whole. When a query plan is executed, an internal node can be executed when its operand tables are available. The internal node can then be replaced by a result table generated by the operation represented by the internal node. This process can continue for all internal nodes until the root node is executed and replaced by the result table, which can be returned as query results.

A single query can be executed through different algorithms or re-written in different forms and represented in different query tree structures by the query optimizer. Specifically, the query optimizer can use various equivalence rules to generate many different relational algebra expressions for the same query. An equivalence rule ensures that expressions of two forms are the same or equivalent because both expressions produce the same output. These different relational algebra expressions (which have different query tree structures) generate the same output to the query. Thus, different query trees associated with these different relational algebra expressions represent different query plans (also referred to as "candidate query plans") for the query. For simplicity, the nodes of a query tree representing a query plan can also be referred to as nodes of the query plan as described hereinafter.

The aim of a query optimizer is to select a query plan (from many candidate query plans) that yields optimal performance. Performance of a query plan can be described in terms of cost, which can be time (e.g., time required to execute the query plan) and/or burden on computing resources (e.g., processing power and/or memory expended to execute the query plan). Cost-based query optimization chooses the query plan with the lowest cost among all candidate query plans. In practice, although the terms "optimal" and "optimize" are used, the actual best plan may not be selected, but the selected plan is deemed better than others based on data available to the optimizer.

To evaluate a cost of a query plan, the query optimizer can estimate data statistics for nodes of the query plan, and use such statistics in a cost model to calculate the cost of the query plan. Some statistics, e.g., cardinality, can indicate size of tables. Some statistics, e.g., distinct count, skewness, etc., can indicate data distribution within tables.

However, errors can be introduced when estimating data statistics, especially for internal nodes of the query trees. For example, while data statistics of leaf nodes can be accurately obtained by scanning the tables represented by the leaf nodes, result tables of the internal nodes are not available before executing the query plan and must be estimated. Estimation of data statistics (e.g., cardinality, distinct count, skewness, etc.) associated with internal nodes can be error prone if some assumptions are not true. For example, for size estimation of a result table of an internal node involving filtering of two attributes (e.g., data columns), selectivity of the two filters can be multiplied if the two attributes are independent. However, if the two attributes are correlated to each other, then multiplying selectivity of the two filters can introduce errors. As another example, although a histogram is often used to characterize data statistics in query trees, a histogram is not suited to represent statistics for highly skewed data (e.g., top-k value list may not capture the skewness of a data column). Sampling is another approach for estimating data statistics in query trees, particularly when dealing with large tables. However, statistics of sampled data may not represent statistics of the large tables when the data is under-sampled (e.g., some data may have zero sample when the distinct count is large). Furthermore, the estimation error of statistics introduced in one internal node can be cascaded/propagated to a parent node of the internal node, thus amplifying the estimation error of statistics associated with the parent node. As a result, the calculated cost of query plans may not be accurate, and the query plan generated by the query optimizer may be sub-optimal.

The technology described herein provides a system and method for runtime statistics feedback for query plan cost estimation. Such system and method provide more accurate estimation of data statistics of query plans in an efficient manner, thus improving cost-based query plan optimization schemes in DBMS.

<FIG> shows an overall block diagram of an example database management system <NUM> that can accurately and efficiently calculate query plan cost based on runtime statistic feedback.

As shown, the database management system <NUM> includes an SQL query processor <NUM> configured to receive an incoming SQL query <NUM> (or simply "query") and generate query results <NUM> in response to the received query <NUM>. The SQL query processor <NUM> can include a cache manager <NUM>, a query parser <NUM>, a query optimizer <NUM>, a query plan executor <NUM>, and a plan cache <NUM>. The plan cache <NUM> represents a fast-access memory space configured to store previously compiled query plans.

An incoming query <NUM> can be evaluated by the cache manager <NUM> to determine if the query <NUM> has a corresponding (compiled) query execution plan stored in the plan cache <NUM> (e.g., by looking up the plan cache <NUM>). If the cache manager <NUM> finds no query execution plan in the plan cache <NUM> that corresponds to the query <NUM>, the query <NUM> can be parsed, checked, and preprocessed by the query parser <NUM> to determine if the query <NUM> contains syntactic and/or semantic errors. After verifying that the query <NUM> is a valid transactional SQL statement that changes data (e.g., SELECT, INSERT, UPDATE, DELETE, MERGE, etc.), the query parser <NUM> can generate one or more query trees. Each query tree represents a corresponding query plan, which determines how the query <NUM> will be executed. The query optimizer <NUM>, as described further below, is configured to determine that, among a plurality of query plans that are generated based on respective query trees, which query plan is deemed to be the most optimal or efficient one (e.g., the one that is cheapest in terms of query cost calculated based on CPU usage, memory usage, etc.).

The determined query plan (e.g., denoted as <NUM>) which is deemed to be the most optimal can be sent to the query plan executor <NUM> for execution. The query plan executor <NUM> can communicate with a data storage or memory space (e.g., a data persistency layer <NUM>) and execute operators in the query plan <NUM> determined by the query optimizer <NUM>.

As described herein, query compilation refers to the process of converting an incoming query <NUM> to the optimal query plan <NUM> (e.g., checking syntactic and/or semantic errors, generating query trees, and determining optimal query plan), as described above. Depending on the complexity of the query <NUM> (e.g., the number of joined tables, etc.) and the query optimization algorithm, query compilation time can be long (e.g., tens of seconds or more). Thus, to improve operational efficiency, the compiled optimal query plan <NUM> corresponding to the incoming query <NUM> can be stored in the plan cache <NUM> so that it can be quickly retrieved and reused if the same query <NUM> is submitted again in the future.

For example, if the cache manager <NUM> determines that the incoming query <NUM> has a corresponding query plan in the plan cache <NUM>, that query plan can be retrieved directly from the plan cache <NUM> and forwarded to the query plan executor <NUM> for execution. Thus, in this scenario, operations by the query parser <NUM> and query optimizer <NUM> can be bypassed. In other words, the incoming query <NUM> does not need to be recompiled because its previously compiled query plan <NUM> is available in the plan cache <NUM>.

As noted above, the plan cache <NUM> can store compiled query plans (e.g., <NUM>). For an incoming query, the cache manager <NUM> can check if it has a compiled query execution plan stored in the plan cache <NUM>. If yes, then this cached query plan can be reused. This can improve efficiency because it eliminates the time of compiling the query (i.e., regenerating the query plan). On the other hand, if the query has no compiled query plan stored in the plan cache <NUM>, the query has to be compiled and optimized. The compiled optimal query plan <NUM> can then be stored in the plan cache <NUM> so that when the same query occurs again in the future, fast access to its cached query plan is feasible. In other words, the plan cache <NUM> can improve performance by keeping recent or often-used query plans in its cache memory which is faster or computationally cheaper to access than normal memory stores.

As described herein, the query optimizer <NUM> can be configured to implement a cost-based query optimization scheme. As shown, the query optimizer <NUM> can include a logical plan rewriter <NUM>, a plan size estimator <NUM>, a plan enumeration and algorithm assignment unit <NUM>, a cost-based plan selector <NUM>, and a runtime feedback manager <NUM>. The runtime feedback manager <NUM> can further include a dictionary <NUM> and a storage for runtime statistics <NUM>, as described more fully below.

The logical plan rewriter <NUM> can be configured to rewrite the original query (e.g., <NUM>) to use materialized views (which contain already precomputed aggregates and joins) so as to improve operating efficiency. For example, rewriting the query can reduce the number of operations (e.g., by merging query operations, removing redundant joins, etc.).

The plan size estimator <NUM> can be configured to perform cost-bounded enumeration and size estimation. Specifically, the plan enumeration and algorithm assignment unit <NUM> can be configured to enumerate, within the constraint of a predefined cost threshold, a plurality of logical query plans (represented by query trees) to perform the query, and further generate physical query plans by annotating logical query plans with physical implementation details (e.g., by using relational algebra algorithms). Based on the generated logical and physical plans, the plan size estimator <NUM> can estimate or calculate the size of query plans. Then, the cost-based plan selector <NUM> can select the query plan <NUM> having the lowest estimated/calculated cost.

The runtime feedback manager <NUM> can be configured to capture the query tree representing the query plan selected by the cost-based plan selector <NUM>. Additionally, the runtime feedback manager <NUM> can be configured to collect data statistics obtained after the selected query plan <NUM> is executed by the query plan executor <NUM>. The collected data statistics is stored in the runtime statistics <NUM> and mapped to the dictionary <NUM>. As described more fully below, the dictionary <NUM> includes a plurality of keys corresponding to nodes of the query trees generated by the plan size estimator <NUM>. The plan size estimator <NUM> searches the dictionary <NUM> for matching keys (and the corresponding statistics) for selected nodes in a query tree. The runtime statistics collected from executing the previous query plan are feedbacked to the plan size estimator <NUM> for improved cost estimation when optimizing the next query. Additionally, the plan size estimator <NUM> identifies alternative subtrees for any selected internal node of a query tree and propagate statistics across respective roots of the alternative subtrees, as described further below. In some circumstances, the dictionary <NUM> and runtime statistics <NUM> can be further stored in the persistency layer <NUM>.

In practice, the systems shown herein, such as system <NUM>, can vary in complexity, with additional functionality, more complex components, and the like. For example, there can be additional functionality within the SQL query processor <NUM>. Additional components can be included to implement security, redundancy, load balancing, report design, and the like.

The described computing systems can be networked via wired or wireless network connections, including the Internet. Alternatively, systems can be connected through an intranet connection (e.g., in a corporate environment, government environment, or the like).

The system <NUM> and any of the other systems described herein can be implemented in conjunction with any of the hardware components described herein, such as the computing systems described below (e.g., processing units, memory, and the like). In any of the examples herein, the statistics (e.g., cardinalities, etc.), the query trees, the keys, the dictionary, and the like can be stored in one or more computer-readable storage media or computer-readable storage devices. The technologies described herein can be generic to the specifics of operating systems or hardware and can be applied in any variety of environments to take advantage of the described features.

<FIG> is a flowchart illustrating an overall method <NUM> of implementing runtime statistics feedback for query plan cost estimation, and can be performed, for example, by the system of <FIG>. In one specific example, the method <NUM> can be implemented by the query optimizer <NUM> depicted in <FIG>.

At <NUM>, a first query plan (e.g., a query plan <NUM> selected by the query optimizer <NUM>) for a query is executed (e.g., by the query plan executor <NUM>).

At <NUM>, statistics for one or more internal nodes of a first query tree representing the first query plan are obtained. As described above, such runtime statistics are stored (e.g., by the runtime feedback manager <NUM>) and mapped to a dictionary (e.g., <NUM>) containing keys representing internal nodes of the query tree.

At <NUM>, a second query tree representing a second query plan for the query is received. The second query tree can be the same as or different from the first query tree.

At <NUM>, for a selected internal node of the second query tree, the method <NUM> searches for a matching internal node out of the one or more internal nodes of the first query.

Then at <NUM>, responsive to finding the matching internal node of the first query tree, the statistics for the matching internal node of the first query tree are applied to the selected internal node of the second query tree for estimating cost of the second query plan during query optimization of the query.

To illustrate, <FIG> schematically depicts a query optimizer <NUM> implementing the method <NUM>. In the depicted example, the query optimizer <NUM> generates an initial query tree <NUM> representing an initial query plan for a query. The initial query tree <NUM> has a root node <NUM>, two internal nodes <NUM>, <NUM>, and three leaf nodes <NUM>, <NUM>, <NUM>. One of the internal nodes <NUM> is a child of the root node <NUM> and defines a subtree <NUM> (e.g., the node <NUM> is a root of the subtree <NUM>). Using an equivalence rule, the query optimizer <NUM> finds an alternative or equivalent subtree <NUM> (having a root node <NUM>) that is logically equivalent to the subtree <NUM>. That is, executing the two subtrees <NUM> and <NUM> produces the same results. Thus, the query optimizer <NUM> can permute the initial query tree <NUM> to a permuted query tree <NUM> by replacing the subtree <NUM> with the equivalent subtree <NUM>. The permuted query tree <NUM> represents an alternative query plan for the query.

The query optimizer <NUM> can calculate and compare costs of the initial query plan and the alternative query plan based on estimated statistics of nodes in the query trees <NUM>, <NUM>. Although statistics of the leaf nodes (e.g., <NUM>, <NUM>, <NUM>) can be accurately calculated by scanning tables represented by the leaf nodes, estimating statistics for the internal nodes (e.g., <NUM>, <NUM>, <NUM>, etc.) may introduce errors, as described above. Without any runtime statistics feedback, the query optimizer <NUM> can initially estimate statistics for the internal nodes, based on which to perform initial cost estimations for the initial query plan and the alternative query plan. In the depicted example, the alternative query plan represented by the permuted query tree <NUM> has a lower cost than the initial query plan represented by the initial query tree <NUM>, and is selected for execution.

When the alternative query plan represented by the permuted query tree <NUM> is executed, data statistics can be collected for the internal nodes of the query tree <NUM>. Such collected statistics can be used to assist subsequent query optimization for the query.

For example, assuming for the subsequently received query, the query optimizer <NUM> generates an initial query tree <NUM> representing an initial query plan for the query. In the depicted example, the initial query tree <NUM> is identical to the previously executed query tree <NUM>. In other examples, the initial query tree <NUM> can be different from the previously executed query tree <NUM>. As shown, the initial query tree <NUM> has a root node <NUM>, two internal nodes <NUM>, <NUM>, and three leaf nodes <NUM>, <NUM>, <NUM>. Using an equivalence rule, the query optimizer <NUM> finds an alternative subtree <NUM> (having a root node <NUM>) that is logically equivalent to the subtree <NUM> of the internal node <NUM>. Thus, the query optimizer <NUM> can permute the initial query tree <NUM> to a permuted query tree <NUM> by replacing the subtree <NUM> with the alternative subtree <NUM>. The permuted query tree <NUM> represents an alternative query plan for the query.

Runtime statistics collected from the query tree <NUM> are used to estimate data statistics for the query trees <NUM>, <NUM>. For example, for some of the internal nodes (e.g., <NUM>, <NUM>, <NUM>, etc.) in the query trees <NUM>, <NUM>, matching nodes can be found in the previously executed query tree <NUM> (the method of finding matching nodes are described more fully below). Accordingly, runtime statistics collected from the internal nodes of the query tree <NUM> are used to more accurately (compared to no runtime statistics feedback) determine statistics for the internal nodes of the query trees <NUM>, <NUM>. Based on more accurate data statistics, the query optimizer <NUM> can more accurately calculate the costs of different query plans. In the depicted example, the query plan represented by the query tree <NUM> has a lower cost than the query plan represented by the query tree <NUM>, and is selected for execution.

Similarly, when the query plan represented by the query tree <NUM> is executed, data statistics can be collected for the internal nodes of the query tree <NUM>, and such runtime statistics can be used to assist subsequent query optimization for the query. In other words, the runtime statistics feedback can be iterated.

Because the runtime statistics collected from the executed query plans can more accurately reflect data statistics of the internal nodes in the query trees, cost-based query optimization can be more accurate and adaptive. For example, when tables involved in a query are relatively stable (e.g., sizes and/or data distributions of the tables remain relatively stable), after one or more iterations, the query plan selected by the query optimizer <NUM> can converge to the optimal query plan having the lowest cost. On the other hand, when tables involved in a query change dynamically (e.g., sizes and/or data distributions of the tables change over time), iterations of runtime statistics feedback allow the query optimizer to adapt to the dynamic changes of the tables, thereby consistently selecting the optimal or nearly optimal query plan having the lowest or nearly lowest cost.

The method <NUM> and any of the other methods described herein can be performed by computer-executable instructions (e.g., causing a computing system to perform the method) stored in one or more computer-readable media (e.g., storage or other tangible media) or stored in one or more computer-readable storage devices. Such methods can be performed in software, firmware, hardware, or combinations thereof. Such methods can be performed at least in part by a computing system (e.g., one or more computing devices).

The illustrated actions can be described from alternative perspectives while still implementing the technologies. For example, "receive" can also be described as "send" from a different perspective.

To illustrate, <FIG> depicts three query trees <NUM>, <NUM>, <NUM> representing three different query plans generated for the same query.

As shown, the query tree <NUM> include two leaf nodes <NUM>, <NUM> representing two tables (T1 and T2) and three internal nodes <NUM>, <NUM>, <NUM> representing three different operations (Filter1, Index Join, and Filter2, respectively). The query tree <NUM> also includes the same leaf nodes <NUM>, <NUM> and internal nodes <NUM>, <NUM>', <NUM>, but have a different topology or logical structure than the query tree <NUM>. For example, while the internal node <NUM> representing Filter2 is the root node of query tree <NUM>, the internal node <NUM> representing Filter1 is the root node of query tree <NUM>. The query tree <NUM> also includes two leaf nodes <NUM> and <NUM>, and three internal nodes <NUM>, <NUM>, <NUM>. Different from query trees <NUM>, <NUM>, the root node <NUM> of query tree <NUM> represents a Hash Join operation.

The three query trees <NUM>, <NUM>, <NUM> represent different logical sequences to execute the query. For example, according the query plan represented by the query tree <NUM>, table T1 (<NUM>) is first filtered by Filter1 (<NUM>). The resulting table of <NUM> is then joined with the table T2 (<NUM>) via Index Join (<NUM>). The resulting table of <NUM> is then filtered by Filter2 (<NUM>). The result of <NUM> is the query result. According to the query plan represented by the query tree <NUM>, table T2 (<NUM>) is first filtered by Filter2 (<NUM>). The resulting table of <NUM> is then joined with the table T1 (<NUM>) via Index Join (<NUM>'). The resulting table of <NUM>' is then filtered by Filter1 (<NUM>). The result of <NUM> is the query result. According to the query plan represented by the query tree <NUM>, table T1 (<NUM>) is filtered by Filter1 (<NUM>) and table T2 (<NUM>) is filtered by Filter2 (<NUM>). The resulting tables of <NUM> and <NUM> are then joined together via Hash Join (<NUM>). The resulting table of <NUM> is the query result.

Although statistics of the leaf nodes <NUM>, <NUM> can be accurately calculated by scanning tables T1 and T2, statistics for the resulting tables of the internal nodes (e.g., <NUM>, <NUM>, <NUM>', <NUM>, <NUM>, etc.) are not available unless a query plan involving such internal nodes are executed. Without any runtime statistics feedback, a query optimizer can initially estimate statistics for the internal nodes, based on which to perform cost estimations for the corresponding query plans. Such estimated statistics can introduce errors (e.g., due to dependency between attributes, skewed data distribution, etc.), as described above. As a result, the cost estimatation may be inaccurate and sub-optimal query plan may be selected. For example, the query optimizer may improperly select either the query plan represented by query tree <NUM> or the query plan represented by query tree <NUM> for execution, even though the query plan represented by query tree <NUM> would have the lowest actual cost (e.g., associated with the best performance and/or lowest execution time, etc.) if executed.

Using runtime statistics feedback as described above, statistics for the internal nodes of the query trees can be more accurately determined. As a result, even if the initially selected query plan is sub-optimal (e.g., a query plan represented by the query tree <NUM> or <NUM> is selected), after one or more iterations, the query optimizer can converge to the optimal query plan represented by the query tree <NUM>.

As another example, <FIG> depicts two query trees <NUM>, <NUM> representing two different query plans generated for the same query.

As shown, the query tree <NUM> include two leaf nodes <NUM>, <NUM> representing two tables (T1 and T2) and three internal nodes <NUM>, <NUM>, <NUM> representing three different operations (Filter, Hash Join, and Group-By, respectively). The query tree <NUM> also includes the same leaf nodes <NUM>, <NUM> and internal nodes <NUM>, <NUM>, <NUM>. In addition, the query tree <NUM> includes a new internal node <NUM>' which also represents a Group-By operation.

In some circumstances, the query optimizer can permutate the query tree <NUM> to generate the query tree <NUM> using relational algebra algorithms, and indicate the internal node <NUM>' represents a pre-aggregation of the Group-By operation represented by the internal node <NUM>. The Group-By operations represented by <NUM> and <NUM>' share certain same grouping attributes or columns (the Group-By operation represented by <NUM>' can have additional grouping columns than the Group-By operation represented by <NUM>). In such circumstances, the query optimizer can deem the two Group-By operations represented by internal nodes <NUM> and <NUM>' share the same grouping selectivity. The grouping selectivity is a ratio of number of records satisfying the Group-By operation (e.g., output rows) to number of total records (e.g., input rows). Thus, if the grouping selectivity is known for the internal node <NUM>, the same grouping selectivity can be applied to the internal node <NUM>', or vice versa.

Sharing grouping selectivity between internal nodes representing Group-By operations can be helpful for cost estimation of query plans. For example, after execution of a query plan represented by the query tree <NUM>, statistics can be collected for the internal nodes <NUM>, <NUM>, and <NUM>. When evaluating the cost of a subsequent query plan represented by the query tree <NUM>, collected runtime statistics for the internal nodes <NUM>, <NUM>, and <NUM> can be used to determine statistics for the same internal nodes in the query tree <NUM>. The statistics for the new internal node <NUM>' can be derived from the internal node <NUM>. For example, if the measured cardinality for the node <NUM> is C and the grouping selectivity for the node <NUM> is S, then the cardinality for the node <NUM>' can be determined to be C × S because the nodes <NUM> and <NUM>' share the same grouping selectivity S, and the input to node <NUM>' is the result table of node <NUM>.

According to certain examples, nodes of a query tree representing a previously executed query plan can be represented as corresponding keys and registered in a dictionary (e.g., <NUM>). Collected runtime statistics (e.g., cardinality, distinct count, etc.) for the nodes can be mapped to respective keys in the dictionary. An example method of registering nodes of a query tree in a dictionary is described herein with reference to <FIG>.

<FIG> depicts an example query tree <NUM> representing an executed query plan for a query. The query tree <NUM> includes five leaf nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) and eight internal nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) including the root node <NUM>. Each node in the query tree <NUM> can be represented by a unique key and registered in a dictionary <NUM>. An example method of generating unique keys for the nodes is described further below.

The registration process can use a bottom-up approach, starting with the leaf nodes and ending with the root node. For example, each of the leaf nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>) can be represented by a key having a unique key identifier (e.g., <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>) and registered in the dictionary <NUM>. In the depicted example, the key identifiers are numeric. In other examples, the key identifiers can have other data formats so long as they can uniquely identify the corresponding nodes.

After the leaf nodes are registered, internal nodes that are parents of the leaf nodes can be registered. For example, the internal node <NUM>, which is the parent of leaf nodes <NUM> and <NUM>, can be registered with a key identifier <NUM>. The internal node <NUM>, which is the parent of leaf node <NUM>, can be registered with a key identifier <NUM>. The internal node <NUM>, which is the parent of leaf node <NUM>, can be registered with a key identifier <NUM>. In the depicted example, the key identifiers of child nodes for each internal node are shown in a pair of square brackets to denote the parent-child relationship between registered nodes.

Next, the parent nodes of these newly registered internal nodes can be registered. For example, the internal node <NUM>, which is the parent of the internal node <NUM>, can be registered with a key identifier <NUM>. The internal node <NUM>, which is the parent of the internal nodes <NUM> and <NUM>, can be registered with a key identifier <NUM>. Similar process can be repeated until the root node is registered. For example, the internal node <NUM>, which is the parent of the internal node <NUM> and leaf node <NUM>, can be registered with a key identifier <NUM>. The internal node <NUM>, which is the parent of the internal nodes <NUM> and <NUM>, can be registered with a key identifier <NUM>. Finally, the root node <NUM>, which is the parent of the internal node <NUM>, can be registered with a key identifier <NUM>.

As described above, collected runtime statistics for the nodes can be mapped to respective keys in the dictionary. For example, runtime statistics for the internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> can be mapped to respective keys with key identifiers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In certain examples, runtime statistics for the leaf nodes <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> can also be mapped to respective keys with key identifiers <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In some examples, keys representing leaf nodes do not need to be mapped to runtime statistics. Instead, statistics for the leaf nodes can be calculated directly and on-demand (when estimating the cost of the query tree) by scanning the tables represented by the leaf nodes.

As described herein, each internal node represents an operation based on child nodes of the internal node. In various examples, the key for each internal node can be generated based on the operation represented by the internal node and child nodes of the internal node. The operation can be characterized by an operator and one or more operands. Example operands include column names (or attributes) of tables represented by the child nodes, numerical values representing limits and/or offsets, predicate strings for JOIN operations, expression strings for data filters, lists of strings for UNION column expression, lists of strings for aggregate functions, lists of strings for grouping expressions, lists of strings for sorting specification, etc..

As an example, <FIG> shows a generated key <NUM>, which includes an operation signature <NUM> and a child key set <NUM>. The operation signature <NUM> can include an operator name <NUM> (e.g., JOIN) and operation details <NUM>. The operation details <NUM> can include detailed information about operands of the operator. In certain examples, the operation details <NUM> can be expressed in a string format. In other examples, the operation details <NUM> can be serialized into a byte stream. As depicted in <FIG>, the operation details <NUM> can be represented by a hash value by applying a hash function to the operands.

The child key set <NUM> can include a list of key identifiers corresponding to the child nodes of the internal node. For example, the example key <NUM> has a child key set [<NUM>, <NUM>], indicating the internal node represented by the key <NUM> has two child nodes with key identifiers <NUM> and <NUM>, respectively.

In the depicted example, the operator name <NUM> is separate from the operation details <NUM>. In other examples, the operator name and the operands can be serialized together (e.g., the operator name and the operands can be represented by a hash value). In some examples, the child key set <NUM> can also be serialized together with the operation details.

In certain examples, when generating the key (e.g., <NUM>) for an internal node, the operation details can be normalized. Normalization can be helpful to ensure the generated key is unique for operations which are expressed differently but generate the same result. For example, the predicate order of operands having a conjunctive or disjunctive relationship can be normalized so that "A and B" and "B and A" can be represented in the same normal form. As another example, the predicate order of operands in a comparison can be normalized so that "A > B" and "B < A" can be represented in the same normal form.

In certain examples, keys can also be generated for leaf nodes of a query tree. The key for a leaf node can be configured to uniquely identify the table represented by the leaf node. For example, the key for a leaf node can be a string or a hash value generated based on the name of the table.

<FIG> depict another query tree <NUM> representing a new query plan for the same query of <FIG>. The query tree <NUM> includes five leaf nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) and eight internal nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) including the root node <NUM>. As shown, the query tree <NUM> has a different logical structure than the query tree <NUM> (e.g., the subtree <NUM> associated with the internal node <NUM> has a different logical structure than the subtree associated with the internal node <NUM>). In other examples, the new query plan can be the same as the previously executed query plan. In such circumstances, the query trees representing the new and old query plans can be the same.

<FIG> also shows three alternative subtrees <NUM>, <NUM>, and <NUM> (e.g., generated by the query optimizer using various equivalent rules), which are determined to be logically equivalent to the subtree <NUM> associated with the internal node <NUM>. Thus, each of the alternative subtrees <NUM>, <NUM>, and <NUM> can replace the subtree <NUM>, leading to different query plans that generate the same query results. As shown, the subtree <NUM> includes two leaf nodes (e.g., <NUM>, <NUM>) and three internal nodes (e.g., <NUM>, <NUM>, <NUM>) including the root node <NUM>. The subtree <NUM> includes two leaf nodes (e.g., <NUM>, <NUM>) and two internal nodes (e.g., <NUM>, <NUM>) including the root node <NUM>. The subtree <NUM> includes two leaf nodes (e.g., <NUM>, <NUM>) and three internal nodes (e.g., <NUM>, <NUM>, <NUM>) including the root node <NUM>. Because the subtrees <NUM>, <NUM>, and <NUM> are logically equivalent to the subtree <NUM>, result tables for the root nodes (e.g., <NUM>, <NUM>, <NUM>, and <NUM>) of the subtrees are identical, thus having the same data statistics.

Although <FIG> depict three alternative subtrees that are logically equivalent to the subtree <NUM>, it should be understood that the number of alternative subtrees generated by the query optimizer can be more or less than three. For example, alternative subtrees can be generated for subtrees associated with any of the internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. Generation of alternative subtrees can be iterative such that additional alternative subtrees can be generated for internal nodes of a previously generated alternative subtree. For example, additional alternative subtrees can be further generated for subtrees associated with any of the internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>.

As described above, after a query plan for a query is executed, internal nodes of a query tree (denoted as a "first query tree") representing the executed query plan are registered in a dictionary with respective keys, and collected runtime statistics (e.g., cardinality, distinct count, etc.) of the internal nodes are mapped to respective keys in the dictionary. Then, when a second query tree representing a subsequent query plan is received, the dictionary is searched to find matching internal nodes of the first query tree for at least some of the internal nodes of the second query tree. Responsive to finding a matching internal node of the first query tree for a selected internal node of the second query tree, the collected runtime statistics for the matching internal node of the first query tree are applied to the selected internal node of the second query tree for estimating cost of the second query plan during query optimization of the query. An example method for finding matching internal nodes, which also follows a bottom-up approach (e.g., from the leaf nodes to the root node), is described herein with reference to <FIG>.

The dictionary <NUM> of <FIG> is replicated in <FIG> and renumbered to <NUM>. <FIG> depicts finding matching keys in the dictionary <NUM> for leaf nodes of the query tree <NUM> and alternative subtrees <NUM>, <NUM>, <NUM>. As shown, matchings keys with key identifiers <NUM>, <NUM>, and <NUM> are found for the leaf nodes <NUM>, <NUM>, and <NUM>, respectively. In other words, leaf nodes <NUM>, <NUM>, and <NUM> depicted in <FIG> represent the same tables as the leaf nodes <NUM>, <NUM>, and <NUM> of <FIG>. Similarly, leaf nodes <NUM>, <NUM>, <NUM>, and <NUM> share a same matching key (key identifier = <NUM>), thus representing the same table as the leaf node <NUM> of <FIG>. Similarly, leaf nodes <NUM>, <NUM>, <NUM>, and <NUM> share a same matching key (key identifier = <NUM>), thus representing the same table as the leaf node <NUM> of <FIG>. The key identifiers of the matching keys can be used to construct child key sets of parent internal nodes, as described below.

As described above, keys for the leaf nodes can be generated based on table names. Thus, finding matching keys in the dictionary can be performed based on comparison of table names (or their transformed hash values, etc.) represented by the leaf nodes.

<FIG> depicts finding matching keys in the dictionary <NUM> for some of the internal nodes, e.g., <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>. To find a matching key in the dictionary <NUM> for a selected internal node, a target key can be generated for the selected internal node, using the same method described above with reference to the example key <NUM> of <FIG>. For example, the target key of the selected internal node can include an operation signature (which can include an operator name and operation details) and a child key set. The child key set can include a list of matching key identifiers corresponding to the child nodes of the internal node. In the depicted example, the internal node <NUM> has a child key set [<NUM>, <NUM>], both the internal nodes <NUM> and <NUM> share a child key set [<NUM>], and the both the internal nodes <NUM> and <NUM> share a child key set [<NUM>].

Then the dictionary <NUM> is searched to find a key that matches the target key. If it is found that the dictionary <NUM> contains a matching key for the selected internal node, previously collected runtime statistics mapped to the matching key are applied to the selected internal node. Because the matching key was generated and registered based on an internal node of the query tree <NUM>, such internal node of the query tree <NUM> can be deemed as a matching internal node for the selected internal node.

In the depicted example, the internal node <NUM> is found to have a matching key (key identifier = <NUM>), indicating the internal node <NUM> has a matching internal node <NUM> of <FIG>. It is noted that the internal nodes <NUM> and <NUM> are logically equivalent because they represent the same operation and have equivalent child nodes (e.g., child nodes <NUM>, <NUM> of the internal node <NUM> are equivalent to child nodes <NUM>, <NUM> of the internal node <NUM>). Similarly, both the internal nodes <NUM> and <NUM> are found to have a matching key (key identifier = <NUM>), indicating that both the internal nodes <NUM> and <NUM> share a matching internal node <NUM> of <FIG>. Additionally, both the internal nodes <NUM> and <NUM> are found to have a matching key (key identifier = <NUM>), indicating that both the internal nodes <NUM> and <NUM> share a matching internal node <NUM> of <FIG>. Similarly, these matching key identifiers can be used to construct child key sets of the parent internal nodes, as described above.

Using the same approach, matching keys can be found for some other internal nodes. For example, <FIG> shows that a matching key (key identifier = <NUM>) is found for the internal node <NUM> (indicating the internal node <NUM> has a matching internal node <NUM> of <FIG>), and another matching key (key identifier = <NUM>) is found for the internal node <NUM> (indicating the internal node <NUM> has a matching internal node <NUM> of <FIG>).

In some circumstances, matching keys may not be found for some of the internal nodes. This can occur, e.g., if the target key of an internal node, which is generated based on the operation signature and child key set of the internal node, does not match any of the keys registered in the dictionary <NUM>. In the example depicted in <FIG>, six internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> have no matching keys during the initial search of the dictionary <NUM>.

However, matching internal nodes <NUM>, <NUM>, <NUM>, can still be found for some of the internal nodes (e.g., <NUM>, <NUM>, <NUM>) that have no matching keys during initial search of the dictionary <NUM>. As described above, the root nodes of logically equivalent subtrees <NUM>, <NUM>, <NUM>, <NUM> generate the same result (thus having the same table statistics). Accordingly, if any of the root nodes <NUM>, <NUM>, <NUM>, and <NUM> is found to have a matching internal node in the query tree <NUM>, that same matching internal node can be shared by all of the root nodes <NUM>, <NUM>, <NUM>, and <NUM>. In the depicted example, because the internal node <NUM> has a matching internal node <NUM>, the three internal nodes <NUM>, <NUM>, and <NUM> all share the same matching internal node <NUM>. Equivalently, the matching key (key identifier = <NUM>) for the node <NUM> is propagated to the nodes <NUM>, <NUM>, and <NUM> (i.e., the matching key for the node <NUM> can be designated to the nodes <NUM>, <NUM>, and <NUM>). Thus, runtime statistics collected from the internal node <NUM> can also be applied to the internal nodes <NUM>, <NUM>, and <NUM>.

<FIG> shows that matching keys can be found for three remaining internal nodes. For example, a matching key (key identifier = <NUM>) is found for the internal node <NUM> (indicating the internal node <NUM> has a matching internal node <NUM> of <FIG>). The internal node <NUM> has two child nodes <NUM> and <NUM>. Although the initial dictionary search does not find a matching key for the child node <NUM>, because the subtrees <NUM> and <NUM> are logically equivalent, the matching key (key identifier = <NUM>) for the node <NUM> can be propagated to the node <NUM>. Thus, to construct a target key for the internal node <NUM>, the child key set of the internal node <NUM> can be set to [<NUM>, <NUM>]. As a result, a matching key (key identifier = <NUM>) can be found for the internal node <NUM> (indicating the internal node <NUM> has a matching internal node <NUM> of <FIG>). Thus, even if the initial dictionary search does not find a matching key for the node <NUM>, a target key for its parent (i.e., the internal node <NUM>) can still be generated based on a designated matching key for the node <NUM> (propagated from the node <NUM>), thereby allowing a matching key for the parent internal node <NUM> to be found. Finally, a matching key (key identifier = <NUM>) can be found for the root node <NUM> (indicating the root node <NUM> has a matching internal node <NUM> of <FIG>).

Thus, only three internal nodes (<NUM>, <NUM>, <NUM>) depicted in <FIG> do not have matching internal nodes in the query tree <NUM>. The statistics of these internal nodes (also referred to as "unmatched internal nodes") can be estimated based on any known query statistics estimation methods because no runtime statistics can be directly applied to these unmatched internal nodes. However, even without direct application of runtime statistics to the unmatched internal nodes, estimation of statistics for the unmatched internal nodes can still be more accurate than conventional approaches where no runtime statistics is used at all.

For example, statistics of a parent node can be estimated based on statistics of its child nodes. In conventional approaches, statistics for the child nodes can have large estimation errors, which can be propagated to and/or amplified when estimating statistics for the parent node. By using runtime statistics feedback technology described herein, statistics of the child nodes can be more accurately determined (e.g., negligible or no errors) if the child nodes have matching internal nodes. As a result, the estimated statistics for the parent node can be more accurate. For example, the estimated statistics for the unmatched internal nodes <NUM>, <NUM>, <NUM> can be more accurate when the runtime statistics for their respective child nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM> are available.

In addition, the estimation error of statistics for an unmatched internal node (if any) can be confined and not propagated to a parent node of the unmatched internal node, e.g., if the parent node has a matching internal node. For example, even if there are estimation errors of statistics for the unmatched internal nodes <NUM>, <NUM>, and <NUM>, such estimation errors will not be propagated to their respective parent nodes <NUM>, <NUM>, and <NUM> because runtime statistics are available for the parent nodes <NUM>, <NUM>, and <NUM>.

Further, in some circumstances, the estimation error of statistics for an unmatched internal node (if any) can be further reduced and/or capped if the parent node of the unmatched internal node has a matching internal node. For example, if there are estimation errors of table sizes (e.g., cardinalities) for the unmatched internal nodes <NUM>, <NUM>, and <NUM>, such estimation errors can be capped by the runtime table sizes collected for their respective parent nodes <NUM>, <NUM>, and <NUM>.

As described herein, the process of runtime statistics feedback can be iterative. For example, if a query plan represented by the query tree <NUM> (or another query tree) is determined to have the lowest cost and selected by the query optimizer for execution, runtime statistics can be collected for such newly executed query plan. The collected runtime statistics can be further feedbacked to determine costs of subsequent query plans for the same query. And such runtime statistics feedback process can continue.

The dictionary (e.g., <NUM>) can be dynamically be updated during the iterative runtime statistics feedback process. For example, responsive to executing the query plan represented by the query tree <NUM> as a result of query optimization of the query, runtime statistics for the internal nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) of the query tree <NUM> can be collected. A new key uniquely identifying the unmatched internal node <NUM> can be generated (using the method key generation method described above) and registered in the dictionary <NUM> (e.g., with a new key identifier <NUM>). The collected statistics for the unmatched internal node <NUM> can be mapped to the new key. Thus, by registering the new key corresponding to the unmatched internal node <NUM>, the dictionary <NUM> is expanded to facilitate subsequent query plan optimization for the same query (e.g., an internal node of a subsequent query tree may find the new key as a matching key).

In certain examples, statistics mapped to respective keys of the dictionary (e.g., <NUM>) can be dynamically updated during the iterative runtime statistics feedback process.

For example, responsive to executing the query plan represented by the query tree <NUM> as a result of query optimization of the query, runtime statistics for the internal nodes (e.g., <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>) of the query tree <NUM> can be collected. As described above, matchings keys with key identifiers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> can be respectively found for the internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> (note the matching key for the node <NUM> is propagated from the node <NUM>). For these matching keys, their mapped statistics can be updated based on newly collected statistics for the corresponding internal nodes.

For example, the newly collected statistics for the internal nodes <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM> can be mapped to the corresponding matching keys with key identifiers <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, <NUM>, and <NUM>, respectively. In such circumstances, the newly collected runtime statistics for an internal node with a matching key replace the old runtime statistics for the internal node. Thus, only the most recent runtime statistics are used for a subsequent query plan optimization.

In some examples, the newly collected runtime statistics for an internal node with a matching key can be combined with the old runtime statistics for the internal node, and such combined statistics can be mapped to the matching key. For example, the combined statistics can be a weighted average of the newly collected runtime statistics and the old runtime statistics for the internal node, where the weights for the newly collected runtime statistics and the old runtime statistics can be predefined. In such circumstances, not only the most recent runtime statistics, but also some earlier runtime statistics, can be used in the feedback for a subsequent query plan optimization.

A number of advantages can be achieved via the technology described herein. As described above, cost-based query optimization needs to estimate statistics of internal nodes of query trees representing different query plans of a query. Estimation errors can occur due to various reasons. Moreover, estimation error in one internal node can propagate to a parent node of the internal node, resulting in a cascading effect that amplifies the errors. As a result, the estimated costs of query plans may not be accurate, and the query plan selected by a query optimizer may not be optimal, and in fact, can be very expensive, e.g., in terms of usage of system resources.

The technology described herein can more accurately determine data statistics for internal nodes of the query trees, thus allowing more accurate calculation of costs of query plans for a query. Because the runtime statistics collected from the executed query plans can more accurately reflect data statistics of the internal nodes in the query trees, cost-based query optimization can be more accurate and adaptive. For example, iterative runtime statistics feedback allows the output of a query optimizer to converge to the optimal query plan having the lowest cost and/or adapt to dynamic changes of data tables involved in the query.

The improved accuracy of query plan cost estimation not only results from direct usage of runtime statistics for matching internal nodes, but also benefits from improved estimation of statistics for unmatched internal nodes. As described above, even if runtime statistics is not available for an unmatched internal node, statistics for the unmatched internal node can still be more accurately estimated because the child nodes of the unmatched internal node can have runtime statistics. Further, any error (if any) in the estimated statistics for the unmatched internal node can be capped and not propagated to the parent node of the unmatched internal node if runtime statistics is available for the parent node.

The technology described herein uses a highly efficient dictionary approach to track internal nodes of executed query plans. Each internal node of an executed query plan can be registered in the dictionary as a corresponding key, which is mapped to runtime statistics collected from the internal node. During optimization of a subsequent query plan, the dictionary can be searched to find matching keys for internal nodes of the query plan. Even if an initial search of the dictionary does not find a matching key for an internal node, the technology described herein can designate a matching key for the internal node by propagating it from an alternative node associated with a logical equivalent subtree, so long as the alternative node has a matching key. The dictionary can be dynamically updated. Thus, as more query plans are executed, more internal nodes of the query plans can be registered in the dictionary, thus facilitating subsequent query plan optimizations.

<FIG> depicts an example of a suitable computing system <NUM> in which the described innovations can be implemented. The computing system <NUM> is not intended to suggest any limitation as to scope of use or functionality of the present disclosure, as the innovations can be implemented in diverse computing systems.

With reference to <FIG>, the computing system <NUM> includes one or more processing units <NUM>, <NUM> and memory <NUM>, <NUM>. In <FIG>, this basic configuration <NUM> is included within a dashed line. The processing units <NUM>, <NUM> can execute computer-executable instructions, such as for implementing the features described in the examples herein (e.g., the method <NUM>). A processing unit can be a general-purpose central processing unit (CPU), processor in an application-specific integrated circuit (ASIC), or any other type of processor. In a multi-processing system, multiple processing units can execute computer-executable instructions to increase processing power. For example, <FIG> shows a central processing unit <NUM> as well as a graphics processing unit or co-processing unit <NUM>. The tangible memory <NUM>, <NUM> can be volatile memory (e.g., registers, cache, RAM), non-volatile memory (e.g., ROM, EEPROM, flash memory, etc.), or some combination of the two, accessible by the processing unit(s) <NUM>, <NUM>. The memory <NUM>, <NUM> can store software <NUM> implementing one or more innovations described herein, in the form of computer-executable instructions suitable for execution by the processing unit(s) <NUM>, <NUM>.

A computing system <NUM> can have additional features. For example, the computing system <NUM> can include storage <NUM>, one or more input devices <NUM>, one or more output devices <NUM>, and one or more communication connections <NUM>, including input devices, output devices, and communication connections for interacting with a user. An interconnection mechanism (not shown) such as a bus, controller, or network can interconnect the components of the computing system <NUM>. Typically, operating system software (not shown) can provide an operating environment for other software executing in the computing system <NUM>, and coordinate activities of the components of the computing system <NUM>.

The tangible storage <NUM> can be removable or non-removable, and includes magnetic disks, magnetic tapes or cassettes, CD-ROMs, DVDs, or any other medium which can be used to store information in a non-transitory way and which can be accessed within the computing system <NUM>. The storage <NUM> can store instructions for the software <NUM> implementing one or more innovations described herein.

The input device(s) <NUM> can be an input device such as a keyboard, mouse, pen, or trackball, a voice input device, a scanning device, touch device (e.g., touchpad, display, or the like) or another device that provides input to the computing system <NUM>. The output device(s) <NUM> can be a display, printer, speaker, CD-writer, or another device that provides output from the computing system <NUM>.

The communication connection(s) <NUM> can enable communication over a communication medium to another computing entity. The communication medium can convey information such as computer-executable instructions, audio or video input or output, or other data in a modulated data signal. A modulated data signal is a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media can use an electrical, optical, RF, or other carrier.

The innovations can be described in the context of computer-executable instructions, such as those included in program modules, being executed in a computing system on a target real or virtual processor (e.g., which is ultimately executed on one or more hardware processors). Generally, program modules or components can include routines, programs, libraries, objects, classes, components, data structures, etc. that perform particular tasks or implement particular abstract data types. The functionality of the program modules can be combined or split between program modules as desired in various embodiments. Computer-executable instructions for program modules can be executed within a local or distributed computing system.

For the sake of presentation, the detailed description uses terms like "determine" and "use" to describe computer operations in a computing system. These terms are high-level descriptions for operations performed by a computer, and should not be confused with acts performed by a human being. The actual computer operations corresponding to these terms vary depending on implementation.

Any of the computer-readable media herein can be non-transitory (e.g., volatile memory such as DRAM or SRAM, nonvolatile memory such as magnetic storage, optical storage, or the like) and/or tangible. Any of the storing actions described herein can be implemented by storing in one or more computer-readable media (e.g., computer-readable storage media or other tangible media). Any of the things (e.g., data created and used during implementation) described as stored can be stored in one or more computer-readable media (e.g., computer-readable storage media or other tangible media). Computer-readable media can be limited to implementations not consisting of a signal.

Any of the methods described herein can be implemented by computer-executable instructions in (e.g., stored on, encoded on, or the like) one or more computer-readable media (e.g., computer-readable storage media or other tangible media) or one or more computer-readable storage devices (e.g., memory, magnetic storage, optical storage, or the like). Such instructions can cause a computing device to perform the method. The technologies described herein can be implemented in a variety of programming languages.

<FIG> depicts an example cloud computing environment <NUM> in which the described technologies can be implemented, including, e.g., the system <NUM> and other systems herein. The cloud computing environment <NUM> can include cloud computing services <NUM>. The cloud computing services <NUM> can comprise various types of cloud computing resources, such as computer servers, data storage repositories, networking resources, etc. The cloud computing services <NUM> can be centrally located (e.g., provided by a data center of a business or organization) or distributed (e.g., provided by various computing resources located at different locations, such as different data centers and/or located in different cities or countries).

The cloud computing services <NUM> can be utilized by various types of computing devices (e.g., client computing devices), such as computing devices <NUM>, <NUM>, and <NUM>. For example, the computing devices (e.g., <NUM>, <NUM>, and <NUM>) can be computers (e.g., desktop or laptop computers), mobile devices (e.g., tablet computers or smart phones), or other types of computing devices. For example, the computing devices (e.g., <NUM>, <NUM>, and <NUM>) can utilize the cloud computing services <NUM> to perform computing operations (e.g., data processing, data storage, and the like).

In practice, cloud-based, on-premises-based, or hybrid scenarios can be supported.

Although the operations of some of the disclosed methods are described in a particular, sequential order for convenient presentation, such manner of description encompasses rearrangement, unless a particular ordering is required by specific language set forth herein. For example, operations described sequentially can in some cases be rearranged or performed concurrently.

Claim 1:
A computer-implemented method (<NUM>) comprising:
executing (<NUM>) a first query plan (<NUM>) for a query;
obtaining (<NUM>) statistics for one or more internal nodes (<NUM>, <NUM>) of a first query tree (<NUM>) representing the first query plan (<NUM>);
receiving (<NUM>) a second query tree (<NUM>) representing a second query plan for the query;
for a selected internal node of the second query tree (<NUM>), searching (<NUM>) for a matching internal node out of the one or more internal nodes of the first query tree (<NUM>); and
responsive to finding the matching internal node of the first query tree (<NUM>), applying (<NUM>) the statistics for the matching internal node of the first query tree (<NUM>) to the selected internal node of the second query tree (<NUM>) for estimating cost of the second query plan during query optimization of the query;
further comprising:
generating keys uniquely identifying the one or more internal nodes of the first query tree (<NUM>);
registering the keys in a dictionary (<NUM>); and
mapping the keys to respective statistics for the one or more internal nodes of the first query tree (<NUM>);
wherein searching for the matching internal node comprises:
using an equivalence rule to select an alternative subtree (<NUM>) that is logically equivalent to a subtree (<NUM>) of the selected internal node of the second query tree (<NUM>);
generating a target key for a root of the alternative subtree (<NUM>); and
searching the dictionary (<NUM>) for a key that matches the target key.