Performant and scalable merge strategy for text indexing

• US 20030229626A1
• Filed: 06/05/2002
• Published: 12/11/2003
• Est. Priority Date: 06/05/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nayak, Tapas K.
• Granted Patent: US 7,016,914 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: Y10S 707/917 Text
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A full-text search index system and method is generated by creating instances of a database index from an in-memory inverted list of keywords associated with a text identifier and the occurrences of the keyword in the text. Instances of the index are placed in a priority queue. A merge scheduling process determines when a merge should be initiated, selects instances of the index to be merged and selects a type of merge to perform.

Instances of an index are assigned a temporal indicator (timestamp). A set of instances is selected to be merged. The set of instances is validated and merged.

Claims

1. A method of indexing data and merging indexes within a database management system, in which the need for an in-memory table tracking currency of the data is eliminated, the method comprising:

assigning a temporal indicator associated with a crawl to an instance of an index generated by the crawl, wherein the index is part of an indexing system of a database management system;

assigning the instance of the index to a set of instances of the index to be merged; and

validating the set of instances to be merged, generating a set of valid instances.

2. The method of claim 1, wherein the crawl is a first crawl, the instance is a first instance, and the temporal indicator is a first temporal indicator, further comprising:

assigning a second temporal indicator associated with a second crawl to a second instance of an index generated by the second crawl;

assigning the second instance of the index to the set of instances to be merged; and

merging the set of valid instances to create a merged index instance.

3. The method of claim 2, wherein the first temporal indicator is not less than the second temporal indicator.

4. The method of claim 3, wherein the merged index instance is associated with the first temporal indicator.

5. The method of claim 2, wherein the first crawl and the second crawl are the same crawl.

6. The method of claim 1, wherein the temporal indicator associated with the crawl is assigned to a data item scanned by the crawl.

7. The method of claim 1, wherein the data item identifier and the temporal indicator assigned to the data item are stored in an indexed database table.

8. The method of claim 6, wherein a view of the table in temporal indicator sequence is maintained.

9. The method of claim 7, wherein the values of the table are compressed.

10. The method of claim 7, wherein the database table is a SQL SERVER table.

11. The method of claim 2, wherein validating the set of instances of the index comprises:

determining that the first temporal indicator is a maximum temporal indicator associated with the set of instances;

in response to determining that the second temporal indicator is identical to the maximum temporal indicator, merging the instances.

12. The method of claim 2, wherein validating the set of instances of the index comprises:

determining that the first temporal indicator is the maximum temporal indicator associated with the set of instances;

in response to determining that the second temporal indicator is not identical to the maximum temporal indicator, determining that the crawl associated with the second temporal indicator is done.

13. The method of claim 11, further comprising, in response to determining that a first subset of the set of instances associated with the first temporal indicator comprises a full crawl of a collection of data and that the second temporal indicator is less than the first temporal indicator, deleting a second subset of the set of instances associated with the second temporal indicator.

14. The method of claim 11, further comprising in response to determining that the set of instances does not include a subset wherein the subset comprises a full crawl of a collection of data, selecting the first instance from the set of instances and in response to determining that the first temporal indicator is not less than an instance in a priority queue of indexes not in the set, deleting the first instance.

15. The method of claim 2, wherein merging the first instance and the second instance further comprises:

for each data item identifier in the first instance and for each keyword in the data item, in response to determining that the first temporal indicator is identical to the maximum temporal indicator, selecting the first instance to generate an entry in the merged instance.

16. The method of claim 2, wherein merging the first instance and the second instance further comprises:

in response to determining that the first temporal indicator of the first instance comprising a keyword and a data item identifier is less than the maximum temporal indicator, determining that the first temporal indicator is a maximum temporal indicator for the keyword and the data item identifier in the set of instances and selecting the first instance to generate an entry in the merged instance for the keyword and data item identifier.

17. The method of claim 2, wherein merging the first instance and the second instance further comprises:

in response to determining that the first temporal indicator of the first instance comprising a keyword and a data item identifier is less than the maximum temporal indicator, determining that the first temporal indicator is not a maximum temporal indicator for the keyword and the data item identifier in the set of instances and removing the first instance from the set of instances to be merged.

18. The method of claim 17, wherein the first instance is returned to a priority queue.

19. A system for indexing data and merging indexes within a database management system, in which the need for an in-memory table tracking currency of the data is eliminated, the system comprising:

an indexing module for indexing data and assigning a temporal indicator to an instance of an index;

a priority queue for storing instances of an index for merging; and

a merging module for validating selected instances from the priority queue for merging, generating a set of valid instances to be merged.

20. The system of claim 19, further comprising a table for tracking an instance of an index and a temporal indicator associated with the instance.

21. The system of claim 19, further comprising a table for tracking the status of a crawl associated with an instance of an index.

22. The system of claim 19, further comprising a table for tracking a data identifier of a data item indexed by the indexing module and a temporal indicator associated with the data item.

23. The system of claim 19, wherein the set of valid instances of an index from the priority queue are merged into a merged index.

24. A computer-readable medium including computer-executable instructions for

assigning a first temporal indicator associated with a first crawl to a first instance of an index generated by the crawl;

and

assigning the first instance of the index to a set of instances of the index to be merged;

assigning a second temporal indicator associated with a second crawl to a second instance of an index generated by the second crawl;

assigning the second instance of the index to the set of instances to be merged;

validating the set of instances to be merged, generated valid instances; and

merging the valid instances to create a merged index instance.