Estimating a number of rows returned by a recursive query

• US 20060235818A1
• Filed: 04/14/2005
• Published: 10/19/2006
• Est. Priority Date: 04/14/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Muras, Brian Robert
• Granted Patent: US 7,337,167 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/28 Databases characterised by their database models, e.g. relational or object models
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A method, apparatus, system, and signal-bearing medium that, in an embodiment, estimate a number of rows that a recursive query will retrieve from a table by recursively probing an index associated with the table. A recursive query includes a seed and a recursive predicate, each of which is associated with a respective column in the table. If the index has a leading column that matches the table column associated with the seed, and the index has a secondary column that matches the table column associated with the recursive predicate, then the index is recursively probed until a threshold depth of the recursive probing is reached or until all nodes of the index have been examined. The estimated number of rows that the recursive query will retrieve is then calculated based on either the number of rows examined in the index (if the threshold depth has not been reached) or based on the threshold depth, a cardinality of the secondary column, and a cardinality of the primary column (if the threshold depth has been reached). If the index does not have a leading column that matches the table column associated with the seed, an index is found that has a recursive and non-recursive columns that match columns that are compared by the recursive predicate. The minimum value of the leading column is then used to start recursively probing up the index, and the estimated number of rows is calculated based on the maximum depth (or average depth in another embodiment) of the recursion, a cardinality of the recursive column, and a cardinality of the non-recursive column.

Claims

1. A method comprising:

receiving a recursive query, wherein the recursive query comprises a recursive predicate associated with a recursive column in a table; and

estimating a number of rows that the recursive query will retrieve, wherein the estimating further comprises recursively probing an index associated with the table.

2. The method of claim 1, wherein the recursive query comprises a seed associated with a seed column in the table and wherein the estimating further comprises:

determining that the seed column of the table is associated with a leading column of the index; and

determining that the recursive column of the table is associated with a secondary column of the index.

3. The method of claim 2, wherein the estimating further comprises:

recursively probing the index until a threshold depth of the recursive probing is reached; and

in response to the threshold depth being reached, calculating the number of rows based on the threshold depth, a cardinality of the secondary column of the index, and a cardinality of the leading column of the index.

4. The method of claim 2, wherein the estimating further comprises:

recursively probing the index until all nodes of the index have been examined by the recursive probing, so long as a threshold depth of the recursive probing is not reached; and

in response to all nodes of the index having been examined by the recursive probing, calculating the number of rows that the recursive query will retrieve based on a number of rows examined by the recursive probing of the index.

5. The method of claim 1, wherein the recursive predicate comprises a comparison of a first column and a second column, and wherein the estimating further comprises:

determining that the recursive column of the index is associated with the first column and a non-recursive column of the index is associated with the second column.

6. The method of claim 5, wherein the estimating further comprises:

finding a minimum value of a leading column of the index; and

recursively probing the index starting with the minimum value.

7. The method of claim 5, wherein the estimating further comprises:

calculating the number of rows based on a maximum depth of the recursive probing, a cardinality of the recursive column, and a cardinality of the non-recursive column.

8. The method of claim 5, wherein the estimating further comprises:

calculating the number of rows based on an average depth of the recursive probing, a cardinality of the recursive column, and a cardinality of the non-recursive column.

9. A signal-bearing medium encoded with instructions, wherein the instructions when executed comprise:

receiving a recursive query, wherein the recursive query comprises a recursive predicate associated with a recursive column in a table; and

estimating a number of rows that the recursive query will retrieve, wherein the estimating further comprises recursively probing an index associated with the table.

10. The signal-bearing medium of claim 9, wherein the recursive query comprises a seed associated with a seed column in the table and wherein the estimating further comprises:

determining that the seed column of the table is associated with a leading column of the index; and

determining that the recursive column of the table is associated with a secondary column of the index.

11. The signal-bearing medium of claim 10, wherein the estimating further comprises:

recursively probing the index until a threshold depth of the recursive probing is reached; and

in response to the threshold depth being reached, calculating the number of rows based on the threshold depth, a cardinality of the secondary column of the index, and a cardinality of the leading column of the index.

12. The signal-bearing medium of claim 10, wherein the estimating further comprises:

recursively probing the index until all nodes of the index have been examined by the recursive probing, so long as a threshold depth of the recursive probing is not reached; and

in response to all nodes of the index having been examined by the recursive probing, calculating the number of rows that the recursive query will retrieve based on a number of rows examined by the recursive probing of the index.

13. The signal-bearing medium of claim 9, wherein the recursive predicate comprises a comparison of a first column and a second column, and wherein the estimating further comprises:

determining that the recursive column of the index is associated with the first column and a non-recursive column of the index is associated with the second column.

14. The signal-bearing medium of claim 13, wherein the estimating further comprises:

finding a minimum value of a leading column of the index; and

recursively probing the index starting with the minimum value.

15. The signal-bearing medium of claim 13, wherein the estimating further comprises:

calculating the number of rows based on a maximum depth of the recursive probing, a cardinality of the recursive column, and a cardinality of the non-recursive column.

16. The signal-bearing medium of claim 13, wherein the estimating further comprises:

calculating the number of rows based on an average depth of the recursive probing, a cardinality of the recursive column, and a cardinality of the non-recursive column.

17. A method for configuring a computer, comprising:

configuring the computer to receive a recursive query, wherein the recursive query comprises a recursive predicate associated with a recursive column in a table; and

configuring the computer to estimate a number of rows that the recursive query will retrieve, wherein the configuring the computer to estimate further comprises configuring the computer to recursively probe an index associated with the table.

18. The method of claim 17, wherein the recursive query comprises a seed associated with a seed column in the table and wherein the configuring the computer to estimate further comprises:

configuring the computer to determine that the seed column of the table is associated with a leading column of the index; and

configuring the computer to determine that the recursive column of the table is associated with a secondary column of the index.

19. The method of claim 18, wherein the configuring the computer to estimate further comprises:

configuring the computer to recursively probe the index until a threshold depth of the recursive probing is reached; and

configuring the computer to, in response to the threshold depth being reached, calculate the number of rows based on the threshold depth, a cardinality of the secondary column of the index, and a cardinality of the leading column of the index.

20. The method of claim 18, wherein the configuring the computer to estimate further comprises:

configuring the computer to recursively probe the index until all nodes of the index have been examined by the recursive probe, so long as a threshold depth of the recursive probe is not reached; and

configuring the computer to, in response to all nodes of the index having been examined by the recursive probe, calculate the number of rows that the recursive query will retrieve based on a number of rows examined by the recursive probe of the index.

21. The method of claim 17, wherein the recursive predicate comprises a comparison of a first column and a second column, and wherein the configuring the computer to estimate further comprises:

configuring the computer to determine that the recursive column of the index is associated with the first column and a non-recursive column of the index is associated with the second column.

22. The method of claim 21, wherein the configuring the computer to estimate further comprises:

configuring the computer to find a minimum value of a leading column of the index; and

configuring the computer to recursively probe the index starting with the minimum value.

23. The method of claim 21, wherein the configuring the computer to estimate further comprises:

configuring the computer to calculate the number of rows that the recursive query will retrieve based on a maximum depth of the recursive probe, a cardinality of the leading column, a cardinality of the secondary column, a number of rows in the table, and a cardinality of the leading column and the secondary column taken together.

24. The method of claim 21, wherein the configuring the computer to estimate further comprises:

configuring the computer to calculate the number of rows based on an average depth of the recursive probe, a cardinality of the recursive column, and a cardinality of the non-recursive column, a number of rows in the table, and a cardinality of the recursive column and the non-recursive column taken together.