Incremental indexing of a database table in a database

• US 7,792,839 B2
• Filed: 11/10/2005
• Issued: 09/07/2010
• Est. Priority Date: 01/13/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hrle, Namik, Teng, James Zu-Chia
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US11/271,677
• Publication Number:
  US 20060155752A1
• Time in Patent Office: 1,762 Days
• Field of Search: 707/100, 707/102
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2272 Management thereof

Abstract

The present system indexes a plurality of entries in a database that contains a database table having a base index. As a recent row is inserted in the database table, an index increment is generated based on the inserted row. Preferably, the index increment is smaller in size than the base index because it is recently generated. The smaller size of the index increment facilitates the management of the index increment. An index entry associated with the inserted row is added to the index increment, and the index increment is merged with the base index.

Claims

1. A computer-implemented method of indexing a plurality of entries in a database stored on a computer readable storage medium that contains a database table having a base index, the method comprising:

inserting a plurality of rows in the database table;

generating a plurality of index increments in response to insertion of the rows in the database table, the index increments comprising a subset of database index entries, each database index entry formatted to match a database index entry in a corresponding base index, wherein a number of database index entries in the index increments is less than a number of database index entries in the base index;

adding a plurality of database index entries associated with the inserted rows to the index increments;

generating an additional index increment from the plurality of index increments in response to an index increment having a memory size that approaches a memory size of volatile cache available to a database generating the additional index increment;

satisfying a database request by performing a parallel index scan of the base index and the index increments, the parallel index scan scanning the base index and the index increments concurrently, the database request received subsequent to insertion of the row; and

merging the index increments with the base index in response to a query response time for the database exceeding a first predefined criterion defined by an administrator of the database table and a number of index entries exceeding a second predefined criterion upon completion of the step of adding the plurality of index entries to the index increments, such that database index entries added to the base index satisfy a predefined ordering of the base index.

2. The method according to claim 1, wherein inserting the row comprises inserting a plurality of rows in the database table;

wherein adding the index entry comprises adding a plurality of index entries associated with the inserted rows, to the index increment; and

wherein merging the index increment occurs in response to the number of index entries exceeding a predefined criterion upon completion of the step of adding the plurality of index entries to the index increment.

3. The method according to claim 1, wherein the database comprises an additional base index, further comprising

generating an additional index increment corresponding to the additional base index;

and

merging the additional index increment with the additional base index.

4. The method according to claim 1, wherein a database system manages the database and wherein the merging of at least one of the plurality of index increments is postponed in response to a determination that the database system is currently performing insert processing.

5. A database management system for indexing a plurality of entries in a database stored on a computer readable storage medium that contains a database table having a base index, the system comprising:

a computer;

a computer readable storage medium for storing data, in communication with the computer;

a memory in communication with the computer, the memory comprising;

the database table storing a plurality of newly inserted rows;

an index increment building module for generating a plurality of index increments in response to insertion of the rows in the database table, the index increments comprising a subset of database index entries, each database index entry formatted to match a database index entry in a corresponding base index, wherein a memory size of the base index is greater than a memory size of volatile cache available to the database generating the index increments, an index increment based on the inserted rows, wherein the index increments are smaller than the base index;

the index increment building module further adding a plurality of database index entries associated with the inserted rows to the index increments;

the index increment building module further generating an additional index increment from the plurality of index increments in response to an index increment having a memory size that approaches the memory size of volatile cache available to the database generating the index increment;

satisfying a database request by performing a parallel index scan of the base index and the index increments, the parallel index scan scanning the base index and the index increments concurrently, the database request received subsequent to insertion of the row; and

an index increment merging module for merging the index increments with the base index in response to a query response time for the database exceeding a first predefined criterion defined by an administrator of the database table and a number of index entries exceeding a second predefined criterion upon completion of the step of adding the plurality of index entries to the index increments, such that database index entries added to the base index satisfy a predefined ordering of the base index.

6. The database management system according to claim 5, wherein the database table stores a plurality of inserted rows;

wherein the index increment building module adds a plurality of index entries associated with the inserted rows, to the index increment; and

wherein the index increment merging module merges the index increment upon adding the plurality of index entries to the index increment.

7. The database management system according to claim 6, wherein the database comprises an additional base index;

wherein the index increment building module generates an additional index increment corresponding to the additional base index; and

wherein the index increment merging module merges the additional index increment with the additional base index.

8. A computer program product stored in a computer readable storage medium, the computer program product having a plurality of program codes for indexing a plurality of entries in a database that contains a database table having a base index, the computer program product comprising:

the database table storing a plurality of newly inserted rows;

a program code for generating a plurality of index increments, in response to insertion of the rows in the database table, the index increments comprising a subset of database index entries, each database index entry formatted to match a database index entry in a corresponding base index, wherein a memory size of the base index is greater than a memory size of volatile cache available to the database generating the index increments;

a program code for adding a plurality of database index entries associated with the inserted rows to the index increments;

a program code for generating an additional index increment from the plurality of index increments in response to an index increment having a memory size that approaches the memory size of volatile cache available to the database generating the index increments;

satisfying a database request by performing a parallel index scan of the base index and the index increments, the parallel index scan scanning the base index and the index increments concurrently, the database request received subsequent to insertion of the row; and

a program code for merging the index increments with the base index in response to a query response time for the database exceeding a first predefined criterion defined by an administrator of the database table and a number of index entries exceeding a second predefined criterion upon completion of the step of adding the plurality of index entries to the index increments, the merging performed during off-peak hours, such that database index entries added to the base index satisfy a predefined ordering of the base index.

9. The computer program product according to claim 8, wherein the database comprises an additional base index;

wherein the program code for generating the index increment generates an additional index increment corresponding to additional base index; and

wherein the program code for adding the index entry merges the additional index increment with the additional base index.