Re: Get more from indices. - Mailing list pgsql-hackers

Hello, this is the revised patch.

> Hmm, that sounds quite resonable in general. But the conflation
> is already found in grouping_planner to some extent.

Although this new patch is not split into unique-index sutff and
others, it removes current_pathkeys from grouping_planner, and
adds pathkeys and is_unique into struct Plan instead. This
eliminates independent and longstanding current_pathkeys variable
and calculus involving it from grouping_planner() so it would be
made clearer and easier to read, I expect.

>  - is_unique and pathkeys is added to the type Path. (umm...)
> 
>  - create function like pathkeys_satisfies(check_pathkeys,
>    pathkeys, isuniq) or path_ordered_by(pathkeys, path) as
>    needed.

This was different from my thought. Finally I added
plan_is_ordered(plan, path) and some of make_<nodename>()
functions take pathkeys and/or uniquely_ordered as parameter and
some of others take them from given leftree plan. Plan nodes
propagate the attributes in autonomous way so explicit
current_pathkeys handling could be thrown away.

>  - Plan will be set ordered and pathkeys derived from source path
>    and its process and grouping_planner consults it to deceide
>    whether to do sort (to hide the currently naked code).
> 
>  - Add check for NULLuble columns :-)
Now IndexOptInfo has new attribute full_ordered and it is set
true if the index does not cover any nullAble columns in
get_relation_info().

And expect file of isolation test is modified to fit the change
in result plan.

