Age Owner Branch data TLA Line data Source code
1 : : /*--------------------------------------------------------------------------
2 : : *
3 : : * test_bloomfilter.c
4 : : * Test false positive rate of Bloom filter.
5 : : *
6 : : * Copyright (c) 2018-2025, PostgreSQL Global Development Group
7 : : *
8 : : * IDENTIFICATION
9 : : * src/test/modules/test_bloomfilter/test_bloomfilter.c
10 : : *
11 : : * -------------------------------------------------------------------------
12 : : */
13 : : #include "postgres.h"
14 : :
15 : : #include "common/pg_prng.h"
16 : : #include "fmgr.h"
17 : : #include "lib/bloomfilter.h"
18 : : #include "miscadmin.h"
19 : :
2716 andres@anarazel.de 20 :CBC 1 : PG_MODULE_MAGIC;
21 : :
22 : : /* Fits decimal representation of PG_INT64_MIN + 2 bytes: */
23 : : #define MAX_ELEMENT_BYTES 21
24 : : /* False positive rate WARNING threshold (1%): */
25 : : #define FPOSITIVE_THRESHOLD 0.01
26 : :
27 : :
28 : : /*
29 : : * Populate an empty Bloom filter with "nelements" dummy strings.
30 : : */
31 : : static void
32 : 1 : populate_with_dummy_strings(bloom_filter *filter, int64 nelements)
33 : : {
34 : : char element[MAX_ELEMENT_BYTES];
35 : : int64 i;
36 : :
37 [ + + ]: 838862 : for (i = 0; i < nelements; i++)
38 : : {
39 [ - + ]: 838861 : CHECK_FOR_INTERRUPTS();
40 : :
41 : 838861 : snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
42 : 838861 : bloom_add_element(filter, (unsigned char *) element, strlen(element));
43 : : }
44 : 1 : }
45 : :
46 : : /*
47 : : * Returns number of strings that are indicated as probably appearing in Bloom
48 : : * filter that were in fact never added by populate_with_dummy_strings().
49 : : * These are false positives.
50 : : */
51 : : static int64
52 : 1 : nfalsepos_for_missing_strings(bloom_filter *filter, int64 nelements)
53 : : {
54 : : char element[MAX_ELEMENT_BYTES];
55 : 1 : int64 nfalsepos = 0;
56 : : int64 i;
57 : :
58 [ + + ]: 838862 : for (i = 0; i < nelements; i++)
59 : : {
60 [ - + ]: 838861 : CHECK_FOR_INTERRUPTS();
61 : :
62 : 838861 : snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
63 [ + + ]: 838861 : if (!bloom_lacks_element(filter, (unsigned char *) element,
64 : : strlen(element)))
65 : 7010 : nfalsepos++;
66 : : }
67 : :
68 : 1 : return nfalsepos;
69 : : }
70 : :
71 : : static void
72 : 1 : create_and_test_bloom(int power, int64 nelements, int callerseed)
73 : : {
74 : : int bloom_work_mem;
75 : : uint64 seed;
76 : : int64 nfalsepos;
77 : : bloom_filter *filter;
78 : :
218 tgl@sss.pgh.pa.us 79 : 1 : bloom_work_mem = ((int64) 1 << power) / (8 * 1024);
80 : :
2716 andres@anarazel.de 81 [ - + ]: 1 : elog(DEBUG1, "bloom_work_mem (KB): %d", bloom_work_mem);
82 : :
83 : : /*
84 : : * Generate random seed, or use caller's. Seed should always be a
85 : : * positive value less than or equal to PG_INT32_MAX, to ensure that any
86 : : * random seed can be recreated through callerseed if the need arises.
87 : : */
1378 tgl@sss.pgh.pa.us 88 [ + - ]: 1 : seed = callerseed < 0 ? pg_prng_int32p(&pg_global_prng_state) : callerseed;
89 : :
90 : : /* Create Bloom filter, populate it, and report on false positive rate */
2716 andres@anarazel.de 91 : 1 : filter = bloom_create(nelements, bloom_work_mem, seed);
92 : 1 : populate_with_dummy_strings(filter, nelements);
93 : 1 : nfalsepos = nfalsepos_for_missing_strings(filter, nelements);
94 : :
95 [ - + - + ]: 1 : ereport((nfalsepos > nelements * FPOSITIVE_THRESHOLD) ? WARNING : DEBUG1,
96 : : (errmsg_internal("seed: " UINT64_FORMAT " false positives: " INT64_FORMAT " (%.6f%%) bitset %.2f%% set",
97 : : seed, nfalsepos, (double) nfalsepos / nelements,
98 : : 100.0 * bloom_prop_bits_set(filter))));
99 : :
100 : 1 : bloom_free(filter);
101 : 1 : }
102 : :
103 : 2 : PG_FUNCTION_INFO_V1(test_bloomfilter);
104 : :
105 : : /*
106 : : * SQL-callable entry point to perform all tests.
107 : : *
108 : : * If a 1% false positive threshold is not met, emits WARNINGs.
109 : : *
110 : : * See README for details of arguments.
111 : : */
112 : : Datum
113 : 1 : test_bloomfilter(PG_FUNCTION_ARGS)
114 : : {
115 : 1 : int power = PG_GETARG_INT32(0);
116 : 1 : int64 nelements = PG_GETARG_INT64(1);
117 : 1 : int seed = PG_GETARG_INT32(2);
118 : 1 : int tests = PG_GETARG_INT32(3);
119 : : int i;
120 : :
121 [ + - - + ]: 1 : if (power < 23 || power > 32)
2716 andres@anarazel.de 122 [ # # ]:UBC 0 : elog(ERROR, "power argument must be between 23 and 32 inclusive");
123 : :
2716 andres@anarazel.de 124 [ - + ]:CBC 1 : if (tests <= 0)
2716 andres@anarazel.de 125 [ # # ]:UBC 0 : elog(ERROR, "invalid number of tests: %d", tests);
126 : :
2716 andres@anarazel.de 127 [ - + ]:CBC 1 : if (nelements < 0)
2716 andres@anarazel.de 128 [ # # ]:UBC 0 : elog(ERROR, "invalid number of elements: %d", tests);
129 : :
2716 andres@anarazel.de 130 [ + + ]:CBC 2 : for (i = 0; i < tests; i++)
131 : : {
132 [ - + ]: 1 : elog(DEBUG1, "beginning test #%d...", i + 1);
133 : :
134 : 1 : create_and_test_bloom(power, nelements, seed);
135 : : }
136 : :
137 : 1 : PG_RETURN_VOID();
138 : : }
|
