Checkpointing iterators during search

• US 8,738,598 B2
• Filed: 07/25/2012
• Issued: 05/27/2014
• Est. Priority Date: 08/31/2007
• Status: Active Grant

• Current Assignee: Zhigu Holdings Limited
• Original Assignee: Microsoft Corporation
• Inventors: Walters, Chad, Biewald, Lukas, Joffe, Nitay, James, Andrew Alan
• Primary Examiner(s): PENG, HUAWEN A
• Application Number:
  US13/557,639
• Publication Number:
  US 20120290554A1
• Time in Patent Office: 671 Days
• Field of Search: 707/708, 707/715, 707/723, 707/706
• US Class Current: 707/706
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Tools and techniques are described herein for checkpointing iterators during search. These tools may provide methods that include instantiating iterators in response to a search request. The iterators include fixed state information that remains constant over a life of the iterator, and further include dynamic state information that is updated over the life of the iterator. The iterators traverse through postings lists in connection with performing the search request. As the iterators traverse the posting lists, the iterators may update their dynamic state information. The iterators may then evaluate whether to create checkpoints, with the checkpoints including representations of the dynamic state information.

Claims

1. A computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

instantiating at least one iterator in response to a search request, wherein the iterator includes fixed state information that remains constant over a life of the iterator, and includes dynamic state information that is updated over the life of the iterator;

creating a storage structure associated with the iterator and storing a representation of the dynamic state information in the storage structure;

creating a stack structure that includes a plurality of entries, further storing the representation of the dynamic state information in one of the entries, and further storing at least a further representation of a further instance of the dynamic state information in a further one of the entries;

traversing the iterator through at least a portion of at least one postings list in connection with performing a search in response to the search request;

updating at least one instance of the dynamic state information, as the iterator traverses through at least the portion of the postings list while performing the search; and

evaluating whether to create a checkpoint of the iterator at one or more points during the iterator traversing through at least the portion of the postings list while performing the search, wherein the checkpoint includes at least a representation of the dynamic state information at one of the points.

2. The storage medium of claim 1, further comprising instructions for storing the representation of only the dynamic state information, as associated with the checkpoint.

3. The storage medium of claim 1, further comprising instructions for storing data from which the dynamic state information is calculated when restoring the checkpoint of the iterator.

4. The storage medium of claim 1, further comprising instructions for evaluating whether the iterator is associated with at least one child iterator.

5. The storage medium of claim 1, further comprising instructions for sending a command to at least one child iterator, associated with the iterator, to create a further checkpoint associated with the child iterator, wherein the further checkpoint includes at least a further representation of further dynamic state information maintained by the child iterator.

6. The storage medium of claim 1, wherein the instructions for evaluating whether to create a checkpoint include instructions for directing the iterator to create a checkpoint, in response to a checkpoint command received from a parent iterator.

7. The storage medium of claim 1, wherein the instructions for evaluating whether to create a checkpoint include instructions for directing the iterator to create a checkpoint.

8. A computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

traversing an iterator through at least a portion of at least one postings list in response to at least one search request, wherein the iterator includes fixed state information that remains constant over a life of the iterator, and dynamic state information that is updated over the life of the iterator, wherein the iterator includes a storage structure associated with the iterator for storing a representation of the dynamic state information, wherein a stack structure includes a pima it of entries for storing the representation of the dynamic state information in one of the entries and for storing at least a further representation of a further instance of the dynamic state information in a further one of the entries, wherein the storage structure further includes a representation of at least one checkpoint, and wherein the checkpoint represents at least one instance of the dynamic state information at a particular point during the iterator traversing through at least the portion of the postings list while performing a search;

updating at least one instance of the dynamic state information as the iterator traverses through at least the portion of the postings list while performing the search; and

evaluating whether to restore the iterator to a previous state represented by the dynamic state information represented by the checkpoint.

9. The storage medium of claim 8, further comprising instructions for loading the dynamic state information from the storage structure into the iterator, so as to restore the iterator to the previous state.

10. The storage medium of claim 8, further comprising instructions for calculating the dynamic state information based on information stored in the storage structure when checkpointing the iterator.

11. The storage medium of claim 8, further comprising instructions for evaluating whether the iterator is associated with at least one child iterator.

12. The storage medium of claim 11, further comprising instructions for sending a command to the at least one child iterator, directing the child iterator to restore dynamic state information maintained by the child iterator.

13. The storage medium of claim 8, wherein the instructions for evaluating whether to restore the iterator include instructions for directing the iterator to restore dynamic state information from at least one checkpoint, in response to a restore command received from a parent iterator.

14. The storage medium of claim 8, wherein the instructions for evaluating whether to restore the iterator include instructions for directing the iterator to restore dynamic state information from at least one previously-stored checkpoint.

15. A computer-implemented method comprising computer-implemented operations for:

instantiating at least one iterator in response to a search request, wherein the iterator includes fixed state information that remains constant over a life of the iterator, and includes dynamic state information that is updated over the life of the iterator;

creating a storage structure associated with the iterator and storing a representation of the dynamic state information in the storage structure;

creating a stack structure that includes a plurality of entries, further storing the representation of the dynamic state information in one of the entries, and further storing at least a further representation of a further instance of the dynamic state information in a further one of the entries;

traversing the iterator through at least a portion of at least one postings list in connection with performing a search in response to the search request;

updating at least one instance of the dynamic state information, as the iterator traverses through at least the portion of the postings list while performing the search; and

evaluating whether to create a checkpoint of the iterator at one or more points during the iterator traversing through at least the portion of the postings list while performing the search, wherein the checkpoint includes at least a representation of the dynamic state information at one of the points.

16. The method of claim 15, further comprising storing the representation of only the dynamic state information, as associated with the checkpoint.

17. The method of claim 15, further comprising storing data from which the dynamic state information is calculated when restoring the checkpoint of the iterator.

18. The method of claim 15, further comprising evaluating whether the iterator is associated with at least one child iterator.

19. The method of claim 15, further comprising sending a command to at least one child iterator, associated with the iterator, to create a further checkpoint associated with the child iterator, wherein the further checkpoint includes at least a further representation of further dynamic state information maintained by the child iterator.

20. The method of claim 15, wherein evaluating whether to create a checkpoint further comprises directing the iterator to create a checkpoint, in response to a checkpoint command received from a parent iterator.