Support bloom filter reading and writing for parquet

[alamb]

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

There are usecases where one wants to search a large amount of parquet data for a relatively small number of rows. For example, if you have distributed tracing data stored as parquet files and want to find the data for a particular trace.

In general, the pattern is "needle in a haystack type query" -- specifically a very selective predicate (passes on only a few rows) on high cardinality (many distinct values) columns.

The rust parquet crate has fairly advanced support for row group pruning, page level indexes, and filter pushdown. These techniques are quite effective when data is sorted and large contiguous ranges of rows can be skipped.

However, doing needle in the haystack queries still often requires substantial amounts of CPU and IO

One challenge is that for typical high cardinality columns such as ids, they often (by design) span the entire range of values of the data type

For example, given the best case when the data is "optimally sorted" by id within a row group, min/max statistics can not help skip row groups or pages. Instead the entire column must be decoded to search for a particular value

┌──────────────────────────┐                WHERE                 
│            id            │       ┌─────── id = 54322342343      
├──────────────────────────┤       │                              
│       00000000000        │       │                              
├──────────────────────────┤       │    Selective predicate on a  
│       00054542543        │       │    high cardinality column   
├──────────────────────────┤       │                              
│           ...            │       │                              
├──────────────────────────┤       │                              
│        ??????????        │◀──────┘                              
├──────────────────────────┤          Can not rule out ranges     
│           ...            │            using min/max values      
├──────────────────────────┤                                      
│       99545435432        │                                      
├──────────────────────────┤                                      
│       99999999999        │                                      
└──────────────────────────┘                                      
                                                                  
  High cardinality column:                                        
    many distinct values                                          
          (sorted)                                                
                                                                  
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐                                           
   min: 00000000000                                               
│  max: 99999999999   │                                           
                                                                  
│       Metadata      │                                           
 ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                                                                     

Describe the solution you'd like
The parquet file format has support for bloom filters: https://github.com/apache/parquet-format/blob/master/BloomFilter.md

A bloom filter is a space efficient structure that allows determining if a value is not in a set quickly. So for a parquet file with bloom filters for id in the metadata, the entire row group can be skipped if the id is not present:

┌──────────────────────────┐                WHERE                
│            id            │      ─ ─ ─ ─ ─ id = 54322342343     
├──────────────────────────┤     │                               
│       00000000000        │           Can quickly check if      
├──────────────────────────┤     │    the value  54322342343     
│       00054542543        │             is not present by       
├──────────────────────────┤     │     consulting the Bloom      
│           ...            │                  Filter             
├──────────────────────────┤     │                               
│        ??????????        │                                     
├──────────────────────────┤     │                               
│           ...            │                                     
├──────────────────────────┤     │                               
│       99545435432        │                                     
├──────────────────────────┤     │                               
│       99999999999        │                                     
└──────────────────────────┘     │                               
  High cardinality column:                                       
    many distinct values         │                               
          (sorted)                                               
                                 │                               
                                                                 
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─      │                               
                           │                                     
│    bloom_filter: ....  ◀ ─ ─ ─ ┘                               
                           │                                     
│  min: 00000000000                                              
   max: 99999999999        │                                     
│                                                                
        Metadata           │                                     
└ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─                                      

I would like the parquet crate to

1. support optionally writing Parquet bloom filters into the metadata
2. support using parquet bloom filters during read to make "needle in the haystack" type queries go quickly by skipping entire row groups if the item is not in the bloom filter.

The format support is here
https://docs.rs/parquet/latest/parquet/format/struct.BloomFilterHeader.html?search=Bloom

Describe alternatives you've considered

Additional context
There is some code for parquet bloom filters in https://github.com/jorgecarleitao/parquet2/tree/main/src/bloom_filter from @jorgecarleitao. I am not sure how mature it is, but perhaps we can use/repurpose some of that

[alamb]

The influxdb_iox project is very interested in this feature and we would love to collaborate with the community to make it happen -- I at least can offer code and design reviews, and blogging about it :)

[aierui]

very cool❤️

[jimexist]

a note to myself for this comment

cc @alamb

[alamb]

(in case other people have missed it, @jimexist has begun work on this feature ❤️ )

[jimexist]

@tustvold and @alamb i might not have the bandwidth to dig into how parquet integrates with arrow so i'd maybe defer this to you or anyone else to follow up in the final piece:

• create an integration test set for parquet crate against pyspark for working with bloom filters #3167

scratch that, i have already done one part in #3176

[alamb]

I think the parquet reading/writing support may be done -- the next phase will be to add support to query engines like DataFusion to take advantage of these filters.

I plan to write up a ticket in DataFusion over the course of the coming week to do so