diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
new file mode 100644
index ee13136..f5621df
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
*************** static void show_grouping_set_keys(PlanS
*** 89,95 ****
  static void show_group_keys(GroupState *gstate, List *ancestors,
  				ExplainState *es);
  static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! 					 int nkeys, AttrNumber *keycols,
  					 Oid *sortOperators, Oid *collations, bool *nullsFirst,
  					 List *ancestors, ExplainState *es);
  static void show_sortorder_options(StringInfo buf, Node *sortexpr,
--- 89,95 ----
  static void show_group_keys(GroupState *gstate, List *ancestors,
  				ExplainState *es);
  static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! 					 int nkeys, int nPresortedKeys, AttrNumber *keycols,
  					 Oid *sortOperators, Oid *collations, bool *nullsFirst,
  					 List *ancestors, ExplainState *es);
  static void show_sortorder_options(StringInfo buf, Node *sortexpr,
*************** show_sort_keys(SortState *sortstate, Lis
*** 1750,1756 ****
  	Sort	   *plan = (Sort *) sortstate->ss.ps.plan;
  
  	show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! 						 plan->numCols, plan->sortColIdx,
  						 plan->sortOperators, plan->collations,
  						 plan->nullsFirst,
  						 ancestors, es);
--- 1750,1756 ----
  	Sort	   *plan = (Sort *) sortstate->ss.ps.plan;
  
  	show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! 						 plan->numCols, plan->skipCols, plan->sortColIdx,
  						 plan->sortOperators, plan->collations,
  						 plan->nullsFirst,
  						 ancestors, es);
