# US 8,788,482 B2 · Join tuple assembly by partial specializations > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,788,482 B2 - Document ID: US8788482B2 - Status: Granted - Kind: B2 - Application number: 13/616,044 - Filed: 2012-09-14 - Published: 2013-01-03 - Granted: 2014-07-22 - Earliest claimed: 2010-05-18 - Assignees: Sap SE - Applicants: Gerhard Hill - Inventors: Gerhard Hill - Web page: https://patentgrep.com/patent/US8788482B2 ## CPC - G06F 16/2456: {Join operations} - G06F 16/24542: {Plan optimisation} - G06F 16/284: {Relational databases} - G06F 16/24532: {of parallel queries} - G06F 16/24537: {of operators} - G06F 16/24544: {Join order optimisation} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Various embodiments of systems and methods for join tuple assembly by partial specializations are described herein. The join tuple assembly by partial specializations is a phase of the method for join query evaluation by semi-join reduction. By using partial specializations of the non-join part of the WHERE clause of a join query and matching sets, the join tuple assembly is organized in a manner that all computations are necessary, none are repeated, and failure to complete a partial join tuple to a full tuple is detected as early as possible. The method can be applied to inner and outer joins, and to arbitrary join graphs and non-join conditions in the WHERE clause. It can also be used outside the context of semi-join reductions. ## Claims ### Claim 1 An article of manufacture including a non-transitory computer readable storage medium to tangibly store instructions, which when executed by a computer, cause the computer to: receive a join query, a materialization graph representing a join part of the join query, and a plurality of matching sets derived from reduction of a plurality of relations; configure a tuple construction counter, which value indicates progression in an overall length of constructing a join tuple, and an iterator that traverses a matching set from the plurality of matching sets; and (A) determine a value of the tuple construction counter, wherein upon determining that the value of the tuple construction counter is a positive integer: (a) compute a partial specialization of an operator tree, wherein the operator tree represents a non-join part of the join query; (b) when the computed partial specialization satisfies the non-join part of the join query and the value of the tuple construction counter is less than the overall length of the join tuple to be constructed, recompute a subset of the plurality of matching sets; (c) when no empty matching set is encountered during recomputation, increase the value of the tuple construction counter by one count; and (d) when the computed partial specialization does not satisfy the non-join part of the join query or an empty matching set is encountered during recomputation, decrease the value of the tuple construction counter by one or more counts and continue to step A. ### Claim 2 (depends on 1) The article of manufacture of claim 1, further comprising instructions, which when executed by the computer, cause the computer to: (e) when the value of the tuple construction counter is equal to the overall length of the join tuple, identify a first join tuple satisfying the join part and the non-join part of the join query. ### Claim 3 (depends on 2) The article of manufacture of claim 2, further comprising instructions, which when executed by the computer, cause the computer to: continue steps (a) to (e) until the value of the tuple construction counter is equal to zero, wherein all join tuples satisfying the join part and the non-join part of the join query are identified when the value of the tuple construction counter is equal to zero. ### Claim 4 (depends on 1) The article of manufacture of claim 1, wherein the first join tuple is used directly in a functionality or stored in a storage unit. ### Claim 5 (depends on 1) The article of manufacture of claim 1, wherein the subset of the plurality of matching sets is recomputed with a tail function equal to the value of the tuple construction counter. ### Claim 6 (depends on 1) The article of manufacture of claim 1, wherein the subset of the plurality of matching sets represents reduction results derived from semi-join reduction of the plurality of relations. ### Claim 7 (depends on 1) The article of manufacture of claim 1, wherein the join part and the non-join part of the join query represent a plurality of Boolean conditions. ### Claim 8 A computer-implemented method comprising: receiving a join query, a materialization graph representing a join part of the join query, and a plurality of matching sets derived from reduction of a plurality of relations; a processor of the computer configuring a tuple construction counter, which value indicates progression in an overall length of constructing a join tuple and an iterator that traverses through elements in a matching set from the plurality of matching sets; and (A) the processor of the computer determining a value of the tuple construction counter, wherein upon determining that the value of the tuple construction counter is a positive integer: (a) computing a partial specialization of an operator tree, wherein the operator tree represents a non-join part of the join query; (b) when the computed partial specialization satisfies the non-join part of the join query and the value of the tuple construction counter is less than the overall length of the join tuple to be constructed, recomputing a subset of the plurality of matching sets; (c) when no empty matching set is encountered during recomputation, increasing the value of the tuple construction counter by one count; and (d) when the computed partial specialization does not satisfy the non-join part of the join query or an empty matching set is encountered, decreasing the value of the tuple construction counter and continue to step A. ### Claim 9 (depends on 8) The method of claim 8, further comprising: (e) when the value of the tuple construction counter is equal to the overall length of the join tuple, identifying a first join tuple satisfying the join part and the non-join part of the join query. ### Claim 10 (depends on 9) The method of claim 9, further comprising: continuing steps (a) to (e) until the value of the tuple construction counter is equal to zero, wherein all join tuples satisfying the join part and the non-join part of the join query are identified when the value of the tuple construction counter is equal to zero. ### Claim 11 (depends on 8) The method of claim 8, wherein the first join tuple is used directly in a functionality or stored in a storage unit. ### Claim 12 (depends on 8) The method of claim 8, wherein the subset of the plurality of matching sets is recomputed with a tail function equal to the value of the tuple construction counter. ### Claim 13 (depends on 8) The method of claim 8, wherein the subset of the plurality of matching sets represent reduction results derived from semi-join reduction of the plurality of relations. ### Claim 14 (depends on 8) The method of claim 8, wherein the join part and the non-join part of the join query represent a plurality of Boolean conditions. ### Claim 15 A computing system comprising: a database storage unit for storing one or more of a plurality of matching sets derived from reduction of a plurality of relations, a join query, and a materialization graph representing a join part of the join query; a processor in communication with the database storage unit that executes instructions including: configuring a tuple construction counter, which value indicates progression in an overall length of constructing a join tuple and an iterator that traverses through elements in a matching set from the plurality of matching sets; and (A) determining a value of the tuple construction counter, wherein upon determining that the value of the tuple construction counter is a positive integer: (a) computing a partial specialization of an operator tree, wherein the operator tree represents a non-join part of the join query; (b) when the computed partial specialization satisfies the non-join part of the join query and the value of the tuple construction counter is less than the overall length of the join tuple to be constructed, recomputing a subset of the plurality of matching sets; (c) when no empty matching set is encountered during recomputation, increasing the value of the tuple construction counter by one count; and (d) when the computed partial specialization does not satisfy the non-join part of the join query or an empty matching set is encountered, decreasing the value of the tuple construction counter and continue to step A. ### Claim 16 (depends on 15) The computing system of claim 15, the processor executes instructions further including: (e) when the value of the tuple construction counter is equal to the overall length of the join tuple, identifying a first join tuple satisfying the join part and the non-join part of the join query. ### Claim 17 (depends on 16) The computing system of claim 16, the processor executes instructions further including: continuing steps (a) to (e) until the value of the tuple construction counter is equal to zero, wherein all join tuples satisfying the join part and the non-join part of the join query are identified when the value of the tuple construction counter is equal to zero. ### Claim 18 (depends on 15) The computing system of claim 15, wherein the first join tuple is used directly in a functionality or stored in a storage unit. ### Claim 19 (depends on 15) The computing system of claim 15, wherein the subset of the plurality of matching sets is recomputed with a tail function equal to the value of the tuple construction counter. ### Claim 20 (depends on 15) The computing system of claim 15, wherein the subset of the plurality of matching sets represent reduction results derived from semi-join reduction of the plurality of relations. ### Claim 21 (depends on 15) The computing system of claim 15, wherein the join part and the non-join part of the join query represent a plurality of Boolean conditions.