Patent ID: 7246108

Claim:
A method of processing a query that comprises an outer query and a first inner query block, comprising the machine-implemented steps of: checking a data structure to determine whether a previously-generated query block information record corresponding to an already-processed first inner query block exists in the data structure, wherein the already-processed first inner query block corresponds to the first inner query block in a first state in an already-processed form; if the previously-generated query block information record exists in the data structure, then establishing query block information for the first inner query block in the first state based on the previously-generated query block information record; if the previously-generated query block information record does not exist in the data structure, then generating and storing the query block information, for the first inner query block in the first state, in a newly-generated query block information record in the data structure; and based on the query block information for the first inner query block in the first state, determining a cost for a semantically equivalent query that includes the first inner query block in the first state; wherein the semantic equivalent query is one of a plurality of semantically equivalent queries for which costs are determined; and based on the costs, selecting and executing one of the plurality of semantically equivalent queries.