apache / apache/parquet-format
Bloom filter size table does not match implementations
- Dominant language
- Thrift
- Stars
- 2.6k
- Forks
- 508
- Avg merge
- 2d 8h
- Merged PRs (30d)
- 4
Description
### 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
```
Contributor guide
Research direction
Compare the sizing table in BloomFilter.md with the formulas linked in Parquet C++ bloom_filter.h and Parquet Java BlockSplitBloomFilter.java, using the Python calculations in the issue to verify the values. Update the documented table once the implementation behavior is confirmed; done means the listed bits per insert match the cited implementations.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- cpp, java, python
- Domain
- data-engineering, documentation
- Issue type
- Bug
- Difficulty
- 2/5
- Estimated time
- 1-3 hours
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 52/100