Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering.
Edward Omiecinski, Liehuey Lee, Peter Scheuermann:
Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering.
IEEE Trans. Knowl. Data Eng. 6(2): 248-257(1994)@article{DBLP:journals/tkde/OmiecinskiLS94,
author = {Edward Omiecinski and
Liehuey Lee and
Peter Scheuermann},
title = {Performance Analysis of a Concurrent File Reorganization Algorithm
for Record Clustering},
journal = {IEEE Trans. Knowl. Data Eng.},
volume = {6},
number = {2},
year = {1994},
pages = {248-257},
ee = {db/journals/tkde/OmiecinskiLS94.html},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX
Abstract
This paper presents a simulation based performance
analysis of a concurrent file reorganization algorithm. We
examine the effect on throughput of (i) buffer size, (ii)
degree of reorganization, (iii) write probability of
transactions, (iv) multiprogramming level and (v) degree of
clustered transactions. The problem of file reorganization
which we consider involves altering the placement of records
on pages of a secondary storage device. In addition, we
want this reorganization to be done in-place, i.e., using
the file's original storage space for the newly reorganized
file. Our approach is also appropriate for a non in-place
reorganization as well. The motivation for such a physical
change, i.e., record clustering, is to improve the database
system's performance, i.e., minimizing the number of page
accesses made in answering a set of queries. There are
numerous record clustering algorithms, but they usually do
not solve the entire problem, i.e., they do not specify how
to efficiently reorganize the file to reflect the clustering
assignment which they determine. In previous work, we have
presented an algorithm that is a companion to general record
clustering algorithms, i.e., it actually transforms the
file. In this work we show through simulation that our
algorithm, when run concurrently with user transactions,
provides an acceptable level of overall database system
performance.
Copyright © 1994 by The Institute of
Electrical and Electronic Engineers, Inc. (IEEE).
Abstract used with permission.
CDROM Version: Load the CDROM "Volume 3 Issue 3, TKDE 1993-1995" and ...
DVD Version: Load ACM SIGMOD Anthology DVD 2" and ...
BibTeX
References
- [1]
- Rakesh Agrawal, Michael J. Carey, Miron Livny:
Models for Studying Concurrency Control Performance: Alternatives and Implications.
SIGMOD Conference 1985: 108-121 BibTeX
- [2]
- Morton M. Astrahan, Mike W. Blasgen, Donald D. Chamberlin, Kapali P. Eswaran, Jim Gray, Patricia P. Griffiths, W. Frank King III, Raymond A. Lorie, Paul R. McJones, James W. Mehl, Gianfranco R. Putzolu, Irving L. Traiger, Bradford W. Wade, Vera Watson:
System R: Relational Approach to Database Management.
ACM Trans. Database Syst. 1(2): 97-137(1976) BibTeX
- [3]
- Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman:
Concurrency Control and Recovery in Database Systems.
Addison-Wesley 1987, ISBN 0-201-10715-5
Contents BibTeX
- [4]
- Matti Jakobsson:
Reducing block accesses in inverted files by partial clustering.
Inf. Syst. 5(1): 1-5(1980) BibTeX
- [5]
- Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
- [6]
- C. Mohan:
ARIES/KVL: A Key-Value Locking Method for Concurrency Control of Multiaction Transactions Operating on B-Tree Indexes.
VLDB 1990: 392-405 BibTeX
- [7]
- Edward Omiecinski:
Incremental File Reorganization Schemes.
VLDB 1985: 346-357 BibTeX
- [8]
- Edward Omiecinski:
Concurrent file conversion between B+-tree and linear hash files.
Inf. Syst. 14(5): 371-383(1989) BibTeX
- [9]
- Edward Omiecinski, Wei Liu, Ian F. Akyildiz:
An Analytical Model of a Deferred and Incremental Update Strategy for Secondary Indexes.
FODO 1989: 218-222 BibTeX
- [10]
- Edward Omiecinski, Peter Scheuermann:
A Global Approach to Record Clustering and File Reorganization.
SIGIR 1984: 201-219 BibTeX
- [11]
- Daniel R. Ries, Michael Stonebraker:
Locking Granularity Revisited.
ACM Trans. Database Syst. 4(2): 210-227(1979) BibTeX
- [12]
- Peter Scheuermann, Aris M. Ouksel:
Multidimensional B-trees for associative searching in database systems.
Inf. Syst. 7(2): 123-137(1982) BibTeX
- [13]
- Peter Scheuermann, Young Chul Park, Edward Omiecinski:
A Heuristic File Reorganization Algorithm Based on Record Clustering.
BIT 29(3): 428-447(1989) BibTeX
- [14]
- 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
- [15]
- Gary H. Sockut, Robert P. Goldberg:
Database Reorganization - Principles and Practice.
ACM Comput. Surv. 11(4): 371-395(1979) BibTeX
- [16]
- Lars Söderlund:
Concurrent Data Base Reorganization - Assessment of a Powerful Technique through Modeling.
VLDB 1981: 499-509 BibTeX
- [17]
- ...
- [18]
- S. Bing Yao:
Approximating the Number of Accesses in Database Organizations.
Commun. ACM 20(4): 260-261(1977) BibTeX
- [19]
- Clement T. Yu, Cheing-Mei Suen, K. Lam, M. K. Siu:
Adaptive Record Clustering.
ACM Trans. Database Syst. 10(2): 180-204(1985) BibTeX
Referenced by
- Peter Zabback, Ibrahim H. Önyüksel, Peter Scheuermann, Gerhard Weikum:
Database Reorganization in Parallel Disk Arrays with I/O Service Stealing.
IEEE Trans. Knowl. Data Eng. 10(5): 855-858(1998)
- Chendong Zou, Betty Salzberg:
Safely and Efficiently Updating References During On-line Reorganization.
VLDB 1998: 512-522
- Edward Omiecinski:
Concurrent File Reorganization: Clustering, Conversion and Maintenance.
IEEE Data Eng. Bull. 19(2): 25-32(1996)
- Kiran J. Achyutuni, Edward Omiecinski, Shamkant B. Navathe:
Two Techniques for On-Line Index Modification in Shared Nothing Parallel Databases.
SIGMOD Conference 1996: 125-136
- Edward Omiecinski, Liehuey Lee, Peter Scheuermann:
Concurrent File Reorganization for Record Clustering: A Performance Study.
ICDE 1992: 265-272
BibTeX
ACM SIGMOD Anthology - DBLP:
[Home | Search: Author, Title | Conferences | Journals]
IEEE Transactions on Data and Knowledge Engineering: Copyright © by IEEE,
Joint ACM SIGMOD / IEEE Computer Society Anthology: Copyright © by ACM (info@acm.org) and IEEE, Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sun May 17 00:28:01 2009