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: obtaining a subset of accurate cardinalities that is valid for each of a set of relevant expressions for the query 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; and extracting a cardinality-optimal query execution plan without executing each expression in the plan, whereby each expression in the plan has exact cardinalities, in order to optimize the query.