[PATCH] Incremental sort (was: PoC: Partial sort)

Hi all!

I decided to start new thread for this patch for following two reasons.
* It's renamed from "Partial sort" to "Incremental sort" per suggestion by
Robert Haas [1]. New name much better characterizes the essence of
algorithm.
* I think it's not PoC anymore. Patch received several rounds of review
and now it's in the pretty good shape.

Attached revision of patch has following changes.
* According to review [1], two new path and plan nodes are responsible for
incremental sort: IncSortPath and IncSort which are inherited from SortPath
and Sort correspondingly. That allowed to get rid of set of hacks with
minimal code changes.
* According to review [1] and comment [2], previous tuple is stored in
standalone tuple slot of SortState rather than just HeapTuple.
* New GUC parameter enable_incsort is introduced to control planner
ability to choose incremental sort.
* Test of postgres_fdw with not pushed down cross join is corrected. It
appeared that with incremental sort such query is profitable to push down.
I changed ORDER BY columns so that index couldn't be used. I think this
solution is more elegant than setting enable_incsort = off.

Also patch has set of assorted code and comments improvements.

Links
1.
https://www.postgresql.org/message-id/CA+TgmoZapyHRm7NVyuyZ+yAV=U1a070BOgRe7PkgyrAegR4JDA@mail.gmail.com
2.
https://www.postgresql.org/message-id/CAM3SWZQL4yD2SnDheMCGL0Q2b2oTdKUvv_L6Zg_FcGoLuwMffg@mail.gmail.com

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, Feb 18, 2017 at 4:01 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> I decided to start new thread for this patch for following two reasons.
> * It's renamed from "Partial sort" to "Incremental sort" per suggestion by
> Robert Haas [1]. New name much better characterizes the essence of
> algorithm.
> * I think it's not PoC anymore. Patch received several rounds of review
> and now it's in the pretty good shape.
>
> Attached revision of patch has following changes.
> * According to review [1], two new path and plan nodes are responsible for
> incremental sort: IncSortPath and IncSort which are inherited from SortPath
> and Sort correspondingly. That allowed to get rid of set of hacks with
> minimal code changes.
> * According to review [1] and comment [2], previous tuple is stored in
> standalone tuple slot of SortState rather than just HeapTuple.
> * New GUC parameter enable_incsort is introduced to control planner ability
> to choose incremental sort.
> * Test of postgres_fdw with not pushed down cross join is corrected. It
> appeared that with incremental sort such query is profitable to push down.
> I changed ORDER BY columns so that index couldn't be used. I think this
> solution is more elegant than setting enable_incsort = off.

I usually advocate for spelling things out instead of abbreviating, so
I guess I'll stay true to form here and suggest that abbreviating
incremental to inc doesn't seem like a great idea. Is that sort
incrementing, incremental, incredible, incautious, or incorporated?

The first hunk in the patch, a change in the postgres_fdw regression
test output, looks an awful lot like a bug: now the query that
formerly returned various different numbers is returning all zeroes.
It might not actually be a bug, because you've also changed the test
query (not sure why), but anyway the new regression test output that
is all zeroes seems less useful for catching bugs in, say, the
ordering of the results than the old output where the different rows
were different.

I don't know of any existing cases where the same executor file is
responsible for executing more than 1 different type of executor node.
I was imagining a more-complete separation of the new executor node.

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

On Sun, Feb 19, 2017 at 2:18 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Sat, Feb 18, 2017 at 4:01 PM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > I decided to start new thread for this patch for following two reasons.
> > * It's renamed from "Partial sort" to "Incremental sort" per suggestion
> by
> > Robert Haas [1]. New name much better characterizes the essence of
> > algorithm.
> > * I think it's not PoC anymore. Patch received several rounds of review
> > and now it's in the pretty good shape.
> >
> > Attached revision of patch has following changes.
> > * According to review [1], two new path and plan nodes are responsible
> for
> > incremental sort: IncSortPath and IncSort which are inherited from
> SortPath
> > and Sort correspondingly. That allowed to get rid of set of hacks with
> > minimal code changes.
> > * According to review [1] and comment [2], previous tuple is stored in
> > standalone tuple slot of SortState rather than just HeapTuple.
> > * New GUC parameter enable_incsort is introduced to control planner
> ability
> > to choose incremental sort.
> > * Test of postgres_fdw with not pushed down cross join is corrected. It
> > appeared that with incremental sort such query is profitable to push
> down.
> > I changed ORDER BY columns so that index couldn't be used. I think this
> > solution is more elegant than setting enable_incsort = off.
>
> I usually advocate for spelling things out instead of abbreviating, so
> I guess I'll stay true to form here and suggest that abbreviating
> incremental to inc doesn't seem like a great idea. Is that sort
> incrementing, incremental, incredible, incautious, or incorporated?
>

I'm not that sure about naming of GUCs, because we already
have enable_hashagg instead of enable_hashaggregate, enable_material
instead of enable_materialize, enable_nestloop instead
of enable_nestedloop. But anyway I renamed "inc" to "Incremental"
everywhere in the code. I renamed enable_incsort GUC into
enable_incrementalsort as well, because I don't have strong opinion here.

The first hunk in the patch, a change in the postgres_fdw regression
> test output, looks an awful lot like a bug: now the query that
> formerly returned various different numbers is returning all zeroes.
> It might not actually be a bug, because you've also changed the test
> query (not sure why), but anyway the new regression test output that
> is all zeroes seems less useful for catching bugs in, say, the
> ordering of the results than the old output where the different rows
> were different.
>

Yes, I've changed regression test query as I mentioned in the previous
message. With incremental sort feature original query can't serve anymore
as an example of non-pushdown join. However, you're right that query which
returns all zeroes doesn't look good there either. So, I changed that
query to ordering by column "c3" which is actually non-indexed textual
representation of "c1".

> I don't know of any existing cases where the same executor file is
> responsible for executing more than 1 different type of executor node.
> I was imagining a more-complete separation of the new executor node.
>

Ok, I put incremental sort into separate executor node.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Feb 27, 2017 at 8:29 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:

This patch needs to be rebased.

1. It fails while applying as below

patching file src/test/regress/expected/sysviews.out
Hunk #1 FAILED at 70.
1 out of 1 hunk FAILED -- saving rejects to file
src/test/regress/expected/sysviews.out.rej
patching file src/test/regress/sql/inherit.sql

2. Also, there are compilation errors due to new commits.

-fwrapv -fexcess-precision=standard -O2 -I../../../../src/include
-D_GNU_SOURCE -c -o createplan.o createplan.c
createplan.c: In function ‘create_gather_merge_plan’:
createplan.c:1510:11: warning: passing argument 3 of ‘make_sort’ makes
integer from pointer without a cast [enabled by default]
gm_plan->nullsFirst);
^
createplan.c:235:14: note: expected ‘int’ but argument is of type ‘AttrNumber *’
static Sort *make_sort(Plan *lefttree, int numCols, int skipCols,
^
createplan.c:1510:11: warning: passing argument 4 of ‘make_sort’ from
incompatible pointer type [enabled by default]
gm_plan->nullsFirst);

--
Thanks and Regards
Mithun C Y
EnterpriseDB: http://www.enterprisedb.com

Dear Mithun,

On Mon, Mar 20, 2017 at 10:01 AM, Mithun Cy <mithun(dot)cy(at)enterprisedb(dot)com>
wrote:

> On Mon, Feb 27, 2017 at 8:29 PM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> This patch needs to be rebased.
>
> 1. It fails while applying as below
>
> patching file src/test/regress/expected/sysviews.out
> Hunk #1 FAILED at 70.
> 1 out of 1 hunk FAILED -- saving rejects to file
> src/test/regress/expected/sysviews.out.rej
> patching file src/test/regress/sql/inherit.sql
>
> 2. Also, there are compilation errors due to new commits.
>
> -fwrapv -fexcess-precision=standard -O2 -I../../../../src/include
> -D_GNU_SOURCE -c -o createplan.o createplan.c
> createplan.c: In function ‘create_gather_merge_plan’:
> createplan.c:1510:11: warning: passing argument 3 of ‘make_sort’ makes
> integer from pointer without a cast [enabled by default]
> gm_plan->nullsFirst);
> ^
> createplan.c:235:14: note: expected ‘int’ but argument is of type
> ‘AttrNumber *’
> static Sort *make_sort(Plan *lefttree, int numCols, int skipCols,
> ^
> createplan.c:1510:11: warning: passing argument 4 of ‘make_sort’ from
> incompatible pointer type [enabled by default]
> gm_plan->nullsFirst);
>

Thank you for the report.
Please, find rebased patch in the attachment.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
> Please, find rebased patch in the attachment.

I had a quick look at this.

* I'd love to have an explanation of what an Incremental Sort is, in the
file header comment for nodeIncrementalSort.c.

* I didn't understand the maxMem stuff in tuplesort.c. The comments
there use the phrase "on-disk memory", which seems like an oxymoron.
Also, "maximum status" seems weird, as it assumes that there's a natural
order to the states.

* In the below example, the incremental sort is significantly slower
than the Seq Scan + Sort you get otherwise:

create table foo (a int4, b int4, c int4);
insert into sorttest select g, g, g from generate_series(1, 1000000) g;
vacuum foo;
create index i_sorttest on sorttest (a, b, c);
set work_mem='100MB';

postgres=# explain select count(*) from (select * from sorttest order by
a, c) as t;
QUERY PLAN

-------------------------------------------------------------------------------------------------------
Aggregate (cost=138655.68..138655.69 rows=1 width=8)
-> Incremental Sort (cost=610.99..124870.38 rows=1102824 width=12)
Sort Key: sorttest.a, sorttest.c
Presorted Key: sorttest.a
-> Index Only Scan using i_sorttest on sorttest
(cost=0.43..53578.79 rows=1102824 width=12)
(5 rows)

Time: 0.409 ms
postgres=# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)

Time: 387.091 ms

postgres=# explain select count(*) from (select * from sorttest order by
a, c) as t;
QUERY PLAN

-------------------------------------------------------------------------------
Aggregate (cost=130063.84..130063.85 rows=1 width=8)
-> Sort (cost=115063.84..117563.84 rows=1000000 width=12)
Sort Key: sorttest.a, sorttest.c
-> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000
width=12)
(4 rows)

Time: 0.345 ms
postgres=# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)

Time: 231.668 ms

According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
alleviate that, it might be worthwhile to add a special case for when
the group contains exactly one group, and not put the tuple to the
tuplesort in that case. Or if we cannot ensure that the Incremental Sort
is actually faster, the cost model should probably be smarter, to avoid
picking an incremental sort when it's not a win.

- Heikki

Hi Alexander,

On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
>> Please, find rebased patch in the attachment.
>
> I had a quick look at this.

<...>

> According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
> alleviate that, it might be worthwhile to add a special case for when
> the group contains exactly one group, and not put the tuple to the
> tuplesort in that case. Or if we cannot ensure that the Incremental Sort
> is actually faster, the cost model should probably be smarter, to avoid
> picking an incremental sort when it's not a win.

This thread has been idle for over a week. Please respond with a new
patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be marked
"Returned with Feedback".

--
-David
david(at)pgmasters(dot)net

On Tue, Mar 28, 2017 at 5:27 PM, David Steele <david(at)pgmasters(dot)net> wrote:

> Hi Alexander,
>
> On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
>
>> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
>>
>>> Please, find rebased patch in the attachment.
>>>
>>
>> I had a quick look at this.
>>
>
> <...>
>
> According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
>> alleviate that, it might be worthwhile to add a special case for when
>> the group contains exactly one group, and not put the tuple to the
>> tuplesort in that case. Or if we cannot ensure that the Incremental Sort
>> is actually faster, the cost model should probably be smarter, to avoid
>> picking an incremental sort when it's not a win.
>>
>
> This thread has been idle for over a week. Please respond with a new
> patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be marked
> "Returned with Feedback".

Thank you for reminder!

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Mar 20, 2017 at 5:19 PM, Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:

> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
>
>> Please, find rebased patch in the attachment.
>>
>
> I had a quick look at this.
>
> * I'd love to have an explanation of what an Incremental Sort is, in the
> file header comment for nodeIncrementalSort.c.
>

Done.

* I didn't understand the maxMem stuff in tuplesort.c. The comments there
> use the phrase "on-disk memory", which seems like an oxymoron. Also,
> "maximum status" seems weird, as it assumes that there's a natural order to
> the states.
>

Variables were renamed.

* In the below example, the incremental sort is significantly slower than
> the Seq Scan + Sort you get otherwise:
>
> create table foo (a int4, b int4, c int4);
> insert into sorttest select g, g, g from generate_series(1, 1000000) g;
> vacuum foo;
> create index i_sorttest on sorttest (a, b, c);
> set work_mem='100MB';
>
>
> postgres=# explain select count(*) from (select * from sorttest order by
> a, c) as t;
> QUERY PLAN
> ------------------------------------------------------------
> -------------------------------------------
> Aggregate (cost=138655.68..138655.69 rows=1 width=8)
> -> Incremental Sort (cost=610.99..124870.38 rows=1102824 width=12)
> Sort Key: sorttest.a, sorttest.c
> Presorted Key: sorttest.a
> -> Index Only Scan using i_sorttest on sorttest
> (cost=0.43..53578.79 rows=1102824 width=12)
> (5 rows)
>
> Time: 0.409 ms
> postgres=# select count(*) from (select * from sorttest order by a, c) as
> t;
> count
> ---------
> 1000000
> (1 row)
>
> Time: 387.091 ms
>
>
> postgres=# explain select count(*) from (select * from sorttest order by
> a, c) as t;
> QUERY PLAN
> ------------------------------------------------------------
> -------------------
> Aggregate (cost=130063.84..130063.85 rows=1 width=8)
> -> Sort (cost=115063.84..117563.84 rows=1000000 width=12)
> Sort Key: sorttest.a, sorttest.c
> -> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000
> width=12)
> (4 rows)
>
> Time: 0.345 ms
> postgres=# select count(*) from (select * from sorttest order by a, c) as
> t;
> count
> ---------
> 1000000
> (1 row)
>
> Time: 231.668 ms
>
> According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
> alleviate that, it might be worthwhile to add a special case for when the
> group contains exactly one group, and not put the tuple to the tuplesort in
> that case.

I'm not sure we should do such optimization for one tuple per group, since
it's similar situation with 2 or 3 tuples per group.

> Or if we cannot ensure that the Incremental Sort is actually faster, the
> cost model should probably be smarter, to avoid picking an incremental sort
> when it's not a win.

I added to cost_sort() extra costing for incremental sort: cost of extra
tuple copying and comparing as well as cost of tuplesort reset.
The only problem is that I made following estimate for tuplesort reset:

run_cost += 10.0 * cpu_tuple_cost * num_groups;

It makes ordinal sort to be selected in your example, but it contains
constant 10 which is quite arbitrary. It would be nice to evade such hard
coded constants, but I don't know how could we calculate such cost
realistically.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 2017-03-29 00:17:02 +0300, Alexander Korotkov wrote:
> On Tue, Mar 28, 2017 at 5:27 PM, David Steele <david(at)pgmasters(dot)net> wrote:
>
> > Hi Alexander,
> >
> > On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
> >
> >> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
> >>
> >>> Please, find rebased patch in the attachment.
> >>>
> >>
> >> I had a quick look at this.
> >>
> >
> > <...>
> >
> > According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
> >> alleviate that, it might be worthwhile to add a special case for when
> >> the group contains exactly one group, and not put the tuple to the
> >> tuplesort in that case. Or if we cannot ensure that the Incremental Sort
> >> is actually faster, the cost model should probably be smarter, to avoid
> >> picking an incremental sort when it's not a win.
> >>
> >
> > This thread has been idle for over a week. Please respond with a new
> > patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be marked
> > "Returned with Feedback".

> Thank you for reminder!

I've just done so. Please resubmit once updated, it's a cool feature.

- Andres

On Mon, Apr 3, 2017 at 9:34 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:

> On 2017-03-29 00:17:02 +0300, Alexander Korotkov wrote:
> > On Tue, Mar 28, 2017 at 5:27 PM, David Steele <david(at)pgmasters(dot)net>
> wrote:
> > > On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
> > >
> > >> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
> > >>
> > >>> Please, find rebased patch in the attachment.
> > >>>
> > >>
> > >> I had a quick look at this.
> > >>
> > >
> > > <...>
> > >
> > > According to 'perf', 85% of the CPU time is spent in ExecCopySlot(). To
> > >> alleviate that, it might be worthwhile to add a special case for when
> > >> the group contains exactly one group, and not put the tuple to the
> > >> tuplesort in that case. Or if we cannot ensure that the Incremental
> Sort
> > >> is actually faster, the cost model should probably be smarter, to
> avoid
> > >> picking an incremental sort when it's not a win.
> > >>
> > >
> > > This thread has been idle for over a week. Please respond with a new
> > > patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be
> marked
> > > "Returned with Feedback".
>
> > Thank you for reminder!
>
> I've just done so. Please resubmit once updated, it's a cool feature.
>

Thank you!
I already sent version of patch after David's reminder.
Please find rebased patch in the attachment.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On April 3, 2017 12:03:56 PM PDT, Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>On Mon, Apr 3, 2017 at 9:34 PM, Andres Freund <andres(at)anarazel(dot)de>
>wrote:
>
>> On 2017-03-29 00:17:02 +0300, Alexander Korotkov wrote:
>> > On Tue, Mar 28, 2017 at 5:27 PM, David Steele <david(at)pgmasters(dot)net>
>> wrote:
>> > > On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
>> > >
>> > >> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
>> > >>
>> > >>> Please, find rebased patch in the attachment.
>> > >>>
>> > >>
>> > >> I had a quick look at this.
>> > >>
>> > >
>> > > <...>
>> > >
>> > > According to 'perf', 85% of the CPU time is spent in
>ExecCopySlot(). To
>> > >> alleviate that, it might be worthwhile to add a special case for
>when
>> > >> the group contains exactly one group, and not put the tuple to
>the
>> > >> tuplesort in that case. Or if we cannot ensure that the
>Incremental
>> Sort
>> > >> is actually faster, the cost model should probably be smarter,
>to
>> avoid
>> > >> picking an incremental sort when it's not a win.
>> > >>
>> > >
>> > > This thread has been idle for over a week. Please respond with a
>new
>> > > patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be
>> marked
>> > > "Returned with Feedback".
>>
>> > Thank you for reminder!
>>
>> I've just done so. Please resubmit once updated, it's a cool
>feature.
>>
>
>Thank you!
>I already sent version of patch after David's reminder.
>Please find rebased patch in the attachment.

Cool. I think that's still a bit late for v10?

Andres
--
Sent from my Android device with K-9 Mail. Please excuse my brevity.

On Mon, Apr 3, 2017 at 10:05 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:

> On April 3, 2017 12:03:56 PM PDT, Alexander Korotkov <
> a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> >On Mon, Apr 3, 2017 at 9:34 PM, Andres Freund <andres(at)anarazel(dot)de>
> >wrote:
> >
> >> On 2017-03-29 00:17:02 +0300, Alexander Korotkov wrote:
> >> > On Tue, Mar 28, 2017 at 5:27 PM, David Steele <david(at)pgmasters(dot)net>
> >> wrote:
> >> > > On 3/20/17 10:19 AM, Heikki Linnakangas wrote:
> >> > >
> >> > >> On 03/20/2017 11:33 AM, Alexander Korotkov wrote:
> >> > >>
> >> > >>> Please, find rebased patch in the attachment.
> >> > >>>
> >> > >>
> >> > >> I had a quick look at this.
> >> > >>
> >> > >
> >> > > <...>
> >> > >
> >> > > According to 'perf', 85% of the CPU time is spent in
> >ExecCopySlot(). To
> >> > >> alleviate that, it might be worthwhile to add a special case for
> >when
> >> > >> the group contains exactly one group, and not put the tuple to
> >the
> >> > >> tuplesort in that case. Or if we cannot ensure that the
> >Incremental
> >> Sort
> >> > >> is actually faster, the cost model should probably be smarter,
> >to
> >> avoid
> >> > >> picking an incremental sort when it's not a win.
> >> > >>
> >> > >
> >> > > This thread has been idle for over a week. Please respond with a
> >new
> >> > > patch by 2017-03-30 00:00 AoE (UTC-12) or this submission will be
> >> marked
> >> > > "Returned with Feedback".
> >>
> >> > Thank you for reminder!
> >>
> >> I've just done so. Please resubmit once updated, it's a cool
> >feature.
> >>
> >
> >Thank you!
> >I already sent version of patch after David's reminder.
> >Please find rebased patch in the attachment.
>
> Cool. I think that's still a bit late for v10?
>

I don't know. ISTM, that I addressed all the issues raised by reviewers.
Also, this patch is pending since late 2013. It would be very nice to
finally get it in...

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi,

