Hacker News Reader

PostgreSQL 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.

Postgres 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

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.

UUID7 basic information/examples - https://uuid7.com

>though ULID has the same problem

I thought that ULID was meant to solve these issues by being sortable, is that not right ?.

You’re correct; I was thinking of NanoID, and updated my post to reflect this.

> 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?

The 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.

Imo 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.

That 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()?

I 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.

> 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-...

Ah nice. Thanks for the extra info. I’m weirdly fascinated by the inner workings of Postgres.

You might like: ‘PostgreSQL 14 Internals’ by Egor Rogov