An Analysis Framework for Access Methods
Marcel Kornacker, Mehul A. Shah, Joseph M. Hellerstein · 1999
Designing and tuning access methods (AMs) has always been more of a black art than a rigorous discipline, with performance assessments being mostly reduced to presenting bottom-line runtime or I/O numbers. (This paper presents an analysis framework for AMs that gives detailed feedback about observed page access performance and the performance implications of individual aspects of an AM design.) The framework defines performance metrics which are more meaningful than bottom-line numbers and which allow the AM designer to detect and isolate deficiencies in an AM design. The analysis process takes a workload---a tree and a set of queries---as input and provides metrics that characterize the performance of each query as well as that of the tree structure and the structure-shaping aspects of the AM implementation. Central to the framework is the use of the optimal behavior---which can be approximated relatively efficiently---as a point of reference against which the actual observed performa...