14 ms·

Unexpected downsides of UUID keys in PostgreSQL

243 points by alexzeitler 3y ago

cryptos 3y ago
While UUIDs are pretty common, they are by far not the only or superior solution. To be able to easily generate IDs on different nodes in a distributed system something host-specific, pure random, or a mixture of both is needed. To be avoid problems with random numbers on DB indexes some time-based part would be useful. There are other approaches like Ulid or TSID which are similar to UUID v7, but are represented in are more compact way. Example Ulid vs UUID: 000360TJXZDDMSKJSQGBQHA5YA fb87f306-b613-4948-be24-00609cf9ccc8 https://github.com/ulid/spec https://github.com/ulid/spec https://tsid.com/de https://tsid.com/de
dloreto 3y ago
The stated downsides come from poor data locality when using mostly random UUIDs; but you can keep most of the benefits of a globally unique identifier, and retain locality, by using UUIDv7. At jetpack.io we've been doing exactly that via TypeIDs: https://github.com/jetpack-io/typeid https://github.com/jetpack-io/typeid and there's a PostgresSQL implementation available. TypeIDs are UUIDv7 with additional type information, so you also get type-safety in your IDs.
pachico 3y ago
How can this be unexpected? Isn't this what Percona discussed for MySQL already several years ago? Or am I missing something?
- bguebert 3y ago
  They suggest to use UUID v7 at the end for more sequential keys. Maybe that's the new part since v7 is relatively recent.
  - mattmanser 3y ago
    MSSQL has had sequential GUIDs for over a decade to solve this very problem, surprised it wasn't done sooner.
    - evntdrvn 3y ago
      their format is pretty funky though lol
- indymike 3y ago
  > How can this be unexpected? If you routinely work with junior developers this will come up because UUID4 seems miraculous at first. There's always a bit of surprise when the question gets asked about why we have so many sequential keys when we could just use UUID4...
- Tehnix 3y ago
  The amount of people with actual experience scaling databases is very small compared to the amount of e.g. Backend Engineers that end up implementing the solutions. I think a root cause is that there’s almost never a case for preferring UUIDv4 over ULID/UUIDv7, but we still see almost all learning material reach for the former. So people only find out once they have a table that exhibits weird/low performance and suddenly need to google for specific performance problems they’ve never encountered before. Similarly, efficiently using indexes is also a very common thing I see people not know much about, since with SQL “everything performs well until it doesn’t” (i.e. you reach scale) :)
gregwebs 3y ago
UUID is also used to avoid leaking information about the underlying system. This includes temporal information that could be used to infer the size of the dataset for all users. If this isn’t a concern, then using a timestamp based approach as recommended in this article is a good approach. That is the default in MongoDB. If it is a concern, one approach is to use random UUIDs to give to end users but then internally to have something like auto increment ids.
- jandrewrogers 3y ago
  Organizations that care about leaking information encrypt their identifiers as UUIDs. UUIDs conveniently have the same size as a single AES block, for which there is dedicated silicon on all modern CPUs. There is almost no overhead. Every other issue with random UUIDs etc, which are ignored here, are solved by encrypting your identifier. Random UUIDs (i.e. UUIDv4) are banned in many places for good reasons.
  - Fire-Dragon-DoL 3y ago
    Won't encrypting defeat the ordering though, reintroducing the performance penalties?
- WeAddValue 3y ago
  Or use hashids.org. Use it to obfuscate your integer auto increment ids anywhere a user might see it.
  - VWWHFSfQ 3y ago
    It's a good option purely for cosmetics but don't rely on it for any kind of serious obscurity since it's trivially reversed. I've used it to great effect in the past to encode multiple integer values like start/end ID, sort order (0/1), etc. for cursor-based pagination. But that's only because there's nothing secret in those numbers. Just purely for convenience.
    - 3y ago
jamil7 3y ago
Can UUID v7 still be created independently, on a client for instance? Or do they ideally need to be generated in the same place?
- jayknight 3y ago
  They can be generated anywhere, otherwise they wouldn't be universally unique.
  - jamil7 3y ago
    I'm not asking about the uniqueness but about ordering across different clients.
    - roenxi 3y ago
      There is probably an impossibility theory somewhere for two clients generating ordered ID without communicating with each other. What if one client was travelling near the speed of light for example? It isn't obvious what order would be correct since the two clients would have wildly different perceptions of time.
      - ahoka 3y ago
        Yes, it’s impossible in theory. Same as the two generals problem, if I’m not mistaken.
    - sibit 3y ago
      If they're generated on the client you would need to keep clock drift[0] in mind since the leading bits are time based. [0]: https://youtu.be/mAyW-4LeXZo https://youtu.be/mAyW-4LeXZo (Clock Synchronization in Distributed Systems by Martin Kleppmann)
- stevesimmons 3y ago
  Yes, UUID v7 can be generated independently. The UUID has three parts, which maintains strict chronological ordering for UUIDs generated in one process, and to within clock skew when UUIDs are generated on different systems. The three parts are: - time-based leading bits. - sequential counter, so that multiple UUID 7s generated very rapidly within the same process will be monotonic even if the time counter does not increment. - enough random bits to ensure no collisions and UUIDs cannot be guessed.
BiteCode_dev 3y ago
That's... not unexpected. That's been the known technical compromise of UUID for years, and why ULID and UUID 7 are born. And usually it is still worth it.
- Tehnix 3y ago
  The main problem is probably that you will not find a “regular Engineer” knowing this unless they’ve had to deal with scaling issues on a DB (e.g. high IOPS etc). The knowledge is definitely out there, but almost all articles will be reaching for UUIDs, so this is understandably what most people end up with :/
zero_iq 3y ago
Article should be called "Totally Expected Downsides..." If you want temporal locality, use ULIDs instead.
- ants_a 3y ago
  The unexpected part for me was not the lack of temporal locality, but which cache it thrashed. The whole dataset fits into buffer cache so one might think that the lack of locality is not that important...
- rjh29 3y ago
  I was going to use UUID with the time portion at the start (also known as UUIDv7) but this looks better.
  - heipei 3y ago
    I've been thinking about converting a legacy application which uses UUIDv4 to use ULIDs instead going forward, but then to represent these ULIDs in a format that is compliant with a UUIDv4. I have not thought through the possible downsides, but I think it should be a pretty straightforward change. Of course old records will remain true random UUIDv4s, but at least new records will be time-order and as such will create less stress on the B-Tree index when writing them.
  - gmhafiz 3y ago
    One potential downside is ULID does not have an RFC, unlike UUID V7
    - rjh29 3y ago
      Good point. It has libraries in most languages and that's good enough for me, but might be a problem if you're interfacing with other projects.
    - samokhvalov 3y ago
      Hopefully, it will soon have it: https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...
