Aggregations size estimation in database services
First Claim
Patent Images
1. A method for estimating a size of an aggregation that aggregates detailed data in database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the method comprising:
- determining level cardinalities for the aggregation levels of the aggregation;
identifying dimension groups consisting of dimensions that are related to each other;
determining dimension group cardinalities for the identified dimension groups; and
estimating the size of the aggregation as a function of the level cardinalities, the dimension group cardinalities, and a size of the detailed data.
2 Assignments
0 Petitions
Accused Products
Abstract
A method, apparatus, and software are disclosed for efficient estimation of the size of an aggregation, or summary of data, in a database. This estimate is used in selecting which aggregations are materialized in an OLAP system or relational database. The estimate is based on cardinalities of aggregation levels and of dimension groups consisting of related dimensions, as well as on the size of the underlying detailed data.
62 Citations
45 Claims
-
1. A method for estimating a size of an aggregation that aggregates detailed data in database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the method comprising:
-
determining level cardinalities for the aggregation levels of the aggregation;
identifying dimension groups consisting of dimensions that are related to each other;
determining dimension group cardinalities for the identified dimension groups; and
estimating the size of the aggregation as a function of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
declaring dependent relationships between the dimensions; and
associating dimensions that have either direct or indirect dependent relationships with each other as a dimension group.
-
-
7. The method according to claim 1, wherein the dimension group cardinality for a particular dimension group is determined by submitting an SQL query to the database.
-
8. The method according to claim 1, wherein the dimension group cardinality for a particular dimension group is determined as the level cardinality of a lowest level of a largest dimension of the aggregation.
-
9. The method according to claim 1, further comprising:
-
for each dimension group, calculating a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculating a product S of the values K for all of the dimension groups; and
estimating the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
10. The method according to claim 9, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
11. The method according to claim 9, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
-
12. A method for estimating a size of an aggregation that aggregates detailed data in a database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the method comprising:
-
determining level cardinalities for the aggregation levels of the aggregation;
declaring dependent relationships between the dimensions;
identifying dimension groups consisting of dimensions that have dependent relationships with each other;
for each dimension group, determining a dimension group cardinality as the level cardinality of a lowest level of a largest dimension of the aggregation; and
estimating the size of the aggregation as a function of a product of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (13, 14, 15)
for each dimension group, calculating a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculating a product S of the values K for all of the dimension groups; and
estimating the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
14. The method according to claim 13, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
15. The method according to claim 13, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
-
16. A computer-readable medium for use in estimating a size of an aggregation that aggregates detailed data in a database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the computer-readable medium having computer-executable instructions for:
-
determining level cardinalities for the aggregation levels of the aggregation;
identifying dimension groups consisting of dimensions that are related to each other;
determining dimension group cardinalities for the identified dimension groups; and
estimating the size of the aggregation as a function of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (17, 18, 19, 20, 21, 22, 23, 24, 25, 26)
declaring dependent relationships between the dimensions; and
associating dimensions that have either direct or indirect dependent relationships with each other as a dimension group.
-
-
22. The computer-readable medium, according to claim 16, wherein the dimension group cardinality for a particular dimension group is determined by submitting an SQL query to the database.
-
23. The computer-readable medium, according to claim 16, wherein the dimension group cardinality for a particular dimension group is determined as the level cardinality of a lowest level of a largest dimension of the aggregation.
-
24. The computer-readable medium, according to claim 16, having further computer-executable instructions for:
-
for each dimension group, calculating a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculating a product S of the values K for all of the dimension groups; and
estimating the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
25. The computer-readable medium, according to claim 24, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
26. The computer-readable medium, according to claim 24, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
-
27. A computer-readable medium for use in estimating a size of an aggregation that aggregates detailed data in a database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the computer-readable medium having computer-executable instructions for:
-
determining level cardinalities for the aggregation levels of the aggregation;
declaring dependent relationships between the dimensions;
identifying dimension groups consisting of dimensions that have dependent relationships with each other;
for each dimension group, determining a dimension group cardinality as the level cardinality of a lowest level of a largest dimension of the aggregation; and
estimating the size of the aggregation as a function of a product of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (28, 29, 30)
for each dimension group, calculating a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculating a product S of the values K for all of the dimension groups; and
estimating the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
29. The computer-readable medium, according to claim 28, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
30. The computer-readable medium, according to claim 28, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
-
31. A computer arrangement for use in estimating a size of an aggregation that aggregates detailed data in a database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the computer arrangement configured to:
-
determine level cardinalities for the aggregation levels of the aggregation;
identify dimension groups consisting of dimensions that are related to each other;
determine dimension group cardinalities for the identified dimension groups; and
estimate the size of the aggregation as a function of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (32, 33, 34, 35, 36, 37, 38, 39, 40, 41)
declaring dependent relationships between the dimensions; and
associating dimensions that have either direct or indirect dependent relationships with each other as a dimension group.
-
-
37. The computer arrangement, according to claim 31, wherein the dimension group cardinality for a particular dimension group is determined by submitting an SQL query to the database.
-
38. The computer arrangement, according to claim 31, wherein the dimension group cardinality for a particular dimension group is determined as the level cardinality of a lowest level of a largest dimension of the aggregation.
-
39. The computer arrangement, according to claim 31, further comprising:
-
for each dimension group, calculating a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculating a product S of the values K for all of the dimension groups; and
estimating the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
40. The computer arrangement, according to claim 39, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
41. The computer arrangement, according to claim 39, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
-
42. A computer arrangement for use in estimating a size of an aggregation that aggregates detailed data in a database characterized by a plurality of dimensions, the aggregation being characterized by aggregation levels corresponding to the dimensions of the aggregation, the computer arrangement configured to:
-
determine level cardinalities for the aggregation levels of the aggregation;
declare dependent relationships between the dimensions;
identify dimension groups consisting of dimensions that have dependent relationships with each other;
for each dimension group, determine a dimension group cardinality as the level cardinality of a lowest level of a largest dimension of the aggregation; and
estimate the size of the aggregation as a function of a product of the level cardinalities, the dimension group cardinalities, and a size of the detailed data. - View Dependent Claims (43, 44, 45)
for each dimension group, calculate a product V of the level cardinalities and a value K as a function of the product V and the dimension group cardinality of the dimension group under consideration;
calculate a product S of the values K for all of the dimension groups; and
estimate the size of the aggregation as a function of the product S and the size of the detailed data.
-
-
44. The computer arrangement, according to claim 43, wherein the value K is calculated as C×
- {1−
[1−
(1/V)C]}, wherein C is the dimension group cardinality of the dimension group under consideration.
- {1−
-
45. The computer arrangement, according to claim 43, wherein the size of the aggregation is estimated as F×
- {1−
[1−
(1/S)F]}, wherein F is a number of fact rows of the detailed data.
- {1−
Specification