SASH: A Self-Adaptive Histogram Set for Dynamically Changing Workloads Lipyeow Lim, Min Wang, and Jeffrey Scott Vitter   View Paper (PDF)   Return to Web & Statistics (Session A10) Abstract Most RDBMSs maintain a set of histograms for estimating the selectivities of given queries. These selectivities are typically used for cost- based query optimization. While the problem of building an accurate histogram for a given attribute or attribute set has been well-studied, little attention has been given to the problem of building and tuning a set of histograms col- lectively for multidimensional queries in a self- managed manner based only on query feedback. In this paper, we present SASH, a Self-Adaptive Set of Histograms that addresses the problem of building and maintaining a set of histograms. SASH uses a novel two-phase method to auto- matically build and maintain itself using query feedback information only. In the online tuning phase, the current set of histograms is tuned in response to the estimation error of each query in an online manner. In the restructuring phase, a new and more accurate set of histograms re- places the current set of histograms. The new set of histograms (attribute sets and memory distribution) is found using information from a batch of query feedback. We present experi- mental results that show the effectiveness and accuracy of our approach. ©2004 Association for Computing Machinery