An Effective Approach to Vertical Partitioning for Physical Design of Relational Databases

Abstract

In a relational database environment, the response time of a transaction or query is strongly affected by the amount of data that needs to be accessed from secondary storage (disk). Since not all attributes in a tuple are required by each transaction, vertical partitioning of the relation can often result in a decrease in the number of disk accesses. The issues are how to formulate the partitioning problem, identify the relevant input parameters and set up the criterion for partitioning. The way a relation is accessed depends upon the access plan selections made by the query optimizer. Thus the partitioning on the physical design level must capture the effect of the query optimizer. In this paper, an approach is developed which consists of a query analysis step and a partitioning step using an optimal binary partitioning algorithm which can be recursively applied. The algorithm is based on an integer programming technique to minimize the number of disk accesses. Performance analysis is provided to study the situation when partitioning can be beneficial and quantify the performance impact. © 1990 IEEE