Re: [HACKERS] The case for removing replacement selection sort

2017-09-29 Thread Peter Geoghegan
On Fri, Sep 29, 2017 at 7:19 AM, Robert Haas wrote: > That supports your theory that there's some confounding factor in the > CREATE INDEX case, such as I/O scheduling. Since this machine has an > SSD, I guess I don't have a mental model for how that works. We're > not

Re: [HACKERS] The case for removing replacement selection sort

2017-09-29 Thread Robert Haas
On Thu, Sep 28, 2017 at 6:44 PM, Peter Geoghegan wrote: > I'm glad to hear that. But, I should reiterate that if sorting > actually gets faster when my patch is applied, then that's something > that I consider to be a bonus. (This is primarily a refactoring patch, > to remove a

Re: [HACKERS] The case for removing replacement selection sort

2017-09-28 Thread Peter Geoghegan
On Thu, Sep 28, 2017 at 3:18 PM, Robert Haas wrote: > On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan wrote: >> With the additional enhancements made to Postgres 10, I doubt that >> there are any remaining cases where it wins. > > I tried my favorite sorting

Re: [HACKERS] The case for removing replacement selection sort

2017-09-28 Thread Robert Haas
On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan wrote: > With the additional enhancements made to Postgres 10, I doubt that > there are any remaining cases where it wins. I tried my favorite sorting test case -- pgbench -i -s 300 and then reindex index pgbench_accounts_pkey. I

Re: [HACKERS] The case for removing replacement selection sort

2017-09-27 Thread Peter Geoghegan
On Wed, Sep 27, 2017 at 12:06 AM, Simon Riggs wrote: >> I think we should remove the replacement_sort_tuples GUC, and kill >> replacement selection entirely. There is no need to do this for >> Postgres 10. I don't feel very strongly about it. It just doesn't make >> sense

Re: [HACKERS] The case for removing replacement selection sort

2017-09-27 Thread Simon Riggs
On 14 July 2017 at 23:20, Peter Geoghegan wrote: > I think we should remove the replacement_sort_tuples GUC, and kill > replacement selection entirely. There is no need to do this for > Postgres 10. I don't feel very strongly about it. It just doesn't make > sense to continue to

Re: [HACKERS] The case for removing replacement selection sort

2017-09-15 Thread Peter Geoghegan
Tomas' e-mail from earlier today, that I've already replied to directly, seems to have been lost to the mailing list. This must be due to having a 1MB attachment (results spreadsheet), which seems a bit aggressive as a reason to withold it IMV. Here is a link to his results, converted to a Google

Re: [HACKERS] The case for removing replacement selection sort

2017-09-15 Thread Peter Geoghegan
On Fri, Sep 15, 2017 at 6:34 AM, Tomas Vondra wrote: > e5-2620-v4 > -- > - probably the CPU we should be looking at, as it's the current model > - in some cases this gives us 3-5x speedup with low work_mem settings > - consider for example the very last line,

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Peter Geoghegan
On Wed, Sep 6, 2017 at 2:55 PM, Peter Geoghegan wrote: > On Wed, Sep 6, 2017 at 2:47 PM, Thomas Munro > wrote: >>> I attach a patch to remove replacement selection, which I'll submit to CF 1. >> >> This breaks the documentation build, because >>

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Peter Geoghegan
On Mon, Sep 11, 2017 at 8:50 AM, Robert Haas wrote: > On Mon, Sep 11, 2017 at 11:47 AM, Tomas Vondra > wrote: >> The question is what is the optimal replacement_sort_tuples value? I >> assume it's the number of tuples that effectively uses CPU

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Peter Geoghegan
On Mon, Sep 11, 2017 at 8:47 AM, Tomas Vondra wrote: > The question is what is the optimal replacement_sort_tuples value? See my remarks to Robert just now. I think that it's incredibly hard to set replacement_sort_tuples sensibly in 9.6. As of Postgres 10, it is

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Peter Geoghegan
On Mon, Sep 11, 2017 at 8:32 AM, Robert Haas wrote: > On Sun, Sep 10, 2017 at 9:39 PM, Peter Geoghegan wrote: >> To be clear, you'll still need to set replacement_sort_tuples high >> when testing RS, to make sure that we really use it for at least the >>

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Peter Geoghegan
On Mon, Sep 11, 2017 at 8:17 AM, Tomas Vondra wrote: > Overall I think the results show quite significant positive impact of > the patch. There are a few cases of regression, but ISTM those may > easily be noise as it's usually 0.03 vs 0.04 second, or something. I'll

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Robert Haas
On Mon, Sep 11, 2017 at 11:47 AM, Tomas Vondra wrote: > The question is what is the optimal replacement_sort_tuples value? I > assume it's the number of tuples that effectively uses CPU caches, at > least that's what our docs say. So I think you're right it to 1B

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Tomas Vondra
On 09/11/2017 05:32 PM, Robert Haas wrote: > On Sun, Sep 10, 2017 at 9:39 PM, Peter Geoghegan wrote: >> To be clear, you'll still need to set replacement_sort_tuples high >> when testing RS, to make sure that we really use it for at least the >> first run when we're expected to.

Re: [HACKERS] The case for removing replacement selection sort

2017-09-11 Thread Robert Haas
On Sun, Sep 10, 2017 at 9:39 PM, Peter Geoghegan wrote: > To be clear, you'll still need to set replacement_sort_tuples high > when testing RS, to make sure that we really use it for at least the > first run when we're expected to. (There is no easy way to have > testing

Re: [HACKERS] The case for removing replacement selection sort

2017-09-10 Thread Peter Geoghegan
On Sun, Sep 10, 2017 at 5:59 PM, Tomas Vondra wrote: > OK, so 1MB, 4MB, 8MB, 32MB? Right. > Ah, so you suggest doing all the tests on current master, by only > tweaking the replacement_sort_tuples value? I've been testing master vs. > your patch, but I guess

Re: [HACKERS] The case for removing replacement selection sort

2017-09-10 Thread Tomas Vondra
On 09/11/2017 02:22 AM, Peter Geoghegan wrote: > On Sun, Sep 10, 2017 at 5:07 PM, Tomas Vondra > wrote: >> I'm currently re-running the benchmarks we did in 2016 for 9.6, but >> those are all sorts with a single column (see the attached script). But >> it'd be good

Re: [HACKERS] The case for removing replacement selection sort

2017-09-10 Thread Peter Geoghegan
On Sun, Sep 10, 2017 at 5:07 PM, Tomas Vondra wrote: > I'm currently re-running the benchmarks we did in 2016 for 9.6, but > those are all sorts with a single column (see the attached script). But > it'd be good to add a few queries testing sorts with multiple keys.

Re: [HACKERS] The case for removing replacement selection sort

2017-09-10 Thread Tomas Vondra
On 09/11/2017 01:03 AM, Peter Geoghegan wrote: > On Sat, Sep 9, 2017 at 8:28 AM, Greg Stark wrote: >> This may be a bit "how long is a piece of string" but how do those two >> compare with string sorting in an interesting encoding/locale -- say >> /usr/share/dict/polish in pl_PL

Re: [HACKERS] The case for removing replacement selection sort

2017-09-10 Thread Peter Geoghegan
On Sat, Sep 9, 2017 at 8:28 AM, Greg Stark wrote: > This may be a bit "how long is a piece of string" but how do those two > compare with string sorting in an interesting encoding/locale -- say > /usr/share/dict/polish in pl_PL for example. It's certainly true that > people do sort

Re: [HACKERS] The case for removing replacement selection sort

2017-09-09 Thread Greg Stark
On 8 September 2017 at 18:06, Peter Geoghegan wrote: > * It's still faster with int4/int8 comparisons on modern hardware, and > I think that most ordered inputs will be of those types in practice. This may be a bit "how long is a piece of string" but how do those two compare with

Re: [HACKERS] The case for removing replacement selection sort

2017-09-08 Thread Peter Geoghegan
On Thu, Sep 7, 2017 at 2:49 PM, Robert Haas wrote: > On Thu, Sep 7, 2017 at 5:38 PM, Tomas Vondra > wrote: >> Do we need/want to repeat some of that benchmarking on these patches? I >> don't recall how much this code changed since those

Re: [HACKERS] The case for removing replacement selection sort

2017-09-07 Thread Robert Haas
On Thu, Sep 7, 2017 at 5:38 PM, Tomas Vondra wrote: > Do we need/want to repeat some of that benchmarking on these patches? I > don't recall how much this code changed since those benchmarks were done > in the 9.6 cycle. +1 for some new benchmarking. I'm all for

Re: [HACKERS] The case for removing replacement selection sort

2017-09-07 Thread Tomas Vondra
Hi, On 08/31/2017 02:56 AM, Peter Geoghegan wrote: > On Wed, Aug 30, 2017 at 5:38 PM, Robert Haas wrote: >> Wow. Just to be clear, I am looking for the BEST case for replacement >> selection, not the worst case. But I would have expected that case to >> be a win for

Re: [HACKERS] The case for removing replacement selection sort

2017-09-06 Thread Peter Geoghegan
On Wed, Sep 6, 2017 at 2:47 PM, Thomas Munro wrote: >> I attach a patch to remove replacement selection, which I'll submit to CF 1. > > This breaks the documentation build, because > doc/src/sgml/release-9.6.sgml still contains

Re: [HACKERS] The case for removing replacement selection sort

2017-09-06 Thread Thomas Munro
On Fri, Sep 1, 2017 at 6:00 AM, Peter Geoghegan wrote: > On Wed, Aug 30, 2017 at 4:59 PM, Peter Geoghegan wrote: >> I may submit the simple patch to remove replacement selection, if >> other contributors are receptive. Apart from everything else, the >>

Re: [HACKERS] The case for removing replacement selection sort

2017-08-31 Thread Peter Geoghegan
On Wed, Aug 30, 2017 at 4:59 PM, Peter Geoghegan wrote: > I may submit the simple patch to remove replacement selection, if > other contributors are receptive. Apart from everything else, the > "incrementalism" of replacement selection works against cleverer batch > memory

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Peter Geoghegan
On Wed, Aug 30, 2017 at 5:38 PM, Robert Haas wrote: > Wow. Just to be clear, I am looking for the BEST case for replacement > selection, not the worst case. But I would have expected that case to > be a win for replacement selection, and it clearly isn't. I can >

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Robert Haas
On Wed, Aug 30, 2017 at 6:14 PM, Peter Geoghegan wrote: > On Wed, Aug 30, 2017 at 3:01 PM, Robert Haas wrote: >> That may all be true, but my point is that if it wins in some cases, >> we should keep it -- and proving it no longer wins in those cases will >>

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Peter Geoghegan
On Wed, Aug 30, 2017 at 3:14 PM, Peter Geoghegan wrote: > This is significantly faster, in a way that's clearly reproducible and > consistent, despite the fact that we need about 10 merge passes > without replacement selection, and only have enough memory for 7 > tapes. I think that

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Peter Geoghegan
On Wed, Aug 30, 2017 at 3:01 PM, Robert Haas wrote: > That may all be true, but my point is that if it wins in some cases, > we should keep it -- and proving it no longer wins in those cases will > require running tests. That's not hard. On my laptop: $ pgbench -i -s 100

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Robert Haas
On Wed, Aug 30, 2017 at 4:18 PM, Peter Geoghegan wrote: > On Wed, Aug 30, 2017 at 12:51 PM, Robert Haas wrote: >> On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan wrote: >>> With the additional enhancements made to Postgres 10, I doubt that >>>

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Peter Geoghegan
On Wed, Aug 30, 2017 at 12:51 PM, Robert Haas wrote: > On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan wrote: >> With the additional enhancements made to Postgres 10, I doubt that >> there are any remaining cases where it wins. > > The thing to do about that

Re: [HACKERS] The case for removing replacement selection sort

2017-08-30 Thread Robert Haas
On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan wrote: > With the additional enhancements made to Postgres 10, I doubt that > there are any remaining cases where it wins. The thing to do about that would be to come up with some cases where someone might plausibly think it would

[HACKERS] The case for removing replacement selection sort

2017-07-14 Thread Peter Geoghegan
There was a number of improvements to tuplesort.c external sort merging made for Postgres 10. One in particular, the changes to merge heap maintenance that occurred for commit 24598337c8d, really helped with presorted cases -- cases when there was an (inverse) physical/logical correlation.