3 ms·

One graph has sorting a 10GB table and refers to it as a “Large sort”… is 10GB large any more?

d_watt 4y ago
Not for OLAP, but this seems to be about OLTP. If you're trying to sort 10GB of data for a traditional OLTP query, I would consider that "too large" and need of some data structure optimization. Also it's specifically about queries where the sorted data is too big for memory: > The final change is aimed at larger scale sorts that exceed the size of work_mem significantly. The algorithm which merges individual tapes was changed to use a k-way merge. When the number of tapes is large, less I/O is required than the original polyphase merge algorithm.
- hinkley 4y ago
  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.
dagw 4y ago
"Large" in this context is stated to mean significantly larger than work_mem, which defaults to 4MB out of the box. Interestingly performance (relative to PG14) seems to get worse as work_mem increases and the ratio of table size to work_mem decreases. If this holds it should mean that for a fixed work_mem PG15 performance (again relative to PG14) should improve as table size increases.
- pigcat 4y ago
  > 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.
  - d_watt 4y ago
    It's in the article, the section being discussed in this thread: https://www.citusdata.com/blog/2022/05/19/speeding-up-sort-performance-in-postgres-15/#change4 https://www.citusdata.com/blog/2022/05/19/speeding-up-sort-p...
- davidrowley 4y ago
  (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_RBh_feHrHMLhigVQXw9jHCyKP9PA@mail.gmail.com 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.

Not for OLAP, but this seems to be about OLTP. If you're trying to sort 10GB of data for a traditional OLTP query, I would consider that "too large" and need of some data structure optimization. Also it's specifically about queries where the sorted data is too big for memory: > The final change is aimed at larger scale sorts that exceed the size of work_mem significantly. The algorithm which merges individual tapes was changed to use a k-way merge. When the number of tapes is large, less I/O is required than the original polyphase merge algorithm.

hinkley 4y ago
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.

dagw 4y ago

"Large" in this context is stated to mean significantly larger than work_mem, which defaults to 4MB out of the box. Interestingly performance (relative to PG14) seems to get worse as work_mem increases and the ratio of table size to work_mem decreases. If this holds it should mean that for a fixed work_mem PG15 performance (again relative to PG14) should improve as table size increases.

pigcat 4y ago
> 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.
- d_watt 4y ago
  It's in the article, the section being discussed in this thread: https://www.citusdata.com/blog/2022/05/19/speeding-up-sort-performance-in-postgres-15/#change4 https://www.citusdata.com/blog/2022/05/19/speeding-up-sort-p...
davidrowley 4y ago
(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_RBh_feHrHMLhigVQXw9jHCyKP9PA@mail.gmail.com 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.