Methods and systems for run-time scheduling database operations that are executed in hardware

Patent metadata

Field	Value
Publication number	US-9424315-B2
Application number	US-9907608-A
Country	US
Kind code	B2
Filing date	Apr 7, 2008
Priority date	Aug 27, 2007
Publication date	Aug 23, 2016
Grant date	Aug 23, 2016

Abstract

Embodiments of the present invention provide a run-time scheduler that schedules tasks for database queries on one or more execution resources in a dataflow fashion. In some embodiments, the run-time scheduler may comprise a task manager, a memory manager, and hardware resource manager. When a query is received by a host database management system, a query plan is created for that query. The query plan splits a query into various fragments. These fragments are further compiled into a directed acyclic graph of tasks. Unlike conventional scheduling, the dependency arc in the directed acyclic graph is based on page resources. Tasks may comprise machine code that may be executed by hardware to perform portions of the query. These tasks may also be performed in software or relate to I/O.

First claim

What is claimed is:

1. A method for scheduling database tasks for a relational query, said method comprising:
receiving at least a portion of a query execution plan comprising a set of fragments with respective tasks having corresponding database virtual address ranges;
mapping the database virtual address ranges to a set of memory pages;
requesting respective locks for the set of memory pages;
locking memory pages for the selected tasks;
marking one or more of the tasks as being ready for execution based on whether locks have been granted for all of the memory page requests; and
scheduling one or more tasks for execution in a dataflow architecture hardware accelerator coupled to the memory pages when locks have been obtained for all of its memory pages, wherein execution of the one or more tasks is based on execution of machine code instructions formatted for the dataflow architecture hardware accelerator and specifying a dataflow of data through the dataflow architecture hardware accelerator.

2. The method of claim 1 , wherein locking memory pages for the selected tasks comprises granting locks on input memory pages for the selected tasks based on whether data is present in the memory pages.

3. The method of claim 1 , wherein locking memory pages for selected tasks comprises locking memory pages for tasks that are to be executed by a hardware accelerator.

4. The method of claim 1 , wherein locking memory pages for selected tasks comprises locking memory pages for tasks that are to be executed by a software execution module.

5. The method of claim 1 , wherein locking memory pages for selected tasks comprises locking memory pages for tasks that are executed by an input/output execution module.

6. The method of claim 1 , wherein receiving the query execution plan comprises receiving a query plan that splits the query into fragments that are compiled into a dataflow, directed acyclic graph of tasks, and wherein dependencies in the directed acyclic graph are based on page resources.

7. The method of claim 1 , wherein scheduling one or more tasks for execution comprises scheduling tasks based on a weighted priority.

8. The method of claim 1 , wherein scheduling one or more tasks for execution comprises scheduling tasks independent of their received order based on a weighted priority.

9. The method of claim 8 , wherein scheduling one or more tasks for execution comprises scheduling tasks in an order according to their weighted priority, wherein the weighted priorities correspond to tasks that must be immediately executed, tasks that have waited beyond a threshold of time are to be scheduled next, tasks that have waited more than a percentage of its respective query fragment estimated execution time, and a remainder of the tasks.

10. The method of claim 9 , wherein scheduling one or more tasks for execution comprises scheduling the remainder of the tasks based on a scheduling cost.

11. The method of claim 10 , wherein the scheduling cost is based on task affinity, workset page availability, waiting time, and estimated execution time of a task.

12. The method of claim 11 , wherein tasks within the same query fragment are assigned a high task affinity.

13. The method of claim 11 , wherein tasks having task affinity are scheduled close to each other.

14. The method of claim 11 , wherein the scheduling cost is based on a query fragment execution time, workset pages, missing pages, available pages, and settable coefficients, and wherein higher scheduling cost reduces scheduling priority.

15. The method of claim 1 , further comprising:
determining a deadlock exists when there is no running task and no task can be dispatched; and
resolving the deadlock based on rescheduling all uncompleted tasks.

16. A method of overlapping execution of tasks for a query in a dataflow fashion to reduce overall latency of the tasks, said method comprising:
receiving at least a portion of a query execution plan comprising a set of fragments with respective tasks that can be executed in one of a dataflow architecture hardware accelerator, a software execution module, or an input/output execution module having access to a memory having memory pages, wherein execution of the one or more respective tasks is based on execution of machine code instructions formatted for the dataflow architecture hardware accelerator and specifying a dataflow of data through the dataflow architecture hardware accelerator;
locking memory pages for the selected tasks;
filling output from a first task into the locked memory pages; and
starting at least one additional task that consumes the output in one or more of the locked memory pages prior to the locked memory pages being released by the first task.

17. The method of claim 16 , wherein the first task is an input/output task and the at least one additional task that is executed on a hardware accelerator.

18. The method of claim 16 , wherein the first task is an input/output task and the at least one additional task that is executed on a software execution module.

19. The method of claim 16 , wherein the first task is executed on a hardware accelerator and the at least one additional task that is another task executed on a hardware accelerator.

20. The method of claim 16 , wherein the first task is executed on a hardware accelerator and the at least one additional task is a task executed by a software execution module.

21. The method of claim 16 , wherein the first task is executed by a software execution module and the at least one additional task that is another task executed on a hardware accelerator.

22. The method of claim 16 , wherein the first task is executed by a software execution module and the at least one additional task that is another task executed by a software execution module.

23. The method of claim 16 , further comprising:
identifying a mark that indicates a valid region of a partially filled locked memory page; and
controlling execution of the at least one additional task based on the identified mark.

24. The method of claim 23 , wherein the first task updates the mark as it fills the locked memory page.

25. The method of claim 23 , further comprising:
determining pages that are eligible for replacement;
determining whether any of the eligible pages contain data that falls within an ending part of a column; and
selectively marking the pages, which contain data that falls within the ending part of the column.

Assignees

• Chamdani Joseph I
• Beck Alan
• Boinepelli Hareesh
• Crowley Jim
• Krishnamurthy Ravi
• Branscome Jeremy
• Teradata Us Inc

Inventors

• Chamdani Joseph I
• Beck Alan
• Boinepelli Hareesh
• Crowley Jim
• Krishnamurthy Ravi
• Branscome Jeremy

Classifications

• G06F16/24549

  Run-time optimisation · CPC title

• G06F16/2455 Primary

  Query execution · CPC title

• G06F2209/484

  Precedence · CPC title

• G06F9/4881

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F17/30474

  Physics · mapped topic