SPLITTING OF A JOIN OPERATION TO ALLOW PARALLELIZATION

• US 20150261820A1
• Filed: 03/13/2014
• Published: 09/17/2015
• Est. Priority Date: 03/13/2014
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: Sybase Incorporated (SAP SE)
• Inventors: Cheng, Xun, Schneider, Peter
• Granted Patent: US 9,792,328 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

A system and method for processing a database query is described. In response to detection that a database query involves a star or snowflake join operation, a join operator in a preliminary query plan can be split into a build operator and a probe operator. The probe operator can be placed in a final query plan in the same place as the join operator in the preliminary query plan, while the build operator can be placed beneath the probe operator in the final query plan, between an exchange operator and the exchange operator'"'"'s child from the preliminary query plan.

Claims

1. A method for optimizing a database query, comprising:

accessing a fact table and a plurality of dimension tables referenced by the database query;

creating a preliminary query plan based on the database query;

detecting that the database query involves a star join or snowflake join operation using the fact table and the plurality of dimension tables;

in response to detecting that the database query involves a star join or snowflake join operation;

splitting a join operator in the preliminary query plan into a build operator and a probe operator;

placing the probe operator in a final query plan in a same place as the join operator in the preliminary query plan; and

placing the build operator beneath the probe operator in the final query plan.

2. The method of claim 1, further comprising executing the final query plan using a plurality of parallel threads by executing each build operator in the final query plan using a different thread.

3. The method of claim 1, wherein the build operator is placed between an exchange operator and the exchange operator'"'"'s child from the preliminary query plan

4. The method of claim 2, wherein the executing comprises passing a memory address of a hash table across the parallel threads without passing all of the rows of a dimension table.

5. The method of claim 2, wherein the executing comprises building a single hash table shared among the parallel probing threads independent of a number of the parallel threads.

6. The method of claim 2, when there is a bloom filter for the join operator, building a bit vector for the bloom filter once and using a same bit vector for probing during multiple scans of a fact table.

7. The method of claim 1, further comprising:

determining a selectivity ratio for each of a plurality of dimension tables, wherein a lower value for the selectivity ratio indicates that a corresponding dimension table is more restrictive compared to other dimension tables in the plurality of dimension tables;

creating a table ordering beginning with a fact table and continuing with each of the dimension tables in ascending order of the corresponding selectivity ratios of the dimension tables; and

creating a query plan involving join operations between successive tables in the table ordering.

8. A system comprising:

at least one processor;

a parser configured to parse a database query;

a normalizer configured to normalize the parsed database query;

an optimizer configured to create a preliminary query plan for the database query;

a query generation and execution component executable by the at least one processor and configured to;

detect that the database query involves a star or snowflake join operation using a determined fact table and a plurality of dimension tables referenced by the database query;

in response to detection that the database query involves a star or snowflake join operation;

split a join operator in the preliminary query plan into a build operator and a probe operator;

place the probe operator in a final query plan in the same place as the join operator in the preliminary query plan; and

place the build operator beneath the probe operator in the final query plan, between an exchange operator and the exchange operator'"'"'s child from the preliminary query plan.

9. The system of claim 8, wherein the optimizer is further configured to:

determine a selectivity ratio for each of the plurality of dimension tables, the selectivity ratio having a lower value the more restrictive a corresponding dimension table is;

create a table ordering beginning with the fact table and continuing with each of the dimension tables in ascending order of their corresponding selectivity ratios; and

create the preliminary query plan involving join operations between successive tables in the table ordering.

10. The system of claim 8, wherein the optimizer further comprises:

a star/snowflake join detector;

an

a dimension restrictiveness analyzer;

11. The system of claim 10, wherein the optimizer further comprises:

an exhaustive search engine.

12. The system of claim 9, wherein the query generation and execution component further comprises:

a hash join split code generator; and

a parallel plan execution engine.

13. The system of claim 9, wherein the system is a relational database management system (RDBMS).

14. A non-transitory machine-readable storage medium comprising instructions, which when implemented by one or more machines, cause the one or more machines to perform operations comprising:

accessing a fact table and a plurality of dimension tables referenced by the database query;

creating a preliminary query plan based on the database query;

detecting that the database query involves a star or snowflake join operation using the determined fact table and plurality of dimension tables;

in response to detection that the database query involves a star or snowflake join operation;

splitting a join operator in the preliminary query plan into a build operator and a probe operator;

placing the probe operator in a final query plan in the same place as the join operator in the preliminary query plan; and

placing the build operator beneath the probe operator in the final query plan.

15. The non-transitory machine-readable storage medium of claim 14, further comprising executing the query plan using a plurality of parallel threads by executing each build operator in the final query plan using a different thread.

16. The non-transitory machine-readable storage medium of claim 14, wherein the build operator is placed between an exchange operator and the exchange operator'"'"'s child from the preliminary query plan.

17. The non-transitory machine-readable storage medium of claim 15, wherein the executing comprises passing a memory address of a hash table across the parallel threads without passing all of the rows of a dimension table.

18. The non-transitory machine-readable storage medium of claim 15, wherein the executing comprises building a single hash table shared among the parallel threads, no matter how many threads are used.

19. The non-transitory machine-readable storage medium of claim 15, when there is a bloom filter for the join operator, building a bit vector for the bloom filter only once and using the same bit vector for probing during multiple scans of a dimension table.

20. The non-transitory machine-readable storage medium of claim 14, further comprising:

determining a selectivity ratio for each of the plurality of dimension tables, the selectivity ratio having a lower value the more restrictive a corresponding dimension table is;

creating a table ordering beginning with the fact table and continuing with each of the dimension tables in ascending order of their corresponding selectivity ratios;

creating a query plan involving join operations between successive tables in the table ordering.