Dwarf cube architecture for reducing storage sizes of multidimensional data

• US 20030126143A1
• Filed: 05/31/2002
• Published: 07/03/2003
• Est. Priority Date: 06/12/2001
• Status: Active Grant

• Current Assignee: University of Maryland
• Original Assignee: University of Maryland
• Inventors: Sismanis, John, Deligiannakis, Antonios, Roussopoulos, Nicholas
• Granted Patent: US 7,133,876 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/957 Multidimensional
• CPC Class Codes: Y10S 707/958 Data cubes
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

The invention relates to data warehouses and the ability to create and maintain data cubes of multi-dimensional data. More specifically, the invention pertains to data cube architectures that permit significant reduction of storage, exhibit very efficient retrieval and provide a very efficient incremental update of the data cubes.

Claims

1. A method for structuring data for storage in either computer main memory or disk memory, which comprises analysing a datacube of said data to identify suffix redundancies in said data, and exploiting any identified suffix redundancies to reduce the size of a datacube needed to store said data.

2. The method of claim 1, wherein said method comprises additionally analysing a datacube of said data to identify prefix redundancies in said data, and exploiting any identified prefix redundancies in an interleaved fashion to reduce the size of the datacube needed to store said data.

3. A method for structuring data for storage in a computer or in a computer-readable storage medium, which comprises the steps of:

(A) sampling the data to estimate the cardinalities and or correlation between dimensions and ordering the dimensions accordingly;

(B) sorting the data according to the dimension ordering acquired by step (A);

(C) assigning one level of a Dwarf structure, moving top-down;

(1) for a full data cube, to each hierarchy level of the dimensions, according to the dimension ordering, and the hierarchy-level ordering within each dimension; and

(2) for a concatenated rollup cube, to each dimension, according to the dimension ordering;

wherein each level consists of multiple rollup representations whose number is equal to the number of hierarchy levels of the dimension;

wherein exactly one rollup representation is assigned to each hierarchy level of the dimension;

wherein the rollup representations are ordered from the one corresponding to the most detailed hierarchy level to the one corresponding to the least detailed hierarchy level; and

(D) inserting data in nodes one tuple at a time.

4. The method of claim 3, wherein in said step (C)(1), for each dimension representing a hierarchy, data is ordered with primary key being the value of the most general level, and proceeding to most specific levels for the case of the full data cube;

wherein each dimension is expanded in the fact table into as many data values, as the number of its hierarchy levels.

5. The method of claim 3, wherein said step (D) comprises the sub-steps of:

(1) creating nodes and cells in a path from the Dwarf structure'"'"'s root to a leaf node;

(2) storing the tuple'"'"'s aggregates in a cell of a leaf node, wherein if the cell already existed, the new values are aggregated with the already stored ones;

(3) for nodes that will receive no more input data, calculating their aggregates values.

6. The method of claim 3, wherein in step (C)(1), for each dimension representing a hierarchy, data is ordered with primary key being the value of the most general level, and proceeding to most specific levels.

7. The method of claim 5, wherein in step (D)(3), said calculation of aggregate values is accomplished by merging previously calculated aggregate values, or by first sorting the corresponding tuples and then processing them accordingly, wherein aggregate values that correspond to different aggregates (group-bys), but which contain identical aggregate values, are identified and their storage is coalesced.

8. The method of claim 3, wherein root-to-leaf paths in the Dwarf structure represent keys for identifying data records.

9. The method of claim 3, wherein each key represents either a value of a hierarchy level of a dimension, or all the values of the dimension'"'"'s hierarchy level.

10. The method of claim 3, wherein the data identified by keys represented by a root-to-leaf path in Dwarf structure is the aggregates of all the data records that match the attribute values of the path.

11. The method of claim 3, wherein group-bys that aggregate values along at least one hierarchy level of any dimension are produced by merging previously calculated aggregate values.

12. The method of claim 3, wherein different sets of group-bys that are calculated from the same input data are identified, said identified sets of different group-bys being suffix redundancies.

