Checkpointing Iterators During Search
First Claim
1. At least one 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;
traversing the iterator through at least a portion of at least one postings list in connection with performing the search request;
updating at least one instance of the dynamic state information, in response to traversing the iterator through at least the portion of the postings list; and
evaluating whether to create a checkpoint of the iterator, wherein the checkpoint includes at least a representation of the dynamic state information.
4 Assignments
0 Petitions
Accused Products
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.
-
Citations
20 Claims
-
1. At least one 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; traversing the iterator through at least a portion of at least one postings list in connection with performing the search request; updating at least one instance of the dynamic state information, in response to traversing the iterator through at least the portion of the postings list; and evaluating whether to create a checkpoint of the iterator, wherein the checkpoint includes at least a representation of the dynamic state information. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. At least one 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 for including a representation of at least one checkpoint, wherein the checkpoint represents a least one instance of the dynamic state information; updating at least one instance of the dynamic state information in response to traversing the iterator through at least a portion of the postings list; and evaluating whether to restore if the iterator to a previous state represented by the dynamic state information stored with the checkpoint. - View Dependent Claims (11, 12, 13, 14, 15, 16)
-
-
17. At least one 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:
-
creating a plurality of iterators, wherein one of the iterators is a parent iterator operating at least a further one of the iterators as a child iterator, wherein the parent iterator includes; 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, wherein the first checkpoint mechanism is 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; wherein the child iterator includes; 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, wherein the second checkpoint mechanism is 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. - View Dependent Claims (18, 19, 20)
-
Specification