EFFICIENT JOIN WITH ONE OR MORE LARGE DIMENSION TABLES

• US 20140214796A1
• Filed: 01/31/2013
• Published: 07/31/2014
• Est. Priority Date: 01/31/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Barber, Ronald J., Chainani, Naresh K., Lohman, Guy M., Pirahesh, Mir Hamid, Raman, Vijayshankar, Sidle, Richard S., Tata, Sandeep
• Granted Patent: US 9,141,667 B2
• Time in Patent Office: Days
• US Class Current: 707/714
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations

Abstract

Embodiments of the invention relate to processing queries that utilize fact and/or dimension tables. In one aspect, a pre-join filtering phase precedes a star join. The necessary conditions for the pre-join filtering are considered for a given SQL query, including an estimated size of the hash table exceeding a threshold and presence of a local predicate either on the fact table or one or more dimension tables that is not a large dimension table. Once the necessary conditions are satisfied, the execution of the query exploits the pre-join filtering to build a pre-join output filter from columns of a reduced fact table that joins with each large dimension table. Thereafter, all the dimension tables and the fact table are joined in a star join while exploiting each pre-join filter. Accordingly, the order of when joins occur is changed in order to reduce the size of the fact table and to work from the fact table to reduce the size of large dimension tables.

Claims

1. A method for efficient hash joins with a large dimension table, comprising:

gathering table characteristics to support a query, the gathering including identifying a first set of at least one dimension table having a hash table size estimated to exceed a defined threshold, and identifying a second set of remaining tables having at least one local predicate;

executing a query responsive to the gathered table characteristics, the query execution including;

reducing each identified large dimension table in the first set, including;

building a join filter from each dimension table of the second set;

scanning a fact table and reducing the fact table by applying predicates local to the fact table, and applying each join predicate to each table in the second set by probing its corresponding join filter; and

for each large dimension table, creating a pre-join output filter from columns of the reduced fact table that join with each large dimension table;

joining all the dimension tables and the fact table in a star join while exploiting each pre-join output filter, including;

scanning each large dimension table of the first set, applying the created pre-join output filter as a local predicate during the scan, and for each qualifying row of the dimension table, creating an entry in a hash table;

scanning each dimension table in the second set, including applying predicates local to each remaining dimension table, and for each qualifying row of each remaining dimension table, creating an entry in an associated hash table; and

joining the fact table with all dimension tables, including scanning the fact table and probing each corresponding hash table for each reduced dimension table.

2. The method of claim 1, further comprising building a separate star join filter for each dimension table and probing the star join filter for each dimension when scanning the fact table, before probing the hash table for that dimension.

3. The method of claim 1, further comprising dynamically verifying initiating the filter join during the building of one of the hash tables responsive to memory requirements exceeding system capacity.

4. The method of claim 1, further comprising eliminating tables in the second set as they are scanned if the local predicate is dynamically verified to be insufficiently selective.

5. The method of claim 1, wherein the pre-join output filter eliminates values in the dimension table that are absent from the fact table.

6. The method of claim 1, further comprising during reducing each identified large dimension table in the first set while scanning each dimension table in the second set, for each qualifying row of each dimension table in the second set creating an entry in an associated hash table, and eliminating scanning of the dimension table in the joining of all the dimension tables and the fact table in a star join.

7. The method of claim 6, further comprising prior to the star join, creating a pre-join output filter for each partition of the fact table and broadcasting the pre-join output filter to each large dimension table partition, and each recipient node containing the partitions of the large dimension table applying a logical OR combining each pre-join output filter.

8. The method of claim 1, further comprising partitioning the fact table and each large dimension table across two or more nodes of a shared-nothing cluster, and all remaining dimension tables are replicated on each node in the cluster.

9. A computer program product for efficient hash joins in a query with a large dimension table, the computer program product comprising a computer-readable storage medium having program code embodied therewith, the program code being executable by a processor to:

gather table characteristics to support the query, the gathering including identification of a first set of at least one dimension table having a hash table size estimated to exceed a defined threshold, and identification of a second set of remaining tables having at least one local predicate;

execute a query responsive to the gathered table characteristics, the query execution including;

reduce each identified large dimension table in the first set, including;

building a join filter from each dimension table of the second set;

scanning a fact table and reducing the fact table by applying predicates local to the fact table, and applying each join predicate to each table in the second set by probing its corresponding join filter; and

