public inbox for [email protected]
help / color / mirror / Atom feedFrom: David Rowley <[email protected]>
To: Richard Guo <[email protected]>
Cc: Ronan Dunklau <[email protected]>
Cc: Justin Pryzby <[email protected]>
Cc: Pavel Luzanov <[email protected]>
Cc: Tom Lane <[email protected]>
Cc: [email protected]
Cc: Ranier Vilela <[email protected]>
Subject: Re: Add proper planner support for ORDER BY / DISTINCT aggregates
Date: Fri, 16 Dec 2022 00:10:44 +1300
Message-ID: <CAApHDvptP-VK+ERLVs6UOAWaCQ7y4bf4_SSfRLCSyKWb-rW5zg@mail.gmail.com> (raw)
In-Reply-To: <CAApHDvr1Sm+g9hbv4REOVuvQKeDWXcKUAhmbK5K+dfun0s9CvA@mail.gmail.com>
References: <3163474.aeNJFYEL58@aivenronan>
<CAApHDvowz-gfbuq=8iwHebRcy4VpFuJv52B3jCcXVi+CPFrd1A@mail.gmail.com>
<[email protected]>
<2202180.iZASKD2KPV@aivenlaptop>
<CAApHDvpkbvDEDJPNZrUqCsCLVC57ZY8qrPn8nGpQSrn4RYstZw@mail.gmail.com>
<CAMbWs4_+5cP+8xjiAc=hds935ZiiG6oepPDeVNovWhQ66DARJw@mail.gmail.com>
<CAApHDvqiEBY5_fVv4ZwUtWDPk0pJ6TdoYKFMwhhF_Gdkv-xAkg@mail.gmail.com>
<CAApHDvr1Sm+g9hbv4REOVuvQKeDWXcKUAhmbK5K+dfun0s9CvA@mail.gmail.com>
On Tue, 13 Dec 2022 at 20:53, David Rowley <[email protected]> wrote:
> I think what we need to do is: Do our best to give incremental sort
> the most realistic costs we can and accept that it might choose a
> worse plan in some cases. Users can turn it off if they really have no
> other means to convince the planner it's wrong.
>
> Additionally, I think what we also need to add a GUC such as
> enable_presorted_aggregate. People can use that when their Index Scan
> -> Incremental Sort -> Aggregate plan is worse than their previous Seq
> Scan -> Sort -> Aggregate plan that they were getting in < 16.
> Turning off enable_incremental_sort alone won't give them the same
> aggregate plan that they had in pg15 as we always set the
> query_pathkeys to request a sort order that will suit the order by /
> distinct aggregates.
>
> I'll draft up a patch for the enable_presorted_aggregate.
I've attached a patch series for this.
v3-0001 can be ignored here. I've posted about that in [1]. Any
discussion about that patch should take place over there. The patch
is required to get the 0002 patch to pass isolation check
v3-0002 removes the 1.5 x cost pessimism from incremental sort and
also rewrites how we make incremental sort paths. I've now gone
through the remaining places where we create an incremental sort path
to give all those the same treatment that I'd added to
add_paths_to_grouping_rel(). There was a 1 or 2 plan changes in the
regression tests. One was the isolation test change, which I claim to
be a broken test and should be fixed another way. The other was
performing a Sort on the cheapest input path which had presorted keys.
That plan now uses an Incremental Sort to make use of the presorted
keys. I'm happy to see just how much redundant code this removes.
About 200 lines.
v3-0003 adds the enable_presorted_aggregate GUC.
David
[1] https://www.postgresql.org/message-id/[email protected]...
From ed0e0bd525ea16ea724e9794b5f4feddf29da497 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Thu, 15 Dec 2022 17:49:40 +1300
Subject: [PATCH v3 1/3] Re-adjust drop-index-concurrently-1 isolation test
It seems that drop-index-concurrently has started to forget what it was
originally meant to be testing. d2d8a229b, which added incremental sorts
changed the expected plan to be an Index Scan plan instead of a Seq Scan
plan. This occurred as the primary key index of the table in question
provided presorted input and, because that index happened to be the
cheapest input path due to enable_seqscan being disabled, the incremental
sort changes just added a Sort on top of that. It seems based on the name
of the PREPAREd statement that the intention here is that query produce a
seqscan plan.
The reason this test has become broken seems to be due to how the test was
originally coded. It tried to force a seqscan plan by performing some
casting to make it so the test_dc couldn't be used to perform the required
filtering. This likely wasn't the best design. It seems much better just
to toggle enable_seqscan to allow the planner to produce a more
predictable plan. Trying to coax the planner into using a plan which has
costed in a disable_cost seems like it's always going to be flakey. So
let's get rid of that and put the expected plans closer to what they were
originally when the test was added.
Additionally, rename a few things in the test and add some additional
wording to the comments to try and make it more clear in the future what
we expect this test to be doing.
---
.../expected/drop-index-concurrently-1.out | 31 ++++++++++---------
.../expected/drop-index-concurrently-1_2.out | 31 ++++++++++---------
.../specs/drop-index-concurrently-1.spec | 22 +++++++------
3 files changed, 44 insertions(+), 40 deletions(-)
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out
index 97e1a6e779..1cb2250891 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -1,17 +1,17 @@
Parsed test spec with 3 sessions
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
is_read_committed
-----------------
t
(1 row)
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
QUERY PLAN
----------------------------------------------
Sort
@@ -20,16 +20,17 @@ Sort
Index Cond: (data = 34)
(4 rows)
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN
-----------------------------------------------
-Sort
- Sort Key: id, data
- -> Index Scan using test_dc_pkey on test_dc
- Filter: ((data)::text = '34'::text)
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN
+---------------------------
+Sort
+ Sort Key: id
+ -> Seq Scan on test_dc
+ Filter: (data = 34)
(4 rows)
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
id|data
--+----
34| 34
@@ -38,14 +39,14 @@ id|data
step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
id|data
---+----
34| 34
134| 34
(2 rows)
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
id|data
---+----
34| 34
diff --git a/src/test/isolation/expected/drop-index-concurrently-1_2.out b/src/test/isolation/expected/drop-index-concurrently-1_2.out
index 04612d3cac..266b0e4ada 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1_2.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1_2.out
@@ -1,17 +1,17 @@
Parsed test spec with 3 sessions
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
is_read_committed
-----------------
f
(1 row)
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
QUERY PLAN
----------------------------------------------
Sort
@@ -20,16 +20,17 @@ Sort
Index Cond: (data = 34)
(4 rows)
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN
-----------------------------------------------
-Sort
- Sort Key: id, data
- -> Index Scan using test_dc_pkey on test_dc
- Filter: ((data)::text = '34'::text)
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN
+---------------------------
+Sort
+ Sort Key: id
+ -> Seq Scan on test_dc
+ Filter: (data = 34)
(4 rows)
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
id|data
--+----
34| 34
@@ -38,13 +39,13 @@ id|data
step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
id|data
--+----
34| 34
(1 row)
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
id|data
--+----
34| 34
diff --git a/src/test/isolation/specs/drop-index-concurrently-1.spec b/src/test/isolation/specs/drop-index-concurrently-1.spec
index 812b5de226..a57a02469d 100644
--- a/src/test/isolation/specs/drop-index-concurrently-1.spec
+++ b/src/test/isolation/specs/drop-index-concurrently-1.spec
@@ -3,7 +3,8 @@
# This test shows that the concurrent write behaviour works correctly
# with the expected output being 2 rows at the READ COMMITTED and READ
# UNCOMMITTED transaction isolation levels, and 1 row at the other
-# transaction isolation levels.
+# transaction isolation levels. We ensure this is the case by checking
+# the returned rows in an index scan plan and a seq scan plan.
#
setup
{
@@ -18,24 +19,25 @@ teardown
}
session s1
-step noseq { SET enable_seqscan = false; }
step chkiso { SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation'; }
-step prepi { PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
-step preps { PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data; }
+step prepi { PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
+step preps { PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
step begin { BEGIN; }
-step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idx; }
-step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seq; }
-step selecti { EXECUTE getrow_idx; }
-step selects { EXECUTE getrow_seq; }
+step disableseq { SET enable_seqscan = false; }
+step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan; }
+step enableseq { SET enable_seqscan = true; }
+step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan; }
+step selecti { EXECUTE getrow_idxscan; }
+step selects { EXECUTE getrow_seqscan; }
step end { COMMIT; }
session s2
setup { BEGIN; }
-step select2 { SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
+step select2 { SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
step insert2 { INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100); }
step end2 { COMMIT; }
session s3
step drop { DROP INDEX CONCURRENTLY test_dc_data; }
-permutation noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
+permutation chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
--
2.35.1.windows.2
From 3112cc7e40778d3d377660d864db1f218a3b2cf6 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Tue, 8 Nov 2022 14:36:38 +1300
Subject: [PATCH v3 2/3] Remove pessimistic cost penalization from Incremental
Sort
When incremental sorts were added in v13 a 1.5x pessimism factor was added
to the cost modal. Seemingly this was done because the cost modal only
has an estimate of the total number of input rows and the number of
presorted groups. It assumes that the input rows will be evenly
distributed throughout the presorted groups. The 1.5x pessimism factor
was added to slightly reduce the likelihood of incremental sorts being
used in the hope to avoid performance regressions where an incremental
sort plan was picked and turned out slower due to a large skew in the
number of rows in the presorted groups.
An additional quirk with the path generation code meant that we could
consider both a sort and an incremental sort on paths with presorted keys.
This meant that with the pessimism factor, it was possible that we opted
to perform a sort rather than an incremental sort when the given path had
presorted keys.
Here we remove the 1.5x pessimism factor to allow incremental sorts to
have a fairer chance at being chosen against a full sort.
Additionally, this changes how incremental sort paths are generated.
Previously we would generally create a sort path on the cheapest input
path (if that wasn't sorted already) and incremental sort paths on any
path which had presorted keys. This meant that if the cheapest input path
wasn't completely sorted but happened to have presorted keys, we would
create a full sort path *and* an incremental sort path on that input path.
Here we change this logic so that if there are presorted keys, we only
create an incremental sort path, and create sort paths only when a full
sort is required or enable_incremental_sort is disabled.
Both the removal of the cost pessimism factor and the changes made to the
path generation make it more likely that incremental sorts will now be
chosen. That, of course, as with teaching the planner any new tricks,
means an increased likelihood that the planner will perform an incremental
sort when it's not the best method. Our standard escape hatch for these
cases is an enable_* GUC. enable_incremental_sort already exists for
this.
This came out of a report by Pavel Luzanov where he mentioned that v16
was choosing to perform a Seq Scan -> Sort -> Group Aggregate for his
query with an ORDER BY aggregate function. The v15 plan for his query
performed an Index Scan -> Group Aggregate, of course, the aggregate
performed the final sort internally in nodeAgg.c for the aggregate's ORDER
BY. The ideal plan would have been to use the index, which provided
partially sorted input then use an incremental sort to provide the
aggregate with the sorted input. This was not being chosen due to the
pessimism in the incremental sort cost modal, so here we remove that and
rationalize the path generation so that sort and incremental sort plans
don't have to needlessly complete.
Reported-by: Pavel Luzanov
Reviewed-by: Richard Guo
Discussion: https://postgr.es/m/9f61ddbf-2989-1536-b31e-6459370a6baa%40postgrespro.ru
---
.../postgres_fdw/expected/postgres_fdw.out | 2 +
contrib/postgres_fdw/sql/postgres_fdw.sql | 2 +
src/backend/optimizer/path/allpaths.c | 94 ++--
src/backend/optimizer/path/costsize.c | 38 +-
src/backend/optimizer/plan/planner.c | 480 ++++++------------
.../regress/expected/incremental_sort.out | 13 -
src/test/regress/expected/partition_join.out | 5 +-
src/test/regress/sql/incremental_sort.sql | 5 -
8 files changed, 220 insertions(+), 419 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 2ab3f1efaa..5f6e1f9833 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2796,6 +2796,7 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
(5 rows)
-- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
explain (verbose, costs off)
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
QUERY PLAN
@@ -2814,6 +2815,7 @@ select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, s
1000 | 4500
(1 row)
+reset enable_incremental_sort;
-- Aggregate is still pushed down by taking unshippable expression out
explain (verbose, costs off)
select c2 * (random() <= 1)::int as sum1, sum(c1) * c2 as sum2 from ft1 group by c2 order by 1, 2;
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index 51560429e0..bfcac4ea14 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -750,9 +750,11 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
-- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
explain (verbose, costs off)
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
+reset enable_incremental_sort;
-- Aggregate is still pushed down by taking unshippable expression out
explain (verbose, costs off)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 0c564be7f6..0cfa3a1d6c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -3207,70 +3207,52 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
continue;
/*
- * Consider regular sort for the cheapest partial path (for each
- * useful pathkeys). We know the path is not sorted, because we'd
- * not get here otherwise.
+ * 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 (subpath != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * Consider regular sort for any path that's not presorted or if
+ * incremental sort is disabled. We've no need to consider both
+ * sort and incremental sort on the same path. We assume that
+ * incremental sort is always faster when there are presorted
+ * keys.
*
* This is not redundant with the gather paths created in
* generate_gather_paths, because that doesn't generate ordered
* output. Here we add an explicit sort to match the useful
* ordering.
*/
- if (cheapest_partial_path == subpath)
+ if (presorted_keys == 0 || !enable_incremental_sort)
{
- Path *tmp;
-
- tmp = (Path *) create_sort_path(root,
- rel,
- subpath,
- useful_pathkeys,
- -1.0);
-
- rows = tmp->rows * tmp->parallel_workers;
-
- path = create_gather_merge_path(root, rel,
- tmp,
- rel->reltarget,
- tmp->pathkeys,
- NULL,
- rowsp);
-
- add_path(rel, &path->path);
-
- /* Fall through */
- }
-
- /*
- * Consider incremental sort, but only when the subpath is already
- * partially sorted on a pathkey prefix.
- */
- if (enable_incremental_sort && presorted_keys > 0)
- {
- Path *tmp;
-
- /*
- * We should have already excluded pathkeys of length 1
- * because then presorted_keys > 0 would imply is_sorted was
- * true.
- */
- Assert(list_length(useful_pathkeys) != 1);
-
- tmp = (Path *) create_incremental_sort_path(root,
- rel,
- subpath,
- useful_pathkeys,
- presorted_keys,
- -1);
-
- path = create_gather_merge_path(root, rel,
- tmp,
- rel->reltarget,
- tmp->pathkeys,
- NULL,
- rowsp);
-
- add_path(rel, &path->path);
+ subpath = (Path *) create_sort_path(root,
+ rel,
+ subpath,
+ useful_pathkeys,
+ -1.0);
+ rows = subpath->rows * subpath->parallel_workers;
}
+ else
+ subpath = (Path *) create_incremental_sort_path(root,
+ rel,
+ subpath,
+ useful_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.c
index 897309d7ec..0f0bcfb7e5 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1959,8 +1959,8 @@ cost_incremental_sort(Path *path,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples)
{
- Cost startup_cost = 0,
- run_cost = 0,
+ Cost startup_cost,
+ run_cost,
input_run_cost = input_total_cost - input_startup_cost;
double group_tuples,
input_groups;
@@ -1969,10 +1969,9 @@ cost_incremental_sort(Path *path,
group_input_run_cost;
List *presortedExprs = NIL;
ListCell *l;
- int i = 0;
bool unknown_varno = false;
- Assert(presorted_keys != 0);
+ Assert(presorted_keys > 0 && presorted_keys < list_length(pathkeys));
/*
* We want to be sure the cost of a sort is never estimated as zero, even
@@ -2025,12 +2024,11 @@ cost_incremental_sort(Path *path,
/* expression not containing any Vars with "varno 0" */
presortedExprs = lappend(presortedExprs, member->em_expr);
- i++;
- if (i >= presorted_keys)
+ if (foreach_current_index(l) + 1 >= presorted_keys)
break;
}
- /* Estimate number of groups with equal presorted keys. */
+ /* Estimate the number of groups with equal presorted keys. */
if (!unknown_varno)
input_groups = estimate_num_groups(root, presortedExprs, input_tuples,
NULL, NULL);
@@ -2039,22 +2037,19 @@ cost_incremental_sort(Path *path,
group_input_run_cost = input_run_cost / input_groups;
/*
- * Estimate average cost of sorting of one group where presorted keys are
- * equal. Incremental sort is sensitive to distribution of tuples to the
- * groups, where we're relying on quite rough assumptions. Thus, we're
- * pessimistic about incremental sort performance and increase its average
- * group size by half.
+ * Estimate the average cost of sorting of one group where presorted keys
+ * are equal.
*/
cost_tuplesort(&group_startup_cost, &group_run_cost,
- 1.5 * group_tuples, width, comparison_cost, sort_mem,
+ group_tuples, width, comparison_cost, sort_mem,
limit_tuples);
/*
* Startup cost of incremental sort is the startup cost of its first group
* plus the cost of its input.
*/
- startup_cost += group_startup_cost
- + input_startup_cost + group_input_run_cost;
+ startup_cost = group_startup_cost + input_startup_cost +
+ group_input_run_cost;
/*
* After we started producing tuples from the first group, the cost of
@@ -2062,17 +2057,20 @@ cost_incremental_sort(Path *path,
* group, plus the total cost to process the remaining groups, plus the
* remaining cost of input.
*/
- run_cost += group_run_cost
- + (group_run_cost + group_startup_cost) * (input_groups - 1)
- + group_input_run_cost * (input_groups - 1);
+ run_cost = group_run_cost + (group_run_cost + group_startup_cost) *
+ (input_groups - 1) + group_input_run_cost * (input_groups - 1);
/*
* Incremental sort adds some overhead by itself. Firstly, it has to
* detect the sort groups. This is roughly equal to one extra copy and
- * comparison per tuple. Secondly, it has to reset the tuplesort context
- * for every group.
+ * comparison per tuple.
*/
run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
+
+ /*
+ * Additionally, we charge double cpu_tuple_cost for each input group to
+ * account for the tuplesort_reset that's performed after each group.
+ */
run_cost += 2.0 * cpu_tuple_cost * input_groups;
path->rows = input_tuples;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5dd4f92720..dfda251d95 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4965,7 +4965,7 @@ create_ordered_paths(PlannerInfo *root,
foreach(lc, input_rel->pathlist)
{
Path *input_path = (Path *) lfirst(lc);
- Path *sorted_path = input_path;
+ Path *sorted_path;
bool is_sorted;
int presorted_keys;
@@ -4973,69 +4973,46 @@ create_ordered_paths(PlannerInfo *root,
input_path->pathkeys, &presorted_keys);
if (is_sorted)
- {
- /* Use the input path as is, but add a 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);
- }
+ sorted_path = input_path;
else
{
/*
- * Try adding an explicit sort, but only to the cheapest total
- * path since a full sort should generally add the same cost to
- * all paths.
+ * 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_input_path)
- {
- /*
- * Sort the cheapest input path. An explicit sort here can
- * take advantage of LIMIT.
- */
+ if (input_path != cheapest_input_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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);
- /* 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);
- }
-
- /*
- * If incremental sort is enabled, then try it as well. Unlike
- * with regular sorts, we can't just look at the cheapest path,
- * because the cost of incremental sort depends on how well
- * presorted the path is. Additionally incremental sort may enable
- * a cheaper startup path to win out despite higher total cost.
- */
- if (!enable_incremental_sort)
- continue;
-
- /* Likewise, if the path can't be used for incremental sort. */
- if (!presorted_keys)
- continue;
-
- /* Also consider incremental sort. */
- sorted_path = (Path *) create_incremental_sort_path(root,
- ordered_rel,
- input_path,
- root->sort_pathkeys,
- presorted_keys,
- limit_tuples);
+ else
+ sorted_path = (Path *) create_incremental_sort_path(root,
+ ordered_rel,
+ input_path,
+ root->sort_pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
- /* Add projection step if needed */
- if (sorted_path->pathtarget != target)
- sorted_path = apply_projection_to_path(root, ordered_rel,
- sorted_path, target);
+ /* 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);
- }
+ add_path(ordered_rel, sorted_path);
}
/*
@@ -6501,12 +6478,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
/*
* Use any available suitably-sorted path as input, and also consider
- * sorting the cheapest-total path.
+ * sorting the cheapest-total path and incremental sort on any paths
+ * with presorted keys.
*/
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -6514,90 +6491,39 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
path->pathkeys,
&presorted_keys);
- if (path == cheapest_path || is_sorted)
+ if (!is_sorted)
{
- /* Sort the cheapest-total path if it isn't already sorted */
- if (!is_sorted)
+ /*
+ * 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_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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,
grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- /* Now decide what to stick atop it */
- if (parse->groupingSets)
- {
- consider_groupingsets_paths(root, grouped_rel,
- path, true, can_hash,
- gd, agg_costs, dNumGroups);
- }
- else if (parse->hasAggs)
- {
- /*
- * We have aggregation, possibly with plain GROUP BY. Make
- * an AggPath.
- */
- add_path(grouped_rel, (Path *)
- create_agg_path(root,
- grouped_rel,
- path,
- grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_SIMPLE,
- parse->groupClause,
- havingQual,
- agg_costs,
- dNumGroups));
- }
- else if (parse->groupClause)
- {
- /*
- * We have GROUP BY without aggregation or grouping sets.
- * Make a GroupPath.
- */
- add_path(grouped_rel, (Path *)
- create_group_path(root,
- grouped_rel,
- path,
- parse->groupClause,
- havingQual,
- dNumGroups));
- }
else
- {
- /* Other cases should have been handled above */
- Assert(false);
- }
+ path = (Path *) create_incremental_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental sort
- * is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, no point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1 because
- * then presorted_keys > 0 would imply is_sorted was true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
/* Now decide what to stick atop it */
if (parse->groupingSets)
{
@@ -6653,7 +6579,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
foreach(lc, partially_grouped_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -6661,19 +6586,38 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
path->pathkeys,
&presorted_keys);
- /*
- * Insert a Sort node, if required. But there's no point in
- * sorting anything but the cheapest path.
- */
if (!is_sorted)
{
- if (path != partially_grouped_rel->cheapest_total_path)
+ /*
+ * 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 != partially_grouped_rel->cheapest_total_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
continue;
- path = (Path *) create_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- -1.0);
+
+ /*
+ * We've no need to consider both a sort and incremental
+ * sort. We'll just do a sort if there are no pre-sorted
+ * keys and an incremental sort when there are presorted
+ * keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ -1.0);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
if (parse->hasAggs)
@@ -6697,55 +6641,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
havingQual,
dNumGroups));
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental
- * sort is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, not point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1
- * because then presorted_keys > 0 would imply is_sorted was
- * true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
- if (parse->hasAggs)
- add_path(grouped_rel, (Path *)
- create_agg_path(root,
- grouped_rel,
- path,
- grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_FINAL_DESERIAL,
- parse->groupClause,
- havingQual,
- agg_final_costs,
- dNumGroups));
- else
- add_path(grouped_rel, (Path *)
- create_group_path(root,
- grouped_rel,
- path,
- parse->groupClause,
- havingQual,
- dNumGroups));
}
}
}
@@ -6950,97 +6845,64 @@ create_partial_grouping_paths(PlannerInfo *root,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ int presorted_keys;
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
- if (path == cheapest_total_path || is_sorted)
+ is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+ if (!is_sorted)
{
- /* Sort the cheapest partial path, if it isn't already */
- if (!is_sorted)
+ /*
+ * 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_total_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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,
partially_grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- if (parse->hasAggs)
- add_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialGroups));
else
- add_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialGroups));
+ path = (Path *) create_incremental_sort_path(root,
+ partially_grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- }
-
- /*
- * 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)
- {
- foreach(lc, input_rel->pathlist)
- {
- Path *path = (Path *) lfirst(lc);
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- /* Ignore already sorted paths */
- if (is_sorted)
- continue;
-
- if (presorted_keys == 0)
- continue;
- /* Since we have presorted keys, consider incremental sort. */
- path = (Path *) create_incremental_sort_path(root,
- partially_grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
- if (parse->hasAggs)
- add_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialGroups));
- else
- add_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialGroups));
- }
+ if (parse->hasAggs)
+ add_path(partially_grouped_rel, (Path *)
+ create_agg_path(root,
+ partially_grouped_rel,
+ path,
+ partially_grouped_rel->reltarget,
+ parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ AGGSPLIT_INITIAL_SERIAL,
+ parse->groupClause,
+ NIL,
+ agg_partial_costs,
+ dNumPartialGroups));
+ else
+ add_path(partially_grouped_rel, (Path *)
+ create_group_path(root,
+ partially_grouped_rel,
+ path,
+ parse->groupClause,
+ NIL,
+ dNumPartialGroups));
}
}
@@ -7050,7 +6912,6 @@ create_partial_grouping_paths(PlannerInfo *root,
foreach(lc, input_rel->partial_pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -7058,66 +6919,39 @@ create_partial_grouping_paths(PlannerInfo *root,
path->pathkeys,
&presorted_keys);
- if (path == cheapest_partial_path || is_sorted)
+ if (!is_sorted)
{
- /* Sort the cheapest partial path, if it isn't already */
- if (!is_sorted)
+ /*
+ * 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;
+
+ /*
+ * 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,
partially_grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- if (parse->hasAggs)
- add_partial_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialPartialGroups));
else
- add_partial_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialPartialGroups));
+ path = (Path *) create_incremental_sort_path(root,
+ partially_grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental sort
- * is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, not point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1 because
- * then presorted_keys > 0 would imply is_sorted was true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- partially_grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
if (parse->hasAggs)
add_partial_path(partially_grouped_rel, (Path *)
create_agg_path(root,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..1a1e8b2365 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1,16 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
- QUERY PLAN
------------------------------------
- Sort
- Sort Key: tenk1.four, tenk1.ten
- -> Sort
- Sort Key: tenk1.four
- -> Seq Scan on tenk1
-(5 rows)
-
-- When there is a LIMIT clause, incremental sort is beneficial because
-- it only has to sort some of the groups, and not the entire table.
explain (costs off)
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index b20facc19f..c59caf1cb3 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -1173,8 +1173,9 @@ EXPLAIN (COSTS OFF)
SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
QUERY PLAN
-----------------------------------------------------------
- Sort
+ Incremental Sort
Sort Key: prt1.a, prt2.b
+ Presorted Key: prt1.a
-> Merge Left Join
Merge Cond: (prt1.a = prt2.b)
-> Sort
@@ -1191,7 +1192,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
Filter: (b > 250)
-> Seq Scan on prt2_p3 prt2_2
Filter: (b > 250)
-(18 rows)
+(19 rows)
SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
a | b
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..071f8a5268 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -1,8 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
-
-- When there is a LIMIT clause, incremental sort is beneficial because
-- it only has to sort some of the groups, and not the entire table.
explain (costs off)
--
2.35.1.windows.2
From 0eb650dd777925d28ff3c47ffbae244f06386d55 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Wed, 14 Dec 2022 10:25:19 +1300
Subject: [PATCH v3 3/3] Add enable_presorted_aggregate GUC
1349d279 added query planner support to allow more efficient execution of
aggregate functions which have an ORDER BY or a DISTINCT clause. Prior to
that commit, the planner would only request that the lower planner produce
a plan with the order required for the GROUP BY clause and it would be
left up to nodeAgg.c to perform the final sort of records within each
group so that the aggregate transition functions were called in the
correct order. Now that the planner requests the lower planner produce a
plan with the GROUP BY and the ORDER BY / DISTINCT aggregates in mind,
there is the possibility that the planner chooses a plan which could be
less efficient than what would have been produced before 1349d279.
While developing 1349d279, I had in mind that Incremental Sort would help
us in cases where an index exists only on the GROUP BY column(s).
Incremental Sort would just replace the implicit tuplesorts which are
being performed in nodeAgg.c. However, because the planner has the
flexibility to instead choose a plan which just performs a full sort on
both the GROUP BY and ORDER BY / DISTINCT aggregate columns, there is
potential for the planner to make a bad choice. The costing for
Incremental Sort is not perfect as it assumes an even distribution of rows
to sort within each sort group.
Here we add an escape hatch in the form of the enable_presorted_aggregate
GUC. This will allow users to get the pre-PG16 behavior in cases where
they have no other means to convince the query planner to produce a plan
which only sorts on the GROUP BY column(s).
Discussion: https://postgr.es/m/CAApHDvr1Sm+g9hbv4REOVuvQKeDWXcKUAhmbK5K+dfun0s9CvA@mail.gmail.com
---
doc/src/sgml/config.sgml | 23 +++++++++++++++++++
src/backend/optimizer/path/costsize.c | 1 +
src/backend/optimizer/plan/planner.c | 3 ++-
src/backend/utils/misc/guc_tables.c | 15 ++++++++++++
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/cost.h | 1 +
src/test/regress/expected/aggregates.out | 11 +++++++++
src/test/regress/expected/sysviews.out | 3 ++-
src/test/regress/sql/aggregates.sql | 6 +++++
9 files changed, 62 insertions(+), 2 deletions(-)
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 8e4145979d..9eedab652d 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5311,6 +5311,29 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
</listitem>
</varlistentry>
+ <varlistentry id="guc-enable-presorted-aggregate" xreflabel="enable_presorted_aggregate">
+ <term><varname>enable_presorted_aggregate</varname> (<type>boolean</type>)
+ <indexterm>
+ <primary><varname>enable_presorted_aggregate</varname> configuration parameter</primary>
+ </indexterm>
+ </term>
+ <listitem>
+ <para>
+ Controls if the query planner will produce a plan which will provide
+ rows which are presorted in the order required for the query's
+ <literal>ORDER BY</literal> / <literal>DISTINCT</literal> aggregate
+ functions. When disabled, the query planner will produce a plan which
+ will always require the executor to perform a sort before performing
+ aggregation of each aggregate function containing an
+ <literal>ORDER BY</literal> or <literal>DISTINCT</literal> clause.
+ When enabled, the planner will try to produce a more efficient plan
+ which provides input to the aggregate functions which is presorted in
+ the order they require for aggregation. The default value is
+ <literal>on</literal>.
+ </para>
+ </listitem>
+ </varlistentry>
+
<varlistentry id="guc-enable-seqscan" xreflabel="enable_seqscan">
<term><varname>enable_seqscan</varname> (<type>boolean</type>)
<indexterm>
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 0f0bcfb7e5..89d3c4352c 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -151,6 +151,7 @@ bool enable_partitionwise_aggregate = false;
bool enable_parallel_append = true;
bool enable_parallel_hash = true;
bool enable_partition_pruning = true;
+bool enable_presorted_aggregate = true;
bool enable_async_append = true;
typedef struct
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index dfda251d95..e21e72eb87 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3191,7 +3191,8 @@ make_pathkeys_for_groupagg(PlannerInfo *root, List *groupClause, List *tlist,
* sets. All handling specific to ordered aggregates must be done by the
* executor in that case.
*/
- if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL)
+ if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL ||
+ !enable_presorted_aggregate)
return grouppathkeys;
/*
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 1bf14eec66..436afe1d21 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -971,6 +971,21 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_presorted_aggregate", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables the planner's ability to produce plans which "
+ "provide presorted input for ORDER BY / DISTINCT aggregate "
+ "functions."),
+ gettext_noop("Allows the query planner to build plans which provide "
+ "presorted input for aggregate functions with an ORDER BY / "
+ "DISTINCT clause. When disabled, implicit sorts are always "
+ "performed during execution."),
+ GUC_EXPLAIN
+ },
+ &enable_presorted_aggregate,
+ true,
+ NULL, NULL, NULL
+ },
{
{"enable_async_append", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of async append plans."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 043864597f..5afdeb04de 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -384,6 +384,7 @@
#enable_partition_pruning = on
#enable_partitionwise_join = off
#enable_partitionwise_aggregate = off
+#enable_presorted_aggregate = on
#enable_seqscan = on
#enable_sort = on
#enable_tidscan = on
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 204e94b6d1..b6cc2c9cd6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -68,6 +68,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
extern PGDLLIMPORT bool enable_parallel_append;
extern PGDLLIMPORT bool enable_parallel_hash;
extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_presorted_aggregate;
extern PGDLLIMPORT bool enable_async_append;
extern PGDLLIMPORT int constraint_exclusion;
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index fc2bd40be2..309c2dc865 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1471,6 +1471,17 @@ group by ten;
-> Seq Scan on tenk1
(5 rows)
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+ QUERY PLAN
+-------------------------
+ Aggregate
+ -> Seq Scan on tenk1
+(2 rows)
+
+reset enable_presorted_aggregate;
--
-- Test combinations of DISTINCT and/or ORDER BY
--
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 579b861d84..001c6e7eb9 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -128,10 +128,11 @@ select name, setting from pg_settings where name like 'enable%';
enable_partition_pruning | on
enable_partitionwise_aggregate | off
enable_partitionwise_join | off
+ enable_presorted_aggregate | on
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(20 rows)
+(21 rows)
-- Test that the pg_timezone_names and pg_timezone_abbrevs views are
-- more-or-less working. We can't test their contents in any great detail
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index a4c00ff7a9..15f6be8e15 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -546,6 +546,12 @@ select
from tenk1
group by ten;
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+reset enable_presorted_aggregate;
+
--
-- Test combinations of DISTINCT and/or ORDER BY
--
--
2.35.1.windows.2
Attachments:
[text/plain] v3-0001-Re-adjust-drop-index-concurrently-1-isolation-tes.patch (9.9K, ../CAApHDvptP-VK+ERLVs6UOAWaCQ7y4bf4_SSfRLCSyKWb-rW5zg@mail.gmail.com/2-v3-0001-Re-adjust-drop-index-concurrently-1-isolation-tes.patch)
download | inline diff:
From ed0e0bd525ea16ea724e9794b5f4feddf29da497 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Thu, 15 Dec 2022 17:49:40 +1300
Subject: [PATCH v3 1/3] Re-adjust drop-index-concurrently-1 isolation test
It seems that drop-index-concurrently has started to forget what it was
originally meant to be testing. d2d8a229b, which added incremental sorts
changed the expected plan to be an Index Scan plan instead of a Seq Scan
plan. This occurred as the primary key index of the table in question
provided presorted input and, because that index happened to be the
cheapest input path due to enable_seqscan being disabled, the incremental
sort changes just added a Sort on top of that. It seems based on the name
of the PREPAREd statement that the intention here is that query produce a
seqscan plan.
The reason this test has become broken seems to be due to how the test was
originally coded. It tried to force a seqscan plan by performing some
casting to make it so the test_dc couldn't be used to perform the required
filtering. This likely wasn't the best design. It seems much better just
to toggle enable_seqscan to allow the planner to produce a more
predictable plan. Trying to coax the planner into using a plan which has
costed in a disable_cost seems like it's always going to be flakey. So
let's get rid of that and put the expected plans closer to what they were
originally when the test was added.
Additionally, rename a few things in the test and add some additional
wording to the comments to try and make it more clear in the future what
we expect this test to be doing.
---
.../expected/drop-index-concurrently-1.out | 31 ++++++++++---------
.../expected/drop-index-concurrently-1_2.out | 31 ++++++++++---------
.../specs/drop-index-concurrently-1.spec | 22 +++++++------
3 files changed, 44 insertions(+), 40 deletions(-)
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out b/src/test/isolation/expected/drop-index-concurrently-1.out
index 97e1a6e779..1cb2250891 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -1,17 +1,17 @@
Parsed test spec with 3 sessions
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
is_read_committed
-----------------
t
(1 row)
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
QUERY PLAN
----------------------------------------------
Sort
@@ -20,16 +20,17 @@ Sort
Index Cond: (data = 34)
(4 rows)
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN
-----------------------------------------------
-Sort
- Sort Key: id, data
- -> Index Scan using test_dc_pkey on test_dc
- Filter: ((data)::text = '34'::text)
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN
+---------------------------
+Sort
+ Sort Key: id
+ -> Seq Scan on test_dc
+ Filter: (data = 34)
(4 rows)
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
id|data
--+----
34| 34
@@ -38,14 +39,14 @@ id|data
step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
id|data
---+----
34| 34
134| 34
(2 rows)
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
id|data
---+----
34| 34
diff --git a/src/test/isolation/expected/drop-index-concurrently-1_2.out b/src/test/isolation/expected/drop-index-concurrently-1_2.out
index 04612d3cac..266b0e4ada 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1_2.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1_2.out
@@ -1,17 +1,17 @@
Parsed test spec with 3 sessions
-starting permutation: noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
-step noseq: SET enable_seqscan = false;
+starting permutation: chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
step chkiso: SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation';
is_read_committed
-----------------
f
(1 row)
-step prepi: PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
-step preps: PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data;
+step prepi: PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
+step preps: PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
step begin: BEGIN;
-step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idx;
+step disableseq: SET enable_seqscan = false;
+step explaini: EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan;
QUERY PLAN
----------------------------------------------
Sort
@@ -20,16 +20,17 @@ Sort
Index Cond: (data = 34)
(4 rows)
-step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;
-QUERY PLAN
-----------------------------------------------
-Sort
- Sort Key: id, data
- -> Index Scan using test_dc_pkey on test_dc
- Filter: ((data)::text = '34'::text)
+step enableseq: SET enable_seqscan = true;
+step explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan;
+QUERY PLAN
+---------------------------
+Sort
+ Sort Key: id
+ -> Seq Scan on test_dc
+ Filter: (data = 34)
(4 rows)
-step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;
+step select2: SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data;
id|data
--+----
34| 34
@@ -38,13 +39,13 @@ id|data
step drop: DROP INDEX CONCURRENTLY test_dc_data; <waiting ...>
step insert2: INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100);
step end2: COMMIT;
-step selecti: EXECUTE getrow_idx;
+step selecti: EXECUTE getrow_idxscan;
id|data
--+----
34| 34
(1 row)
-step selects: EXECUTE getrow_seq;
+step selects: EXECUTE getrow_seqscan;
id|data
--+----
34| 34
diff --git a/src/test/isolation/specs/drop-index-concurrently-1.spec b/src/test/isolation/specs/drop-index-concurrently-1.spec
index 812b5de226..a57a02469d 100644
--- a/src/test/isolation/specs/drop-index-concurrently-1.spec
+++ b/src/test/isolation/specs/drop-index-concurrently-1.spec
@@ -3,7 +3,8 @@
# This test shows that the concurrent write behaviour works correctly
# with the expected output being 2 rows at the READ COMMITTED and READ
# UNCOMMITTED transaction isolation levels, and 1 row at the other
-# transaction isolation levels.
+# transaction isolation levels. We ensure this is the case by checking
+# the returned rows in an index scan plan and a seq scan plan.
#
setup
{
@@ -18,24 +19,25 @@ teardown
}
session s1
-step noseq { SET enable_seqscan = false; }
step chkiso { SELECT (setting in ('read committed','read uncommitted')) AS is_read_committed FROM pg_settings WHERE name = 'default_transaction_isolation'; }
-step prepi { PREPARE getrow_idx AS SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
-step preps { PREPARE getrow_seq AS SELECT * FROM test_dc WHERE data::text=34::text ORDER BY id,data; }
+step prepi { PREPARE getrow_idxscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
+step preps { PREPARE getrow_seqscan AS SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
step begin { BEGIN; }
-step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idx; }
-step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seq; }
-step selecti { EXECUTE getrow_idx; }
-step selects { EXECUTE getrow_seq; }
+step disableseq { SET enable_seqscan = false; }
+step explaini { EXPLAIN (COSTS OFF) EXECUTE getrow_idxscan; }
+step enableseq { SET enable_seqscan = true; }
+step explains { EXPLAIN (COSTS OFF) EXECUTE getrow_seqscan; }
+step selecti { EXECUTE getrow_idxscan; }
+step selects { EXECUTE getrow_seqscan; }
step end { COMMIT; }
session s2
setup { BEGIN; }
-step select2 { SELECT * FROM test_dc WHERE data=34 ORDER BY id,data; }
+step select2 { SELECT * FROM test_dc WHERE data = 34 ORDER BY id,data; }
step insert2 { INSERT INTO test_dc(data) SELECT * FROM generate_series(1, 100); }
step end2 { COMMIT; }
session s3
step drop { DROP INDEX CONCURRENTLY test_dc_data; }
-permutation noseq chkiso prepi preps begin explaini explains select2 drop insert2 end2 selecti selects end
+permutation chkiso prepi preps begin disableseq explaini enableseq explains select2 drop insert2 end2 selecti selects end
--
2.35.1.windows.2
[text/plain] v3-0002-Remove-pessimistic-cost-penalization-from-Increme.patch (33.9K, ../CAApHDvptP-VK+ERLVs6UOAWaCQ7y4bf4_SSfRLCSyKWb-rW5zg@mail.gmail.com/3-v3-0002-Remove-pessimistic-cost-penalization-from-Increme.patch)
download | inline diff:
From 3112cc7e40778d3d377660d864db1f218a3b2cf6 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Tue, 8 Nov 2022 14:36:38 +1300
Subject: [PATCH v3 2/3] Remove pessimistic cost penalization from Incremental
Sort
When incremental sorts were added in v13 a 1.5x pessimism factor was added
to the cost modal. Seemingly this was done because the cost modal only
has an estimate of the total number of input rows and the number of
presorted groups. It assumes that the input rows will be evenly
distributed throughout the presorted groups. The 1.5x pessimism factor
was added to slightly reduce the likelihood of incremental sorts being
used in the hope to avoid performance regressions where an incremental
sort plan was picked and turned out slower due to a large skew in the
number of rows in the presorted groups.
An additional quirk with the path generation code meant that we could
consider both a sort and an incremental sort on paths with presorted keys.
This meant that with the pessimism factor, it was possible that we opted
to perform a sort rather than an incremental sort when the given path had
presorted keys.
Here we remove the 1.5x pessimism factor to allow incremental sorts to
have a fairer chance at being chosen against a full sort.
Additionally, this changes how incremental sort paths are generated.
Previously we would generally create a sort path on the cheapest input
path (if that wasn't sorted already) and incremental sort paths on any
path which had presorted keys. This meant that if the cheapest input path
wasn't completely sorted but happened to have presorted keys, we would
create a full sort path *and* an incremental sort path on that input path.
Here we change this logic so that if there are presorted keys, we only
create an incremental sort path, and create sort paths only when a full
sort is required or enable_incremental_sort is disabled.
Both the removal of the cost pessimism factor and the changes made to the
path generation make it more likely that incremental sorts will now be
chosen. That, of course, as with teaching the planner any new tricks,
means an increased likelihood that the planner will perform an incremental
sort when it's not the best method. Our standard escape hatch for these
cases is an enable_* GUC. enable_incremental_sort already exists for
this.
This came out of a report by Pavel Luzanov where he mentioned that v16
was choosing to perform a Seq Scan -> Sort -> Group Aggregate for his
query with an ORDER BY aggregate function. The v15 plan for his query
performed an Index Scan -> Group Aggregate, of course, the aggregate
performed the final sort internally in nodeAgg.c for the aggregate's ORDER
BY. The ideal plan would have been to use the index, which provided
partially sorted input then use an incremental sort to provide the
aggregate with the sorted input. This was not being chosen due to the
pessimism in the incremental sort cost modal, so here we remove that and
rationalize the path generation so that sort and incremental sort plans
don't have to needlessly complete.
Reported-by: Pavel Luzanov
Reviewed-by: Richard Guo
Discussion: https://postgr.es/m/9f61ddbf-2989-1536-b31e-6459370a6baa%40postgrespro.ru
---
.../postgres_fdw/expected/postgres_fdw.out | 2 +
contrib/postgres_fdw/sql/postgres_fdw.sql | 2 +
src/backend/optimizer/path/allpaths.c | 94 ++--
src/backend/optimizer/path/costsize.c | 38 +-
src/backend/optimizer/plan/planner.c | 480 ++++++------------
.../regress/expected/incremental_sort.out | 13 -
src/test/regress/expected/partition_join.out | 5 +-
src/test/regress/sql/incremental_sort.sql | 5 -
8 files changed, 220 insertions(+), 419 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index 2ab3f1efaa..5f6e1f9833 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -2796,6 +2796,7 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
(5 rows)
-- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
explain (verbose, costs off)
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
QUERY PLAN
@@ -2814,6 +2815,7 @@ select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, s
1000 | 4500
(1 row)
+reset enable_incremental_sort;
-- Aggregate is still pushed down by taking unshippable expression out
explain (verbose, costs off)
select c2 * (random() <= 1)::int as sum1, sum(c1) * c2 as sum2 from ft1 group by c2 order by 1, 2;
diff --git a/contrib/postgres_fdw/sql/postgres_fdw.sql b/contrib/postgres_fdw/sql/postgres_fdw.sql
index 51560429e0..bfcac4ea14 100644
--- a/contrib/postgres_fdw/sql/postgres_fdw.sql
+++ b/contrib/postgres_fdw/sql/postgres_fdw.sql
@@ -750,9 +750,11 @@ select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
select c2/2, sum(c2) * (c2/2) from ft1 group by c2/2 order by c2/2;
-- Aggregates in subquery are pushed down.
+set enable_incremental_sort = off;
explain (verbose, costs off)
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
select count(x.a), sum(x.a) from (select c2 a, sum(c1) b from ft1 group by c2, sqrt(c1) order by 1, 2) x;
+reset enable_incremental_sort;
-- Aggregate is still pushed down by taking unshippable expression out
explain (verbose, costs off)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 0c564be7f6..0cfa3a1d6c 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -3207,70 +3207,52 @@ generate_useful_gather_paths(PlannerInfo *root, RelOptInfo *rel, bool override_r
continue;
/*
- * Consider regular sort for the cheapest partial path (for each
- * useful pathkeys). We know the path is not sorted, because we'd
- * not get here otherwise.
+ * 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 (subpath != cheapest_partial_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * Consider regular sort for any path that's not presorted or if
+ * incremental sort is disabled. We've no need to consider both
+ * sort and incremental sort on the same path. We assume that
+ * incremental sort is always faster when there are presorted
+ * keys.
*
* This is not redundant with the gather paths created in
* generate_gather_paths, because that doesn't generate ordered
* output. Here we add an explicit sort to match the useful
* ordering.
*/
- if (cheapest_partial_path == subpath)
+ if (presorted_keys == 0 || !enable_incremental_sort)
{
- Path *tmp;
-
- tmp = (Path *) create_sort_path(root,
- rel,
- subpath,
- useful_pathkeys,
- -1.0);
-
- rows = tmp->rows * tmp->parallel_workers;
-
- path = create_gather_merge_path(root, rel,
- tmp,
- rel->reltarget,
- tmp->pathkeys,
- NULL,
- rowsp);
-
- add_path(rel, &path->path);
-
- /* Fall through */
- }
-
- /*
- * Consider incremental sort, but only when the subpath is already
- * partially sorted on a pathkey prefix.
- */
- if (enable_incremental_sort && presorted_keys > 0)
- {
- Path *tmp;
-
- /*
- * We should have already excluded pathkeys of length 1
- * because then presorted_keys > 0 would imply is_sorted was
- * true.
- */
- Assert(list_length(useful_pathkeys) != 1);
-
- tmp = (Path *) create_incremental_sort_path(root,
- rel,
- subpath,
- useful_pathkeys,
- presorted_keys,
- -1);
-
- path = create_gather_merge_path(root, rel,
- tmp,
- rel->reltarget,
- tmp->pathkeys,
- NULL,
- rowsp);
-
- add_path(rel, &path->path);
+ subpath = (Path *) create_sort_path(root,
+ rel,
+ subpath,
+ useful_pathkeys,
+ -1.0);
+ rows = subpath->rows * subpath->parallel_workers;
}
+ else
+ subpath = (Path *) create_incremental_sort_path(root,
+ rel,
+ subpath,
+ useful_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.c
index 897309d7ec..0f0bcfb7e5 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1959,8 +1959,8 @@ cost_incremental_sort(Path *path,
double input_tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples)
{
- Cost startup_cost = 0,
- run_cost = 0,
+ Cost startup_cost,
+ run_cost,
input_run_cost = input_total_cost - input_startup_cost;
double group_tuples,
input_groups;
@@ -1969,10 +1969,9 @@ cost_incremental_sort(Path *path,
group_input_run_cost;
List *presortedExprs = NIL;
ListCell *l;
- int i = 0;
bool unknown_varno = false;
- Assert(presorted_keys != 0);
+ Assert(presorted_keys > 0 && presorted_keys < list_length(pathkeys));
/*
* We want to be sure the cost of a sort is never estimated as zero, even
@@ -2025,12 +2024,11 @@ cost_incremental_sort(Path *path,
/* expression not containing any Vars with "varno 0" */
presortedExprs = lappend(presortedExprs, member->em_expr);
- i++;
- if (i >= presorted_keys)
+ if (foreach_current_index(l) + 1 >= presorted_keys)
break;
}
- /* Estimate number of groups with equal presorted keys. */
+ /* Estimate the number of groups with equal presorted keys. */
if (!unknown_varno)
input_groups = estimate_num_groups(root, presortedExprs, input_tuples,
NULL, NULL);
@@ -2039,22 +2037,19 @@ cost_incremental_sort(Path *path,
group_input_run_cost = input_run_cost / input_groups;
/*
- * Estimate average cost of sorting of one group where presorted keys are
- * equal. Incremental sort is sensitive to distribution of tuples to the
- * groups, where we're relying on quite rough assumptions. Thus, we're
- * pessimistic about incremental sort performance and increase its average
- * group size by half.
+ * Estimate the average cost of sorting of one group where presorted keys
+ * are equal.
*/
cost_tuplesort(&group_startup_cost, &group_run_cost,
- 1.5 * group_tuples, width, comparison_cost, sort_mem,
+ group_tuples, width, comparison_cost, sort_mem,
limit_tuples);
/*
* Startup cost of incremental sort is the startup cost of its first group
* plus the cost of its input.
*/
- startup_cost += group_startup_cost
- + input_startup_cost + group_input_run_cost;
+ startup_cost = group_startup_cost + input_startup_cost +
+ group_input_run_cost;
/*
* After we started producing tuples from the first group, the cost of
@@ -2062,17 +2057,20 @@ cost_incremental_sort(Path *path,
* group, plus the total cost to process the remaining groups, plus the
* remaining cost of input.
*/
- run_cost += group_run_cost
- + (group_run_cost + group_startup_cost) * (input_groups - 1)
- + group_input_run_cost * (input_groups - 1);
+ run_cost = group_run_cost + (group_run_cost + group_startup_cost) *
+ (input_groups - 1) + group_input_run_cost * (input_groups - 1);
/*
* Incremental sort adds some overhead by itself. Firstly, it has to
* detect the sort groups. This is roughly equal to one extra copy and
- * comparison per tuple. Secondly, it has to reset the tuplesort context
- * for every group.
+ * comparison per tuple.
*/
run_cost += (cpu_tuple_cost + comparison_cost) * input_tuples;
+
+ /*
+ * Additionally, we charge double cpu_tuple_cost for each input group to
+ * account for the tuplesort_reset that's performed after each group.
+ */
run_cost += 2.0 * cpu_tuple_cost * input_groups;
path->rows = input_tuples;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 5dd4f92720..dfda251d95 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4965,7 +4965,7 @@ create_ordered_paths(PlannerInfo *root,
foreach(lc, input_rel->pathlist)
{
Path *input_path = (Path *) lfirst(lc);
- Path *sorted_path = input_path;
+ Path *sorted_path;
bool is_sorted;
int presorted_keys;
@@ -4973,69 +4973,46 @@ create_ordered_paths(PlannerInfo *root,
input_path->pathkeys, &presorted_keys);
if (is_sorted)
- {
- /* Use the input path as is, but add a 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);
- }
+ sorted_path = input_path;
else
{
/*
- * Try adding an explicit sort, but only to the cheapest total
- * path since a full sort should generally add the same cost to
- * all paths.
+ * 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_input_path)
- {
- /*
- * Sort the cheapest input path. An explicit sort here can
- * take advantage of LIMIT.
- */
+ if (input_path != cheapest_input_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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);
- /* 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);
- }
-
- /*
- * If incremental sort is enabled, then try it as well. Unlike
- * with regular sorts, we can't just look at the cheapest path,
- * because the cost of incremental sort depends on how well
- * presorted the path is. Additionally incremental sort may enable
- * a cheaper startup path to win out despite higher total cost.
- */
- if (!enable_incremental_sort)
- continue;
-
- /* Likewise, if the path can't be used for incremental sort. */
- if (!presorted_keys)
- continue;
-
- /* Also consider incremental sort. */
- sorted_path = (Path *) create_incremental_sort_path(root,
- ordered_rel,
- input_path,
- root->sort_pathkeys,
- presorted_keys,
- limit_tuples);
+ else
+ sorted_path = (Path *) create_incremental_sort_path(root,
+ ordered_rel,
+ input_path,
+ root->sort_pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
- /* Add projection step if needed */
- if (sorted_path->pathtarget != target)
- sorted_path = apply_projection_to_path(root, ordered_rel,
- sorted_path, target);
+ /* 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);
- }
+ add_path(ordered_rel, sorted_path);
}
/*
@@ -6501,12 +6478,12 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
{
/*
* Use any available suitably-sorted path as input, and also consider
- * sorting the cheapest-total path.
+ * sorting the cheapest-total path and incremental sort on any paths
+ * with presorted keys.
*/
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -6514,90 +6491,39 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
path->pathkeys,
&presorted_keys);
- if (path == cheapest_path || is_sorted)
+ if (!is_sorted)
{
- /* Sort the cheapest-total path if it isn't already sorted */
- if (!is_sorted)
+ /*
+ * 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_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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,
grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- /* Now decide what to stick atop it */
- if (parse->groupingSets)
- {
- consider_groupingsets_paths(root, grouped_rel,
- path, true, can_hash,
- gd, agg_costs, dNumGroups);
- }
- else if (parse->hasAggs)
- {
- /*
- * We have aggregation, possibly with plain GROUP BY. Make
- * an AggPath.
- */
- add_path(grouped_rel, (Path *)
- create_agg_path(root,
- grouped_rel,
- path,
- grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_SIMPLE,
- parse->groupClause,
- havingQual,
- agg_costs,
- dNumGroups));
- }
- else if (parse->groupClause)
- {
- /*
- * We have GROUP BY without aggregation or grouping sets.
- * Make a GroupPath.
- */
- add_path(grouped_rel, (Path *)
- create_group_path(root,
- grouped_rel,
- path,
- parse->groupClause,
- havingQual,
- dNumGroups));
- }
else
- {
- /* Other cases should have been handled above */
- Assert(false);
- }
+ path = (Path *) create_incremental_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental sort
- * is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, no point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1 because
- * then presorted_keys > 0 would imply is_sorted was true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
/* Now decide what to stick atop it */
if (parse->groupingSets)
{
@@ -6653,7 +6579,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
foreach(lc, partially_grouped_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -6661,19 +6586,38 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
path->pathkeys,
&presorted_keys);
- /*
- * Insert a Sort node, if required. But there's no point in
- * sorting anything but the cheapest path.
- */
if (!is_sorted)
{
- if (path != partially_grouped_rel->cheapest_total_path)
+ /*
+ * 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 != partially_grouped_rel->cheapest_total_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
continue;
- path = (Path *) create_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- -1.0);
+
+ /*
+ * We've no need to consider both a sort and incremental
+ * sort. We'll just do a sort if there are no pre-sorted
+ * keys and an incremental sort when there are presorted
+ * keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ -1.0);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
if (parse->hasAggs)
@@ -6697,55 +6641,6 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
havingQual,
dNumGroups));
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental
- * sort is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, not point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1
- * because then presorted_keys > 0 would imply is_sorted was
- * true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
- if (parse->hasAggs)
- add_path(grouped_rel, (Path *)
- create_agg_path(root,
- grouped_rel,
- path,
- grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_FINAL_DESERIAL,
- parse->groupClause,
- havingQual,
- agg_final_costs,
- dNumGroups));
- else
- add_path(grouped_rel, (Path *)
- create_group_path(root,
- grouped_rel,
- path,
- parse->groupClause,
- havingQual,
- dNumGroups));
}
}
}
@@ -6950,97 +6845,64 @@ create_partial_grouping_paths(PlannerInfo *root,
{
Path *path = (Path *) lfirst(lc);
bool is_sorted;
+ int presorted_keys;
- is_sorted = pathkeys_contained_in(root->group_pathkeys,
- path->pathkeys);
- if (path == cheapest_total_path || is_sorted)
+ is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+ if (!is_sorted)
{
- /* Sort the cheapest partial path, if it isn't already */
- if (!is_sorted)
+ /*
+ * 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_total_path &&
+ (presorted_keys == 0 || !enable_incremental_sort))
+ continue;
+
+ /*
+ * 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,
partially_grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- if (parse->hasAggs)
- add_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialGroups));
else
- add_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialGroups));
+ path = (Path *) create_incremental_sort_path(root,
+ partially_grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- }
-
- /*
- * 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)
- {
- foreach(lc, input_rel->pathlist)
- {
- Path *path = (Path *) lfirst(lc);
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(root->group_pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- /* Ignore already sorted paths */
- if (is_sorted)
- continue;
-
- if (presorted_keys == 0)
- continue;
- /* Since we have presorted keys, consider incremental sort. */
- path = (Path *) create_incremental_sort_path(root,
- partially_grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
- if (parse->hasAggs)
- add_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialGroups));
- else
- add_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialGroups));
- }
+ if (parse->hasAggs)
+ add_path(partially_grouped_rel, (Path *)
+ create_agg_path(root,
+ partially_grouped_rel,
+ path,
+ partially_grouped_rel->reltarget,
+ parse->groupClause ? AGG_SORTED : AGG_PLAIN,
+ AGGSPLIT_INITIAL_SERIAL,
+ parse->groupClause,
+ NIL,
+ agg_partial_costs,
+ dNumPartialGroups));
+ else
+ add_path(partially_grouped_rel, (Path *)
+ create_group_path(root,
+ partially_grouped_rel,
+ path,
+ parse->groupClause,
+ NIL,
+ dNumPartialGroups));
}
}
@@ -7050,7 +6912,6 @@ create_partial_grouping_paths(PlannerInfo *root,
foreach(lc, input_rel->partial_pathlist)
{
Path *path = (Path *) lfirst(lc);
- Path *path_original = path;
bool is_sorted;
int presorted_keys;
@@ -7058,66 +6919,39 @@ create_partial_grouping_paths(PlannerInfo *root,
path->pathkeys,
&presorted_keys);
- if (path == cheapest_partial_path || is_sorted)
+ if (!is_sorted)
{
- /* Sort the cheapest partial path, if it isn't already */
- if (!is_sorted)
+ /*
+ * 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;
+
+ /*
+ * 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,
partially_grouped_rel,
path,
root->group_pathkeys,
-1.0);
-
- if (parse->hasAggs)
- add_partial_path(partially_grouped_rel, (Path *)
- create_agg_path(root,
- partially_grouped_rel,
- path,
- partially_grouped_rel->reltarget,
- parse->groupClause ? AGG_SORTED : AGG_PLAIN,
- AGGSPLIT_INITIAL_SERIAL,
- parse->groupClause,
- NIL,
- agg_partial_costs,
- dNumPartialPartialGroups));
else
- add_partial_path(partially_grouped_rel, (Path *)
- create_group_path(root,
- partially_grouped_rel,
- path,
- parse->groupClause,
- NIL,
- dNumPartialPartialGroups));
+ path = (Path *) create_incremental_sort_path(root,
+ partially_grouped_rel,
+ path,
+ root->group_pathkeys,
+ presorted_keys,
+ -1.0);
}
- /*
- * Now we may consider incremental sort on this path, but only
- * when the path is not already sorted and when incremental sort
- * is enabled.
- */
- if (is_sorted || !enable_incremental_sort)
- continue;
-
- /* Restore the input path (we might have added Sort on top). */
- path = path_original;
-
- /* no shared prefix, not point in building incremental sort */
- if (presorted_keys == 0)
- continue;
-
- /*
- * We should have already excluded pathkeys of length 1 because
- * then presorted_keys > 0 would imply is_sorted was true.
- */
- Assert(list_length(root->group_pathkeys) != 1);
-
- path = (Path *) create_incremental_sort_path(root,
- partially_grouped_rel,
- path,
- root->group_pathkeys,
- presorted_keys,
- -1.0);
-
if (parse->hasAggs)
add_partial_path(partially_grouped_rel, (Path *)
create_agg_path(root,
diff --git a/src/test/regress/expected/incremental_sort.out b/src/test/regress/expected/incremental_sort.out
index 0a631124c2..1a1e8b2365 100644
--- a/src/test/regress/expected/incremental_sort.out
+++ b/src/test/regress/expected/incremental_sort.out
@@ -1,16 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
- QUERY PLAN
------------------------------------
- Sort
- Sort Key: tenk1.four, tenk1.ten
- -> Sort
- Sort Key: tenk1.four
- -> Seq Scan on tenk1
-(5 rows)
-
-- When there is a LIMIT clause, incremental sort is beneficial because
-- it only has to sort some of the groups, and not the entire table.
explain (costs off)
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index b20facc19f..c59caf1cb3 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -1173,8 +1173,9 @@ EXPLAIN (COSTS OFF)
SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
QUERY PLAN
-----------------------------------------------------------
- Sort
+ Incremental Sort
Sort Key: prt1.a, prt2.b
+ Presorted Key: prt1.a
-> Merge Left Join
Merge Cond: (prt1.a = prt2.b)
-> Sort
@@ -1191,7 +1192,7 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
Filter: (b > 250)
-> Seq Scan on prt2_p3 prt2_2
Filter: (b > 250)
-(18 rows)
+(19 rows)
SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT * FROM prt2 WHERE b > 250) t2 ON t1.a = t2.b WHERE t1.b = 0 ORDER BY t1.a, t2.b;
a | b
diff --git a/src/test/regress/sql/incremental_sort.sql b/src/test/regress/sql/incremental_sort.sql
index 284a354dbb..071f8a5268 100644
--- a/src/test/regress/sql/incremental_sort.sql
+++ b/src/test/regress/sql/incremental_sort.sql
@@ -1,8 +1,3 @@
--- When we have to sort the entire table, incremental sort will
--- be slower than plain sort, so it should not be used.
-explain (costs off)
-select * from (select * from tenk1 order by four) t order by four, ten;
-
-- When there is a LIMIT clause, incremental sort is beneficial because
-- it only has to sort some of the groups, and not the entire table.
explain (costs off)
--
2.35.1.windows.2
[text/plain] v3-0003-Add-enable_presorted_aggregate-GUC.patch (9.1K, ../CAApHDvptP-VK+ERLVs6UOAWaCQ7y4bf4_SSfRLCSyKWb-rW5zg@mail.gmail.com/4-v3-0003-Add-enable_presorted_aggregate-GUC.patch)
download | inline diff:
From 0eb650dd777925d28ff3c47ffbae244f06386d55 Mon Sep 17 00:00:00 2001
From: David Rowley <[email protected]>
Date: Wed, 14 Dec 2022 10:25:19 +1300
Subject: [PATCH v3 3/3] Add enable_presorted_aggregate GUC
1349d279 added query planner support to allow more efficient execution of
aggregate functions which have an ORDER BY or a DISTINCT clause. Prior to
that commit, the planner would only request that the lower planner produce
a plan with the order required for the GROUP BY clause and it would be
left up to nodeAgg.c to perform the final sort of records within each
group so that the aggregate transition functions were called in the
correct order. Now that the planner requests the lower planner produce a
plan with the GROUP BY and the ORDER BY / DISTINCT aggregates in mind,
there is the possibility that the planner chooses a plan which could be
less efficient than what would have been produced before 1349d279.
While developing 1349d279, I had in mind that Incremental Sort would help
us in cases where an index exists only on the GROUP BY column(s).
Incremental Sort would just replace the implicit tuplesorts which are
being performed in nodeAgg.c. However, because the planner has the
flexibility to instead choose a plan which just performs a full sort on
both the GROUP BY and ORDER BY / DISTINCT aggregate columns, there is
potential for the planner to make a bad choice. The costing for
Incremental Sort is not perfect as it assumes an even distribution of rows
to sort within each sort group.
Here we add an escape hatch in the form of the enable_presorted_aggregate
GUC. This will allow users to get the pre-PG16 behavior in cases where
they have no other means to convince the query planner to produce a plan
which only sorts on the GROUP BY column(s).
Discussion: https://postgr.es/m/CAApHDvr1Sm+g9hbv4REOVuvQKeDWXcKUAhmbK5K+dfun0s9CvA@mail.gmail.com
---
doc/src/sgml/config.sgml | 23 +++++++++++++++++++
src/backend/optimizer/path/costsize.c | 1 +
src/backend/optimizer/plan/planner.c | 3 ++-
src/backend/utils/misc/guc_tables.c | 15 ++++++++++++
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/cost.h | 1 +
src/test/regress/expected/aggregates.out | 11 +++++++++
src/test/regress/expected/sysviews.out | 3 ++-
src/test/regress/sql/aggregates.sql | 6 +++++
9 files changed, 62 insertions(+), 2 deletions(-)
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index 8e4145979d..9eedab652d 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5311,6 +5311,29 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
</listitem>
</varlistentry>
+ <varlistentry id="guc-enable-presorted-aggregate" xreflabel="enable_presorted_aggregate">
+ <term><varname>enable_presorted_aggregate</varname> (<type>boolean</type>)
+ <indexterm>
+ <primary><varname>enable_presorted_aggregate</varname> configuration parameter</primary>
+ </indexterm>
+ </term>
+ <listitem>
+ <para>
+ Controls if the query planner will produce a plan which will provide
+ rows which are presorted in the order required for the query's
+ <literal>ORDER BY</literal> / <literal>DISTINCT</literal> aggregate
+ functions. When disabled, the query planner will produce a plan which
+ will always require the executor to perform a sort before performing
+ aggregation of each aggregate function containing an
+ <literal>ORDER BY</literal> or <literal>DISTINCT</literal> clause.
+ When enabled, the planner will try to produce a more efficient plan
+ which provides input to the aggregate functions which is presorted in
+ the order they require for aggregation. The default value is
+ <literal>on</literal>.
+ </para>
+ </listitem>
+ </varlistentry>
+
<varlistentry id="guc-enable-seqscan" xreflabel="enable_seqscan">
<term><varname>enable_seqscan</varname> (<type>boolean</type>)
<indexterm>
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 0f0bcfb7e5..89d3c4352c 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -151,6 +151,7 @@ bool enable_partitionwise_aggregate = false;
bool enable_parallel_append = true;
bool enable_parallel_hash = true;
bool enable_partition_pruning = true;
+bool enable_presorted_aggregate = true;
bool enable_async_append = true;
typedef struct
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index dfda251d95..e21e72eb87 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -3191,7 +3191,8 @@ make_pathkeys_for_groupagg(PlannerInfo *root, List *groupClause, List *tlist,
* sets. All handling specific to ordered aggregates must be done by the
* executor in that case.
*/
- if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL)
+ if (root->numOrderedAggs == 0 || root->parse->groupingSets != NIL ||
+ !enable_presorted_aggregate)
return grouppathkeys;
/*
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 1bf14eec66..436afe1d21 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -971,6 +971,21 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_presorted_aggregate", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables the planner's ability to produce plans which "
+ "provide presorted input for ORDER BY / DISTINCT aggregate "
+ "functions."),
+ gettext_noop("Allows the query planner to build plans which provide "
+ "presorted input for aggregate functions with an ORDER BY / "
+ "DISTINCT clause. When disabled, implicit sorts are always "
+ "performed during execution."),
+ GUC_EXPLAIN
+ },
+ &enable_presorted_aggregate,
+ true,
+ NULL, NULL, NULL
+ },
{
{"enable_async_append", PGC_USERSET, QUERY_TUNING_METHOD,
gettext_noop("Enables the planner's use of async append plans."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 043864597f..5afdeb04de 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -384,6 +384,7 @@
#enable_partition_pruning = on
#enable_partitionwise_join = off
#enable_partitionwise_aggregate = off
+#enable_presorted_aggregate = on
#enable_seqscan = on
#enable_sort = on
#enable_tidscan = on
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index 204e94b6d1..b6cc2c9cd6 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -68,6 +68,7 @@ extern PGDLLIMPORT bool enable_partitionwise_aggregate;
extern PGDLLIMPORT bool enable_parallel_append;
extern PGDLLIMPORT bool enable_parallel_hash;
extern PGDLLIMPORT bool enable_partition_pruning;
+extern PGDLLIMPORT bool enable_presorted_aggregate;
extern PGDLLIMPORT bool enable_async_append;
extern PGDLLIMPORT int constraint_exclusion;
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index fc2bd40be2..309c2dc865 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1471,6 +1471,17 @@ group by ten;
-> Seq Scan on tenk1
(5 rows)
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+ QUERY PLAN
+-------------------------
+ Aggregate
+ -> Seq Scan on tenk1
+(2 rows)
+
+reset enable_presorted_aggregate;
--
-- Test combinations of DISTINCT and/or ORDER BY
--
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 579b861d84..001c6e7eb9 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -128,10 +128,11 @@ select name, setting from pg_settings where name like 'enable%';
enable_partition_pruning | on
enable_partitionwise_aggregate | off
enable_partitionwise_join | off
+ enable_presorted_aggregate | on
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(20 rows)
+(21 rows)
-- Test that the pg_timezone_names and pg_timezone_abbrevs views are
-- more-or-less working. We can't test their contents in any great detail
diff --git a/src/test/regress/sql/aggregates.sql b/src/test/regress/sql/aggregates.sql
index a4c00ff7a9..15f6be8e15 100644
--- a/src/test/regress/sql/aggregates.sql
+++ b/src/test/regress/sql/aggregates.sql
@@ -546,6 +546,12 @@ select
from tenk1
group by ten;
+-- Ensure no ordering is requested when enable_presorted_aggregate is off
+set enable_presorted_aggregate to off;
+explain (costs off)
+select sum(two order by two) from tenk1;
+reset enable_presorted_aggregate;
+
--
-- Test combinations of DISTINCT and/or ORDER BY
--
--
2.35.1.windows.2
view thread (64+ messages) latest in thread
reply
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: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]
Subject: Re: Add proper planner support for ORDER BY / DISTINCT aggregates
In-Reply-To: <CAApHDvptP-VK+ERLVs6UOAWaCQ7y4bf4_SSfRLCSyKWb-rW5zg@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox