diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c new file mode 100644 index 1247433..d2955b7 *** a/src/backend/commands/explain.c --- b/src/backend/commands/explain.c *************** static void show_grouping_set_keys(PlanS *** 91,97 **** 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, --- 91,97 ---- 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 *** 1810,1816 **** 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); --- 1810,1816 ---- 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 *** 1826,1832 **** 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); --- 1826,1832 ---- 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 *** 1850,1856 **** 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); --- 1850,1856 ---- 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 *** 1906,1912 **** if (sortnode) { show_sort_group_keys(planstate, "Sort Key", ! sortnode->numCols, sortnode->sortColIdx, sortnode->sortOperators, sortnode->collations, sortnode->nullsFirst, ancestors, es); --- 1906,1912 ---- 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 *** 1963,1969 **** /* 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); --- 1963,1969 ---- /* 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 *** 1976,1988 **** */ 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; --- 1976,1989 ---- */ 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 *** 2022,2030 **** --- 2023,2035 ---- 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 *** 2172,2183 **** --- 2177,2197 ---- 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 2587ef7..4e7c222 *** 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) *** 510,519 **** 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) *** 566,577 **** } /* ! * ExecMaterializesOutput - does a plan type materialize its output? * ! * Returns true if the plan node type is one that automatically materializes ! * its output (typically by keeping it in a tuplestore). For such plans, ! * a rescan without any parameter change will have zero startup cost and ! * very low per-tuple cost. */ bool ExecMaterializesOutput(NodeTag plantype) --- 578,589 ---- } /* ! * ExecMaterializesOutput - can a plan type materialize its output? * ! * Returns true if the plan node type can materialize its output. When this ! * function returns true, it should be rechecked for Plan node itself using ! * ExecPlanMaterializesOutput function. It might appears that despite this ! * plan type can materialize output, particular plan does not. */ bool ExecMaterializesOutput(NodeTag plantype) *************** ExecMaterializesOutput(NodeTag plantype) *** 582,587 **** --- 594,601 ---- case T_FunctionScan: case T_CteScan: case T_WorkTableScan: + return true; + case T_Sort: return true; *************** ExecMaterializesOutput(NodeTag plantype) *** 591,593 **** --- 605,630 ---- return false; } + + /* + * ExecPlanMaterializesOutput - does a plan materialize its output? + * + * Returns true if the plan node isautomatically materializes its output + * (typically by keeping it in a tuplestore). For such plans, a rescan without + * any parameter change will have zero startup cost and very low per-tuple cost. + */ + bool + ExecPlanMaterializesOutput(Plan *node) + { + if (node->type == T_Sort) + { + if (((Sort *)node)->skipCols == 0) + return true; + else + return false; + } + else + { + return ExecMaterializesOutput(node->type); + } + } diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c new file mode 100644 index ce2fc28..d2c04e5 *** a/src/backend/executor/nodeAgg.c --- b/src/backend/executor/nodeAgg.c *************** initialize_phase(AggState *aggstate, int *** 567,572 **** --- 567,573 ---- sortnode->collations, sortnode->nullsFirst, work_mem, + false, false); } *************** initialize_aggregate(AggState *aggstate, *** 645,651 **** pertrans->sortOperators, pertrans->sortCollations, pertrans->sortNullsFirst, ! work_mem, false); } /* --- 646,652 ---- 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..2369980 *** a/src/backend/executor/nodeSort.c --- b/src/backend/executor/nodeSort.c *************** *** 15,25 **** --- 15,113 ---- #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); + + /* Special case for NULL-vs-NULL, else use standard comparison */ + 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 **** --- 130,140 ---- 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,87 **** 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, --- 147,189 ---- 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 (skipCols == 0) + { + /* Regular case: no skip cols */ tuplesortstate = tuplesort_begin_heap(tupDesc, plannode->numCols, plannode->sortColIdx, *************** ExecSort(SortState *node) *** 89,132 **** 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"); --- 191,342 ---- plannode->collations, plannode->nullsFirst, work_mem, ! node->randomAccess, ! false); node->tuplesortstate = (void *) tuplesortstate; ! if (node->bounded) ! tuplesort_set_bound(tuplesortstate, node->bound); ! } ! else ! { ! /* Partial sort case */ ! if (node->tuplesortstate == NULL) ! { ! /* ! * We are going to process the first group of presorted data. ! * Initialize support structures for cmpSortSkipCols - already ! * sorted columns. ! */ ! 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, ! false, ! true); ! node->tuplesortstate = (void *) tuplesortstate; ! node->groupsCount++; ! } ! else { ! /* Next group of presorted data */ ! tuplesort_reset((Tuplesortstate *) node->tuplesortstate); ! node->groupsCount++; ! } ! ! /* Calculate remaining bound for bounded sort */ ! 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) + { + /* Regular sort case: put all tuples to the tuplesort */ if (TupIsNull(slot)) + { + node->finished = true; break; ! } tuplesort_puttupleslot(tuplesortstate, slot); + nTuples++; } + else + { + /* Partial sort case: put group of presorted data to the tuplesort */ + if (!node->prev) + { + /* First tuple */ + if (TupIsNull(slot)) + { + node->finished = true; + break; + } + else + { + node->prev = ExecCopySlotTuple(slot); + } + } + else + { + /* 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); ! /* Replace previous tuple with current one */ ! heap_freetuple(node->prev); ! node->prev = ExecCopySlotTuple(slot); ! /* ! * When skipCols are not equal then group of presorted data ! * is finished ! */ ! if (!cmp) ! break; ! } ! } ! } ! } ! ! /* ! * 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 **** --- 367,381 ---- "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 **** --- 393,404 ---- 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 **** --- 542,548 ---- 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 4f39dad..f8e1596 *** a/src/backend/nodes/copyfuncs.c --- b/src/backend/nodes/copyfuncs.c *************** _copySort(const Sort *from) *** 832,837 **** --- 832,838 ---- 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 90fecb1..24b5993 *** a/src/backend/nodes/outfuncs.c --- b/src/backend/nodes/outfuncs.c *************** _outSort(StringInfo str, const Sort *nod *** 794,799 **** --- 794,800 ---- _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 894a48f..e90a7d4 *** a/src/backend/nodes/readfuncs.c --- b/src/backend/nodes/readfuncs.c *************** _readSort(void) *** 1967,1972 **** --- 1967,1973 ---- 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 2a49639..30d7327 *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *************** cost_recursive_union(Path *runion, Path *** 1429,1434 **** --- 1429,1441 ---- * 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 *** 1455,1461 **** * 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 --- 1462,1469 ---- * 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 *** 1471,1485 **** */ 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) --- 1479,1500 ---- */ 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, *** 1509,1521 **** 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; double mergeorder = tuplesort_merge_order(sort_mem_bytes); double log_runs; double npageaccesses; --- 1524,1573 ---- 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; double mergeorder = tuplesort_merge_order(sort_mem_bytes); double log_runs; double npageaccesses; *************** cost_sort(Path *path, PlannerInfo *root, *** 1525,1531 **** * * Assume about N log2 N comparisons */ ! startup_cost += comparison_cost * tuples * LOG2(tuples); /* Disk costs */ --- 1577,1583 ---- * * Assume about N log2 N comparisons */ ! group_cost = comparison_cost * group_tuples * LOG2(group_tuples); /* Disk costs */ *************** cost_sort(Path *path, PlannerInfo *root, *** 1536,1545 **** 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 --- 1588,1597 ---- 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, *** 1547,1560 **** * 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 --- 1599,1624 ---- * 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 *** 2307,2312 **** --- 2371,2378 ---- 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 *** 2333,2338 **** --- 2399,2406 ---- 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 *** 3067,3073 **** * every time. */ if (subplan->parParam == NIL && ! ExecMaterializesOutput(nodeTag(plan))) sp_cost.startup += plan->startup_cost; else sp_cost.per_tuple += plan->startup_cost; --- 3135,3141 ---- * every time. */ if (subplan->parParam == NIL && ! ExecPlanMaterializesOutput(plan)) sp_cost.startup += plan->startup_cost; else sp_cost.per_tuple += plan->startup_cost; 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 47158f6..4421615 *** 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 *** 1062,1067 **** --- 1064,1070 ---- 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 *** 1096,1104 **** 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); --- 1099,1109 ---- 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 *** 1504,1509 **** --- 1509,1515 ---- { 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 *** 1513,1519 **** 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); --- 1519,1529 ---- 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 *** 1759,1765 **** sort_plan = (Plan *) make_sort_from_groupcols(groupClause, new_grpColIdx, ! subplan); agg_plan = (Plan *) make_agg(NIL, NIL, --- 1769,1776 ---- sort_plan = (Plan *) make_sort_from_groupcols(groupClause, new_grpColIdx, ! subplan, ! 0); agg_plan = (Plan *) make_agg(NIL, NIL, *************** create_mergejoin_plan(PlannerInfo *root, *** 3586,3593 **** */ 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; --- 3597,3610 ---- */ 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, *** 3598,3605 **** 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; --- 3615,3628 ---- 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 *** 4617,4623 **** 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, --- 4640,4647 ---- 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, *** 5139,5145 **** * nullsFirst arrays already. */ static Sort * ! make_sort(Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst) { --- 5163,5169 ---- * 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, *** 5151,5156 **** --- 5175,5181 ---- 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 *** 5477,5483 **** * '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; --- 5502,5508 ---- * '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, *** 5497,5503 **** &nullsFirst); /* Now build the Sort node */ ! return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst); } --- 5522,5528 ---- &nullsFirst); /* Now build the Sort node */ ! return make_sort(lefttree, numsortkeys, skipCols, sortColIdx, sortOperators, collations, nullsFirst); } *************** make_sort_from_sortclauses(List *sortcls *** 5540,5546 **** numsortkeys++; } ! return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst); } --- 5565,5571 ---- numsortkeys++; } ! return make_sort(lefttree, numsortkeys, 0, sortColIdx, sortOperators, collations, nullsFirst); } *************** make_sort_from_sortclauses(List *sortcls *** 5561,5567 **** static Sort * make_sort_from_groupcols(List *groupcls, AttrNumber *grpColIdx, ! Plan *lefttree) { List *sub_tlist = lefttree->targetlist; ListCell *l; --- 5586,5593 ---- 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, *** 5594,5600 **** numsortkeys++; } ! return make_sort(lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst); } --- 5620,5626 ---- 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 805aae7..094d28f *** 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 *** 344,349 **** --- 345,351 ---- 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 *** 454,464 **** 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; --- 456,470 ---- 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 174210b..2a4398c *** a/src/backend/optimizer/plan/planner.c --- b/src/backend/optimizer/plan/planner.c *************** create_grouping_paths(PlannerInfo *root, *** 3638,3651 **** 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, --- 3638,3651 ---- 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, *** 4301,4313 **** 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, --- 4301,4313 ---- 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 *** 5281,5288 **** /* 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 */ --- 5281,5289 ---- /* 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 6edefb1..cc3788f *** a/src/backend/optimizer/plan/subselect.c --- b/src/backend/optimizer/plan/subselect.c *************** build_subplan(PlannerInfo *root, Plan *p *** 838,844 **** * unnecessarily, so we don't. */ else if (splan->parParam == NIL && enable_material && ! !ExecMaterializesOutput(nodeTag(plan))) plan = materialize_finished_plan(plan); result = (Node *) splan; --- 838,844 ---- * unnecessarily, so we don't. */ else if (splan->parParam == NIL && enable_material && ! !ExecPlanMaterializesOutput(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 b714783..4b36822 *** a/src/backend/optimizer/prep/prepunion.c --- b/src/backend/optimizer/prep/prepunion.c *************** choose_hashed_setop(PlannerInfo *root, L *** 964,970 **** 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, --- 964,971 ---- 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 abb7507..52fbecc *** 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 *** 1296,1307 **** 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; --- 1337,1349 ---- 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 *** 1315,1320 **** --- 1357,1364 ---- 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 *** 1551,1557 **** /* * Estimate cost for sort+unique implementation */ ! cost_sort(&sort_path, root, NIL, subpath->total_cost, rel->rows, subpath->pathtarget->width, --- 1595,1602 ---- /* * 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, *** 2337,2342 **** --- 2382,2392 ---- 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, *** 2349,2358 **** subpath->parallel_safe; pathnode->path.parallel_workers = subpath->parallel_workers; pathnode->path.pathkeys = pathkeys; pathnode->subpath = subpath; ! cost_sort(&pathnode->path, root, pathkeys, subpath->total_cost, subpath->rows, subpath->pathtarget->width, --- 2399,2411 ---- subpath->parallel_safe; pathnode->path.parallel_workers = subpath->parallel_workers; 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 *** 2624,2630 **** 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, --- 2677,2684 ---- 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 56943f2..213d045 *** a/src/backend/utils/adt/selfuncs.c --- b/src/backend/utils/adt/selfuncs.c *************** estimate_num_groups(PlannerInfo *root, L *** 3506,3511 **** --- 3506,3547 ---- } /* + * 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 d600670..1de488e *** a/src/backend/utils/sort/tuplesort.c --- b/src/backend/utils/sort/tuplesort.c *************** struct Tuplesortstate *** 262,267 **** --- 262,272 ---- int64 allowedMem; /* total memory allowed, in bytes */ int maxTapes; /* number of tapes (Knuth's T) */ int tapeRange; /* maxTapes-1 (Knuth's P) */ + TupSortStatus maxStatus; /* maximum status reached between sort groups */ + int64 maxMem; /* maximum amount of memory used between + sort groups */ + bool maxMemOnDisk; /* is maxMem value for on-disk memory */ + MemoryContext maincontext; MemoryContext sortcontext; /* memory context holding most sort data */ MemoryContext tuplecontext; /* sub-context of sortcontext for tuple data */ LogicalTapeSet *tapeset; /* logtape.c object for tapes in a temp file */ *************** static void readtup_datum(Tuplesortstate *** 612,617 **** --- 617,625 ---- int tapenum, unsigned int len); static void movetup_datum(void *dest, void *src, unsigned int len); static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup); + static void tuplesort_free(Tuplesortstate *state, bool delete); + static void tuplesort_updatemax(Tuplesortstate *state); + /* * Special versions of qsort just for SortTuple objects. qsort_tuple() sorts *************** static Tuplesortstate * *** 646,664 **** tuplesort_begin_common(int workMem, bool randomAccess) { Tuplesortstate *state; MemoryContext sortcontext; MemoryContext tuplecontext; MemoryContext oldcontext; /* ! * Create a working memory context for this sort operation. All data ! * needed by the sort will live inside this context. */ ! sortcontext = AllocSetContextCreate(CurrentMemoryContext, "TupleSort main", ALLOCSET_DEFAULT_SIZES); /* * Caller tuple (e.g. IndexTuple) memory context. * * A dedicated child context used exclusively for caller passed tuples --- 654,683 ---- tuplesort_begin_common(int workMem, bool randomAccess) { Tuplesortstate *state; + MemoryContext maincontext; MemoryContext sortcontext; MemoryContext tuplecontext; MemoryContext oldcontext; /* ! * Memory context surviving tuplesort_reset. This memory context holds ! * data which is useful to keep while sorting multiple similar batches. */ ! maincontext = AllocSetContextCreate(CurrentMemoryContext, "TupleSort main", ALLOCSET_DEFAULT_SIZES); /* + * Create a working memory context for one sort operation. The content of + * this context is deleted by tuplesort_reset. + */ + sortcontext = AllocSetContextCreate(maincontext, + "TupleSort sort", + ALLOCSET_DEFAULT_MINSIZE, + ALLOCSET_DEFAULT_INITSIZE, + ALLOCSET_DEFAULT_MAXSIZE); + + /* * Caller tuple (e.g. IndexTuple) memory context. * * A dedicated child context used exclusively for caller passed tuples *************** tuplesort_begin_common(int workMem, bool *** 675,681 **** * Make the Tuplesortstate within the per-sort context. This way, we * don't need a separate pfree() operation for it at shutdown. */ ! oldcontext = MemoryContextSwitchTo(sortcontext); state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate)); --- 694,700 ---- * Make the Tuplesortstate within the per-sort context. This way, we * don't need a separate pfree() operation for it at shutdown. */ ! oldcontext = MemoryContextSwitchTo(maincontext); state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate)); *************** tuplesort_begin_common(int workMem, bool *** 693,698 **** --- 712,718 ---- state->availMem = state->allowedMem; state->sortcontext = sortcontext; state->tuplecontext = tuplecontext; + state->maincontext = maincontext; state->tapeset = NULL; state->memtupcount = 0; *************** tuplesort_begin_heap(TupleDesc tupDesc, *** 733,745 **** int nkeys, AttrNumber *attNums, Oid *sortOperators, Oid *sortCollations, bool *nullsFirstFlags, ! int workMem, bool randomAccess) { Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess); MemoryContext oldcontext; int i; ! oldcontext = MemoryContextSwitchTo(state->sortcontext); AssertArg(nkeys > 0); --- 753,766 ---- 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; int i; ! oldcontext = MemoryContextSwitchTo(state->maincontext); AssertArg(nkeys > 0); *************** tuplesort_begin_heap(TupleDesc tupDesc, *** 782,788 **** 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); } --- 803,809 ---- 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_begin_cluster(TupleDesc tupDes *** 813,819 **** Assert(indexRel->rd_rel->relam == BTREE_AM_OID); ! oldcontext = MemoryContextSwitchTo(state->sortcontext); #ifdef TRACE_SORT if (trace_sort) --- 834,840 ---- Assert(indexRel->rd_rel->relam == BTREE_AM_OID); ! oldcontext = MemoryContextSwitchTo(state->maincontext); #ifdef TRACE_SORT if (trace_sort) *************** tuplesort_begin_index_btree(Relation hea *** 905,911 **** MemoryContext oldcontext; int i; ! oldcontext = MemoryContextSwitchTo(state->sortcontext); #ifdef TRACE_SORT if (trace_sort) --- 926,932 ---- MemoryContext oldcontext; int i; ! oldcontext = MemoryContextSwitchTo(state->maincontext); #ifdef TRACE_SORT if (trace_sort) *************** tuplesort_begin_index_hash(Relation heap *** 979,985 **** Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess); MemoryContext oldcontext; ! oldcontext = MemoryContextSwitchTo(state->sortcontext); #ifdef TRACE_SORT if (trace_sort) --- 1000,1006 ---- Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess); MemoryContext oldcontext; ! oldcontext = MemoryContextSwitchTo(state->maincontext); #ifdef TRACE_SORT if (trace_sort) *************** tuplesort_begin_datum(Oid datumType, Oid *** 1017,1023 **** int16 typlen; bool typbyval; ! oldcontext = MemoryContextSwitchTo(state->sortcontext); #ifdef TRACE_SORT if (trace_sort) --- 1038,1044 ---- int16 typlen; bool typbyval; ! oldcontext = MemoryContextSwitchTo(state->maincontext); #ifdef TRACE_SORT if (trace_sort) *************** tuplesort_set_bound(Tuplesortstate *stat *** 1129,1144 **** } /* ! * tuplesort_end ! * ! * Release resources and clean up. * ! * NOTE: after calling this, any pointers returned by tuplesort_getXXX are ! * pointing to garbage. Be careful not to attempt to use or free such ! * pointers afterwards! */ ! void ! tuplesort_end(Tuplesortstate *state) { /* context swap probably not needed, but let's be safe */ MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext); --- 1150,1161 ---- } /* ! * tuplesort_free * ! * Internal routine for freeing resources of tuplesort. */ ! static void ! tuplesort_free(Tuplesortstate *state, bool delete) { /* context swap probably not needed, but let's be safe */ MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext); *************** tuplesort_end(Tuplesortstate *state) *** 1197,1203 **** * Free the per-sort memory context, thereby releasing all working memory, * including the Tuplesortstate struct itself. */ ! MemoryContextDelete(state->sortcontext); } /* --- 1214,1307 ---- * Free the per-sort memory context, thereby releasing all working memory, * including the Tuplesortstate struct itself. */ ! if (delete) ! { ! MemoryContextDelete(state->maincontext); ! } ! else ! { ! MemoryContextResetOnly(state->sortcontext); ! MemoryContextResetOnly(state->tuplecontext); ! } ! } ! ! /* ! * tuplesort_end ! * ! * Release resources and clean up. ! * ! * NOTE: after calling this, any pointers returned by tuplesort_getXXX are ! * pointing to garbage. Be careful not to attempt to use or free such ! * pointers afterwards! ! */ ! void ! tuplesort_end(Tuplesortstate *state) ! { ! tuplesort_free(state, true); ! } ! ! /* ! * tuplesort_updatemax ! * ! * Update maximum resource usage statistics. ! */ ! static void ! tuplesort_updatemax(Tuplesortstate *state) ! { ! int64 memUsed; ! bool memUsedOnDisk; ! ! /* ! * Note: it might seem we should provide both memory and disk usage for a ! * disk-based sort. However, the current code doesn't track memory space ! * accurately once we have begun to return tuples to the caller (since we ! * don't account for pfree's the caller is expected to do), so we cannot ! * rely on availMem in a disk sort. This does not seem worth the overhead ! * to fix. Is it worth creating an API for the memory context code to ! * tell us how much is actually used in sortcontext? ! */ ! if (state->tapeset) ! { ! memUsedOnDisk = true; ! memUsed = LogicalTapeSetBlocks(state->tapeset) * BLCKSZ; ! } ! else ! { ! memUsedOnDisk = false; ! memUsed = state->allowedMem - state->availMem; ! } ! ! state->maxStatus = Max(state->maxStatus, state->status); ! if (memUsed > state->maxMem) ! { ! state->maxMem = memUsed; ! state->maxMemOnDisk = memUsedOnDisk; ! } ! } ! ! /* ! * tuplesort_reset ! * ! * Reset the tuplesort. Reset all the data in the tuplesort, but leave the ! * meta-information in. After tuplesort_reset, tuplesort is ready to start ! * a new sort. It allows evade recreation of tuple sort (and save resources) ! * when sorting multiple small batches. ! */ ! void ! tuplesort_reset(Tuplesortstate *state) ! { ! tuplesort_updatemax(state); ! tuplesort_free(state, false); ! state->status = TSS_INITIAL; ! state->memtupcount = 0; ! state->boundUsed = false; ! state->tapeset = NULL; ! state->currentRun = 0; ! state->result_tape = -1; ! state->bounded = false; ! state->batchUsed = false; ! state->availMem = state->allowedMem; ! USEMEM(state, GetMemoryChunkSpace(state->memtuples)); } /* *************** tuplesort_get_stats(Tuplesortstate *stat *** 3574,3600 **** const char **spaceType, long *spaceUsed) { ! /* ! * Note: it might seem we should provide both memory and disk usage for a ! * disk-based sort. However, the current code doesn't track memory space ! * accurately once we have begun to return tuples to the caller (since we ! * don't account for pfree's the caller is expected to do), so we cannot ! * rely on availMem in a disk sort. This does not seem worth the overhead ! * to fix. Is it worth creating an API for the memory context code to ! * tell us how much is actually used in sortcontext? ! */ ! if (state->tapeset) ! { *spaceType = "Disk"; - *spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024); - } else - { *spaceType = "Memory"; ! *spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024; ! } ! switch (state->status) { case TSS_SORTEDINMEM: if (state->boundUsed) --- 3678,3692 ---- const char **spaceType, long *spaceUsed) { ! tuplesort_updatemax(state); ! ! if (state->maxMemOnDisk) *spaceType = "Disk"; else *spaceType = "Memory"; ! *spaceUsed = (state->maxMem + 1023) / 1024; ! switch (state->maxStatus) { case TSS_SORTEDINMEM: if (state->boundUsed) diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h new file mode 100644 index 39521ed..f172330 *** a/src/include/executor/executor.h --- b/src/include/executor/executor.h *************** extern void ExecRestrPos(PlanState *node *** 107,112 **** --- 107,113 ---- extern bool ExecSupportsMarkRestore(struct Path *pathnode); extern bool ExecSupportsBackwardScan(Plan *node); extern bool ExecMaterializesOutput(NodeTag plantype); + extern bool ExecPlanMaterializesOutput(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 e28477d..0bd2add *** a/src/include/nodes/execnodes.h --- b/src/include/nodes/execnodes.h *************** typedef struct MaterialState *** 1773,1778 **** --- 1773,1792 ---- Tuplestorestate *tuplestorestate; } MaterialState; + + /* ---------------- + * When performing sorting by multiple keys input dataset could be already + * presorted by some prefix of these keys. We call them "skip keys". + * SkipKeyData represents information about one such key. + * ---------------- + */ + typedef struct SkipKeyData + { + FmgrInfo flinfo; /* comparison function info */ + FunctionCallInfoData fcinfo; /* comparison function call info */ + OffsetNumber attno; /* attribute number in tuple */ + } SkipKeyData; + /* ---------------- * SortState information * ---------------- *************** typedef struct SortState *** 1784,1792 **** --- 1798,1811 ---- 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 */ void *tuplesortstate; /* private state of tuplesort.c */ + SkipKeyData *skipKeys; /* keys, dataset is presorted by */ + long groupsCount; /* number of groups with equal skip keys */ + 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 e2fbc7d..ffab23f *** a/src/include/nodes/plannodes.h --- b/src/include/nodes/plannodes.h *************** typedef struct Sort *** 673,678 **** --- 673,679 ---- { 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 2709cc7..76b4365 *** a/src/include/nodes/relation.h --- b/src/include/nodes/relation.h *************** typedef struct SortPath *** 1307,1312 **** --- 1307,1313 ---- { 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 2a4df2f..516357f *** 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 71d9154..1b19dd0 *** 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 44abe83..2695080 *** a/src/include/optimizer/paths.h --- b/src/include/optimizer/paths.h *************** typedef enum *** 175,187 **** 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, --- 175,189 ---- 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 8e0d317..06c0d7d *** a/src/include/utils/selfuncs.h --- b/src/include/utils/selfuncs.h *************** extern void mergejoinscansel(PlannerInfo *** 230,235 **** --- 230,238 ---- 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 45208a6..85cb8f3 *** 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 *** 995,1009 **** 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; --- 995,1012 ---- 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 d8b5b1d..752f1b6 *** 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)