Marcel Kornacker, Mehul Shah and Joseph M. Hellerstein

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-99-1051
1999

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/CSD-99-1051.pdf

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 defines performance metrics which are more meaningful than bottom-line numbers and thereby 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 performance is measured. The performance metrics themselves reflect the fundamental performance-relevant properties of the input tree. The framework applies to most balanced tree-structured AMs and is not restricted to particular types of of data or queries. It is implemented in amdb, a comprehensive graphical design tool for AMs that are constructed on top of the Generalized Search Tree abstraction. Amdb complements the analysis framework with visualization and debugging functionality, allowing the AM designer to investigate the source of those deficiencies that were brought to light with the help of the analysis framework.

BibTeX citation:

@techreport{Kornacker:CSD-99-1051,
    Author = {Kornacker, Marcel and Shah, Mehul and Hellerstein, Joseph M.},
    Title = {An Analysis Framework for Access Methods},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1999},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5520.html},
    Number = {UCB/CSD-99-1051},
    Abstract = {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 defines performance metrics which are more meaningful than bottom-line numbers and thereby 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 performance is measured. The performance metrics themselves reflect the fundamental performance-relevant properties of the input tree. The framework applies to most balanced tree-structured AMs and is not restricted to particular types of of data or queries. It is implemented in amdb, a comprehensive graphical design tool for AMs that are constructed on top of the Generalized Search Tree abstraction. Amdb complements the analysis framework with visualization and debugging functionality, allowing the AM designer to investigate the source of those deficiencies that were brought to light with the help of the analysis framework.}
}

EndNote citation:

%0 Report
%A Kornacker, Marcel
%A Shah, Mehul
%A Hellerstein, Joseph M.
%T An Analysis Framework for Access Methods
%I EECS Department, University of California, Berkeley
%D 1999
%@ UCB/CSD-99-1051
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1999/5520.html
%F Kornacker:CSD-99-1051