Repository navigation
Commit dab1684
Bloom filter implementation (#9398)
## Rationale for this change
<!--
Why are you proposing this change, and what is its impact?
Is it part of a long term effort, or a bigger change?
If this PR is related to a tracked effort or an open issue, please link
to the relevant issue.
-->
This is part of a bigger issue around skip indexes but only focuses on
the Bloom filter implementation:
- #8901
## What changes are included in this PR?
<!--
No need to duplicate information from the previous section, but if
you're touching many
parts of the code base, its worth explicitly noting the important
changes or how they are tested.
-->
This is a continuation of a previous PR that already implements a
simpler version of a bloom filter:
#8933.
Most of the changes included in this PR are replacing the hand-rolled
bloom-filter from the base PR with the [split block bloom
filter](https://arxiv.org/pdf/2101.01719), and expanding support for
more canonicals and constants. So far it supports bool, primitives,
decimals, varbinview, and extensions, and this PR leaves out composable
types out of the implementation (struct, list and so on).
<!--
Are there any user-facing changes that might require documentation
updates
Is any public API changed?
-->
## About the code
The Bloom filter implementation is a translation from the [paper source
code](https://arxiv.org/pdf/2101.01719), given that it is very short I
thought it wouldn't be a big deal. The code doesn't use arch-y fn calls,
but relies on the compiler optimizer for vectorizing/calling the correct
assembler expression, which from my checks on godbolt, seems to get
translated well. I could have gone into specializing the code into
different architectures but keeping it as is seemed better for
maintenance.
### Accumulators
Bloom filter's accumulators for canonicals are very similar to those of
the min/max aggregation fn. I used those implementations as a reference
for manipulating each case, with some slight variations.
Invalid values are left out of Bloom filters. Only valid values apply.
Accumulating an invalid value will just skip it, but asking for a scalar
that is invalid will raise a `VortexError`.
### Options/tuning
The Bloom filter has a single tuning option called `blocks_count`. The
more blocks, the more memory/space usage (per zone), but the fewer false
positives. Defaults to 256 (8KiB p/zone), derived from the default
amount of 8192 rows in a zone. The paper suggests keeping between 20 and
52 distinct hash values per block. Assuming all 8,192 values are
distinct, choosing 32 values per block gives 8,192 / 32 = 256 blocks
(low false positive rate: ~3%).
Another approach could be to use statistics from a subset of the data,
as is done with encoders, to select the best block count. I think this
approach aligns with how Vortex encoders work, but it shouldn't be part
of this PR, as it may depend on how the skip index writer is designed.
### Hasher crate
This PR also includes a new crate `twox-hash` that implements XxHash,
similar to how Parquet uses the same hasher for the same use case, but
it relies on vendored code. Happy to change or look for alternatives.
## Pending tasks
- [x] Microbenchmarks
- [x] Goldenfile
- [x] Salt-order check
- [x] Define hashing fn (`XxHash3_64` vs `XXH64`)
- [x] More docs in source
---------
Signed-off-by: Connor Tsui <[email protected]>
Signed-off-by: Joaquin Colacci <[email protected]>
Co-authored-by: Connor Tsui <[email protected]>1 parent 792cef7 commit dab1684
19 files changed
Lines changed: 2740 additions & 0 deletions
File tree
- vortex-layout
- benches
- goldenfiles
- src/layouts/zoned
- aggregates
- bloom_filter
- canonical
- partial
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
284 | 284 | | |
285 | 285 | | |
286 | 286 | | |
| 287 | + | |
287 | 288 | | |
288 | 289 | | |
289 | 290 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
38 | 38 | | |
39 | 39 | | |
40 | 40 | | |
| 41 | + | |
41 | 42 | | |
42 | 43 | | |
43 | 44 | | |
| |||
56 | 57 | | |
57 | 58 | | |
58 | 59 | | |
| 60 | + | |
59 | 61 | | |
| 62 | + | |
60 | 63 | | |
61 | 64 | | |
62 | 65 | | |
| |||
79 | 82 | | |
80 | 83 | | |
81 | 84 | | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
82 | 89 | | |
83 | 90 | | |
84 | 91 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
Binary file not shown.
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
0 commit comments