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

摘要

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.

主权项

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; andreturn 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 thelast 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; andwherein the query condition specifies a value for a hash key component of the items targeted by the query and a range key component condition.