Some revises in adding sorting path
While reviewing [1]/messages/by-id/CAApHDvo8Lz2H=42urBbfP65LTcEUOh288MT7DsG2_EWtW1AXHQ@mail.gmail.com, I visited other places where sorting is needed, and
have some findings.
In add_paths_with_pathkeys_for_rel, we do not try incremental sort atop
of the epq_path, which I think we can do. I'm not sure how useful this
is in real world since the epq_path is used only for EPQ checks, but it
seems doing that doesn't cost too much.
In create_ordered_paths, we are trying to sort the cheapest partial path
and incremental sort on any partial paths with presorted keys, and then
use Gather Merge. If the cheapest partial path is not completely sorted
but happens to have presorted keys, we would create a full sort path and
an incremental sort path on it. I think this is not what we want. We
are supposed to only create an incremental sort path if there are
presorted keys.
In gather_grouping_paths, we have the same issue. In addition, for the
incremental sort paths created atop partial paths, we neglect to
calculate 'total_groups' before we use it in create_gather_merge_path.
[1]: /messages/by-id/CAApHDvo8Lz2H=42urBbfP65LTcEUOh288MT7DsG2_EWtW1AXHQ@mail.gmail.com
/messages/by-id/CAApHDvo8Lz2H=42urBbfP65LTcEUOh288MT7DsG2_EWtW1AXHQ@mail.gmail.com
Thanks
Richard
Attachments:
v1-0003-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchapplication/octet-stream; name=v1-0003-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchDownload
From eba72b5998d8d51605c6fea535569464c3a4770f Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 10 Jan 2023 17:17:14 +0800
Subject: [PATCH v1 3/3] Revise how we sort partial paths in
gather_grouping_paths
---
src/backend/optimizer/plan/planner.c | 68 +++++++++++-----------------
1 file changed, 27 insertions(+), 41 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 9f22bcbf1a..29fa2e6bcc 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -7191,42 +7191,8 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
/* Try Gather for unordered paths and Gather Merge for ordered ones. */
generate_useful_gather_paths(root, rel, true);
- /* Try cheapest partial path + explicit Sort + Gather Merge. */
cheapest_partial_path = linitial(rel->partial_pathlist);
- if (!pathkeys_contained_in(root->group_pathkeys,
- cheapest_partial_path->pathkeys))
- {
- Path *path;
- double total_groups;
-
- total_groups =
- cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
- path = (Path *) create_sort_path(root, rel, cheapest_partial_path,
- root->group_pathkeys,
- -1.0);
- path = (Path *)
- create_gather_merge_path(root,
- rel,
- path,
- rel->reltarget,
- root->group_pathkeys,
- NULL,
- &total_groups);
-
- add_path(rel, path);
- }
-
- /*
- * Consider incremental sort on all partial paths, if enabled.
- *
- * We can also skip the entire loop when we only have a single-item
- * group_pathkeys because then we can't possibly have a presorted prefix
- * of the list without having the list be fully sorted.
- */
- if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1)
- return;
- /* also consider incremental sort on partial paths, if enabled */
foreach(lc, rel->partial_pathlist)
{
Path *path = (Path *) lfirst(lc);
@@ -7241,15 +7207,35 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
if (is_sorted)
continue;
- if (presorted_keys == 0)
+ /*
+ * Try at least sorting the cheapest path and also try
+ * incrementally sorting any path which is partially sorted
+ * already (no need to deal with paths which have presorted
+ * keys when incremental sort is disabled unless it's the
+ * cheapest input path).
+ */
+ if (path != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
continue;
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
+ total_groups = path->rows * path->parallel_workers;
+
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root, rel, path,
+ root->group_pathkeys,
+ -1.0);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
path = (Path *)
create_gather_merge_path(root,
--
2.31.0
v1-0002-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchapplication/octet-stream; name=v1-0002-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchDownload
From 744c94b9be05a4195a167bb9360e2f8769dd524f Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 10 Jan 2023 16:40:39 +0800
Subject: [PATCH v1 2/3] Revise how we sort partial paths in
create_ordered_paths
---
src/backend/optimizer/plan/planner.c | 124 +++++++++++----------------
1 file changed, 48 insertions(+), 76 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 000d757bdd..9f22bcbf1a 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -5045,97 +5045,69 @@ create_ordered_paths(PlannerInfo *root,
cheapest_partial_path = linitial(input_rel->partial_pathlist);
- /*
- * If cheapest partial path doesn't need a sort, this is redundant
- * with what's already been tried.
- */
- if (!pathkeys_contained_in(root->sort_pathkeys,
- cheapest_partial_path->pathkeys))
+ foreach(lc, input_rel->partial_pathlist)
{
- Path *path;
+ Path *input_path = (Path *) lfirst(lc);
+ Path *sorted_path;
+ bool is_sorted;
+ int presorted_keys;
double total_groups;
- path = (Path *) create_sort_path(root,
- ordered_rel,
- cheapest_partial_path,
- root->sort_pathkeys,
- limit_tuples);
-
- total_groups = cheapest_partial_path->rows *
- cheapest_partial_path->parallel_workers;
- path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- path,
- path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (path->pathtarget != target)
- path = apply_projection_to_path(root, ordered_rel,
- path, target);
-
- add_path(ordered_rel, path);
- }
+ is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
+ input_path->pathkeys,
+ &presorted_keys);
- /*
- * Consider incremental sort with a gather merge on partial paths.
- *
- * We can also skip the entire loop when we only have a single-item
- * sort_pathkeys because then we can't possibly have a presorted
- * prefix of the list without having the list be fully sorted.
- */
- if (enable_incremental_sort && list_length(root->sort_pathkeys) > 1)
- {
- foreach(lc, input_rel->partial_pathlist)
- {
- Path *input_path = (Path *) lfirst(lc);
- Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
- double total_groups;
+ /* No point in adding incremental sort on fully sorted paths. */
+ if (is_sorted)
+ continue;
- /*
- * We don't care if this is the cheapest partial path - we
- * can't simply skip it, because it may be partially sorted in
- * which case we want to consider adding incremental sort
- * (instead of full sort, which is what happens above).
- */
+ /*
+ * Try at least sorting the cheapest path and also try
+ * incrementally sorting any path which is partially sorted
+ * already (no need to deal with paths which have presorted
+ * keys when incremental sort is disabled unless it's the
+ * cheapest input path).
+ */
+ if (input_path != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
- is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ sorted_path = (Path *) create_sort_path(root,
+ ordered_rel,
+ input_path,
+ root->sort_pathkeys,
+ limit_tuples);
- /* No point in adding incremental sort on fully sorted paths. */
- if (is_sorted)
- continue;
- if (presorted_keys == 0)
- continue;
- /* Since we have presorted keys, consider incremental sort. */
+ else
sorted_path = (Path *) create_incremental_sort_path(root,
ordered_rel,
input_path,
root->sort_pathkeys,
presorted_keys,
limit_tuples);
- total_groups = input_path->rows *
- input_path->parallel_workers;
- sorted_path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- sorted_path,
- sorted_path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (sorted_path->pathtarget != target)
- sorted_path = apply_projection_to_path(root, ordered_rel,
- sorted_path, target);
-
- add_path(ordered_rel, sorted_path);
- }
+ total_groups = input_path->rows *
+ input_path->parallel_workers;
+ sorted_path = (Path *)
+ create_gather_merge_path(root, ordered_rel,
+ sorted_path,
+ sorted_path->pathtarget,
+ root->sort_pathkeys, NULL,
+ &total_groups);
+
+ /* Add projection step if needed */
+ if (sorted_path->pathtarget != target)
+ sorted_path = apply_projection_to_path(root, ordered_rel,
+ sorted_path, target);
+
+ add_path(ordered_rel, sorted_path);
}
}
--
2.31.0
v1-0001-postgres_fdw-Allow-incremental-sort-atop-of-the-epq_path.patchapplication/octet-stream; name=v1-0001-postgres_fdw-Allow-incremental-sort-atop-of-the-epq_path.patchDownload
From 7f639719e8c1a4a06614dd50960377ffdba8fb31 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Tue, 10 Jan 2023 16:03:56 +0800
Subject: [PATCH v1 1/3] postgres_fdw: Allow incremental sort atop of the
epq_path
---
.../postgres_fdw/expected/postgres_fdw.out | 43 +++++++++++++++++++
contrib/postgres_fdw/postgres_fdw.c | 42 ++++++++++++++----
contrib/postgres_fdw/sql/postgres_fdw.sql | 5 +++
3 files changed, 81 insertions(+), 9 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index c0267a99d2..d3b559d10a 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2553,6 +2553,49 @@ SELECT * FROM local_tbl LEFT JOIN (SELECT ft1.* FROM ft1 INNER JOIN ft2 ON (ft1.
ALTER SERVER loopback OPTIONS (DROP fdw_startup_cost);
ALTER SERVER loopback OPTIONS (ADD extensions 'postgres_fdw');
DROP TABLE local_tbl;
+-- test that add_paths_with_pathkeys_for_rel() allows incremental sort atop of the epq_path
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNER JOIN (SELECT t2.c1, t3.c1, t3.c2 FROM (SELECT c1 FROM ft4 WHERE c1 between 50 and 60) t2 INNER JOIN (SELECT c1, c2 FROM ft5 WHERE c1 between 50 and 60) t3 ON (t2.c1 = t3.c1) ) ss(a, b, c) ON (TRUE) ORDER BY t1.c1, ss.a, ss.b, ss.c FOR UPDATE OF t1;
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
+ LockRows
+ Output: "T 3".c1, ft4.c1, ft5.c1, ft5.c2, "T 3".ctid, ft4.*, ft5.*
+ -> Nested Loop
+ Output: "T 3".c1, ft4.c1, ft5.c1, ft5.c2, "T 3".ctid, ft4.*, ft5.*
+ -> Foreign Scan
+ Output: ft4.c1, ft4.*, ft5.c1, ft5.c2, ft5.*
+ Relations: (public.ft4) INNER JOIN (public.ft5)
+ Remote SQL: SELECT r8.c1, CASE WHEN (r8.*)::text IS NOT NULL THEN ROW(r8.c1, r8.c2, r8.c3) END, r9.c1, r9.c2, CASE WHEN (r9.*)::text IS NOT NULL THEN ROW(r9.c1, r9.c2, r9.c3) END FROM ("S 1"."T 3" r8 INNER JOIN "S 1"."T 4" r9 ON (((r8.c1 = r9.c1)) AND ((r9.c1 >= 50)) AND ((r9.c1 <= 60)) AND ((r8.c1 >= 50)) AND ((r8.c1 <= 60)))) ORDER BY r8.c1 ASC NULLS LAST, r9.c2 ASC NULLS LAST
+ -> Incremental Sort
+ Output: ft4.c1, ft4.*, ft5.c1, ft5.c2, ft5.*
+ Sort Key: ft4.c1, ft5.c2
+ Presorted Key: ft4.c1
+ -> Merge Join
+ Output: ft4.c1, ft4.*, ft5.c1, ft5.c2, ft5.*
+ Merge Cond: (ft4.c1 = ft5.c1)
+ -> Sort
+ Output: ft4.c1, ft4.*
+ Sort Key: ft4.c1
+ -> Foreign Scan on public.ft4
+ Output: ft4.c1, ft4.*
+ Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 3" WHERE ((c1 >= 50)) AND ((c1 <= 60))
+ -> Materialize
+ Output: ft5.c1, ft5.c2, ft5.*
+ -> Foreign Scan on public.ft5
+ Output: ft5.c1, ft5.c2, ft5.*
+ Remote SQL: SELECT c1, c2, c3 FROM "S 1"."T 4" WHERE ((c1 >= 50)) AND ((c1 <= 60)) ORDER BY c1 ASC NULLS LAST, c2 ASC NULLS LAST
+ -> Seq Scan on "S 1"."T 3"
+ Output: "T 3".c1, "T 3".ctid
+ Filter: ("T 3".c1 = 50)
+(29 rows)
+
+SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNER JOIN (SELECT t2.c1, t3.c1, t3.c2 FROM (SELECT c1 FROM ft4 WHERE c1 between 50 and 60) t2 INNER JOIN (SELECT c1, c2 FROM ft5 WHERE c1 between 50 and 60) t3 ON (t2.c1 = t3.c1) ) ss(a, b, c) ON (TRUE) ORDER BY t1.c1, ss.a, ss.b, ss.c FOR UPDATE OF t1;
+ c1 | a | b
+----+----+----
+ 50 | 54 | 54
+ 50 | 60 | 60
+(2 rows)
+
-- check join pushdown in situations where multiple userids are involved
CREATE ROLE regress_view_owner SUPERUSER;
CREATE USER MAPPING FOR regress_view_owner SERVER loopback;
diff --git a/contrib/postgres_fdw/postgres_fdw.c b/contrib/postgres_fdw/postgres_fdw.c
index 53f890bb48..cec50a6926 100644
--- a/contrib/postgres_fdw/postgres_fdw.c
+++ b/contrib/postgres_fdw/postgres_fdw.c
@@ -6066,15 +6066,39 @@ add_paths_with_pathkeys_for_rel(PlannerInfo *root, RelOptInfo *rel,
* case it gets used as input to a mergejoin.
*/
sorted_epq_path = epq_path;
- if (sorted_epq_path != NULL &&
- !pathkeys_contained_in(useful_pathkeys,
- sorted_epq_path->pathkeys))
- sorted_epq_path = (Path *)
- create_sort_path(root,
- rel,
- sorted_epq_path,
- useful_pathkeys,
- -1.0);
+ if (sorted_epq_path != NULL)
+ {
+ bool is_sorted;
+ int presorted_keys;
+
+ is_sorted = pathkeys_count_contained_in(useful_pathkeys,
+ sorted_epq_path->pathkeys,
+ &presorted_keys);
+
+ if (!is_sorted)
+ {
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ sorted_epq_path = (Path *)
+ create_sort_path(root,
+ rel,
+ sorted_epq_path,
+ useful_pathkeys,
+ -1.0);
+ else
+ sorted_epq_path = (Path *)
+ create_incremental_sort_path(root,
+ rel,
+ sorted_epq_path,
+ useful_pathkeys,
+ presorted_keys,
+ -1.0);
+ }
+ }
if (IS_SIMPLE_REL(rel))
add_path(rel, (Path *)
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index c37aa80383..5711f50690 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -687,6 +687,11 @@ ALTER SERVER loopback OPTIONS (ADD extensions 'postgres_fdw');
DROP TABLE local_tbl;
+-- test that add_paths_with_pathkeys_for_rel() allows incremental sort atop of the epq_path
+EXPLAIN (VERBOSE, COSTS OFF)
+SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNER JOIN (SELECT t2.c1, t3.c1, t3.c2 FROM (SELECT c1 FROM ft4 WHERE c1 between 50 and 60) t2 INNER JOIN (SELECT c1, c2 FROM ft5 WHERE c1 between 50 and 60) t3 ON (t2.c1 = t3.c1) ) ss(a, b, c) ON (TRUE) ORDER BY t1.c1, ss.a, ss.b, ss.c FOR UPDATE OF t1;
+SELECT t1.c1, ss.a, ss.b FROM (SELECT c1 FROM "S 1"."T 3" WHERE c1 = 50) t1 INNER JOIN (SELECT t2.c1, t3.c1, t3.c2 FROM (SELECT c1 FROM ft4 WHERE c1 between 50 and 60) t2 INNER JOIN (SELECT c1, c2 FROM ft5 WHERE c1 between 50 and 60) t3 ON (t2.c1 = t3.c1) ) ss(a, b, c) ON (TRUE) ORDER BY t1.c1, ss.a, ss.b, ss.c FOR UPDATE OF t1;
+
-- check join pushdown in situations where multiple userids are involved
CREATE ROLE regress_view_owner SUPERUSER;
CREATE USER MAPPING FOR regress_view_owner SERVER loopback;
--
2.31.0
I looked at the three patches and have some thoughts:
0001:
Does the newly added test have to be this complex? I think it might
be better to just come up with the most simple test you can that uses
an incremental sort. I really can't think why the test requires a FOR
UPDATE, to test incremental sort, for example. The danger with making
a test more complex than it needs to be is that it frequently gets
broken by unrelated changes. The complexity makes it harder for
people to understand the test's intentions and that increases the risk
that the test eventually does not test what it was originally meant to
test as the underlying code changes and the expected output is
updated.
0002:
I think the following existing comment does not seem to be true any longer:
However, there's one more
* possibility: it may make sense to sort the cheapest partial path
* according to the required output order and then use Gather Merge.
You've removed the comment that talks about trying Incremental Sort ->
Gather Merge paths yet the code is still doing that, the two are just
more consolidated now, so perhaps you need to come up with a new
comment to explain what we're trying to achieve.
* already (no need to deal with paths which have presorted
* keys when incremental sort is disabled unless it's the
* cheapest input path).
I think "input path" should be "partial path". (I maybe didn't get
that right in all places in 4a29eabd1).
0003:
Looking at gather_grouping_paths(), I see it calls
generate_useful_gather_paths() which generates a bunch of Gather Merge
paths after sorting the cheapest path and incrementally sorting any
partially sorted paths. Then back in gather_grouping_paths(), we go
and create Gather Merge paths again, but this time according to the
group_pathkeys instead of the query_pathkeys. I know you're not really
changing anything here, but as I'm struggling to understand why
exactly we're creating two sets of Gather Merge paths, it makes it a
bit scary to consider changing anything in this area. I've not really
found any comments that can explain to me sufficiently well enough so
that I understand why this needs to be done. Do you know?
David
Hi Richard,
On Tue, Jan 10, 2023 at 8:06 PM Richard Guo <guofenglinux@gmail.com> wrote:
In add_paths_with_pathkeys_for_rel, we do not try incremental sort atop
of the epq_path, which I think we can do. I'm not sure how useful this
is in real world since the epq_path is used only for EPQ checks, but it
seems doing that doesn't cost too much.
I'm not sure this is a good idea, because the epq_path will return at
most one tuple in an EPQ recheck.
The reason why an extra Sort node is injected into the epq_path is
only label it with the correct sort order to use it as an input for
the EPQ merge-join path of a higher-level foreign join, so shouldn't
we keep this step as much as simple and save cycles even a little?
Sorry for being late to the party.
Best regards,
Etsuro Fujita
On Thu, Feb 16, 2023 at 7:50 PM Etsuro Fujita <etsuro.fujita@gmail.com>
wrote:
I'm not sure this is a good idea, because the epq_path will return at
most one tuple in an EPQ recheck.The reason why an extra Sort node is injected into the epq_path is
only label it with the correct sort order to use it as an input for
the EPQ merge-join path of a higher-level foreign join, so shouldn't
we keep this step as much as simple and save cycles even a little?
Agreed. Thanks for the explanation. I also wondered whether it's
worthwhile to do the change here. I'll remove the 0001 patch.
Thanks
Richard
On Tue, Feb 14, 2023 at 10:53 AM David Rowley <dgrowleyml@gmail.com> wrote:
I looked at the three patches and have some thoughts:
Thanks for reviewing!
0001:
Does the newly added test have to be this complex? I think it might
be better to just come up with the most simple test you can that uses
an incremental sort. I really can't think why the test requires a FOR
UPDATE, to test incremental sort, for example. The danger with making
a test more complex than it needs to be is that it frequently gets
broken by unrelated changes. The complexity makes it harder for
people to understand the test's intentions and that increases the risk
that the test eventually does not test what it was originally meant to
test as the underlying code changes and the expected output is
updated.
That makes sense. I agree that we should always use the minimal query
for test. For this patch, as pointed by Etsuro, it may not be a good
idea for the change. So I'll remove 0001.
0002:
I think the following existing comment does not seem to be true any longer:
However, there's one more
* possibility: it may make sense to sort the cheapest partial path
* according to the required output order and then use Gather Merge.You've removed the comment that talks about trying Incremental Sort ->
Gather Merge paths yet the code is still doing that, the two are just
more consolidated now, so perhaps you need to come up with a new
comment to explain what we're trying to achieve.
Yes, you are right. How about the comment below?
- * possibility: it may make sense to sort the cheapest partial path
- * according to the required output order and then use Gather Merge.
+ * possibility: it may make sense to sort the cheapest partial path or
+ * incrementally sort any partial path that is partially sorted according
+ * to the required output order and then use Gather Merge.Looking at the codes now I have some concern that what we do in
create_ordered_paths for partial paths may have already been done in
generate_useful_gather_paths, especially when query_pathkeys is equal to
sort_pathkeys. Not sure if this is a problem. And the comment there
mentions generate_gather_paths(), but ISTM we should mention what
generate_useful_gather_paths has done.
0003:
Looking at gather_grouping_paths(), I see it calls
generate_useful_gather_paths() which generates a bunch of Gather Merge
paths after sorting the cheapest path and incrementally sorting any
partially sorted paths. Then back in gather_grouping_paths(), we go
and create Gather Merge paths again, but this time according to the
group_pathkeys instead of the query_pathkeys. I know you're not really
changing anything here, but as I'm struggling to understand why
exactly we're creating two sets of Gather Merge paths, it makes it a
bit scary to consider changing anything in this area. I've not really
found any comments that can explain to me sufficiently well enough so
that I understand why this needs to be done. Do you know?
I'm also not sure why gather_grouping_paths creates Gather Merge paths
according to group_pathkeys after what generate_useful_gather_paths has
done. There is comment that mentions this but seems more explanation is
needed.
* generate_useful_gather_paths does most of the work, but we also consider a
* special case: we could try sorting the data by the group_pathkeys and then
* applying Gather Merge.
It seems that if there is available group_pathkeys, we will set
query_pathkeys to group_pathkeys because we want the result sorted for
grouping. In this case gather_grouping_paths may just generate
duplicate Gather Merge paths because generate_useful_gather_paths has
generated Gather Merge paths according to query_pathkeys. I tried to
reduce the code of gather_grouping_paths to just call
generate_useful_gather_paths and found no diffs in regression tests.
Thanks
Richard
On Tue, 21 Feb 2023 at 22:02, Richard Guo <guofenglinux@gmail.com> wrote:
Looking at the codes now I have some concern that what we do in
create_ordered_paths for partial paths may have already been done in
generate_useful_gather_paths, especially when query_pathkeys is equal to
sort_pathkeys. Not sure if this is a problem. And the comment there
mentions generate_gather_paths(), but ISTM we should mention what
generate_useful_gather_paths has done.
I think you need to write some tests for this. I've managed to come up
with something to get that code to perform a Sort, but I've not
managed to get it to perform an incremental sort.
create or replace function parallel_safe_volatile(a int) returns int
as $$ begin return a; end; $$ parallel safe volatile language plpgsql;
create table abc(a int, b int, c int);
insert into abc select x,y,z from generate_Series(1,100)x,
generate_Series(1,100)y, generate_Series(1,100)z;
set parallel_tuple_cost=0;
Without making those parallel paths, we get:
postgres=# explain select * from abc where a=1 order by
a,b,parallel_safe_volatile(c);
QUERY PLAN
--------------------------------------------------------------------------------
Sort (cost=13391.49..13417.49 rows=10400 width=16)
Sort Key: b, (parallel_safe_volatile(c))
-> Gather (cost=1000.00..12697.58 rows=10400 width=16)
Workers Planned: 2
-> Parallel Seq Scan on abc (cost=0.00..11697.58 rows=4333 width=16)
Filter: (a = 1)
(6 rows)
but with, the plan is:
postgres=# explain select * from abc where a=1 order by
a,b,parallel_safe_volatile(c);
QUERY PLAN
--------------------------------------------------------------------------------
Gather Merge (cost=12959.35..13060.52 rows=8666 width=16)
Workers Planned: 2
-> Sort (cost=11959.32..11970.15 rows=4333 width=16)
Sort Key: b, (parallel_safe_volatile(c))
-> Parallel Seq Scan on abc (cost=0.00..11697.58 rows=4333 width=16)
Filter: (a = 1)
(6 rows)
I added the parallel safe and volatile function so that
get_useful_pathkeys_for_relation() wouldn't include all of the
query_pathkeys.
If you write some tests for this code, it will be useful to prove that
it actually does something, and also that it does not break again in
the future. I don't really want to just blindly copy the pattern used
in 3c6fc5820 for creating incremental sort paths if it's not useful
here. It would be good to see tests that make an Incremental Sort path
using the code you're changing.
Same for the 0003 patch.
I'll mark this as waiting on author while you work on that.
David
On 28 Mar 2023, at 21:59, David Rowley <dgrowleyml@gmail.com> wrote:
I'll mark this as waiting on author while you work on that.
Richard: have you had a chance to incorporate the tests proposed by David in
this thread into your patch?
--
Daniel Gustafsson
On Wed, Mar 29, 2023 at 4:00 AM David Rowley <dgrowleyml@gmail.com> wrote:
If you write some tests for this code, it will be useful to prove that
it actually does something, and also that it does not break again in
the future. I don't really want to just blindly copy the pattern used
in 3c6fc5820 for creating incremental sort paths if it's not useful
here. It would be good to see tests that make an Incremental Sort path
using the code you're changing.
Thanks for the suggestion. I've managed to come up with a query that
gets the codes being changed here to perform an incremental sort.
set min_parallel_index_scan_size to 0;
set enable_seqscan to off;
Without making those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred,
parallel_safe_volatile(thousand);
QUERY PLAN
--------------------------------------------------------------
Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Gather Merge
Workers Planned: 3
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)
and with those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred,
parallel_safe_volatile(thousand);
QUERY PLAN
---------------------------------------------------------------
Gather Merge
Workers Planned: 3
-> Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)
I've added two tests for the code changes in create_ordered_paths in the
new patch.
Same for the 0003 patch.
For the code changes in gather_grouping_paths, I've managed to come up
with a query that makes an explicit Sort atop cheapest partial path.
explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Gather Merge
Workers Planned: 4
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)
Without this logic the plan would look like:
explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Gather
Workers Planned: 4
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)
This test is also added in the new patch.
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.
So update the patches to v2.
Thanks
Richard
Attachments:
v2-0001-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchapplication/octet-stream; name=v2-0001-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchDownload
From d3670fd7245d01d5878b066b600f7e846fb553bb Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 17 Jul 2023 14:07:39 +0800
Subject: [PATCH v2 1/2] Revise how we sort partial paths in
create_ordered_paths
---
src/backend/optimizer/plan/planner.c | 129 +++++++-----------
src/test/regress/expected/select_parallel.out | 33 +++++
src/test/regress/sql/select_parallel.sql | 17 +++
3 files changed, 101 insertions(+), 78 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 44efb1f4eb..cf0a3fad2a 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -5192,8 +5192,9 @@ create_ordered_paths(PlannerInfo *root,
* have generated order-preserving Gather Merge plans which can be used
* without sorting if they happen to match the sort_pathkeys, and the loop
* above will have handled those as well. However, there's one more
- * possibility: it may make sense to sort the cheapest partial path
- * according to the required output order and then use Gather Merge.
+ * possibility: it may make sense to sort the cheapest partial path or
+ * incrementally sort any partial path that is partially sorted according
+ * to the required output order and then use Gather Merge.
*/
if (ordered_rel->consider_parallel && root->sort_pathkeys != NIL &&
input_rel->partial_pathlist != NIL)
@@ -5202,97 +5203,69 @@ create_ordered_paths(PlannerInfo *root,
cheapest_partial_path = linitial(input_rel->partial_pathlist);
- /*
- * If cheapest partial path doesn't need a sort, this is redundant
- * with what's already been tried.
- */
- if (!pathkeys_contained_in(root->sort_pathkeys,
- cheapest_partial_path->pathkeys))
+ foreach(lc, input_rel->partial_pathlist)
{
- Path *path;
+ Path *input_path = (Path *) lfirst(lc);
+ Path *sorted_path;
+ bool is_sorted;
+ int presorted_keys;
double total_groups;
- path = (Path *) create_sort_path(root,
- ordered_rel,
- cheapest_partial_path,
- root->sort_pathkeys,
- limit_tuples);
-
- total_groups = cheapest_partial_path->rows *
- cheapest_partial_path->parallel_workers;
- path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- path,
- path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (path->pathtarget != target)
- path = apply_projection_to_path(root, ordered_rel,
- path, target);
-
- add_path(ordered_rel, path);
- }
+ is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
+ input_path->pathkeys,
+ &presorted_keys);
- /*
- * Consider incremental sort with a gather merge on partial paths.
- *
- * We can also skip the entire loop when we only have a single-item
- * sort_pathkeys because then we can't possibly have a presorted
- * prefix of the list without having the list be fully sorted.
- */
- if (enable_incremental_sort && list_length(root->sort_pathkeys) > 1)
- {
- foreach(lc, input_rel->partial_pathlist)
- {
- Path *input_path = (Path *) lfirst(lc);
- Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
- double total_groups;
+ /* No point in adding incremental sort on fully sorted paths. */
+ if (is_sorted)
+ continue;
- /*
- * We don't care if this is the cheapest partial path - we
- * can't simply skip it, because it may be partially sorted in
- * which case we want to consider adding incremental sort
- * (instead of full sort, which is what happens above).
- */
+ /*
+ * Try at least sorting the cheapest path and also try
+ * incrementally sorting any path which is partially sorted
+ * already (no need to deal with paths which have presorted
+ * keys when incremental sort is disabled unless it's the
+ * cheapest partial path).
+ */
+ if (input_path != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
- is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ sorted_path = (Path *) create_sort_path(root,
+ ordered_rel,
+ input_path,
+ root->sort_pathkeys,
+ limit_tuples);
- /* No point in adding incremental sort on fully sorted paths. */
- if (is_sorted)
- continue;
- if (presorted_keys == 0)
- continue;
- /* Since we have presorted keys, consider incremental sort. */
+ else
sorted_path = (Path *) create_incremental_sort_path(root,
ordered_rel,
input_path,
root->sort_pathkeys,
presorted_keys,
limit_tuples);
- total_groups = input_path->rows *
- input_path->parallel_workers;
- sorted_path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- sorted_path,
- sorted_path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (sorted_path->pathtarget != target)
- sorted_path = apply_projection_to_path(root, ordered_rel,
- sorted_path, target);
-
- add_path(ordered_rel, sorted_path);
- }
+ total_groups = input_path->rows *
+ input_path->parallel_workers;
+ sorted_path = (Path *)
+ create_gather_merge_path(root, ordered_rel,
+ sorted_path,
+ sorted_path->pathtarget,
+ root->sort_pathkeys, NULL,
+ &total_groups);
+
+ /* Add projection step if needed */
+ if (sorted_path->pathtarget != target)
+ sorted_path = apply_projection_to_path(root, ordered_rel,
+ sorted_path, target);
+
+ add_path(ordered_rel, sorted_path);
}
}
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index d88353d496..d82a7799e6 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -937,6 +937,39 @@ select string4 from tenk1 order by string4 limit 5;
reset parallel_leader_participation;
reset max_parallel_workers;
+-- gather merge atop sort of partial paths
+create function parallel_safe_volatile(a int) returns int as
+ $$ begin return a; end; $$ parallel safe volatile language plpgsql;
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+ QUERY PLAN
+---------------------------------------------------------------
+ Gather Merge
+ Workers Planned: 4
+ -> Sort
+ Sort Key: hundred, (parallel_safe_volatile(thousand))
+ -> Parallel Seq Scan on tenk1
+ Filter: (four = 2)
+(6 rows)
+
+-- gather merge atop incremental sort of partial paths
+set min_parallel_index_scan_size to 0;
+set enable_seqscan = off;
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+ QUERY PLAN
+---------------------------------------------------------------
+ Gather Merge
+ Workers Planned: 4
+ -> Incremental Sort
+ Sort Key: hundred, (parallel_safe_volatile(thousand))
+ Presorted Key: hundred
+ -> Parallel Index Scan using tenk1_hundred on tenk1
+ Filter: (four = 2)
+(7 rows)
+
+reset min_parallel_index_scan_size;
+reset enable_seqscan;
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index 80c914dc02..7cba6519cb 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -343,6 +343,23 @@ select string4 from tenk1 order by string4 limit 5;
reset parallel_leader_participation;
reset max_parallel_workers;
+-- gather merge atop sort of partial paths
+create function parallel_safe_volatile(a int) returns int as
+ $$ begin return a; end; $$ parallel safe volatile language plpgsql;
+
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+
+-- gather merge atop incremental sort of partial paths
+set min_parallel_index_scan_size to 0;
+set enable_seqscan = off;
+
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+
+reset min_parallel_index_scan_size;
+reset enable_seqscan;
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
--
2.31.0
v2-0002-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchapplication/octet-stream; name=v2-0002-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchDownload
From 2b305be1a9b7423075f02b865ddbf10461407061 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 17 Jul 2023 14:08:10 +0800
Subject: [PATCH v2 2/2] Revise how we sort partial paths in
gather_grouping_paths
---
src/backend/optimizer/plan/planner.c | 49 ++-----------------
src/test/regress/expected/select_parallel.out | 16 ++++++
src/test/regress/sql/select_parallel.sql | 4 ++
3 files changed, 24 insertions(+), 45 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index cf0a3fad2a..065a4f0f07 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -7380,7 +7380,6 @@ create_partial_grouping_paths(PlannerInfo *root,
static void
gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
{
- ListCell *lc;
Path *cheapest_partial_path;
/* Try Gather for unordered paths and Gather Merge for ordered ones. */
@@ -7412,51 +7411,11 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
}
/*
- * Consider incremental sort on all partial paths, if enabled.
- *
- * We can also skip the entire loop when we only have a single-item
- * group_pathkeys because then we can't possibly have a presorted prefix
- * of the list without having the list be fully sorted.
+ * We do not need to consider incremental sort on partial paths, because
+ * for a partial path of a grouped or partially grouped relation, it is
+ * either unordered (HashAggregate or Append), or it has been ordered by
+ * the group_pathkeys (GroupAggregate).
*/
- if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1)
- return;
-
- /* also consider incremental sort on partial paths, if enabled */
- foreach(lc, rel->partial_pathlist)
- {
- Path *path = (Path *) lfirst(lc);
- bool is_sorted;
- int presorted_keys;
- double total_groups;
-
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- if (is_sorted)
- continue;
-
- if (presorted_keys == 0)
- continue;
-
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
- path = (Path *)
- create_gather_merge_path(root,
- rel,
- path,
- rel->reltarget,
- root->group_pathkeys,
- NULL,
- &total_groups);
-
- add_path(rel, path);
- }
}
/*
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index d82a7799e6..5d1b8e05c9 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -970,6 +970,22 @@ select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatil
reset min_parallel_index_scan_size;
reset enable_seqscan;
+-- gather merge atop sort of grouped rel's partial paths
+explain (costs off)
+select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
+ QUERY PLAN
+--------------------------------------------------------------------
+ Finalize GroupAggregate
+ Group Key: twenty, (parallel_safe_volatile(two))
+ -> Gather Merge
+ Workers Planned: 4
+ -> Sort
+ Sort Key: twenty, (parallel_safe_volatile(two))
+ -> Partial HashAggregate
+ Group Key: twenty, parallel_safe_volatile(two)
+ -> Parallel Seq Scan on tenk1
+(9 rows)
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index 7cba6519cb..0f9e874ae9 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -360,6 +360,10 @@ select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatil
reset min_parallel_index_scan_size;
reset enable_seqscan;
+-- gather merge atop sort of grouped rel's partial paths
+explain (costs off)
+select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
--
2.31.0
On Mon, Jul 10, 2023 at 5:37 PM Daniel Gustafsson <daniel@yesql.se> wrote:
On 28 Mar 2023, at 21:59, David Rowley <dgrowleyml@gmail.com> wrote:
I'll mark this as waiting on author while you work on that.Richard: have you had a chance to incorporate the tests proposed by David
in
this thread into your patch?
I just updated the patches according to David's reviews. So I'll change
it back to needs review.
Thanks
Richard
On Thu, Dec 28, 2023 at 4:00 PM Richard Guo <guofenglinux@gmail.com> wrote:
On Wed, Mar 29, 2023 at 4:00 AM David Rowley <dgrowleyml@gmail.com> wrote:
If you write some tests for this code, it will be useful to prove that
it actually does something, and also that it does not break again in
the future. I don't really want to just blindly copy the pattern used
in 3c6fc5820 for creating incremental sort paths if it's not useful
here. It would be good to see tests that make an Incremental Sort path
using the code you're changing.Thanks for the suggestion. I've managed to come up with a query that
gets the codes being changed here to perform an incremental sort.set min_parallel_index_scan_size to 0;
set enable_seqscan to off;Without making those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
--------------------------------------------------------------
Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Gather Merge
Workers Planned: 3
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)and with those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
---------------------------------------------------------------
Gather Merge
Workers Planned: 3
-> Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)I've added two tests for the code changes in create_ordered_paths in the
new patch.Same for the 0003 patch.
For the code changes in gather_grouping_paths, I've managed to come up
with a query that makes an explicit Sort atop cheapest partial path.explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Gather Merge
Workers Planned: 4
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)Without this logic the plan would look like:
explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Gather
Workers Planned: 4
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)This test is also added in the new patch.
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.
I reviewed the Patch and it looks fine to me.
Thanks and Regards,
Shubham Khanna.
On Thu, Dec 28, 2023 at 4:01 PM Shubham Khanna
<khannashubham1197@gmail.com> wrote:
On Thu, Dec 28, 2023 at 4:00 PM Richard Guo <guofenglinux@gmail.com> wrote:
On Wed, Mar 29, 2023 at 4:00 AM David Rowley <dgrowleyml@gmail.com> wrote:
If you write some tests for this code, it will be useful to prove that
it actually does something, and also that it does not break again in
the future. I don't really want to just blindly copy the pattern used
in 3c6fc5820 for creating incremental sort paths if it's not useful
here. It would be good to see tests that make an Incremental Sort path
using the code you're changing.Thanks for the suggestion. I've managed to come up with a query that
gets the codes being changed here to perform an incremental sort.set min_parallel_index_scan_size to 0;
set enable_seqscan to off;Without making those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
--------------------------------------------------------------
Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Gather Merge
Workers Planned: 3
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)and with those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
---------------------------------------------------------------
Gather Merge
Workers Planned: 3
-> Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)I've added two tests for the code changes in create_ordered_paths in the
new patch.Same for the 0003 patch.
For the code changes in gather_grouping_paths, I've managed to come up
with a query that makes an explicit Sort atop cheapest partial path.explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Gather Merge
Workers Planned: 4
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)Without this logic the plan would look like:
explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Gather
Workers Planned: 4
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)This test is also added in the new patch.
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.
Just for clarity; I am not familiar with the code. And for the review,
I ran 'make check' and 'make check-world' and all the test cases
passed successfully.
Thanks and Regards,
Shubham Khanna.
On Mon, 17 Jul 2023 at 14:25, Richard Guo <guofenglinux@gmail.com> wrote:
On Wed, Mar 29, 2023 at 4:00 AM David Rowley <dgrowleyml@gmail.com> wrote:
If you write some tests for this code, it will be useful to prove that
it actually does something, and also that it does not break again in
the future. I don't really want to just blindly copy the pattern used
in 3c6fc5820 for creating incremental sort paths if it's not useful
here. It would be good to see tests that make an Incremental Sort path
using the code you're changing.Thanks for the suggestion. I've managed to come up with a query that
gets the codes being changed here to perform an incremental sort.set min_parallel_index_scan_size to 0;
set enable_seqscan to off;Without making those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
--------------------------------------------------------------
Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Gather Merge
Workers Planned: 3
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)and with those parallel paths:
explain (costs off)
select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
QUERY PLAN
---------------------------------------------------------------
Gather Merge
Workers Planned: 3
-> Incremental Sort
Sort Key: hundred, (parallel_safe_volatile(thousand))
Presorted Key: hundred
-> Parallel Index Scan using tenk1_hundred on tenk1
Filter: (four = 2)
(7 rows)I've added two tests for the code changes in create_ordered_paths in the
new patch.Same for the 0003 patch.
For the code changes in gather_grouping_paths, I've managed to come up
with a query that makes an explicit Sort atop cheapest partial path.explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Gather Merge
Workers Planned: 4
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)Without this logic the plan would look like:
explain (costs off)
select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
QUERY PLAN
--------------------------------------------------------------------
Finalize GroupAggregate
Group Key: twenty, (parallel_safe_volatile(two))
-> Sort
Sort Key: twenty, (parallel_safe_volatile(two))
-> Gather
Workers Planned: 4
-> Partial HashAggregate
Group Key: twenty, parallel_safe_volatile(two)
-> Parallel Seq Scan on tenk1
(9 rows)This test is also added in the new patch.
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.So update the patches to v2.
CFBot shows that the patch does not apply anymore as in [1]http://cfbot.cputube.org/patch_46_4119.log:
=== Applying patches on top of PostgreSQL commit ID
f2bf8fb04886e3ea82e7f7f86696ac78e06b7e60 ===
...
=== applying patch
./v2-0002-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patch
patching file src/backend/optimizer/plan/planner.c
Hunk #1 succeeded at 7289 (offset -91 lines).
Hunk #2 FAILED at 7411.
1 out of 2 hunks FAILED -- saving rejects to file
src/backend/optimizer/plan/planner.c.rej
Please post an updated version for the same.
[1]: http://cfbot.cputube.org/patch_46_4119.log
Regards,
Vignesh
On Mon, Jul 17, 2023 at 4:55 PM Richard Guo <guofenglinux@gmail.com> wrote:
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.
Since now we'd try to reorder the group by keys (see 0452b461bc), it is
possible that we have a partial path that is partially sorted. So this
conclusion is not true any more. For instance,
create table t (a int, b int, c int, d int);
insert into t select i%10, i%10, i%10, i%10 from
generate_series(1,1000000)i;
create index on t (a, b);
analyze t;
set enable_hashagg to off;
set enable_seqscan to off;
explain (costs off)
select count(*) from t group by a, c, b, parallel_safe_volatile(d);
QUERY PLAN
--------------------------------------------------------------------------
Finalize GroupAggregate
Group Key: a, c, b, (parallel_safe_volatile(d))
-> Gather Merge
Workers Planned: 2
-> Incremental Sort
Sort Key: a, c, b, (parallel_safe_volatile(d))
Presorted Key: a
-> Partial GroupAggregate
Group Key: a, b, c, (parallel_safe_volatile(d))
-> Incremental Sort
Sort Key: a, b, c, (parallel_safe_volatile(d))
Presorted Key: a, b
-> Parallel Index Scan using t_a_b_idx on t
(13 rows)
If we do not consider incremental sort on partial paths in
gather_grouping_paths(), we'd get a plan that looks like:
explain (costs off)
select count(*) from t group by a, c, b, parallel_safe_volatile(d);
QUERY PLAN
--------------------------------------------------------------------------------
Finalize GroupAggregate
Group Key: a, c, b, (parallel_safe_volatile(d))
-> Incremental Sort
Sort Key: a, c, b, (parallel_safe_volatile(d))
Presorted Key: a, c, b
-> Gather Merge
Workers Planned: 2
-> Incremental Sort
Sort Key: a, c, b
Presorted Key: a
-> Partial GroupAggregate
Group Key: a, b, c, (parallel_safe_volatile(d))
-> Incremental Sort
Sort Key: a, b, c,
(parallel_safe_volatile(d))
Presorted Key: a, b
-> Parallel Index Scan using t_a_b_idx on
t
(16 rows)
So in the v3 patch I've brought back the logic that considers
incremental sort on partial paths in gather_grouping_paths(). However,
I failed to compose a test case for this scenario without having to
generate a huge table. So in the v3 patch I did not include a test case
for this aspect.
Thanks
Richard
Attachments:
v3-0001-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchapplication/octet-stream; name=v3-0001-Revise-how-we-sort-partial-paths-in-create_ordered_paths.patchDownload
From facaafe466926c9f743d819e41e8702c311aaa91 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 17 Jul 2023 14:07:39 +0800
Subject: [PATCH v3 1/2] Revise how we sort partial paths in
create_ordered_paths
---
src/backend/optimizer/plan/planner.c | 129 +++++++-----------
src/test/regress/expected/select_parallel.out | 33 +++++
src/test/regress/sql/select_parallel.sql | 17 +++
3 files changed, 101 insertions(+), 78 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 2e2458b128..a882fe6d5b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -5102,8 +5102,9 @@ create_ordered_paths(PlannerInfo *root,
* have generated order-preserving Gather Merge plans which can be used
* without sorting if they happen to match the sort_pathkeys, and the loop
* above will have handled those as well. However, there's one more
- * possibility: it may make sense to sort the cheapest partial path
- * according to the required output order and then use Gather Merge.
+ * possibility: it may make sense to sort the cheapest partial path or
+ * incrementally sort any partial path that is partially sorted according
+ * to the required output order and then use Gather Merge.
*/
if (ordered_rel->consider_parallel && root->sort_pathkeys != NIL &&
input_rel->partial_pathlist != NIL)
@@ -5112,97 +5113,69 @@ create_ordered_paths(PlannerInfo *root,
cheapest_partial_path = linitial(input_rel->partial_pathlist);
- /*
- * If cheapest partial path doesn't need a sort, this is redundant
- * with what's already been tried.
- */
- if (!pathkeys_contained_in(root->sort_pathkeys,
- cheapest_partial_path->pathkeys))
+ foreach(lc, input_rel->partial_pathlist)
{
- Path *path;
+ Path *input_path = (Path *) lfirst(lc);
+ Path *sorted_path;
+ bool is_sorted;
+ int presorted_keys;
double total_groups;
- path = (Path *) create_sort_path(root,
- ordered_rel,
- cheapest_partial_path,
- root->sort_pathkeys,
- limit_tuples);
-
- total_groups = cheapest_partial_path->rows *
- cheapest_partial_path->parallel_workers;
- path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- path,
- path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (path->pathtarget != target)
- path = apply_projection_to_path(root, ordered_rel,
- path, target);
-
- add_path(ordered_rel, path);
- }
+ is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
+ input_path->pathkeys,
+ &presorted_keys);
- /*
- * Consider incremental sort with a gather merge on partial paths.
- *
- * We can also skip the entire loop when we only have a single-item
- * sort_pathkeys because then we can't possibly have a presorted
- * prefix of the list without having the list be fully sorted.
- */
- if (enable_incremental_sort && list_length(root->sort_pathkeys) > 1)
- {
- foreach(lc, input_rel->partial_pathlist)
- {
- Path *input_path = (Path *) lfirst(lc);
- Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
- double total_groups;
+ /* No point in adding incremental sort on fully sorted paths. */
+ if (is_sorted)
+ continue;
- /*
- * We don't care if this is the cheapest partial path - we
- * can't simply skip it, because it may be partially sorted in
- * which case we want to consider adding incremental sort
- * (instead of full sort, which is what happens above).
- */
+ /*
+ * Try at least sorting the cheapest path and also try
+ * incrementally sorting any path which is partially sorted
+ * already (no need to deal with paths which have presorted
+ * keys when incremental sort is disabled unless it's the
+ * cheapest partial path).
+ */
+ if (input_path != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
- is_sorted = pathkeys_count_contained_in(root->sort_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ sorted_path = (Path *) create_sort_path(root,
+ ordered_rel,
+ input_path,
+ root->sort_pathkeys,
+ limit_tuples);
- /* No point in adding incremental sort on fully sorted paths. */
- if (is_sorted)
- continue;
- if (presorted_keys == 0)
- continue;
- /* Since we have presorted keys, consider incremental sort. */
+ else
sorted_path = (Path *) create_incremental_sort_path(root,
ordered_rel,
input_path,
root->sort_pathkeys,
presorted_keys,
limit_tuples);
- total_groups = input_path->rows *
- input_path->parallel_workers;
- sorted_path = (Path *)
- create_gather_merge_path(root, ordered_rel,
- sorted_path,
- sorted_path->pathtarget,
- root->sort_pathkeys, NULL,
- &total_groups);
-
- /* Add projection step if needed */
- if (sorted_path->pathtarget != target)
- sorted_path = apply_projection_to_path(root, ordered_rel,
- sorted_path, target);
-
- add_path(ordered_rel, sorted_path);
- }
+ total_groups = input_path->rows *
+ input_path->parallel_workers;
+ sorted_path = (Path *)
+ create_gather_merge_path(root, ordered_rel,
+ sorted_path,
+ sorted_path->pathtarget,
+ root->sort_pathkeys, NULL,
+ &total_groups);
+
+ /* Add projection step if needed */
+ if (sorted_path->pathtarget != target)
+ sorted_path = apply_projection_to_path(root, ordered_rel,
+ sorted_path, target);
+
+ add_path(ordered_rel, sorted_path);
}
}
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index d88353d496..d82a7799e6 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -937,6 +937,39 @@ select string4 from tenk1 order by string4 limit 5;
reset parallel_leader_participation;
reset max_parallel_workers;
+-- gather merge atop sort of partial paths
+create function parallel_safe_volatile(a int) returns int as
+ $$ begin return a; end; $$ parallel safe volatile language plpgsql;
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+ QUERY PLAN
+---------------------------------------------------------------
+ Gather Merge
+ Workers Planned: 4
+ -> Sort
+ Sort Key: hundred, (parallel_safe_volatile(thousand))
+ -> Parallel Seq Scan on tenk1
+ Filter: (four = 2)
+(6 rows)
+
+-- gather merge atop incremental sort of partial paths
+set min_parallel_index_scan_size to 0;
+set enable_seqscan = off;
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+ QUERY PLAN
+---------------------------------------------------------------
+ Gather Merge
+ Workers Planned: 4
+ -> Incremental Sort
+ Sort Key: hundred, (parallel_safe_volatile(thousand))
+ Presorted Key: hundred
+ -> Parallel Index Scan using tenk1_hundred on tenk1
+ Filter: (four = 2)
+(7 rows)
+
+reset min_parallel_index_scan_size;
+reset enable_seqscan;
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index 80c914dc02..7cba6519cb 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -343,6 +343,23 @@ select string4 from tenk1 order by string4 limit 5;
reset parallel_leader_participation;
reset max_parallel_workers;
+-- gather merge atop sort of partial paths
+create function parallel_safe_volatile(a int) returns int as
+ $$ begin return a; end; $$ parallel safe volatile language plpgsql;
+
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+
+-- gather merge atop incremental sort of partial paths
+set min_parallel_index_scan_size to 0;
+set enable_seqscan = off;
+
+explain (costs off)
+select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatile(thousand);
+
+reset min_parallel_index_scan_size;
+reset enable_seqscan;
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
--
2.31.0
v3-0002-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchapplication/octet-stream; name=v3-0002-Revise-how-we-sort-partial-paths-in-gather_grouping_paths.patchDownload
From 146d9a4719a815a0195da0c1a8df5b149241f9b5 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 17 Jul 2023 14:08:10 +0800
Subject: [PATCH v3 2/2] Revise how we sort partial paths in
gather_grouping_paths
---
src/backend/optimizer/plan/planner.c | 71 ++++++++-----------
src/test/regress/expected/select_parallel.out | 16 +++++
src/test/regress/sql/select_parallel.sql | 4 ++
3 files changed, 48 insertions(+), 43 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index a882fe6d5b..c934a41953 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -7295,44 +7295,9 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
/* Try Gather for unordered paths and Gather Merge for ordered ones. */
generate_useful_gather_paths(root, rel, true);
- /* Try cheapest partial path + explicit Sort + Gather Merge. */
cheapest_partial_path = linitial(rel->partial_pathlist);
- if (!pathkeys_contained_in(root->group_pathkeys,
- cheapest_partial_path->pathkeys))
- {
- Path *path;
- double total_groups;
-
- total_groups =
- cheapest_partial_path->rows * cheapest_partial_path->parallel_workers;
- path = (Path *) create_sort_path(root, rel, cheapest_partial_path,
- root->group_pathkeys,
- -1.0);
- path = (Path *)
- create_gather_merge_path(root,
- rel,
- path,
- rel->reltarget,
- root->group_pathkeys,
- NULL,
- &total_groups);
-
- add_path(rel, path);
- }
- /*
- * Consider incremental sort on all partial paths, if enabled.
- *
- * We can also skip the entire loop when we only have a single-item
- * group_pathkeys because then we can't possibly have a presorted prefix
- * of the list without having the list be fully sorted.
- *
- * XXX Shouldn't this also consider the group-key-reordering?
- */
- if (!enable_incremental_sort || list_length(root->group_pathkeys) == 1)
- return;
-
- /* also consider incremental sort on partial paths, if enabled */
+ /* XXX Shouldn't this also consider the group-key-reordering? */
foreach(lc, rel->partial_pathlist)
{
Path *path = (Path *) lfirst(lc);
@@ -7347,15 +7312,35 @@ gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel)
if (is_sorted)
continue;
- if (presorted_keys == 0)
+ /*
+ * Try at least sorting the cheapest path and also try
+ * incrementally sorting any path which is partially sorted
+ * already (no need to deal with paths which have presorted
+ * keys when incremental sort is disabled unless it's the
+ * cheapest input path).
+ */
+ if (path != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
continue;
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
+ total_groups = path->rows * path->parallel_workers;
+
+ /*
+ * We've no need to consider both a sort and incremental sort.
+ * We'll just do a sort if there are no presorted keys and an
+ * incremental sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root, rel, path,
+ root->group_pathkeys,
+ -1.0);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
path = (Path *)
create_gather_merge_path(root,
diff --git a/src/test/regress/expected/select_parallel.out b/src/test/regress/expected/select_parallel.out
index d82a7799e6..5d1b8e05c9 100644
--- a/src/test/regress/expected/select_parallel.out
+++ b/src/test/regress/expected/select_parallel.out
@@ -970,6 +970,22 @@ select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatil
reset min_parallel_index_scan_size;
reset enable_seqscan;
+-- gather merge atop sort of grouped rel's partial paths
+explain (costs off)
+select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
+ QUERY PLAN
+--------------------------------------------------------------------
+ Finalize GroupAggregate
+ Group Key: twenty, (parallel_safe_volatile(two))
+ -> Gather Merge
+ Workers Planned: 4
+ -> Sort
+ Sort Key: twenty, (parallel_safe_volatile(two))
+ -> Partial HashAggregate
+ Group Key: twenty, parallel_safe_volatile(two)
+ -> Parallel Seq Scan on tenk1
+(9 rows)
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
diff --git a/src/test/regress/sql/select_parallel.sql b/src/test/regress/sql/select_parallel.sql
index 7cba6519cb..0f9e874ae9 100644
--- a/src/test/regress/sql/select_parallel.sql
+++ b/src/test/regress/sql/select_parallel.sql
@@ -360,6 +360,10 @@ select * from tenk1 where four = 2 order by four, hundred, parallel_safe_volatil
reset min_parallel_index_scan_size;
reset enable_seqscan;
+-- gather merge atop sort of grouped rel's partial paths
+explain (costs off)
+select count(*) from tenk1 group by twenty, parallel_safe_volatile(two);
+
SAVEPOINT settings;
SET LOCAL debug_parallel_query = 1;
explain (costs off)
--
2.31.0
On Mon, 29 Jan 2024 at 22:39, Richard Guo <guofenglinux@gmail.com> wrote:
So in the v3 patch I've brought back the logic that considers
incremental sort on partial paths in gather_grouping_paths(). However,
I failed to compose a test case for this scenario without having to
generate a huge table. So in the v3 patch I did not include a test case
for this aspect.
Can you share the test with the huge table?
I tried and failed as, if I'm not mistaken, you're talking about a
parallel aggregate query with an incremental sort between the Partial
Aggregate node and the Finalize Group Aggregate node. If the partial
aggregate was a Group Aggregate, then it would already be correctly
sorted. We don't need a more strict sort ordering to perform the
Finalize Group Aggregate, the results must already be sorted by at
least the GROUP BY clause. If the partial aggregate had opted to Hash
Aggregate, then there'd be no presorted keys, so we could only get a
full sort. I can't see any way to get an incremental sort between the
2 aggregate phases.
What am I missing?
I also tried reverting your changes to planner.c to see if your new
tests would fail. They all passed. So it looks like none of these
tests are testing anything new.
David
On Tue, Jan 30, 2024 at 7:00 PM David Rowley <dgrowleyml@gmail.com> wrote:
On Mon, 29 Jan 2024 at 22:39, Richard Guo <guofenglinux@gmail.com> wrote:
So in the v3 patch I've brought back the logic that considers
incremental sort on partial paths in gather_grouping_paths(). However,
I failed to compose a test case for this scenario without having to
generate a huge table. So in the v3 patch I did not include a test case
for this aspect.Can you share the test with the huge table?
The test had been shown in upthread [1]/messages/by-id/CAMbWs4_iDwMAf5mp+G-tXq-gYzvR6koSHvNUqBPK4pt7+11tJw@mail.gmail.com. Pasting it here:
create table t (a int, b int, c int, d int);
insert into t select i%10, i%10, i%10, i%10 from
generate_series(1,1000000)i;
create index on t (a, b);
analyze t;
set enable_hashagg to off;
set enable_seqscan to off;
explain (costs off)
select count(*) from t group by a, c, b, parallel_safe_volatile(d);
QUERY PLAN
--------------------------------------------------------------------------
Finalize GroupAggregate
Group Key: a, c, b, (parallel_safe_volatile(d))
-> Gather Merge
Workers Planned: 2
-> Incremental Sort
Sort Key: a, c, b, (parallel_safe_volatile(d))
Presorted Key: a
-> Partial GroupAggregate
Group Key: a, b, c, (parallel_safe_volatile(d))
-> Incremental Sort
Sort Key: a, b, c, (parallel_safe_volatile(d))
Presorted Key: a, b
-> Parallel Index Scan using t_a_b_idx on t
(13 rows)
I tried and failed as, if I'm not mistaken, you're talking about a
parallel aggregate query with an incremental sort between the Partial
Aggregate node and the Finalize Group Aggregate node. If the partial
aggregate was a Group Aggregate, then it would already be correctly
sorted. We don't need a more strict sort ordering to perform the
Finalize Group Aggregate, the results must already be sorted by at
least the GROUP BY clause. If the partial aggregate had opted to Hash
Aggregate, then there'd be no presorted keys, so we could only get a
full sort. I can't see any way to get an incremental sort between the
2 aggregate phases.What am I missing?
This was true before 0452b461bc, and I reached the same conclusion in
[2]: /messages/by-id/CAMbWs497h5jVCVwNDb+BX31Z_K8iBaPQKOcsTvpFQ7kF18a2+g@mail.gmail.com
"
But I did not find a query that makes an incremental sort in this case.
After trying for a while it seems to me that we do not need to consider
incremental sort in this case, because for a partial path of a grouped
or partially grouped relation, it is either unordered (HashAggregate or
Append), or it has been ordered by the group_pathkeys (GroupAggregate).
It seems there is no case that we'd have a partial path that is
partially sorted.
"
But if we've reordered the group by keys to match the input path's
pathkeys, we might have a partial GroupAggregate that is partially
sorted. See the plan above.
I also tried reverting your changes to planner.c to see if your new
tests would fail. They all passed. So it looks like none of these
tests are testing anything new.
This patchset does not aim to introduce anything new; it simply
refactors the existing code. The newly added tests are used to show
that the code that is touched here is not redundant, but rather
essential for generating certain paths. I remember the tests were added
per your comment in [3]/messages/by-id/CAApHDvo+FagxVSGmvt-LUrhLZQ0KViiLvX8dPaG3ZzWLNd-Zpg@mail.gmail.com.
[1]: /messages/by-id/CAMbWs4_iDwMAf5mp+G-tXq-gYzvR6koSHvNUqBPK4pt7+11tJw@mail.gmail.com
/messages/by-id/CAMbWs4_iDwMAf5mp+G-tXq-gYzvR6koSHvNUqBPK4pt7+11tJw@mail.gmail.com
[2]: /messages/by-id/CAMbWs497h5jVCVwNDb+BX31Z_K8iBaPQKOcsTvpFQ7kF18a2+g@mail.gmail.com
/messages/by-id/CAMbWs497h5jVCVwNDb+BX31Z_K8iBaPQKOcsTvpFQ7kF18a2+g@mail.gmail.com
[3]: /messages/by-id/CAApHDvo+FagxVSGmvt-LUrhLZQ0KViiLvX8dPaG3ZzWLNd-Zpg@mail.gmail.com
/messages/by-id/CAApHDvo+FagxVSGmvt-LUrhLZQ0KViiLvX8dPaG3ZzWLNd-Zpg@mail.gmail.com
Thanks
Richard
On Wed, 31 Jan 2024 at 00:44, Richard Guo <guofenglinux@gmail.com> wrote:
This patchset does not aim to introduce anything new; it simply
refactors the existing code. The newly added tests are used to show
that the code that is touched here is not redundant, but rather
essential for generating certain paths. I remember the tests were added
per your comment in [3].[3] /messages/by-id/CAApHDvo+FagxVSGmvt-LUrhLZQ0KViiLvX8dPaG3ZzWLNd-Zpg@mail.gmail.com
OK. I've pushed the patched based on it being a simplification of the
partial path generation.
David
On Wed, Jan 31, 2024 at 5:13 AM David Rowley <dgrowleyml@gmail.com> wrote:
On Wed, 31 Jan 2024 at 00:44, Richard Guo <guofenglinux@gmail.com> wrote:
This patchset does not aim to introduce anything new; it simply
refactors the existing code. The newly added tests are used to show
that the code that is touched here is not redundant, but rather
essential for generating certain paths. I remember the tests were added
per your comment in [3].[3]
/messages/by-id/CAApHDvo+FagxVSGmvt-LUrhLZQ0KViiLvX8dPaG3ZzWLNd-Zpg@mail.gmail.com
OK. I've pushed the patched based on it being a simplification of the
partial path generation.
Thanks for pushing it!
Thanks
Richard