On 2017-04-04 00:04:09 +0300, Alexander Korotkov wrote:
> > >Thank you!
> > >I already sent version of patch after David's reminder.
> > >Please find rebased patch in the attachment.
> >
> > Cool. I think that's still a bit late for v10?
> >
>
> I don't know. ISTM, that I addressed all the issues raised by reviewers.
> Also, this patch is pending since late 2013. It would be very nice to
> finally get it in...

To me this hasn't gotten even remotely enough performance evaluation.
And I don't think it's fair to characterize it as pending since 2013,
given it was essentially "waiting on author" for most of that.

Greetings,

Andres Freund

On Tue, Apr 4, 2017 at 12:09 AM, Andres Freund <andres(at)anarazel(dot)de> wrote:

> On 2017-04-04 00:04:09 +0300, Alexander Korotkov wrote:
> > > >Thank you!
> > > >I already sent version of patch after David's reminder.
> > > >Please find rebased patch in the attachment.
> > >
> > > Cool. I think that's still a bit late for v10?
> > >
> >
> > I don't know. ISTM, that I addressed all the issues raised by reviewers.
> > Also, this patch is pending since late 2013. It would be very nice to
> > finally get it in...
>
> To me this hasn't gotten even remotely enough performance evaluation.
>

I'm ready to put my efforts on that.

> And I don't think it's fair to characterize it as pending since 2013,
>

Probably, this duration isn't good characteristic at all.

> given it was essentially "waiting on author" for most of that.
>

What makes you think so? Do you have some statistics? Or is it just
random assumption?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Apr 3, 2017 at 5:09 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> To me this hasn't gotten even remotely enough performance evaluation.
> And I don't think it's fair to characterize it as pending since 2013,
> given it was essentially "waiting on author" for most of that.

This is undeniably a patch which has been kicking around for a lot of
time without getting a lot of attention, and if it just keeps getting
punted down the road, it's never going to become committable.
Alexander's questions upthread about what decisions the committer who
took an interest (Heikki) would prefer never really got an answer, for
example. I don't deny that there may be some work left to do here,
but I think blaming the author for a week's delay when this has been
ignored so often for so long is unfair.

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

On 2017-04-03 22:18:21 -0400, Robert Haas wrote:
> On Mon, Apr 3, 2017 at 5:09 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:
> > To me this hasn't gotten even remotely enough performance evaluation.
> > And I don't think it's fair to characterize it as pending since 2013,
> > given it was essentially "waiting on author" for most of that.
>
> This is undeniably a patch which has been kicking around for a lot of
> time without getting a lot of attention, and if it just keeps getting
> punted down the road, it's never going to become committable.

Indeed, it's old. And it hasn't gotten enough timely feedback.

But I don't think the wait time can meaningfully be measured by
subtracting two dates:
The first version of the patch, as a PoC, has been posted 2013-12-14,
which then got a good amount of feedback & revisions, and then stalled
till 2014-07-12. There a few back-and forths yielded a new version.
From 2014-09-15 till 2015-10-16 the patch stalled, waiting on its
author. That version had open todos ([1]), as had the version from
2016-03-13 [2], which weren't addressed 2016-03-30 - unfortunately that
was pretty much when the tree was frozen. 2016-09-13 a rebased patch
was sent, some minor points were raised 2016-10-02 (unaddressed), a
larger review was done 2016-12-01 ([5]), unaddressed till 2017-02-18.
At that point we're in this thread.

There's obviously some long waiting-on-author periods in there. And
some long needs-review periods.

> Alexander's questions upthread about what decisions the committer who
> took an interest (Heikki) would prefer never really got an answer, for
> example. I don't deny that there may be some work left to do here,
> but I think blaming the author for a week's delay when this has been
> ignored so often for so long is unfair.

I'm not trying to blame Alexander for a week's worth of delay, at all.
It's just that, well, we're past the original code-freeze date, three
days before the "final" code freeze. I don't think fairness is something
we can achieve at this point :(. Given the risk of regressions -
demonstrated in this thread although partially adressed - and the very
limited amount of benchmarking done, it seems unlikely that this is
going to be merged.

Regards,

Andres

[1] http://archives.postgresql.org/message-id/CAPpHfdvhwMsG69exCRUGK3ms-ng0PSPcucH5FU6tAaM-qL-1%2Bw%40mail.gmail.com
[2] http://archives.postgresql.org/message-id/CAPpHfdvzjYGLTyA-8ib8UYnKLPrewd9Z%3DT4YJNCRWiHWHHweWw%40mail.gmail.com
[3] http://archives.postgresql.org/message-id/CAPpHfdtCcHZ-mLWzsFrRCvHpV1LPSaOGooMZ3sa40AkwR=7ouQ@mail.gmail.com
[4] http://archives.postgresql.org/message-id/CAPpHfdvj1Tdi2WA64ZbBp5-yG-uzaRXzk3K7J7zt-cRX6YSd0A@mail.gmail.com
[5] http://archives.postgresql.org/message-id/CA+TgmoZapyHRm7NVyuyZ+yAV=U1a070BOgRe7PkgyrAegR4JDA@mail.gmail.com
[6] http://archives.postgresql.org/message-id/CAPpHfds1waRZ=NOmueYq0sx1ZSCnt+5QJvizT8ndT2=etZEeAQ@mail.gmail.com

On Wed, Mar 29, 2017 at 5:14 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> I added to cost_sort() extra costing for incremental sort: cost of extra
> tuple copying and comparing as well as cost of tuplesort reset.
> The only problem is that I made following estimate for tuplesort reset:
>
> run_cost += 10.0 * cpu_tuple_cost * num_groups;
>
>
> It makes ordinal sort to be selected in your example, but it contains
> constant 10 which is quite arbitrary. It would be nice to evade such hard
> coded constants, but I don't know how could we calculate such cost
> realistically.
>

That appears to be wrong. I intended to make cost_sort prefer plain sort
over incremental sort for this dataset size. But, that appears to be not
always right solution. Quick sort is so fast only on presorted data.
On my laptop I have following numbers for test case provided by Heikki.

Presorted data – very fast.

# explain select count(*) from (select * from sorttest order by a, c) as t;
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate (cost=147154.34..147154.35 rows=1 width=8)
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: sorttest.a, sorttest.c
-> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000
width=12)
(4 rows)

# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)

Time: 260,752 ms

Not presorted data – not so fast. It's actually slower than incremental
sort was.

# explain select count(*) from (select * from sorttest order by a desc, c
desc) as t;
QUERY PLAN
-------------------------------------------------------------------------------
Aggregate (cost=130063.84..130063.85 rows=1 width=8)
-> Sort (cost=115063.84..117563.84 rows=1000000 width=12)
Sort Key: sorttest.a DESC, sorttest.c DESC
-> Seq Scan on sorttest (cost=0.00..15406.00 rows=1000000
width=12)
(4 rows)

# select count(*) from (select * from sorttest order by a desc, c desc) as
t;
count
---------
1000000
(1 row)

Time: 416,207 ms

Thus, it would be nice to reflect the fact that our quicksort
implementation is very fast on presorted data. Fortunately, we have
corresponding statistics: STATISTIC_KIND_CORRELATION. However, it probably
should be a subject of a separate patch.

But I'd like to make incremental sort not slower than quicksort in case of
presorted data. New idea about it comes to my mind. Since cause of
incremental sort slowness in this case is too frequent reset of tuplesort,
then what if we would artificially put data in larger groups. Attached
revision of patch implements this: it doesn't stop to accumulate tuples to
tuplesort until we have MIN_GROUP_SIZE tuples.

# explain select count(*) from (select * from sorttest order by a, c) as t;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Aggregate (cost=85412.43..85412.43 rows=1 width=8)
-> Incremental Sort (cost=0.46..72912.43 rows=1000000 width=12)
Sort Key: sorttest.a, sorttest.c
Presorted Key: sorttest.a
-> Index Only Scan using i_sorttest on sorttest
(cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)

# select count(*) from (select * from sorttest order by a, c) as t;
count
---------
1000000
(1 row)

Time: 251,227 ms

# explain select count(*) from (select * from sorttest order by a desc, c
desc) as t;
QUERY PLAN
────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Aggregate (cost=85412.43..85412.43 rows=1 width=8)
-> Incremental Sort (cost=0.46..72912.43 rows=1000000 width=12)
Sort Key: sorttest.a DESC, sorttest.c DESC
Presorted Key: sorttest.a
-> Index Only Scan Backward using i_sorttest on sorttest
(cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)

# select count(*) from (select * from sorttest order by a desc, c desc) as
t;
count
---------
1000000
(1 row)

Time: 253,270 ms

Now, incremental sort is not slower than quicksort. And this seems to be
cool.
However, in the LIMIT case we will pay the price of fetching some extra
tuples from outer node. But, that doesn't seem to hurt us too much.

# explain select * from sorttest order by a, c limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------
Limit (cost=0.46..0.84 rows=10 width=12)
-> Incremental Sort (cost=0.46..37500.78 rows=1000000 width=12)
Sort Key: a, c
Presorted Key: a
-> Index Only Scan using i_sorttest on sorttest
(cost=0.42..30412.42 rows=1000000 width=12)
(5 rows)

# select * from sorttest order by a, c limit 10;
a | b | c
----+----+----
1 | 1 | 1
2 | 2 | 2
3 | 3 | 3
4 | 4 | 4
5 | 5 | 5
6 | 6 | 6
7 | 7 | 7
8 | 8 | 8
9 | 9 | 9
10 | 10 | 10
(10 rows)

Time: 0,903 ms

Any thoughts?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, Apr 26, 2017 at 8:39 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> That appears to be wrong. I intended to make cost_sort prefer plain sort
> over incremental sort for this dataset size. But, that appears to be not
> always right solution. Quick sort is so fast only on presorted data.

As you may know, I've often said that the precheck for sorted input
added to our quicksort implementation by a3f0b3d is misguided. It
sometimes throws away a ton of work if the presorted input isn't
*perfectly* presorted. This happens when the first out of order tuple
is towards the end of the presorted input.

I think that it isn't fair to credit our qsort with doing so well on a
100% presorted case, because it doesn't do the necessary bookkeeping
to not throw that work away completely in certain important cases.

--
Peter Geoghegan

VMware vCenter Server
https://www.vmware.com/

On Wed, Apr 26, 2017 at 7:56 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

> On Wed, Apr 26, 2017 at 8:39 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > That appears to be wrong. I intended to make cost_sort prefer plain sort
> > over incremental sort for this dataset size. But, that appears to be not
> > always right solution. Quick sort is so fast only on presorted data.
>
> As you may know, I've often said that the precheck for sorted input
> added to our quicksort implementation by a3f0b3d is misguided. It
> sometimes throws away a ton of work if the presorted input isn't
> *perfectly* presorted. This happens when the first out of order tuple
> is towards the end of the presorted input.
>
> I think that it isn't fair to credit our qsort with doing so well on a
> 100% presorted case, because it doesn't do the necessary bookkeeping
> to not throw that work away completely in certain important cases.
>

OK, I get it. Our qsort is so fast not only on 100% presorted case.
However, that doesn't change many things in context of incremental sort.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, Apr 26, 2017 at 10:10 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> OK, I get it. Our qsort is so fast not only on 100% presorted case.
> However, that doesn't change many things in context of incremental sort.

The important point is to make any presorted test case only ~99%
presorted, so as to not give too much credit to the "high risk"
presort check optimization.

The switch to insertion sort that we left in (not the bad one removed
by a3f0b3d -- the insertion sort that actually comes from the B&M
paper) does "legitimately" make sorting faster with presorted cases.

--
Peter Geoghegan

VMware vCenter Server
https://www.vmware.com/

On Wed, Apr 26, 2017 at 8:20 PM, Peter Geoghegan <pg(at)bowt(dot)ie> wrote:

> On Wed, Apr 26, 2017 at 10:10 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > OK, I get it. Our qsort is so fast not only on 100% presorted case.
> > However, that doesn't change many things in context of incremental sort.
>
> The important point is to make any presorted test case only ~99%
> presorted, so as to not give too much credit to the "high risk"
> presort check optimization.
>
> The switch to insertion sort that we left in (not the bad one removed
> by a3f0b3d -- the insertion sort that actually comes from the B&M
> paper) does "legitimately" make sorting faster with presorted cases.

I'm still focusing on making incremental sort not slower than qsort with
presorted optimization. Independently on whether this is "high risk"
optimization or not...
However, adding more test cases is always good.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, Apr 26, 2017 at 11:39 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> But I'd like to make incremental sort not slower than quicksort in case of
> presorted data. New idea about it comes to my mind. Since cause of
> incremental sort slowness in this case is too frequent reset of tuplesort,
> then what if we would artificially put data in larger groups. Attached
> revision of patch implements this: it doesn't stop to accumulate tuples to
> tuplesort until we have MIN_GROUP_SIZE tuples.
>
> Now, incremental sort is not slower than quicksort. And this seems to be
> cool.
> However, in the LIMIT case we will pay the price of fetching some extra
> tuples from outer node. But, that doesn't seem to hurt us too much.
>
> Any thoughts?

Nice idea.

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

On Thu, Apr 27, 2017 at 5:06 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Wed, Apr 26, 2017 at 11:39 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > But I'd like to make incremental sort not slower than quicksort in case
> of
> > presorted data. New idea about it comes to my mind. Since cause of
> > incremental sort slowness in this case is too frequent reset of
> tuplesort,
> > then what if we would artificially put data in larger groups. Attached
> > revision of patch implements this: it doesn't stop to accumulate tuples
> to
> > tuplesort until we have MIN_GROUP_SIZE tuples.
> >
> > Now, incremental sort is not slower than quicksort. And this seems to be
> > cool.
> > However, in the LIMIT case we will pay the price of fetching some extra
> > tuples from outer node. But, that doesn't seem to hurt us too much.
> >
> > Any thoughts?
>
> Nice idea.

Cool.
Than I'm going to make a set of synthetic performance tests in order to
ensure that there is no regression.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, Apr 27, 2017 at 5:23 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Thu, Apr 27, 2017 at 5:06 PM, Robert Haas <robertmhaas(at)gmail(dot)com>
> wrote:
>
>> On Wed, Apr 26, 2017 at 11:39 AM, Alexander Korotkov
>> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>> > But I'd like to make incremental sort not slower than quicksort in case
>> of
>> > presorted data. New idea about it comes to my mind. Since cause of
>> > incremental sort slowness in this case is too frequent reset of
>> tuplesort,
>> > then what if we would artificially put data in larger groups. Attached
>> > revision of patch implements this: it doesn't stop to accumulate tuples
>> to
>> > tuplesort until we have MIN_GROUP_SIZE tuples.
>> >
>> > Now, incremental sort is not slower than quicksort. And this seems to
>> be
>> > cool.
>> > However, in the LIMIT case we will pay the price of fetching some extra
>> > tuples from outer node. But, that doesn't seem to hurt us too much.
>> >
>> > Any thoughts?
>>
>> Nice idea.
>
>
> Cool.
> Than I'm going to make a set of synthetic performance tests in order to
> ensure that there is no regression.
>

Next revision of patch is attached.
This revision contains one important optimization. I found that it's not
necessary to make every tuple go through prevTuple slot. It's enough to
save single sample tuple per sort group in order to compare skip columns
with it. This optimization allows to evade regression on large sort groups
which I have observed.

I'm also attaching python script (incsort_test.py) which I use for
synthetic performance benchmarking. This script runs benchmarks which are
similar to one posted by Heikki, but with some variations. These
benchmarks are aimed to check if there are cases when incremental sort is
slower than plain sort.

This script generates tables with structure described in 'tables' array.
For generation of texts, md5 function is used. For first GroupedCols
number of table columns, groups of GroupSize equal values are generated.
Then there are columns which values are just sequential. In the last column
have PreorderedFrac fraction of sequential values and rest of values are
random. Therefore, we can measure influence of presorted optimization in
qsort with various fractions of presorted data. Also there is btree index
which covers all the columns of that table.

The benchmark query select contents of generated table order by grouped
columns and by last column. Index only scan outputs tuples ordered by
grouped columns, and incremental sort have to perform sorting inside those
groups. Plain sort case is forced to also use index only scans, in order
to compare sort methods not scan methods.

Results are also attached (results.csv). Last column contains difference
between incremental and plain sort time in percents. Negative value mean
that incremental sort is faster in this case.

Incremental sort is faster in vast majority of cases. It appears to be
slower only when whose dataset is one sort group. In this case incremental
sort is useless, and it should be considered as misuse of incremental
sort. Slowdown is related to the fact that we anyway have to do extra
comparisons, unless we somehow push our comparison result into qsort itself
and save some cpu cycles (but that would be unreasonable break of
encapsulation). Thus, in such cases regression seems to be inevitable
anyway. I think we could evade this regression during query planning. If
we see that there would be only few groups, we should choose plain sort
instead of incremental sort.

Any thoughts?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, May 5, 2017 at 11:13 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> Incremental sort is faster in vast majority of cases. It appears to be
> slower only when whose dataset is one sort group. In this case incremental
> sort is useless, and it should be considered as misuse of incremental sort.
> Slowdown is related to the fact that we anyway have to do extra comparisons,
> unless we somehow push our comparison result into qsort itself and save some
> cpu cycles (but that would be unreasonable break of encapsulation). Thus,
> in such cases regression seems to be inevitable anyway. I think we could
> evade this regression during query planning. If we see that there would be
> only few groups, we should choose plain sort instead of incremental sort.

I'm sorry that I don't have time to review this in detail right now,
but it sounds like you are doing good work to file down cases where
this might cause regressions, which is great. Regarding the point in
the paragraph above, I'd say that it's OK for the planner to be
responsible for picking between Sort and Incremental Sort in some way.
It is, after all, the planner's job to decide between different
strategies for executing the same query and, of course, sometimes it
will be wrong, but that's OK as long as it's not wrong too often (or
by too much, hopefully). It may be a little difficult to get this
right, though, because I'm not sure that the information you need
actually exists (or is reliable). For example, consider the case
where we need to sort 100m rows and there are 2 groups. If 1 group
contains 1 row and the other group contains all of the rest, there is
really no point in an incremental sort. On the other hand, if each
group contains 50m rows and we can get the data presorted by the
grouping column, there might be a lot of point to an incremental sort,
because two 50m-row sorts might be a lot cheaper than one 100m sort.
More generally, it's quite easy to imagine situations where the
individual groups can be quicksorted but sorting all of the rows
requires I/O, even when the number of groups isn't that big. On the
other hand, the real sweet spot for this is probably the case where
the number of groups is very large, with many single-row groups or
many groups with just a few rows each, so if we can at least get this
to work in those cases that may be good enough. On the third hand,
when costing aggregation, I think we often underestimate the number of
groups and there might well be similar problems here.

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

On Mon, May 8, 2017 at 6:51 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Fri, May 5, 2017 at 11:13 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > Incremental sort is faster in vast majority of cases. It appears to be
> > slower only when whose dataset is one sort group. In this case
> incremental
> > sort is useless, and it should be considered as misuse of incremental
> sort.
> > Slowdown is related to the fact that we anyway have to do extra
> comparisons,
> > unless we somehow push our comparison result into qsort itself and save
> some
> > cpu cycles (but that would be unreasonable break of encapsulation).
> Thus,
> > in such cases regression seems to be inevitable anyway. I think we could
> > evade this regression during query planning. If we see that there would
> be
> > only few groups, we should choose plain sort instead of incremental sort.
>
> I'm sorry that I don't have time to review this in detail right now,
> but it sounds like you are doing good work to file down cases where
> this might cause regressions, which is great.

Thank you for paying attention to this patch!

> Regarding the point in
> the paragraph above, I'd say that it's OK for the planner to be
> responsible for picking between Sort and Incremental Sort in some way.
> It is, after all, the planner's job to decide between different
> strategies for executing the same query and, of course, sometimes it
> will be wrong, but that's OK as long as it's not wrong too often (or
> by too much, hopefully).

Right, I agree.

> It may be a little difficult to get this
> right, though, because I'm not sure that the information you need
> actually exists (or is reliable). For example, consider the case
> where we need to sort 100m rows and there are 2 groups. If 1 group
> contains 1 row and the other group contains all of the rest, there is
> really no point in an incremental sort. On the other hand, if each
> group contains 50m rows and we can get the data presorted by the
> grouping column, there might be a lot of point to an incremental sort,
> because two 50m-row sorts might be a lot cheaper than one 100m sort.
>
More generally, it's quite easy to imagine situations where the
> individual groups can be quicksorted but sorting all of the rows
> requires I/O, even when the number of groups isn't that big. On the
> other hand, the real sweet spot for this is probably the case where
> the number of groups is very large, with many single-row groups or
> many groups with just a few rows each, so if we can at least get this
> to work in those cases that may be good enough. On the third hand,
> when costing aggregation, I think we often underestimate the number of
> groups and there might well be similar problems here.

I agree with that. I need to test this patch more carefully in the case
when groups have different sizes. It's likely I need to add yet another
parameter to my testing script: groups count skew.

