Efficient query processing in columnar databases using bloom filters

• US 8,972,337 B1
• Filed: 02/21/2013
• Issued: 03/03/2015
• Est. Priority Date: 02/21/2013
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Gupta, Anurag Windlass
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US13/773,476
• Time in Patent Office: 740 Days
• Field of Search: 707/602
• US Class Current: 707/602
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• 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

A bloom filter is generated for efficient query processing for unsorted data in a column of a columnar database. Bloom filters represented as bitmaps are generated for data blocks storing data for a column of a columnar database table. An indication of a query directed toward the column is received and the bloom filter for each data block is examined to determine which ones of the data blocks do not need to be read in order to service the query for the select data. Data is then read from the data blocks storing data for the column excepting the ones which do not need to be read.

Claims

1. A distributed data warehouse system, comprising:

a plurality of nodes, wherein at least some nodes of the plurality of nodes each comprise;

storage for a columnar database table, wherein said storage comprises a plurality of data blocks;

a bloom filter generator, configured to;

generate a bloom filter for each of one or more data blocks storing data for a column of the columnar database table, wherein each bloom filter is represented as a bitmap, wherein different patterns of set bits in the bitmap indicate data values not stored in the data block;

a read module;

a query engine, configured to;

receive an indication of a query directed to the column of the columnar database table for select data;

evaluate the indication of the query to determine one or more predicate data values that identify the select data;

in response to receiving and evaluating the indication of the query;

analyze the bitmap representing the bloom filter for the one or more predicate data values for each of the one or more data blocks to determine particular ones of the one or more data blocks which do not need to be read in order to service the query for the select data; and

direct the read module to read the one or more data blocks storing data for the column excepting the particular ones of the one or more data blocks which do not need to be read.

2. The system of claim 1, wherein the bloom filter generator is further configured to:

receive additional data to be stored in an additional data block for the column of the columnar database table; and

generate an additional bloom filter for the additional data block.

3. The system of claim 1, wherein to generate the bloom filter for each of the one or more data blocks storing the data for the column of the columnar database table, the bloom filter generator is configured to:

determine a bloom filter size based, at least in part, on a number of data values stored in the data block;

generate the bitmap representing the bloom filter and comprising a plurality of bits corresponding to the bloom filter size; and

populate the bitmap with the different patterns of set bits based, at least in part, on the data stored in the data block to produce the bloom filter, comprising;

apply a plurality of hash functions to each data value stored in the data block; and

set bits in locations of the bitmap corresponding to the output of the plurality of hash functions in order to generate the different patterns of set bits.

4. The system of claim 1, wherein the one or more nodes of the plurality of nodes are one or more compute nodes of a data warehouse cluster, wherein a different node of the plurality of nodes is a leader node of the data warehouse cluster, and wherein the leader node is configured to send one or more queries directed to the column of the columnar database table to the one or more compute nodes.

5. A method, comprising:

performing, by one or more computing devices;

generating a bloom filter for each of one or more data blocks storing data for a column of a columnar database table, wherein each bloom filter is represented as a bitmap, wherein different patterns of set bits in the bitmap indicate data values not stored in the data block;

receiving an indication of a query directed to the column of the columnar database table for select data; and

in response to receiving the indication of the query, examining the bloom filter for each of the one or more data blocks storing data for the column to determine particular ones of the one or more data blocks which do not need to be read in order to service the query for the select data.

6. The method of claim 5, wherein said generating the bloom filter for each of the one or more data blocks storing the data for the column of the columnar database table comprises:

determining a bloom filter size based, at least in part, on a number of possible data values stored in the data block;

generating the bitmap representing the bloom filter and comprising a plurality of bits corresponding to the bloom filter size; and

populating the bitmap with the different patterns of set bits based, at least in part, on the data stored in the data block to produce the bloom filter, wherein said populating comprises;

applying a plurality of hash functions to each data value stored in the data block; and

setting bits in locations of the bitmap corresponding to the output of the plurality of hash functions in order to generate the different patterns of set bits.

7. The method of claim 6, wherein said examining the bloom filter for each of the one or more data blocks comprises:

for a given data block;

for each data value of the select data;

determining bit pattern locations using the plurality of hash functions applied to the data value; and

examining the bit pattern locations in the bitmap representing the bloom filter for the given data block to determine whether the given data block is one of the particular ones which do not need to be read in order to service the query for the select data.

8. The method of claim 5, further comprising in response to receiving the indication of the query, reading the data from the one or more data blocks storing data for the column in order to service the query for the select data excepting the particular ones of the one or more data blocks which do not need to be read.

9. The method of claim 5, wherein the data for the column of the columnar database table is unsorted.

