diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c new file mode 100644 index 09b2eb0..65bf9fd *** a/src/backend/executor/nodeSort.c --- b/src/backend/executor/nodeSort.c *************** *** 15,25 **** --- 15,52 ---- #include "postgres.h" + #include "access/htup_details.h" #include "executor/execdebug.h" #include "executor/nodeSort.h" #include "miscadmin.h" #include "utils/tuplesort.h" + /* + * Check if first "skipCols" sort values are equal. + */ + static bool + cmpTuples(SortState *node, TupleDesc tupDesc, HeapTuple a, TupleTableSlot *b) + { + int n = ((Sort *)node->ss.ps.plan)->skipCols, i; + SortSupport sortKeys = tuplesort_get_sortkeys(node->tuplesortstate); + + for (i = 0; i < n; i++) + { + Datum datumA, datumB; + bool isnullA, isnullB; + AttrNumber attno = sortKeys[i].ssup_attno; + + datumA = heap_getattr(a, attno, tupDesc, &isnullA); + datumB = slot_getattr(b, attno, &isnullB); + + if (ApplySortComparator(datumA, isnullA, + datumB, isnullB, + &sortKeys[i])) + return false; + } + return true; + } + /* ---------------------------------------------------------------- * ExecSort *************** ExecSort(SortState *node) *** 54,131 **** 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"); --- 81,194 ---- 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) || 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. */ ! 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; ! /* ! * Put next group of tuples where skipCols" sort values are equal to ! * tuplesort. ! */ ! for (;;) ! { ! slot = ExecProcNode(outerNode); ! if (node->prev) { ! ExecStoreTuple(node->prev, node->ss.ps.ps_ResultTupleSlot, InvalidBuffer, false); ! tuplesort_puttupleslot(tuplesortstate, node->ss.ps.ps_ResultTupleSlot); if (TupIsNull(slot)) + { + node->finished = true; break; ! } ! else ! { ! bool cmp; ! cmp = cmpTuples(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; ! node->bound_Done = node->bound; ! SO1_printf("ExecSort: %s\n", "sorting done"); SO1_printf("ExecSort: %s\n", "retrieving tuple from tuplesort"); *************** ExecInitSort(Sort *node, EState *estate, *** 174,180 **** --- 237,245 ---- sortstate->bounded = false; sortstate->sort_Done = false; + sortstate->finished = false; sortstate->tuplesortstate = NULL; + sortstate->prev = NULL; /* * Miscellaneous initialization diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c new file mode 100644 index e3edcf6..d698559 *** a/src/backend/nodes/copyfuncs.c --- b/src/backend/nodes/copyfuncs.c *************** _copySort(const Sort *from) *** 735,740 **** --- 735,741 ---- 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/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c new file mode 100644 index 9c8ede6..067730f *** a/src/backend/optimizer/path/pathkeys.c --- b/src/backend/optimizer/path/pathkeys.c *************** compare_pathkeys(List *keys1, List *keys *** 312,317 **** --- 312,343 ---- } /* + * 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_fractional_path_for_pathkey *** 403,409 **** 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; } --- 429,435 ---- compare_fractional_path_costs(matched_path, path, fraction) <= 0) continue; ! if (pathkeys_common(pathkeys, path->pathkeys) != 0 && bms_is_subset(PATH_REQ_OUTER(path), required_outer)) matched_path = path; } *************** right_merge_direction(PlannerInfo *root, *** 1457,1469 **** static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) { if (root->query_pathkeys == NIL) return 0; /* no special ordering requested */ 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); --- 1483,1499 ---- static int pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys) { + int n; + if (root->query_pathkeys == NIL) return 0; /* no special ordering requested */ if (pathkeys == NIL) return 0; /* unordered path */ ! n = pathkeys_common(root->query_pathkeys, pathkeys); ! ! if (n != 0) { /* It's useful ... or at least the first N keys are */ return list_length(root->query_pathkeys); diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c new file mode 100644 index f2c122d..87dd985 *** a/src/backend/optimizer/plan/createplan.c --- b/src/backend/optimizer/plan/createplan.c *************** static MergeJoin *make_mergejoin(List *t *** 148,154 **** bool *mergenullsfirst, Plan *lefttree, Plan *righttree, JoinType jointype); ! static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples); --- 148,154 ---- bool *mergenullsfirst, Plan *lefttree, Plan *righttree, JoinType jointype); ! static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, int skipCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples); *************** create_merge_append_plan(PlannerInfo *ro *** 808,814 **** /* Now, insert a Sort node if subplan isn't sufficiently ordered */ if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) ! subplan = (Plan *) make_sort(root, subplan, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, best_path->limit_tuples); --- 808,814 ---- /* Now, insert a Sort node if subplan isn't sufficiently ordered */ if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) ! subplan = (Plan *) make_sort(root, subplan, numsortkeys, 0, sortColIdx, sortOperators, collations, nullsFirst, best_path->limit_tuples); *************** create_mergejoin_plan(PlannerInfo *root, *** 2186,2192 **** make_sort_from_pathkeys(root, outer_plan, best_path->outersortkeys, ! -1.0); outerpathkeys = best_path->outersortkeys; } else --- 2186,2192 ---- make_sort_from_pathkeys(root, outer_plan, best_path->outersortkeys, ! -1.0, 0); outerpathkeys = best_path->outersortkeys; } else *************** create_mergejoin_plan(PlannerInfo *root, *** 2199,2205 **** make_sort_from_pathkeys(root, inner_plan, best_path->innersortkeys, ! -1.0); innerpathkeys = best_path->innersortkeys; } else --- 2199,2205 ---- make_sort_from_pathkeys(root, inner_plan, best_path->innersortkeys, ! -1.0, 0); innerpathkeys = best_path->innersortkeys; } else *************** make_mergejoin(List *tlist, *** 3738,3744 **** * limit_tuples is as for cost_sort (in particular, pass -1 if no limit) */ static Sort * ! make_sort(PlannerInfo *root, Plan *lefttree, int numCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples) --- 3738,3744 ---- * limit_tuples is as for cost_sort (in particular, pass -1 if no limit) */ static Sort * ! make_sort(PlannerInfo *root, Plan *lefttree, int numCols, int skipCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples) *************** make_sort(PlannerInfo *root, Plan *leftt *** 3762,3767 **** --- 3762,3768 ---- 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 *** 4090,4096 **** */ Sort * make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, ! double limit_tuples) { int numsortkeys; AttrNumber *sortColIdx; --- 4091,4097 ---- */ Sort * make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys, ! double limit_tuples, int skipCols) { int numsortkeys; AttrNumber *sortColIdx; *************** make_sort_from_pathkeys(PlannerInfo *roo *** 4110,4116 **** &nullsFirst); /* Now build the Sort node */ ! return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, limit_tuples); } --- 4111,4117 ---- &nullsFirst); /* Now build the Sort node */ ! return make_sort(root, lefttree, numsortkeys, skipCols, sortColIdx, sortOperators, collations, nullsFirst, limit_tuples); } *************** make_sort_from_sortclauses(PlannerInfo * *** 4153,4159 **** numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } --- 4154,4160 ---- numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, 0, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } *************** make_sort_from_groupcols(PlannerInfo *ro *** 4208,4214 **** numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } --- 4209,4215 ---- numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, 0, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c new file mode 100644 index 6670794..94cb114 *** a/src/backend/optimizer/plan/planner.c --- b/src/backend/optimizer/plan/planner.c *************** grouping_planner(PlannerInfo *root, doub *** 1360,1367 **** Path sort_path; /* dummy for result of cost_sort */ if (root->query_pathkeys == NIL || ! pathkeys_contained_in(root->query_pathkeys, ! cheapest_path->pathkeys)) { /* No sort needed for cheapest path */ sort_path.startup_cost = cheapest_path->startup_cost; --- 1360,1367 ---- Path sort_path; /* dummy for result of cost_sort */ if (root->query_pathkeys == NIL || ! pathkeys_common(root->query_pathkeys, ! cheapest_path->pathkeys) != 0) { /* No sort needed for cheapest path */ sort_path.startup_cost = cheapest_path->startup_cost; *************** grouping_planner(PlannerInfo *root, doub *** 1721,1727 **** sort_plan = make_sort_from_pathkeys(root, result_plan, window_pathkeys, ! -1.0); if (!pathkeys_contained_in(window_pathkeys, current_pathkeys)) { --- 1721,1727 ---- sort_plan = make_sort_from_pathkeys(root, result_plan, window_pathkeys, ! -1.0, 0); if (!pathkeys_contained_in(window_pathkeys, current_pathkeys)) { *************** grouping_planner(PlannerInfo *root, doub *** 1881,1887 **** result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, current_pathkeys, ! -1.0); } result_plan = (Plan *) make_unique(result_plan, --- 1881,1887 ---- result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, current_pathkeys, ! -1.0, 0); } result_plan = (Plan *) make_unique(result_plan, *************** grouping_planner(PlannerInfo *root, doub *** 1897,1908 **** */ if (parse->sortClause) { ! if (!pathkeys_contained_in(root->sort_pathkeys, current_pathkeys)) { result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, root->sort_pathkeys, ! limit_tuples); current_pathkeys = root->sort_pathkeys; } } --- 1897,1912 ---- */ if (parse->sortClause) { ! int common = pathkeys_common(root->sort_pathkeys, current_pathkeys); ! int sortLength = list_length(root->sort_pathkeys); ! ! if (common <= sortLength) { result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, root->sort_pathkeys, ! limit_tuples, ! common); current_pathkeys = root->sort_pathkeys; } } diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c new file mode 100644 index ea8af9f..29b90f2 *** a/src/backend/utils/sort/tuplesort.c --- b/src/backend/utils/sort/tuplesort.c *************** free_sort_tuple(Tuplesortstate *state, S *** 3455,3457 **** --- 3455,3464 ---- FREEMEM(state, GetMemoryChunkSpace(stup->tuple)); pfree(stup->tuple); } + + SortSupport + tuplesort_get_sortkeys(Tuplesortstate *state) + { + return state->sortKeys; + } + diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h new file mode 100644 index 5a40347..3723a18 *** a/src/include/nodes/execnodes.h --- b/src/include/nodes/execnodes.h *************** typedef struct SortState *** 1663,1670 **** --- 1663,1672 ---- int64 bound; /* if bounded, how many tuples are needed */ bool sort_Done; /* sort completed yet? */ bool bounded_Done; /* value of bounded we did the sort with */ + bool finished; int64 bound_Done; /* value of bound we did the sort with */ void *tuplesortstate; /* private state of tuplesort.c */ + HeapTuple prev; } SortState; /* --------------------- diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h new file mode 100644 index 101e22c..28b871e *** a/src/include/nodes/plannodes.h --- b/src/include/nodes/plannodes.h *************** typedef struct Sort *** 582,587 **** --- 582,588 ---- { Plan plan; int numCols; /* number of sort-key columns */ + int skipCols; AttrNumber *sortColIdx; /* their indexes in the target list */ Oid *sortOperators; /* OIDs of operators to sort them by */ Oid *collations; /* OIDs of collations */ diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h new file mode 100644 index 999adaa..7c09301 *** a/src/include/optimizer/paths.h --- b/src/include/optimizer/paths.h *************** typedef enum *** 157,162 **** --- 157,163 ---- 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); diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h new file mode 100644 index ba7ae7c..b46d71c *** a/src/include/optimizer/planmain.h --- b/src/include/optimizer/planmain.h *************** extern RecursiveUnion *make_recursive_un *** 50,56 **** Plan *lefttree, Plan *righttree, int wtParam, List *distinctList, long numGroups); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, ! List *pathkeys, double limit_tuples); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree); extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls, --- 50,56 ---- Plan *lefttree, Plan *righttree, int wtParam, List *distinctList, long numGroups); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, ! List *pathkeys, double limit_tuples, int skipCols); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree); extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls, diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h new file mode 100644 index 25fa6de..267a988 *** a/src/include/utils/tuplesort.h --- b/src/include/utils/tuplesort.h *************** *** 24,29 **** --- 24,30 ---- #include "executor/tuptable.h" #include "fmgr.h" #include "utils/relcache.h" + #include "utils/sortsupport.h" /* Tuplesortstate is an opaque type whose details are not known outside *************** extern void tuplesort_get_stats(Tuplesor *** 108,113 **** --- 109,116 ---- extern int tuplesort_merge_order(int64 allowedMem); + extern SortSupport tuplesort_get_sortkeys(Tuplesortstate *state); + /* * These routines may only be called if randomAccess was specified 'true'. * Likewise, backwards scan in gettuple/getdatum is only allowed if