Method, apparatus, and computer-readable medium for efficiently performing operations on distinct data values

• US 9,218,379 B2
• Filed: 03/15/2013
• Issued: 12/22/2015
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Informatica LLC (Informatica, Inc. (California))
• Original Assignee: Informatica LLC (Informatica, Inc. (California))
• Inventors: Grondin, Richard, Fadeitchev, Evgueni
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US13/835,590
• Publication Number:
  US 20140279853A1
• Time in Patent Office: 1,012 Days
• Field of Search: 707/602, 707/609, 707/803, 707/736, 707/741
• US Class Current: 1/1
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/285 Clustering or classification
• CPC Class Codes: G06F 16/84 Mapping; Conversion

Abstract

An apparatus, computer-readable medium, and computer-implemented method for efficiently performing operations on distinct data values, including storing a tokenized column of data in a table by mapping each unique data value in a corresponding domain to a unique entity ID, and replacing each of the data values in the column with the corresponding entity ID to generate a column of tokenized data containing one or more entity IDs, receiving a query directed to the column of data, the query defining one or more group sets for grouping the data retrieved in response to the query, and generating an entity map vector for each group set, the length of each entity map vector equal to the number of unique entity IDs for the domain, and the value of each bit in the entity map vector indicating the presence or absence of a different unique entity ID in the group set.

Claims

1. A method for efficiently performing operations on distinct data values by one or more computing devices, the method comprising:

storing, by at least one of the one or more computing devices, a tokenized column of data in a table, the tokenized column of data created by mapping each unique data value in a domain of a database to an entity ID, and replacing each of a plurality of data values in a column of data corresponding to the domain with the corresponding entity ID to generate the column of tokenized data containing a plurality of entity IDs;

receiving, by at least one of the one or more computing devices, a query directed to the column of data, the query defining one or more group sets for grouping data retrieved in response to the query, wherein each group set in the one or more group sets corresponds to a unique group of one or more values associated with one or more other domains of the database; and

generating, by at least one of the one or more computing devices, an entity map vector for each group set in the one or more group sets by identifying any entity IDs in the tokenized column of data which are present in any rows of the table which include the unique group of one or more values corresponding to the group set, wherein the length of each entity map vector is equal to the total number of entity IDs in the domain and the value of each bit in each entity map vector indicates the presence or absence of a different entity ID in the corresponding group set.

2. The method of claim 1, wherein the mappings between each of the entity IDs and the unique data values are stored in a look-up dictionary.

3. The method of claim 1, wherein a value of “

1”

for a bit in an entity map vector indicates the presence of an entity ID in the group set, and a value of “

0”

for a bit in an entity map vector indicates the absence of the entity ID in the group set.

4. The method of claim 1, wherein the number of distinct data values in any group set is equal to the sum of the values of each of the bits of the entity map vector corresponding to that group set.

5. The method of claim 1, wherein the one or more group sets comprise at least two group sets, the method further comprising:

receiving, by at least one of the one or more computing devices, a command to aggregate the data from two or more of the group sets into a combined group set; and

performing, by at least one of the one or more computing devices, a Boolean OR operation on the entity map vectors corresponding to the two or more group sets to generate a combined entity map vector.

6. The method of claim 5, wherein the number of distinct data values in the combined group set is equal to the sum of the values of each of the bits of the combined entity map vector.

7. The method of claim 1, wherein the table is partitioned and distributed over a plurality of computing nodes, and wherein the column of data is a first column partition in a set of column partitions, the domain is a first domain partition in a set of domain partitions, the one or more entity IDs are one or more first partition entity IDs, and the entity map vectors are one or more first partition entity map vectors, the method further comprising:

combining, by at least one of the one or more computing devices, the first domain partition with one or more other domain partitions in the set of domain partitions to generate a global domain;

tokenizing, by at least one of the one or more computing devices, one or more of the unique data values in the global domain by mapping each of the one or more unique data values to a global entity ID to generate one or more global entity IDs;

mapping, by at least one of the one or more computing devices, each of the one or more first partition entity IDs to a corresponding global entity ID in the one or more global entity IDs by cross-referencing a common unique data value; and

translating, by at least one of the one or more computing devices, each of the one or more first partition entity map vectors to one or more global entity map vectors based on the mapping of one or more first partition entity IDs to one or more global entity IDs.

8. The method of claim 7, further comprising:

performing, by at least one of the one or more computing devices, a Boolean OR operation on the one or more global entity map vectors corresponding to the first partition and one or more second global entity map vectors corresponding to a second partition to generate one or more combined global entity map vectors.

9. The method of claim 8, wherein the sum of the values of each of the bits of each of the combined global entity map vectors is the total number of distinct elements in a particular group set corresponding to that global entity map vector across the first partition and the second partition.