robertlagrant 3y ago
Is this a downside of UUID keys in general, or of using them as indexes? Would it be possible to create a primary index on a combination of inserted date and uuid and get opaque UUIDs and good indexing?
- bandrami 3y ago
  The alternative is having two required-unique columns only one of which is definitionally unique. It solves some problems and introduces others.
  - rjh29 3y ago
    You can use UUIDv7 or ULID for that. One value with both the timestamp and random data inside.
    - bandrami 3y ago
      Sorry, right; I meant that's the collation alternative to a multi-field record like v7.
- exyi 3y ago
  Yes, it's a downside of using them in b-tree indexes. However, the purpose of having an ID is usually to use it for lookup (from foreign keys, query string arguments, ...). If you create an index on two columns, you won't be able to lookup using only the second value, at least not in Postgres.
  - robertlagrant 3y ago
    That's interesting - I don't know enough about this! If it's lookup from a foreign key, won't it just go straight to the record? What's the index for there?
MPSimmons 3y ago
I don't find myself dealing with databases in any depth very often, so this was news to me, and I thought it was well written, for what it's worth. Thanks for posting.
daneel_w 3y ago
Nothing unexpected about it at all. PostgreSQL's default index in this case is a B-tree, and they don't index disorderly data very well which is the nature of all UUID versions. On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641 PostgreSQL can do (among other types) 32-bit hash indices which work out better for certain use cases. Personally I would avoid B-trees for any UUID unless I really had to do partial or ranged scans on them.
- ants_a 3y ago
  B-trees index random UUIDs perfectly fine, it's just that range scans over the resulting indexes cause random access patterns that interact really poorly with caches when data size exceeds cache size. The blog was about an interesting case when dataset fits into buffer cache, but the random access pattern still hurts because of other caches.
- marginalia_nu 3y ago
  > On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641 I don't think this is the same phenomenon at all, if anything that looks like an implementation problem rather than something that's somehow inherent in B-trees. Depending on how you construct the tree, it's however still possible to end up with something that's very fragmented and inefficient, but you can always construct a dense b-tree with a space complexity of O(N/(B-1)). To see why you can just lay out the data in a list and manually create the index layers. Each layer will be bounded by N/B, N/B², N/B³, ... (and the sum of 1/B^n over all n is 1/(B-1) ) Considering an actual tree, for N=10, B=3 1 2 3 4 5 6 7 8 9 10 data <3 | <6| <9 | <10 index 1 <6 |<10 | index 2 <10 root Looking at this, I think it should be apparent that if you change this ordered sequence 1-10 to ten UUIDs ordered in the same way, there would be no change in the structure of the tree. It would be a bit bigger on disk because UUIDs are bigger than integers, and you may end up with an additional data layer because of that (because you want to align with the disk block size). One reason you might see a difference even when the implementation makes the appropriate assumptions is that B-trees can do very clever things with somewhat sequential data when it comes to joins, where you can get linear nearly runtimes for the operation. But as mentioned, this only works with relatively ordered data.
croes 3y ago
Can't you simply add a additional timestamp column for time based sorting? No need to raise the collision probability.
- plagiarist 3y ago
  If size isn't an issue it seems so. I know of one implementation that uses wall clock to get a "close enough" sorting https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid
damethos 3y ago
Why not just use auto-increment integers and expose them with something like this: https://www.npmjs.com/package/hashids https://www.npmjs.com/package/hashids (The linked library is just an example). Yes, you will need to transform the IDs before returning them to an external caller which is a little bit annoying but it's probably not that a big of a deal. Also another approach I've seen, which personally I find it a bit complicated, is to use auto-increment primary keys for the internal system and UUIDs for the public facing interactions.
- cryptos 3y ago
  Incrementing integers doesn't work well in a distributed system, where the IDs might be generated outside of the database (to have it before the transaction ends, for example).
xmdx 3y ago
That's what created_at and updated_at are for surely
- sam_lowry_ 3y ago
  From the ActiveRecord fame ;-)
- yesimahuman 3y ago
  I was going to ask, when would you only rely on a sequential id for temporal locality, wouldn't most people be indexing and sorting on `created_at` or something equivalent?
  - Tehnix 3y ago
    You don’t need to need temporal elements, the simple fact that UUIDs are a bad fit for B-Trees means that simply inserting a bunch of data that relies on a UUIDv4 for its unique ID, will also run into these same problems. You’d typically see this as either lower performance of a table than you expect, or higher IOPS usage of your database (which gets expensive at scale).
jongjong 3y ago
I can't think of many use cases where I would sacrifice the beauty and elegance of UUIDs to optimize access times by a millisecond or two. UUID is totally worth the cost. UUID actually performs much better than I thought based on the author's example with a COUNT query. COUNT queries aren't very efficient because typically, all records are traversed; here we're talking about a 50% slowdown on 10 million records... How often do you need to access 10 million contiguous records? Most of the time, for user-facing apps, you'll be accessing 100 contiguous records at most and, in fact, most queries will access a single record... I suspect that the average per-query performance loss for a typical app is probably less than 5%. Also, you could simply index by a separate date/timestamp field if you need records to be ordered by time and probably won't incur any performance cost. IMO, unless you're building an app for high-frequency trading, auto-incrementing IDs aren't worth the pain and lack of flexibility.
- jongjong 3y ago
  Recently, I wrote a client-side wallet app for cryptocurrency use case and it required transactions to be created and signed entirely on the client-side and so the transaction UUID had to be created on the client side (before signing) and I was surprised at how elegant and simple the application's logic turned out to be (both on the front end and back end). One of the best things about UUIDs is that if your front end tries to create a resource and fails due to a bad connection, you can simply resend that exact same resource for creation again (with the same UUID) and you don't need to worry about duplicate records being inserted into the database since you would get an ID collision; it results in much simpler/cleaner code which is idempotent and deterministic by default. With auto-incrementing IDs, if there is a connection issue or other failure, it's not possible to cleanly figure out if a resource was already created or not since only the database knows what the ID of that resource was until that ID is sent back and reaches the client across the network. Just because the client did not receive a successful response from the server, it does not mean that the resource was not created; and if it was, you cannot know since the client has no way of referencing that resource in a reliable way. It just seems completely wrong that the client (which created the resource) cannot reference it until the database has inserted it. It's a hack to pretend that resource creation starts in the database, when in fact, it starts on the front end.
VWWHFSfQ 3y ago
My go-to pattern for many years now is to use a plain bigint autoincrement column for internal database relations and then a uuid for application-level identifiers and natural keys. Basically never use the uuid as the actual primary key because they're enormous and now the DBMS has to copy that gigantic number to every side of the relation. Don't do it
- zzzeek 3y ago
  Same, I'm surprised nobody is mentioning this. All the foreign key columns become uuids also and the DB becomes miserable to deal with.
