METHODS AND SYSTEMS FOR GENERATING QUERY PLANS THAT ARE COMPATIBLE FOR EXECUTION IN HARDWARE

• US 20100005077A1
• Filed: 07/07/2008
• Published: 01/07/2010
• Est. Priority Date: 07/07/2008
• Status: Abandoned Application

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Kickfire, Inc. (Teradata Corporation)
• Inventors: Ku, Chi-Young, Chamdani, Joseph I., Surlaker, Kapil, Zhang, Chun, Shau, James, Krishnamurthy, Ravi, Corwin, Michael, Branscome, Jeremy
• Application Number:
  US12/168,821
• Publication Number:
  US 20100005077A1
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Embodiments of the present invention generate and optimize query plans that are at least partially executable in hardware. Upon receiving a query, the query is rewritten and optimized with a bias for hardware execution of fragments of the query. A template-based algorithm may be employed for transforming a query into fragments and then into query tasks. The various query tasks can then be routed to either a hardware accelerator, a software module, or sent back to a database management system for execution. For those tasks routed to the hardware accelerator, the query tasks are compiled into machine code database instructions. In order to optimize query execution, query tasks may be broken into subtasks, rearranged based on available resources of the hardware, pipelined, or branched conditionally

Claims

1. A query compiler, said compiler comprising:

a processor; and

a memory having program code for configuring the processor to;

receive a SQL query;

determine query fragments needed to perform the SQL query;

determine an execution mode for each of the query fragments, wherein at least one execution mode relates to execution in a hardware accelerator; and

compile query fragments, which will be executed in the hardware accelerator, into respective sets of machine code database instructions, and

grouping the sets of machine code database instructions into tasks that can be executed as a dataflow based on resources of the hardware accelerator.

2. The query compiler of claim 1, wherein the program code further comprises code for determining an execution mode that relates to execution by a host processor coupled to the hardware accelerator.

3. The query compiler of claim 1, wherein the program code further comprises code for removing at least one control flow from execution of the SQL query to enable dataflow execution in the hardware accelerator.

4. The query compiler of claim 3, wherein the program code further comprises code for using Magic-Set based rewrites of the SQL query to enable dataflow execution in the hardware accelerator.

5. The query compiler of claim 3, wherein the program code further comprises code for decorrelating the SQL query to remove loops from execution of the SQL query to enable dataflow execution in the hardware accelerator.

6. The query compiler of claim 1, wherein the program code further comprises code for compiling the SQL query into a form suitable for dataflow execution within a limit of the hardware accelerator resources.

7. The query compiler of claim 6, wherein the program code further comprises code for compiling the SQL query into a dataflow execution having a finite width of data.

8. The query compiler of claim 6, wherein the program code further comprises code for compiling the SQL query into a dataflow execution within a capacity of memory of the hardware accelerator.

9. The query compiler of claim 6, wherein the program code further comprises code for compiling the SQL query into a dataflow execution for a finite number of processing elements in the hardware accelerator.

10. The query compiler of claim 1, wherein the program code further comprises code for translating the SQL query into a dataflow suitable for execution on the hardware accelerator.

11. The query compiler of claim 10, wherein the program code for translating the SQL query further comprises:

code for annotating the SQL query that defines a unique execution; and

code for translating the annotated SQL query into a program of database machine code instructions.

12. The query compiler of claim 10, wherein the program code for translating the SQL query further comprises code for translating the SQL query into the dataflow based on a set of templates.

13. The query compiler of claim 12, wherein the program code further comprises code for identifying at least one pattern for each template that corresponds to a set of database machine code instructions.

14. The query compiler of claim 1, wherein the program code further comprises code for execution of the query fragments directly on compressed data.

30. The method of claim 14, further comprising routing query fragments to a database management system based on the execution mode of the query fragments.

31. The method of claim 14, further comprising compiling the query fragments into to be executed on compressed data.

15. A method for creating query fragments and operations for a query, said method comprising:

receiving a SQL query;

determining query fragments needed to perform the SQL query;

determining an execution mode for each of the query fragments, wherein at least one execution mode relates to execution in a hardware accelerator;

compiling query fragments, which will be executed in the hardware accelerator, into respective sets of machine code database instructions; and

grouping the sets of machine code database instructions into tasks that can be executed as a dataflow based on resources of the hardware accelerator.

16. The method of claim 15, wherein determining an execution mode for each of the query fragments comprises determining an execution mode that relates to execution by a host processor coupled to the hardware accelerator.

17. The method of claim 15, wherein determining query fragments needed to perform the SQL query comprises removing at least one control flow from execution of the SQL query to enable dataflow execution in the hardware accelerator.

18. The method of claim 17, wherein determining query fragments needed to perform the SQL query comprises rewriting the SQL query to enable dataflow execution in the hardware accelerator based on Magic-Sets.

19. The method of claim 17, wherein determining query fragments needed to perform the SQL query comprises decorrelating the SQL query to remove loops from execution of the SQL query to enable dataflow execution in the hardware accelerator.

20. The method of claim 15, wherein determining query fragments needed to perform the SQL query comprises rewriting the SQL query into a form suitable for dataflow execution within a limit of the hardware accelerator resources.

21. The method of claim 20, wherein determining query fragments needed to perform the SQL query comprises rewriting the SQL query into a dataflow execution having a finite width.

22. The method of claim 20, wherein determining query fragments needed to perform the SQL query comprises rewriting the SQL query into a dataflow execution within a capacity of memory of the hardware accelerator.

23. The method of claim 20, wherein determining query fragments needed to perform the SQL query comprises rewriting the SQL query into a dataflow execution for a finite number of processing elements in the hardware accelerator.

24. The method of claim 15, wherein determining query fragments needed to perform the SQL query comprises translating the SQL query into a dataflow suitable for execution on the hardware accelerator.

25. The method of claim 23, wherein translating the SQL query further comprises:

annotating the SQL query that defines a unique execution; and

translating the annotated SQL query into a program of database machine code instructions.

26. The method of claim 23, wherein translating the SQL query further comprises translating the SQL query into the dataflow based on a set of templates.

27. The method of claim 23, wherein translating the SQL query further comprises identifying at least one pattern for each template that corresponds to a set of database machine code instructions.

28. The method of claim 15, further comprising routing query fragments to a host processor based on the execution mode of the query fragments.

29. The method of claim 15, further comprising routing query fragments to software running on a host processor based on the execution mode of the query fragments.