1. A process for optimizing a query to produce a query execution plan for a specific database comprising the steps of: a) initializing a sub-plan memo data structure for storing data concerning multiple sub-plans that form parts of potential query execution plans; b) optimizing an input query to produce a first set of sub-plans, which when executed produce result record sets from the database; c) forming a sub-plan query statement for each of the sub-plans that make up the first set of query execution sub-plans; and d) executing each of the sub-plan query statements on the database and storing a result of said execution in the sub-plan memo data structure for use in producing a final query execution plan for answering the input query.