US 8,572,091 B1Granted

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

AssigneeAmazon Technologies, Inc.

InventorsSwaminathan Sivasubramanian, Stefano Stefani, Chiranjeeb Buragohain, Rande A. Blackman, Timothy Andrew Rath, Grant A. M. McAlister, Jakub Kulesza, Wei Xiao, Raymond S. Bradford

Life of this patent

Estimating the term…

patentgrep

Loading patent…

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.

Claims35

Dependent claims

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.

10 more elements

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:

maintaining one or more tables in a non-relational data store on behalf of one or more storage service clients;
wherein each of the one or more tables is configured to store a plurality of items;
wherein each of the one or more 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 one of the one or more tables 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 a storage service client on whose behalf the item is stored;
and
wherein maintaining the plurality of tables comprises partitioning 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.

6 more elements

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 non-relational data store;
wherein the data store maintains a plurality of tables, each of which is partitioned and indexed according to a primary key that comprises a hash key component and a range key component, wherein each item stored in a given one of the plurality of tables comprises a respective value for the hash key component and a respective value for the range key component, and wherein the respective values for the hash key component and the range key component are provided by a client on whose behalf the item is stored;
wherein in response to receiving a request to query the given one of the plurality of tables, the data store is configured to:
determine whether any items that are stored in the given table match a query condition that is specified in the request;
return information indicating whether any items that are stored in the given table match the specified query condition;
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.

3 more elements

Dependencies are inferred from the claim text.