Hello, This is the last episode of the 'dance with indices'?
series.

Unique indexes can sort the tuples in corresponding tables
prefectly. So this query might can use index.

> uniquetest=# create table t (a int, b int, c int, d text);
> uniquetest=# create unique index i_t_pkey on t(a, b);
> uniquetest=# insert into t
>   (select a % 10, a / 10, a, 't' from generate_series(0, 100000) a);
> uniquetest=# analyze;
> 
> uniquetest=# explain (costs off, analyze on) select distinct * from t;
>                                 QUERY PLAN                                 
> ---------------------------------------------------------------------------
> Unique (actual time=149.625..245.978 rows=100001 loops=1)
>  ->  Sort (actual time=149.624..199.806 rows=100001 loops=1)
>      Sort Key: a, b, c, d
>      Sort Method: external merge  Disk: 2328kB
>   ->  Seq Scan on t (actual time=0.016..15.597 rows=100001 loops=1)
> Total runtime: 251.272 ms

With this patch, the plan for this query becomes as follows,

> uniquetest=# explain (costs off, analyze on) select distinct * from t;
>                               QUERY PLAN
> ---------------------------------------------------------------------
>  Index Scan using i_t_pkey on t
>                   (actual time=0.019..32.457 rows=100001 loops=1)
>  Total runtime: 37.488 ms

This only seems not so valuable to archive, but with my previous
MergeAppend for UNION patch, this will have more value.

> uniquetest=# create table pu1 (a int, b int, c int, d text);
> uniquetest=# create unique index pu1_pkey_idx on pu1 (a, b);
> uniquetest=# create table cu11 (like pu1 including all) inherits (pu1);
> uniquetest=# create table cu12 (like pu1 including all) inherits (pu1);
> uniquetest=# create table pu2 (like pu1 including all);
> uniquetest=# create table cu21 (like pu1 including all) inherits (pu2);
> uniquetest=# create table cu22 (like pu1 including all) inherits (pu2);
> uniquetest=# insert into cu11 (select a / 5, 4 - (a % 5), a, 'cu11'
>                               from generate_series(000000, 099999) a);
> uniquetest=# insert into cu12 (select a / 5, 4 - (a % 5), a, 'cu12'
>                                from generate_series(100000, 199999) a);
> uniquetest=# insert into cu21 (select a / 5, 4 - (a % 5), a, 'cu21'
>                               from generate_series(150000, 249999) a);
> uniquetest=# insert into cu22 (select a / 5, 4 - (a % 5), a, 'cu22'
>                                from generate_series(250000, 349999) a);
> uniquetest=# explain (analyze on, costs off)
>        select * from pu1 union select * from pu2 order by a, b limit 100;
>                                  QUERY PLAN
> --------------------------------------------------------------------------
>  Limit (actual time=0.226..0.591 rows=100 loops=1)
>   ->  Unique (actual time=0.223..0.561 rows=100 loops=1)
>    ->  Merge Append (actual time=0.223..0.470 rows=100 loops=1)
>        Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
>     ->  Limit (actual time=0.125..0.326 rows=100 loops=1)
>      ->  Unique (actual time=0.125..0.303 rows=100 loops=1)
>       ->  Merge Append (actual time=0.123..0.220 rows=100 loops=1)
>           Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
>        ->  Index Scan using..on pu1 (actual time=0.005..0.005 rows=0 loops=1)
>        ->  Index Scan using..on cu11(actual time=0.071..0.128 rows=100 
> loops=1)
>        ->  Index Scan using..on cu12 (actual time=0.045..0.045 rows=1 loops=1)
>     ->  Limit (actual time=0.096..0.096 rows=1 loops=1)
>      ->  Unique (actual time=0.096..0.096 rows=1 loops=1)
>       ->  Merge Append (actual time=0.094..0.094 rows=1 loops=1)
>           Sort Key: pu2.a, pu2.b, pu2.c, pu2.d
>        ->  Index Scan using..on pu2 (actual time=0.002..0.002 rows=0 loops=1)
>        ->  Index Scan using..on cu21 (actual time=0.047..0.047 rows=1 loops=1)
>        ->  Index Scan using..on cu22 (actual time=0.043..0.043 rows=1 loops=1)
>  Total runtime: 1.987 ms

On the other hand, what we will get from the unpatched PostgreSQL is,

