MIME-Version: 1.0
In-Reply-To: 
 <CA+TgmobfERYNqztHVdAuuwiZh+EJYAOvHakr8iOZczbNV23nBQ@mail.gmail.com>
References: 
 <CAM3SWZQVSpNeHHKKq-rjJddOcbpdmyHDJUMBBL2-AP2R+4YCHg@mail.gmail.com>
 <CAMkU=1ym2N-v+3=aMm9m-h1A941gQV7CgM9HJuwhRFu-8tHFaw@mail.gmail.com>
 <CAM3SWZQS==-K+SpLsmPdzQ=nrXKMhyNDMELfJKWbpKx0a1+sdg@mail.gmail.com>
 <CA+TgmoakcV5FzZwo+WNwbpnXwbY3N+qVs_zKdmE_OYmfivWnkQ@mail.gmail.com>
 <CAM3SWZTX5=nHxPpogPirQsH4cR+BpQS6r7Ktax0HMQiNLf-1qA@mail.gmail.com>
 <CA+Tgmob9ssG0XB4-GzPARCe0C8gXzHBCrAzNyout1oWj+9Nc9Q@mail.gmail.com>
 <CAM3SWZTR3UE2FEaaAiDbs7N31Td1KufQDAXKeVi4hDMva0PRjQ@mail.gmail.com>
 <CA+TgmobfERYNqztHVdAuuwiZh+EJYAOvHakr8iOZczbNV23nBQ@mail.gmail.com>
Date: Fri, 20 Nov 2015 14:58:52 -0800
Message-ID: 
 <CAM3SWZRZ_ChN6FOOnOR8fc-DcdJB2GJtbfrpOrrh41HfcbWaBQ@mail.gmail.com>
Subject: Re: Using quicksort for every external sort run
From: Peter Geoghegan <pg@heroku.com>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Jeff Janes <jeff.janes@gmail.com>,
 Pg Hackers <pgsql-hackers@postgresql.org>,
 Heikki Linnakangas <hlinnaka@iki.fi>, Simon Riggs <simon@2ndquadrant.com>
Content-Type: text/plain; charset=UTF-8
Precedence: bulk
Sender: pgsql-hackers-owner@postgresql.org

On Fri, Nov 20, 2015 at 12:52 PM, Robert Haas <robertmhaas@gmail.com> wrote:
> That's what I was asking about.  It seemed to me that you were saying
> we could ignore those cases, which doesn't seem to me to be true.

I've been around for long enough to know that there are very few cases
that can be ignored.  :-)

>> The latter 16MB work_mem example query/table is still faster with a
>> 12MB work_mem than master, even with multiple passes. Quite a bit
>> faster, in fact: about 37 seconds on master, to about 24.7 seconds
>> with the patches (same for higher settings short of 16MB).
>
> Is this because we save enough by quicksorting rather than heapsorting
> to cover the cost of the additional merge phase?
>
> If not, then why is it happening like this?

I think it's because of caching effects alone, but I am not 100% sure
of that. I concede that it might not be enough to make up for the
additional I/O on some systems or platforms. The fact remains,
however, that the patch was faster on the unsympathetic case I ran on
the machine I had available (which has an SSD), and that I really have
not managed to find a case that is regressed after some effort.

>> I should point out that there is no evidence that any case has been
>> regressed, let alone written off entirely or ignored. I looked. I
>> probably have not been completely exhaustive, and I'd be willing to
>> believe there is something that I've missed, but it's still quite
>> possible that there is no downside to any of this.
>
> If that's so, it's excellent news.

As I mentioned up-thread, maybe I shouldn't have brought all the
theoretical justifications for killing replacement selection into the
discussion so early. Those observations on replacement selection
(which are not my own original insights) happen to be what spurred
this work. I spent so much time talking about how irrelevant
multi-pass merging was that people imagined that that was severely
regressed, when it really was not. That just happened to be the way I
came at the problem.

The numbers speak for themselves here. I just want to be clear about
the disadvantages of what I propose, even if it's well worth it
overall in most (all?) cases.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers