The case for removing replacement selection sort

On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan <pg@bowt.ie> 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 win and benchmark them to find
out what happens. I find it really hard to believe that sorting a
long presorted stream of tuples (or, say, 2-1-4-3-6-5-8-7-10-9 etc.)
is ever going to be as fast with any other algorithm as it is with
replacement selection.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Wed, Aug 30, 2017 at 12:51 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan <pg@bowt.ie> 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 win and benchmark them to find
out what happens. I find it really hard to believe that sorting a
long presorted stream of tuples (or, say, 2-1-4-3-6-5-8-7-10-9 etc.)
is ever going to be as fast with any other algorithm as it is with
replacement selection.

Replacement selection as implemented in Postgres is supposed to be
about the "single run, no merge" best case. This must use
TSS_SORTEDONTAPE processing, which is optimized for random access,
which is usually the wrong thing.

In general, sorting is only one cost that is involved here, and is not
the predominant cost with presorted input.

--
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

On Wed, Aug 30, 2017 at 4:18 PM, Peter Geoghegan <pg@bowt.ie> wrote:

On Wed, Aug 30, 2017 at 12:51 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Fri, Jul 14, 2017 at 6:20 PM, Peter Geoghegan <pg@bowt.ie> 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 win and benchmark them to find
out what happens. I find it really hard to believe that sorting a
long presorted stream of tuples (or, say, 2-1-4-3-6-5-8-7-10-9 etc.)
is ever going to be as fast with any other algorithm as it is with
replacement selection.

Replacement selection as implemented in Postgres is supposed to be
about the "single run, no merge" best case. This must use
TSS_SORTEDONTAPE processing, which is optimized for random access,
which is usually the wrong thing.

In general, sorting is only one cost that is involved here, and is not
the predominant cost with presorted input.

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.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Wed, Aug 30, 2017 at 3:01 PM, Robert Haas <robertmhaas@gmail.com> 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
...

postgres=# set work_mem = '2MB';
SET
postgres=# show replacement_sort_tuples ;
replacement_sort_tuples
─────────────────────────
150000
(1 row)
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 4157.267 ms (00:04.157)
(30784) /postgres=# set replacement_sort_tuples = 0;
SET
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 3343.789 ms (00:03.344)

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 I could find a case that makes replacement
selection look much worse, if I tried.

--
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

On Wed, Aug 30, 2017 at 3:14 PM, Peter Geoghegan <pg@bowt.ie> 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 I could find a case that makes replacement
selection look much worse, if I tried.

Just to see where we end up, I quickly wrote a patch to remove
replacement selection + replacement_sort_tuples. The LOC impact worked
out like this:

$ git diff master --stat
doc/src/sgml/config.sgml | 39 ----
src/backend/utils/init/globals.c | 1 -
src/backend/utils/misc/guc.c | 10 -
src/backend/utils/misc/postgresql.conf.sample | 1 -
src/backend/utils/sort/tuplesort.c | 403
+++++------------------------------
src/include/miscadmin.h | 1 -
src/test/regress/expected/cluster.out | 17 +-
src/test/regress/sql/cluster.sql | 14 +-
8 files changed, 52 insertions(+), 434 deletions(-)

It was nice to be able to remove comments that make certain
distinctions that replacement selection cares about. These were
tedious to read. I managed to remove several paragraphs within
tuplesort.c's header comments.

Another advantage of the changes made that I noticed in passing is
that SortTuple.tupindex is now only used while merging. It would be
quite possible to remove SortTuple.tupindex entirely, as an additional
piece of work, by providing some other indirection to get that
information when merging. From there, we could replace SortTuple.tuple
with a bitfield, that has one bit for NULLness, and treats other bits
as a 63-bit or 31-bit integer. This integer would be used an offset
into a buffer that we repalloc(), thus removing all retail palloc()s,
even during run generation. Using one big buffer for tuples would make
tuplesort.c quite a bit more memory efficient (SortTuple will only be
16 bytes, we won't waste memory on palloc() headers, and sequential
access is made more cache efficient in presorted pass-by-reference
cases).

