Query Optimizer

The optimizer takes a query tree from parser and decides on the best evaluation of the query based on a heuristic (described below). The optimizer uses catalog information (cardinalities and indexes). The planner then interprets the tree.

The optimizer is in general a System R style optimizer, as described in "Access Path Selection in a Relational Database Management System", Proceedings of the ACM-SIGMOD International Conference on Management of Data, June 1979.

The optimizer also considers many plans that Minibase proper does not support. These include some join methods, clustered indexes, order by, group by, distinct, and aggregates.

Information about the estimates for cost formulas for joins and access methods are available. See the text for a more detailed description of query optimization and the associated cost formulas.

Design Decisions

There are two places one might want the optimizer to get its catalog information from. One is the actual catalog relations stored in a Minibase database. The other is a text file that describes a hypothetical catalog; this is convenient for experimenting with the optimizer. The Minibase optimizer handles both of these options, using an abstract interface contained in the global systemCatalogs object.

Examples

Some sample plans are available here. Note that the optimizer may have had some changes since these plans were generated, so your results may not be identical. (For example, index-only full scans on Hash indexes are not considered in this version).

Click here for the public interface to the catalogs
Click here for the public interface to the planner
Back to the Minibase Home Page
Back to the Components Home Page