pg.ddx.io pgsql-hackers@postgresql.org mailing list archive
help / color / mirror / Atom feedReordering DISTINCT keys to match input path's pathkeys
17+ messages / 5 participants
[nested] [flat]
Commits from this thread:
2024-11-26 e15e567137 Fix test case from a8ccf4e93
2024-11-26 a8ccf4e93a Reordering DISTINCT keys to match input path's pathkeys
* Reordering DISTINCT keys to match input path's pathkeys
@ 2024-01-23 05:55 Richard Guo <guofenglinux@gmail.com>
2024-01-23 08:04 ` Re: Reordering DISTINCT keys to match input path's pathkeys Laurenz Albe <laurenz.albe@cybertec.at>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
0 siblings, 2 replies; 17+ messages in thread
From: Richard Guo @ 2024-01-23 05:55 UTC (permalink / raw)
To: pgsql-hackers
Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
path's pathkeys, which can help reduce cost by avoiding unnecessary
re-sort, or allowing us to use incremental-sort to save efforts. For
instance,
create table t (a int, b int);
create index on t (a, b);
explain (costs off) select distinct b, a from t limit 10;
QUERY PLAN
--------------------------------------------------
Limit
-> Unique
-> Index Only Scan using t_a_b_idx on t
(3 rows)
Please note that the parser has ensured that the DISTINCT pathkeys
matches the order of ORDER BY clauses. So there is no need to do this
part again.
In principle, we can perform such reordering for DISTINCT ON too, but we
need to make sure that the resulting pathkeys matches initial ORDER BY
keys, which seems not trivial. So it doesn't seem worth the effort.
Attached is a patch for this optimization. Any thoughts?
Thanks
Richard
Attachments:
v1-0001-Reordering-DISTINCT-keys-to-match-input-path-s-pathkeys.patch (application/octet-stream, 27.2K) download
From 53f6a945a21ce31a32871da373777f0618524600 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Fri, 19 Jan 2024 19:24:54 +0800
Subject: [PATCH v1] Reordering DISTINCT keys to match input path's pathkeys
Similar to what we did to GROUP BY keys in 0452b461bc, we can do the
same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
path's pathkeys, which can help reduce cost by avoiding unnecessary
re-sort, or allowing us to use incremental-sort to save efforts.
Please note that the parser has ensured that the DISTINCT pathkeys
matches the order of ORDER BY clauses. So there is no need to do this
part in this commit.
In principle, we can perform such reordering for DISTINCT ON too, but we
need to make sure that the resulting pathkeys matches initial ORDER BY
keys, which seems not trivial. So don't bother with that.
This introduces a new GUC enable_distinct_reordering so that the
optimization may be disabled if needed.
---
src/backend/optimizer/path/pathkeys.c | 39 ++
src/backend/optimizer/plan/planner.c | 397 ++++++++++--------
src/backend/utils/misc/guc_tables.c | 10 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/optimizer.h | 1 +
src/test/regress/expected/select_distinct.out | 108 +++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/sql/select_distinct.sql | 63 +++
8 files changed, 453 insertions(+), 169 deletions(-)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 82ff31273b..45bbb53083 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2186,6 +2186,42 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
return n;
}
+/*
+ * pathkeys_useful_for_distinct
+ * Count the number of pathkeys that are useful for DISTINCT clause.
+ *
+ * DISTINCT keys could also be reordered to benefit from the ordering. As with
+ * pathkeys_useful_for_grouping, we return the number of leading keys in the
+ * list that are shared by the distinctClause pathkeys.
+ */
+static int
+pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
+{
+ int n_common_pathkeys;
+ ListCell *lc;
+
+ if (root->distinct_pathkeys == NIL)
+ return 0; /* no special ordering requested for DISTINCT */
+
+ if (pathkeys == NIL)
+ return 0; /* unordered path */
+
+ /* walk the pathkeys and search for matching DISTINCT key */
+ n_common_pathkeys = 0;
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /* no matching group key, we're done */
+ if (!list_member_ptr(root->distinct_pathkeys, pathkey))
+ break;
+
+ n_common_pathkeys++;
+ }
+
+ return n_common_pathkeys;
+}
+
/*
* truncate_useless_pathkeys
* Shorten the given pathkey list to just the useful pathkeys.
@@ -2203,6 +2239,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 2e2458b128..1b9d1458e9 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -72,6 +72,7 @@
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
int debug_parallel_query = DEBUG_PARALLEL_OFF;
bool parallel_leader_participation = true;
+bool enable_distinct_reordering = true;
/* Hook for plugins to get control in planner() */
planner_hook_type planner_hook = NULL;
@@ -197,6 +198,9 @@ static void create_partial_distinct_paths(PlannerInfo *root,
static RelOptInfo *create_final_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel,
RelOptInfo *distinct_rel);
+static List *get_useful_pathkeys_for_distinct(PlannerInfo *root,
+ List *distinct_pathkeys,
+ List *path_pathkeys);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
PathTarget *target,
@@ -234,6 +238,12 @@ static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,
grouping_sets_data *gd,
GroupPathExtraData *extra,
bool force_rel_creation);
+static Path *make_ordered_path(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *path,
+ Path *cheapest_path,
+ List *pathkeys,
+ double limit_tuples);
static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);
static bool can_partial_agg(PlannerInfo *root);
static void apply_scanjoin_target_to_paths(PlannerInfo *root,
@@ -4695,53 +4705,35 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(root->distinct_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ root->distinct_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * Try at least sorting the cheapest path and also try
- * incrementally sorting any path which is partially sorted
- * already (no need to deal with paths which have presorted
- * keys when incremental sort is disabled unless it's the
- * cheapest partial path).
- */
- if (input_path != cheapest_partial_path &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ partial_distinct_rel,
+ input_path,
+ cheapest_partial_path,
+ useful_pathkeys,
+ -1.0);
+
+ if (sorted_path == NULL)
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,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- -1.0);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- presorted_keys,
- -1.0);
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_upper_unique_path(root, partial_distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
}
-
- add_partial_path(partial_distinct_rel, (Path *)
- create_upper_unique_path(root, partial_distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
}
}
@@ -4873,86 +4865,69 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(needed_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ needed_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * 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 &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ distinct_rel,
+ input_path,
+ cheapest_input_path,
+ useful_pathkeys,
+ limittuples);
+
+ if (sorted_path == NULL)
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.
+ * distinct_pathkeys may have become empty if all of the
+ * pathkeys were determined to be redundant. If all of the
+ * pathkeys are redundant then each DISTINCT target must only
+ * allow a single value, therefore all resulting tuples must be
+ * identical (or at least indistinguishable by an equality
+ * check). We can uniquify these tuples simply by just taking
+ * the first tuple. All we do here is add a path to do "LIMIT
+ * 1" atop of 'sorted_path'. When doing a DISTINCT ON we may
+ * still have a non-NIL sort_pathkeys list, so we must still
+ * only do this with paths which are correctly sorted by
+ * sort_pathkeys.
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- limittuples);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- presorted_keys,
- limittuples);
- }
-
- /*
- * distinct_pathkeys may have become empty if all of the pathkeys
- * were determined to be redundant. If all of the pathkeys are
- * redundant then each DISTINCT target must only allow a single
- * value, therefore all resulting tuples must be identical (or at
- * least indistinguishable by an equality check). We can uniquify
- * these tuples simply by just taking the first tuple. All we do
- * here is add a path to do "LIMIT 1" atop of 'sorted_path'. When
- * doing a DISTINCT ON we may still have a non-NIL sort_pathkeys
- * list, so we must still only do this with paths which are
- * correctly sorted by sort_pathkeys.
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * If the query already has a LIMIT clause, then we could end
- * up with a duplicate LimitPath in the final plan. That does
- * not seem worth troubling over too much.
- */
- add_path(distinct_rel, (Path *)
- create_limit_path(root, distinct_rel, sorted_path,
- NULL, limitCount,
- LIMIT_OPTION_COUNT, 0, 1));
- }
- else
- {
- add_path(distinct_rel, (Path *)
- create_upper_unique_path(root, distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * If the query already has a LIMIT clause, then we could
+ * end up with a duplicate LimitPath in the final plan.
+ * That does not seem worth troubling over too much.
+ */
+ add_path(distinct_rel, (Path *)
+ create_limit_path(root, distinct_rel, sorted_path,
+ NULL, limitCount,
+ LIMIT_OPTION_COUNT, 0, 1));
+ }
+ else
+ {
+ add_path(distinct_rel, (Path *)
+ create_upper_unique_path(root, distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -4995,6 +4970,88 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
return distinct_rel;
}
+/*
+ * get_useful_pathkeys_for_distinct
+ * Get useful orderings of distinctClause by reordering 'distinct_pathkeys'
+ * to match the given 'path_pathkeys' as much as possible.
+ *
+ * This returns a list of pathkeys that can be useful for DISTINCT clause,
+ * which, for convenience, always includes the given 'distinct_pathkeys'.
+ */
+static List *
+get_useful_pathkeys_for_distinct(PlannerInfo *root, List *distinct_pathkeys,
+ List *path_pathkeys)
+{
+ List *useful_pathkeys_list = NIL;
+ List *useful_pathkeys = NIL;
+ ListCell *lc;
+
+ /* always including the given 'distinct_pathkeys' */
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ distinct_pathkeys);
+
+ if (!enable_distinct_reordering)
+ return useful_pathkeys_list;
+
+ /*
+ * Do not try to reorder pathkeys for DISTINCT ON
+ *
+ * XXX It might be possible to perform reordering for DISTINCT ON too, but
+ * we need to make sure that the resulting pathkeys matches initial ORDER
+ * BY keys, which seems not trivial. So don't bother with that.
+ */
+ if (root->parse->hasDistinctOn)
+ return useful_pathkeys_list;
+
+ /*
+ * Scan the given 'path_pathkeys' and construct a list of PathKey nodes
+ * that match 'distinct_pathkeys', but only as far as we can make a
+ * matching prefix.
+ */
+ foreach(lc, path_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /*
+ * The PathKey nodes are canonical, so they can be checked for equality
+ * by simple pointer comparison.
+ */
+ if (!list_member_ptr(distinct_pathkeys, pathkey))
+ break;
+
+ useful_pathkeys = lappend(useful_pathkeys, pathkey);
+ }
+
+ /* If no match at all, no point in reordering distinct_pathkeys */
+ if (useful_pathkeys == NIL)
+ return useful_pathkeys_list;
+
+ /*
+ * If not full match, the resulting pathkeys is not useful without
+ * incremental sort.
+ */
+ if (list_length(useful_pathkeys) < list_length(distinct_pathkeys) &&
+ !enable_incremental_sort)
+ return useful_pathkeys_list;
+
+ /* Append the remaining distinct PathKey nodes */
+ useful_pathkeys = list_concat_unique_ptr(useful_pathkeys,
+ distinct_pathkeys);
+
+ /*
+ * If the resulting pathkeys is the same as the 'distinct_pathkeys', just
+ * drop it.
+ */
+ if (compare_pathkeys(distinct_pathkeys,
+ useful_pathkeys) == PATHKEYS_EQUAL)
+ return useful_pathkeys_list;
+
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ useful_pathkeys);
+
+ return useful_pathkeys_list;
+}
+
/*
* create_ordered_paths
*
@@ -6722,58 +6779,6 @@ done:
return parallel_workers;
}
-/*
- * make_ordered_path
- * Return a path ordered by 'pathkeys' based on the given 'path'. May
- * return NULL if it doesn't make sense to generate an ordered path in
- * this case.
- */
-static Path *
-make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
- Path *cheapest_path, List *pathkeys)
-{
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- 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))
- return NULL;
-
- /*
- * We've no need to consider both a sort and incremental sort. We'll
- * just do a sort if there are no presorted keys and an incremental
- * sort when there are presorted keys.
- */
- if (presorted_keys == 0 || !enable_incremental_sort)
- path = (Path *) create_sort_path(root,
- rel,
- path,
- pathkeys,
- -1.0);
- else
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- pathkeys,
- presorted_keys,
- -1.0);
- }
-
- return path;
-}
-
/*
* add_paths_to_grouping_rel
*
@@ -6825,7 +6830,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
cheapest_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -6906,7 +6912,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
partially_grouped_rel->cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7157,7 +7164,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7214,7 +7222,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_partial_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7300,6 +7309,58 @@ create_partial_grouping_paths(PlannerInfo *root,
return partially_grouped_rel;
}
+/*
+ * make_ordered_path
+ * Return a path ordered by 'pathkeys' based on the given 'path'. May
+ * return NULL if it doesn't make sense to generate an ordered path in
+ * this case.
+ */
+static Path *
+make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
+ Path *cheapest_path, List *pathkeys, double limit_tuples)
+{
+ bool is_sorted;
+ int presorted_keys;
+
+ is_sorted = pathkeys_count_contained_in(pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+
+ 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))
+ return NULL;
+
+ /*
+ * We've no need to consider both a sort and incremental sort. We'll
+ * just do a sort if there are no presorted keys and an incremental
+ * sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ limit_tuples);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
+
+ return path;
+}
+
/*
* Generate Gather and Gather Merge paths for a grouping relation or partial
* grouping relation.
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 7fe58518d7..7384e4ad17 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1060,6 +1060,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_distinct_reordering", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables reordering of DISTINCT pathkeys."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_distinct_reordering,
+ true,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index da10b43dac..0c2c21cacf 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -400,6 +400,7 @@
#enable_sort = on
#enable_tidscan = on
#enable_group_by_reordering = on
+#enable_distinct_reordering = on
# - Planner Cost Constants -
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 7b63c5cf71..798b9732b8 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -111,6 +111,7 @@ typedef enum
/* GUC parameters */
extern PGDLLIMPORT int debug_parallel_query;
extern PGDLLIMPORT bool parallel_leader_participation;
+extern PGDLLIMPORT bool enable_distinct_reordering;
extern struct PlannedStmt *planner(Query *parse, const char *query_string,
int cursorOptions,
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index 9d44ea8056..71249564f9 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -444,3 +444,111 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
t
(1 row)
+--
+-- DISTINCT optimization by reordering the distinctClause Pathkey nodes to
+-- match the input path's ordering
+--
+CREATE TABLE btg AS SELECT
+ i % 100 AS x,
+ i % 100 AS y,
+ 'abc' || i % 10 AS z,
+ i AS w
+FROM generate_series(1,10000) AS i;
+CREATE INDEX abc ON btg(x,y);
+ANALYZE btg;
+SET enable_hashagg TO OFF;
+-- Utilize index scan ordering to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM btg;
+ QUERY PLAN
+----------------------------------------
+ Unique
+ -> Index Only Scan using abc on btg
+(2 rows)
+
+-- Engage incremental sort
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, w, x FROM btg;
+ QUERY PLAN
+-----------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: x, y, z, w
+ Presorted Key: x, y
+ -> Index Scan using abc on btg
+(5 rows)
+
+-- Utilize subquery scan ordering to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT w, x, z, y
+ FROM (SELECT * FROM btg ORDER BY x, y, w, z) AS q1;
+ QUERY PLAN
+----------------------------------------------------
+ Unique
+ -> Subquery Scan on q1
+ -> Incremental Sort
+ Sort Key: btg.x, btg.y, btg.w, btg.z
+ Presorted Key: btg.x, btg.y
+ -> Index Scan using abc on btg
+(6 rows)
+
+-- Utilize merge join ordering to avoid a Sort operation
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.w, t1.x, t1.z, t1.y
+ FROM btg t1 JOIN btg t2 ON t1.x = t2.x AND t1.y = t2.y;
+ QUERY PLAN
+-------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: t1.x, t1.y, t1.w, t1.z
+ Presorted Key: t1.x, t1.y
+ -> Merge Join
+ Merge Cond: ((t1.x = t2.x) AND (t1.y = t2.y))
+ -> Index Scan using abc on btg t1
+ -> Index Only Scan using abc on btg t2
+(8 rows)
+
+RESET enable_nestloop;
+RESET enable_hashjoin;
+-- Engage ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM btg ORDER BY x, z;
+ QUERY PLAN
+-----------------------------------------------
+ Incremental Sort
+ Sort Key: x, z
+ Presorted Key: x
+ -> Unique
+ -> Incremental Sort
+ Sort Key: x, y, z
+ Presorted Key: x, y
+ -> Index Scan using abc on btg
+(8 rows)
+
+-- Engage parallel DISTINCT
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM btg limit 10;
+ QUERY PLAN
+-------------------------------------------------------------------
+ Limit
+ -> Unique
+ -> Gather Merge
+ Workers Planned: 2
+ -> Unique
+ -> Parallel Index Only Scan using abc on btg
+(6 rows)
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+RESET enable_hashagg;
+DROP TABLE btg;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 9be7aca2b8..564c007ddd 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -113,6 +113,7 @@ select name, setting from pg_settings where name like 'enable%';
--------------------------------+---------
enable_async_append | on
enable_bitmapscan | on
+ enable_distinct_reordering | on
enable_gathermerge | on
enable_group_by_reordering | on
enable_hashagg | on
@@ -134,7 +135,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(23 rows)
+(24 rows)
-- There are always wait event descriptions for various types.
select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index 1643526d99..8f8fea0851 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -208,3 +208,66 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
SELECT 2 IS NOT DISTINCT FROM null as "no";
SELECT null IS NOT DISTINCT FROM null as "yes";
+
+--
+-- DISTINCT optimization by reordering the distinctClause Pathkey nodes to
+-- match the input path's ordering
+--
+
+CREATE TABLE btg AS SELECT
+ i % 100 AS x,
+ i % 100 AS y,
+ 'abc' || i % 10 AS z,
+ i AS w
+FROM generate_series(1,10000) AS i;
+CREATE INDEX abc ON btg(x,y);
+ANALYZE btg;
+
+SET enable_hashagg TO OFF;
+
+-- Utilize index scan ordering to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM btg;
+
+-- Engage incremental sort
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, w, x FROM btg;
+
+-- Utilize subquery scan ordering to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT w, x, z, y
+ FROM (SELECT * FROM btg ORDER BY x, y, w, z) AS q1;
+
+-- Utilize merge join ordering to avoid a Sort operation
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.w, t1.x, t1.z, t1.y
+ FROM btg t1 JOIN btg t2 ON t1.x = t2.x AND t1.y = t2.y;
+
+RESET enable_nestloop;
+RESET enable_hashjoin;
+
+-- Engage ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM btg ORDER BY x, z;
+
+-- Engage parallel DISTINCT
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM btg limit 10;
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+
+RESET enable_hashagg;
+
+DROP TABLE btg;
--
2.31.0
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-01-23 08:04 ` Laurenz Albe <laurenz.albe@cybertec.at>
1 sibling, 0 replies; 17+ messages in thread
From: Laurenz Albe @ 2024-01-23 08:04 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; pgsql-hackers
On Tue, 2024-01-23 at 13:55 +0800, Richard Guo wrote:
> Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
> the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
> path's pathkeys, which can help reduce cost by avoiding unnecessary
> re-sort, or allowing us to use incremental-sort to save efforts.
>
> Attached is a patch for this optimization. Any thoughts?
I didn't scrutinize the code, but that sounds like a fine optimization.
Yours,
Laurenz Albe
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-01-23 09:03 ` David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: David Rowley @ 2024-01-23 09:03 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-hackers
On Tue, 23 Jan 2024 at 18:56, Richard Guo <guofenglinux@gmail.com> wrote:
>
> Similar to what we did to GROUP BY keys in 0452b461bc, I think we can do
> the same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
> path's pathkeys, which can help reduce cost by avoiding unnecessary
> re-sort, or allowing us to use incremental-sort to save efforts. For
> instance,
I've not caught up on the specifics of 0452b461b, but I just wanted to
highlight that there was some work done in [1] in this area. It seems
Ankit didn't ever add that to a CF, so that might explain why it's
been lost.
Anyway, just pointing it out as there may be useful code or discussion
in the corresponding threads.
David
[1] https://postgr.es/m/da9425ae-8ff7-33d9-23b3-2a3eb605e106%40gmail.com
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
@ 2024-01-26 10:48 ` Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Richard Guo @ 2024-01-26 10:48 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: pgsql-hackers
On Tue, Jan 23, 2024 at 5:03 PM David Rowley <dgrowleyml@gmail.com> wrote:
> I've not caught up on the specifics of 0452b461b, but I just wanted to
> highlight that there was some work done in [1] in this area. It seems
> Ankit didn't ever add that to a CF, so that might explain why it's
> been lost.
>
> Anyway, just pointing it out as there may be useful code or discussion
> in the corresponding threads.
Thanks for pointing it out. I looked at the patch there and noticed
several problems with it.
* That patch is incomplete and does not work as expected. It at least
needs to modify truncate_useless_pathkeys() to account for DISTINCT
clause (I think this has been mentioned in that thread).
* That patch would not consider the origin DISTINCT pathkeys if it could
do some reordering, which is not great and can generate inefficient
plans. For instance (after fixing the first problem)
create table t (a int, b int);
create index on t(a);
set enable_hashagg to off;
set enable_incremental_sort to off;
set enable_seqscan to off;
explain (costs off) select distinct b, a from t order by b, a;
QUERY PLAN
-------------------------------------------------
Sort
Sort Key: b, a
-> Unique
-> Sort
Sort Key: a, b
-> Index Scan using t_a_idx on t
(6 rows)
Using DISTINCT pathkeys {b, a} is more efficient for this plan, because
only one Sort would be required. But that patch is not able to do that,
because it does not consider the origin DISTINCT pathkeys after
reordering.
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-02-05 03:18 ` Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Richard Guo @ 2024-02-05 03:18 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: pgsql-hackers
cfbot reminds that this patch does not apply any more. So I've rebased
it on master, and also adjusted the test cases a bit.
Thanks
Richard
Attachments:
v2-0001-Reordering-DISTINCT-keys-to-match-input-path-s-pathkeys.patch (application/octet-stream, 30.4K) download
From 1c6e61ebdbc5a70fb75a0018eca113c501572a40 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Mon, 5 Feb 2024 10:02:13 +0800
Subject: [PATCH v2] Reordering DISTINCT keys to match input path's pathkeys
Similar to what we did to GROUP BY keys in 0452b461bc, we can do the
same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
path's pathkeys, which can help reduce cost by avoiding unnecessary
re-sort, or allowing us to use incremental-sort to save efforts.
Please note that the parser has ensured that the DISTINCT pathkeys
matches the order of ORDER BY clauses. So there is no need to do this
part in this commit.
In principle, we can perform such reordering for DISTINCT ON too, but we
need to make sure that the resulting pathkeys matches initial ORDER BY
keys, which seems not trivial. So don't bother with that.
This introduces a new GUC enable_distinct_reordering so that the
optimization may be disabled if needed.
---
src/backend/optimizer/path/pathkeys.c | 39 ++
src/backend/optimizer/plan/planner.c | 457 ++++++++++--------
src/backend/utils/misc/guc_tables.c | 10 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/optimizer.h | 1 +
src/test/regress/expected/select_distinct.out | 111 +++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/sql/select_distinct.sql | 65 +++
8 files changed, 488 insertions(+), 199 deletions(-)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 82ff31273b..45bbb53083 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2186,6 +2186,42 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
return n;
}
+/*
+ * pathkeys_useful_for_distinct
+ * Count the number of pathkeys that are useful for DISTINCT clause.
+ *
+ * DISTINCT keys could also be reordered to benefit from the ordering. As with
+ * pathkeys_useful_for_grouping, we return the number of leading keys in the
+ * list that are shared by the distinctClause pathkeys.
+ */
+static int
+pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
+{
+ int n_common_pathkeys;
+ ListCell *lc;
+
+ if (root->distinct_pathkeys == NIL)
+ return 0; /* no special ordering requested for DISTINCT */
+
+ if (pathkeys == NIL)
+ return 0; /* unordered path */
+
+ /* walk the pathkeys and search for matching DISTINCT key */
+ n_common_pathkeys = 0;
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /* no matching group key, we're done */
+ if (!list_member_ptr(root->distinct_pathkeys, pathkey))
+ break;
+
+ n_common_pathkeys++;
+ }
+
+ return n_common_pathkeys;
+}
+
/*
* truncate_useless_pathkeys
* Shorten the given pathkey list to just the useful pathkeys.
@@ -2203,6 +2239,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index acc324122f..ba1a49d6c0 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -72,6 +72,7 @@
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
int debug_parallel_query = DEBUG_PARALLEL_OFF;
bool parallel_leader_participation = true;
+bool enable_distinct_reordering = true;
/* Hook for plugins to get control in planner() */
planner_hook_type planner_hook = NULL;
@@ -197,6 +198,9 @@ static void create_partial_distinct_paths(PlannerInfo *root,
static RelOptInfo *create_final_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel,
RelOptInfo *distinct_rel);
+static List *get_useful_pathkeys_for_distinct(PlannerInfo *root,
+ List *distinct_pathkeys,
+ List *path_pathkeys);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
PathTarget *target,
@@ -234,6 +238,12 @@ static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,
grouping_sets_data *gd,
GroupPathExtraData *extra,
bool force_rel_creation);
+static Path *make_ordered_path(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *path,
+ Path *cheapest_path,
+ List *pathkeys,
+ double limit_tuples);
static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);
static bool can_partial_agg(PlannerInfo *root);
static void apply_scanjoin_target_to_paths(PlannerInfo *root,
@@ -4695,86 +4705,68 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(root->distinct_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ root->distinct_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * Try at least sorting the cheapest path and also try
- * incrementally sorting any path which is partially sorted
- * already (no need to deal with paths which have presorted
- * keys when incremental sort is disabled unless it's the
- * cheapest partial path).
- */
- if (input_path != cheapest_partial_path &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ partial_distinct_rel,
+ input_path,
+ cheapest_partial_path,
+ useful_pathkeys,
+ -1.0);
+
+ if (sorted_path == NULL)
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.
+ * An empty distinct_pathkeys means all tuples have the same value
+ * for the DISTINCT clause. See create_final_distinct_paths()
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- -1.0);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- presorted_keys,
- -1.0);
- }
-
- /*
- * An empty distinct_pathkeys means all tuples have the same value
- * for the DISTINCT clause. See create_final_distinct_paths()
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * Apply a LimitPath onto the partial path to restrict the
- * tuples from each worker to 1. create_final_distinct_paths
- * will need to apply an additional LimitPath to restrict this
- * to a single row after the Gather node. If the query
- * already has a LIMIT clause, then we could end up with three
- * Limit nodes in the final plan. Consolidating the top two
- * of these could be done, but does not seem worth troubling
- * over.
- */
- add_partial_path(partial_distinct_rel, (Path *)
- create_limit_path(root, partial_distinct_rel,
- sorted_path,
- NULL,
- limitCount,
- LIMIT_OPTION_COUNT,
- 0, 1));
- }
- else
- {
- add_partial_path(partial_distinct_rel, (Path *)
- create_upper_unique_path(root, partial_distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * Apply a LimitPath onto the partial path to restrict the
+ * tuples from each worker to 1. create_final_distinct_paths
+ * will need to apply an additional LimitPath to restrict this
+ * to a single row after the Gather node. If the query
+ * already has a LIMIT clause, then we could end up with three
+ * Limit nodes in the final plan. Consolidating the top two
+ * of these could be done, but does not seem worth troubling
+ * over.
+ */
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_limit_path(root, partial_distinct_rel,
+ sorted_path,
+ NULL,
+ limitCount,
+ LIMIT_OPTION_COUNT,
+ 0, 1));
+ }
+ else
+ {
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_upper_unique_path(root, partial_distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -4907,86 +4899,69 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(needed_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ needed_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * 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 &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ distinct_rel,
+ input_path,
+ cheapest_input_path,
+ useful_pathkeys,
+ limittuples);
+
+ if (sorted_path == NULL)
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.
+ * distinct_pathkeys may have become empty if all of the
+ * pathkeys were determined to be redundant. If all of the
+ * pathkeys are redundant then each DISTINCT target must only
+ * allow a single value, therefore all resulting tuples must be
+ * identical (or at least indistinguishable by an equality
+ * check). We can uniquify these tuples simply by just taking
+ * the first tuple. All we do here is add a path to do "LIMIT
+ * 1" atop of 'sorted_path'. When doing a DISTINCT ON we may
+ * still have a non-NIL sort_pathkeys list, so we must still
+ * only do this with paths which are correctly sorted by
+ * sort_pathkeys.
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- limittuples);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- presorted_keys,
- limittuples);
- }
-
- /*
- * distinct_pathkeys may have become empty if all of the pathkeys
- * were determined to be redundant. If all of the pathkeys are
- * redundant then each DISTINCT target must only allow a single
- * value, therefore all resulting tuples must be identical (or at
- * least indistinguishable by an equality check). We can uniquify
- * these tuples simply by just taking the first tuple. All we do
- * here is add a path to do "LIMIT 1" atop of 'sorted_path'. When
- * doing a DISTINCT ON we may still have a non-NIL sort_pathkeys
- * list, so we must still only do this with paths which are
- * correctly sorted by sort_pathkeys.
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * If the query already has a LIMIT clause, then we could end
- * up with a duplicate LimitPath in the final plan. That does
- * not seem worth troubling over too much.
- */
- add_path(distinct_rel, (Path *)
- create_limit_path(root, distinct_rel, sorted_path,
- NULL, limitCount,
- LIMIT_OPTION_COUNT, 0, 1));
- }
- else
- {
- add_path(distinct_rel, (Path *)
- create_upper_unique_path(root, distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * If the query already has a LIMIT clause, then we could
+ * end up with a duplicate LimitPath in the final plan.
+ * That does not seem worth troubling over too much.
+ */
+ add_path(distinct_rel, (Path *)
+ create_limit_path(root, distinct_rel, sorted_path,
+ NULL, limitCount,
+ LIMIT_OPTION_COUNT, 0, 1));
+ }
+ else
+ {
+ add_path(distinct_rel, (Path *)
+ create_upper_unique_path(root, distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -5029,6 +5004,88 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
return distinct_rel;
}
+/*
+ * get_useful_pathkeys_for_distinct
+ * Get useful orderings of distinctClause by reordering 'distinct_pathkeys'
+ * to match the given 'path_pathkeys' as much as possible.
+ *
+ * This returns a list of pathkeys that can be useful for DISTINCT clause,
+ * which, for convenience, always includes the given 'distinct_pathkeys'.
+ */
+static List *
+get_useful_pathkeys_for_distinct(PlannerInfo *root, List *distinct_pathkeys,
+ List *path_pathkeys)
+{
+ List *useful_pathkeys_list = NIL;
+ List *useful_pathkeys = NIL;
+ ListCell *lc;
+
+ /* always including the given 'distinct_pathkeys' */
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ distinct_pathkeys);
+
+ if (!enable_distinct_reordering)
+ return useful_pathkeys_list;
+
+ /*
+ * Do not try to reorder pathkeys for DISTINCT ON
+ *
+ * XXX It might be possible to perform reordering for DISTINCT ON too, but
+ * we need to make sure that the resulting pathkeys matches initial ORDER
+ * BY keys, which seems not trivial. So don't bother with that.
+ */
+ if (root->parse->hasDistinctOn)
+ return useful_pathkeys_list;
+
+ /*
+ * Scan the given 'path_pathkeys' and construct a list of PathKey nodes
+ * that match 'distinct_pathkeys', but only as far as we can make a
+ * matching prefix.
+ */
+ foreach(lc, path_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /*
+ * The PathKey nodes are canonical, so they can be checked for equality
+ * by simple pointer comparison.
+ */
+ if (!list_member_ptr(distinct_pathkeys, pathkey))
+ break;
+
+ useful_pathkeys = lappend(useful_pathkeys, pathkey);
+ }
+
+ /* If no match at all, no point in reordering distinct_pathkeys */
+ if (useful_pathkeys == NIL)
+ return useful_pathkeys_list;
+
+ /*
+ * If not full match, the resulting pathkeys is not useful without
+ * incremental sort.
+ */
+ if (list_length(useful_pathkeys) < list_length(distinct_pathkeys) &&
+ !enable_incremental_sort)
+ return useful_pathkeys_list;
+
+ /* Append the remaining distinct PathKey nodes */
+ useful_pathkeys = list_concat_unique_ptr(useful_pathkeys,
+ distinct_pathkeys);
+
+ /*
+ * If the resulting pathkeys is the same as the 'distinct_pathkeys', just
+ * drop it.
+ */
+ if (compare_pathkeys(distinct_pathkeys,
+ useful_pathkeys) == PATHKEYS_EQUAL)
+ return useful_pathkeys_list;
+
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ useful_pathkeys);
+
+ return useful_pathkeys_list;
+}
+
/*
* create_ordered_paths
*
@@ -6725,58 +6782,6 @@ done:
return parallel_workers;
}
-/*
- * make_ordered_path
- * Return a path ordered by 'pathkeys' based on the given 'path'. May
- * return NULL if it doesn't make sense to generate an ordered path in
- * this case.
- */
-static Path *
-make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
- Path *cheapest_path, List *pathkeys)
-{
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- 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))
- return NULL;
-
- /*
- * We've no need to consider both a sort and incremental sort. We'll
- * just do a sort if there are no presorted keys and an incremental
- * sort when there are presorted keys.
- */
- if (presorted_keys == 0 || !enable_incremental_sort)
- path = (Path *) create_sort_path(root,
- rel,
- path,
- pathkeys,
- -1.0);
- else
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- pathkeys,
- presorted_keys,
- -1.0);
- }
-
- return path;
-}
-
/*
* add_paths_to_grouping_rel
*
@@ -6828,7 +6833,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
cheapest_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -6909,7 +6915,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
partially_grouped_rel->cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7160,7 +7167,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7217,7 +7225,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_partial_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7303,6 +7312,58 @@ create_partial_grouping_paths(PlannerInfo *root,
return partially_grouped_rel;
}
+/*
+ * make_ordered_path
+ * Return a path ordered by 'pathkeys' based on the given 'path'. May
+ * return NULL if it doesn't make sense to generate an ordered path in
+ * this case.
+ */
+static Path *
+make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
+ Path *cheapest_path, List *pathkeys, double limit_tuples)
+{
+ bool is_sorted;
+ int presorted_keys;
+
+ is_sorted = pathkeys_count_contained_in(pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+
+ 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))
+ return NULL;
+
+ /*
+ * We've no need to consider both a sort and incremental sort. We'll
+ * just do a sort if there are no presorted keys and an incremental
+ * sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ limit_tuples);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
+
+ return path;
+}
+
/*
* Generate Gather and Gather Merge paths for a grouping relation or partial
* grouping relation.
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 7fe58518d7..7384e4ad17 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -1060,6 +1060,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_distinct_reordering", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables reordering of DISTINCT pathkeys."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_distinct_reordering,
+ true,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index da10b43dac..0c2c21cacf 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -400,6 +400,7 @@
#enable_sort = on
#enable_tidscan = on
#enable_group_by_reordering = on
+#enable_distinct_reordering = on
# - Planner Cost Constants -
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 7b63c5cf71..798b9732b8 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -111,6 +111,7 @@ typedef enum
/* GUC parameters */
extern PGDLLIMPORT int debug_parallel_query;
extern PGDLLIMPORT bool parallel_leader_participation;
+extern PGDLLIMPORT bool enable_distinct_reordering;
extern struct PlannedStmt *planner(Query *parse, const char *query_string,
int cursorOptions,
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index 82b8e54f5f..bf30842d02 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -464,3 +464,114 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
t
(1 row)
+--
+-- DISTINCT optimization by reordering the distinctClause Pathkey nodes to
+-- match the input path's ordering
+--
+CREATE TABLE distinct_tbl AS SELECT
+ i % 10 AS x,
+ i % 10 AS y,
+ 'abc' || i % 10 AS z,
+ i AS w
+FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl(x, y);
+ANALYZE distinct_tbl;
+SET enable_hashagg TO OFF;
+SET enable_seqscan TO OFF;
+-- Utilize the ordering of index scan to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+ QUERY PLAN
+------------------------------------------------------------------
+ Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(2 rows)
+
+-- Engage incremental sort
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, w, x FROM distinct_tbl;
+ QUERY PLAN
+-------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: x, y, z, w
+ Presorted Key: x, y
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl
+(5 rows)
+
+-- Utilize the ordering of subquery scan to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT w, x, z, y
+ FROM (SELECT * FROM distinct_tbl ORDER BY x, y, w, z) AS s;
+ QUERY PLAN
+----------------------------------------------------------------------------------------
+ Unique
+ -> Subquery Scan on s
+ -> Incremental Sort
+ Sort Key: distinct_tbl.x, distinct_tbl.y, distinct_tbl.w, distinct_tbl.z
+ Presorted Key: distinct_tbl.x, distinct_tbl.y
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+-- Utilize the ordering of merge join to avoid a full-Sort operation
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.w, t1.x, t1.z, t1.y
+ FROM distinct_tbl t1 JOIN distinct_tbl t2 ON t1.x = t2.x AND t1.y = t2.y;
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: t1.x, t1.y, t1.w, t1.z
+ Presorted Key: t1.x, t1.y
+ -> Merge Join
+ Merge Cond: ((t1.x = t2.x) AND (t1.y = t2.y))
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl t1
+ -> Materialize
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl t2
+(9 rows)
+
+RESET enable_hashjoin;
+RESET enable_nestloop;
+-- Engage ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM distinct_tbl ORDER BY x, z;
+ QUERY PLAN
+-------------------------------------------------------------------------
+ Incremental Sort
+ Sort Key: x, z
+ Presorted Key: x
+ -> Unique
+ -> Incremental Sort
+ Sort Key: x, y, z
+ Presorted Key: x, y
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl
+(8 rows)
+
+-- Engage parallel DISTINCT
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------
+ Limit
+ -> Unique
+ -> Gather Merge
+ Workers Planned: 1
+ -> Unique
+ -> Parallel Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+RESET enable_seqscan;
+RESET enable_hashagg;
+DROP TABLE distinct_tbl;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index 9be7aca2b8..564c007ddd 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -113,6 +113,7 @@ select name, setting from pg_settings where name like 'enable%';
--------------------------------+---------
enable_async_append | on
enable_bitmapscan | on
+ enable_distinct_reordering | on
enable_gathermerge | on
enable_group_by_reordering | on
enable_hashagg | on
@@ -134,7 +135,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(23 rows)
+(24 rows)
-- There are always wait event descriptions for various types.
select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index da92c197ab..08a1050c56 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -221,3 +221,68 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
SELECT 2 IS NOT DISTINCT FROM null as "no";
SELECT null IS NOT DISTINCT FROM null as "yes";
+
+--
+-- DISTINCT optimization by reordering the distinctClause Pathkey nodes to
+-- match the input path's ordering
+--
+
+CREATE TABLE distinct_tbl AS SELECT
+ i % 10 AS x,
+ i % 10 AS y,
+ 'abc' || i % 10 AS z,
+ i AS w
+FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl(x, y);
+ANALYZE distinct_tbl;
+
+SET enable_hashagg TO OFF;
+SET enable_seqscan TO OFF;
+
+-- Utilize the ordering of index scan to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+
+-- Engage incremental sort
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, w, x FROM distinct_tbl;
+
+-- Utilize the ordering of subquery scan to avoid a Sort operation
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT w, x, z, y
+ FROM (SELECT * FROM distinct_tbl ORDER BY x, y, w, z) AS s;
+
+-- Utilize the ordering of merge join to avoid a full-Sort operation
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.w, t1.x, t1.z, t1.y
+ FROM distinct_tbl t1 JOIN distinct_tbl t2 ON t1.x = t2.x AND t1.y = t2.y;
+
+RESET enable_hashjoin;
+RESET enable_nestloop;
+
+-- Engage ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM distinct_tbl ORDER BY x, z;
+
+-- Engage parallel DISTINCT
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+
+RESET enable_seqscan;
+RESET enable_hashagg;
+
+DROP TABLE distinct_tbl;
--
2.31.0
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-06-07 09:46 ` Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Richard Guo @ 2024-06-07 09:46 UTC (permalink / raw)
To: David Rowley <dgrowleyml@gmail.com>; +Cc: pgsql-hackers
On Mon, Feb 5, 2024 at 11:18 AM Richard Guo <guofenglinux@gmail.com> wrote:
> cfbot reminds that this patch does not apply any more. So I've rebased
> it on master, and also adjusted the test cases a bit.
This patch does not apply any more, so here is a new rebase, with some
tweaks to the comments.
Thanks
Richard
Attachments:
v3-0001-Reordering-DISTINCT-keys-to-match-input-path-s-pathkeys.patch (application/octet-stream, 31.3K) download
From 08142f2c450ec5763875583923e00daaefd88c09 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 6 Jun 2024 19:23:55 +0900
Subject: [PATCH v3] Reordering DISTINCT keys to match input path's pathkeys
Similar to what we did to GROUP BY keys in 0452b461bc, we can do the
same to DISTINCT keys, i.e. reordering DISTINCT keys to match input
path's pathkeys, which can help reduce cost by avoiding unnecessary
re-sort, or allowing us to use incremental-sort to save efforts.
Please note that the parser has ensured that the DISTINCT pathkeys
matches the order of ORDER BY clauses. So there is no need to do this
part in this commit.
In principle, we can perform such reordering for DISTINCT ON too, but we
need to make sure that the resulting pathkeys matches initial ORDER BY
keys, which seems not trivial. So don't bother with that.
This introduces a new GUC enable_distinct_reordering so that the
optimization can be disabled if needed.
---
src/backend/optimizer/path/pathkeys.c | 36 ++
src/backend/optimizer/plan/planner.c | 457 ++++++++++--------
src/backend/utils/misc/guc_tables.c | 10 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/optimizer.h | 1 +
src/test/regress/expected/select_distinct.out | 112 +++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/sql/select_distinct.sql | 69 +++
8 files changed, 490 insertions(+), 199 deletions(-)
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 416fc4e240..55a59d894c 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2188,6 +2188,39 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
return n;
}
+/*
+ * pathkeys_useful_for_distinct
+ * Count the number of pathkeys that are useful for DISTINCT clause.
+ *
+ * DISTINCT keys could also be reordered to benefit from the ordering. As with
+ * pathkeys_useful_for_grouping, we return the number of leading keys in the
+ * list that are shared by the distinctClause pathkeys.
+ */
+static int
+pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
+{
+ int n_common_pathkeys;
+ ListCell *lc;
+
+ if (root->distinct_pathkeys == NIL)
+ return 0; /* no special ordering requested for DISTINCT */
+
+ /* walk the pathkeys and search for matching DISTINCT key */
+ n_common_pathkeys = 0;
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /* no matching DISTINCT key, we're done */
+ if (!list_member_ptr(root->distinct_pathkeys, pathkey))
+ break;
+
+ n_common_pathkeys++;
+ }
+
+ return n_common_pathkeys;
+}
+
/*
* pathkeys_useful_for_setop
* Count the number of leading common pathkeys root's 'setop_pathkeys' in
@@ -2221,6 +2254,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 4711f91239..57f21392cb 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -66,6 +66,7 @@
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
int debug_parallel_query = DEBUG_PARALLEL_OFF;
bool parallel_leader_participation = true;
+bool enable_distinct_reordering = true;
/* Hook for plugins to get control in planner() */
planner_hook_type planner_hook = NULL;
@@ -196,6 +197,9 @@ static void create_partial_distinct_paths(PlannerInfo *root,
static RelOptInfo *create_final_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel,
RelOptInfo *distinct_rel);
+static List *get_useful_pathkeys_for_distinct(PlannerInfo *root,
+ List *distinct_pathkeys,
+ List *path_pathkeys);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
PathTarget *target,
@@ -233,6 +237,12 @@ static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,
grouping_sets_data *gd,
GroupPathExtraData *extra,
bool force_rel_creation);
+static Path *make_ordered_path(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *path,
+ Path *cheapest_path,
+ List *pathkeys,
+ double limit_tuples);
static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);
static bool can_partial_agg(PlannerInfo *root);
static void apply_scanjoin_target_to_paths(PlannerInfo *root,
@@ -4874,86 +4884,68 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(root->distinct_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ root->distinct_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * Try at least sorting the cheapest path and also try
- * incrementally sorting any path which is partially sorted
- * already (no need to deal with paths which have presorted
- * keys when incremental sort is disabled unless it's the
- * cheapest partial path).
- */
- if (input_path != cheapest_partial_path &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = (List *) lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ partial_distinct_rel,
+ input_path,
+ cheapest_partial_path,
+ useful_pathkeys,
+ -1.0);
+
+ if (sorted_path == NULL)
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.
+ * An empty distinct_pathkeys means all tuples have the same value
+ * for the DISTINCT clause. See create_final_distinct_paths()
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- -1.0);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- presorted_keys,
- -1.0);
- }
-
- /*
- * An empty distinct_pathkeys means all tuples have the same value
- * for the DISTINCT clause. See create_final_distinct_paths()
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * Apply a LimitPath onto the partial path to restrict the
- * tuples from each worker to 1. create_final_distinct_paths
- * will need to apply an additional LimitPath to restrict this
- * to a single row after the Gather node. If the query
- * already has a LIMIT clause, then we could end up with three
- * Limit nodes in the final plan. Consolidating the top two
- * of these could be done, but does not seem worth troubling
- * over.
- */
- add_partial_path(partial_distinct_rel, (Path *)
- create_limit_path(root, partial_distinct_rel,
- sorted_path,
- NULL,
- limitCount,
- LIMIT_OPTION_COUNT,
- 0, 1));
- }
- else
- {
- add_partial_path(partial_distinct_rel, (Path *)
- create_upper_unique_path(root, partial_distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * Apply a LimitPath onto the partial path to restrict the
+ * tuples from each worker to 1. create_final_distinct_paths
+ * will need to apply an additional LimitPath to restrict this
+ * to a single row after the Gather node. If the query
+ * already has a LIMIT clause, then we could end up with three
+ * Limit nodes in the final plan. Consolidating the top two
+ * of these could be done, but does not seem worth troubling
+ * over.
+ */
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_limit_path(root, partial_distinct_rel,
+ sorted_path,
+ NULL,
+ limitCount,
+ LIMIT_OPTION_COUNT,
+ 0, 1));
+ }
+ else
+ {
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_upper_unique_path(root, partial_distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -5086,86 +5078,69 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(needed_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ needed_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * 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 &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = (List *) lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ distinct_rel,
+ input_path,
+ cheapest_input_path,
+ useful_pathkeys,
+ limittuples);
+
+ if (sorted_path == NULL)
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.
+ * distinct_pathkeys may have become empty if all of the
+ * pathkeys were determined to be redundant. If all of the
+ * pathkeys are redundant then each DISTINCT target must only
+ * allow a single value, therefore all resulting tuples must be
+ * identical (or at least indistinguishable by an equality
+ * check). We can uniquify these tuples simply by just taking
+ * the first tuple. All we do here is add a path to do "LIMIT
+ * 1" atop of 'sorted_path'. When doing a DISTINCT ON we may
+ * still have a non-NIL sort_pathkeys list, so we must still
+ * only do this with paths which are correctly sorted by
+ * sort_pathkeys.
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- limittuples);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- presorted_keys,
- limittuples);
- }
-
- /*
- * distinct_pathkeys may have become empty if all of the pathkeys
- * were determined to be redundant. If all of the pathkeys are
- * redundant then each DISTINCT target must only allow a single
- * value, therefore all resulting tuples must be identical (or at
- * least indistinguishable by an equality check). We can uniquify
- * these tuples simply by just taking the first tuple. All we do
- * here is add a path to do "LIMIT 1" atop of 'sorted_path'. When
- * doing a DISTINCT ON we may still have a non-NIL sort_pathkeys
- * list, so we must still only do this with paths which are
- * correctly sorted by sort_pathkeys.
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * If the query already has a LIMIT clause, then we could end
- * up with a duplicate LimitPath in the final plan. That does
- * not seem worth troubling over too much.
- */
- add_path(distinct_rel, (Path *)
- create_limit_path(root, distinct_rel, sorted_path,
- NULL, limitCount,
- LIMIT_OPTION_COUNT, 0, 1));
- }
- else
- {
- add_path(distinct_rel, (Path *)
- create_upper_unique_path(root, distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * If the query already has a LIMIT clause, then we could
+ * end up with a duplicate LimitPath in the final plan.
+ * That does not seem worth troubling over too much.
+ */
+ add_path(distinct_rel, (Path *)
+ create_limit_path(root, distinct_rel, sorted_path,
+ NULL, limitCount,
+ LIMIT_OPTION_COUNT, 0, 1));
+ }
+ else
+ {
+ add_path(distinct_rel, (Path *)
+ create_upper_unique_path(root, distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -5208,6 +5183,88 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
return distinct_rel;
}
+/*
+ * get_useful_pathkeys_for_distinct
+ * Get useful orderings of distinctClause by reordering 'distinct_pathkeys'
+ * to match the given 'path_pathkeys' as much as possible.
+ *
+ * This returns a list of pathkeys that can be useful for DISTINCT clause,
+ * which, for convenience, always includes the given 'distinct_pathkeys'.
+ */
+static List *
+get_useful_pathkeys_for_distinct(PlannerInfo *root, List *distinct_pathkeys,
+ List *path_pathkeys)
+{
+ List *useful_pathkeys_list = NIL;
+ List *useful_pathkeys = NIL;
+ ListCell *lc;
+
+ /* always include the given 'distinct_pathkeys' */
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ distinct_pathkeys);
+
+ if (!enable_distinct_reordering)
+ return useful_pathkeys_list;
+
+ /*
+ * Do not try to reorder pathkeys for DISTINCT ON
+ *
+ * XXX It might be possible to perform reordering for DISTINCT ON too, but
+ * we need to make sure that the resulting pathkeys matches initial ORDER
+ * BY keys, which seems not trivial. So don't bother with that.
+ */
+ if (root->parse->hasDistinctOn)
+ return useful_pathkeys_list;
+
+ /*
+ * Scan the given 'path_pathkeys' and construct a list of PathKey nodes
+ * that match 'distinct_pathkeys', but only as far as we can make a
+ * matching prefix.
+ */
+ foreach(lc, path_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /*
+ * The PathKey nodes are canonical, so they can be checked for equality
+ * by simple pointer comparison.
+ */
+ if (!list_member_ptr(distinct_pathkeys, pathkey))
+ break;
+
+ useful_pathkeys = lappend(useful_pathkeys, pathkey);
+ }
+
+ /* If no match at all, no point in reordering distinct_pathkeys */
+ if (useful_pathkeys == NIL)
+ return useful_pathkeys_list;
+
+ /*
+ * If not full match, the resulting pathkeys is not useful without
+ * incremental sort.
+ */
+ if (list_length(useful_pathkeys) < list_length(distinct_pathkeys) &&
+ !enable_incremental_sort)
+ return useful_pathkeys_list;
+
+ /* Append the remaining distinct PathKey nodes */
+ useful_pathkeys = list_concat_unique_ptr(useful_pathkeys,
+ distinct_pathkeys);
+
+ /*
+ * If the resulting pathkeys is the same as the 'distinct_pathkeys', just
+ * drop it.
+ */
+ if (compare_pathkeys(distinct_pathkeys,
+ useful_pathkeys) == PATHKEYS_EQUAL)
+ return useful_pathkeys_list;
+
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ useful_pathkeys);
+
+ return useful_pathkeys_list;
+}
+
/*
* create_ordered_paths
*
@@ -6905,58 +6962,6 @@ done:
return parallel_workers;
}
-/*
- * make_ordered_path
- * Return a path ordered by 'pathkeys' based on the given 'path'. May
- * return NULL if it doesn't make sense to generate an ordered path in
- * this case.
- */
-static Path *
-make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
- Path *cheapest_path, List *pathkeys)
-{
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- 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))
- return NULL;
-
- /*
- * We've no need to consider both a sort and incremental sort. We'll
- * just do a sort if there are no presorted keys and an incremental
- * sort when there are presorted keys.
- */
- if (presorted_keys == 0 || !enable_incremental_sort)
- path = (Path *) create_sort_path(root,
- rel,
- path,
- pathkeys,
- -1.0);
- else
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- pathkeys,
- presorted_keys,
- -1.0);
- }
-
- return path;
-}
-
/*
* add_paths_to_grouping_rel
*
@@ -7008,7 +7013,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
cheapest_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7089,7 +7095,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
partially_grouped_rel->cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7340,7 +7347,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7397,7 +7405,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_partial_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7483,6 +7492,58 @@ create_partial_grouping_paths(PlannerInfo *root,
return partially_grouped_rel;
}
+/*
+ * make_ordered_path
+ * Return a path ordered by 'pathkeys' based on the given 'path'. May
+ * return NULL if it doesn't make sense to generate an ordered path in
+ * this case.
+ */
+static Path *
+make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
+ Path *cheapest_path, List *pathkeys, double limit_tuples)
+{
+ bool is_sorted;
+ int presorted_keys;
+
+ is_sorted = pathkeys_count_contained_in(pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+
+ 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))
+ return NULL;
+
+ /*
+ * We've no need to consider both a sort and incremental sort. We'll
+ * just do a sort if there are no presorted keys and an incremental
+ * sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ limit_tuples);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
+
+ return path;
+}
+
/*
* Generate Gather and Gather Merge paths for a grouping relation or partial
* grouping relation.
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 46c258be28..26d491b80d 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -996,6 +996,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_distinct_reordering", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables reordering of DISTINCT pathkeys."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_distinct_reordering,
+ true,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index e0567de219..672822c46b 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -413,6 +413,7 @@
#enable_sort = on
#enable_tidscan = on
#enable_group_by_reordering = on
+#enable_distinct_reordering = on
# - Planner Cost Constants -
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 7b63c5cf71..798b9732b8 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -111,6 +111,7 @@ typedef enum
/* GUC parameters */
extern PGDLLIMPORT int debug_parallel_query;
extern PGDLLIMPORT bool parallel_leader_participation;
+extern PGDLLIMPORT bool enable_distinct_reordering;
extern struct PlannedStmt *planner(Query *parse, const char *query_string,
int cursorOptions,
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index 82b8e54f5f..febd613694 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -464,3 +464,115 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
t
(1 row)
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+CREATE TABLE distinct_tbl (x int, y int, z int);
+INSERT INTO distinct_tbl SELECT i%10, i%10, i FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl(x, y);
+ANALYZE distinct_tbl;
+SET enable_hashagg TO OFF;
+SET enable_seqscan TO OFF;
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of index scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+ QUERY PLAN
+------------------------------------------------------------------
+ Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(2 rows)
+
+-- Ensure we leverage incremental sort to avoid full Sort operation by
+-- reordering the distinctClause Pathkeys to partially match the ordering of
+-- index scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM distinct_tbl;
+ QUERY PLAN
+-------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: x, y, z
+ Presorted Key: x, y
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl
+(5 rows)
+
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of subquery scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x, z, y
+ FROM (SELECT * FROM distinct_tbl ORDER BY x, y, z) AS s;
+ QUERY PLAN
+-------------------------------------------------------------------------
+ Unique
+ -> Subquery Scan on s
+ -> Incremental Sort
+ Sort Key: distinct_tbl.x, distinct_tbl.y, distinct_tbl.z
+ Presorted Key: distinct_tbl.x, distinct_tbl.y
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+-- Ensure we leverage incremental sort to avoid full Sort operation by
+-- reordering the distinctClause Pathkeys to partially match the ordering of
+-- merge join
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.x, t1.z, t1.y
+ FROM distinct_tbl t1 JOIN distinct_tbl t2 ON t1.x = t2.x AND t1.y = t2.y;
+ QUERY PLAN
+---------------------------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: t1.x, t1.y, t1.z
+ Presorted Key: t1.x, t1.y
+ -> Merge Join
+ Merge Cond: ((t1.x = t2.x) AND (t1.y = t2.y))
+ -> Index Scan using distinct_tbl_x_y_idx on distinct_tbl t1
+ -> Materialize
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl t2
+(9 rows)
+
+RESET enable_hashjoin;
+RESET enable_nestloop;
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of index scan in parallel plan
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------
+ Limit
+ -> Unique
+ -> Gather Merge
+ Workers Planned: 1
+ -> Unique
+ -> Parallel Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of index
+-- scan even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y limit 1;
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Limit
+ -> Sort
+ Sort Key: y
+ -> Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(5 rows)
+
+RESET enable_seqscan;
+RESET enable_hashagg;
+DROP TABLE distinct_tbl;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index dbfd0c13d4..4bb87801fa 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -136,6 +136,7 @@ select name, setting from pg_settings where name like 'enable%';
--------------------------------+---------
enable_async_append | on
enable_bitmapscan | on
+ enable_distinct_reordering | on
enable_gathermerge | on
enable_group_by_reordering | on
enable_hashagg | on
@@ -156,7 +157,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(22 rows)
+(23 rows)
-- There are always wait event descriptions for various types.
select type, count(*) > 0 as ok FROM pg_wait_events
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index da92c197ab..f63469d401 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -221,3 +221,72 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
SELECT 2 IS NOT DISTINCT FROM null as "no";
SELECT null IS NOT DISTINCT FROM null as "yes";
+
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+
+CREATE TABLE distinct_tbl (x int, y int, z int);
+INSERT INTO distinct_tbl SELECT i%10, i%10, i FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl(x, y);
+ANALYZE distinct_tbl;
+
+SET enable_hashagg TO OFF;
+SET enable_seqscan TO OFF;
+
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of index scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+
+-- Ensure we leverage incremental sort to avoid full Sort operation by
+-- reordering the distinctClause Pathkeys to partially match the ordering of
+-- index scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT z, y, x FROM distinct_tbl;
+
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of subquery scan
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT x, z, y
+ FROM (SELECT * FROM distinct_tbl ORDER BY x, y, z) AS s;
+
+-- Ensure we leverage incremental sort to avoid full Sort operation by
+-- reordering the distinctClause Pathkeys to partially match the ordering of
+-- merge join
+SET enable_nestloop TO OFF;
+SET enable_hashjoin TO OFF;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT t1.x, t1.z, t1.y
+ FROM distinct_tbl t1 JOIN distinct_tbl t2 ON t1.x = t2.x AND t1.y = t2.y;
+
+RESET enable_hashjoin;
+RESET enable_nestloop;
+
+-- Ensure we avoid the Sort operation by reordering the distinctClause Pathkeys
+-- to match the ordering of index scan in parallel plan
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of index
+-- scan even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y limit 1;
+
+RESET enable_seqscan;
+RESET enable_hashagg;
+
+DROP TABLE distinct_tbl;
--
2.43.0
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-10-28 09:15 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Andrei Lepikhov @ 2024-10-28 09:15 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On 6/7/24 16:46, Richard Guo wrote:
> On Mon, Feb 5, 2024 at 11:18 AM Richard Guo <guofenglinux@gmail.com> wrote:
>> cfbot reminds that this patch does not apply any more. So I've rebased
>> it on master, and also adjusted the test cases a bit.
>
> This patch does not apply any more, so here is a new rebase, with some
> tweaks to the comments.
This patch needs a minor rebase again.
After skimming the code, I want to say that it looks good. But maybe to
avoid one more *_reordering GUC - it would be better to cover all path
key reorderings under a single GUC.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
@ 2024-11-13 06:49 ` Richard Guo <guofenglinux@gmail.com>
2024-11-13 10:36 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
0 siblings, 2 replies; 17+ messages in thread
From: Richard Guo @ 2024-11-13 06:49 UTC (permalink / raw)
To: Andrei Lepikhov <lepihov@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> On 6/7/24 16:46, Richard Guo wrote:
> > This patch does not apply any more, so here is a new rebase, with some
> > tweaks to the comments.
> This patch needs a minor rebase again.
> After skimming the code, I want to say that it looks good. But maybe to
> avoid one more *_reordering GUC - it would be better to cover all path
> key reorderings under a single GUC.
Thanks for reviewing this patch. After some consideration, I think
it's not too complex to also apply this optimization to DISTINCT ON.
The parser already ensures that the DISTINCT ON expressions match the
initial ORDER BY expressions; we just need to ensure that the
resulting pathkey list from the reordering matches the original
distinctClause pathkeys, while leaving the remaining pathkeys
unchanged in order. Please see attached.
I'm not sure about merging these two 'reordering' GUCs into one.
While they may look similar, they apply to very different scenarios.
However, I'm open to other suggestions.
Thanks
Richard
Attachments:
v4-0001-Reordering-DISTINCT-keys-to-match-input-path-s-pathkeys.patch (application/octet-stream, 38.4K) download
From a515b0faf26a8d3dc1a1c63aa8eda28d4bf98c32 Mon Sep 17 00:00:00 2001
From: Richard Guo <guofenglinux@gmail.com>
Date: Thu, 6 Jun 2024 19:23:55 +0900
Subject: [PATCH v4] Reordering DISTINCT keys to match input path's pathkeys
The ordering of DISTINCT items is semantically insignificant, so we
can reorder them as needed. In fact, in the parser, we absorb the
sorting semantics of the sortClause as much as possible into the
distinctClause, ensuring that one clause is a prefix of the other.
This can help avoid a possible need to re-sort.
In this commit, we attempt to adjust the DISTINCT keys to match the
input path's pathkeys. This can likewise help avoid re-sorting, or
allow us to use incremental-sort to save efforts.
For DISTINCT ON expressions, the parser already ensures that they
match the initial ORDER BY expressions. When reordering the DISTINCT
keys, we must ensure that the resulting pathkey list matches the
initial distinctClause pathkeys.
This introduces a new GUC, enable_distinct_reordering, which allows
the optimization to be disabled if needed.
Author: Richard Guo
Reviewed-by: Andrei Lepikhov
Discussion: https://postgr.es/m/CAMbWs48dR26cCcX0f=8bja2JKQPcU64136kHk=xekHT9xschiQ@mail.gmail.com
---
doc/src/sgml/config.sgml | 14 +
src/backend/optimizer/path/pathkeys.c | 41 ++
src/backend/optimizer/plan/planner.c | 465 ++++++++++--------
src/backend/utils/misc/guc_tables.c | 10 +
src/backend/utils/misc/postgresql.conf.sample | 1 +
src/include/optimizer/optimizer.h | 1 +
src/test/regress/expected/select_distinct.out | 132 +++++
.../regress/expected/select_distinct_on.out | 125 +++++
src/test/regress/expected/sysviews.out | 3 +-
src/test/regress/sql/select_distinct.sql | 53 ++
src/test/regress/sql/select_distinct_on.sql | 40 ++
11 files changed, 684 insertions(+), 201 deletions(-)
diff --git a/doc/src/sgml/config.sgml b/doc/src/sgml/config.sgml
index a84e60c09b..76ab72db96 100644
--- a/doc/src/sgml/config.sgml
+++ b/doc/src/sgml/config.sgml
@@ -5360,6 +5360,20 @@ ANY <replaceable class="parameter">num_sync</replaceable> ( <replaceable class="
</listitem>
</varlistentry>
+ <varlistentry id="guc-enable-distinct-reordering" xreflabel="enable_distinct_reordering">
+ <term><varname>enable_distinct_reordering</varname> (<type>boolean</type>)
+ <indexterm>
+ <primary><varname>enable_distinct_reordering</varname> configuration parameter</primary>
+ </indexterm>
+ </term>
+ <listitem>
+ <para>
+ Enables or disables the query planner's ability to reorder DISTINCT
+ keys to match the input path's pathkeys. The default is <literal>on</literal>.
+ </para>
+ </listitem>
+ </varlistentry>
+
<varlistentry id="guc-enable-gathermerge" xreflabel="enable_gathermerge">
<term><varname>enable_gathermerge</varname> (<type>boolean</type>)
<indexterm>
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 7cf15e89b6..c9fd4487d8 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2207,6 +2207,44 @@ pathkeys_useful_for_grouping(PlannerInfo *root, List *pathkeys)
return n;
}
+/*
+ * pathkeys_useful_for_distinct
+ * Count the number of pathkeys that are useful for DISTINCT or DISTINCT
+ * ON clause.
+ *
+ * DISTINCT keys could be reordered to benefit from the given pathkey list. As
+ * with pathkeys_useful_for_grouping, we return the number of leading keys in
+ * the list that are shared by the distinctClause pathkeys.
+ */
+static int
+pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
+{
+ int n_common_pathkeys;
+ ListCell *lc;
+
+ /*
+ * distinct_pathkeys may have become empty if all of the pathkeys were
+ * determined to be redundant. Return 0 in this case.
+ */
+ if (root->distinct_pathkeys == NIL)
+ return 0;
+
+ /* walk the pathkeys and search for matching DISTINCT key */
+ n_common_pathkeys = 0;
+ foreach(lc, pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /* no matching DISTINCT key, we're done */
+ if (!list_member_ptr(root->distinct_pathkeys, pathkey))
+ break;
+
+ n_common_pathkeys++;
+ }
+
+ return n_common_pathkeys;
+}
+
/*
* pathkeys_useful_for_setop
* Count the number of leading common pathkeys root's 'setop_pathkeys' in
@@ -2240,6 +2278,9 @@ truncate_useless_pathkeys(PlannerInfo *root,
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_grouping(root, pathkeys);
+ if (nuseful2 > nuseful)
+ nuseful = nuseful2;
+ nuseful2 = pathkeys_useful_for_distinct(root, pathkeys);
if (nuseful2 > nuseful)
nuseful = nuseful2;
nuseful2 = pathkeys_useful_for_setop(root, pathkeys);
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 1f78dc3d53..2870ef58f0 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -67,6 +67,7 @@
double cursor_tuple_fraction = DEFAULT_CURSOR_TUPLE_FRACTION;
int debug_parallel_query = DEBUG_PARALLEL_OFF;
bool parallel_leader_participation = true;
+bool enable_distinct_reordering = true;
/* Hook for plugins to get control in planner() */
planner_hook_type planner_hook = NULL;
@@ -198,6 +199,9 @@ static void create_partial_distinct_paths(PlannerInfo *root,
static RelOptInfo *create_final_distinct_paths(PlannerInfo *root,
RelOptInfo *input_rel,
RelOptInfo *distinct_rel);
+static List *get_useful_pathkeys_for_distinct(PlannerInfo *root,
+ List *needed_pathkeys,
+ List *path_pathkeys);
static RelOptInfo *create_ordered_paths(PlannerInfo *root,
RelOptInfo *input_rel,
PathTarget *target,
@@ -235,6 +239,12 @@ static RelOptInfo *create_partial_grouping_paths(PlannerInfo *root,
grouping_sets_data *gd,
GroupPathExtraData *extra,
bool force_rel_creation);
+static Path *make_ordered_path(PlannerInfo *root,
+ RelOptInfo *rel,
+ Path *path,
+ Path *cheapest_path,
+ List *pathkeys,
+ double limit_tuples);
static void gather_grouping_paths(PlannerInfo *root, RelOptInfo *rel);
static bool can_partial_agg(PlannerInfo *root);
static void apply_scanjoin_target_to_paths(PlannerInfo *root,
@@ -4938,7 +4948,10 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
/*
* Try sorting the cheapest path and incrementally sorting any paths with
- * presorted keys and put a unique paths atop of those.
+ * presorted keys and put a unique paths atop of those. We'll also
+ * attempt to reorder the required pathkeys to match the input path's
+ * pathkeys as much as possible, in hopes of avoiding a possible need to
+ * re-sort.
*/
if (grouping_is_sortable(root->processed_distinctClause))
{
@@ -4946,86 +4959,70 @@ create_partial_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(root->distinct_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ root->distinct_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * Try at least sorting the cheapest path and also try
- * incrementally sorting any path which is partially sorted
- * already (no need to deal with paths which have presorted
- * keys when incremental sort is disabled unless it's the
- * cheapest partial path).
- */
- if (input_path != cheapest_partial_path &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = (List *) lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ partial_distinct_rel,
+ input_path,
+ cheapest_partial_path,
+ useful_pathkeys,
+ -1.0);
+
+ if (sorted_path == NULL)
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.
+ * An empty distinct_pathkeys means all tuples have the same
+ * value for the DISTINCT clause. See
+ * create_final_distinct_paths()
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- -1.0);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- partial_distinct_rel,
- input_path,
- root->distinct_pathkeys,
- presorted_keys,
- -1.0);
- }
-
- /*
- * An empty distinct_pathkeys means all tuples have the same value
- * for the DISTINCT clause. See create_final_distinct_paths()
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * Apply a LimitPath onto the partial path to restrict the
- * tuples from each worker to 1. create_final_distinct_paths
- * will need to apply an additional LimitPath to restrict this
- * to a single row after the Gather node. If the query
- * already has a LIMIT clause, then we could end up with three
- * Limit nodes in the final plan. Consolidating the top two
- * of these could be done, but does not seem worth troubling
- * over.
- */
- add_partial_path(partial_distinct_rel, (Path *)
- create_limit_path(root, partial_distinct_rel,
- sorted_path,
- NULL,
- limitCount,
- LIMIT_OPTION_COUNT,
- 0, 1));
- }
- else
- {
- add_partial_path(partial_distinct_rel, (Path *)
- create_upper_unique_path(root, partial_distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * Apply a LimitPath onto the partial path to restrict the
+ * tuples from each worker to 1.
+ * create_final_distinct_paths will need to apply an
+ * additional LimitPath to restrict this to a single row
+ * after the Gather node. If the query already has a
+ * LIMIT clause, then we could end up with three Limit
+ * nodes in the final plan. Consolidating the top two of
+ * these could be done, but does not seem worth troubling
+ * over.
+ */
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_limit_path(root, partial_distinct_rel,
+ sorted_path,
+ NULL,
+ limitCount,
+ LIMIT_OPTION_COUNT,
+ 0, 1));
+ }
+ else
+ {
+ add_partial_path(partial_distinct_rel, (Path *)
+ create_upper_unique_path(root, partial_distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -5134,7 +5131,9 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
* Unique node on those. We also, consider doing an explicit sort of
* the cheapest input path and Unique'ing that. If any paths have
* presorted keys then we'll create an incremental sort atop of those
- * before adding a unique node on the top.
+ * before adding a unique node on the top. We'll also attempt to
+ * reorder the required pathkeys to match the input path's pathkeys as
+ * much as possible, in hopes of avoiding a possible need to re-sort.
*
* When we have DISTINCT ON, we must sort by the more rigorous of
* DISTINCT and ORDER BY, else it won't have the desired behavior.
@@ -5158,86 +5157,69 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
{
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
- bool is_sorted;
- int presorted_keys;
+ List *useful_pathkeys_list = NIL;
+ ListCell *lc2;
- is_sorted = pathkeys_count_contained_in(needed_pathkeys,
- input_path->pathkeys,
- &presorted_keys);
+ useful_pathkeys_list =
+ get_useful_pathkeys_for_distinct(root,
+ needed_pathkeys,
+ input_path->pathkeys);
+ Assert(list_length(useful_pathkeys_list) > 0);
- if (is_sorted)
- sorted_path = input_path;
- else
+ foreach(lc2, useful_pathkeys_list)
{
- /*
- * 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 &&
- (presorted_keys == 0 || !enable_incremental_sort))
+ List *useful_pathkeys = (List *) lfirst(lc2);
+
+ sorted_path = make_ordered_path(root,
+ distinct_rel,
+ input_path,
+ cheapest_input_path,
+ useful_pathkeys,
+ limittuples);
+
+ if (sorted_path == NULL)
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.
+ * distinct_pathkeys may have become empty if all of the
+ * pathkeys were determined to be redundant. If all of the
+ * pathkeys are redundant then each DISTINCT target must only
+ * allow a single value, therefore all resulting tuples must
+ * be identical (or at least indistinguishable by an equality
+ * check). We can uniquify these tuples simply by just taking
+ * the first tuple. All we do here is add a path to do "LIMIT
+ * 1" atop of 'sorted_path'. When doing a DISTINCT ON we may
+ * still have a non-NIL sort_pathkeys list, so we must still
+ * only do this with paths which are correctly sorted by
+ * sort_pathkeys.
*/
- if (presorted_keys == 0 || !enable_incremental_sort)
- sorted_path = (Path *) create_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- limittuples);
- else
- sorted_path = (Path *) create_incremental_sort_path(root,
- distinct_rel,
- input_path,
- needed_pathkeys,
- presorted_keys,
- limittuples);
- }
-
- /*
- * distinct_pathkeys may have become empty if all of the pathkeys
- * were determined to be redundant. If all of the pathkeys are
- * redundant then each DISTINCT target must only allow a single
- * value, therefore all resulting tuples must be identical (or at
- * least indistinguishable by an equality check). We can uniquify
- * these tuples simply by just taking the first tuple. All we do
- * here is add a path to do "LIMIT 1" atop of 'sorted_path'. When
- * doing a DISTINCT ON we may still have a non-NIL sort_pathkeys
- * list, so we must still only do this with paths which are
- * correctly sorted by sort_pathkeys.
- */
- if (root->distinct_pathkeys == NIL)
- {
- Node *limitCount;
+ if (root->distinct_pathkeys == NIL)
+ {
+ Node *limitCount;
- limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
- sizeof(int64),
- Int64GetDatum(1), false,
- FLOAT8PASSBYVAL);
+ limitCount = (Node *) makeConst(INT8OID, -1, InvalidOid,
+ sizeof(int64),
+ Int64GetDatum(1), false,
+ FLOAT8PASSBYVAL);
- /*
- * If the query already has a LIMIT clause, then we could end
- * up with a duplicate LimitPath in the final plan. That does
- * not seem worth troubling over too much.
- */
- add_path(distinct_rel, (Path *)
- create_limit_path(root, distinct_rel, sorted_path,
- NULL, limitCount,
- LIMIT_OPTION_COUNT, 0, 1));
- }
- else
- {
- add_path(distinct_rel, (Path *)
- create_upper_unique_path(root, distinct_rel,
- sorted_path,
- list_length(root->distinct_pathkeys),
- numDistinctRows));
+ /*
+ * If the query already has a LIMIT clause, then we could
+ * end up with a duplicate LimitPath in the final plan.
+ * That does not seem worth troubling over too much.
+ */
+ add_path(distinct_rel, (Path *)
+ create_limit_path(root, distinct_rel, sorted_path,
+ NULL, limitCount,
+ LIMIT_OPTION_COUNT, 0, 1));
+ }
+ else
+ {
+ add_path(distinct_rel, (Path *)
+ create_upper_unique_path(root, distinct_rel,
+ sorted_path,
+ list_length(root->distinct_pathkeys),
+ numDistinctRows));
+ }
}
}
}
@@ -5280,6 +5262,85 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
return distinct_rel;
}
+/*
+ * get_useful_pathkeys_for_distinct
+ * Get useful orderings of pathkeys for distinctClause by reordering
+ * 'needed_pathkeys' to match the given 'path_pathkeys' as much as possible.
+ *
+ * This returns a list of pathkeys that can be useful for DISTINCT or DISTINCT
+ * ON clause. For convenience, it always includes the given 'needed_pathkeys'.
+ */
+static List *
+get_useful_pathkeys_for_distinct(PlannerInfo *root, List *needed_pathkeys,
+ List *path_pathkeys)
+{
+ List *useful_pathkeys_list = NIL;
+ List *useful_pathkeys = NIL;
+ ListCell *lc;
+
+ /* always include the given 'needed_pathkeys' */
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ needed_pathkeys);
+
+ if (!enable_distinct_reordering)
+ return useful_pathkeys_list;
+
+ /*
+ * Scan the given 'path_pathkeys' and construct a list of PathKey nodes
+ * that match 'needed_pathkeys', but only up to the longest matching
+ * prefix.
+ *
+ * When we have DISTINCT ON, we must ensure that the resulting pathkey
+ * list matches initial distinctClause pathkeys; otherwise, it won't have
+ * the desired behavior.
+ */
+ foreach(lc, path_pathkeys)
+ {
+ PathKey *pathkey = (PathKey *) lfirst(lc);
+
+ /*
+ * The PathKey nodes are canonical, so they can be checked for
+ * equality by simple pointer comparison.
+ */
+ if (!list_member_ptr(needed_pathkeys, pathkey))
+ break;
+ if (root->parse->hasDistinctOn &&
+ !list_member_ptr(root->distinct_pathkeys, pathkey))
+ break;
+
+ useful_pathkeys = lappend(useful_pathkeys, pathkey);
+ }
+
+ /* If no match at all, no point in reordering needed_pathkeys */
+ if (useful_pathkeys == NIL)
+ return useful_pathkeys_list;
+
+ /*
+ * If not full match, the resulting pathkey list is not useful without
+ * incremental sort.
+ */
+ if (list_length(useful_pathkeys) < list_length(needed_pathkeys) &&
+ !enable_incremental_sort)
+ return useful_pathkeys_list;
+
+ /* Append the remaining PathKey nodes in needed_pathkeys */
+ useful_pathkeys = list_concat_unique_ptr(useful_pathkeys,
+ needed_pathkeys);
+
+ /*
+ * If the resulting pathkey list is the same as the 'needed_pathkeys',
+ * just drop it.
+ */
+ if (compare_pathkeys(needed_pathkeys,
+ useful_pathkeys) == PATHKEYS_EQUAL)
+ return useful_pathkeys_list;
+
+ useful_pathkeys_list = lappend(useful_pathkeys_list,
+ useful_pathkeys);
+
+ return useful_pathkeys_list;
+}
+
/*
* create_ordered_paths
*
@@ -7008,58 +7069,6 @@ done:
return parallel_workers;
}
-/*
- * make_ordered_path
- * Return a path ordered by 'pathkeys' based on the given 'path'. May
- * return NULL if it doesn't make sense to generate an ordered path in
- * this case.
- */
-static Path *
-make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
- Path *cheapest_path, List *pathkeys)
-{
- bool is_sorted;
- int presorted_keys;
-
- is_sorted = pathkeys_count_contained_in(pathkeys,
- path->pathkeys,
- &presorted_keys);
-
- 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))
- return NULL;
-
- /*
- * We've no need to consider both a sort and incremental sort. We'll
- * just do a sort if there are no presorted keys and an incremental
- * sort when there are presorted keys.
- */
- if (presorted_keys == 0 || !enable_incremental_sort)
- path = (Path *) create_sort_path(root,
- rel,
- path,
- pathkeys,
- -1.0);
- else
- path = (Path *) create_incremental_sort_path(root,
- rel,
- path,
- pathkeys,
- presorted_keys,
- -1.0);
- }
-
- return path;
-}
-
/*
* add_paths_to_grouping_rel
*
@@ -7111,7 +7120,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
cheapest_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7192,7 +7202,8 @@ add_paths_to_grouping_rel(PlannerInfo *root, RelOptInfo *input_rel,
grouped_rel,
path,
partially_grouped_rel->cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7443,7 +7454,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_total_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7500,7 +7512,8 @@ create_partial_grouping_paths(PlannerInfo *root,
partially_grouped_rel,
path,
cheapest_partial_path,
- info->pathkeys);
+ info->pathkeys,
+ -1.0);
if (path == NULL)
continue;
@@ -7586,6 +7599,58 @@ create_partial_grouping_paths(PlannerInfo *root,
return partially_grouped_rel;
}
+/*
+ * make_ordered_path
+ * Return a path ordered by 'pathkeys' based on the given 'path'. May
+ * return NULL if it doesn't make sense to generate an ordered path in
+ * this case.
+ */
+static Path *
+make_ordered_path(PlannerInfo *root, RelOptInfo *rel, Path *path,
+ Path *cheapest_path, List *pathkeys, double limit_tuples)
+{
+ bool is_sorted;
+ int presorted_keys;
+
+ is_sorted = pathkeys_count_contained_in(pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+
+ 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))
+ return NULL;
+
+ /*
+ * We've no need to consider both a sort and incremental sort. We'll
+ * just do a sort if there are no presorted keys and an incremental
+ * sort when there are presorted keys.
+ */
+ if (presorted_keys == 0 || !enable_incremental_sort)
+ path = (Path *) create_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ limit_tuples);
+ else
+ path = (Path *) create_incremental_sort_path(root,
+ rel,
+ path,
+ pathkeys,
+ presorted_keys,
+ limit_tuples);
+ }
+
+ return path;
+}
+
/*
* Generate Gather and Gather Merge paths for a grouping relation or partial
* grouping relation.
diff --git a/src/backend/utils/misc/guc_tables.c b/src/backend/utils/misc/guc_tables.c
index 8a67f01200..9845abd693 100644
--- a/src/backend/utils/misc/guc_tables.c
+++ b/src/backend/utils/misc/guc_tables.c
@@ -996,6 +996,16 @@ struct config_bool ConfigureNamesBool[] =
true,
NULL, NULL, NULL
},
+ {
+ {"enable_distinct_reordering", PGC_USERSET, QUERY_TUNING_METHOD,
+ gettext_noop("Enables reordering of DISTINCT pathkeys."),
+ NULL,
+ GUC_EXPLAIN
+ },
+ &enable_distinct_reordering,
+ true,
+ NULL, NULL, NULL
+ },
{
{"geqo", PGC_USERSET, QUERY_TUNING_GEQO,
gettext_noop("Enables genetic query optimization."),
diff --git a/src/backend/utils/misc/postgresql.conf.sample b/src/backend/utils/misc/postgresql.conf.sample
index 39a3ac2312..407cd1e08c 100644
--- a/src/backend/utils/misc/postgresql.conf.sample
+++ b/src/backend/utils/misc/postgresql.conf.sample
@@ -414,6 +414,7 @@
#enable_sort = on
#enable_tidscan = on
#enable_group_by_reordering = on
+#enable_distinct_reordering = on
# - Planner Cost Constants -
diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h
index 93e3dc719d..2e123e08b7 100644
--- a/src/include/optimizer/optimizer.h
+++ b/src/include/optimizer/optimizer.h
@@ -111,6 +111,7 @@ typedef enum
/* GUC parameters */
extern PGDLLIMPORT int debug_parallel_query;
extern PGDLLIMPORT bool parallel_leader_participation;
+extern PGDLLIMPORT bool enable_distinct_reordering;
extern struct PlannedStmt *planner(Query *parse, const char *query_string,
int cursorOptions,
diff --git a/src/test/regress/expected/select_distinct.out b/src/test/regress/expected/select_distinct.out
index 82b8e54f5f..379ba0bc9f 100644
--- a/src/test/regress/expected/select_distinct.out
+++ b/src/test/regress/expected/select_distinct.out
@@ -464,3 +464,135 @@ SELECT null IS NOT DISTINCT FROM null as "yes";
t
(1 row)
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+CREATE TABLE distinct_tbl (x int, y int);
+INSERT INTO distinct_tbl SELECT i%10, i%10 FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl (x, y);
+ANALYZE distinct_tbl;
+-- Produce results with sorting.
+SET enable_hashagg TO OFF;
+-- Ensure we avoid the need to re-sort by reordering the distinctClause
+-- Pathkeys to match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+ QUERY PLAN
+------------------------------------------------------------------
+ Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(2 rows)
+
+SELECT DISTINCT y, x FROM distinct_tbl;
+ y | x
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+-- Ensure we leverage incremental-sort by reordering the distinctClause
+-- Pathkeys to partially match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: s.x, s.y
+ Presorted Key: s.x
+ -> Subquery Scan on s
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+SELECT DISTINCT y, x FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+ y | x
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+-- Ensure we avoid the need to re-sort in partial distinct by reordering the
+-- distinctClause Pathkeys to match the ordering of the input path
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+ QUERY PLAN
+---------------------------------------------------------------------------------------------
+ Limit
+ -> Unique
+ -> Gather Merge
+ Workers Planned: 1
+ -> Unique
+ -> Parallel Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+ y | x
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of the
+-- input path even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
+ QUERY PLAN
+------------------------------------------------------------------------
+ Sort
+ Sort Key: y
+ -> Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(4 rows)
+
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
+ y | x
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+RESET enable_hashagg;
+DROP TABLE distinct_tbl;
diff --git a/src/test/regress/expected/select_distinct_on.out b/src/test/regress/expected/select_distinct_on.out
index 958381afe5..69e0cf3959 100644
--- a/src/test/regress/expected/select_distinct_on.out
+++ b/src/test/regress/expected/select_distinct_on.out
@@ -121,3 +121,128 @@ SELECT DISTINCT ON (four) four,hundred
Filter: (four = 0)
(3 rows)
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+CREATE TABLE distinct_tbl (x int, y int, z int);
+INSERT INTO distinct_tbl SELECT i%10, i%10, i%10 FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl (x, y);
+ANALYZE distinct_tbl;
+-- Produce results with sorting.
+SET enable_hashagg TO OFF;
+-- Ensure we avoid the need to re-sort by reordering the distinctClause
+-- Pathkeys to match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl;
+ QUERY PLAN
+------------------------------------------------------------------
+ Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(2 rows)
+
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl;
+ x | y
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+-- Ensure we leverage incremental-sort by reordering the distinctClause
+-- Pathkeys to partially match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+ QUERY PLAN
+------------------------------------------------------------------------------
+ Unique
+ -> Incremental Sort
+ Sort Key: s.x, s.y
+ Presorted Key: s.x
+ -> Subquery Scan on s
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(6 rows)
+
+SELECT DISTINCT ON (y, x) x, y FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+ x | y
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of the
+-- input path even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl ORDER BY y;
+ QUERY PLAN
+------------------------------------------------------------------------
+ Sort
+ Sort Key: y
+ -> Unique
+ -> Index Only Scan using distinct_tbl_x_y_idx on distinct_tbl
+(4 rows)
+
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl ORDER BY y;
+ x | y
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+-- Ensure the resulting pathkey list matches the initial distinctClause Pathkeys
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM (select * from distinct_tbl order by x, z, y) s ORDER BY y, x, z;
+ QUERY PLAN
+------------------------------------------------------------------------------------
+ Sort
+ Sort Key: s.y, s.x, s.z
+ -> Unique
+ -> Incremental Sort
+ Sort Key: s.x, s.y, s.z
+ Presorted Key: s.x
+ -> Subquery Scan on s
+ -> Sort
+ Sort Key: distinct_tbl.x, distinct_tbl.z, distinct_tbl.y
+ -> Seq Scan on distinct_tbl
+(10 rows)
+
+SELECT DISTINCT ON (y, x) x, y FROM (select * from distinct_tbl order by x, z, y) s ORDER BY y, x, z;
+ x | y
+---+---
+ 0 | 0
+ 1 | 1
+ 2 | 2
+ 3 | 3
+ 4 | 4
+ 5 | 5
+ 6 | 6
+ 7 | 7
+ 8 | 8
+ 9 | 9
+(10 rows)
+
+RESET enable_hashagg;
+DROP TABLE distinct_tbl;
diff --git a/src/test/regress/expected/sysviews.out b/src/test/regress/expected/sysviews.out
index fad7fc3a7e..91089ac215 100644
--- a/src/test/regress/expected/sysviews.out
+++ b/src/test/regress/expected/sysviews.out
@@ -150,6 +150,7 @@ select name, setting from pg_settings where name like 'enable%';
--------------------------------+---------
enable_async_append | on
enable_bitmapscan | on
+ enable_distinct_reordering | on
enable_gathermerge | on
enable_group_by_reordering | on
enable_hashagg | on
@@ -170,7 +171,7 @@ select name, setting from pg_settings where name like 'enable%';
enable_seqscan | on
enable_sort | on
enable_tidscan | on
-(22 rows)
+(23 rows)
-- There are always wait event descriptions for various types. InjectionPoint
-- may be present or absent, depending on history since last postmaster start.
diff --git a/src/test/regress/sql/select_distinct.sql b/src/test/regress/sql/select_distinct.sql
index da92c197ab..50ac7dde39 100644
--- a/src/test/regress/sql/select_distinct.sql
+++ b/src/test/regress/sql/select_distinct.sql
@@ -221,3 +221,56 @@ SELECT 1 IS NOT DISTINCT FROM 2 as "no";
SELECT 2 IS NOT DISTINCT FROM 2 as "yes";
SELECT 2 IS NOT DISTINCT FROM null as "no";
SELECT null IS NOT DISTINCT FROM null as "yes";
+
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+
+CREATE TABLE distinct_tbl (x int, y int);
+INSERT INTO distinct_tbl SELECT i%10, i%10 FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl (x, y);
+ANALYZE distinct_tbl;
+
+-- Produce results with sorting.
+SET enable_hashagg TO OFF;
+
+-- Ensure we avoid the need to re-sort by reordering the distinctClause
+-- Pathkeys to match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl;
+SELECT DISTINCT y, x FROM distinct_tbl;
+
+-- Ensure we leverage incremental-sort by reordering the distinctClause
+-- Pathkeys to partially match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+SELECT DISTINCT y, x FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+
+-- Ensure we avoid the need to re-sort in partial distinct by reordering the
+-- distinctClause Pathkeys to match the ordering of the input path
+SET parallel_tuple_cost=0;
+SET parallel_setup_cost=0;
+SET min_parallel_table_scan_size=0;
+SET min_parallel_index_scan_size=0;
+SET max_parallel_workers_per_gather=2;
+
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+SELECT DISTINCT y, x FROM distinct_tbl limit 10;
+
+RESET max_parallel_workers_per_gather;
+RESET min_parallel_index_scan_size;
+RESET min_parallel_table_scan_size;
+RESET parallel_setup_cost;
+RESET parallel_tuple_cost;
+
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of the
+-- input path even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
+SELECT DISTINCT y, x FROM distinct_tbl ORDER BY y;
+
+RESET enable_hashagg;
+
+DROP TABLE distinct_tbl;
diff --git a/src/test/regress/sql/select_distinct_on.sql b/src/test/regress/sql/select_distinct_on.sql
index 261e6140fe..d79dace94c 100644
--- a/src/test/regress/sql/select_distinct_on.sql
+++ b/src/test/regress/sql/select_distinct_on.sql
@@ -42,3 +42,43 @@ SELECT DISTINCT ON (four) four,two
EXPLAIN (COSTS OFF)
SELECT DISTINCT ON (four) four,hundred
FROM tenk1 WHERE four = 0 ORDER BY 1,2;
+
+--
+-- Test the planner's ability to reorder the distinctClause Pathkeys to match
+-- the input path's ordering
+--
+
+CREATE TABLE distinct_tbl (x int, y int, z int);
+INSERT INTO distinct_tbl SELECT i%10, i%10, i%10 FROM generate_series(1, 1000) AS i;
+CREATE INDEX distinct_tbl_x_y_idx ON distinct_tbl (x, y);
+ANALYZE distinct_tbl;
+
+-- Produce results with sorting.
+SET enable_hashagg TO OFF;
+
+-- Ensure we avoid the need to re-sort by reordering the distinctClause
+-- Pathkeys to match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl;
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl;
+
+-- Ensure we leverage incremental-sort by reordering the distinctClause
+-- Pathkeys to partially match the ordering of the input path
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+SELECT DISTINCT ON (y, x) x, y FROM (SELECT * FROM distinct_tbl ORDER BY x) s;
+
+-- Ensure we reorder the distinctClause Pathkeys to match the ordering of the
+-- input path even if there is ORDER BY clause
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl ORDER BY y;
+SELECT DISTINCT ON (y, x) x, y FROM distinct_tbl ORDER BY y;
+
+-- Ensure the resulting pathkey list matches the initial distinctClause Pathkeys
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT ON (y, x) x, y FROM (select * from distinct_tbl order by x, z, y) s ORDER BY y, x, z;
+SELECT DISTINCT ON (y, x) x, y FROM (select * from distinct_tbl order by x, z, y) s ORDER BY y, x, z;
+
+RESET enable_hashagg;
+
+DROP TABLE distinct_tbl;
--
2.43.0
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-13 10:36 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-14 01:09 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: Andrei Lepikhov @ 2024-11-13 10:36 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On 11/13/24 13:49, Richard Guo wrote:
> On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> On 6/7/24 16:46, Richard Guo wrote:
>>> This patch does not apply any more, so here is a new rebase, with some
>>> tweaks to the comments.
>
>> This patch needs a minor rebase again.
>> After skimming the code, I want to say that it looks good. But maybe to
>> avoid one more *_reordering GUC - it would be better to cover all path
>> key reorderings under a single GUC.
>
> Thanks for reviewing this patch. After some consideration, I think
> it's not too complex to also apply this optimization to DISTINCT ON.
> The parser already ensures that the DISTINCT ON expressions match the
> initial ORDER BY expressions; we just need to ensure that the
> resulting pathkey list from the reordering matches the original
> distinctClause pathkeys, while leaving the remaining pathkeys
> unchanged in order. Please see attached.
Thanks, I'll discover it later.
BTW have you ever thought about one more, cost-based reordering strategy?
For now, we can reorder GROUP-BY and distinct clauses according to two
orderings: 1) ORDER-BY order and 2) order derived from the underlying
query tree.
In thread [1], I try to add one more strategy that minimises the number
of comparison operator calls. It seems that it would work the same way
with the DISTINCT statement. Do you think it make sense in general and
can be a possible direction of improvement for the current patch?
>
> I'm not sure about merging these two 'reordering' GUCs into one.
> While they may look similar, they apply to very different scenarios.
> However, I'm open to other suggestions.
Sure, they enable different optimisations. But, they enable highly
specialised optimisations. Having two GUCs looks too expensive.
Moreover, this stuff is cost-based and should work automatically. So, I
treat these GUCs as mostly debugging or last-chance stuff used to
disable features during severe slowdowns or bugs. It might make sense to
group them into a single 'Clause Reordering' parameter.
[1]
https://www.postgresql.org/message-id/flat/8742aaa8-9519-4a1f-91bd-364aec65f5cf%40gmail.com
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-13 10:36 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
@ 2024-11-14 01:09 ` Richard Guo <guofenglinux@gmail.com>
2024-11-14 12:01 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Richard Guo @ 2024-11-14 01:09 UTC (permalink / raw)
To: Andrei Lepikhov <lepihov@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Wed, Nov 13, 2024 at 7:36 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> On 11/13/24 13:49, Richard Guo wrote:
> > Thanks for reviewing this patch. After some consideration, I think
> > it's not too complex to also apply this optimization to DISTINCT ON.
> > The parser already ensures that the DISTINCT ON expressions match the
> > initial ORDER BY expressions; we just need to ensure that the
> > resulting pathkey list from the reordering matches the original
> > distinctClause pathkeys, while leaving the remaining pathkeys
> > unchanged in order. Please see attached.
> BTW have you ever thought about one more, cost-based reordering strategy?
> For now, we can reorder GROUP-BY and distinct clauses according to two
> orderings: 1) ORDER-BY order and 2) order derived from the underlying
> query tree.
> In thread [1], I try to add one more strategy that minimises the number
> of comparison operator calls. It seems that it would work the same way
> with the DISTINCT statement. Do you think it make sense in general and
> can be a possible direction of improvement for the current patch?
I haven’t had a chance to follow that thread. From a quick look at
that patch, it seems to improve the general costing logic for sorting.
If that’s the case, I think it would be beneficial in the areas where
we use cost_sort(), including in this patch.
> > I'm not sure about merging these two 'reordering' GUCs into one.
> > While they may look similar, they apply to very different scenarios.
> > However, I'm open to other suggestions.
> Sure, they enable different optimisations. But, they enable highly
> specialised optimisations. Having two GUCs looks too expensive.
> Moreover, this stuff is cost-based and should work automatically. So, I
> treat these GUCs as mostly debugging or last-chance stuff used to
> disable features during severe slowdowns or bugs. It might make sense to
> group them into a single 'Clause Reordering' parameter.
I don't want to argue too much about this, but the two types of
optimizations are quite different in terms of implementation details.
For example, with DISTINCT ON, one key requirement is ensuring that
the resulting pathkey list matches the original distinctClause
pathkeys, and this logic doesn’t exist in the GROUP BY reordering
code. If these GUCs are mainly for debugging, I think it's better to
keep them separate so that we can debug each optimization individually.
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-13 10:36 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-14 01:09 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-14 12:01 ` Andrei Lepikhov <lepihov@gmail.com>
0 siblings, 0 replies; 17+ messages in thread
From: Andrei Lepikhov @ 2024-11-14 12:01 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On 11/14/24 08:09, Richard Guo wrote:
> On Wed, Nov 13, 2024 at 7:36 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> On 11/13/24 13:49, Richard Guo wrote:
>> In thread [1], I try to add one more strategy that minimises the number
>> of comparison operator calls. It seems that it would work the same way
>> with the DISTINCT statement. Do you think it make sense in general and
>> can be a possible direction of improvement for the current patch?
>
> I haven’t had a chance to follow that thread. From a quick look at
> that patch, it seems to improve the general costing logic for sorting.
> If that’s the case, I think it would be beneficial in the areas where
> we use cost_sort(), including in this patch.
Yes, the core of the discussion is cost calculation. It is a base for
the final patch that adds a grouping strategy, according to which it may
be profitable to put the column with max distinct value at the first
position to make sorting less expensive. I think it makes sense to do
the same in this DISTINCT feature, too (as a further improvement, of
course).
>> disable features during severe slowdowns or bugs. It might make sense to
>> group them into a single 'Clause Reordering' parameter.
> code. If these GUCs are mainly for debugging, I think it's better to
> keep them separate so that we can debug each optimization individually.
Ok.
See minor changes I propose in the attachment.
--
regards, Andrei Lepikhov
Attachments:
minor-fix.diff (text/x-patch, 3.5K) download
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 99063d0506..9006a14abc 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -2287,7 +2287,6 @@ static int
pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
{
int n_common_pathkeys;
- ListCell *lc;
/*
* distinct_pathkeys may have become empty if all of the pathkeys were
@@ -2298,10 +2297,8 @@ pathkeys_useful_for_distinct(PlannerInfo *root, List *pathkeys)
/* walk the pathkeys and search for matching DISTINCT key */
n_common_pathkeys = 0;
- foreach(lc, pathkeys)
+ foreach_node(PathKey, pathkey, pathkeys)
{
- PathKey *pathkey = (PathKey *) lfirst(lc);
-
/* no matching DISTINCT key, we're done */
if (!list_member_ptr(root->distinct_pathkeys, pathkey))
break;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 2870ef58f0..c22e41e83b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -5158,7 +5158,6 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
Path *input_path = (Path *) lfirst(lc);
Path *sorted_path;
List *useful_pathkeys_list = NIL;
- ListCell *lc2;
useful_pathkeys_list =
get_useful_pathkeys_for_distinct(root,
@@ -5166,10 +5165,8 @@ create_final_distinct_paths(PlannerInfo *root, RelOptInfo *input_rel,
input_path->pathkeys);
Assert(list_length(useful_pathkeys_list) > 0);
- foreach(lc2, useful_pathkeys_list)
+ foreach_node(List, useful_pathkeys, useful_pathkeys_list)
{
- List *useful_pathkeys = (List *) lfirst(lc2);
-
sorted_path = make_ordered_path(root,
distinct_rel,
input_path,
@@ -5276,11 +5273,9 @@ get_useful_pathkeys_for_distinct(PlannerInfo *root, List *needed_pathkeys,
{
List *useful_pathkeys_list = NIL;
List *useful_pathkeys = NIL;
- ListCell *lc;
/* always include the given 'needed_pathkeys' */
- useful_pathkeys_list = lappend(useful_pathkeys_list,
- needed_pathkeys);
+ useful_pathkeys_list = lappend(useful_pathkeys_list, needed_pathkeys);
if (!enable_distinct_reordering)
return useful_pathkeys_list;
@@ -5294,10 +5289,8 @@ get_useful_pathkeys_for_distinct(PlannerInfo *root, List *needed_pathkeys,
* list matches initial distinctClause pathkeys; otherwise, it won't have
* the desired behavior.
*/
- foreach(lc, path_pathkeys)
+ foreach_node(PathKey, pathkey, path_pathkeys)
{
- PathKey *pathkey = (PathKey *) lfirst(lc);
-
/*
* The PathKey nodes are canonical, so they can be checked for
* equality by simple pointer comparison.
@@ -5324,19 +5317,16 @@ get_useful_pathkeys_for_distinct(PlannerInfo *root, List *needed_pathkeys,
return useful_pathkeys_list;
/* Append the remaining PathKey nodes in needed_pathkeys */
- useful_pathkeys = list_concat_unique_ptr(useful_pathkeys,
- needed_pathkeys);
+ useful_pathkeys = list_concat_unique_ptr(useful_pathkeys, needed_pathkeys);
/*
* If the resulting pathkey list is the same as the 'needed_pathkeys',
* just drop it.
*/
- if (compare_pathkeys(needed_pathkeys,
- useful_pathkeys) == PATHKEYS_EQUAL)
+ if (compare_pathkeys(needed_pathkeys, useful_pathkeys) == PATHKEYS_EQUAL)
return useful_pathkeys_list;
- useful_pathkeys_list = lappend(useful_pathkeys_list,
- useful_pathkeys);
+ useful_pathkeys_list = lappend(useful_pathkeys_list, useful_pathkeys);
return useful_pathkeys_list;
}
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-22 08:39 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: Andrei Lepikhov @ 2024-11-22 08:39 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On 11/13/24 13:49, Richard Guo wrote:
> On Mon, Oct 28, 2024 at 6:15 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> On 6/7/24 16:46, Richard Guo wrote:
> I'm not sure about merging these two 'reordering' GUCs into one.
> While they may look similar, they apply to very different scenarios.
> However, I'm open to other suggestions.
I finally have passed through the code. It generally looks OK. Let me
only write a few words on tests.
I wonder if it would be possible to print only three rows instead of 10
to prove the DISTINCT's correctness.
Also, to stabilise tests with parallel workers, I would recommend
setting max_parallel_workers_per_gather into 1 and enabling
debug_parallel_query.
--
regards, Andrei Lepikhov
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
@ 2024-11-26 00:43 ` Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:10 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:12 ` Re: Reordering DISTINCT keys to match input path's pathkeys Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 17+ messages in thread
From: Richard Guo @ 2024-11-26 00:43 UTC (permalink / raw)
To: Andrei Lepikhov <lepihov@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Fri, Nov 22, 2024 at 5:40 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> I wonder if it would be possible to print only three rows instead of 10
> to prove the DISTINCT's correctness.
There are ten distinct values in the 'distinct_tbl' test table, so
I think it’d better to print all of them to verify correctness.
> Also, to stabilise tests with parallel workers, I would recommend
> setting max_parallel_workers_per_gather into 1 and enabling
> debug_parallel_query.
Since we're testing sort-based DISTINCT, the results will always be
well-ordered, so they should be pretty stable as is.
I've applied some of the changes you suggested in your previous email
and pushed the updated patch. Thank you for your review.
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-26 01:10 ` Richard Guo <guofenglinux@gmail.com>
1 sibling, 0 replies; 17+ messages in thread
From: Richard Guo @ 2024-11-26 01:10 UTC (permalink / raw)
To: Andrei Lepikhov <lepihov@gmail.com>; +Cc: pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Tue, Nov 26, 2024 at 9:43 AM Richard Guo <guofenglinux@gmail.com> wrote:
> I've applied some of the changes you suggested in your previous email
> and pushed the updated patch. Thank you for your review.
Ah, the buildfarm is complaining. I shouldn't create tables with the
same name in two test files. Fixing ...
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-26 01:12 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-11-26 01:22 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
1 sibling, 1 reply; 17+ messages in thread
From: Tom Lane @ 2024-11-26 01:12 UTC (permalink / raw)
To: Richard Guo <guofenglinux@gmail.com>; +Cc: Andrei Lepikhov <lepihov@gmail.com>; pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
Richard Guo <guofenglinux@gmail.com> writes:
> I've applied some of the changes you suggested in your previous email
> and pushed the updated patch. Thank you for your review.
The buildfarm's not too happy. It looks like this patch decided
to use the name "distinct_tbl" in a test script that runs in
parallel with another one already using "distinct_tbl".
regards, tom lane
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:12 ` Re: Reordering DISTINCT keys to match input path's pathkeys Tom Lane <tgl@sss.pgh.pa.us>
@ 2024-11-26 01:22 ` Richard Guo <guofenglinux@gmail.com>
2024-11-26 05:56 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
0 siblings, 1 reply; 17+ messages in thread
From: Richard Guo @ 2024-11-26 01:22 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andrei Lepikhov <lepihov@gmail.com>; pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Tue, Nov 26, 2024 at 10:12 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Richard Guo <guofenglinux@gmail.com> writes:
> > I've applied some of the changes you suggested in your previous email
> > and pushed the updated patch. Thank you for your review.
>
> The buildfarm's not too happy. It looks like this patch decided
> to use the name "distinct_tbl" in a test script that runs in
> parallel with another one already using "distinct_tbl".
Exactly. I shouldn't create tables with the same name in two test
files. Will push a fix shortly.
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
* Re: Reordering DISTINCT keys to match input path's pathkeys
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 09:03 ` Re: Reordering DISTINCT keys to match input path's pathkeys David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-22 08:39 ` Re: Reordering DISTINCT keys to match input path's pathkeys Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:12 ` Re: Reordering DISTINCT keys to match input path's pathkeys Tom Lane <tgl@sss.pgh.pa.us>
2024-11-26 01:22 ` Re: Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
@ 2024-11-26 05:56 ` Richard Guo <guofenglinux@gmail.com>
0 siblings, 0 replies; 17+ messages in thread
From: Richard Guo @ 2024-11-26 05:56 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Andrei Lepikhov <lepihov@gmail.com>; pgsql-hackers; David Rowley <dgrowleyml@gmail.com>
On Tue, Nov 26, 2024 at 10:22 AM Richard Guo <guofenglinux@gmail.com> wrote:
> On Tue, Nov 26, 2024 at 10:12 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > Richard Guo <guofenglinux@gmail.com> writes:
> > > I've applied some of the changes you suggested in your previous email
> > > and pushed the updated patch. Thank you for your review.
> > The buildfarm's not too happy. It looks like this patch decided
> > to use the name "distinct_tbl" in a test script that runs in
> > parallel with another one already using "distinct_tbl".
> Exactly. I shouldn't create tables with the same name in two test
> files. Will push a fix shortly.
Fixed.
Thanks
Richard
^ permalink raw reply [nested|flat] 17+ messages in thread
end of thread, other threads:[~2024-11-26 05:56 UTC | newest]
Thread overview: 17+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-01-23 05:55 Reordering DISTINCT keys to match input path's pathkeys Richard Guo <guofenglinux@gmail.com>
2024-01-23 08:04 ` Laurenz Albe <laurenz.albe@cybertec.at>
2024-01-23 09:03 ` David Rowley <dgrowleyml@gmail.com>
2024-01-26 10:48 ` Richard Guo <guofenglinux@gmail.com>
2024-02-05 03:18 ` Richard Guo <guofenglinux@gmail.com>
2024-06-07 09:46 ` Richard Guo <guofenglinux@gmail.com>
2024-10-28 09:15 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-13 06:49 ` Richard Guo <guofenglinux@gmail.com>
2024-11-13 10:36 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-14 01:09 ` Richard Guo <guofenglinux@gmail.com>
2024-11-14 12:01 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-22 08:39 ` Andrei Lepikhov <lepihov@gmail.com>
2024-11-26 00:43 ` Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:10 ` Richard Guo <guofenglinux@gmail.com>
2024-11-26 01:12 ` Tom Lane <tgl@sss.pgh.pa.us>
2024-11-26 01:22 ` Richard Guo <guofenglinux@gmail.com>
2024-11-26 05:56 ` Richard Guo <guofenglinux@gmail.com>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox