Pushed, after clarifying the comments a bit.
I also looked into what would it take to consider incremental paths, and
in principle it doesn't seem all that complicated. The attached PoC
patch extends get_cheapest_fractional_path_for_pathkeys() to optionally
build incremental sort on paths if needed. There are two GUCs that make
experimenting simpler:
* enable_fractional_paths - disables fractional paths entirely, i.e. we
get behavior without the part I already pushed
* enable_fractional_incremental_paths - disables the incremental sort
part added by the attached patch
With this, I get this plan (see the test in partitionwise_join.sql)
test=# EXPLAIN (COSTS OFF)
test-# SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2)
ORDER BY id1 ASC, id2 ASC LIMIT 10;
QUERY PLAN
------------------------------------------------------------------------------
Limit
-> Merge Left Join
Merge Cond: ((x.id1 = y.id1) AND (x.id2 = y.id2))
-> Append
-> Index Only Scan using fract_t0_id1_id2_idx on
fract_t0 x_1
-> Incremental Sort
Sort Key: x_2.id1, x_2.id2
Presorted Key: x_2.id1
-> Index Scan using fract_t1_pkey on fract_t1 x_2
-> Materialize
-> Append
-> Incremental Sort
Sort Key: y_1.id1, y_1.id2
Presorted Key: y_1.id1
-> Index Scan using fract_t0_pkey on
fract_t0 y_1
Index Cond: (id1 = id1)
Filter: (id2 = id2)
-> Incremental Sort
Sort Key: y_2.id1, y_2.id2
Presorted Key: y_2.id1
-> Index Scan using fract_t1_pkey on
fract_t1 y_2
Index Cond: (id1 = id1)
Filter: (id2 = id2)
(23 rows)
instead of
QUERY PLAN
------------------------------------------------------------------------------
Limit
-> Incremental Sort
Sort Key: x.id1, x.id2
Presorted Key: x.id1
-> Merge Left Join
Merge Cond: (x.id1 = y.id1)
Join Filter: (x.id2 = y.id2)
-> Append
-> Index Scan using fract_t0_pkey on fract_t0 x_1
-> Index Scan using fract_t1_pkey on fract_t1 x_2
-> Materialize
-> Append
-> Index Scan using fract_t0_pkey on
fract_t0 y_1
-> Index Scan using fract_t1_pkey on
fract_t1 y_2
(14 rows)
i.e. the incremental sorts moved below the merge join (and the cost is
lower, but that's not shown here).
So that seems reasonable, but there's a couple issues too:
1) Planning works (hence we can run explain), but execution fails
because of segfault in CheckVarSlotCompatibility - it gets NULL slot for
some reason. I haven't looked into the details, but I'd guess we need to
pass a different rel to create_incrementalsort_path, not childrel.
2) enable_partitionwisejoin=on seems to cause some confusion, because it
results in picking a different plan with higher cost. But that's clearly
not because of this patch.
3) I'm still a bit skeptical about the cost of this implementation - it
builds the incrementalsort path, just to throw most of the paths away.
It'd be much better to just calculate the cost, which should be much
cheaper, and only do the heavy work for the one "best" path.
4) One thing I did not realize before is what pathkeys we even consider
here. Imagine you have two tables:
CREATE TABLE t1 (a int, b int, primary key (a));
CREATE TABLE t2 (a int, b int, primary key (a));
and query
SELECT * FROM t1 JOIN t2 USING (a,b);
It seems reasonable to also consider pathkeys (a,b) because that's make
e.g. mergejoin much cheaper, right? But no, we'll not do that - we only
consider pathkeys that at least one child relation has, so in this case
it's just (a). Which means we'll never consider incremental sort for
this particular example.
It's a bit strange, because it's enough to create index on (a,b) for
just one of the relations, and it'll suddenly consider building
incremental sort on both sides.
I don't plan to pursue this further at this point, so I pushed the first
part because that's a fairly simple improvement over what we have now.
But it seems like a fairly promising area for improvements.
Also, the non-intuitive effects of enabling partition-wise joins (i.e.
picking plans with higher estimated costs) is something worth exploring,
I guess. But that's a separate issue.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
From 60c69a72ec421ac00deadf1f9c70f7acee689b67 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas.von...@postgresql.org>
Date: Wed, 12 Jan 2022 22:22:31 +0100
Subject: [PATCH] Consider incremental sort in generate_orderedappend_paths
---
src/backend/optimizer/path/allpaths.c | 11 ++++--
src/backend/optimizer/path/pathkeys.c | 47 ++++++++++++++++++++++--
src/backend/optimizer/plan/planagg.c | 6 ++--
src/backend/utils/misc/guc.c | 20 +++++++++++
src/include/optimizer/paths.h | 9 +++--
src/test/regress/sql/partition_join.sql | 48 +++++++++++++++++++++++++
6 files changed, 132 insertions(+), 9 deletions(-)
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 169b1d53fc8..1cd3fc6f585 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -60,6 +60,8 @@ typedef struct pushdown_safety_info
/* These parameters are set by GUC */
bool enable_geqo = false; /* just in case GUC doesn't set it */
+bool enable_fractional_paths = true; /* just in case GUC doesn't set it */
+bool enable_fractional_incremental_paths = true; /* just in case GUC doesn't set it */
int geqo_threshold;
int min_parallel_table_scan_size;
int min_parallel_index_scan_size;
@@ -1784,15 +1786,18 @@ generate_orderedappend_paths(PlannerInfo *root, RelOptInfo *rel,
* When needed (building fractional path), determine the cheapest
* fractional path too.
*/
- if (root->tuple_fraction > 0)
+ if (enable_fractional_paths && (root->tuple_fraction > 0))
{
double path_fraction = (1.0 / root->tuple_fraction);
cheapest_fractional =
- get_cheapest_fractional_path_for_pathkeys(childrel->pathlist,
+ get_cheapest_fractional_path_for_pathkeys(root,
+ childrel,
+ childrel->pathlist,
pathkeys,
NULL,
- path_fraction);
+ path_fraction,
+ enable_fractional_incremental_paths);
/*
* If we found no path with matching pathkeys, use the cheapest
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 86a35cdef17..0c935199fff 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -22,6 +22,7 @@
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
+#include "optimizer/cost.h"
#include "optimizer/optimizer.h"
#include "optimizer/pathnode.h"
#include "optimizer/paths.h"
@@ -446,17 +447,24 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
* 'fraction' is the fraction of the total tuples expected to be retrieved
*/
Path *
-get_cheapest_fractional_path_for_pathkeys(List *paths,
+get_cheapest_fractional_path_for_pathkeys(PlannerInfo *root, RelOptInfo *rel,
+ List *paths,
List *pathkeys,
Relids required_outer,
- double fraction)
+ double fraction,
+ bool incremental_sort)
{
Path *matched_path = NULL;
ListCell *l;
+ bool try_incremental_sort;
+
+ try_incremental_sort = (enable_incremental_sort && incremental_sort);
foreach(l, paths)
{
Path *path = (Path *) lfirst(l);
+ bool is_sorted;
+ int presorted_keys;
/*
* Since cost comparison is a lot cheaper than pathkey comparison, do
@@ -468,7 +476,42 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
bms_is_subset(PATH_REQ_OUTER(path), required_outer))
+ {
matched_path = path;
+ continue;
+ }
+
+ /* Incremental sort disabled or not requested. */
+ if (!try_incremental_sort)
+ continue;
+
+ is_sorted = pathkeys_count_contained_in(pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+
+ /*
+ * If fully sorted, it should have been handled before. If there
+ * are no presorted keys, no point in trying incremental sort.
+ */
+ if (is_sorted || (presorted_keys == 0))
+ continue;
+
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ presorted_keys,
+ -1); /* FIXME can we get something better? */
+
+ /*
+ * Since cost comparison is a lot cheaper than pathkey comparison, do
+ * that first. (XXX is that still true?)
+ */
+ if (matched_path != NULL &&
+ compare_fractional_path_costs(matched_path, path, fraction) <= 0)
+ continue;
+
+ matched_path = path;
}
return matched_path;
}
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
index 9330908cbf1..fc68305b8e4 100644
--- a/src/backend/optimizer/plan/planagg.c
+++ b/src/backend/optimizer/plan/planagg.c
@@ -439,10 +439,12 @@ build_minmax_path(PlannerInfo *root, MinMaxAggInfo *mminfo,
path_fraction = 1.0;
sorted_path =
- get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
+ get_cheapest_fractional_path_for_pathkeys(root, final_rel,
+ final_rel->pathlist,
subroot->query_pathkeys,
NULL,
- path_fraction);
+ path_fraction,
+ false);
if (!sorted_path)
return false;
diff --git a/src/backend/utils/misc/guc.c b/src/backend/utils/misc/guc.c
index 6fc5cbc09a5..bb8a9e3242a 100644
--- a/src/backend/utils/misc/guc.c
+++ b/src/backend/utils/misc/guc.c
@@ -1173,6 +1173,26 @@ static struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_fractional_paths", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables fractional paths in generate_orderappend_paths."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_fractional_paths,
+ true,
+ NULL, NULL, NULL
+ },
+ {
+ {"enable_fractional_incremental_paths", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables fractional paths with incremental sort in generate_orderappend_paths."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_fractional_incremental_paths,
+ true,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 0c3a0b90c85..1ad62dd9794 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -21,6 +21,8 @@
* allpaths.c
*/
extern PGDLLIMPORT bool enable_geqo;
+extern PGDLLIMPORT bool enable_fractional_paths;
+extern PGDLLIMPORT bool enable_fractional_incremental_paths;
extern PGDLLIMPORT int geqo_threshold;
extern PGDLLIMPORT int min_parallel_table_scan_size;
extern PGDLLIMPORT int min_parallel_index_scan_size;
@@ -207,10 +209,13 @@ extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
CostSelector cost_criterion,
bool require_parallel_safe);
-extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
+extern Path *get_cheapest_fractional_path_for_pathkeys(PlannerInfo *root,
+ RelOptInfo *rel,
+ List *paths,
List *pathkeys,
Relids required_outer,
- double fraction);
+ double fraction,
+ bool incremental_sort);
extern Path *get_cheapest_parallel_safe_total_inner(List *paths);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
ScanDirection scandir);
diff --git a/src/test/regress/sql/partition_join.sql b/src/test/regress/sql/partition_join.sql
index 67f506361f8..9263e2464db 100644
--- a/src/test/regress/sql/partition_join.sql
+++ b/src/test/regress/sql/partition_join.sql
@@ -1165,5 +1165,53 @@ SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id) ORDER BY id DESC LIMIT 10
-- cleanup
DROP TABLE fract_t;
+-- partitionwise join with fractional paths and incremental sort
+CREATE TABLE fract_t (id1 BIGINT, id2 BIGINT, PRIMARY KEY (id1)) PARTITION BY RANGE (id1);
+CREATE TABLE fract_t0 PARTITION OF fract_t FOR VALUES FROM ('0') TO ('1000');
+CREATE TABLE fract_t1 PARTITION OF fract_t FOR VALUES FROM ('1000') TO ('2000');
+
+
+CREATE INDEX ON fract_t0 (id1, id2);
+
+-- insert data
+INSERT INTO fract_t (id1, id2) (SELECT i, i FROM generate_series(0, 1999) s(i));
+ANALYZE fract_t;
+
+-- verify plan; nested index only scans
+SET max_parallel_workers_per_gather = 0;
+
+-- important, otherwise a plan with higher cost wins
+SET enable_partitionwise_join = off;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 ASC, id2 ASC LIMIT 10;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 DESC, id2 DESC LIMIT 10;
+
+-- no incremental sorts below append
+SET enable_fractional_incremental_paths = off;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 ASC, id2 ASC LIMIT 10;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 DESC, id2 DESC LIMIT 10;
+
+-- no fractional paths
+SET enable_fractional_paths = off;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 ASC, id2 ASC LIMIT 10;
+
+EXPLAIN (COSTS OFF)
+SELECT * FROM fract_t x LEFT JOIN fract_t y USING (id1, id2) ORDER BY id1 DESC, id2 DESC LIMIT 10;
+
+
+-- cleanup
+DROP TABLE fract_t;
+
+
+
RESET max_parallel_workers_per_gather;
RESET enable_partitionwise_join;
--
2.31.1