*************** show_merge_append_keys(MergeAppendState 
*** 1766,1772 ****
  	MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
  
  	show_sort_group_keys((PlanState *) mstate, "Sort Key",
! 						 plan->numCols, plan->sortColIdx,
  						 plan->sortOperators, plan->collations,
  						 plan->nullsFirst,
  						 ancestors, es);
--- 1766,1772 ----
  	MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
  
  	show_sort_group_keys((PlanState *) mstate, "Sort Key",
! 						 plan->numCols, 0, plan->sortColIdx,
  						 plan->sortOperators, plan->collations,
  						 plan->nullsFirst,
  						 ancestors, es);
*************** show_agg_keys(AggState *astate, List *an
*** 1790,1796 ****
  			show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
  		else
  			show_sort_group_keys(outerPlanState(astate), "Group Key",
! 								 plan->numCols, plan->grpColIdx,
  								 NULL, NULL, NULL,
  								 ancestors, es);
  
--- 1790,1796 ----
  			show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
  		else
  			show_sort_group_keys(outerPlanState(astate), "Group Key",
! 								 plan->numCols, 0, plan->grpColIdx,
  								 NULL, NULL, NULL,
  								 ancestors, es);
  
*************** show_grouping_set_keys(PlanState *planst
*** 1846,1852 ****
  	if (sortnode)
  	{
  		show_sort_group_keys(planstate, "Sort Key",
! 							 sortnode->numCols, sortnode->sortColIdx,
  							 sortnode->sortOperators, sortnode->collations,
  							 sortnode->nullsFirst,
  							 ancestors, es);
--- 1846,1852 ----
  	if (sortnode)
  	{
  		show_sort_group_keys(planstate, "Sort Key",
! 							 sortnode->numCols, 0, sortnode->sortColIdx,
  							 sortnode->sortOperators, sortnode->collations,
  							 sortnode->nullsFirst,
  							 ancestors, es);
*************** show_group_keys(GroupState *gstate, List
*** 1903,1909 ****
  	/* The key columns refer to the tlist of the child plan */
  	ancestors = lcons(gstate, ancestors);
  	show_sort_group_keys(outerPlanState(gstate), "Group Key",
! 						 plan->numCols, plan->grpColIdx,
  						 NULL, NULL, NULL,
  						 ancestors, es);
  	ancestors = list_delete_first(ancestors);
--- 1903,1909 ----
  	/* The key columns refer to the tlist of the child plan */
  	ancestors = lcons(gstate, ancestors);
  	show_sort_group_keys(outerPlanState(gstate), "Group Key",
! 						 plan->numCols, 0, plan->grpColIdx,
  						 NULL, NULL, NULL,
  						 ancestors, es);
  	ancestors = list_delete_first(ancestors);
*************** show_group_keys(GroupState *gstate, List
*** 1916,1928 ****
   */
  static void
  show_sort_group_keys(PlanState *planstate, const char *qlabel,
! 					 int nkeys, AttrNumber *keycols,
  					 Oid *sortOperators, Oid *collations, bool *nullsFirst,
  					 List *ancestors, ExplainState *es)
  {
  	Plan	   *plan = planstate->plan;
  	List	   *context;
  	List	   *result = NIL;
  	StringInfoData sortkeybuf;
  	bool		useprefix;
  	int			keyno;
--- 1916,1929 ----
   */
  static void
  show_sort_group_keys(PlanState *planstate, const char *qlabel,
! 					 int nkeys, int nPresortedKeys, AttrNumber *keycols,
  					 Oid *sortOperators, Oid *collations, bool *nullsFirst,
  					 List *ancestors, ExplainState *es)
  {
  	Plan	   *plan = planstate->plan;
  	List	   *context;
  	List	   *result = NIL;
+ 	List	   *resultPresorted = NIL;
  	StringInfoData sortkeybuf;
  	bool		useprefix;
  	int			keyno;
*************** show_sort_group_keys(PlanState *planstat
*** 1962,1970 ****
--- 1963,1975 ----
  								   nullsFirst[keyno]);
  		/* Emit one property-list item per sort key */
  		result = lappend(result, pstrdup(sortkeybuf.data));
+ 		if (keyno < nPresortedKeys)
+ 			resultPresorted = lappend(resultPresorted, exprstr);
  	}
  
  	ExplainPropertyList(qlabel, result, es);
+ 	if (nPresortedKeys > 0)
+ 		ExplainPropertyList("Presorted Key", resultPresorted, es);
  }
  
  /*
*************** show_sort_info(SortState *sortstate, Exp
*** 2112,2123 ****
--- 2117,2137 ----
  			appendStringInfoSpaces(es->str, es->indent * 2);
  			appendStringInfo(es->str, "Sort Method: %s  %s: %ldkB\n",
  							 sortMethod, spaceType, spaceUsed);
+ 			if (sortstate->skipKeys)
+ 			{
+ 				appendStringInfoSpaces(es->str, es->indent * 2);
+ 				appendStringInfo(es->str, "Sort groups: %ld\n",
+ 								 sortstate->groupsCount);
+ 			}
  		}
  		else
  		{
  			ExplainPropertyText("Sort Method", sortMethod, es);
  			ExplainPropertyLong("Sort Space Used", spaceUsed, es);
  			ExplainPropertyText("Sort Space Type", spaceType, es);
+ 			if (sortstate->skipKeys)
+ 				ExplainPropertyLong("Sort groups: %ld",
+ 									sortstate->groupsCount, es);
  		}
  	}
  }
diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c
new file mode 100644
index 35864c1..951ea69
*** a/src/backend/executor/execAmi.c
--- b/src/backend/executor/execAmi.c
*************** ExecRestrPos(PlanState *node)
*** 383,389 ****
   * know which plan types support mark/restore.
   */
  bool
! ExecSupportsMarkRestore(Path *pathnode)
  {
  	/*
  	 * For consistency with the routines above, we do not examine the nodeTag
--- 383,389 ----
   * know which plan types support mark/restore.
   */
  bool
! ExecSupportsMarkRestore(Path *pathnode, Plan *node)
  {
  	/*
  	 * For consistency with the routines above, we do not examine the nodeTag
*************** ExecSupportsMarkRestore(Path *pathnode)
*** 395,403 ****
  		case T_IndexScan:
  		case T_IndexOnlyScan:
  		case T_Material:
- 		case T_Sort:
  			return true;
  
  		case T_CustomScan:
  			Assert(IsA(pathnode, CustomPath));
  			if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
--- 395,411 ----
  		case T_IndexScan:
  		case T_IndexOnlyScan:
  		case T_Material:
  			return true;
  
+ 		case T_Sort:
+ 			/* We shouldn't reach here without having plan node */
+ 			Assert(node);
+ 			/* With skipCols sort node holds only last bucket */
+ 			if (node && ((Sort *)node)->skipCols == 0)
+ 				return true;
+ 			else
+ 				return false;
+ 
  		case T_CustomScan:
  			Assert(IsA(pathnode, CustomPath));
  			if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
*************** ExecSupportsBackwardScan(Plan *node)
*** 508,517 ****
  			return false;
  
  		case T_Material:
- 		case T_Sort:
  			/* these don't evaluate tlist */
  			return true;
  
  		case T_LockRows:
  		case T_Limit:
  			/* these don't evaluate tlist */
--- 516,531 ----
  			return false;
  
  		case T_Material:
  			/* these don't evaluate tlist */
  			return true;
  
+ 		case T_Sort:
+ 			/* With skipCols sort node holds only last bucket */
+ 			if (((Sort *)node)->skipCols == 0)
+ 				return true;
+ 			else
+ 				return false;
+ 
  		case T_LockRows:
  		case T_Limit:
  			/* these don't evaluate tlist */
*************** IndexSupportsBackwardScan(Oid indexid)
*** 572,578 ****
   * very low per-tuple cost.
   */
  bool
! ExecMaterializesOutput(NodeTag plantype)
  {
  	switch (plantype)
  	{
--- 586,592 ----
   * very low per-tuple cost.
   */
  bool
! ExecMaterializesOutput(NodeTag plantype, Plan *node)
  {
  	switch (plantype)
  	{
*************** ExecMaterializesOutput(NodeTag plantype)
*** 580,588 ****
  		case T_FunctionScan:
  		case T_CteScan:
  		case T_WorkTableScan:
- 		case T_Sort:
  			return true;
  
  		default:
  			break;
  	}
--- 594,610 ----
  		case T_FunctionScan:
  		case T_CteScan:
  		case T_WorkTableScan:
  			return true;
  
+ 		case T_Sort:
+ 			/* We shouldn't reach here without having plan node */
+ 			Assert(node);
+ 			/* With skipCols sort node holds only last bucket */
+ 			if (node && ((Sort *)node)->skipCols == 0)
+ 				return true;
+ 			else
+ 				return false;
+ 
  		default:
  			break;
  	}
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
new file mode 100644
index 03aa20f..c22610c
*** a/src/backend/executor/nodeAgg.c
--- b/src/backend/executor/nodeAgg.c
*************** initialize_phase(AggState *aggstate, int
*** 556,561 ****
--- 556,562 ----
  												  sortnode->collations,
  												  sortnode->nullsFirst,
  												  work_mem,
+ 												  false,
  												  false);
  	}
  
*************** initialize_aggregate(AggState *aggstate,
*** 634,640 ****
  									 pertrans->sortOperators,
  									 pertrans->sortCollations,
  									 pertrans->sortNullsFirst,
! 									 work_mem, false);
  	}
  
  	/*
--- 635,641 ----
  									 pertrans->sortOperators,
  									 pertrans->sortCollations,
  									 pertrans->sortNullsFirst,
! 									 work_mem, false, false);
  	}
  
  	/*
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
new file mode 100644
index a34dcc5..d9d0f61
*** a/src/backend/executor/nodeSort.c
--- b/src/backend/executor/nodeSort.c
***************
*** 15,25 ****
--- 15,112 ----
  
  #include "postgres.h"
  
+ #include "access/htup_details.h"
  #include "executor/execdebug.h"
  #include "executor/nodeSort.h"
  #include "miscadmin.h"
+ #include "utils/lsyscache.h"
  #include "utils/tuplesort.h"
  
+ /*
+  * Check if first "skipCols" sort values are equal.
+  */
+ static bool
+ cmpSortSkipCols(SortState *node, TupleDesc tupDesc, HeapTuple a, TupleTableSlot *b)
+ {
+ 	int n = ((Sort *)node->ss.ps.plan)->skipCols, i;
+ 
+ 	for (i = 0; i < n; i++)
+ 	{
+ 		Datum datumA, datumB, result;
+ 		bool isnullA, isnullB;
+ 		AttrNumber attno = node->skipKeys[i].attno;
+ 		SkipKeyData *key;
+ 
+ 		datumA = heap_getattr(a, attno, tupDesc, &isnullA);
+ 		datumB = slot_getattr(b, attno, &isnullB);
+ 
+ 		if (isnullA || isnullB)
+ 		{
+ 			if (isnullA == isnullB)
+ 				continue;
+ 			else
+ 				return false;
+ 		}
+ 
+ 		key = &node->skipKeys[i];
+ 
+ 		key->fcinfo.arg[0] = datumA;
+ 		key->fcinfo.arg[1] = datumB;
+ 
+ 		/* just for paranoia's sake, we reset isnull each time */
+ 		key->fcinfo.isnull = false;
+ 
+ 		result = FunctionCallInvoke(&key->fcinfo);
+ 
+ 		/* Check for null result, since caller is clearly not expecting one */
+ 		if (key->fcinfo.isnull)
+ 			elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
+ 
+ 		if (!DatumGetBool(result))
+ 			return false;
+ 	}
+ 	return true;
+ }
+ 
+ /*
+  * Prepare information for skipKeys comparison.
+  */
+ static void
+ prepareSkipCols(Sort *plannode, SortState *node)
+ {
+ 	int skipCols = plannode->skipCols, i;
+ 
+ 	node->skipKeys = (SkipKeyData *)palloc(skipCols * sizeof(SkipKeyData));
+ 
+ 	for (i = 0; i < skipCols; i++)
+ 	{
+ 		Oid equalityOp, equalityFunc;
+ 		SkipKeyData *key;
+ 
+ 		key = &node->skipKeys[i];
+ 		key->attno = plannode->sortColIdx[i];
+ 
+ 		equalityOp = get_equality_op_for_ordering_op(
+ 											plannode->sortOperators[i], NULL);
+ 		if (!OidIsValid(equalityOp))
+ 			elog(ERROR, "missing equality operator for ordering operator %u",
+ 					plannode->sortOperators[i]);
+ 
+ 		equalityFunc = get_opcode(equalityOp);
+ 		if (!OidIsValid(equalityFunc))
+ 			elog(ERROR, "missing function for operator %u", equalityOp);
+ 
+ 		/* Lookup the comparison function */
+ 		fmgr_info_cxt(equalityFunc, &key->flinfo, CurrentMemoryContext);
+ 
+ 		/* We can initialize the callinfo just once and re-use it */
+ 		InitFunctionCallInfoData(key->fcinfo, &key->flinfo, 2,
+ 								plannode->collations[i], NULL, NULL);
+ 		key->fcinfo.argnull[0] = false;
+ 		key->fcinfo.argnull[1] = false;
+ 	}
+ }
+ 
  
  /* ----------------------------------------------------------------
   *		ExecSort
*************** ExecSort(SortState *node)
*** 42,47 ****
--- 129,139 ----
  	ScanDirection dir;
  	Tuplesortstate *tuplesortstate;
  	TupleTableSlot *slot;
+ 	Sort	   *plannode = (Sort *) node->ss.ps.plan;
+ 	PlanState  *outerNode;
+ 	TupleDesc	tupDesc;
+ 	int			skipCols = plannode->skipCols;
+ 	int64		nTuples = 0;
  
  	/*
  	 * get state info from node
*************** ExecSort(SortState *node)
*** 54,132 ****
  	tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
  
  	/*
  	 * If first time through, read all tuples from outer plan and pass them to
  	 * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
  	 */
  
! 	if (!node->sort_Done)
! 	{
! 		Sort	   *plannode = (Sort *) node->ss.ps.plan;
! 		PlanState  *outerNode;
! 		TupleDesc	tupDesc;
  
! 		SO1_printf("ExecSort: %s\n",
! 				   "sorting subplan");
  
! 		/*
! 		 * Want to scan subplan in the forward direction while creating the
! 		 * sorted data.
! 		 */
! 		estate->es_direction = ForwardScanDirection;
  
! 		/*
! 		 * Initialize tuplesort module.
! 		 */
! 		SO1_printf("ExecSort: %s\n",
! 				   "calling tuplesort_begin");
  
! 		outerNode = outerPlanState(node);
! 		tupDesc = ExecGetResultType(outerNode);
  
  		tuplesortstate = tuplesort_begin_heap(tupDesc,
! 											  plannode->numCols,
! 											  plannode->sortColIdx,
! 											  plannode->sortOperators,
! 											  plannode->collations,
! 											  plannode->nullsFirst,
  											  work_mem,
! 											  node->randomAccess);
! 		if (node->bounded)
! 			tuplesort_set_bound(tuplesortstate, node->bound);
  		node->tuplesortstate = (void *) tuplesortstate;
  
! 		/*
! 		 * Scan the subplan and feed all the tuples to tuplesort.
! 		 */
  
! 		for (;;)
! 		{
! 			slot = ExecProcNode(outerNode);
  
  			if (TupIsNull(slot))
  				break;
! 
  			tuplesort_puttupleslot(tuplesortstate, slot);
  		}
  
! 		/*
! 		 * Complete the sort.
! 		 */
! 		tuplesort_performsort(tuplesortstate);
  
! 		/*
! 		 * restore to user specified direction
! 		 */
! 		estate->es_direction = dir;
  
! 		/*
! 		 * finally set the sorted flag to true
! 		 */
! 		node->sort_Done = true;
! 		node->bounded_Done = node->bounded;
! 		node->bound_Done = node->bound;
! 		SO1_printf("ExecSort: %s\n", "sorting done");
  	}
  
  	SO1_printf("ExecSort: %s\n",
  			   "retrieving tuple from tuplesort");
  
--- 146,300 ----
  	tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
  
  	/*
+ 	 * Return next tuple from sorted set if any.
+ 	 */
+ 	if (node->sort_Done)
+ 	{
+ 		slot = node->ss.ps.ps_ResultTupleSlot;
+ 		if (tuplesort_gettupleslot(tuplesortstate,
+ 									  ScanDirectionIsForward(dir),
+ 									  slot, NULL) || node->finished)
+ 			return slot;
+ 	}
+ 
+ 	/*
  	 * If first time through, read all tuples from outer plan and pass them to
  	 * tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
  	 */
  
! 	SO1_printf("ExecSort: %s\n",
! 			   "sorting subplan");
  
! 	/*
! 	 * Want to scan subplan in the forward direction while creating the
! 	 * sorted data.
! 	 */
! 	estate->es_direction = ForwardScanDirection;
  
! 	/*
! 	 * Initialize tuplesort module.
! 	 */
! 	SO1_printf("ExecSort: %s\n",
! 			   "calling tuplesort_begin");
  
! 	outerNode = outerPlanState(node);
! 	tupDesc = ExecGetResultType(outerNode);
  
! 	if (node->tuplesortstate != NULL)
! 	{
! 		tuplesort_reset((Tuplesortstate *) node->tuplesortstate);
! 		node->groupsCount++;
! 	}
! 	else
! 	{
! 		/* Support structures for cmpSortSkipCols - already sorted columns */
! 		if (skipCols)
! 			prepareSkipCols(plannode, node);
  
+ 		/*
+ 		 * Only pass on remaining columns that are unsorted.  Skip abbreviated
+ 		 * keys usage for partial sort.  We unlikely will have huge groups
+ 		 * with partial sort.  Therefore usage of abbreviated keys would be
+ 		 * likely a waste of time.
+ 		 */
  		tuplesortstate = tuplesort_begin_heap(tupDesc,
! 											  plannode->numCols - skipCols,
! 											  &(plannode->sortColIdx[skipCols]),
! 											  &(plannode->sortOperators[skipCols]),
! 											  &(plannode->collations[skipCols]),
! 											  &(plannode->nullsFirst[skipCols]),
  											  work_mem,
! 											  node->randomAccess,
! 											  skipCols > 0 ? true : false);
  		node->tuplesortstate = (void *) tuplesortstate;
+ 		node->groupsCount++;
+ 	}
  
! 	if (node->bounded)
! 		tuplesort_set_bound(tuplesortstate, node->bound - node->bound_Done);
  
! 	/*
! 	 * Put next group of tuples where skipCols sort values are equal to
! 	 * tuplesort.
! 	 */
! 	for (;;)
! 	{
! 		slot = ExecProcNode(outerNode);
  
+ 		if (skipCols == 0)
+ 		{
  			if (TupIsNull(slot))
+ 			{
+ 				node->finished = true;
  				break;
! 			}
  			tuplesort_puttupleslot(tuplesortstate, slot);
+ 			nTuples++;
  		}
+ 		else if (node->prev)
+ 		{
+ 			/* Put previous tuple into tuplesort */
+ 			ExecStoreTuple(node->prev, node->ss.ps.ps_ResultTupleSlot, InvalidBuffer, false);
+ 			tuplesort_puttupleslot(tuplesortstate, node->ss.ps.ps_ResultTupleSlot);
+ 			nTuples++;
  
! 			if (TupIsNull(slot))
! 			{
! 				node->finished = true;
! 				break;
! 			}
! 			else
! 			{
! 				bool cmp;
! 				cmp = cmpSortSkipCols(node, tupDesc, node->prev, slot);
! 				node->prev = ExecCopySlotTuple(slot);
! 				if (!cmp)
! 					break;
! 			}
! 		}
! 		else
! 		{
! 			if (TupIsNull(slot))
! 			{
! 				node->finished = true;
! 				break;
! 			}
! 			else
! 			{
! 				node->prev = ExecCopySlotTuple(slot);
! 			}
! 		}
! 	}
  
! 	/*
! 	 * Complete the sort.
! 	 */
! 	tuplesort_performsort(tuplesortstate);
  
! 	/*
! 	 * restore to user specified direction
! 	 */
! 	estate->es_direction = dir;
! 
! 	/*
! 	 * finally set the sorted flag to true
! 	 */
! 	node->sort_Done = true;
! 	node->bounded_Done = node->bounded;
! 
! 	/*
! 	 * Adjust bound_Done with number of tuples we've actually sorted.
! 	 */
! 	if (node->bounded)
! 	{
! 		if (node->finished)
! 			node->bound_Done = node->bound;
! 		else
! 			node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
  	}
  
+ 	SO1_printf("ExecSort: %s\n", "sorting done");
+ 
  	SO1_printf("ExecSort: %s\n",
  			   "retrieving tuple from tuplesort");
  
*************** ExecInitSort(Sort *node, EState *estate,
*** 157,162 ****
--- 325,339 ----
  			   "initializing sort node");
  
  	/*
+ 	 * skipCols can't be used with either EXEC_FLAG_REWIND, EXEC_FLAG_BACKWARD
+ 	 * or EXEC_FLAG_MARK, because we hold only current bucket in
+ 	 * tuplesortstate.
+ 	 */
+ 	Assert(node->skipCols == 0 || (eflags & (EXEC_FLAG_REWIND |
+ 											 EXEC_FLAG_BACKWARD |
+ 											 EXEC_FLAG_MARK)) == 0);
+ 
+ 	/*
  	 * create state structure
  	 */
  	sortstate = makeNode(SortState);
*************** ExecInitSort(Sort *node, EState *estate,
*** 174,180 ****
--- 351,362 ----
  
  	sortstate->bounded = false;
  	sortstate->sort_Done = false;
+ 	sortstate->finished = false;
  	sortstate->tuplesortstate = NULL;
+ 	sortstate->prev = NULL;
+ 	sortstate->bound_Done = 0;
+ 	sortstate->groupsCount = 0;
+ 	sortstate->skipKeys = NULL;
  
  	/*
  	 * Miscellaneous initialization
*************** ExecReScanSort(SortState *node)
*** 318,323 ****
--- 500,506 ----
  		node->sort_Done = false;
  		tuplesort_end((Tuplesortstate *) node->tuplesortstate);
  		node->tuplesortstate = NULL;
+ 		node->bound_Done = 0;
  
  		/*
  		 * if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
new file mode 100644
index a9e9cc3..86b9c01
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copySort(const Sort *from)
*** 830,835 ****
--- 830,836 ----
  	CopyPlanFields((const Plan *) from, (Plan *) newnode);
  
  	COPY_SCALAR_FIELD(numCols);
+ 	COPY_SCALAR_FIELD(skipCols);
  	COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
  	COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
  	COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
new file mode 100644
index 85acce8..def5520
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outSort(StringInfo str, const Sort *nod
*** 798,803 ****
--- 798,804 ----
  	_outPlanInfo(str, (const Plan *) node);
  
  	WRITE_INT_FIELD(numCols);
+ 	WRITE_INT_FIELD(skipCols);
  
  	appendStringInfoString(str, " :sortColIdx");
  	for (i = 0; i < node->numCols; i++)
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
new file mode 100644
index e6e6f29..aadde14
*** a/src/backend/nodes/readfuncs.c
--- b/src/backend/nodes/readfuncs.c
*************** _readSort(void)
*** 1961,1966 ****
--- 1961,1967 ----
  	ReadCommonPlan(&local_node->plan);
  
  	READ_INT_FIELD(numCols);
+ 	READ_INT_FIELD(skipCols);
  	READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
  	READ_OID_ARRAY(sortOperators, local_node->numCols);
  	READ_OID_ARRAY(collations, local_node->numCols);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
new file mode 100644
index 5fc2f9c..42c9c64
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_recursive_union(Plan *runion, Plan 
*** 1414,1419 ****
--- 1414,1426 ----
   *	  Determines and returns the cost of sorting a relation, including
   *	  the cost of reading the input data.
   *
+  * Sort could be either full sort of relation or partial sort when we already
+  * have data presorted by some of required pathkeys.  In the second case
+  * we estimate number of groups which source data is divided to by presorted
+  * pathkeys.  And then estimate cost of sorting each individual group assuming
+  * data is divided into group uniformly.  Also, if LIMIT is specified then
+  * we have to pull from source and sort only some of total groups.
+  *
   * If the total volume of data to sort is less than sort_mem, we will do
   * an in-memory sort, which requires no I/O and about t*log2(t) tuple
   * comparisons for t tuples.
*************** cost_recursive_union(Plan *runion, Plan 
*** 1440,1446 ****
   * work that has to be done to prepare the inputs to the comparison operators.
   *
   * 'pathkeys' is a list of sort keys
!  * 'input_cost' is the total cost for reading the input data
   * 'tuples' is the number of tuples in the relation
   * 'width' is the average tuple width in bytes
   * 'comparison_cost' is the extra cost per comparison, if any
--- 1447,1454 ----
   * work that has to be done to prepare the inputs to the comparison operators.
   *
   * 'pathkeys' is a list of sort keys
!  * 'input_startup_cost' is the startup cost for reading the input data
!  * 'input_total_cost' is the total cost for reading the input data
   * 'tuples' is the number of tuples in the relation
   * 'width' is the average tuple width in bytes
   * 'comparison_cost' is the extra cost per comparison, if any
*************** cost_recursive_union(Plan *runion, Plan 
*** 1456,1470 ****
   */
  void
  cost_sort(Path *path, PlannerInfo *root,
! 		  List *pathkeys, Cost input_cost, double tuples, int width,
! 		  Cost comparison_cost, int sort_mem,
  		  double limit_tuples)
  {
! 	Cost		startup_cost = input_cost;
! 	Cost		run_cost = 0;
  	double		input_bytes = relation_byte_size(tuples, width);
  	double		output_bytes;
  	double		output_tuples;
  	long		sort_mem_bytes = sort_mem * 1024L;
  
  	if (!enable_sort)
--- 1464,1485 ----
   */
  void
  cost_sort(Path *path, PlannerInfo *root,
! 		  List *pathkeys, int presorted_keys,
! 		  Cost input_startup_cost, Cost input_total_cost,
! 		  double tuples, int width, Cost comparison_cost, int sort_mem,
  		  double limit_tuples)
  {
! 	Cost		startup_cost = input_startup_cost;
! 	Cost		run_cost = 0,
! 				rest_cost,
! 				group_cost,
! 				input_run_cost = input_total_cost - input_startup_cost;
  	double		input_bytes = relation_byte_size(tuples, width);
  	double		output_bytes;
  	double		output_tuples;
+ 	double		num_groups,
+ 				group_input_bytes,
+ 				group_tuples;
  	long		sort_mem_bytes = sort_mem * 1024L;
  
  	if (!enable_sort)
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1494,1506 ****
  		output_bytes = input_bytes;
  	}
  
! 	if (output_bytes > sort_mem_bytes)
  	{
  		/*
  		 * We'll have to use a disk-based sort of all the tuples
  		 */
! 		double		npages = ceil(input_bytes / BLCKSZ);
! 		double		nruns = (input_bytes / sort_mem_bytes) * 0.5;
  		double		mergeorder = tuplesort_merge_order(sort_mem_bytes);
  		double		log_runs;
  		double		npageaccesses;
--- 1509,1558 ----
  		output_bytes = input_bytes;
  	}
  
! 	/*
! 	 * Estimate number of groups which dataset is divided by presorted keys.
! 	 */
! 	if (presorted_keys > 0)
! 	{
! 		List	   *presortedExprs = NIL;
! 		ListCell   *l;
! 		int			i = 0;
! 
! 		/* Extract presorted keys as list of expressions */
! 		foreach(l, pathkeys)
! 		{
! 			PathKey *key = (PathKey *)lfirst(l);
! 			EquivalenceMember *member = (EquivalenceMember *)
! 								lfirst(list_head(key->pk_eclass->ec_members));
! 
! 			presortedExprs = lappend(presortedExprs, member->em_expr);
! 
! 			i++;
! 			if (i >= presorted_keys)
! 				break;
! 		}
! 
! 		/* Estimate number of groups with equal presorted keys */
! 		num_groups = estimate_num_groups(root, presortedExprs, tuples, NULL);
! 	}
! 	else
! 	{
! 		num_groups = 1.0;
! 	}
! 
! 	/*
! 	 * Estimate average cost of sorting of one group where presorted keys are
! 	 * equal.
! 	 */
! 	group_input_bytes = input_bytes / num_groups;
! 	group_tuples = tuples / num_groups;
! 	if (output_bytes > sort_mem_bytes && group_input_bytes > sort_mem_bytes)
  	{
  		/*
  		 * We'll have to use a disk-based sort of all the tuples
  		 */
! 		double		npages = ceil(group_input_bytes / BLCKSZ);
! 		double		nruns = (group_input_bytes / sort_mem_bytes) * 0.5;
  		double		mergeorder = tuplesort_merge_order(sort_mem_bytes);
  		double		log_runs;
  		double		npageaccesses;
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1510,1516 ****
  		 *
  		 * Assume about N log2 N comparisons
  		 */
! 		startup_cost += comparison_cost * tuples * LOG2(tuples);
  
  		/* Disk costs */
  
--- 1562,1568 ----
  		 *
  		 * Assume about N log2 N comparisons
  		 */
! 		group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
  
  		/* Disk costs */
  
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1521,1530 ****
  			log_runs = 1.0;
  		npageaccesses = 2.0 * npages * log_runs;
  		/* Assume 3/4ths of accesses are sequential, 1/4th are not */
! 		startup_cost += npageaccesses *
  			(seq_page_cost * 0.75 + random_page_cost * 0.25);
  	}
! 	else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
  	{
  		/*
  		 * We'll use a bounded heap-sort keeping just K tuples in memory, for
--- 1573,1582 ----
  			log_runs = 1.0;
  		npageaccesses = 2.0 * npages * log_runs;
  		/* Assume 3/4ths of accesses are sequential, 1/4th are not */
! 		group_cost += npageaccesses *
  			(seq_page_cost * 0.75 + random_page_cost * 0.25);
  	}
! 	else if (group_tuples > 2 * output_tuples || group_input_bytes > sort_mem_bytes)
  	{
  		/*
  		 * We'll use a bounded heap-sort keeping just K tuples in memory, for
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1532,1545 ****
  		 * factor is a bit higher than for quicksort.  Tweak it so that the
  		 * cost curve is continuous at the crossover point.
  		 */
! 		startup_cost += comparison_cost * tuples * LOG2(2.0 * output_tuples);
  	}
  	else
  	{
  		/* We'll use plain quicksort on all the input tuples */
! 		startup_cost += comparison_cost * tuples * LOG2(tuples);
  	}
  
  	/*
  	 * Also charge a small amount (arbitrarily set equal to operator cost) per
  	 * extracted tuple.  We don't charge cpu_tuple_cost because a Sort node
--- 1584,1609 ----
  		 * factor is a bit higher than for quicksort.  Tweak it so that the
  		 * cost curve is continuous at the crossover point.
  		 */
! 		group_cost = comparison_cost * group_tuples * LOG2(2.0 * output_tuples);
  	}
  	else
  	{
  		/* We'll use plain quicksort on all the input tuples */
! 		group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
  	}
  
+ 	/* Add per group cost of fetching tuples from input */
+ 	group_cost += input_run_cost / num_groups;
+ 
+ 	/*
+ 	 * We've to sort first group to start output from node. Sorting rest of
+ 	 * groups are required to return all the other tuples.
+ 	 */
+ 	startup_cost += group_cost;
+ 	rest_cost = (num_groups * (output_tuples / tuples) - 1.0) * group_cost;
+ 	if (rest_cost > 0.0)
+ 		run_cost += rest_cost;
+ 
  	/*
  	 * Also charge a small amount (arbitrarily set equal to operator cost) per
  	 * extracted tuple.  We don't charge cpu_tuple_cost because a Sort node
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2284,2289 ****
--- 2348,2355 ----
  		cost_sort(&sort_path,
  				  root,
  				  outersortkeys,
+ 				  pathkeys_common(outer_path->pathkeys, outersortkeys),
+ 				  outer_path->startup_cost,
  				  outer_path->total_cost,
  				  outer_path_rows,
  				  outer_path->pathtarget->width,
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2310,2315 ****
--- 2376,2383 ----
  		cost_sort(&sort_path,
  				  root,
  				  innersortkeys,
+ 				  pathkeys_common(inner_path->pathkeys, innersortkeys),
+ 				  inner_path->startup_cost,
  				  inner_path->total_cost,
  				  inner_path_rows,
  				  inner_path->pathtarget->width,
*************** final_cost_mergejoin(PlannerInfo *root, 
*** 2521,2527 ****
  	 * it off does not entitle us to deliver an invalid plan.
  	 */
  	else if (innersortkeys == NIL &&
! 			 !ExecSupportsMarkRestore(inner_path))
  		path->materialize_inner = true;
  
  	/*
--- 2589,2595 ----
  	 * it off does not entitle us to deliver an invalid plan.
  	 */
  	else if (innersortkeys == NIL &&
! 			 !ExecSupportsMarkRestore(inner_path, NULL))
  		path->materialize_inner = true;
  
  	/*
*************** cost_subplan(PlannerInfo *root, SubPlan 
*** 3044,3050 ****
  		 * every time.
  		 */
  		if (subplan->parParam == NIL &&
! 			ExecMaterializesOutput(nodeTag(plan)))
  			sp_cost.startup += plan->startup_cost;
  		else
  			sp_cost.per_tuple += plan->startup_cost;
--- 3112,3118 ----
  		 * every time.
  		 */
  		if (subplan->parParam == NIL &&
! 			ExecMaterializesOutput(nodeTag(plan), plan))
  			sp_cost.startup += plan->startup_cost;
  		else
  			sp_cost.per_tuple += plan->startup_cost;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
new file mode 100644
index 3b898da..6cdd6ea
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** match_unsorted_outer(PlannerInfo *root,
*** 889,895 ****
  		 * output anyway.
  		 */
  		if (enable_material && inner_cheapest_total != NULL &&
! 			!ExecMaterializesOutput(inner_cheapest_total->pathtype))
  			matpath = (Path *)
  				create_material_path(innerrel, inner_cheapest_total);
  	}
--- 889,895 ----
  		 * output anyway.
  		 */
  		if (enable_material && inner_cheapest_total != NULL &&
! 			!ExecMaterializesOutput(inner_cheapest_total->pathtype, NULL))
  			matpath = (Path *)
  				create_material_path(innerrel, inner_cheapest_total);
  	}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
new file mode 100644
index eed39b9..4ae1309
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 26,31 ****
--- 26,32 ----
  #include "optimizer/paths.h"
  #include "optimizer/tlist.h"
  #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
  
  
  static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
*************** compare_pathkeys(List *keys1, List *keys
*** 309,314 ****
--- 310,341 ----
  }
  
  /*
+  * pathkeys_common
+  *    Returns length of longest common prefix of keys1 and keys2.
+  */
+ int
+ pathkeys_common(List *keys1, List *keys2)
+ {
+ 	int n;
+ 	ListCell   *key1,
+ 			   *key2;
+ 	n = 0;
+ 
+ 	forboth(key1, keys1, key2, keys2)
+ 	{
+ 		PathKey    *pathkey1 = (PathKey *) lfirst(key1);
+ 		PathKey    *pathkey2 = (PathKey *) lfirst(key2);
+ 
+ 		if (pathkey1 != pathkey2)
+ 			return n;
+ 		n++;
+ 	}
+ 
+ 	return n;
+ }
+ 
+ 
+ /*
   * pathkeys_contained_in
   *	  Common special case of compare_pathkeys: we just want to know
   *	  if keys2 are at least as well sorted as keys1.
*************** get_cheapest_path_for_pathkeys(List *pat
*** 368,375 ****
  /*
   * 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.
!  *	  Return NULL if no such path.
   *
   * See compare_fractional_path_costs() for the interpretation of the fraction
   * parameter.
--- 395,406 ----
  /*
   * get_cheapest_fractional_path_for_pathkeys
   *	  Find the cheapest path (for retrieving a specified fraction of all
!  *	  the tuples) that satisfies given parameterization and at least partially
!  *	  satisfies the given pathkeys.  Return NULL if no path found.
!  *	  If pathkeys are satisfied partially then we would have to do partial
!  *	  sort in order to satisfy pathkeys completely.  Since partial sort
!  *	  consumes data by presorted groups, we would have to consume more data
!  *	  than in the case of fully presorted path.
   *
   * See compare_fractional_path_costs() for the interpretation of the fraction
   * parameter.
*************** get_cheapest_path_for_pathkeys(List *pat
*** 378,409 ****
   * 'pathkeys' represents a required ordering (in canonical form!)
   * 'required_outer' denotes allowable outer relations for parameterized paths
   * 'fraction' is the fraction of the total tuples expected to be retrieved
   */
  Path *
  get_cheapest_fractional_path_for_pathkeys(List *paths,
  										  List *pathkeys,
  										  Relids required_outer,
! 										  double fraction)
  {
  	Path	   *matched_path = NULL;
  	ListCell   *l;
  
  	foreach(l, paths)
  	{
  		Path	   *path = (Path *) lfirst(l);
  
  		/*
! 		 * Since cost comparison is a lot cheaper than pathkey comparison, do
! 		 * that first.  (XXX is that still true?)
  		 */
! 		if (matched_path != NULL &&
! 			compare_fractional_path_costs(matched_path, path, fraction) <= 0)
! 			continue;
  
! 		if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
  			bms_is_subset(PATH_REQ_OUTER(path), required_outer))
  			matched_path = path;
  	}
  	return matched_path;
  }
  
--- 409,480 ----
   * 'pathkeys' represents a required ordering (in canonical form!)
   * 'required_outer' denotes allowable outer relations for parameterized paths
   * 'fraction' is the fraction of the total tuples expected to be retrieved
+  * 'num_groups' array of group numbers which pathkeys divide data to. Should
+  *	  be estimated using estimate_partialsort_groups().
   */
  Path *
  get_cheapest_fractional_path_for_pathkeys(List *paths,
  										  List *pathkeys,
  										  Relids required_outer,
! 										  double fraction,
! 										  double *num_groups)
  {
  	Path	   *matched_path = NULL;
+ 	int			matched_n_common_pathkeys = 0,
+ 				costs_cmp, n_common_pathkeys,
+ 				n_pathkeys = list_length(pathkeys);
  	ListCell   *l;
+ 	double		matched_fraction;
  
  	foreach(l, paths)
  	{
  		Path	   *path = (Path *) lfirst(l);
+ 		double		current_fraction;
+ 
+ 		n_common_pathkeys = pathkeys_common(pathkeys, path->pathkeys);
+ 
+ 		if (n_pathkeys != 0 && n_common_pathkeys == 0)
+ 			continue;
  
  		/*
! 		 * Partial sort consumes data not per tuple but per presorted group.
! 		 * Increase fraction of tuples we have to read from source path by
! 		 * one presorted group.
  		 */
! 		current_fraction = fraction;
! 		if (n_common_pathkeys < n_pathkeys)
! 		{
! 			current_fraction += 1.0 / num_groups[n_common_pathkeys - 1];
! 			current_fraction = Min(current_fraction, 1.0);
! 		}
  
! 		/*
! 		 * Do cost comparison assuming paths could have different number
! 		 * of required pathkeys and therefore different fraction of tuples
! 		 * to fetch.
! 		 */
! 		if (matched_path != NULL)
! 		{
! 			costs_cmp = compare_bifractional_path_costs(matched_path, path,
! 					matched_fraction, current_fraction);
! 		}
! 		else
! 		{
! 			costs_cmp = 1;
! 		}
! 
! 		/*
! 		 * Cheaper path with matching outer becomes a new leader.
! 		 */
! 		if (costs_cmp > 0 &&
  			bms_is_subset(PATH_REQ_OUTER(path), required_outer))
+ 		{
  			matched_path = path;
+ 			matched_n_common_pathkeys = n_common_pathkeys;
+ 			matched_fraction = current_fraction;
+ 		}
  	}
+ 
  	return matched_path;
  }
  
*************** right_merge_direction(PlannerInfo *root,
*** 1447,1455 ****
   *		Count the number of pathkeys that are useful for meeting the
   *		query's requested output ordering.
   *
!  * 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).
   */
  static int
  pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
--- 1518,1525 ----
   *		Count the number of pathkeys that are useful for meeting the
   *		query's requested output ordering.
   *
!  * Returns number of pathkeys that maches given argument. Others can be
!  * satisfied by partial sort.
   */
  static int
  pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
*************** pathkeys_useful_for_ordering(PlannerInfo
*** 1460,1472 ****
  	if (pathkeys == NIL)
  		return 0;				/* unordered path */
  
! 	if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
! 	{
! 		/* It's useful ... or at least the first N keys are */
! 		return list_length(root->query_pathkeys);
! 	}
! 
! 	return 0;					/* path ordering not useful */
  }
  
  /*
--- 1530,1541 ----
  	if (pathkeys == NIL)
  		return 0;				/* unordered path */
  
! 	/*
! 	 * Return the number of path keys in common, or 0 if there are none. Any
! 	 * first common pathkeys could be useful for ordering because we can use
! 	 * partial sort.
! 	 */
! 	return pathkeys_common(root->query_pathkeys, pathkeys);
  }
  
  /*
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
new file mode 100644
index 198b06b..3da150d
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** static MergeJoin *make_mergejoin(List *t
*** 163,168 ****
--- 163,169 ----
  			   Plan *lefttree, Plan *righttree,
  			   JoinType jointype);
  static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
+ 		  List *pathkeys, int skipCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst,
  		  double limit_tuples);
*************** create_merge_append_plan(PlannerInfo *ro
*** 815,820 ****
--- 816,822 ----
  		Oid		   *sortOperators;
  		Oid		   *collations;
  		bool	   *nullsFirst;
+ 		int			n_common_pathkeys;
  
  		/* Build the child plan */
  		subplan = create_plan_recurse(root, subpath);
*************** create_merge_append_plan(PlannerInfo *ro
*** 848,855 ****
  					  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,
  										 sortColIdx, sortOperators,
  										 collations, nullsFirst,
  										 best_path->limit_tuples);
--- 850,859 ----
  					  numsortkeys * sizeof(bool)) == 0);
  
  		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
! 		n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys);
! 		if (n_common_pathkeys < list_length(pathkeys))
  			subplan = (Plan *) make_sort(root, subplan, numsortkeys,
+ 										 pathkeys, n_common_pathkeys,
  										 sortColIdx, sortOperators,
  										 collations, nullsFirst,
  										 best_path->limit_tuples);
*************** create_mergejoin_plan(PlannerInfo *root,
*** 2469,2477 ****
  		disuse_physical_tlist(root, outer_plan, best_path->jpath.outerjoinpath);
  		outer_plan = (Plan *)
  			make_sort_from_pathkeys(root,
! 									outer_plan,
! 									best_path->outersortkeys,
! 									-1.0);
  		outerpathkeys = best_path->outersortkeys;
  	}
  	else
--- 2473,2483 ----
  		disuse_physical_tlist(root, outer_plan, best_path->jpath.outerjoinpath);
  		outer_plan = (Plan *)
  			make_sort_from_pathkeys(root,
! 								outer_plan,
! 								best_path->outersortkeys,
! 								-1.0,
! 								pathkeys_common(best_path->outersortkeys,
! 									best_path->jpath.outerjoinpath->pathkeys));
  		outerpathkeys = best_path->outersortkeys;
  	}
  	else
*************** create_mergejoin_plan(PlannerInfo *root,
*** 2482,2490 ****
  		disuse_physical_tlist(root, inner_plan, best_path->jpath.innerjoinpath);
  		inner_plan = (Plan *)
  			make_sort_from_pathkeys(root,
! 									inner_plan,
! 									best_path->innersortkeys,
! 									-1.0);
  		innerpathkeys = best_path->innersortkeys;
  	}
  	else
--- 2488,2498 ----
  		disuse_physical_tlist(root, inner_plan, best_path->jpath.innerjoinpath);
  		inner_plan = (Plan *)
  			make_sort_from_pathkeys(root,
! 								inner_plan,
! 								best_path->innersortkeys,
! 								-1.0,
! 								pathkeys_common(best_path->innersortkeys,
! 									best_path->jpath.innerjoinpath->pathkeys));
  		innerpathkeys = best_path->innersortkeys;
  	}
  	else
*************** make_mergejoin(List *tlist,
*** 4059,4064 ****
--- 4067,4073 ----
   */
  static Sort *
  make_sort(PlannerInfo *root, Plan *lefttree, int numCols,
+           List *pathkeys, int skipCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst,
  		  double limit_tuples)
*************** make_sort(PlannerInfo *root, Plan *leftt
*** 4068,4074 ****
  	Path		sort_path;		/* dummy for result of cost_sort */
  
  	copy_plan_costsize(plan, lefttree); /* only care about copying size */
! 	cost_sort(&sort_path, root, NIL,
  			  lefttree->total_cost,
  			  lefttree->plan_rows,
  			  lefttree->plan_width,
--- 4077,4084 ----
  	Path		sort_path;		/* dummy for result of cost_sort */
  
  	copy_plan_costsize(plan, lefttree); /* only care about copying size */
! 	cost_sort(&sort_path, root, pathkeys, skipCols,
! 			  lefttree->startup_cost,
  			  lefttree->total_cost,
  			  lefttree->plan_rows,
  			  lefttree->plan_width,
*************** make_sort(PlannerInfo *root, Plan *leftt
*** 4082,4087 ****
--- 4092,4098 ----
  	plan->lefttree = lefttree;
  	plan->righttree = NULL;
  	node->numCols = numCols;
+ 	node->skipCols = skipCols;
  	node->sortColIdx = sortColIdx;
  	node->sortOperators = sortOperators;
  	node->collations = collations;
*************** find_ec_member_for_tle(EquivalenceClass 
*** 4410,4416 ****
   */
  Sort *
  make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
! 						double limit_tuples)
  {
  	int			numsortkeys;
  	AttrNumber *sortColIdx;
--- 4421,4427 ----
   */
  Sort *
  make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
! 						double limit_tuples, int skipCols)
  {
  	int			numsortkeys;
  	AttrNumber *sortColIdx;
*************** make_sort_from_pathkeys(PlannerInfo *roo
*** 4430,4436 ****
  										  &nullsFirst);
  
  	/* Now build the Sort node */
! 	return make_sort(root, lefttree, numsortkeys,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, limit_tuples);
  }
--- 4441,4447 ----
  										  &nullsFirst);
  
  	/* Now build the Sort node */
! 	return make_sort(root, lefttree, numsortkeys, pathkeys, skipCols,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, limit_tuples);
  }
*************** make_sort_from_sortclauses(PlannerInfo *
*** 4473,4479 ****
  		numsortkeys++;
  	}
  
! 	return make_sort(root, lefttree, numsortkeys,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, -1.0);
  }
--- 4484,4490 ----
  		numsortkeys++;
  	}
  
! 	return make_sort(root, lefttree, numsortkeys, NIL, 0,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, -1.0);
  }
*************** Sort *
*** 4495,4501 ****
  make_sort_from_groupcols(PlannerInfo *root,
  						 List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree)
  {
  	List	   *sub_tlist = lefttree->targetlist;
  	ListCell   *l;
--- 4506,4513 ----
  make_sort_from_groupcols(PlannerInfo *root,
  						 List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree,
! 						 List *pathkeys, int skipCols)
  {
  	List	   *sub_tlist = lefttree->targetlist;
  	ListCell   *l;
*************** make_sort_from_groupcols(PlannerInfo *ro
*** 4528,4534 ****
  		numsortkeys++;
  	}
  
! 	return make_sort(root, lefttree, numsortkeys,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, -1.0);
  }
--- 4540,4546 ----
  		numsortkeys++;
  	}
  
! 	return make_sort(root, lefttree, numsortkeys, pathkeys, skipCols,
  					 sortColIdx, sortOperators, collations,
  					 nullsFirst, -1.0);
  }
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
new file mode 100644
index 373e6cc..b68443f
*** a/src/backend/optimizer/plan/planagg.c
--- b/src/backend/optimizer/plan/planagg.c
***************
*** 43,48 ****
--- 43,49 ----
  #include "parser/parsetree.h"
  #include "parser/parse_clause.h"
  #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
  #include "utils/syscache.h"
  
  
*************** build_minmax_path(PlannerInfo *root, Min
*** 409,414 ****
--- 410,416 ----
  	Path	   *sorted_path;
  	Cost		path_cost;
  	double		path_fraction;
+ 	double	   *psort_num_groups;
  
  	/*----------
  	 * Generate modified query of the form
*************** build_minmax_path(PlannerInfo *root, Min
*** 500,510 ****
  	else
  		path_fraction = 1.0;
  
  	sorted_path =
  		get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
  												  subroot->query_pathkeys,
  												  NULL,
! 												  path_fraction);
  	if (!sorted_path)
  		return false;
  
--- 502,516 ----
  	else
  		path_fraction = 1.0;
  
+ 	psort_num_groups = estimate_pathkeys_groups(subroot->query_pathkeys,
+ 												subroot,
+ 												final_rel->rows);
  	sorted_path =
  		get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
  												  subroot->query_pathkeys,
  												  NULL,
! 												  path_fraction,
! 												  psort_num_groups);
  	if (!sorted_path)
  		return false;
  
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
new file mode 100644
index 65b99e2..23d0aa4
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** static Plan *build_grouping_chain(Planne
*** 141,147 ****
  					 AttrNumber *groupColIdx,
  					 AggClauseCosts *agg_costs,
  					 long numGroups,
! 					 Plan *result_plan);
  
  /*****************************************************************************
   *
--- 141,149 ----
  					 AttrNumber *groupColIdx,
  					 AggClauseCosts *agg_costs,
  					 long numGroups,
! 					 Plan *result_plan,
! 					 List *path_keys,
! 					 int n_common_pathkeys);
  
  /*****************************************************************************
   *
*************** grouping_planner(PlannerInfo *root, doub
*** 1481,1486 ****
--- 1483,1489 ----
  		Path	   *cheapest_path;
  		Path	   *sorted_path;
  		Path	   *best_path;
+ 		double	   *psort_num_groups;
  
  		MemSet(&agg_costs, 0, sizeof(AggClauseCosts));
  
*************** grouping_planner(PlannerInfo *root, doub
*** 1815,1825 ****
  		 */
  		cheapest_path = final_rel->cheapest_total_path;
  
  		sorted_path =
  			get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
  													  root->query_pathkeys,
  													  NULL,
! 													  tuple_fraction);
  
  		/* Don't consider same path in both guises; just wastes effort */
  		if (sorted_path == cheapest_path)
--- 1818,1832 ----
  		 */
  		cheapest_path = final_rel->cheapest_total_path;
  
+ 		psort_num_groups = estimate_pathkeys_groups(root->query_pathkeys,
+ 													root,
+ 													path_rows);
  		sorted_path =
  			get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
  													  root->query_pathkeys,
  													  NULL,
! 													  tuple_fraction,
! 													  psort_num_groups);
  
  		/* Don't consider same path in both guises; just wastes effort */
  		if (sorted_path == cheapest_path)