- sumtechguy 3y ago
  This is a good answer. You want your primary/cluster key to usually be something that makes sense in your data. If you use something like UUID the placement can be basically random. That is usually in SQL is not a desirable trait. If you use it for a primary key you are basically saying you are fine with a memory cmp vs a register compare for you finding the right data. That can be undesirable too. UUIDs do have very desirable traits such as uniqueness. But that does come at a cost and usually you can fix that by deciding what process decides the source of truth in a different way.
londons_explore 3y ago
Note that if you use something like spanner, you never want data locality, because it will prevent your data being spread effectively between nodes. So your id's of top level entities should be something random.
londons_explore 3y ago
There are downsides to anything ascending/descending in a database too... They mess with table statistics. If you do a query like "SELECT * from users where creation_date > NOW-1h", the query analyzer doesn't know that there might be thousands of users created in the last hour. It is probably working from day-old statistics that say all users have a creation_date between 2008 and 2023-06-21. That makes it sometimes pick an exceptionally poor query plan. Ie. instead of your query taking 50 milliseconds, it might take 50 hours and involve an n^2 scan of all data in your database.
willvarfar 3y ago
> if you want to use UUID’s, try to use a sequential variant. UUID v7 is a good option. Hopefully it’s coming to PostgreSQL 17 Yeap, UUIDv7 directly addresses the issues in the article. Warmly recommended. (There is the issue that exposing ULIDs to users may 'leak' information about when things were created etc, but that is usually not a problem.)
- rollcat 3y ago
  I also like UUIDv8. It's broadly similar to v7 but the vendor is free to define how the timestamps are represented, how many bits to split between timestamps/randomness, define own packing, etc. So we've started making UUIDs that encode the current ISO8601 date+time in a human-readable format: YYYYMMDD-HHMM-VRRR-RRRR-RRRRRRRRR This is especially useful for things you have few of (no more than a couple per minute), that you regularly need to cross-reference with other systems (e.g. files on S3).
  - JdeBP 3y ago
    Enough iterations in this direction, and people will come full circle to how message IDs operated on Usenet. <datetime.processID.sequencenumber@domain> for example.
  - pgaddict 3y ago
    The one problem with this "perfectly" sequential UUIDs is that it can easily lead to index bloat. Imagine you have such sequential UUIDs generated over a year, for example. And then you delete e.g. 99% of old data (say, everything except some records that you're required to keep for audit purposes or whatever). If there was an index, the "old" part will be 99% empty. For regular UUIDs this would be fine, because new entries would get routed to this part of the index and the space would be reused. Not so for sequential UUIDs (v7/v8). This is mostly why year ago I wrote "sequential-uuids" extension, doing roughly what v7/v8 do, but wrapping the timestamp once in a while. Of course, if you don't delete data, this is not an issue and v7/v8 will work fine.
    - rollcat 3y ago
osigurdson 3y ago
On the one hand, a serial base id like https://example.com/user/items/55 https://example.com/user/items/55, seems less secure than a UUID based approach as if all else fails the UUID is still hard to guess. On the other, some systems (github private repos for example), don't seem to worry about how easily a URL can be guessed. Is it perhaps the case that probability of successful attack is not materially reduced in with a hard to guess url in the final analysis?
Timpy 3y ago
For me, the visual noise is a downside for UUIDs. A lot of time investigating data issues means glancing at query results and deciding if something looks unexpected. I just can't parse a UUID with my eyes that quick. I've come up against this at my current job a little too often and I'm cursing the decision to switch to UUIDs. I know, it's a balancing act of competing concerns. But for us moving to UUIDs was future proofing for a problem that never arose, and the senior dev who made us switch left the company a few years ago. I just don't like the dev experience of UUIDs in a world where you do have to get hands (and eyes) on the data all the time.
- Pet_Ant 3y ago
  Something I saw a longtime ago was hashing UUIDs into a RGB value and then colouring the background of the cell (at least when viewing in a DB IDE). That way you can quickly at a glance tell if it's worth going over character by character.
  - Timpy 3y ago
    Wow I really love that idea. Next time I get stuck on a fix tinkering with my setup I'm going to check this out.
  - adverbly 3y ago
    Holy crap this is brilliant. I'd just change the text color of the uuid itself though - no need to change the background(although you'd need to make sure that the hash function avoided your existing background color to maintain a high enough contrast ratio for readability). I want this as a vscode extension. Or maybe as a terminal plugin or something? Is that possible? Could tmux do it maybe?
- michaelsalim 3y ago
  Interesting take. I do agree there's some visual noise there, but not how you described it. UUID just takes so much screen space compared to its integer counterpart. If you don't have a good UI sorting things out it's quite annoying. Otherwise it's pretty great.
