1

Because of supporting offline clients I unfortunately have to replace some of my integer Primary Key's for UUID's (but not necessarily the 16 byte (128-bit) RFC 4122 version). I'm on Postgres 12 (could upgrade to 13, but there seems nothing in the changelog related to this). What would be the best performing option? I have some thoughts written below. Any insights/answers?

Length.

To improve overall performance, I am assuming that shorter is better for the PK. I'm aiming for a shorter 8 byte key.

Monotony.

As I have a degree of control over the application I can have a key that is shorter than the typical UUID, which at 16 bytes, feels a bit long to me.

I have been informing myself on Postgres PK's, and learned that they are B+-Tree's, and may (if I understand it correctly) benefit from monotonically increasing values.

I'm thinking of making a 8 byte key composed of three parts:

  1. The Unix epoch in (4 bytes, monotonic) Depending on if unsigned ints are available in Postgres, this would work up to the year 2038 (18y) or 2106 (85y) for resp. available size for 2147483647/4294967294. I could even take it one step further by establishing that we're not counting from 1-1-1970 but from 1-1-2021, which gives resp. 68 and 136 years of seconds.

  2. ..followed by a 1 byte counter (0-255) in case more than one object is created by the client at the same time.

  3. ..followed by a 3 byte random number (16,777,216), of which I am not too sure is long enough.

The resulting key will thus not be entirely monotonous, but still somewhat. Pretty much all online sources I read state that monotony is good for b-tree's, although the exact reason still eludes me somewhat. To my surprise in an article by Jimmy Nilsson put the sequence on the end of the key. https://www.informit.com/articles/article.aspx?p=25862&seqNum=10

Question: Does it matter, and if so, what is better, to put the monotonous part of the key on the beginning or on the end of the value?

Data type.

The key is thus an unsigned 8-byte number. Unfortunately, PostgreSQL does not seem to have an uint8, although there seems to be extensions (such as https://github.com/petere/pguint), but I am wary of potential side effects of using such an extension (should I be?).

However, looking at the number, it did gave me an idea: The max number of a signed BIGINT is 9,223,372,036,854,775,807. What if I approach this like this:

|9,223,372,036|,8|54,775,807|
| timestamp   |ct| random   |

And instead of allowing the full maximum, cap it at:

|8,999,999,999|,9|99,999,999|
| timestamp   |ct| random   |

A range of 9,223,372,036 for the timestamp, gives space till the year 2262, but 8,999,999,999 is still a whopping year 2255. The counter is only allowing for 10 objects per second (which is ok) but the random number is now a better 99.9mln (which must now of course be 0-padded).

Other things.

Security: A benefit of UUID's is that they cannot be guessed. My application has no need of that.

MAC address: As proposed in the comments, won't fly, as my clients will mostly be browser tabs which have (luckily) no access the MAC. Browsers (rightfully) take precautions against fingerprinting, therefore I am discounting client fingerprints entirely at the moment in favour of a time+random approach.

Edit: I rewrote the question after the initial comment from a_horse_with_no_name and reading https://www.2ndquadrant.com/en/blog/sequential-uuid-generators/ including the UUIDv6 approach.

4
  • 1
    A UUID only needs 16 byte storage, so that would be the shortest of all your alternatives
    – user1822
    Commented Feb 7, 2021 at 21:40
  • yes, I see my mistake... I will look into sequential uuid generators and rephrase or drop the question
    – svenema
    Commented Feb 7, 2021 at 23:35
  • Base36 sounds pretty inefficient. Maybe a bigint with the last 24 bits of MAC address plus 32 bit unix epoch, plus a simple counter for the remaining 8 bits Commented Feb 8, 2021 at 1:07
  • @Charlieface MAC addresses are not available in my client (browser)
    – svenema
    Commented Feb 8, 2021 at 11:35

1 Answer 1

2

Yes, you are right. “Sequential UUIDs” will lead to better-performing indexes, which is one of the reasons why there are now a number of sequential UUID implementations available for PostgreSQL.

I recommend UUIDv7, which is relatively easy to implement, as its timestamp is Unix epoch based. The cleanest implementation thereof is (in my opinion) pg_uuidv7, a PostgreSQL extension by Florian Boulnois.

If you want to compare pg_uuidv7 to other options, you may be interested in the overview of PostgreSQL sequential UUID solutions that I recently published.

A good overview of the problem with non-sequential UUIDs in PostgreSQL is this blog post by Tomas Vondra, though I don't recommend the solution he implemented, since there are now the upcoming UUIDv6, UUIDv7 and UUIDv8 standards, which I am sure will gain more acceptance and momentum.

1
  • 1
    Really nice articles, but just scanned it quickly. Will do a deep-dive when I have some more time. Thanks.
    – svenema
    Commented Jun 20, 2023 at 14:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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