Cost-based object query optimization

This dissertation investigates cost-based object query optimization techniques. We focus on cost-based optimization, which has been adopted by all commercial relational database management systems (DBMSs). We identify several practical issues in developing cost-based optimizers for object queries. To attack these issues, we propose an algebraic framework for cost-based object query optimization with special attention paid to queries involving collection-valued attributes (CVAs) and multiple collection types.; The object algebra we propose, the COAL algebra, can express all queries in ODMG's OQL language. OQL is a standard object query language from the Object Data Management Group (ODMG) [CB97].; Our unnesting technique subsumes the existing unnesting techniques for both relational and object-relational queries.; The new reference materialization technique we propose, the hybrid approach, improves upon previous techniques by processing CVAs and shared attributes more efficiently. The performance of the proposed techniques is evaluated analytically and experimentally.; In spite of their impact in cost-based optimization, cost models themselves have not been sufficiently investigated. In particular, an appropriate quality measurement for cost models is still absent. The quality of cost models is important in cost-based query optimization because the quality of a cost-based optimizer depends on that of the cost model. A good measurement for cost models is a necessary step towards assessing the quality of cost-based optimizers. We propose the expected penalty measurement as a quality metric for cost models. Derived from both experiments and analysis, this measurement corresponds well with several intuitive observations about the quality of cost models.; Another issue for cost models is parameter representation and propagation. In relational DBMSs, the catalog stores the statistics used in costing evaluation plans. The catalog structure for object databases has not been investigated and documented. We present a simple catalog structure for storing object database statistics.; We implemented all the components proposed in this dissertation within COCOUN (COlumbia with COllection and UNnesting), a cost-based OQL query optimizer based on a cost-based relational query optimizer framework Columbia [SMB01].; We also implemented an OQL query evaluator that can accept the evaluation plans output by COCOUN and execute those plans on a Java-based commercial OODBMS. The evaluator has been a useful platform for tuning and validating the cost model implemented in COCOUN. (Abstract shortened by UMI.)...