pfooti 3y ago
Weirdly, and this may be a side effect of writing code that uses Cloud Spanner, but I tend to think of uuidv4's random distribution through keyspace as a _good_ thing. My instinct is to not use sequential-ish indices/primary keys, because I don't want to hotspot one part of the storage with all my writes for today in the same tablet.
insanitybit 3y ago
Another (potentially!) significant problem with uuids is that they're inefficient to store. Compared to an 8 byte value obviously they double the storage size. But it's actually worse - if you have loosely ordered integers, even with gaps, you can compress those down to even less, like practically 1 byte on average. That makes uuids ~16x worse for disk storage, ~2x worse for memory storage (cache). That + Losing locality can be, for some workloads, a significant loss. Where UUIDs reign supreme for performance is in terms of generation - if you have a super high write load and really high latency requirements it may not be viable to have a single integer counter. Although, in my own testing, I've found Postgres is more than capable of hundreds of thousands of increments per second and if you're willing to allow for gaps/ interleaving in your counter (slight hit to locality) you're really unlikely to hit a bottleneck. Sequentual uuids help and are desirable but they still can't compete on storage :)
- fabian2k 3y ago
  I'm not aware of any situation where Postgres (without extensions) would compress ints that way? That is more of a column-oriented or time-series DB thing to me. Are there any cases in Postgres where this actually plays a role and sequential ints get compressed?
  - insanitybit 3y ago
    Sorry, let me clarify. I used Postgres to generate the counters as external IDs into other data stores (so instead of `give me a new uuid` I said `hey postgres give me a new counter`. Postgres was only used to maintain the counters themselves in a tiny database where compression isn't relevant anyways. The other data stores where I used this were a combination of Parquet on S3 (where you get compression) and ScyllaDB (where you also get compression).
- insanitybit 3y ago
  Oh yeah, this also makes pagination trivial. You can basically just give your clients a literal number indicating where they are. So good, you basically get paging APIs for free.
deleted 3y ago
[deleted]
moi2388 3y ago
int key for internal use, guid for external purposes
coding123 3y ago
Use flakeids
neurostimulant 3y ago
CouchDB uses sequential UUID by default: https://docs.couchdb.org/en/stable/config/misc.html#uuids-configuration https://docs.couchdb.org/en/stable/config/misc.html#uuids-co... > Impact of UUID choices: the choice of UUID has a significant impact on the layout of the B-tree, prior to compaction. > For example, using a sequential UUID algorithm while uploading a large batch of documents will avoid the need to rewrite many intermediate B-tree nodes. A random UUID algorithm may require rewriting intermediate nodes on a regular basis, resulting in significantly decreased throughput and wasted disk space space due to the append-only B-tree design. > It is generally recommended to set your own UUIDs, or use the sequential algorithm unless you have a specific need and take into account the likely need for compaction to re-balance the B-tree and reclaim wasted space.
NicoJuicy 3y ago
Tbh. I use UUID's a lot, perhaps usefull to know that Deterministic UUID exist, eg. DeterministicGuid.Create(tenantNamespace, "my-tenant-name"); Note: https://github.com/Informatievlaanderen/deterministic-guid-generator https://github.com/Informatievlaanderen/deterministic-guid-g... for dotnet. Additionally, know that there are different versions of UUID's. If you want to create chronologic UUID's so that queries are more easily ordered, use the correct type.
hn_throwaway_99 3y ago
The new/upcoming UUID v7 really solves pretty much all of these problems: 1. They're ordered by a timestamp, so they preserve DB locality 2. They include a total of 74 bits of random data. This isn't enough to be used as unguessable keys, but it does offer some good protection if you have other bugs that could otherwise lead to IDOR vulnerabilities. 3. They're still 16 bytes, but IMO any minor hit to storage/time is completely worth it for the benefits they provide, especially since the other option is usually to have an integer primary key AND another "public ID" column that stores a UUID.
frodowtf 3y ago
With some basic knowledge about how a db stores data, there is nothing really "unexpected" about this behavior. It's weird though how little devs actually know or care about it.
aarondf 3y ago
I did a video covering choosing a primary key type for MySQL [1], including UUIDs. Long story short: you should probably use a bigint unless you have a pretty good reason not to. Good reasons exist! If you do use a UUID, make sure you use a version that is time-sorted. 1: https://planetscale.com/courses/mysql-for-developers/indexes/primary-key-data-types https://planetscale.com/courses/mysql-for-developers/indexes...
deleted 3y ago
[deleted]
bfrog 3y ago
Snowflake ids fit this sort of thing better, and maintain temporal locality. I ran into this exact issue when building out a graph like database in Postgres many moons ago. It’s probably less of an issue with fast nvme sad drives now, but on mechanical drives ordering and locality are massive.
ilyt 3y ago
How is any of that "unexpected" ? What did the author expected ?
samokhvalov 3y ago
We discussed some of these problems here during a Postgres.tv session, and developed a patch to support ULID / UUIDv7: https://www.youtube.com/watch?v=YPq_hiOE-N8 https://www.youtube.com/watch?v=YPq_hiOE-N8 And then Andrey proposed a patch in the pgsql-hackers mailing list: https://www.postgresql.org/message-id/flat/CAAhFRxitJv%3DyoGnXUgeLB_O%2BM7J2BJAmb5jqAT9gZ3bij3uLDA%40mail.gmail.com https://www.postgresql.org/message-id/flat/CAAhFRxitJv%3DyoG..., https://commitfest.postgresql.org/43/4388/ https://commitfest.postgresql.org/43/4388/ Everyone who can help (test, discuss, etc.) – please participate in that discussion. The standard is not finalized yet, but there some expectations that it will be, if it happens, it would be great to have this in future Postgres 17.
- pksunkara 3y ago
  Implementing support for UUIDv7 does not equal implementing support for ULID. ULID needs to be treated as a first class citizen (type, read format, storage format, converters) instead of being an afterthought result from UUIDv7. I have built a postgres extension for adding ULID support which does what I described. https://github.com/pksunkara/pgx_ulid https://github.com/pksunkara/pgx_ulid
seanhunter 3y ago
I’ll genuinely never understand why people benchmark in this way. They are doing a thing that is slow and inefficient in a fundamental way and then producing a blogpost about it being slow and inefficient in a much more trivial respect. If you care about performance, select count(uuid) from records; Makes absolutely no sense. You know the uuid is unique so you are deliberately selecting a value and then throwing it away just to count it. select count(1) from records; Would give the same value and could be answered from the index without requiring a scan of the table. This is true of any unique column in the table no matter what type (it doesn’t have to be a uuid). The fact that uuids are a bit slower than other types of keys when you scan the entire table unnecessarily seems beside the point.
- ants_a 3y ago
  I agree, though it's not the uniqueness, but not null constraint that matters here. PostgreSQL could, but doesn't right now, use the not null constraint to optimize the former to the latter. The actual case came to my attention because an ORM insisted on generating the count(uuid) variant and I thought it peculiar that the performance difference was so large. But silly ORMs aside, the same problem will happen on any index only range scan over an index that has uuid in it. For a more realistic case, a `count(*) where somecol = 'value'` with a `(somecol, uuid)` index will hit the same problem. I thought the rather hidden single entry visibility map buffer reference cache was an interesting example where random ordering can cause performance problems.
- insanitybit 3y ago
  I can't imagine that the author is saying "don't count uuids this way!" but instead is trying to explain how locality works in btree indices, using a trivial example to demonstrate it.
- seanhunter 3y ago
  I should add for people who are not aware, the same concept is very important to bear in mind if there is a WHERE EXISTS or WHERE NOT EXISTS subclause to your query. Something like select u.username as good_user from users u where not exists ( select 1 from naughty_users n where n.id = u.id ) …is generally going to be much much faster than what a lot of people instinctively do which is to select the username or user id from the inner query. Since you’re just checking for (non)existence it doesn’t matter what the inner query returns so select 1 will answer the query from the index (assuming the id is indexed which if it isn’t you have bigger problems). If you spend a while looking at explain plans for your queries you will spot common patterns like this where you can avoid a table scan often.
JoeAltmaier 3y ago
The correlation of locality and sequential keys was a coincidence. It's unfortunate that folks rely on this coincidence for performance. Databases can be made with better algorithms now that UUIDs are common. It would be a mistake to enshrine sequential indexes as some special optimization, just to be blown away later when better algorithms get used.
penciltwirler 3y ago
Have a look at ULIDs

243 points by alexzeitler 3y ago

While UUIDs are pretty common, they are by far not the only or superior solution. To be able to easily generate IDs on different nodes in a distributed system something host-specific, pure random, or a mixture of both is needed. To be avoid problems with random numbers on DB indexes some time-based part would be useful. There are other approaches like Ulid or TSID which are similar to UUID v7, but are represented in are more compact way. Example Ulid vs UUID: 000360TJXZDDMSKJSQGBQHA5YA fb87f306-b613-4948-be24-00609cf9ccc8 https://github.com/ulid/spec https://github.com/ulid/spec https://tsid.com/de https://tsid.com/de

dloreto 3y ago

The stated downsides come from poor data locality when using mostly random UUIDs; but you can keep most of the benefits of a globally unique identifier, and retain locality, by using UUIDv7. At jetpack.io we've been doing exactly that via TypeIDs: https://github.com/jetpack-io/typeid https://github.com/jetpack-io/typeid and there's a PostgresSQL implementation available. TypeIDs are UUIDv7 with additional type information, so you also get type-safety in your IDs.

pachico 3y ago

How can this be unexpected? Isn't this what Percona discussed for MySQL already several years ago? Or am I missing something?

bguebert 3y ago
They suggest to use UUID v7 at the end for more sequential keys. Maybe that's the new part since v7 is relatively recent.
- mattmanser 3y ago
  MSSQL has had sequential GUIDs for over a decade to solve this very problem, surprised it wasn't done sooner.
  - evntdrvn 3y ago
    their format is pretty funky though lol
indymike 3y ago
> How can this be unexpected? If you routinely work with junior developers this will come up because UUID4 seems miraculous at first. There's always a bit of surprise when the question gets asked about why we have so many sequential keys when we could just use UUID4...
Tehnix 3y ago
The amount of people with actual experience scaling databases is very small compared to the amount of e.g. Backend Engineers that end up implementing the solutions. I think a root cause is that there’s almost never a case for preferring UUIDv4 over ULID/UUIDv7, but we still see almost all learning material reach for the former. So people only find out once they have a table that exhibits weird/low performance and suddenly need to google for specific performance problems they’ve never encountered before. Similarly, efficiently using indexes is also a very common thing I see people not know much about, since with SQL “everything performs well until it doesn’t” (i.e. you reach scale) :)

