1. In a relational database having records stored therein and having a query optimizer that generates a query execution plan wherein each query plan comprises a plurality of intermediate query plan components that verify a subset of records from the database meeting query criteria, a method for evaluating a user query comprising the steps of: accessing the query plan and a set of stored intermediate statistics for records verified by query components of the query plan; selecting intermediate statistics and applying them to the query plan to form a transformed query plan; and estimating the cardinality of the transformed query plan.