Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-23
2002-06-25
Popovici, Dov (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06411964
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates in general to database management systems performed by computers, and in particular, to a method of providing in-place reorganization of a database.
2. Description of Related Art
(Note: This application references a number of different publications as indicated throughout the specification by reference numbers enclosed in brackets, e.g., [x]. A list of these different publications ordered according to these reference numbers can be found in Section 8 of the “Detailed Description of the Preferred Embodiment.” Each of these publications is incorporated by reference herein.)
Any database management system (DBMS) can need some type of reorganization. Reorganization of a database is defined as changing some aspect of the logical and/or physical arrangement of the database. A tutorial paper referenced in [12] discusses issues in reorganization and types of reorganization. This specification describes the problem in reorganizing offline, and the need for online reorganization. (See, e.g., [11]).
The type of reorganization described herein involves restoration of clustering. Clustering is the practice of storing records near each other if they meet certain criteria. One popular criterion is consecutive values in a column of the records. Clustering should reduce disk input/output for records that users often access together. When users write data into the database, this writing can decrease the amount of clustering and thus degrade performance.
Reorganization can restore clustering and performance. During most types of reorganization in a typical database, the area being reorganized is offline or only partially available; users cannot write (and perhaps cannot even read) data in that area. However, a highly available database (a database that is to be fully available 24 hours per day, 7 days per week) should not go offline for significant periods, of course. Applications that require high availability include reservations, finance (especially global finance), process control, hospitals, police, armed forces, and Internet service.
Even for less essential applications, many database administrators prefer 24 hour availability. The maximum tolerable period of unavailability is specific to the application. When queried, DBMS customers (not all of whom have highly available databases) state that the maximum tolerable period ranges from 0 to 5 hours. Even without such a preference for 24-hour availability, reorganizing a very large database might require much longer than the maximum tolerable period of unavailability.
As examples of very large databases, a survey paper [6] mentions a database with several terabytes of data and the desire for one with petabytes. The author of one book [14] considers offline reorganization such an important problem for very large databases that he defines a very large database as one “whose reorganization by reloading takes a longer time than the users can afford to have the database unavailable.” These considerations call for the ability to reorganize the database online (concurrently with usage or incrementally within users' transactions), so that users can read and write the database during most or all phases of reorganization.
In the context of papers that do not concentrate on online reorganization, many people have stated the need for the ability to reorganize online. As the amount of information and dependence on computers both grow, the number of very large or highly available databases will grow. Therefore, the importance of online reorganization will grow.
The present invention provides methods for in-place online reorganization (specifically, for restoration of clustering). The data structures are those of IBM's DBMS Database 2 (DB2) for OS/390 [4], but the concepts in the methods presented herein should apply to many DBMS's. The methods perform reorganization in place; i.e., they do not make a new copy of the data being reorganized. To allow high-throughput concurrent usage by users of the database, the methods track the reorganization's movement of records across a user's position within a scan of data, and they correct the behavior of a user transaction to account for the movement.
This specification describes relevant features of a DBMS, discusses the advantages of the present invention over previous research (including the novelty of the methods), presents the concepts in the methods, describes the methods in more detail, and proposes extensions based on the methods.
SUMMARY OF THE INVENTION
To overcome the limitations in the prior art described above, and to overcome other limitations that will become apparent upon reading and understanding the present specification, the present invention discloses a method, system, and article of manufacture for providing in-place reorganization of a database that achieves reasonably accurate results for users during high-throughput concurrent usage of the database. The reorganization's movement of records across a user transaction's position within a scan of the database is tracked. The behavior of the user transaction is corrected to account for the movement of the records.
REFERENCES:
patent: 4627019 (1986-12-01), Ng
patent: 4648036 (1987-03-01), Gallant
patent: 4823310 (1989-04-01), Grand
patent: 4847754 (1989-07-01), Obermarck et al.
patent: 5222235 (1993-06-01), Hintz et al.
patent: 5247672 (1993-09-01), Mohan
patent: 5367675 (1994-11-01), Cheng et al.
patent: 5434994 (1995-07-01), Shaheen et al.
patent: 5455944 (1995-10-01), Haderle et al.
patent: 5504888 (1996-04-01), Iwamoto et al.
patent: 5596706 (1997-01-01), Shimazaki et al.
patent: 5596747 (1997-01-01), Katabami et al.
patent: 5692178 (1997-11-01), Shaughnessy
patent: 5717919 (1998-02-01), Kodavalla et al.
patent: 5721915 (1998-02-01), Sockut et al.
patent: 5778392 (1998-07-01), Stockman et al.
patent: 5815415 (1998-09-01), Bentley et al.
patent: 5864849 (1999-01-01), Bohannon et al.
patent: 5940813 (1999-08-01), Hutchings
patent: 5983225 (1999-11-01), Anfindsen
patent: 6023706 (2000-02-01), Schmuck et al.
patent: 6067545 (2000-05-01), Wolff
patent: 6144970 (2000-11-01), Bonner et al.
patent: 6185601 (2001-02-01), Wolff
patent: 06-67944 (1994-03-01), None
patent: 06-67950 (1994-03-01), None
patent: 07-175699 (1995-07-01), None
patent: 07-244604 (1995-09-01), None
patent: 07-311702 (1995-11-01), None
patent: 09-34758 (1997-02-01), None
IBM Corporation, “DB2 for OS/390 Version 5: Utility Guide and Reference—Chapter 2-14: Reorg,” SC26-8967-00, Jun. 1997.
IBM Technical Disclosure Bulletin, “Reducing Buffer Pool Working Set for Certain Database Utilities,” Vol. 32, No. 10B, Mar. 1990, p. 339.
Nakamura, T. et al., “Performance Improvement in Relational Database Management System,” NTT R&D, vol. 41, No. 12, 1992, pp. 1397-1406—Translation: English abstract.
Omiecinski, E. et al., “Concurrent File Reorganization for Record Clustering: A Performance Study,” Proceedings of the 8thInternational Conference on Data Engineering, IEEE-CS, Feb. 1992, IEEE, 1992, pp. 265-272.
Omiecinski, E. et al., “Performance Analysis of a Concurrent File Reorganization Algorithm for Record Clustering,” IEEE Transactions on Knowledge and Data Engineering, vol. 6, No. 2, Apr. 1994, pp. 248-257.
Salzberg, B. et al., “Principles of Transaction-Based On-Line Reorganization,” Proceeding of the 18thVLDB Conference, Vancouver, British Columbia, Canada 1992, Morgan Kaufmann Publishers, San Mateo, CA, Aug. 1992, pp. 511-520.
Sockut, G.H. et al., “A Method for On-Line Reorganization of a Database,” IBM Systems Journal, vol. 36, No. 3, 1997, pp. 411-436.
Sockut, G.H. et al, “Reorganizing Database Concurrently with Usage: A Survey,” Technical Report 03.488, IBM, Santa Teresa Laboratory, San Jose, CA, Jun. 1993.
Sockut, G.H. et al., “Database Reorganization—Principles and Practice,” Computing Surveys, ACM, vol. 11, No. 4, Dec. 1979, pp. 371-395.
Iyer Balakrishna Raghavendra
Sockut Gary Howard
Gates & Cooper LLP
Popovici Dov
Wang Mary
LandOfFree
Methods for in-place online reorganization of a database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods for in-place online reorganization of a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods for in-place online reorganization of a database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2891035