Back to results
US 12,111,833 B1Granted
Query acceleration for disjunctive equijoin conditions
AssigneeAmazon Technologies, Inc.
InventorsSteven Alan Kirk, Mohammed Alkateb, Andreas Michael Kipf
Life of this patent
Estimating the term…
Abstract
Queries may be accelerated with disjunctive equijoin conditions. A query is received and a disjunctive equijoin condition identified. Different strategies, such as creating a filter data structure for distinct equijoins may be implemented where the filter data structure is applied to the result of scan operations for the disjunctive equijoin conditions. These strategies may be incorporated into a query plan generated for the query, which is then executed to return a result for the query.
Claims20
A system, comprising:
- a plurality of nodes implementing a processing cluster, respectively comprising at least one processor and a memory;
- wherein the processing cluster is configured to:
- receiving a query;
- parse the query to identify disjunctive equijoin condition comprising a plurality of equijoins between respective columns of different tables, wherein the disjunctive equijoin condition is specified in the query;
- generate a plan to perform the query, wherein the query plan comprises operations to:
- create a filter data structure for distinct ones of the plurality of equijoins, wherein the filter data structure is populated as part of a scan operation of the respective column that is identified as a build side of the distinct ones of the plurality of equijoins;
- and
- apply the filter data structure to tuples obtained by a further scan operation of a different one of the respective columns that is identified as a probe side of the distinct ones of the plurality of equijoins, wherein application of the filter removes one or more of the tuples from a result of the query according to an evaluation of the filter data structure that determines that a corresponding tuple for the one or more tuples is not present in the respective column identified as the build side;
- execute the plan to perform the query;
- and
- return the result of the query.
8 more elements
A method, comprising:
- receiving a query at a database system;
- identifying, by the database system, a disjunctive equijoin condition comprising a plurality of equijoins between respective columns of different tables, wherein the disjunctive equijoin condition is specified in the query;
- generating, by the database system, a plan to perform the query, wherein the query plan comprises:
- creating a filter data structure for distinct ones of the plurality of equijoins, wherein the filter data structure is populated as part of a scan operation of the respective column that is identified as a build side of the distinct ones of the plurality of equijoins;
- and
- applying the filter data structure to tuples obtained by a further scan operation of a different one of the respective columns that is identified as a probe side of the distinct ones of the plurality of equijoins, wherein application of the filter removes one or more of the tuples from a result of the query according to an evaluation of the filter data structure that determines that a corresponding tuple for the one or more tuples is not present in the respective column identified as the build side;
- executing, by the database system, the plan to perform the query;
- and
- returning, by the database system, the result of the query.
6 more elements
One or more non-transitory, computer-readable storage media, storing program instructions that when executed on or across one or more computing devices cause the one or more computing devices to implement:
- receiving a query at a database system;
- identifying, by the database system, a disjunctive equijoin condition comprising a plurality of equijoins between respective columns of different tables, wherein the disjunctive equijoin condition is specified in the query;
- generating, by the database system, a plan to perform the query, wherein the query plan comprises:
- creating a filter data structure for distinct ones of the plurality of equijoins, wherein the filter data structure is populated as part of a scan operation of the respective column that is identified as a build side of the distinct ones of the plurality of equijoins;
- and
- applying the filter data structure to tuples obtained by a further scan operation of a different one of the respective columns that is identified as a probe side of the distinct ones of the plurality of equijoins, wherein application of the filter removes one or more of the tuples from a result of the query according to an evaluation of the filter data structure that determines that a corresponding tuple for the one or more tuples is not present in the respective column identified as the build side;
- executing, by the database system, the plan to perform the query;
- and
- returning, by the database system, the result of the query.
6 more elements
Dependencies are inferred from the claim text.