Online tracking and fixing of invalid guess-DBAs in secondary indexes and mapping tables on primary B+tree structures

1. A method for maintaining a system for database management, the method comprising:

during splitting of a leaf block of a database index recording an address of a newly created leaf block;

maintaining the address of the newly created leaf block in a list as part of metadata of a primary B+tree; and

maintaining a measure of invalid guess-database block addresses by calculating a ratio of a count of database block addresses in the list of new addresses to a total number of leaf blocks of the primary B+tree.

2. The method according to claim 1 , wherein the measure of invalid guess-database block addresses applies to mapping tables and secondary indexes on the primary B+tree.

3. The method according to claim 1 , wherein the list of database block addresses and the ratio are maintained only when the ratio is less than a threshold value.

4. The method according to claim 3 , wherein the threshold value for the ratio is about 10%.

5. The method according to claim 2 , further comprising:

adjusting a guess-DBA quality of at least one of the mapping table and the secondary index utilizing the ratio.

6. The method according to claim 3 , wherein if the ratio is below the threshold value the method further comprises:

selectively correcting entries in the mapping table and/or secondary index.

7. The method according to claim 6 , wherein correcting entries in the mapping table comprises for all rows in a list of blocks in the primary B+tree:

obtaining corresponding mapping table row identifiers and database block addresses of a current block in the list;

sorting the corresponding mapping table row identifiers;

obtaining mapping table rows corresponding to the mapping table row identifiers; and

updating a guess-DBA component if it has changed.

8. The method according to claim 7 , wherein the correcting is carried out on-line in a piece-wise manner.

9. The method according to claim 3 , wherein correcting entries in the secondary index comprises for all rows in a list of blocks in the primary B+tree:

obtaining a secondary index key, a primary key and a database block address of a current block in the list of blocks;

sorting the secondary index keys, primary keys and database addresses in order of (secondary index key, primary key) pairs;

obtaining an index row corresponding to the (secondary index key, primary key) pair; and

updating a guess-DBA component of the index row if the guess-DBA has changed.

10. The method according to claim 9 , wherein the correcting is carried out on-line in a piece-wise manner.

11. The method according to claim 3 , wherein if the ratio is above the threshold value the method further comprises:

correcting guess-database addresses on a per object basis.

12. The method according to claim 11 , wherein correcting guess-database block addresses on the mapping table comprises:

performing a full scan of the mapping table;

determining for each row of the mapping table a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the mapping table with the correct guess-database block address; and

committing the correct guess-database address to the mapping table in batches.

13. The method according to claim 11 , wherein correcting guess-database block addresses on a per object basis comprises for each secondary index object:

performing a full scan of the secondary index object;

determining for each row of the secondary index a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the secondary index with the correct guess-database block address; and

committing the correct guess-database block address to the secondary index in batches.

14. The method according to claim 1 , further comprising:

maintaining a list of database block addresses in the list.

15. A system comprising:

a list of addresses of blocks newly created during splitting of a primary B+tree;

a count of database block addresses in the list; and

a ratio of count of database block addresses to total number of leaf blocks as a measure of invalid guess-database block addresses.

16. The system according to claim 15 , wherein the database index is a primary B+tree structure, wherein the system further comprises:

a mapping table used to support bitmap indexes.

17. The system according to claim 16 , further comprising:

a bitmap index supported by the mapping table.

18. The system according to claim 15 , wherein the database index is a primary B+tree structure, wherein the system further comprises:

a secondary index structure comprising hybrid row identifiers.

19. A computer program product for performing a process for maintaining a database management system, comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of:

during splitting of a leaf block of a primary B+tree recording an address of a newly created leaf block;

maintaining the address of the newly created leaf block in a list as part of primary B+tree metadata; and

maintaining a measure of invalid guess-database block addresses by calculating a ratio of a count of database block addresses in the list of new addresses to a total number of leaf blocks of the primary B+tree.

20. A system for performing a process for maintaining a database management system, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of:

during splitting of a leaf block of a primary B+tree recording an address of a newly created leaf block;

maintaining the address of the newly created leaf block in a list as part of primary B+tree metadata; and

maintaining a measure of invalid guess-database block addresses by calculating a ratio of a count of database block addresses in the list of new addresses to a total number of leaf blocks of the primary B+tree.

21. The computer program product according to claim 19 , wherein the measure of invalid guess-database block addresses applies to mapping table and secondary indexes on the primary B+tree.

22. The computer program product according to claim 19 , wherein the list of database block addresses and the ratio are maintained only when the ratio is less than a threhold value.

