Checkpointing iterators during search

• US 8,316,036 B2
• Filed: 08/29/2008
• Issued: 11/20/2012
• 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:
  US12/201,051
• Publication Number:
  US 20090070308A1
• Time in Patent Office: 1,544 Days
• Field of Search: 707/708, 707/715, 707/723, 707/758
• US Class Current: 707/758
• 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 that is not a signal having computer-executable instructions stored thereon which, when executed by a computer system, cause the computer system to perform a method comprising:

creating a plurality of iterators, one of the plurality of iterators being a parent iterator operating at least a further one of the plurality of iterators as a child iterator,

the parent iterator comprising

first fixed state information that remains constant over a life of the parent iterator,

first dynamic state information that is updated over the life of the parent iterator, and

a first checkpoint mechanism that includes a first stack structure associated with a plurality of entries, the first checkpoint mechanism being responsive to an internal checkpoint command to copy at least one instance of only the first dynamic state information, and not the first fixed state information, into one of the entries of the first stack structure, and to update a first counter mechanism to indicate that a first checkpoint including only the first dynamic state information has been copied into the first stack structure, and

the child iterator comprising

second fixed state information that remains constant over a life of the child iterator,

second dynamic state information that is updated over the life of the child iterator, and

a second checkpoint mechanism that includes a second stack structure associated with a plurality of entries, the second checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the second dynamic state information, and not the second fixed state information, into one of the entries of the second stack structure, and to update a second counter mechanism to indicate that a second checkpoint including the second dynamic state information has been copied into the second stack structure;

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

updating at least one instance of the second dynamic state information in response to traversing the child iterator through at least a portion of the postings list;

storing the first checkpoint in the first stack structure, wherein the first checkpoint includes the first dynamic state information;

storing the second checkpoint in the second stack structure, wherein the second checkpoint includes the second dynamic state information;

restoring at least the child iterator to a previous state by copying the second dynamic state information from the second checkpoint; and

restoring at least the parent iterator to the previous state by copying the first dynamic state information from the first checkpoint.

2. The storage medium of claim 1, further comprising instructions for creating at least a further child iterator, the further child iterator comprising:

third fixed state information that remains constant over a life of the further child iterator,

third dynamic state information that is updated over the life of the further child iterator, and

a third checkpoint mechanism that includes a third stack structure having a plurality of entries, the third checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the third dynamic state information, and not the third fixed state information, into one of the entries of the third stack structure, and to update a third counter mechanism to indicate that a third checkpoint including the third dynamic state information has been copied into the third stack structure.

3. The storage medium of claim 2, further comprising instructions for:

traversing at least the further child iterator through at least a portion of at least a further postings list in response to the search request;

updating at least one instance of the third dynamic state information in response to traversing the further child iterator through at least a portion of the further postings list;

storing the third checkpoint in the third stack structure, the third checkpoint comprising the third dynamic state information; and

restoring at least the further child iterator to the previous state by copying the third dynamic state information from the third checkpoint.

4. The storage medium of claim 3, wherein the parent iterator is for:

receiving first document information from the child iterator, the first document information being extracted from the postings list,

receiving further document information from the further child iterator, the further document information being extracted from the further postings list, and

performing at least one combinatorial operation on the first document information and the further document information to provide results responsive to the search request.

5. A computer-implemented method for checkpointing iterators during a search, the computer-implemented method comprising computer-implemented operations for:

creating a plurality of iterators, one of the plurality of iterators being a parent iterator operating at least a further one of the plurality of iterators as a child iterator,

the parent iterator comprising

first fixed state information that remains constant over a life of the parent iterator,

first dynamic state information that is updated over the life of the parent iterator, and

a first checkpoint mechanism that includes a first stack structure associated with a plurality of entries, the first checkpoint mechanism being responsive to an internal checkpoint command to copy at least one instance of only the first dynamic state information, and not the first fixed state information, into one of the entries of the first stack structure, and to update a first counter mechanism to indicate that a first checkpoint including only the first dynamic state information has been copied into the first stack structure, and

the child iterator comprising

second fixed state information that remains constant over a life of the child iterator,

second dynamic state information that is updated over the life of the child iterator, and

a second checkpoint mechanism that includes a second stack structure associated with a plurality of entries, the second checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the second dynamic state information, and not the second fixed state information, into one of the entries of the second stack structure, and to update a second counter mechanism to indicate that a second checkpoint including the second dynamic state information has been copied into the second stack structure;

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

updating at least one instance of the second dynamic state information in response to traversing the child iterator through at least a portion of the postings list;

storing the first checkpoint in the first stack structure, wherein the first checkpoint includes the first dynamic state information;

storing the second checkpoint in the second stack structure, wherein the second checkpoint includes the second dynamic state information;

