Compression of tables based on occurrence of values
First Claim
1. A non-transitory computer program product, tangibly embodied in a computer-readable medium, the computer program product being operable to cause data processing apparatus to perform operations comprising:
- generating columns of dictionary-based compression values, the columns of dictionary-based compression values being based on a dictionary of possible values for each column of a column-based database and being structured business data;
sorting the columns such that a first column ordered first in an ordering of the columns has a most-frequently occurring value of the first column occurring more frequently than frequently occurring values of other columns, such that the sorted first column includes, at one end of the first column, instances of the most-frequently occurring value of the first column and the other columns include, at an end of each of the other columns, instances of most-frequently occurring values of the other columns;
generating a bit vector for at least one of the columns, each of the bit vectors representing most-frequently occurring values of a respective column, the generating comprising having each bit of the bit vector represent whether the most-frequently occurring value exists in a respective row of the respective column;
generating a number for each of the columns having an associated bit vector, the number representing an amount of occurrences of the most-frequently occurring value of one end of the column, wherein the most frequently occurring value comprises a plurality of bits;
removing from each of the bit vectors a representation of the most-frequently occurring value of one end of the respective column based on the number associated with the bit vector;
storing the number associated with each of the bit vectors to enable non-volatile memory searches of the data represented by the number associated with each of the bit vectors and each of the bit vectors; and
generating a delta index separate from the columns and configured to store changes to at least one column that occur after the generation and storing of the compression values, wherein the changes include at least one of an addition, a modification, or a deletion to the at least one column, and wherein the stored changes are comprised of dictionary values and value identifiers assigned in an attribute table, the dictionary values being added to the delta index in chronological order to reflect an ordering of changes made to data in the columns over time.
2 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatus, including computer program products, for compression of tables based on occurrence of values. In general, a number representing an amount of occurrences of a frequently occurring value in a group of adjacent rows of a column is generated, a vector representing whether the frequently occurring value exists in a row of the column is generated, and the number and the vector are stored to enable searches of the data represented by the number and the vector. The vector may omit a portion representing the group of adjacent rows. The values may be dictionary-based compression values representing business data such as business objects. The compression may be performed in-memory, in parallel, to improve memory utilization, network bandwidth consumption, and processing performance.
-
Citations
12 Claims
-
1. A non-transitory computer program product, tangibly embodied in a computer-readable medium, the computer program product being operable to cause data processing apparatus to perform operations comprising:
-
generating columns of dictionary-based compression values, the columns of dictionary-based compression values being based on a dictionary of possible values for each column of a column-based database and being structured business data; sorting the columns such that a first column ordered first in an ordering of the columns has a most-frequently occurring value of the first column occurring more frequently than frequently occurring values of other columns, such that the sorted first column includes, at one end of the first column, instances of the most-frequently occurring value of the first column and the other columns include, at an end of each of the other columns, instances of most-frequently occurring values of the other columns; generating a bit vector for at least one of the columns, each of the bit vectors representing most-frequently occurring values of a respective column, the generating comprising having each bit of the bit vector represent whether the most-frequently occurring value exists in a respective row of the respective column; generating a number for each of the columns having an associated bit vector, the number representing an amount of occurrences of the most-frequently occurring value of one end of the column, wherein the most frequently occurring value comprises a plurality of bits; removing from each of the bit vectors a representation of the most-frequently occurring value of one end of the respective column based on the number associated with the bit vector; storing the number associated with each of the bit vectors to enable non-volatile memory searches of the data represented by the number associated with each of the bit vectors and each of the bit vectors; and generating a delta index separate from the columns and configured to store changes to at least one column that occur after the generation and storing of the compression values, wherein the changes include at least one of an addition, a modification, or a deletion to the at least one column, and wherein the stored changes are comprised of dictionary values and value identifiers assigned in an attribute table, the dictionary values being added to the delta index in chronological order to reflect an ordering of changes made to data in the columns over time. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method comprising:
-
generating, by one or more processors, columns of dictionary-based compression values, the columns of dictionary-based compression values being based on a dictionary of possible values for each column of a column-based database and being structured business data; sorting, by the one or more processors, at the one or more processors, the columns such that a first column ordered first in an ordering of the columns has a most-frequently occurring value of the first column occurring more frequently than frequently-occurring values of the other columns, such that the sorted first column includes, at one end of the first column, instances of the most-frequently occurring value of the first column and the other columns include, at an end of each of the other columns, instances of most-frequently occurring values of the other columns; generating, by the one or more processors, a bit vector for at least one of the columns, each of the bit vectors representing most-frequently occurring values of a respective column, the generating comprising having each bit of the vector represent whether the most-frequently occurring value exists in a respective row of the respective column; generating, by the one or more processors, from each of the bit vectors a representation of the most-frequently occurring value of one end of the respective column based on the number associated with the bit vector; storing, by the one or more processors, the number associated with each of the bit vectors to enable non-volatile memory searches of the data represented by the number associated with each of the bit vectors and each of the bit vectors; and generating, by the one or more processors, a delta index separate from the columns and configured to store changes to at least one column that occur after the generation and storing of the compression values, wherein the changes include at least one of an addition, a modification or a deletion to the at least one column, and wherein the stored changes are comprised of dictionary values and value identifiers assigned in an attribute table, the dictionary values being added to the delta index in chronological order to reflect an ordering of changes made to data in the columns over time. - View Dependent Claims (9, 10, 11, 12)
-
Specification