Thread: Bloom Filter indexes?

Bloom Filter indexes?

From
Gregory Maxwell
Date:
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.


Bloom Filter indexes?

From
Gregory Maxwell
Date:
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.


Re: Bloom Filter indexes?

From
Oleg Bartunov
Date:
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@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83