fix(bloom): BloomBitsPerKey does not depend on number of keys #4
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
During the bits per key (m/n) calculation we first multiply the result by
numEntries
to get the size of the bloom filter (m), and then divide bynumEntries
to get the m/n. Also for some reason, as was mentioned in #1763, current implementation underestimates the result by 30% because of erroneous multiplication byLn2
.Wikipedia suggests that bits per key calculation can be simplified to:
While here also fix edgecases for very small and large ε to protect against misuse and added tests.
This is a copy of: dgraph-io/badger#1773
This change is