13. The method of claim 12, wherein said calculation uses the SuffixCoalesce algorithm.

14. The method of claim 12, wherein said calculation uses the SuffixCoalesceWithSort algorithm.

15. The method of claim 12, wherein said calculation uses the HybridSuffixCoalesce algorithm.

16. The method of claim 11, wherein said calculation uses the SuffixHierarchies algorithm.

17. The method of claim 3, wherein the storage of different group-bys that are calculated from the same input data is coalesced, and their suffix redundancy is therefore eliminated.

18. A data storage device comprising a Dwarf data structure, said structure comprising:

(A) A full data cube, wherein the structure of said full data cube contains as many levels as the sum of all the hierarchy levels of all the dimensions of the stored data;

wherein;

(1) exactly one level of the structure is assigned to each hierarchy level of the dimensions;

(2) nodes at each level contain cells;

wherein each cell of a non-leaf node consists of a key value and a pointer to a node of the next lower level; and

wherein each cell of a leaf-node comprises a key value and the desired aggregate values; and

wherein each node also contains a special ALL cell, the ALL cell corresponding to all the keys of the node;

wherein ALL cells of non-leaf nodes contain pointers to the next lower level, and ALL cells of leaf nodes contain aggregate values;

or

(B) a concatenated rollup datacube, wherein the structure of said concatenated rollup datacube contains as many levels as the number of the dimensions of the stored data; and

wherein;

(1) exactly one level of the structure is assigned to each dimension;

(2) each level consists of multiple “

rollup representations”

, whose number is equal to the number of hierarchy levels of the dimension;

wherein exactly one rollup representation is assigned to each hierarchy level of the dimension;

wherein the rollup representations are ordered from the one corresponding to the most detailed hierarchy level to the one corresponding to the least detailed hierarchy level;

(3) nodes at each level contain cells;

wherein each cell of a non-leaf node consists of a key value and a pointer to a node of the next lower level; and

wherein each cell of a leaf-node comprises a key value and the desired aggregate values; and

wherein each node also contains a special ALL cell, the ALL cell corresponding to all the keys of the node;

wherein ALL cells of nodes in the last rollup representation contain aggregate values of the stored data when they belong to the last level, or a pointer to a node at the next level otherwise; and

wherein ALL cells of nodes not in the last rollup representation contain pointers to a node in the next rollup representation of the current level.

19. The data storage device of claim 18, wherein said data structure is constructed by inserting one tuple at a time, according to the sub-steps of:

(A) creating nodes and cells in a path from the Dwarf structure'"'"'s root to a leaf node;

(B) storing the tuple'"'"'s aggregates in a cell of a leaf node, wherein if the cell already existed, the new values are aggregated with the already stored ones; and

(C) For nodes that will receive no more input data, calculating their aggregates values.

20. The data storage device of claim 19, wherein in step (C), said calculation of aggregate values is accomplished by merging previously calculated aggregate values, or by first sorting the corresponding tuples and then processing them accordingly, wherein aggregate values that correspond to different aggregates (group-bys), but which contain identical aggregate values, are identified and their storage is coalesced.

21. The data storage device of any of claims 19 or 20, wherein said device additionally samples input data to estimate the cardinality of each dimension and orders the dimensions according to decreasing cardinalities.

22. The data storage device of any of claims 19 or 20, wherein said device additionally calculates group-bys that aggregate values across at least one hierarchy level by merging previously calculated aggregate values.

23. The data storage device of any of claims 19 or 20, wherein said device additionally organizes key values of cells within a node in a sorted list, which becomes a B+-tree if the number of keys exceeds a user-specified threshold.

24. The data storage device of claim 23, wherein said device additionally coalesces the store of organized different sets of group-bys and eliminates their suffix redundancy.

25. The data storage device of any of claims 19 or 20, wherein said device additionally identifies different sets of group-bys that can be calculated from the same input data and which contain the same aggregate values.

26. A data storage device comprising:

(A) a Dwarf data structure;

