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.