Debian Codegraph @

src/test/modules/test_bloomfilter/README

raw
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.