1. A computer implemented method, comprising: using at least one computer system configured for: receiving a database query language statement and performance information related to the database query language statement; determining whether one or more statistics relating to the database query language statement are available or accurate in the performance information; determining a hint for a missing or an inaccurate statistic in the performance information; creating or improving an estimate of a value of an execution of the query language statement by at least recursively determining whether a predicate selectivity exceeds a threshold, wherein the act of creating or improving the estimate comprises sampling an adjustable portion of data against which the query language statement is to be performed without requiring performance of a full table scan based at least in part upon a relationship between the predicate selectivity and the threshold; and verifying the estimate by executing the query language statement to perform at least the full table scan based at least in part upon the predicate selectivity, wherein the act of verifying the estimate performs a sample of a result of the full table scan to adjust the estimate.