Patch rebased to current master is attached. I'm going to improve my
testing script and post new results.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Thu, Sep 14, 2017 at 2:48 AM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> Patch rebased to current master is attached. I'm going to improve my
> testing script and post new results.
>

New benchmarking script and results are attached. There new dataset
parameter is introduced: skew factor. Skew factor defines skew in
distribution of groups sizes.
My idea of generating is just usage of power function where power is from 0
to 1. Following formula is used to get group number for particular item
number i.
[((i / number_of_indexes) ^ power) * number_of_groups]
For example, power = 1/6 gives following distribution of groups sizes:
group number group size
0 2
1 63
2 665
3 3367
4 11529
5 31031
6 70993
7 144495
8 269297
9 468558

For convenience, instead of power itself, I use skew factor where power =
1.0 / (1.0 + skew). Therefore, with skew = 0.0, distribution of groups
sizes is uniform. Larger skew gives more skewed distribution (and that
seems to be quite intuitive). For, negative skew, group sizes are mirrored
as for corresponding positive skew. For example, skew factor = -5.0 gives
following groups sizes distribution:
group number group size
0 468558
1 269297
2 144495
3 70993
4 31031
5 11529
6 3367
7 665
8 63
9 2

Results shows that between 2172 test cases, in 2113 incremental sort gives
speedup while in 59 it causes slowdown. The following 4 test cases show
most significant slowdown (>10% of time).

Table GroupedCols GroupCount Skew PreorderedFrac
FullSortMedian IncSortMedian TimeChangePercent
int4|int4|numeric 1 100 -10 0
1.5688240528 2.0607631207 31.36
text|int8|text|int4 1 1 0 0
1.7785198689 2.1816160679 22.66
int8|int8|int4 1 10 -10 0
1.136412859 1.3166360855 15.86
numeric|text|int4|int8 2 10 -10 1
0.4403841496 0.5070910454 15.15

As you can see, 3 of this 4 test cases have skewed distribution while one
of them is related to costly location-aware comparison of text. I've no
particular idea of how to cope these slowdowns. Probably, it's OK to have
slowdown in some cases while have speedup in majority of cases (assuming
there is an option to turn off new behavior). Probably, we should teach
optimizer more about skewed distributions of groups, but that doesn't seem
feasible for me.

Any thoughts?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, Sep 16, 2017 at 2:46 AM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Thu, Sep 14, 2017 at 2:48 AM, Alexander Korotkov <
> a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
>> Patch rebased to current master is attached. I'm going to improve my
>> testing script and post new results.
>>
>
> New benchmarking script and results are attached. There new dataset
> parameter is introduced: skew factor. Skew factor defines skew in
> distribution of groups sizes.
> My idea of generating is just usage of power function where power is from
> 0 to 1. Following formula is used to get group number for particular item
> number i.
> [((i / number_of_indexes) ^ power) * number_of_groups]
> For example, power = 1/6 gives following distribution of groups sizes:
> group number group size
> 0 2
> 1 63
> 2 665
> 3 3367
> 4 11529
> 5 31031
> 6 70993
> 7 144495
> 8 269297
> 9 468558
>
> For convenience, instead of power itself, I use skew factor where power =
> 1.0 / (1.0 + skew). Therefore, with skew = 0.0, distribution of groups
> sizes is uniform. Larger skew gives more skewed distribution (and that
> seems to be quite intuitive). For, negative skew, group sizes are mirrored
> as for corresponding positive skew. For example, skew factor = -5.0 gives
> following groups sizes distribution:
> group number group size
> 0 468558
> 1 269297
> 2 144495
> 3 70993
> 4 31031
> 5 11529
> 6 3367
> 7 665
> 8 63
> 9 2
>
> Results shows that between 2172 test cases, in 2113 incremental sort gives
> speedup while in 59 it causes slowdown. The following 4 test cases show
> most significant slowdown (>10% of time).
>
> Table GroupedCols GroupCount Skew PreorderedFrac
> FullSortMedian IncSortMedian TimeChangePercent
> int4|int4|numeric 1 100 -10 0
> 1.5688240528 2.0607631207 31.36
> text|int8|text|int4 1 1 0 0
> 1.7785198689 <(778)%20519-8689> 2.1816160679 22.66
> int8|int8|int4 1 10 -10 0
> 1.136412859 1.3166360855 15.86
> numeric|text|int4|int8 2 10 -10 1
> 0.4403841496 0.5070910454 15.15
>
> As you can see, 3 of this 4 test cases have skewed distribution while one
> of them is related to costly location-aware comparison of text. I've no
> particular idea of how to cope these slowdowns. Probably, it's OK to have
> slowdown in some cases while have speedup in majority of cases (assuming
> there is an option to turn off new behavior). Probably, we should teach
> optimizer more about skewed distributions of groups, but that doesn't seem
> feasible for me.
>
> Any thoughts?
>

BTW, replacement selection sort was removed by 8b304b8b. I think it worth
to rerun benchmarks after that, because results might be changed. Will do.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, Sep 30, 2017 at 11:20 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Sat, Sep 16, 2017 at 2:46 AM, Alexander Korotkov <
> a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
>> On Thu, Sep 14, 2017 at 2:48 AM, Alexander Korotkov <
>> a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>>
>>> Patch rebased to current master is attached. I'm going to improve my
>>> testing script and post new results.
>>>
>>
>> New benchmarking script and results are attached. There new dataset
>> parameter is introduced: skew factor. Skew factor defines skew in
>> distribution of groups sizes.
>> My idea of generating is just usage of power function where power is from
>> 0 to 1. Following formula is used to get group number for particular item
>> number i.
>> [((i / number_of_indexes) ^ power) * number_of_groups]
>> For example, power = 1/6 gives following distribution of groups sizes:
>> group number group size
>> 0 2
>> 1 63
>> 2 665
>> 3 3367
>> 4 11529
>> 5 31031
>> 6 70993
>> 7 144495
>> 8 269297
>> 9 468558
>>
>> For convenience, instead of power itself, I use skew factor where power =
>> 1.0 / (1.0 + skew). Therefore, with skew = 0.0, distribution of groups
>> sizes is uniform. Larger skew gives more skewed distribution (and that
>> seems to be quite intuitive). For, negative skew, group sizes are mirrored
>> as for corresponding positive skew. For example, skew factor = -5.0 gives
>> following groups sizes distribution:
>> group number group size
>> 0 468558
>> 1 269297
>> 2 144495
>> 3 70993
>> 4 31031
>> 5 11529
>> 6 3367
>> 7 665
>> 8 63
>> 9 2
>>
>> Results shows that between 2172 test cases, in 2113 incremental sort
>> gives speedup while in 59 it causes slowdown. The following 4 test cases
>> show most significant slowdown (>10% of time).
>>
>> Table GroupedCols GroupCount Skew PreorderedFrac
>> FullSortMedian IncSortMedian TimeChangePercent
>> int4|int4|numeric 1 100 -10 0
>> 1.5688240528 2.0607631207 31.36
>> text|int8|text|int4 1 1 0 0
>> 1.7785198689 <(778)%20519-8689> 2.1816160679 22.66
>> int8|int8|int4 1 10 -10 0
>> 1.136412859 1.3166360855 15.86
>> numeric|text|int4|int8 2 10 -10 1
>> 0.4403841496 0.5070910454 15.15
>>
>> As you can see, 3 of this 4 test cases have skewed distribution while one
>> of them is related to costly location-aware comparison of text. I've no
>> particular idea of how to cope these slowdowns. Probably, it's OK to have
>> slowdown in some cases while have speedup in majority of cases (assuming
>> there is an option to turn off new behavior). Probably, we should teach
>> optimizer more about skewed distributions of groups, but that doesn't seem
>> feasible for me.
>>
>> Any thoughts?
>>
>
> BTW, replacement selection sort was removed by 8b304b8b. I think it worth
> to rerun benchmarks after that, because results might be changed. Will do.
>

I've applied patch on top of c12d570f and rerun the same benchmarks.
CSV-file with results is attached. There is no dramatical changes. There
is still minority of performance regression cases while majority of cases
has improvement.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Oct 2, 2017 at 12:37 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> I've applied patch on top of c12d570f and rerun the same benchmarks.
> CSV-file with results is attached. There is no dramatical changes. There
> is still minority of performance regression cases while majority of cases
> has improvement.

Yes, I think these results look pretty good. But are these times in
seconds? You might need to do some testing with bigger sorts.

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

On Tue, Oct 3, 2017 at 2:52 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:

> On Mon, Oct 2, 2017 at 12:37 PM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > I've applied patch on top of c12d570f and rerun the same benchmarks.
> > CSV-file with results is attached. There is no dramatical changes.
> There
> > is still minority of performance regression cases while majority of cases
> > has improvement.
>
> Yes, I think these results look pretty good. But are these times in
> seconds? You might need to do some testing with bigger sorts.

Good point. I'll rerun benchmarks with larger dataset size.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> Patch rebased to current master is attached. I'm going to improve my testing script and post new results.

I wanted to review this patch but incremental-sort-8.patch fails to apply. Can
you please rebase it again?

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at

On Tue, Nov 14, 2017 at 7:00 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Patch rebased to current master is attached. I'm going to improve my
> testing script and post new results.
>
> I wanted to review this patch but incremental-sort-8.patch fails to apply.
> Can
> you please rebase it again?
>

Sure, please find rebased patch attached.
Also, I'd like to share partial results of benchmarks with 100M of rows.
It appears that for 100M of rows it takes quite amount of time. Perhaps in
cases when there were degradation on 1M of rows, it becomes somewhat
bigger...

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Patch rebased to current master is attached. I'm going to improve my testing script and post new results.
>
> I wanted to review this patch but incremental-sort-8.patch fails to apply. Can
> you please rebase it again?

I could find the matching HEAD quite easily (9b6cb46), so following are my comments:

* cost_sort()

** "presorted_keys" missing in the prologue

** when called from label_sort_with_costsize(), 0 is passed for
"presorted_keys". However label_sort_with_costsize() can sometimes be
called on an IncrementalSort, in which case there are some "presorted
keys". See create_mergejoin_plan() for example. (IIUC this should only
make EXPLAIN inaccurate, but should not cause incorrect decisions.)

** instead of

if (!enable_incrementalsort)
presorted_keys = false;

you probably meant

if (!enable_incrementalsort)
presorted_keys = 0;

** instead of

