Characterization of database access Skew in a transaction processing environment

Abstract

The knowledge of access skew (non-uniform access) in each database relation is useful for both workload management (buffer pool allocation, transact ion routing, etc. ), as well as capacity planning for changing workload mix. H[owever, it is a challenging problem to characterize the access skew of a real database workload in a simple manner that can easily be used to compute the buffer hit probability under the LRU replacement policy. A concise way to characterize the access skew is proposed by assuming that the large number of data pages may be logically grouped into a s~mall number of partitions such that the frequency of accessing each page within a partition can be treated as equal. B;wed on this approach, a recursive binary partitioning algorithm is presented that can infer the access skew from the buffer hit probabilities for a subset of the buffer sizes. This avoids explicit estimation of individual access frequencies for the large number of database pages. The method is validated of its ability to predict buffer hit from the skew characterization using production database traces.