Hi.
Now when planner finds suitable pathkeys in
generate_orderedappend_paths(), it uses them, even if explicit sort of
the cheapest child path could be more efficient.
We encountered this issue on partitioned table with two indexes, where
one is suitable for sorting, and another is good for selecting data.
MergeAppend was generated
with subpaths doing index scan on suitably ordered index and filtering a
lot of data.
The suggested fix allows MergeAppend to consider sorting on cheapest
childrel total path as an alternative.
--
Best regards,
Alexander Pyhalov,
Postgres Professional
From d5eb3d326d83e2ca47c17552fcc6fd27b6b98d4e Mon Sep 17 00:00:00 2001
From: Alexander Pyhalov <a.pyha...@postgrespro.ru>
Date: Tue, 18 Jun 2024 15:56:18 +0300
Subject: [PATCH] MergeAppend could consider using sorted best path.
This helps when index with suitable pathkeys is not
good for filtering data.
---
.../postgres_fdw/expected/postgres_fdw.out | 6 +-
src/backend/optimizer/path/allpaths.c | 21 +++++
src/test/regress/expected/inherit.out | 45 +++++++++-
src/test/regress/expected/partition_join.out | 87 +++++++++++--------
src/test/regress/expected/union.out | 6 +-
src/test/regress/sql/inherit.sql | 17 ++++
6 files changed, 141 insertions(+), 41 deletions(-)
diff --git a/contrib/postgres_fdw/expected/postgres_fdw.out b/contrib/postgres_fdw/expected/postgres_fdw.out
index ea566d50341..687591e4a97 100644
--- a/contrib/postgres_fdw/expected/postgres_fdw.out
+++ b/contrib/postgres_fdw/expected/postgres_fdw.out
@@ -10074,13 +10074,15 @@ SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2 ON (t1.a = t2.b) WHERE t1.a
-> Nested Loop
Join Filter: (t1.a = t2.b)
-> Append
- -> Foreign Scan on ftprt1_p1 t1_1
+ -> Sort
+ Sort Key: t1_1.a
+ -> Foreign Scan on ftprt1_p1 t1_1
-> Foreign Scan on ftprt1_p2 t1_2
-> Materialize
-> Append
-> Foreign Scan on ftprt2_p1 t2_1
-> Foreign Scan on ftprt2_p2 t2_2
-(10 rows)
+(12 rows)
SELECT t1.a, t2.b FROM fprt1 t1 INNER JOIN fprt2 t2 ON (t1.a = t2.b) WHERE t1.a % 25 = 0 ORDER BY 1,2 FOR UPDATE OF t1;
a | b
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4895cee9944..827bc469269 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -1845,6 +1845,27 @@ generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
/* Assert we do have an unparameterized path for this child */
Assert(cheapest_total->param_info == NULL);
}
+ else
+ {
+ /*
+ * Even if we found necessary pathkeys, using unsorted path
+ * can be more efficient.
+ */
+ Path sort_path;
+
+ cost_sort(&sort_path,
+ root,
+ pathkeys,
+ childrel->cheapest_total_path->total_cost,
+ childrel->cheapest_total_path->rows,
+ childrel->cheapest_total_path->pathtarget->width,
+ 0.0,
+ work_mem,
+ -1.0 /* need all tuples to sort them */ );
+
+ if (compare_path_costs(&sort_path, cheapest_total, TOTAL_COST) < 0)
+ cheapest_total = childrel->cheapest_total_path;
+ }
/*
* When building a fractional path, determine a cheapest
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
index ad732134148..16e78c8d2ff 100644
--- a/src/test/regress/expected/inherit.out
+++ b/src/test/regress/expected/inherit.out
@@ -1555,6 +1555,7 @@ insert into matest2 (name) values ('Test 4');
insert into matest3 (name) values ('Test 5');
insert into matest3 (name) values ('Test 6');
set enable_indexscan = off; -- force use of seqscan/sort, so no merge
+set enable_sort = off; -- avoid sorting below MergeAppend
explain (verbose, costs off) select * from matest0 order by 1-id;
QUERY PLAN
------------------------------------------------------------
@@ -1608,6 +1609,7 @@ select min(1-id) from matest0;
(1 row)
reset enable_indexscan;
+reset enable_sort;
set enable_seqscan = off; -- plan with fewest seqscans should be merge
set enable_parallel_append = off; -- Don't let parallel-append interfere
explain (verbose, costs off) select * from matest0 order by 1-id;
@@ -1702,7 +1704,9 @@ order by t1.b limit 10;
Merge Cond: (t1.b = t2.b)
-> Merge Append
Sort Key: t1.b
- -> Index Scan using matest0i on matest0 t1_1
+ -> Sort
+ Sort Key: t1_1.b
+ -> Seq Scan on matest0 t1_1
-> Index Scan using matest1i on matest1 t1_2
-> Materialize
-> Merge Append
@@ -1711,7 +1715,7 @@ order by t1.b limit 10;
Filter: (c = d)
-> Index Scan using matest1i on matest1 t2_2
Filter: (c = d)
-(14 rows)
+(16 rows)
reset enable_nestloop;
drop table matest0 cascade;
@@ -2663,6 +2667,43 @@ explain (costs off) select * from mcrparted where a = 10 order by a, abs(b), c;
reset enable_bitmapscan;
drop table mcrparted;
+-- Check that sort path can be used by MergeAppend even when there are suitable pathkeys
+create table hash_parted (i int, j int, k int) partition by hash(i);
+create table hash_parted_1 partition of hash_parted for values with (modulus 4, remainder 0);
+create table hash_parted_2 partition of hash_parted for values with (modulus 4, remainder 1);
+create table hash_parted_3 partition of hash_parted for values with (modulus 4, remainder 2);
+create table hash_parted_4 partition of hash_parted for values with (modulus 4, remainder 3);
+--create table hash_parted_5 partition of hash_parted for values with (modulus 6, remainder 4);
+--create table hash_parted_6 partition of hash_parted for values with (modulus 6, remainder 5);
+create index on hash_parted(j);
+create index on hash_parted(k);
+insert into hash_parted select i, i, i from generate_series(1,10000) i;
+analyze hash_parted;
+explain (costs off) select * from hash_parted where k<100 order by j limit 100;
+ QUERY PLAN
+-------------------------------------------------------------------------
+ Limit
+ -> Merge Append
+ Sort Key: hash_parted.j
+ -> Sort
+ Sort Key: hash_parted_1.j
+ -> Index Scan using hash_parted_1_k_idx on hash_parted_1
+ Index Cond: (k < 100)
+ -> Sort
+ Sort Key: hash_parted_2.j
+ -> Index Scan using hash_parted_2_k_idx on hash_parted_2
+ Index Cond: (k < 100)
+ -> Sort
+ Sort Key: hash_parted_3.j
+ -> Index Scan using hash_parted_3_k_idx on hash_parted_3
+ Index Cond: (k < 100)
+ -> Sort
+ Sort Key: hash_parted_4.j
+ -> Index Scan using hash_parted_4_k_idx on hash_parted_4
+ Index Cond: (k < 100)
+(19 rows)
+
+drop table hash_parted;
-- Ensure LIST partitions allow an Append to be used instead of a MergeAppend
create table bool_lp (b bool) partition by list(b);
create table bool_lp_true partition of bool_lp for values in(true);
diff --git a/src/test/regress/expected/partition_join.out b/src/test/regress/expected/partition_join.out
index 6d07f86b9bc..80d480d33d5 100644
--- a/src/test/regress/expected/partition_join.out
+++ b/src/test/regress/expected/partition_join.out
@@ -1309,28 +1309,32 @@ SELECT t1.a, t1.c, t2.b, t2.c, t3.a + t3.b, t3.c FROM (prt1 t1 LEFT JOIN prt2 t2
-- This should generate a partitionwise join, but currently fails to
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
------------------------------------------------------------
- Incremental Sort
+ QUERY PLAN
+-----------------------------------------------------------------
+ Sort
Sort Key: prt1.a, prt2.b
- Presorted Key: prt1.a
- -> Merge Left Join
- Merge Cond: (prt1.a = prt2.b)
- -> Sort
- Sort Key: prt1.a
- -> Append
- -> Seq Scan on prt1_p1 prt1_1
- Filter: ((a < 450) AND (b = 0))
- -> Seq Scan on prt1_p2 prt1_2
- Filter: ((a < 450) AND (b = 0))
- -> Sort
- Sort Key: prt2.b
- -> Append
+ -> Merge Right Join
+ Merge Cond: (prt2.b = prt1.a)
+ -> Append
+ -> Sort
+ Sort Key: prt2_1.b
-> Seq Scan on prt2_p2 prt2_1
Filter: (b > 250)
+ -> Sort
+ Sort Key: prt2_2.b
-> Seq Scan on prt2_p3 prt2_2
Filter: (b > 250)
-(19 rows)
+ -> Materialize
+ -> Append
+ -> Sort
+ Sort Key: prt1_1.a
+ -> Seq Scan on prt1_p1 prt1_1
+ Filter: ((a < 450) AND (b = 0))
+ -> Sort
+ Sort Key: prt1_2.a
+ -> Seq Scan on prt1_p2 prt1_2
+ Filter: ((a < 450) AND (b = 0))
+(23 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
@@ -1350,25 +1354,33 @@ SELECT t1.a, t2.b FROM (SELECT * FROM prt1 WHERE a < 450) t1 LEFT JOIN (SELECT *
-- partitionwise join does not apply
EXPLAIN (COSTS OFF)
SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a = t2.b ORDER BY t1.a;
- QUERY PLAN
------------------------------------------------------------------------------------------
+ QUERY PLAN
+------------------------------------------------------------------
Merge Join
- Merge Cond: ((t1.a = t2.b) AND (((((t1.*)::prt1))::text) = ((((t2.*)::prt2))::text)))
- -> Sort
- Sort Key: t1.a, ((((t1.*)::prt1))::text)
- -> Result
- -> Append
- -> Seq Scan on prt1_p1 t1_1
- -> Seq Scan on prt1_p2 t1_2
- -> Seq Scan on prt1_p3 t1_3
- -> Sort
- Sort Key: t2.b, ((((t2.*)::prt2))::text)
- -> Result
- -> Append
+ Merge Cond: (t1.a = t2.b)
+ Join Filter: ((((t2.*)::prt2))::text = (((t1.*)::prt1))::text)
+ -> Append
+ -> Sort
+ Sort Key: t1_1.a
+ -> Seq Scan on prt1_p1 t1_1
+ -> Sort
+ Sort Key: t1_2.a
+ -> Seq Scan on prt1_p2 t1_2
+ -> Sort
+ Sort Key: t1_3.a
+ -> Seq Scan on prt1_p3 t1_3
+ -> Materialize
+ -> Append
+ -> Sort
+ Sort Key: t2_1.b
-> Seq Scan on prt2_p1 t2_1
+ -> Sort
+ Sort Key: t2_2.b
-> Seq Scan on prt2_p2 t2_2
+ -> Sort
+ Sort Key: t2_3.b
-> Seq Scan on prt2_p3 t2_3
-(16 rows)
+(24 rows)
SELECT t1.a, t2.b FROM prt1 t1, prt2 t2 WHERE t1::text = t2::text AND t1.a = t2.b ORDER BY t1.a;
a | b
@@ -4906,21 +4918,26 @@ EXPLAIN (COSTS OFF)
SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2.b) WHERE t1.b >= 125 AND t1.b < 225 ORDER BY t1.a, t1.b;
QUERY PLAN
--------------------------------------------------------------------
- Sort
+ Merge Append
Sort Key: t1.a, t1.b
- -> Append
+ -> Sort
+ Sort Key: t1_1.a, t1_1.b
-> Hash Join
Hash Cond: ((t1_1.a = t2_1.a) AND (t1_1.b = t2_1.b))
-> Seq Scan on alpha_neg_p1 t1_1
Filter: ((b >= 125) AND (b < 225))
-> Hash
-> Seq Scan on beta_neg_p1 t2_1
+ -> Sort
+ Sort Key: t1_2.a, t1_2.b
-> Hash Join
Hash Cond: ((t2_2.a = t1_2.a) AND (t2_2.b = t1_2.b))
-> Seq Scan on beta_neg_p2 t2_2
-> Hash
-> Seq Scan on alpha_neg_p2 t1_2
Filter: ((b >= 125) AND (b < 225))
+ -> Sort
+ Sort Key: t1_4.a, t1_4.b
-> Hash Join
Hash Cond: ((t2_4.a = t1_4.a) AND (t2_4.b = t1_4.b))
-> Append
@@ -4935,7 +4952,7 @@ SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2
Filter: ((b >= 125) AND (b < 225))
-> Seq Scan on alpha_pos_p3 t1_6
Filter: ((b >= 125) AND (b < 225))
-(29 rows)
+(34 rows)
SELECT t1.*, t2.* FROM alpha t1 INNER JOIN beta t2 ON (t1.a = t2.a AND t1.b = t2.b) WHERE t1.b >= 125 AND t1.b < 225 ORDER BY t1.a, t1.b;
a | b | c | a | b | c
diff --git a/src/test/regress/expected/union.out b/src/test/regress/expected/union.out
index 0fd0e1c38b3..4c1c173d8e6 100644
--- a/src/test/regress/expected/union.out
+++ b/src/test/regress/expected/union.out
@@ -1195,12 +1195,14 @@ select event_id
----------------------------------------------------------
Merge Append
Sort Key: events.event_id
- -> Index Scan using events_pkey on events
+ -> Sort
+ Sort Key: events.event_id
+ -> Seq Scan on events
-> Sort
Sort Key: events_1.event_id
-> Seq Scan on events_child events_1
-> Index Scan using other_events_pkey on other_events
-(7 rows)
+(9 rows)
drop table events_child, events, other_events;
reset enable_indexonlyscan;
diff --git a/src/test/regress/sql/inherit.sql b/src/test/regress/sql/inherit.sql
index e3bcfdb181e..5331e49283f 100644
--- a/src/test/regress/sql/inherit.sql
+++ b/src/test/regress/sql/inherit.sql
@@ -586,11 +586,13 @@ insert into matest3 (name) values ('Test 5');
insert into matest3 (name) values ('Test 6');
set enable_indexscan = off; -- force use of seqscan/sort, so no merge
+set enable_sort = off; -- avoid sorting below MergeAppend
explain (verbose, costs off) select * from matest0 order by 1-id;
select * from matest0 order by 1-id;
explain (verbose, costs off) select min(1-id) from matest0;
select min(1-id) from matest0;
reset enable_indexscan;
+reset enable_sort;
set enable_seqscan = off; -- plan with fewest seqscans should be merge
set enable_parallel_append = off; -- Don't let parallel-append interfere
@@ -976,6 +978,21 @@ reset enable_bitmapscan;
drop table mcrparted;
+-- Check that sort path can be used by MergeAppend even when there are suitable pathkeys
+create table hash_parted (i int, j int, k int) partition by hash(i);
+create table hash_parted_1 partition of hash_parted for values with (modulus 4, remainder 0);
+create table hash_parted_2 partition of hash_parted for values with (modulus 4, remainder 1);
+create table hash_parted_3 partition of hash_parted for values with (modulus 4, remainder 2);
+create table hash_parted_4 partition of hash_parted for values with (modulus 4, remainder 3);
+--create table hash_parted_5 partition of hash_parted for values with (modulus 6, remainder 4);
+--create table hash_parted_6 partition of hash_parted for values with (modulus 6, remainder 5);
+create index on hash_parted(j);
+create index on hash_parted(k);
+insert into hash_parted select i, i, i from generate_series(1,10000) i;
+analyze hash_parted;
+explain (costs off) select * from hash_parted where k<100 order by j limit 100;
+drop table hash_parted;
+
-- Ensure LIST partitions allow an Append to be used instead of a MergeAppend
create table bool_lp (b bool) partition by list(b);
create table bool_lp_true partition of bool_lp for values in(true);
--
2.34.1
