Re: Bloom Filter indexes?

We use it in contrib/intarray for set operations and contrib/tsearch2 for
full text search. The problem is how to store it to provide efficient
operations. We use RD-tree as a storage.

Oleg
On Sat, 28 May 2005, Gregory Maxwell wrote:

> Has any thought been given to adding bloom filter indexes to PostgreSQL?
>
> A bloom index would be created on a column, and could then be used to
> accelerate exact matches where it is common that the user may query
> for a value that doesn't exist. For example, with the query select
> userid from user_table where name="notauser", the failure could be
> returned instantly, in most cases.
>
> A bloom filter index could be used to accelerate joins, esp full outer joins.
>
> Insertions into a bloom filter are very cheap. Updates could be done
> as an insert. Deletes are expensive (either you make a refcounted
> filter or you regenerate the filter). However, since bloom filters
> have false positives, it would be acceptable to regenerate the filter
> during a vacuum if there have been entries deleted or updated. The
> filter could be resized at vacuum time based on statistics gathered
> during execution.
>
> It would also be useful to have an array bloom index: store a bloom
> filter per record for an arrayed field, as well as the bloom filter
> for all records. This would allow membership tests for a field
> containing large arrays to happen very quickly. Perhaps useful for GIS
> and full text indexing applications.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 5: Have you checked our extensive FAQ?
>
> http://www.postgresql.org/docs/faq
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83