Bloom Filter improvements in postgesql
Hi All,
I would like to propose some improvements to the bloom filter
implementation that exists in postgres at the moment. I will describe the
changes along with a patch with some tests. I wanted to get feedback before
I spend more time on this so the patch is not production ready(WIP) but is
sufficient for feedback. The patch code compiles and tests successfully and
doesn't break anything(to the best of my knowledge!)
*Problem Statement*
The existing bloom filter uses an integer number of hash functions. This is
completely fine but we can do better. In a recent paper
<https://arxiv.org/abs/2502.02193> its described how bloom filters can be
tuned to use non-integer values of hash functions. This is
particularly nice as often the optimal number of hash functions to use is
not an integer number. When the hash functions(K) to be used is calculated,
it could be something like 2.3. Then we would round up to 3 and use k=3
hash functions for the bloom filter. This means that the filter size will
be ceil(k)/k = 1/k times larger than the optimal filter size. If we take
floor(k) instead we get an increase in the filter's density which increases
the false positive rate which may not be desirable.
*Proposed Improvements *
Instead we can relax the assumption that it must be an integer value for k.
To do this we split the k value into an integer and a rational part. Call
this k and r. So in the example above where we calculated k to be equal to
2.3 this would mean k = 2 and r = 0.3. We always use k hash functions but
we apply a third hash function 30% of the time(corresponding to r = 0.3 in
this case). This is done deterministically so the same element always gets
the same treatment(keeps the bloom filter promise of no false negatives).
The paper has more information but this is the gist of the rational part of
the bloom filter.
However we can take this further and look to make the bloom filter
lossless. Using the rational part described above we've given ourselves
some wriggle room so to speak. We can compliment the rational 'lossy' bloom
filter with an additional array called a witness. This allows us to
reconstruct the original input, which just means a false positive rate of
0. The witness(W) is constructed concurrently with the bloom filter bitmap.
The witness encodes information for every element that passes the
initial bloom filter test(both the true and false positives). Clearly this
establishes a direct relationship between the false positive rate and the
size of the witness. As this is all done deterministically the decoding
process is just the reverse of the encoding process. We can easily figure
out true positives from false positives by checking the witness. By
extension of the deterministic process there can be no false negatives.
*Tradeoffs and Considerations*
As stated in the previous section there is a direct relationship between
the false positive rate and the size of the witness. The lossless
capability comes at the price of more memory for the witness. The expected
witness size can be calculated t * (1 + r ^2) where t = true positives and
r = 1/ln2. Let's give a concrete example
t = 1000000 (a million items in the filter)
fp = 0.01
size of the filter = 9,585,059 (bits or approx 1.14 mb)
k = 6.65 (assuming we use rational number of hfc's)
For a bloom filter setup for these parameters we can expect a witness size
of approximately 3,000,000 bits. The total space complexity is still 0(N).
The main tradeoffs are of course the memory overhead of the witness. I have
done some preliminary benchmarking and as expected the use of the witness
does slow down inserts and lookups. The insert speed is around 3x slower
and the lookup speed 2x slower. I definitely think this can be made faster
but in any case it will always be slower than the traditional bloom filter
if we wanted to also have a 'lossless' option.
*Final thoughts and comments*
The rational bloom filter would be a nice improvement to the existing bloom
filter implementation. The lossless option could be useful in some
scenarios at the expense of extra memory and slower lookup and insertion
times. I have attached two patches showing a WIP of the changes(mainly to
do with the lossless option). I would appreciate any feedback on whether
any/all of this proposal would be considered. I'd be happy to make the
changes myself.
Attachments:
0001-create-an-improved-filter-with-a-zero-fp-rate-for-ve.patchapplication/octet-stream; name=0001-create-an-improved-filter-with-a-zero-fp-rate-for-ve.patchDownload
From 88686f7b331c21010f0e3213898e9bf784ff5556 Mon Sep 17 00:00:00 2001
From: ross39 <Rheaney26@gmail.com>
Date: Sat, 28 Jun 2025 20:31:34 +0100
Subject: [PATCH 1/2] create an improved filter with a zero fp rate for very
minimal overhead
---
src/backend/lib/bloomfilter.c | 469 ++++++++++++++++++
src/include/lib/bloomfilter.h | 36 ++
.../test_lossless_bloomfilter/Makefile | 21 +
.../test_lossless_bloomfilter--1.0.sql | 28 ++
.../test_lossless_bloomfilter.c | 356 +++++++++++++
.../test_lossless_bloomfilter.control | 5 +
6 files changed, 915 insertions(+)
create mode 100644 src/test/modules/test_lossless_bloomfilter/Makefile
create mode 100644 src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter--1.0.sql
create mode 100644 src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.c
create mode 100644 src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.control
diff --git a/src/backend/lib/bloomfilter.c b/src/backend/lib/bloomfilter.c
index d3f935170db..9875ec9aed8 100644
--- a/src/backend/lib/bloomfilter.c
+++ b/src/backend/lib/bloomfilter.c
@@ -24,6 +24,13 @@
* caller many authoritative lookups, such as expensive probes of a much larger
* on-disk structure.
*
+ * Enhanced Lossless Bloom Filter Implementation:
+ * This file also contains an enhanced implementation that combines:
+ * 1. Rational Bloom Filters (RBF) - allowing non-integer k values
+ * 2. Variably-Sized Block Bloom Filters (VSBBF) - flexible filter sizes
+ * 3. Witness Data Structure - for lossless membership testing
+ * 4. Conditional Hashing - optimized hash function usage based on element properties
+ *
* Copyright (c) 2018-2025, PostgreSQL Global Development Group
*
* IDENTIFICATION
@@ -38,8 +45,12 @@
#include "common/hashfn.h"
#include "lib/bloomfilter.h"
#include "port/pg_bitutils.h"
+#include "utils/hsearch.h"
+#include "utils/memutils.h"
+#include "common/pg_prng.h"
#define MAX_HASH_FUNCS 10
+#define MAX_BLOCKS 32 /* Maximum number of blocks in VSBBF */
struct bloom_filter
{
@@ -51,12 +62,67 @@ struct bloom_filter
unsigned char bitset[FLEXIBLE_ARRAY_MEMBER];
};
+/* Block definition for Variably-Sized Block Bloom Filter */
+typedef struct bloom_block
+{
+ uint64 size; /* Size of this block in bits (power of 2) */
+ double k_rational; /* Rational number of hash functions for this block */
+ int k_floor; /* Floor of k_rational */
+ double k_fractional; /* Fractional part of k_rational */
+ uint64 offset; /* Bit offset in the combined bitset */
+} bloom_block;
+
+/* Witness entry for lossless membership testing */
+typedef struct witness_entry
+{
+ uint64 hash1; /* First hash of the element */
+ uint64 hash2; /* Second hash of the element */
+} witness_entry;
+
+/* Enhanced Lossless Bloom Filter structure */
+struct lossless_bloom_filter
+{
+ /* Configuration */
+ bloom_config config;
+
+ /* VSBBF structure */
+ int num_blocks; /* Number of blocks */
+ bloom_block blocks[MAX_BLOCKS]; /* Block definitions */
+ uint64 total_bits; /* Total bits across all blocks */
+ unsigned char *bitset; /* Combined bitset for all blocks */
+
+ /* Conditional hashing parameters */
+ bool use_conditional_hashing;
+ double k_with_property; /* k for elements with property P */
+ double k_without_property; /* k for elements without property P */
+
+ /* Witness data structure (hash table) */
+ HTAB *witness_table;
+ uint64 witness_entries; /* Number of entries in witness */
+
+ /* Statistics */
+ uint64 bits_set; /* Number of bits currently set */
+ uint64 elements_added; /* Number of elements added */
+};
+
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 val, uint64 m);
+/* Enhanced bloom filter static functions */
+static void decompose_into_blocks(uint64 total_bits, bloom_block *blocks, int *num_blocks);
+static double calculate_rational_k(uint64 block_bits, int64 total_elems);
+static void calculate_conditional_k_values(bloom_config *config, double base_k,
+ double *k_with_prop, double *k_without_prop);
+static void enhanced_k_hashes(lossless_bloom_filter *filter, uint32 *hashes,
+ unsigned char *elem, size_t len, double k_effective,
+ int block_idx, int *num_hashes_out);
+static uint32 witness_hash_func(const void *key, Size keysize);
+static int witness_match_func(const void *key1, const void *key2, Size keysize);
+static bool apply_rational_hashing(double k_fractional, uint64 hash_seed);
+
/*
* Create Bloom filter in caller's memory context. We aim for a false positive
* rate of between 1% and 2% when bitset size is not constrained by memory
@@ -292,3 +358,406 @@ mod_m(uint32 val, uint64 m)
return val & (m - 1);
}
+
+/*
+ * Enhanced Lossless Bloom Filter Implementation
+ */
+
+/*
+ * Create enhanced lossless bloom filter - OPTIMIZED VERSION
+ */
+lossless_bloom_filter *
+lossless_bloom_create(bloom_config *config)
+{
+ lossless_bloom_filter *filter;
+ HASHCTL hash_ctl;
+ uint64 target_bits;
+ uint64 bitset_bytes;
+ int bloom_power;
+
+ Assert(config != NULL);
+ Assert(config->total_elems > 0);
+
+ filter = (lossless_bloom_filter *) palloc0(sizeof(lossless_bloom_filter));
+
+ /* Copy configuration */
+ memcpy(&filter->config, config, sizeof(bloom_config));
+
+ /* OPTIMIZATION: Simplified bit calculation - single power-of-2 block */
+ target_bits = Min(config->bloom_work_mem * UINT64CONST(1024) * 8,
+ config->total_elems * 16);
+ target_bits = Max(1024 * 8, target_bits); /* Minimum 1KB */
+
+ /* Round to power of 2 for fast modulo operations */
+ bloom_power = 0;
+ while ((UINT64CONST(1) << bloom_power) < target_bits && bloom_power < 32)
+ bloom_power++;
+
+ filter->total_bits = UINT64CONST(1) << bloom_power;
+
+ /* OPTIMIZATION: Single block setup (eliminates VSBBF complexity) */
+ filter->num_blocks = 1;
+ filter->blocks[0].size = filter->total_bits;
+ filter->blocks[0].offset = 0;
+ filter->blocks[0].k_rational = log(2.0) * filter->total_bits / config->total_elems;
+ filter->blocks[0].k_floor = Max(1, Min((int)rint(filter->blocks[0].k_rational), MAX_HASH_FUNCS));
+ filter->blocks[0].k_fractional = 0.0; /* Disable fractional hashing for speed */
+
+ /* Allocate bitset */
+ bitset_bytes = (filter->total_bits + 7) / 8;
+ filter->bitset = (unsigned char *) palloc0(bitset_bytes);
+
+ /* OPTIMIZATION: Disable conditional hashing for performance */
+ filter->use_conditional_hashing = false;
+
+ /* OPTIMIZATION: Smaller initial witness table size */
+ MemSet(&hash_ctl, 0, sizeof(hash_ctl));
+ hash_ctl.keysize = sizeof(witness_entry);
+ hash_ctl.entrysize = sizeof(witness_entry);
+ hash_ctl.hash = witness_hash_func;
+ hash_ctl.match = witness_match_func;
+ hash_ctl.hcxt = CurrentMemoryContext;
+
+ filter->witness_table = hash_create("Bloom Witness Table",
+ Max(1024, config->total_elems / 16), /* Smaller initial size */
+ &hash_ctl,
+ HASH_ELEM | HASH_FUNCTION | HASH_COMPARE | HASH_CONTEXT);
+
+ filter->witness_entries = 0;
+ filter->bits_set = 0;
+ filter->elements_added = 0;
+
+ return filter;
+}
+
+/*
+ * Free enhanced bloom filter
+ */
+void
+lossless_bloom_free(lossless_bloom_filter *filter)
+{
+ if (filter == NULL)
+ return;
+
+ if (filter->bitset)
+ pfree(filter->bitset);
+
+ if (filter->witness_table)
+ hash_destroy(filter->witness_table);
+
+ pfree(filter);
+}
+
+/*
+ * Add element to enhanced bloom filter - OPTIMIZED VERSION
+ */
+void
+lossless_bloom_add_element(lossless_bloom_filter *filter, unsigned char *elem, size_t len)
+{
+ uint64 base_hash;
+ uint32 x, y;
+ witness_entry witness_key;
+ bool found;
+ int i;
+ uint32 hashes[MAX_HASH_FUNCS];
+ int k_hash_funcs;
+ uint64 bit_mask;
+
+ Assert(filter != NULL);
+ Assert(elem != NULL);
+
+ /* OPTIMIZATION: Single hash computation */
+ base_hash = DatumGetUInt64(hash_any_extended(elem, len, filter->config.seed));
+ x = (uint32) base_hash;
+ y = (uint32) (base_hash >> 32);
+
+ /* Create witness entry */
+ witness_key.hash1 = x;
+ witness_key.hash2 = y;
+
+ /* Add to witness table */
+ (void) hash_search(filter->witness_table,
+ &witness_key,
+ HASH_ENTER,
+ &found);
+ if (!found)
+ {
+ filter->witness_entries++;
+ }
+
+ /* OPTIMIZATION: Use pre-calculated k and bit mask for fast operations */
+ k_hash_funcs = filter->blocks[0].k_floor; /* Single block, pre-calculated */
+ bit_mask = (uint32)(filter->total_bits - 1); /* Fast modulo for power-of-2 */
+
+ /* OPTIMIZATION: Simplified hash generation - enhanced double hashing */
+ y |= 1; /* Ensure y is odd for good double hashing properties */
+ hashes[0] = x;
+ for (i = 1; i < k_hash_funcs; i++)
+ {
+ x += y;
+ hashes[i] = x;
+ }
+
+ /* OPTIMIZATION: Fast bit setting with bitwise operations */
+ for (i = 0; i < k_hash_funcs; i++)
+ {
+ uint64 bit_pos = hashes[i] & bit_mask; /* Fast modulo using bitwise AND */
+ uint64 byte_pos = bit_pos >> 3; /* Fast divide by 8 */
+ int bit_offset = bit_pos & 7; /* Fast modulo 8 */
+
+ if (!(filter->bitset[byte_pos] & (1 << bit_offset)))
+ {
+ filter->bitset[byte_pos] |= (1 << bit_offset);
+ filter->bits_set++;
+ }
+ }
+
+ filter->elements_added++;
+}
+
+/*
+ * Test lossless membership in enhanced bloom filter - OPTIMIZED VERSION
+ */
+bool
+lossless_bloom_contains_element(lossless_bloom_filter *filter, unsigned char *elem, size_t len)
+{
+ uint64 base_hash;
+ uint32 x, y;
+ witness_entry witness_key;
+ witness_entry *witness_found;
+ int i;
+ uint32 hashes[MAX_HASH_FUNCS];
+ int k_hash_funcs;
+ uint64 bit_mask;
+
+ Assert(filter != NULL);
+ Assert(elem != NULL);
+
+ /* OPTIMIZATION: Single hash computation */
+ base_hash = DatumGetUInt64(hash_any_extended(elem, len, filter->config.seed));
+ x = (uint32) base_hash;
+ y = (uint32) (base_hash >> 32);
+
+ /* OPTIMIZATION: Use pre-calculated k and bit mask for fast operations */
+ k_hash_funcs = filter->blocks[0].k_floor; /* Single block, pre-calculated */
+ bit_mask = (uint32)(filter->total_bits - 1); /* Fast modulo for power-of-2 */
+
+ /* OPTIMIZATION: Simplified hash generation - enhanced double hashing */
+ y |= 1; /* Ensure y is odd for good double hashing properties */
+ hashes[0] = x;
+ for (i = 1; i < k_hash_funcs; i++)
+ {
+ x += y;
+ hashes[i] = x;
+ }
+
+ /* OPTIMIZATION: Fast bit checking with bitwise operations */
+ for (i = 0; i < k_hash_funcs; i++)
+ {
+ uint64 bit_pos = hashes[i] & bit_mask; /* Fast modulo using bitwise AND */
+ uint64 byte_pos = bit_pos >> 3; /* Fast divide by 8 */
+ int bit_offset = bit_pos & 7; /* Fast modulo 8 */
+
+ if (!(filter->bitset[byte_pos] & (1 << bit_offset)))
+ {
+ /* Definitely not in set */
+ return false;
+ }
+ }
+
+ /* All bits are set - check witness for lossless confirmation */
+ witness_key.hash1 = (uint32) base_hash;
+ witness_key.hash2 = (uint32) (base_hash >> 32);
+
+ witness_found = (witness_entry *) hash_search(filter->witness_table,
+ &witness_key,
+ HASH_FIND,
+ NULL);
+
+ /* Return true only if confirmed by witness */
+ return (witness_found != NULL);
+}
+
+/*
+ * Get proportion of bits set in enhanced bloom filter
+ */
+double
+lossless_bloom_prop_bits_set(lossless_bloom_filter *filter)
+{
+ if (filter->total_bits == 0)
+ return 0.0;
+
+ return (double) filter->bits_set / filter->total_bits;
+}
+
+/*
+ * Get statistics from enhanced bloom filter
+ */
+void
+lossless_bloom_get_stats(lossless_bloom_filter *filter,
+ uint64 *witness_entries,
+ uint64 *total_bits,
+ uint64 *bits_set,
+ int *num_blocks)
+{
+ if (witness_entries)
+ *witness_entries = filter->witness_entries;
+ if (total_bits)
+ *total_bits = filter->total_bits;
+ if (bits_set)
+ *bits_set = filter->bits_set;
+ if (num_blocks)
+ *num_blocks = filter->num_blocks;
+}
+
+/*
+ * Static helper functions for enhanced bloom filter
+ */
+
+/* UNUSED FUNCTIONS - Kept for potential future use in advanced optimizations
+ *
+ * These functions were part of the original VSBBF (Variable Size Bloom Filter)
+ * implementation with conditional and rational hashing. They are currently
+ * unused due to the simplified single-block optimization but may be useful
+ * for future advanced features.
+ */
+
+#ifdef FUTURE_OPTIMIZATIONS
+/*
+ * Decompose total bits into power-of-two blocks for VSBBF
+ */
+static void
+decompose_into_blocks(uint64 total_bits, bloom_block *blocks, int *num_blocks)
+{
+ int count = 0;
+ uint64 remaining = total_bits;
+ int power;
+
+ /* Decompose into largest power-of-two components */
+ while (remaining > 0 && count < MAX_BLOCKS)
+ {
+ /* Find highest power of 2 <= remaining */
+ power = 0;
+ while ((UINT64CONST(1) << (power + 1)) <= remaining && power < 31)
+ power++;
+
+ blocks[count].size = UINT64CONST(1) << power;
+ remaining -= blocks[count].size;
+ count++;
+ }
+
+ *num_blocks = count;
+}
+
+/*
+ * Calculate rational k for a block
+ */
+static double
+calculate_rational_k(uint64 block_bits, int64 total_elems)
+{
+ double k = log(2.0) * block_bits / total_elems;
+ return Max(0.1, Min(k, MAX_HASH_FUNCS)); /* Reasonable bounds */
+}
+
+/*
+ * Calculate conditional k values for elements with/without property P
+ */
+static void
+calculate_conditional_k_values(bloom_config *config, double base_k,
+ double *k_with_prop, double *k_without_prop)
+{
+ double a = config->property_prob_true_pos;
+ double b = config->property_prob_true_neg;
+ double p = a / (a + b); /* Simplified calculation */
+
+ /* Adjust k values to minimize overall FPR while maintaining average k */
+ *k_with_prop = base_k * (1.0 + p);
+ *k_without_prop = base_k * (1.0 - p);
+
+ /* Ensure reasonable bounds */
+ *k_with_prop = Max(0.1, Min(*k_with_prop, MAX_HASH_FUNCS));
+ *k_without_prop = Max(0.1, Min(*k_without_prop, MAX_HASH_FUNCS));
+}
+
+/*
+ * Generate enhanced k hashes with rational bloom filter logic
+ */
+static void
+enhanced_k_hashes(lossless_bloom_filter *filter, uint32 *hashes,
+ unsigned char *elem, size_t len, double k_effective,
+ int block_idx, int *num_hashes_out)
+{
+ uint64 hash;
+ uint32 x, y;
+ int k_floor = (int) floor(k_effective);
+ double k_fractional = k_effective - k_floor;
+ int i;
+ uint64 block_seed;
+
+ /* Generate block-specific seed */
+ block_seed = filter->config.seed ^ (block_idx + 1);
+
+ /* Use 64-bit hashing to get two independent 32-bit hashes */
+ hash = DatumGetUInt64(hash_any_extended(elem, len, block_seed));
+ x = (uint32) hash;
+ y = (uint32) (hash >> 32);
+
+ /* Generate deterministic k_floor hashes */
+ hashes[0] = x;
+ for (i = 1; i < k_floor && i < MAX_HASH_FUNCS; i++)
+ {
+ x = x + y;
+ y = y + i;
+ hashes[i] = x;
+ }
+
+ *num_hashes_out = k_floor;
+
+ /* Apply fractional hash probabilistically */
+ if (k_fractional > 0.0 && *num_hashes_out < MAX_HASH_FUNCS)
+ {
+ if (apply_rational_hashing(k_fractional, hash))
+ {
+ x = x + y;
+ y = y + *num_hashes_out;
+ hashes[*num_hashes_out] = x;
+ (*num_hashes_out)++;
+ }
+ }
+}
+#endif /* FUTURE_OPTIMIZATIONS */
+
+/*
+ * Apply rational hashing decision based on fractional part
+ */
+static bool
+apply_rational_hashing(double k_fractional, uint64 hash_seed)
+{
+ /* Use hash_seed to generate deterministic pseudo-random decision */
+ uint32 rand_val = (uint32)(hash_seed >> 32);
+ double threshold = (double)rand_val / (double)UINT32_MAX;
+
+ return threshold < k_fractional;
+}
+
+/*
+ * Hash function for witness table
+ */
+static uint32
+witness_hash_func(const void *key, Size keysize)
+{
+ const witness_entry *entry = (const witness_entry *) key;
+ return (uint32)(entry->hash1 ^ (entry->hash2 << 1));
+}
+
+/*
+ * Match function for witness table
+ */
+static int
+witness_match_func(const void *key1, const void *key2, Size keysize)
+{
+ const witness_entry *entry1 = (const witness_entry *) key1;
+ const witness_entry *entry2 = (const witness_entry *) key2;
+
+ return (entry1->hash1 == entry2->hash1 && entry1->hash2 == entry2->hash2) ? 0 : 1;
+}
diff --git a/src/include/lib/bloomfilter.h b/src/include/lib/bloomfilter.h
index dd9fddd8422..b0b5df5cf19 100644
--- a/src/include/lib/bloomfilter.h
+++ b/src/include/lib/bloomfilter.h
@@ -15,6 +15,7 @@
typedef struct bloom_filter bloom_filter;
+/* Traditional bloom filter API */
extern bloom_filter *bloom_create(int64 total_elems, int bloom_work_mem,
uint64 seed);
extern void bloom_free(bloom_filter *filter);
@@ -24,4 +25,39 @@ extern bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem,
size_t len);
extern double bloom_prop_bits_set(bloom_filter *filter);
+/* Enhanced Lossless Bloom Filter API */
+typedef struct lossless_bloom_filter lossless_bloom_filter;
+
+/* Property function type for conditional hashing */
+typedef bool (*bloom_property_func)(unsigned char *elem, size_t len, void *context);
+
+/* Configuration for enhanced bloom filter */
+typedef struct bloom_config
+{
+ int64 total_elems; /* estimated number of elements */
+ int bloom_work_mem; /* memory limit in KB */
+ uint64 seed; /* hash seed */
+
+ /* Optional conditional hashing configuration */
+ bloom_property_func property_func; /* function to test property P */
+ void *property_context; /* context for property function */
+ double property_prob_true_pos; /* Pr(P | item is true positive) */
+ double property_prob_true_neg; /* Pr(P | item is true negative) */
+} bloom_config;
+
+extern lossless_bloom_filter *lossless_bloom_create(bloom_config *config);
+extern void lossless_bloom_free(lossless_bloom_filter *filter);
+extern void lossless_bloom_add_element(lossless_bloom_filter *filter,
+ unsigned char *elem, size_t len);
+extern bool lossless_bloom_contains_element(lossless_bloom_filter *filter,
+ unsigned char *elem, size_t len);
+extern double lossless_bloom_prop_bits_set(lossless_bloom_filter *filter);
+
+/* Statistics and debugging */
+extern void lossless_bloom_get_stats(lossless_bloom_filter *filter,
+ uint64 *witness_entries,
+ uint64 *total_bits,
+ uint64 *bits_set,
+ int *num_blocks);
+
#endif /* BLOOMFILTER_H */
diff --git a/src/test/modules/test_lossless_bloomfilter/Makefile b/src/test/modules/test_lossless_bloomfilter/Makefile
new file mode 100644
index 00000000000..adae92199d3
--- /dev/null
+++ b/src/test/modules/test_lossless_bloomfilter/Makefile
@@ -0,0 +1,21 @@
+# src/test/modules/test_lossless_bloomfilter/Makefile
+
+MODULE_big = test_lossless_bloomfilter
+OBJS = \
+ $(WIN32RES) \
+ test_lossless_bloomfilter.o
+PGFILEDESC = "test_lossless_bloomfilter - test code for enhanced lossless Bloom filter"
+
+EXTENSION = test_lossless_bloomfilter
+DATA = test_lossless_bloomfilter--1.0.sql
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = src/test/modules/test_lossless_bloomfilter
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
\ No newline at end of file
diff --git a/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter--1.0.sql b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter--1.0.sql
new file mode 100644
index 00000000000..4f722380976
--- /dev/null
+++ b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter--1.0.sql
@@ -0,0 +1,28 @@
+/* src/test/modules/test_bloomfilter/test_lossless_bloomfilter--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION test_lossless_bloomfilter" to load this file. \quit
+
+-- Test basic lossless bloom filter functionality
+CREATE FUNCTION test_lossless_basic(nelements bigint, bloom_work_mem integer)
+RETURNS boolean
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+
+-- Test conditional hashing functionality
+CREATE FUNCTION test_lossless_conditional(nelements bigint, bloom_work_mem integer)
+RETURNS boolean
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+
+-- Compare traditional vs lossless bloom filter performance
+CREATE FUNCTION test_bloom_comparison(nelements bigint, bloom_work_mem integer)
+RETURNS boolean
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+
+-- Demonstrate VSBBF block decomposition
+CREATE FUNCTION test_vsbbf_blocks(total_bits bigint)
+RETURNS text
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
\ No newline at end of file
diff --git a/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.c b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.c
new file mode 100644
index 00000000000..5a6dee81a39
--- /dev/null
+++ b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.c
@@ -0,0 +1,356 @@
+/*--------------------------------------------------------------------------
+ *
+ * test_lossless_bloomfilter.c
+ * Test enhanced lossless bloom filter implementation.
+ *
+ * This module tests the enhanced bloom filter that combines:
+ * 1. Rational Bloom Filters (RBF) - allowing non-integer k values
+ * 2. Variably-Sized Block Bloom Filters (VSBBF) - flexible filter sizes
+ * 3. Witness Data Structure - for lossless membership testing
+ * 4. Conditional Hashing - optimized hash function usage based on element properties
+ *
+ * Copyright (c) 2018-2025, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ * src/test/modules/test_bloomfilter/test_lossless_bloomfilter.c
+ *
+ * -------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include "common/pg_prng.h"
+#include "fmgr.h"
+#include "lib/bloomfilter.h"
+#include "miscadmin.h"
+#include "utils/builtins.h"
+
+PG_MODULE_MAGIC;
+
+/* Fits decimal representation of PG_INT64_MIN + 2 bytes: */
+#define MAX_ELEMENT_BYTES 21
+
+/*
+ * Property function for conditional hashing demo
+ * Returns true if the element represents an "even" number
+ */
+static bool
+is_even_number_property(unsigned char *elem, size_t len, void *context)
+{
+ char *str = (char *) elem;
+ int64 num;
+
+ /* Simple parsing - assume element is "i<number>" format */
+ if (len > 1 && str[0] == 'i')
+ {
+ num = strtoll(&str[1], NULL, 10);
+ return (num % 2 == 0);
+ }
+
+ return false;
+}
+
+/*
+ * Test basic lossless bloom filter functionality
+ */
+PG_FUNCTION_INFO_V1(test_lossless_basic);
+Datum
+test_lossless_basic(PG_FUNCTION_ARGS)
+{
+ int64 nelements = PG_GETARG_INT64(0);
+ int bloom_work_mem = PG_GETARG_INT32(1);
+ lossless_bloom_filter *filter;
+ bloom_config config;
+ char element[MAX_ELEMENT_BYTES];
+ int64 i;
+ int64 false_positives = 0;
+ int64 false_negatives = 0;
+ uint64 witness_entries, total_bits, bits_set;
+ int num_blocks;
+ double fill_ratio;
+
+ /* Initialize configuration */
+ memset(&config, 0, sizeof(bloom_config));
+ config.total_elems = nelements;
+ config.bloom_work_mem = bloom_work_mem;
+ config.seed = pg_prng_uint64(&pg_global_prng_state);
+ config.property_func = NULL; /* No conditional hashing for basic test */
+
+ /* Create lossless bloom filter */
+ filter = lossless_bloom_create(&config);
+
+ /* Populate with "nelements" dummy strings */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
+ lossless_bloom_add_element(filter, (unsigned char *) element, strlen(element));
+ }
+
+ /* Test for elements that should be present (no false negatives expected) */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
+ if (!lossless_bloom_contains_element(filter, (unsigned char *) element, strlen(element)))
+ {
+ false_negatives++;
+ }
+ }
+
+ /* Test for elements that should NOT be present (no false positives expected) */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
+ if (lossless_bloom_contains_element(filter, (unsigned char *) element, strlen(element)))
+ {
+ false_positives++;
+ }
+ }
+
+ /* Get statistics */
+ lossless_bloom_get_stats(filter, &witness_entries, &total_bits, &bits_set, &num_blocks);
+ fill_ratio = lossless_bloom_prop_bits_set(filter);
+
+ /* Clean up */
+ lossless_bloom_free(filter);
+
+ /* Return results as text */
+ ereport(NOTICE,
+ (errmsg("Lossless Bloom Filter Test Results:"),
+ errdetail("Elements: " INT64_FORMAT ", "
+ "False Positives: " INT64_FORMAT " (should be 0), "
+ "False Negatives: " INT64_FORMAT " (should be 0), "
+ "Witness Entries: " UINT64_FORMAT ", "
+ "Total Bits: " UINT64_FORMAT ", "
+ "Bits Set: " UINT64_FORMAT " (%.2f%%), "
+ "Blocks: %d",
+ nelements, false_positives, false_negatives,
+ witness_entries, total_bits, bits_set, fill_ratio * 100.0, num_blocks)));
+
+ PG_RETURN_BOOL(false_positives == 0 && false_negatives == 0);
+}
+
+/*
+ * Test conditional hashing functionality
+ */
+PG_FUNCTION_INFO_V1(test_lossless_conditional);
+Datum
+test_lossless_conditional(PG_FUNCTION_ARGS)
+{
+ int64 nelements = PG_GETARG_INT64(0);
+ int bloom_work_mem = PG_GETARG_INT32(1);
+ lossless_bloom_filter *filter;
+ bloom_config config;
+ char element[MAX_ELEMENT_BYTES];
+ int64 i;
+ int64 false_positives = 0;
+ int64 false_negatives = 0;
+ uint64 witness_entries, total_bits, bits_set;
+ int num_blocks;
+ double fill_ratio;
+
+ /* Initialize configuration with conditional hashing */
+ memset(&config, 0, sizeof(bloom_config));
+ config.total_elems = nelements;
+ config.bloom_work_mem = bloom_work_mem;
+ config.seed = pg_prng_uint64(&pg_global_prng_state);
+ config.property_func = is_even_number_property;
+ config.property_context = NULL;
+ config.property_prob_true_pos = 0.6; /* Even numbers more likely to be true positives */
+ config.property_prob_true_neg = 0.4; /* Odd numbers less likely to be true positives */
+
+ /* Create lossless bloom filter with conditional hashing */
+ filter = lossless_bloom_create(&config);
+
+ /* Populate with "nelements" dummy strings */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
+ lossless_bloom_add_element(filter, (unsigned char *) element, strlen(element));
+ }
+
+ /* Test for elements that should be present (no false negatives expected) */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
+ if (!lossless_bloom_contains_element(filter, (unsigned char *) element, strlen(element)))
+ {
+ false_negatives++;
+ }
+ }
+
+ /* Test for elements that should NOT be present (no false positives expected) */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
+ if (lossless_bloom_contains_element(filter, (unsigned char *) element, strlen(element)))
+ {
+ false_positives++;
+ }
+ }
+
+ /* Get statistics */
+ lossless_bloom_get_stats(filter, &witness_entries, &total_bits, &bits_set, &num_blocks);
+ fill_ratio = lossless_bloom_prop_bits_set(filter);
+
+ /* Clean up */
+ lossless_bloom_free(filter);
+
+ /* Return results as text */
+ ereport(NOTICE,
+ (errmsg("Lossless Bloom Filter with Conditional Hashing Test Results:"),
+ errdetail("Elements: " INT64_FORMAT ", "
+ "False Positives: " INT64_FORMAT " (should be 0), "
+ "False Negatives: " INT64_FORMAT " (should be 0), "
+ "Witness Entries: " UINT64_FORMAT ", "
+ "Total Bits: " UINT64_FORMAT ", "
+ "Bits Set: " UINT64_FORMAT " (%.2f%%), "
+ "Blocks: %d",
+ nelements, false_positives, false_negatives,
+ witness_entries, total_bits, bits_set, fill_ratio * 100.0, num_blocks)));
+
+ PG_RETURN_BOOL(false_positives == 0 && false_negatives == 0);
+}
+
+/*
+ * Compare traditional vs lossless bloom filter performance
+ */
+PG_FUNCTION_INFO_V1(test_bloom_comparison);
+Datum
+test_bloom_comparison(PG_FUNCTION_ARGS)
+{
+ int64 nelements = PG_GETARG_INT64(0);
+ int bloom_work_mem = PG_GETARG_INT32(1);
+
+ /* Traditional bloom filter test */
+ bloom_filter *traditional_filter;
+ uint64 traditional_seed = pg_prng_uint64(&pg_global_prng_state);
+ int64 traditional_false_positives = 0;
+
+ /* Lossless bloom filter test */
+ lossless_bloom_filter *lossless_filter;
+ bloom_config config;
+ int64 lossless_false_positives = 0;
+
+ char element[MAX_ELEMENT_BYTES];
+ int64 i;
+ uint64 witness_entries, total_bits, bits_set;
+ int num_blocks;
+
+ /* Create traditional bloom filter */
+ traditional_filter = bloom_create(nelements, bloom_work_mem, traditional_seed);
+
+ /* Create lossless bloom filter */
+ memset(&config, 0, sizeof(bloom_config));
+ config.total_elems = nelements;
+ config.bloom_work_mem = bloom_work_mem;
+ config.seed = traditional_seed; /* Use same seed for fair comparison */
+ config.property_func = NULL;
+ lossless_filter = lossless_bloom_create(&config);
+
+ /* Populate both filters with same elements */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "i" INT64_FORMAT, i);
+ bloom_add_element(traditional_filter, (unsigned char *) element, strlen(element));
+ lossless_bloom_add_element(lossless_filter, (unsigned char *) element, strlen(element));
+ }
+
+ /* Test both filters for elements that should NOT be present */
+ for (i = 0; i < nelements; i++)
+ {
+ CHECK_FOR_INTERRUPTS();
+
+ snprintf(element, sizeof(element), "M" INT64_FORMAT, i);
+
+ /* Traditional filter - count false positives */
+ if (!bloom_lacks_element(traditional_filter, (unsigned char *) element, strlen(element)))
+ {
+ traditional_false_positives++;
+ }
+
+ /* Lossless filter - should have zero false positives */
+ if (lossless_bloom_contains_element(lossless_filter, (unsigned char *) element, strlen(element)))
+ {
+ lossless_false_positives++;
+ }
+ }
+
+ /* Get lossless filter statistics */
+ lossless_bloom_get_stats(lossless_filter, &witness_entries, &total_bits, &bits_set, &num_blocks);
+
+ /* Clean up */
+ bloom_free(traditional_filter);
+ lossless_bloom_free(lossless_filter);
+
+ /* Return comparison results */
+ ereport(NOTICE,
+ (errmsg("Bloom Filter Comparison Results:"),
+ errdetail("Elements tested: " INT64_FORMAT ", "
+ "Traditional Filter False Positives: " INT64_FORMAT " (%.2f%%), "
+ "Lossless Filter False Positives: " INT64_FORMAT " (%.2f%%), "
+ "Lossless Witness Entries: " UINT64_FORMAT ", "
+ "Lossless Blocks: %d",
+ nelements,
+ traditional_false_positives,
+ (double)traditional_false_positives / nelements * 100.0,
+ lossless_false_positives,
+ (double)lossless_false_positives / nelements * 100.0,
+ witness_entries, num_blocks)));
+
+ PG_RETURN_BOOL(lossless_false_positives == 0);
+}
+
+/*
+ * Demonstrate VSBBF block decomposition
+ */
+PG_FUNCTION_INFO_V1(test_vsbbf_blocks);
+Datum
+test_vsbbf_blocks(PG_FUNCTION_ARGS)
+{
+ int64 total_bits = PG_GETARG_INT64(0);
+ lossless_bloom_filter *filter;
+ bloom_config config;
+ uint64 witness_entries, actual_total_bits, bits_set;
+ int num_blocks;
+ StringInfoData result;
+
+ /* Initialize configuration */
+ memset(&config, 0, sizeof(bloom_config));
+ config.total_elems = 1000; /* Dummy value */
+ config.bloom_work_mem = (total_bits / 8 / 1024) + 1; /* Convert bits to KB */
+ config.seed = 12345;
+ config.property_func = NULL;
+
+ /* Create filter to see block decomposition */
+ filter = lossless_bloom_create(&config);
+
+ /* Get statistics */
+ lossless_bloom_get_stats(filter, &witness_entries, &actual_total_bits, &bits_set, &num_blocks);
+
+ /* Build result string */
+ initStringInfo(&result);
+ appendStringInfo(&result, "VSBBF Block Decomposition for " INT64_FORMAT " target bits:\n", total_bits);
+ appendStringInfo(&result, "Actual total bits: " UINT64_FORMAT "\n", actual_total_bits);
+ appendStringInfo(&result, "Number of blocks: %d\n", num_blocks);
+
+ /* Note: We can't access the internal block structure from here,
+ * but this demonstrates the concept */
+
+ /* Clean up */
+ lossless_bloom_free(filter);
+
+ PG_RETURN_TEXT_P(cstring_to_text(result.data));
+}
\ No newline at end of file
diff --git a/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.control b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.control
new file mode 100644
index 00000000000..1421e106914
--- /dev/null
+++ b/src/test/modules/test_lossless_bloomfilter/test_lossless_bloomfilter.control
@@ -0,0 +1,5 @@
+# test_lossless_bloomfilter extension
+comment = 'Test enhanced lossless bloom filter functionality'
+default_version = '1.0'
+module_pathname = '$libdir/test_lossless_bloomfilter'
+relocatable = true
\ No newline at end of file
--
2.39.5 (Apple Git-154)
0002-update-to-use-rational-hashing.-Still-working-out-so.patchapplication/octet-stream; name=0002-update-to-use-rational-hashing.-Still-working-out-so.patchDownload
From bc5a4751be5b535b3414fc12cdde4a7cb5c325e0 Mon Sep 17 00:00:00 2001
From: ross39 <Rheaney26@gmail.com>
Date: Thu, 3 Jul 2025 12:21:38 +0100
Subject: [PATCH 2/2] update to use rational hashing. Still working out some
performance details
---
src/backend/lib/bloomfilter.c | 26 ++++++++++++++++++++++++--
1 file changed, 24 insertions(+), 2 deletions(-)
diff --git a/src/backend/lib/bloomfilter.c b/src/backend/lib/bloomfilter.c
index 9875ec9aed8..0e79a07e284 100644
--- a/src/backend/lib/bloomfilter.c
+++ b/src/backend/lib/bloomfilter.c
@@ -400,8 +400,8 @@ lossless_bloom_create(bloom_config *config)
filter->blocks[0].size = filter->total_bits;
filter->blocks[0].offset = 0;
filter->blocks[0].k_rational = log(2.0) * filter->total_bits / config->total_elems;
- filter->blocks[0].k_floor = Max(1, Min((int)rint(filter->blocks[0].k_rational), MAX_HASH_FUNCS));
- filter->blocks[0].k_fractional = 0.0; /* Disable fractional hashing for speed */
+ filter->blocks[0].k_floor = Max(1, Min((int)floor(filter->blocks[0].k_rational), MAX_HASH_FUNCS));
+ filter->blocks[0].k_fractional = filter->blocks[0].k_rational - filter->blocks[0].k_floor; /* Enable fractional hashing */
/* Allocate bitset */
bitset_bytes = (filter->total_bits + 7) / 8;
@@ -498,6 +498,17 @@ lossless_bloom_add_element(lossless_bloom_filter *filter, unsigned char *elem, s
hashes[i] = x;
}
+ /* RATIONAL HASHING: Apply fractional hash function probabilistically */
+ if (filter->blocks[0].k_fractional > 0.0 && k_hash_funcs < MAX_HASH_FUNCS)
+ {
+ if (apply_rational_hashing(filter->blocks[0].k_fractional, base_hash))
+ {
+ x += y;
+ hashes[k_hash_funcs] = x;
+ k_hash_funcs++;
+ }
+ }
+
/* OPTIMIZATION: Fast bit setting with bitwise operations */
for (i = 0; i < k_hash_funcs; i++)
{
@@ -551,6 +562,17 @@ lossless_bloom_contains_element(lossless_bloom_filter *filter, unsigned char *el
hashes[i] = x;
}
+ /* RATIONAL HASHING: Apply fractional hash function probabilistically */
+ if (filter->blocks[0].k_fractional > 0.0 && k_hash_funcs < MAX_HASH_FUNCS)
+ {
+ if (apply_rational_hashing(filter->blocks[0].k_fractional, base_hash))
+ {
+ x += y;
+ hashes[k_hash_funcs] = x;
+ k_hash_funcs++;
+ }
+ }
+
/* OPTIMIZATION: Fast bit checking with bitwise operations */
for (i = 0; i < k_hash_funcs; i++)
{
--
2.39.5 (Apple Git-154)
Hello,
This is an interesting proposal, thanks for posting.
On Jul 3, 2025, at 11:00, Ross Heaney <rheaney26@gmail.com> wrote:
Proposed Improvements
Instead we can relax the assumption that it must be an integer value for k. To do this we split the k value into an integer and a rational part. Call this k and r. So in the example above where we calculated k to be equal to 2.3 this would mean k = 2 and r = 0.3. We always use k hash functions but we apply a third hash function 30% of the time(corresponding to r = 0.3 in this case). This is done deterministically so the same element always gets the same treatment(keeps the bloom filter promise of no false negatives). The paper has more information but this is the gist of the rational part of the bloom filter.
Intuitively this makes sense to me. I skimmed the paper and my eyes rolled up into my head, but the basic idea certainly seems sound. I’m curious about the "Variably-Sized Block Bloom filter,” bit, though, which I don’t follow and doesn’t seem to be part of your proposal.
However we can take this further and look to make the bloom filter lossless. Using the rational part described above we've given ourselves some wriggle room so to speak. We can compliment the rational 'lossy' bloom filter with an additional array called a witness. This allows us to reconstruct the original input, which just means a false positive rate of 0.
I have a bit of a harder time with the witness. I get that the size is limited, so it won’t grow to ginormous size based on the number of entries, but don’t understand how it could be so small (adding around 25% of additional memory in your example) unless it, too, accepts a certain false positivity rate. In which case I wonder whether there is a comparable reduction in the false positive rate by simply increasing the size of the bloom filter itself by 25%.
But since you suggest that the false positive rate can be reduced to effectively zero, I must be missing something. I’d be curious to read more on this pattern.
Best,
David
Hi David,
I appreciate you taking the time to explore this. I plan to work on getting
the patches more production ready state and do some more benchmarking. I
also appreciate you highlighting that I did not reply to all in my previous
email. This was an oversight on my part. I will paste my message below so
that others can see.
Your observation that the witness adds "around 25% of additional memory" is
correct. However, the crucial distinction is that the witness data
structure itself does not incur a false positive rate. Its fundamental
purpose is to enable lossless reconstruction of the original input. A
standard Bloom filter is inherently lossy due to its probabilistic nature;
it can produce false positives (reporting an element as present when it is
not) but never false negatives. The witness acts as a definitive resolver
for these false positives. For any element that the Bloom filter might
indicate as present (i.e., it passes the Bloom filter test), the witness
stores a single bit that unequivocally declares whether that element is a
true positive (originally in the set) or a false positive (not originally
in the set). The witness does not store information for every element in
the entire universe. Instead, it only needs to store a bit for each element
that passes the Bloom filter test. This set of elements comprises all the
true positives (elements that were actually inserted) and all the false
positives (elements not inserted but for which the Bloom filter incorrectly
returns a positive). This establishes a direct correlation between the
witness size and the false positive rate.
In effect this is a compression scheme and a pretty decent one at that. I
have posted on hacker news about this scheme and I have a repo
<https://github.com/ross39/new_bloom_filter_repo.> where I am using it to
compress video(a different topic not related to postgres) .
I'll publish this as a paper at some point. As with any compression scheme
there are some caveats. The ratio of true positives to the universe of
possible values must be below 0.32 for it to be effective. For example in
postgres, suppose we use a bloom filter to query indexes. Therefore the
universe of possible values would be all possible 64 bit integers. The true
values would be the values of the actual indexes we wish to store in the
bloom filter. Therefore the fact that the ratio must not exceed 0.32 isn't
that big of a deal given the massive number a 64 bit integer can hold.
I hope this maybe explains the witness data structure a bit better.
Feel free to ask me any further questions. I would be more than happy to
collaborate on this patch or any future patches.
Regards,
Ross
On Fri, Jul 4, 2025 at 3:02 PM David E. Wheeler <david@justatheory.com>
wrote:
Show quoted text
Hi Ross,
I hope to put some time into exploring this in the next week, but wanted
to point out here, in case you hadn’t noticed, that your reply went only to
me and not pgsql-hackers. The convention on that list is to reply to all
for most messages unless people need/want to sidebar on a topic. Not sure
if that’s what you intended, but I suspect other people would find your
reply interesting.Best,
David
On Jul 3, 2025, at 16:44, Ross Heaney <rheaney26@gmail.com> wrote:
Hi,
Your observation that the witness adds "around 25% of additional memory"
is correct. However, the crucial distinction is that the witness data
structure itself does not incur a false positive rate. Its fundamental
purpose is to enable lossless reconstruction of the original input. A
standard Bloom filter is inherently lossy due to its probabilistic nature;
it can produce false positives (reporting an element as present when it is
not) but never false negatives. The witness acts as a definitive resolver
for these false positives. For any element that the Bloom filter might
indicate as present (i.e., it passes the Bloom filter test), the witness
stores a single bit that unequivocally declares whether that element is a
true positive (originally in the set) or a false positive (not originally
in the set). The witness does not store information for every element in
the entire universe. Instead, it only needs to store a bit for each element
that passes the Bloom filter test. This set of elements comprises all the
true positives (elements that were actually inserted) and all the false
positives (elements not inserted but for which the Bloom filter incorrectly
returns a positive). This establishes a direct correlation between the
witness size and the false positive rate.In effect this is a compression scheme and a pretty decent one at that.
I have posted on hacker news about this scheme and I have a repo where I am
using it to compress video(a different topic not related to postgres) .I'll publish this as a paper at some point. As with any compression
scheme there are some caveats. The ratio of true positives to the universe
of possible values must be below 0.32 for it to be effective. For example
in postgres, suppose we use a bloom filter to query indexes. Therefore the
universe of possible values would be all possible 64 bit integers. The true
values would be the values of the actual indexes we wish to store in the
bloom filter. Therefore the fact that the ratio must not exceed 0.32 isn't
that big of a deal given the massive number a 64 bit integer can hold.I hope this maybe explains the witness data structure a bit better.
Regards,
RossOn Thu, Jul 3, 2025 at 4:59 PM David E. Wheeler <david@justatheory.com>
wrote:
Hello,
This is an interesting proposal, thanks for posting.
On Jul 3, 2025, at 11:00, Ross Heaney <rheaney26@gmail.com> wrote:
Proposed Improvements
Instead we can relax the assumption that it must be an integer valuefor k. To do this we split the k value into an integer and a rational part.
Call this k and r. So in the example above where we calculated k to be
equal to 2.3 this would mean k = 2 and r = 0.3. We always use k hash
functions but we apply a third hash function 30% of the time(corresponding
to r = 0.3 in this case). This is done deterministically so the same
element always gets the same treatment(keeps the bloom filter promise of no
false negatives). The paper has more information but this is the gist of
the rational part of the bloom filter.Intuitively this makes sense to me. I skimmed the paper and my eyes
rolled up into my head, but the basic idea certainly seems sound. I’m
curious about the "Variably-Sized Block Bloom filter,” bit, though, which I
don’t follow and doesn’t seem to be part of your proposal.However we can take this further and look to make the bloom filter
lossless. Using the rational part described above we've given ourselves
some wriggle room so to speak. We can compliment the rational 'lossy' bloom
filter with an additional array called a witness. This allows us to
reconstruct the original input, which just means a false positive rate of 0.I have a bit of a harder time with the witness. I get that the size is
limited, so it won’t grow to ginormous size based on the number of entries,
but don’t understand how it could be so small (adding around 25% of
additional memory in your example) unless it, too, accepts a certain false
positivity rate. In which case I wonder whether there is a comparable
reduction in the false positive rate by simply increasing the size of the
bloom filter itself by 25%.But since you suggest that the false positive rate can be reduced to
effectively zero, I must be missing something. I’d be curious to read more
on this pattern.Best,
David
Import Notes
Reply to msg id not found: 8B600F84-4E89-4A5C-B888-9F5BD0188F05@justatheory.com
On Fri, 4 Jul 2025 at 17:43, Ross Heaney <rheaney26@gmail.com> wrote:
The witness does not store information for every element in the entire universe. Instead, it only needs to store a bit for each element that passes the Bloom filter test.
I think this has a major flaw, in that it is nearly impossible to
guarantee zero false positives in practice using the scheme you
describe. Assuming 1 bit for each element that passes the main Bloom
filter test, the witness list needs to be sized to O(universe *
fp_rate) to accomodate a bit for all passed elements (with some margin
to either direction to account for variability in the practical Bloom
filter false positive rate).
When you store 32-bit integers, this would be ~2^22 bits for a false
positive rate of 1/1024. Storing 64-bit integers at the same fp_rate
would require ~2^54 bits in this witness list. Assuming the bloom
filter itself contains only N elements, and the size of a bloom filter
is proportional to -log(fp_rate) * N, which for any complex data type
is orders of magnitude smaller than the witness list.
The bloom filter is orders of magnitude smaller, because this witness
list only works when we assume that there is no pidgeon hole issue
with the values stored, that we're only looking for small integer
types, or hashes and don't mind hash collisions and the related false
positives.
It is quite possible (guaranteed even!) that two different strings
hash to exactly the same values when using a fixed-size hash output,
like the hash methods used in PostgreSQL. A witness list that uses
your described method to guarantee no false positives even for strings
would have to be sized to the order of 2^(8 * 2^30), give or take a
few zeroes, to account for all possible string values in PostgreSQL.
That just isn't practical.
Actually, after looking at your 0001 patch, it looks like your
'witness' is not a list of both true and false positives, but a
hashmap of only the true positive values, i.e. the list of inserted
values. That does indeed make the combined data structure mostly
"lossless", but
1.) this adds O(n_inserted) overhead with a large constant multiplier
on n_inserted, as hash maps have about 24B/192bits of overhead per
entry, which is probably an order of magnitude more than the
approximately O(-log(p)) of the bloom filter itself; and
2.) this won't solve the pidgeon hole issue with trying to use a bloom
filter on strings or other data types that might have more than the
kept 64 bits of entropy.
So, I'm sorry, but I don't think this is a lossless Bloom filter.
Kind regards,
Matthias van de Meent
Databricks
Hi,
I appreciate you taking the time to leave feedback. I would like to address
your points
I think this has a major flaw, in that it is nearly impossible to
guarantee zero false positives in practice using the scheme you
describe. Assuming 1 bit for each element that passes the main Bloom
filter test, the witness list needs to be sized to O(universe *
fp_rate) to accomodate a bit for all passed elements (with some margin
to either direction to account for variability in the practical Bloom
filter false positive rate).
When you store 32-bit integers, this would be ~2^22 bits for a false
positive rate of 1/1024. Storing 64-bit integers at the same fp_rate
would require ~2^54 bits in this witness list. Assuming the bloom
filter itself contains only N elements, and the size of a bloom filter
is proportional to -log(fp_rate) * N, which for any complex data type
is orders of magnitude smaller than the witness list.
You've highlighted an important point. I was quite lazy in how I defined
the universe of possible values to be. I defined it to be all possible 64
bit values and so your calculation is correct. I have been primarily using
this scheme to compress video where the universe of possible values is much
much smaller and I did not fully think through the implications of allowing
the universe of possible values to be that large.
After thinking about this a bit more I don't think it's practical at all to
use this scheme in PostgreSQL. I still think the ideas from the paper
<https://arxiv.org/abs/2502.02193> around using a rational number of hash
functions is worthwhile and I would be happy to provide a patch for this
Kind regards,
Ross
On Fri, Jul 4, 2025 at 6:26 PM Matthias van de Meent <
boekewurm+postgres@gmail.com> wrote:
Show quoted text
On Fri, 4 Jul 2025 at 17:43, Ross Heaney <rheaney26@gmail.com> wrote:
The witness does not store information for every element in the entire
universe. Instead, it only needs to store a bit for each element that
passes the Bloom filter test.I think this has a major flaw, in that it is nearly impossible to
guarantee zero false positives in practice using the scheme you
describe. Assuming 1 bit for each element that passes the main Bloom
filter test, the witness list needs to be sized to O(universe *
fp_rate) to accomodate a bit for all passed elements (with some margin
to either direction to account for variability in the practical Bloom
filter false positive rate).
When you store 32-bit integers, this would be ~2^22 bits for a false
positive rate of 1/1024. Storing 64-bit integers at the same fp_rate
would require ~2^54 bits in this witness list. Assuming the bloom
filter itself contains only N elements, and the size of a bloom filter
is proportional to -log(fp_rate) * N, which for any complex data type
is orders of magnitude smaller than the witness list.The bloom filter is orders of magnitude smaller, because this witness
list only works when we assume that there is no pidgeon hole issue
with the values stored, that we're only looking for small integer
types, or hashes and don't mind hash collisions and the related false
positives.
It is quite possible (guaranteed even!) that two different strings
hash to exactly the same values when using a fixed-size hash output,
like the hash methods used in PostgreSQL. A witness list that uses
your described method to guarantee no false positives even for strings
would have to be sized to the order of 2^(8 * 2^30), give or take a
few zeroes, to account for all possible string values in PostgreSQL.
That just isn't practical.Actually, after looking at your 0001 patch, it looks like your
'witness' is not a list of both true and false positives, but a
hashmap of only the true positive values, i.e. the list of inserted
values. That does indeed make the combined data structure mostly
"lossless", but
1.) this adds O(n_inserted) overhead with a large constant multiplier
on n_inserted, as hash maps have about 24B/192bits of overhead per
entry, which is probably an order of magnitude more than the
approximately O(-log(p)) of the bloom filter itself; and
2.) this won't solve the pidgeon hole issue with trying to use a bloom
filter on strings or other data types that might have more than the
kept 64 bits of entropy.So, I'm sorry, but I don't think this is a lossless Bloom filter.
Kind regards,
Matthias van de Meent
Databricks