Join tuple assembly by partial specializations

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.

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.