/* Extract presorted keys as list of expressions */
foreach(l, pathkeys)
{
PathKey *key = (PathKey *)lfirst(l);
EquivalenceMember *member = (EquivalenceMember *)
lfirst(list_head(key->pk_eclass->ec_members));

you can use linitial():

/* Extract presorted keys as list of expressions */
foreach(l, pathkeys)
{
PathKey *key = (PathKey *)lfirst(l);
EquivalenceMember *member = (EquivalenceMember *)
linitial(key->pk_eclass->ec_members);

* get_cheapest_fractional_path_for_pathkeys()

The prologue says "... at least partially satisfies the given pathkeys ..."
but I see no change in the function code. In particular the use of
pathkeys_contained_in() does not allow for any kind of partial sorting.

* pathkeys_useful_for_ordering()

Extra whitespace following the comment opening string "/*":

/*
* When incremental sort is disabled, pathkeys are useful only when they

* make_sort_from_pathkeys() - the "skipCols" argument should be mentioned in
the prologue.

* create_sort_plan()

I noticed that pathkeys_common() is called, but the value of n_common_pathkeys
should already be in the path's "skipCols" field if the underlying path is
actually IncrementalSortPath.

* create_unique_plan() does not seem to make use of the incremental
sort. Shouldn't it do?

* nodeIncrementalSort.c

** These comments seem to contain typos:

"Incremental sort algorithm would sort by xfollowing groups, which have ..."

"Interate while skip cols are same as in saved tuple"

** (This is rather a pedantic comment) I think prepareSkipCols() should be
defined in front of cmpSortSkipCols().

** the MIN_GROUP_SIZE constant deserves a comment.

* ExecIncrementalSort()

** if (node->tuplesortstate == NULL)

If both branches contain the expression

node->groupsCount++;

I suggest it to be moved outside the "if" construct.

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at

On Wed, Nov 15, 2017 at 7:42 AM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> Sure, please find rebased patch attached.

+ /*
+ * Check if first "skipCols" sort values are equal.
+ */
+ static bool
+ cmpSortSkipCols(IncrementalSortState *node, TupleTableSlot *a,
+ TupleTableSlot *b)
+ {
+ int n, i;
+
+ Assert(IsA(node->ss.ps.plan, IncrementalSort));
+
+ n = ((IncrementalSort *) node->ss.ps.plan)->skipCols;
+
+ for (i = 0; i < n; i++)
+ {
+ Datum datumA, datumB, result;
+ bool isnullA, isnullB;
+ AttrNumber attno = node->skipKeys[i].attno;
+ SkipKeyData *key;
+
+ datumA = slot_getattr(a, attno, &isnullA);
+ datumB = slot_getattr(b, attno, &isnullB);
+
+ /* Special case for NULL-vs-NULL, else use standard comparison */
+ if (isnullA || isnullB)
+ {
+ if (isnullA == isnullB)
+ continue;
+ else
+ return false;
+ }
+
+ key = &node->skipKeys[i];
+
+ key->fcinfo.arg[0] = datumA;
+ key->fcinfo.arg[1] = datumB;
+
+ /* just for paranoia's sake, we reset isnull each time */
+ key->fcinfo.isnull = false;
+
+ result = FunctionCallInvoke(&key->fcinfo);
+
+ /* Check for null result, since caller is clearly not expecting one */
+ if (key->fcinfo.isnull)
+ elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
+
+ if (!DatumGetBool(result))
+ return false;
+ }
+ return true;
+ }

Is there some reason not to use ApplySortComparator for this? I think
you're missing out on lower-overhead comparators, and in any case it's
probably good code reuse, no?

Embarrassingly, I was unaware of this patch and started prototyping
exactly the same thing independently[1]. I hadn't got very far and
will now abandon that, but that's one thing I did differently. Two
other things that may be different: I had a special case for groups of
size 1 that skipped the sorting, and I only sorted on the suffix
because I didn't put tuples with different prefixes into the sorter (I
was assuming that tuplesort_reset was going to be super efficient,
though I hadn't got around to writing that). I gather that you have
determined empirically that it's better to be able to sort groups of
at least MIN_GROUP_SIZE than to be able to skip the comparisons on the
leading attributes, but why is that the case?

[1] https://github.com/macdice/postgres/commit/ab0f8aff9c4b25d5598aa6b3c630df864302f572

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

Hi!

Thank you very much for review. I really appreciate this topic gets
attention. Please, find next revision of patch in the attachment.

On Wed, Nov 15, 2017 at 7:20 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> > Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> >
> > > Patch rebased to current master is attached. I'm going to improve my
> testing script and post new results.
> >
> > I wanted to review this patch but incremental-sort-8.patch fails to
> apply. Can
> > you please rebase it again?
>
> I could find the matching HEAD quite easily (9b6cb46), so following are my
> comments:
>
> * cost_sort()
>
> ** "presorted_keys" missing in the prologue
>

Comment is added.

** when called from label_sort_with_costsize(), 0 is passed for
> "presorted_keys". However label_sort_with_costsize() can sometimes be
> called on an IncrementalSort, in which case there are some "presorted
> keys". See create_mergejoin_plan() for example. (IIUC this should only
> make EXPLAIN inaccurate, but should not cause incorrect decisions.)
>

Good catch. Fixed.

** instead of
>
> if (!enable_incrementalsort)
> presorted_keys = false;
>
> you probably meant
>
> if (!enable_incrementalsort)
> presorted_keys = 0;
>

Absolutely correct. Fixed.

> ** instead of
>
> /* Extract presorted keys as list of expressions */
> foreach(l, pathkeys)
> {
> PathKey *key = (PathKey *)lfirst(l);
> EquivalenceMember *member = (EquivalenceMember *)
> lfirst(list_head(key->pk_eclass->ec_members));
>
> you can use linitial():
>
> /* Extract presorted keys as list of expressions */
> foreach(l, pathkeys)
> {
> PathKey *key = (PathKey *)lfirst(l);
> EquivalenceMember *member = (EquivalenceMember *)
> linitial(key->pk_eclass->ec_members);
>

Sure. Fixed.

>
> * get_cheapest_fractional_path_for_pathkeys()
>
> The prologue says "... at least partially satisfies the given pathkeys ..."
> but I see no change in the function code. In particular the use of
> pathkeys_contained_in() does not allow for any kind of partial sorting.
>

Good catch. This is a part of optimization for build_minmax_path() which
existed in earlier version of patch. That optimization contained set of
arguable solutions. This is why I decided to wipe it out from the patch,
and let it wait for initial implementation to be committed.

* pathkeys_useful_for_ordering()
>
> Extra whitespace following the comment opening string "/*":
>
> /*
> * When incremental sort is disabled, pathkeys are useful only when they
>

Fixed.

> * make_sort_from_pathkeys() - the "skipCols" argument should be mentioned
> in
> the prologue.
>

Comment is added.

> * create_sort_plan()
>
> I noticed that pathkeys_common() is called, but the value of
> n_common_pathkeys
> should already be in the path's "skipCols" field if the underlying path is
> actually IncrementalSortPath.
>

Sounds like reasonable optimization. Done.

> * create_unique_plan() does not seem to make use of the incremental
> sort. Shouldn't it do?
>

It definitely should. But proper solution doesn't seem to be easy for me.
We should construct possibly useful paths before. Wherein it should be
done in agnostic manner to the order of pathkeys. I'm afraid for possible
regression in query planning. Therefore, it seems like a topic for
separate discussion. I would prefer to commit some basic implementation
first and then consider smaller patches with possible enhancement including
this one.

* nodeIncrementalSort.c
>
> ** These comments seem to contain typos:
>
> "Incremental sort algorithm would sort by xfollowing groups, which have
> ..."
>
> "Interate while skip cols are same as in saved tuple"
>

Fixed.

>
> ** (This is rather a pedantic comment) I think prepareSkipCols() should be
> defined in front of cmpSortSkipCols().
>

That's a good comment. We're trying to be as pedantic about code as we can
:)
Fixed.

** the MIN_GROUP_SIZE constant deserves a comment.
>

Sure. Explanation was added.

> * ExecIncrementalSort()
>
> ** if (node->tuplesortstate == NULL)
>
> If both branches contain the expression
>
> node->groupsCount++;
>
> I suggest it to be moved outside the "if" construct.

Done.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi!

On Mon, Nov 20, 2017 at 12:24 AM, Thomas Munro <
thomas(dot)munro(at)enterprisedb(dot)com> wrote:

> On Wed, Nov 15, 2017 at 7:42 AM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> > Sure, please find rebased patch attached.
>
> + /*
> + * Check if first "skipCols" sort values are equal.
> + */
> + static bool
> + cmpSortSkipCols(IncrementalSortState *node, TupleTableSlot *a,
> +
> TupleTableSlot *b)
> + {
> + int n, i;
> +
> + Assert(IsA(node->ss.ps.plan, IncrementalSort));
> +
> + n = ((IncrementalSort *) node->ss.ps.plan)->skipCols;
> +
> + for (i = 0; i < n; i++)
> + {
> + Datum datumA, datumB, result;
> + bool isnullA, isnullB;
> + AttrNumber attno = node->skipKeys[i].attno;
> + SkipKeyData *key;
> +
> + datumA = slot_getattr(a, attno, &isnullA);
> + datumB = slot_getattr(b, attno, &isnullB);
> +
> + /* Special case for NULL-vs-NULL, else use standard comparison */
> + if (isnullA || isnullB)
> + {
> + if (isnullA == isnullB)
> + continue;
> + else
> + return false;
> + }
> +
> + key = &node->skipKeys[i];
> +
> + key->fcinfo.arg[0] = datumA;
> + key->fcinfo.arg[1] = datumB;
> +
> + /* just for paranoia's sake, we reset isnull each time */
> + key->fcinfo.isnull = false;
> +
> + result = FunctionCallInvoke(&key->fcinfo);
> +
> + /* Check for null result, since caller is clearly not expecting
> one */
> + if (key->fcinfo.isnull)
> + elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
> +
> + if (!DatumGetBool(result))
> + return false;
> + }
> + return true;
> + }
>
> Is there some reason not to use ApplySortComparator for this? I think
> you're missing out on lower-overhead comparators, and in any case it's
> probably good code reuse, no?
>

However, for incremental sort case we don't need to know here whether A > B
or B > A. It's enough for us to know if A = B or A != B. In some cases
it's way cheaper. For instance, for texts equality check is basically
memcmp while comparison may use collation.

Embarrassingly, I was unaware of this patch and started prototyping
> exactly the same thing independently[1]. I hadn't got very far and
> will now abandon that, but that's one thing I did differently. Two
> other things that may be different: I had a special case for groups of
> size 1 that skipped the sorting, and I only sorted on the suffix
> because I didn't put tuples with different prefixes into the sorter (I
> was assuming that tuplesort_reset was going to be super efficient,
> though I hadn't got around to writing that). I gather that you have
> determined empirically that it's better to be able to sort groups of
> at least MIN_GROUP_SIZE than to be able to skip the comparisons on the
> leading attributes, but why is that the case?
>

Right. The issue that not only case of one tuple per group could cause
overhead, but few tuples (like 2 or 3) is also case of overhead. Also,
overhead is related not only to sorting. While investigate of regression
case provided by Heikki [1], I've seen extra time spent mostly in extra
copying of sample tuple and comparison with that. In order to cope this
overhead I've introduced MIN_GROUP_SIZE which allows to skip copying sample
tuples too frequently.

[1]
https://www.postgresql.org/message-id/2c59b009-61d3-9350-04ee-4b701eb93101@iki.fi

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Nov 20, 2017 at 3:34 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> Thank you very much for review. I really appreciate this topic gets
> attention. Please, find next revision of patch in the attachment.

I would really like to see this get into v11. This is an important
patch, that has fallen through the cracks far too many times.

--
Peter Geoghegan

On Tue, Nov 21, 2017 at 1:00 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> On Mon, Nov 20, 2017 at 12:24 AM, Thomas Munro
> <thomas(dot)munro(at)enterprisedb(dot)com> wrote:
>> Is there some reason not to use ApplySortComparator for this? I think
>> you're missing out on lower-overhead comparators, and in any case it's
>> probably good code reuse, no?
>
> However, for incremental sort case we don't need to know here whether A > B
> or B > A. It's enough for us to know if A = B or A != B. In some cases
> it's way cheaper. For instance, for texts equality check is basically
> memcmp while comparison may use collation.

Ah, right, of course.

>> I gather that you have
>> determined empirically that it's better to be able to sort groups of
>> at least MIN_GROUP_SIZE than to be able to skip the comparisons on the
>> leading attributes, but why is that the case?
>
> Right. The issue that not only case of one tuple per group could cause
> overhead, but few tuples (like 2 or 3) is also case of overhead. Also,
> overhead is related not only to sorting. While investigate of regression
> case provided by Heikki [1], I've seen extra time spent mostly in extra
> copying of sample tuple and comparison with that. In order to cope this
> overhead I've introduced MIN_GROUP_SIZE which allows to skip copying sample
> tuples too frequently.

I see. I wonder if there could ever be a function like
ExecMoveTuple(dst, src). Given the polymorphism involved it'd be
slightly complicated and you'd probably have a general case that just
copies the tuple to dst and clears src, but there might be a bunch of
cases where you can do something more efficient like moving a pointer
and pin ownership. I haven't really thought that through and
there may be fundamental problems with it...

If you're going to push the tuples into the sorter every time, then I
guess there are some special cases that could allow future
optimisations: (1) if you noticed that every prefix was different, you
can skip the sort operation (that is, you can use the sorter as a dumb
tuplestore and just get the tuples out in the same order you put them
in; not sure if Tuplesort supports that but it presumably could), (2)
if you noticed that every prefix was the same (that is, you have only
one prefix/group in the sorter) then you could sort only on the suffix
(that is, you could somehow tell Tuplesort to ignore the leading
columns), (3) as a more complicated optimisation for intermediate
group sizes 1 < n < MIN_GROUP_SIZE, you could somehow number the
groups with an integer that increments whenever you see the prefix
change, and somehow tell tuplesort.c to use that instead of the
leading columns. Ok, that last one is probably hard but the first two
might be easier...

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

Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> Antonin Houska <ah(at)cybertec(dot)at> wrote:

> > * ExecIncrementalSort()
> >
> > ** if (node->tuplesortstate == NULL)
> >
> > If both branches contain the expression
> >
> > node->groupsCount++;
> >
> > I suggest it to be moved outside the "if" construct.
>
> Done.

One more comment on this: I wonder if the field isn't incremented too
early. It seems to me that the value can end up non-zero if the input set is
to be empty (not sure if it can happen in practice).

And finally one question about regression tests: what's the purpose of the
changes in contrib/postgres_fdw/sql/postgres_fdw.sql ? I see no
IncrementalSort node in the output.

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at

On Mon, Mar 20, 2017 at 6:33 PM, Alexander Korotkov
<a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> Thank you for the report.
> Please, find rebased patch in the attachment.

This patch cannot be applied. Please provide a rebased version. I am
moving it to next CF with waiting on author as status.
--
Michael

On Wed, Nov 22, 2017 at 1:22 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> > > * ExecIncrementalSort()
> > >
> > > ** if (node->tuplesortstate == NULL)
> > >
> > > If both branches contain the expression
> > >
> > > node->groupsCount++;
> > >
> > > I suggest it to be moved outside the "if" construct.
> >
> > Done.
>
> One more comment on this: I wonder if the field isn't incremented too
> early. It seems to me that the value can end up non-zero if the input set
> is
> to be empty (not sure if it can happen in practice).
>

That happens in practice. On empty input set, incremental sort would count
exactly one group.

# create table t (x int, y int);
CREATE TABLE
# create index t_x_idx on t (x);
CREATE INDEX
# set enable_seqscan = off;
SET
# explain (analyze, buffers) select * from t order by x, y;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
Incremental Sort (cost=0.74..161.14 rows=2260 width=8) (actual
time=0.024..0.024 rows=0 loops=1)
Sort Key: x, y
Presorted Key: x
Sort Method: quicksort Memory: 25kB
Sort Groups: 1
Buffers: shared hit=1
-> Index Scan using t_x_idx on t (cost=0.15..78.06 rows=2260 width=8)
(actual time=0.011..0.011 rows=0 loops=1)
Buffers: shared hit=1
Planning time: 0.088 ms
Execution time: 0.066 ms
(10 rows)

But from prospective of how code works, it's really 1 group. Tuple sort
was defined, inserted no tuples, then sorted and got no tuples out of
there. So, I'm not sure if it's really incorrect...

And finally one question about regression tests: what's the purpose of the
> changes in contrib/postgres_fdw/sql/postgres_fdw.sql ? I see no
> IncrementalSort node in the output.

But there is IncrementalSort node on the remote side.
Let's see what happens. Idea of "CROSS JOIN, not pushed down" test is that
cross join with ORDER BY LIMIT is not beneficial to push down, because
LIMIT is not pushed down and remote side wouldn't be able to use top-N
heapsort. But if remote side has incremental sort then it can be used, and
fetching first 110 rows is cheap. Let's see plan of original "CROSS JOIN,
not pushed down" test with incremental sort.

# EXPLAIN (ANALYZE, VERBOSE) SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2
t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;

QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=160.32..161.31 rows=10 width=46) (actual time=1.918..1.921
rows=10 loops=1)
Output: t1.c3, t2.c3, t1.c1, t2.c1
-> Foreign Scan (cost=150.47..66711.06 rows=675684 width=46) (actual
time=1.684..1.911 rows=110 loops=1)
Output: t1.c3, t2.c3, t1.c1, t2.c1
Relations: (public.ft1 t1) INNER JOIN (public.ft2 t2)
Remote SQL: SELECT r1.c3, r1."C 1", r2.c3, r2."C 1" FROM ("S 1"."T
1" r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS
LAST, r2."C 1" ASC NULLS LAST
Planning time: 1.370 ms
Execution time: 2.068 ms
(8 rows)

And "remote SQL" has following execution plan. This is plan of full
execution while FDW is fetching only first 110 rows out of there.

# EXPLAIN ANALYZE SELECT r1.c3, r1."C 1", r2.c3, r2."C 1" FROM ("S 1"."T 1"
r1 INNER JOIN "S 1"."T 1" r2 ON (TRUE)) ORDER BY r1."C 1" ASC NULLS LAST,
r2."C 1" ASC NULLS LAST;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------
Incremental Sort (cost=50.47..53097.38 rows=675684 width=34) (actual
time=1.883..747.694 rows=675684 loops=1)
Sort Key: r1."C 1", r2."C 1"
Presorted Key: r1."C 1"
Sort Method: quicksort Memory: 114kB
Sort Groups: 822
-> Nested Loop (cost=0.28..8543.25 rows=675684 width=34) (actual
time=0.027..144.070 rows=675684 loops=1)
-> Index Scan using t1_pkey on "T 1" r1 (cost=0.28..73.93
rows=822 width=17) (actual time=0.015..0.537 rows=822 loops=1)
-> Materialize (cost=0.00..25.33 rows=822 width=17) (actual
time=0.000..0.053 rows=822 loops=822)
-> Seq Scan on "T 1" r2 (cost=0.00..21.22 rows=822
width=17) (actual time=0.007..0.257 rows=822 loops=1)
Planning time: 0.109 ms
Execution time: 785.400 ms
(11 rows)

Thus, with incremental sort this test doesn't do what it was designed to
do. Changing ORDER BY from t1.c1, t2.c1 to t1.c3, t2.c3 fixes this
problem, because there is no index on c3. Query and result are slightly
different, but it serves original design.

Please, find rebased patch attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Wed, Nov 22, 2017 at 1:22 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> > > * ExecIncrementalSort()
> > >
> > > ** if (node->tuplesortstate == NULL)
> > >
> > > If both branches contain the expression
> > >
> > > node->groupsCount++;
> > >
> > > I suggest it to be moved outside the "if" construct.
> >
> > Done.
>
> One more comment on this: I wonder if the field isn't incremented too
> early. It seems to me that the value can end up non-zero if the input set is
> to be empty (not sure if it can happen in practice).
>
> That happens in practice. On empty input set, incremental sort would count exactly one group.
>
> # create table t (x int, y int);
> CREATE TABLE
> # create index t_x_idx on t (x);
> CREATE INDEX
> # set enable_seqscan = off;
> SET
> # explain (analyze, buffers) select * from t order by x, y;
> QUERY PLAN
> ---------------------------------------------------------------------------------------------------------------------
> Incremental Sort (cost=0.74..161.14 rows=2260 width=8) (actual time=0.024..0.024 rows=0 loops=1)
> Sort Key: x, y
> Presorted Key: x
> Sort Method: quicksort Memory: 25kB
> Sort Groups: 1
> Buffers: shared hit=1
> -> Index Scan using t_x_idx on t (cost=0.15..78.06 rows=2260 width=8) (actual time=0.011..0.011 rows=0 loops=1)
> Buffers: shared hit=1
> Planning time: 0.088 ms
> Execution time: 0.066 ms
> (10 rows)
> But from prospective of how code works, it's really 1 group. Tuple sort was defined, inserted no tuples, then sorted and got no tuples out of there. So, I'm not sure if it's really incorrect...

I expected the number of groups actually that actually appear in the output,
you consider it the number of groups started. I can't find similar case
elsewhere in the code (e.g. Agg node does not report this kind of
information), so I have no clue. Someone else will have to decide.

>
> But there is IncrementalSort node on the remote side.
> Let's see what happens. Idea of "CROSS JOIN, not pushed down" test is that cross join with ORDER BY LIMIT is not beneficial to push down, because LIMIT is not pushed down and remote side wouldn't be able to use top-N heapsort. But if remote side has incremental sort then it can be
> used, and fetching first 110 rows is cheap. Let's see plan of original "CROSS JOIN, not pushed down" test with incremental sort.
>
> # EXPLAIN (ANALYZE, VERBOSE) SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;

ok, understood, thanks. Perhaps it's worth a comment in the test script.

I'm afraid I still see a problem. The diff removes a query that (although a
bit different from the one above) lets the CROSS JOIN to be pushed down and
does introduce the IncrementalSort in the remote database. This query is
replaced with one that does not allow for the join push down.

*** a/contrib/postgres_fdw/sql/postgres_fdw.sql
--- b/contrib/postgres_fdw/sql/postgres_fdw.sql
*************** SELECT t1.c1 FROM ft1 t1 WHERE NOT EXIST
*** 510,517 ****
SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
-- CROSS JOIN, not pushed down
EXPLAIN (VERBOSE, COSTS OFF)
! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
-- different server, not pushed down. No result expected.
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
--- 510,517 ----
SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
-- CROSS JOIN, not pushed down
EXPLAIN (VERBOSE, COSTS OFF)
! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3 OFFSET 100 LIMIT 10;
! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3 OFFSET 100 LIMIT 10;
-- different server, not pushed down. No result expected.
EXPLAIN (VERBOSE, COSTS OFF)
SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;

Shouldn't the test contain *both* cases?

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at

On Wed, Nov 22, 2017 at 12:01 AM, Thomas Munro <
thomas(dot)munro(at)enterprisedb(dot)com> wrote:

> >> I gather that you have
> >> determined empirically that it's better to be able to sort groups of
> >> at least MIN_GROUP_SIZE than to be able to skip the comparisons on the
> >> leading attributes, but why is that the case?
> >
> > Right. The issue that not only case of one tuple per group could cause
> > overhead, but few tuples (like 2 or 3) is also case of overhead. Also,
> > overhead is related not only to sorting. While investigate of regression
> > case provided by Heikki [1], I've seen extra time spent mostly in extra
> > copying of sample tuple and comparison with that. In order to cope this
> > overhead I've introduced MIN_GROUP_SIZE which allows to skip copying
> sample
> > tuples too frequently.
>
> I see. I wonder if there could ever be a function like
> ExecMoveTuple(dst, src). Given the polymorphism involved it'd be
> slightly complicated and you'd probably have a general case that just
> copies the tuple to dst and clears src, but there might be a bunch of
> cases where you can do something more efficient like moving a pointer
> and pin ownership. I haven't really thought that through and
> there may be fundamental problems with it...
>

ExecMoveTuple(dst, src) would be good. But, it would be hard to implement
"moving a pointer and pin ownership" principle in our current
infrastructure. It's because source and destination can have different
memory contexts. AFAICS, we can't just move memory area between memory
contexts: we have to allocate new area, then memcpy, and then deallocate
old area.

> If you're going to push the tuples into the sorter every time, then I
> guess there are some special cases that could allow future
> optimisations: (1) if you noticed that every prefix was different, you
> can skip the sort operation (that is, you can use the sorter as a dumb
> tuplestore and just get the tuples out in the same order you put them
> in; not sure if Tuplesort supports that but it presumably could),

In order to notice that every prefix is different, I have to compare every
prefix. But that may introduce an overhead. So, there reason why I
introduced MIN_GROUP_SIZE is exactly to not compare every prefix...

> (2)
> if you noticed that every prefix was the same (that is, you have only
> one prefix/group in the sorter) then you could sort only on the suffix
> (that is, you could somehow tell Tuplesort to ignore the leading
> columns),

Yes, I did so before. But again, after introducing MIN_GROUP_SIZE, I
missed knowledge whether all the prefixes were the same or different. This
is why, I've to sort by full column list for now...

(3) as a more complicated optimisation for intermediate
> group sizes 1 < n < MIN_GROUP_SIZE, you could somehow number the
> groups with an integer that increments whenever you see the prefix
> change, and somehow tell tuplesort.c to use that instead of the
> leading columns.

That is interesting idea. The reason we have an overhead in comparison
with plain sort is that we do extra comparison (and copying), but knowledge
of this comparison result is lost for sorting itself. Thus, sorting can
"reuse" prefix comparison, and overhead would be lower. But the problem is
that we have to reformat tuples before putting them into tuplesort. I
wonder if tuple reformatting could eat potential performance win...

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi!

On Fri, Dec 1, 2017 at 11:39 AM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> I expected the number of groups actually that actually appear in the
> output,
> you consider it the number of groups started. I can't find similar case
> elsewhere in the code (e.g. Agg node does not report this kind of
> information), so I have no clue. Someone else will have to decide.
>

OK.

> But there is IncrementalSort node on the remote side.
> > Let's see what happens. Idea of "CROSS JOIN, not pushed down" test is
> that cross join with ORDER BY LIMIT is not beneficial to push down, because
> LIMIT is not pushed down and remote side wouldn't be able to use top-N
> heapsort. But if remote side has incremental sort then it can be
> > used, and fetching first 110 rows is cheap. Let's see plan of original
> "CROSS JOIN, not pushed down" test with incremental sort.
> >
> > # EXPLAIN (ANALYZE, VERBOSE) SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN
> ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET 100 LIMIT 10;
>
> ok, understood, thanks. Perhaps it's worth a comment in the test script.
>
> I'm afraid I still see a problem. The diff removes a query that (although a
> bit different from the one above) lets the CROSS JOIN to be pushed down and
> does introduce the IncrementalSort in the remote database. This query is
> replaced with one that does not allow for the join push down.
>
> *** a/contrib/postgres_fdw/sql/postgres_fdw.sql
> --- b/contrib/postgres_fdw/sql/postgres_fdw.sql
> *************** SELECT t1.c1 FROM ft1 t1 WHERE NOT EXIST
> *** 510,517 ****
> SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE
> t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
> -- CROSS JOIN, not pushed down
> EXPLAIN (VERBOSE, COSTS OFF)
> ! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1
> OFFSET 100 LIMIT 10;
> ! SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1
> OFFSET 100 LIMIT 10;
> -- different server, not pushed down. No result expected.
> EXPLAIN (VERBOSE, COSTS OFF)
> SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY
> t1.c1, t2.c1 OFFSET 100 LIMIT 10;
> --- 510,517 ----
> SELECT t1.c1 FROM ft1 t1 WHERE NOT EXISTS (SELECT 1 FROM ft2 t2 WHERE
> t1.c1 = t2.c2) ORDER BY t1.c1 OFFSET 100 LIMIT 10;
> -- CROSS JOIN, not pushed down
> EXPLAIN (VERBOSE, COSTS OFF)
> ! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3
> OFFSET 100 LIMIT 10;
> ! SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3
> OFFSET 100 LIMIT 10;
> -- different server, not pushed down. No result expected.
> EXPLAIN (VERBOSE, COSTS OFF)
> SELECT t1.c1, t2.c1 FROM ft5 t1 JOIN ft6 t2 ON (t1.c1 = t2.c1) ORDER BY
> t1.c1, t2.c1 OFFSET 100 LIMIT 10;
>
> Shouldn't the test contain *both* cases?

Thank you for pointing that. Sure, both cases are better. I've added
second case as well as comments. Patch is attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, Dec 8, 2017 at 4:06 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> Thank you for pointing that. Sure, both cases are better. I've added
> second case as well as comments. Patch is attached.
>

I just found that patch apply is failed according to commitfest.cputube.org.
Please, find rebased patch attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hello Alexander,

On Thu, January 4, 2018 4:36 pm, Alexander Korotkov wrote:
> On Fri, Dec 8, 2017 at 4:06 PM, Alexander Korotkov <
> a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
>> Thank you for pointing that. Sure, both cases are better. I've added
>> second case as well as comments. Patch is attached.

I had a quick look, this isn't a full review, but a few things struck me
on a read through the diff:

There are quite a few places where lines are broken like so:

+ ExecIncrementalSortInitializeWorker((IncrementalSortState *) planstate,
+ pwcxt);
Or like this:

+ result = (PlanState *) ExecInitIncrementalSort(
+ (IncrementalSort *) node, estate, eflags);

e.g. a param is on the next line, but aligned to the very same place where
it would be w/o the linebreak. Or is this just some sort of artefact
because I viewed the diff with tabspacing = 8?

I'd fix the grammar here:

+ * Incremental sort is specially optimized kind of multikey sort when
+ * input is already presorted by prefix of required keys list.

Like so:

"Incremental sort is a specially optimized kind of multikey sort used when
the input is already presorted by a prefix of the required keys list."

+ * Consider following example. We have input tuples consisting from

"Consider the following example: We have ..."

+ * In incremental sort case we also have to cost to detect sort groups.

"we also have to cost the detection of sort groups."

"+ * It turns out into extra copy and comparison for each tuple."

"This turns out to be one extra copy and comparison per tuple."

+ "Portions Copyright (c) 1996-2017"

Should probably be 2018 now - time flies fast :)

return_value = _readMaterial();
else if (MATCH("SORT", 4))
return_value = _readSort();
+ else if (MATCH("INCREMENTALSORT", 7))
+ return_value = _readIncrementalSort();
else if (MATCH("GROUP", 5))
return_value = _readGroup();

I think the ", 7" here is left-over from when it was named "INCSORT", and
it should be MATCH("INCREMENTALSORT", 15)), shouldn't it?

+ space, fase when it's value for in-memory

typo: "space, false when ..."

+ bool cmp;
+ cmp = cmpSortSkipCols(node, node->sampleSlot, slot);
+
+ if (cmp)

In the above, the variable cmp could be optimized away with:

+ if (cmpSortSkipCols(node, node->sampleSlot, slot))

