Delegated UNIQUENESS in Postgres

10 min readDec 21, 2021

Second helper-table might not that shiny but still uniq © u/Xanice

What’s inside

Multiple approaches to objects ‘optimistic’ creation
Delegating UNIQUE constraints to a helper table using uuid VS text column types.
Playing HOT and ‘cold’ on UPDATE requests
INSERT or UPDATE — should you pay 1 to save 14?

Uniqueness flavours

Uniqueness is a usual feature for an application and business logic to have. I want to separate some handy flavours of a uniqueness:

mutable uniqueness: a uniqueness which should be enforced against updateable column, for instance a changeable user nickname.
immutable uniqueness: a uniqueness applied against immutable column. For instance a registration with an email, it should be unique across all users, and let say user cannot change it after. So a backend needs to apply unique constrant only once: during record creation.
short term uniqueness: a uniqueness applied only for a limited ‘sliding’ subset data, usually the latest records. For instance, optimistic objects creation resolving a race condition on a back-end. Let say you have a mobile application with an ability to create some kind of objects without being online ( even being online, but retrying after unexpected failure ). User definitely doesn’t want to experience a multiple entities creation whenever network or service hiccups, that is definitely a bad UX you want to avoid. So back-end needs some kind of uuid based uniqueness at least for a short time period, untill the user application gets a confirmation and the pkey id of a freshly created record.

Rem. All of these flavours could be defined without strict conditions, but with some weights numbers. For instance, we can allow updates but the ratio between create and update operations is so small that we actually facing ‘immutable uniqueness’ case, rather than normal ‘mutable’ uniqueness. And a ‘short term uniqueness’ is like a ‘create-only uniqueness’ but over a limited set of last N records.

Unique index

The easiest way to handle uniqueness over an attribute or a combination of attributes is to introduce a unique index over them.

Any blazing fast triggers-based check or not so blazing fast ORM validation callback cannot deliver 100% solid uniqueness guarantee, because ORM or trigger validation could fall into the race condition.

But adding an index comes with a price: its slows updates and insertions, the more indexes you add — the slower insert and update will become, even adding 1 index can cost you ~40% UPDATEs tps performance.

The best UPDATE performance you can get

Postgres has one cool performance booster for UPDATE operations, it’s a heap-only tuples update. There are two conditions for HOT updates to be used:

there must be enough space in the block containing the updated row
there is no index defined on any column whose value is modified

The later refers not only to the values of indexed columns but also the conditional columns for partial indexes:

HOT solves this problem for a restricted but useful special case: where a tuple is repeatedly updated in ways that do not change its indexed columns. (Here, “indexed column” means any column referenced at all in an index definition, including for example columns that are tested in a partial-index predicate but are not stored in the index.)

UPDATE operation performance in Postgres follows the HOT-updates ratio, the higher it is, the faster your UPDATEs will be, and vice-versa, lower HOT-updates ratio — slower the UPDATEs.

So the idea of the speeding up UPDATEs is simple:

do it HOT if you can
have lesser indexes whenever it’s not-HOT

Delegated uniqueness, the idea

If we don’t have a normal mutable uniqueness demand, but ‘immutable’ or ‘short-term’ uniqueness cases, we can extract the unique condition to an external helper table with an unique index over extracted values. We can do this using a trigger executed during an INSERT operation on an original table. In other words we are delegating the unique constraint to the helper-table and its unique index*.

In terms of unique constraints this approach works the same way unique index over original table would do, but we can skip unique index UPDATEs via trigger conditions, because for our special uniqueness cases we will hit the trigger only on INSERT operation.

Rem. This approach could be applied not only to unique indexes of course. You could delegate append-only indexes externally if you want to boost non-HOT UPDATEs, but this idea would need some other math and justification to be done.

The experiment

I’m gonna measure two kinds of triggers vs indexes: two elements array transform to string + text index, and direct insert of uuid + uuid index.

