System and Method for Querying a Distributed Dwarf Cube

• US 20160048560A1
• 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,019,472 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Systems and methods for querying a distributed dwarf cube are disclosed. A query for retrieving data from a distributed dwarf cube is received. The distributed dwarf cube is built of the data. The data comprises cube values. The distributed dwarf cube is built by processing the data to generate indexes for the data. The cube values in one or more dimensions are sorted based on a cardinality of the cube values. The data is partitioned into data blocks to build distributed dwarf cube from each data block based upon the cardinality of the cube values. The distributed dwarf cube comprises one or more ranges defined for the cube values. The one or more ranges of the cube values are checked based upon the query. Using the cube values, a list is created. The list of the cube values is transmitted from the distributed dwarf cube corresponding to the query.

Claims

1. A method for querying a distributed dwarf cube, the method comprising:

receiving a query for retrieving data from a distributed dwarf cube, wherein the distributed dwarf cube is built of the data, wherein the data comprises cube values, wherein the distributed dwarf cube is built by;

processing the data to generate indexes for the data;

sorting the cube values in one or more dimensions based on a cardinality of the cube values, wherein the cube values are sorted 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 to build distributed dwarf cube from each data block based upon the cardinality of the cube values, wherein the distributed dwarf cube comprise one or more ranges defined for the cube values;

checking the one or more ranges of the cube values based upon the query, wherein the one or more ranges comprise complete cube values and non-complete cube values, wherein the non-complete cube values indicate the cube values present at a start or an end of a range of the one or more ranges;

creating a list of the cube values comprising the complete cube values and/or the non-complete cube values; and

transmitting the list of the cube values from the distributed dwarf cube corresponding to the query.

2. The method of claim 1, wherein the distributed dwarf cube is built using a mapreduce technique.

3. The method of claim 1, wherein the building further comprises replicating the distributed dwarf cube on a plurality of nodes.

4. The method of claim 3, wherein the distributed dwarf cube is queried on the plurality of nodes.

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

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

7. The method of claim 5, wherein the generation of 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.

8. The method of claim 1, wherein the querying further comprises:

launching a series of threads; and

retrieving the cube values using the series of threads from the distributed dwarf cube, the retrieving comprising;

adding the cube values to the list when the cube values are complete cube values or merging the cube values to the list when the cube values are non-complete cube values.

9. The method of claim 1, the querying further comprises:

receiving the query to retrieve multiple cube values from two or more dimensions;

combining the two or more dimensions based on the query, wherein the two or more dimensions comprises at least one root dimension comprising one or more non-root dimensions;

searching the two or more dimensions to identify an intersection of the cube values based on the combination; and

retrieving the cube values based upon the searching.

10. A system for querying a distributed dwarf cube, the system comprising:

a processor;

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

receive a query for retrieving data from a distributed dwarf cube, wherein the distributed dwarf cube is built of the data, wherein the data comprises cube values, wherein the distributed dwarf cube is built by;

processing the data to generate indexes for the data;

sorting the cube values in one or more dimensions based on a cardinality of the cube values, wherein the cube values are sorted 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 to build distributed dwarf cube from each data block based upon the cardinality of the cube values, wherein the distributed dwarf cube comprise one or more ranges defined for the cube values;

check the one or more ranges of the cube values based upon the query, wherein the one or more ranges comprise complete cube values and non-complete cube values, wherein the non-complete cube values indicate the cube values present at a start or an end of a range of the one or more ranges;

create a list of the cube values comprising the complete cube values and/or the non-complete cube values; and

transmit the list of the cube values from the distributed dwarf cube corresponding to the query.

11. The system of claim 10, wherein the distributed dwarf cube is built using a mapreduce technique.

12. The system of claim 10, building further comprises replicating the distributed dwarf cube on a plurality of nodes.

13. The system of claim 12, wherein the distributed dwarf cube is queried on the plurality of nodes.

14. The system of claim 10, wherein the one or more dimensions are in a form of a star schema files or a single fact file.

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

16. The system of claim 14, wherein the generation of 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.

17. The system of claim 10, wherein the processor further executes the program instructions to:

launch a series of threads; and

retrieve the cube values using the series of threads from the distributed dwarf cube, the retrieving comprising;

adding the cube values to the list when the cube values are complete cube values or merging the cube values to the list when the cube values are non-complete cube values.

18. The system of claim 10, wherein the processor further executes the program instructions to:

receive the query to retrieve multiple cube values from two or more dimensions;

combine the two or more dimensions based on the query, wherein the two or more dimensions comprises at least one root dimension comprising one or more leaf dimensions;

search the two or more dimensions to identify an intersection of the cube values based on the combination; and

retrieve the cube values based upon the searching.

19. A non-transitory computer readable medium embodying a program executable in a computing device for querying a distributed dwarf cube, the program comprising:

a program code for receiving a query for retrieving data from a distributed dwarf cube, wherein the distributed dwarf cube is built of the data, wherein the data comprises cube values, wherein the distributed dwarf cube is built by;

processing the data to generate indexes for the data;

sorting the cube values in one or more dimensions based on a cardinality of the cube values, wherein the cube values are sorted 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 to build distributed dwarf cube from each data block based upon the cardinality of the cube values, wherein the distributed dwarf cube comprise one or more ranges defined for the cube values;

a program code for checking the one or more ranges of the cube values based upon the query, wherein the one or more ranges comprise complete cube values and non-complete cube values, wherein the non-complete cube values indicate the cube values present at a start or an end of a range of the one or more ranges;

a program code for creating a list of the cube values comprising the complete cube values and/or the non-complete cube values; and

a program code for transmitting the list of the cube values from the distributed dwarf cube corresponding to the query.