(not sure if modern compilers won't do this, anway, though)

+typedef struct IncrementalSortState
+{
+ ScanState ss; /* its first field is NodeTag */
+ bool bounded; /* is the result set
bounded? */
+ int64 bound; /* if bounded, how many
tuples are needed */

If I'm not wrong, the layout of the struct will include quite a bit of
padding on 64 bit due to the mixing of bool and int64, maybe it would be
better to sort the fields differently, e.g. pack 4 or 8 bools together?
Not sure if that makes much of a difference, though.

That's all for now :)

Thank you for your work,

Tels

Hi!

On Fri, Jan 5, 2018 at 2:21 AM, Tels <nospam-pg-abuse(at)bloodgate(dot)com> wrote:

> On Thu, January 4, 2018 4:36 pm, Alexander Korotkov wrote:
> > On Fri, Dec 8, 2017 at 4:06 PM, Alexander Korotkov <
> > a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> >
> >> Thank you for pointing that. Sure, both cases are better. I've added
> >> second case as well as comments. Patch is attached.
>
> I had a quick look, this isn't a full review, but a few things struck me
> on a read through the diff:
>
> There are quite a few places where lines are broken like so:
>
> + ExecIncrementalSortInitializeWorker((IncrementalSortState
> *) planstate,
> +
> pwcxt);
>

It's quite common practice to align second argument to the same position as
first argument. See other lines nearby.

> Or like this:
>
> + result = (PlanState *) ExecInitIncrementalSort(
> +
> (IncrementalSort *) node, estate, eflags);
>

It was probably not so good idea to insert line break before first
argument. Fixed.

>
> e.g. a param is on the next line, but aligned to the very same place where
> it would be w/o the linebreak. Or is this just some sort of artefact
> because I viewed the diff with tabspacing = 8?
>
> I'd fix the grammar here:
>
> + * Incremental sort is specially optimized kind of multikey
> sort when
> + * input is already presorted by prefix of required keys list.
>
> Like so:
>
> "Incremental sort is a specially optimized kind of multikey sort used when
> the input is already presorted by a prefix of the required keys list."
>
> + * Consider following example. We have input tuples
> consisting from
>
> "Consider the following example: We have ..."
>
> + * In incremental sort case we also have to cost to detect
> sort groups.
>
> "we also have to cost the detection of sort groups."
>
> "+ * It turns out into extra copy and comparison for each
> tuple."
>
> "This turns out to be one extra copy and comparison per tuple."
>

Many thanks for noticing these. Fixed.

> + "Portions Copyright (c) 1996-2017"
>
> Should probably be 2018 now - time flies fast :)
>

Right. Happy New Year! :)

> return_value = _readMaterial();
> else if (MATCH("SORT", 4))
> return_value = _readSort();
> + else if (MATCH("INCREMENTALSORT", 7))
> + return_value = _readIncrementalSort();
> else if (MATCH("GROUP", 5))
> return_value = _readGroup();
>
> I think the ", 7" here is left-over from when it was named "INCSORT", and
> it should be MATCH("INCREMENTALSORT", 15)), shouldn't it?
>

Good catch, thank you!

>
> + space,
> fase when it's value for in-memory
>
> typo: "space, false when ..."
>

Right. Fixed.

> + bool cmp;
> + cmp = cmpSortSkipCols(node, node->sampleSlot,
> slot);
> +
> + if (cmp)
>
> In the above, the variable cmp could be optimized away with:
>
> + if (cmpSortSkipCols(node, node->sampleSlot, slot))
>

Right. This comes from time when there was more complicated code which
have to use the cmp variable multiple times.

(not sure if modern compilers won't do this, anway, though)
>

Anyway, it's code simplification which is good regardless whether compilers
able to do it themselves or not.

+typedef struct IncrementalSortState
> +{
> + ScanState ss; /* its first field
> is NodeTag */
> + bool bounded; /* is the result set
> bounded? */
> + int64 bound; /* if bounded, how many
> tuples are needed */
>
> If I'm not wrong, the layout of the struct will include quite a bit of
> padding on 64 bit due to the mixing of bool and int64, maybe it would be
> better to sort the fields differently, e.g. pack 4 or 8 bools together?
> Not sure if that makes much of a difference, though.
>

I'd like to leave common members between of SortState and
IncrementalSortState to be ordered the same way.
Thus, I think that if we're going to reorder then we should do this in both
data structures.
But I'm not sure it worth considering, because these data structures are
very unlikely be the source of significant memory consumption...

That's all for now :)
>

Great, thank you for review.

BTW, I also fixed documentation markup (regarding migration to xml).

Rebased patch is attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> Antonin Houska <ah(at)cybertec(dot)at> wrote:

> > Shouldn't the test contain *both* cases?

> Thank you for pointing that. Sure, both cases are better. I've added second case as well as comments. Patch is attached.

I'm fine with the tests now but have a minor comment on this comment:

-- CROSS JOIN, not pushed down, because we don't push down LIMIT and remote side
-- can't perform top-N sort like local side can.

I think the note on LIMIT push-down makes the comment less clear because
there's no difference in processing the LIMIT: EXPLAIN shows that both

SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1 OFFSET
100 LIMIT 10;

and

SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3 OFFSET
100 LIMIT 10;

evaluate the LIMIT clause only locally.

What I consider the important difference is that the 2nd case does not
generate the appropriate input for remote incremental sort (while incremental
sort tends to be very cheap). Therefore it's cheaper to do no remote sort at
all and perform the top-N sort locally than to do a regular (non-incremental)
remote sort.

I have no other questions about this patch. I expect the CFM to set the status
to "ready for committer" as soon as the other reviewers confirm they're happy
about the patch status.

--
Antonin Houska
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt
Web: http://www.postgresql-support.de, http://www.cybertec.at

On Mon, Jan 8, 2018 at 2:29 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
>
> > Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> > > Shouldn't the test contain *both* cases?
>
> > Thank you for pointing that. Sure, both cases are better. I've added
> second case as well as comments. Patch is attached.
>
> I'm fine with the tests now but have a minor comment on this comment:
>
> -- CROSS JOIN, not pushed down, because we don't push down LIMIT and
> remote side
> -- can't perform top-N sort like local side can.
>
> I think the note on LIMIT push-down makes the comment less clear because
> there's no difference in processing the LIMIT: EXPLAIN shows that both
>
> SELECT t1.c1, t2.c1 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c1, t2.c1
> OFFSET
> 100 LIMIT 10;
>
> and
>
> SELECT t1.c3, t2.c3 FROM ft1 t1 CROSS JOIN ft2 t2 ORDER BY t1.c3, t2.c3
> OFFSET
> 100 LIMIT 10;
>
> evaluate the LIMIT clause only locally.
>
> What I consider the important difference is that the 2nd case does not
> generate the appropriate input for remote incremental sort (while
> incremental
> sort tends to be very cheap). Therefore it's cheaper to do no remote sort
> at
> all and perform the top-N sort locally than to do a regular
> (non-incremental)
> remote sort.
>

Agree, these comments are not clear enough. I've rewritten comments: they
became much
more wordy, but now they look clearer for me. Also I've swapped the
queries order, for me
it seems to easier for understanding.

> I have no other questions about this patch. I expect the CFM to set the
> status
> to "ready for committer" as soon as the other reviewers confirm they're
> happy
> about the patch status.

Good, thank you. Let's see what other reviewers will say.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Mon, Jan 8, 2018 at 10:17 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> I have no other questions about this patch. I expect the CFM to set the
>> status
>> to "ready for committer" as soon as the other reviewers confirm they're
>> happy
>> about the patch status.
>
>
> Good, thank you. Let's see what other reviewers will say.
>

Rebased patch is attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi,

I have started reviewing the patch and doing some testing, and I have
pretty quickly ran into a segfault. Attached is a simple reproducer and
an backtrace. AFAICS the bug seems to be somewhere in the tuplesort
changes, likely resetting a memory context too soon or something like
that. I haven't investigated it further, but it matches my hunch that
tuplesort is likely where the bugs will be.

Otherwise the patch seems fairly complete. A couple of minor things that
I noticed while eyeballing the changes in a diff editor.

1) On a couple of places the new code has this comment

/* even when not parallel-aware */

while all the immediately preceding blocks use

/* even when not parallel-aware, for EXPLAIN ANALYZE */

I suggest using the same comment, otherwise it kinda suggests it's not
because of EXPLAIN ANALYZE.

2) I think the purpose of sampleSlot should be explicitly documented
(and I'm not sure "sample" is a good term here, as is suggest some sort
of sampling (for example nodeAgg uses grp_firstTuple).

3) skipCols/SkipKeyData seems a bit strange too, I think. I'd use
PresortedKeyData or something like that.

4) In cmpSortSkipCols, when checking if the columns changed, the patch
does this:

n = ((IncrementalSort *) node->ss.ps.plan)->skipCols;

for (i = 0; i < n; i++)
{
... check i-th key ...
}

My hunch is that checking the keys from the last one, i.e.

for (i = (n-1); i >= 0; i--)
{
....
}

would be faster. The reasoning is that with "ORDER BY a,b" the column
"b" changes more often. But I've been unable to test this because of the
segfault crashes.

5) The changes from

if (pathkeys_contained_in(...))

to

n = pathkeys_common(pathkeys, subpath->pathkeys);

if (n == 0)

seem rather inconvenient to me, as it makes the code unnecessarily
verbose. I wonder if there's a better way to deal with this.

regards

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

Hi!

Thank you for reviewing this patch!
Revised version is attached.

On Mon, Mar 5, 2018 at 1:19 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> I have started reviewing the patch and doing some testing, and I have
> pretty quickly ran into a segfault. Attached is a simple reproducer and
> an backtrace. AFAICS the bug seems to be somewhere in the tuplesort
> changes, likely resetting a memory context too soon or something like
> that. I haven't investigated it further, but it matches my hunch that
> tuplesort is likely where the bugs will be.
>

Right. Incremental sort patch introduces maincontext of memory which
is persistent between incremental sort groups. But mergeruns()
reallocates memtuples in sortcontext which is cleared by tuplesort_reset().
Fixed in the revised patch.

Otherwise the patch seems fairly complete. A couple of minor things that
> I noticed while eyeballing the changes in a diff editor.
>
>
> 1) On a couple of places the new code has this comment
>
> /* even when not parallel-aware */
>
> while all the immediately preceding blocks use
>
> /* even when not parallel-aware, for EXPLAIN ANALYZE */
>
> I suggest using the same comment, otherwise it kinda suggests it's not
> because of EXPLAIN ANALYZE.
>

Right, fixed. I also found that incremental sort shoudn't support
DSM reinitialization similarly to regular sort. Fixes in the revised patch.

2) I think the purpose of sampleSlot should be explicitly documented
> (and I'm not sure "sample" is a good term here, as is suggest some sort
> of sampling (for example nodeAgg uses grp_firstTuple).
>

Yes, "sample" isn't a good term here. However, "first" isn't really
correct,
because we can skip some tuples from beginning of the group in
order to not form groups too frequently. I'd rather name it "pivot" tuple
slot.

> 3) skipCols/SkipKeyData seems a bit strange too, I think. I'd use
> PresortedKeyData or something like that.
>

Good point, renamed.

4) In cmpSortSkipCols, when checking if the columns changed, the patch
> does this:
>
> n = ((IncrementalSort *) node->ss.ps.plan)->skipCols;
>
> for (i = 0; i < n; i++)
> {
> ... check i-th key ...
> }
>
> My hunch is that checking the keys from the last one, i.e.
>
> for (i = (n-1); i >= 0; i--)
> {
> ....
> }
>
> would be faster. The reasoning is that with "ORDER BY a,b" the column
> "b" changes more often. But I've been unable to test this because of the
> segfault crashes.
>

Agreed.

5) The changes from
>
> if (pathkeys_contained_in(...))
>
> to
>
> n = pathkeys_common(pathkeys, subpath->pathkeys);
>
>
> if (n == 0)
>
> seem rather inconvenient to me, as it makes the code unnecessarily
> verbose. I wonder if there's a better way to deal with this.
>

I would rather say, that it changes from

if (pathkeys_contained_in(...))

to

n = pathkeys_common(pathkeys, subpath->pathkeys);

if (n == list_length(pathkeys))

I've introduced pathkeys_common_contained_in() which returns the same
result as pathkeys_contained_in(), but sets number of common pathkeys
to the last argument. It simplifies code a little bit. The name, probably,
could be improved.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 03/05/2018 11:07 PM, Alexander Korotkov wrote:
> Hi!
>
> Thank you for reviewing this patch!
> Revised version is attached.
>

OK, the revised patch works fine - I've done a lot of testing and
benchmarking, and not a single segfault or any other crash.

Regarding the benchmarks, I generally used queries of the form

SELECT * FROM (SELECT * FROM t ORDER BY a) foo ORDER BY a,b

with the first sort done in various ways:

* regular Sort node
* indexes with Index Scan
* indexes with Index Only Scan

and all these three options with and without LIMIT (the limit was set to
1% of the source table).

I've also varied parallelism (max_parallel_workers_per_gather was set to
either 0 or 2), work_mem (from 4MB to 256MB) and data set size (tables
from 1000 rows to 10M rows).

All of this may seem like an overkill, but I've found a couple of
regressions thanks to that.

The full scripts and results are available here:

https://github.com/tvondra/incremental-sort-tests

The queries actually executed are a bit more complicated, to eliminate
overhead due to data transfer to client etc. The same approach was used
in the other sorting benchmarks we've done in the past.

I'm attaching results for two scales - 10k and 10M rows, preprocessed
into .ods format. I haven't looked at the other scales yet, but I don't
expect any surprises there.

Each .ods file contains raw data for one of the tests (matching the .sh
script filename), pivot table, and comparison of durations with and
without the incremental sort.

In general, I think the results look pretty impressive. Almost all the
comparisons are green, which means "faster than master" - usually by
tens of percent (without limit), or by up to ~95% (with LIMIT).

There are a couple of regressions in two cases sort-indexes and
sort-indexes-ios.

Oh the small dataset this seems to be related to the number of groups
(essentially, number of distinct values in a column). My assumption is
that there is some additional overhead when "switching" between the
groups, and with many groups it's significant enough to affect results
on these tiny tables (where master only takes ~3ms to do the sort). The
slowdown seems to be

On the large data set it seems to be somehow related to both work_mem
and number of groups, but I didn't have time to investigate that yet
(there are explain analyze plans in the results, so feel free to look).

In general, I think this looks really nice. It's certainly awesome with
the LIMIT case, as it allows us to leverage indexes on a subset of the
ORDER BY columns.

Now, there's a caveat in those tests - the data set is synthetic and
perfectly random, i.e. all groups equally likely, no correlations or
anything like that.

I wonder what is the "worst case" scenario, i.e. how to construct a data
set with particularly bad behavior of the incremental sort.

regards

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

On Thu, Mar 8, 2018 at 2:49 AM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> OK, the revised patch works fine - I've done a lot of testing and
> benchmarking, and not a single segfault or any other crash.
>
> Regarding the benchmarks, I generally used queries of the form
>
> SELECT * FROM (SELECT * FROM t ORDER BY a) foo ORDER BY a,b
>
> with the first sort done in various ways:
>
> * regular Sort node
> * indexes with Index Scan
> * indexes with Index Only Scan
>
> and all these three options with and without LIMIT (the limit was set to
> 1% of the source table).
>
> I've also varied parallelism (max_parallel_workers_per_gather was set to
> either 0 or 2), work_mem (from 4MB to 256MB) and data set size (tables
> from 1000 rows to 10M rows).
>
> All of this may seem like an overkill, but I've found a couple of
> regressions thanks to that.
>
> The full scripts and results are available here:
>
> https://github.com/tvondra/incremental-sort-tests
>
> The queries actually executed are a bit more complicated, to eliminate
> overhead due to data transfer to client etc. The same approach was used
> in the other sorting benchmarks we've done in the past.
>
> I'm attaching results for two scales - 10k and 10M rows, preprocessed
> into .ods format. I haven't looked at the other scales yet, but I don't
> expect any surprises there.
>
> Each .ods file contains raw data for one of the tests (matching the .sh
> script filename), pivot table, and comparison of durations with and
> without the incremental sort.
>
> In general, I think the results look pretty impressive. Almost all the
> comparisons are green, which means "faster than master" - usually by
> tens of percent (without limit), or by up to ~95% (with LIMIT).
>
> There are a couple of regressions in two cases sort-indexes and
> sort-indexes-ios.
>
> Oh the small dataset this seems to be related to the number of groups
> (essentially, number of distinct values in a column). My assumption is
> that there is some additional overhead when "switching" between the
> groups, and with many groups it's significant enough to affect results
> on these tiny tables (where master only takes ~3ms to do the sort). The
> slowdown seems to be
>
> On the large data set it seems to be somehow related to both work_mem
> and number of groups, but I didn't have time to investigate that yet
> (there are explain analyze plans in the results, so feel free to look).
>
> In general, I think this looks really nice. It's certainly awesome with
> the LIMIT case, as it allows us to leverage indexes on a subset of the
> ORDER BY columns.
>

Thank you very much for testing and benchmarking. I'll investigate
the regressions you found.

> Now, there's a caveat in those tests - the data set is synthetic and
> perfectly random, i.e. all groups equally likely, no correlations or
> anything like that.
>
> I wonder what is the "worst case" scenario, i.e. how to construct a data
> set with particularly bad behavior of the incremental sort.

I think that depends on the reason of bad behavior of incremental sort.
For example, our quick sort implementation behaves very good on
presorted data. But, incremental sort appears to be not so good in
this case as Heikki showed upthread. That prompted me to test
presorted datasets (which appeared to be "worst case") more intensively.
But I suspect that regressions you found have another reason, and
correspondingly "worst case" would be also different.
When I'll investigate the reason of regressions, I'll try to construct
"worst case" as well.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Sat, Mar 10, 2018 at 6:42 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Thu, Mar 8, 2018 at 2:49 AM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com
> > wrote:
> Thank you very much for testing and benchmarking. I'll investigate
> the regressions you found.
>
>
>> Now, there's a caveat in those tests - the data set is synthetic and
>> perfectly random, i.e. all groups equally likely, no correlations or
>> anything like that.
>>
>> I wonder what is the "worst case" scenario, i.e. how to construct a data
>> set with particularly bad behavior of the incremental sort.
>
>
> I think that depends on the reason of bad behavior of incremental sort.
> For example, our quick sort implementation behaves very good on
> presorted data. But, incremental sort appears to be not so good in
> this case as Heikki showed upthread. That prompted me to test
> presorted datasets (which appeared to be "worst case") more intensively.
> But I suspect that regressions you found have another reason, and
> correspondingly "worst case" would be also different.
> When I'll investigate the reason of regressions, I'll try to construct
> "worst case" as well.
>

After some investigation of benchmark results, I found 2 sources of
regressions of incremental sort.

*Case 1: Underlying node scan lose is bigger than incremental sort win*

===== 33 [Wed Mar 7 10:14:14 CET 2018] scale:10000000 groups:10
work_mem:64MB incremental:on max_workers:0 =====
SELECT * FROM s_1 ORDER BY a, b
QUERY
PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1588080.84..1588080.84 rows=1 width=20) (actual
time=5874.527..5874.527 rows=0 loops=1)
-> Incremental Sort (cost=119371.51..1488081.45 rows=9999939 width=20)
(actual time=202.842..5653.224 rows=10000000 loops=1)
Sort Key: s_1.a, s_1.b
Presorted Key: s_1.a
Sort Method: external merge Disk: 29408kB
Sort Groups: 11
-> Index Scan using s_1_a_idx on s_1 (cost=0.43..323385.52
rows=9999939 width=20) (actual time=0.051..1494.105 rows=10000000 loops=1)
Planning time: 0.269 ms
Execution time: 5877.367 ms
(9 rows)

===== 37 [Wed Mar 7 10:15:51 CET 2018] scale:10000000 groups:10
work_mem:64MB incremental:off max_workers:0 =====
SELECT * FROM s_1 ORDER BY a, b
QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1656439.93..1656439.93 rows=1 width=20) (actual
time=4741.716..4741.716 rows=0 loops=1)
-> Sort (cost=1531440.69..1556440.54 rows=9999939 width=20) (actual
time=3522.156..4519.278 rows=10000000 loops=1)
Sort Key: s_1.a, s_1.b
Sort Method: external merge Disk: 293648kB
-> Seq Scan on s_1 (cost=0.00..163694.39 rows=9999939 width=20)
(actual time=0.021..650.322 rows=10000000 loops=1)
Planning time: 0.249 ms
Execution time: 4777.088 ms
(7 rows)

In this case optimizer have decided that "Index Scan + Incremental Sort"
would be
cheaper than "Seq Scan + Sort". But it appears that the amount of time we
loose by
selecting Index Scan over Seq Scan is bigger than amount of time we win by
selecting Incremental Sort over Sort. I would note that regular Sort
consumes
about 10X more disk space. I bet that all this space has fit to OS cache
of test
machine. But optimizer did expect actual IO to take place in this case.
This
has lead actual time to be inadequate the costing.

*Case 2: Underlying node is not parallelyzed*

