3 ms·
UUIDv4 specifically (though ULID [EDIT: this is incorrect, I was thinking of NanoID] has the same problem). Anything non-k-sortable will bloat a B+tree index, c
by sgarland 2y ago
UUIDv4 specifically (though ULID [EDIT: this is incorrect, I was thinking of NanoID] has the same problem). Anything non-k-sortable will bloat a B+tree index, causing far more reads than should be required.
MySQL (technically InnoDB) and SQL Server have a huge problem with them due to their design as a clustering index – since the tuples are physically located, or clustered, around the PK, the random nature means that doing a simple query like "SELECT id FROM customer WHERE date_created > NOW() - INTERVAL 1 WEEK" means that the hits are going to be on tons of different pages. Even if everything is cached, that's still a lot of extra work.
Postgres has its own problems with them as well. In the above query, it's possible that it could be an index-only scan. Great, you don't have to dereference the pointer to find the tuple in the heap! Except you still have to go through the Visibility Map, and it's going to be extremely bloated with a UUIDv4 PK. Additionally, due to the combination of how Postgres manages the A in ACID (via `full_page_writes`) and its MVCC implementation, a change to any indexed column in a table results in the entire row being re-written. While logically sequential tuples may be physically co-located (which would be ideal from a write perspective), the index pages are highly unlikely to be if there are non-k-sortable keys, so now you've bloated the WAL as well.
If you must use a UUID (I maintain you generally don't – PlanetScale uses integers internally [0], so clearly it can be done at scale), UUIDv7 is probably the best from a DB performance perspective.
[0]: https://github.com/planetscale/discussion/discussions/366 https://github.com/planetscale/discussion/discussions/366
- auspiv 2y agoUUID7 basic information/examples - https://uuid7.com https://uuid7.com
- deleted 2y ago[deleted]
- quadrature 2y ago>though ULID has the same problem I thought that ULID was meant to solve these issues by being sortable, is that not right ?.
- sgarland 2y agoYou’re correct; I was thinking of NanoID, and updated my post to reflect this.
- arethuza 2y agoThat presumably explains why some of Microsoft's own products use sequentially assigned GUIDs in SQL Server rather than random ones - using NEWSEQUENTIALID() rather than NEWID()?
- kbolino 2y agoPostgreSQL also supports a hash index type, which should be able to handle random (v4) UUIDs pretty well. Since there's no meaning to the sort order on random UUIDs anyway, the limitation to exact comparisons (=) shouldn't be a problem. It doesn't seem like you can specify what index type is used to implement the PRIMARY KEY constraint, though, so this is really only useful for certain situations.
- hot_gril 2y agoPostgres hash indexes were sorta unusable until a few years ago, and in my experience they weren't any faster back then. Haven't tried again recently, but if I did, I would run benchmarks before trusting it. Also, giving credit where it's due, someone on HN showed me why even this option is less scalable in theory than a btree with semi-ordered keys: https://news.ycombinator.com/item?id=40590760 https://news.ycombinator.com/item?id=40590760 Still, UUID4 is a good default for publicly visible IDs since anything else leaks info. But there's almost no need to have one as a PK.
- aidos 2y agoI don’t think the visibility map suffers from bloat. It’s a bitmap with 1 bit per page. You might have more pages due to the extra size of each tuple, but it’s not likely to be a big difference.
- sgarland 2y ago> 1 bit per page Close, it’s 2 bits/page :-) It’s not that it bloats, it’s that the hits are scattered among many pages. My wording wasn’t great on that point. Some tests demonstrating this are here [0]. [0]: https://www.cybertec-postgresql.com/en/unexpected-downsides-of-uuid-keys-in-postgresql/ https://www.cybertec-postgresql.com/en/unexpected-downsides-...
- deleted 2y ago[deleted]
- deleted 2y ago[deleted]
- srcreigh 2y ago> MySQL (technically InnoDB) and SQL Server have a huge problem with them due to their design as a clustering index – since the tuples are physically located, or clustered, around the PK, the random nature means that doing a simple query like "SELECT id FROM customer WHERE date_created > NOW() - INTERVAL 1 WEEK" means that the hits are going to be on tons of different pages. Even if everything is cached, that's still a lot of extra work. How do you fix this problem in Postgres?
- Izkata 2y agoThe postgres query planner has a correlation statistic for how well indexes match the order of the table data on disk, and if it's bad and the query is expected to return enough rows, it'll skip the index entirely. Instead it'll do a sequential scan and sort, to work with the disk cache instead of against it. Postgres provides a CLUSTER command to reorder the table data on disk to match a given index, resulting in a high correlation and allowing it to do an index scan without the penalty for random disk access. If you're on an SSD or know you have enough memory to have all the data cached you can also disable the random access penalty in the configuration; it exists mainly for spinning disks.
- srcreigh 2y agoImo I agree CLUSTER should help, although pg_repack is even better, since it doesn't yknow hold an exclusive lock while it copies the entire table. pg_repack still is very slow compared to consistent BTree rebalancing in MySQL. The problem isn't fixed with SSD or RAM or the settings in Postgres. Fast random access is great, but if your data isn't localized you are leaving a 100x optimization on the table. The original comment I replied to explained the data localization problem as if it was a MySQL problem and Postgres doesn't have the issue. That's like saying that Rust allows unsafe and this can cause memory corruption, so let's use C++. It's hard to understate how little sense it makes. Postgres is basically the only DB which doesn't offer a decent solution for data localization. Every other DB lets you control the layout of rows automatically with minimal resource overhead, postgres tools are extremely bad in comparison.