Database calculation using parallel-computation in a directed acyclic graph

• US 9,576,072 B2
• Filed: 02/13/2014
• Issued: 02/21/2017
• Est. Priority Date: 02/13/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Gu, Jing, Zhao, Jie, Shi, Xiangling, Wang, Chengchang, Ru, Yi, Li, Gan, Qu, Jiale, Li, Xu, Zou, Zhonglei
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Bibbee, Jared
• Application Number:
  US14/347,241
• Publication Number:
  US 20150234935A1
• Time in Patent Office: 1,104 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/1858 Parallel file systems, i.e. file systems supporting multiple processors
• CPC Class Codes: G06F 16/212 with details for data modelling support
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence

Abstract

Disclosed herein are technologies related to database calculation that utilizes parallel-computation of tasks in a directed acyclic graph. In accordance with one aspect, dependency of tasks is converted into a directed acyclic graph that topologically orders the tasks into layers of tasks. A database calculation may be performed, wherein the database calculation computes in parallel the tasks in each layer of the layers of tasks.

Claims

1. A method of database calculation, the method comprising:

identifying dependency of tasks;

converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the tasks into layers of tasks; and

performing the database calculation, wherein the database calculation computes in parallel the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed.

2. The method according to claim 1,

wherein the other second set of nodes are the node or nodes that become independent after the parallel-computation of the preceding second set of nodes.

3. The method according to claim 1, wherein the first set of nodes are the node or nodes in outermost vertices of the directed acyclic graph.

4. The method according to claim 1, wherein the root node is the node or nodes at an end of the topological ordering of the directed acyclic graph.

5. The method according to claim 1, wherein the performing the database calculation has a number of loops that is defined by a depth of dependency in the identified dependency of tasks.

6. The method according to claim 1, wherein the identified tasks in a first layer of the layers of tasks are independent tasks.

7. The method according to claim 1, wherein the identified tasks are grouped into nodes in each layer of the layers of tasks.

8. The method according to claim 1, wherein each layer in the layers of tasks is separated by a depth of dependency.

9. The method according to claim 1, wherein the parallel-computation of a first layer in the layers of tasks transforms a second layer to become an independent layer.

10. The method according to claim 1, wherein the directed acyclic graph utilizes an internal parallelism and an external parallelism of the identified tasks.

11. One or more computer-readable media storing processor-executable instructions that when executed cause one or more processors to perform operations that facilitate calculation logic comprising:

identifying dependency of tasks;

converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the identified tasks into layers of tasks; and

performing a database calculation, wherein the database calculation utilizes parallel-computation of the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed.

12. The one or more computer-readable media according to claim 11,

wherein the other second set of nodes are the node or nodes that become independent after the parallel-computation of the preceding second set of nodes.

13. The one or more computer-readable media according to claim 11, wherein the first set of nodes are the node or nodes in an outermost vertices of the directed acyclic graph, wherein the outermost vertices are independent of another node or nodes.

14. The one or more computer-readable media according to claim 11, wherein the root node is the node or nodes at an end of the topological ordering of the directed acyclic graph.

15. The one or more computer-readable media according to claim 11, wherein the performing the database calculation has a number of loops that is defined by a depth of dependency in the identified dependency of tasks.

16. The one or more computer-readable media according to claim 11, wherein the identified tasks in a first layer of the layers of tasks are independent tasks.

17. The one or more computer-readable media according to claim 11, wherein the identified tasks are grouped into nodes in each layer of the layers of tasks.

18. The one or more computer-readable media according to claim 11, wherein each layer in the layers of tasks is separated by a depth of dependency.

19. A system that facilities calculation logic, the system comprising:

one or more processors that are configured to perform;

identifying dependency of tasks;

converting the identified dependency of tasks into a directed acyclic graph in response to the identified dependency of tasks, wherein the directed acyclic graph topologically orders the identified tasks into layers of tasks;

performing a database calculation, wherein the database calculation utilizes parallel-computation of the tasks in each layer of the layers of tasks, wherein the performing the database calculation further comprises selecting a first set of nodes in a topological ordering of the directed acyclic graph, performing parallel-computation of the tasks in the selected first set of nodes, selecting a second set of nodes, performing parallel computation of the tasks in the selected second set of nodes, and determining if the selected second set of nodes is a root node, wherein in response to a finding of the root node, the parallel-computation of the tasks ends, otherwise, the selecting of another second set of nodes is performed; and

an output interface configured to the one or more processors, that provides results of the database calculation.

20. The system according to claim 19, wherein the other second set of nodes are the node or nodes that become independent after the parallel-computation of the preceding second set of nodes.