| 1 |
test_bloomfilter overview |
| 2 |
========================= |
| 3 |
|
| 4 |
test_bloomfilter is a test harness module for testing Bloom filter library set |
| 5 |
membership operations. It consists of a single SQL-callable function, |
| 6 |
test_bloomfilter(), plus a regression test that calls test_bloomfilter(). |
| 7 |
Membership tests are performed against a dataset that the test harness module |
| 8 |
generates. |
| 9 |
|
| 10 |
The test_bloomfilter() function displays instrumentation at DEBUG1 elog level |
| 11 |
(WARNING when the false positive rate exceeds a 1% threshold). This can be |
| 12 |
used to get a sense of the performance characteristics of the Postgres Bloom |
| 13 |
filter implementation under varied conditions. |
| 14 |
|
| 15 |
Bitset size |
| 16 |
----------- |
| 17 |
|
| 18 |
The main bloomfilter.c criteria for sizing its bitset is that the false |
| 19 |
positive rate should not exceed 2% when sufficient bloom_work_mem is available |
| 20 |
(and the caller-supplied estimate of the number of elements turns out to have |
| 21 |
been accurate). A 1% - 2% rate is currently assumed to be suitable for all |
| 22 |
Bloom filter callers. |
| 23 |
|
| 24 |
With an optimal K (number of hash functions), Bloom filters should only have a |
| 25 |
1% false positive rate with just 9.6 bits of memory per element. The Postgres |
| 26 |
implementation's 2% worst case guarantee exists because there is a need for |
| 27 |
some slop due to implementation inflexibility in bitset sizing. Since the |
| 28 |
bitset size is always actually kept to a power of two number of bits, callers |
| 29 |
can have their bloom_work_mem argument truncated down by almost half. |
| 30 |
In practice, callers that make a point of passing a bloom_work_mem that is an |
| 31 |
exact power of two bitset size (such as test_bloomfilter.c) will actually get |
| 32 |
the "9.6 bits per element" 1% false positive rate. |
| 33 |
|
| 34 |
Testing strategy |
| 35 |
---------------- |
| 36 |
|
| 37 |
Our approach to regression testing is to test that a Bloom filter has only a 1% |
| 38 |
false positive rate for a single bitset size (2 ^ 23, or 1MB). We test a |
| 39 |
dataset with 838,861 elements, which works out at 10 bits of memory per |
| 40 |
element. We round up from 9.6 bits to 10 bits to make sure that we reliably |
| 41 |
get under 1% for regression testing. Note that a random seed is used in the |
| 42 |
regression tests because the exact false positive rate is inconsistent across |
| 43 |
platforms. Inconsistent hash function behavior is something that the |
| 44 |
regression tests need to be tolerant of anyway. |
| 45 |
|
| 46 |
test_bloomfilter() SQL-callable function |
| 47 |
======================================== |
| 48 |
|
| 49 |
The SQL-callable function test_bloomfilter() provides the following arguments: |
| 50 |
|
| 51 |
* "power" is the power of two used to size the Bloom filter's bitset. |
| 52 |
|
| 53 |
The minimum valid argument value is 23 (2^23 bits), or 1MB of memory. The |
| 54 |
maximum valid argument value is 32, or 512MB of memory. |
| 55 |
|
| 56 |
* "nelements" is the number of elements to generate for testing purposes. |
| 57 |
|
| 58 |
* "seed" is a seed value for hashing. |
| 59 |
|
| 60 |
A value < 0 is interpreted as "use random seed". Varying the seed value (or |
| 61 |
specifying -1) should result in small variations in the total number of false |
| 62 |
positives. |
| 63 |
|
| 64 |
* "tests" is the number of tests to run. |
| 65 |
|
| 66 |
This may be increased when it's useful to perform many tests in an interactive |
| 67 |
session. It only makes sense to perform multiple tests when a random seed is |
| 68 |
used. |