1. A method implemented on a general-purpose computing device for optimizing a query, comprising: using the general-purpose computing device to perform the following: selecting a subset of expressions in a set of relevant expressions of the query such that by executing the selected subset of expressions on a database exact cardinalities of each of the relevant expressions becomes available using at least one of the following techniques: a covering queries optimization technique that obtains an unordered subset of relevant expressions for the query that is a subset of a set of relevant expressions for the query; an expressions ordering technique that determine in which order to execute expressions in the unordered subset of relevant expressions to obtain an ordered subset of relevant expressions; an early termination technique that uses at least some of the expressions in the ordered subset of relevant expressions to determine whether execution of the expressions can be terminated early; selecting an expression having a highest benefit value from the subset of expressions to determine whether early termination is possible; computing a current execution plan for the selected expression; extracting a cardinality-optimal query execution plan without executing each expression in the plan, whereby each expression in the plan has exact cardinalities; and optimizing the query using the cardinal-optimal query execution plan.