for each large dimension table, creating a pre-join output filter from columns of the reduced fact table that join with each large dimension table; and

join all the dimension tables and the fact table in a star join while exploiting each pre-join output filter, including;

scanning each large dimension table of the first set, applying the created pre-join output filter as a local predicate during the scan and for each qualifying row of the dimension table creating an entry in a hash table;

scanning each dimension table in the second set, including applying predicates local to each remaining dimension table and for each qualifying row of each remaining dimension table creating an entry in an associated hash table; and

joining the fact table with all dimension tables, including scanning the fact table and probing each corresponding hash table for each reduced dimension table.

10. The computer program product of claim 9, further comprising program code to build a separate star join filter for each dimension table and probe the star join filter for each dimension when scanning the fact table, before probing the hash table for that dimension.

11. The computer program product of claim 9, further comprising program code to dynamically verify initiating the filter join during the building of one of the hash tables responsive to memory requirements exceeding system capacity.

12. The computer program product of claim 9, further comprising program code to eliminate tables in the second set as they are scanned if the local predicate is dynamically verified to be insufficiently selective.

13. The computer program product of claim 9, wherein the pre-join output filter eliminates values in the dimension table that are absent from the fact table.

14. The computer program product of claim 9, further comprising program code to create an entry an associated hash table while scanning each dimension table in the second set for each qualifying row of each dimension table in the second set, including eliminating scanning of the dimension table in the star join phase.

15. The computer program product of claim 14, further comprising prior to the star join, program code to create the pre-join output filter for each partition of the fact table and to broadcast the pre-join output filter to each large dimension table partition, and program code for each recipient node containing the partitions of the large dimension table to apply a logical OR combining each pre-join output filter.

16. The computer program product of claim 9, further comprising program code to partition the fact table and each large dimension table across two or more nodes of a shared-nothing cluster, and replicate all remaining dimension tables on each node in the cluster.

17. A system comprising:

a processing unit in communication with data storage, the data storage having one or more tables of a database;

a functional unit in communication with memory and the processing unit, the functional unit having tools to support query processing, the tools comprising;

an identification manager to identify a first set of at least one dimension table having a hash table size estimated to exceed a defined threshold, and to identify a second set of remaining tables having at least one local predicate;

a query manager in communication with the identification manager, the query manager to execute a query, the query execution including a first phase manager and a second phase manager;

the first phase manager to reduce each identified large dimension table in the first set, including;

build a join filter from each dimension table of the second set;

scan a fact table and reduce the fact table by applying predicates local to the fact table, and apply each join predicate to each table in the second set by probing its corresponding join filter; and

for each large dimension table, create a pre-join output filter from columns of the reduced fact table that join with each large dimension table;

the second phase manager to join all the dimension tables and the fact table in a star join while exploiting each pre-join output filter from the first phase, including;

scan each large dimension table of the first set, apply the created pre-join output filter as a local predicate during the scan and for each qualifying row of the dimension table create an entry in a hash table; and

scan each dimension table in the second set, including applying predicates local to each remaining dimension table and for each qualifying row of each remaining dimension table create an entry in an associated hash table; and

a join manager in communication with query manager, the join manager to join the fact table with all dimension tables, including scanning the fact table and probing each corresponding hash table for each reduced dimension table.

18. The system of claim 17, further comprising a star join manager in communication with the query manager, the star join manager to build a separate star join filter for each dimension table and to probe the star join filter for each dimension when scanning the fact table and before probing the hash table for that dimension.

19. The system of claim 17, further comprising the first phase manager to dynamically verify initiation of the filter join during the build of one of the hash tables responsive to memory requirements exceeding system capacity.

20. The system of claim 17, further comprising the first phase manager to eliminate tables in the second set as they are scanned if the local predicate is dynamically verified to be insufficiently selective.

21. The system of claim 17, further comprising the first phase manager to eliminate values in the dimension table that are absent from the fact table.

22. The system of claim 21, further comprising the first phase manager to create a pre-join output filter for each partition of the fact table and to broadcast the pre-join output filter to each large dimension table partition, and for each recipient node containing the partitions of the large dimension table to apply a logical OR combining each pre-join output filter.

23. The system of claim 17, further comprising a partition manager in communication with the query manager, the partition manager to partition the fact table and each large dimension table across two or more nodes of a shared-nothing cluster, and to replicate all remaining dimension tables on each node in the cluster.