LCOV - code coverage report
Current view: top level - src/test/modules/test_bloomfilter - test_bloomfilter.c (source / functions) Hit Total Coverage
Test: PostgreSQL 12beta2 Lines: 38 41 92.7 %
Date: 2019-06-19 16:07:09 Functions: 6 6 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /*--------------------------------------------------------------------------
       2             :  *
       3             :  * test_bloomfilter.c
       4             :  *      Test false positive rate of Bloom filter.
       5             :  *
       6             :  * Copyright (c) 2018-2019, 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 "fmgr.h"
      16             : #include "lib/bloomfilter.h"
      17             : #include "miscadmin.h"
      18             : 
      19           2 : PG_MODULE_MAGIC;
      20             : 
      21             : /* Fits decimal representation of PG_INT64_MIN + 2 bytes: */
      22             : #define MAX_ELEMENT_BYTES       21
      23             : /* False positive rate WARNING threshold (1%): */
      24             : #define FPOSITIVE_THRESHOLD     0.01
      25             : 
      26             : 
      27             : /*
      28             :  * Populate an empty Bloom filter with "nelements" dummy strings.
      29             :  */
      30             : static void
      31           2 : populate_with_dummy_strings(bloom_filter *filter, int64 nelements)
      32             : {
      33             :     char        element[MAX_ELEMENT_BYTES];
      34             :     int64       i;
      35             : 
      36     1677724 :     for (i = 0; i < nelements; i++)
      37             :     {
      38     1677722 :         CHECK_FOR_INTERRUPTS();
      39             : 
      40     1677722 :         snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
      41     1677722 :         bloom_add_element(filter, (unsigned char *) element, strlen(element));
      42             :     }
      43           2 : }
      44             : 
      45             : /*
      46             :  * Returns number of strings that are indicated as probably appearing in Bloom
      47             :  * filter that were in fact never added by populate_with_dummy_strings().
      48             :  * These are false positives.
      49             :  */
      50             : static int64
      51           2 : nfalsepos_for_missing_strings(bloom_filter *filter, int64 nelements)
      52             : {
      53             :     char        element[MAX_ELEMENT_BYTES];
      54           2 :     int64       nfalsepos = 0;
      55             :     int64       i;
      56             : 
      57     1677724 :     for (i = 0; i < nelements; i++)
      58             :     {
      59     1677722 :         CHECK_FOR_INTERRUPTS();
      60             : 
      61     1677722 :         snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
      62     1677722 :         if (!bloom_lacks_element(filter, (unsigned char *) element,
      63             :                                  strlen(element)))
      64       13998 :             nfalsepos++;
      65             :     }
      66             : 
      67           2 :     return nfalsepos;
      68             : }
      69             : 
      70             : static void
      71           2 : create_and_test_bloom(int power, int64 nelements, int callerseed)
      72             : {
      73             :     int         bloom_work_mem;
      74             :     uint64      seed;
      75             :     int64       nfalsepos;
      76             :     bloom_filter *filter;
      77             : 
      78           2 :     bloom_work_mem = (1L << power) / 8L / 1024L;
      79             : 
      80           2 :     elog(DEBUG1, "bloom_work_mem (KB): %d", bloom_work_mem);
      81             : 
      82             :     /*
      83             :      * Generate random seed, or use caller's.  Seed should always be a
      84             :      * positive value less than or equal to PG_INT32_MAX, to ensure that any
      85             :      * random seed can be recreated through callerseed if the need arises.
      86             :      * (Don't assume that RAND_MAX cannot exceed PG_INT32_MAX.)
      87             :      */
      88           2 :     seed = callerseed < 0 ? random() % PG_INT32_MAX : callerseed;
      89             : 
      90             :     /* Create Bloom filter, populate it, and report on false positive rate */
      91           2 :     filter = bloom_create(nelements, bloom_work_mem, seed);
      92           2 :     populate_with_dummy_strings(filter, nelements);
      93           2 :     nfalsepos = nfalsepos_for_missing_strings(filter, nelements);
      94             : 
      95           2 :     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           2 :     bloom_free(filter);
     101           2 : }
     102             : 
     103           4 : 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           2 : test_bloomfilter(PG_FUNCTION_ARGS)
     114             : {
     115           2 :     int         power = PG_GETARG_INT32(0);
     116           2 :     int64       nelements = PG_GETARG_INT64(1);
     117           2 :     int         seed = PG_GETARG_INT32(2);
     118           2 :     int         tests = PG_GETARG_INT32(3);
     119             :     int         i;
     120             : 
     121           2 :     if (power < 23 || power > 32)
     122           0 :         elog(ERROR, "power argument must be between 23 and 32 inclusive");
     123             : 
     124           2 :     if (tests <= 0)
     125           0 :         elog(ERROR, "invalid number of tests: %d", tests);
     126             : 
     127           2 :     if (nelements < 0)
     128           0 :         elog(ERROR, "invalid number of elements: %d", tests);
     129             : 
     130           4 :     for (i = 0; i < tests; i++)
     131             :     {
     132           2 :         elog(DEBUG1, "beginning test #%d...", i + 1);
     133             : 
     134           2 :         create_and_test_bloom(power, nelements, seed);
     135             :     }
     136             : 
     137           2 :     PG_RETURN_VOID();
     138             : }

Generated by: LCOV version 1.13