(B) means for sampling the input data to estimate the cardinality of each dimension and ordering the dimensions according to decreasing cardinalities;

(C) means for calculating group-bys that aggregate values across at least one hierarchy level by merging previously calculated aggregate values;

(D) means for organizing key values of cells within a node in a sorted list, which becomes a B+-tree if the number of keys exceeds 2 disk pages;

(E) means for identifying different sets of group-bys that can be calculated from the same input data and which, therefore, contain the same aggregate values;

(F) Means for coalescing the store of different sets of group-bys that are identified in (E), thus eliminating their suffix redundancy.

27. The data storage device of claim 26, wherein said Dwarf data structure is a full datacube that contains as many levels as the sum of all the hierarchy levels of all the dimensions of the stored data, wherein:

(1) exactly one level of the structure is assigned to each hierarchy level of the dimensions;

(2) nodes at each level contain cells;

wherein each cell of a non-leaf node consists of a key value and a pointer to a node of the next lower level; and

wherein each cell of a leaf-node comprises a key value and the desired aggregate values; and

(3) each node also contains a special ALL cell, said ALL cell corresponding to all the keys of the node;

wherein ALL cells of non-leaf nodes contain pointers to the next lower level, and ALL cells of leaf nodes contain aggregate values.

28. The data storage device of claim 26, wherein said Dwarf data structure is a concatenated rollup datacube that contains as many levels as the number of the dimensions of the stored data;

wherein;

(1) exactly one level of the structure is assigned to each dimension;

(2) each level consists of multiple rollup representations, whose number is equal to the number of hierarchy levels of the dimension;

wherein exactly one rollup representation is assigned to each hierarchy level of the dimension;

wherein the rollup representations are ordered from the one corresponding to the most detailed hierarchy level to the one corresponding to the least detailed hierarchy level; and

(3) nodes at each level contain cells;

wherein each cell of a non-leaf node consists of a key value and a pointer to a node of the next lower level; and

wherein each cell of a leaf-node comprises a key value and the desired aggregate values; and

wherein each node also contains a special ALL cell, the ALL cell corresponding to all the keys of the node;

wherein ALL cells of nodes in the last rollup representation contain aggregate values of the stored data when they belong to the last level, or a pointer to a node at the next level otherwise; and

wherein ALL cells of nodes not in the last rollup representation contain pointers to a node in the next rollup representation of the current level.

29. The data storage device of any of claims 27 or 28, wherein said Dwarf data structure is constructed by inserting one tuple at a time.

30. The data storage device of claim 29, wherein said tuple being inserted is inserted according to the sub-steps of:

(A) creating nodes and cells in a path from the Dwarf structure'"'"'s root to a leaf node;

(B) storing the tuple'"'"'s aggregates in a cell of a leaf node, wherein if the cell already existed, the new values are aggregated with the already stored ones; and

(C) For nodes that will receive no more input data, calculating their aggregates values.

31. The data storage device of claim 30, wherein in step (C), said calculation of aggregate values is accomplished by merging previously calculated aggregate values, or by first sorting the corresponding tuples and then processing them accordingly, wherein aggregate values that correspond to different aggregates (group-bys), but which contain identical aggregate values, are identified and their storage is coalesced.

32. The data storage device of claim 26, wherein estimates of the dimensions'"'"' cardinalities are acquired by sampling the input data.

33. The data storage device of claim 26, wherein a dimension ordering is created based on the acquired estimates.

34. The data storage device of claim 26, wherein the input data are sorted according to an acquired dimension ordering.

35. The data storage device of claim 26, wherein the input data is inserted in the Dwarf structure.

36. The data storage device of claim 26, wherein aggregate values are calculated by merging previously calculated values, whenever possible.

37. The data storage device of claim 26, wherein suffix redundancies are identified and their storage is coalesced.

38. The data storage device of claim 26, wherein the calculation of a sub-dwarf of the ALL cell of a node N is accomplished through the use of either the SuffixCoalesce, SuffixCoalesceWithSort, HybridSuffixCoalesce or HierarchiesCoalesce algorithm by estimating whether the sub-dwarfs to be merged are currently stored in the system'"'"'s buffers.