===== 178 [Wed Mar 7 11:18:53 CET 2018] scale:10000000 groups:100
work_mem:8MB incremental:on max_workers:2 =====
SELECT * FROM s_2 ORDER BY a, b, c
QUERY
PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1179047.88..1179047.88 rows=1 width=20) (actual
time=4819.999..4819.999 rows=0 loops=1)
-> Incremental Sort (cost=89.04..1079047.34 rows=10000054 width=20)
(actual time=0.203..4603.197 rows=10000000 loops=1)
Sort Key: s_2.a, s_2.b, s_2.c
Presorted Key: s_2.a, s_2.b
Sort Method: quicksort Memory: 135kB
Sort Groups: 10201
-> Index Scan using s_2_a_b_idx on s_2 (cost=0.43..406985.62
rows=10000054 width=20) (actual time=0.052..1461.177 rows=10000000 loops=1)
Planning time: 0.313 ms
Execution time: 4820.037 ms
(9 rows)

===== 182 [Wed Mar 7 11:20:11 CET 2018] scale:10000000 groups:100
work_mem:8MB incremental:off max_workers:2 =====
SELECT * FROM s_2 ORDER BY a, b, c
QUERY
PLAN
--------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=1705580.76..1705580.76 rows=1 width=20) (actual
time=3985.818..3985.818 rows=0 loops=1)
-> Gather Merge (cost=649951.66..1622246.98 rows=8333378 width=20)
(actual time=1782.354..3750.868 rows=10000000 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Sort (cost=648951.64..659368.36 rows=4166689 width=20)
(actual time=1778.362..2091.253 rows=3333333 loops=3)
Sort Key: s_2.a, s_2.b, s_2.c
Sort Method: external merge Disk: 99136kB
Worker 0: Sort Method: external merge Disk: 96984kB
Worker 1: Sort Method: external merge Disk: 97496kB
-> Parallel Seq Scan on s_2 (cost=0.00..105361.89
rows=4166689 width=20) (actual time=0.022..233.640 rows=3333333 loops=3)
Planning time: 0.265 ms
Execution time: 4007.591 ms
(12 rows)

The situation is similar to case #1 except that in the pair "Seq Scan +
Sort" Sort also
gets paralellyzed. In the same way as in previous case, disk writes/reads
during
external sort are overestimated, because they actually use OS cache.
I would also say that it's not necessary wrong decision of optimizer,
because
doing this work in single backend may consume less resources despite being
overall slower.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 03/10/2018 06:05 PM, Alexander Korotkov wrote:
> On Sat, Mar 10, 2018 at 6:42 PM, Alexander Korotkov
> <a(dot)korotkov(at)postgrespro(dot)ru <mailto:a(dot)korotkov(at)postgrespro(dot)ru>> wrote:
>
> ...
>
> After some investigation of benchmark results, I found 2 sources of
> regressions of incremental sort.
>
> *Case 1: Underlying node scan lose is bigger than incremental sort win*
>
> ===== 33 [Wed Mar  7 10:14:14 CET 2018] scale:10000000 groups:10
> work_mem:64MB incremental:on max_workers:0 =====
> SELECT * FROM s_1 ORDER BY a, b
>                                                                    QUERY
> PLAN                                                                    
> -------------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1588080.84..1588080.84 rows=1 width=20) (actual
> time=5874.527..5874.527 rows=0 loops=1)
>    ->  Incremental Sort  (cost=119371.51..1488081.45 rows=9999939
> width=20) (actual time=202.842..5653.224 rows=10000000 loops=1)
>          Sort Key: s_1.a, s_1.b
>          Presorted Key: s_1.a
>          Sort Method: external merge  Disk: 29408kB
>          Sort Groups: 11
>          ->  Index Scan using s_1_a_idx on s_1  (cost=0.43..323385.52
> rows=9999939 width=20) (actual time=0.051..1494.105 rows=10000000 loops=1)
>  Planning time: 0.269 ms
>  Execution time: 5877.367 ms
> (9 rows)
>
> ===== 37 [Wed Mar  7 10:15:51 CET 2018] scale:10000000 groups:10
> work_mem:64MB incremental:off max_workers:0 =====
> SELECT * FROM s_1 ORDER BY a, b
>                                                           QUERY PLAN   
>                                                       
> ------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1656439.93..1656439.93 rows=1 width=20) (actual
> time=4741.716..4741.716 rows=0 loops=1)
>    ->  Sort  (cost=1531440.69..1556440.54 rows=9999939 width=20) (actual
> time=3522.156..4519.278 rows=10000000 loops=1)
>          Sort Key: s_1.a, s_1.b
>          Sort Method: external merge  Disk: 293648kB
>          ->  Seq Scan on s_1  (cost=0.00..163694.39 rows=9999939
> width=20) (actual time=0.021..650.322 rows=10000000 loops=1)
>  Planning time: 0.249 ms
>  Execution time: 4777.088 ms
> (7 rows)
>
> In this case optimizer have decided that "Index Scan + Incremental
> Sort" would be cheaper than "Seq Scan + Sort". But it appears that
> the amount of time we loose by selecting Index Scan over Seq Scan is
> bigger than amount of time we win by selecting Incremental Sort over
> Sort. I would note that regular Sort consumes about 10X more disk
> space. I bet that all this space has fit to OS cache of test
> machine. But optimizer did expect actual IO to take place in this
> case. This has lead actual time to be inadequate the costing.
>

Yes, you're right the temporary file(s) likely fit into RAM in this test
(and even if they did not, the storage system is pretty good).

> *Case 2: Underlying node is not parallelyzed*
>
> ===== 178 [Wed Mar  7 11:18:53 CET 2018] scale:10000000 groups:100
> work_mem:8MB incremental:on max_workers:2 =====
> SELECT * FROM s_2 ORDER BY a, b, c
>                                                                    
>  QUERY PLAN                                                             
>        
> ----------------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1179047.88..1179047.88 rows=1 width=20) (actual
> time=4819.999..4819.999 rows=0 loops=1)
>    ->  Incremental Sort  (cost=89.04..1079047.34 rows=10000054 width=20)
> (actual time=0.203..4603.197 rows=10000000 loops=1)
>          Sort Key: s_2.a, s_2.b, s_2.c
>          Presorted Key: s_2.a, s_2.b
>          Sort Method: quicksort  Memory: 135kB
>          Sort Groups: 10201
>          ->  Index Scan using s_2_a_b_idx on s_2  (cost=0.43..406985.62
> rows=10000054 width=20) (actual time=0.052..1461.177 rows=10000000 loops=1)
>  Planning time: 0.313 ms
>  Execution time: 4820.037 ms
> (9 rows)
>
> ===== 182 [Wed Mar  7 11:20:11 CET 2018] scale:10000000 groups:100
> work_mem:8MB incremental:off max_workers:2 =====
> SELECT * FROM s_2 ORDER BY a, b, c
>                                                                  QUERY
> PLAN                                                                 
> --------------------------------------------------------------------------------------------------------------------------------------------
>  Limit  (cost=1705580.76..1705580.76 rows=1 width=20) (actual
> time=3985.818..3985.818 rows=0 loops=1)
>    ->  Gather Merge  (cost=649951.66..1622246.98 rows=8333378 width=20)
> (actual time=1782.354..3750.868 rows=10000000 loops=1)
>          Workers Planned: 2
>          Workers Launched: 2
>          ->  Sort  (cost=648951.64..659368.36 rows=4166689 width=20)
> (actual time=1778.362..2091.253 rows=3333333 loops=3)
>                Sort Key: s_2.a, s_2.b, s_2.c
>                Sort Method: external merge  Disk: 99136kB
>                Worker 0:  Sort Method: external merge  Disk: 96984kB
>                Worker 1:  Sort Method: external merge  Disk: 97496kB
>                ->  Parallel Seq Scan on s_2  (cost=0.00..105361.89
> rows=4166689 width=20) (actual time=0.022..233.640 rows=3333333 loops=3)
>  Planning time: 0.265 ms
>  Execution time: 4007.591 ms
> (12 rows)
>
> The situation is similar to case #1 except that in the pair "Seq Scan
> + Sort" Sort also gets paralellyzed. In the same way as in previous
> case, disk writes/reads during external sort are overestimated,
> because they actually use OS cache. I would also say that it's not
> necessary wrong decision of optimizer, because doing this work in
> single backend may consume less resources despite being overall
> slower.
>

Yes, that seems like a likely explanation too.

I agree those don't seem like an issue in the Incremental Sort patch,
but like a more generic costing problems.

Thanks for looking into the benchmark results.

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

On Fri, Mar 16, 2018 at 5:12 AM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> I agree those don't seem like an issue in the Incremental Sort patch,
> but like a more generic costing problems.
>

Yes, I think so too.
Do you think we can mark this patch RFC assuming that it have already got
pretty
much of review previously.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 03/16/2018 09:47 AM, Alexander Korotkov wrote:
> On Fri, Mar 16, 2018 at 5:12 AM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
> I agree those don't seem like an issue in the Incremental Sort patch,
> but like a more generic costing problems.
>
>
> Yes, I think so too.

I wonder if we could make the costing a bit more pessimistic, to make
these loses less likely, while still keeping the main wins (particularly
for the LIMIT queries). But that seems a bit like a lost case, I guess.

> Do you think we can mark this patch RFC assuming that it have
> already got pretty much of review previously.
>

Actually, I was going to propose to switch it to RFC, so I've just done
that. I think the patch is clearly ready for a committer to take a
closer look. I really like this improvement.

I'm going to rerun the tests, but that's mostly because I'm interested
if the change from i++ to i-- in cmpSortPresortedCols makes a measurable
difference. I don't expect to find any issues, so why wait with the RFC?

regards

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

Hi!

Revised patch is attached. It's rebased to the last master.

On Fri, Mar 16, 2018 at 3:55 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> On 03/16/2018 09:47 AM, Alexander Korotkov wrote:
> > On Fri, Mar 16, 2018 at 5:12 AM, Tomas Vondra
> > <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>>
> wrote:
> >
> > I agree those don't seem like an issue in the Incremental Sort patch,
> > but like a more generic costing problems.
> >
> >
> > Yes, I think so too.
>
> I wonder if we could make the costing a bit more pessimistic, to make
> these loses less likely, while still keeping the main wins (particularly
> for the LIMIT queries). But that seems a bit like a lost case, I guess.
>

Making costing more pessimistic makes sense. Revised patch does
it in quite rough way: volumes of groups in incremental sort are multiplied
by 1.5. That makes one query in regression tests to fallback to fullsort
from incremental sort. Could you test it? If this will shorten number of
cases where incremental sort causes regression, then it might be an
acceptable way to do more pessimistic costing.

> Do you think we can mark this patch RFC assuming that it have
> > already got pretty much of review previously.
> >
>
> Actually, I was going to propose to switch it to RFC, so I've just done
> that. I think the patch is clearly ready for a committer to take a
> closer look. I really like this improvement.
>
> I'm going to rerun the tests, but that's mostly because I'm interested
> if the change from i++ to i-- in cmpSortPresortedCols makes a measurable
> difference. I don't expect to find any issues, so why wait with the RFC?
>

Good, thanks.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi,

on a PostGIS system tuned for preferring parallelism heavily (
min_parallel_table_scan_size=10kB) we experience issues with QGIS table
discovery query with this patch:

Failing query is:
[local] gis(at)gis=# SELECT
l.f_table_name,l.f_table_schema,l.f_geometry_column,upper(l.type),l.srid,l.coord_dimension,c.relkind,obj_description(c.oid)
FROM geometry_columns l,pg_class c,pg_namespace n WHERE
c.relname=l.f_table_name AND l.f_table_schema=n.
nspname AND n.oid=c.relnamespace AND
has_schema_privilege(n.nspname,'usage') AND
has_table_privilege('"'||n.nspname||'"."'||c.relname||'"','select') AND
l.f_table_schema='public' ORDER BY n.nspname,c.relname,l.f_geometry_column;

ERROR: XX000: badly formatted node string "INCREMENTALSORT :startup_cost
37"...
CONTEXT: parallel worker
LOCATION: parseNodeString, readfuncs.c:2693
Time: 42,052 ms

Query plan:

QUERY PLAN

──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────
Sort (cost=38717.21..38717.22 rows=1 width=393)
Sort Key: c_1.relname, a.attname
-> Nested Loop (cost=36059.35..38717.20 rows=1 width=393)
-> Index Scan using pg_namespace_nspname_index on pg_namespace n
(cost=0.28..2.30 rows=1 width=68)
Index Cond: (nspname = 'public'::name)
Filter: has_schema_privilege((nspname)::text, 'usage'::text)
-> Nested Loop (cost=36059.08..38714.59 rows=1 width=407)
-> Nested Loop Left Join (cost=36058.65..38712.12 rows=1
width=334)
Join Filter: ((s_2.connamespace = n_1.oid) AND
(a.attnum = ANY (s_2.conkey)))
-> Nested Loop Left Join (cost=36058.51..38711.94
rows=1 width=298)
Join Filter: ((s_1.connamespace = n_1.oid) AND
(a.attnum = ANY (s_1.conkey)))
-> Nested Loop (cost=36058.38..38711.75 rows=1
width=252)
Join Filter: (a.atttypid = t.oid)
-> Gather Merge (cost=36057.95..38702.65
rows=444 width=256)
Workers Planned: 10
-> Merge Left Join
(cost=35057.76..37689.01 rows=44 width=256)
Merge Cond: ((n_1.oid =
s.connamespace) AND (c_1.oid = s.conrelid))
Join Filter: (a.attnum = ANY
(s.conkey))
-> Incremental Sort
(cost=37687.19..37687.30 rows=44 width=210)
Sort Key: n_1.oid, c_1.oid
Presorted Key: n_1.oid
-> Nested Loop
(cost=34837.25..37685.99 rows=44 width=210)
-> Merge Join
(cost=34836.82..34865.99 rows=9 width=136)
Merge Cond:
(c_1.relnamespace = n_1.oid)
-> Sort
(cost=34834.52..34849.05 rows=5814 width=72)
Sort
Key: c_1.relnamespace
->
Parallel Seq Scan on pg_class c_1 (cost=0.00..34470.99 rows=5814 width=72)

Filter: ((relname <> 'raster_columns'::name) AND (NOT
pg_is_other_temp_schema(relnamespace)) AND has_table_privilege(oid,
'SELECT'::text) AND (relkind = ANY ('{r,v,m,f,p}'::"char"[])))
-> Sort
(cost=2.30..2.31 rows=1 width=68)
Sort
Key: n_1.oid
->
Index Scan using pg_namespace_nspname_index on pg_namespace n_1
(cost=0.28..2.29 rows=1 width=68)

Index Cond: (nspname = 'public'::name)
-> Index Scan
using pg_attribute_relid_attnum_index on pg_attribute a (cost=0.43..200.52
rows=11281 width=78)
Index Cond:
(attrelid = c_1.oid)
Filter: (NOT
attisdropped)
-> Sort (cost=1.35..1.35
rows=1 width=77)
Sort Key: s.connamespace,
s.conrelid
-> Seq Scan on
pg_constraint s (cost=0.00..1.34 rows=1 width=77)
Filter: (consrc ~~*
'%geometrytype(% = %'::text)
-> Materialize (cost=0.42..2.45 rows=1
width=4)
-> Index Scan using
pg_type_typname_nsp_index on pg_type t (cost=0.42..2.44 rows=1 width=4)
Index Cond: (typname =
'geometry'::name)
-> Index Scan using pg_constraint_conrelid_index
on pg_constraint s_1 (cost=0.14..0.16 rows=1 width=77)
Index Cond: (conrelid = c_1.oid)
Filter: (consrc ~~* '%ndims(% = %'::text)
-> Index Scan using pg_constraint_conrelid_index on
pg_constraint s_2 (cost=0.14..0.16 rows=1 width=77)
Index Cond: (conrelid = c_1.oid)
Filter: (consrc ~~* '%srid(% = %'::text)
-> Index Scan using pg_class_relname_nsp_index on pg_class
c (cost=0.42..2.46 rows=1 width=73)
Index Cond: ((relname = c_1.relname) AND (relnamespace
= n.oid))
Filter: has_table_privilege((((('"'::text ||
(n.nspname)::text) || '"."'::text) || (relname)::text) || '"'::text),
'select'::text)
(51 rows)

Darafei Praliaskouski,
GIS Engineer / Juno Minsk

Hi!

On Wed, Mar 21, 2018 at 2:30 PM, Darafei "Komяpa" Praliaskouski <
me(at)komzpa(dot)net> wrote:

> on a PostGIS system tuned for preferring parallelism heavily (
> min_parallel_table_scan_size=10kB) we experience issues with QGIS table
> discovery query with this patch:
>
> Failing query is:
> [local] gis(at)gis=# SELECT l.f_table_name,l.f_table_
> schema,l.f_geometry_column,upper(l.type),l.srid,l.coord_
> dimension,c.relkind,obj_description(c.oid) FROM geometry_columns
> l,pg_class c,pg_namespace n WHERE c.relname=l.f_table_name AND
> l.f_table_schema=n.
> nspname AND n.oid=c.relnamespace AND has_schema_privilege(n.nspname,'usage')
> AND has_table_privilege('"'||n.nspname||'"."'||c.relname||'"','select')
> AND l.f_table_schema='public' ORDER BY n.nspname,c.relname,l.f_geometry_column;
>
> ERROR: XX000: badly formatted node string "INCREMENTALSORT :startup_cost
> 37"...
> CONTEXT: parallel worker
> LOCATION: parseNodeString, readfuncs.c:2693
> Time: 42,052 ms
>
>
> Query plan:
>
>
> QUERY PLAN
>
>
> ────────────────────────────────────────────────────────────
> ────────────────────────────────────────────────────────────
> ────────────────────────────────────────────────────────────
> ────────────────────────────────────────────────────────────
> ──────────────────
> Sort (cost=38717.21..38717.22 rows=1 width=393)
> Sort Key: c_1.relname, a.attname
> -> Nested Loop (cost=36059.35..38717.20 rows=1 width=393)
> -> Index Scan using pg_namespace_nspname_index on pg_namespace n
> (cost=0.28..2.30 rows=1 width=68)
> Index Cond: (nspname = 'public'::name)
> Filter: has_schema_privilege((nspname)::text, 'usage'::text)
> -> Nested Loop (cost=36059.08..38714.59 rows=1 width=407)
> -> Nested Loop Left Join (cost=36058.65..38712.12 rows=1
> width=334)
> Join Filter: ((s_2.connamespace = n_1.oid) AND
> (a.attnum = ANY (s_2.conkey)))
> -> Nested Loop Left Join (cost=36058.51..38711.94
> rows=1 width=298)
> Join Filter: ((s_1.connamespace = n_1.oid) AND
> (a.attnum = ANY (s_1.conkey)))
> -> Nested Loop (cost=36058.38..38711.75 rows=1
> width=252)
> Join Filter: (a.atttypid = t.oid)
> -> Gather Merge (cost=36057.95..38702.65
> rows=444 width=256)
> Workers Planned: 10
> -> Merge Left Join
> (cost=35057.76..37689.01 rows=44 width=256)
> Merge Cond: ((n_1.oid =
> s.connamespace) AND (c_1.oid = s.conrelid))
> Join Filter: (a.attnum = ANY
> (s.conkey))
> -> Incremental Sort
> (cost=37687.19..37687.30 rows=44 width=210)
> Sort Key: n_1.oid,
> c_1.oid
> Presorted Key: n_1.oid
> -> Nested Loop
> (cost=34837.25..37685.99 rows=44 width=210)
> -> Merge Join
> (cost=34836.82..34865.99 rows=9 width=136)
> Merge Cond:
> (c_1.relnamespace = n_1.oid)
> -> Sort
> (cost=34834.52..34849.05 rows=5814 width=72)
> Sort
> Key: c_1.relnamespace
> ->
> Parallel Seq Scan on pg_class c_1 (cost=0.00..34470.99 rows=5814 width=72)
>
> Filter: ((relname <> 'raster_columns'::name) AND (NOT
> pg_is_other_temp_schema(relnamespace)) AND has_table_privilege(oid,
> 'SELECT'::text) AND (relkind = ANY ('{r,v,m,f,p}'::"char"[])))
> -> Sort
> (cost=2.30..2.31 rows=1 width=68)
> Sort
> Key: n_1.oid
> ->
> Index Scan using pg_namespace_nspname_index on pg_namespace n_1
> (cost=0.28..2.29 rows=1 width=68)
>
> Index Cond: (nspname = 'public'::name)
> -> Index Scan
> using pg_attribute_relid_attnum_index on pg_attribute a
> (cost=0.43..200.52 rows=11281 width=78)
> Index Cond:
> (attrelid = c_1.oid)
> Filter: (NOT
> attisdropped)
> -> Sort (cost=1.35..1.35
> rows=1 width=77)
> Sort Key:
> s.connamespace, s.conrelid
> -> Seq Scan on
> pg_constraint s (cost=0.00..1.34 rows=1 width=77)
> Filter: (consrc
> ~~* '%geometrytype(% = %'::text)
> -> Materialize (cost=0.42..2.45 rows=1
> width=4)
> -> Index Scan using
> pg_type_typname_nsp_index on pg_type t (cost=0.42..2.44 rows=1 width=4)
> Index Cond: (typname =
> 'geometry'::name)
> -> Index Scan using
> pg_constraint_conrelid_index on pg_constraint s_1 (cost=0.14..0.16 rows=1
> width=77)
> Index Cond: (conrelid = c_1.oid)
> Filter: (consrc ~~* '%ndims(% = %'::text)
> -> Index Scan using pg_constraint_conrelid_index on
> pg_constraint s_2 (cost=0.14..0.16 rows=1 width=77)
> Index Cond: (conrelid = c_1.oid)
> Filter: (consrc ~~* '%srid(% = %'::text)
> -> Index Scan using pg_class_relname_nsp_index on pg_class
> c (cost=0.42..2.46 rows=1 width=73)
> Index Cond: ((relname = c_1.relname) AND (relnamespace
> = n.oid))
> Filter: has_table_privilege((((('"'::text ||
> (n.nspname)::text) || '"."'::text) || (relname)::text) || '"'::text),
> 'select'::text)
> (51 rows)
>

