APPARATUS, SYSTEM, AND METHOD FOR IMPROVING UPDATE PERFORMANCE FOR INDEXING USING DELTA KEY UPDATES

• US 20090063400A1
• Filed: 09/05/2007
• Published: 03/05/2009
• Est. Priority Date: 09/05/2007
• Status: Abandoned Application

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lee, Christina M., Borkar, Dipti D., Lyle, Robert W.
• Application Number:
  US11/850,443
• Publication Number:
  US 20090063400A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures

Abstract

An apparatus, system, and method are disclosed for updating database indexes on complex data types. Instead of deleting all the index keys for an old indexable entity, only the old index keys which are not in the set of new index keys associated with a replacement indexable entity will be deleted. In addition, only new index keys which are not in the set of old index keys are inserted into the index. In this manner, performance is greatly improved by elimination unnecessary deletions and insertions to an index.

Claims

1. A system for updating database indexes, the system comprising:

a database;

a database management system (DBMS) for managing the database, the DBMS comprising an index manager configured to perform operations comprising;

identifying at least one index comprised of index keys, the index keys defined by an index key definition and corresponding to nodes of an indexable entity;

processing an old indexable entity in response to an update command;

generating a set of delete index keys, the delete index keys corresponding to nodes of the old indexable entity satisfying the index key definition of the index;

processing a replacement indexable entity wherein the replacement indexable entity is intended to replace the old indexable entity in response to an update command;

generating a set of insert index keys, the insert index keys corresponding to nodes of the replacement indexable entity satisfying the index key definition of the index;

inserting into the index only the insert index keys that do not match one of the delete index keys; and

deleting from the index only the delete index keys that do not match one of the insert index keys.

2. The system of claim 1, wherein the operations further comprise storing the set of delete index keys in a buffer.

3. The system of claim 2, wherein the operations further comprise storing each insert index key in the buffer in response to determining that the insert index key does not match one of the delete index keys.

4. The system of claim 3, wherein the operations further comprise marking a delete index key with an identifier in response to determining that that delete index key matches one of the insert index keys.

5. The system of claim 4, wherein deleting from the index only the delete index keys that do not match one of the insert index keys is accomplished by deleting index keys from the index which correspond to delete index keys in the buffer not marked with the identifier.

6. The system of claim 5, wherein the operations further comprise discarding each insert index key that does not match one of the delete index keys such that each matching insert index key is not stored in the buffer.

7. The system of claim 6, wherein the inserting into the index of an insert index key occurs in response to the insert index key remaining in the buffer after the replacement indexable entity has been completely processed.

8. The system of claim 7, wherein the old indexable entity is processed in the same order as the replacement indexable entity such that the set of delete index keys is generated in the same order as the set of insert index keys, and wherein the old indexable entity is processed only once to generate the set of delete index keys and the replacement indexable entity is processed only once to generate the set of insert index keys.

9. The system of claim 1, wherein the operations further comprise adding the set of delete index keys and the set of insert index keys into a list and sorting the delete index keys and insert index keys in the list to define index pairs and index singles based on one or more index key parts, an index pair comprising a delete index key and a matching insert index key, an index single comprising one of a single insert index key and a single delete index key.

10. The system of claim 1, wherein the set of delete index keys is generated in a different order than the set of insert index keys.

11. The system of claim 1, wherein the indexable entity is an Extensible Markup Language (XML) document.

12. The system of claim 1, wherein inserting insert index keys into and deleting delete index keys from the index occurs immediately in response to determining that a delete index key does not have a matching insert index key or that an insert index key does not have a matching delete index key such that the use of a buffer for storing the delete index keys and insert index keys may be avoided.

13. A computer program product comprising a computer readable medium having computer usable program code stored on a tangible medium and executable on a processor to perform operations for updating database indexes, the operations of the computer program product comprising:

identifying at least one index comprised of index keys, the index keys defined by an index key definition and corresponding to nodes of an indexable entity in a database;

processing an old indexable entity in response to an update command;

generating a delete index key for each node of the old indexable entity that satisfies the index key definition, each delete index key corresponding to an index key stored in the at least one index;

processing a replacement indexable entity, the replacement indexable entity configured to replace the old indexable entity in response to an update command;

generating an insert index key for each node of the replacement indexable entity satisfying the index key definition;

sorting the delete index keys and insert index keys in a list to define index pairs and index singles based on one or more index key parts, an index pair comprising a delete index key and a matching insert index key, an index single comprising one of a single insert index key and a single delete index key;

deleting each index key from the index which corresponds to a single delete index key in the list; and

inserting each single insert index key into the index.

14. The computer program product of claim 13, further comprising storing the delete index keys and insert index keys in a buffer prior to sorting.

15. The computer program product of claim 13, further comprising processing the list and skipping index pairs in the list such that index pairs are not applied to the index.

16. The computer program product of claim 13, wherein the one or more index key parts comprises a node identifier.

17. The computer program product of claim 13, wherein the one or more index key parts comprises a text value from an indexable entity.

18. The computer program product of claim 13, wherein at least one node of the old indexable entity is unchanged in a corresponding node of the replacement indexable entity.

20. The computer program product of claim 16, further comprising discarding each insert index key that matches one of the delete index keys in the buffer such that the matching insert index key is not stored in the buffer.

19. A computer program product comprising a computer readable medium having computer usable program code stored on a tangible medium and executable on a processor to perform operations for updating database indexes, the operations of the computer program product comprising:

identifying at least one index comprised of index keys, the index keys defined by an index key definition and corresponding to nodes of an indexable entity in a database;

processing an old indexable entity in response to an update command;

generating a delete index key for each node of the old indexable entity that satisfies the index key definition of the index, each delete index key corresponding to an existing index key stored in the at least one index;

storing the generated delete index keys in a buffer;

processing a replacement indexable entity wherein the replacement indexable entity is intended to replace the old indexable entity in response to an update command;

generating an insert index key for each node of the replacement indexable entity satisfying the index key definition of the index;

storing each insert index key in the buffer in response to determining that the insert index key does not match any of the delete index keys stored in the buffer;

marking each delete index key that matches one of the insert index keys with an identifier;

deleting from the index only the index keys corresponding to delete index keys in the buffer that are not marked with the identifier; and

inserting into the index each insert index key stored in the buffer.