3 ms·

I feel that you don't understand what locality is about: the property of IDs that were generated closely together in time to be close together numerically. You

by patrec 3y ago

I feel that you don't understand what locality is about: the property of IDs that were generated closely together in time to be close together numerically. You don't get that by "hashing" the UUID (which makes no sense anyway, since you might as well just take some truncation of the UUID). In fact the whole idea behind a hash is to destroy this property of the input data. The reason the numerical locality matters is that it is much more efficient to in-sequence-insert several numbers that are close together into an index than to in-sequence-insert the identical amount of randomly distributed numbers. The GP was talking about the first graph here: https://www.2ndquadrant.com/en/blog/on-the-impact-of-full-page-writes/ https://www.2ndquadrant.com/en/blog/on-the-impact-of-full-pa...

ok123456 3y ago
I thought you were talking about cache locality within the CPU. Real cache locality. If you care about the insert location, why not just add a brin index on a timestamp field and use that instead of assuming that the index is sequential.
- insanitybit 3y ago
  CPU cache locality is not "real cache locality", it is just another place where caches exist and locality is optimized for. Your solution wouldn't work for CPUs either, other than that you could fit more data into a cache line - but that's like saying "increase the cache size to solve this problem", which obviously can help but is not addressing the inherent issue.
- patrec 3y ago
  How would adding a BRIN index help in any way with reducing the discussed problems, such as write amplification?
  - pgaddict 3y ago
    This is a bit confusing, as it mixes two things - BRIN index and index on a timestamp. The main source of write amplification comes from updating random pages of the btree index. Imagine inserting 10 random UUID values into a large index - it's pretty likely those will go into 10 different leaf pages. And every first update of a page after a checkpoint (which typically happens every 30 minutes or so), we have to write a FPI (i.e. the whole 8kB page) to WAL. So because btrees are based on ordering, random values end up on random leaf pages, causing write amplification. If you have BRIN index on UUID column, this does not happen, because the index is not based on ordering but location in the table. If the 10 rows get appended to the same table page, that'll be just 1 write, with one FPI. This is why BRIN does not have the write amplification issue. But it's also a bit pointless, because BRIN on random data is pretty useless for querying (Well, at least the minmax indexes, are. Let's ignore BRIN bloom indexes here.) If you create BRIN on timestamp, that's not going to have write amplification problem, and it'll be good for querying. The thing is - BTREE would not have write amplification problem either, because the timestamps are going to be sequential (hence no updates to random leaf pages).
    - saltcured 3y ago
      Right, you just need to avoid having the btree index on the UUID field. Similarly, don't pose queries to sort by the randomized UUID field either. This is where the often maligned hash index type could be useful, to allow lookup of individual rows by UUID without all the expense of a btree index maintenance. Use other fields for ordering that have better write locality. What this means in practice, of course, is that you shouldn't expect to do application driven pagination with UUID keys either. You would need to expose some other boundary marker with a total order that works well with btrees. And this could bring you back to "leaking" predictable key material that you were trying to hide by adopting UUIDs...

by patrec 3y ago

ok123456 3y ago

I thought you were talking about cache locality within the CPU. Real cache locality. If you care about the insert location, why not just add a brin index on a timestamp field and use that instead of assuming that the index is sequential.

insanitybit 3y ago
CPU cache locality is not "real cache locality", it is just another place where caches exist and locality is optimized for. Your solution wouldn't work for CPUs either, other than that you could fit more data into a cache line - but that's like saying "increase the cache size to solve this problem", which obviously can help but is not addressing the inherent issue.
patrec 3y ago
How would adding a BRIN index help in any way with reducing the discussed problems, such as write amplification?
- pgaddict 3y ago
  This is a bit confusing, as it mixes two things - BRIN index and index on a timestamp. The main source of write amplification comes from updating random pages of the btree index. Imagine inserting 10 random UUID values into a large index - it's pretty likely those will go into 10 different leaf pages. And every first update of a page after a checkpoint (which typically happens every 30 minutes or so), we have to write a FPI (i.e. the whole 8kB page) to WAL. So because btrees are based on ordering, random values end up on random leaf pages, causing write amplification. If you have BRIN index on UUID column, this does not happen, because the index is not based on ordering but location in the table. If the 10 rows get appended to the same table page, that'll be just 1 write, with one FPI. This is why BRIN does not have the write amplification issue. But it's also a bit pointless, because BRIN on random data is pretty useless for querying (Well, at least the minmax indexes, are. Let's ignore BRIN bloom indexes here.) If you create BRIN on timestamp, that's not going to have write amplification problem, and it'll be good for querying. The thing is - BTREE would not have write amplification problem either, because the timestamps are going to be sequential (hence no updates to random leaf pages).
  - saltcured 3y ago
    Right, you just need to avoid having the btree index on the UUID field. Similarly, don't pose queries to sort by the randomized UUID field either. This is where the often maligned hash index type could be useful, to allow lookup of individual rows by UUID without all the expense of a btree index maintenance. Use other fields for ordering that have better write locality. What this means in practice, of course, is that you shouldn't expect to do application driven pagination with UUID keys either. You would need to expose some other boundary marker with a total order that works well with btrees. And this could bring you back to "leaking" predictable key material that you were trying to hide by adopting UUIDs...