Data store with lock-free stateless paging capability

• US 20060129540A1
• Filed: 12/12/2005
• Published: 06/15/2006
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Minds LLC
• Inventors: Hillis, W. Daniel, Kao, Harry, Callejas, Augusto, Kolehmainen, Mathias L., Bax, Eric
• Granted Patent: US 8,996,486 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/334 Query execution G06F16/335 takes precedence
• CPC Class Codes: G06F 16/9038 Presentation of query results
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

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.

Claims

1. A method for limiting the number of results returned by a data store containing data items in response to a query, comprising the steps of:

receiving a query comprising one or more query conditions;

determining if said query further comprises a marker;

returning a page of results comprising a subset of said data items within said data store that satisfy said query conditions; and

providinig with said page of results an updated marker;

wherein if said query further comprises said marker, said marker indicates an extent of a previous subset returned in response to a, previous query comprising said query conditions; and

wherein said updated marker indicates an extent of a union of said previous subset and said subset.

2. The method of claim 1, wherein said subset is disjoint from said previous subset.

3. The method of claim 1, wherein the number of data items in said subset is specified for said query upon submission of said query.

4. The method of claim 1, wherein the number of data items in said subset is determined by a page size specified by an administrator of said data store.

5. The method of claim 1, wherein said data store stores data in any of:

permanent storage;

temporary storage,

disk-based storage; and

RAM-based storage.

6. The method of claim 1, wherein each data item within said data store is characterized by an ordinal ranking of said data item within said data store.

7. The method of claim 6, wherein said marker comprises a greatest ordinal ranking among the ordinal rankings of the data items within said previous subset, and wherein said returning step comprises the step of:

retrieving from within said data store the data items having lowest ordinal ranking among the data items having ordinal ranking greater than said greatest ordinal ranking to create said page of results.

8. The method of claim 6, wherein said ordinal ranking is based on a globally unique identifier.

9. The method of claim 8, wherein said globally unique identifier comprises any of:

a timestamp; and

a unique machine identifier identifying a computer receiving said query.

10. The method of claim 8, wherein said globally unique identifier is stored within said data store.

11. The method of claim 6., wherein a methodology for computing said ordinal ranking is specified with said query.

12. The method of claim 1, wherein said data store comprises a distributed data store.

13. The method of claim 12, wherein said distributed data store comprises one or more nodes.

14. The method of claim 13, wherein said nodes are connected in a directed acyclic graph.

15. The method of claim 13, wherein each of said nodes comprises any of:

a server capable of receiving a query from a client;

a repository capable of storing data items on a permanent basis; and

a relay that cannot store data items on a permanent basis.

16. The method of claim 13,

wherein a receiving node among said nodes receives said query;

wherein each of said nodes, upon receiving a query, performs the steps of;

partitioning said query into one or more subqueries, each subquery comprising one or more subquery conditions;

retrieving from a local store of data items within said node, for each of a portion of said subqueries, an internal page comprising a set of data items that satisfy said subquery conditions;

forwarding as a query to one or more of said nodes, each of a remaining portion of said subqueries;

receiving a return page from each node to which a subquery was forwarded;

merging said return pages and said internal pages to create a merged return page; and

retrieving said merged return page as a return page; and

wherein said return page comprises said page of results for said receiving node.

17. The method of claim 16, wherein said internal pages, said return pages, and said merged return page each comprises a common number of data items.

18. The method of claim 16, wherein each data item within said data store has an ordinal ranking within said data store, and

wherein said merging step comprises the step of selecting data items having greatest ordinal ranking among a union of said return pages and said internal pages.

19. The method of claim 1, wherein said data store comprises a distributed, ordered tuple store comprising one or more nodes;

and wherein said data items within said data store comprise tuples having values stored in one or more fields.

20. The method of claim 19, wherein said query conditions comprise a range of values specified for at least one of said fields.

21. The method of claim 19, wherein said query conditions comprise a wildcard specified for at least one of said fields for values in said at least one of said fields that are not considered in returning said page of results.

22. The method of claim 19, wherein each of said tuples has an ordinal ranking within said distributed, ordered tuple store.

23. The method of claim 22, wherein said ordinal ranking is based on a globally unique identifier.

24. The method of claim 23, wherein said globally unique identifier is stored within said distributed, ordered tuple store as a value in one of said fields.

25. The method of claim 23, wherein said globally unique identifier is calculated based on the values stored in one or more of said fields.

26. The method of claim 19,

wherein a receiving node among said nodes receives said query, and

wherein upon receiving a query, said receiving node performs the steps of:

partitioning said query into one or more subqueries, each subquery comprising one or more subquery conditions;

retrieving from a local store of tuples within said node, for each of a portion of said subqueries, an internal page comprising a set of tuples that satisfy said subquery conditions;

forwarding as a query to one or more of said nodes each of a remaining portion of said subqueries;

receiving a return page from each node to which a subquery was forwarded;

merging said return pages and said internal pages to create a merged return page; and

returning said merged return page as a return page;

wherein said return page comprises said page of results for said receiving node.

