Fetching optimization in multi-way pipelined database joins
View Patent ↗A method of performing a multi-way join of a plurality of database relations includes executing a plurality of pipelined two-way joins with the database relations. Each two-way join has two sequential phases. In the first phase, missing attributes of the input relations that are required to evaluate a joining criterion specific to said two-way join are fetched from a non-volatile memory device, and the input relations are joined according to the criterion. In the second phase, any additional missing attributes of the input relations are fetched from the non-volatile memory device as assigned by an optimization process executed prior to commencing the multi-way join.
1. A method of performing a multi-way join of a plurality of database relations, comprising:
executing a plurality of pipelined two-way joins with said relations, each said two-way join comprising a first phase and a second phase;
in which said first phase of each said two-way join comprises:
materializing from a non-volatile memory device any missing attributes in input relations that are required in a joining criterion specific to said two-way join and have not been materialized; and
joining said input relations according to said criterion; and in which said second phase of each said two-way join comprises:
materializing from said non-volatile memory device any additional missing attributes in said input relations as assigned by an optimization process executed prior to commencing said multi-way join,
in which the attributes in the relations are assigned to be materialized at one of the first phase and second phase of the two-way join based on whether the attributes are required for the recipient of the two-way join's result and based on whether the current two-way join requires the attributes, and
in which the missing attributes comprise any attributes that are required for the result of the two-way join and have not been materialized.
2. The method of claim 1 , in which said database relations are stored on said non-volatile memory device in a column-based mini page format.
3. The method of claim 1 , in which said optimization process is configured to individually assign each attribute in said database relations to be fetched during one of said first and second phases in one of said two-way joins according to a computed minimum time cost in fetching said attribute.
4. The method of claim 1 , in which said optimization process is configured to order fetches according to attribute sizes at each two-way join.
5. The method of claim 1 , in which said non-volatile memory device comprises at least one solid state drive.
6. The method of claim 1 , in which said joining said input relations according to said criterion comprises performing at least one of: a hash-join, a sort-merge join, an indexed nested loop, and a nested loop on said input relations.
7. The method of claim 1 , in which materializing comprises fetching said missing attributes into an instantiation of said database relations stored in volatile memory.
8. The method of claim 1 , further comprising writing a final result of said plurality of pipelined two-way joins to said non-volatile memory device.
9. The method of claim 1 , further comprising:
determining if each of the attributes in the relations is required by an earlier two-way join among the plurality of pipelined two-way joins,
in which if an attribute among the attributes in the relations is required by an earlier two-way join among the plurality of pipelined two-way joins, then skipping the attribute and evaluating the attribute at an earlier two-way join among the plurality of pipelined two-way joins.
10. The method of claim 9 , further comprising:
if the attribute is not required by an earlier two-way join among the plurality of pipelined two-way joins, then determining whether the attribute first appears in the two-way join.
11. The method of claim 10 , further comprising:
if the attribute first appears in the two-way join, then:
assigning the attribute to be materialized during the first phase of the two-way join if the attribute is required for the two-way join; and
assigning the attribute to be materialized during the second phase of the two-way join if the attribute is not required for the two-way join.
12. The method of claim 10 , further comprising:
if the attribute does not first appear in the two-way join, then:
determining if the result of the recipient of the two-way join is smaller than the largest input relation in a two-way join where this attribute first appears.
13. The method of claim 12 , in which if the result of the recipient of the two-way join is smaller than the largest input relation in a two-way join where this attribute first appears, then assigning the attribute to the second phase of the two-way join.
14. The method of claim 12 , in which if the result of the recipient of the two-way join is not smaller than the largest input relation in a two-way join where this attribute first appears, then evaluating whether the attribute first appears in a two-way join preceding the two-way join.
15. A system for performing a multi-way join on a plurality of database relations, said system comprising:
a non-volatile memory device configured to store said database relations, and;
a processor communicatively coupled to said non-volatile memory device, said processor comprising volatile memory;
in which said database management program instructs said processor to execute a plurality of pipelined two-way joins with said relations, each said two-way join comprising a first phase and a second phase;
in which said first phase of each said two-way join comprises:
materializing from said non-volatile memory device into said volatile memory any missing attributes in input relations that are required in a joining criterion specific to said two-way join and have not been materialized; and
joining said input relations according to said criterion; and in which said second phase of each said two-way join comprises:
materializing from said non-volatile memory device any additional missing attributes in said input relations as assigned by said database management program prior to commencing said multi-way join,
in which the attributes in the relations are assigned to be materialized at one of the first phase and second phase of the two-way join based on whether the attributes are required for the recipient of the two-way join's result and based on whether the current two-way join requires the attributes, and
in which the missing attributes comprise any attributes that are required for the result of the two-way join and have not been materialized.
16. The system of claim 15 , in which said database relations are stored on said non-volatile memory device in a column-based mini page format.
17. The system of claim 15 , in which said non-volatile memory device comprises at least one solid state drive.
18. The system of claim 15 , in which said joining said input relations according to said criterion comprises performing at least one of: a hash-join, a sort-merge join, an indexed nested loop, and a nested loop on said input relations.
19. The system of claim 15 , in which the database management program instructs the processor to individually assign each attribute in the database relations to be materialized during one of the first and second phases in one of the two-way joins during an optimization process according to a computed minimum time cost in fetching the attribute.
20. The system of claim 19 , in which said optimization process is configured to order attribute fetching in said multi-way join according to attribute sizes at each two-way join.
21. The system of claim 19 , in which said optimization process is configured to assign said attributes to said two-way joins in a sequential order beginning with a last of said two-way joins to be joined in said multi-way join and ending with a first of said two-way joins to be joined in said multi-way join.
22. A computer program product for performing a multi-way join of a plurality of database relations, said computer program product comprising:
a non-transitory computer usable medium configured to store computer usable program code, said computer usable program code comprising:
computer usable program code to, when executed by a processor, execute an optimization process prior to commencing said multi-way join;
computer usable program code to, when executed by a processor, execute a plurality of pipelined two-way joins with said relations, each said two-way join comprising a first phase and a second phase;
in which said first phase of each said two-way join comprises:
materializing from a non-volatile memory device any missing attributes in input relations that are required in a joining criterion specific to said two-way join; and
joining said input relations according to said criterion; and
in which said second phase of each said two-way join comprises:
materializing from said non-volatile memory device any additional missing attributes in said input relations as assigned by said optimization process,
in which the attributes in the relations are assigned to be materialized at one of the first phase and second phase of the two-way join based on whether the attributes are required for the recipient of the two-way join's result and based on whether the current two-way join requires the attributes, and
in which the missing attributes comprise any attributes that are required for the result of the two-way join and have not been materialized.
23. The computer program product of claim 22 , in which said database relations are stored on said non-volatile memory device in a column-based mini page format.
24. The computer program product of claim 23 , in which said optimization process is configured to individually assign each attribute in said database relations to be materialized during one of said first and second phases in one of said two-way joins according to a computed minimum time cost in fetching said attribute.
25. The computer program product of claim 22 , in which said optimization process is configured to order said fetches according to attribute sizes at each two-way join.
26. The computer program product of claim 22 , in which said non-volatile memory device comprises at least one solid state drive.