39. The data storage device of claim 26, wherein for each non-leaf node N at level i of a D-level Dwarf, the aggregate value V obtained by following from node N ALL cells until V is reached can be copied to the ALL cell of node N.

40. The data storage device of claim 39, wherein the Dwarf structure is queried, and the aggregate values for any specified group-by are retrieved.

41. The data storage device of claim 26, wherein the Dwarf structure is bulk-updated by using a merge-pack algorithm.

42. The data storage device of claim 26, wherein the Dwarf structure is updated by using an incremental update algorithm.

43. The data storage device of claim 26, wherein the Dwarf structure is updated by using a Dwarf reconstruction algorithm.

44. A method for retrieving the aggregate values that correspond to any specified group-by of stored data, which comprises querying a data storage device comprising said data, said data storage device comprising:

(A) a Dwarf data structure;

(B) means for sampling the input data to estimate the cardinality of each dimension and ordering the dimensions according to decreasing cardinalities;

(C) means for calculating group-bys that aggregate values across at least one hierarchy level by merging previously calculated aggregate values;

(D) means for organizing key values of cells within a node in a sorted list, which becomes a B+-tree if the number of keys exceeds 2 disk pages;

(E) means for identifying different sets of group-bys that can be calculated from the same input data and which, therefore, contain the same aggregate values;

(F) means for coalescing the store of different sets of group-bys that are identified in (E), thus eliminating their suffix redundancy.

45. A method for updating a Dwarf datacube structure comprised of the steps:

(A) creating a Delta-Dwarf for the update data, by;

(1) sampling input data to estimate the cardinality of each dimension and orders the dimensions according to decreasing cardinalities;

(2) calculating group-bys that aggregate values across at least one hierarchy level by merging previously calculated aggregate values;

(3) organizing key values of cells within a node in a sorted list, which becomes a B⁺-tree if the number of keys exceeds 2 disk pages and coalescing the store of organized different sets of group-bys thereby eliminating their suffix redundancy; and

(4) identifying different sets of group-bys that can be calculated from the same input data and which contain the same aggregate values;

and

(B) merging the Delta-Dwarf with the old Dwarf using a merge-packing algorithm.

46. A method for incrementally updating an existing Dwarf datacube structure comprised of the steps:

(1) Ordering the dimensions of the update data according to the dimension ordering of the existing Dwarf datacube;

(2) Traversing the old Dwarf structure top-down to identify nodes that need to be updated due to the existence of update tuples;

wherein a node at a level L of the Dwarf structure needs to be updated if and only if at least one update tuple contains a prefix of length L-1 that is identical to the path followed from the root of the structure to the current node, and wherein each node also contains a special ALL cell, the ALL cell corresponding to all the keys of the node;

(3) Updating any node N at the lowest level of the structure by;

(a) Identifying whether the update tuples that influence the aggregate values stored in N will require the insertion of new key values in N;

(b) Creating a new node to store the results if the process in step (a) shows that new keys need to be inserted to N, otherwise storing the results in N.

(c) For each key in the resulting node, merging the aggregate values existing in N with those of the update tuples.

(d) Calculating the aggregate values for the ALL cell.

(5) Updating any node N at higher levels by a method comprised of;

(a) Recursively propagating the update procedure to the nodes pointed by the cells of N.

(b) Merging the resulting updated dwarfs to calculate the ALL cell of the node.

47. A method for updating an existing Dwarf datacube structure into a new Dwarf datacube structure using a reconstruct algorithm comprised of the steps:

(A) Extracting the tuples of the old Dwarf by performing a query on the most detailed hierarchy level of each dimension, requesting all possible values;

(B) Ordering the data in the update tuples according to the dimension ordering in the existing Dwarf;

(C) Merging the tuples acquired from steps (A) and (B);

(D) Employing said merged tuples to construct a new Dwarf datacube.