Systems and methods for memory optimization interest-driven business intelligence systems

• US 9,934,304 B2
• Filed: 08/18/2015
• Issued: 04/03/2018
• Est. Priority Date: 08/18/2015
• Status: Active Grant

• Current Assignee: Workday Incorporated
• Original Assignee: Workday Incorporated
• Inventors: Beyer, Kevin, Pradhan, Mayank, Sukumar, Vignesh
• Primary Examiner(s): Le, Hung
• Application Number:
  US14/828,836
• Publication Number:
  US 20170053010A1
• Time in Patent Office: 959 Days
• Field of Search: None
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Systems and methods for optimizing memory in an interest-driven business intelligence system in accordance with embodiments of the invention are illustrated. A dictionary for storing values of a dataset may be partitioned in accordance with some embodiments. The partitions of the dictionary may be generated by mapping and reducer processes. The mapping processes receive a value, determine the dimension of the data to which the value belongs, and provides the value to a reducer process that handles the determined dimension. Each reducer process generates partitions of the dictionary for each dimension. The number of values in each partition is determined and compared to a threshold value. Partitions that have a number of values greater than the threshold are stored in a common memory. Partitions smaller than the threshold value can be combined with other partitions such that the cardinality of the combined partition exceeds the threshold value.

Claims

1. A system comprising:

at least two processors; and

a memory storing an application wherein the application directs the at least two processors to;

receive raw data that has a plurality of dimensions;

generate one or more partitions of a dictionary for each dimension of the plurality of dimensions of the raw data, wherein each of the one or more partitions includes an entry for at least one dimension of the plurality of dimensions, wherein the entry at least includes a corresponding dictionary identifier and a corresponding value;

determine a number of entries in each of the one or more partitions;

determine whether the number of entries in a partition of the one or more partitions is greater than a threshold value;

in the event the number of entries for the partition of the one or more partitions is greater than the threshold value, store the partition in a common memory;

in the event the number of entries for the partition of the one or more partitions is not greater than the threshold number;

combine the partition with another partition having the number of entries less than the threshold value into a single partition in which the number of entries is greater than the threshold value; and

store the single partition in the common memory.

2. The system of claim 1, wherein each dimension of the plurality of dimensions is a column of the raw data.

3. The system of claim 2, wherein the application further directs the at least two processors to columnize the raw data.

4. The system of claim 1, wherein:

the application further directs the at least two processors to provide at least one mapping process and at least one reducer process

wherein the at least one mapping process receives a value from a particular dimension of the raw data and provides the value to one of the at least one reducer process, wherein the at least one reducer process is configured to generate the one or more partitions of the dictionary for the particular dimension,

wherein the at least one reducer process generates a particular partition of the dictionary for each dimension of the plurality of dimensions for which the value is received by the at least one reducer.

5. The system of claim 1, wherein the application further directs the at least two processors to replace a value in the raw data with a partition identifier and a dictionary identifier.

6. The system of claim 1, wherein the application further directs the at least two processors to change a partition identifier of a value in response to combining one or more partitions.

7. The system of claim 1, wherein the application further directs the at least two processors to reconcile dictionary identifiers for values in combined partitions in response to combining two or more partitions.

8. The system of claim 1, wherein the application further directs the at least two processors to:

receive a request to obtain a value;

read position in data to obtain a partition identifier and dictionary identifier of the value; and

obtain the value from a partition of the dictionary identified by the partition identifier using the dictionary identifier.

9. The system of claim 8, wherein the obtaining of the value includes loading the partition identified by the partition identifier into the memory associated with one of the at least two processors.

10. The system of claim 1, wherein the application further directs the at least two processors to read a column identifier from the position in the data and to use a dictionary identifier and the column identifier to obtain a value from the partition.

11. The system of claim 1, wherein each of the one or more partitions includes a corresponding partition identifier, wherein the application further directs the at least two processors to retrieve the value from the dictionary at least in part by:

reading a partition identifier associated with one of the one or more partitions;

determining the one of the one or more partitions to be storing the value based on the partition identifier; and

determining the value based on the dictionary identifier stored in one of the entries of the one of the one or more partitions.

12. A method, comprising:

receiving raw data that has a plurality of dimensions;

generating, by a processor, one or more partitions of a dictionary for each dimension of the plurality of dimensions of the raw data, wherein each of the one or more partitions includes an entry for at least one dimension of the plurality of dimensions, wherein entry at least includes a dictionary identifier and a value;

determining, by the processor, a number of entries in each of the one or more partitions;

determining, by the processor whether the number of entries in a partition of the one or more partitions is greater than a threshold value;

in the event the number of entries for the partition of the one or more partitions is greater than the threshold value, storing the partition in a common memory;

in the event the number of entries for the partition of the one or more partitions is not greater than the threshold value;

combining the partition with another partition having the number of entries less than the threshold value into a single partition in which the number of entries is greater than the threshold value; and

storing the single partition in the common memory.

13. The method of claim 12, wherein each dimension of the plurality of dimensions is a column of the raw data.

14. The method of claim 13, further comprising columnizing the raw data.

15. The method of claim 12, further comprising providing at least one mapping process and at least one reducer process, wherein:

the at least one mapping process receives a value from a particular dimension of the raw data and provides the value to one of the at least one reducer process, wherein the at least one reducer process is configured to generate the one or more partitions of the dictionary for the particular dimension,

wherein the at least one reducer process generates a particular partition of the dictionary for each dimension of the plurality of dimensions for which the value is received by the at least one reducer.

16. The method of claim 12, further comprising replacing a value in the raw data with a partition identifier and a dictionary identifier.

17. The method of claim 12, further comprising changing the partition identifier of a value in response to combining one or more partitions.

18. The method of claim 12, further comprising reconciling dictionary identifiers for values in combined partitions in response to combining two or more partitions.

19. The method of claim 12, further comprising:

receiving a request to obtain a value;

reading a position in the data to obtain a partition identifier and dictionary identifier of the value; and

obtaining the value from a partition of the dictionary identified by the partition identifier based upon the dictionary identifier.

20. The method of claim 19, wherein the obtaining of the value includes loading the partition identified by the partition identifier into a memory.

21. A computer program product, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

receiving raw data that has a plurality of dimensions;

generating one or more partitions of a dictionary for each dimension of the plurality of dimensions of the raw data, wherein each of the one or more partitions includes an entry for at least one dimension of the plurality of dimensions, wherein the entry at least includes a dictionary identifier and a value;

determining a number of entries in each of the one or more partitions;

determining whether the number of entries in a partition of the one or more partitions is greater than a threshold value;

in the event the number of entries for the partition of the one or more partitions is greater than the threshold value, storing the partition in a common memory; and

in the event the number of entries for the partition of the one or more partitions is not greater than the threshold value;

combining the partition with another partition having the number of entries less than the threshold value into a single partition in which the number of entries is greater than the threshold value; and

storing the single partition in the common memory.