METHODS AND SYSTEMS FOR RUN-TIME SCHEDULING DATABASE OPERATIONS THAT ARE EXECUTED IN HARDWARE

• US 20090254774A1
• Filed: 04/07/2008
• Published: 10/08/2009
• Est. Priority Date: 08/27/2007
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: Kickfire, Inc. (Teradata Corporation)
• Inventors: Boinepelli, Hareesh, Crowley, Jim, Beck, Alan, Chamdani, Joseph I., Krishnamurthy, Ravi, Branscome, Jeremy
• Granted Patent: US 9,424,315 B2
• Time in Patent Office: Days
• US Class Current: 714/2
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

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.

Claims

1. A method for scheduling database tasks for a 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 when locks have been obtained for all of its memory pages.

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 hardware accelerator, a software execution module, or an input/output execution module;

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.

26. A system having a plurality of memory resources under a single virtual addressing scheme, said system comprising:

at least one host processor having respective memory;

at least one hardware accelerator having respective memory;

at least one storage subsystem; and

at least one memory manager that addresses the memory of the at least one host processor and the at least one storage subsystem along with the memory of the at least one hardware accelerator under a single virtual address space.

27. The system of claim 26, wherein the at least one hardware accelerator comprises a plurality of hardware accelerators having respective memories that are each addressed under the same single virtual address space.

28. The system of claim 26, wherein the at least one hardware accelerator has a memory about 16 gigabytes.

29. The system of claim 26, wherein the at least one hardware accelerator has a memory in excess of 256 gigabytes.

30. The system of claim 26, wherein the at least one memory manager allocates portions of the single virtual address space based on a size of columns.

31. The system of claim 26, wherein the at least one memory manager maps portions of the single virtual address space to other virtual address spaces of the at least one host processor, the at least one storage subsystem, or the at least one hardware accelerator.

32. The system of claim 31, further comprising an address translation buffer that maps the single virtual address space to at least one of the other virtual address spaces.

33. The system of claim 30, wherein the at least one memory manager calculates a physical address based on translating an address from the single virtual address space into another address from the other virtual address space.

34. The system of claim 30, wherein the at least one memory manager calculates a physical address based on translating an address from the single virtual address 64-bit space into another address from another virtual address 50-bit space.

35. The system of claim 30, wherein the at least one memory manager defragments the single virtual address space based on updating a mapping of the single virtual address space to the other virtual address spaces.

36. The system of claim 30, wherein the at least one memory manager defragments the single virtual address space without moving data in the memory of the at least one host processor, the at least one storage subsystem, or the memory of the at least one hardware accelerator.

37. The system of claim 30, wherein the at least one memory manager allocates additional contiguous portions of the single virtual address space based on a request.

38. The system of claim 32, wherein the at least one memory manager remaps the additional contiguous portions of the single virtual address space into at least one of the other virtual address spaces.

39. A method of ranking columns of a column-store database based on their usage to assist in query processing, said method comprising:

identifying columns having at least one of a predetermined characteristic;

ranking the identified columns based on the at least one predetermined characteristic;

determining usage of all the columns in the column-store database; and

updating rankings of all the columns based on their usage.

40. The method of claim 39, wherein identifying the columns having at least one of a predetermined characteristic comprises identifying the columns that are index columns.

41. The method of claim 39, wherein identifying the columns having at least one of a predetermined characteristic comprises identifying the columns that contain floating point numerical data.

42. The method of claim 39, wherein identifying the columns having at least one of a predetermined characteristic comprises identifying the columns having a size above a threshold.

43. The method of claim 39, wherein identifying the columns having at least one of a predetermined characteristic comprises identifying the columns that contain keys.

44. The method of claim 39, wherein identifying the columns having at least one of a predetermined characteristic comprises identifying the columns that contain date information.

45. The method of claim 39, wherein ranking the identified columns comprises ranking the identified columns based on the number of predetermined characteristics of the columns.

46. The method of claim 39, wherein ranking the identified columns comprises ranking the identified columns based on a weighted sum of predetermined characteristics.

