12. A method for obtaining a query execution plan for a query in a database management system on a general-purpose computing device, comprising: using the general-purpose computing device to compute a subset of relevant expressions that is a portion of a set of relevant query expressions for the query; initializing a lower bound and an upper bound on cardinalities of expressions in the subset of relevant expressions where exact cardinalities have not been obtained; selecting an expression having a highest benefit value from the subset of relevant expressions; computing a low execution plan (P low ), a high execution plan (P high ), and a current execution plan (P curr ); computing an execution plan for a random point that is between the low execution plan (P low ) and the high execution plan (P high ); determining whether P low =P curr =P high ; based on whether P low =P curr =P high , determining a cardinality-optimal query execution plan having exact cardinalities for each expression; and optimizing the query using the cardinal-optimal query execution plan.
12. A method for obtaining a query execution plan for a query in a database management system on a general-purpose computing device, comprising: using the general-purpose computing device to compute a subset of relevant expressions that is a portion of a set of relevant query expressions for the query; initializing a lower bound and an upper bound on cardinalities of expressions in the subset of relevant expressions where exact cardinalities have not been obtained; selecting an expression having a highest benefit value from the subset of relevant expressions; computing a low execution plan (P low ), a high execution plan (P high ), and a current execution plan (P curr ); computing an execution plan for a random point that is between the low execution plan (P low ) and the high execution plan (P high ); determining whether P low =P curr =P high ; based on whether P low =P curr =P high , determining a cardinality-optimal query execution plan having exact cardinalities for each expression; and optimizing the query using the cardinal-optimal query execution plan. 15. The method of claim 12 , further comprising: selecting an expression from the set of relevant query expressions for the query; and defining a benefit value as: 
 |Feedback( e )− S |/Cost( e ), where e is an expression in the set of relevant expressions, Feedback(e) is a feedback obtain from executing the expression, S is a set of expressions for which exact cardinalities have been obtained, and Cost(e) is an optimizer estimated cost of executing the expression.