• Andres Freund's avatar
    Add Bloom filter implementation. · 51bc2717
    Andres Freund authored
    A Bloom filter is a space-efficient, probabilistic data structure that
    can be used to test set membership.  Callers will sometimes incur false
    positives, but never false negatives.  The rate of false positives is a
    function of the total number of elements and the amount of memory
    available for the Bloom filter.
    
    Two classic applications of Bloom filters are cache filtering, and data
    synchronization testing.  Any user of Bloom filters must accept the
    possibility of false positives as a cost worth paying for the benefit in
    space efficiency.
    
    This commit adds a test harness extension module, test_bloomfilter.  It
    can be used to get a sense of how the Bloom filter implementation
    performs under varying conditions.
    
    This is infrastructure for the upcoming "heapallindexed" amcheck patch,
    which verifies the consistency of a heap relation against one of its
    indexes.
    
    Author: Peter Geoghegan
    Reviewed-By: Andrey Borodin, Michael Paquier, Thomas Munro, Andres Freund
    Discussion: https://postgr.es/m/CAH2-Wzm5VmG7cu1N-H=nnS57wZThoSDQU+F5dewx3o84M+jY=g@mail.gmail.com
    51bc2717
README 961 Bytes