You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@parquet.apache.org by "pitrou (via GitHub)" <gi...@apache.org> on 2026/01/14 11:10:44 UTC

[I] Bloom filter size table does not match implementations [parquet-format]

pitrou opened a new issue, #547:
URL: https://github.com/apache/parquet-format/issues/547

   ### Describe the bug, including details regarding any error messages, version, and platform.
   
   The bits/key values in [this table](https://github.com/apache/parquet-format/blob/master/BloomFilter.md#sizing-an-sbbf) do not seem to match results given by the formula used in the [Parquet C++](https://github.com/apache/arrow/blob/a1ec5a9a1decb163eef26deecf60a6903f9aa125/cpp/src/parquet/bloom_filter.h#L237) and [Parquet Java](https://github.com/apache/parquet-java/blob/aa41aa121ff29e360273675edc899ba1c2640047/parquet-column/src/main/java/org/apache/parquet/column/values/bloomfilter/BlockSplitBloomFilter.java#L286) implementations.
   
   Using that formula (the same in both implementations) I get this table:
   
   | Bits of space per `insert` | False positive probability |
   | -------------------------- | -------------------------- |
   |                        5.8 | 10 %                       |
   |                        9.7 |  1 %                       |
   |                       14.6 |  0.1 %                     |
   |                       21   |  0.01 %                    |
   |                       29.6  |  0.001 %                   |
   
   In Python:
   ```python
   >>> fpp = 0.1 ; 8/math.log(1/(1 - fpp**0.125))
   5.7725418439029506
   >>> fpp = 0.01 ; 8/math.log(1/(1 - fpp**0.125))
   9.681526738735679
   >>> fpp = 0.001 ; 8/math.log(1/(1 - fpp**0.125))
   14.607697478479535
   >>> fpp = 0.0001 ; 8/math.log(1/(1 - fpp**0.125))
   21.045409233894773
   >>> fpp = 0.00001 ; 8/math.log(1/(1 - fpp**0.125))
   29.555488704606017
   ```
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3749051999

   Am I misunderstanding / miscalculating something here?
   
   @wgtmac @rdblue @chenjunjiedada @gszadovszky @alamb 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3750168637

   Also @mapleFU 


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3767386805

   > Thank you for pinging me. A correct implementation of the size requirement and false positive probability can be found at https://github.com/jbapple/libfilter/blob/master/c/lib/util.c. It is Apache 2.0 licensed and can be used here.
   
   Am I right in understanding that a single call to `libfilter_block_bytes_needed_detail` will make tens of thousands of `lgamma` and `log` computations?
   https://github.com/apache/parquet-format/issues/547#issuecomment-3765386436
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "jimexist (via GitHub)" <gi...@apache.org>.
jimexist commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3765386436

   i have updated my pull request to reflect @jbapple 's code to estimate the fpp and shown that the adjustment is indeed in some cases necessary


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "jimexist (via GitHub)" <gi...@apache.org>.
jimexist commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3762501192

   i guess the original implementation didn't quite compensate the size bloat. i'll take another stab at https://github.com/apache/arrow-rs/pull/9206


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3762927484

   I am not advocating to change implementations here. They probably use that formula for good reasons. I'm just saying that the table in the doc is probably wrong and deserves fixing.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "jimexist (via GitHub)" <gi...@apache.org>.
jimexist commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3763027821

   original table in https://github.com/apache/parquet-format/commit/fa53342948f79a71d040402a9b44b5413e7bfa6a was provided by @jbapple who might be a better poc to provide more details on how they arrived at the metrics.
   
   my understanding was that they were derived from [this paper](https://dl.acm.org/doi/epdf/10.1145/1498698.1594230), my initial rust implementation didn't include those adjustments (for the cause of cache alignment).
   
   agree that implementation change should not be rushed, i guess many years have passed, it makes sense to re-evaluate the caching boost again?


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3767413124

   > i have updated my pull request to reflect [@jbapple](https://github.com/jbapple) 's code to estimate the fpp and shown that the adjustment is indeed in some cases necessary
   
   Is it actually necessary, though? If I look at:
   ```
   NDV: 100, Target FPP: 0.01
     Naive: 128 bytes, actual FPP: 0.011359 ❌ EXCEEDS TARGET
     Compensated: 256 bytes, actual FPP: 0.000371 ✓ meets target
   ```
   
   then sure, 0.011359 is above the target but it's quite close, while 0.000371 is a lot smaller. Unless the target is considered an absolute maximum, then I'm not sure the "naive" computation is a problem.
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3761888626

   I am not an expert in this area (I think @jimexist originally implemented it). Here is the relevant calculation in arrow-rs (looks the same as for C++ and Java to me)
   
   
   
   
   https://github.com/apache/arrow-rs/blob/c1333339626430ceb23efc7eff8b6af46d0b4a3b/parquet/src/bloom_filter/mod.rs#L245-L253
   
   ```rust
   // see http://algo2.iti.kit.edu/documents/cacheefficientbloomfilters-jea.pdf
   // given fpp = (1 - e^(-k * n / m)) ^ k
   // we have m = - k * n / ln(1 - fpp ^ (1 / k))
   // where k = number of hash functions, m = number of bits, n = number of distinct values
   #[inline]
   fn num_of_bits_from_ndv_fpp(ndv: u64, fpp: f64) -> usize {
       let num_bits = -8.0 * ndv as f64 / (1.0 - fpp.powf(1.0 / 8.0)).ln();
       num_bits as usize
   }
   ```
   
   I found the prose confusing -- if the table is supposed to reflect the bits for distinct value I agree the table doesn't seem to match the calcluatiosn
   


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "jimexist (via GitHub)" <gi...@apache.org>.
jimexist commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3762606071

   if the C++ impl is to follow the change i think the line to modify is near https://github.com/apache/arrow/blob/6ec91627ecee34b53291c915d53e674e32ba3367/cpp/src/parquet/bloom_filter.h#L246


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "pitrou (via GitHub)" <gi...@apache.org>.
pitrou commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3762928013

   Though perhaps we should look for the actual theoretical math on Bloom filters.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org


Re: [I] Bloom filter size table does not match implementations [parquet-format]

Posted by "jbapple (via GitHub)" <gi...@apache.org>.
jbapple commented on issue #547:
URL: https://github.com/apache/parquet-format/issues/547#issuecomment-3763202950

   Thank you for pinging me. A correct implementation of the size requirement and false positive probability can be found at https://github.com/jbapple/libfilter/blob/master/c/lib/util.c. It is Apache 2.0 licensed and can be used here.


-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@parquet.apache.org
For additional commands, e-mail: issues-help@parquet.apache.org