Finally, this version became to conflict with the another UNION
patch so I detached from it and rebased to current master.

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..43be0a5 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->full_ordered);        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->full_ordered);        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..954d8a8 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->full_ordered &&
+        (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
joinrelbut 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,14 @@ right_merge_direction(PlannerInfo *root, PathKey *pathkey) * Unlike merge pathkeys, this is an
all-or-nothingaffair: it does us * no good to order by just the first key(s) of the requested ordering. * So the result
isalways either 0 or list_length(root->query_pathkeys).
 
+
+ * pk_full_ordered can be true when pathkeys are strictly unique key (which
+ * should not contain no NULLable column). 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_full_ordered){    if (root->query_pathkeys == NIL)        return 0;
/* no special ordering requested */
 
@@ -1394,23 +1461,35 @@ 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_full_ordered &&
+        pathkeys_contained_in(pathkeys, root->query_pathkeys))
+        return list_length(pathkeys);
+    return 0;                    /* path ordering not useful */}/* * truncate_useless_pathkeys *        Shorten the
givenpathkey list to just the useful pathkeys.
 
+ *
+ * When pk_full_ordered 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 pk_full_ordered){    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, pk_full_ordered);    if (nuseful2 > nuseful)
nuseful= nuseful2;
 
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 5947e5b..7755cbb 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -98,11 +98,13 @@ static SeqScan *make_seqscan(List *qptlist, List *qpqual, Index scanrelid);static IndexScan
*make_indexscan(List*qptlist, List *qpqual, Index scanrelid,               Oid indexid, List *indexqual, List
*indexqualorig,              List *indexorderby, List *indexorderbyorig,
 
+               List *pathkeys, bool uniquely_ordered,               ScanDirection indexscandir);static IndexOnlyScan
*make_indexonlyscan(List*qptlist, List *qpqual,                   Index scanrelid, Oid indexid,                   List
*indexqual,List *indexorderby,                   List *indextlist,
 
+                   List *pathkeys, bool uniquely_ordered,                   ScanDirection indexscandir);static
BitmapIndexScan*make_bitmap_indexscan(Index scanrelid, Oid indexid,                      List *indexqual,
 
@@ -150,10 +152,10 @@ static MergeJoin *make_mergejoin(List *tlist,               bool *mergenullsfirst,
Plan*lefttree, Plan *righttree,               JoinType jointype);
 
-static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
-          AttrNumber *sortColIdx, Oid *sortOperators,
+static Sort *make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+          int numCols,  AttrNumber *sortColIdx, Oid *sortOperators,          Oid *collations, bool *nullsFirst,
-          double limit_tuples);
+          double limit_tuples);static Plan *prepare_sort_from_pathkeys(PlannerInfo *root,
Plan*lefttree, List *pathkeys,                           Relids relids,
 
@@ -750,6 +752,8 @@ create_merge_append_plan(PlannerInfo *root, MergeAppendPath *best_path)    plan->qual = NIL;
plan->lefttree= NULL;    plan->righttree = NULL;
 
+    plan->pathkeys = pathkeys;
+    plan->is_unique = false;    /* Compute sort column info, and adjust MergeAppend's tlist as needed */    (void)
prepare_sort_from_pathkeys(root,plan, pathkeys,
 
@@ -809,8 +813,8 @@ 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))
-            subplan = (Plan *) make_sort(root, subplan, numsortkeys,
+        if (!path_is_ordered(subpath, pathkeys))
+            subplan = (Plan *) make_sort(root, subplan, pathkeys, numsortkeys,
sortColIdx,sortOperators,                                         collations, nullsFirst,
         best_path->limit_tuples);
 
@@ -1147,6 +1151,7 @@ create_indexscan_plan(PlannerInfo *root,    List       *fixed_indexquals;    List
*fixed_indexorderbys;   ListCell   *l;
 
+    bool        uniquely_ordered = false;    /* it should be a base rel... */    Assert(baserelid > 0);
@@ -1254,6 +1259,9 @@ create_indexscan_plan(PlannerInfo *root,            replace_nestloop_params(root, (Node *)
indexorderbys);   }
 
+    uniquely_ordered = 
+        path_is_uniquely_ordered((Path*)best_path, root->query_pathkeys);
+    /* Finally ready to build the plan node */    if (indexonly)        scan_plan = (Scan *)
make_indexonlyscan(tlist,
@@ -1263,6 +1271,8 @@ create_indexscan_plan(PlannerInfo *root,
fixed_indexquals,                                               fixed_indexorderbys,
       best_path->indexinfo->indextlist,
 
+                                                best_path->path.pathkeys,
+                                                uniquely_ordered,
best_path->indexscandir);   else        scan_plan = (Scan *) make_indexscan(tlist,
 
@@ -1273,6 +1283,8 @@ create_indexscan_plan(PlannerInfo *root,
stripped_indexquals,                                           fixed_indexorderbys,
      indexorderbys,
 
+                                            best_path->path.pathkeys,
+                                            uniquely_ordered,
best_path->indexscandir);   copy_path_costsize(&scan_plan->plan, &best_path->path);
 
@@ -3245,6 +3257,8 @@ make_indexscan(List *qptlist,               List *indexqualorig,               List
*indexorderby,              List *indexorderbyorig,
 
+               List *pathkeys,
+               bool  uniquely_ordered,               ScanDirection indexscandir){    IndexScan  *node =
makeNode(IndexScan);
@@ -3255,6 +3269,8 @@ make_indexscan(List *qptlist,    plan->qual = qpqual;    plan->lefttree = NULL;
plan->righttree= NULL;
 
+    plan->pathkeys = pathkeys;
+    plan->is_unique = uniquely_ordered;    node->scan.scanrelid = scanrelid;    node->indexid = indexid;
node->indexqual= indexqual;
 
@@ -3274,6 +3290,8 @@ make_indexonlyscan(List *qptlist,                   List *indexqual,                   List
*indexorderby,                  List *indextlist,
 
+                   List *pathkeys,
+                   bool  uniquely_ordered,                   ScanDirection indexscandir){    IndexOnlyScan *node =
makeNode(IndexOnlyScan);
@@ -3284,6 +3302,8 @@ make_indexonlyscan(List *qptlist,    plan->qual = qpqual;    plan->lefttree = NULL;
plan->righttree= NULL;
 
+    plan->pathkeys = pathkeys;
+    plan->is_unique = uniquely_ordered;    node->scan.scanrelid = scanrelid;    node->indexid = indexid;
node->indexqual= indexqual;
 
@@ -3753,8 +3773,8 @@ make_mergejoin(List *tlist, * limit_tuples is as for cost_sort (in particular, pass -1 if no
limit)*/static Sort *
 
-make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
-          AttrNumber *sortColIdx, Oid *sortOperators,
+make_sort(PlannerInfo *root, Plan *lefttree, List *pathkeys,
+          int numCols,  AttrNumber *sortColIdx, Oid *sortOperators,          Oid *collations, bool *nullsFirst,
 double limit_tuples){
 
@@ -3776,6 +3796,8 @@ make_sort(PlannerInfo *root, Plan *lefttree, int numCols,    plan->qual = NIL;    plan->lefttree
=lefttree;    plan->righttree = NULL;
 
+    plan->pathkeys = pathkeys;
+    plan->is_unique = false;    node->numCols = numCols;    node->sortColIdx = sortColIdx;    node->sortOperators =
sortOperators;
@@ -4125,7 +4147,7 @@ make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
                 &nullsFirst);    /* Now build the Sort node */
 
-    return make_sort(root, lefttree, numsortkeys,
+    return make_sort(root, lefttree, pathkeys, numsortkeys,                     sortColIdx, sortOperators, collations,
                   nullsFirst, limit_tuples);}
 
@@ -4147,6 +4169,7 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)    Oid
*sortOperators;   Oid           *collations;    bool       *nullsFirst;
 
+    List        *pathkeys;    /* Convert list-ish representation to arrays wanted by executor */    numsortkeys =
list_length(sortcls);
@@ -4168,7 +4191,9 @@ make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree)
numsortkeys++;   }
 
-    return make_sort(root, lefttree, numsortkeys,
+    pathkeys = make_pathkeys_for_sortclauses(root, sortcls, sub_tlist);
+
+    return make_sort(root, lefttree, pathkeys, numsortkeys,                     sortColIdx, sortOperators, collations,
                   nullsFirst, -1.0);}
 
@@ -4199,6 +4224,7 @@ make_sort_from_groupcols(PlannerInfo *root,    Oid           *sortOperators;    Oid
*collations;   bool       *nullsFirst;
 
+    List       *pathkeys;    /* Convert list-ish representation to arrays wanted by executor */    numsortkeys =
list_length(groupcls);
@@ -4220,10 +4246,17 @@ make_sort_from_groupcols(PlannerInfo *root,        sortOperators[numsortkeys] = grpcl->sortop;
     collations[numsortkeys] = exprCollation((Node *) tle->expr);        nullsFirst[numsortkeys] = grpcl->nulls_first;
 
+
+        /* This tlist should not be bound with any other orderig clause */
+        Assert(tle->ressortgroupref == 0);
+        tle->ressortgroupref = grpcl->tleSortGroupRef;
+        numsortkeys++;    }
-    return make_sort(root, lefttree, numsortkeys,
+    pathkeys = make_pathkeys_for_sortclauses(root, groupcls, sub_tlist);
+
+    return make_sort(root, lefttree, pathkeys, numsortkeys,                     sortColIdx, sortOperators, collations,
                   nullsFirst, -1.0);}
 
@@ -4338,6 +4371,15 @@ make_agg(PlannerInfo *root, List *tlist, List *qual,    plan->targetlist = tlist;
plan->lefttree= lefttree;    plan->righttree = NULL;
 
+    /*
+     * We can safely assume that the lefttree and therefore the result is
+     * sorted on group pathkeys and unique if given aggstrategy is AGG_SORTED.
+     */
+    if (node->aggstrategy == AGG_SORTED)
+        plan->pathkeys =  root->group_pathkeys;
+    else
+        plan->pathkeys =  NIL;
+    plan->is_unique = true;    return node;}
@@ -4447,6 +4489,12 @@ make_group(PlannerInfo *root,    plan->targetlist = tlist;    plan->lefttree = lefttree;
plan->righttree= NULL;
 
+    /*
+     * We assume that lefttree is ordered on the same pathkeys with that this
+     * group node wants.
+     */
+    plan->pathkeys = lefttree->pathkeys;
+    plan->is_unique = true;    return node;}
@@ -4486,6 +4534,8 @@ make_unique(Plan *lefttree, List *distinctList)    plan->qual = NIL;    plan->lefttree =
lefttree;   plan->righttree = NULL;
 
+    plan->pathkeys = lefttree->pathkeys;
+    plan->is_unique = true;    /*     * convert SortGroupClause list into arrays of attr indexes and equality
@@ -4717,6 +4767,10 @@ make_result(PlannerInfo *root,    plan->qual = NIL;    plan->lefttree = subplan;
plan->righttree= NULL;
 
+
+    /* this plan emits zero or one row when subplan is NULL */
+    if (subplan == NULL) plan->is_unique = true;
+    node->resconstantqual = resconstantqual;    return node;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d8aa35d..c80556e 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -1011,6 +1011,19 @@ inheritance_planner(PlannerInfo *root)
SS_assign_special_param(root));}
+static bool
+plan_is_ordered(Plan *plan, List *pathkeys)
+{
+    if (pathkeys_contained_in(pathkeys, plan->pathkeys))
+        return true;
+
+    if (plan->pathkeys && plan->is_unique &&
+        pathkeys_contained_in(plan->pathkeys, pathkeys))
+        return true;
+
+    return false;
+}
+/*-------------------- * grouping_planner *      Perform planning steps related to grouping, aggregation, etc.
@@ -1039,7 +1052,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)    int64        count_est = 0;
double       limit_tuples = -1.0;    Plan       *result_plan;
 
-    List       *current_pathkeys;    double        dNumGroups = 0;    bool        use_hashed_distinct = false;    bool
      tested_hashed_distinct = false;
 
@@ -1081,15 +1093,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
  &set_sortclauses);        /*
 
-         * Calculate pathkeys representing the sort order (if any) of the set
-         * operation's result.  We have to do this before overwriting the sort
-         * key information...
-         */
-        current_pathkeys = make_pathkeys_for_sortclauses(root,
-                                                         set_sortclauses,
-                                                    result_plan->targetlist);
-
-        /*         * We should not need to call preprocess_targetlist, since we must be         * in a SELECT query
node.   Instead, use the targetlist returned by         * plan_set_operations (since this tells whether it returned
any
@@ -1442,15 +1445,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
         tlist,                                                 &agg_costs,
   best_path);
 
-        if (result_plan != NULL)
-        {
-            /*
-             * optimize_minmax_aggregates generated the full plan, with the
-             * right tlist, and it has no sort order.
-             */
-            current_pathkeys = NIL;
-        }
-        else
+        if (result_plan == NULL)        {            /*             * Normal case --- create a plan according to
query_planner's
@@ -1459,11 +1454,10 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)            bool
need_sort_for_grouping= false;            result_plan = create_plan(root, best_path);
 
-            current_pathkeys = best_path->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))
+                !plan_is_ordered(result_plan, root->group_pathkeys))            {
need_sort_for_grouping= true;
 
@@ -1541,37 +1535,21 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause),                                               numGroups,
                         result_plan);
 
-                /* Hashed aggregation produces randomly-ordered results */
-                current_pathkeys = NIL;            }            else if (parse->hasAggs)            {
/*Plain aggregate plan --- sort if needed */                AggStrategy aggstrategy;
 
-                if (parse->groupClause)
-                {
-                    if (need_sort_for_grouping)
-                    {
-                        result_plan = (Plan *)
-                            make_sort_from_groupcols(root,
-                                                     parse->groupClause,
-                                                     groupColIdx,
-                                                     result_plan);
-                        current_pathkeys = root->group_pathkeys;
-                    }
-                    aggstrategy = AGG_SORTED;
+                aggstrategy = parse->groupClause ? AGG_SORTED : AGG_PLAIN;
-                    /*
-                     * The AGG node will not change the sort ordering of its
-                     * groups, so current_pathkeys describes the result too.
-                     */
-                }
-                else
+                if (aggstrategy == AGG_SORTED && need_sort_for_grouping)                {
-                    aggstrategy = AGG_PLAIN;
-                    /* Result will be only one row anyway; no sort order */
-                    current_pathkeys = NIL;
+                    result_plan = (Plan *)
+                        make_sort_from_groupcols(root,
+                                                 parse->groupClause,
+                                                 groupColIdx,
+                                                 result_plan);                }                result_plan = (Plan *)
make_agg(root,
@@ -1601,7 +1579,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
        parse->groupClause,                                                 groupColIdx,
                result_plan);
 
-                    current_pathkeys = root->group_pathkeys;                }                result_plan = (Plan *)
make_group(root,
@@ -1612,7 +1589,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->groupClause),                                                 dNumGroups,
                              result_plan);
 
-                /* The Group node won't change sort ordering */            }            else if (root->hasHavingQual)
         {
 
@@ -1722,13 +1698,14 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
                 result_plan,                                                        window_pathkeys,
                                    -1.0);
 
-                    if (!pathkeys_contained_in(window_pathkeys,
-                                               current_pathkeys))
-                    {
-                        /* we do indeed need to sort */
+
+                    /*
+                     * we do indeed need to sort if result_plan is not ordered
+                     * on window_pathkeys
+                     */
+                    if (!plan_is_ordered(result_plan, window_pathkeys))                        result_plan = (Plan *)
sort_plan;
-                        current_pathkeys = window_pathkeys;
-                    }
+                    /* In either case, extract the per-column information */
get_column_info_for_window(root,wc, tlist,                                               sort_plan->numCols,
 
@@ -1792,12 +1769,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)        long        numDistinctRows;
     /*
 
-         * If there was grouping or aggregation, use the current number of
-         * rows as the estimated number of DISTINCT rows (ie, assume the
-         * result was already mostly unique).  If not, use the number of
+         * If result_plan emits already distinct'ed rows, use the current
+         * number of rows as the estimated number of DISTINCT rows (ie, assume
+         * the result was already mostly unique).  If not, use the number of         * distinct-groups calculated
previously.        */
 
-        if (parse->groupClause || root->hasHavingQual || parse->hasAggs)
+        if (result_plan->is_unique)            dNumDistinctRows = result_plan->plan_rows;        else
dNumDistinctRows= dNumGroups;
 
@@ -1822,7 +1799,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
result_plan->total_cost,                                      result_plan->startup_cost,
      result_plan->total_cost,
 
-                                       current_pathkeys,
+                                       result_plan->pathkeys,                                       dNumDistinctRows);
      }
 
@@ -1840,8 +1817,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
extract_grouping_ops(parse->distinctClause),                                           numDistinctRows,
                          result_plan);
 
