apache / apache/parquet-format

Bloom filter size table does not match implementations

Open
#547 12 comments 0 reactions 0 assignees View on GitHub
Type: bug
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.