27. The method of claim 26, wherein said internal l)ages, said return pages, and said merged return page each comprise a common number of tuples.

28. The method of claim 26, wherein said portion and said remaining portion are determined based upon a storage range of said node, wherein said storage range indicates which of said tuples are stored within said local store of tuples.

29. The method of claim 26, wherein said forwarding step is used upon a (coverage of each of said nodes to which said node is connected, wherein said coverage indicates which of said tuples are accessible to each of said nodes to which said node is connected.

30. A data store limiting the number of results returned in response to a query, comprising:

data items;

means for receiving a query comprising one or more query conditions;

means for determining if said query further comprises a marker;

means for returning a page of results comprising a subset of said data items within said data store that satisfy said query conditions; and

means for providing with said page of results an updated marker;

wherein if said query further comprises said marker, said marker indicates an extent of a previous subset returned in response to a previous query comprising said query conditions; and

wherein said updated marker indicates an extent of a union of said previous subset and said subset.

31. The data store of claim 30, wherein said subset is disjoint from said previous subset.

32. The data store of claim 30, wherein each data item within said data store is characterized by an ordinal ranking of said data item within said data store.

33. The data store of claim 32, wherein said marker comprises a greatest ordinal ranking among the ordinal rankings of the data items within said previous subset, and wherein said means for returning comprises:

means for retrieving from within said data store the data items having lowest ordinal ranking among the data items having ordinal ranking greater than said greatest ordinal ranking to create said page of results.

34. The data store of claim 32, wherein said ordinal ranking is based on a globally unique identififiercomprising any of:

a timestamp; and

a unique machine identifier identifying a computer receiving said query.

35. The data store of claim 30, wherein said data store comprises a distributed data store comprising one or more nodes.

36. The data store of claim 35,

wherein a receiving node among said nodes receives said query;

wherein each of said nodes comprises;

means for partitioning said query into one or more subqueries, each subquery comprising one or more subquery conditions;

means for retrieving from a local store of data items within said node, for each of a portion of said subqueries, an internal page comprising a set of data items that satisfy said subquery conditions;

means for forwarding as a query to one or more of said nodes, each of a remaining portion of said subqueries;

means for receiving a return page from each node to which a subquery was forwarded;

means for merging said return pages and said internal pages to create a merged return page; and

means for returning said merged return page as a return page; and

wherein said return page comprises said page of results for said receiving node.

37. The data store of claim 30, wherein said data store comprises a distributed, ordered tuple store comprising one or more nodes;

and wherein said data items within said data store comprise tuples having values stored in one or more fields.

38. The data store of claim 37, wherein each of said tuples has an ordinal ranking within said distributed, ordered tuple store based on a globally unique identifier.

39. A method for limiting the number of results returned by a data store containing data items in response to a query, comprising the steps of:

receiving a query comprising one or more query conditions,

returning a page of results comprising a subset of said data items within said data store that satisfy said query conditions; and

providing with said page of results a marker;

wherein said marker indicates an extent of said subset.

40. The method of claim 39, additionally comprising the step of, after said receiving step:

determining if said query further comprises a previous marker;

wherein if said query further comprises said previous marker, said previous marker indicates an extent of a previous subset returned in response to a previous query comprising said query conditions; and

wherein said marker indicates an extent of a union of said previous subset and said subset.

41. A method for limiting the number of data items returned by a data store containing data items in response to at least one query, comprising the steps of:

receiving an initial query comprising one or more query conditions;

returning an initial page of results comprising and initial subset of said data items within said data store that satisfy said query conditions; and

,

providing with said initial page of results a marker that indicates the extent of said initial subset; and

,

if additional results are desired from said data store;

receiving a subsequent query comprising said query conditions and said marker;

returning a subsequent page of results comprising a subsequent subset of said data items within said data store that satisfy said query conditions, said subsequent subset being disjoint from said initial subset and

providing with said subsequent page of results an updated marker that indicates an extent of a union of said initial subset and said subsequent subset;

wherein one or more additional queries may be submitted with said updated marker if additional results are desired from said data store.

42. A method for limiting the number of results returned by a data store containing data items in response to a query having query conditions, comprising the steps of:

upon receiving an initial query, said data store returning a page of results that includes an initial subset of said data items within said data store that satisfy said query conditions;

said data store providing a marker that indicates the extent of said initial subset of data items;

when a subsequent query is received that requests additional results that satisfy said initial query conditions and that includes said marker, said data store returning a page of results that includes a subsequent subset of data items that is disjoint from said initial subset; and

said data store providing an updated marker indicating an extent of a union of said initial and subsequent subsets.

43. A distributed data store, comprising:

means for paging results provided by said data store in response to a search; and

means for limiting a number of results returned by each node within said data store during said search;

wherein additional operations with said data store are allowed to proceed between pages during said search.

44. The distributed data store of claim 43, wherein said additional operations comprise any of insertion, deletion, and query operations.

45. A distributed data store, comprising:

means for limiting computation required per node per page of results returned in response to a search operation at said data store without storing a search operation state between successive pages and

means for interleaving of any of insertion, deletion and search operations at said data store.