Query result iteration

• US 8,024,351 B2
• Filed: 05/17/2010
• Issued: 09/20/2011
• Est. Priority Date: 06/08/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Hornkvist, John Martin
• Primary Examiner(s): Perveen; Rehana
• Assistant Examiner(s): BUI, THUY T
• Application Number:
  US12/781,767
• Publication Number:
  US 20100228771A1
• Time in Patent Office: 491 Days
• Field of Search: 707/769, 707/765, 707/705, 707/715
• US Class Current: 707/769
• CPC Class Codes: G06F 16/319 Inverted lists

Abstract

Systems and methods for processing an index are described. A pulse in an inverted index refers to a group of items that do not occur in any other pulse in the index. When processing a query against an inverted index in which pulses are present, the query is processed against a single pulse. The end of the pulse is determined based on the characteristics of the pulse and the linked list nodes that comprise the postings lists from which the index was generated. In some embodiments, index updates are applied to the query result obtained from a single pulse to provide an efficient and up to date query result.

Claims

1. A machine-implemented method of restricting a query of an inverted index to a portion of the inverted index, the method comprising:

receiving a query against an inverted index, the inverted index having stored thereon postings lists of 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;

restricting the query to items represented in a subset of nodes, the subset of nodes having been processed in a previous update to the inverted index, wherein each item represented in the subset of nodes is not represented in any other node in the inverted index;

returning a query result responsive to restricting the query to the items represented in the subset of nodes, the query result identifying those items represented in the subset of nodes containing the term that matches a search term corresponding to the query; and

updating the query result, wherein updating comprises one or both of;

determining that a delta postings list contains changes for the items to which the query has been restricted and updating the query result in accordance with the delta postings list, including removing from the query result identifications of those items no longer containing the matching search term and adding to the query result identifications of those items newly containing the matching search term; and

determining that a live index contains postings lists for the term that matches the search term corresponding to the query, processing the query against the live index, and updating the query result in accordance with the live index query results.

2. The method of claim 1, wherein restricting the query to items represented in the subset of nodes in the inverted index comprises:

processing a starting node, the starting node being a node in an inverted index representing one or more items containing the matching search term;

processing a closest next node, the closest next node being an older node in the inverted index being pointed to from the starting node, the closest next node representing one or more additional items also containing the matching search term, the additional items being older than the items represented in the starting node;

tracking which item of the items encountered during processing the nodes is newest, the newest item having been created more recently than the others; and

returning the query result responsive to tracking which item is newest, the query result identifying those items represented in the subset of nodes containing the matching search term from the oldest item up to the newest item encountered during processing the nodes.

3. The method of claim 2, wherein the newest item encountered during processing the nodes is identified by having an item ID with a greater value as compared to lesser values of item IDs for other items encountered during processing the nodes, the greater values indicating that the item has been created more recently than items having items IDs with lesser values.

4. A machine-implemented data processing system for restricting a query of an inverted index to a portion of the inverted index, the data processing system comprising:

an input means for receiving a query against an inverted index, the inverted index having stored thereon postings lists of 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;

a processing means for restricting the query to items represented in a subset of nodes, the subset of nodes having been processed in a previous update to the inverted index, wherein each item represented in the subset of nodes is not represented in any other node in the inverted index;

an output means for returning a query result responsive to restricting the query to the items represented in the subset of nodes, the query result identifying those items represented in the subset of nodes containing the term that matches a search term corresponding to the query; and

a processing means for updating the query result, wherein the processing means for updating includes at least one of;

means for determining that a delta postings list contains changes for the items to which the query has been restricted and means for updating the query result in accordance with the delta postings list, including a means for removing from the query result identifications of those items no longer containing the matching search term and a means for adding to the query result identifications of those items newly containing the matching search term; and

means for determining that a live index contains postings lists for the term that matches the search term corresponding to the query, means for processing the query against the live index, and means for updating the query result in accordance with the live index query results.

5. The machine-implemented data processing system of claim 4, wherein the processing means for restricting the query to items represented in the subset of nodes in the inverted index includes:

means for processing a starting node, the starting node being a node in an inverted index representing one or more items containing the matching search term;

means for processing a closest next node, the closest next node being an older node in the inverted index being pointed to from the starting node, the closest next node representing one or more additional items also containing the matching search term, the additional items being older than the items represented in the starting node;

means for tracking which item of the items encountered during processing the nodes is newest, the newest item having been created more recently than the others; and

