公开(公告)号：US10592506B1

公开(公告)日：2020-03-17

申请号：US13766683

申请日：2013-02-13

Applicant: Amazon Technologies, Inc.

Inventor： Neil Thombre ,  Zelaine Fong ,  Stefano Stefani ,  Hakan Jakobsson ,  Anurag Windlass Gupta

IPC: G06F16/2453

Abstract: A query optimizer may receive a query block that includes a hint. The hint may include a unique object identifier to specify an object to which the hint applies. In some instances, the object may correspond to a nested query block. A query optimization plan may be determined based, at least in part, on the hint. The query execution plan may then be executed to query a data store.

公开(公告)号：US10534768B2

公开(公告)日：2020-01-14

申请号：US14981540

申请日：2015-12-28

Applicant: Amazon Technologies, Inc.

Inventor： Pradeep Jnana Madhavarapu ,  Raman Mittal ,  Benjamin Tobler ,  James McClellan Corey ,  Yan Valerie Leshinsky ,  Samuel James McKelvie ,  Anurag Windlass Gupta

IPC: G06F16/23 ,  G06F16/27

Abstract: A log-structured data store may implement optimized log storage for asynchronous log updates. In some embodiments, log records may be received indicating updates to data stored for a storage client and indicating positions in a log record sequence. The log records themselves may not be guaranteed to be received according to the log record sequence. Received log records may be stored in a hot log portion of a block-based storage device according to an order in which they are received. Log records in the hot log portion may then be identified to be moved to a cold log portion of the block-based storage device in order to complete a next portion of the log record sequence. Log records may be modified, such as compressed, or coalesced, before being stored together in a data block of the cold log portion according to the log record sequence.

公开(公告)号：US10528599B1

公开(公告)日：2020-01-07

申请号：US15382326

申请日：2016-12-16

Applicant: Amazon Technologies, Inc.

Inventor： Ippokratis Pandis ,  Mengchu Cai ,  Martin Grund ,  Anurag Windlass Gupta

IPC: G06F16/28 ,  H04L29/08 ,  G06F16/22 ,  G06F16/248 ,  G06F16/2455

Abstract: Data processing engines implement tiered data processing for distributed data in local and remote data stores. Requests to access distributed data including a data object in a remote data store are received at a data processing engine. A query plan is generated to service the access request. Different operations in the query plan are identified and assigned to one or more remote query processing engines that may access the remote data object. Requests to perform the different operations are sent to the one or more remote query processing engines. A final result is generated for the request based on the results received for the different operations from the remote query processing engine and results from operations performed with respect to locally stored data.

公开(公告)号：US10474547B2

公开(公告)日：2019-11-12

申请号：US15391729

申请日：2016-12-27

Applicant: Amazon Technologies, Inc.

Inventor： Grant Alexander MacDonald McAlister ,  Samuel James McKelvie ,  Anurag Windlass Gupta

IPC: G06F17/00 ,  G06F7/00 ,  G06F11/20 ,  G06F11/14 ,  G06F16/27 ,  H04L12/24 ,  G06Q40/04 ,  H04L29/08

Abstract: A network-based services provider may reserve and provision primary resource instance capacity for a given service (e.g., enough compute instances, storage instances, or other virtual resource instances to implement the service) in one or more availability zones, and may designate contingency resource instance capacity for the service in another availability zone (without provisioning or reserving the contingency instances for the exclusive use of the service). For example, the service provider may provision resource instance(s) for a database engine head node in one availability zone and designate resource instance capacity for another database engine head node in another availability zone without instantiating the other database engine head node. While the service operates as expected using the primary resource instance capacity, the contingency resource capacity may be leased to other entities on a spot market. Leases for contingency instance capacity may be revoked when needed for the given service (e.g., during failover).

公开(公告)号：US10372723B2

公开(公告)日：2019-08-06

申请号：US15706511

申请日：2017-09-15

Applicant: Amazon Technologies, Inc.

Inventor： Anurag Windlass Gupta

IPC: G06F17/30 ,  G06F16/25 ,  G06F16/22 ,  G06F16/245 ,  G06F16/28 ,  G06F16/2455 ,  G06F16/27

Abstract: A probabilistic data structure is generated for efficient query processing using a histogram for unsorted data in a column of a columnar database. A bucket range size is determined for multiples buckets of a histogram of a column in a columnar database table. In at least some embodiments, the histogram may be a height-balanced histogram. A probabilistic data structure is generated to indicate for which particular buckets in the histogram there is a data value stored in the data block. When an indication of a query directed to the column for select data is received, the probabilistic data structure for each of the data blocks storing data for the column may be examined to determine particular ones of the data blocks which do not need to be read in order to service the query for the select data.

