4 ms·

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 a

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.

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.