I'm not planning to work on this myself. It is similar to something
that Heikki described last year, but goes a bit further by eliminating
all palloc() header overhead, while also not playing tricks with
reclaiming bits from pointers (I recall that Tom didn't like that
aspect of Heikki's proposal at all). There would be new infrastructure
required to make this work -- we'd have to be able to ask routines
like ExecCopySlotMinimalTuple() and heap_copytuple() to copy into our
own large tuple buffer, rather than doing their own palloc() on
tuplesort's behalf. But that seems like a good idea anyway.

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 management of the type I just outlined, which seems like a
useful direction to take tuplesort in.

--
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

On Wed, Aug 30, 2017 at 6:14 PM, Peter Geoghegan <pg@bowt.ie> wrote:

On Wed, Aug 30, 2017 at 3:01 PM, Robert Haas <robertmhaas@gmail.com> 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
...

postgres=# set work_mem = '2MB';
SET
postgres=# show replacement_sort_tuples ;
replacement_sort_tuples
─────────────────────────
150000
(1 row)
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 4157.267 ms (00:04.157)
(30784) /postgres=# set replacement_sort_tuples = 0;
SET
(30784) /postgres=# select count(distinct aid) from pgbench_accounts ;
count
────────────
10,000,000
(1 row)

Time: 3343.789 ms (00:03.344)

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 I could find a case that makes replacement
selection look much worse, if I tried.

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
reproduce your results here.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Wed, Aug 30, 2017 at 5:38 PM, Robert Haas <robertmhaas@gmail.com> 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
reproduce your results here.

But I *was* trying to get a best case. That's why it isn't even worse.
That's what the docs say the best case is, after all.

This is the kind of thing that replacement selection actually did do
better with on 9.6. I clearly remember Tomas Vondra doing lots of
benchmarking, showing some benefit with RS with a work_mem of 8MB or
less. As I said in my introduction on this thread, we weren't wrong to
add replacement_sort_tuples to 9.6, given where things were with
merging at the time. But, it does very much appear to create less than
zero benefit these days. The picture changed.

--
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

On Wed, Aug 30, 2017 at 4:59 PM, Peter Geoghegan <pg@bowt.ie> 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 management of the type I just outlined, which seems like a
useful direction to take tuplesort in.

I attach a patch to remove replacement selection, which I'll submit to CF 1.

--
Peter Geoghegan

On Fri, Sep 1, 2017 at 6:00 AM, Peter Geoghegan <pg@bowt.ie> wrote:

On Wed, Aug 30, 2017 at 4:59 PM, Peter Geoghegan <pg@bowt.ie> 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 management of the type I just outlined, which seems like a
useful direction to take tuplesort in.

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 <xref
linkend="guc-replacement-sort-tuples"> but you removed that id.

--
Thomas Munro
http://www.enterprisedb.com

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

On Wed, Sep 6, 2017 at 2:47 PM, Thomas Munro
<thomas.munro@enterprisedb.com> 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 <xref
linkend="guc-replacement-sort-tuples"> but you removed that id.

Thanks for looking into it.

I suppose that the solution is to change the 9.6 release notes to no
longer have a replacement_sort_tuples link. Anyone else have an
opinion on that?

--
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

Hi,

On 08/31/2017 02:56 AM, Peter Geoghegan wrote:

On Wed, Aug 30, 2017 at 5:38 PM, Robert Haas <robertmhaas@gmail.com> 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
reproduce your results here.

But I *was* trying to get a best case. That's why it isn't even worse.
That's what the docs say the best case is, after all.

This is the kind of thing that replacement selection actually did do
better with on 9.6. I clearly remember Tomas Vondra doing lots of
benchmarking, showing some benefit with RS with a work_mem of 8MB or
less. As I said in my introduction on this thread, we weren't wrong to
add replacement_sort_tuples to 9.6, given where things were with
merging at the time. But, it does very much appear to create less than
zero benefit these days. The picture changed.

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.

regards

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

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

On Thu, Sep 7, 2017 at 5:38 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> 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 removing this code if we
don't need it any more, but it'd be a lot better to have more numbers
before deciding that.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

On Thu, Sep 7, 2017 at 2:49 PM, Robert Haas <robertmhaas@gmail.com> wrote:

On Thu, Sep 7, 2017 at 5:38 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> 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 removing this code if we
don't need it any more, but it'd be a lot better to have more numbers
before deciding that.

It isn't always a win. For example, if I alter the pgbench_accounts
table so that the column "aid" is of type numeric, the picture changes
for my test case -- replacement selection is still somewhat faster for
the "select count(distinct aid) from pgbench_accounts" query with
work_mem=2MB. It takes about 5.4 seconds with replacement selection,
versus 7.4 seconds for quicksorting. But, I still think we should
proceed with my patch, because:

* 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.
The trade-off between those two properties (faster for int4/int8 when
ordered, slower for numeric) recommends killing replacement selection
entirely. It's not a slam dunk, but it makes sense on performance
grounds, IMV.

* The comparator numeric_fast_cmp() is not well optimized -- it
doesn't avoid allocating memory with each call, for example, unlike
varstrfastcmp_locale(). This could and should be improved, and might
even change the picture for this second test case.

* With the default work_mem of 8MB, we never use replacement selection
anyway. Whatever its merits, it's pretty rare to use replacement
selection simply because the default replacement_sort_tuples just
isn't that many tuples (150,000).

* The upside of my patch is not inconsiderable: We can remove a lot of
code, which will enable further improvements in the future, which are
far more compelling (cleaner memory management, the use of memory
batches during run generation).

--
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

On 8 September 2017 at 18:06, Peter Geoghegan <pg@bowt.ie> 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 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 text as well as numbers. Also, people often sort on
keys of more than one column....

--
greg

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

On Sat, Sep 9, 2017 at 8:28 AM, Greg Stark <stark@mit.edu> 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 text as well as numbers.

I haven't looked at text, because I presume that it's very rare for
tuples within a table to be more or less ordered by a text attribute.
While the traditional big advantage of replacement selection has
always been its ability to double initial run length on average, where
text performance is quite interesting because localized clustering
still happens, that doesn't really seem relevant here. The remaining
use of replacement selection is expressly only about the "single run,
no merge" best case, and in particular about avoiding regressions when
upgrading from versions prior to 9.6 (9.6 is the version where we
began to generally prefer quicksort).

Also, people often sort on
keys of more than one column....

Very true. I should test this.

--
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

On 09/11/2017 01:03 AM, Peter Geoghegan wrote:

On Sat, Sep 9, 2017 at 8:28 AM, Greg Stark <stark@mit.edu> 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 text as well as numbers.

I haven't looked at text, because I presume that it's very rare for
tuples within a table to be more or less ordered by a text
attribute. While the traditional big advantage of replacement
selection has always been its ability to double initial run length on
average, where text performance is quite interesting because
localized clustering still happens, that doesn't really seem relevant
here. The remaining use of replacement selection is expressly only
about the "single run, no merge" best case, and in particular about
avoiding regressions when upgrading from versions prior to 9.6 (9.6
is the version where we began to generally prefer quicksort).

Also, people often sort on keys of more than one column....

Very true. I should test this.

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. We
can either tweak some of the existing data sets + queries, or come up
with entirely new tests.

The current tests construct data sets with different features (unique or
low/high-cardinality, random/sorted/almost-sorted). How should that work
for multi-key sorts? Same features for all columns, or some mix?

For the existing queries, I should have some initial results tomorrow,
at least for the data sets with 100k and 1M rows. The tests with 10M
rows will take much more time (it takes 1-2hours for a single work_mem
value, and we're testing 6 of them).

But perhaps we can reduce the number of tests somehow, only testing the
largest/smallest work_mem values? So that we could get some numbers now,
possibly running the complete test suite later.

regards

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

On Sun, Sep 10, 2017 at 5:07 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> 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. We
can either tweak some of the existing data sets + queries, or come up
with entirely new tests.

I see that work_mem is set like this in the script:

"for wm in '1MB' '8MB' '32MB' '128MB' '512MB' '1GB'; do"

I suggest that we forget about values over 32MB, since the question of
how well quicksort does there was settled by your tests in 2016. I
would also add '4MB' to the list of wm values that you'll actually
test.

Any case with input that is initially in random order or DESC sort
order is not interesting, either. I suggest you remove those, too.

I think we're only interested in benchmarks where replacement
selection really does get its putative best case (no merge needed in
the end). Any (almost) sorted cases (the only cases that you are
interesting to test now) will always manage that, once you set
replacement_sort_tuples high enough, and provided there isn't even a
single tuple that is completely out of order. The "before" cases here
should have a replacement_sort_tuples of 1 billion (so that we're sure
to not have the limit prevent the use of replacement selection in the
first place), versus the "after" cases, which should have a
replacement_sort_tuples of 0 to represent my proposal (to represent
performance in a world where replacement selection is totally
removed).

For the existing queries, I should have some initial results tomorrow,
at least for the data sets with 100k and 1M rows. The tests with 10M
rows will take much more time (it takes 1-2hours for a single work_mem
value, and we're testing 6 of them).

I myself don't see that much value in a 10M row test.

Thanks for volunteering to test!
--
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

On 09/11/2017 02:22 AM, Peter Geoghegan wrote:

On Sun, Sep 10, 2017 at 5:07 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> 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. We
can either tweak some of the existing data sets + queries, or come up
with entirely new tests.

I see that work_mem is set like this in the script:

"for wm in '1MB' '8MB' '32MB' '128MB' '512MB' '1GB'; do"

I suggest that we forget about values over 32MB, since the question of
how well quicksort does there was settled by your tests in 2016. I
would also add '4MB' to the list of wm values that you'll actually
test.

OK, so 1MB, 4MB, 8MB, 32MB?

Any case with input that is initially in random order or DESC sort
order is not interesting, either. I suggest you remove those, too.

OK.

I think we're only interested in benchmarks where replacement
selection really does get its putative best case (no merge needed in
the end). Any (almost) sorted cases (the only cases that you are
interesting to test now) will always manage that, once you set
replacement_sort_tuples high enough, and provided there isn't even a
single tuple that is completely out of order. The "before" cases here
should have a replacement_sort_tuples of 1 billion (so that we're sure
to not have the limit prevent the use of replacement selection in the
first place), versus the "after" cases, which should have a
replacement_sort_tuples of 0 to represent my proposal (to represent
performance in a world where replacement selection is totally
removed).

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 setting replacement_sort_tuples=0 should have
the same effect.

I probably won't eliminate the random/DESC data sets, though. At least
not from the two smaller data sets - I want to do a bit of benchmarking
on Heikki's polyphase merge removal patch, and for that patch those data
sets are still relevant. Also, it's useful to have a subset of results
where we know we don't expect any change.

For the existing queries, I should have some initial results
tomorrow, at least for the data sets with 100k and 1M rows. The
tests with 10M rows will take much more time (it takes 1-2hours for
a single work_mem value, and we're testing 6 of them).

I myself don't see that much value in a 10M row test.

Meh, more data is probably better. And with the reduced work_mem values
and skipping of random/DESC data sets it should complete much faster.

regards

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

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

On Sun, Sep 10, 2017 at 5:59 PM, Tomas Vondra
<tomas.vondra@2ndquadrant.com> 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 setting replacement_sort_tuples=0 should have
the same effect.

I think that there may be a very slight advantage to RS-free
performance with my patch actually applied, because it removes the
number of instructions that heap maintenance (merging) routines
consist of. This is due to my removing HEAPCOMPARE()/tupindex
handling. However, it's probably a low single digit percentage
difference -- not enough to be worth taking into account, probably. I
assume that just setting replacement_sort_tuples to zero is more
convenient for you (that's what I did).

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 mechanically verify that we really do only have one run in the
end with RS, but I assume that such paranoia is unneeded.)

I probably won't eliminate the random/DESC data sets, though. At least
not from the two smaller data sets - I want to do a bit of benchmarking
on Heikki's polyphase merge removal patch, and for that patch those data
sets are still relevant. Also, it's useful to have a subset of results
where we know we don't expect any change.

Okay. The DESC dataset is going to make my patch look good, because it
won't change anything for merging (same number of runs in the end),
but sorting will be slower for the first run with RS.

Meh, more data is probably better. And with the reduced work_mem values
and skipping of random/DESC data sets it should complete much faster.

Note that my own test case had a much higher number of tuples than
even 10 million -- it had 100 million tuples. I think that if any of
your test cases bring about a new insight, it will not be due to the
number of distinct tuples. But, if the extra time it takes doesn't
matter to you, then it doesn't matter to me either.

--
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