23. The computer program product according to claim 22 , wherein the threshold value for the ratio is about 10%.

24. The computer program product according to claim 21 , further comprising:

adjusting a guess-DBA quality of at least one of the mapping table and the secondary index utilizing the ratio.

25. The computer program product according to claim 22 , wherein if the ratio is below the threshold value the computer program product further comprises:

selectively correcting entries in the mapping table and/so secondary index.

26. The computer program product according to claim 25 , wherein correcting entries in the mapping table comprises for all rows in a list of blocks in the primary B+tree:

obtaining corresponding mapping table row identifiers and database block addresses of a current block in the list;

sorting the corresponding mapping table row identifiers;

obtaining mapping table rows corresponding to the mapping table row identifiers; and

updating a guress-DBA component if it has changed.

27. The computer program product according to claim 26 , wherein the correcting is carried out on-line in a piece-wise manner.

28. The computer program product according to claim 22 , wherein correcting entries in the secondary index comprises for all rows in a list of blocks in the primary B+tree:

obtaining a secondary index key, a primary key and a database block address of a current block in the list of blocks;

sorting the secondary index keys, primary keys and database addresses in order of (secondary index key, primary key) pairs;

obtaining an index row corresponding to the (secondary index key, primary key) pair; and

updating a guess-DBA component of the index row if the guess-OBA has changed.

29. The computer program product according to claim 28 , wherein the correcting is carried out on-line in a piece-wise manner.

30. The computer program product according to claim 22 , wherein if the ratio is above the threshold value the computer program product further comprises:

correcting guess-database addresses on a per object basis.

31. The computer program product according to claim 30 , wherein correcting guess-database block addresses on the mapping table comprises: performing a full scan of the mapping table;

determining for each row of the mapping table a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the mapping table with the correct guess-database block address; and

committing the correct guess-database address to the mapping table in batches.

32. The computer program product according to claim 30 , wherein correcting guess-database block addresses on a per object basis comprises for each secondary index object:

performing a full scan of the secondary index object;

determining for each row of the secondary index a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the secondary index with the correct guess-database block address; and

committing the correct guess-database block address to the secondary index in batches.

33. The computer program product according to claim 19 , further comprising:

maintaining a list of database block addresses in the list.

34. The system according to claim 20 , wherein the measure of invalid guess-database block addresses applies to mapping tables and secondary indexes on the primary B+tree.

35. The system according to claim 20 , wherein the list of database block addresses and the ratio are maintained only when the ratio is less than a threshold value.

36. The system according to claim 35 , wherein the threshold value for the ratio is about 10%.

37. The system according to claim 34 , further comprising:

adjusting a guess-DBA quality of at least one of the mapping table and the secondary index utilizing the ratio.

38. The system according to claim 35 , wherein if the ratio is below the threshold value the system further comprises:

selectively correcting entries in the mapping table and/or secondary index.

39. The system according to claim 38 , wherein correcting entries in the mapping table comprises for all rows in a list of blocks in the primary B+tree:

obtaining corresponding mapping table row identifiers and database block addresses of a current block in the list;

sorting the corresponding mapping table row identifiers;

obtaining mapping table rows corresponding to the mapping table row identifiers; and

updating a guess-DBA component if it has changed.

40. The system according to claim 39 , wherein the correcting is carried out on-line in a piece-wise manner.

41. The system according to claim 35 , wherein correcting entries in the secondary index comprises for all rows in a list of blocks in the primary B+tree:

obtaining a secondary index key, a primary key and a database block address of a current block in the list of blocks;

sorting the secondary index keys, primary keys and database addresses in order of (secondary index key, primary key) pairs;

obtaining an index row corresponding to the (secondary index key, primary key) pair; and

updating a guess-DBA component of the index row if the guess-DBA has changed.

42. The system according to claim 41 , wherein the correcting is carried out on-line in a piece-wise manner.

43. The system according to claim 35 , wherein if the ratio is above the threshold value the system further comprises:

correcting guess-database addresses on a per object basis.

44. The system according to claim 43 , wherein correcting guess- database block addresses on the mapping table comprises:

performing a full scan of the mapping table;

determining for each row of the mapping table a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the mapping table with the correct guess-database block address; and

committing the correct guess-database address to the mapping table in batches.

45. The system according to claim 43 , wherein correcting guess- database block addresses on a per object basis comprises for each secondary index object:

performing a full scan of the secondary index object;

determining for each row of the secondary index a correct guess-database block address by traversing the primary B+tree up to a penultimate level;

updating each row of the secondary index with the correct guess-database block address; and

committing the correct guess-database block address to the secondary index in batches.

