92. A machine-readable storage medium storing one or more sequences of instructions for processing a query, which instructions, when executed by one or more processors, cause the one or more processors to perform steps comprising: receiving the query, wherein the query comprises one or more query blocks; establishing a current-best query based on the query; determining a set of candidate queries and costs, wherein the costs include a cost corresponding to each candidate query in the set of candidate queries, wherein each candidate query in the set of candidate queries is determined based on the current-best query and an alternative state of a particular query block of the one or more query blocks, wherein if a specific cost associated with a specific candidate query satisfies a first particular mathematical relationship with a current-best cost for the current-best query, then the specific candidate query is established as the current-best query; wherein each candidate query in the set of candidate queries is semantically equivalent to the query; choosing a particular query from the set of candidate queries based on the costs for the candidate queries in the set of candidate queries; and executing the particular query in response to a request to execute the query.
92. A machine-readable storage medium storing one or more sequences of instructions for processing a query, which instructions, when executed by one or more processors, cause the one or more processors to perform steps comprising: receiving the query, wherein the query comprises one or more query blocks; establishing a current-best query based on the query; determining a set of candidate queries and costs, wherein the costs include a cost corresponding to each candidate query in the set of candidate queries, wherein each candidate query in the set of candidate queries is determined based on the current-best query and an alternative state of a particular query block of the one or more query blocks, wherein if a specific cost associated with a specific candidate query satisfies a first particular mathematical relationship with a current-best cost for the current-best query, then the specific candidate query is established as the current-best query; wherein each candidate query in the set of candidate queries is semantically equivalent to the query; choosing a particular query from the set of candidate queries based on the costs for the candidate queries in the set of candidate queries; and executing the particular query in response to a request to execute the query. 101. The machine-readable storage medium of claim 92 , wherein the query has one or more query blocks and wherein the instructions that cause determining the set of candidate queries comprise instructions which, when executed by the one or more processors, cause the one or more processors to perform the step of determining a particular semantically equivalent query based on the query and an alternative query block, wherein the alternative query block is determined based on a first query block of the one or more query blocks.