Reducing data I/O using in-memory data structures

1. A method comprising:

receiving a query for a target data set managed by a database management system, the query specifying at least one predicate for at least one column of the target data set, said at least one predicate comprising at least one filtering value to be compared with row values of the at least one column of the target data set;

prior to accessing a plurality of data block sets that store the target data set in persistent storage, identifying a plurality of in-memory summaries, each in-memory summary corresponding to a corresponding data block set from the plurality of data block sets, said each in-memory summary comprising one or more in-memory data structures, each in-memory data structure of said one or more in-memory data structures representing values stored in the corresponding data block set in a corresponding column of the target data set;

wherein a particular in-memory data structure of said plurality of in-memory summaries represents values stored in the at least one column of a particular data block set of said plurality of data block sets;

determining whether the particular data block set can possibly contain the at least one filtering value in the at least one column by at least determining, based on the particular in-memory data structure, a set of membership of said at least one filtering value in the values stored in said at least one column of said particular data block set;

based on the determining that the particular data block set cannot possibly contain the at least one filtering value in the at least one column, skipping a retrieval of the particular data block set from the persistent storage in evaluating the query; and

based on the determining the particular data block set can possibly contain the at least one filtering value in the at least one column, retrieving the corresponding data block set from the persistent storage for evaluating the query;

wherein the method is executed by one or more computing devices.

2. The method of claim 1 , further comprising:

prior to receiving the query, generating the plurality of the in-memory summaries for the plurality of data block sets, the plurality of data block sets being selected for generating the plurality of the in-memory summaries based on a skip rate.

3. The method of claim 1 , further comprising:

prior to receiving the query, generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set;

wherein the at least one column is selected from a plurality of columns in the particular data block set based on statistics of each column of the plurality of columns;

wherein the statistics includes cardinality of said each column, cardinality of said each column only for values stored in the particular data block set, or frequency of usage of said each column in predicates of one or more queries received by the database management system.

4. The method of claim 1 , further comprising:

based on cardinality of values of the at least one column in the particular data block set or cardinality of the at least one column, selecting to generate a dictionary data structure or a dense bloom filter data structure as the particular in-memory data structure; and

generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set.

5. The method of claim 4 , wherein generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set comprises generating a respective hash value by applying a hash algorithm to each corresponding value, of the at least one column in the particular data block set, stored in the particular data block set for the at least one column and storing at least a portion of the corresponding hash value in the dictionary data structure as a representation of said each corresponding value of the at least one column in the particular data block set.

6. The method of claim 4 , wherein generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set comprises:

generating a respective hash value by applying a hash algorithm of cryptographic strength on each corresponding value stored in the particular data block set for the at least one column;

identifying at least two sub-hash values of the respective hash value, wherein each sub-hash value of the at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values;

based on said each sub-hash value, determining one or more bit addresses of a bit vector of the dense bloom filter data structure;

setting one or more bits corresponding to the determined one or more bit addresses in the bit vector of the dense bloom filter data structure.

7. The method of claim 1 ,

wherein the particular in-memory data structure is a dictionary data structure;

the method further comprising:

generating a hash value for the at least one filtering value by applying a hash algorithm to the at least one filtering value; and

comparing the hash value of the at least one filtering value to one or more hash values stored in the dictionary data structure;

if the hash value for the at least one filtering value exists in the dictionary data structure, then determining the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set;

if the hash value for the at least one filtering value does not exist in the dictionary data structure, then determining the particular data block set cannot possibly contain the at least one filtering value in the at least one column of the target data set.

8. The method of claim 7 , wherein a particular type of the hash algorithm and length of output hash values of the hash algorithms depends on metadata associated with said each in-memory summary.

9. The method of claim 1 , wherein the particular in-memory data structure is a dense bloom filter data structure; and

the method further comprising:

generating a hash value for the at least one filtering value by applying a hash algorithm of cryptographic strength to the at least one filtering value;

identifying at least two sub-hash values of the hash value of the at least one filtering value, wherein each sub-hash value of the at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values;

using said each sub-hash value, determining for said each sub hash value, one or more bit addresses of a bit vector of the dense bloom data structure;

