Methods for in-place online reorganization of a database

• US 6,411,964 B1
• Filed: 12/23/1998
• Issued: 06/25/2002
• Est. Priority Date: 12/23/1998
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iyer, Balakrishna Raghavendra, Sockut, Gary Howard
• Primary Examiner(s): Popovici, Dov
• Assistant Examiner(s): CHEUNG, MARY DA ZHI WANG
• Application Number:
  US09/220,084
• Time in Patent Office: 1,280 Days
• Field of Search: 707/1, 707/2, 707/3, 707/6, 707/8, 707/102, 707/103, 707/104, 707/200, 707/205, 707/206, 709/100-105, 709/200-203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

An in-place reorganization of a database 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.

Claims

1. A computer-implemented method of providing in-place reorganization of a database to achieve reasonably accurate results for user transactions during high-throughput concurrent usage of the database, comprising:

(a) tracing, in a computer, the reorganization'"'"'s movement of records across a user transaction'"'"'s position within a scan of the database by maintaining at least one movement list to track the reorganization'"'"'s movement of records that the user transaction through access, wherein the movement list comprises a differential list that tracks the records that the reorganization moves forward, backward, or behind the user transaction; and

(b) correcting, in the computer, a behavior of the user transaction to account for the movement of the records.

2. The method of claim 1, wherein the reorganization clusters data.

3. The method of claim 1, wherein the reorganization provides online restoration of clustering.

4. The method of claim 1, wherein the reorganization distributes free space evenly.

5. The method of claim 1, wherein the reorganization removes overflow.

6. The method of claim 1, wherein the reorganization is performed concurrently with a plurality of concurrent user transactions.

7. The method of claim 6, wherein the concurrent user transactions are allowed to use different types of access to the database.

8. The method of claim 1, wherein the reorganization allows repeatable read for the user transaction.

9. The method of claim 1, wherein the reorganization does not require repeatable read but does allow cursor stability for the user transaction.

10. The method of claim 1, wherein the tracking step comprises concurrently maintaining different types of movement lists appropriate for different types of access by different user transactions.

11. The method of claim 10, wherein a type of access determines a type of movement list used in the reorganization.

12. The method of claim 10, wherein the movement list comprises at least one of the lists in a group comprising a forward ordered list, backward ordered list, and the differential list.

13. The method of claim 12, wherein the forward ordered list tracks records that the reorganization moves forward.

14. The method of claim 12, wherein the forward ordered list tracks records that the user transaction has already processed.

15. The method of claim 12, further comprising omitting redundant processing of records that appear in the forward ordered list.

16. The method of claim 12, wherein the backward ordered list tracks records that the reorganization moves backward.

17. The method of claim 12, wherein the backward ordered list tracks records that the user transaction has not yet processed.

18. The method of claim 12, further comprising processing records that appear on the backward ordered list.

19. The method of claim 12, further comprising applying the differential list to a list of records maintained by the user transaction to correct the list of records.

20. The method of claim 19, wherein the list of records is derived from an index.

21. The method of claim 19, further comprising correcting the list of records by insert new entries of the list into the differential list and by deleting old entries of the list from the differential list.

22. The method of claim 12, further comprising modifying the differential list when the reorganization moves a record.

23. The method of claim 12, further comprising maintaining both a recent differential list and a composite differential list.

24. A computer-implemented system for providing in-place reorganization of a database to achieve reasonably accurate results for user transactions during high-throughput concurrent usage of the database, comprising:

(a) a computer;

(b) means, performed by the computer, for tracking a reorganization'"'"'s movement of records across a user transaction'"'"'s position within a scan of the database by maintaining at least one movement list to track the reorganization'"'"'s movement of records that the user transaction might access, wherein he movement list comprises a differential list that tracks the records that the reorganization moves forward, backward, or behind the user transaction; and

(c) means, performed by the computer, for correcting a behavior of the user transaction to account for the movement of the records.

25. The system of claim 24, wherein the reorganization clusters data.

26. The system of claim 24, wherein the reorganization provides online restoration of clustering.

27. The system of claim 24, wherein the reorganization distributes free space evenly.

28. The system of claim 24, wherein the reorganization removes overflow.

29. The system of claim 24, wherein the reorganization is performed concurrently with a plurality of concurrent user transactions.

