Data store with lock-free stateless paging capability

• US 8,996,486 B2
• Filed: 12/12/2005
• Issued: 03/31/2015
• Est. Priority Date: 12/15/2004
• Status: Active Grant

• Current Assignee: Applied Invention, LLC
• Original Assignee: Applied Invention, LLC
• Inventors: Hillis, W. Daniel, Bax, Eric, Callejas, Augusto, Kao, Harry, Kolehmainen, Mathias L.
• Primary Examiner(s): Alam, Hosain
• Assistant Examiner(s): HARPER, ELIYAH STONE
• Application Number:
  US11/301,985
• Publication Number:
  US 20060129540A1
• Time in Patent Office: 3,396 Days
• Field of Search: 707/104.1, 707/100, 707/10, 707/3
• US Class Current: 707/705
• 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 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; and

returning 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; and

returning 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.

2. The method of claim 1, wherein the number of data items in any of said initial page and said subsequent page is specified for said query upon submission of said query.

3. The method of claim 1, wherein the number of data items in any of said initial page and said subsequent page is determined by a page size specified by an administrator of said data store.

4. 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.

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

6. The method of claim 5, wherein said globally unique identifier comprises any of:

a timestamp; and

a unique machine identifier identifying a server receiving said query.

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

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

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

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

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

12. The method of claim 10, wherein each of said nodes resides on a computer and said node 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.

13. The method of claim 10,

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

returning said merged return page as a return page; and

wherein said return page comprises any of said initial page and said subsequent page of results for said receiving node.

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

15. The method of claim 13, 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.

16. 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.

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

18. The method of claim 16, 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 any of said initial page and said subsequent page of results.

19. The method of claim 16, wherein said ordinal ranking is based on a globally unique identifier and wherein said globally unique identifier is stored within said distributed, ordered tuple store as a value in one of said fields.

20. The method of claim 16, wherein said ordinal ranking is based on a globally unique identifier and wherein said globally unique identifier is calculated based on the values stored in one or more of said fields.

21. The method of claim 16,

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 receiving 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 any of said initial page and said subsequent page of results for said receiving node.

22. The method of claim 21, wherein said internal pages, said return pages, and said merged return page each comprise a common number of tuples.

23. The method of claim 21, 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.

24. The method of claim 21, wherein said forwarding step is based 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.

25. A computer for limiting the number of results returned from a data store containing data items in response to a query, comprising:

a memory;

a processor configured to implement instructions stored in the memory, the memory storing executable instructions;

said processor configured for receiving a query comprising one or more query conditions wherein said data store contains one or more data items each having an ordinal ranking;

said processor configured for determining if said query further comprises a marker that indicates the greatest ordinal ranking among ordinal rankings of results in a previous page of results;

said processor configured for, responsive to determining that said query does not comprise a marker,

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; and

returning an initial page of results comprising said initial subset of data items and said particular marker for said initial page;

said processor configured for, responsive to determining that said query comprises a marker,

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 particular 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; and

returning 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.

26. The computer of claim 25, wherein said ordinal ranking is based on a globally unique identifier comprising any of:

a timestamp; and

a unique machine identifier identifying a server receiving said query.

27. The computer of claim 25, wherein said data store comprises a distributed data store comprising one or more nodes.

28. The computer of claim 27,

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 any of said initial page and said subsequent page of results for said receiving node.

29. The computer of claim 25, 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.

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

31. A computer-implemented method for limiting the number of results returned from a data store containing data items in response to a query, comprising the steps of:

receiving by a data store having a plurality of data items, a query comprising one or more query conditions;

returning, by said data store, a page of results comprising a subset of said plurality of data items from said data store, wherein each of said data items in said subset has an ordinal ranking among said plurality of data items within said data store, satisfies said query conditions, and has lowest ordinal ranking among the remaining data items not in the subset; and

providing, by said data store, with said page of results a marker that indicates the greatest ordinal ranking among said ordinal rankings of said data items in subset in said page of results;

wherein submitting said marker to said data store within a subsequent query ensures that a subsequent page of results is disjoint from said page of results.

32. The method of claim 31, additionally comprising the step of, after said receiving step:

determining, by said computer, 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 page returned in response to a previous query comprising said query conditions; and

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

33. A computer-implemented method for limiting the number of data items returned from a data store containing data items in response to at least one query, comprising the steps of:

receiving, by a data store, an initial 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, an initial page of results comprising an initial subset of said data items within said data store that satisfy said query conditions, said subset of data items having lowest ordinal ranking;

generating, using said initial page of results, a marker that indicates the greatest ordinal ranking among said ordinal rankings of said data items within said initial page of results;

returning, by said data store, said marker and said initial page of results; and

if additional results are desired from said data store;

receiving, by said data store, a subsequent query comprising said query conditions and said marker;

returning, by said data store, a subsequent page of results comprising a subsequent subset of said data items within said data store satisfying said query conditions and having lowest ordinal ranking among data items with ordinal ranking greater than said greatest ordinal ranking indicated by said marker and an updated marker that indicates a new greatest ordinal ranking among ordinal rankings of said data items in said subsequent page of results;

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

wherein submitting said updated marker to said data store within a subsequent query ensures that a subsequent page of results is disjoint from a previous page of results.

34. A computer-implemented 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, a data store returning an initial page of results that includes an initial subset of data items from said data store, wherein each of said data items has an ordinal ranking within said data store, that satisfy said query conditions, said initial subset of data items having lowest ordinal ranking within said data store;

said data store generating an initial marker that indicates the greatest ordinal ranking among said ordinal rankings of said initial subset of data items in said initial page of results;

when a subsequent query is received that requests additional results satisfying said initial query conditions and that includes said initial marker, said data store returning;

a subsequent page of results that includes a subsequent subset of data items having lowest ordinal ranking among said data items contained in said data store with ordinal ranking greater than said greatest ordinal ranking; and

a subsequent marker indicating the greatest ordinal ranking among said ordinal rankings of said data items in said subsequent page of results;

wherein submitting said subsequent marker to said data store within a subsequent query ensures that a subsequent page of results is disjoint from a previous page of results.