Re: WIP: BRIN bloom indexes

Hi,

On 10/27/2017 05:22 PM, Sokolov Yura wrote:
>
> Hi, Tomas
>
> BRIN bloom index is a really cool feature, that definitely should be in
> core distribution (either in contrib or builtin)!!!
>
> Small suggestion for algorithm:
>
> It is well known practice not to calculate whole hash function for every
> point, but use double hashing approach.
> Example of proving double hashing approach for bloom filters:
> https://www.eecs.harvard.edu/~michaelm/postscripts/rsa2008.pdf
>
> So, instead of:
>     for (i = 0; i < filter->nhashes; i++)
>     {
>         /* compute the hashes with a seed, used for the bloom filter */
>         uint32 h = ((uint32)DatumGetInt64(hash_uint32_extended(value,
> i))) % filter->nbits;
>
>         /* set or check bit h */
>     }
>
> such construction could be used:
>     /* compute the hashes, used for the bloom filter */
>     uint32 big_h = ((uint32)DatumGetInt64(hash_uint32_extended(value, i)));
>     uint32 h = big_h % filter->nbits;
>     /* ensures d is never >= filter->nbits */
>     uint32 d = big_h % (filter->nbits - 1);
>
>     for (i = 0; i < filter->nhashes; i++)
>     {
>         /* set or check bit h */
>
>         /* compute next bit h */
>         h += d++;
>         if (h >= filter->nbits) h -= filter->nbits;
>         if (d == filter->nbits) d = 0;
>     }
>
> Modulo of one 64bit result by two coprime numbers (`nbits` and `nbits-1`)
> gives two good-quality functions usable for double hashing.
>

OK, thanks for the suggestion.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services