46. The system according to claim 20 , further comprising:

maintaining a list of database block addresses in the list.

47. A method of maintaining a system for database management, the method comprising:

modifying a primary index in the database management system;

storing information relating to the modification of the primary index in a secondary index or a mapping table in the database management system; and

maintaining a measure of quality of the secondary index or the mapping table based on a ratio of information relating to the modification of the primary index to a size of the primary index.

48. The method of claim 47 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of the amount of information relating to the modification of the primary index in the secondary index or the mapping table to a size of the primary index.

49. The method of claim 47 , wherein modifying the primary index comprises splitting a leaf block of the primary index.

50. The method of claim 49 , wherein storing information relating to the modification of the primary index in a secondary index or a mapping table comprises storing an address of a leaf block created during the splitting of the leaf block of the primary index in the secondary index or the mapping table.

51. The method of claim 50 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of a number of addresses of leaf blocks created during the splitting of the leaf block of the primary index that are stored in the secondary index or the mapping table to a total number of leaf blocks in the primary index.

52. The method of claim 47 , further comprising:

adjusting a quality of at least one of the secondary index or the mapping table utilizing the ratio.

53. The method of claim 47 , wherein the ratio is maintained only when the ratio is less than a threshold value.

54. The method of claim 53 , wherein the threshold value for the ratio is about 10%.

55. The method of claim 53 , wherein if the ratio is below the threshold value the method further comprises:

selectively correcting the information in the secondary index or the mapping table.

56. A computer program product for performing a process for maintaining a database management system, comprising:

a computer readable medium; and

computer program instructions, recorded on the computer readable medium, executable by a processor, for performing the steps of:

modifying a primary index in the database management system;

storing information relating to the modification of the primary index in a secondary index or a mapping table in the database management system; and

maintaining a measure of quality of the secondary index or the mapping table based on a ratio of information relating to the modification of the primary index to a size of the primary index.

57. The computer program product of claim 56 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of the amount of information relating to the modification of the primary index in the secondary index or the mapping table to a size of the primary index.

58. The computer program product of claim 56 , wherein modifying the primary index comprises splitting a leaf block of the primary index.

59. The computer program product of claim 58 , wherein storing information relating to the modification of the primary index in a secondary index or a mapping table comprises storing an address of a leaf block created during the splitting of the leaf block of the primary index in the secondary index or the mapping table.

60. The computer program product of claim 59 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of a number of addresses of leaf blocks created during the splitting of the leaf block of the primary index that are stored in the secondary index or the mapping table to a total number of leaf blocks in the primary index.

61. The computer program product of claim 56 , further comprising:

adjusting a quality of at least one of the secondary index or the mapping table utilizing the ratio.

62. The computer program product of claim 56 , wherein the ratio is maintained only when the ratio is less than a threshold value.

63. The computer program product of claim 62 , wherein the threshold value for the ratio is about 10%.

64. The computer program product of claim 62 , wherein if the ratio is below the threshold value the computer program product further comprises:

selectively correcting the information in the secondary index or the mapping table.

65. A system for performing a process for maintaining a database management system, comprising:

a processor operable to execute computer program instructions; and

a memory operable to store computer program instructions executable by the processor, for performing the steps of:

modifying a primary index in the database management system;

storing information relating to the modification of the primary index in a secondary index or a mapping table in the database management system; and

maintaining a measure of quality of the secondary index or the mapping table based on a ratio of information relating to the modification of the primary index to a size of the primary index.

66. The system of claim 65 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of the amount of information relating to the modification of the primary index in the secondary index or the mapping table to a size of the primary index.

67. The system of claim 65 , wherein modifying the primary index comprises splitting a leaf block of the primary index.

68. The system of claim 67 , wherein storing information relating to the modification of the primary index in a secondary index or a mapping table comprises storing an address of a leaf block created during the splitting of the leaf block of the primary index in the secondary index or the mapping table.

69. The system of claim 68 , wherein maintaining a measure of quality of the secondary index or a mapping table comprises calculating a ratio of a number of addresses of leaf blocks created during the splitting of the leaf block of the primary index that are stored in the secondary index or the mapping table to a total number of leaf blocks in the primary index.

70. The system of claim 65 , further comprising:

adjusting a quality of at least one of the secondary index or the mapping table utilizing the ratio.

71. The system of claim 65 , wherein the ratio is maintained only when the ratio is less than a threshold value.

72. The system of claim 71 , wherein the threshold value for the ratio is about 10%.

73. The system of claim 71 , wherein if the ratio is below the threshold value the system further comprises:

selectively correcting the information in the secondary index or the mapping table.