I’ll measure INSERT overhead of the different triggers calls VS unique indexes over the same data in place
I’ll measure costs for non-HOT updates for base table configuration and for +1 unique index of text and uuid types

Rem. I’ll use schema from my original project with a partially filled data.

Base table configuration stats

4M records splitted 50/50 between dialogs and multi-user chats
1 int64 pkey index
1 non-pkey index over int64 column
table fillfactor is 70%
average record size 830 bytes, max 2077, min 360 ( so its a ~7 records per page )
PostgreSQL v11.13

Text type uniqueness example: unique dialog between two users

Any messenger like whatsup or telegram with dialogs and multi-user chats should apply unique constraint for direct messaging chats a.k.a. dialogs.

The original table has an array column user_ids for storing participants ids. For records with type ‘Dialog’ user_ids will have only two ids for which we need to ensure uniqueness across all records of ‘Dialog’ type.

This constraint prevents a situation whenever two user starting direct messaging at the same time and end up with two direct-chats created in parallel.

Here is a schema for the delegated uniqueness trial:

-- 'two elements array to string' deterministic conversion function 
CREATE OR REPLACE FUNCTION user_ids_to_str( user_ids anyarray ) RETURNS text AS $$
   BEGIN
        RETURN CASE WHEN( user_ids[1] > user_ids[2]) 
          THEN user_ids[1]::text || '_' || user_ids[2]::text 
          ELSE user_ids[2]::text || '_' || user_ids[1]::text END;
    END
$$ LANGUAGE plpgSQL;
-- Helper table schema. No pkey, only one text column + unique index
CREATE TABLE dialog_uniqs ( uniq_str text );CREATE UNIQUE INDEX index_dialog_uniqs_on_uuid ON dialog_uniqs 
  USING btree (uniq_str);-- a trigger function to 'delegate' uniq constraint to the helper tableCREATE OR REPLACE FUNCTION dlg_uniqs_trg() RETURNS trigger AS $$
BEGIN 
  INSERT INTO dialog_uniqs VALUES ( user_ids_to_str(NEW.user_ids) );
  RETURN NEW;
END $$ LANGUAGE plpgSQL;CREATE TRIGGER dlg_uniqs_trg BEFORE INSERT ON chats 
  FOR EACH ROW WHEN( NEW.type = 'Dialog' )
  EXECUTE FUNCTION dlg_uniqs_trg();-- an index for dialogs uniqueness CREATE UNIQUE INDEX IF NOT EXISTS dlg_user_ids_index 
  ON chats USING btree(user_ids_to_str(user_ids)) 
  WHERE( type='Dialog' );

uuid type example: optimistic singleton creation

‘Optimistic’ entities creation, whenever front-end creates an object first, and then tries to create it using api. The simplest way to eliminate double objects creation on the race condition and map ‘optimistic’ local objects with created ones is to use uuid’s and apply ‘short-term’ or ‘imutable’ uniqueness across front-end generated uuids on the backend side.

Schema for uuid-type based uniqueness:

-- Schema for helper table. No pkey, only one uuid-type column
CREATE TABLE chat_uuids ( uuid uuid );CREATE UNIQUE INDEX index_dialog_uniqs_on_uuid ON chat_uuids 
  USING btree (uuid);CREATE OR REPLACE FUNCTION cht_uuid_trg() RETURNS trigger AS $$
BEGIN 
  INSERT INTO chat_uuids VALUES ( NEW.uuid );
  RETURN NEW;
END $$ LANGUAGE plpgSQL;

CREATE TRIGGER dlg_uuid_trg BEFORE INSERT ON chats 
  FOR EACH ROW WHEN( NEW.type = 'Dialog' )
  EXECUTE FUNCTION cht_uuid_trg();-- this an index for optimistic record creation uniqueness 
-- partial condition added just to have comparable performance stats between uuid and text indexesCREATE INDEX chats_uuid_index ON chats USING btree(uuid) WHERE( type='Dialog' );

INSERT-numbers