10. The method of claim 7, wherein the global entity map vectors for each partition are stored in a global data cube, the global data cube including an entity map vector dimension, a group set dimension, and a partition dimension.

11. The method of claim 1, wherein the number of group sets is determined, at least in part, by the number of distinct data values in a second column of data in the table.

12. The method of claim 1, wherein the group sets are defined in reference to one or more second columns of data in the table.

13. The method of claim 1, wherein each entity ID is mapped to each unique data value in chronological order of appearance of the unique data values, such that the first entity ID is mapped to the first unique data value encountered.

14. The method of claim 13, wherein the one or more entity IDs are one or more global entity IDs and the one or more the entity map vectors are one or more preexisting global entity map vectors, the method further comprising:

receiving, by at least one of the one or more computing devices, an update comprising one or more new entity map vectors corresponding to one or more new entity IDs, wherein each of the new entity IDs corresponds to a unique data value;

assigning, by at least one of the one or more computing devices, a new global entity ID to each unique data value that is not already represented in the domain; and

generating, by at least one of the one or more computing devices, one or more global entity map vectors corresponding to the one or more new entity map vectors, wherein the length of each global entity map vector is equal to the total number of global entity IDs, and the value of each bit in each global entity map vector indicates the presence or absence of a different global entity ID in a corresponding group set.

15. The method of claim 14, further comprising:

updating, by at least one of the one or more computing devices, the pre-existing global entity map vectors by appending a number of zeroes to the end of each of the pre-existing global entity map vectors, wherein the number of zeroes is equal to the number of unique data values in the update that were not already represented in the domain.

16. The method of claim 1, wherein each entity ID is mapped to each unique data value in the lexical order of the unique data values, such that the first entity ID is mapped to the unique data value that is first in the lexical order of the unique data values.

17. The method of claim 1, wherein the numerical location of each bit in an entity map vector corresponds to the entity ID whose presence or absence in the group set the bit represents.

18. The method of claim 1, wherein storing a tokenized column of data occurs after receiving a query.

19. The method of claim 1, wherein storing a tokenized column of data occurs before receiving a query.

20. The method of claim 1, wherein the query includes a sum command pertaining to each of the one or more group sets and the method further comprises:

for each of the one or more group sets, summing, by at least one of the one or more computing devices, the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.

21. The method of claim 1, wherein the query includes an average command pertaining to each of the one or more group sets and the method further comprises:

for each of the one or more group sets, computing, by at least one of the one or more computing devices, the average of the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.

22. An apparatus for efficiently performing operations on distinct data values, the apparatus comprising:

one or more processors; and

one or more memories operatively coupled to at least one of the one or more processors and having instructions stored thereon that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to;

store a tokenized column of data in a table, the tokenized column of data created by mapping each unique data value in a domain of a database to an entity ID, and replacing each of a plurality of data values in a column of data corresponding to the domain with the corresponding entity ID to generate the column of tokenized data containing a plurality of entity IDs;

receive a query directed to the column of data, the query defining one or more group sets for grouping data retrieved in response to the query, wherein each group set in the one or more group sets corresponds to a unique group of one or more values associated with one or more other domains of the database; and

generate an entity map vector for each group set in the one or more group sets by identifying any entity IDs in the tokenized column of data which are present in any rows of the table which include the unique group of one or more values corresponding to the group set, wherein the length of each entity map vector is equal to the total number of entity IDs in the domain and the value of each bit in each entity map vector indicates the presence or absence of a different entity ID in the corresponding group set.

23. The apparatus of claim 22, wherein the mappings between each of the entity IDs and the unique data values are stored in a look-up dictionary.

24. The apparatus of claim 22, wherein a value of “

1”

for a bit in an entity map vector indicates the presence of an entity ID in the group set, and a value of “

0”

for a bit in an entity map vector indicates the absence of the entity ID in the group set.

25. The apparatus of claim 22, wherein the number of distinct data values in any group set is equal to the sum of the values of each of the bits of the entity map vector corresponding to that group set.

26. The apparatus of claim 22, wherein the one or more group sets comprise at least two group sets, and the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

receive a command to aggregate the data from two or more of the group sets into a combined group set; and

perform a Boolean OR operation on the entity map vectors corresponding to the two or more group sets to generate a combined entity map vector.

27. The apparatus of claim 26, wherein the number of distinct data values in the combined group set is equal to the sum of the values of each of the bits of the combined entity map vector.

28. The apparatus of claim 22, wherein the table is partitioned and distributed over a plurality of computing nodes, and wherein the column of data is a first column partition in a set of column partitions, the domain is a first domain partition in a set of domain partitions, the one or more entity IDs are one or more first partition entity IDs, and the entity map vectors are one or more first partition entity map vectors, wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

combine the first domain partition with one or more other domain partitions in the set of domain partitions to generate a global domain;

