Line data    Source code

       1              : /*--------------------------------------------------------------------------
       2              :  *
       3              :  * test_bloomfilter.c
       4              :  *      Test false positive rate of Bloom filter.
       5              :  *
       6              :  * Copyright (c) 2018-2026, 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              : 
      20            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         6901 :             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              : 
      79            1 :     bloom_work_mem = ((int64) 1 << power) / (8 * 1024);
      80              : 
      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              :      */
      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 */
      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)
     122            0 :         elog(ERROR, "power argument must be between 23 and 32 inclusive");
     123              : 
     124            1 :     if (tests <= 0)
     125            0 :         elog(ERROR, "invalid number of tests: %d", tests);
     126              : 
     127            1 :     if (nelements < 0)
     128            0 :         elog(ERROR, "invalid number of elements: %d", tests);
     129              : 
     130            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              : }