AUTOMATED PHYSICAL DESIGN TOOL FOR RELATIONAL DATABASE

Abstract

Performance is one of the major considerations of database design. Given an application, a good design can make full use of the capability of the underlying database management system and hardware to achieve optimal performance. While the semantic clarity is largely determined by the logical design of a database, performance largely depends on the physical design of the database, including the physical organization of data and supporting access paths. Traditionally, physical database design is conducted by database designers or DBAs manually. It is a time-consuming task since there are usually a great number of alternatives, and the designer has to compare possible design options and select the optimal one from them. What makes the situation worse is that the quality of a design can be hardly guaranteed as it depends on the knowledge and experience of the designer, his/her understanding of tlw DBMS used and the applications. This thesis describes the design, implementation and evaluation of a physical database design-aid system. The system adopts a layered approach where each layer applies a technique to improve on its input design. It comprises three layers that improve on the initial schema generated by the logical design phase of a database through vertical partitioning, denormalization, and storage structure and index selection. The vertical partitioning layer partitions relations into fragments according to the access pattern to reduce I/O costs. That is, the attributes that are frequently accessed within a query or a set of queries are grouped together in the same fragment and are separated from those attributes that are not accessed at the same time. The denormalization layer reduces the number of required joins by duplicating certain attributes in relations. Finally, the third layer, storage structure and access path selection, determines the physical structure of stored relations (e.g. clustering and sorting) and necessary indices to facilitate fast access. The work reported in this thesis is different from existing work in the following ways. First, the architecture is extensible in the sense that an additional layer can be "plugged" into the system. or an existing layer can be "turned off". This is achieved by designing each layer with a uniform interface. Second, although the algorithms used in the prototype system are variants of existing techniques, they are redesigned for seamless integration into our environment. A series of experiments have been conducted to study the quality of designs generated by the proposed system. The results show that, given an initial schema. of a database and the expected workload, the system can generate a schema with good overall performance for the given workload. It is also found that, while vertical partitioning and denormalization can improve the performance of a database, the storage structure and access path selection contributes the most to the performance improvement.