10. The method of claim 5, further comprising for each of the one or more data blocks, storing the bitmap representing the bloom filter in a respective entry in a block metadata data structure that stores information about the one or more data blocks.

11. The method of claim 5, further comprising:

receiving additional data to be stored in one of the one or more data blocks for the column of the columnar database table; and

updating the bitmap representing the bloom filter for the one data block to include the additional data.

12. The method of claim 5, wherein the indication of the query further indicates that the query is a data join query, wherein the plurality of computing devices are part of a larger collection of computing devices implementing a database cluster in a distributed data warehouse system, wherein the plurality of computing devices implement a compute node of the database cluster, wherein another plurality of computing devices that are part of the larger collection of computing devices implement a different compute node storing another columnar database table, and wherein the method further comprises:

performing, by the compute node;

in response to receiving the indication of the query, sending the bitmap representing the bloom filter for each of at least some of the one or more data blocks to the different compute node;

performing, by the different compute node;

receiving the indication of the data join query for the select data;

receiving the bitmap representing the bloom filter for each of the at least some of the one or more data blocks from the compute node; and

in response to receiving the indication of the data join query and receiving the bitmap representing the bloom filter for the at least some of the one or more data blocks, obtaining data from data blocks storing data for the other columnar database table based, at least in part, on the bitmap representing the bloom filter for each of the at least some data blocks in order to service the data join query for the select data.

13. The method of claim 5, further comprising:

detecting an indexing event for the column of the columnar database table; and

in response to detecting the indexing event;

for each of the one or more data blocks, generating a new probabilistic data structure which indicates one or more data values not stored in the data block in place of the bloom filter.

14. The method of claim 13, wherein said detecting an indexing event for the column of the columnar database table comprises:

for each of the one or more data blocks, evaluate the bitmap representing the bloom filter for the data block to determine a selectivity level for the bitmap; and

determine that the selectivity level for at least some of the one or more data blocks is below a selectivity efficiency threshold.

15. The method of claim 13, further comprising:

receiving a plurality of indications of a plurality of different queries directed to the column of the columnar database table; and

wherein said detecting an indexing event for the column of the columnar database table comprises analyzing the plurality of different queries to determine that a number of the queries are range queries and that the number of range queries exceeds a query type threshold.

16. A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices implement:

generating a bloom filter for each of one or more data blocks storing data for a column of a columnar database table, wherein each bloom filter is represented as a bitmap, wherein different patterns of set bits in the bitmap indicate data values not stored in the data block;

for each of the one or more data blocks, storing the bitmap representing the bloom filter in a respective entry for the data block in a block metadata data structure that stores information about the one or more data blocks;

receiving an indication of a query directed to the column of the columnar database table for select data; and

in response to receiving the indication of the query;

analyzing the bloom filter for each of the one or more data blocks storing data for the column to determine particular ones of the one or more data blocks which do not need to be read in order to service the query for the select data; and

reading the one or more data blocks storing data for the column in order to service the query for the select data excepting the particular ones of the one or more data blocks which do not need to be read.

17. The non-transitory, computer-readable storage medium of claim 16, wherein the program instructions when executed by the one or more computing devices further implement:

detecting an indexing event for the column of the columnar database table; and

in response to detecting the indexing event;

for each of the one or more data blocks, generating a new probabilistic data structure which indicates one or more data values not stored in the data block in place of the bloom filter.

18. The non-transitory, computer-readable storage medium of claim 17, wherein, in said examining the bloom filter for each of the one or more data blocks storing data for the column to determine particular ones of the one or more data blocks which do not need to be read in order to service the query for the select data, the program instructions when executed by the one or more computing devices implement:

for a given data block;

for each data value of the select data;

determining bit pattern locations using the plurality of hash functions applied to the data value; and

examining the bit pattern locations in the bitmap representing the bloom filter for the given data block to determine whether the given data block is one of the particular ones which do not need to be read in order to service the query for the select data.

19. The non-transitory, computer-readable storage medium of claim 18, wherein, in said generating the bloom filter for each of the one or more data blocks storing data for the column of the columnar database table, the program instructions when executed by the one or more computing devices implement:

determining a bloom filter size based, at least in part, on a number of possible data values stored in the data block;

generating the bitmap representing the bloom filter and comprising a plurality of bits corresponding to the bloom filter size; and

populating the bitmap representing the bloom filter based, at least in part, on the data values stored in the data block, wherein said populating comprises;

applying a plurality of hash functions to each of the data values stored in the data block; and

setting bits in locations of the bitmap corresponding to output of the plurality of hash functions in order to generate the different patterns of the plurality of bits.

20. The non-transitory, computer-readable storage medium of claim 16, wherein the data for the column of the columnar database table is unsorted.