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}
}
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.
CDROM Version: Load the CDROM "Volume 1 Issue 4, VLDB '75-'88" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...
Printed Edition
Very Large Data Bases, 7th International Conference, September 9-11, 1981, Cannes, France, Proceedings.
IEEE Computer Society 1981
Contents
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)
![bibliographical record in XML](../../xml.gif)
- [BaHs78]
- Jayanta Banerjee, David K. Hsiao:
Performance Study of a Database Machine in Supporting Relational Databases.
VLDB 1978: 319-329
![bibliographical record in XML](../../xml.gif)
- [Bato]
- ...
- [Bell81]
- ...
- [BeIr77]
- Elias Berelian, Keki B. Irani:
Evaluation and Optimization.
VLDB 1977: 545-555
![bibliographical record in XML](../../xml.gif)
- [BlEs77]
- Mike W. Blasgen, Kapali P. Eswaran:
Storage and Access in Relational Data Bases.
IBM Systems Journal 16(4): 362-377(1977)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [Card73]
- Alfonso F. Cardenas:
Evaluation and Selection of File Organization - A Model and System.
Commun. ACM 16(9): 540-548(1973)
![bibliographical record in XML](../../xml.gif)
- [Card75]
- Alfonso F. Cardenas:
Analysis and Performance of Inverted Data Base Structures.
Commun. ACM 18(5): 253-263(1975)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [Casa81]
- ...
- [Chen76]
- Peter P. Chen:
The Entity-Relationship Model - Toward a Unified View of Data.
ACM Trans. Database Syst. 1(1): 9-36(1976)
![bibliographical record in XML](../../xml.gif)
- [Chen77]
- ...
- [ChYa77]
- Peter P. Chen, S. Bing Yao:
Design and Performance Tools for Data Base Systems.
VLDB 1977: 3-15
![bibliographical record in XML](../../xml.gif)
- [Chr81]
- ...
- [ClYa78]
- Billy G. Claybrook, Chung-Shu Yang:
Efficient algorithms for answering queries with unsorted multilists.
Inf. Syst. 3(2): 93-97(1978)
![bibliographical record in XML](../../xml.gif)
- [DeBu78]
- Peter J. Denning, Jeffrey P. Buzen:
The Operational Analysis of Queueing Network Models.
ACM Comput. Surv. 10(3): 225-261(1978)
![bibliographical record in XML](../../xml.gif)
- [Demo80]
- Robert Demolombe:
Estimation of the Number of Tuples Satisfying a Query Expressed in Predicate Calculus Language.
VLDB 1980: 55-63
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [FaSc75]
- Gilles Farley, Stewart A. Schuster:
Query Execution and Index Selection for Relational Data Bases.
VLDB 1975: 519
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [FrBe76]
- ...
- [Gall81]
- ...
- [GaGe77]
- Thomas J. Gambino, Rob Gerritsen:
A Data Base Design Decision Support System.
VLDB 1977: 534-544
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [HaCh76]
- Michael Hammer, Arvola Chan:
Index Selection in a Self-Adaptive Data Base Management System.
SIGMOD Conference 1976: 1-8
![bibliographical record in XML](../../xml.gif)
- [HaMc78]
- Michael Hammer, Dennis McLeod:
The Semantic Data Model: A Modelling Mechanism for Data Base Applications.
SIGMOD Conference 1978: 26-36
![bibliographical record in XML](../../xml.gif)
- [HaNi79]
- Michael Hammer, Bahram Niamir:
A Heuristic Approach to Attribute Partitioning.
SIGMOD Conference 1979: 93-101
![bibliographical record in XML](../../xml.gif)
- [HaSt79]
- Paula B. Hawthorn, Michael Stonebraker:
Performance Analysis of a Relational Data Base Management System.
SIGMOD Conference 1979: 1-12
![bibliographical record in XML](../../xml.gif)
- [HoSe75]
- Jeffrey A. Hoffer, Dennis G. Severance:
The Use of Cluster Analysis in Physical Data Base Design.
VLDB 1975: 69-86
![bibliographical record in XML](../../xml.gif)
- [Hubb78]
- ...
- [HuSo77]
- Christer Hulten, Lars Söderlund:
A Simulation Model for Performance Analysis of Large Shared Data Bases.
VLDB 1977: 524-532
![bibliographical record in XML](../../xml.gif)
- [IrLi79]
- Keki B. Irani, Hing-Lung Lin:
Queuing Network Models for Concurrent Transaction Processing in a Database System.
SIGMOD Conference 1979: 134-142
![bibliographical record in XML](../../xml.gif)
- [IrPT79]
- Keki B. Irani, Subir Purkayastha, Toby J. Teorey:
A Designer for DBMS-Processable Logical Database Structures.
VLDB 1979: 219-231
![bibliographical record in XML](../../xml.gif)
- [Jako80]
- Matti Jakobsson:
Reducing block accesses in inverted files by partial clustering.
Inf. Syst. 5(1): 1-5(1980)
![bibliographical record in XML](../../xml.gif)
- [Kahn76]
- Beverly K. Kahn:
A Method for Describing Information Required by the Database Design Process.
SIGMOD Conference 1976: 53-64
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [LaSh76]
- ...
- [Levy80]
- ...
- [LiYa77]
- J. H. Liou, S. Bing Yao:
Multi-dimensional clustering for data base organizations.
Inf. Syst. 2(4): 187-198(1977)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [MaSe78]
- Salvatore T. March, Dennis G. Severance:
A Mathematical Modeling Approach to the Automatic Selection of Database Designs.
SIGMOD Conference 1978: 52-65
![bibliographical record in XML](../../xml.gif)
- [Merr77]
- T. H. Merrett:
Database Cost Analysis: a Top-Down Approach.
SIGMOD Conference 1977: 135-143
![bibliographical record in XML](../../xml.gif)
- [Milr75]
- Michael F. Mitoma, Keki B. Irani:
Automatic Data Base Schema Design and Optimization.
VLDB 1975: 286-321
![bibliographical record in XML](../../xml.gif)
- [Miya75]
- Isao Miyamoto:
Hierarchical Performance Analysis Models for Data Base Systems.
VLDB 1975: 322-352
![bibliographical record in XML](../../xml.gif)
- [MyWB78]
- ...
- [NaMi78]
- Toshiyuki Nakamura, Tetsuo Mizoguchi:
An Analysis of Storage Utilization Factor in Block Split Data Structuring Scheme.
VLDB 1978: 489-495
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [Pezz80]
- ...
- [PoLe80]
- Dominique Potier, Ph. Leblanc:
Analysis of Locking Policies in Database Management Systems.
Commun. ACM 23(10): 584-593(1980)
![bibliographical record in XML](../../xml.gif)
- [Putk79]
- Anne Putkonen:
On the selection of the access path in inverted database organization.
Inf. Syst. 4(1): 219-225(1979)
![bibliographical record in XML](../../xml.gif)
- [RaRo76]
- ...
- [RaHu77]
- ...
- [Rich81]
- Philippe Richard:
Evaluation of the Size of a Query Expressed in Relational Algebra.
SIGMOD Conference 1981: 155-163
![bibliographical record in XML](../../xml.gif)
- [RiSt79]
- Daniel R. Ries, Michael Stonebraker:
Locking Granularity Revisited.
ACM Trans. Database Syst. 4(2): 210-227(1979)
![bibliographical record in XML](../../xml.gif)
- [RoHi75]
- ...
- [RoMy75]
- Nick Roussopoulos, John Mylopoulos:
Using Semantic Networks for Database Management.
VLDB 1975: 144-172
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [Schk75]
- Mario Schkolnick:
The Optimal Selection of Secondary Indices for Files.
Inf. Syst. 1(4): 141-146(1975)
![bibliographical record in XML](../../xml.gif)
- [Schk77]
- Mario Schkolnick:
A Clustering Algorithm for Hierarchical Structures.
ACM Trans. Database Syst. 2(1): 27-44(1977)
![bibliographical record in XML](../../xml.gif)
- [Schk78a]
- Mario Schkolnick:
A Survey of Physical Database Design Methodology and Techniques.
VLDB 1978: 474-487
![bibliographical record in XML](../../xml.gif)
- [Schk78b]
- ...
- [ScGo76]
- Ben Shneiderman, Victor Goodman:
Batched Searching of Sequential and Tree Structured Files.
ACM Trans. Database Syst. 1(3): 268-275(1976)
![bibliographical record in XML](../../xml.gif)
- [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
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [SeDu76]
- Dennis G. Severance, Richardo Duhne:
A Practitioner's Guide To Addressing Algorithms.
Commun. ACM 19(6): 314-326(1976)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [Sile76]
- Kenneth F. Siler:
A Stochastic Evaluation Model for Database Organization in Data Retrieval Systems.
Commun. ACM 19(2): 84-95(1976)
![bibliographical record in XML](../../xml.gif)
- [Smit78]
- Alan Jay Smith:
Sequentiality and Prefetching in Database Systems.
ACM Trans. Database Syst. 3(3): 223-247(1978)
![bibliographical record in XML](../../xml.gif)
- [SmBr80]
- ...
- [SmSm78]
- ...
- [SoGo79]
- Gary H. Sockut, Robert P. Goldberg:
Database Reorganization - Principles and Practice.
ACM Comput. Surv. 11(4): 371-395(1979)
![bibliographical record in XML](../../xml.gif)
- [Sund78]
- Bo Sundgren:
Data Base Design in Theory and Practice - Towards an Integrated Methodology.
VLDB Surveys 1978: 3-23
![bibliographical record in XML](../../xml.gif)
- [TeDa76]
- Toby J. Teorey, K. Sundar Das:
Application of an Analytical Model to Evaluate Storage Structures.
SIGMOD Conference 1976: 9-19
![bibliographical record in XML](../../xml.gif)
- [TeFr80]
- Toby J. Teorey, James P. Fry:
The Logical Record Access Approach to Database Design.
ACM Comput. Surv. 12(2): 179-211(1980)
![bibliographical record in XML](../../xml.gif)
- [TeOb78]
- ...
- [Tomp76]
- Frank Wm. Tompa:
Choosing an Efficient Internal Schema.
VLDB 1976: 65-77
![bibliographical record in XML](../../xml.gif)
- [TsLo81]
- ...
- [Tuel76]
- William G. Tuel Jr.:
An Analysis of Buffer Paging in Virtual Storage Systems.
IBM J. Res. Dev. 20(5): 518-520(1976)
![bibliographical record in XML](../../xml.gif)
- [TuRo75]
- ...
- [Ullm80]
- Jeffrey D. Ullman:
Principles of Database Systems, 1st Edition.
Computer Science Press 1980
![bibliographical record in XML](../../xml.gif)
- [WaBo81]
- Anthony I. Wasserman, Karen Botnich:
Annotated Bibliography on Data Design.
SIGMOD Record 11(1): 45-77(1981)
![bibliographical record in XML](../../xml.gif)
- [WoKa78]
- ...
- [WoYo76]
- Eugene Wong, Karel Youssefi:
Decomposition - A Strategy for Query Processing.
ACM Trans. Database Syst. 1(3): 223-241(1976)
![bibliographical record in XML](../../xml.gif)
- [WoMy77]
- ...
- [Yao77a]
- S. Bing Yao:
An Attribute Based Model for Database Access Cost Analysis.
ACM Trans. Database Syst. 2(1): 45-67(1977)
![bibliographical record in XML](../../xml.gif)
- [Yao77b]
- S. Bing Yao:
Approximating the Number of Accesses in Database Organizations.
Commun. ACM 20(4): 260-261(1977)
![bibliographical record in XML](../../xml.gif)
- [Yao79]
- S. Bing Yao:
Optimization of Query Evaluation Algorithms.
ACM Trans. Database Syst. 4(2): 133-155(1979)
![bibliographical record in XML](../../xml.gif)
- [YaDe78]
- S. Bing Yao, D. DeJong:
Evaluation of Database Access Paths.
SIGMOD Conference 1978: 66-77
![bibliographical record in XML](../../xml.gif)
- [YaMe75]
- S. Bing Yao, Alan G. Merten:
Selection of File Organization Using an Analytic Model.
VLDB 1975: 255-267
![bibliographical record in XML](../../xml.gif)
- [YaNW78]
- ...
- [YeBa77]
- Raymond T. Yeh, Jerry W. Baker:
Toward a Design Methodology for DBMS: A Software Engineering Approach.
VLDB 1977: 16-27
![bibliographical record in XML](../../xml.gif)
- [YoWo79]
- Karel Youssefi, Eugene Wong:
Query Processing in a Relational Database Management System.
VLDB 1979: 409-417
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [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)
![bibliographical record in XML](../../xml.gif)
- [ZaMe81]
- Carlo Zaniolo, Michel A. Melkanoff:
On the Design of Relational Database Schemata.
ACM Trans. Database Syst. 6(1): 1-47(1981)
![bibliographical record in XML](../../xml.gif)
- [Zipf49]
- George Kingsley Zipf:
Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology.
Addison-Wesley 1949
![bibliographical record in XML](../../xml.gif)
Copyright © Tue Mar 16 02:21:56 2010
by Michael Ley (ley@uni-trier.de)