Back to results
US 11,030,177 B1Granted
Selectively scanning portions of a multidimensional index for processing queries
AssigneeAmazon Technologies, Inc.
InventorsZachary Paul Slayton, Matthew S. Canterbury
Life of this patent
Estimating the term…
Abstract
Portions of a multidimensional index for a database table may be selectively scanned for processing queries. A query may be received for a database table with a multidimensional index. A range of the multidimensional index may be identified for processing the query. Items mapped to different portions of the query may be scanned to apply the query. Some portions adjacent to a scanned portion may be skipped upon a determination that the adjacent portion does not include items that can satisfy the query. A result based on the scan operations can be provided in response to the query.
Claims19
A system, comprising:
- a memory to store program instructions which, if performed by at least one processor, cause the at least one processor to perform a method to at least:
- receive, at a database client that implements a multidimensional query engine, a first query from an application directed to a multidimensional index for a database table, wherein the first query includes one or more predicates for one or more dimensions of a plurality of dimensions included in the multidimensional index, and wherein the multidimensional index is generated from the plurality of dimensions according to a space filling curve;
- in response to receiving the first query at the database client:
- identify, by the database client, one or more dimensional ranges of the one or more dimensions that satisfy the predicates;
- identify, by the database client, a range of the multidimensional index to scan for processing the first query based, at least in part, on the identified dimensional ranges, wherein the range of the multidimensional index comprises a plurality of different portions, each including one or more multidimensional index values that satisfy the predicates, and an another portion, adjacent to at least some of the different portions, not including multidimensional index values that satisfy the predicates, and wherein boundaries of the different portions are determined at least in part by the dimensional ranges that satisfy the predicates;
- send a request from the database client to a processing node of a database service, the request causing the processing node to access storage that stores the database table to perform a scan of respective items mapped to the different portions of the range of the multidimensional index to apply the first query, wherein the request from the database client comprises an initial multidimensional index value and a filter for the items incorporating the dimensional ranges;
- upon receipt of a result of the performance of the scan of the respective items of at least one of the different portions of the range:
- determine, by the database client based at least in part on the received result, that a next multidimensional index value to scan lies within the other portion of the range adjacent to the one portion of the range, wherein the next multidimensional index value is not within the dimensional ranges, and wherein the received result excludes items determined, according to the filter, not to satisfy the first query;
- and
- in response to the determination that the next multidimensional index value is not within the dimensional ranges, skip the other portion of the range;
- and
- provide a result of the first query according to the performance of the scans of the respective items of the different portions of the range.
9 more elements
A method, comprising:
- receiving, at a database client that implements a multidimensional query engine, a first query from an application directed to a multidimensional index for a database table, wherein the first query includes one or more predicates for one or more dimensions included in the multidimensional index;
- performing, by the database client, in response to receiving the first query at the database client:
- identifying one or more dimensional ranges of the one or more dimensions that satisfy the predicates;
- identifying a range of the multidimensional index to scan for processing the first query based, at least in part, on the identified dimensional ranges, wherein the range of the multidimensional index comprises a plurality of different portions, each including one or more multidimensional index values that satisfy the predicates, and an another portion, adjacent to at least some of the different portions, not including multidimensional index values that satisfy the predicates, and wherein boundaries of the different portions are determined at least in part by the dimensional ranges that satisfy the predicates;
- sending a request from the database client to a processing node of a database service, the request causing the processing node to access storage that stores the database table to perform a scan of respective items mapped to the different portions of the range of the multidimensional index to apply the first query, wherein the request from the database client comprises an initial multidimensional index value and a filter for the items incorporating the dimensional ranges;
- upon receiving a result of the scanning of the respective items of at least one of the different portions of the range, skipping the other portion of the range that is adjacent to the scanned at least one portion of the range to generate a next multidimensional index to scan, wherein the received result excludes items determined, according to the filter, not to satisfy the first query;
- and
- providing a result of the first query according to the scanning of the respective items of the different portions of the range.
5 more elements
A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:
- receiving, at a database client that implements a multidimensional query engine, a first query from an application directed to a multidimensional index for a database table, wherein the first query includes one or more predicates for one or more dimensions included in the multidimensional index;
- performing, by the database client, in response to receiving the first query at the database client:
- identifying one or more dimensional ranges of the one or more dimensions that satisfy the predicates;
- identifying a range of the multidimensional index to scan for processing the first query based, at least in part, on the identified dimensional ranges, wherein the range of the multidimensional index comprises a plurality of different portions, each including one or more multidimensional index values that satisfy the predicates, and an another portion, adjacent to at least some of the different portions, not including multidimensional index values that satisfy the predicates, and wherein boundaries of the different portions are determined at least in part by the dimensional ranges that satisfy the predicates;
- sending a request from the database client to a processing node of a database service, the request causing the processing node to access storage that stores the database table to perform a scan of respective items mapped to the different portions of the range of the multidimensional index to apply the first query, wherein the request from the database client comprises an initial multidimensional index value and a filter for the items incorporating the dimensional ranges;
- upon receiving a result of the scanning of the respective items of at least one of the different portions of the range, skipping the other portion of the range that is adjacent to the scanned at least one portion of the range to generate a next multidimensional index to scan, wherein the received result excludes items determined, according to the filter, not to satisfy the first query;
- and
- providing a result of the first query according to the scanning of the respective items of the different portions of the range.
5 more elements
Dependencies are inferred from the claim text.