1. A method that estimates a selectivity of a query expression on a database comprising: deriving a probability distribution for possible selectivity values for the query expression; and evaluating the probability distribution using a desired selectivity confidence to derive the estimated selectivity.