Data store with lock-free stateless paging capacity
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 method for operating a distributed data store, comprising:
paging, by one or more computer processors, results provided by the data store in response to a search; and
limiting, by the one or more computer processors, a number of the results returned by each node within the data store during the search,
wherein additional operations within the data store are allowed to proceed between pages during the search, and
wherein the additional operations comprise at least one of an insertion, a deletion, or a query.
2. The method of claim 1 , comprising:
limiting, by the one or more computer processors, computation required per node per page of the results returned in response to the search at the data store without storing a search state between successive pages; and
interleaving, by the one or more computer processors, the at least one of an insertion, a deletion, or a query at the data store.
3. The method of claim 1 , wherein the paging is performed without locking data within the data store.
4. The method of claim 1 , wherein the data store comprises a plurality of tuples, and wherein each tuple of the plurality of tuples has an ordinal rank, the method comprising:
returning, by the one or more computer processors, a subset of the plurality of tuples having a lowest ordinal rank.
5. The method of claim 1 , comprising:
partitioning, by the one or more computer processors, the query into one or more subqueries; and
retrieving, by the one or more computer processors, a page for at least one subquery.
6. The method of claim 5 , comprising:
forwarding, by the one or more computer processors, remaining subqueries to one or more other nodes within the data store.
7. The method of claim 6 , comprising:
receiving, by the one or more computer processors, a return page from each node to which a subquery was forwarded; and
merging, by the one or more computer processors, the return page with the page to create a merged return page.
8. A distributed data store, comprising:
one or more computer processors; and
a non-transitory computer-readable storage medium storing computer instructions, which when executed by the one or more computer processors cause the data store to:
page results provided by the data store in response to a search; and
limit a number of the results returned by each node within the data store during the search,
wherein additional operations within the data store are allowed to proceed between pages during the search.
9. The data store of claim 8 , wherein the computer instructions cause the data store to:
limit computation required per node per page of the results returned in response to the search at the data store without storing a search state between successive pages; and
interleave the at least one of an insertion, a deletion, or a query at the data store.
10. The data store of claim 8 , wherein the paging is performed without locking data within the data store.
11. The data store of claim 8 ,
wherein the data store comprises a plurality of tuples,
each tuple of the plurality of tuples has an ordinal rank, and
the computer instructions cause the data store to:
return a subset of the plurality of tuples having a lowest ordinal rank.
12. The data store of claim 8 , wherein the computer instructions cause the data store to:
partition a query into one or more subqueries; and
retrieve a page for at least one subquery.
13. The data store of claim 12 , wherein the computer instructions cause the data store to:
forward remaining subqueries to one or more other nodes within the data store.
14. The data store of claim 13 , wherein the computer instructions cause the data store to:
receive a return page from each node to which a subquery was forwarded; and
merge the return page with the page to create a merged return page.
15. A non-transitory computer-readable storage medium storing computer instructions, which when executed by one or more computer processors cause the one or more computer processors to:
page results provided by a data store in response to a search; and
limit a number of the results returned by each node within the data store during the search,
wherein additional operations within the data store are allowed to proceed between pages during the search.
16. The non-transitory computer-readable storage medium of claim 15 , wherein the computer instructions cause the one or more computer processors to:
limit computation required per node per page of the results returned in response to the search at the data store without storing a search state between successive pages; and
interleave the at least one of an insertion, a deletion, or a query at the data store.
17. The non-transitory computer-readable storage medium of claim 15 , wherein the paging is performed without locking data within the data store.
18. The non-transitory computer-readable storage medium of claim 15 ,
wherein the data store comprises a plurality of tuples,
each tuple of the plurality of tuples has an ordinal rank, and
the computer instructions cause the one or more computer processors to:
return a subset of the plurality of tuples having a lowest ordinal rank.
19. The non-transitory computer-readable storage medium of claim 15 , wherein the computer instructions cause the one or more computer processors to:
partition a query into one or more subqueries; and
retrieve a page for at least one subquery.
20. The non-transitory computer-readable storage medium of claim 19 , wherein the computer instructions cause the one or more computer processors to:
forward remaining subqueries to one or more other nodes within the data store.