Re: Bloom Indexes - bit array length and the total number of bits (or hash functions ?? ) !

> But the 2 direct questions i have are :
>
> 1. What is the structure of the Bloom Index ? Can you please let me know
> what are the fields of a Bloom Index ? Is it just the Item Pointer
> and BloomSignatureWord ?

I'm not sure of Postgres actual implementation, I have just looked at the
underlying hash functions implementation.

> When i describe my bloom index it looks like following.
>
> postgres=# \d+ foo.idx_bloom_bar
> Index "foo.idx_bloom_bar"
> Column | Type | Key? | Definition | Storage | Stats target
> ---------+---------+------+------------+---------+--------------
> id | integer | yes | id | plain |
> dept | integer | yes | dept | plain |
> id2 | integer | yes | id2 | plain |
> id3 | integer | yes | id3 | plain |
> id4 | integer | yes | id4 | plain |
> id5 | integer | yes | id5 | plain |
> id6 | integer | yes | id6 | plain |
> zipcode | integer | yes | zipcode | plain |
> bloom, for table "foo.bar"

The bloom index associates a signature, i.e. a bitfield the size of which
is specified by the parameter "length", to the tuple location. The
bitfield is computed by hashing the value of columns which are listed
above in the index definition. The many values are somehow compressed into
the small signature.

> Options: length=64, col1=4, col2=4, col3=4, col4=4, col5=4, col6=4, col7=4,
> col8=4

I doubt that these parameters are good. The is no point to include a
unique column into a bloom index. If you look at my blog, the number of
bits associated to each field should depend on the expected selectivity,
which depends on the entropy of each field and the signature size. The
column entropy can be computed with a query.

> 2. If we are storing just one signature word per row, how is this
> aggregated for all column values of that row into one signature in high
> level ?

The aggregation, if performed, is not very useful in practice because it
can only be effective on a few (first) bits, which are randomly computed
anyway and the value of the query is not likely to hit them.

Fundamentally all bitfields are scanned to extract which tuples are
possibly of interest, i.e. are not excluded by the index. The "full scan"
of the bloom index is not a bad thing if it is much smaller than the table
itself.

> For example, if length = 64, does it mean that a bit array of 64 bits is
> generated per each row ?

Yes.

> If col1=4, does it mean the value of col1 is passed to 4 hash functions
> that generate 4 positions that can be set to 1 in the bit array ?

Yes.

Try to apply the formula in the blog to see what you get for your
parameters, but it is likely to be < 4.

--
Fabien.