dblp.uni-trier.de www.dagstuhl.de www.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        = {http://www.vldb.org/journal/VLDBJ4/P127.pdf},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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.

References

[Chou & Dewitt 1985]
Hong-Tai Chou, David J. DeWitt: An Evaluation of Buffer Management Strategies for Relational Database Systems. VLDB 1985: 127-141 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Cornell & Yu 1989]
Douglas W. Cornell, Philip S. Yu: Integration of Buffer Management and Query Optimization in Relational Database Environment. VLDB 1989: 247-255 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Dan & Towsley 1990]
Asit Dan, Donald F. Towsley: An Approximate Analysis of the LRU and FIFO Buffer Replacement Schemes. SIGMETRICS 1990: 143-152 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Effelsberg & Haerder 1984]
Wolfgang Effelsberg, Theo Härder: Principles of Database Buffer Management. ACM Trans. Database Syst. 9(4): 560-595(1984) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Faloutsos & Sellis 1991]
Christos Faloutsos, Raymond T. Ng, Timos K. Sellis: Predictive Load Control for Flexible Buffer Allocation. VLDB 1991: 265-274 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gray 1991]
Jim Gray (Ed.): The Benchmark Handbook for Database and Transaction Systems (1st Edition). Morgan Kaufmann 1991
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Hawthorn & Stonebraker 1979]
Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[IBM Database 2 Adminitration Guide 1993]
...
[Kearns & Defazio 1989]
John P. Kearns, Samuel DeFazio: Diversity in Database Reference Behavior. SIGMETRICS 1989: 11-19 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Smith 1978]
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Verkamo 1985]
A. Inkeri Verkamo: Empirical Results on Locality in Database Referencing. SIGMETRICS 1985: 49-58 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Yu & Cornell 1991]
Philip S. Yu, Douglas W. Cornell: Optimal Buffer Allocation in A Multi-Query Environment. ICDE 1991: 622-631 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Last update Fri Sep 14 18:29:09 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page