Rapid and robust predicate evaluation

1. An apparatus for accelerating data access and predicate evaluation, the apparatus comprising:

a computer memory for storing (i) base data as a plurality of base columns, (ii) a plurality of sketched columns, each corresponding to a base column in the base data and having smaller code values compared thereto, and (iii) a compression map for mapping at least one base column to the corresponding sketched column; and

a computer processor configured to:

apply the compression map to a query having a predicate;

determine data on the sketched column that satisfies the predicate; and

evaluate the predicate based at least in part on the determined data on the sketched column without accessing the base column in the base data,

wherein the computer processor is further configured to implement lossy compression for constructing the compression map and the base data comprises categorical data, the computer processor being further configured to encode the categorical data using lossy dictionary encoding.

2. The apparatus of claim 1 , wherein the computer processor is further configured to:

determine at least one value whose appearance in the base column is above a predetermined threshold;

apply the compression map to assign a unique code to the at least one value; and

associate the unique code with the sketched column.

3. The apparatus of claim 2 , wherein the compression map comprises at least one of an array of sorted values or a hash table having the unique code and a hash function.

4. The apparatus of claim 3 , wherein the compression map comprises the array of sorted values when the compression map is order-preserving.

5. The apparatus of claim 3 , wherein the compression map comprises the hash table when the compression map is non-order preserving.

6. The apparatus of claim 1 , wherein the computer processor is further configured to:

construct a plurality of contiguous histogram buckets having an equi-depth histogram that approximates a common data format of the base data; and

create the sketched columns based at least in part on the histogram buckets.

7. The apparatus of claim 6 , wherein the computer processor is further configured to construct the histogram buckets by sampling values uniformly from the base columns, generating a sorted list of the sampled values, and generating endpoints of each histogram bucket based on the sorted list.

8. The apparatus of claim 7 , wherein the computer processor is further configured to (i) determine at least one frequent value based at least in part on a number of the endpoints and values in the base data and (ii) assign a unique code to the at least one frequent value.

9. The apparatus of claim 1 , wherein the computer processor is further configured to:

assign a numerical code to each unique value in the base column; and

determine whether the numerical codes have appearance in the base column above a predetermined threshold, and, if not, collapse at least some of the numerical codes into a single code.

10. The apparatus of claim 1 , wherein the sketched column has a fixed width.

11. A method of accelerating data access to a computer memory and predicate evaluation comprising:

storing, in the computer memory, (i) base data as a plurality of base columns, (ii) a plurality of sketched columns, each corresponding to a base column in the base data and having smaller code values compared thereto, and (iii) a compression map for mapping at least one base column to the corresponding sketched column, wherein the base data comprises categorical data;

implementing lossy compression for constructing the compression map;

encoding the categorical data using lossy dictionary encoding;

applying the compression map to a query having a predicate;

determining data on the sketched column that satisfies the predicate; and

evaluating the predicate based at least in part on the determined data on the sketched column without accessing the base column in the base data.

12. The method of claim 11 , further comprising:

determining at least one value whose appearance in the base column is above a predetermined threshold;

applying the compression map to assign a unique code to the at least one value; and

associating the unique code with the sketched column.

13. The method of claim 12 , wherein the compression map comprises at least one of an array of sorted values or a hash table having the unique code and a hash function.

14. The method of claim 13 , wherein the compression map comprises the array of sorted values when the compression map is order-preserving.

15. The method of claim 13 , wherein the compression map comprises the hash table when the compression map is non-order preserving.

16. The method of claim 11 , further comprising:

constructing a plurality of contiguous histogram buckets having an equi-depth histogram that approximates a common data format of the base data; and

creating the sketched columns based at least in part on the histogram buckets.

17. The method of claim 11 , wherein the histogram buckets is constructed by sampling values uniformly from the base columns, generating a sorted list of the sampled values, and generating endpoints of each histogram bucket based on the sorted list.

18. The method of claim 17 , further comprising:

determining at least one frequent value based at least in part on a number of the endpoints and values in the base data; and

assigning a unique code to the at least one frequent value.

19. The method of claim 11 , further comprising:

assigning a numerical code to each unique value in the base column; and

determining whether the numerical codes have appearance in the base column above a predetermined threshold, and, if not, collapse at least some of the numerical codes into a single code.

20. The method of claim 11 , wherein the sketched column has a fixed width.