Probabilistic Diagnosis of Hot Spots

Abstract:

Commonly, a few objects in a database account for a large share of all
database accesses. These objects are called hot spots. The ability to
determine which objects are hot spots opens the door to a variety of
performance improvements. Data reorganization, migration, and
replication techniques can take advantage of knowledge of hot spots to
improve performance at low cost. In this paper we present some
techniques that can be used to identify those objects in the database
that account for more than a specified percentage of database
accesses. Identification is accomplished by analyzing a string of
database references and collecting statistics. Depending on the length
of the reference string and the amount of space available for the
analysis, each technique will have a non-zero probability of false
diagnosis, i.e., mistaking "cold" items for hot spots and vice versa.
We compare the techniques analytically and show the tradeoffs among
time, space and the probability of false diagnoses.