公开(公告)号：US10331655B2

公开(公告)日：2019-06-25

申请号：US15613637

申请日：2017-06-05

Applicant: Amazon Technologies, Inc.

Inventor： Anurag Windlass Gupta ,  Pradeep Jnana Madhavarapu ,  Laurion Darrell Burchall ,  Neal Fachan

IPC: G06F16/00 ,  G06F16/23 ,  G06F16/27 ,  G06F11/14

Abstract: A database system may maintain a plurality of log records at a distributed storage system. Each of the plurality of log records may be associated with a respective change to a data page. Upon detection of a coalesce event for a particular data page, log records linked to the particular data page may be applied to generate the particular data page in its current state. Detecting the coalesce event may be a determination that the number of log records linked to the particular data page exceeds a threshold.

公开(公告)号：US20190188406A1

公开(公告)日：2019-06-20

申请号：US16283517

申请日：2019-02-22

Applicant: Amazon Technologies, Inc.

Inventor： Samuel James McKelvie ,  Maximiliano Maccanti ,  Anurag Windlass Gupta ,  Pradeep Jnana Madhavarapu ,  Yan Valerie Leshinsky

IPC: G06F21/62

CPC classification number: G06F21/6218 ,  G06F21/6227 ,  G06F2221/2141

Abstract: A distributed database system may implement dynamic quorum group membership changes. In various embodiments, a quorum set may maintain a replica of a data object among group members according to a protection group policy for the data object. A group member may be identified as to be replaced. In response, a new quorum set may be created from the remaining group members and a new group member. The protection group policy may be updated to include the new group members such that subsequently received updates are maintained at both the previous to quorum set and the new quorum set. Previously received updates may be replicated on the new group member. Upon completion of replicating the previously received updates, the protection group policy for the data object may be revised such that subsequently received updates are maintained at the new quorum set.

公开(公告)号：US10289723B1

公开(公告)日：2019-05-14

申请号：US14465134

申请日：2014-08-21

Applicant: Amazon Technologies, Inc.

Inventor： Mengchu Cai ,  Anurag Windlass Gupta

IPC: G06F7/00 ,  G06F17/30

Abstract: Queries that involve multiple tables in a data warehouse system may be specified through structured query language (“SQL”) statements that include union, order by, and limit clauses. When the tables are partitioned, a query of this type may be processed by forming a query plan in which intermediate results are formed by applying sort and limit operators at the partition level, combining the intermediate results from the partitions, and again applying sort and limit operations. Additional clauses, such as a unique clause, may also be pushed down to the partition level and reapplied at the level of the result set.

公开(公告)号：US10095738B1

公开(公告)日：2018-10-09

申请号：US14978842

申请日：2015-12-22

Applicant: Amazon Technologies, Inc.

Inventor： Andrew Edward Caldwell ,  Michail Petropoulos ,  Anurag Windlass Gupta

IPC: G06F17/30 ,  G06F7/00

Abstract: A data store may implement dynamically assign storage locations to logical partitions according to query predicate indexes. Query predicate indexes may be maintained for individual storage locations in a data store that indicate whether storage locations store data values that do not satisfy a query predicate. The query predicate indexes may be evaluated to assign the storage locations to one or multiple logical partitions. The logical partitions may then be utilized to provide access to data stored in the data store. In some embodiments, a logical partition may be a remote storage partition that identifies data in storage locations to copy to a remote data store.

公开(公告)号：US10061834B1

公开(公告)日：2018-08-28

申请号：US14530495

申请日：2014-10-31

Applicant: Amazon Technologies, Inc.

Inventor： Jakub Kulesza ,  Bharath Kumar Chelepalli ,  Deepak Agarwal ,  Anurag Windlass Gupta

IPC: G06F17/30

CPC classification number: G06F16/283 ,  G06F16/27

Abstract: A data store may implement incremental out-of-place updates to a dataset. A dataset may maintain data across different storage locations linked together according to an ordering schema for servicing queries. As updates to the dataset are received, the updates may be persisted but not maintained in-place. In order to update the data store and maintain the ordering schema, incremental updates to the dataset may be performed without blocking queries directed toward the dataset. The dataset may be divided into multiple data chunks that correspond to different storage locations and an updated version of the data chunk may be generated in new storage locations. The new storage locations may then replace the storage locations of the prior version of the data chunk in order to link the new storage locations to the other linked storage locations in the dataset for servicing queries.