ACM SIGMOD Anthology VLDB dblp.uni-trier.de

Data Base System Performance Prediction Using an Analytical Model (Invited Paper).

Kenneth C. Sevcik: Data Base System Performance Prediction Using an Analytical Model (Invited Paper). VLDB 1981: 182-198
@inproceedings{DBLP:conf/vldb/Sevcik81,
  author    = {Kenneth C. Sevcik},
  title     = {Data Base System Performance Prediction Using an Analytical Model
               (Invited Paper)},
  booktitle = {Very Large Data Bases, 7th International Conference, September
               9-11, 1981, Cannes, France, Proceedings},
  publisher = {IEEE Computer Society},
  year      = {1981},
  pages     = {182-198},
  ee        = {db/conf/vldb/Sevcik81.html},
  crossref  = {DBLP:conf/vldb/81},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

Much progress has been made recently in developing strategies for data base design at both the logical and physical levels. Various approaches, some built into automated design aids, produce designs that are known to be "good" (or even "optimal" in some sense). The measurement criteria by which the designs are judged, however, are difficult to relate to some of the performance measures of importance to computer system managers and data base system users. Such performance measures include device utilizations, transaction throughputs, and the distribution of responsetimes. In this paper, we suggest an overall framework for assessing and predicting the effect on resource consumption, throughputs, and response times of a variety of physical and logical data base design decisions that affect performance. We use ananalytical model based, at the lowest level, on queueing network models. Queueing network models have already proven useful in understanding and predicting performance in many actual computer systems (with and without data base components). At higher levels of the analytical model, we establish a sequence of data base system workload descriptions, each one dependent on more performance related design decisions. By analytical techniques, the workload description at one level and a set of design choices are transformed into the workload description at the next lower (more fully specified) level. By this approach, many data base design alternatives can be represented by changes at a single level of the layered model. The design alternatives can be assessed with respect to their effect on a variety of performance measures, including record accesses, block accesses, physical disk transfers, throughputs, and mean response times. The presence of other workload components running concurrently on the same hardware configuration can also be taken into account.

Copyright © 1981 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.


ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ... DVD Version: Load ACM SIGMOD Anthology DVD 1" and ... BibTeX

Printed Edition

Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings. IEEE Computer Society 1981
Contents BibTeX

References

[Alle79]
...
[AnBe77]
Henry D. Anderson, P. Bruce Berra: Minimum Cost Selection of Secondary Indexes for Formatted Files. ACM Trans. Database Syst. 2(1): 68-90(1977) BibTeX
[BaHs78]
Jayanta Banerjee, David K. Hsiao: Performance Study of a Database Machine in Supporting Relational Databases. VLDB 1978: 319-329 BibTeX
[Bato]
...
[Bell81]
...
[BeIr77]
Elias Berelian, Keki B. Irani: Evaluation and Optimization. VLDB 1977: 545-555 BibTeX
[BlEs77]
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
[BrSh77]
Richard S. Brice, Stephen W. Sherman: An Extension of the Performance of a Database Manager in a Virtual Memory System Using Partially Locked Virtual Buffers. ACM Trans. Database Syst. 2(2): 196-207(1977) BibTeX
[CAKL81]
Donald D. Chamberlin, Morton M. Astrahan, W. Frank King III, Raymond A. Lorie, James W. Mehl, Thomas G. Price, Mario Schkolnick, Patricia G. Selinger, Donald R. Slutz, Bradford W. Wade, Robert A. Yost: Support for Repetitive Transactions and Ad Hoc Queries in System R. ACM Trans. Database Syst. 6(1): 70-94(1981) BibTeX
[Card73]
Alfonso F. Cardenas: Evaluation and Selection of File Organization - A Model and System. Commun. ACM 16(9): 540-548(1973) BibTeX
[Card75]
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
[CaSa75]
Alfonso F. Cardenas, James P. Sagamang: Modeling and analysis of data base organization. The doubly chained tree structure. Inf. Syst. 1(2): 57-67(1975) BibTeX
[Casa81]
...
[Chen76]
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
[Chen77]
...
[ChYa77]
Peter P. Chen, S. Bing Yao: Design and Performance Tools for Data Base Systems. VLDB 1977: 3-15 BibTeX
[Chr81]
...
[ClYa78]
Billy G. Claybrook, Chung-Shu Yang: Efficient algorithms for answering queries with unsorted multilists. Inf. Syst. 3(2): 93-97(1978) BibTeX
[DeBu78]
Peter J. Denning, Jeffrey P. Buzen: The Operational Analysis of Queueing Network Models. ACM Comput. Surv. 10(3): 225-261(1978) BibTeX
[Demo80]
Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX
[DuSe78]
...
[East78]
Malcolm C. Easton: Model for Database Reference Strings Based on Behavior of Reference Clusters. IBM J. Res. Dev. 22(2): 197-202(1978) BibTeX
[FaSc75]
Gilles Farley, Stewart A. Schuster: Query Execution and Index Selection for Relational Data Bases. VLDB 1975: 519 BibTeX
[FeLW78]
Eduardo B. Fernández, Tomás Lang, Christopher Wood: Effect of Replacement Algorithms on a Paged Buffer Database System. IBM J. Res. Dev. 22(2): 185-196(1978) BibTeX
[FrBe76]
...
[Gall81]
...
[GaGe77]
Thomas J. Gambino, Rob Gerritsen: A Data Base Design Decision Support System. VLDB 1977: 534-544 BibTeX
[GaLP76]
...
[Gerr78]
...
[GhTu76]
Sakti P. Ghosh, William G. Tuel Jr.: A Design of an Experiment to Model Data Base System Performance. IEEE Trans. Software Eng. 2(2): 97-106(1976) BibTeX
[Giov80]
...
[GoHa74]
...
[GoVe80]
V. Gopalakrishna, C. E. Veni Madhavan: Performance Evaluation of Attribute-Based Tree Organization. ACM Trans. Database Syst. 5(1): 69-87(1980) BibTeX
[GrZa81]
...
[Haer78]
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX
[HaCh76]
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
[HaMc78]
Michael Hammer, Dennis McLeod: The Semantic Data Model: A Modelling Mechanism for Data Base Applications. SIGMOD Conference 1978: 26-36 BibTeX
[HaNi79]
Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 BibTeX
[HaSt79]
Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 BibTeX
[HoSe75]
Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX
[Hubb78]
...
[HuSo77]
Christer Hulten, Lars Söderlund: A Simulation Model for Performance Analysis of Large Shared Data Bases. VLDB 1977: 524-532 BibTeX
[IrLi79]
Keki B. Irani, Hing-Lung Lin: Queuing Network Models for Concurrent Transaction Processing in a Database System. SIGMOD Conference 1979: 134-142 BibTeX
[IrPT79]
Keki B. Irani, Subir Purkayastha, Toby J. Teorey: A Designer for DBMS-Processable Logical Database Structures. VLDB 1979: 219-231 BibTeX
[Jako80]
Matti Jakobsson: Reducing block accesses in inverted files by partial clustering. Inf. Syst. 5(1): 1-5(1980) BibTeX
[Kahn76]
Beverly K. Kahn: A Method for Describing Information Required by the Database Design Process. SIGMOD Conference 1976: 53-64 BibTeX
[KaSY78]
Rangasami L. Kashyap, S. K. C. Subas, S. Bing Yao: Analysis of the Multiple-Attribute-Tree Data-Base Organization. IEEE Trans. Software Eng. 3(6): 451-467(1977) BibTeX
[KeLa74]
...
[King74]
...
[Korn79]
...
[LaWF77]
Tomás Lang, Christopher Wood, Eduardo B. Fernández: Database Buffer Paging in Virtual Storage Systems. ACM Trans. Database Syst. 2(4): 339-351(1977) BibTeX
[LaSh76]
...
[Levy80]
...
[LiYa77]
J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977) BibTeX
[Liu76]
Jane W.-S. Liu: Algorithms for Parsing Search Queries in Systems with Inverted File Organization. ACM Trans. Database Syst. 1(4): 299-316(1976) BibTeX
[LoMu77]
Guy M. Lohman, John A. Muckstadt: Optimal Policy for Batch Operations: Backup, Checkpointing, Reorganization, and Updating. ACM Trans. Database Syst. 2(3): 209-222(1977) BibTeX
[LGST79]
Vincent Y. Lum, Sakti P. Ghosh, Mario Schkolnick, Robert W. Taylor, D. Jefferson, Stanley Y. W. Su, James P. Fry, Toby J. Teorey, B. Yao, D. S. Rund, B. Kahn, Shamkant B. Navathe, D. Smith, L. Aguilar, W. J. Barr, P. E. Jones: 1978 New Orleans Data Base Design Workshop Report. VLDB 1979: 328-339 BibTeX
[Maga81]
...
[MaCa80]
...
[MaSe77]
Salvatore T. March, Dennis G. Severance: The Determination of Efficient Record Segmentations and Blocking Factors for Shared Data Files. ACM Trans. Database Syst. 2(3): 279-296(1977) BibTeX
[MaSe78]
Salvatore T. March, Dennis G. Severance: A Mathematical Modeling Approach to the Automatic Selection of Database Designs. SIGMOD Conference 1978: 52-65 BibTeX
[Merr77]
T. H. Merrett: Database Cost Analysis: a Top-Down Approach. SIGMOD Conference 1977: 135-143 BibTeX
[Milr75]
Michael F. Mitoma, Keki B. Irani: Automatic Data Base Schema Design and Optimization. VLDB 1975: 286-321 BibTeX
[Miya75]
Isao Miyamoto: Hierarchical Performance Analysis Models for Data Base Systems. VLDB 1975: 322-352 BibTeX
[MyWB78]
...
[NaMi78]
Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495 BibTeX
[NaYK75]
...
[OrAs79]
Ole Oren, Frode Aschim: Statistice for the Usage of a Conceptual Data Model as a Basis for Logical Data Base Design. VLDB 1979: 140-145 BibTeX
[OzSS77]
Esen A. Ozkarahan, Stewart A. Schuster, Kenneth C. Sevcik: Performance Evaluation of a Relational Associative Processor. ACM Trans. Database Syst. 2(2): 175-195(1977) BibTeX
[Pezz80]
...
[PoLe80]
Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
[Putk79]
Anne Putkonen: On the selection of the access path in inverted database organization. Inf. Syst. 4(1): 219-225(1979) BibTeX
[RaRo76]
...
[RaHu77]
...
[Rich81]
Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163 BibTeX
[RiSt79]
Daniel R. Ries, Michael Stonebraker: Locking Granularity Revisited. ACM Trans. Database Syst. 4(2): 210-227(1979) BibTeX
[RoHi75]
...
[RoMy75]
Nick Roussopoulos, John Mylopoulos: Using Semantic Networks for Database Management. VLDB 1975: 144-172 BibTeX
[SACL79]
Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34 BibTeX
[Schk75]
Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX
[Schk77]
Mario Schkolnick: A Clustering Algorithm for Hierarchical Structures. ACM Trans. Database Syst. 2(1): 27-44(1977) BibTeX
[Schk78a]
Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487 BibTeX
[Schk78b]
...
[ScGo76]
Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
[Senk77]
...
[SeAl76]
Michael E. Senko, Edward B. Altman: DIAM II and Levels of Abstraction - The Physical Device Level: A General Model for Access Methods. VLDB 1976: 79-94 BibTeX
[SAA73]
...
[SeLO68]
...
[SeCa77]
Dennis G. Severance, John V. Carlis: A Practical Approach to Selecting Record Access Paths. ACM Comput. Surv. 9(4): 259-272(1977) BibTeX
[SeDu76]
Dennis G. Severance, Richardo Duhne: A Practitioner's Guide To Addressing Algorithms. Commun. ACM 19(6): 314-326(1976) BibTeX
[SeLo76]
Dennis G. Severance, Guy M. Lohman: Differential Files: Their Application to the Maintenance of Large Databases. ACM Trans. Database Syst. 1(3): 256-267(1976) BibTeX
[ShBr76]
Stephen W. Sherman, Richard S. Brice: Performance of a Database Manager in a Virtual Memory System. ACM Trans. Database Syst. 1(4): 317-343(1976) BibTeX
[Sile76]
Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976) BibTeX
[Smit78]
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) BibTeX
[SmBr80]
...
[SmSm78]
...
[SoGo79]
Gary H. Sockut, Robert P. Goldberg: Database Reorganization - Principles and Practice. ACM Comput. Surv. 11(4): 371-395(1979) BibTeX
[Sund78]
Bo Sundgren: Data Base Design in Theory and Practice - Towards an Integrated Methodology. VLDB Surveys 1978: 3-23 BibTeX
[TeDa76]
Toby J. Teorey, K. Sundar Das: Application of an Analytical Model to Evaluate Storage Structures. SIGMOD Conference 1976: 9-19 BibTeX
[TeFr80]
Toby J. Teorey, James P. Fry: The Logical Record Access Approach to Database Design. ACM Comput. Surv. 12(2): 179-211(1980) BibTeX
[TeOb78]
...
[Tomp76]
Frank Wm. Tompa: Choosing an Efficient Internal Schema. VLDB 1976: 65-77 BibTeX
[TsLo81]
...
[Tuel76]
William G. Tuel Jr.: An Analysis of Buffer Paging in Virtual Storage Systems. IBM J. Res. Dev. 20(5): 518-520(1976) BibTeX
[TuRo75]
...
[Ullm80]
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
BibTeX
[WaBo81]
Anthony I. Wasserman, Karen Botnich: Annotated Bibliography on Data Design. SIGMOD Record 11(1): 45-77(1981) BibTeX
[WoKa78]
...
[WoYo76]
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
[WoMy77]
...
[Yao77a]
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX
[Yao77b]
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
[Yao79]
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX
[YaDe78]
S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77 BibTeX
[YaMe75]
S. Bing Yao, Alan G. Merten: Selection of File Organization Using an Analytic Model. VLDB 1975: 255-267 BibTeX
[YaNW78]
...
[YeBa77]
Raymond T. Yeh, Jerry W. Baker: Toward a Design Methodology for DBMS: A Software Engineering Approach. VLDB 1977: 16-27 BibTeX
[YoWo79]
Karel Youssefi, Eugene Wong: Query Processing in a Relational Database Management System. VLDB 1979: 409-417 BibTeX
[YuLS77]
Clement T. Yu, W. S. Luk, M. K. Siu: On the Estimation of the Number of Desired Records with Respect to a Given Query. ACM Trans. Database Syst. 3(1): 41-56(1978) BibTeX
[YuWo75]
...
[Zaho80]
...
[ZSEG81]
John Zahorjan, Kenneth C. Sevcik, Derek L. Eager, Bruce Galler: Balanced Job Bound Analysis of Queueing Networks. Commun. ACM 25(2): 134-141(1982) BibTeX
[ZaMe81]
Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981) BibTeX
[Zipf49]
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949
BibTeX

