Allocation performance by query optimization

• US 7,415,454 B2
• Filed: 11/18/2005
• Issued: 08/19/2008
• Est. Priority Date: 11/18/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yan, Peiyuan
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): OWYANG, MICHELLE N
• Application Number:
  US11/282,363
• Publication Number:
  US 20070118501A1
• Time in Patent Office: 1,005 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Allocation performance is enhanced by optimizing queries associated with the allocation. A sparse definition space for a calculation is translated into a dense space for performing the calculation for efficient resource utilization. A calculation expression is symbolically analyzed to determine a relationship between non-zero calculated results and non-zero cells in the input data. From this relationship the regions on which the calculated results are non-zero are obtained by examining the input data. The calculation space is thus reduced to a smaller one. The resulting calculation space is no longer sparse and enables efficient performance of allocation.

Claims

1. A computer-implemented method for improving a performance of an allocation by query optimization, comprising:

receiving a first query that specifies;

a calculation target expression that specifies a set of calculation target cells that consists of all cells in a multidimensional dataset (MDDS) that are associated with a member of each non-calculation dimension of the MDDS that is in a set of members and is associated with a calculation target member in a calculation dimension of the MDDS,

wherein the set of calculation target cells is dividable into;

a set of non-empty calculation target cells that consists of each non-empty cell in the set of calculation target cells; and

a set of empty calculation target cells that consists of each empty cell in the set of calculation target cells;

a calculation expression that specifies that values in the set of calculation target cells are to be calculated from values in a set of calculation source cells that consists of all cells in the MDDS that are associated with a member of each non-calculation dimension of the MDDS that is in the set of members and is associated with a calculation source member in the calculation dimension of the MDDS; and

a first selection expression that specifies a selected set of cells in the MDDS by specifying that the selected set of cells is derivable by finding non-empty cells in the set of calculation target cells;

in response to receiving the first query, symbolically analyzing the calculation expression to identify the calculation source member;

after symbolically analyzing the calculation expression, using the first query and the identified calculation source member to generate a second query that specifies;

the calculation target expression;

the calculation expression; and

a second selection expression that specifies the selected set of cells in the MDDS by specifying that the set of non-empty calculation target cells is derivable by computing a cross join of;

a non-empty cross join of the members in the set of members; and

the calculation target member;

executing the second query to obtain values in the selected set of cells by;

computing the non-empty cross join of the members in the set of members, thereby computing a first set of tuples that identify cells in the MDDS;

wherein each tuple in the first set of tuples specifies a member in the set of members of each of the non-calculation dimensions; and

wherein no cell indicated by a tuple in the first set of tuples is empty;

computing the cross join of the first set of tuples and the calculation target member, thereby computing a second set of tuples that identify all cells in the set of non-empty calculation target cells;

using the calculation expression to calculate values in the set of non-empty calculation target cells, thereby obtaining the values in the selected set of cells; and

after obtaining the values in the selected set of cells, returning the values in the selected set of cells.

2. The computer-implemented method of claim 1, wherein symbolically analyzing the calculation expression includes parsing the calculation expression into an object tree.

3. The computer-implemented method of claim 2, wherein leaves of the object tree correspond to at least one of a constant, a tuple, and a tuple set.

4. The computer-implemented method of claim 2, wherein symbolically analyzing the calculation expression further includes identifying the calculation dimension as a dimension of the MDDS indicated by a leaf of the object tree that corresponds to one of:

a tuple that specifies the dimension and a tuple set that specifies the dimension.

5. The computer-implemented method of claim 4, wherein symbolically analyzing the calculation expression further includes designating dimensions of the MDDS other than the calculation dimension as the non-calculation dimensions.

6. The computer-implemented method of claim 1, wherein using the first query and the identified calculation source member to generate the second query comprises generating the second query such that the second selection expression specifies that the set of non-empty calculation target cells is derivable by computing a cross join of:

a result of invoking a NonEmptyCrossjoin function on the members in the set of members; and

the calculation target member.

7. The computer-implemented method of claim 5, wherein designating dimensions other than the calculation dimension as the non-calculation dimensions includes creating an outline of the non-calculation dimensions and their members in a desired order.

8. The computer-implemented method of claim 1, wherein using the first query and the identified calculation source member to generate the second query comprises generating the second query such that the second query conforms to a Multi-Dimensional eXpression (MDX) standard.

9. A computer-readable storage medium having computer instructions for an allocation in a multi-dimensional business application, the instructions causing a computer that executes the instructions to:

receive a first query that specifies;

a calculation target expression that specifies a set of calculation target cells that consists of all cells in a multidimensional dataset (MDDS) that are associated with a member of each non-calculation dimension of the MDDS that is in a set of members and is associated with a calculation target member in a calculation dimension of the MDDS,

wherein the set of calculation target cells is dividable into;

a set of non-empty calculation target cells that consists of each non-empty cell in the set of calculation target cells; and

a set of empty calculation target cells that consists of each empty cell in the set of calculation target cells;

a calculation expression that specifies that values in the set of calculation target cells are to be calculated from values in a set of calculation source cells that consists of all cells in the MDDS that are associated with a member of each non-calculation dimension of the MDDS that is in the set of members and is associated with a calculation source member in the calculation dimension of the MDDS; and

