Re: Bloom Filter indexes?

From: Oleg Bartunov <oleg(at)sai(dot)msu(dot)su>
To: Gregory Maxwell <gmaxwell(at)gmail(dot)com>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Bloom Filter indexes?
Date: 2005-05-29 06:26:09
Message-ID: Pine.GSO.4.62.0505291024040.1721@ra.sai.msu.su
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

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

In response to

Browse pgsql-hackers by date

  From Date Subject
Next Message Michael Paesold 2005-05-29 07:37:54 Re: [HACKERS] patches for items from TODO list
Previous Message Tom Lane 2005-05-29 04:25:22 Re: unsafe use of hash_search(... HASH_ENTER ...)