*************** grouping_planner(PlannerInfo *root, doub
*** 1834,1844 ****
  		 */
  		if (sorted_path)
  		{
! 			Path		sort_path;		/* dummy for result of cost_sort */
  
  			if (root->query_pathkeys == NIL ||
! 				pathkeys_contained_in(root->query_pathkeys,
! 									  cheapest_path->pathkeys))
  			{
  				/* No sort needed for cheapest path */
  				sort_path.startup_cost = cheapest_path->startup_cost;
--- 1841,1860 ----
  		 */
  		if (sorted_path)
  		{
! 			/* dummy for result of cost_sort */
! 			Path		sort_path;
! 			/*
! 			 * dummy for original cost of fully presorted path or
! 			 * result of cost_sort in case of partial sort
! 			 */
! 			Path		presorted_path;	
! 			int			n_common_pathkeys;
! 
! 			n_common_pathkeys = pathkeys_common(root->query_pathkeys,
! 												cheapest_path->pathkeys);
  
  			if (root->query_pathkeys == NIL ||
! 					n_common_pathkeys == list_length(root->query_pathkeys))
  			{
  				/* No sort needed for cheapest path */
  				sort_path.startup_cost = cheapest_path->startup_cost;
*************** grouping_planner(PlannerInfo *root, doub
*** 1848,1859 ****
  			{
  				/* Figure cost for sorting */
  				cost_sort(&sort_path, root, root->query_pathkeys,
  						  cheapest_path->total_cost,
  						  path_rows, cheapest_path->pathtarget->width,
  						  0.0, work_mem, root->limit_tuples);
  			}
  
! 			if (compare_fractional_path_costs(sorted_path, &sort_path,
  											  tuple_fraction) > 0)
  			{
  				/* Presorted path is a loser */
--- 1864,1904 ----
  			{
  				/* Figure cost for sorting */
  				cost_sort(&sort_path, root, root->query_pathkeys,
+ 						  n_common_pathkeys,
+ 						  cheapest_path->startup_cost,
  						  cheapest_path->total_cost,
  						  path_rows, cheapest_path->pathtarget->width,
  						  0.0, work_mem, root->limit_tuples);
  			}
  
! 			n_common_pathkeys = pathkeys_common(root->query_pathkeys,
! 												sorted_path->pathkeys);
! 
! 			if (root->query_pathkeys == NIL ||
! 					n_common_pathkeys == list_length(root->query_pathkeys))
! 			{
! 				/*
! 				 * Presorted path fully match query pathkeys.
! 				 * No partial sort is needed.
! 				 */
! 				presorted_path.startup_cost = sorted_path->startup_cost;
! 				presorted_path.total_cost = sorted_path->total_cost;
! 			}
! 			else
! 			{
! 				/*
! 				 * Figure cost for sorting when presorted path only partially
! 				 * match query pathkeys.
! 				 */
! 				cost_sort(&presorted_path, root, root->query_pathkeys,
! 						  n_common_pathkeys,
! 						  sorted_path->startup_cost,
! 						  sorted_path->total_cost,
! 						  path_rows, sorted_path->pathtarget->width,
! 						  0.0, work_mem, root->limit_tuples);
! 			}
! 
! 			if (compare_fractional_path_costs(&presorted_path, &sort_path,
  											  tuple_fraction) > 0)
  			{
  				/* Presorted path is a loser */
*************** grouping_planner(PlannerInfo *root, doub
*** 1950,1962 ****
  			AttrNumber *groupColIdx = NULL;
  			bool		need_tlist_eval = true;
  			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))
  				need_sort_for_grouping = true;
  
  			/*
--- 1995,2010 ----
  			AttrNumber *groupColIdx = NULL;
  			bool		need_tlist_eval = true;
  			bool		need_sort_for_grouping = false;
+ 			int			n_common_pathkeys_grouping;
  
  			result_plan = create_plan(root, best_path);
  			current_pathkeys = best_path->pathkeys;
  
  			/* Detect if we'll need an explicit sort for grouping */
+ 			n_common_pathkeys_grouping = pathkeys_common(root->group_pathkeys,
+ 														 current_pathkeys);
  			if (parse->groupClause && !use_hashed_grouping &&
! 				n_common_pathkeys_grouping < list_length(root->group_pathkeys))
  				need_sort_for_grouping = true;
  
  			/*
*************** grouping_planner(PlannerInfo *root, doub
*** 2090,2096 ****
  												   groupColIdx,
  												   &agg_costs,
  												   numGroups,
! 												   result_plan);
  			}
  			else if (parse->groupClause)
  			{
--- 2138,2146 ----
  												   groupColIdx,
  												   &agg_costs,
  												   numGroups,
! 												   result_plan,
! 												   root->group_pathkeys,
! 												   n_common_pathkeys_grouping);
  			}
  			else if (parse->groupClause)
  			{
*************** grouping_planner(PlannerInfo *root, doub
*** 2107,2113 ****
  						make_sort_from_groupcols(root,
  												 parse->groupClause,
  												 groupColIdx,
! 												 result_plan);
  					current_pathkeys = root->group_pathkeys;
  				}
  
--- 2157,2165 ----
  						make_sort_from_groupcols(root,
  												 parse->groupClause,
  												 groupColIdx,
! 												 result_plan,
! 												 root->group_pathkeys,
! 												 n_common_pathkeys_grouping);
  					current_pathkeys = root->group_pathkeys;
  				}
  
*************** grouping_planner(PlannerInfo *root, doub
*** 2245,2257 ****
  				if (window_pathkeys)
  				{
  					Sort	   *sort_plan;
  
  					sort_plan = make_sort_from_pathkeys(root,
  														result_plan,
  														window_pathkeys,
! 														-1.0);
! 					if (!pathkeys_contained_in(window_pathkeys,
! 											   current_pathkeys))
  					{
  						/* we do indeed need to sort */
  						result_plan = (Plan *) sort_plan;
--- 2297,2313 ----
  				if (window_pathkeys)
  				{
  					Sort	   *sort_plan;
+ 					int			n_common_pathkeys;
+ 
+ 					n_common_pathkeys = pathkeys_common(window_pathkeys,
+ 													    current_pathkeys);
  
  					sort_plan = make_sort_from_pathkeys(root,
  														result_plan,
  														window_pathkeys,
! 														-1.0,
! 														n_common_pathkeys);
! 					if (n_common_pathkeys < list_length(window_pathkeys))
  					{
  						/* we do indeed need to sort */
  						result_plan = (Plan *) sort_plan;
*************** grouping_planner(PlannerInfo *root, doub
*** 2401,2419 ****
  			{
  				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));
  				}
  
  				result_plan = (Plan *) make_sort_from_pathkeys(root,
  															   result_plan,
! 															current_pathkeys,
! 															   -1.0);
  			}
  
  			result_plan = (Plan *) make_unique(result_plan,
--- 2457,2477 ----
  			{
  				if (list_length(root->distinct_pathkeys) >=
  					list_length(root->sort_pathkeys))
! 					needed_pathkeys = root->distinct_pathkeys;
  				else
  				{
! 					needed_pathkeys = root->sort_pathkeys;
  					/* Assert checks that parser didn't mess up... */
  					Assert(pathkeys_contained_in(root->distinct_pathkeys,
! 												 needed_pathkeys));
  				}
  
  				result_plan = (Plan *) make_sort_from_pathkeys(root,
  															   result_plan,
! 															   needed_pathkeys,
! 															   -1.0,
! 							pathkeys_common(needed_pathkeys, current_pathkeys));
! 				current_pathkeys = needed_pathkeys;
  			}
  
  			result_plan = (Plan *) make_unique(result_plan,
*************** grouping_planner(PlannerInfo *root, doub
*** 2429,2440 ****
  	 */
  	if (parse->sortClause)
  	{
! 		if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
  		{
  			result_plan = (Plan *) make_sort_from_pathkeys(root,
  														   result_plan,
  														 root->sort_pathkeys,
! 														   limit_tuples);
  			current_pathkeys = root->sort_pathkeys;
  		}
  	}
--- 2487,2501 ----
  	 */
  	if (parse->sortClause)
  	{
! 		int common = pathkeys_common(root->sort_pathkeys, current_pathkeys);
! 		
! 		if (common < list_length(root->sort_pathkeys))
  		{
  			result_plan = (Plan *) make_sort_from_pathkeys(root,
  														   result_plan,
  														 root->sort_pathkeys,
! 														   limit_tuples,
! 														   common);
  			current_pathkeys = root->sort_pathkeys;
  		}
  	}
*************** build_grouping_chain(PlannerInfo *root,
*** 2536,2542 ****
  					 AttrNumber *groupColIdx,
  					 AggClauseCosts *agg_costs,
  					 long numGroups,
! 					 Plan *result_plan)
  {
  	AttrNumber *top_grpColIdx = groupColIdx;
  	List	   *chain = NIL;
--- 2597,2605 ----
  					 AttrNumber *groupColIdx,
  					 AggClauseCosts *agg_costs,
  					 long numGroups,
! 					 Plan *result_plan,
! 					 List *path_keys,
! 					 int n_common_pathkeys)
  {
  	AttrNumber *top_grpColIdx = groupColIdx;
  	List	   *chain = NIL;
*************** build_grouping_chain(PlannerInfo *root,
*** 2557,2563 ****
  			make_sort_from_groupcols(root,
  									 llast(rollup_groupclauses),
  									 top_grpColIdx,
! 									 result_plan);
  	}
  
  	/*
--- 2620,2628 ----
  			make_sort_from_groupcols(root,
  									 llast(rollup_groupclauses),
  									 top_grpColIdx,
! 									 result_plan,
! 									 path_keys,
! 									 n_common_pathkeys);
  	}
  
  	/*
*************** build_grouping_chain(PlannerInfo *root,
*** 2588,2594 ****
  				make_sort_from_groupcols(root,
  										 groupClause,
  										 new_grpColIdx,
! 										 result_plan);
  
  			/*
  			 * sort_plan includes the cost of result_plan, which is not what
--- 2653,2661 ----
  				make_sort_from_groupcols(root,
  										 groupClause,
  										 new_grpColIdx,
! 										 result_plan,
! 										 NIL,
! 										 0);
  
  			/*
  			 * sort_plan includes the cost of result_plan, which is not what
*************** choose_hashed_grouping(PlannerInfo *root
*** 3859,3864 ****
--- 3926,3932 ----
  	List	   *current_pathkeys;
  	Path		hashed_p;
  	Path		sorted_p;
+ 	int			n_common_pathkeys;
  	int			sorted_p_width;
  
  	/*
*************** choose_hashed_grouping(PlannerInfo *root
*** 3942,3948 ****
  			 path_rows);
  	/* Result of hashed agg is always unsorted */
  	if (target_pathkeys)
! 		cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost,
  				  dNumGroups, cheapest_path->pathtarget->width,
  				  0.0, work_mem, limit_tuples);
  
--- 4010,4017 ----
  			 path_rows);
  	/* Result of hashed agg is always unsorted */
  	if (target_pathkeys)
! 		cost_sort(&hashed_p, root, target_pathkeys, 0,
! 				  hashed_p.startup_cost, hashed_p.total_cost,
  				  dNumGroups, cheapest_path->pathtarget->width,
  				  0.0, work_mem, limit_tuples);
  
*************** choose_hashed_grouping(PlannerInfo *root
*** 3960,3968 ****
  		sorted_p_width = cheapest_path->pathtarget->width;
  		current_pathkeys = cheapest_path->pathkeys;
  	}
! 	if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys))
  	{
! 		cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost,
  				  path_rows, sorted_p_width,
  				  0.0, work_mem, -1.0);
  		current_pathkeys = root->group_pathkeys;
--- 4029,4040 ----
  		sorted_p_width = cheapest_path->pathtarget->width;
  		current_pathkeys = cheapest_path->pathkeys;
  	}
! 
! 	n_common_pathkeys = pathkeys_common(root->group_pathkeys, current_pathkeys);
! 	if (n_common_pathkeys < list_length(root->group_pathkeys))
  	{
! 		cost_sort(&sorted_p, root, root->group_pathkeys,
! 				  n_common_pathkeys, sorted_p.startup_cost, sorted_p.total_cost,
  				  path_rows, sorted_p_width,
  				  0.0, work_mem, -1.0);
  		current_pathkeys = root->group_pathkeys;
*************** choose_hashed_grouping(PlannerInfo *root
*** 3977,3986 ****
  		cost_group(&sorted_p, root, numGroupCols, dNumGroups,
  				   sorted_p.startup_cost, sorted_p.total_cost,
  				   path_rows);
  	/* The Agg or Group node will preserve ordering */
! 	if (target_pathkeys &&
! 		!pathkeys_contained_in(target_pathkeys, current_pathkeys))
! 		cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost,
  				  dNumGroups, sorted_p_width,
  				  0.0, work_mem, limit_tuples);
  
--- 4049,4060 ----
  		cost_group(&sorted_p, root, numGroupCols, dNumGroups,
  				   sorted_p.startup_cost, sorted_p.total_cost,
  				   path_rows);
+ 
  	/* The Agg or Group node will preserve ordering */
! 	n_common_pathkeys = pathkeys_common(target_pathkeys, current_pathkeys);
! 	if (target_pathkeys && n_common_pathkeys < list_length(target_pathkeys))
! 		cost_sort(&sorted_p, root, target_pathkeys, n_common_pathkeys,
! 				  sorted_p.startup_cost, sorted_p.total_cost,
  				  dNumGroups, sorted_p_width,
  				  0.0, work_mem, limit_tuples);
  
*************** choose_hashed_distinct(PlannerInfo *root
*** 4035,4040 ****
--- 4109,4115 ----
  	List	   *needed_pathkeys;
  	Path		hashed_p;
  	Path		sorted_p;
+ 	int			n_common_pathkeys;
  
  	/*
  	 * If we have a sortable DISTINCT ON clause, we always use sorting. This
*************** choose_hashed_distinct(PlannerInfo *root
*** 4101,4107 ****
  	 * need to charge for the final sort.
  	 */
  	if (parse->sortClause)
! 		cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost,
  				  dNumDistinctRows, cheapest_path_width,
  				  0.0, work_mem, limit_tuples);
  
--- 4176,4183 ----
  	 * need to charge for the final sort.
  	 */
  	if (parse->sortClause)
! 		cost_sort(&hashed_p, root, root->sort_pathkeys, 0,
! 				  hashed_p.startup_cost, hashed_p.total_cost,
  				  dNumDistinctRows, cheapest_path_width,
  				  0.0, work_mem, limit_tuples);
  
*************** choose_hashed_distinct(PlannerInfo *root
*** 4118,4140 ****
  		needed_pathkeys = root->sort_pathkeys;
  	else
  		needed_pathkeys = root->distinct_pathkeys;
! 	if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys))
  	{
  		if (list_length(root->distinct_pathkeys) >=
  			list_length(root->sort_pathkeys))
  			current_pathkeys = root->distinct_pathkeys;
  		else
  			current_pathkeys = root->sort_pathkeys;
! 		cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost,
  				  path_rows, sorted_path_width,
  				  0.0, work_mem, -1.0);
  	}
  	cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
  			   sorted_p.startup_cost, sorted_p.total_cost,
  			   path_rows);
  	if (parse->sortClause &&
! 		!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys))
! 		cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost,
  				  dNumDistinctRows, sorted_path_width,
  				  0.0, work_mem, limit_tuples);
  
--- 4194,4223 ----
  		needed_pathkeys = root->sort_pathkeys;
  	else
  		needed_pathkeys = root->distinct_pathkeys;
! 
! 	n_common_pathkeys = pathkeys_common(needed_pathkeys, current_pathkeys);
! 	if (n_common_pathkeys < list_length(needed_pathkeys))
  	{
  		if (list_length(root->distinct_pathkeys) >=
  			list_length(root->sort_pathkeys))
  			current_pathkeys = root->distinct_pathkeys;
  		else
  			current_pathkeys = root->sort_pathkeys;
! 		cost_sort(&sorted_p, root, current_pathkeys,
! 				  n_common_pathkeys, sorted_p.startup_cost, sorted_p.total_cost,
  				  path_rows, sorted_path_width,
  				  0.0, work_mem, -1.0);
  	}
  	cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows,
  			   sorted_p.startup_cost, sorted_p.total_cost,
  			   path_rows);
+ 
+ 
+ 	n_common_pathkeys = pathkeys_common(root->sort_pathkeys, current_pathkeys);
  	if (parse->sortClause &&
! 		n_common_pathkeys < list_length(root->sort_pathkeys))
! 		cost_sort(&sorted_p, root, root->sort_pathkeys, n_common_pathkeys,
! 				  sorted_p.startup_cost, sorted_p.total_cost,
  				  dNumDistinctRows, sorted_path_width,
  				  0.0, work_mem, limit_tuples);
  
*************** plan_cluster_use_sort(Oid tableOid, Oid 
*** 4924,4931 ****
  
  	/* Estimate the cost of seq scan + sort */
  	seqScanPath = create_seqscan_path(root, rel, NULL, 0);
! 	cost_sort(&seqScanAndSortPath, root, NIL,
! 			  seqScanPath->total_cost, rel->tuples, rel->reltarget.width,
  			  comparisonCost, maintenance_work_mem, -1.0);
  
  	/* Estimate the cost of index scan */
--- 5007,5015 ----
  
  	/* Estimate the cost of seq scan + sort */
  	seqScanPath = create_seqscan_path(root, rel, NULL, 0);
! 	cost_sort(&seqScanAndSortPath, root, NIL, 0,
! 			  seqScanPath->startup_cost, seqScanPath->total_cost,
! 			  rel->tuples, rel->reltarget.width,
  			  comparisonCost, maintenance_work_mem, -1.0);
  
  	/* Estimate the cost of index scan */
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
new file mode 100644
index 31db35c..66e82ec
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** build_subplan(PlannerInfo *root, Plan *p
*** 823,829 ****
  		 * unnecessarily, so we don't.
  		 */
  		else if (splan->parParam == NIL && enable_material &&
! 				 !ExecMaterializesOutput(nodeTag(plan)))
  			plan = materialize_finished_plan(plan);
  
  		result = (Node *) splan;
--- 823,829 ----
  		 * unnecessarily, so we don't.
  		 */
  		else if (splan->parParam == NIL && enable_material &&
! 				 !ExecMaterializesOutput(nodeTag(plan), plan))
  			plan = materialize_finished_plan(plan);
  
  		result = (Node *) splan;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
new file mode 100644
index e509a1a..24caf36
*** a/src/backend/optimizer/prep/prepunion.c
--- b/src/backend/optimizer/prep/prepunion.c
*************** choose_hashed_setop(PlannerInfo *root, L
*** 865,871 ****
  	sorted_p.startup_cost = input_plan->startup_cost;
  	sorted_p.total_cost = input_plan->total_cost;
  	/* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
! 	cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
  			  input_plan->plan_rows, input_plan->plan_width,
  			  0.0, work_mem, -1.0);
  	cost_group(&sorted_p, root, numGroupCols, dNumGroups,
--- 865,872 ----
  	sorted_p.startup_cost = input_plan->startup_cost;
  	sorted_p.total_cost = input_plan->total_cost;
  	/* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
! 	cost_sort(&sorted_p, root, NIL, 0,
! 			  sorted_p.startup_cost, sorted_p.total_cost,
  			  input_plan->plan_rows, input_plan->plan_width,
  			  0.0, work_mem, -1.0);
  	cost_group(&sorted_p, root, numGroupCols, dNumGroups,
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
new file mode 100644
index 9417587..0418406
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** compare_path_costs(Path *path1, Path *pa
*** 95,101 ****
  }
  
  /*
!  * compare_path_fractional_costs
   *	  Return -1, 0, or +1 according as path1 is cheaper, the same cost,
   *	  or more expensive than path2 for fetching the specified fraction
   *	  of the total tuples.
--- 95,101 ----
  }
  
  /*
!  * compare_fractional_path_costs
   *	  Return -1, 0, or +1 according as path1 is cheaper, the same cost,
   *	  or more expensive than path2 for fetching the specified fraction
   *	  of the total tuples.
*************** compare_fractional_path_costs(Path *path
*** 124,129 ****
--- 124,170 ----
  }
  
  /*
+  * compare_bifractional_path_costs
+  *	  Return -1, 0, or +1 according as fetching the fraction1 tuples of path1 is
+  *	  cheaper, the same cost, or more expensive than fetching fraction2 tuples
+  *	  of path2.
+  *
+  * fraction1 and fraction2 are fractions of total tuples between 0 and 1.
+  * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
+  * path with the cheaper total_cost.
+  */
+ 
+ /*
+  * Compare cost of two paths assuming different fractions of tuples be returned
+  * from each paths.
+  */
+ int
+ compare_bifractional_path_costs(Path *path1, Path *path2,
+ 								double fraction1, double fraction2)
+ {
+ 	Cost		cost1,
+ 				cost2;
+ 
+ 	if (fraction1 <= 0.0 || fraction1 >= 1.0)
+ 		fraction1 = 1.0;
+ 	if (fraction2 <= 0.0 || fraction2 >= 1.0)
+ 		fraction2 = 1.0;
+ 
+ 	if (fraction1 == 1.0 && fraction2 == 1.0)
+ 		return compare_path_costs(path1, path2, TOTAL_COST);
+ 
+ 	cost1 = path1->startup_cost +
+ 		fraction1 * (path1->total_cost - path1->startup_cost);
+ 	cost2 = path2->startup_cost +
+ 		fraction2 * (path2->total_cost - path2->startup_cost);
+ 	if (cost1 < cost2)
+ 		return -1;
+ 	if (cost1 > cost2)
+ 		return +1;
+ 	return 0;
+ }
+ 
+ /*
   * compare_path_costs_fuzzily
   *	  Compare the costs of two paths to see if either can be said to
   *	  dominate the other.
*************** create_merge_append_path(PlannerInfo *ro
*** 1278,1289 ****
  	foreach(l, subpaths)
  	{
  		Path	   *subpath = (Path *) lfirst(l);
  
  		pathnode->path.rows += subpath->rows;
  		pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
  			subpath->parallel_safe;
  
! 		if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
  		{
  			/* Subpath is adequately ordered, we won't need to sort it */
  			input_startup_cost += subpath->startup_cost;
--- 1319,1331 ----
  	foreach(l, subpaths)
  	{
  		Path	   *subpath = (Path *) lfirst(l);
+ 		int			n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys);
  
  		pathnode->path.rows += subpath->rows;
  		pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
  			subpath->parallel_safe;
  
! 		if (n_common_pathkeys == list_length(pathkeys))
  		{
  			/* Subpath is adequately ordered, we won't need to sort it */
  			input_startup_cost += subpath->startup_cost;
*************** create_merge_append_path(PlannerInfo *ro
*** 1297,1302 ****
--- 1339,1346 ----
  			cost_sort(&sort_path,
  					  root,
  					  pathkeys,
+ 					  n_common_pathkeys,
+ 					  subpath->startup_cost,
  					  subpath->total_cost,
  					  subpath->parent->tuples,
  					  subpath->pathtarget->width,
*************** create_unique_path(PlannerInfo *root, Re
*** 1528,1534 ****
  		/*
  		 * Estimate cost for sort+unique implementation
  		 */
! 		cost_sort(&sort_path, root, NIL,
  				  subpath->total_cost,
  				  rel->rows,
  				  subpath->pathtarget->width,
--- 1572,1579 ----
  		/*
  		 * Estimate cost for sort+unique implementation
  		 */
! 		cost_sort(&sort_path, root, NIL, 0,
! 				  subpath->startup_cost,
  				  subpath->total_cost,
  				  rel->rows,
  				  subpath->pathtarget->width,
diff --git a/src/backend/utils/adt/orderedsetaggs.c b/src/backend/utils/adt/orderedsetaggs.c
new file mode 100644
index fe44d56..8d1717c
*** a/src/backend/utils/adt/orderedsetaggs.c
--- b/src/backend/utils/adt/orderedsetaggs.c
*************** ordered_set_startup(FunctionCallInfo fci
*** 276,282 ****
  												   qstate->sortOperators,
  												   qstate->sortCollations,
  												   qstate->sortNullsFirsts,
! 												   work_mem, false);
  	else
  		osastate->sortstate = tuplesort_begin_datum(qstate->sortColType,
  													qstate->sortOperator,
--- 276,282 ----
  												   qstate->sortOperators,
  												   qstate->sortCollations,
  												   qstate->sortNullsFirsts,
! 												   work_mem, false, false);
  	else
  		osastate->sortstate = tuplesort_begin_datum(qstate->sortColType,
  													qstate->sortOperator,
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
new file mode 100644
index 46c95b0..9df7d1e
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** estimate_num_groups(PlannerInfo *root, L
*** 3463,3468 ****
--- 3463,3504 ----
  }
  
  /*
+  * estimate_pathkeys_groups	- Estimate number of groups which dataset is
+  * 							  divided to by pathkeys.
+  *
+  * Returns an array of group numbers. i'th element of array is number of groups
+  * which first i pathkeys divides dataset into.  Actually is a convenience
+  * wrapper over estimate_num_groups().
+  */
+ double *
+ estimate_pathkeys_groups(List *pathkeys, PlannerInfo *root, double tuples)
+ {
+ 	ListCell   *l;
+ 	List	   *groupExprs = NIL;
+ 	double	   *result;
+ 	int			i;
+ 
+ 	/*
+ 	 * Get number of groups for each prefix of pathkeys.
+ 	 */
+ 	i = 0;
+ 	result = (double *) palloc(sizeof(double) * list_length(pathkeys));
+ 	foreach(l, pathkeys)
+ 	{
+ 		PathKey *key = (PathKey *)lfirst(l);
+ 		EquivalenceMember *member = (EquivalenceMember *)
+ 							linitial(key->pk_eclass->ec_members);
+ 
+ 		groupExprs = lappend(groupExprs, member->em_expr);
+ 
+ 		result[i] = estimate_num_groups(root, groupExprs, tuples, NULL);
+ 		i++;
+ 	}
+ 
+ 	return result;
+ }
+ 
+ /*
   * Estimate hash bucketsize fraction (ie, number of entries in a bucket
   * divided by total tuples in relation) if the specified expression is used
   * as a hash key.
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
new file mode 100644
index 67d86ed..6260e44
*** a/src/backend/utils/sort/tuplesort.c
--- b/src/backend/utils/sort/tuplesort.c
*************** tuplesort_begin_heap(TupleDesc tupDesc,
*** 614,620 ****
  					 int nkeys, AttrNumber *attNums,
  					 Oid *sortOperators, Oid *sortCollations,
  					 bool *nullsFirstFlags,
! 					 int workMem, bool randomAccess)
  {
  	Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
  	MemoryContext oldcontext;
--- 614,621 ----
  					 int nkeys, AttrNumber *attNums,
  					 Oid *sortOperators, Oid *sortCollations,
  					 bool *nullsFirstFlags,
! 					 int workMem, bool randomAccess,
! 					 bool skipAbbrev)
  {
  	Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
  	MemoryContext oldcontext;
*************** tuplesort_begin_heap(TupleDesc tupDesc,
*** 662,668 ****
  		sortKey->ssup_nulls_first = nullsFirstFlags[i];
  		sortKey->ssup_attno = attNums[i];
  		/* Convey if abbreviation optimization is applicable in principle */
! 		sortKey->abbreviate = (i == 0);
  
  		PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
  	}
--- 663,669 ----
  		sortKey->ssup_nulls_first = nullsFirstFlags[i];
  		sortKey->ssup_attno = attNums[i];
  		/* Convey if abbreviation optimization is applicable in principle */
! 		sortKey->abbreviate = (i == 0) && !skipAbbrev;
  
  		PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
  	}
*************** tuplesort_end(Tuplesortstate *state)
*** 1076,1081 ****
--- 1077,1102 ----
  	MemoryContextDelete(state->sortcontext);
  }
  
+ void
+ tuplesort_reset(Tuplesortstate *state)
+ {
+ 	int i;
+ 
+ 	if (state->tapeset)
+ 		LogicalTapeSetClose(state->tapeset);
+ 
+ 	for (i = 0; i < state->memtupcount; i++)
+ 		free_sort_tuple(state, state->memtuples + i);
+ 
+ 	state->status = TSS_INITIAL;
+ 	state->memtupcount = 0;
+ 	state->boundUsed = false;
+ 	state->tapeset = NULL;
+ 	state->currentRun = 0;
+ 	state->result_tape = -1;
+ 	state->bounded = false;
+ }
+ 
  /*
   * Grow the memtuples[] array, if possible within our memory constraint.  We
   * must not exceed INT_MAX tuples in memory or the caller-provided memory
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
new file mode 100644
index 1a44085..0075be5
*** a/src/include/executor/executor.h
--- b/src/include/executor/executor.h
*************** struct Path;					/* avoid including rela
*** 104,112 ****
  extern void ExecReScan(PlanState *node);
  extern void ExecMarkPos(PlanState *node);
  extern void ExecRestrPos(PlanState *node);
! extern bool ExecSupportsMarkRestore(struct Path *pathnode);
  extern bool ExecSupportsBackwardScan(Plan *node);
! extern bool ExecMaterializesOutput(NodeTag plantype);
  
  /*
   * prototypes from functions in execCurrent.c
--- 104,112 ----
  extern void ExecReScan(PlanState *node);
  extern void ExecMarkPos(PlanState *node);
  extern void ExecRestrPos(PlanState *node);
! extern bool ExecSupportsMarkRestore(struct Path *pathnode, Plan *node);
  extern bool ExecSupportsBackwardScan(Plan *node);
! extern bool ExecMaterializesOutput(NodeTag plantype, Plan *node);
  
  /*
   * prototypes from functions in execCurrent.c
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
new file mode 100644
index 064a050..c3c1692
*** a/src/include/nodes/execnodes.h
--- b/src/include/nodes/execnodes.h
*************** typedef struct MaterialState
*** 1801,1806 ****
--- 1801,1813 ----
  	Tuplestorestate *tuplestorestate;
  } MaterialState;
  
+ typedef struct SkipKeyData
+ {
+ 	FunctionCallInfoData	fcinfo;
+ 	FmgrInfo				flinfo;
+ 	OffsetNumber			attno;
+ } SkipKeyData;
+ 
  /* ----------------
   *	 SortState information
   * ----------------
*************** typedef struct SortState
*** 1812,1820 ****
--- 1819,1832 ----
  	bool		bounded;		/* is the result set bounded? */
  	int64		bound;			/* if bounded, how many tuples are needed */
  	bool		sort_Done;		/* sort completed yet? */
+ 	bool		finished;		/* fetching tuples from outer node
+ 								   is finished ? */
  	bool		bounded_Done;	/* value of bounded we did the sort with */
  	int64		bound_Done;		/* value of bound we did the sort with */
+ 	long		groupsCount;
  	void	   *tuplesortstate; /* private state of tuplesort.c */
+ 	SkipKeyData *skipKeys;
+ 	HeapTuple	prev;			/* previous tuple from outer node */
  } SortState;
  
  /* ---------------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
new file mode 100644
index ae224cf..2fa20ed
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
*************** typedef struct Sort
*** 680,685 ****
--- 680,686 ----
  {
  	Plan		plan;
  	int			numCols;		/* number of sort-key columns */
+ 	int			skipCols;
  	AttrNumber *sortColIdx;		/* their indexes in the target list */
  	Oid		   *sortOperators;	/* OIDs of operators to sort them by */
  	Oid		   *collations;		/* OIDs of collations */
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
new file mode 100644
index 78c7cae..e7ae3ea
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern void cost_ctescan(Path *path, Pla
*** 95,102 ****
  			 RelOptInfo *baserel, ParamPathInfo *param_info);
  extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm);
  extern void cost_sort(Path *path, PlannerInfo *root,
! 		  List *pathkeys, Cost input_cost, double tuples, int width,
! 		  Cost comparison_cost, int sort_mem,
  		  double limit_tuples);
  extern void cost_merge_append(Path *path, PlannerInfo *root,
  				  List *pathkeys, int n_streams,
--- 95,103 ----
  			 RelOptInfo *baserel, ParamPathInfo *param_info);
  extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm);
  extern void cost_sort(Path *path, PlannerInfo *root,
! 		  List *pathkeys, int presorted_keys,
! 		  Cost input_startup_cost, Cost input_total_cost,
! 		  double tuples, int width, Cost comparison_cost, int sort_mem,
  		  double limit_tuples);
  extern void cost_merge_append(Path *path, PlannerInfo *root,
  				  List *pathkeys, int n_streams,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
new file mode 100644
index f479981..e698e2c
*** a/src/include/optimizer/pathnode.h
--- b/src/include/optimizer/pathnode.h
*************** extern int compare_path_costs(Path *path
*** 24,29 ****
--- 24,31 ----
  				   CostSelector criterion);
  extern int compare_fractional_path_costs(Path *path1, Path *path2,
  							  double fraction);
+ extern int compare_bifractional_path_costs(Path *path1, Path *path2,
+ 							  double fraction1, double fraction2);
  extern void set_cheapest(RelOptInfo *parent_rel);
  extern void add_path(RelOptInfo *parent_rel, Path *new_path);
  extern bool add_path_precheck(RelOptInfo *parent_rel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
new file mode 100644
index 20474c3..cd117ca
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** typedef enum
*** 169,181 ****
  
  extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
  extern bool pathkeys_contained_in(List *keys1, List *keys2);
  extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
  							   Relids required_outer,
  							   CostSelector cost_criterion);
  extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
  										  List *pathkeys,
  										  Relids required_outer,
! 										  double fraction);
  extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
  					 ScanDirection scandir);
  extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
--- 169,183 ----
  
  extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
  extern bool pathkeys_contained_in(List *keys1, List *keys2);
+ extern int pathkeys_common(List *keys1, List *keys2);
  extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
  							   Relids required_outer,
  							   CostSelector cost_criterion);
  extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
  										  List *pathkeys,
  										  Relids required_outer,
! 										  double fraction,
! 										  double *num_groups);
  extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
  					 ScanDirection scandir);
  extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
new file mode 100644
index eaa642b..c8ff0bf
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RecursiveUnion *make_recursive_un
*** 61,71 ****
  					 Plan *lefttree, Plan *righttree, int wtParam,
  					 List *distinctList, long numGroups);
  extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
