System and method for automatic dependency analysis for use with a multidimensional database
In accordance with an embodiment, described herein is a system and method for dependency analysis for a calculation script in a multidimensional database computing environment. A multidimensional database cube aggregation can be represented as a lattice of blocks or cube, arranged according to a database outline (e.g., intra-dimensional or member hierarchy). When the multidimensional database system performs computations in parallel for a given calculation script, portions of the cube that can be computed concurrently are identified.
1. A system for providing parallel calculation within a multidimensional database, comprising:
a multidimensional database for storing data in accordance with a plurality of dimensions;
a computing device having a processor executing instructions that cause the processor to:
determine a set of task dimensions for an operation on the multidimensional database, wherein a task dimension comprises a sparse dimension of the multidimensional database whose members define data blocks;
generate a plurality of tasks for the operation based on each member of each task dimension of the set of task dimensions, wherein each task of the plurality of tasks calculates a data block associated with a combination of members from each task dimension;
identify a task dimension, of the set of task dimensions, as a non-participating dimension, wherein each member of the non-participating dimension does not participate in the calculations of the plurality of tasks;
determine a plurality of task levels including a first task level, wherein the first task level includes a first set of tasks of the plurality of tasks determined to have no dependencies on other tasks of the plurality of tasks;
include, in the first task level, a task associated with the non-participating dimension; and
execute, in parallel, the first set of tasks and the task associated with the non-participating dimension.
2. The system of claim 1 , wherein the non-participating dimension is a dimension that specifies a slice of the multidimensional database on which the operation is performed.
3. The system of claim 2 , wherein, within the slice specified based on the non-participating dimension, the operation includes only dense calculations along the non-participating dimension.
4. The system of claim 1 , wherein the plurality of task levels includes a second task level that includes a second set of tasks of the plurality of tasks determined to have dependencies on the first set of tasks.
5. The system of claim 1 , wherein the task associated with the non-participating dimension is associated with a member of the non-participating dimension and a member of the sparse dimension of one of the task dimensions of the set of task dimensions.
6. The system of claim 5 , wherein the member of the non-participating dimension and the member of the sparse dimension of one of the task dimensions of the set of task dimensions are identical members.
7. The system of claim 1 , wherein the non-participating dimensions are identified based on a calculation script for the operation.
8. The system of claim 1 , wherein the processor is further configured to determine a calculation order for the plurality of tasks based on a dependency analysis, wherein the calculation order is determined utilizing a single level dependency group for all members of the non-participating dimension.
9. A method for parallel calculation for a multidimensional database, comprising:
determining, at a computing device, a set of task dimensions for an operation on the multidimensional database wherein a task dimension comprises a sparse dimension of the multidimensional database whose members define data blocks;
generating, by the computing device, a plurality of tasks for the operation based on each member of each task dimension of the set of task dimensions, wherein each task of the plurality of tasks calculates a data block associated with a combination of members from each task dimension;
identifying, by the computing device, a task dimension, of the set of task dimensions, as a non-participating dimension, wherein each member of the non-participating dimension does not participate in the calculations of the plurality of tasks;
determining a plurality of task levels including a first task level, wherein the first task level includes a first set of tasks of the plurality of tasks determined to have no dependencies on other tasks of the plurality of tasks;
including, in the first task level, a task associated with the non-participating dimension; and
executing, in parallel, the first set of tasks and the task associated with the non-participating dimension.
10. The method of claim 9 , wherein the non-participating dimension is a dimension that specifies a slice of the multidimensional database on which the operation is performed, and the operation includes only dense calculations along the non-participating dimension.
11. The method of claim 9 , further comprising creating a second task level of the plurality of task levels that includes a second set of tasks of the plurality of tasks determined to have dependencies on the first set of tasks.
12. The method of claim 9 , wherein the task associated with the non-participating dimension is associated with a member of the non-participating dimension and a member of the sparse dimension of one of the task dimensions of the set of task dimensions.
13. The method of claim 12 , wherein the member of the non-participating dimension and the member of the sparse dimension of one of the task dimensions of the set of task dimensions are identical members.
14. The method of claim 9 , further comprising:
identifying task dimensions as non-participating dimensions based on a calculation script for the operation; and
determining a calculation order for the plurality of tasks based on a dependency analysis, wherein the calculation order is determined utilizing a single level dependency group for all members of the non-participating dimension.
15. A non-transitory computer-readable storage medium having instructions stored thereon, which when read and executed by a computer, cause the computer to:
determine a set of task dimensions for an operation on the multidimensional database, wherein a task dimension comprises a sparse dimension of a multidimensional database whose members define data blocks;
generate a plurality of tasks for the operation based on each member of each task dimension of the set of task dimensions, wherein each task of the plurality of tasks calculates a data block associated with a combination of members from each task dimension;
identify a task dimension, of the set of task dimensions, as a non-participating dimension, wherein each member of the non-participating dimension does not participate in the calculations of the plurality of tasks;
determine a plurality of task levels including a first task level, wherein the first task level includes a first set of tasks of the plurality of tasks determined to have no dependencies on other tasks of the plurality of tasks;
include, in the first task level, a task associated with the non-participating dimension; and
execute, in parallel, the first set of tasks and the task associated with the non-participating dimension.
16. The non-transitory computer-readable storage medium of claim 15 , wherein the non-participating dimension is a dimension that specifies a slice of the multidimensional database on which the operation is performed, and the operation includes only dense calculations along the non-participating dimension.
17. The non-transitory computer-readable storage medium of claim 15 , wherein the instructions further cause the computer to create a second task level of the plurality of task levels that includes a second set of tasks of the plurality of tasks determined to have dependencies on the first set of tasks.
18. The non-transitory computer-readable storage medium of claim 15 , wherein the task associated with the non-participating dimension is associated with a member of the non-participating dimension and a member of the sparse dimension of one of the task dimensions of the set of task dimensions.
19. The non-transitory computer-readable storage medium of claim 15 , wherein the plurality of task levels includes a second task level that includes a second set of tasks of the plurality of tasks determined to have dependencies on the first set of tasks.
20. The non-transitory computer-readable storage medium of claim of claim 15 , wherein the instructions further configure the computer to:
identify the non-participating dimension based on a calculation script for the operation; and
determine a calculation order for the plurality of tasks based on a dependency analysis, wherein the calculation order is determined utilizing a single level dependency group for all members of the non-participating dimension.