Subject: Re: Fwd: GSOC 2018 Project - A New Sorting Routine
To: Kefan Yang <starordust@gmail.com>,
 PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
References: 
 <CAF448YLZz5cD+w5qYQGMcfFPY9zAu2mkkiCtOPSBJmwbjuPNig@mail.gmail.com>
 <57ae7691-6dc8-d6d0-361a-a7269e656273@2ndquadrant.com>
 <CAF448YKLbmmSPbb_AFEaTKozjnFOEfT+s2eiSjfH=us34VNr4w@mail.gmail.com>
 <CAF448YK0xhqK6mg3EeP-dt4j9V-VxkG8Vswmrt3t90OYSrNSsQ@mail.gmail.com>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <2af33cf9-16cf-df04-e8c4-6ab33a1b6f68@2ndquadrant.com>
Date: Sat, 14 Jul 2018 03:03:21 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.5.2
MIME-Version: 1.0
In-Reply-To: 
 <CAF448YK0xhqK6mg3EeP-dt4j9V-VxkG8Vswmrt3t90OYSrNSsQ@mail.gmail.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Precedence: bulk

On 07/14/2018 12:04 AM, Kefan Yang wrote:
> 
> ...
>
>     And finally, I see the PDF reports "CPU clocks" but I'm not sure what
>     that actually is? Is that elapsed time in milliseconds or something
>     else?
> 
> 
> Sorry for the confusion, but "CPU clocks" actually means CPU clock
> ticks, which are units of time of a constant but system-specific length.
> 

OK, how do you measure this metric?

> After reading your test results, I think the main problems of intro sort are
> 
> 1. Slow on CREATE INDEX cases.
> 
> I am still trying to figure out where the bottleneck is. Is the data
> pattern in index creation very different from other cases? Also,
> pg_qsort has 10%-20% advantage at creating index even on sorted data
> (faster CPU, N = 1000000). This is very strange to me since the two
> sorting routines execute exactly the same code when the input data is
> sorted.
> 
> 2. Slow on faster CPU and large data set.
> 
> The main difference is still on CREATE INDEX.  But there are several
> SELECT cases(faster CPU, line 179, 206, 377) where pg_qsort can have
> more than 60% advantage, which is crazy. All these cases are dealing
> with mostly sorted data. 
> 
> Personally, I would say intro sort is good as long as it has nearly the
> same performance as pg_qsort on average cases because of the better
> worst-case complexity. In fact, we can make the two sorting routines as
> similar as we want by increasing the threshold that intro sort switches
> to heap sort. Therefore, I think by no means could pg_qsort be 10%-20%
> faster than a well-optimized intro sort because they execute the same
> code most of the time. There must be something special about CREATE
> INDEX test cases, and I am trying to figure it out. Also, I am
> considering performing the preordered check on every recursion, like
> what pg_qsort does, and see how it goes.
> 

I don't know. All I have is the results I shared. I suggest you try
reproducing the tests on your system - the scripts are in the git
repositories.

> Finally, you've mentioned
> 
>     But even if it was, I guess the easiest way to deal with it would be to
>     randomize the selection of pivots.
> 
> 
> I am wondering if pg_sort with random pivot selecting could be faster
> than intro sort. I've just done some simple tests, which shows that
> intro sort in faster in all cases. But I guess it depends on how we
> would implement the random number generation.
> 

Unlikely. The pivot randomization is merely a way to defeat an adversary
attempting to perform DoS by triggering sorts on a killer sequence.
Randomization makes it much harder/impossible, because the killer
sequence changes over time. It's not a regular performance optimization.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services