if the one or more bit addresses of the bit vector for said each sub-hash value is set, then determining the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set;

if the one or more bit addresses of the bit vector for said each sub-hash value is not set, then determining the particular data block set cannot possibly contain the at least one filtering value in the at least one column of the target data set.

10. The method of claim 9 , wherein a particular type of the hash algorithm and length of output hash values of the hash algorithms depends on metadata associated with said each in-memory summary.

11. The method of claim 1 , further comprising:

determining whether the particular in-memory data structure is a dense bloom filter data structure containing a bit vector or a dictionary data structure containing hash values;

based on determining whether the particular in-memory data structure is a dense bloom filter data structure or a dictionary data structure, and to determine whether the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set, determining whether to generate a hash value that contains at least two sub-hash value from the at least one filtering value by applying a hash algorithm of cryptographic strength to the at least one filtering value, wherein each sub-hash value of at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values.

12. The method of claim 11 , wherein determining whether the particular in-memory data structure is a dense bloom filter data structure or a dictionary data structure is based on metadata associated with the particular in-memory data structure.

13. One or more non-transitory computer-readable media storing instructions, wherein the instructions include:

instructions which, when executed by one or more hardware processors, cause receiving a query for a target data set managed by a database management system, the query specifying at least one predicate for at least one column of the target data set, said at least one predicate comprising at least one filtering value to be compared with row values of the at least one column of the target data set;

instructions which, when executed by one or more hardware processors, cause prior to accessing a plurality of data block sets that store the target data set in persistent storage, identifying a plurality of in-memory summaries, each in-memory summary corresponding to a corresponding data block set from the plurality of data block sets, said each in-memory summary comprising one or more in-memory data structures, each in-memory data structure of said one or more in-memory data structures representing values stored in the corresponding data block set in a corresponding column of the target data set;

wherein a particular in-memory data structure of said plurality of in-memory summaries represents values stored in the at least one column of a particular data block set of said plurality of data block sets;

instructions which, when executed by one or more hardware processors, cause determining whether the particular data block set can possibly contain the at least one filtering value in the at least one column by at least determining, based on the particular in-memory data structure, a set of membership of said at least one filtering value in the values stored in said at least one column of said particular data block set;

instructions which, when executed by one or more hardware processors, cause, based on the determining that the particular data block set cannot possibly contain the at least one filtering value in the at least one column, skipping a retrieval of the particular data block set from the persistent storage in evaluating the query; and

instructions which, when executed by one or more hardware processors, cause, based on the determining the particular data block set can possibly contain the at least one filtering value in the at least one column, retrieving the corresponding data block set from the persistent storage for evaluating the query.

14. The one or more non-transitory computer-readable media of claim 13 , wherein the instructions further include:

instructions which, when executed by one or more hardware processors, cause, prior to receiving the query, generating the plurality of the in-memory summaries for the plurality of data block sets, the plurality of data block sets being selected for generating the plurality of the in-memory summaries based on a skip rate.

15. The one or more non-transitory computer-readable media of claim 13 , wherein the instructions include:

instructions which, when executed by one or more hardware processors, cause, prior to receiving the query, generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set;

wherein the at least one column is selected from a plurality of columns in the particular data block set based on statistics of each column of the plurality of columns;

wherein the statistics includes cardinality of said each column, cardinality of said each column only for values stored in the particular data block set, or frequency of usage of said each column in predicates of one or more queries received by the database management system.

16. The one or more non-transitory computer-readable media of claim 13 , wherein the instructions further include:

instructions which, when executed by one or more hardware processors, cause, based on cardinality of values of the at least one column in the particular data block set or cardinality of the at least one column, selecting to generate a dictionary data structure or a dense bloom filter data structure as the particular in-memory data structure; and

instructions which, when executed by one or more hardware processors, cause, generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set.

17. The one or more non-transitory computer-readable media of claim 16 , wherein the instructions, for generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set, further include instructions which, when executed by one or more hardware processors, cause generating a respective hash value by applying a hash algorithm to each corresponding value, of the at least one column in the particular data block set, stored in the particular data block set for the at least one column and storing at least a portion of the corresponding hash value in the dictionary data structure as a representation of said each corresponding value of the at least one column in the particular data block set.

