partial-sort-basic-7.patch

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 0c8e939..eaf54d7
*** a/src/backend/executor/execAmi.c
--- b/src/backend/executor/execAmi.c
*************** 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,409 ----
  		case T_IndexScan:
  		case T_IndexOnlyScan:
  		case T_Material:
  			return true;
  
+ 		case T_Sort:
+ 			/* With skipCols sort node holds only last bucket */
+ 			if (((SortPath *)pathnode)->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)
*** 511,520 ****
  			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 */
--- 517,532 ----
  			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)
*** 575,581 ****
   * very low per-tuple cost.
   */
  bool
! ExecMaterializesOutput(NodeTag plantype)
  {
  	switch (plantype)
  	{
--- 587,593 ----
   * very low per-tuple cost.
   */
  bool
! ExecMaterializesOutput(NodeTag plantype, Plan *node)
  {
  	switch (plantype)
  	{
*************** ExecMaterializesOutput(NodeTag plantype)
*** 583,591 ****
  		case T_FunctionScan:
  		case T_CteScan:
  		case T_WorkTableScan:
- 		case T_Sort:
  			return true;
  
  		default:
  			break;
  	}
--- 595,611 ----
  		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 df7c2fa..054d117
*** 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 eb0fc1e..7374046
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outSort(StringInfo str, const Sort *nod
*** 796,801 ****
--- 796,802 ----
  	_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 a2c2243..f188893
*** 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 5350329..2e13492
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_recursive_union(Path *runion, Path 
*** 1412,1417 ****
--- 1412,1424 ----
   *	  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(Path *runion, Path 
*** 1438,1444 ****
   * 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
--- 1445,1452 ----
   * 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(Path *runion, Path 
*** 1454,1468 ****
   */
  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)
--- 1462,1483 ----
   */
  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,
*** 1492,1504 ****
  		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;
--- 1507,1556 ----
  		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,
*** 1508,1514 ****
  		 *
  		 * Assume about N log2 N comparisons
  		 */
! 		startup_cost += comparison_cost * tuples * LOG2(tuples);
  
  		/* Disk costs */
  
--- 1560,1566 ----
  		 *
  		 * Assume about N log2 N comparisons
  		 */
! 		group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
  
  		/* Disk costs */
  
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1519,1528 ****
  			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
--- 1571,1580 ----
  			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,
*** 1530,1543 ****
  		 * 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
--- 1582,1607 ----
  		 * 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
*** 2282,2287 ****
--- 2346,2353 ----
  		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
*** 2308,2313 ****
--- 2374,2381 ----
  		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,
*************** cost_subplan(PlannerInfo *root, SubPlan 
*** 3042,3048 ****
  		 * every time.
  		 */
  		if (subplan->parParam == NIL &&
! 			ExecMaterializesOutput(nodeTag(plan)))
  			sp_cost.startup += plan->startup_cost;
  		else
  			sp_cost.per_tuple += plan->startup_cost;
--- 3110,3116 ----
  		 * 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 4436ac1..d60c421
*** 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,
*** 1448,1456 ****
   *		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)
--- 1519,1526 ----
   *		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
*** 1461,1473 ****
  	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 */
  }
  
  /*
--- 1531,1542 ----
  	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 913ac84..94b01e8
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** static MergeJoin *make_mergejoin(List *t
*** 226,232 ****
  			   bool *mergenullsfirst,
  			   Plan *lefttree, Plan *righttree,
  			   JoinType jointype);
! static Sort *make_sort(Plan *lefttree, int numCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst);
  static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
--- 226,232 ----
  			   bool *mergenullsfirst,
  			   Plan *lefttree, Plan *righttree,
  			   JoinType jointype);
! static Sort *make_sort(Plan *lefttree, int numCols, int skipCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst);
  static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
*************** static Plan *prepare_sort_from_pathkeys(
*** 241,250 ****
  static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
  					   TargetEntry *tle,
  					   Relids relids);
! static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys);
  static Sort *make_sort_from_groupcols(List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree);
  static Material *make_material(Plan *lefttree);
  static WindowAgg *make_windowagg(List *tlist, Index winref,
  			   int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
--- 241,252 ----
  static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
  					   TargetEntry *tle,
  					   Relids relids);
! static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
! 						 int skipCols);
  static Sort *make_sort_from_groupcols(List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree,
! 						 int skipCols);
  static Material *make_material(Plan *lefttree);
  static WindowAgg *make_windowagg(List *tlist, Index winref,
  			   int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
*************** create_merge_append_plan(PlannerInfo *ro
*** 1031,1036 ****
--- 1033,1039 ----
  		Oid		   *sortOperators;
  		Oid		   *collations;
  		bool	   *nullsFirst;
+ 		int			n_common_pathkeys;
  
  		/* Build the child plan */
  		/* Must insist that all children return the same tlist */
*************** create_merge_append_plan(PlannerInfo *ro
*** 1065,1073 ****
  					  numsortkeys * sizeof(bool)) == 0);
  
  		/* Now, insert a Sort node if subplan isn't sufficiently ordered */
! 		if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
  		{
  			Sort	   *sort = make_sort(subplan, numsortkeys,
  										 sortColIdx, sortOperators,
  										 collations, nullsFirst);
  
--- 1068,1078 ----
  					  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))
  		{
  			Sort	   *sort = make_sort(subplan, numsortkeys,
+ 										 n_common_pathkeys,
  										 sortColIdx, sortOperators,
  										 collations, nullsFirst);
  
*************** create_sort_plan(PlannerInfo *root, Sort
*** 1465,1470 ****
--- 1470,1476 ----
  {
  	Sort	   *plan;
  	Plan	   *subplan;
+ 	int			n_common_pathkeys;
  
  	/*
  	 * We don't want any excess columns in the sorted tuples, so request a
*************** create_sort_plan(PlannerInfo *root, Sort
*** 1474,1480 ****
  	subplan = create_plan_recurse(root, best_path->subpath,
  								  flags | CP_SMALL_TLIST);
  
! 	plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys);
  
  	copy_generic_path_info(&plan->plan, (Path *) best_path);
  
--- 1480,1490 ----
  	subplan = create_plan_recurse(root, best_path->subpath,
  								  flags | CP_SMALL_TLIST);
  
! 	n_common_pathkeys = pathkeys_common(best_path->path.pathkeys,
! 										best_path->subpath->pathkeys);
! 
! 	plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
! 								   n_common_pathkeys);
  
  	copy_generic_path_info(&plan->plan, (Path *) best_path);
  
*************** create_groupingsets_plan(PlannerInfo *ro
*** 1721,1727 ****
  			sort_plan = (Plan *)
  				make_sort_from_groupcols(groupClause,
  										 new_grpColIdx,
! 										 subplan);
  
  			agg_plan = (Plan *) make_agg(NIL,
  										 NIL,
--- 1731,1738 ----
  			sort_plan = (Plan *)
  				make_sort_from_groupcols(groupClause,
  										 new_grpColIdx,
! 										 subplan,
! 										 0);
  
  			agg_plan = (Plan *) make_agg(NIL,
  										 NIL,
*************** create_mergejoin_plan(PlannerInfo *root,
*** 3571,3578 ****
  	 */
  	if (best_path->outersortkeys)
  	{
! 		Sort	   *sort = make_sort_from_pathkeys(outer_plan,
! 												   best_path->outersortkeys);
  
  		label_sort_with_costsize(root, sort, -1.0);
  		outer_plan = (Plan *) sort;
--- 3582,3595 ----
  	 */
  	if (best_path->outersortkeys)
  	{
! 		Sort	   *sort;
! 		int			n_common_pathkeys;
! 
! 		n_common_pathkeys = pathkeys_common(best_path->outersortkeys,
! 									best_path->jpath.outerjoinpath->pathkeys);
! 
! 		sort = make_sort_from_pathkeys(outer_plan, best_path->outersortkeys,
! 									   n_common_pathkeys);
  
  		label_sort_with_costsize(root, sort, -1.0);
  		outer_plan = (Plan *) sort;
*************** create_mergejoin_plan(PlannerInfo *root,
*** 3583,3590 ****
  
  	if (best_path->innersortkeys)
  	{
! 		Sort	   *sort = make_sort_from_pathkeys(inner_plan,
! 												   best_path->innersortkeys);
  
  		label_sort_with_costsize(root, sort, -1.0);
  		inner_plan = (Plan *) sort;
--- 3600,3613 ----
  
  	if (best_path->innersortkeys)
  	{
! 		Sort	   *sort;
! 		int			n_common_pathkeys;
! 
! 		n_common_pathkeys = pathkeys_common(best_path->innersortkeys,
! 									best_path->jpath.innerjoinpath->pathkeys);
! 
! 		sort = make_sort_from_pathkeys(inner_plan, best_path->innersortkeys,
! 									   n_common_pathkeys);
  
  		label_sort_with_costsize(root, sort, -1.0);
  		inner_plan = (Plan *) sort;
*************** label_sort_with_costsize(PlannerInfo *ro
*** 4602,4608 ****
  	Plan	   *lefttree = plan->plan.lefttree;
  	Path		sort_path;		/* dummy for result of cost_sort */
  
! 	cost_sort(&sort_path, root, NIL,
  			  lefttree->total_cost,
  			  lefttree->plan_rows,
  			  lefttree->plan_width,
--- 4625,4632 ----
  	Plan	   *lefttree = plan->plan.lefttree;
  	Path		sort_path;		/* dummy for result of cost_sort */
  
! 	cost_sort(&sort_path, root, NIL, 0,
! 			  lefttree->startup_cost,
  			  lefttree->total_cost,
  			  lefttree->plan_rows,
  			  lefttree->plan_width,
*************** make_mergejoin(List *tlist,
*** 5123,5129 ****
   * nullsFirst arrays already.
   */
  static Sort *
! make_sort(Plan *lefttree, int numCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst)
  {
--- 5147,5153 ----
   * nullsFirst arrays already.
   */
  static Sort *
! make_sort(Plan *lefttree, int numCols, int skipCols,
  		  AttrNumber *sortColIdx, Oid *sortOperators,
  		  Oid *collations, bool *nullsFirst)
  {
*************** make_sort(Plan *lefttree, int numCols,
*** 5135,5140 ****
--- 5159,5165 ----
  	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 
*** 5461,5467 ****
   *	  'pathkeys' is the list of pathkeys by which the result is to be sorted
   */
  static Sort *
! make_sort_from_pathkeys(Plan *lefttree, List *pathkeys)
  {
  	int			numsortkeys;
  	AttrNumber *sortColIdx;
--- 5486,5492 ----
   *	  'pathkeys' is the list of pathkeys by which the result is to be sorted
   */
  static Sort *
! make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, int skipCols)
  {
  	int			numsortkeys;
  	AttrNumber *sortColIdx;
*************** make_sort_from_pathkeys(Plan *lefttree, 
*** 5481,5487 ****
  										  &nullsFirst);
  
  	/* Now build the Sort node */
! 	return make_sort(lefttree, numsortkeys,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
--- 5506,5512 ----
  										  &nullsFirst);
  
  	/* Now build the Sort node */
! 	return make_sort(lefttree, numsortkeys, skipCols,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
*************** make_sort_from_sortclauses(List *sortcls
*** 5524,5530 ****
  		numsortkeys++;
  	}
  
! 	return make_sort(lefttree, numsortkeys,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
--- 5549,5555 ----
  		numsortkeys++;
  	}
  
! 	return make_sort(lefttree, numsortkeys, 0,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
*************** make_sort_from_sortclauses(List *sortcls
*** 5545,5551 ****
  static Sort *
  make_sort_from_groupcols(List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree)
  {
  	List	   *sub_tlist = lefttree->targetlist;
  	ListCell   *l;
--- 5570,5577 ----
  static Sort *
  make_sort_from_groupcols(List *groupcls,
  						 AttrNumber *grpColIdx,
! 						 Plan *lefttree,
! 						 int skipCols)
  {
  	List	   *sub_tlist = lefttree->targetlist;
  	ListCell   *l;
*************** make_sort_from_groupcols(List *groupcls,
*** 5578,5584 ****
  		numsortkeys++;
  	}
  
! 	return make_sort(lefttree, numsortkeys,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
--- 5604,5610 ----
  		numsortkeys++;
  	}
  
! 	return make_sort(lefttree, numsortkeys, skipCols,
  					 sortColIdx, sortOperators,
  					 collations, nullsFirst);
  }
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
new file mode 100644
index cefec7b..75f3f29
*** a/src/backend/optimizer/plan/planagg.c
--- b/src/backend/optimizer/plan/planagg.c
***************
*** 44,49 ****
--- 44,50 ----
  #include "parser/parse_clause.h"
  #include "rewrite/rewriteManip.h"
  #include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
  #include "utils/syscache.h"
  
  
*************** build_minmax_path(PlannerInfo *root, Min
*** 341,346 ****
--- 342,348 ----
  	Path	   *sorted_path;
  	Cost		path_cost;
  	double		path_fraction;
+ 	double	   *psort_num_groups;
  
  	/*
  	 * We are going to construct what is effectively a sub-SELECT query, so
*************** build_minmax_path(PlannerInfo *root, Min
*** 451,461 ****
  	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;
  
--- 453,467 ----
  	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 8afac0b..13e9737
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** create_grouping_paths(PlannerInfo *root,
*** 3243,3256 ****
  		foreach(lc, input_rel->pathlist)
  		{
  			Path	   *path = (Path *) lfirst(lc);
! 			bool		is_sorted;
  
! 			is_sorted = pathkeys_contained_in(root->group_pathkeys,
! 											  path->pathkeys);
! 			if (path == cheapest_path || is_sorted)
  			{
  				/* Sort the cheapest-total path if it isn't already sorted */
! 				if (!is_sorted)
  					path = (Path *) create_sort_path(root,
  													 grouped_rel,
  													 path,
--- 3243,3256 ----
  		foreach(lc, input_rel->pathlist)
  		{
  			Path	   *path = (Path *) lfirst(lc);
! 			int			n_common_pathkeys;
  
! 			n_common_pathkeys = pathkeys_common(root->group_pathkeys,
! 												path->pathkeys);
! 			if (path == cheapest_path || n_common_pathkeys > 0)
  			{
  				/* Sort the cheapest-total path if it isn't already sorted */
! 				if (n_common_pathkeys < list_length(root->group_pathkeys))
  					path = (Path *) create_sort_path(root,
  													 grouped_rel,
  													 path,
*************** create_ordered_paths(PlannerInfo *root,
*** 3751,3763 ****
  	foreach(lc, input_rel->pathlist)
  	{
  		Path	   *path = (Path *) lfirst(lc);
! 		bool		is_sorted;
  
! 		is_sorted = pathkeys_contained_in(root->sort_pathkeys,
! 										  path->pathkeys);
! 		if (path == cheapest_input_path || is_sorted)
  		{
! 			if (!is_sorted)
  			{
  				/* An explicit sort here can take advantage of LIMIT */
  				path = (Path *) create_sort_path(root,
--- 3751,3763 ----
  	foreach(lc, input_rel->pathlist)
  	{
  		Path	   *path = (Path *) lfirst(lc);
! 		int			n_common_pathkeys;
  
! 		n_common_pathkeys = pathkeys_common(root->sort_pathkeys,
! 											path->pathkeys);
! 		if (path == cheapest_input_path || n_common_pathkeys > 0)
  		{
! 			if (n_common_pathkeys < list_length(root->sort_pathkeys))
  			{
  				/* An explicit sort here can take advantage of LIMIT */
  				path = (Path *) create_sort_path(root,
*************** plan_cluster_use_sort(Oid tableOid, Oid 
*** 4549,4556 ****
  
  	/* 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 */
--- 4549,4557 ----
  
  	/* 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 1ff4302..d7542e9
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** build_subplan(PlannerInfo *root, Plan *p
*** 837,843 ****
  		 * unnecessarily, so we don't.
  		 */
  		else if (splan->parParam == NIL && enable_material &&
! 				 !ExecMaterializesOutput(nodeTag(plan)))
  			plan = materialize_finished_plan(plan);
  
  		result = (Node *) splan;
--- 837,843 ----
  		 * 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 6ea3319..456e8df
*** a/src/backend/optimizer/prep/prepunion.c
--- b/src/backend/optimizer/prep/prepunion.c
*************** choose_hashed_setop(PlannerInfo *root, L
*** 954,960 ****
  	sorted_p.startup_cost = input_path->startup_cost;
  	sorted_p.total_cost = input_path->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_path->rows, input_path->pathtarget->width,
  			  0.0, work_mem, -1.0);
  	cost_group(&sorted_p, root, numGroupCols, dNumGroups,
--- 954,961 ----
  	sorted_p.startup_cost = input_path->startup_cost;
  	sorted_p.total_cost = input_path->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_path->rows, input_path->pathtarget->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 6e79800..48b23c4
*** 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
*** 1533,1539 ****
  		/*
  		 * Estimate cost for sort+unique implementation
  		 */
! 		cost_sort(&sort_path, root, NIL,
  				  subpath->total_cost,
  				  rel->rows,
  				  subpath->pathtarget->width,
--- 1577,1584 ----
  		/*
  		 * Estimate cost for sort+unique implementation
  		 */
! 		cost_sort(&sort_path, root, NIL, 0,
! 				  subpath->startup_cost,
  				  subpath->total_cost,
  				  rel->rows,
  				  subpath->pathtarget->width,
*************** create_sort_path(PlannerInfo *root,
*** 2240,2245 ****
--- 2285,2295 ----
  				 double limit_tuples)
  {
  	SortPath   *pathnode = makeNode(SortPath);
+ 	int			n_common_pathkeys;
+ 
+ 	n_common_pathkeys = pathkeys_common(subpath->pathkeys, pathkeys);
+ 
+ 	Assert(n_common_pathkeys < list_length(pathkeys));
  
  	pathnode->path.pathtype = T_Sort;
  	pathnode->path.parent = rel;
*************** create_sort_path(PlannerInfo *root,
*** 2252,2261 ****
  		subpath->parallel_safe;
  	pathnode->path.parallel_degree = subpath->parallel_degree;
  	pathnode->path.pathkeys = pathkeys;
  
  	pathnode->subpath = subpath;
  
! 	cost_sort(&pathnode->path, root, pathkeys,
  			  subpath->total_cost,
  			  subpath->rows,
  			  subpath->pathtarget->width,
--- 2302,2314 ----
  		subpath->parallel_safe;
  	pathnode->path.parallel_degree = subpath->parallel_degree;
  	pathnode->path.pathkeys = pathkeys;
+ 	pathnode->skipCols = n_common_pathkeys;
  
  	pathnode->subpath = subpath;
  
! 	cost_sort(&pathnode->path, root,
! 			  pathkeys, n_common_pathkeys,
! 			  subpath->startup_cost,
  			  subpath->total_cost,
  			  subpath->rows,
  			  subpath->pathtarget->width,
*************** create_groupingsets_path(PlannerInfo *ro
*** 2524,2530 ****
  				break;
  
  			/* Account for cost of sort, but don't charge input cost again */
! 			cost_sort(&sort_path, root, NIL,
  					  0.0,
  					  subpath->rows,
  					  subpath->pathtarget->width,
--- 2577,2584 ----
  				break;
  
  			/* Account for cost of sort, but don't charge input cost again */
! 			cost_sort(&sort_path, root, NIL, 0,
! 					  0.0,
  					  0.0,
  					  subpath->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 d396ef1..465d2f0
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** estimate_num_groups(PlannerInfo *root, L
*** 3464,3469 ****
--- 3464,3505 ----
  }
  
  /*
+  * 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 44fac27..5bc4d08
*** a/src/include/executor/executor.h
--- b/src/include/executor/executor.h
*************** extern void ExecMarkPos(PlanState *node)
*** 106,112 ****
  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
--- 106,112 ----
  extern void ExecRestrPos(PlanState *node);
  extern bool ExecSupportsMarkRestore(struct Path *pathnode);
  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 d35ec81..0a7ba55
*** 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 5961f2c..e640b73
*** 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/nodes/relation.h b/src/include/nodes/relation.h
new file mode 100644
index 641728b..e7245aa
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct SortPath
*** 1253,1258 ****
--- 1253,1259 ----
  {
  	Path		path;
  	Path	   *subpath;		/* path representing input source */
+ 	int			skipCols;
  } SortPath;
  
  /*
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
new file mode 100644
index fea2bb7..f7c0d8b
*** 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(Path *runion, Path *nrterm, Path *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(Path *runion, Path *nrterm, Path *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 3007adb..690c566
*** 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 2fccc3a..71b2b84
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** typedef enum
*** 166,178 ****
  
  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,
--- 166,180 ----
  
  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/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 601bdb4..6f3b86b
*** 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
*** 898,912 ****
  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;
--- 898,915 ----
  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.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..25ef3cd
*** a/src/test/regress/expected/inherit.out
--- b/src/test/regress/expected/inherit.out
*************** ORDER BY thousand, tenthous;
*** 1359,1366 ****
     ->  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
--- 1359,1367 ----
     ->  Index Only Scan using tenk1_thous_tenthous on tenk1
     ->  Sort
           Sort Key: tenk1_1.thousand, tenk1_1.thousand
+          Presorted Key: tenk1_1.thousand
           ->  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
*************** ORDER BY x, y;
*** 1443,1450 ****
     ->  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)
--- 1444,1452 ----
     ->  Index Only Scan using tenk1_thous_tenthous on tenk1 a
     ->  Sort
           Sort Key: b.unique2, b.unique2
+          Presorted Key: b.unique2
           ->  Index Only Scan using tenk1_unique2 on tenk1 b
! (7 rows)
  
  -- exercise rescan code path via a repeatedly-evaluated subquery
  explain (costs off)