! 						List *pathkeys, double limit_tuples);
  extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls,
  						   Plan *lefttree);
  extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls,
! 						 AttrNumber *grpColIdx, Plan *lefttree);
  extern Agg *make_agg(PlannerInfo *root, List *tlist, List *qual,
  		 AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
  		 int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
--- 61,72 ----
  					 Plan *lefttree, Plan *righttree, int wtParam,
  					 List *distinctList, long numGroups);
  extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree,
! 						List *pathkeys, double limit_tuples, int skipCols);
  extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls,
  						   Plan *lefttree);
  extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls,
! 						 AttrNumber *grpColIdx, Plan *lefttree, List *pathkeys,
! 						 int skipCols);
  extern Agg *make_agg(PlannerInfo *root, List *tlist, List *qual,
  		 AggStrategy aggstrategy, const AggClauseCosts *aggcosts,
  		 int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators,
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
new file mode 100644
index 06fbca7..3ee58ed
*** a/src/include/utils/selfuncs.h
--- b/src/include/utils/selfuncs.h
*************** extern void mergejoinscansel(PlannerInfo
*** 188,193 ****
--- 188,196 ----
  extern double estimate_num_groups(PlannerInfo *root, List *groupExprs,
  					double input_rows, List **pgset);
  
+ extern double *estimate_pathkeys_groups(List *pathkeys, PlannerInfo *root,
+ 										double tuples);
+ 
  extern Selectivity estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey,
  						 double nbuckets);
  
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
new file mode 100644
index 5cecd6d..6476504
*** a/src/include/utils/tuplesort.h
--- b/src/include/utils/tuplesort.h
*************** extern Tuplesortstate *tuplesort_begin_h
*** 62,68 ****
  					 int nkeys, AttrNumber *attNums,
  					 Oid *sortOperators, Oid *sortCollations,
  					 bool *nullsFirstFlags,
! 					 int workMem, bool randomAccess);
  extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
  						Relation indexRel,
  						int workMem, bool randomAccess);
