# US 9,870,397 B2 · Processing multi-way theta join queries involving arithmetic operators on MapReduce > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,870,397 B2 - Document ID: US9870397B2 - Status: Granted - Kind: B2 - Application number: 14/462,730 - Filed: 2014-08-19 - Published: 2016-02-25 - Granted: 2018-01-16 - Earliest claimed: 2014-08-19 - Assignees: International Business Machines Corporation - Applicants: International Business Machines Corporation - Inventors: Bhupesh Chawda; Himanshu Gupta; Sriram Raghavan - Web page: https://patentgrep.com/patent/US9870397B2 ## CPC - G06F 16/24544: {Join order optimisation} - G06F 16/2456: {Join operations} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods, systems, and computer program products for processing multi-way theta join queries involving arithmetic operators on MapReduce are provided herein. A method includes converting (i) a multi-way theta join query into a multi-way interval join query, and (ii) one or more items of data associated with the multi-way theta join query to one or more items of interval data; executing the multi-way interval join query on the one or more items of interval data via MapReduce to generate an output, wherein the output comprises a set of multiple responses to the multi-way interval join query; and processing the output to generate a solution to the multi-way theta join query, wherein said processing comprises discarding each response from the set that does not satisfy the multi-way theta join query. ## Claims ### Claim 1 A method comprising: converting (i) a multi-way theta join query on MapReduce into a multi-way interval join query on MapReduce, and (ii) one or more items of data associated with the multi-way theta join query to one or more items of interval data; executing the multi-way interval join query on the one or more items of interval data via MapReduce to generate an output, wherein the output comprises a set of multiple responses to the multi-way interval join query; and processing the output to generate a solution to the multi-way theta join query, wherein said processing comprises discarding each response from the set that does not satisfy the multi-way theta join query; wherein said converting, said executing, and said processing are carried out by at least one computing device. ### Claim 2 (depends on 1) The method of claim 1, wherein said processing comprises generating the solution without a series of intermediate joins. ### Claim 3 (depends on 1) The method of claim 1, comprising: storing said one or more items of interval data. ### Claim 4 (depends on 1) The method of claim 1, comprising: optimizing the multi-way interval join query. ### Claim 5 (depends on 4) The method of claim 4, wherein said optimizing comprises reducing the number of conditions in the multi-way interval join query involving one or more arithmetic operators. ### Claim 6 (depends on 1) The method of claim 1, wherein said converting comprises converting the multi-way theta join query into multiple multi-way interval join queries. ### Claim 7 (depends on 6) The method of claim 6, comprising: selecting one multi-way interval join query from the multiple multi-way interval join queries. ### Claim 8 (depends on 1) The method of claim 1, comprising: categorizing the multi-way interval join query into one of multiple classes. ### Claim 9 (depends on 8) The method of claim 8, wherein the multiple classes comprise (i) co-location interval join queries, (ii) sequence interval join queries, (iii) hybrid interval join queries, and (iv) general interval join queries. ### Claim 10 A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computing device to cause the computing device to: convert (i) a multi-way theta join query on MapReduce into a multi-way interval join query on MapReduce, and (ii) one or more items of data associated with the multi-way theta join query to one or more items of interval data; execute the multi-way interval join query on the one or more items of interval data via MapReduce to generate an output, wherein the output comprises a set of multiple responses to the multi-way interval join query; and process the output to generate a solution to the multi-way theta join query, wherein said processing comprises discarding each response from the set that does not satisfy the multi-way theta join query. ### Claim 11 (depends on 10) The computer program product of claim 10, wherein said processing comprises generating the solution without a series of intermediate joins. ### Claim 12 A system comprising: a memory; and at least one processor coupled to the memory and configured for: converting (i) a multi-way theta join query on MapReduce into a multi-way interval join query on MapReduce, and (ii) one or more items of data associated with the multi-way theta join query to one or more items of interval data; executing the multi-way interval join query on the one or more items of interval data via MapReduce to generate an output, wherein the output comprises a set of multiple responses to the multi-way interval join query; and processing the output to generate a solution to the multi-way theta join query, wherein said processing comprises discarding each response from the set that does not satisfy the multi-way theta join query. ### Claim 13 (depends on 12) The system of claim 12, wherein said processing comprises generating the solution without a series of intermediate joins. ### Claim 14 A method comprising: converting a multi-way theta join query on MapReduce into a multi-way interval join query on MapReduce, wherein the multi-way theta join query comprises one or more join conditions involving one or more arithmetic operators on one or more items of real-valued data; optimizing the multi-way interval join query to reduce the number of conditions in the multi-way interval join query that include the one or more arithmetic operators; executing the optimized multi-way interval join query via MapReduce to generate an output; and processing the output to generate a solution in response to the optimized multi-way theta join query; wherein said converting, said optimizing, said executing, and said processing are carried out by at least one computing device. ### Claim 15 (depends on 14) The method of claim 14, wherein said converting further comprises converting one or more items of data associated with the multi-way theta join query to one or more items of interval data. ### Claim 16 (depends on 15) The method of claim 15, wherein said converting the one or more items of data associated with the multi-way theta join query to one or more items of interval data comprises generating one or more items of intermediate data. ### Claim 17 (depends on 14) The method of claim 14, wherein said converting comprises converting the multi-way theta join query into multiple multi-way interval join queries. ### Claim 18 (depends on 17) The method of claim 17, comprising: selecting one multi-way interval join query from the multiple multi-way interval join queries. ### Claim 19 (depends on 14) The method of claim 14, comprising: categorizing the multi-way interval join query into one of multiple classes. ### Claim 20 (depends on 19) The method of claim 19, wherein the multiple classes comprise (i) co-location interval join queries, (ii) sequence interval join queries, (iii) hybrid interval join queries, and (iv) general interval join queries.