Fast algorithms for computing semijoin reduction sequences

• US 20080027904A1
• Filed: 07/27/2006
• Published: 01/31/2008
• Est. Priority Date: 07/27/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Peh, Thomas, Hill, Gerhard L.
• Granted Patent: US 8,271,478 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation

Abstract

Systems and methods for using optimization techniques to construct a nearly optimal execution plan for an outer join query are disclosed. A query graph of the outer join query is constructed, by computing for each node the set of nodes influencing it, for each target node the set of its needed reducers, and predetermining the effects of all admissible moves in all possible sequences. The directed graph of all admissible move sequences is formed. An optimization process includes dynamically generating good estimations for the target distance of a search state. Some heuristics are disclosed for providing start solutions for the optimization process.

Claims

1. A method for executing an outer join query in which all joins are evaluated by semijoins, the method comprising:

generating a query graph of nodes and target nodes for a query, comprising;

computing for each node the set of nodes influencing it;

computing for each target node the set of its needed reducers;

predetermining the effects of admissible move sequences;

forming a directed graph for the admissible move sequences; and

performing an optimization process, using a search algorithm on the directed graph to determine a least-cost execution plan for the query.

2. A method in accordance with claim 1, further comprising using a close lower bound estimation of the future cost h(s) of a search state s, valid for the outer join query.

3. A method in accordance with claim 1, further comprising executing the execution plan to execute the outer join query.

4. A method in accordance with claim 1, further comprising determining a start solution for the search algorithm using start heuristics.

5. A method in accordance with claim 4, wherein the start heuristics is selected from a set of start heuristics that contains:

a star heuristic, a snake heuristic, and heuristics of local and global improvement on other heuristics.

6. A method in accordance with claim 4, where the use of heuristics and optimization, with regard to sequence and time, is subject to a time management scheme.

7. A method in accordance with claim 1, wherein the optimization process includes an A* optimization process, and includes maintaining at least two lists of search states including an OPEN list having search states whose successors have not yet been constructed, and a CLOSED list having those search states whose successors have been constructed.

8. A method in accordance with claim 5, further comprising, wherein if the least cost of the search states in the OPEN list are substantially the same, ordering the substantially identical search states in the OPEN list according to progress.

9. A method for executing an outer join query in which all joins are evaluated by semijoins, the method comprising:

generating a query graph of nodes and target nodes for the query; and

performing an optimization process, using a search algorithm on the directed graph to determine a least-cost execution plan for the query.

10. A method in accordance with claim 9, wherein generating a query graph further comprises:

computing for each node the set of nodes influencing it; and

computing for each target node the set of its needed reducers.

11. A method in accordance with claim 10, wherein generating a query graph further comprises:

predetermining the effects of admissible move sequences; and

forming a directed graph for the admissible move sequences.

13. A method in accordance with claim 9, further comprising using a close lower bound estimation of the future cost h(s) of a search state s, valid for the outer join query.

14. A method in accordance with claim 9, further comprising executing the execution plan to execute the outer join query.

15. A method in accordance with claim 9, further comprising determining a start solution for the search algorithm using start heuristics.

18. A method in accordance with claim 9, wherein the optimization process includes an A* optimization process, and includes maintaining at least two lists of search states including an OPEN list having search states whose successors have not yet been constructed, and a CLOSED list having those search states whose successors have been constructed.

19. A method in accordance with claim 18, further comprising, wherein if the least cost of the search states in the OPEN list are substantially the same, ordering the substantially identical search states in the OPEN list according to progress.

16. A method in accordance with claim 12, wherein the start heuristics is selected from a set of start heuristics that contains:

a star heuristic, a snake heuristic, and heuristics of local and global improvement on other heuristics.

17. A method in accordance with claim 16, where the use of heuristics and optimization, with regard to sequence and time, is subject to a time management scheme.

20. A computer program product, embodied on tangible media, the computer program product including pieces of executable code to cause a data processing apparatus to perform operations comprising:

executing an outer join query in which all joins are evaluated by semijoins, the outer join query comprising;

generating a query graph of nodes and target nodes for a query, comprising;

computing for each node the set of nodes influencing it;

computing for each target node the set of its needed reducers;

predetermining the effects of admissible move sequences;

forming a directed graph for the admissible move sequences; and

performing an optimization process, using a search algorithm on the directed graph to determine a least-cost execution plan for the query.