QUERY RESULT ITERATION FOR MULTIPLE QUERIES

• US 20110113052A1
• Filed: 01/14/2011
• Published: 05/12/2011
• Est. Priority Date: 06/08/2007
• Status: Abandoned Application

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: HÖRNKVIST, JOHN
• Application Number:
  US13/007,543
• Publication Number:
  US 20110113052A1
• Time in Patent Office: Days
• US Class Current: 707/759
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

Systems and methods for processing an inverted index are described. Multiple queries against the same inverted index are merged into merged query of unique nodes. The unique nodes are used to create a unified document set from which query result iteration is performed to eliminate redundancies and/or inefficiencies in processing the multiple queries separately. The merged query result is separated into the results for each of the multiple queries and returned to the respective originators of the queries. The unified document set can be limited to postings lists found in a single pulse of the inverted index to improve performance. Index updates can be applied to the merged query result to provide efficient and up to date query results.

Claims

7. A machine-readable storage medium storing program instructions that, when executed, cause a data processing system to perform a method of processing multiple queries against an inverted index, the method comprising:

receiving multiple queries against an inverted index, the inverted index having stored thereon postings lists for terms, a postings list being a linked list of one or more nodes, each of the one or more nodes representing one or more items containing a term;

merging the multiple queries to a single merged query, the single merged query containing unique search terms extracted from the multiple queries;

generating a unified document set of document sets present in postings lists having items containing terms that match the unique search terms extracted from the multiple queries;

iterating the unified document set to generate a merged query result; and

returning a query result responsive to each of the multiple queries, the query result being identified in a portion of the merged query result based on the respective unique search terms extracted from the multiple queries.

1. A machine-implemented method of processing multiple queries against an inverted index, the method comprising:

receiving multiple queries against an inverted index, the inverted index having stored thereon postings lists for terms, a postings list being a linked list of one or more nodes, each of the one or more nodes representing one or more items containing a term;

merging the multiple queries to a single merged query, the single merged query containing unique search terms extracted from the multiple queries;

generating a unified document set of document sets present in postings lists found in the inverted index to have items containing terms that match the unique search terms extracted from the multiple queries;

iterating the unified document set to generate a merged query result; and

returning a query result responsive to each of the multiple queries, the query result being identified in a portion of the merged query result based on the respective unique search terms extracted from the multiple queries.

2. A method as in claim 1, wherein the single merged query is formed as an array of unique nodes representing the unique search terms extracted from the multiple queries.

3. A method as in claim 2, wherein merging the multiple queries to the single merged query further comprises:

parsing each of the multiple queries into query trees;

optimizing the query trees for index searching;

extracting the unique search terms from the query trees in an order; and

placing the unique search terms into the array of unique nodes.

4. A method as in claim 1, further comprising updating the merged query result, wherein updating comprises:

determining that a delta postings list contains changes to items in the merged query result; and

updating the merged query result in accordance with the delta postings list, including removing from the merged query result identifications of those items no longer containing the matching search term and adding to the merged query result identifications of those items newly containing the matching search term.

5. A method as in claim 1, further comprising updating the merged query result, wherein updating comprises:

determining whether a live index contains postings lists for the term that matches the search term corresponding to the merged query;

processing the merged query against the live index; and

updating the merged query result in accordance with the live index merged query results.

6. A method as in claim 1, wherein the inverted index is formed in pulses comprising a group of items not occurring in any other pulse in the inverted index, and further wherein generating the unified document set is limited to document sets present in postings lists found in a single pulse formed in the inverted index.

8. A medium as in claim 7, wherein the single merged query is formed as an array of unique nodes representing the unique search terms extracted from the multiple queries.

9. A medium as in claim 8, wherein merging the multiple queries to the single merged query further comprises:

parsing each of the multiple queries into query trees;

optimizing the query trees for index searching;

extracting the unique search terms from the query trees in an order; and

placing the unique search terms into the array of unique nodes.

10. A medium as in claim 7, further comprising updating the merged query result, wherein updating comprises:

determining that a delta postings list contains changes for the items in the merged query result; and

updating the merged query result in accordance with the delta postings list, including removing from the merged query result identifications of those items no longer containing the matching search term and adding to the merged query result identifications of those items newly containing the matching search term.

11. A medium as in claim 7, further comprising updating the merged query result, wherein updating comprises:

determining whether a live index contains postings lists for the term that matches the search term corresponding to the merged query;

processing the merged query against the live index; and

updating the merged query result in accordance with the live index merged query results.

11-1. A medium as in claim 7, wherein the inverted index is formed in pulses comprising a group of items not occurring in any other pulse in the inverted index, and further wherein generating the unified document set is limited to document sets present in postings lists found in a single pulse formed in the inverted index.

12. A data processing system comprising:

means for receiving multiple queries against an inverted index, the inverted index having stored thereon postings lists for terms, a postings list being a linked list of one or more nodes, each of the one or more nodes representing one or more items containing a term;

means for merging the multiple queries to a single merged query, the single merged query containing unique search terms extracted from the multiple queries;

means for generating a unified document set of document sets present in postings lists having items containing terms that match the unique search terms extracted from the multiple queries;

means for iterating the unified document set to generate a merged query result;

means for returning a query result responsive to each of the multiple queries, the query result being identified in a portion of the merged query result based on the respective unique search terms extracted from the multiple queries.

13. A query server for processing multiple queries against an inverted index, the query server comprising:

a query processor to service a first query against an inverted index, the first query received from a first application, the inverted index having stored thereon postings lists for terms, a postings list being a linked list of one or more nodes, each of the one or more nodes representing one or more items containing a term, wherein the query processor is to;

place the first query in a query queue if the query processor is busy;

upon becoming idle, combining the first query with a second query in the query queue into a single merged query, the second query having been received from a second application, the single merged query containing unique search terms extracted from the first and second queries;

generating a unified document set of document sets present in postings lists having items containing terms that match the unique search terms extracted from the first and second queries;

iterating the unified document set to generate a merged query result; and

returning a query result to each of the first and second applications responsive to each of the first and second queries, each query result being identified in a portion of the merged query result based on the respective unique search terms extracted from each of the first and second queries.

14. A query server as in claim 13, wherein the query processor is to further:

determine that a query received from an application contains multiple queries against the same inverted index; and

combining the multiple queries into a single merged query before servicing the query, including combining the multiple queries with other queries received from other applications.