Efficient uniqueness check on large dataset

Question

I'm refactoring a health monitoring system which requires that certain attributes of an Entity have to be unique across the system. The attributes of an Entity are configurable by the end-user and the user can pick one or more attributes to be unique (either "universally" unique or unique across a geographical area).

Currently, the solution performs very poorly when looking up these unique values (we use Postgres). By using Postgres partial indexes mitigates the performance issue,but, on large datasets (500 millions rows, which is not unusual) the performance is not acceptable.

One solution I'm considering is to hash the attribute + value using a trigger before INSERT and UPDATE. The trigger would check this "hashes" unique-index before allowing the INSERT. If the hash is missing, then it inserts. Otherwise it blocks the operation.

Is there a better solution to this problem, considering the size of the dataset?

Edit:

Following @JimmyJames suggestion (use a Bloom index), I did run some tests to verify which index is faster for a direct lookup. Env: Postgres 12, 64Gb ram, 16 cores AMD

First I have created 500 millions pseudo-hashes:

insert into bloom_filter (
   hash
)
select
    gen_random_uuid()
from generate_series(1, 500000000) s(i);

Created a b-tree index:

CREATE INDEX idx_btree_bar on bloom_filter (hash);

Index creation took ~19 min.

A simple lookup takes 24ms. (milliseconds)

select count(*) from bloom_filter where hash= '99c2b46f-cc36-4249-ae36-f16f047f2962';

Then, I have killed the b-tree index, and created a bloom index:

CREATE EXTENSION bloom;

CREATE INDEX idx_bloom_hash ON bloom_filter USING bloom(hash)
WITH (length=64, col1=4);

Index creation took: 2m 54s

Same lookup query as above takes 1.536 sec., which is significantly more than a b-tree index. Not surprisingly, an hash index has a similar look-up speed of a b-tree index.

Answer 1

One solution I'm considering is to hash the attribute + value using a trigger before INSERT and UPDATE. The trigger would check this "hashes" unique-index before allowing the INSERT. If the hash is missing, than it inserts it otherwise it blocks the operation.

You should probably consider using a Bloom filter. This is an approach that will tell you for sure if an element is not in the set. It cannot tell you for sure if the element is in the set. Here's a good interactive page for learning more about the concept.

Postgres has support for bloom indexes. I would encourage you to explore this before building your own solution.

Answer 2

If the hash is missing, than it inserts it otherwise it blocks the operation.

Meaning that if the hash (of a set of attribute values) already exists then reject the operation without further consideration?

Are you sure that's what you want? Hashes aren't unique: very different values could end up with the same hash. I would think rejecting an operation because its hash happened to match an others is not actually what you want.

If the hash does not collide then that set of values is definitely unique.

If the hash does collide then do a secondary check to see if the current entity values actually match any of the (hopefully few) entities with the same hash.

Also consider the trade-off between cost of creating larger-more unique hashes compared to the cost of this secondary check when a hash collides.

Additionally:

We'll say a "key" is a user-defined set of attributes values which must be unique.

You don't need to include the attribute names in the hash, just hash the values in a consistent way.

If there can be multiple keys per entity then you'll need a different hash for each.

If a new key is introduced (including if a key changed) then you'll need to re-compute the hash for this new key for each entity; Probably an uncommon scenario but still something to consider.