DataQuest: A comparative analysis of heuristic query optimization algorithms

The thesis is an implementation and study on query optimization for a single-user database system. The general objective is to show whether applying query optimization in a single-user interpretative relational DBMS is justifiable. The specific objectives are: to implement a prototype relational database management system, and to implement and analyze two query optimization algorithms. The prototype DBMS is an interpretative system and is based on the relational model. Its main function is to process ad-hoc queries. An SQL interface provides commands for data definition (CREATE, DROP, COPY and SORT) and data manipulation (INSERT and SELECT). Database information and statistics are stored and maintained by the system catalog manager. The system uses two storage structures: heap files, hash files and b+tree indices. Relational operations using different kinds of access paths are implemented. Two query optimization algorithms are implemented for the study. The algebraic manipulation technique is a heuristic algorithm and is based on the relational algebra tree. It applies transformation rules to optimize the tree. The optimized tree is then submitted to a relational algebra tree processor which performs the query. The decomposition technique is a heuristic algorithm which applies detachment and tuple substitution strategies to optimize the query. It dynamically processes the query during optimization. Aside from these algorithms, a query processing strategy without optimization is also implemented. A sample database is created for the analysis. Query response time is the parameter used for comparison