pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedGSOC 2018 Project - A New Sorting Routine
15+ messages / 5 participants
[nested] [flat]
* GSOC 2018 Project - A New Sorting Routine
@ 2018-07-10 21:02 Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 1 reply; 15+ messages in thread
From: Kefan Yang @ 2018-07-10 21:02 UTC (permalink / raw)
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hello, Hackers!
I am working on my project in Google Summer of Code 2018
<https://wiki.postgresql.org/wiki/GSoC_2018#Sorting_algorithms_benchmark_and_implementation_.282018.2...;.
In this project, I am trying to improve the in-memory sorting routine in
PostgreSQL. Now I am very excited to share my progress with you guys.
Originally, PostgreSQL is using the QuickSort implemented by J. L. Bentley
and M. D. McIlroy in "Engineering a sort function" with some modifications.
This sorting routine is very fast, yet may fall to O(n^2) time complexity
in the worst case scenario. We are trying to find faster sorting algorithms
with guaranteed O(nlogn) time complexity.
In this patch, I
1. Use IntroSort to implement pg_qsort. IntroSort is a hybrid sorting
algorithm. It uses Quicksort most of the time, but switch to insertion sort
when the array is small and heapsort when the recursion exceeds depth limit.
2. Only check if the array is preordered once on the whole array to get
better overall performance. Previously the sorting routine checks if the
array is preordered on every recursion.
After some performance test, I find the new sorting routine
1. Slightly faster on sorting random arrays.
2. Much faster on worst case scenario since it has O(nlogn) worst case
complexity.
3. Has nearly the same performance on mostly sorted arrays.
I use both standalone tests and pgbench to show the result. A more detailed
report is in the attachment, along with the patch and some scripts to
reproduce the result.
*Notice:* this patch may fail a test case in ‘make check’ because QuickSort
and HeapSort are unstable. The two sorting routines may give different
results if multiple entries in the array have the same key value.
Generally speaking, I think the new sorting routine seems to be an
improvement in many ways. Please let me know if you have any thoughts or
suggestions.
Regards,
Kefan Yang
Attachments:
[application/x-zip-compressed] NewSorting.zip (1.4M, ../../CAF448YLZz5cD+w5qYQGMcfFPY9zAu2mkkiCtOPSBJmwbjuPNig@mail.gmail.com/3-NewSorting.zip)
download
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-07-13 00:50 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
0 siblings, 1 reply; 15+ messages in thread
From: Tomas Vondra @ 2018-07-13 00:50 UTC (permalink / raw)
To: Kefan Yang <starordust@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hi Kefan,
On 07/10/2018 11:02 PM, Kefan Yang wrote:
> Hello, Hackers!
>
> I am working on my project in Google Summer of Code 2018
> <https://wiki.postgresql.org/wiki/GSoC_2018#Sorting_algorithms_benchmark_and_implementation_.282018.2...;.
> In this project, I am trying to improve the in-memory sorting routine in
> PostgreSQL. Now I am very excited to share my progress with you guys.
>
> Originally, PostgreSQL is using the QuickSort implemented by J. L.
> Bentley and M. D. McIlroy in "Engineering a sort function" with some
> modifications. This sorting routine is very fast, yet may fall to O(n^2)
> time complexity in the worst case scenario. We are trying to find faster
> sorting algorithms with guaranteed O(nlogn) time complexity.
>
Time complexity is nice, but it merely estimates the number of
comparisons needed by the sort algorithm. It entirely ignores other
factors that are quite important - behavior with caches, for example.
And quicksort works really well in this regard, I think.
The worst-case complexity may be an issue, but we're already dealing
with it by using median-of-three (actually, median-of-nine, IIRC) in
pg_qsort. Hitting the worst-case accidentally is possible, but it should
be quite unlikely. It's still deterministic so an adversary might
construct a data set triggering it and use it for a DDoS, but if that
was a real issue in practice - I assume we'd already hear about it. But
even if it was, I guess the easiest way to deal with it would be to
randomize the selection of pivots.
In other words, replacing quicksort with an algorithm that is slower on
average but has better worst-case behavior is unlikely to be accepted
with joy, when the worst case is unlikely / bordering with impossible.
> In this patch, I
>
> 1. Use IntroSort to implement pg_qsort. IntroSort is a hybrid sorting
> algorithm. It uses Quicksort most of the time, but switch to
> insertion sort when the array is small and heapsort when the
> recursion exceeds depth limit.
> 2. Only check if the array is preordered once on the whole array to get
> better overall performance. Previously the sorting routine checks if
> the array is preordered on every recursion.
>
> After some performance test, I find the new sorting routine
>
> 1. Slightly faster on sorting random arrays.
> 2. Much faster on worst case scenario since it has O(nlogn) worst case
> complexity.
> 3. Has nearly the same performance on mostly sorted arrays.
>
> I use both standalone tests and pgbench to show the result. A more
> detailed report is in the attachment, along with the patch and some
> scripts to reproduce the result.
>
I find those results rather unconvincing.
First of all, testing this on t2.micro is *insane* considering that this
instance type is subject to throttling (depending on CPU credits). I
don't know if this happened to be an issue during your tests, of course.
Furthermore, the instance only has 1 virtual core, so there's likely a
lot of noise due to other tasks (kernel of whatever needs to run).
Secondly, I see the PDF includes results for various data set types
(random, reversed, mostly random, ...) but the archive you provided only
includes the random + killer cases.
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?
So I've done a bit of benchmarking by running the battery of tests I've
previously used for sort-related patches, and those results seem much
less optimistic. I've done this on two different x86 machines (one with
an old i5-2500K CPU, the other one with rather new e5-2620v4). Full
results and scripts are available at [1] and [2], a summary of the
results is attached here.
Each spreadsheet has a couple of "comparison N" sheets, where N is the
number of rows on the test. The last set of columns is comparison to
unpatched master, where values below 100% mean "faster than master" and
above 100% "slower than master".
On the (quite old) i5-2500k CPU, there's pretty much no difference
between master with and without the patch.
On the (much newer) e5-2620v4 system, the results seem somewhat more
variable - ~10% regressions on CREATE INDEX cases, ~5% gains on the
other cases, for the smallest data set (10k rows). But as the data set
grows, the regressions pretty clearly prevail. Not great, I guess :-(
I don't want to discourage you from working on sorting, and I'm sure
significant improvements in this area are possible (and needed). But my
guess is that those optimizations will happen at higher level, not by
tweaking the low-level algorithm.
regards
[1] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
[2] https://bitbucket.org/tvondra/sort-intro-sort/src/master/
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Attachments:
[application/vnd.oasis.opendocument.spreadsheet] i5-2500k.ods (1.8M, ../../57ae7691-6dc8-d6d0-361a-a7269e656273@2ndquadrant.com/2-i5-2500k.ods)
download
[application/vnd.oasis.opendocument.spreadsheet] e5-2620-v4.ods (1.8M, ../../57ae7691-6dc8-d6d0-361a-a7269e656273@2ndquadrant.com/3-e5-2620-v4.ods)
download
^ permalink raw reply [nested|flat] 15+ messages in thread
* Fwd: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-13 22:04 ` Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 01:03 ` Re: Fwd: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 2 replies; 15+ messages in thread
From: Kefan Yang @ 2018-07-13 22:04 UTC (permalink / raw)
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
---------- Forwarded message ----------
From: Kefan Yang <starordust@gmail.com>
Date: 2018-07-13 15:02 GMT-07:00
Subject: Re: GSOC 2018 Project - A New Sorting Routine
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Hey Tomas,
Thanks for your reply!
First I’d like to make some clarification about my test result.
> First of all, testing this on t2.micro is *insane* considering that this
> instance type is subject to throttling (depending on CPU credits). I
> don't know if this happened to be an issue during your tests, of course.
> Furthermore, the instance only has 1 virtual core, so there's likely a
> lot of noise due to other tasks (kernel of whatever needs to run).
I agree that testing this on t2.micro instance might not be a very great
idea. But I have tried 100 rounds for each test case to minimize the
influence of other processes. In fact, I think the result is
consistent with yours on i5-2500k (the older CPU): intro sort with only one
preordered check is slightly better on random cases. There's no big
difference if we also take the other cases into consideration. (I would say
intro sort is still better by simply counting the number of improved test
cases)
Secondly, I see the PDF includes results for various data set types
> (random, reversed, mostly random, ...) but the archive you provided only
> includes the random + killer cases.
I tried data of all patterns in the standalone test, but only random and
killer cases in pg_bench. This is a problem but I would try other cases in
pg_bench once I write a shell script to do it automatically.
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.
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.
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.
In conclusion, I still believe intro sort is good if we optimized the
implementation and select the parameters more carefully.
Thanks again for your time. I am hoping to see your thoughts on this:)
Regards,
Kefan
2018-07-12 17:50 GMT-07:00 Tomas Vondra <tomas.vondra@2ndquadrant.com>:
> Hi Kefan,
>
> On 07/10/2018 11:02 PM, Kefan Yang wrote:
> > Hello, Hackers!
> >
> > I am working on my project in Google Summer of Code 2018
> > <https://wiki.postgresql.org/wiki/GSoC_2018#Sorting_algorith
> ms_benchmark_and_implementation_.282018.29>.
> > In this project, I am trying to improve the in-memory sorting routine in
> > PostgreSQL. Now I am very excited to share my progress with you guys.
> >
> > Originally, PostgreSQL is using the QuickSort implemented by J. L.
> > Bentley and M. D. McIlroy in "Engineering a sort function" with some
> > modifications. This sorting routine is very fast, yet may fall to O(n^2)
> > time complexity in the worst case scenario. We are trying to find faster
> > sorting algorithms with guaranteed O(nlogn) time complexity.
> >
>
> Time complexity is nice, but it merely estimates the number of
> comparisons needed by the sort algorithm. It entirely ignores other
> factors that are quite important - behavior with caches, for example.
> And quicksort works really well in this regard, I think.
>
> The worst-case complexity may be an issue, but we're already dealing
> with it by using median-of-three (actually, median-of-nine, IIRC) in
> pg_qsort. Hitting the worst-case accidentally is possible, but it should
> be quite unlikely. It's still deterministic so an adversary might
> construct a data set triggering it and use it for a DDoS, but if that
> was a real issue in practice - I assume we'd already hear about it. But
> even if it was, I guess the easiest way to deal with it would be to
> randomize the selection of pivots.
>
> In other words, replacing quicksort with an algorithm that is slower on
> average but has better worst-case behavior is unlikely to be accepted
> with joy, when the worst case is unlikely / bordering with impossible.
>
>
> > In this patch, I
> >
> > 1. Use IntroSort to implement pg_qsort. IntroSort is a hybrid sorting
> > algorithm. It uses Quicksort most of the time, but switch to
> > insertion sort when the array is small and heapsort when the
> > recursion exceeds depth limit.
> > 2. Only check if the array is preordered once on the whole array to get
> > better overall performance. Previously the sorting routine checks if
> > the array is preordered on every recursion.
> >
> > After some performance test, I find the new sorting routine
> >
> > 1. Slightly faster on sorting random arrays.
> > 2. Much faster on worst case scenario since it has O(nlogn) worst case
> > complexity.
> > 3. Has nearly the same performance on mostly sorted arrays.
> >
> > I use both standalone tests and pgbench to show the result. A more
> > detailed report is in the attachment, along with the patch and some
> > scripts to reproduce the result.
> >
>
> I find those results rather unconvincing.
>
> First of all, testing this on t2.micro is *insane* considering that this
> instance type is subject to throttling (depending on CPU credits). I
> don't know if this happened to be an issue during your tests, of course.
> Furthermore, the instance only has 1 virtual core, so there's likely a
> lot of noise due to other tasks (kernel of whatever needs to run).
>
> Secondly, I see the PDF includes results for various data set types
> (random, reversed, mostly random, ...) but the archive you provided only
> includes the random + killer cases.
>
> 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?
>
> So I've done a bit of benchmarking by running the battery of tests I've
> previously used for sort-related patches, and those results seem much
> less optimistic. I've done this on two different x86 machines (one with
> an old i5-2500K CPU, the other one with rather new e5-2620v4). Full
> results and scripts are available at [1] and [2], a summary of the
> results is attached here.
>
> Each spreadsheet has a couple of "comparison N" sheets, where N is the
> number of rows on the test. The last set of columns is comparison to
> unpatched master, where values below 100% mean "faster than master" and
> above 100% "slower than master".
>
> On the (quite old) i5-2500k CPU, there's pretty much no difference
> between master with and without the patch.
>
> On the (much newer) e5-2620v4 system, the results seem somewhat more
> variable - ~10% regressions on CREATE INDEX cases, ~5% gains on the
> other cases, for the smallest data set (10k rows). But as the data set
> grows, the regressions pretty clearly prevail. Not great, I guess :-(
>
> I don't want to discourage you from working on sorting, and I'm sure
> significant improvements in this area are possible (and needed). But my
> guess is that those optimizations will happen at higher level, not by
> tweaking the low-level algorithm.
>
>
> regards
>
> [1] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
> [2] https://bitbucket.org/tvondra/sort-intro-sort/src/master/
>
> --
> Tomas Vondra http://www.2ndQuadrant.com
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-07-13 22:10 ` Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 1 reply; 15+ messages in thread
From: Peter Geoghegan @ 2018-07-13 22:10 UTC (permalink / raw)
To: Kefan Yang <starordust@gmail.com>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Fri, Jul 13, 2018 at 3:04 PM, Kefan Yang <starordust@gmail.com> wrote:
> 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.
Yes. CREATE INDEX uses heap TID as a tie-breaker, so it's impossible
for any two index tuples to compare as equal within tuplesort.c, even
though they may be equal in other contexts. This is likely to defeat
things like the Bentley-McIlroy optimization where equal keys are
swapped, which is very effective in the event of many equal keys.
(Could also be parallelism, though I suppose you probably accounted for that.)
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
@ 2018-07-14 21:20 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
0 siblings, 1 reply; 15+ messages in thread
From: Tomas Vondra @ 2018-07-14 21:20 UTC (permalink / raw)
To: Peter Geoghegan <pg@bowt.ie>; Kefan Yang <starordust@gmail.com>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On 07/14/2018 12:10 AM, Peter Geoghegan wrote:
> On Fri, Jul 13, 2018 at 3:04 PM, Kefan Yang <starordust@gmail.com> wrote:
>> 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.
>
> Yes. CREATE INDEX uses heap TID as a tie-breaker, so it's impossible
> for any two index tuples to compare as equal within tuplesort.c, even
> though they may be equal in other contexts. This is likely to defeat
> things like the Bentley-McIlroy optimization where equal keys are
> swapped, which is very effective in the event of many equal keys.
>
> (Could also be parallelism, though I suppose you probably accounted for that.)
>
Hmmm. Those scripts are older than max_parallel_maintenance_workers, so
were only setting the regular max_parallel_workers_per_gather GUCs. OTOH
these tests were done on fairly small data sets, starting from 10k rows
and the 10-20% regression is clearly visible for all scales (we don't
use parallel CREATE INDEX for tiny tables, right?). And it's not visible
on the i5 CPU at all, which would be a bit strange if it's
parallelism-related.
So I doubt it's this, but I've tweaked the scripts to also set this GUC
and restarted the tests on both machines. Let's see what that does.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-18 05:06 ` Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
0 siblings, 1 reply; 15+ messages in thread
From: Andrey Borodin @ 2018-07-18 05:06 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Peter Geoghegan <pg@bowt.ie>; Kefan Yang <starordust@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hi, Tomas!
> 15 июля 2018 г., в 1:20, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):
>
> So I doubt it's this, but I've tweaked the scripts to also set this GUC
> and restarted the tests on both machines. Let's see what that does.
Do you observe any different results?
Thanks!
Best regards, Andrey Borodin.=
^ permalink raw reply [nested|flat] 15+ messages in thread
* RE: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
@ 2018-07-18 21:13 ` Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
0 siblings, 1 reply; 15+ messages in thread
From: Kefan Yang @ 2018-07-18 21:13 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hey Tomas!
I am trying to reproduce the results on my machine. Could you please share the script to generate .ods files?
Regards,
Kefan
From: Tomas Vondra
Sent: July 18, 2018 2:05 AM
To: Andrey Borodin
Cc: Peter Geoghegan; Kefan Yang; PostgreSQL Hackers
Subject: Re: GSOC 2018 Project - A New Sorting Routine
On 07/18/2018 07:06 AM, Andrey Borodin wrote:
> Hi, Tomas!
>
>> 15 июля 2018 г., в 1:20, Tomas Vondra <tomas.vondra@2ndquadrant.com
>> <mailto:tomas.vondra@2ndquadrant.com>> написал(а):
>>
>> So I doubt it's this, but I've tweaked the scripts to also set this GUC
>> and restarted the tests on both machines. Let's see what that does.
>
> Do you observe any different results?
>
It did change the CREATE INDEX results, depending on the scale. The full
data is available at [1] and [2], attached is a spreadsheet summary from
the Xeon box.
For the largest scale (1M rows) the regressions for CREATE INDEX queries
mostly disappeared. For 10k rows it still affects CREATE INDEX with a
text column, and the 100k case behaves just like before (so significant
regressions for CREATE INDEX).
I don't have time to investigate this further at the moment, but I'm
still of the opinion that there's little to gain by replacing our
current sort algorithm with this.
[1] https://bitbucket.org/tvondra/sort-intro-sort-xeon/src/master/
[2] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-07-18 21:26 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 22:13 ` Re: GSOC 2018 Project - A New Sorting Routine Alvaro Herrera <alvherre@2ndquadrant.com>
2018-07-23 22:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
0 siblings, 2 replies; 15+ messages in thread
From: Tomas Vondra @ 2018-07-18 21:26 UTC (permalink / raw)
To: Kefan Yang <starordust@gmail.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
I don't have any script for that - load the files into a spreadsheet,
create pivot tables and you're done.
regards
On 07/18/2018 11:13 PM, Kefan Yang wrote:
> Hey Tomas!
>
>
>
> I am trying to reproduce the results on my machine. Could you please
> share the script to generate .ods files?
>
>
>
> Regards,
>
> Kefan
>
>
>
> *From: *Tomas Vondra <mailto:tomas.vondra@2ndquadrant.com>
> *Sent: *July 18, 2018 2:05 AM
> *To: *Andrey Borodin <mailto:x4mmm@yandex-team.ru>
> *Cc: *Peter Geoghegan <mailto:pg@bowt.ie>; Kefan Yang
> <mailto:starordust@gmail.com>; PostgreSQL Hackers
> <mailto:pgsql-hackers@lists.postgresql.org>
> *Subject: *Re: GSOC 2018 Project - A New Sorting Routine
>
>
>
>
>
>
>
> On 07/18/2018 07:06 AM, Andrey Borodin wrote:
>
>> Hi, Tomas!
>
>>
>
>>> 15 июля 2018 г., в 1:20, Tomas Vondra <tomas.vondra@2ndquadrant.com
>
>>> <mailto:tomas.vondra@2ndquadrant.com>> написал(а):
>
>>>
>
>>> So I doubt it's this, but I've tweaked the scripts to also set this GUC
>
>>> and restarted the tests on both machines. Let's see what that does.
>
>>
>
>> Do you observe any different results?
>
>>
>
>
>
> It did change the CREATE INDEX results, depending on the scale. The full
>
> data is available at [1] and [2], attached is a spreadsheet summary from
>
> the Xeon box.
>
>
>
> For the largest scale (1M rows) the regressions for CREATE INDEX queries
>
> mostly disappeared. For 10k rows it still affects CREATE INDEX with a
>
> text column, and the 100k case behaves just like before (so significant
>
> regressions for CREATE INDEX).
>
>
>
> I don't have time to investigate this further at the moment, but I'm
>
> still of the opinion that there's little to gain by replacing our
>
> current sort algorithm with this.
>
>
>
>
>
> [1] https://bitbucket.org/tvondra/sort-intro-sort-xeon/src/master/
>
> [2] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
>
>
>
> regards
>
>
>
> --
>
> Tomas Vondra http://www.2ndQuadrant.com
>
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>
>
>
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-18 22:13 ` Alvaro Herrera <alvherre@2ndquadrant.com>
1 sibling, 0 replies; 15+ messages in thread
From: Alvaro Herrera @ 2018-07-18 22:13 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Kefan Yang <starordust@gmail.com>; Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On 2018-Jul-18, Tomas Vondra wrote:
> I don't have any script for that - load the files into a spreadsheet,
> create pivot tables and you're done.
What!? You don't use psql's \crosstabview !?
... walks away disappointed ...
--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* RE: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-23 22:21 ` Kefan Yang <starordust@gmail.com>
2018-07-24 15:16 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
1 sibling, 1 reply; 15+ messages in thread
From: Kefan Yang @ 2018-07-23 22:21 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; alvherre@2ndquadrant.com <alvherre@2ndquadrant.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hi Tomas!
I did a few tests on my own Linux machine, but the problem is that my resources on AWS(CPU, RAM and even Disk space) are very limited. I considered establishing virtual machine on my own PC but the performance is even worse.
My original patch has two main optimizations: (1) switch to heap sort when depth limit exceeded (2) check whether the array is presorted only once at the beginning. Now I want to test these optimizations separately. On AWS EC2 instance, regressions on CREATE INDEX cases seems to be less significant if we use (1) only, but I can only test up to 100000 records and 512MB memory using your scripts.
So would you mind re-running the tests using the two patches I provided in the attachment? That will be very helpful
Regards,
Kefan
From: Tomas Vondra
Sent: July 18, 2018 2:26 PM
To: Kefan Yang
Cc: Andrey Borodin; Peter Geoghegan; PostgreSQL Hackers
Subject: Re: GSOC 2018 Project - A New Sorting Routine
I don't have any script for that - load the files into a spreadsheet,
create pivot tables and you're done.
regards
On 07/18/2018 11:13 PM, Kefan Yang wrote:
> Hey Tomas!
>
>
>
> I am trying to reproduce the results on my machine. Could you please
> share the script to generate .ods files?
>
>
>
> Regards,
>
> Kefan
>
>
>
> *From: *Tomas Vondra <mailto:tomas.vondra@2ndquadrant.com>
> *Sent: *July 18, 2018 2:05 AM
> *To: *Andrey Borodin <mailto:x4mmm@yandex-team.ru>
> *Cc: *Peter Geoghegan <mailto:pg@bowt.ie>; Kefan Yang
> <mailto:starordust@gmail.com>; PostgreSQL Hackers
> <mailto:pgsql-hackers@lists.postgresql.org>
> *Subject: *Re: GSOC 2018 Project - A New Sorting Routine
>
>
>
>
>
>
>
> On 07/18/2018 07:06 AM, Andrey Borodin wrote:
>
>> Hi, Tomas!
>
>>
>
>>> 15 июля 2018 г., в 1:20, Tomas Vondra <tomas.vondra@2ndquadrant.com
>
>>> <mailto:tomas.vondra@2ndquadrant.com>> написал(а):
>
>>>
>
>>> So I doubt it's this, but I've tweaked the scripts to also set this GUC
>
>>> and restarted the tests on both machines. Let's see what that does.
>
>>
>
>> Do you observe any different results?
>
>>
>
>
>
> It did change the CREATE INDEX results, depending on the scale. The full
>
> data is available at [1] and [2], attached is a spreadsheet summary from
>
> the Xeon box.
>
>
>
> For the largest scale (1M rows) the regressions for CREATE INDEX queries
>
> mostly disappeared. For 10k rows it still affects CREATE INDEX with a
>
> text column, and the 100k case behaves just like before (so significant
>
> regressions for CREATE INDEX).
>
>
>
> I don't have time to investigate this further at the moment, but I'm
>
> still of the opinion that there's little to gain by replacing our
>
> current sort algorithm with this.
>
>
>
>
>
> [1] https://bitbucket.org/tvondra/sort-intro-sort-xeon/src/master/
>
> [2] https://bitbucket.org/tvondra/sort-intro-sort-i5/src/master/
>
>
>
> regards
>
>
>
> --
>
> Tomas Vondra http://www.2ndQuadrant.com
>
> PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
>
>
>
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
Attachments:
[application/octet-stream] check_once.diff (9.7K, ../../5b5654cc.1c69fb81.5ea44.d698@mx.google.com/3-check_once.diff)
download | inline diff:
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl
index 6186d0a..20d7fb4 100644
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ b/src/backend/utils/sort/gen_qsort_tuple.pl
@@ -108,6 +108,8 @@ sub emit_qsort_boilerplate
* worth the effort", but we have seen crashes in the field due to stack
* overrun, so that judgment seems wrong.
*/
+
+#include <math.h>
static void
swapfunc(SortTuple *a, SortTuple *b, size_t n)
@@ -146,7 +148,7 @@ med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS)
}
static void
-qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+qsort_recursive_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
{
SortTuple *pa,
*pb,
@@ -157,8 +159,7 @@ qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
*pn;
size_t d1,
d2;
- int r,
- presorted;
+ int r;
loop:
CHECK_FOR_INTERRUPTS();
@@ -169,18 +170,7 @@ loop:
swap(pl, pl - 1);
return;
}
- presorted = 1;
- for (pm = a + 1; pm < a + n; pm++)
- {
- CHECK_FOR_INTERRUPTS();
- if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0)
- {
- presorted = 0;
- break;
- }
- }
- if (presorted)
- return;
+
pm = a + (n / 2);
if (n > 7)
{
@@ -238,11 +228,11 @@ loop:
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > 1)
- qsort_$SUFFIX(a, d1$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(a, d1$EXTRAPARAMS);
if (d2 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
a = pn - d2;
n = d2;
goto loop;
@@ -252,15 +242,35 @@ loop:
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > 1)
- qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
if (d1 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(a, d1$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(a, d1$EXTRAPARAMS); */
n = d1;
goto loop;
}
}
}
+
+static void
+qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+{
+ int presorted = 1;
+ SortTuple* pm;
+ for (pm = a + 1; pm < a + n; pm++)
+ {
+ CHECK_FOR_INTERRUPTS();
+ if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ qsort_recursive_$SUFFIX(a, n$EXTRAPARAMS);
+}
+
EOM
}
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 1a8ee08..7341aed 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -109,47 +111,35 @@ med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
}
-void
-pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
+static void
+pg_qsort_recursive(void *a, size_t n, int swaptype, size_t es, int(*cmp) (const void *, const void *))
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
- int r,
- swaptype,
- presorted;
+ d2;
+ int r;
-loop:SWAPINIT(a, es);
+loop:
if (n < 7)
{
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
- pl -= es)
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl >(char *) a && cmp(pl - es, pl) > 0;
+ pl -= es)
swap(pl, pl - es);
return;
}
- presorted = 1;
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- {
- if (cmp(pm - es, pm) > 0)
- {
- presorted = 0;
- break;
- }
- }
- if (presorted)
- return;
- pm = (char *) a + (n / 2) * es;
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +151,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a)) <= 0)
@@ -189,8 +179,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ pn = (char *)a + n * es;
+ d1 = Min(pa - (char *)a, pb - pa);
vecswap(a, pb - d1, d1);
d1 = Min(pd - pc, pn - pd - es);
vecswap(pb, pn - d1, d1);
@@ -200,11 +190,11 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- pg_qsort(a, d1 / es, es, cmp);
+ pg_qsort_recursive(a, d1 / es, swaptype, es, cmp);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(pn - d2, d2 / es, es, cmp); */
+ /* pg_qsort_recursive(pn - d2, d2 / es, es, cmp); */
a = pn - d2;
n = d2 / es;
goto loop;
@@ -214,17 +204,36 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- pg_qsort(pn - d2, d2 / es, es, cmp);
+ pg_qsort_recursive(pn - d2, d2 / es, swaptype, es, cmp);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(a, d1 / es, es, cmp); */
+ /* pg_qsort_recursive(a, d1 / es, es, cmp); */
n = d1 / es;
goto loop;
}
}
}
+
+void
+pg_qsort(void *a, const size_t size, const size_t es, int(*cmp) (const void *, const void *)) {
+ int swaptype, presorted = 1;
+ char* pm;
+ for (pm = (char *)a + es; pm < (char *)a + size * es; pm += es)
+ {
+ if (cmp(pm - es, pm) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ SWAPINIT(a, es);
+ pg_qsort_recursive(a, size, swaptype, es, cmp);
+};
+
/*
* qsort comparator wrapper for strcmp.
*/
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
index 24acd2c..7de3167 100644
--- a/src/port/qsort_arg.c
+++ b/src/port/qsort_arg.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -102,54 +104,42 @@ swapfunc(char *a, char *b, size_t n, int swaptype)
#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
static char *
-med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
+med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void* arg)
{
return cmp(a, b, arg) < 0 ?
- (cmp(b, c, arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
- : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
+ (cmp(b, c , arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
+ : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
}
-void
-qsort_arg(void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
+static void
+pg_qsort_arg_recursive(void *a, size_t n, int swaptype, size_t es, qsort_arg_comparator cmp, void* arg)
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
- int r,
- swaptype,
- presorted;
+ d2;
+ int r;
-loop:SWAPINIT(a, es);
+loop:
if (n < 7)
{
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl, arg) > 0;
- pl -= es)
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl >(char *) a && cmp(pl - es, pl, arg) > 0;
+ pl -= es)
swap(pl, pl - es);
return;
}
- presorted = 1;
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- {
- if (cmp(pm - es, pm, arg) > 0)
- {
- presorted = 0;
- break;
- }
- }
- if (presorted)
- return;
- pm = (char *) a + (n / 2) * es;
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +151,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp, arg);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
@@ -189,8 +179,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ pn = (char *)a + n * es;
+ d1 = Min(pa - (char *)a, pb - pa);
vecswap(a, pb - d1, d1);
d1 = Min(pd - pc, pn - pd - es);
vecswap(pb, pn - d1, d1);
@@ -200,11 +190,11 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- qsort_arg(a, d1 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(a, d1 / es, swaptype, es, cmp, arg);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(pn - d2, d2 / es, es, cmp, arg); */
a = pn - d2;
n = d2 / es;
goto loop;
@@ -214,13 +204,33 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- qsort_arg(pn - d2, d2 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(pn - d2, d2 / es, swaptype, es, cmp, arg);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(a, d1 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(a, d1 / es, es, cmp, arg); */
n = d1 / es;
goto loop;
}
}
}
+
+
+void
+qsort_arg(void *a, const size_t size, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ int swaptype, presorted = 1;
+ char* pm;
+ for (pm = (char *)a + es; pm < (char *)a + size * es; pm += es)
+ {
+ if (cmp(pm - es, pm, arg) > 0)
+ {
+ presorted = 0;
+ break;
+ }
+ }
+ if (presorted)
+ return;
+ SWAPINIT(a, es);
+ pg_qsort_arg_recursive(a, size, swaptype, es, cmp, arg);
+};
+
[application/octet-stream] use_heap.diff (13.2K, ../../5b5654cc.1c69fb81.5ea44.d698@mx.google.com/4-use_heap.diff)
download | inline diff:
diff --git a/src/backend/utils/sort/gen_qsort_tuple.pl b/src/backend/utils/sort/gen_qsort_tuple.pl
index 6186d0a..a9ae496 100644
--- a/src/backend/utils/sort/gen_qsort_tuple.pl
+++ b/src/backend/utils/sort/gen_qsort_tuple.pl
@@ -108,6 +108,8 @@ sub emit_qsort_boilerplate
* worth the effort", but we have seen crashes in the field due to stack
* overrun, so that judgment seems wrong.
*/
+
+#include <math.h>
static void
swapfunc(SortTuple *a, SortTuple *b, size_t n)
@@ -145,8 +147,63 @@ med3_$SUFFIX(SortTuple *a, SortTuple *b, SortTuple *c$EXTRAARGS)
(cmp_$SUFFIX(a, c$CMPPARAMS) < 0 ? a : c));
}
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down_$SUFFIX(SortTuple *a, const size_t start, const size_t end$EXTRAARGS) {
+ size_t child, root = start;
+
+ while ((root << 1) + 1 <= end) {
+ CHECK_FOR_INTERRUPTS();
+
+ child = (root << 1) + 1;
+
+ if ((child < end) && cmp_$SUFFIX(a + child, a + (child + 1)$CMPPARAMS) < 0) {
+ child++;
+ }
+
+ if (cmp_$SUFFIX(a + root, a + child$CMPPARAMS) < 0) {
+ swap(a + root, a + child);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort_$SUFFIX(SortTuple *a, const size_t size$EXTRAARGS) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down_$SUFFIX(a, start, end$EXTRAPARAMS);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap(a + end, a);
+ heap_shift_down_$SUFFIX(a, 0, end - 1$EXTRAPARAMS);
+ end--;
+ }
+}
+
static void
-qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+qsort_recursive_$SUFFIX(SortTuple *a, size_t n, size_t depth$EXTRAARGS)
{
SortTuple *pa,
*pb,
@@ -158,7 +215,7 @@ qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
size_t d1,
d2;
int r,
- presorted;
+ presorted;
loop:
CHECK_FOR_INTERRUPTS();
@@ -169,8 +226,9 @@ loop:
swap(pl, pl - 1);
return;
}
- presorted = 1;
- for (pm = a + 1; pm < a + n; pm++)
+
+ presorted = 1;
+ for (pm = a + 1; pm < a + n; pm++)
{
CHECK_FOR_INTERRUPTS();
if (cmp_$SUFFIX(pm - 1, pm$CMPPARAMS) > 0)
@@ -181,6 +239,13 @@ loop:
}
if (presorted)
return;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort_$SUFFIX(a, n$EXTRAPARAMS);
+ return;
+ }
+
pm = a + (n / 2);
if (n > 7)
{
@@ -238,13 +303,14 @@ loop:
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > 1)
- qsort_$SUFFIX(a, d1$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(a, d1, depth - 1$EXTRAPARAMS);
if (d2 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(pn - d2, d2, depth - 1$EXTRAPARAMS); */
a = pn - d2;
n = d2;
+ depth--;
goto loop;
}
}
@@ -252,15 +318,23 @@ loop:
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > 1)
- qsort_$SUFFIX(pn - d2, d2$EXTRAPARAMS);
+ qsort_recursive_$SUFFIX(pn - d2, d2, depth - 1$EXTRAPARAMS);
if (d1 > 1)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_$SUFFIX(a, d1$EXTRAPARAMS); */
+ /* qsort_recursive_$SUFFIX(a, d1, depth - 1$EXTRAPARAMS); */
n = d1;
+ depth--;
goto loop;
}
}
}
+
+static void
+qsort_$SUFFIX(SortTuple *a, size_t n$EXTRAARGS)
+{
+ qsort_recursive_$SUFFIX(a, n, 2 * log(n)$EXTRAPARAMS);
+}
+
EOM
}
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 1a8ee08..49175a7 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -109,32 +111,85 @@ med3(char *a, char *b, char *c, int (*cmp) (const void *, const void *))
: (cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c));
}
-void
-pg_qsort(void *a, size_t n, size_t es, int (*cmp) (const void *, const void *))
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down(void *a, const size_t start, const size_t end,
+ int swaptype, const size_t es, int(*cmp) (const void *, const void *)) {
+ size_t root = start;
+
+ while ((root << 1) + 1 <= end) {
+ size_t child = (root << 1) + 1;
+
+ if ((child < end) && cmp((char*)a + child * es, (char*)a + (child + 1)*es) < 0) {
+ child++;
+ }
+
+ if (cmp((char*)a + root * es, (char*)a + child * es) < 0) {
+ swap((char*)a + root * es, (char*)a + child * es);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort(void *a, const size_t size, int swaptype, const size_t es, int(*cmp) (const void *, const void *)) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down(a, start, end, swaptype, es, cmp);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap((char*)a + end * es, (char*)a);
+ heap_shift_down(a, 0, end - 1, swaptype, es, cmp);
+ end--;
+ }
+}
+
+static void
+pg_qsort_recursive(void *a, size_t n, size_t depth, int swaptype, size_t es, int(*cmp) (const void *, const void *))
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
+ d2;
int r,
- swaptype,
- presorted;
+ presorted;
-loop:SWAPINIT(a, es);
+loop:
if (n < 7)
{
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0;
- pl -= es)
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl >(char *) a && cmp(pl - es, pl) > 0;
+ pl -= es)
swap(pl, pl - es);
return;
}
- presorted = 1;
+ presorted = 1;
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
{
if (cmp(pm - es, pm) > 0)
@@ -145,11 +200,18 @@ loop:SWAPINIT(a, es);
}
if (presorted)
return;
- pm = (char *) a + (n / 2) * es;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort(a, n, swaptype, es, cmp);
+ return;
+ }
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +223,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a)) <= 0)
@@ -189,8 +251,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ pn = (char *)a + n * es;
+ d1 = Min(pa - (char *)a, pb - pa);
vecswap(a, pb - d1, d1);
d1 = Min(pd - pc, pn - pd - es);
vecswap(pb, pn - d1, d1);
@@ -200,13 +262,14 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- pg_qsort(a, d1 / es, es, cmp);
+ pg_qsort_recursive(a, d1 / es, depth - 1, swaptype, es, cmp);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(pn - d2, d2 / es, es, cmp); */
+ /* pg_qsort_recursive(pn - d2, d2 / es, depth - 1, es, cmp); */
a = pn - d2;
n = d2 / es;
+ depth--;
goto loop;
}
}
@@ -214,17 +277,26 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- pg_qsort(pn - d2, d2 / es, es, cmp);
+ pg_qsort_recursive(pn - d2, d2 / es, depth - 1, swaptype, es, cmp);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* pg_qsort(a, d1 / es, es, cmp); */
+ /* pg_qsort_recursive(a, d1 / es, depth - 1, es, cmp); */
n = d1 / es;
+ depth--;
goto loop;
}
}
}
+
+void
+pg_qsort(void *a, const size_t size, const size_t es, int(*cmp) (const void *, const void *)) {
+ int swaptype;
+ SWAPINIT(a, es);
+ pg_qsort_recursive(a, size, 2 * log(size), swaptype, es, cmp);
+};
+
/*
* qsort comparator wrapper for strcmp.
*/
diff --git a/src/port/qsort_arg.c b/src/port/qsort_arg.c
index 24acd2c..b785778 100644
--- a/src/port/qsort_arg.c
+++ b/src/port/qsort_arg.c
@@ -44,6 +44,8 @@
* SUCH DAMAGE.
*/
+
+#include <math.h>
#include "c.h"
@@ -102,39 +104,94 @@ swapfunc(char *a, char *b, size_t n, int swaptype)
#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype)
static char *
-med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void *arg)
+med3(char *a, char *b, char *c, qsort_arg_comparator cmp, void* arg)
{
return cmp(a, b, arg) < 0 ?
- (cmp(b, c, arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
- : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
+ (cmp(b, c , arg) < 0 ? b : (cmp(a, c, arg) < 0 ? c : a))
+ : (cmp(b, c, arg) > 0 ? b : (cmp(a, c, arg) < 0 ? a : c));
}
-void
-qsort_arg(void *a, size_t n, size_t es, qsort_arg_comparator cmp, void *arg)
+
+/* heap sort: based on wikipedia */
+
+static inline void
+heap_shift_down(void *a, const size_t start, const size_t end,
+ int swaptype, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ size_t root = start;
+
+ while ((root << 1) + 1 <= end) {
+ size_t child = (root << 1) + 1;
+
+ if ((child < end) && cmp((char*)a + child * es, (char*)a + (child + 1)*es, arg) < 0) {
+ child++;
+ }
+
+ if (cmp((char*)a + root * es, (char*)a + child * es, arg) < 0) {
+ swap((char*)a + root * es, (char*)a + child * es);
+ root = child;
+ }
+ else {
+ return;
+ }
+ }
+}
+
+static inline void
+heap_sort(void *a, const size_t size, int swaptype, const size_t es, qsort_arg_comparator cmp, void* arg) {
+
+ size_t start, end;
+ /* don't bother sorting an array of size <= 1 */
+ if (size <= 1) {
+ return;
+ }
+
+ end = size - 1;
+
+ /* heapify */
+ start = (end - 1) >> 1;
+ while (1) {
+ heap_shift_down(a, start, end, swaptype, es, cmp, arg);
+
+ if (start == 0) {
+ break;
+ }
+
+ start--;
+ }
+
+ while (end > 0) {
+ swap((char*)a + end * es, (char*)a);
+ heap_shift_down(a, 0, end - 1, swaptype, es, cmp, arg);
+ end--;
+ }
+}
+
+static void
+pg_qsort_arg_recursive(void *a, size_t n, size_t depth, int swaptype, size_t es, qsort_arg_comparator cmp, void* arg)
{
char *pa,
- *pb,
- *pc,
- *pd,
- *pl,
- *pm,
- *pn;
+ *pb,
+ *pc,
+ *pd,
+ *pl,
+ *pm,
+ *pn;
size_t d1,
- d2;
+ d2;
int r,
- swaptype,
- presorted;
+ presorted;
-loop:SWAPINIT(a, es);
+loop:
if (n < 7)
{
- for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
- for (pl = pm; pl > (char *) a && cmp(pl - es, pl, arg) > 0;
- pl -= es)
+ for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
+ for (pl = pm; pl >(char *) a && cmp(pl - es, pl, arg) > 0;
+ pl -= es)
swap(pl, pl - es);
return;
}
- presorted = 1;
+
+ presorted = 1;
for (pm = (char *) a + es; pm < (char *) a + n * es; pm += es)
{
if (cmp(pm - es, pm, arg) > 0)
@@ -145,11 +202,18 @@ loop:SWAPINIT(a, es);
}
if (presorted)
return;
- pm = (char *) a + (n / 2) * es;
+
+ /* convert to heap sort if exceed depth limit */
+ if (!depth) {
+ heap_sort(a, n, swaptype, es, cmp, arg);
+ return;
+ }
+
+ pm = (char *)a + (n / 2) * es;
if (n > 7)
{
- pl = (char *) a;
- pn = (char *) a + (n - 1) * es;
+ pl = (char *)a;
+ pn = (char *)a + (n - 1) * es;
if (n > 40)
{
size_t d = (n / 8) * es;
@@ -161,8 +225,8 @@ loop:SWAPINIT(a, es);
pm = med3(pl, pm, pn, cmp, arg);
}
swap(a, pm);
- pa = pb = (char *) a + es;
- pc = pd = (char *) a + (n - 1) * es;
+ pa = pb = (char *)a + es;
+ pc = pd = (char *)a + (n - 1) * es;
for (;;)
{
while (pb <= pc && (r = cmp(pb, a, arg)) <= 0)
@@ -189,8 +253,8 @@ loop:SWAPINIT(a, es);
pb += es;
pc -= es;
}
- pn = (char *) a + n * es;
- d1 = Min(pa - (char *) a, pb - pa);
+ pn = (char *)a + n * es;
+ d1 = Min(pa - (char *)a, pb - pa);
vecswap(a, pb - d1, d1);
d1 = Min(pd - pc, pn - pd - es);
vecswap(pb, pn - d1, d1);
@@ -200,13 +264,14 @@ loop:SWAPINIT(a, es);
{
/* Recurse on left partition, then iterate on right partition */
if (d1 > es)
- qsort_arg(a, d1 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(a, d1 / es, depth - 1, swaptype, es, cmp, arg);
if (d2 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(pn - d2, d2 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(pn - d2, d2 / es, depth - 1, es, cmp, arg); */
a = pn - d2;
n = d2 / es;
+ depth--;
goto loop;
}
}
@@ -214,13 +279,23 @@ loop:SWAPINIT(a, es);
{
/* Recurse on right partition, then iterate on left partition */
if (d2 > es)
- qsort_arg(pn - d2, d2 / es, es, cmp, arg);
+ pg_qsort_arg_recursive(pn - d2, d2 / es, depth - 1, swaptype, es, cmp, arg);
if (d1 > es)
{
/* Iterate rather than recurse to save stack space */
- /* qsort_arg(a, d1 / es, es, cmp, arg); */
+ /* pg_qsort_arg_recursive(a, d1 / es, depth - 1, es, cmp, arg); */
n = d1 / es;
+ depth--;
goto loop;
}
}
}
+
+
+void
+qsort_arg(void *a, const size_t size, const size_t es, qsort_arg_comparator cmp, void* arg) {
+ int swaptype;
+ SWAPINIT(a, es);
+ pg_qsort_arg_recursive(a, size, 2 * log(size), swaptype, es, cmp, arg);
+};
+
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-23 22:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-07-24 15:16 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-30 21:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
0 siblings, 1 reply; 15+ messages in thread
From: Tomas Vondra @ 2018-07-24 15:16 UTC (permalink / raw)
To: Kefan Yang <starordust@gmail.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; alvherre@2ndquadrant.com <alvherre@2ndquadrant.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On 07/24/2018 12:21 AM, Kefan Yang wrote:
> Hi Tomas!
>
> I did a few tests on my own Linux machine, but the problem is that my
> resources on AWS(CPU, RAM and even Disk space) are very limited. I
> considered establishing virtual machine on my own PC but the performance
> is even worse.
>
> My original patch has two main optimizations: (1) switch to heap sort
> when depth limit exceeded (2) check whether the array is presorted only
> once at the beginning. Now I want to test these optimizations
> separately. On AWS EC2 instance, regressions on CREATE INDEX cases seems
> to be less significant if we use (1) only, but I can only test up to
> 100000 records and 512MB memory using your scripts.
>
> So would you mind re-running the tests using the two patches I provided
> in the attachment? That will be very helpful
>
I can do that, but it'll have to wait a couple of days. I'm currently
using the boxes for some other tests.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* RE: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-23 22:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-24 15:16 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-30 21:21 ` Kefan Yang <starordust@gmail.com>
2018-08-01 17:05 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
0 siblings, 1 reply; 15+ messages in thread
From: Kefan Yang @ 2018-07-30 21:21 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; alvherre@2ndquadrant.com <alvherre@2ndquadrant.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Hey Tomas!
Sorry to bother but it would be great if we can get the test results this week.
Regards,
Kefan
From: Tomas Vondra
Sent: July 24, 2018 8:16 AM
To: Kefan Yang
Cc: Andrey Borodin; Peter Geoghegan; alvherre@2ndquadrant.com; PostgreSQL Hackers
Subject: Re: GSOC 2018 Project - A New Sorting Routine
On 07/24/2018 12:21 AM, Kefan Yang wrote:
> Hi Tomas!
>
> I did a few tests on my own Linux machine, but the problem is that my
> resources on AWS(CPU, RAM and even Disk space) are very limited. I
> considered establishing virtual machine on my own PC but the performance
> is even worse.
>
> My original patch has two main optimizations: (1) switch to heap sort
> when depth limit exceeded (2) check whether the array is presorted only
> once at the beginning. Now I want to test these optimizations
> separately. On AWS EC2 instance, regressions on CREATE INDEX cases seems
> to be less significant if we use (1) only, but I can only test up to
> 100000 records and 512MB memory using your scripts.
>
> So would you mind re-running the tests using the two patches I provided
> in the attachment? That will be very helpful
>
I can do that, but it'll have to wait a couple of days. I'm currently
using the boxes for some other tests.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* RE: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Re: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Re: GSOC 2018 Project - A New Sorting Routine Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-23 22:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-24 15:16 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-30 21:21 ` RE: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-08-01 17:05 ` Kefan Yang <starordust@gmail.com>
0 siblings, 0 replies; 15+ messages in thread
From: Kefan Yang @ 2018-08-01 17:05 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Andrey Borodin <x4mmm@yandex-team.ru>; Peter Geoghegan <pg@bowt.ie>; alvherre@2ndquadrant.com <alvherre@2ndquadrant.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Thanks for your time!
From: Tomas Vondra
Sent: August 1, 2018 6:30 AM
To: Kefan Yang
Cc: Andrey Borodin; Peter Geoghegan; alvherre@2ndquadrant.com; PostgreSQL Hackers
Subject: Re: GSOC 2018 Project - A New Sorting Routine
On 07/30/2018 11:21 PM, Kefan Yang wrote:
> Hey Tomas!
>
> Sorry to bother but it would be great if we can get the test results
> this week.
>
Attached are results from the i5 machine. I'm unable to rerun the tests
on the xeon box at the moment (which is IMHO the more interesting one).
Complete test data is available at
https://bitbucket.org/tvondra/sort-intro-sort-i5-2/src
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Fwd: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
@ 2018-07-14 01:03 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-14 01:24 ` Re: Fwd: GSOC 2018 Project - A New Sorting Routine Peter Geoghegan <pg@bowt.ie>
1 sibling, 1 reply; 15+ messages in thread
From: Tomas Vondra @ 2018-07-14 01:03 UTC (permalink / raw)
To: Kefan Yang <starordust@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
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
^ permalink raw reply [nested|flat] 15+ messages in thread
* Re: Fwd: GSOC 2018 Project - A New Sorting Routine
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Re: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Fwd: GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-14 01:03 ` Re: Fwd: GSOC 2018 Project - A New Sorting Routine Tomas Vondra <tomas.vondra@2ndquadrant.com>
@ 2018-07-14 01:24 ` Peter Geoghegan <pg@bowt.ie>
0 siblings, 0 replies; 15+ messages in thread
From: Peter Geoghegan @ 2018-07-14 01:24 UTC (permalink / raw)
To: Tomas Vondra <tomas.vondra@2ndquadrant.com>; +Cc: Kefan Yang <starordust@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Fri, Jul 13, 2018 at 6:03 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
> 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.
+1. The importance of the quadratic worst case for an industrial
strength quicksort seems to often be overstated.
Robert Sedgewick's Algorithms book has *excellent* analysis of
quicksort's worst case, which might be worth a read.
--
Peter Geoghegan
^ permalink raw reply [nested|flat] 15+ messages in thread
end of thread, other threads:[~2018-08-01 17:05 UTC | newest]
Thread overview: 15+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2018-07-10 21:02 GSOC 2018 Project - A New Sorting Routine Kefan Yang <starordust@gmail.com>
2018-07-13 00:50 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-13 22:04 ` Kefan Yang <starordust@gmail.com>
2018-07-13 22:10 ` Peter Geoghegan <pg@bowt.ie>
2018-07-14 21:20 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 05:06 ` Andrey Borodin <x4mmm@yandex-team.ru>
2018-07-18 21:13 ` Kefan Yang <starordust@gmail.com>
2018-07-18 21:26 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-18 22:13 ` Alvaro Herrera <alvherre@2ndquadrant.com>
2018-07-23 22:21 ` Kefan Yang <starordust@gmail.com>
2018-07-24 15:16 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-30 21:21 ` Kefan Yang <starordust@gmail.com>
2018-08-01 17:05 ` Kefan Yang <starordust@gmail.com>
2018-07-14 01:03 ` Tomas Vondra <tomas.vondra@2ndquadrant.com>
2018-07-14 01:24 ` Peter Geoghegan <pg@bowt.ie>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox