Heuristic-based conditional data indexing
View Patent ↗A computer system for the indexing of data in which a heuristic determination function is applied to predict an efficient index updating approach. The system is able to update an index relating to a first data set by incrementally updating the index or by a rebuild of the index at the completion of the addition of a second set of data to the first set of data. The system applies a heuristic determination function to the characteristics of the first set of data, its index, and the second set of data, to predict whether an incremental update or a rebuild update of the index will result in a more efficient rebuild of the data. The system applies this approach to a restore and rollforward recovery or a data load operation to improve the efficiency of these operations.
1. A method for updating an index on a database table when data is added to the table, comprising:
receiving data records to load into the table;
selecting one of a first operation and second operation, wherein the first operation incrementally updates the index on the table as each received data record is added to the table and the second operation rebuilds the index from the table after all the received data records have been added to the table; and
using the selected first operation to incrementally update the index with the data from the received data records, and using the selected second operation to rebuild the index with the data from the received data records.
2. The method of claim 1 , further comprising:
determining which of the first operation or second operation is more efficient, wherein the first or second operation determined to be more efficient is the selected operation used for updating the index with the received data records.
3. The method of claim 2 , wherein determining which operation is more efficient is a function of a percentage of the received data records to add to the table and characteristics of the index.
4. The method of claim 3 , wherein the characteristics of the index used in determining which operation is more efficient comprise a size and complexity of the index.
5. The method of claim 4 , wherein the index comprises a binary tree structure, and wherein a height of the index tree is indicative of the size and complexity of the index.
6. The method of claim 2 , wherein determining which operation is more efficient further comprises considering at least one of a following factors: an estimated time required to extract index keys from the table; an estimated time to sort the index keys, and an estimated time to rebuild the index from the sorted keys.
7. The method of claim 2 , further comprising:
maintaining a list of threshold values for different index sizes; and
using the number of received data records to add to the table to determine a comparison value, wherein determining whether the first or second operation is more efficient is based on the comparison value and the threshold for the size of the index to be updated.
8. the method of claim 7 , wherein the comparison value comprises the number of the received data records as a percentage of all data records in the table.
9. The method of claim 8 , wherein the index comprises a binary tree and wherein the list of threshold values provides one threshold for each of a plurality of different height index binary trees, wherein the threshold selected for comparison with the comparison value is based on the height of the index to update.
10. The method of claim 7 , wherein the first operation is more efficient if the comparison value is less than the threshold value and wherein the second operation is more efficient if the comparison value is greater than the threshold value.
11. The method of claim 1 , wherein selecting is performed by a heuristic determination function.
12. The method of claim 11 , wherein the heuristic determination function allows a user to specify a selection between an incremental update of the index and a full rebuild of the index.
13. The method of claim 11 , wherein the heuristic determination function takes as input index meta-data.
14. A system for updating an index on a database table when data is added to the table, comprising:
a database system including the table and the index on the table;
means for receiving data records to load into the table;
means for selecting one of a first operation and second operation, wherein the first operation incrementally updates the index on the table as each received data record is added to the table and the second operation rebuilds the index from the table after all the received data records have been added to the table; and
means for using the selected first operation to incrementally update the index with the data from the received data records and using the selected second operation to rebuild the index with the data from the received data records.
15. The system of claim 14 , further comprising:
means for determining which of the first operation or second operation is more efficient, wherein the first or second operation determined to be more efficient is selected to use for updating the index with the received data records.
16. The system of claim 15 , wherein the means for determining which operation is more efficient is a function of a percentage of the received data records to add to the table and characteristics of the index.
17. The system of claim 16 , wherein the characteristics of the index used in determining which operation is more efficient comprise a size and complexity of the index.
18. The system of claim 17 , wherein the index comprises a binary tree structure, and wherein a height of the index tree is indicative of the size and complexity of the index.
19. The system of claim 15 , wherein the means for determining which operation is more efficient further comprises considering at least one of a following factors; an estimated time required to extract index keys from the table; an estimated time to sort the index keys; and an estimated time to rebuild the index from the sorted keys.
20. The system of claim 15 , further comprising:
means for maintaining a list of threshold values for different index sizes; and
means for using the number of received data records to add to the table to determine a comparison value, wherein determining whether the first or second operation is more efficient is based on the comparison value and the threshold for the size of the index to be updated.
21. The system of claim 20 , wherein the comparison value comprises the number of the received data records as a percentage of all data records in the table.
22. The system of claim 21 , wherein the index comprises a binary tree and wherein the list of threshold values provides one threshold for each of a plurality of different height index binary trees, wherein the threshold selected for comparison with the comparison value is based on the height of the index to update.
23. The system of claim 20 , wherein the first operation is more efficient if the comparison value is less than the threshold value and wherein the second operation is more efficient if the comparison value is greater than the threshold value.
24. The system of claim 14 , wherein the means for selecting comprises a heuristic determination function.
25. The system of claim 24 , wherein the heuristic determination function allows a user to specify a selection between an incremental update of the index and a full rebuild of the index.
26. The system of claim 24 , wherein the heuristic determination function takes as input index meta-data.
27. A program for updating an index on a database table when data is added to the table, wherein the program is embedded in a computer readable medium and capable of causing a computer to perform:
receiving data records to load into the table;
selecting one of a first operation and second operation, wherein the first operation incrementally updates the index on the table as each received data record is added to the table and the second operation rebuilds the index from the table after all the received data records have been added to the table; and
using the selected first operation to incrementally update the index with the data from the received data records and using the selected second operation to rebuild the index with the data from the received data records.
28. The program of claim 27 , wherein the program is further capable of causing the processor to perform:
determining which of the first operation or second operation is more efficient, wherein the first or second operation determined to be more efficient is selected to use for updating the index with the received data records.
29. The program of claim 28 , wherein determining which operation is more efficient is a function of a percentage of the received data records to add to the table and characteristics of the index.
30. The program of claim 29 , wherein the characteristics of the index used in determining which operation is more efficient comprise a size and complexity of the index.
31. The program of claim 30 , wherein the index comprises a binary tree structure, and wherein a height of the index tree is indicative of the size and complexity of the index.
32. The program of claim 29 , wherein determining which operation is more efficient further comprises considering at least one of a following factors: an estimated time required to extract index keys from the table; an estimated time to sort the index keys; and an estimated time to rebuild the index from the sorted keys.
33. The program of claim 29 , wherein the program is further capable of causing the processor to perform:
maintaining a list of threshold values for different index sizes; and
using the number of received data records to add to the table to determine a comparison value, wherein determining whether the first or second operation is more efficient is based on the comparison value and the threshold for the size of the index to be updated.
34. The program of claim 33 , wherein the comparison value comprises the number of the received data records as a percentage of all data records in the table.
35. The program of claim 34 , wherein the index comprises a binary tree and wherein the list of threshold values provides one threshold for each of a plurality of different height index binary trees, wherein the threshold selected for comparison with the comparison value is based on the height of the index to update.
36. The program of claim 33 , wherein the first operation is more efficient if the comparison value is less than the threshold value and wherein the second operation is more efficient if the comparison value is greater than the threshold value.
37. The program of claim 27 , wherein selecting is performed by a heuristic determination function.
38. The program of claim 37 , wherein the heuristic determination function allows a user to specify a selection between an incremental update of the index and a full rebuild of the index.
39. The program of claim 37 , wherein the heuristic determination function takes as input index meta-data.