Re: Bloom Filter improvements in postgesql - Mailing list pgsql-hackers

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,
> Ross
>
> On 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 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
>