gregwebs 3y ago

UUID is also used to avoid leaking information about the underlying system. This includes temporal information that could be used to infer the size of the dataset for all users. If this isn’t a concern, then using a timestamp based approach as recommended in this article is a good approach. That is the default in MongoDB. If it is a concern, one approach is to use random UUIDs to give to end users but then internally to have something like auto increment ids.

jandrewrogers 3y ago
Organizations that care about leaking information encrypt their identifiers as UUIDs. UUIDs conveniently have the same size as a single AES block, for which there is dedicated silicon on all modern CPUs. There is almost no overhead. Every other issue with random UUIDs etc, which are ignored here, are solved by encrypting your identifier. Random UUIDs (i.e. UUIDv4) are banned in many places for good reasons.
- Fire-Dragon-DoL 3y ago
  Won't encrypting defeat the ordering though, reintroducing the performance penalties?
WeAddValue 3y ago
Or use hashids.org. Use it to obfuscate your integer auto increment ids anywhere a user might see it.
- VWWHFSfQ 3y ago
  It's a good option purely for cosmetics but don't rely on it for any kind of serious obscurity since it's trivially reversed. I've used it to great effect in the past to encode multiple integer values like start/end ID, sort order (0/1), etc. for cursor-based pagination. But that's only because there's nothing secret in those numbers. Just purely for convenience.
  - 3y ago

jamil7 3y ago

Can UUID v7 still be created independently, on a client for instance? Or do they ideally need to be generated in the same place?

jayknight 3y ago
They can be generated anywhere, otherwise they wouldn't be universally unique.
- jamil7 3y ago
  I'm not asking about the uniqueness but about ordering across different clients.
  - roenxi 3y ago
    There is probably an impossibility theory somewhere for two clients generating ordered ID without communicating with each other. What if one client was travelling near the speed of light for example? It isn't obvious what order would be correct since the two clients would have wildly different perceptions of time.
    - ahoka 3y ago
      Yes, it’s impossible in theory. Same as the two generals problem, if I’m not mistaken.
  - sibit 3y ago
    If they're generated on the client you would need to keep clock drift[0] in mind since the leading bits are time based. [0]: https://youtu.be/mAyW-4LeXZo https://youtu.be/mAyW-4LeXZo (Clock Synchronization in Distributed Systems by Martin Kleppmann)
stevesimmons 3y ago
Yes, UUID v7 can be generated independently. The UUID has three parts, which maintains strict chronological ordering for UUIDs generated in one process, and to within clock skew when UUIDs are generated on different systems. The three parts are: - time-based leading bits. - sequential counter, so that multiple UUID 7s generated very rapidly within the same process will be monotonic even if the time counter does not increment. - enough random bits to ensure no collisions and UUIDs cannot be guessed.

BiteCode_dev 3y ago

That's... not unexpected. That's been the known technical compromise of UUID for years, and why ULID and UUID 7 are born. And usually it is still worth it.

Tehnix 3y ago
The main problem is probably that you will not find a “regular Engineer” knowing this unless they’ve had to deal with scaling issues on a DB (e.g. high IOPS etc). The knowledge is definitely out there, but almost all articles will be reaching for UUIDs, so this is understandably what most people end up with :/

zero_iq 3y ago

Article should be called "Totally Expected Downsides..." If you want temporal locality, use ULIDs instead.

ants_a 3y ago
The unexpected part for me was not the lack of temporal locality, but which cache it thrashed. The whole dataset fits into buffer cache so one might think that the lack of locality is not that important...
rjh29 3y ago
I was going to use UUID with the time portion at the start (also known as UUIDv7) but this looks better.
- heipei 3y ago
  I've been thinking about converting a legacy application which uses UUIDv4 to use ULIDs instead going forward, but then to represent these ULIDs in a format that is compliant with a UUIDv4. I have not thought through the possible downsides, but I think it should be a pretty straightforward change. Of course old records will remain true random UUIDv4s, but at least new records will be time-order and as such will create less stress on the B-Tree index when writing them.
- gmhafiz 3y ago
  One potential downside is ULID does not have an RFC, unlike UUID V7
  - rjh29 3y ago
    Good point. It has libraries in most languages and that's good enough for me, but might be a problem if you're interfacing with other projects.
  - samokhvalov 3y ago
    Hopefully, it will soon have it: https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc4122bis https://datatracker.ietf.org/doc/html/draft-ietf-uuidrev-rfc...

