News for hackers. Stuff that matters.
Re:How to Get the Most Out of Postgres Memory Settings by sgarland on Wednesday June 12, 2024 @10:23AM (#40658525)
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

Re:How to Get the Most Out of Postgres Memory Settings by quadrature on Wednesday June 12, 2024 @11:35AM (#40659277)
>though ULID has the same problem

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

Re:How to Get the Most Out of Postgres Memory Settings by sgarland on Wednesday June 12, 2024 @12:12PM (#40659729)
You’re correct; I was thinking of NanoID, and updated my post to reflect this.
Re:How to Get the Most Out of Postgres Memory Settings by arethuza on Wednesday June 12, 2024 @11:40AM (#40659347)
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()?
Re:How to Get the Most Out of Postgres Memory Settings by auspiv on Wednesday June 12, 2024 @10:35AM (#40658658)
UUID7 basic information/examples - https://uuid7.com
Re:How to Get the Most Out of Postgres Memory Settings by kbolino on Wednesday June 12, 2024 @01:26PM (#40660677)
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.

Re:How to Get the Most Out of Postgres Memory Settings by hot_gril on Wednesday June 12, 2024 @07:52PM (#40664444)
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.

Re:How to Get the Most Out of Postgres Memory Settings by aidos on Wednesday June 12, 2024 @03:10PM (#40661784)
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.

Re:How to Get the Most Out of Postgres Memory Settings by sgarland on Wednesday June 12, 2024 @05:58PM (#40663672)
> 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-...

Re:How to Get the Most Out of Postgres Memory Settings by aidos on Wednesday June 12, 2024 @06:36PM (#40663960)
Ah nice. Thanks for the extra info. I’m weirdly fascinated by the inner workings of Postgres.
Re:How to Get the Most Out of Postgres Memory Settings by Cwizard on Thursday June 13, 2024 @02:11AM (#40666453)
You might like: ‘PostgreSQL 14 Internals’ by Egor Rogov
Re:How to Get the Most Out of Postgres Memory Settings by srcreigh on Wednesday June 12, 2024 @04:26PM (#40662689)
> 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?

Re:How to Get the Most Out of Postgres Memory Settings by Izkata on Wednesday June 12, 2024 @05:15PM (#40663201)
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.

Re:How to Get the Most Out of Postgres Memory Settings by srcreigh on Thursday June 20, 2024 @01:38AM (#40735277)
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.