System and method for partitioning and indexing table data using a composite primary key

• US 8,819,027 B1
• Filed: 10/28/2013
• Issued: 08/26/2014
• Est. Priority Date: 06/27/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sivasubramanian, Swaminathan, Stefani, Stefano, Buragohain, Chiranjeeb, Blackman, Rande A., Rath, Timothy Andrew, McAlister, Grant A. M., Kulesza, Jakub, Xiao, Wei, Bradford, Raymond S.
• Primary Examiner(s): NGUYEN, PHONG H
• Application Number:
  US14/064,943
• Time in Patent Office: 302 Days
• Field of Search: 707/737, 707/747, 707/968, 707/972, 707/741
• US Class Current: 707/747
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/325 Hash tables
• CPC Class Codes: G06F 16/9014 hash tables
• CPC Class Codes: Y10S 707/968 Partitioning
• CPC Class Codes: Y10S 707/972 Partitioning

Abstract

A system that implements a scaleable data storage service may maintain tables in a non-relational data store on behalf of service clients. Each table may include multiple items. Each item may include one or more attributes, each containing a name-value pair. The system may provide an API through which clients can query tables maintained by the service. Items may be partitioned and indexed in a table according to a simple or composite primary key contained in all items in the table. A composite primary key may include a hash key attribute, and a range key attribute. The range key attribute may be usable to order items having the same hash key attribute value, and to partition them dependent on a range of range key attribute values. A query request may specify a logical or mathematical expression dependent on range key attribute values and may be directed to multiple partitions.

Claims

1. A system, comprising:

a plurality of computing nodes, each comprising at least one processor and memory, wherein the plurality of computing nodes is configured to implement a data storage service;

wherein the data storage service provides a web services interface through which service requests are received;

wherein the data storage service maintains a plurality of tables in a non-relational data store on behalf of one or more storage service clients, wherein each table is configured to store a plurality of items;

wherein each of the plurality of tables is partitioned and indexed according to a respective primary key that comprises a hash key component and a range key component;

wherein in maintaining a given table, the data storage service is configured to partition the given table;

wherein the data storage service determines or a service request specifies a maximum number of items whose attribute values can be returned in response to a single request;

wherein in response to receiving a service request to query the given table, the data storage service is configured to;

determine whether any items that are stored in the given table match a query condition that is specified in the request; and

return information indicating whether any items that are stored in the given table match the specified query condition, wherein said return information comprises return an identifier of a last item in the given table whose attribute values are returned in response to the request;

wherein the identifier of the

last item is usable to specify a point in the given table for a subsequent request to begin evaluating additional items in the given table in order to apply the query condition to any remaining items in the given table; and

wherein the query condition specifies a value for a hash key component of the items targeted by the query and a range key component condition.

2. The system of claim 1,

wherein the hash key component comprises an item attribute whose value identifies a group of items in the given table;

and

wherein a given range key attribute value uniquely identifies a particular item from among all items in the given table having a same hash key attribute value; and

wherein the items having the same hash key attribute value are ordered in the given table according to their respective range key attribute values.

3. The system of claim 2, wherein the query condition specifies a value for the hash key component and a mathematical or logical expression to be evaluated dependent on values of the range key component of the items in the given table, and wherein the mathematical or logical expression comprises a comparison operator and at least one value for the range key attribute.

4. The system of claim 3, wherein the comparison operator is applied to determine whether the range key attribute value of an item is equal to a value specified in the range key component of the query condition, is less than a value specified in the range key component of the query condition, is less than or equal to a value specified in the range key component of the query condition, is greater than a value specified in the range key component of the query condition, is greater than or equal to a value specified in the range key component of the query condition, is between two values specified in the range key component of the query condition or begins with a value specified in the range key component of the query condition.

5. The system of claim 1, wherein the received service request specifies the maximum number of items whose attribute values can be returned in response to the single request.

6. The system of claim 1, wherein the last item in the given table whose attribute values were returned in response to the request corresponds with the maximum number of items whose attribute values can be returned in response to a single request.

7. A method, comprising:

performing by one or more computer devices;

receiving a request to query a given one of a plurality of tables in a non-relational data store, each of which is partitioned and indexed according to a primary key that comprises a hash key component and a range key component;

determining a maximum number of items whose attribute values can be returned in response to a single request;

in response to said receiving, determining whether any items that are stored in the given table match a query condition that is specified in the request; and

returning information indicating whether any items that are stored in the given table match the specified query condition, wherein said returning comprises returning an identifier of a last item in the given table whose attribute values were returned in response to the request;

wherein the identifier of the last item is usable to specify a point in the given table for a subsequent request to begin evaluating additional items in the given table in order to apply the query condition to any remaining items in the given table; and

wherein the query condition specifies a value for a hash key component of the items targeted by the query and a range key component condition.

8. The method of claim 7, wherein said returning comprises returning the values of one or more attributes of items that are stored in the given table and that match the specified query condition.

9. The method of claim 8, wherein the request specifies the one or more attributes whose values are to be returned in response to the request.

10. The method of claim 8,

wherein the request specifies the maximum number of items whose attribute values can be returned in response to the single request.

11. The method of claim 7,

wherein the request specifies that a count of items that are stored in the given table and that match the query condition is to be returned;

and

wherein said returning comprises returning a count of items that are stored in the given table and that match the query condition.

12. The method of claim 7, wherein the hash key component comprises an item attribute whose value identifies a group of items in the given table.

13. The method of claim 12,

wherein the range key component comprises an attribute other than that of the hash key component;

and

wherein a given range key attribute value uniquely identifies a particular item from among all items in the given table having a same hash key attribute value, wherein the items having the same hash key attribute value are ordered in the given table according to their respective range key attribute values.

14. The method of claim 13, wherein the range key component condition comprises a mathematical or logical expression to be evaluated dependent on the respective range key attribute values of the items, and wherein the mathematical or logical expression comprises a comparison operator and at least one value for the range key component attribute.

15. The method of claim 14, wherein the comparison operator is applied to determine whether the range key attribute value of an item is equal to a value specified in the range key component of the query condition, is less than a value specified in the range key component of the query condition, is less than or equal to a value specified in the range key component of the query condition, is greater than a value specified in the range key component of the query condition, is greater than or equal to a value specified in the range key component of the query condition, is between two values specified in the range key component of the query condition or begins with a value specified in the range key component of the query condition.

16. The method of claim 7 wherein the last item in the given table whose attribute values were returned in response to the request corresponds with said maximum determined number of items whose attribute values can be returned in response to a single request.

17. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

receiving a request to query a given one of a plurality of tables in a non-relational data store

each of

which is partitioned and indexed according to a primary key that comprises a hash key component and a range key component;

determining a maximum number of items

whose attribute values can be returned in response to a single request;

in response to said receiving, determining whether any items that are stored in the given table match a query condition that is specified in the request;

returning information indicating whether any items that are stored in the given table match the specified query condition, wherein said returning comprises returning an identifier of a last item in the given table whose attribute values were returned in response to the request;

wherein the identifier of the last item is usable to specify a point in the given table for a subsequent request to begin evaluating additional items in the given table in order to apply the query condition to any remaining items in the given table; and

wherein the query condition specifies a value for a hash key component of the items targeted by the query and a range key component condition.

18. The storage medium of claim 17, wherein the last item in the given table whose attribute values were returned in response to the request corresponds with said maximum determined number of items whose attribute values can be returned in response to a single request.

19. The storage medium of claim 17, wherein the request specifies the maximum number of items whose attribute values can be returned in response to a single request.

20. The storage medium of claim 17, wherein said returning comprises returning the values of one or more attributes of items that are stored in the given table and that match the specified query condition.