From 60c69a72ec421ac00deadf1f9c70f7acee689b67 Mon Sep 17 00:00:00 2001 From: Tomas Vondra 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