> uniquetest=# explain (analyze on, costs off)
>      select * from pu1 union select * from pu2 order by a, b limit 100;
>                                QUERY PLAN
> -------------------------------------------------------------------------
> Limit (actual time=535.620..535.706 rows=100 loops=1)
>  ->  Unique (actual time=535.618..535.695 rows=100 loops=1)
>   ->  Sort (actual time=535.617..535.637 rows=100 loops=1)
>       Sort Key: pu1.a, pu1.b, pu1.c, pu1.d
>       Sort Method: external sort  Disk: 10568kB
>    ->  Append (actual time=0.012..144.144 rows=400000 loops=1)
>     ->  Append (actual time=0.012..49.570 rows=200000 loops=1)
>      ->  Seq Scan on pu1 (actual time=0.001..0.001 rows=0 loops=1)
>      ->  Seq Scan on cu11 (actual time=0.011..16.202 rows=100000 loops=1)
>      ->  Seq Scan on cu12 (actual time=0.008..16.334 rows=100000 loops=1)
>     ->  Append (actual time=0.010..54.052 rows=200000 loops=1)
>      ->  Seq Scan on pu2 (actual time=0.000..0.000 rows=0 loops=1)
>      ->  Seq Scan on cu21 (actual time=0.009..16.444 rows=100000 loops=1)
>      ->  Seq Scan on cu22 (actual time=0.021..18.923 rows=100000 loops=1)
> Total runtime: 537.765 ms

What do you think about this?


This could be realized by following modifications,

 - Consider a query pathekeys is useful for ordering when a index
   pathkey is a subset of that when the index is UNIQUE.
   (build_index_paths, pathkeys_useful_for_ordering,
   truncate_useless_pathkeys, grouping_planner)

 - Judge a path is orderd or not counting the uniqueness of the
   path.

    - Regard IndexPath on UNIQUE index is reagarded uniquely
      ordered.

    - Regard MergeAppendPath of which all children is uniquely
      orderd as (not necessarily uniquely) ordered.
      (path_is_ordered)

 - Judge the necessity of sorting on above
   premises. (grouping_planner)

Needless to say, theses patches have no effect on any other set
operations than UNION(ALL). They are, INTERSECT(ALL),
EXCEPT(ALL).

regards,

-- 
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c
index 606734a..bc1ab9a 100644
--- a/src/backend/optimizer/path/indxpath.c
+++ b/src/backend/optimizer/path/indxpath.c
@@ -953,7 +953,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 		index_pathkeys = build_index_pathkeys(root, index,
 											  ForwardScanDirection);
 		useful_pathkeys = truncate_useless_pathkeys(root, rel,
-													index_pathkeys);
+													index_pathkeys,
+													index->unique);
 		orderbyclauses = NIL;
 		orderbyclausecols = NIL;
 	}
@@ -1015,7 +1016,8 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel,
 		index_pathkeys = build_index_pathkeys(root, index,
 											  BackwardScanDirection);
 		useful_pathkeys = truncate_useless_pathkeys(root, rel,
-													index_pathkeys);
+													index_pathkeys,
+													index->unique);
 		if (useful_pathkeys != NIL)
 		{
 			ipath = create_index_path(root, index,
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
index 6724996..87070e7 100644
--- a/src/backend/optimizer/path/pathkeys.c
+++ b/src/backend/optimizer/path/pathkeys.c
@@ -363,6 +363,68 @@ get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 }
 
 /*
+ * path_is_uniquely_ordered
+ * Return true if the path is apparently uniquely ordered on the pathkeys.
+ */
+bool
+path_is_uniquely_ordered(Path *path, List *pathkeys)
+{
+	if (pathkeys && path->pathkeys &&
+		IsA(path, IndexPath) &&
+		((IndexPath*)path)->indexinfo->unique &&
+		(pathkeys_contained_in(path->pathkeys, pathkeys)))
+	{
+		return true;
+	}
+	
+	return false;
+}
+
+
+/*
+ * path_is_ordered
+ * Return true if the path is apparently ordered on the pathkeys.  The given
+ * path might be modified so that it will be recognized later as sufficiently
+ * ordered.
+ */
+bool
+path_is_ordered(Path *path, List *pathkeys)
+{
+	if (pathkeys_contained_in(pathkeys, path->pathkeys))
+		return true;
+
+	/* path is obviously ordered when uniquely ordered */
+	if (path_is_uniquely_ordered(path, pathkeys))
+		return true;
+
+	/*
+	 * MergeAppendPath's pathkeys can be replaced by arbitrary pathkeys when
+	 * all subpaths are uniquely ordered on the target pathkeys.
+	 */
+	if (IsA(path, MergeAppendPath))
+	{
+		ListCell *lc;
+		MergeAppendPath *mpath = (MergeAppendPath *)path;
+		
+		foreach (lc, mpath->subpaths)
+		{
+			Path *subpath = (Path *) lfirst(lc);
+			if (!path_is_uniquely_ordered(subpath, pathkeys)) break;
+		}
+		if (!lc)
+		{
+			/*
+			 * This MergeAppendPath is sufficiently ordered on the target
+			 * pathkeys. Reflect that on this path.
+			 */
+			mpath->path.pathkeys = pathkeys;
+			return true;
+		}
+	}
+	return false;
+}
+
+/*
  * get_cheapest_fractional_path_for_pathkeys
  *	  Find the cheapest path (for retrieving a specified fraction of all
  *	  the tuples) that satisfies the given pathkeys and parameterization.
@@ -397,7 +459,7 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
 			compare_fractional_path_costs(matched_path, path, fraction) <= 0)
 			continue;
 
-		if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
+		if (path_is_ordered(path, pathkeys) &&
 			bms_is_subset(PATH_REQ_OUTER(path), required_outer))
 			matched_path = path;
 	}
@@ -733,7 +795,7 @@ build_join_pathkeys(PlannerInfo *root,
 	 * contain pathkeys that were useful for forming this joinrel but are
 	 * uninteresting to higher levels.
 	 */
-	return truncate_useless_pathkeys(root, joinrel, outer_pathkeys);
+	return truncate_useless_pathkeys(root, joinrel, outer_pathkeys, false);
 }
 
 /****************************************************************************
@@ -1378,9 +1440,12 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey)
  * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
  * no good to order by just the first key(s) of the requested ordering.
  * So the result is always either 0 or list_length(root->query_pathkeys).
+ * pk_uniq can be true when pathkeys are unique key itself. Tuples are
+ * sufficiently ordered when the pathkeys are the subset of the
+ * query_pathkeys for the case.
  */
 static int
-pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
+pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys, bool pk_uniq)
 {
 	if (root->query_pathkeys == NIL)
 		return 0;				/* no special ordering requested */
@@ -1394,23 +1459,34 @@ pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
 		return list_length(root->query_pathkeys);
 	}
 
+	/*
+	 * Given that the pathkeys compose an unique key, they are useful for
+	 * ordering when they are a sublist of query_pathkeys.
+	 */
+	if (pk_uniq && pathkeys_contained_in(pathkeys, root->query_pathkeys))
+		return list_length(pathkeys);
+
 	return 0;					/* path ordering not useful */
 }
 
 /*
  * truncate_useless_pathkeys
  *		Shorten the given pathkey list to just the useful pathkeys.
+ *
+ * When pathkeys_unique is true, reconsider counting the uniqueness even if
+ * the pathkeys are once judged as useless by the general criteria.
  */
 List *
 truncate_useless_pathkeys(PlannerInfo *root,
 						  RelOptInfo *rel,
-						  List *pathkeys)
+						  List *pathkeys,
+						  bool pathkeys_unique)
 {
 	int			nuseful;
 	int			nuseful2;
 
 	nuseful = pathkeys_useful_for_merging(root, rel, pathkeys);
-	nuseful2 = pathkeys_useful_for_ordering(root, pathkeys);
+	nuseful2 = pathkeys_useful_for_ordering(root, pathkeys, pathkeys_unique);
 	if (nuseful2 > nuseful)
 		nuseful = nuseful2;
 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 9b9eb2f..7b1490f 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -809,7 +809,7 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)
 					  numsortkeys * sizeof(bool)) == 0);
 
 		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
-		if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
+		if (!path_is_ordered(subpath, pathkeys))
 			subplan = (Plan *) make_sort(root, subplan, numsortkeys,
 										 sortColIdx, sortOperators,
 										 collations, nullsFirst,
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 86abdf6..1ce04ac 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -258,6 +258,31 @@ standard_planner(Query *parse, int cursorOptions, ParamListInfo boundParams)
 	return result;
 }
 
+/*
+ * Check if a path is sufficiently ordered on target pathkeys. This function
+ * is intended to be used as a replace for pathkeys_contained_in() when the
+ * focused path might be uniquely ordered on the current_pathkeys.
+ */
+static bool
+sort_needed(List *current_pathkeys, bool path_is_unique, List *target_pathkeys)
+{
+	/*
+	 * If target pathkeys are a sublist of current pathkeys, the path is
+	 * ordered also on target pathkeys
+	 */
+	if (pathkeys_contained_in(target_pathkeys, current_pathkeys))
+		return false;
+	
+    /*
+	 * If a plan is uniquely ordered on current_pathkeys, it is sufficiently
+	 * ordered on any pathkeys containing it.
+	 */
+	if (path_is_unique && current_pathkeys &&
+		pathkeys_contained_in(current_pathkeys, target_pathkeys))
+		return false;
+
+	return true;
+}
 
 /*--------------------
  * subquery_planner
@@ -1043,6 +1068,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	double		dNumGroups = 0;
 	bool		use_hashed_distinct = false;
 	bool		tested_hashed_distinct = false;
+	bool		result_plan_is_unique = false;
 
 	/* Tweak caller-supplied tuple_fraction if have LIMIT/OFFSET */
 	if (parse->limitCount || parse->limitOffset)