a first selection expression that specifies a selected set of cells in the MDDS by specifying that the selected set of cells is derivable by finding non-empty cells in the set of calculation target cells;

symbolically analyze the calculation expression to identify the calculation source member in response to receiving the first query;

after symbolically analyzing the calculation expression, use the first query and the identified calculation source member to generate a second query that specifies;

the calculation target expression;

the calculation expression; and

a second selection expression that specifies the selected set of cells in the MDDS by specifying that the set of non-empty calculation target cells is derivable by computing a cross join of;

a non-empty cross join of the members in the set of members; and

the calculation target member;

execute the second query to obtain values of the selected set of cells by;

computing the non-empty cross join of the members in the set of members, thereby computing a first set of tuples that identify cells in the MDDS;

wherein each tuple in the first set of tuples specifies a member in the set of members of each of the non-calculation dimensions; and

wherein no cell indicated by a tuple in the first set of tuples is empty;

computing the cross join of the first set of tuples and the calculation target member, thereby computing a second set of tuples that identify all cells in the set of non-empty calculation target cells;

using the calculation expression to calculate values in the set of non-empty calculation target cells; and

returning the calculated values in the set of non-empty calculation target cells as the values of the selected set of cells.

10. The computer-readable storage medium of claim 9, wherein the instructions that cause the computer to use the first query and the identified calculation source member to generate the second query cause the computer to generate the second query such that the second selection expression specifies that the set of non-empty calculation target cells is derivable by computing a cross join of:

a result of invoking a NonEmptyCrossjoin function on the members in the set of members; and

the identified calculation target member.

11. The computer-readable storage medium of claim 9, wherein the allocation is at least one of:

a planning allocation, a budgeting allocation, and an allocation that forecasts a scenario in the business application.

12. The computer-readable storage medium of claim 9, wherein the set of calculation target cells is a sparse data space, and the selected set of cells form a dense calculation space.

13. The computer-readable storage medium of claim 9, wherein the first query conforms to a Multi-Dimensional eXpression (MDX) standard.

14. The computer-readable storage medium of claim 9, wherein the instructions that cause the computer to symbolically analyze the calculation expression cause the computer to parse the calculation expression into a binary object tree.

15. A system for performing an allocation in a multi-dimensional dataset (MDDS), the system comprising:

a database configured to store a MDDS, wherein the MDDS includes data to be used for the allocation;

a processor configured to;

receive a first query that conforms to a Multi-Dimensional eXpression (MDX) standard, the first query specifying;

a “

WITH”

clause that includes a calculation target expression that specifies a set of calculation target cells that consists of all cells in a MDDS that are associated with a member of each non-calculation dimension of the MDDS that is in a set of members and is associated with a calculation target member in a calculation dimension of the MDDS,

wherein the set of calculation target cells is dividable into;

 

a set of non-empty calculation target cells that consists of each non-empty cell in the set of calculation target cells; and

 

a set of empty calculation target cells that consists of each empty cell in the set of calculation target cells;

an “

AS”

clause that includes a calculation expression that specifies that values in the set of calculation target cells are to be calculated from values in a set of calculation source cells that consists of all cells in the MDDS that are associated with a member of each non-calculation dimension of the MDDS that is in the set of members and is associated with a calculation source member in the calculation dimension of the MDDS; and

a “

SELECT”

clause that includes a first selection expression that specifies a selected set of cells in the MDDS by specifying that the selected set of cells is derivable by finding non-empty cells in the set of calculation target cells;

symbolically analyze the calculation expression to identify the calculation source member in response to receiving the first query;

after symbolically analyzing the calculation expression, use the first query and the identified calculation source member to generate a second query that conforms to the MDX standard, the second query specifying;

a “

WITH”

clause that includes the calculation target expression;

an “

AS”

clause that includes the calculation expression; and

a “

SELECT”

clause that includes a second selection expression that specifies the selected set of cells by specifying that the set of non-empty calculation target cells is derivable by computing a cross join of;

a non-empty cross join of the members in the set of members; and

the calculation target member;

execute the second query by;

computing the non-empty cross join of the members in the set of members, thereby computing a first set of tuples that identify cells in the MDDS,

wherein each tuple in the first set of tuples specifies a member in the set of members of each of the non-calculation dimensions; and

wherein no cell indicated by a tuple in the first set of tuples is empty; and

computing the cross join of the first set of tuples and the calculation target member, thereby computing a second set of tuples that identify all cells in the set of non-empty calculation target cells;

using the calculation expression to calculate values in the set of non-empty calculation target cells; and

returning the calculated values in the set of non-empty calculation target cells.

16. The system of claim 15, wherein the processor is further configured to symbolically analyze the calculation expression by:

parsing the calculation expression into an object tree, identifying the calculation dimension as a dimension of the MDDS indicated by a leaf of the object tree that corresponds to one of;

a tuple and a tuple set, and

designating dimensions of the MDDS other than the calculation dimensions as the non-calculation dimensions.

17. The system of claim 15, wherein the database is further configured to store the calculated values in the set of non-empty calculation target cells.