18. The one or more non-transitory computer-readable media of claim 16 , wherein the instructions, for generating the particular in-memory data structure for representing values of the at least one column stored in the particular data block set, further include:

instructions which, when executed by one or more hardware processors, cause generating a respective hash value by applying a hash algorithm of cryptographic strength on each corresponding value stored in the particular data block set for the at least one column;

instructions which, when executed by one or more hardware processors, cause identifying at least two sub-hash values of the respective hash value, wherein each sub-hash value of the at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values;

instructions which, when executed by one or more hardware processors, cause, based on said each sub-hash value, determining one or more bit addresses of a bit vector of the dense bloom filter data structure;

instructions which, when executed by one or more hardware processors, cause, setting one or more bits corresponding to the determined one or more bit addresses in the bit vector of the dense bloom filter data structure.

19. The one or more non-transitory computer-readable media of claim 13 ,

wherein the particular in-memory data structure is a dictionary data structure;

the instructions further include:

instructions which, when executed by one or more hardware processors, cause generating a hash value for the at least one filtering value by applying a hash algorithm to the at least one filtering value; and

instructions which, when executed by one or more hardware processors, cause comparing the hash value of the at least one filtering value to one or more hash values stored in the dictionary data structure;

instructions which, when executed by one or more hardware processors, cause, if the hash value for the at least one filtering value exists in the dictionary data structure, then determining the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set;

instructions which, when executed by one or more hardware processors, cause, if the hash value for the at least one filtering value does not exist in the dictionary data structure, then determining the particular data block set cannot possibly contain the at least one filtering value in the at least one column of the target data set.

20. The one or more non-transitory computer-readable media of claim 19 , wherein a particular type of the hash algorithm and length of output hash values of the hash algorithms depends on metadata associated with said each in-memory summary.

21. The one or more non-transitory computer-readable media of claim 13 , wherein the particular in-memory data structure is a dense bloom filter data structure; and

the instructions further include:

instructions which, when executed by one or more hardware processors, cause generating a hash value for the at least one filtering value by applying a hash algorithm of cryptographic strength to the at least one filtering value;

instructions which, when executed by one or more hardware processors, cause identifying at least two sub-hash values of the hash value of the at least one filtering value, wherein each sub-hash value of the at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values;

instructions which, when executed by one or more hardware processors, cause, using said each sub-hash value, determining for said each sub hash value, one or more bit addresses of a bit vector of the dense bloom data structure;

instructions which, when executed by one or more hardware processors, cause, if the one or more bit addresses of the bit vector for said each sub-hash value is set, then determining the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set;

instructions which, when executed by one or more hardware processors, cause, if the one or more bit addresses of the bit vector for said each sub-hash value is not set, then determining the particular data block set cannot possibly contain the at least one filtering value in the at least one column of the target data set.

22. The one or more non-transitory computer-readable media of claim 21 , wherein a particular type of the hash algorithm and length of output hash values of the hash algorithms depends on metadata associated with said each in-memory summary.

23. The one or more non-transitory computer-readable media of claim 13 , wherein the instructions further include:

instructions which, when executed by one or more hardware processors, cause determining whether the particular in-memory data structure is a dense bloom filter data structure containing a bit vector or a dictionary data structure containing hash values;

instructions which, when executed by one or more hardware processors, cause, based on determining whether the particular in-memory data structure is a dense bloom filter data structure or a dictionary data structure, and to determine whether the particular data block set can possibly contain the at least one filtering value in the at least one column of the target data set, determining whether to generate a hash value that contains at least two sub-hash value from the at least one filtering value by applying a hash algorithm of cryptographic strength to the at least one filtering value, wherein each sub-hash value of at least two sub-hash values is statistically independent from other sub-hash value of the at least two sub-hash values.

24. The one or more non-transitory computer-readable media of claim 23 , wherein the instructions further include, instructions which, when executed by one or more hardware processors, cause determining whether the particular in-memory data structure is a dense bloom filter data structure or a dictionary data structure based on metadata associated with the particular in-memory data structure.