Thank you for pointing. I'll try to reproduce this issue and fix it.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Wed, Mar 21, 2018 at 2:32 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Wed, Mar 21, 2018 at 2:30 PM, Darafei "Komяpa" Praliaskouski <
> me(at)komzpa(dot)net> wrote:
>
>> on a PostGIS system tuned for preferring parallelism heavily (
>> min_parallel_table_scan_size=10kB) we experience issues with QGIS table
>> discovery query with this patch:
>>
>> Failing query is:
>> [local] gis(at)gis=# SELECT l.f_table_name,l.f_table_schem
>> a,l.f_geometry_column,upper(l.type),l.srid,l.coord_dimension
>> ,c.relkind,obj_description(c.oid) FROM geometry_columns l,pg_class
>> c,pg_namespace n WHERE c.relname=l.f_table_name AND l.f_table_schema=n.
>> nspname AND n.oid=c.relnamespace AND has_schema_privilege(n.nspname,'usage')
>> AND has_table_privilege('"'||n.nspname||'"."'||c.relname||'"','select')
>> AND l.f_table_schema='public' ORDER BY n.nspname,c.relname,l.f_geometry_column;
>>
>> ERROR: XX000: badly formatted node string "INCREMENTALSORT :startup_cost
>> 37"...
>> CONTEXT: parallel worker
>> LOCATION: parseNodeString, readfuncs.c:2693
>> Time: 42,052 ms
>>
>>
>> Query plan:
>>
>>
>> QUERY PLAN
>>
>>
>> ────────────────────────────────────────────────────────────
>> ────────────────────────────────────────────────────────────
>> ────────────────────────────────────────────────────────────
>> ────────────────────────────────────────────────────────────
>> ──────────────────
>> Sort (cost=38717.21..38717.22 rows=1 width=393)
>> Sort Key: c_1.relname, a.attname
>> -> Nested Loop (cost=36059.35..38717.20 rows=1 width=393)
>> -> Index Scan using pg_namespace_nspname_index on pg_namespace
>> n (cost=0.28..2.30 rows=1 width=68)
>> Index Cond: (nspname = 'public'::name)
>> Filter: has_schema_privilege((nspname)::text,
>> 'usage'::text)
>> -> Nested Loop (cost=36059.08..38714.59 rows=1 width=407)
>> -> Nested Loop Left Join (cost=36058.65..38712.12 rows=1
>> width=334)
>> Join Filter: ((s_2.connamespace = n_1.oid) AND
>> (a.attnum = ANY (s_2.conkey)))
>> -> Nested Loop Left Join (cost=36058.51..38711.94
>> rows=1 width=298)
>> Join Filter: ((s_1.connamespace = n_1.oid) AND
>> (a.attnum = ANY (s_1.conkey)))
>> -> Nested Loop (cost=36058.38..38711.75
>> rows=1 width=252)
>> Join Filter: (a.atttypid = t.oid)
>> -> Gather Merge
>> (cost=36057.95..38702.65 rows=444 width=256)
>> Workers Planned: 10
>> -> Merge Left Join
>> (cost=35057.76..37689.01 rows=44 width=256)
>> Merge Cond: ((n_1.oid =
>> s.connamespace) AND (c_1.oid = s.conrelid))
>> Join Filter: (a.attnum = ANY
>> (s.conkey))
>> -> Incremental Sort
>> (cost=37687.19..37687.30 rows=44 width=210)
>> Sort Key: n_1.oid,
>> c_1.oid
>> Presorted Key: n_1.oid
>> -> Nested Loop
>> (cost=34837.25..37685.99 rows=44 width=210)
>> -> Merge Join
>> (cost=34836.82..34865.99 rows=9 width=136)
>> Merge Cond:
>> (c_1.relnamespace = n_1.oid)
>> -> Sort
>> (cost=34834.52..34849.05 rows=5814 width=72)
>> Sort
>> Key: c_1.relnamespace
>> ->
>> Parallel Seq Scan on pg_class c_1 (cost=0.00..34470.99 rows=5814 width=72)
>>
>> Filter: ((relname <> 'raster_columns'::name) AND (NOT
>> pg_is_other_temp_schema(relnamespace)) AND has_table_privilege(oid,
>> 'SELECT'::text) AND (relkind = ANY ('{r,v,m,f,p}'::"char"[])))
>> -> Sort
>> (cost=2.30..2.31 rows=1 width=68)
>> Sort
>> Key: n_1.oid
>> ->
>> Index Scan using pg_namespace_nspname_index on pg_namespace n_1
>> (cost=0.28..2.29 rows=1 width=68)
>>
>> Index Cond: (nspname = 'public'::name)
>> -> Index Scan
>> using pg_attribute_relid_attnum_index on pg_attribute a
>> (cost=0.43..200.52 rows=11281 width=78)
>> Index Cond:
>> (attrelid = c_1.oid)
>> Filter:
>> (NOT attisdropped)
>> -> Sort (cost=1.35..1.35
>> rows=1 width=77)
>> Sort Key:
>> s.connamespace, s.conrelid
>> -> Seq Scan on
>> pg_constraint s (cost=0.00..1.34 rows=1 width=77)
>> Filter: (consrc
>> ~~* '%geometrytype(% = %'::text)
>> -> Materialize (cost=0.42..2.45 rows=1
>> width=4)
>> -> Index Scan using
>> pg_type_typname_nsp_index on pg_type t (cost=0.42..2.44 rows=1 width=4)
>> Index Cond: (typname =
>> 'geometry'::name)
>> -> Index Scan using
>> pg_constraint_conrelid_index on pg_constraint s_1 (cost=0.14..0.16 rows=1
>> width=77)
>> Index Cond: (conrelid = c_1.oid)
>> Filter: (consrc ~~* '%ndims(% = %'::text)
>> -> Index Scan using pg_constraint_conrelid_index on
>> pg_constraint s_2 (cost=0.14..0.16 rows=1 width=77)
>> Index Cond: (conrelid = c_1.oid)
>> Filter: (consrc ~~* '%srid(% = %'::text)
>> -> Index Scan using pg_class_relname_nsp_index on pg_class
>> c (cost=0.42..2.46 rows=1 width=73)
>> Index Cond: ((relname = c_1.relname) AND
>> (relnamespace = n.oid))
>> Filter: has_table_privilege((((('"'::text ||
>> (n.nspname)::text) || '"."'::text) || (relname)::text) || '"'::text),
>> 'select'::text)
>> (51 rows)
>>
>
> Thank you for pointing. I'll try to reproduce this issue and fix it.
>

I found that Darafei used build made using incremental-sort-7.patch. That
version contained bug in incremental sort node deserialization.
Modern patch versions doesn't contain that bug.

I've checked that it works.

create table t (i int, value float8);
insert into t select i%1000, random() from generate_series(1,1000000) i;
set force_parallel_mode = on;

# explain select count(*) from (select * from (select * from t order by i)
x order by i, value) y;
QUERY PLAN
------------------------------------------------------------------------------------
Gather (cost=254804.94..254805.05 rows=1 width=8)
Workers Planned: 1
Single Copy: true
-> Aggregate (cost=253804.94..253804.95 rows=1 width=8)
-> Incremental Sort (cost=132245.97..241304.94 rows=1000000
width=12)
Sort Key: t.i, t.value
Presorted Key: t.i
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: t.i
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000
width=12)
(10 rows)

# select count(*) from (select * from (select * from t order by i) x order
by i, value) y;
count
---------
1000000
(1 row)

BTW, patch had conflicts with master. Please, find rebased version
attached.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

> BTW, patch had conflicts with master.  Please, find rebased version attached.

Sorry, but patch conflicts with master again.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

> BTW, patch had conflicts with master.  Please, find rebased version attached.

Despite by patch conflist patch looks commitable, has anybody objections to
commit it?

Patch recieved several rounds of review during 2 years, and seems to me, keeping
it out from sources may cause a lost it. Although it suggests performance
improvement in rather wide usecases.

--
Teodor Sigaev E-mail: teodor(at)sigaev(dot)ru
WWW: http://www.sigaev.ru/

On 03/28/2018 03:28 PM, Teodor Sigaev wrote:
>> BTW, patch had conflicts with master.  Please, find rebased version
>> attached.
>
> Despite by patch conflist patch looks commitable, has anybody objections
> to commit it?
>
> Patch recieved several rounds of review during 2 years, and seems to me,
> keeping it out from sources may cause a lost it. Although it suggests
> performance improvement in rather wide usecases.
>

No objections from me - if you want me to do one final round of review
after the rebase (not sure how invasive it'll turn out), let me know.

BTW one detail I'd change is name of the GUC variable. enable_incsort
seems unnecessarily terse - let's go for enable_incremental_sort or
something like that.

regards

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

On Wed, Mar 28, 2018 at 4:44 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> On 03/28/2018 03:28 PM, Teodor Sigaev wrote:
> >> BTW, patch had conflicts with master. Please, find rebased version
> >> attached.
> >
> > Despite by patch conflist patch looks commitable, has anybody objections
> > to commit it?
> >
> > Patch recieved several rounds of review during 2 years, and seems to me,
> > keeping it out from sources may cause a lost it. Although it suggests
> > performance improvement in rather wide usecases.
> >
>
> No objections from me - if you want me to do one final round of review
> after the rebase (not sure how invasive it'll turn out), let me know.
>

Rebased patch is attached. Incremental sort get used in multiple places
of partition_aggregate regression test. I've checked those cases, and it
seems
that incremental sort was selected right.

BTW one detail I'd change is name of the GUC variable. enable_incsort
> seems unnecessarily terse - let's go for enable_incremental_sort or
> something like that.
>

Already enable_incsort was already renamed to enable_incrementalsort
since [1].

1.
https://www.postgresql.org/message-id/CAPpHfduAVmiGDZC%2BdfNL1rEGu0mt45Rd_mxwjY57uqwWhrvQzg%40mail.gmail.com

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 03/28/2018 05:12 PM, Alexander Korotkov wrote:
> On Wed, Mar 28, 2018 at 4:44 PM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
> On 03/28/2018 03:28 PM, Teodor Sigaev wrote:
> >> BTW, patch had conflicts with master.  Please, find rebased version
> >> attached.
> >
> > Despite by patch conflist patch looks commitable, has anybody objections
> > to commit it?
> >
> > Patch recieved several rounds of review during 2 years, and seems to me,
> > keeping it out from sources may cause a lost it. Although it suggests
> > performance improvement in rather wide usecases.
> >
>
> No objections from me - if you want me to do one final round of review
> after the rebase (not sure how invasive it'll turn out), let me know.
>
>
> Rebased patch is attached.  Incremental sort get used in multiple places
> of partition_aggregate regression test.  I've checked those cases, and
> it seems that incremental sort was selected right.
>

OK, I'll take a look.

> BTW one detail I'd change is name of the GUC variable. enable_incsort
> seems unnecessarily terse - let's go for enable_incremental_sort or
> something like that.
>
>
> Already enable_incsort was already renamed to enable_incrementalsort
> since [1].  
>
> 1.
> https://www.postgresql.org/message-id/CAPpHfduAVmiGDZC%2BdfNL1rEGu0mt45Rd_mxwjY57uqwWhrvQzg%40mail.gmail.com 
>

Ah, apologies. I've been looking at the wrong version.

regards

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

Teodor Sigaev wrote:
> > BTW, patch had conflicts with master.  Please, find rebased version attached.
>
> Despite by patch conflist patch looks commitable, has anybody objections to
> commit it?
>
> Patch recieved several rounds of review during 2 years, and seems to me,
> keeping it out from sources may cause a lost it. Although it suggests
> performance improvement in rather wide usecases.

Can we have a recap on what the patch *does*? I see there's a
description in Alexander's first email
https://postgr.es/m/CAPpHfdscOX5an71nHd8WSUH6GNOCf=V7wgDaTXdDd9=goN-gfA@mail.gmail.com
but that was a long time ago, and the patch has likely changed in the
meantime ...

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi,

On 2018-03-28 16:28:01 +0300, Teodor Sigaev wrote:
> > BTW, patch had conflicts with master.  Please, find rebased version attached.
>
> Despite by patch conflist patch looks commitable, has anybody objections to
> commit it?

> Patch recieved several rounds of review during 2 years, and seems to me,
> keeping it out from sources may cause a lost it. Although it suggests
> performance improvement in rather wide usecases.

My impression it has *NOT* received enough review to be RFC. Not saying
it's impossible to get there this release, but that just committing it
doesn't seem wise.

Greetings,

Andres Freund

On Wed, Mar 28, 2018 at 7:17 PM, Andres Freund <andres(at)anarazel(dot)de> wrote:

> On 2018-03-28 16:28:01 +0300, Teodor Sigaev wrote:
> > > BTW, patch had conflicts with master. Please, find rebased version
> attached.
> >
> > Despite by patch conflist patch looks commitable, has anybody objections
> to
> > commit it?
>
> > Patch recieved several rounds of review during 2 years, and seems to me,
> > keeping it out from sources may cause a lost it. Although it suggests
> > performance improvement in rather wide usecases.
>
> My impression it has *NOT* received enough review to be RFC. Not saying
> it's impossible to get there this release, but that just committing it
> doesn't seem wise.
>

I would say that executor part of this patch already received plenty of
review.
For sure, there still might be issues. I just mean that amount of review of
executor part of this patch is not less than in average patch we commit.
But optimizer and costing part of this patch still need somebody to take
a look at it.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi Alexander,

I took a quick look at the patch. Some things I fixed myself in the
attached patch v.21. Here is the summary:

Typo in compare_fractional_path_costs() should be fixed as a separate patch.
Remove unused function estimate_pathkeys_groups.
Extra MemoryContextReset before tuplesort_end() shouldn't be a big deal,
so we don't have to add a parameter to tuplesoft_free().
Add comment to maincontext declaration.
Fix typo in INITIAL_MEMTUPSIZE.
Remove trailing whitespace.

Some other things I found:

In tuplesort_reset:
if (state->memtupsize < INITIAL_MEMTUPSIZE)
    <reallocate memtuples to INITIAL_MEMTUPSIZE>
I'd add a comment explaining when and why we have to do this. Also maybe
a comment to other allocations of memtuples in tuplesort_begin() and
mergeruns(), explaining why it is reallocated and why in maincontext.

In tuplesort_updatemax:
    /* XXX */
    if (spaceUsedOnDisk > state->maxSpaceOnDisk ||
        (spaceUsedOnDisk == state->maxSpaceOnDisk && spaceUsed >
state->maxSpace))
XXX. Also comparing bools with '>' looks confusing to me.

We should add a comment on top of tuplesort.c, explaining that we now
have a faster way to sort multiple batches of data using the same sort
conditions.

The name 'main context' sounds somewhat vague. Maybe 'top context'? Not
sure.

In ExecSupportBackwardsScan:
        case T_IncrementalSort:
            return false;
This separate case looks useless, I'd either add a comment explaining
why it can't scan backwards, or just return false by default.

That's all I have for today; tomorrow I'll continue with reviewing the
planner part of the patch.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi,

I've been doing a bit more review of the patch today, focusing on the
planner part, and I'm starting to have some doubts regarding the way
incremental sort paths are created. I do have some question about the
executor and other parts too.

I'll mark this as 'waiting on author' to make it clear the patch is
still being discussed, RFC is not appropriate status for that.

Attached is a patch that highlights some of the interesting places, and
also suggests some minor changes to comments and other tweaks.

1) planning/costing of incremental vs. non-incremental sorts
------------------------------------------------------------

In sort, all the various places that create/cost sorts:

* createplan.c (make_sort)
* planner.c (create_sort_path)
* pathnode.c (cost_sort)

seem to prefer incremental sorts whenever available. Consider for
example this code from create_merge_append_plan():

if (!pathkeys_common_contained_in(pathkeys, subpath->pathkeys,
&n_common_pathkeys))
{
Sort *sort = make_sort(subplan, numsortkeys,
n_common_pathkeys,
sortColIdx, sortOperators,
collations, nullsFirst);

label_sort_with_costsize(root, sort, best_path->limit_tuples);
subplan = (Plan *) sort;
}

This essentially says that when (n_common_pathkeys > 0), the sort is
going to be incremental.

That however seems to rely on an important assumption - when the input
is presorted, the incremental sort is expected to be cheaper than
regular sort.

This assumption however seems to be proven invalid by cost_sort, which
does the common part for both sort modes (incremental/non-incremental)
first, and then does this:

/* Extra costs of incremental sort */
if (presorted_keys > 0)
{
... add something to the costs ...
}

That is, the incremental cost seems to be pretty much guaranteed to be
more expensive than regular Sort (with the exception of LIMIT queries,
where it's guaranteed to win thanks to lower startup cost).

I don't know how significant the cost difference may be (perhaps not
much), or if it may lead to inefficient plans. For example what if the
cheapest total path is partially sorted by chance, and only has a single
prefix group? Then all the comparisons with pivotSlot are unnecessary.

But I'm pretty sure it may lead to surprising behavior - for example if
you disable incremental sorts (enable_incrementalsort=off), the plan
will switch to plain sort without the additional costs. So you'll get a
cheaper plan by disabling some operation. That's surprising.

So I think it would be more appropriate if those places actually did a
costing of incremental vs. non-incremental sorts, and then constructed
the cheaper option. Essentially we should consider both plain and
incremental sort for each partially sorted input path, and then pick the
right one.

Of course, this is going to be tricky in createplan.c which builds the
plans directly - in that case it might be integrated into make_sort() or
something like that.

Also, I wonder if we could run into problems, due to incremental sort
not supporting things the regular sort does (rewind, backwards scans and
mark/restore).

2) nodeIncrementalsort.c
------------------------

There's a couple of obsolete comments, that came from nodeSort.c and did
not get tweaked (and so talk about first-time through when incremental
sort needs to do that for each group, etc.). The attached diff tweaks
those, and clarifies a couple of others. I've also added some comments
explaining what the pivotSlot is about etc. There's also a couple of XXX
comments asking additional questions/clarifications.

I'm wondering if a static MIN_GROUP_SIZE is good idea. For example, what
if the subplan is expected to return only very few tuples (say, 33), but
the query includes LIMIT 1. Now, let's assume the startup/total cost of
the subplan is 1 and 1000000. With MIN_GROUP_SIZE 32 we're bound to
execute it pretty much till the end, while we could terminate after the
first tuple (if the prefix changes).

So I think we should use a Min(limit,MIN_GROUP_SIZE) here, and perhaps
this should depend on average group size too.

The other questionable thing seems to be this claim:

* We unlikely will have huge groups with incremental sort. Therefore
* usage of abbreviated keys would be likely a waste of time.

followed by disabling abbreviated keys in the tuplesort_begin_heap call.
I find this rather dubious and unsupported by any arguments (I certainly
don't see any in the comments).

If would be more acceptable if the estimated number of groups was used
when deciding whether to use incremental sort or not, but that's not the
case - as explained in the first part, we simply prefer incremental
sorts whenever there is a prefix. In those cases we have very little
idea (or even guarantees) regarding the average group size.

Furthermore, cost_sort is estimating the number of groups, so it does
know the average group size. I don't see why we couldn't consider it
here too, and disable/enable abbreviated keys depending on that.

3) pathkeys.c
-------------

The new function pathkeys_useful_for_ordering() does actually change
behavior depending on enable_incrementalsort. That seems like a rather
bad idea, for a couple or reasons.

AFAICS pathkeys.c is supposed to provide generic utils for work with
pathkeys, and no one would expect the functions to change behavior
depending on enable_* GUCs. I certainly would not.

In short, this does not seem like the right place to enable/disable
incremental sorts, that should be done when costing the plan (i.e. in
costsize.c) or creating the plan.

regards

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

On 03/31/2018 10:43 PM, Tomas Vondra wrote:
> ...
> But I'm pretty sure it may lead to surprising behavior - for example if
> you disable incremental sorts (enable_incrementalsort=off), the plan
> will switch to plain sort without the additional costs. So you'll get a
> cheaper plan by disabling some operation. That's surprising.
>

To illustrate this is a valid issue, consider this trivial example:

create table t (a int, b int, c int);

insert into t select 10*random(), 10*random(), 10*random()
from generate_series(1,1000000) s(i);

analyze t;

explain select * from (select * from t order by a,b) foo order by a,b,c;

QUERY PLAN
------------------------------------------------------------------------
Incremental Sort (cost=133100.48..264139.27 rows=1000000 width=12)
Sort Key: t.a, t.b, t.c
Presorted Key: t.a, t.b
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: t.a, t.b
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
(6 rows)

set enable_incrementalsort = off;

explain select * from (select * from t order by a,b) foo order by a,b,c;
QUERY PLAN
------------------------------------------------------------------------
Sort (cost=261402.69..263902.69 rows=1000000 width=12)
Sort Key: t.a, t.b, t.c
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: t.a, t.b
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
(5 rows)

So the cost with incremental sort was 264139, and after disabling the
incremental cost it dropped to 263902. Granted, the difference is
negligible in this case, but it's still surprising.

Also, it can be made much more significant by reducing the number of
prefix groups in the data:

truncate t;

insert into t select 1,1,1 from generate_series(1,1000000) s(i);

analyze t;

set enable_incrementalsort = on;

explain select * from (select * from t order by a,b) foo order by a,b,c;

QUERY PLAN
------------------------------------------------------------------------
Incremental Sort (cost=324165.83..341665.85 rows=1000000 width=12)
Sort Key: t.a, t.b, t.c
Presorted Key: t.a, t.b
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: t.a, t.b
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
(6 rows)

So that's 263902 vs. 341665, yet we still prefer the incremental mode.

regards

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

On Sun, Apr 1, 2018 at 12:06 AM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> On 03/31/2018 10:43 PM, Tomas Vondra wrote:
> > ...
> > But I'm pretty sure it may lead to surprising behavior - for example if
> > you disable incremental sorts (enable_incrementalsort=off), the plan
> > will switch to plain sort without the additional costs. So you'll get a
> > cheaper plan by disabling some operation. That's surprising.
> >
>
> To illustrate this is a valid issue, consider this trivial example:
>
> create table t (a int, b int, c int);
>
> insert into t select 10*random(), 10*random(), 10*random()
> from generate_series(1,1000000) s(i);
>
> analyze t;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
>
> QUERY PLAN
> ------------------------------------------------------------------------
> Incremental Sort (cost=133100.48..264139.27 rows=1000000 width=12)
> Sort Key: t.a, t.b, t.c
> Presorted Key: t.a, t.b
> -> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
> Sort Key: t.a, t.b
> -> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
> (6 rows)
>
> set enable_incrementalsort = off;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
> QUERY PLAN
> ------------------------------------------------------------------------
> Sort (cost=261402.69..263902.69 rows=1000000 width=12)
> Sort Key: t.a, t.b, t.c
> -> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
> Sort Key: t.a, t.b
> -> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
> (5 rows)
>
> So the cost with incremental sort was 264139, and after disabling the
> incremental cost it dropped to 263902. Granted, the difference is
> negligible in this case, but it's still surprising.
>
> Also, it can be made much more significant by reducing the number of
> prefix groups in the data:
>
> truncate t;
>
> insert into t select 1,1,1 from generate_series(1,1000000) s(i);
>
> analyze t;
>
> set enable_incrementalsort = on;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
>
> QUERY PLAN
> ------------------------------------------------------------------------
> Incremental Sort (cost=324165.83..341665.85 rows=1000000 width=12)
> Sort Key: t.a, t.b, t.c
> Presorted Key: t.a, t.b
> -> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
> Sort Key: t.a, t.b
> -> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
> (6 rows)
>
> So that's 263902 vs. 341665, yet we still prefer the incremental mode.

Problem is well-defined, thank you.
I'll check what can be done in this field today.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 04/03/2018 11:09 AM, Alexander Korotkov wrote:
> On Sun, Apr 1, 2018 at 12:06 AM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
> On 03/31/2018 10:43 PM, Tomas Vondra wrote:
> > ...
> > But I'm pretty sure it may lead to surprising behavior - for example if
> > you disable incremental sorts (enable_incrementalsort=off), the plan
> > will switch to plain sort without the additional costs. So you'll get a
> > cheaper plan by disabling some operation. That's surprising.
> >
>
> To illustrate this is a valid issue, consider this trivial example:
>
> create table t (a int, b int, c int);
>
> insert into t select 10*random(), 10*random(), 10*random()
>   from generate_series(1,1000000) s(i);
>
> analyze t;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
>
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  Incremental Sort  (cost=133100.48..264139.27 rows=1000000 width=12)
>    Sort Key: t.a, t.b, t.c
>    Presorted Key: t.a, t.b
>    ->  Sort  (cost=132154.34..134654.34 rows=1000000 width=12)
>          Sort Key: t.a, t.b
>          ->  Seq Scan on t  (cost=0.00..15406.00 rows=1000000 width=12)
> (6 rows)
>
> set enable_incrementalsort = off;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  Sort  (cost=261402.69..263902.69 rows=1000000 width=12)
>    Sort Key: t.a, t.b, t.c
>    ->  Sort  (cost=132154.34..134654.34 rows=1000000 width=12)
>          Sort Key: t.a, t.b
>          ->  Seq Scan on t  (cost=0.00..15406.00 rows=1000000 width=12)
> (5 rows)
>
> So the cost with incremental sort was 264139, and after disabling the
> incremental cost it dropped to 263902. Granted, the difference is
> negligible in this case, but it's still surprising.
>
> Also, it can be made much more significant by reducing the number of
> prefix groups in the data:
>
> truncate t;
>
> insert into t select 1,1,1 from generate_series(1,1000000) s(i);
>
> analyze t;
>
> set enable_incrementalsort = on;
>
> explain select * from (select * from t order by a,b) foo order by a,b,c;
>
>                                QUERY PLAN
> ------------------------------------------------------------------------
>  Incremental Sort  (cost=324165.83..341665.85 rows=1000000 width=12)
>    Sort Key: t.a, t.b, t.c
>    Presorted Key: t.a, t.b
>    ->  Sort  (cost=132154.34..134654.34 rows=1000000 width=12)
>          Sort Key: t.a, t.b
>          ->  Seq Scan on t  (cost=0.00..15406.00 rows=1000000 width=12)
> (6 rows)
>
> So that's 263902 vs. 341665, yet we still prefer the incremental mode.
>
>
> Problem is well-defined, thank you.
> I'll check what can be done in this field today.
>

I think solving this may be fairly straight-forward. Essentially, until
now we only had one way to do the sort, so it was OK to make the sort
implicit by checking if the path is sorted

if (input not sorted)
{
... add a Sort node ...
}

But now we have multiple possible ways to do the sort, with different
startup/total costs. So the places that create the sorts need to
actually generate the Sort paths for each sort alternative, and store
the information in the Sort node (instead of relying on pathkeys).

Ultimately, this should simplify the createplan.c places making all the
make_sort calls unnecessary (i.e. the input should be already sorted
when needed). Otherwise it'd mean the decision needs to be done locally,
but I don't think that should be needed.

But it's surely a fairly invasive change to the patch ...

regards

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

Hi!

On Tue, Apr 3, 2018 at 2:10 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com>
wrote:

> I think solving this may be fairly straight-forward. Essentially, until
> now we only had one way to do the sort, so it was OK to make the sort
> implicit by checking if the path is sorted
>
> if (input not sorted)
> {
> ... add a Sort node ...
> }
>
> But now we have multiple possible ways to do the sort, with different
> startup/total costs. So the places that create the sorts need to
> actually generate the Sort paths for each sort alternative, and store
> the information in the Sort node (instead of relying on pathkeys).
>
> Ultimately, this should simplify the createplan.c places making all the
> make_sort calls unnecessary (i.e. the input should be already sorted
> when needed). Otherwise it'd mean the decision needs to be done locally,
> but I don't think that should be needed.
>
> But it's surely a fairly invasive change to the patch ...
>

Right, there are situation when incremental sort has lower startup cost,
but higher total cost. In order to find lower cost, we ideally should
generate
paths for both full sort and incremental sort. However, that would increase
number of total pathes, and could slowdown planning time. Another issue
that we don't always generate pathes for sort. And yes, it would be rather
invasive. So, that doesn't look feasible to get into 11.

Intead, I decided to cut usage of incremental sort. Now, incremental sort
is generated only in create_sort_path(). Cheaper path selected between
incremental sort and full sort with taking limit_tuples into account.
That limits usage of incremental sort, however risk of regression by this
patch is also minimal. In fact, incremental sort will be used only when
sort is explicitly specified and simultaneously LIMIT is specified or
dataset to be sorted is large and incremental sort saves disk IO.

Attached patch also incorporates following commits made by Alexander
Kuzmenkov:
* Rename fields of IncrementalSortState to snake_case for the sake of
consistency.
* Rename group test function to isCurrentGroup.
* Comments from Tomas Vondra about nodeIncrementalSort.c
* Add a test for incremental sort.
* Add a separate function to calculate costs of incremental sort.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 04/06/2018 01:43 AM, Alexander Korotkov wrote:
> Hi!
>
> On Tue, Apr 3, 2018 at 2:10 PM, Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com <mailto:tomas(dot)vondra(at)2ndquadrant(dot)com>> wrote:
>
> I think solving this may be fairly straight-forward. Essentially, until
> now we only had one way to do the sort, so it was OK to make the sort
> implicit by checking if the path is sorted
>
>     if (input not sorted)
>     {
>         ... add a Sort node ...
>     }
>
> But now we have multiple possible ways to do the sort, with different
> startup/total costs. So the places that create the sorts need to
> actually generate the Sort paths for each sort alternative, and store
> the information in the Sort node (instead of relying on pathkeys).
>
> Ultimately, this should simplify the createplan.c places making all the
> make_sort calls unnecessary (i.e. the input should be already sorted
> when needed). Otherwise it'd mean the decision needs to be done locally,
> but I don't think that should be needed.
>
> But it's surely a fairly invasive change to the patch ...
>
>
> Right, there are situation when incremental sort has lower startup cost,
> but higher total cost.  In order to find lower cost, we ideally should
> generate
> paths for both full sort and incremental sort.  However, that would increase
> number of total pathes, and could slowdown planning time.  Another issue
> that we don't always generate pathes for sort.  And yes, it would be rather
> invasive.  So, that doesn't look feasible to get into 11.
>

I agree that's probably not feasible for PG11, considering the freeze is
about 48h from now. Not necessarily because of amount of code needed to
do that (it might be fairly small, actually) but because of the risk of
regressions in other types of plans and lack of time for review/testing.

I do not think this would cause a significant increase in path number.
We already do have the (partially sorted) paths in pathlist, otherwise
v21 wouldn't be able to build the incremental sort path anyway. And the
plans that did the decision in createplan.c could fairly easily do the
decision when constructing the path, I believe.

Looking v21, this affects three different places:

1) create_merge_append_plan