robertlagrant 3y ago

Is this a downside of UUID keys in general, or of using them as indexes? Would it be possible to create a primary index on a combination of inserted date and uuid and get opaque UUIDs and good indexing?

bandrami 3y ago
The alternative is having two required-unique columns only one of which is definitionally unique. It solves some problems and introduces others.
- rjh29 3y ago
  You can use UUIDv7 or ULID for that. One value with both the timestamp and random data inside.
  - bandrami 3y ago
    Sorry, right; I meant that's the collation alternative to a multi-field record like v7.
exyi 3y ago
Yes, it's a downside of using them in b-tree indexes. However, the purpose of having an ID is usually to use it for lookup (from foreign keys, query string arguments, ...). If you create an index on two columns, you won't be able to lookup using only the second value, at least not in Postgres.
- robertlagrant 3y ago
  That's interesting - I don't know enough about this! If it's lookup from a foreign key, won't it just go straight to the record? What's the index for there?

MPSimmons 3y ago

I don't find myself dealing with databases in any depth very often, so this was news to me, and I thought it was well written, for what it's worth. Thanks for posting.

daneel_w 3y ago

Nothing unexpected about it at all. PostgreSQL's default index in this case is a B-tree, and they don't index disorderly data very well which is the nature of all UUID versions. On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641 PostgreSQL can do (among other types) 32-bit hash indices which work out better for certain use cases. Personally I would avoid B-trees for any UUID unless I really had to do partial or ranged scans on them.

ants_a 3y ago
B-trees index random UUIDs perfectly fine, it's just that range scans over the resulting indexes cause random access patterns that interact really poorly with caches when data size exceeds cache size. The blog was about an interesting case when dataset fits into buffer cache, but the random access pattern still hurts because of other caches.
marginalia_nu 3y ago
> On the topic of how important it is for B-trees to be "orderly": https://news.ycombinator.com/item?id=34404641 https://news.ycombinator.com/item?id=34404641 I don't think this is the same phenomenon at all, if anything that looks like an implementation problem rather than something that's somehow inherent in B-trees. Depending on how you construct the tree, it's however still possible to end up with something that's very fragmented and inefficient, but you can always construct a dense b-tree with a space complexity of O(N/(B-1)). To see why you can just lay out the data in a list and manually create the index layers. Each layer will be bounded by N/B, N/B², N/B³, ... (and the sum of 1/B^n over all n is 1/(B-1) ) Considering an actual tree, for N=10, B=3 1 2 3 4 5 6 7 8 9 10 data <3 | <6| <9 | <10 index 1 <6 |<10 | index 2 <10 root Looking at this, I think it should be apparent that if you change this ordered sequence 1-10 to ten UUIDs ordered in the same way, there would be no change in the structure of the tree. It would be a bit bigger on disk because UUIDs are bigger than integers, and you may end up with an additional data layer because of that (because you want to align with the disk block size). One reason you might see a difference even when the implementation makes the appropriate assumptions is that B-trees can do very clever things with somewhat sequential data when it comes to joins, where you can get linear nearly runtimes for the operation. But as mentioned, this only works with relatively ordered data.

croes 3y ago

Can't you simply add a additional timestamp column for time based sorting? No need to raise the collision probability.

plagiarist 3y ago
If size isn't an issue it seems so. I know of one implementation that uses wall clock to get a "close enough" sorting https://github.com/segmentio/ksuid https://github.com/segmentio/ksuid

damethos 3y ago

Why not just use auto-increment integers and expose them with something like this: https://www.npmjs.com/package/hashids https://www.npmjs.com/package/hashids (The linked library is just an example). Yes, you will need to transform the IDs before returning them to an external caller which is a little bit annoying but it's probably not that a big of a deal. Also another approach I've seen, which personally I find it a bit complicated, is to use auto-increment primary keys for the internal system and UUIDs for the public facing interactions.

cryptos 3y ago
Incrementing integers doesn't work well in a distributed system, where the IDs might be generated outside of the database (to have it before the transaction ends, for example).

xmdx 3y ago

That's what created_at and updated_at are for surely

sam_lowry_ 3y ago
From the ActiveRecord fame ;-)
yesimahuman 3y ago
I was going to ask, when would you only rely on a sequential id for temporal locality, wouldn't most people be indexing and sorting on `created_at` or something equivalent?
- Tehnix 3y ago
  You don’t need to need temporal elements, the simple fact that UUIDs are a bad fit for B-Trees means that simply inserting a bunch of data that relies on a UUIDv4 for its unique ID, will also run into these same problems. You’d typically see this as either lower performance of a table than you expect, or higher IOPS usage of your database (which gets expensive at scale).

jongjong 3y ago

I can't think of many use cases where I would sacrifice the beauty and elegance of UUIDs to optimize access times by a millisecond or two. UUID is totally worth the cost. UUID actually performs much better than I thought based on the author's example with a COUNT query. COUNT queries aren't very efficient because typically, all records are traversed; here we're talking about a 50% slowdown on 10 million records... How often do you need to access 10 million contiguous records? Most of the time, for user-facing apps, you'll be accessing 100 contiguous records at most and, in fact, most queries will access a single record... I suspect that the average per-query performance loss for a typical app is probably less than 5%. Also, you could simply index by a separate date/timestamp field if you need records to be ordered by time and probably won't incur any performance cost. IMO, unless you're building an app for high-frequency trading, auto-incrementing IDs aren't worth the pain and lack of flexibility.

jongjong 3y ago
Recently, I wrote a client-side wallet app for cryptocurrency use case and it required transactions to be created and signed entirely on the client-side and so the transaction UUID had to be created on the client side (before signing) and I was surprised at how elegant and simple the application's logic turned out to be (both on the front end and back end). One of the best things about UUIDs is that if your front end tries to create a resource and fails due to a bad connection, you can simply resend that exact same resource for creation again (with the same UUID) and you don't need to worry about duplicate records being inserted into the database since you would get an ID collision; it results in much simpler/cleaner code which is idempotent and deterministic by default. With auto-incrementing IDs, if there is a connection issue or other failure, it's not possible to cleanly figure out if a resource was already created or not since only the database knows what the ID of that resource was until that ID is sent back and reaches the client across the network. Just because the client did not receive a successful response from the server, it does not mean that the resource was not created; and if it was, you cannot know since the client has no way of referencing that resource in a reliable way. It just seems completely wrong that the client (which created the resource) cannot reference it until the database has inserted it. It's a hack to pretend that resource creation starts in the database, when in fact, it starts on the front end.

VWWHFSfQ 3y ago

My go-to pattern for many years now is to use a plain bigint autoincrement column for internal database relations and then a uuid for application-level identifiers and natural keys. Basically never use the uuid as the actual primary key because they're enormous and now the DBMS has to copy that gigantic number to every side of the relation. Don't do it

zzzeek 3y ago
Same, I'm surprised nobody is mentioning this. All the foreign key columns become uuids also and the DB becomes miserable to deal with.
sumtechguy 3y ago
This is a good answer. You want your primary/cluster key to usually be something that makes sense in your data. If you use something like UUID the placement can be basically random. That is usually in SQL is not a desirable trait. If you use it for a primary key you are basically saying you are fine with a memory cmp vs a register compare for you finding the right data. That can be undesirable too. UUIDs do have very desirable traits such as uniqueness. But that does come at a cost and usually you can fix that by deciding what process decides the source of truth in a different way.

londons_explore 3y ago

Note that if you use something like spanner, you never want data locality, because it will prevent your data being spread effectively between nodes. So your id's of top level entities should be something random.

londons_explore 3y ago

There are downsides to anything ascending/descending in a database too... They mess with table statistics. If you do a query like "SELECT * from users where creation_date > NOW-1h", the query analyzer doesn't know that there might be thousands of users created in the last hour. It is probably working from day-old statistics that say all users have a creation_date between 2008 and 2023-06-21. That makes it sometimes pick an exceptionally poor query plan. Ie. instead of your query taking 50 milliseconds, it might take 50 hours and involve an n^2 scan of all data in your database.

willvarfar 3y ago

> if you want to use UUID’s, try to use a sequential variant. UUID v7 is a good option. Hopefully it’s coming to PostgreSQL 17 Yeap, UUIDv7 directly addresses the issues in the article. Warmly recommended. (There is the issue that exposing ULIDs to users may 'leak' information about when things were created etc, but that is usually not a problem.)

rollcat 3y ago
I also like UUIDv8. It's broadly similar to v7 but the vendor is free to define how the timestamps are represented, how many bits to split between timestamps/randomness, define own packing, etc. So we've started making UUIDs that encode the current ISO8601 date+time in a human-readable format: YYYYMMDD-HHMM-VRRR-RRRR-RRRRRRRRR This is especially useful for things you have few of (no more than a couple per minute), that you regularly need to cross-reference with other systems (e.g. files on S3).
- JdeBP 3y ago
  Enough iterations in this direction, and people will come full circle to how message IDs operated on Usenet. <datetime.processID.sequencenumber@domain> for example.
- pgaddict 3y ago
  The one problem with this "perfectly" sequential UUIDs is that it can easily lead to index bloat. Imagine you have such sequential UUIDs generated over a year, for example. And then you delete e.g. 99% of old data (say, everything except some records that you're required to keep for audit purposes or whatever). If there was an index, the "old" part will be 99% empty. For regular UUIDs this would be fine, because new entries would get routed to this part of the index and the space would be reused. Not so for sequential UUIDs (v7/v8). This is mostly why year ago I wrote "sequential-uuids" extension, doing roughly what v7/v8 do, but wrapping the timestamp once in a while. Of course, if you don't delete data, this is not an issue and v7/v8 will work fine.
  - rollcat 3y ago

osigurdson 3y ago

On the one hand, a serial base id like https://example.com/user/items/55 https://example.com/user/items/55, seems less secure than a UUID based approach as if all else fails the UUID is still hard to guess. On the other, some systems (github private repos for example), don't seem to worry about how easily a URL can be guessed. Is it perhaps the case that probability of successful attack is not materially reduced in with a hard to guess url in the final analysis?

Timpy 3y ago

For me, the visual noise is a downside for UUIDs. A lot of time investigating data issues means glancing at query results and deciding if something looks unexpected. I just can't parse a UUID with my eyes that quick. I've come up against this at my current job a little too often and I'm cursing the decision to switch to UUIDs. I know, it's a balancing act of competing concerns. But for us moving to UUIDs was future proofing for a problem that never arose, and the senior dev who made us switch left the company a few years ago. I just don't like the dev experience of UUIDs in a world where you do have to get hands (and eyes) on the data all the time.

Pet_Ant 3y ago
Something I saw a longtime ago was hashing UUIDs into a RGB value and then colouring the background of the cell (at least when viewing in a DB IDE). That way you can quickly at a glance tell if it's worth going over character by character.
- Timpy 3y ago
  Wow I really love that idea. Next time I get stuck on a fix tinkering with my setup I'm going to check this out.
- adverbly 3y ago
  Holy crap this is brilliant. I'd just change the text color of the uuid itself though - no need to change the background(although you'd need to make sure that the hash function avoided your existing background color to maintain a high enough contrast ratio for readability). I want this as a vscode extension. Or maybe as a terminal plugin or something? Is that possible? Could tmux do it maybe?
michaelsalim 3y ago
Interesting take. I do agree there's some visual noise there, but not how you described it. UUID just takes so much screen space compared to its integer counterpart. If you don't have a good UI sorting things out it's quite annoying. Otherwise it's pretty great.

pfooti 3y ago

Weirdly, and this may be a side effect of writing code that uses Cloud Spanner, but I tend to think of uuidv4's random distribution through keyspace as a _good_ thing. My instinct is to not use sequential-ish indices/primary keys, because I don't want to hotspot one part of the storage with all my writes for today in the same tablet.

insanitybit 3y ago

Another (potentially!) significant problem with uuids is that they're inefficient to store. Compared to an 8 byte value obviously they double the storage size. But it's actually worse - if you have loosely ordered integers, even with gaps, you can compress those down to even less, like practically 1 byte on average. That makes uuids ~16x worse for disk storage, ~2x worse for memory storage (cache). That + Losing locality can be, for some workloads, a significant loss. Where UUIDs reign supreme for performance is in terms of generation - if you have a super high write load and really high latency requirements it may not be viable to have a single integer counter. Although, in my own testing, I've found Postgres is more than capable of hundreds of thousands of increments per second and if you're willing to allow for gaps/ interleaving in your counter (slight hit to locality) you're really unlikely to hit a bottleneck. Sequentual uuids help and are desirable but they still can't compete on storage :)

