Prioritized merging for full-text index on relational store

• US 7,007,015 B1
• Filed: 05/01/2002
• Issued: 02/28/2006
• Est. Priority Date: 05/01/2002
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nayak, Tapas K.
• Primary Examiner(s): TRUONG, CAM Y T
• Application Number:
  US10/137,023
• Time in Patent Office: 1,399 Days
• Field of Search: 707/2, 707/4, 707/5, 707/7, 707/3, 707/100, 715/531
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/31 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99937 Sorting

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.

Claims

1. A method of full-text searching of a database, the method comprising:

providing data to be indexed for the full-text searching;

creating inverted lists in memory from a keyword memory by database management threads, the keyword memory accessed by a word breaker external to a database management system and by a database management system thread, wherein each inverted list comprises at least one of a plurality of keywords in the data, an identifier associated with the data and at least one occurrence of the at least one keyword in the data;

generating instances of an index based on the data, the index comprising part of a database indexing system of the database management system, the instances of the index generated from the inverted lists;

storing the instances of the index in a priority queue, wherein each instance is assigned a priority based on a number of keywords of the instance and a size of the instance;

scheduling a merge to be run on the instances of the index based on query load and merge load;

selecting instances to be merged based on the assigned priorities of the instances; and

merging the selected instances based on a selected type of merge to generate an instance of the index.

2. The method of claim 1, wherein the instances of the index are a first instance and a second instance;

merging the first instance and the second instance to generate a third instance of the index.

3. The method of claim 1, wherein the database management system is Structured Query Language (SQL) Server.

4. The method of claim 1, wherein scheduling a merge to be run is based on balancing query processing load and merge processing load.

5. The method of claim 4, wherein the balancing of query processing load and merge processing load is based on a comparison of a number of indexes in the priority queue and a configurable parameter representing a preferred number of indexes for the priority queue to contain.

6. The method of claim 1, wherein selecting at least two of a plurality of instances of the index in the priority queue comprises sorting the plurality of instances of the index in the priority queue in an order of increasing number of keywords in the index.

7. The method of claim 6, further comprising sorting the instances of the index in the priority queue into increasing order of size of the instance.

8. The method of claim 1, wherein selecting a type of merge to be performed comprises selecting one of a merge-in-place, a merge-out-of-place and an insert merge.

9. The method of claim 8, wherein a merge-in-place comprises merging all rows of selected instances of the index into a last selected instance of the index.

10. The method of claim 8, wherein a merge-out-of-place comprises merging all selected instances of the index into a new instance of the index.

11. A system for generating a full text search index integrated within a database management system comprising:

a processing thread pool comprising at least one of a plurality of processing threads of the database management system, the processing threads creating instances of the full text search index from inverted lists;

a memory for storing the inverted lists, the memory accessed by a word breaker external to the database management system and the database management system processing threads;

each inverted list comprising at least one of a plurality of keywords contained in data, an identifier associated with the data and at least one occurrence of the at least one keyword in the data;

a priority queue for storing and prioritizing the instances of the full text search index, wherein each instance is assigned a priority based on a number of rows of the instance and a size of the instance;

a merging thread pool comprising at least one of a plurality of merge threads, the at least one merge thread determining when a merge is scheduled, selecting, based on the assigned priorities of the instances, a plurality of instances from the priority queue, determining a type of merge to perform on the selected instances, and merging the selected instances based on the determined type of merge to generate an instance of the index.

12. The system of claim 11, wherein the database management system is SQL Server.

13. A computer-readable medium for full-text searching of a database comprising computer-executable instructions for:

providing data to be indexed for the full-text searching;

creating inverted lists in memory from a keyword memory, the keyword memory accessed by a word breaker external to a database management system and by a database management system thread, each inverted list comprising at least one of a plurality of keywords contained in the data, an identifier associated with the data and at least one occurrence of the at least one keyword in the data;

creating instances of an index based on the inverted lists, the index comprising part of a database indexing system of the database management system;

placing the instances of the index in a priority queue for processing, wherein each instance is assigned a priority based on a number of rows of the instance and a size of the instance;

selecting for merge a plurality of instances of the index from the priority queue based on the assigned priorities of the instances;

scheduling a merge to be run on the selected instances based on consideration of query load and merge load; and

merging the selected instances based on a selected type of merge to generate an instance of the index.