From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: James Coleman <jtc331@gmail.com>
Cc: Peter Geoghegan <pg@bowt.ie>
Cc: Simon Riggs <simon@2ndquadrant.com>
Cc: Rafia Sabih <rafia.pghackers@gmail.com>
Cc: Shaun Thomas <shaun.thomas@2ndquadrant.com>
Cc: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Alexander Korotkov <a.korotkov@postgrespro.ru>
Cc: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
Date: Sun, 7 Jul 2019 14:34:49 +0200
Message-ID: <20190707123449.w3b2vetwv4y42evj@development> (raw)
In-Reply-To: <CAAaqYe8PVSO3dzysZZ-RB8HRMAZ_JMOPwW--veY9ZEuTCcbe8A@mail.gmail.com>
References: <CAAaqYe9pzNZnF328bFZfzR8zJK9Mvft3i6TN0NjxjCkWeVm1iQ@mail.gmail.com>
<20190625160235.6ctryjzvw5je7cet@development>
<CAAaqYe_JMQh0FeSSynr_j66ZNNiX3BjKoLiMgMF4zna1m0tcVg@mail.gmail.com>
<CAH2-Wz=ptCW_dnRi3z4n8eUCzc82Y2qsd9ReWLr0-nxfhh=Hsg@mail.gmail.com>
<CAAaqYe_pPWgcgjM5OVkwwgDPn9e63ZjFbv6ychiuHF_22B-FjQ@mail.gmail.com>
<CAH2-Wz=L8dZNttnvSXvH6NTMWw2T5VsBBC4oU4tLTMV9CoLRvg@mail.gmail.com>
<20190625203207.lvmmat7d2ilnr64t@development>
<CAAaqYe-i7D+D+oih1AZ5QyyAMSWKjzNT7+eBz-RMr9i18zG96g@mail.gmail.com>
<20190625232205.ssecrwplyb7faxbb@development>
<CAAaqYe8PVSO3dzysZZ-RB8HRMAZ_JMOPwW--veY9ZEuTCcbe8A@mail.gmail.com>
On Thu, Jul 04, 2019 at 09:29:49AM -0400, James Coleman wrote:
>On Tue, Jun 25, 2019 at 7:22 PM Tomas Vondra
><tomas.vondra@2ndquadrant.com> wrote:
>>
>> On Tue, Jun 25, 2019 at 04:53:40PM -0400, James Coleman wrote:
>> >
>> >Unrelated: if you or someone else you know that's more familiar with
>> >the parallel code, I'd be interested in their looking at the patch at
>> >some point, because I have a suspicion it might not be operating in
>...
>> So I've looked into that, and the reason seems fairly simple - when
>> generating the Gather Merge paths, we only look at paths that are in
>> partial_pathlist. See generate_gather_paths().
>>
>> And we only have sequential + index paths in partial_pathlist, not
>> incremental sort paths.
>>
>> IMHO we can do two things:
>>
>> 1) modify generate_gather_paths to also consider incremental sort for
>> each sorted path, similarly to what create_ordered_paths does
>>
>> 2) modify build_index_paths to also generate an incremental sort path
>> for each index path
>>
>> IMHO (1) is the right choice here, because it automatically does the
>> trick for all other types of ordered paths, not just index scans. So,
>> something like the attached patch, which gives me plans like this:
>...
>> But I'm not going to claim those are total fixes, it's the minimum I
>> needed to do to make this particular type of plan work.
>
>Thanks for looking into this!
>
>I intended to apply this to my most recent version of the patch (just
>sent a few minutes ago), but when I apply it I noticed that the
>partition_aggregate regression tests have several of these failures:
>
>ERROR: could not find pathkey item to sort
>
>I haven't had time to look into the cause yet, so I decided to wait
>until the next patch revision.
>
I wanted to investigate this today, but I can't reprodure it. How are
you building and running the regression tests?
Attached is a patch adding the incremental sort below gather merge, and
also tweaking the costing. But that's mostly for and better planning
decisions, I don't get any pathkey errors even with the first patch.
regards
--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 3efc807164..d7bf33f64d 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -2719,6 +2719,8 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
{
Path *subpath = (Path *) lfirst(lc);
GatherMergePath *path;
+ bool is_sorted;+ int presorted_keys;
if (subpath->pathkeys == NIL)
continue;
@@ -2727,6 +2729,26 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
subpath->pathkeys, NULL, rowsp);
add_path(rel, &path->path);
++ /* consider incremental sort */+ is_sorted = pathkeys_common_contained_in(root->sort_pathkeys,+ subpath->pathkeys, &presorted_keys);++ if (!is_sorted && (presorted_keys > 0))+ {+ /* Also consider incremental sort. */+ subpath = (Path *) create_incremental_sort_path(root,+ rel,+ subpath,+ root->sort_pathkeys,+ presorted_keys,+ -1);++ path = create_gather_merge_path(root, rel, subpath, rel->reltarget,+ subpath->pathkeys, NULL, rowsp);++ add_path(rel, &path->path);+ }
}
}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex 7f820e7351..c6aa17ba67 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -1875,16 +1875,8 @@ cost_incremental_sort(Path *path,
limit_tuples);
/* If we have a LIMIT, adjust the number of groups we'll have to return. */
- if (limit_tuples > 0 && limit_tuples < input_tuples)- {- output_tuples = limit_tuples;- output_groups = floor(output_tuples / group_tuples) + 1;- }- else- {- output_tuples = input_tuples;- output_groups = input_groups;- }+ output_tuples = input_tuples;+ output_groups = input_groups;
/*
* Startup cost of incremental sort is the startup cost of its first group
Attachments:
[text/plain] parallel-incremental-sort-v2.patch (2.0K, ../20190707123449.w3b2vetwv4y42evj@development/2-parallel-incremental-sort-v2.patch)
download | inline diff:diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.cindex 3efc807164..d7bf33f64d 100644--- a/src/backend/optimizer/path/allpaths.c+++ b/src/backend/optimizer/path/allpaths.c@@ -2719,6 +2719,8 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
{
Path *subpath = (Path *) lfirst(lc);
GatherMergePath *path;
+ bool is_sorted;+ int presorted_keys;
if (subpath->pathkeys == NIL)
continue;
@@ -2727,6 +2729,26 @@ generate_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_rows)
path = create_gather_merge_path(root, rel, subpath, rel->reltarget,
subpath->pathkeys, NULL, rowsp);
add_path(rel, &path->path);
++ /* consider incremental sort */+ is_sorted = pathkeys_common_contained_in(root->sort_pathkeys,+ subpath->pathkeys, &presorted_keys);++ if (!is_sorted && (presorted_keys > 0))+ {+ /* Also consider incremental sort. */+ subpath = (Path *) create_incremental_sort_path(root,+ rel,+ subpath,+ root->sort_pathkeys,+ presorted_keys,+ -1);++ path = create_gather_merge_path(root, rel, subpath, rel->reltarget,+ subpath->pathkeys, NULL, rowsp);++ add_path(rel, &path->path);+ }
}
}
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.cindex 7f820e7351..c6aa17ba67 100644--- a/src/backend/optimizer/path/costsize.c+++ b/src/backend/optimizer/path/costsize.c@@ -1875,16 +1875,8 @@ cost_incremental_sort(Path *path,
limit_tuples);
/* If we have a LIMIT, adjust the number of groups we'll have to return. */
- if (limit_tuples > 0 && limit_tuples < input_tuples)- {- output_tuples = limit_tuples;- output_groups = floor(output_tuples / group_tuples) + 1;- }- else- {- output_tuples = input_tuples;- output_groups = input_groups;- }+ output_tuples = input_tuples;+ output_groups = input_groups;
/*
* Startup cost of incremental sort is the startup cost of its first group
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: tomas.vondra@2ndquadrant.com, jtc331@gmail.com, pg@bowt.ie, simon@2ndquadrant.com, rafia.pghackers@gmail.com, shaun.thomas@2ndquadrant.com, 9erthalion6@gmail.com, a.korotkov@postgrespro.ru, tgl@sss.pgh.pa.us, pgsql-hackers@lists.postgresql.org
Subject: Re: [PATCH] Incremental sort (was: PoC: Partial sort)
In-Reply-To: <20190707123449.w3b2vetwv4y42evj@development>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox