User specified confidence threshold specifies how likely it should be that the actual cost of the plan is less than or equal to the reported (point) cost estimate. Cardinality estimates for base tables and intermediate query results are based on join synopses, under the restriction that only foreign-key joins are permitted. The cardinality distribution is determined using the join synopsis and Bayes' rule.

Represents uncertainty in operator estimates using intervals, and tries to identify plans that are robust (close to optimal) throughout the interval, or a set of switchable plans that cover the interval. Implements a run-time switch operation, and modifies other operators so that they initially produce a randomized sample of their output.

Hardcopy on file. Plan reoptimization is triggered by cardinality checking operators inserted into the plan. Checks determine whether the actual cardinality differs from the predicted cardinality by enough that the optimizer would have chosen a different plan. The plan transition cardinalities are determined at optimization time. Reoptimization considers the use of materialized intermediate results when reoptimizing the query.

Claims average 30% estimation time error with 3% of compilation time overhead to produce the estimate.

Classifies SPJ queries using features such as number of tables in the query, the number of SARGable predicates in the query, and the sizes of the tables. For each class of queries, the system maintains a plan template, which can be instantiated for any query in the class. To process a query, system first tries to match it to an existing class. If it can, the class plan template is instantiated and the resulting plan is used for the query. Otherwise, the query is compiled and used to start a new class.

How to produce dynamic query evaluation plans that include ChoosePlan operators. Generalizes the optimizer so that it understands that cost estimates may only partially order the candidate evaluation plans.