@@ -1451,18 +1477,24 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 
 			result_plan = create_plan(root, best_path);
 			current_pathkeys = best_path->pathkeys;
+			result_plan_is_unique =
+				path_is_uniquely_ordered(best_path, root->query_pathkeys);
 
 			/* Detect if we'll need an explicit sort for grouping */
-			if (parse->groupClause && !use_hashed_grouping &&
-			  !pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
+			if (parse->groupClause && !use_hashed_grouping)
 			{
-				need_sort_for_grouping = true;
+				if (path_is_ordered(best_path, root->group_pathkeys))
+					current_pathkeys = root->group_pathkeys;
+				else
+				{
+					need_sort_for_grouping = true;
 
-				/*
-				 * Always override create_plan's tlist, so that we don't sort
-				 * useless data from a "physical" tlist.
-				 */
-				need_tlist_eval = true;
+					/*
+					 * Always override create_plan's tlist, so that we don't
+					 * sort useless data from a "physical" tlist.
+					 */
+					need_tlist_eval = true;
+				}
 			}
 
 			/*
@@ -1575,6 +1607,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 									extract_grouping_ops(parse->groupClause),
 												numGroups,
 												result_plan);
+
+				/* Aggregation might break the tuple uniqueness. */
+				result_plan_is_unique = false;
 			}
 			else if (parse->groupClause)
 			{
@@ -1603,7 +1638,11 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 									extract_grouping_ops(parse->groupClause),
 												  dNumGroups,
 												  result_plan);
-				/* The Group node won't change sort ordering */
+				/*
+				 * The Group node won't change sort ordering, however might
+				 * break the uniqueness.
+				 */
+				result_plan_is_unique = false;
 			}
 			else if (root->hasHavingQual)
 			{
@@ -1713,8 +1752,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 														result_plan,
 														window_pathkeys,
 														-1.0);
-					if (!pathkeys_contained_in(window_pathkeys,
-											   current_pathkeys))
+
+					if (sort_needed(current_pathkeys, result_plan_is_unique,
+									window_pathkeys))
 					{
 						/* we do indeed need to sort */
 						result_plan = (Plan *) sort_plan;
@@ -1770,6 +1810,8 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 								   wc->startOffset,
 								   wc->endOffset,
 								   result_plan);
+				/* Aggregation might break the tuple uniqueness. */
+				result_plan_is_unique = false;
 			}
 		}
 	}							/* end of if (setOperations) */
@@ -1855,8 +1897,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 				needed_pathkeys = root->sort_pathkeys;
 			else
 				needed_pathkeys = root->distinct_pathkeys;
-
-			if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
+			
+			if (sort_needed(current_pathkeys, result_plan_is_unique,
+							needed_pathkeys))
 			{
 				if (list_length(root->distinct_pathkeys) >=
 					list_length(root->sort_pathkeys))
@@ -1875,8 +1918,9 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 															   -1.0);
 			}
 
-			result_plan = (Plan *) make_unique(result_plan,
-											   parse->distinctClause);
+			if (!result_plan_is_unique)
+				result_plan = (Plan *) make_unique(result_plan,
+												   parse->distinctClause);
 			result_plan->plan_rows = dNumDistinctRows;
 			/* The Unique node won't change sort ordering */
 		}
@@ -1888,7 +1932,8 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
 	 */
 	if (parse->sortClause)
 	{
-		if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
+		if (sort_needed(current_pathkeys, result_plan_is_unique,
+						root->sort_pathkeys))
 		{
 			result_plan = (Plan *) make_sort_from_pathkeys(root,
 														   result_plan,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ef93c7..8e6d0e7 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -156,6 +156,8 @@ typedef enum
 
 extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
 extern bool pathkeys_contained_in(List *keys1, List *keys2);
+extern bool path_is_ordered(Path *path, List *pathkeys);
+extern bool path_is_uniquely_ordered(Path *path, List *pathkeys);
 extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
 							   Relids required_outer,
 							   CostSelector cost_criterion);
@@ -190,7 +192,8 @@ extern List *make_inner_pathkeys_for_merge(PlannerInfo *root,
 							  List *outer_pathkeys);
 extern List *truncate_useless_pathkeys(PlannerInfo *root,
 						  RelOptInfo *rel,
-						  List *pathkeys);
+						  List *pathkeys,
+						  bool pathkeys_unique);
 extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo *rel);
 
 #endif   /* PATHS_H */
-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Reply via email to