ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability.

Asit Dan, Philip S. Yu, Jen-Yao Chung: Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability. VLDB J. 4(1): 127-154(1995)
@article{DBLP:journals/vldb/DanYC95,
  author    = {Asit Dan and
               Philip S. Yu and
               Jen-Yao Chung},
  title     = {Characterization of Database Access Pattern for Analytic Prediction
               of Buffer Hit Probability},
  journal   = {VLDB J.},
  volume    = {4},
  number    = {1},
  year      = {1995},
  pages     = {127-154},
  ee        = {db/journals/vldb/DanYC95.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The analytic prediction of buffer hit probability, based on the characterization of database accesses from real reference traces, is extremly useful for workload management and system capacity planning. The knowledge can be helpful for proper allocation of buffer space to various database relations, as well as for the management of buffer space for a mixed transaction and query environment. Access characterization can also be used to predict the buffer invalidation effect in a multi-node environment which, in turn, can influence transaction routing strategies. However, it is a challenge to characterize the database access pattern of a real workload reference trace in a simple manner that can easily be used to compute buffer hit probability. In this article, we use a characterization method that distinguishes three types of access patterns from a trace: (1) locality within a transaction, (2) random accesses by transactions, and (3) sequential accesses by long queries. We then propose a concise way to characterize the access skew across randomly accessed pages by logically grouping the large number of data pages into a small number of partitions such that the frequency of accessing each page within a partition can be treated as equal. Based on this approach, we present a recursive binary partition algorithm that can infer the access skew characterization from the buffer hit probabilities for a subset of the buffer sizes. We validate the buffer hit predictions for single and multiple node systems using production database traces. We further show that the proposed approach can predict the buffer hit probability of a composite workload from those of its component files.

Copyright © 1995 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Key Words

Database access characterization, access skew, sequential access, reference trace, workload management, analytic prediction.

Online Paper

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

References

[Chou & Dewitt 1985]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 BibTeX
[Cornell & Yu 1989]
Douglas W. Cornell, Philip S. Yu: Integration of Buffer Management and Query Optimization in Relational Database Environment. VLDB 1989: 247-255 BibTeX
[Dan & Towsley 1990]
Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152 BibTeX
[Dan et al. 1994a]
Asit Dan, Daniel M. Dias, Philip S. Yu: Buffer Analysis for a Data Sharing Environment with Skewed Data Access. IEEE Trans. Knowl. Data Eng. 6(2): 331-337(1994) BibTeX
[Dan et al. 1994b]
Asit Dan, Philip S. Yu, Daniel M. Dias: Performance Modelling and Comparisons of Global Shared Buffer Management Policies in a Cluster Environment. IEEE Trans. Computers 43(11): 1281-1297(1994) BibTeX
[Dan et al. 1991]
Asit Dan, Philip S. Yu, Jen-Yao Chung: Characterization of Database Access Skew in a Transaction Processing Environment. SIGMETRICS 1992: 251-252 BibTeX
[Date & White 1989]
...
[Effelsberg & Loomis 1984]
Wolfgang Effelsberg, Mary E. S. Loomis: Logical, Internal, and Physical Reference Behavior in CODASYL Database Systems. ACM Trans. Database Syst. 9(2): 187-213(1984) BibTeX
[Effelsberg & Haerder 1984]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) BibTeX
[Faloutsos & Sellis 1991]
Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274 BibTeX
[Gray 1991]
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents BibTeX
[Hawthorn & Stonebraker 1979]
Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 BibTeX
[IBM Database 2 Adminitration Guide 1993]
...
[Kearns & Defazio 1989]
John P. Kearns, Samuel DeFazio: Diversity in Database Reference Behavior. SIGMETRICS 1989: 11-19 BibTeX
[Kronenberg et al. 1986]
Nancy P. Kronenberg, Henry M. Levy, William D. Strecker: VAXclusters: A Closely-Coupled Distributed System. ACM Trans. Comput. Syst. 4(2): 130-146(1986) BibTeX
[Mattson et al. 1970]
...
[Ng et al. 1990]
Raymond T. Ng, Christos Faloutsos, Timos K. Sellis: Flexible Buffer Allocation Based on Marginal Gains. SIGMOD Conference 1991: 387-396 BibTeX
[Nicola et al. 1992]
Victor F. Nicola, Asit Dan, Daniel M. Dias: Analysis of the Generalized Clock Buffer Replacement Scheme for Database Transaction Processing. SIGMETRICS 1992: 35-46 BibTeX
[Press et al. 1986]
...
[Rodriguez-Rosell 1976]
...
[Sacco & Schkolnick 1986]
Giovanni Maria Sacco, Mario Schkolnick: Buffer Management in Relational Database Systems. ACM Trans. Database Syst. 11(4): 473-498(1986) BibTeX
[Smith 1978]
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) BibTeX
[Strickland et al. 1982]
...
[Tay et al. 1985]
Y. C. Tay, Rajan Suri, Nathan Goodman: A Mean Value Performance Model for Locking in Databases: The No-Waiting Case. J. ACM 32(3): 618-651(1985) BibTeX
[Teng & Gumar 1984]
...
[van den Berg & Towsley 1993]
Jacob van den Berg, Donald F. Towsley: Properties of the Miss Ratio for a 2-Level Storage Model with LRU or FIFO Replacement Strategy and Independent References. IEEE Trans. Computers 42(4): 508-512(1993) BibTeX
[Verkamo 1985]
A. Inkeri Verkamo: Empirical Results on Locality in Database Referencing. SIGMETRICS 1985: 49-58 BibTeX
[Yu et al. 1993]
Philip S. Yu, Daniel M. Dias, Stephen S. Lavenberg: On the Analytical Modeling of Database Concurrency Control. J. ACM 40(4): 831-872(1993) BibTeX
[Yu & Cornell 1991]
Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631 BibTeX

Referenced by

  1. Kurt P. Brown, Michael J. Carey, Miron Livny: Goal-Oriented Buffer Management Revisited. SIGMOD Conference 1996: 353-364
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Journal: 1992-1995 Copyright © by VLDB Endowment / 1996-... Copyright © by Springer Verlag,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:31:23 2009