It is a common complaint in discussions about sort algorithms that the case for sorting numbers is a degenerate case and 'real' cases involve at least pointer chasing, which can make the cost of compares to stop being constant time, or have a constant time that is greater than log(n) (or worse, n).

Sometimes locality of reference may increase the total number of comparisons but decrease the average cost considerably. For practical applications like databases, it's the runtime that matters, not the theory.

> performance (relative to PG14) seems to get worse as work_mem increases and the ratio of table size to work_mem decreases

Do you have any source for this? This is the first time I've ever heard this and it seems contrary to everything I've read.

(blog author here) Yes, thanks for raising this. I didn't manage to complete my analysis for the regression at 64MB work_mem before publishing the blog. I drew up my analysis on https://www.postgresql.org/message-id/CAApHDvqXpLzav6dUeR5vO... shortly after publishing. Basically it relates to the generation memory context having a slightly larger chunk header than the original aset context combined with the tuple width of my test table being exactly 64 bytes, which results in no power-of-2 rounding savings. This causes slightly fewer tuples to be stored per batch in PG15, which results in more batches (tapes) and slower performance. If I'd added another column to that table the results would have been very different. PG14 would have rounded the allocation size up to 128 bytes and only about half the tuples would have been sorted per tape. The allocation size would be 72-bytes in PG15 with an extra column in the test table.