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.