Base configuration (2 x int64 indexes), 100 records* inserts ~ 3.5ms on average

Insert on chats  (cost=0.00..1.50 rows=100 width=380) (actual time=4.029..4.053 rows=0 loops=1)->  Values Scan on "*VALUES*"  (cost=0.00..1.50 rows=100 width=380) (actual time=0.027..1.790 rows=100 loops=1)Planning Time: 0.515 msExecution Time: 4.170 ms

Rem *The 100 records set delivers a more or less stable UPDATE trials. Running 1K records set trial multiple times in a row to get an average, can easily put all results under a heavy cache influence on 4+M data set.

Base configuration + 1 chats_uuid_index index, 100 records inserts ~4.7ms on average.

Insert on chats  (cost=0.00..1.50 rows=100 width=380) (actual time=4.659..4.684 rows=0 loops=1)->  Values Scan on "*VALUES*"  (cost=0.00..1.50 rows=100 width=380) (actual time=0.027..1.919 rows=100 loops=1)Planning Time: 0.516 msExecution Time: 4.748 ms

Base configuration + 1 dlg_user_ids_index* text index, 100 records inserts ~5.5ms on average:

Insert on chats  (cost=0.00..1.50 rows=100 width=380) (actual time=5.729..5.752 rows=0 loops=1)->  Values Scan on "*VALUES*"  (cost=0.00..1.50 rows=100 width=380) (actual time=0.028..1.889 rows=100 loops=1)Planning Time: 0.546 msExecution Time: 5.820 ms

*Look for dlg_user_ids_index definition, to the index specifics.

Base configuration + a simple uuid transition trigger and a helper table, 100 inserts in one request ~7.9ms on average:

Insert on chats  (cost=0.00..1.50 rows=100 width=380) (actual time=8.475..8.498 rows=0 loops=1)->  Values Scan on "*VALUES*"  (cost=0.00..1.50 rows=100 width=380) (actual time=0.027..1.829 rows=100 loops=1)Planning Time: 0.565 msTrigger dlg_uuids_trg: time=3.510 calls=100Execution Time: 8.563 ms

Base configuration + a ‘complex’ trigger with a conversion and a helper table, 0.1K inserts in one request is ~8.4ms on average:

Insert on chats  (cost=0.00..1.50 rows=100 width=380) (actual time=8.930..8.952 rows=0 loops=1)->  Values Scan on "*VALUES*"  (cost=0.00..1.50 rows=100 width=380) (actual time=0.027..1.779 rows=100 loops=1)Planning Time: 0.507 msTrigger dialog_uniqs_trg: time=4.126 calls=100Execution Time: 9.014 ms

Pay attention to this execution plan parts timings:

-- two elems array transform to a string trigger time:
Trigger dialog_uniqs_trg: time=4.126 calls=100-- uuid insert trigger without any manipulation: 
Trigger dlg_uuids_trg: time=3.510 calls=100

You can see the real timing of the added triggers ~0.03-0.04ms per one execution*, so you can get some valuable hint on the overheads.

*This timmings depends on amount of records to be inserted in a query, 1K inserts shows a little bit faster executions: (Trigger dialog_uniqs_trg: time=34.242 calls=1000 / Trigger dlg_uuids_trg: time=28.092 calls=1000 )

Rem. For truncated helper-table insertion trigger executes x1.2 times faster on a 2M scale, this could be considered as an optimization for ‘short-term’ uniqueness, but it should be done with caution.

UPDATE

In contrast to INSERT, UPDATE operation is very sensitive to the state of a Postgres cache. Numbers are bouncing a lot, so to eliminate cache factor I’m averaging series of 10 requests of 100 record updates couple of times, and in between doing some dummy full scan request against table, like COUNT, MIN, MAX, AVG, creating/dropping indexes e.t.c.. This makes result more or less predictable and measurable.

1–2 indexes, HOT update of 100 records, average time~11ms:

