Utilization limiting for nested object queries

Patent metadata

Field	Value
Publication number	US-10387578-B1
Application number	US-201514868181-A
Country	US
Kind code	B1
Filing date	Sep 28, 2015
Priority date	Sep 28, 2015
Publication date	Aug 20, 2019
Grant date	Aug 20, 2019

Abstract

Capacity utilization may be controlled by a token-based allocation of input/output capacity. Operations on nested objects may utilize capacity based on factors other than input/output capacity. A capacity utilization model may be used to scale input/output utilization associated with an operation on a nested object so that the scaled input/output utilization correlates to the computing capacity used performing the operation on the nested object. The correlation may be determined to be valid for a range of attributes associated with the operation.

First claim

What is claimed is:

1. A system for controlling capacity utilization of a database maintaining a collection of nested objects, the system comprising:
a storage device; and
one or more computing nodes that process requests to store and retrieve the nested objects on the storage device, wherein the one or more computing nodes at least:
store an association between an account and a first value indicative of a maximum amount of input/output capacity that may be used access data on behalf of the account;
receive a request to access at least one of the nested objects stored on the storage device, the request comprising a query and information indicative of the association;
verify that the query conforms to an input/output utilization model by at least determining that a number of operators in the query does not exceed a first threshold amount, determining that a nesting level of the query does not exceed a second threshold amount, and determining that a number of operands in the query do not exceed a third threshold amount;
form a second value based at least in part on the input/output utilization model, the second value indicative of a correlation between central processing unit utilization and an amount of input/output utilization that can be compared to the first value; and
determine to perform the query based at least in part on comparing the second value to the first value.

2. The system of claim 1 , wherein the one or more computing nodes at least:
form the second value by multiplying a value indicative of a size of the at least one of the nested objects multiplied by an adjustment factor indicative of a complexity of the query.

3. The system of claim 1 , wherein the one or more computing nodes at least:
execute a second query comprising a first number of operators, a first number of operands, and a first nesting level;
determine that central processing unit utilization is below a bottleneck percentage for the first number of operators, the first number of operands, and the first nesting level; and
set the first threshold amount, the second threshold amount, and the third threshold amount based on the determination that the central processing unit utilization is below the bottleneck percentage.

4. The system of claim 1 , wherein the one or more computing nodes at least:
receive a second request to access a scalar value; and
determine that performing the second request is not estimated to cause the maximum amount of input/output capacity to be exceeded, based at least in part on a size of the scalar value.

5. The system of claim 1 , wherein the one or more computing nodes at least:
determine an amount of input/output utilization that is sustainable on the one or more computing nodes;
determine an amount of central processing unit utilization that is sustainable on the computing node; and
determine a first range of values for the first threshold amount, a second range of values for the second threshold amount, and a third range of values for the third threshold amount for which the input/output utilization model may be used to correlate the amount of central processing unit utilization that is sustainable to the amount of input/output utilization that is sustainable.

6. A method for controlling computing capacity used to access nested objects stored in a repository, the method comprising:
associating an account with an amount of computing capacity that may be used to access data on behalf of the account;
verifying that a query involving of at least one nested object among the nested objects to be performed on behalf of the account conforms to a capacity model, wherein the verification comprises determining that a number of operators in the query does not exceed a first threshold amount, determining that a nesting level of the query does not exceed a second threshold amount, and determining that a number of operands in the query does not exceed a third threshold amount;
estimating, based at least in part on the capacity model, an amount of capacity to be used performing the query; and
determining to perform the query based at least in part on the estimated amount of capacity not exceeding the amount of computing capacity that may be used to access data.

7. The method of claim 6 , further comprising:
estimating the amount of capacity to be used performing the query by multiplying a value indicative of a size of the at least one nested object multiplied by an adjustment factor indicative of a complexity of the query.

8. The method of claim 6 , further comprising:
executing a second query comprising a first number of operators, a first number of operands, and a first nesting level;
determining that central processing unit utilization is below a bottleneck percentage for the first number of operators, the first number of operands, and the first nesting level; and
setting the first threshold amount, the second threshold amount, and the third threshold amount based on the determination that the central processing unit utilization is below the bottleneck percentage.

9. The method of claim 6 , further comprising:
receiving a second request to access a scalar value stored in the repository; and
determining that performing the second request is not estimated to cause the amount of computing capacity that may be used to be exceeded, based at least in part on a size of the scalar value.

10. The method of claim 6 , further comprising:
obtaining information indicative of computing capacity utilized performing the query; and
determining that the capacity model is consistent with the computing capacity utilized performing the query.

11. The method of claim 6 , wherein the verification comprises counting operands provided to an IN operator of the query.

12. The method of claim 6 , wherein the verification comprises determining that an update expression of the query contains less than a fourth threshold amount of operators.

13. The method of claim 6 , further comprising:
determining to not perform a second query in response to determining that the second query does not conform to the capacity model.

14. The method of claim 6 , further comprising:
forming a model that correlates input/output utilization to central processing unit utilization for a range in which the number of operators in the query does not exceed the first threshold amount, the nesting level of the query does not exceed the second threshold amount, and the number of operands in the query does not exceed the third threshold amount.

15. A method comprising:
associating an account with an amount of input/output utilization of a computing node allocated to the account for accessing data;
identifying, for an attribute associated with queries of nested objects, a range of values for the attribute, wherein size of a nested object is determined to be predictive of capacity utilized by performing a query in which the attribute has a value that falls within the range;
receiving, by the computing node, a first query of a nested object, the first query associated with the attribute;
estimating capacity to be used performing the first query in response to determining that the attribute associated with the first query falls within the range of values; and
determining that the amount of input/output utilization allocated to the account will not be exceeded by performing the first query.

16. The method of claim 15 , further comprising:
determining that central processing utilization will not exceed a threshold amount when the attribute is within the range of values.

17. The method of claim 1

Assignees

• Amazon Tech Inc

Inventors

• Xiao Wei
• Yanacek David Craig

Classifications

• G06F16/835 Primary

  Query processing · CPC title

• G06F16/2425 Primary

  Iterative querying; Query formulation based on the results of a preceding query · CPC title

• G06F16/24553

  of query operations · CPC title

• G06F17/30483

  Physics · mapped topic

• G06F17/30395 Primary

  Physics · mapped topic