For merge_append the issue is that generate_mergeappend_paths() calls
get_cheapest_path_for_pathkeys(), which however only looks at cheapest
startup/total path, and then simply falls-back to cheapest_total_path if
there are no suitably sorted paths. IMHO if you modify this to also
consider partially-sorted paths, it should work. You'll have to account
for the extra cost of incremental cost, and it needs to be fairly cheap
(perhaps even by first quickly computing some initial cost estimate -
see e.g. initial_cost_nestloop/final_cost_nestloop).

2) create_mergejoin_plan

For mergejoin, the issue is that sort_inner_and_outer() only looks at
cheapest_total_path for both sides, even before computing the merge
pathkeys. So some of the code would have to move into the foreach loop,
and the paths would be picked by get_cheapest_path_for_pathkeys(). This
time only using total cost, per the comment in sort_inner_and_outer().

3) create_gather_merge_plan

This seems fairly simple - the issue is that gather_grouping_paths()
only looks at cheapest_partial_path. Should be a matter of simply
calling the improved get_cheapest_path_for_pathkeys().

Of course, this is all fairly hand-wavy and it may turn out to be fairly
expensive in some cases. But we can use another trick - we don't need to
search through all partially sorted paths, because for each pathkey
prefix there can be just one "best" path for startup cost and one for
total cost. So we could maintain a much shorter list of partially sorted
paths, I think.

>
> Intead, I decided to cut usage of incremental sort.  Now, incremental sort
> is generated only in create_sort_path().  Cheaper path selected between
> incremental sort and full sort with taking limit_tuples into account.
> That limits usage of incremental sort, however risk of regression by this
> patch is also minimal.  In fact, incremental sort will be used only when
> sort is explicitly specified and simultaneously LIMIT is specified or
> dataset to be sorted is large and incremental sort saves disk IO.
>

I personally am OK with reducing the scope of the patch like this. It's
still beneficial for the common ORDER BY + LIMIT case, which is good. I
don't think it may negatively affect other cases (at least I can't think
of any).

It's pretty obvious it may be extremely useful for the other cases too
(particularly for mergejoin on large tables, where it can allow
in-memory sort with quick startup).

But even if you managed to make the necessary code changes, it's
unlikely any experienced committer will look into such significant
change this close to the cutoff. Either they are going to be away for a
weekend, or they are already looking at other patches :-(

> Attached patch also incorporates following commits made by Alexander
> Kuzmenkov:
> * Rename fields of IncrementalSortState to snake_case for the sake of
> consistency.
> * Rename group test function to isCurrentGroup.
> * Comments from Tomas Vondra about nodeIncrementalSort.c
> * Add a test for incremental sort.
> * Add a separate function to calculate costs of incremental sort.
>

Those changes seem fine, but are still a couple of issues remaining:

1) pathkeys_useful_for_ordering() still uses enable_incrementalsort,
which I think is a bad idea. I've complained about it in my review on
31/3, and I don't see any explanation why this is a good idea.

2) Likewise, I've suggested that the claim about abbreviated keys in
nodeIncrementalsort.c is dubious. No response, and the XXX comment was
instead merged into the patch:

* XXX The claim about abbreviated keys seems rather dubious, IMHO.

3) There is a comment at cost_merge_append, despite there being no
relevant changes in that function. Misplaced comment?

4) It's not clear to me why INITIAL_MEMTUPSIZE is defined the way it is.
There needs to be a comment - the intent seems to be making it large
enough to exceed ALLOCSET_SEPARATE_THRESHOLD, but it's not quite clear
why that's a good idea.

5) I do get this warning when building the code:

costsize.c: In function ‘cost_incremental_sort’:
costsize.c:1812:2: warning: ISO C90 forbids mixed declarations and code
[-Wdeclaration-after-statement]
List *presortedExprs = NIL;
^~~~

6) The comment at cost_incremental_sort talks about cost_sort_internal,
but it's cost_sort_tuplesort I guess.

7) The new code in create_sort_path is somewhat ugly, I guess. It's
correct, but it really needs to be made easier to comprehend. I might
have time to look into that tomorrow, but I can't promise that.

Attached is a diff highlighting some of those places, and couple of
minor code formatting fixes.

regards

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

Hi all,

This is the other Alexander K. speaking.

On 06.04.2018 20:26, Tomas Vondra wrote:
> I personally am OK with reducing the scope of the patch like this. It's
> still beneficial for the common ORDER BY + LIMIT case, which is good. I
> don't think it may negatively affect other cases (at least I can't think
> of any).

I think we can reduce it even further. Just try incremental sort along
with full sort over the cheapest path in create_ordered_paths, and don't
touch anything else. This is a very minimal and a probably safe start,
and then we can continue working on other, more complex cases. In the
attached patch I tried to do this. We probably should also remove
changes in make_sort() and create a separate function
make_incremental_sort() for it, but I'm done for today.

> 1) pathkeys_useful_for_ordering() still uses enable_incrementalsort,
> which I think is a bad idea. I've complained about it in my review on
> 31/3, and I don't see any explanation why this is a good idea.

Removed.

> 2) Likewise, I've suggested that the claim about abbreviated keys in
> nodeIncrementalsort.c is dubious. No response, and the XXX comment was
> instead merged into the patch:
>
> * XXX The claim about abbreviated keys seems rather dubious, IMHO.

Not sure about that, maybe just use abbreviated keys for the first
version? Later we can research this more closely and maybe start
deciding whether to use abbrev on planning stage.

> 3) There is a comment at cost_merge_append, despite there being no
> relevant changes in that function. Misplaced comment?

Removed.

> 4) It's not clear to me why INITIAL_MEMTUPSIZE is defined the way it is.
> There needs to be a comment - the intent seems to be making it large
> enough to exceed ALLOCSET_SEPARATE_THRESHOLD, but it's not quite clear
> why that's a good idea.

Not sure myself, let's ask the other Alexander.

> 5) I do get this warning when building the code:
>
> costsize.c: In function ‘cost_incremental_sort’:
> costsize.c:1812:2: warning: ISO C90 forbids mixed declarations and code
> [-Wdeclaration-after-statement]
> List *presortedExprs = NIL;
> ^~~~
>
> 6) The comment at cost_incremental_sort talks about cost_sort_internal,
> but it's cost_sort_tuplesort I guess.

Fixed.

> 7) The new code in create_sort_path is somewhat ugly, I guess. It's
> correct, but it really needs to be made easier to comprehend. I might
> have time to look into that tomorrow, but I can't promise that.

Removed this code altogether, now the costs are compared by add_path as
usual.

> Attached is a diff highlighting some of those places, and couple of
> minor code formatting fixes.

Applied.

Also some other changes from me:

Remove extra blank lines
label_sort_with_costsize shouldn't have to deal with IncrementalSort
plans, because they are only created from corresponding Path nodes.
Reword a comment in ExecSupportsBackwardsScan.
Clarify cost calculations.
enable_incrementalsort is checked at path level, we don't have to check
it again at plan level.
enable_sort should act as a cost-based soft disable for both incremental
and normal sort.

--
Alexander Kuzmenkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On Fri, Apr 6, 2018 at 11:40 PM, Alexander Kuzmenkov <
a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:

> On 06.04.2018 20:26, Tomas Vondra wrote:
>
>> I personally am OK with reducing the scope of the patch like this. It's
>> still beneficial for the common ORDER BY + LIMIT case, which is good. I
>> don't think it may negatively affect other cases (at least I can't think
>> of any).
>>
>
> I think we can reduce it even further. Just try incremental sort along
> with full sort over the cheapest path in create_ordered_paths, and don't
> touch anything else. This is a very minimal and a probably safe start, and
> then we can continue working on other, more complex cases. In the attached
> patch I tried to do this. We probably should also remove changes in
> make_sort() and create a separate function make_incremental_sort() for it,
> but I'm done for today.

I've done further unwedding of sort and incremental sort providing them
separate function for plan createion.

2) Likewise, I've suggested that the claim about abbreviated keys in
>>
> nodeIncrementalsort.c is dubious. No response, and the XXX comment was
>> instead merged into the patch:
>>
>> * XXX The claim about abbreviated keys seems rather dubious, IMHO.
>>
>
> Not sure about that, maybe just use abbreviated keys for the first
> version? Later we can research this more closely and maybe start deciding
> whether to use abbrev on planning stage.

That comes from time when we're trying to make incremental sort to be always
not worse than full sort. Now, we have separate paths for full and
incremental sorts,
and some costing penalty for incremental sort. So, incremental sort should
be
selected only when it's expected to give big win. Thus, we can give up
with this
optimization at least in the initial version.

So, removed.

4) It's not clear to me why INITIAL_MEMTUPSIZE is defined the way it is.
>> There needs to be a comment - the intent seems to be making it large
>> enough to exceed ALLOCSET_SEPARATE_THRESHOLD, but it's not quite clear
>> why that's a good idea.
>>
>
> Not sure myself, let's ask the other Alexander.

I've added comment to INITIAL_MEMTUPSIZE. However, to be fair it's not
invention of this patch. Initial size of memtuples array was so previously.
What this patch did is just move it to the macro.

Also, this note hadn't been adressed yet.

On Sat, Mar 31, 2018 at 11:43 PM, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com
> wrote:

> I'm wondering if a static MIN_GROUP_SIZE is good idea. For example, what
> if the subplan is expected to return only very few tuples (say, 33), but
> the query includes LIMIT 1. Now, let's assume the startup/total cost of
> the subplan is 1 and 1000000. With MIN_GROUP_SIZE 32 we're bound to
> execute it pretty much till the end, while we could terminate after the
> first tuple (if the prefix changes).
>
> So I think we should use a Min(limit,MIN_GROUP_SIZE) here, and perhaps
> this should depend on average group size too.
>

I agree with that. For bounded sort, attached patch now selects minimal
group
size as Min(DEFAULT_MIN_GROUP_SIZE, bound). That should improve
"LIMIT small_number" case.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company