ACM SIGMOD Anthology TKDE dblp.uni-trier.de

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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

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

  1. 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)
  2. Chendong Zou, Betty Salzberg: Safely and Efficiently Updating References During On-line Reorganization. VLDB 1998: 512-522
  3. Edward Omiecinski: Concurrent File Reorganization: Clustering, Conversion and Maintenance. IEEE Data Eng. Bull. 19(2): 25-32(1996)
  4. 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
  5. 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