47. The method of claim 39, wherein determining usage of all the columns in the column-store database comprises updating the usage based on when the column is accessed by a task of query.

48. The method of claim 39, further comprising selectively loading columns into a hardware accelerator based on their ranking.

49. The method of claim 39, further comprising speculatively prefetching columns into a hardware accelerator based on their ranking.

50. The method of claim 49, wherein speculatively prefetching columns into the hardware accelerator based on unused input/output capacity of the hardware accelerator.

51. The method of claim 49, wherein speculatively prefetching columns into the hardware accelerator based on free space in the hardware accelerator'"'"'s memory.

52. The method of claim 39, further comprising selectively discarding columns from a hardware accelerator based on their ranking.

53. A method of handling a disruption in dataflow execution of tasks by a hardware accelerator for a database system, said method comprising:

determining a disruption that occurred in a dataflow execution of tasks by the hardware accelerator;

identifying a cause of the disruption; and

resolving the disruption based on its cause.

54. The method of claim 53, wherein identifying the cause of the disruption comprises determining whether an overflow in a buffer of a memory of the hardware accelerator has occurred.

55. The method of claim 54, wherein handling the disruption comprises extending the virtual address and allocating additional physical address space in the memory of the hardware accelerator to accommodate the overflow in the buffer.

56. The method of claim 53, wherein identifying the cause of the disruption comprises identifying a miss by a translation buffer in the hardware accelerator.

57. The method of claim 53, wherein identifying the cause of the disruption comprises identifying a task that exceeds a processing element capability of the hardware accelerator.

58. The method of claim 57, wherein identifying the task that exceeds the processing element capability comprises identifying an arithmetic overflow.

59. The method of claim 54, wherein identifying the cause of the disruption comprises identifying an uncorrectable error in the buffer of the memory of the hardware accelerator.

60. The method of claim 54, wherein identifying the cause of the disruption comprises identifying an uncorrectable physical link error in the hardware accelerator.

61. The method of claim 57, wherein resolving the disruption comprises re-execution of the disrupted task by a software processing module.

62. The method of claim 53, wherein identifying the cause of the disruption comprises identifying a conditional task included in the dataflow execution of tasks.

63. The method of claim 62, wherein resolving the disruption comprises:

determining a state of the conditional task; and

requesting a new plan for continuing the dataflow execution of the query based on the state of the conditional task.

67. The method of claim 63, wherein predicting the memory page to be processed comprises predicting the memory page based on a database schema.

68. The method of claim 67, wherein predicting the memory page to be processed comprises predicting the memory page based on a data type specified in the database schema.

69. The method of claim 63, wherein determining when an input/output execution module has available capacity comprises determining when a hardware execution module has available input capacity.

70. The method of claim 63, wherein determining when an input/output execution module has available capacity comprises determining when the input/output execution module is not processing another prefetch.

71. The method of claim 63, wherein prefetching at least a portion of the memory page comprises prefetching at least one memory page of a column.

72. The method of claim 63, wherein prefetching at least a portion of the memory page comprises:

determining a minimum useful part of the memory page; and

requesting prefetch of the minimum useful part of the memory page.

73. The method of claim 71, wherein determining the minimum useful part of the memory page is based on avoiding collision with a prefetch of another memory page.

74. The method of claim 71, wherein determining the minimum useful part of the memory page is based on avoiding collision with a prefetch having a higher priority for another memory page.

75. The method of claim 71, wherein prefetching at least a portion of the memory page comprises requesting prefetch of subsequent minimum useful parts of the memory page.

64. A method of prefetching memory pages for a task of a query, said method comprising:

predicting a memory page to be processed for a future task;

determining when an input/output execution module has available capacity;

prefetching at least a portion of the memory page based on the available capacity of the input/output execution module.

65. The method of claim 64, wherein predicting the memory page to be processed comprises predicting the memory page based on a column ranking.

66. The method of claim 64, wherein predicting the memory page to be processed comprises predicting the memory page based on a previous usage pattern.