Re: bloom filter indexes?

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