-            /* Hashed aggregation produces randomly-ordered results */
-            current_pathkeys = NIL;        }        else        {
@@ -1864,28 +1839,23 @@ 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 (!plan_is_ordered(result_plan, needed_pathkeys))            {
-                if (list_length(root->distinct_pathkeys) >=
-                    list_length(root->sort_pathkeys))
-                    current_pathkeys = root->distinct_pathkeys;
-                else
-                {
-                    current_pathkeys = root->sort_pathkeys;
-                    /* Assert checks that parser didn't mess up... */
-                    Assert(pathkeys_contained_in(root->distinct_pathkeys,
-                                                 current_pathkeys));
-                }
-
+                /* Assert checks that parser didn't mess up... */
+                Assert(pathkeys_contained_in(root->distinct_pathkeys,
+                                             needed_pathkeys));
+                Assert(pathkeys_contained_in(root->sort_pathkeys,
+                                             needed_pathkeys));                result_plan = (Plan *)
make_sort_from_pathkeys(root,                                                              result_plan,
 
-                                                            current_pathkeys,
+                                                               needed_pathkeys,
                      -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 */        }
 
@@ -1897,13 +1867,12 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)     */    if (parse->sortClause)
{
-        if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
+        if (!plan_is_ordered(result_plan, root->sort_pathkeys))        {            result_plan = (Plan *)
make_sort_from_pathkeys(root,                                                          result_plan,
                                   root->sort_pathkeys,
limit_tuples);
-            current_pathkeys = root->sort_pathkeys;        }    }
@@ -1919,11 +1888,6 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
     root->rowMarks,                                             SS_assign_special_param(root));
 