Referenced by

  1. Brian A. Nixon: Implementation of Information System Design Specifications: A Performance Perspective. DBPL 1991: 149-168
  2. Frédéric Andrès, Michel Couprie, Yann Viémont: A Multi-Environment Cost Evaluator for Parallel Database Systems. DASFAA 1991: 126-135
  3. Haran Boral, William Alexander, Larry Clay, George P. Copeland, Scott Danforth, Michael J. Franklin, Brian E. Hart, Marc G. Smith, Patrick Valduriez: Prototyping Bubba, A Highly Parallel Database System. IEEE Trans. Knowl. Data Eng. 2(1): 4-24(1990)
  4. Salvatore Orlando, V. Perri, S. Scrivano, Witold Staniszkis: Database Analyzer and Predictor - An Overview. ICDE 1989: 625-634
  5. Ignacio R. Casas, Kenneth C. Sevcik: A Buffer Management Model For Use In Predicting Overall Database System Performance. ICDE 1989: 463-469
  6. Lawrence Chung, Daniel Rios-Zertuche, Brian A. Nixon, John Mylopoulos: Process Management and Assertion Enforcement for a Semantic Data Model. EDBT 1988: 469-487
  7. Stavros Christodoulakis: Implications of Certain Assumptions in Database Performance Evaluation. ACM Trans. Database Syst. 9(2): 163-186(1984)
  8. Salvatore Orlando, Pasquale Rullo, Witold Staniszkis: Transaction Workload Evaluation in the CODASYL Database Environment. ICDE 1984: 562-569
  9. Wen-Te K. Lin, Jerry Nolte: Basic Timestamp, Multiple Version Timestamp, and Two-Phase Locking. VLDB 1983: 109-119
  10. Stavros Christodoulakis: Estimating Block Transfers and Join Sizes. SIGMOD Conference 1983: 40-54
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:45:12 2009