Patent ID: 8572091

Claim:
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 each of the items stored in a given table comprises a respective value for the hash key attribute and a respective value for the range key attribute, and wherein the respective values for the hash key attribute and the range key attribute are provided by the storage service clients on whose behalf the items are stored; wherein in maintaining a given table, the data storage service is configured to partition the given table, wherein partitioning the given table comprises: partitioning the items that are stored in the given table into two or more partitions dependent on a hash of their respective hash key attribute values; and for at least one of the two or more partitions, further partitioning the items that are stored in the given table and that have a same hash key attribute value into two or more additional partitions dependent on their respective range key attribute values; wherein in response to receiving a service request to query the given table, the data storage service is configured to: return the values of one or more attributes of one or more items that are stored in the given table and that match a query condition that is specified in the service request, or a count of the one or more items that are stored in the given table and that match the query condition; wherein the service request comprises the name of the given table and the query condition; and 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.