tokenize one or more of the unique data values in the global domain by mapping each of the one or more unique data values to a global entity ID to generate one or more global entity IDs;

map each of the one or more first partition entity IDs to a corresponding global entity ID in the one or more global entity IDs by cross-referencing a common unique data value; and

translate each of the one or more first partition entity map vectors to one or more global entity map vectors based on the mapping of one or more first partition entity IDs to one or more global entity IDs.

29. The apparatus of claim 28, wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

perform a Boolean OR operation on the one or more global entity map vectors corresponding to the first partition and one or more second global entity map vectors corresponding to a second partition to generate one or more combined global entity map vectors.

30. The apparatus of claim 29, wherein the sum of the values of each of the bits of each of the combined global entity map vectors is the total number of distinct elements in a particular group set corresponding to that global entity map vector across the first partition and the second partition.

31. The apparatus of claim 28, wherein the global entity map vectors for each partition are stored in a global data cube, the global data cube including an entity map vector dimension, a group set dimension, and a partition dimension.

32. The apparatus of claim 22, wherein the number of group sets is determined, at least in part, by the number of distinct data values in a second column of data in the table.

33. The apparatus of claim 22, wherein the group sets are defined in reference to one or more second columns of data in the table.

34. The apparatus of claim 22, wherein each entity ID is mapped to each unique data value in chronological order of appearance of the unique data values, such that the first entity ID is mapped to the first unique data value encountered.

35. The apparatus of claim 34, wherein the one or more entity IDs are one or more global entity IDs, the one or more the entity map vectors are one or more preexisting global entity map vectors, and wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

receive an update comprising one or more new entity map vectors corresponding to one or more new entity IDs, wherein each of the new entity IDs corresponds to a unique data value;

assign a new global entity ID to each unique data value that is not already represented in the domain; and

generate one or more global entity map vectors corresponding to the one or more new entity map vectors, wherein the length of each global entity map vector is equal to the total number of global entity IDs, and the value of each bit in each global entity map vector indicates the presence or absence of a different global entity ID in a corresponding group set.

36. The apparatus of claim 35, wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

update the pre-existing global entity map vectors by appending a number of zeroes to the end of each of the pre-existing global entity map vectors, wherein the number of zeroes is equal to the number of unique data values in the update that were not already represented in the domain.

37. The apparatus of claim 22, wherein each entity ID is mapped to each unique data value in the lexical order of the unique data values, such that the first entity ID is mapped to the unique data value that is first in the lexical order of the unique data values.

38. The apparatus of claim 22, wherein the numerical location of each bit in the entity map vector corresponds to an entity ID whose presence or absence in the group set the bit represents.

39. The apparatus of claim 22, wherein the tokenized column of data is stored after receiving a query.

40. The apparatus of claim 22, wherein the tokenized column of data is stored before receiving a query.

41. The apparatus of claim 22, wherein the query includes a sum command pertaining to each of the one or more group sets and wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

for each of the one or more group sets, sum the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.

42. The apparatus of claim 22, wherein the query includes an average command pertaining to each of the one or more group sets and wherein the one or more memories have further instructions stored thereon, that, when executed by at least one of the one or more processors, cause at least one of the one or more processors to:

for each of the one or more group sets, compute the average of the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.

43. At least one non-transitory computer-readable medium storing computer-readable instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

store a tokenized column of data in a table, the tokenized column of data created by mapping each unique data value in a domain of a database to an entity ID, and replacing each of a plurality of data values in a column of data corresponding to the domain with the corresponding entity ID to generate the column of tokenized data containing a plurality of entity IDs;

receive a query directed to the column of data, the query defining one or more group sets for grouping data retrieved in response to the query, wherein each group set in the one or more group sets corresponds to a unique group of one or more values associated with one or more other domains of the database; and

generate an entity map vector for each group set in the one or more group sets by identifying any entity IDs in the tokenized column of data which are present in any rows of the table which include the unique group of one or more values corresponding to the group set, wherein the length of each entity map vector is equal to the total number of entity IDs in the domain and the value of each bit in each entity map vector indicates the presence or absence of a different entity ID in the corresponding group set.

44. The at least one non-transitory computer-readable medium of claim 43, wherein the mappings between each of the entity IDs and the unique data values are stored in a look-up dictionary.

45. The at least one non-transitory computer-readable medium of claim 43, wherein a value of “

1”

for a bit in an entity map vector indicates the presence of an entity ID in the group set, and a value of “

0”

for a bit in an entity map vector indicates the absence of the entity ID in the group set.

46. The at least one non-transitory computer-readable medium of claim 43, wherein the number of distinct data values in any group set is equal to the sum of the values of each of the bits of the bit map vector corresponding to that group set.

47. The at least one non-transitory computer-readable medium of claim 43, wherein the one or more group sets comprise at least two group sets, the at least one non-transitory computer-readable medium further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

