From 2ff9dcace49ea590762701717235d87e13b03c6b Mon Sep 17 00:00:00 2001 From: Peter Geoghegan Date: Thu, 24 Aug 2017 20:58:21 -0700 Subject: [PATCH 1/2] Add Bloom filter data structure implementation. A Bloom filter is a space-efficient, probabilistic data structure that can be used to test set membership. Callers will sometimes incur false positives, but never false negatives. The rate of false positives is a function of the total number of elements and the amount of memory available for the Bloom filter. Two classic applications of Bloom filters are cache filtering, and data synchronization testing. Any user of Bloom filters must accept the possibility of false positives as a cost worth paying for the benefit in space efficiency. This commit adds a test harness extension module, test_bloomfilter. It can be used to get a sense of how the Bloom filter implementation performs under varying conditions. --- src/backend/lib/Makefile | 4 +- src/backend/lib/README | 2 + src/backend/lib/bloomfilter.c | 303 +++++++++++++++++++++ src/include/lib/bloomfilter.h | 27 ++ src/test/modules/Makefile | 1 + src/test/modules/test_bloomfilter/.gitignore | 4 + src/test/modules/test_bloomfilter/Makefile | 21 ++ src/test/modules/test_bloomfilter/README | 71 +++++ .../test_bloomfilter/expected/test_bloomfilter.out | 25 ++ .../test_bloomfilter/sql/test_bloomfilter.sql | 22 ++ .../test_bloomfilter/test_bloomfilter--1.0.sql | 10 + .../modules/test_bloomfilter/test_bloomfilter.c | 138 ++++++++++ .../test_bloomfilter/test_bloomfilter.control | 4 + src/tools/pgindent/typedefs.list | 1 + 14 files changed, 631 insertions(+), 2 deletions(-) create mode 100644 src/backend/lib/bloomfilter.c create mode 100644 src/include/lib/bloomfilter.h create mode 100644 src/test/modules/test_bloomfilter/.gitignore create mode 100644 src/test/modules/test_bloomfilter/Makefile create mode 100644 src/test/modules/test_bloomfilter/README create mode 100644 src/test/modules/test_bloomfilter/expected/test_bloomfilter.out create mode 100644 src/test/modules/test_bloomfilter/sql/test_bloomfilter.sql create mode 100644 src/test/modules/test_bloomfilter/test_bloomfilter--1.0.sql create mode 100644 src/test/modules/test_bloomfilter/test_bloomfilter.c create mode 100644 src/test/modules/test_bloomfilter/test_bloomfilter.control diff --git a/src/backend/lib/Makefile b/src/backend/lib/Makefile index d1fefe4..191ea9b 100644 --- a/src/backend/lib/Makefile +++ b/src/backend/lib/Makefile @@ -12,7 +12,7 @@ subdir = src/backend/lib top_builddir = ../../.. include $(top_builddir)/src/Makefile.global -OBJS = binaryheap.o bipartite_match.o dshash.o hyperloglog.o ilist.o \ - knapsack.o pairingheap.o rbtree.o stringinfo.o +OBJS = binaryheap.o bipartite_match.o bloomfilter.o dshash.o hyperloglog.o \ + ilist.o knapsack.o pairingheap.o rbtree.o stringinfo.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/lib/README b/src/backend/lib/README index 5e5ba5e..376ae27 100644 --- a/src/backend/lib/README +++ b/src/backend/lib/README @@ -3,6 +3,8 @@ in the backend: binaryheap.c - a binary heap +bloomfilter.c - probabilistic, space-efficient set membership testing + hyperloglog.c - a streaming cardinality estimator pairingheap.c - a pairing heap diff --git a/src/backend/lib/bloomfilter.c b/src/backend/lib/bloomfilter.c new file mode 100644 index 0000000..a4ca18d --- /dev/null +++ b/src/backend/lib/bloomfilter.c @@ -0,0 +1,303 @@ +/*------------------------------------------------------------------------- + * + * bloomfilter.c + * Minimal Bloom filter + * + * A Bloom filter is a probabilistic data structure that is used to test an + * element's membership of a set. False positives are possible, but false + * negatives are not; a test of membership of the set returns either "possibly + * in set" or "definitely not in set". This can be very space efficient when + * individual elements are larger than a few bytes, because elements are hashed + * in order to set bits in the Bloom filter bitset. + * + * Elements can be added to the set, but not removed. The more elements that + * are added, the larger the probability of false positives. Caller must hint + * an estimated total size of the set when its Bloom filter is initialized. + * This is used to balance the use of memory against the final false positive + * rate. + * + * Copyright (c) 2018, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/lib/bloomfilter.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include + +#include "access/hash.h" +#include "lib/bloomfilter.h" + +#define MAX_HASH_FUNCS 10 + +struct bloom_filter +{ + /* K hash functions are used, seeded by caller's seed */ + int k_hash_funcs; + uint64 seed; + /* m is bitset size, in bits. Must be a power-of-two <= 2^32. */ + uint64 m; + unsigned char bitset[FLEXIBLE_ARRAY_MEMBER]; +}; + +static int my_bloom_power(uint64 target_bitset_bits); +static int optimal_k(uint64 bitset_bits, int64 total_elems); +static void k_hashes(bloom_filter *filter, uint32 *hashes, unsigned char *elem, + size_t len); +static inline uint32 mod_m(uint32 a, uint64 m); + +/* + * Create Bloom filter in caller's memory context. This should get a false + * positive rate of between 1% and 2% when bitset is not constrained by memory. + * + * total_elems is an estimate of the final size of the set. It ought to be + * approximately correct, but we can cope well with it being off by perhaps a + * factor of five or more. See "Bloom Filters in Probabilistic Verification" + * (Dillinger & Manolios, 2004) for details of why this is the case. + * + * bloom_work_mem is sized in KB, in line with the general work_mem convention. + * + * The Bloom filter behaves non-deterministically when caller passes a random + * seed value. This ensures that the same false positives will not occur from + * one run to the next, which is useful to some callers. + * + * Notes on appropriate use: + * + * To keep the implementation simple and predictable, the underlying bitset is + * always sized as a power-of-two number of bits, and the largest possible + * bitset is 512MB. The implementation rounds down as needed. + * + * The implementation is well suited to data synchronization problems between + * unordered sets, where predictable performance is more important than worst + * case guarantees around false positives. Another problem that the + * implementation is well suited for is cache filtering where good performance + * already relies upon having a relatively small and/or low cardinality set of + * things that are interesting (with perhaps many more uninteresting things + * that never populate the filter). + */ +bloom_filter * +bloom_create(int64 total_elems, int bloom_work_mem, uint32 seed) +{ + bloom_filter *filter; + int bloom_power; + uint64 bitset_bytes; + uint64 bitset_bits; + + /* + * Aim for two bytes per element; this is sufficient to get a false + * positive rate below 1%, independent of the size of the bitset or total + * number of elements. Also, if rounding down the size of the bitset to + * the next lowest power of two turns out to be a significant drop, the + * false positive rate still won't exceed 2% in almost all cases. + */ + bitset_bytes = Min(bloom_work_mem * 1024L, total_elems * 2); + /* Minimum allowable size is 1MB */ + bitset_bytes = Max(1024L * 1024L, bitset_bytes); + + /* Size in bits should be the highest power of two within budget */ + bloom_power = my_bloom_power(bitset_bytes * BITS_PER_BYTE); + /* Use uint64 to size bitset, since PG_UINT32_MAX is 2^32 - 1, not 2^32 */ + bitset_bits = UINT64CONST(1) << bloom_power; + bitset_bytes = bitset_bits / BITS_PER_BYTE; + + /* Allocate bloom filter as all-zeroes */ + filter = palloc0(offsetof(bloom_filter, bitset) + + sizeof(unsigned char) * bitset_bytes); + filter->k_hash_funcs = optimal_k(bitset_bits, total_elems); + + /* + * Caller will probably use signed 32-bit pseudo-random number, so hash + * caller's value to get 64-bit seed value + */ + filter->seed = DatumGetUInt64(hash_uint32_extended(seed, 0)); + filter->m = bitset_bits; + + return filter; +} + +/* + * Free Bloom filter + */ +void +bloom_free(bloom_filter *filter) +{ + pfree(filter); +} + +/* + * Add element to Bloom filter + */ +void +bloom_add_element(bloom_filter *filter, unsigned char *elem, size_t len) +{ + uint32 hashes[MAX_HASH_FUNCS]; + int i; + + k_hashes(filter, hashes, elem, len); + + /* Map a bit-wise address to a byte-wise address + bit offset */ + for (i = 0; i < filter->k_hash_funcs; i++) + { + filter->bitset[hashes[i] >> 3] |= 1 << (hashes[i] & 7); + } +} + +/* + * Test if Bloom filter definitely lacks element. + * + * Returns true if the element is definitely not in the set of elements + * observed by bloom_add_element(). Otherwise, returns false, indicating that + * element is probably present in set. + */ +bool +bloom_lacks_element(bloom_filter *filter, unsigned char *elem, size_t len) +{ + uint32 hashes[MAX_HASH_FUNCS]; + int i; + + k_hashes(filter, hashes, elem, len); + + /* Map a bit-wise address to a byte-wise address + bit offset */ + for (i = 0; i < filter->k_hash_funcs; i++) + { + if (!(filter->bitset[hashes[i] >> 3] & (1 << (hashes[i] & 7)))) + return true; + } + + return false; +} + +/* + * What proportion of bits are currently set? + * + * Returns proportion, expressed as a multiplier of filter size. That should + * generally be close to 0.5, even when we have more than enough memory to + * ensure a false positive rate within target 1% to 2% band, since more hash + * functions are used as more memory is available per element. + * + * This is the only instrumentation that is low overhead enough to appear in + * debug traces. When debugging Bloom filter code, it's likely to be far more + * interesting to directly test the false positive rate. + */ +double +bloom_prop_bits_set(bloom_filter *filter) +{ + int bitset_bytes = filter->m / BITS_PER_BYTE; + uint64 bits_set = 0; + int i; + + for (i = 0; i < bitset_bytes; i++) + { + unsigned char byte = filter->bitset[i]; + + while (byte) + { + bits_set++; + byte &= (byte - 1); + } + } + + return bits_set / (double) filter->m; +} + +/* + * Which element in the sequence of powers-of-two is less than or equal to + * target_bitset_bits? + * + * Value returned here must be generally safe as the basis for actual bitset + * size. + * + * Bitset is never allowed to exceed 2 ^ 32 bits (512MB). This is sufficient + * for the needs of all current callers, and allows us to use 32-bit hash + * functions. It also makes it easy to stay under the MaxAllocSize restriction + * (caller needs to leave room for non-bitset fields that appear before + * flexible array member, so a 1GB bitset would use an allocation that just + * exceeds MaxAllocSize). + */ +static int +my_bloom_power(uint64 target_bitset_bits) +{ + int bloom_power = -1; + + while (target_bitset_bits > 0 && bloom_power < 32) + { + bloom_power++; + target_bitset_bits >>= 1; + } + + return bloom_power; +} + +/* + * Determine optimal number of hash functions based on size of filter in bits, + * and projected total number of elements. The optimal number is the number + * that minimizes the false positive rate. + */ +static int +optimal_k(uint64 bitset_bits, int64 total_elems) +{ + int k = round(log(2.0) * bitset_bits / total_elems); + + return Max(1, Min(k, MAX_HASH_FUNCS)); +} + +/* + * Generate k hash values for element. + * + * Caller passes array, which is filled-in with k values determined by hashing + * caller's element. + * + * Only 2 real independent hash functions are actually used to support an + * interface of up to MAX_HASH_FUNCS hash functions; enhanced double hashing is + * used to make this work. The main reason we prefer enhanced double hashing + * to classic double hashing is that the latter has an issue with collisions + * when using power-of-two sized bitsets. See Dillinger & Manolios for full + * details. + */ +static void +k_hashes(bloom_filter *filter, uint32 *hashes, unsigned char *elem, size_t len) +{ + uint64 hash; + uint32 x, y; + uint64 m; + int i; + + /* Use 64-bit hashing to get two independent 32-bit hashes */ + hash = DatumGetUInt64(hash_any_extended(elem, len, filter->seed)); + x = (uint32) hash; + y = (uint32) (hash >> 32); + m = filter->m; + + x = mod_m(x, m); + y = mod_m(y, m); + + /* Accumulate hashes */ + hashes[0] = x; + for (i = 1; i < filter->k_hash_funcs; i++) + { + x = mod_m(x + y, m); + y = mod_m(y + i, m); + + hashes[i] = x; + } +} + +/* + * Calculate "val MOD m" inexpensively. + * + * Assumes that m (which is bitset size) is a power-of-two. + * + * Using a power-of-two number of bits for bitset size allows us to use bitwise + * AND operations to calculate the modulo of a hash value. It's also a simple + * way of avoiding the modulo bias effect. + */ +static inline uint32 +mod_m(uint32 val, uint64 m) +{ + Assert(m <= PG_UINT32_MAX + UINT64CONST(1)); + Assert(((m - 1) & m) == 0); + + return val & (m - 1); +} diff --git a/src/include/lib/bloomfilter.h b/src/include/lib/bloomfilter.h new file mode 100644 index 0000000..5bc99c3 --- /dev/null +++ b/src/include/lib/bloomfilter.h @@ -0,0 +1,27 @@ +/*------------------------------------------------------------------------- + * + * bloomfilter.h + * Minimal Bloom filter + * + * Copyright (c) 2018, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/include/lib/bloomfilter.h + * + *------------------------------------------------------------------------- + */ +#ifndef _BLOOMFILTER_H_ +#define _BLOOMFILTER_H_ + +typedef struct bloom_filter bloom_filter; + +extern bloom_filter *bloom_create(int64 total_elems, int bloom_work_mem, + uint32 seed); +extern void bloom_free(bloom_filter *filter); +extern void bloom_add_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern double bloom_prop_bits_set(bloom_filter *filter); + +#endif diff --git a/src/test/modules/Makefile b/src/test/modules/Makefile index b7ed0af..fb3aae1 100644 --- a/src/test/modules/Makefile +++ b/src/test/modules/Makefile @@ -9,6 +9,7 @@ SUBDIRS = \ commit_ts \ dummy_seclabel \ snapshot_too_old \ + test_bloomfilter \ test_ddl_deparse \ test_extensions \ test_parser \ diff --git a/src/test/modules/test_bloomfilter/.gitignore b/src/test/modules/test_bloomfilter/.gitignore new file mode 100644 index 0000000..5dcb3ff --- /dev/null +++ b/src/test/modules/test_bloomfilter/.gitignore @@ -0,0 +1,4 @@ +# Generated subdirectories +/log/ +/results/ +/tmp_check/ diff --git a/src/test/modules/test_bloomfilter/Makefile b/src/test/modules/test_bloomfilter/Makefile new file mode 100644 index 0000000..808c931 --- /dev/null +++ b/src/test/modules/test_bloomfilter/Makefile @@ -0,0 +1,21 @@ +# src/test/modules/test_bloomfilter/Makefile + +MODULE_big = test_bloomfilter +OBJS = test_bloomfilter.o $(WIN32RES) +PGFILEDESC = "test_bloomfilter - test code for Bloom filter library" + +EXTENSION = test_bloomfilter +DATA = test_bloomfilter--1.0.sql + +REGRESS = test_bloomfilter + +ifdef USE_PGXS +PG_CONFIG = pg_config +PGXS := $(shell $(PG_CONFIG) --pgxs) +include $(PGXS) +else +subdir = src/test/modules/test_bloomfilter +top_builddir = ../../../.. +include $(top_builddir)/src/Makefile.global +include $(top_srcdir)/contrib/contrib-global.mk +endif diff --git a/src/test/modules/test_bloomfilter/README b/src/test/modules/test_bloomfilter/README new file mode 100644 index 0000000..e54ed13 --- /dev/null +++ b/src/test/modules/test_bloomfilter/README @@ -0,0 +1,71 @@ +test_bloomfilter overview +========================= + +test_bloomfilter is a test harness module for testing Bloom filter library set +membership operations. It consists of a single SQL-callable function, +test_bloomfilter(), and regression tests. Membership tests are performed using +an artificial dataset that is programmatically generated. + +The test_bloomfilter() function displays instrumentation at DEBUG1 elog level +(WARNING when the false positive rate exceeds a 1% threshold). This can be +used to get a sense of the performance characteristics of the Postgres Bloom +filter implementation under varied conditions. + +Bitset size +----------- + +The main bloomfilter.c criteria for sizing its bitset is that the false +positive rate should not exceed 2% when sufficient bloom_work_mem is available +(and the caller-supplied estimate of the number of elements turns out to have +been accurate). A 2% rate is currently assumed to be good enough for all Bloom +filter callers. + +The traditional guarantee Bloom filters offer is that with an optimal K, there +will be only a 1% false positive rate with just 9.6 bits of memory per element. +The 2% worst case guarantee exists because there is a need for some slop, to +account for implementation inflexibility in bitset sizing. The bitset is kept +to a power-of-two number of bits in size, so callers may have their +bloom_work_mem argument truncated down by almost half -- when that happens, the +guarantee needs to hold up. In practice callers that always pass a +bloom_work_mem that is aligned with a power-of-two bitset size will actually +get the "9.6 bits per element" 1% false positive rate. (Under-promising in +this manner is a fudge that allows the contract to be kept simple.) + +Strategy +-------- + +Our approach to regression testing is to test that bloomfilter.c has only a 1% +false positive rate for a single bitset size (2 ^ 23, or 1MB). We test a +dataset with 838,861 elements, which works out at 10 bits of memory per +element. We round up from 9.6 bits to 10 bits to make sure that we reliably +get under 1% for regression testing. Note that a random seed is used in the +regression tests, because the exact false positive rate is inconsistent across +platforms, which makes non-deterministic hashing something that the regression +tests need to be tolerant of anyway. + +SQL-callable function +===================== + +The SQL-callable function test_bloomfilter() provides the following arguments: + +* "power" is the power-of-two used to size the Bloom filter's bitset. + +The minimum valid argument value is 23 (2^23 bits), or 1MB of memory. The +maximum valid argument value is 32, or 512MB of memory. These restrictions +reflect restrictions in bloomfilter.c itself. + +* "nelements" is the number of elements to generate for testing purposes. + +Adjust argument value to observe changes in the false positive rate for a given +Bloom filter bitset size. + +* "seed" is a seed value for hashing. + +A value < 0 is interpreted as "use random seed". Varying the seed value (or +specifying -1) should result in small variations in the total number of false +positives. + +* "tests" is the number of tests to run. + +This may be increased when it's useful to perform many tests without the +overhead of setting up and tearing down a pg_regress database each time. diff --git a/src/test/modules/test_bloomfilter/expected/test_bloomfilter.out b/src/test/modules/test_bloomfilter/expected/test_bloomfilter.out new file mode 100644 index 0000000..4d60eca --- /dev/null +++ b/src/test/modules/test_bloomfilter/expected/test_bloomfilter.out @@ -0,0 +1,25 @@ +CREATE EXTENSION test_bloomfilter; +-- +-- These tests don't produce any interesting output, unless they fail. For an +-- explanation of the arguments, and the values used here, see README. +-- +SELECT test_bloomfilter(power => 23, + nelements => 838861, + seed => -1, + tests => 1); + test_bloomfilter +------------------ + +(1 row) + +-- Equivalent "10 bits per element" tests for all possible bitset sizes: +-- +-- SELECT test_bloomfilter(24, 1677722) +-- SELECT test_bloomfilter(25, 3355443) +-- SELECT test_bloomfilter(26, 6710886) +-- SELECT test_bloomfilter(27, 13421773) +-- SELECT test_bloomfilter(28, 26843546) +-- SELECT test_bloomfilter(29, 53687091) +-- SELECT test_bloomfilter(30, 107374182) +-- SELECT test_bloomfilter(31, 214748365) +-- SELECT test_bloomfilter(32, 429496730) diff --git a/src/test/modules/test_bloomfilter/sql/test_bloomfilter.sql b/src/test/modules/test_bloomfilter/sql/test_bloomfilter.sql new file mode 100644 index 0000000..cc9d19e --- /dev/null +++ b/src/test/modules/test_bloomfilter/sql/test_bloomfilter.sql @@ -0,0 +1,22 @@ +CREATE EXTENSION test_bloomfilter; + +-- +-- These tests don't produce any interesting output, unless they fail. For an +-- explanation of the arguments, and the values used here, see README. +-- +SELECT test_bloomfilter(power => 23, + nelements => 838861, + seed => -1, + tests => 1); + +-- Equivalent "10 bits per element" tests for all possible bitset sizes: +-- +-- SELECT test_bloomfilter(24, 1677722) +-- SELECT test_bloomfilter(25, 3355443) +-- SELECT test_bloomfilter(26, 6710886) +-- SELECT test_bloomfilter(27, 13421773) +-- SELECT test_bloomfilter(28, 26843546) +-- SELECT test_bloomfilter(29, 53687091) +-- SELECT test_bloomfilter(30, 107374182) +-- SELECT test_bloomfilter(31, 214748365) +-- SELECT test_bloomfilter(32, 429496730) diff --git a/src/test/modules/test_bloomfilter/test_bloomfilter--1.0.sql b/src/test/modules/test_bloomfilter/test_bloomfilter--1.0.sql new file mode 100644 index 0000000..bf1f1cd --- /dev/null +++ b/src/test/modules/test_bloomfilter/test_bloomfilter--1.0.sql @@ -0,0 +1,10 @@ +/* src/test/modules/test_bloomfilter/test_bloomfilter--1.0.sql */ + +-- complain if script is sourced in psql, rather than via CREATE EXTENSION +\echo Use "CREATE EXTENSION test_bloomfilter" to load this file. \quit + +-- See README for an explanation of each argument +CREATE FUNCTION test_bloomfilter(power integer, nelements bigint, + seed integer DEFAULT -1, tests integer DEFAULT 1) + RETURNS pg_catalog.void STRICT + AS 'MODULE_PATHNAME' LANGUAGE C; diff --git a/src/test/modules/test_bloomfilter/test_bloomfilter.c b/src/test/modules/test_bloomfilter/test_bloomfilter.c new file mode 100644 index 0000000..74afd36 --- /dev/null +++ b/src/test/modules/test_bloomfilter/test_bloomfilter.c @@ -0,0 +1,138 @@ +/*-------------------------------------------------------------------------- + * + * test_bloomfilter.c + * Test false positive rate of Bloom filter against test dataset. + * + * Copyright (c) 2018, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/test/modules/test_bloomfilter/test_bloomfilter.c + * + * ------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "fmgr.h" +#include "lib/bloomfilter.h" +#include "miscadmin.h" + +PG_MODULE_MAGIC; + +/* Must fit decimal representation of PG_INT64_MAX + 2 bytes: */ +#define MAX_ELEMENT_BYTES 20 +/* False positive rate WARNING threshold (1%): */ +#define FPOSITIVE_THRESHOLD 0.01 + + +/* + * Populate an empty Bloom filter with "nelements" dummy strings. + */ +static void +populate_with_dummy_strings(bloom_filter *filter, int64 nelements) +{ + char element[MAX_ELEMENT_BYTES]; + int64 i; + + for (i = 0; i < nelements; i++) + { + CHECK_FOR_INTERRUPTS(); + + snprintf(element, sizeof(element), "i" INT64_FORMAT, i); + bloom_add_element(filter, (unsigned char *) element, strlen(element)); + } +} + +/* + * Returns number of strings that are indicated as probably appearing in Bloom + * filter that were in fact never added by populate_with_dummy_strings(). + * These are false positives. + */ +static int64 +nfalsepos_for_missing_strings(bloom_filter *filter, int64 nelements) +{ + char element[MAX_ELEMENT_BYTES]; + int64 nfalsepos = 0; + int64 i; + + for (i = 0; i < nelements; i++) + { + CHECK_FOR_INTERRUPTS(); + + snprintf(element, sizeof(element), "M" INT64_FORMAT, i); + if (!bloom_lacks_element(filter, (unsigned char *) element, + strlen(element))) + nfalsepos++; + } + + return nfalsepos; +} + +static void +create_and_test_bloom(int power, int64 nelements, int callerseed) +{ + int bloom_work_mem; + uint32 seed; + int64 nfalsepos; + bloom_filter *filter; + + bloom_work_mem = (1L << power) / 8L / 1024L; + + elog(DEBUG1, "bloom_work_mem (KB): %d", bloom_work_mem); + + /* + * Generate random seed, or use caller's. Seed should always be a + * positive value less than or equal to PG_INT32_MAX, to ensure that any + * random seed can be recreated through callerseed if the need arises. + * (Don't assume that RAND_MAX cannot exceed PG_INT32_MAX.) + */ + seed = callerseed < 0 ? random() % PG_INT32_MAX : callerseed; + + /* Create Bloom filter, populate it, and report on false positive rate */ + filter = bloom_create(nelements, bloom_work_mem, seed); + populate_with_dummy_strings(filter, nelements); + nfalsepos = nfalsepos_for_missing_strings(filter, nelements); + + ereport((nfalsepos > nelements * FPOSITIVE_THRESHOLD) ? WARNING : DEBUG1, + (errmsg_internal("false positives: " INT64_FORMAT " (rate: %.6f, proportion bits set: %.6f, seed: %u)", + nfalsepos, (double) nfalsepos / nelements, + bloom_prop_bits_set(filter), seed))); + + bloom_free(filter); +} + +PG_FUNCTION_INFO_V1(test_bloomfilter); + +/* + * SQL-callable entry point to perform all tests. + * + * If a 1% false positive threshold is not met, emits WARNINGs. + * + * See README for details of arguments. + */ +Datum +test_bloomfilter(PG_FUNCTION_ARGS) +{ + int power = PG_GETARG_INT32(0); + int64 nelements = PG_GETARG_INT64(1); + int seed = PG_GETARG_INT32(2); + int tests = PG_GETARG_INT32(3); + int i; + + if (power < 23 || power > 32) + elog(ERROR, "power argument must be between 23 and 32 inclusive"); + + if (tests <= 0) + elog(ERROR, "invalid number of tests: %d", tests); + + if (nelements < 0) + elog(ERROR, "invalid number of elements: %d", tests); + + for (i = 0; i < tests; i++) + { + elog(DEBUG1, "beginning test #%d...", i + 1); + + create_and_test_bloom(power, nelements, seed); + } + + PG_RETURN_VOID(); +} diff --git a/src/test/modules/test_bloomfilter/test_bloomfilter.control b/src/test/modules/test_bloomfilter/test_bloomfilter.control new file mode 100644 index 0000000..99e56ee --- /dev/null +++ b/src/test/modules/test_bloomfilter/test_bloomfilter.control @@ -0,0 +1,4 @@ +comment = 'Test code for Bloom filter library' +default_version = '1.0' +module_pathname = '$libdir/test_bloomfilter' +relocatable = true diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index d4765ce..1b1a996 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -2580,6 +2580,7 @@ bitmapword bits16 bits32 bits8 +bloom_filter bool brin_column_state bytea -- 2.7.4