Runtime statistics feedback for query plan cost estimation

1. A computer-implemented method comprising:

executing a first query plan for a query;

obtaining statistics for one or more internal nodes of a first query tree representing the first query plan;

receiving a second query tree representing a second query plan for the query;

for a selected internal node of the second query tree, searching for a matching internal node out of the one or more internal nodes of the first query tree;

responsive to finding the matching internal node of the first query tree, applying the statistics for the matching internal node of the first query tree to the selected internal node of the second query tree for estimating cost of the second query plan during query optimization of the query;

identifying a first internal node and a second internal node of the second query tree, wherein the first internal node represents a group-by operation having a known selectivity, wherein the second internal node represents a pre-aggregation of the group-by operation represented by the first internal node; and

applying the known selectivity of the first internal node to the second internal node.

2. The method of claim 1 , wherein obtaining statistics for an internal node of the first query tree comprises determining a cardinality of a table resulted from an operation represented by the internal node after executing the first query plan.

3. The method of claim 1 , further comprising:

generating keys uniquely identifying the one or more internal nodes of the first query tree;

registering the keys in a dictionary; and

mapping the keys to respective statistics for the one or more internal nodes of the first query tree.

4. The method of claim 3 , wherein generating a key for an internal node of the first query tree comprises generating a signature for an operation represented by the internal node and identifying child nodes of the internal node.

5. The method of claim 4 , wherein generating the signature comprises:

identifying an operator, one or more operands, and a predicate order of the one or more operands defined by the operation; and

normalizing the predicate order of operands having a conjunctive or disjunctive relationship.

6. The method of claim 3 , wherein searching for the matching internal node comprises:

generating a target key for the selected internal node of the second query tree; and

searching the dictionary for a key that matches the target key.

7. The method of claim 3 , wherein searching for the matching internal node comprises:

selecting an alternative subtree that is logically equivalent to a subtree of the selected internal node of the second query tree;

generating a target key for a root of the alternative subtree; and

searching the dictionary for a key that matches the target key.

8. The method of claim 3 , further comprising:

responsive to executing the second query plan as a result of query optimization of the query, obtaining statistics for one or more internal nodes of the second query tree;

identifying an unmatched internal node of the second query tree that has no matching internal node of the first query tree;

generating a new key uniquely identifying the unmatched internal node;

registering the new key in the dictionary; and

mapping the new key to the statistics for the unmatched internal node of the second query tree.

9. The method of claim 3 , further comprising:

responsive to executing the second query plan as a result of query optimization of the query, obtaining statistics for one or more internal nodes of the second query tree;

finding a matching key in the dictionary identifying the matching internal node of the first query tree corresponding to the selected internal node of the second query tree; and

mapping the matching key to the statistics for the selected internal node of the second query tree.

10. A computing system, comprising:

memory;

one or more hardware processors coupled to the memory; and

one or more computer readable storage media storing instructions that, when loaded into the memory, cause the one or more hardware processors to perform operations comprising:

executing a first query plan for a query;

obtaining statistics for one or more internal nodes of a first query tree representing the first query plan;

receiving a second query tree representing a second query plan for the query;

for a selected internal node of the second query tree, searching for a matching internal node out of the one or more internal nodes of the first query tree;

responsive to finding the matching internal node of the first query tree, applying the statistics for the matching internal node of the first query tree to the selected internal node of the second query tree for estimating cost of the second query plan during query optimization of the query;

identifying a first internal node and a second internal node of the second query tree, wherein the first internal node represents a group-by operation having a known selectivity, wherein the second internal node represents a pre-aggregation of the group-by operation represented by the first internal node; and

applying the known selectivity of the first internal node to the second internal node.

11. The system of claim 10 , wherein the statistics for an internal node of the first query tree comprises a cardinality of a table resulted from an operation represented by the internal node after executing the first query plan.

12. The system of claim 10 , wherein the operations further comprise:

generating keys uniquely identifying the one or more internal nodes of the first query tree;

registering the keys in a dictionary; and

mapping the keys to respective statistics for the one or more internal nodes of the first query tree.

13. The system of claim 12 , wherein a key for an internal node of the first query tree comprises a signature for an operation represented by the internal node and identifiers of child nodes of the internal node.

14. The system of claim 13 , wherein the signature comprises an operator and operands defined by the operation, wherein operands having a conjunctive or disjunctive relationship are normalized.

15. The system of claim 12 , wherein the operation for searching for the matching internal node comprises:

generating a target key for the selected internal node of the second query tree,

searching the dictionary for a key that matches the target key.

16. The system of claim 12 , wherein the operation for searching for the matching internal node comprises:

selecting an alternative subtree that is logically equivalent to a subtree of the selected internal node of the second query tree;

generating a target key for a root of the alternative subtree; and

searching the dictionary for a key that matches the target key.

17. The system of claim 12 , wherein the operations further comprise:

responsive to executing the second query plan as a result of query optimization of the query, obtaining statistics for one or more internal nodes of the second query tree;

identifying an unmatched internal node of the second query tree that has no matching internal node of the first query tree;

generating a new key uniquely identifying the unmatched internal node;

registering the new key in the dictionary; and

mapping the new key to the statistics for the unmatched internal node of the second query tree.

18. The system of claim 12 , wherein the operations further comprise:

responsive to executing the second query plan as a result of query optimization of the query, obtaining statistics for one or more internal nodes of the second query tree;

finding a matching key in the dictionary identifying the matching internal node of the first query tree corresponding to the selected internal node of the second query tree; and

mapping the matching key to the statistics for the selected internal node of the second query tree.

19. One or more non-transitory computer-readable media having encoded thereon computer-executable instructions causing one or more processors to perform a method comprising:

executing a first query plan for a query;

obtaining cardinalities for one or more internal nodes of a first query tree representing the first query plan;

receiving a second query tree representing a second query plan for the query;

for a selected internal node of the second query tree, searching for a matching internal node out of the one or more internal nodes of the first query tree;

responsive to finding the matching internal node of the first query tree, applying the cardinality for the matching internal node of the first query tree to the selected internal node of the second query tree for estimating cost of the second query plan during query optimization of the query;

identifying a first internal node and a second internal node of the second query tree, wherein the first internal node represents a group-by operation having a known selectivity, wherein the second internal node represents a pre-aggregation of the group-by operation represented by the first internal node; and

applying the known selectivity of the first internal node to the second internal node.