--- 62,69 ----
  					 int nkeys, AttrNumber *attNums,
  					 Oid *sortOperators, Oid *sortCollations,
  					 bool *nullsFirstFlags,
! 					 int workMem, bool randomAccess,
! 					 bool skipAbbrev);
  extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
  						Relation indexRel,
  						int workMem, bool randomAccess);
*************** extern bool tuplesort_skiptuples(Tupleso
*** 106,111 ****
--- 107,114 ----
  
  extern void tuplesort_end(Tuplesortstate *state);
  
+ extern void tuplesort_reset(Tuplesortstate *state);
+ 
  extern void tuplesort_get_stats(Tuplesortstate *state,
  					const char **sortMethod,
  					const char **spaceType,
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
new file mode 100644
index e434c5d..86a15a1
*** a/src/test/regress/expected/aggregates.out
--- b/src/test/regress/expected/aggregates.out
*************** group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t
*** 897,911 ****
  explain (costs off) select t1.*,t2.x,t2.z
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
!                       QUERY PLAN                       
! -------------------------------------------------------
!  HashAggregate
     Group Key: t1.a, t1.b, t2.x, t2.z
!    ->  Merge Join
!          Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
!          ->  Index Scan using t1_pkey on t1
!          ->  Index Scan using t2_pkey on t2
! (6 rows)
  
  -- Cannot optimize when PK is deferrable
  explain (costs off) select * from t3 group by a,b,c;
--- 897,914 ----
  explain (costs off) select t1.*,t2.x,t2.z
  from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
  group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
!                          QUERY PLAN                          
! -------------------------------------------------------------
!  Group
     Group Key: t1.a, t1.b, t2.x, t2.z
!    ->  Sort
!          Sort Key: t1.a, t1.b, t2.x, t2.z
!          Presorted Key: t1.a, t1.b
!          ->  Merge Join
!                Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
!                ->  Index Scan using t1_pkey on t1
!                ->  Index Scan using t2_pkey on t2
! (9 rows)
  
  -- Cannot optimize when PK is deferrable
  explain (costs off) select * from t3 group by a,b,c;
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
new file mode 100644
index 89b6c1c..3c2b0ad
*** a/src/test/regress/expected/inherit.out
--- b/src/test/regress/expected/inherit.out
*************** SELECT thousand, thousand FROM tenk1
*** 1354,1366 ****
  ORDER BY thousand, tenthous;
                                 QUERY PLAN                                
  -------------------------------------------------------------------------
!  Merge Append
     Sort Key: tenk1.thousand, tenk1.tenthous
!    ->  Index Only Scan using tenk1_thous_tenthous on tenk1
!    ->  Sort
!          Sort Key: tenk1_1.thousand, tenk1_1.thousand
           ->  Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (6 rows)
  
  explain (costs off)
  SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
--- 1354,1367 ----
  ORDER BY thousand, tenthous;
                                 QUERY PLAN                                
  -------------------------------------------------------------------------
!  Sort
     Sort Key: tenk1.thousand, tenk1.tenthous
!    Presorted Key: tenk1.thousand
!    ->  Merge Append
!          Sort Key: tenk1.thousand
!          ->  Index Only Scan using tenk1_thous_tenthous on tenk1
           ->  Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (7 rows)
  
  explain (costs off)
  SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
*************** SELECT x, y FROM
*** 1436,1450 ****
     UNION ALL
     SELECT unique2 AS x, unique2 AS y FROM tenk1 b) s
  ORDER BY x, y;
!                          QUERY PLAN                          
! -------------------------------------------------------------
!  Merge Append
     Sort Key: a.thousand, a.tenthous
!    ->  Index Only Scan using tenk1_thous_tenthous on tenk1 a
!    ->  Sort
!          Sort Key: b.unique2, b.unique2
           ->  Index Only Scan using tenk1_unique2 on tenk1 b
! (6 rows)
  
  -- exercise rescan code path via a repeatedly-evaluated subquery
  explain (costs off)
--- 1437,1452 ----
     UNION ALL
     SELECT unique2 AS x, unique2 AS y FROM tenk1 b) s
  ORDER BY x, y;
!                             QUERY PLAN                             
! -------------------------------------------------------------------
!  Sort
     Sort Key: a.thousand, a.tenthous
!    Presorted Key: a.thousand
!    ->  Merge Append
!          Sort Key: a.thousand
!          ->  Index Only Scan using tenk1_thous_tenthous on tenk1 a
           ->  Index Only Scan using tenk1_unique2 on tenk1 b
! (7 rows)
  
  -- exercise rescan code path via a repeatedly-evaluated subquery
  explain (costs off)