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
  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,}


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


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
Jayanta Banerjee, David K. Hsiao: Performance Study of a Database Machine in Supporting Relational Databases. VLDB 1978: 319-329 BibTeX
Elias Berelian, Keki B. Irani: Evaluation and Optimization. VLDB 1977: 545-555 BibTeX
Mike W. Blasgen, Kapali P. Eswaran: Storage and Access in Relational Data Bases. IBM Systems Journal 16(4): 362-377(1977) BibTeX
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
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
Alfonso F. Cardenas: Evaluation and Selection of File Organization - A Model and System. Commun. ACM 16(9): 540-548(1973) BibTeX
Alfonso F. Cardenas: Analysis and Performance of Inverted Data Base Structures. Commun. ACM 18(5): 253-263(1975) BibTeX
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
Peter P. Chen: The Entity-Relationship Model - Toward a Unified View of Data. ACM Trans. Database Syst. 1(1): 9-36(1976) BibTeX
Peter P. Chen, S. Bing Yao: Design and Performance Tools for Data Base Systems. VLDB 1977: 3-15 BibTeX
Billy G. Claybrook, Chung-Shu Yang: Efficient algorithms for answering queries with unsorted multilists. Inf. Syst. 3(2): 93-97(1978) BibTeX
Peter J. Denning, Jeffrey P. Buzen: The Operational Analysis of Queueing Network Models. ACM Comput. Surv. 10(3): 225-261(1978) BibTeX
Robert Demolombe: Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language. VLDB 1980: 55-63 BibTeX
Malcolm C. Easton: Model for Database Reference Strings Based on Behavior of Reference Clusters. IBM J. Res. Dev. 22(2): 197-202(1978) BibTeX
Gilles Farley, Stewart A. Schuster: Query Execution and Index Selection for Relational Data Bases. VLDB 1975: 519 BibTeX
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
Thomas J. Gambino, Rob Gerritsen: A Data Base Design Decision Support System. VLDB 1977: 534-544 BibTeX
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
V. Gopalakrishna, C. E. Veni Madhavan: Performance Evaluation of Attribute-Based Tree Organization. ACM Trans. Database Syst. 5(1): 69-87(1980) BibTeX
Theo Härder: Implementing a Generalized Access Path Structure for a Relational Database System. ACM Trans. Database Syst. 3(3): 285-298(1978) BibTeX
Michael Hammer, Arvola Chan: Index Selection in a Self-Adaptive Data Base Management System. SIGMOD Conference 1976: 1-8 BibTeX
Michael Hammer, Dennis McLeod: The Semantic Data Model: A Modelling Mechanism for Data Base Applications. SIGMOD Conference 1978: 26-36 BibTeX
Michael Hammer, Bahram Niamir: A Heuristic Approach to Attribute Partitioning. SIGMOD Conference 1979: 93-101 BibTeX
Paula B. Hawthorn, Michael Stonebraker: Performance Analysis of a Relational Data Base Management System. SIGMOD Conference 1979: 1-12 BibTeX
Jeffrey A. Hoffer, Dennis G. Severance: The Use of Cluster Analysis in Physical Data Base Design. VLDB 1975: 69-86 BibTeX
Christer Hulten, Lars Söderlund: A Simulation Model for Performance Analysis of Large Shared Data Bases. VLDB 1977: 524-532 BibTeX
Keki B. Irani, Hing-Lung Lin: Queuing Network Models for Concurrent Transaction Processing in a Database System. SIGMOD Conference 1979: 134-142 BibTeX
Keki B. Irani, Subir Purkayastha, Toby J. Teorey: A Designer for DBMS-Processable Logical Database Structures. VLDB 1979: 219-231 BibTeX
Matti Jakobsson: Reducing block accesses in inverted files by partial clustering. Inf. Syst. 5(1): 1-5(1980) BibTeX
Beverly K. Kahn: A Method for Describing Information Required by the Database Design Process. SIGMOD Conference 1976: 53-64 BibTeX
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
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
J. H. Liou, S. Bing Yao: Multi-dimensional clustering for data base organizations. Inf. Syst. 2(4): 187-198(1977) BibTeX
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
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
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
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
Salvatore T. March, Dennis G. Severance: A Mathematical Modeling Approach to the Automatic Selection of Database Designs. SIGMOD Conference 1978: 52-65 BibTeX
T. H. Merrett: Database Cost Analysis: a Top-Down Approach. SIGMOD Conference 1977: 135-143 BibTeX
Michael F. Mitoma, Keki B. Irani: Automatic Data Base Schema Design and Optimization. VLDB 1975: 286-321 BibTeX
Isao Miyamoto: Hierarchical Performance Analysis Models for Data Base Systems. VLDB 1975: 322-352 BibTeX
Toshiyuki Nakamura, Tetsuo Mizoguchi: An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme. VLDB 1978: 489-495 BibTeX
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
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
Dominique Potier, Ph. Leblanc: Analysis of Locking Policies in Database Management Systems. Commun. ACM 23(10): 584-593(1980) BibTeX
Anne Putkonen: On the selection of the access path in inverted database organization. Inf. Syst. 4(1): 219-225(1979) BibTeX
Philippe Richard: Evaluation of the Size of a Query Expressed in Relational Algebra. SIGMOD Conference 1981: 155-163 BibTeX
Daniel R. Ries, Michael Stonebraker: Locking Granularity Revisited. ACM Trans. Database Syst. 4(2): 210-227(1979) BibTeX
Nick Roussopoulos, John Mylopoulos: Using Semantic Networks for Database Management. VLDB 1975: 144-172 BibTeX
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
Mario Schkolnick: The Optimal Selection of Secondary Indices for Files. Inf. Syst. 1(4): 141-146(1975) BibTeX
Mario Schkolnick: A Clustering Algorithm for Hierarchical Structures. ACM Trans. Database Syst. 2(1): 27-44(1977) BibTeX
Mario Schkolnick: A Survey of Physical Database Design Methodology and Techniques. VLDB 1978: 474-487 BibTeX
Ben Shneiderman, Victor Goodman: Batched Searching of Sequential and Tree Structured Files. ACM Trans. Database Syst. 1(3): 268-275(1976) BibTeX
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
Dennis G. Severance, John V. Carlis: A Practical Approach to Selecting Record Access Paths. ACM Comput. Surv. 9(4): 259-272(1977) BibTeX
Dennis G. Severance, Richardo Duhne: A Practitioner's Guide To Addressing Algorithms. Commun. ACM 19(6): 314-326(1976) BibTeX
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
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
Kenneth F. Siler: A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems. Commun. ACM 19(2): 84-95(1976) BibTeX
Alan Jay Smith: Sequentiality and Prefetching in Database Systems. ACM Trans. Database Syst. 3(3): 223-247(1978) BibTeX
Gary H. Sockut, Robert P. Goldberg: Database Reorganization - Principles and Practice. ACM Comput. Surv. 11(4): 371-395(1979) BibTeX
Bo Sundgren: Data Base Design in Theory and Practice - Towards an Integrated Methodology. VLDB Surveys 1978: 3-23 BibTeX
Toby J. Teorey, K. Sundar Das: Application of an Analytical Model to Evaluate Storage Structures. SIGMOD Conference 1976: 9-19 BibTeX
Toby J. Teorey, James P. Fry: The Logical Record Access Approach to Database Design. ACM Comput. Surv. 12(2): 179-211(1980) BibTeX
Frank Wm. Tompa: Choosing an Efficient Internal Schema. VLDB 1976: 65-77 BibTeX
William G. Tuel Jr.: An Analysis of Buffer Paging in Virtual Storage Systems. IBM J. Res. Dev. 20(5): 518-520(1976) BibTeX
Jeffrey D. Ullman: Principles of Database Systems, 1st Edition. Computer Science Press 1980
Anthony I. Wasserman, Karen Botnich: Annotated Bibliography on Data Design. SIGMOD Record 11(1): 45-77(1981) BibTeX
Eugene Wong, Karel Youssefi: Decomposition - A Strategy for Query Processing. ACM Trans. Database Syst. 1(3): 223-241(1976) BibTeX
S. Bing Yao: An Attribute Based Model for Database Access Cost Analysis. ACM Trans. Database Syst. 2(1): 45-67(1977) BibTeX
S. Bing Yao: Approximating the Number of Accesses in Database Organizations. Commun. ACM 20(4): 260-261(1977) BibTeX
S. Bing Yao: Optimization of Query Evaluation Algorithms. ACM Trans. Database Syst. 4(2): 133-155(1979) BibTeX
S. Bing Yao, D. DeJong: Evaluation of Database Access Paths. SIGMOD Conference 1978: 66-77 BibTeX
S. Bing Yao, Alan G. Merten: Selection of File Organization Using an Analytic Model. VLDB 1975: 255-267 BibTeX
Raymond T. Yeh, Jerry W. Baker: Toward a Design Methodology for DBMS: A Software Engineering Approach. VLDB 1977: 16-27 BibTeX
Karel Youssefi, Eugene Wong: Query Processing in a Relational Database Management System. VLDB 1979: 409-417 BibTeX
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
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
Carlo Zaniolo, Michel A. Melkanoff: On the Design of Relational Database Schemata. ACM Trans. Database Syst. 6(1): 1-47(1981) BibTeX
George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949

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
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
VLDB Proceedings (1977-1981): Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:45:12 2009