Re: Bloom Filter improvements in postgesql

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(at)justatheory(dot)com>
wrote:

> 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(at)gmail(dot)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,
> > Ross
> >
> > On Thu, Jul 3, 2025 at 4:59 PM David E. Wheeler <david(at)justatheory(dot)com>
> wrote:
> > Hello,
> >
> > This is an interesting proposal, thanks for posting.
> >
> > On Jul 3, 2025, at 11:00, Ross Heaney <rheaney26(at)gmail(dot)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
> >
>
>