receive a command to aggregate the data from two or more of the group sets into a combined group set; and

perform a Boolean OR operation on the entity map vectors corresponding to the two or more group sets to generate a combined entity map vector.

48. The at least one non-transitory computer-readable medium of claim 47, wherein the number of distinct data values in the combined group set is equal to the sum of the values of each of the bits of the combined entity map vector.

49. The at least one non-transitory computer-readable medium of claim 43, wherein the table is partitioned and distributed over a plurality of computing nodes, and wherein the column of data is a first column partition in a set of column partitions, the domain is a first domain partition in a set of domain partitions, the one or more entity IDs are one or more first partition entity IDs, and the entity map vectors are one or more first partition entity map vectors, the at least one non-transitory computer-readable medium further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

combine the first domain partition with one or more other domain partitions in the set of domain partitions to generate a global domain;

tokenize one or more of the unique data values in the global domain by mapping each of the one or more unique data values to a global entity ID to generate one or more global entity IDs;

map each of the one or more first partition entity IDs to a corresponding global entity ID in the one or more global entity IDs by cross-referencing a common unique data value; and

translate each of the one or more first partition entity map vectors to one or more global entity map vectors based on the mapping of one or more first partition entity IDs to one or more global entity IDs.

50. The at least one non-transitory computer-readable medium of claim 49, the at least one non-transitory computer-readable medium further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

perform a Boolean OR operation on the one or more global entity map vectors corresponding to the first partition and one or more second global entity map vectors corresponding to a second partition to generate one or more combined global entity map vectors.

51. The at least one non-transitory computer-readable medium of claim 50, wherein the sum of the values of each of the bits of each of the combined global entity map vectors is the total number of distinct elements in a particular group set corresponding to that global entity map vector across the first partition and the second partition.

52. The at least one non-transitory computer-readable medium of claim 49, wherein the global entity map vectors for each partition are stored in a global data cube, the global data cube including an entity map vector dimension, a group set dimension, and a partition dimension.

53. The at least one non-transitory computer-readable medium of claim 43, wherein the number of group sets is determined, at least in part, by the number of distinct data values in a second column of data in the table.

54. The at least one non-transitory computer-readable medium of claim 43, wherein the group sets are defined in reference to one or more second columns of data in the table.

55. The at least one non-transitory computer-readable medium of claim 43, wherein each entity ID is mapped to each unique data value in chronological order of appearance of the unique data values, such that the first entity ID is mapped to the first unique data value encountered.

56. The at least one non-transitory computer-readable medium of claim 55, wherein the one or more entity IDs are one or more global entity IDs, the one or more the entity map vectors are one or more preexisting global entity map vectors, and the at least one non-transitory computer-readable medium further comprises additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

receive an update comprising one or more new entity map vectors corresponding to one or more new entity IDs, wherein each of the new entity IDs corresponds to a unique data value;

assign a new global entity ID to each unique data value that is not already represented in the domain; and

generate one or more global entity map vectors corresponding to the one or more new entity map vectors, wherein the length of each global entity map vector is equal to the total number of global entity IDs, and the value of each bit in each global entity map vector indicates the presence or absence of a different global entity ID in a corresponding group set.

57. The at least one non-transitory computer-readable medium of claim 56, the at least one non-transitory computer-readable medium further comprising additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

update the pre-existing global entity map vectors by appending a number of zeroes to the end of each of the pre-existing global entity map vectors, wherein the number of zeroes is equal to the number of unique data values in the update that were not already represented in the domain.

58. The at least one non-transitory computer-readable medium of claim 43, wherein each entity ID is mapped to each unique data value in the lexical order of the unique data values, such that the first entity ID is mapped to the unique data value that is first in the lexical order of the unique data values.

59. The at least one non-transitory computer-readable medium of claim 43, wherein the numerical location of each bit in an entity map vector corresponds to the entity ID whose presence or absence in the group set the bit represents.

60. The at least one non-transitory computer-readable medium of claim 43, wherein the tokenized column of data is stored after receiving a query.

61. The at least one non-transitory computer-readable medium of claim 43, wherein the tokenized column of data is stored before receiving a query.

62. The at least one non-transitory computer-readable medium of claim 43, wherein the query includes a sum command pertaining to each of the one or more group sets, and the at least one non-transitory computer-readable medium further comprises additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

for each of the one or more group sets, sum the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.

63. The at least one non-transitory computer-readable medium of claim 43, wherein the query includes an average command pertaining to each of the one or more group sets, and the at least one non-transitory computer-readable medium further comprises additional instructions that, when executed by one or more computing devices, cause at least one of the one or more computing devices to:

for each of the one or more group sets, compute the average of the unique data values corresponding to the entity IDs which are indicated as present in the entity map vector corresponding to that group set.