restoring at least the child iterator to a previous state by copying the second dynamic state information from the second checkpoint; and

restoring at least the parent iterator to the previous state by copying the first dynamic state information from the first checkpoint.

6. The computer-implemented method of claim 5, further comprising creating at least a further child iterator, the further child iterator comprising:

third fixed state information that remains constant over a life of the further child iterator,

third dynamic state information that is updated over the life of the further child iterator, and

a third checkpoint mechanism that includes a third stack structure having a plurality of entries, the third checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the third dynamic state information, and not the third fixed state information, into one of the entries of the third stack structure, and to update a third counter mechanism to indicate that a third checkpoint including the third dynamic state information has been copied into the third stack structure.

7. The computer-implemented method of claim 6, further comprising:

traversing at least the further child iterator through at least a portion of at least a further postings list in response to the search request;

updating at least one instance of the third dynamic state information in response to traversing the further child iterator through at least a portion of the further postings list;

storing the third checkpoint in the third stack structure, the third checkpoint comprising the third dynamic state information; and

restoring at least the further child iterator to the previous state by copying the third dynamic state information from the third checkpoint.

8. The computer-implemented method of claim 7, further comprising:

receiving, utilizing the parent iterator, first document information from the child iterator, the first document information being extracted from the postings list,

receiving, utilizing the parent iterator, further document information from the further child iterator, the further document information being extracted from the further postings list, and

performing, utilizing the parent iterator, at least one combinatorial operation on the first document information and the further document information to provide results responsive to the search request.

9. A computer system for checkpointing iterators during a search, the computer system comprising:

a processor; and

a computer-readable storage medium having computer-executable instructions stored thereon which, when executed by the processor, cause the processor to perform a method comprising

creating a plurality of iterators, one of the plurality of iterators being a parent iterator operating at least a further one of the plurality of iterators as a child iterator,

the parent iterator comprising

first fixed state information that remains constant over a life of the parent iterator,

first dynamic state information that is updated over the life of the parent iterator, and

a first checkpoint mechanism that includes a first stack structure associated with a plurality of entries, the first checkpoint mechanism being responsive to an internal checkpoint command to copy at least one instance of only the first dynamic state information, and not the first fixed state information, into one of the entries of the first stack structure, and to update a first counter mechanism to indicate that a first checkpoint including only the first dynamic state information has been copied into the first stack structure, and

the child iterator comprising

second fixed state information that remains constant over a life of the child iterator,

second dynamic state information that is updated over the life of the child iterator, and

a second checkpoint mechanism that includes a second stack structure associated with a plurality of entries, the second checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the second dynamic state information, and not the second fixed state information, into one of the entries of the second stack structure, and to update a second counter mechanism to indicate that a second checkpoint including the second dynamic state information has been copied into the second stack structure;

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

updating at least one instance of the second dynamic state information in response to traversing the child iterator through at least a portion of the postings list;

storing the first checkpoint in the first stack structure, wherein the first checkpoint includes the first dynamic state information;

storing the second checkpoint in the second stack structure, wherein the second checkpoint includes the second dynamic state information;

restoring at least the child iterator to a previous state by copying the second dynamic state information from the second checkpoint; and

restoring at least the parent iterator to the previous state by copying the first dynamic state information from the first checkpoint.

10. The computer system of claim 9, wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed by the processor, cause the processor to perform the method further comprising creating at least a further child iterator, the further child iterator comprising:

third fixed state information that remains constant over a life of the further child iterator,

third dynamic state information that is updated over the life of the further child iterator, and

a third checkpoint mechanism that includes a third stack structure having a plurality of entries, the third checkpoint mechanism being responsive to an external checkpoint command received from the parent iterator to copy at least one instance of only the third dynamic state information, and not the third fixed state information, into one of the entries of the third stack structure, and to update a third counter mechanism to indicate that a third checkpoint including the third dynamic state information has been copied into the third stack structure.

11. The computer system of claim 10, wherein the computer-readable storage medium has further computer-executable instructions stored thereon which, when executed by the processor, cause the processor to perform the method further comprising:

traversing at least the further child iterator through at least a portion of at least a further postings list in response to the search request;

updating at least one instance of the third dynamic state information in response to traversing the further child iterator through at least a portion of the further postings list;

storing the third checkpoint in the third stack structure, the third checkpoint comprising the third dynamic state information; and

restoring at least the further child iterator to the previous state by copying the third dynamic state information from the third checkpoint.

12. The computer system of claim 11, wherein the parent iterator is for:

receiving, utilizing the parent iterator, first document information from the child iterator, the first document information being extracted from the postings list,

receiving further document information from the further child iterator, the further document information being extracted from the further postings list, and

performing at least one combinatorial operation on the first document information and the further document information to provide results responsive to the search request.