Estimating rows returned by recursive queries using fanout
In an embodiment, a recursive query is received that comprises a first select statement with a seed select statement and a second select statement with a recursive reference, wherein the recursive query further identifies at least two columns in at least one table, wherein the at least two columns have parent-child relationships represented by nodes in a graph, wherein the graph represents the organization of values in rows in the at least one table. A target recursion depth is calculated for the graph based on a fanout of the graph. In an embodiment, the target recursion depth is calculated by summing the fanout at each recursion depth of the graph multiplied by a number of nodes at each recursion depth of the graph. An estimated number of rows that the recursive query will return is estimated based on the target recursion depth.
1. A method comprising:
receiving a recursive query that comprises a first select statement with a seed select statement and a second select statement with a recursive reference, wherein the recursive query further identifies at least two columns in at least one table, wherein the at least two columns have parent-child relationships represented by nodes in a graph, wherein the graph represents an organization of values in rows in the at least one table;
calculating a target recursion depth for the graph based on a fanout of the graph, wherein the calculating the target recursion depth further comprises summing the fanout at each recursion depth of the graph multiplied by a number of nodes at the each recursion depth of the graph;
estimating an estimated number of rows that the recursive query will return to a result set based on the target recursion depth; and
selecting a selected query plan from among a plurality of query plans based the estimated number of rows.
2. The method of claim 1 , wherein an aggregation of the each recursion depth of the graph, for which the summing is performed, comprises all recursion depths of the graph that comprise half of all of the nodes in the graph.
3. The method of claim 1 , wherein an aggregation of the each recursion depth of the graph, for which the summing is performed, comprises all recursion depths of the graph that comprise all of the nodes in the graph.
4. The method of claim 3 , wherein the calculating the target recursion depth further comprises:
calculating a weighted average of the number of nodes at the each recursion depth, up to the target recursion depth.
5. The method of claim 4 , wherein a weight for the number of nodes at the each recursion depth is the each recursion depth.
6. The method of claim 1 , wherein the recursive query further comprises a third select statement, and wherein the estimating further comprises:
calculating a selectivity of the third select statement.
7. The method of claim 6 , wherein the estimating further comprises:
recursively computing a product of the fanout of the graph multiplied by a number of rows at the each recursion depth of the graph and multiplied by the selectivity, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.
8. The method of claim 1 , wherein the estimating further comprises:
iteratively computing a product of a fanout of the graph multiplied by a number of rows at the each recursion depth of the graph, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.
9. A computer-readable storage medium encoded with instructions, wherein the instructions when executed comprise:
receiving a recursive query that comprises a first select statement with a seed select statement and a second select statement with a recursive reference, wherein the recursive query further identifies at least two columns in at least one table, wherein the at least two columns have parent-child relationships represented by nodes in a graph, wherein the graph represents an organization of values in rows in the at least one table;
calculating a target recursion depth for the graph based on a fanout of the graph, wherein the calculating the target recursion depth further comprises summing the fanout at each recursion depth of the graph multiplied by a number of nodes at the each recursion depth of the graph;
estimating an estimated number of rows that the recursive query will return to a result set based on the target recursion depth; and
selecting a selected query plan from among a plurality of query plans based the estimated number of rows.
10. The computer-readable storage medium of claim 9 , wherein an aggregation of the each recursion depth of the graph, for which the summing is performed, comprises all recursion depths of the graph that comprise half of all of the nodes in the graph.
11. The computer-readable storage medium of claim 9 , wherein an aggregation of the each recursion depth of the graph, for which the summing is performed, comprises all recursion depths of the graph that comprise all of the nodes in the graph.
12. The computer-readable storage medium of claim 11 , wherein the calculating the target recursion depth further comprises:
calculating a weighted average of the number of nodes at the each recursion depth, up to the target recursion depth, wherein a weight for the number of nodes at the each recursion depth is the each recursion depth.
13. The computer-readable storage medium of claim 9 , wherein the recursive query further comprises a third select statement, and wherein the estimating further comprises:
calculating a selectivity of the third select statement.
14. The computer-readable storage medium of claim 13 , wherein the estimating further comprises:
recursively computing a product of the fanout of the graph multiplied by a number of rows at the each recursion depth of the graph and multiplied by the selectivity, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.
15. The computer-readable storage medium of claim 9 , wherein the estimating further comprises:
iteratively computing a product of a fanout of the graph multiplied by a number of rows at the each recursion depth of the graph, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.
16. A computer comprising:
a processor; and
memory communicatively connected to the processor, wherein the memory is encoded with instructions, and wherein the instructions when executed by the processor comprise
receiving a recursive query that comprises a first select statement with a seed select statement and a second select statement with a recursive reference, and a third select statement, wherein the recursive query further identifies at least two columns in at least one table, wherein the at least two columns have parent-child relationships represented by nodes in a graph, wherein the graph represents an organization of values in rows in the at least one table,
calculating a target recursion depth for the graph, wherein the calculating the target recursion depth further comprises calculating a logarithmic function of a fanout of the graph, a total number of rows in the at least one table, and a seed number of rows,
estimating an estimated number of rows that the recursive query will return to a result set based on the target recursion depth, and
selecting a selected query plan from among a plurality of query plans based the estimated number of rows.
17. The computer of claim 16 , wherein the logarithm function has a base of the fanout of the graph.
18. The computer of claim 16 , wherein the recursive query further comprises a third select statement, and wherein the estimating further comprises:
calculating a selectivity of the third select statement.
19. The computer of claim 18 , wherein the estimating further comprises:
recursively computing a product of the fanout of the graph multiplied by a number of rows at each recursion depth of the graph and multiplied by the selectivity, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.
20. The computer of claim 16 wherein the estimating further comprises:
iteratively computing a product of the fanout of the graph multiplied by a number of rows at each recursion depth of the graph, starting from a seed selection, for a number of times specified by the target recursion depth and summing intermediate values of the product, to yield the estimated number of rows that will be returned to the result set.