fabian2k 3y ago
I'm not aware of any situation where Postgres (without extensions) would compress ints that way? That is more of a column-oriented or time-series DB thing to me. Are there any cases in Postgres where this actually plays a role and sequential ints get compressed?
- insanitybit 3y ago
  Sorry, let me clarify. I used Postgres to generate the counters as external IDs into other data stores (so instead of `give me a new uuid` I said `hey postgres give me a new counter`. Postgres was only used to maintain the counters themselves in a tiny database where compression isn't relevant anyways. The other data stores where I used this were a combination of Parquet on S3 (where you get compression) and ScyllaDB (where you also get compression).
insanitybit 3y ago
Oh yeah, this also makes pagination trivial. You can basically just give your clients a literal number indicating where they are. So good, you basically get paging APIs for free.

deleted 3y ago

[deleted]

moi2388 3y ago

int key for internal use, guid for external purposes

coding123 3y ago

Use flakeids

neurostimulant 3y ago

CouchDB uses sequential UUID by default: https://docs.couchdb.org/en/stable/config/misc.html#uuids-configuration https://docs.couchdb.org/en/stable/config/misc.html#uuids-co... > Impact of UUID choices: the choice of UUID has a significant impact on the layout of the B-tree, prior to compaction. > For example, using a sequential UUID algorithm while uploading a large batch of documents will avoid the need to rewrite many intermediate B-tree nodes. A random UUID algorithm may require rewriting intermediate nodes on a regular basis, resulting in significantly decreased throughput and wasted disk space space due to the append-only B-tree design. > It is generally recommended to set your own UUIDs, or use the sequential algorithm unless you have a specific need and take into account the likely need for compaction to re-balance the B-tree and reclaim wasted space.

NicoJuicy 3y ago

Tbh. I use UUID's a lot, perhaps usefull to know that Deterministic UUID exist, eg. DeterministicGuid.Create(tenantNamespace, "my-tenant-name"); Note: https://github.com/Informatievlaanderen/deterministic-guid-generator https://github.com/Informatievlaanderen/deterministic-guid-g... for dotnet. Additionally, know that there are different versions of UUID's. If you want to create chronologic UUID's so that queries are more easily ordered, use the correct type.

hn_throwaway_99 3y ago

The new/upcoming UUID v7 really solves pretty much all of these problems: 1. They're ordered by a timestamp, so they preserve DB locality 2. They include a total of 74 bits of random data. This isn't enough to be used as unguessable keys, but it does offer some good protection if you have other bugs that could otherwise lead to IDOR vulnerabilities. 3. They're still 16 bytes, but IMO any minor hit to storage/time is completely worth it for the benefits they provide, especially since the other option is usually to have an integer primary key AND another "public ID" column that stores a UUID.

frodowtf 3y ago

With some basic knowledge about how a db stores data, there is nothing really "unexpected" about this behavior. It's weird though how little devs actually know or care about it.

aarondf 3y ago

I did a video covering choosing a primary key type for MySQL [1], including UUIDs. Long story short: you should probably use a bigint unless you have a pretty good reason not to. Good reasons exist! If you do use a UUID, make sure you use a version that is time-sorted. 1: https://planetscale.com/courses/mysql-for-developers/indexes/primary-key-data-types https://planetscale.com/courses/mysql-for-developers/indexes...

deleted 3y ago

[deleted]

bfrog 3y ago

Snowflake ids fit this sort of thing better, and maintain temporal locality. I ran into this exact issue when building out a graph like database in Postgres many moons ago. It’s probably less of an issue with fast nvme sad drives now, but on mechanical drives ordering and locality are massive.

ilyt 3y ago

How is any of that "unexpected" ? What did the author expected ?

samokhvalov 3y ago

We discussed some of these problems here during a Postgres.tv session, and developed a patch to support ULID / UUIDv7: https://www.youtube.com/watch?v=YPq_hiOE-N8 https://www.youtube.com/watch?v=YPq_hiOE-N8 And then Andrey proposed a patch in the pgsql-hackers mailing list: https://www.postgresql.org/message-id/flat/CAAhFRxitJv%3DyoGnXUgeLB_O%2BM7J2BJAmb5jqAT9gZ3bij3uLDA%40mail.gmail.com https://www.postgresql.org/message-id/flat/CAAhFRxitJv%3DyoG..., https://commitfest.postgresql.org/43/4388/ https://commitfest.postgresql.org/43/4388/ Everyone who can help (test, discuss, etc.) – please participate in that discussion. The standard is not finalized yet, but there some expectations that it will be, if it happens, it would be great to have this in future Postgres 17.

pksunkara 3y ago
Implementing support for UUIDv7 does not equal implementing support for ULID. ULID needs to be treated as a first class citizen (type, read format, storage format, converters) instead of being an afterthought result from UUIDv7. I have built a postgres extension for adding ULID support which does what I described. https://github.com/pksunkara/pgx_ulid https://github.com/pksunkara/pgx_ulid

seanhunter 3y ago

I’ll genuinely never understand why people benchmark in this way. They are doing a thing that is slow and inefficient in a fundamental way and then producing a blogpost about it being slow and inefficient in a much more trivial respect. If you care about performance, select count(uuid) from records; Makes absolutely no sense. You know the uuid is unique so you are deliberately selecting a value and then throwing it away just to count it. select count(1) from records; Would give the same value and could be answered from the index without requiring a scan of the table. This is true of any unique column in the table no matter what type (it doesn’t have to be a uuid). The fact that uuids are a bit slower than other types of keys when you scan the entire table unnecessarily seems beside the point.

ants_a 3y ago
I agree, though it's not the uniqueness, but not null constraint that matters here. PostgreSQL could, but doesn't right now, use the not null constraint to optimize the former to the latter. The actual case came to my attention because an ORM insisted on generating the count(uuid) variant and I thought it peculiar that the performance difference was so large. But silly ORMs aside, the same problem will happen on any index only range scan over an index that has uuid in it. For a more realistic case, a `count(*) where somecol = 'value'` with a `(somecol, uuid)` index will hit the same problem. I thought the rather hidden single entry visibility map buffer reference cache was an interesting example where random ordering can cause performance problems.
insanitybit 3y ago
I can't imagine that the author is saying "don't count uuids this way!" but instead is trying to explain how locality works in btree indices, using a trivial example to demonstrate it.
seanhunter 3y ago
I should add for people who are not aware, the same concept is very important to bear in mind if there is a WHERE EXISTS or WHERE NOT EXISTS subclause to your query. Something like select u.username as good_user from users u where not exists ( select 1 from naughty_users n where n.id = u.id ) …is generally going to be much much faster than what a lot of people instinctively do which is to select the username or user id from the inner query. Since you’re just checking for (non)existence it doesn’t matter what the inner query returns so select 1 will answer the query from the index (assuming the id is indexed which if it isn’t you have bigger problems). If you spend a while looking at explain plans for your queries you will spot common patterns like this where you can avoid a table scan often.

JoeAltmaier 3y ago

The correlation of locality and sequential keys was a coincidence. It's unfortunate that folks rely on this coincidence for performance. Databases can be made with better algorithms now that UUIDs are common. It would be a mistake to enshrine sequential indexes as some special optimization, just to be blown away later when better algorithms get used.

penciltwirler 3y ago

Have a look at ULIDs