Patent ID: 7240044

Claim:
In a computer system, a computer readable medium having stored thereon instructions for optimizing a query to produce an optimized query execution plan for a database and a sub-plan memo data structure comprising a plurality of sub-plan records corresponding to a plurality of sub-plan queries that form parts of potential query execution plans, wherein each of said records includes: a) a first data field for storing a sub-plan query; b) a second data field for storing a value for a size of a return set of records resulting from execution of said sub-plan query over a specified database; and c) a third data field for storing a value for a number of distinct values in the return set of records resulting from execution of said sub-plan query of said specified database, wherein the computer readable medium comprises instructions for: executing one or more sub-plan queries on the specified database; storing corresponding results of each executed sub-plan query in the first, second and third data fields of the sub-plan record corresponding to each sub-plan query; and using the stored results to produce an optimized query execution plan.