2

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.

2
  • 1
    What hash algorithm are you considering, and what is the bit size of its output? Mar 13, 2020 at 21:53
  • I was considering sha-256, mostly to avoid collisions Mar 14, 2020 at 14:28

2 Answers 2

5

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.

5
  • Cool, sounds like a built-in way to get the same benefits of a hash key.
    – xtratic
    Mar 13, 2020 at 14:58
  • @xtratic A bloom filter uses hash functions at it's core. They tend to provide a good space/time tradeoff for large sets.
    – JimmyJames
    Mar 13, 2020 at 15:09
  • Thanks, I haven't thought about using a Bloom filter. I'll build a small prototype with 1 billion values to check the performances of a Bllom filter vs. other type of filters. Mar 13, 2020 at 15:21
  • @JimmyJames I figured it might, that's certainly convenient for situations where it fits, like this one. As you say, it's definitely preferable over rolling-your-own.
    – xtratic
    Mar 13, 2020 at 17:09
  • 1
    @LucianoFiandesio One thing I realized when doing some math around this is that you will want to have more bits in your filter than you have items. Otherwise your expected false-positive rate goes to 100% (per pigeon hole theorem). As you increase the number of hash functions, this extra headroom becomes more important.
    – JimmyJames
    Mar 13, 2020 at 17:24
0

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.

4
  • Quite a bit might depend on whether the most-likely outcome is that "it will be allowed" vs "it will be refused." If you can develop some kind of hash-string that can be used as a sentinel, indicating by its presence or by its absence that you don't have to look any farther, then "that would be a win" because it could drastically cut down on the number of time-consuming further checks that you would have to do. I'd definitely pursue this line of reasoning ... the hash isn't tasked with providing the answer but rather with telling you if you need to look harder for it. Mar 13, 2020 at 14:37
  • @MikeRobinson Exactly, a unique hash would means it's definitely "allowed". But even for the "refused" outcome the hash will help a good bit. I'll update my answer to explain in more detail.
    – xtratic
    Mar 13, 2020 at 14:56
  • @xtratic good point about hash collisions. A couple of considerations: speed is not the most relevant thing here, since insert and update happen asyncronously, so potentially I could use a "slower" but virtually collision free hashing algo (such as SHA-256) Mar 13, 2020 at 15:25
  • @LucianoFiandesio Yep, I guessed you might want to go for a larger hash and get fewer collisions. I expect you might also be able to configure a bloom index (mentioned by JimmyJames) to use longer hashes. Of course don't just go off guesses, tune properly if you really do need the performance boost as you say.
    – xtratic
    Mar 13, 2020 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.