46. A computer-implemented method of processing a query, comprising: receiving the query, wherein the query comprises one or more query blocks; determining multiple starting queries based on the query and one or more heuristics; for each starting query of the multiple starting queries: establishing said each starting query as a local-best query; determining a set of candidate queries and costs, wherein the costs include a cost for each candidate query in the set of candidate queries, wherein each candidate query in the set of candidate queries is determined based on the local-best query and an alternative state for a particular query block of the one or more query blocks, and wherein, if a specific cost for a specific candidate query satisfies a first particular mathematical relationship with a local-best cost for the local-best query, then establishing the specific candidate query as the local-best query; wherein each candidate query in the set of candidate queries is semantically equivalent to the query; choosing a particular query from a set of local-best queries based on costs for each query in the set of local-best queries, wherein the set of local-best queries comprises the local-best query for each set of candidate queries; and executing the particular query in response to a request to execute the query; wherein the method is performed by one or more computing devices.
56. The method of claim 46 , wherein the query has one or more query blocks and wherein determining the set of candidate queries for each starting query comprises determining a particular semantically equivalent query based on the starting 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.