wherein the output means for returning the query result includes means for returning the query result responsive to tracking which item is newest, the query result identifying those items represented in the subset of nodes containing the matching search term from the oldest item up to the newest item encountered during processing the nodes.

6. The machine-implemented data processing system of claim 5, wherein the means for tracking which item of the items encountered during processing the nodes is newest includes means for determining which item has an item ID with a greater value as compared to lesser values of item IDs for other items encountered during processing the nodes, the greater values indicating that the item has been created more recently than items having items IDs with lesser values.

7. A non-transitory computer readable storage medium containing executable program instructions for causing a data processing system to perform a method of restricting a query of an inverted index to a portion of the inverted index, the method comprising:

receiving a query against an inverted index, the inverted index having stored thereon postings lists of 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;

restricting the query to items represented in a subset of nodes, the subset of nodes having been processed in a previous update to the inverted index, wherein each item represented in the subset of nodes is not represented in any other node in the inverted index;

returning a query result responsive to restricting the query to the items represented in the subset of nodes, the query result identifying those items represented in the subset of nodes containing the term that matches a search term corresponding to the query; and

updating the query result, wherein updating comprises one or both of;

determining that a delta postings list contains changes for the items to which the query has been restricted and updating the query result in accordance with the delta postings list, including removing from the query result identifications of those items no longer containing the matching search term and adding to the query result identifications of those items newly containing the matching search term; and

determining whether a live index contains postings lists for the term that matches the search term corresponding to the query, processing the query against the live index, and updating the query result in accordance with the live index query results.

8. The non-transitory computer readable storage medium of claim 7, wherein restricting the query to items represented in the subset of nodes in the inverted index comprises:

processing a starting node, the starting node being a node in an inverted index representing one or more items containing the matching search term;

processing a closest next node, the closest next node being an older node in the inverted index being pointed to from the starting node, the closest next node representing one or more additional items also containing the matching search term, the additional items being older than the items represented in the starting node;

tracking which item of the items encountered during processing the nodes is newest, the newest item having been created more recently than the others; and

returning the query result responsive to tracking which item is newest, the query result identifying those items represented in the subset of nodes containing the matching search term from the oldest item up to the newest item encountered during processing the nodes.

9. The non-transitory computer readable storage medium of claim 8, wherein the newest item encountered during processing the nodes is identified by having an item ID with a greater value as compared to lesser values of item IDs for other items encountered during processing the nodes, the greater values indicating that the item has been created more recently than items having items IDs with lesser values.

10. A machine implemented method of querying an inverted index, the method comprising:

receiving a query against an index having pulses comprising a group of item IDs not occurring in any other pulse in the index;

processing, in a data processing system, the query starting with a node in a current pulse of the index, where the starting node is obtained from a sorted queue of nodes representing items containing a search term corresponding to the query;

tracking a highest item ID encountered when processing each node in the current pulse;

processing all item IDs up to the highest item ID in the current pulse; and

determining whether a next node in the sorted queue of nodes is beyond an end of the current pulse; and

applying updates to the index to a result of processing the query against the current pulse, wherein applying updates to the index includes applying a delta postings list for the search term to the query result.

11. The method of claim 10, wherein determining whether the next node in the sorted queue of nodes is beyond an end of the current pulse is determining that the next node in the sorted queue of nodes is a closest next node, the closest next node being pointed to from the currently processed node.

12. The method of claim 10 wherein the index is an inverted index.

13. The method of claim 10 further comprising:

returning a query result responsive to the query based on the processing.

14. A machine readable non-transitory storage medium containing instructions which when executed cause a data processing system to perform a method of querying an inverted index, the method comprising:

receiving a query against an index having pulses comprising a group of item IDs not occurring in any other pulse in the index;

processing the query starting with a node in a current pulse of the index, where the starting node is obtained from a sorted queue of nodes representing items containing a search term corresponding to the query;

tracking a highest item ID encountered when processing each node in the current pulse;

processing all item IDs up to the highest item ID in the current pulse;

determining whether a next node in the sorted queue of nodes is beyond an end of the current pulse; and

applying updates to the index to a query result of processing the query against the current pulse, wherein applying updates includes applying a delta postings list for the search term to the query result.

15. The medium of claim 14, wherein determining whether the next node in the sorted queue of nodes is beyond an end of the current pulse is determining that the next node in the sorted queue of nodes is a closest next node, the closest next node being pointed to from the currently processed node.