Re: bloom filter indexes?

From: Jeff Davis <pgsql(at)j-davis(dot)com>
To: Mason Hale <masonhale(at)gmail(dot)com>
Cc: pgsql-general <pgsql-general(at)postgresql(dot)org>
Subject: Re: bloom filter indexes?
Date: 2008-06-03 17:04:18
Message-ID: 1212512658.31688.12.camel@dogma.ljc.laika.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

On Tue, 2008-06-03 at 09:43 -0500, Mason Hale wrote:
> I've been working on partitioning a rather large dataset into multiple
> tables. One limitation I've run into the lack of cross-partition-table
> unique indexes. In my case I need to guarantee the uniqueness of a
> two-column pair across all partitions -- and this value is not used to
> partition the tables. The table is partitioned based on a insert date
> timestamp.

You're looking for a constraint across tables.

> To check the uniqueness of this value I've added an insert/update
> trigger to search for matches in the other partitions. This trigger is
> adding significant overhead to inserts and updates.

Do you lock all of the tables before doing the check? If not, then you
have a race condition.

> This sort of 'membership test' where I need only need to know if the
> key exists in the table is a perfect match for bloom filter. (see:
> http://en.wikipedia.org/wiki/Bloom_filter)

This is more of an implementation detail. Is a bloom filter faster than
BTree in your case?

> The Bloom filter can give false positives so using it alone won't
> provide the uniqueness check I need, but it should greatly speed up
> this process.

False positives are OK, that's what RECHECK is for.

It's possible this index strategy will be better for your case.
However, I think what you really want is some kind of multi-table
primary key. Have you considered storing the key in its own two-column
table with a UNIQUE index and having the partitions reference it?

Regards,
Jeff Davis

In response to

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Mason Hale 2008-06-03 18:06:15 Re: bloom filter indexes?
Previous Message Steve Crawford 2008-06-03 16:38:28 pg_dump: invalid memory alloc request size 4294967293