Data store with lock-free stateless paging capability

摘要

Disclosed are a method and apparatus for limiting the number of results returned by a data store in response to a query. Upon receiving an initial query, the data store returns a page of results that includes a subset of the data items within the data store satisfying the conditions of the query. The data store also provides a marker indicating the extent of the set of data items. If a subsequent query that requests additional results which satisfy the same query conditions and that includes the marker is received, the data store returns a page of results that includes a subset of data items that are disjoint from the initial subset, and provides an updated marker which indicates the extent of the union of the initial and subsequent subsets. If still further results are desired from the data store, an additional query containing the updated marker may be submitted.

主权项

1. A computer-implemented method for limiting a number of results returned from a data store in response to a query, comprising the steps of:
receiving, by a data store, a query comprising one or more query conditions, wherein said data store contains one or more data items, each having an ordinal ranking; determining, by said data store, if said query further comprises a marker that indicates the greatest ordinal ranking among ordinal rankings of results in a previous page of results; responsive to determining that said query does not comprise a marker, said data store
determining an initial subset of data items of said one or more data items within said data store that satisfy said query conditions and that have lowest ordinal ranking among said one or more data items within said data store:generating a particular marker indicating a greatest ordinal ranking of ordinal rankings of said data items within said initial subset; andreturning an initial page of results comprising said initial subset of data items and said particular marker for said initial page; and responsive to determining that said query comprises a marker, said data store
determining a subsequent subset of data items within said data store that satisfy said query conditions and that have lowest ordinal ranking among data items within said data store that have ordinal ranking greater than said greatest ordinal ranking indicated by said marker, wherein said marker is said particular marker;updating said particular marker to indicate a greatest ordinal ranking among said ordinal rankings of said data items within said subsequent subset of data items; andreturning a subsequent page of results comprising said subsequent subset of data items and said updated particular marker for said subsequent page;wherein submitting said updated particular marker to said data store within a subsequent query ensures that a subsequent page of results is disjoint from a previous page of results.