# US 12,111,833 B1 · Query acceleration for disjunctive equijoin conditions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 12,111,833 B1 - Document ID: US12111833B1 - Status: Granted - Kind: B1 - Application number: 18/477,926 - Filed: 2023-09-29 - Granted: 2024-10-08 - Earliest claimed: 2023-09-29 - Assignees: Amazon Technologies, Inc. - Applicants: Amazon Technologies, Inc. - Inventors: Steven Alan Kirk; Mohammed Alkateb; Andreas Michael Kipf - Web page: https://patentgrep.com/patent/US12111833B1 ## CPC - G06F 16/24544: {Join order optimisation} - G06F 16/2282: {Tablespace storage structures; Management thereof} - G06F 16/24542: {Plan optimisation} - G06F 16/248: Presentation of query results - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The system of claim 1, wherein the processing cluster is further configured to: receive another query at the database system; identify a disjunctive equijoin condition comprising a plurality of equijoins between respective columns of different tables, wherein the disjunctive equijoin condition is specified in the other query, and wherein a first column of the respective columns of one of the different tables is a shared column specified in a first equijoin of the plurality of equijoins that is joined with a second column of the different columns, and wherein the shared column is also specified in a second equijoin of the plurality of equijoins that is joined with a third column of the different columns; generate another plan to perform the other query, wherein the other query plan comprises operations to: performing respective hash table probes for both the second column and the third column for tuples obtained by a scan operation to identify one or tuples that successfully match the shared column according to the respective hash table probes for generating a result of the other query; execute the other plan to perform the other query; and return the result of the other query. ### Claim 3 (depends on 1) The system of claim 1, wherein the processing cluster is further configured to: receive another query; identify a disjunctive equijoin condition and a single column condition for the other query, wherein the disjunctive equijoin condition comprises a plurality of equijoins between respective columns of different tables; determine that the single column condition is one column of the respective columns in the plurality of equijoins of the disjunctive equijoin condition; generate another plan to perform the other query, wherein the other query plan comprises: adding the single column condition to the evaluation of the one column in the plurality of equijoins in the disjunctive equijoin condition; execute the other plan to perform the other query; and return a result of the other query. ### Claim 4 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. ### Claim 5 (depends on 4) The system of claim 4, wherein the processing cluster is hosted as part of a database service implemented as part of a provider network. ### Claim 6 (depends on 4) The method of claim 4, further comprising: receiving another query at the 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 other query, and wherein a first column of the respective columns of one of the different tables is a shared column specified in a first equijoin of the plurality of equijoins that is joined with a second column of the different columns, and wherein the shared column is also specified in a second equijoin of the plurality of equijoins that is joined with a third column of the different columns; generating, by the database system, another plan to perform the other query, wherein the other query plan comprises: performing respective hash table probes for both the second column and the third column for tuples obtained by a scan operation to identify one or tuples that successfully match the shared column according to the respective hash table probes for generating a result of the other query; executing, by the database system, the other plan to perform the other query; and returning, by the database system, the result of the other query. ### Claim 7 (depends on 6) The method of claim 6, wherein the second column and the third column are from respective smaller sides of the first equijoin and the second equijoin, wherein the other plan builds a first hash table and a second hash table, wherein the second hash table includes a field that points back to a hash entry in the first hash table. ### Claim 8 (depends on 4) The method of claim 4, wherein the application of the filter data structure is performed by a compute node of a processing cluster. ### Claim 9 (depends on 4) The method of claim 4, further comprising: receiving another query at the database system; identifying, by the database system, a disjunctive equijoin condition and a single column condition for the other query, wherein the disjunctive equijoin condition comprises a plurality of equijoins between respective columns of different tables; determining, by the database system, that the single column condition is one column of the respective columns in the plurality of equijoins of the disjunctive equijoin condition; generating, by the database system, another plan to perform the other query, wherein the other query plan comprises: adding the single column condition to the evaluation of the one column in the plurality of equijoins in the disjunctive equijoin condition; executing, by the database system, the other plan to perform the other query; and returning, by the database system, a result of the other query. ### Claim 10 (depends on 9) The method of claim 9, wherein the single column condition is determined based, at least in part, on a zone map maintained by the database system. ### Claim 11 (depends on 4) The method of claim 4, wherein the filter data structure is a probabilistic data structure. ### Claim 12 (depends on 4) The method of claim 4, wherein the filter data structure is a deterministic data structure. ### Claim 13 (depends on 4) The method of claim 4, wherein the database system is hosted as part of a database service implemented as part of a provider network. ### Claim 14 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. ### Claim 15 (depends on 14) The one or more non-transitory, computer-readable storage media of claim 14, storing further program instructions that when executed on or across the other one or more computing devices, causes the one or more computing devices to implement: receiving another query at the 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 other query, and wherein a first column of the respective columns of one of the different tables is a shared column specified in a first equijoin of the plurality of equijoins that is joined with a second column of the different columns, and wherein the shared column is also specified in a second equijoin of the plurality of equijoins that is joined with a third column of the different columns; generating, by the database system, another plan to perform the other query, wherein the other query plan comprises: performing respective hash table probes for both the second column and the third column for tuples obtained by a scan operation to identify one or tuples that successfully match the shared column according to the respective hash table probes for generating a result of the other query; executing, by the database system, the other plan to perform the other query; and returning, by the database system, the result of the other query. ### Claim 16 (depends on 15) The one or more non-transitory, computer-readable storage media of claim 15, wherein the second column and the third column are from respective smaller sides of the first equijoin and the second equijoin, wherein the other plan builds a first hash table and a second hash table, wherein the second hash table includes a field that points back to a hash entry in the first hash table. ### Claim 17 (depends on 14) The one or more non-transitory, computer-readable storage media of claim 14, wherein the filter data structure is a probabilistic data structure. ### Claim 18 (depends on 14) The one or more non-transitory, computer-readable storage media of claim 14, storing further program instructions that when executed on or across the other one or more computing devices, causes the one or more computing devices to implement: receiving another query at the database system; identifying, by the database system, a disjunctive equijoin condition and a single column condition for the other query, wherein the disjunctive equijoin condition comprises a plurality of equijoins between respective columns of different tables; determining, by the database system, that the single column condition is one column of the respective columns in the plurality of equijoins of the disjunctive equijoin condition; generating, by the database system, another plan to perform the other query, wherein the other query plan comprises: adding the single column condition to the evaluation of the one column in the plurality of equijoins in the disjunctive equijoin condition; executing, by the database system, the other plan to perform the other query; and returning, by the database system, a result of the other query. ### Claim 19 (depends on 18) The one or more non-transitory, computer-readable storage media of claim 18, wherein the single column condition is determined based, at least in part, on a zone map maintained by the database system. ### Claim 20 (depends on 14) The one or more non-transitory, computer-readable storage media of claim 14, wherein the database system is hosted as part of a database service implemented as part of a provider network.