Building a Distributed Dwarf Cube using Mapreduce Technique

• US 20160048572A1
• Filed: 08/14/2014
• Published: 02/18/2016
• Est. Priority Date: 08/14/2014
• Status: Active Grant

• Current Assignee: Intellicus Technologies Pvt. Ltd. (Intellicus Technologies, Inc.)
• Original Assignee: Intellicus Technologies Pvt. Ltd. (Intellicus Technologies, Inc.)
• Inventors: Khandelwal, Ankit, Ghodawat, Kapil, Rastogi, Sajal, Gupta, Saurabh
• Granted Patent: US 10,877,995 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Systems and methods for building a distributed dwarf cube comprising dwarf cuboid using mapreduce technique are disclosed. Data comprising cube values and a cube definition may be received. The cube definition comprises dimensions defined for the cube values. The data received is processed. The data may be transformed to a format. Based upon the format of the data, indexes may be generated. The cube values in one or more dimensions may be sorted based on a cardinality of the cube values. The cube values may be sorted in an order of highest cardinality to lowest cardinality. The cardinality indicates distinctiveness of the cube values in the one or more dimensions. The data may be partitioned into data blocks. A dwarf cuboid may be built for one or more data blocks based upon the order of the cardinality of the cube values.

Claims

1. A method for building a distributed dwarf cube comprising a plurality of dwarf cuboids using a mapreduce technique, the method comprising:

receiving data comprising cube values and a cube definition, wherein the cube definition comprises dimensions defined for the cube values;

processing the data;

transforming the data to a format;

generating indexes based upon the format of the data;

sorting the cube values in one or more dimensions based on a cardinality of the cube values, and wherein the cube values are sorted with in an order of highest cardinality to lowest cardinality, wherein the cardinality indicates distinctiveness of the cube values in the one or more dimensions;

partitioning the data into data blocks; and

building a dwarf cuboid for one or more data blocks based upon the order of the cardinality of the cube values.

2. The method of claim 1, wherein the one or more dimensions are in a form of a single file fact table or star schema.

3. The method of claim 2, wherein generation the indexes, for the star schema, comprises replacing the cube values comprising primary keys with the indexes in a sorted order.

4. The method of claim 2, wherein the generation the indexes, for the fact table comprises:

creating a tree map for the cube values, wherein the tree map comprises a disk based tree-map and a tree like data structure;

collecting the cube values that are distinct in the tree map;

sorting the cube values that are distinct for the dimension; and

replacing the cube values with the indexes for the dimension.

5. The method of claim 1, further comprising replicating the dwarf cuboid on a query engine, the replication comprising:

requesting a thread to replicate the dwarf cuboid on the query engine, wherein the thread indicates at least one sequential flow of control within a program instruction; and

copying the dwarf cuboid on the query engine based on a replication factor, wherein the replication factor indicates number of the query engines available for the replication.

6. The method of claim 1, further comprising updating the dwarf cuboid, the updating comprising:

receiving an incremental cube values, wherein the incremental cube values indicates at least a record that is added in a dimension in a single file or a fact table; and

adding the incremental cube values in the single file or the fact table of the dimension.

7. The method of claim 1, further comprising aggregating an attribute at a run-time of building the dwarf cuboid, the aggregating comprises:

introducing a primary key at a pseudo level in the dimensions; and

creating a new dwarf cuboid using the primary key.

8. The method of claim 1, further comprising combining two or more dimensions in the dwarf cuboid, wherein the two or more dimensions comprises at least one root dimension comprising one or more non-root dimensions.

9. A system for building a distributed dwarf cube comprising a plurality of dwarf cuboids using a mapreduce technique, the system comprising:

a processor; and

a memory coupled to the processor, wherein the processor executes program instructions stored in the memory, to;

receive data comprising cube values and a cube definition, wherein the cube definition comprises dimensions defined for the cube values;

process the data;

transform the data to a format;

generate indexes based upon the format of the data;

sort the cube values in one or more dimensions based on a cardinality of the cube values, and wherein the cube values are sorted with in an order of highest cardinality to lowest cardinality, wherein the cardinality indicates distinctiveness of the cube values in the one or more dimensions;

partition the data into data blocks; and

build a dwarf cuboid for one or more data blocks based upon the order of the cardinality of the cube values.

10. The system of claim 9, wherein the one or more dimensions are in a form of a single file (star schema) or a fact table.

11. The system of claim 10, wherein generating indexes for the star schema comprises the processor to execute program instructions to generate replace the cube values comprising primary keys with the indexes in a sorted order.

12. The system of claim 10, wherein generating indexes for the star schema comprises the processor to execute the program instructions to:

create a tree map for the cube values, wherein the tree map comprises a disk based tree-map and a tree like data structure;

collect the cube values that are distinct in the tree map;

sort the cube values that are distinct for the dimension; and

replace the cube values with the indexes for the dimension.

13. The system of claim 10, wherein the processor further executes the program instructions to replicate the dwarf cuboid on a query engine, the replication comprising:

requesting a thread to replicate the dwarf cuboid on the query engine, wherein the thread indicates at least one sequential flow of control within a program instruction; and

copying the dwarf cuboid on the query engine based on a replication factor, wherein the replication factor indicates number of the query engines available for the replication.

14. The system of claim 9, wherein the processor further executes the program instructions to update the dwarf cuboid, the updating comprising:

receiving an incremental cube values, wherein the incremental cube values indicates at least a record that is added in a dimension in a single file or a fact table; and

adding the incremental cube values in the single file or the fact table of the dimension.

15. The system of claim 9, wherein the processor further executes the program instructions to aggregate an attribute at a run-time of building the dwarf cuboid, the aggregating comprises:

introducing a primary key at a pseudo level in the dimensions; and

creating a new dwarf cuboid using the primary key.

16. The system of claim 9, wherein the processor further executes the program instructions to combine two or more dimensions in the dwarf cuboid, wherein the two or more dimensions comprises at least one root dimension comprising one or more non-root dimensions.

17. A non-transitory computer readable medium embodying a program executable in a computing device for building a distributed dwarf cube comprising a plurality of dwarf cuboids using a mapreduce technique, the program comprising:

a program code for receiving data comprising cube values and a cube definition, wherein the cube definition comprises dimensions defined for the cube values;

a program code for processing the data;

a program code for transforming the data to a format;

a program code for generating indexes based upon the format of the data;

a program code for sorting the cube values in one or more dimensions based on a cardinality of the cube values, and wherein the cube values are sorted with in an order of highest cardinality to lowest cardinality, wherein the cardinality indicates distinctiveness of the cube values in the one or more dimensions;

a program code for partitioning the data into data blocks; and

a program code for building a dwarf cuboid for one or more data blocks based upon the order of the cardinality of the cube values.