Update on spaces  (cost=0.43..843.49 rows=100 width=656) (actual time=10.962..10.979 rows=0 loops=1)->  Index Scan using spaces_pkey on spaces  (cost=0.43..843.49 rows=100 width=656) (actual time=0.049..9.297 rows=100 loops=1)Index Cond: (id = ANY ('{5375068,1547543,...}'::bigint[]))Planning Time: 0.203 msExecution Time: 11.024 ms

Base configuration, 100 records, not-HOT update, average time ~22ms:

Update on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=20.232..20.254 rows=0 loops=1)->  Index Scan using spaces_pkey on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=0.063..6.511 rows=100 loops=1)Index Cond: (id = ANY ('{2398499,4590088,2755979,...}'::bigint[]))Planning Time: 0.205 msExecution Time: 20.324 ms

Base configuration + 1 dlg_user_ids_index index, not-HOT update, 100 records, average time ~64ms

Update on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=73.879..73.897 rows=0 loops=1)->  Index Scan using spaces_pkey on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=1.377..41.769 rows=100 loops=1)Index Cond: (id = ANY ('{5578295,5815602,....}'::bigint[]))Planning Time: 0.281 msExecution Time: 73.965 ms

Base configuration + 1 chats_uuid_index index, not-HOT update, 100 records, average time ~45ms

Update on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=47.357..47.446 rows=0 loops=1)->  Index Scan using spaces_pkey on spaces  (cost=0.43..844.24 rows=100 width=656) (actual time=0.061..24.770 rows=100 loops=1)Index Cond: (id = ANY ('{2594083,4525270,...}'::bigint[]))Planning Time: 0.242 msExecution Time: 47.517 ms

Rem. The average size of indexed data uuid vs text in a given set of data is 16 / 24.77 ~ 2:3

Trade-offs and summary

INSERT operation with a trigger and a helper-table is ~ 2–2.5 times slower than normal index solution. (+2ms VS +5ms).

UPDATE request is far more expensive operation than INSERT. Its 3–12 times slower than INSERT depending on a HOT/non-HOT execution and indexes amount.

+1 unique text index slowed not-HOT updates ~3 times against non-HOT updates done with a pkey and +1 int64 indexes. ( +22ms VS +64ms )
+1 uuid based uniq index slowed base configuration ~2 times for non-HOT updates ( +22ms VS +45ms )

One time deal +1ms overhead on a records INSERT will save 14ms on every non-HOT UPDATE! ( 8.4ms-5.5ms=2.9ms VS 64ms-22ms=42ms )

Conclusion

Delegating uniqueness to a standalone helper table via INSERT trigger might be a reasonable idea for special cases of ‘imutable’ or ‘short term’ uniqueness, but with one strong condition: you should have noticeable amount of non-HOT updates*

*To get your numbers use cool dba helpers from https://github.com/NikolayS/postgres_dba.

Appendix

Why delegated uniqueness for optimistic creation is better than ‘mutex’ based solution.

To be honest this was the original idea on the matter how to avoid the UNIQUE index for optimistic entity creation.

Another way to handle optimistic creation is to use some kind of a ‘mutex’, for instance, based on redis.

In short:

SETNX with uuid as a key set to -1 with TTL whenever entering entity creation and check what was there before.
If value exists and equals to -1 — we are in race condition and should wait till uuid key is freed by timeout or creation process success.
If value exists and equals to pkey — return existing object.
after successful creation SET uuid with recieved entity pkey.

You can combine this mutex with DB triggers and callbacks trying to avoid +1 index creation. But while being an improvement to the process happened without it, ‘mutex’ approach still not 100% solid. You need to do +1 round trip to redis, redis can loose your ‘mutexes’, application can fail after record creation happened but before pkey stored in mutex, you need to add code for handling race condition, you still cannot be sure that mutex freed via timeout really failed and so on.

On the other hand having delegated uniqueness inside Postgres is solid, simple and much faster.

Ruby gem

Good news for ruby users: I will extract delegated uniqueness feature into the izolenta gem, I already cybersquatted the name :)