Pushing joins across a union

• US 10,642,834 B1
• Filed: 03/30/2017
• Issued: 05/05/2020
• Est. Priority Date: 06/17/2008
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Teradata US, Inc. (Teradata Corporation)
• Inventors: Ghazal, Ahmad Said, McKenna, William Joseph
• Primary Examiner(s): Daye, Chelcie L
• Application Number:
  US15/474,657
• Time in Patent Office: 1,132 Days
• Field of Search: 707713, 707714
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24544 Join order optimisation

Abstract

Selecting a join plan for a query containing a join and a union block includes determining whether to propose a join plan with the join pushed across the union block. A selection is made between a join plan in which the join is not pushed across the union block and any proposed join plan in which the join is pushed across the union block.

Claims

1. A computer-implemented method for selecting a join plan for a query containing a plurality of joins and a union block, the computer-implemented method comprising:

selecting from among the plurality of joins a subset to consider for pushing across the union block;

identifying from among the selected joins N joins for which pushing the join across the union block is semantically correct;

proposing a join plan for all of the plurality of joins without any of the joins being pushed across the union block;

proposing 2^N separate join plans for the plurality of joins, each of the 2^N separate join plans comprising a unique combination of pushed joins and unpushed joins; and

selecting a join plan from among the proposed join plans;

wherein selecting from among the plurality of joins a subset to consider for pushing across the union block comprises;

determining that the number of joins in the plurality of joins is too great to propose a join plan for each of the possible alternatives of pushing one of the plurality of joins across the union block or not; and

in response, applying a set of heuristics to select fewer than all of the plurality of joins to consider for pushing across the union block.

2. The computer-implemented method of claim 1 wherein the subset is all of the plurality of joins.

3. The computer-implemented method of claim 1 wherein the subset is a proper subset of the plurality of joins.

4. The computer-implemented method of claim 1 wherein identifying the selected joins that should be pushed across the union block comprises:

determining that one of the selected joins comprises an inner join;

in response, determining that the union block comprises a UNION ALL; and

in response, identifying the one of the selected joins as an identified join.

5. The computer-implemented method of claim 1 wherein the union comprises a plurality of branches, each of the plurality of branches has a cardinality, and wherein identifying the selected joins that should be pushed across the union block comprises:

determining that one of the selected joins comprises an inner join;

in response, determining that the union block comprises a UNION (distinct);

in response, determining that pushing the one of the selected joins will not increase the cardinality of any of the plurality of branches of the union block; and

in response, identifying the one of the selected joins as an identified join.

6. The computer-implemented method of claim 1 wherein the union comprises a plurality of branches, each of the plurality of branches has a cardinality, and wherein identifying the selected joins that should be pushed across the union block comprises:

determining that one of the selected joins comprises an inner join;

in response, determining that the union block comprises a UNION (distinct);

in response, determining that pushing the one of the selected joins will increase the cardinality of any of the plurality of branches of the union block; and

in response, rejecting the one of the selected joins as an identified join.

7. The computer-implemented method of claim 1 wherein identifying the selected joins that should be pushed across the union block comprises:

determining that one of the selected joins comprises an outer join having an outer table and an inner table;

in response, determining that the union block is the outer table;

in response, identifying the one of the selected joins as an identified join.

8. The computer-implemented method of claim 1 wherein identifying the selected joins that should be pushed across the union block comprises:

determining that one of the selected joins comprises an outer join having an outer table and an inner table;

in response, determining that the union block is the inner table; and

in response, rejecting the one of the selected joins as an identified join.