REAL-TIME SEARCH OF VERTICALLY PARTITIONED, INVERTED INDEXES

• US 20130018891A1
• Filed: 09/13/2012
• Published: 01/17/2013
• Est. Priority Date: 07/13/2011
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: BUSCH, Michael, DESAI, Rajesh M., FOYLE, Robert A., JAYAPANDIAN, Magesh
• Granted Patent: US 9,171,062 B2
• Time in Patent Office: Days
• US Class Current: 707/742
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/319 Inverted lists
• CPC Class Codes: G06F 16/3331 Query processing

Abstract

Provided are techniques for processing a query. A query including constraints for at least two vertically partitioned, inverted indexes is received. The constraints in the query are separated based on the vertically partitioned, inverted indexes. A document identifier iterator is obtained for each of the constraints, wherein each document identifier iterator is associated with a posting list, and wherein each posting list is ordered by document identifier order. A run-time join of the posting lists is performed to obtain a final result set.

Claims

1. A method for processing a query, comprising:

receiving a query including constraints for at least two vertically partitioned, inverted indexes;

separating the constraints in the query based on the vertically partitioned, inverted indexes;

obtaining a document identifier iterator for each of the constraints, wherein each document identifier iterator is associated with a posting list, and wherein each posting list is ordered by document identifier order; and

performing a run-time join of the posting lists to obtain a final result set.

2. The method of claim 1, further comprising:

mapping each of the constraints to one of a primary query processor and an auxiliary query processor, wherein the primary query processor and the auxiliary query processor are each associated with one of the vertically partitioned, inverted indexes, and wherein the mapping depends on which of the vertically partitioned, inverted indexes is associated with that constraint.

3. The method of claim 1, further comprising:

evaluating a query parse tree with a primary query processor and an auxiliary query processor at a lowest level of the query parse tree by iterating through each posting list.

4. The method of claim 1, wherein one of the vertically partitioned, inverted indexes stores document data and the remaining vertically partitioned, inverted indexes store annotation data, and further comprising:

receiving a query with a document constraint and an annotation constraint;

processing the query using the vertically partitioned, inverted indexes to obtain a document posting list for the document constraint and a re-ordered annotation posting list for the annotation constraint; and

performing a run-time join of the document posting list and the re-ordered annotation posting list.

5. The method of claim 4, further comprising:

storing document identifiers in the one of the vertically partitioned, inverted indexes storing document data; and

at index construction time, storing the document identifiers in the remaining vertically partitioned, inverted indexes storing annotation data, wherein the document identifiers comprise foreign keys.

6. The method of claim 1, further comprising:

returning the final result set in response to the received query.

7. The method of claim 1, wherein a text document is categorized in a category, and wherein the category is stored in an auxiliary index for search and analysis in real-time.

8. The method of claim 1, further comprising:

creating vertically partitioned, inverted indexes, with each of the vertically partitioned, inverted indexes associated with one or more constraints.

9-24. -24. (canceled)