30. The system of claim 29, wherein the concurrent user transactions are allowed to use different types of access to the database.

31. The system of claim 24, wherein the reorganization allows repeatable read for the user transaction.

32. The system of claim 24, wherein the reorganization does nor require repeatable read but does allow cursor stability for the user transaction.

33. The system of claim 24, wherein the means for tracking comprises means for concurrently maintaining different types of movement lists appropriate for different types of access by different user transactions.

34. The system of claim 33, wherein a type of access determines a type of movement list used in the reorganization.

35. The system of claim 33, when the movement list comprises at least one of the lists in a group comprising a ford ordered list, backward ordered list, and the differential list.

36. The system of claim 35, wherein the forward ordered list tracks records that the reorganization moves forward.

37. The system of claim 35, wherein the forward ordered list tracks records that the user transaction has already processed.

38. The system of claim 35, further comprising means for omitting redundant processing of records that appear in the forward ordered list.

39. The system of claim 35, wherein the backward ordered list tracks records that the reorganization moves backward.

40. The system of claim 35, wherein tie backward ordered list tracks records that the user transaction has not yet processed.

41. The system of claim 35, further comprising means for processing records that appear on the backward ordered list.

42. The system of claim 35, further comprising means for applying the differential list to a list of records maintained by die user transaction to correct the list of records.

43. The system of claim 42, wherein the list of records is derived from an index.

44. The system of claim 42, further comprising means for correcting the list of records by inserting new entries of the list into the differential list and by deleting old entries of the list from the differential list.

45. The system of claim 35, further comprising means for modifying the differential list when the reorganization moves a record.

46. The system of claim 35, further comprising means for maintaining both a recent differential list and a composite differential list.

47. An article of manufacture embodying logic for a computer-implemented method of providing in-place reorganization of a database to achieve reasonably accurate results for user transactions during high-throughput concurrent usage of the database, comprising:

(a) tracking the reorganization'"'"'s movement of records across a user transaction'"'"'s position within a scan of the database by maintaining at least one movement list to track the reorganization'"'"'s movement of records that the user transaction might access, wherein the movement list comprises a differential list that tracks the records that the reorganization moves forward, backward, or behind the user transaction; and

(b) correcting a behavior of the user transaction to account for the movement of the records.

48. The method of claim 47, wherein the reorganization clusters data.

49. The method of claim 47, wherein the reorganization provides online restoration of clustering.

50. The method of claim 47, wherein the reorganization distributes free space evenly.

51. The method of claim 47, wherein the reorganization removes overflow.

52. The method of claim 47, wherein the reorganization is performed concurrently with a plurality of concurrent user transactions.

53. The method of claim 52, wherein the concurrent user transactions are allowed to use different types of access to the database.

54. The method of claim 47, wherein the reorganization allows repeatable read for the user transaction.

55. The method of claim 47, wherein the reorganization does not require repeatable read but does allow cursor stability for the user transaction.

56. The method of claim 47, wherein the tracking step comprises concurrently maintaining different types of movement lists appropriate for different types of access by different user transactions.

57. The method of claim 56, wherein a type of access determines a type of movement list used in the reorganization.

58. The method of claim 56, wherein the movement list comprises at least one of the lists in a group comprising a forward ordered list, backward ordered list, and the differential list.

59. The method of claim 58, wherein the forward ordered list tracks records that the reorganization moves forward.

60. The method of claim 58, wherein the forward ordered list tracks records that the user transaction has already processed.

61. The method of claim 58, further comprising omitting redundant processing of records that appear in the forward ordered list.

62. The method of claim 58, wherein the backward ordered list tracks records that the reorganization moves backward.

63. The method of claim 58, wherein the backward ordered list tracks records that the user transaction has not yet processed.

64. The method of claim 58, further comprising processing records that appear on the backward ordered list.

65. The method of claim 58, further comprising applying the differential list to a list of records maintained by the user transaction to correct the list of records.

66. The method of claim 65, wherein the list of records is derived from an index.

67. The method of claim 65, further comprising correcting the list of records by inserting new entries of the list into the differential list and by deleting old entries of the list from the differential list.

68. The method of claim 58, further comprising modifying the differential list when the reorganization moves a record.

69. The method of claim 58, further comprising maintaining both a recent differential list and a composite differential list.