-        /*
-         * The result can no longer be assumed sorted, since locking might
-         * cause the sort key columns to be replaced with new values.
-         */
-        current_pathkeys = NIL;    }    /*
@@ -1942,7 +1906,7 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)     * Return the actual output
orderingin query_pathkeys for possible use by     * an outer query level.     */
 
-    root->query_pathkeys = current_pathkeys;
+    root->query_pathkeys = result_plan->pathkeys;    return result_plan;}
diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index 954666c..d81f9e3 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -231,6 +231,7 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,             */
if (info->relam == BTREE_AM_OID)            {
 
+                bool has_nullable_keycol = false;                /*                 * If it's a btree index, we can
useits opfamily OIDs                 * directly as the sort ordering opfamily OIDs.
 
@@ -244,10 +245,25 @@ get_relation_info(PlannerInfo *root, Oid relationObjectId, bool inhparent,                for (i
=0; i < ncolumns; i++)                {                    int16        opt = indexRelation->rd_indoption[i];
 
+                    int16        keyattno = index->indkey.values[i];                    info->reverse_sort[i] = (opt &
INDOPTION_DESC)!= 0;                    info->nulls_first[i] = (opt & INDOPTION_NULLS_FIRST) != 0;
 
+
+                    if (keyattno > 0)
+                    {
+                        has_nullable_keycol |= 
+                            !relation->rd_att->attrs[keyattno - 1]->attnotnull;
+                    }
+                    else if (keyattno != ObjectIdAttributeNumber)
+                        has_nullable_keycol = true;                }
+
+                /* Check to see if it is a full-ordered index */
+                if (IndexIsValid(index) &&
+                    index->indisunique && index->indimmediate &&
+                    !has_nullable_keycol)
+                    info->full_ordered = true;            }            else if (indexRelation->rd_am->amcanorder)
     {
 
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 44ea0b7..6f0935c 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -101,7 +101,8 @@ typedef struct Plan     */    double        plan_rows;        /* number of rows plan is expected to
emit*/    int            plan_width;        /* average row width in bytes */
 
-
+    List       *pathkeys;        /* ordered on this pathkeys if any */
+    bool        is_unique;        /* emits unique result */    /*     * Common structural data for all Plan types.
*/
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index a2853fb..e09d75a 100644
--- a/src/include/nodes/relation.h
+++ b/src/include/nodes/relation.h
@@ -515,6 +515,7 @@ typedef struct IndexOptInfo    bool        predOK;            /* true if predicate matches query */
  bool        unique;            /* true if a unique index */    bool        immediate;        /* is uniqueness
enforcedimmediately? */
 
+    bool        full_ordered;    /* is fully-ordered? */    bool        hypothetical;    /* true if index doesn't
reallyexist */    bool        canreturn;        /* can index return IndexTuples? */    bool        amcanorderbyop; /*
doesAM support order by operator result? */
 
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 9ef93c7..9a6c8e0 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -156,6 +156,8 @@ typedef enumextern 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);externList *truncate_useless_pathkeys(PlannerInfo *root,                          RelOptInfo *rel,
 
-                          List *pathkeys);
+                          List *pathkeys,
+                          bool pk_full_ordered);extern bool has_useful_pathkeys(PlannerInfo *root, RelOptInfo
*rel);#endif  /* PATHS_H */
 
diff --git a/src/test/isolation/expected/drop-index-concurrently-1.out
b/src/test/isolation/expected/drop-index-concurrently-1.out
index 75dff56..ab96fa0 100644
--- a/src/test/isolation/expected/drop-index-concurrently-1.out
+++ b/src/test/isolation/expected/drop-index-concurrently-1.out
@@ -19,10 +19,8 @@ Sortstep explains: EXPLAIN (COSTS OFF) EXECUTE getrow_seq;QUERY PLAN     
-Sort           
-  Sort Key: id, data
-  ->  Seq Scan on test_dc
-        Filter: ((data)::text = '34'::text)
+Index Scan using test_dc_pkey on test_dc
+  Filter: ((data)::text = '34'::text)step select2: SELECT * FROM test_dc WHERE data=34 ORDER BY id,data;id
data