diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c new file mode 100644 index 9969a25..07cb66d *** a/src/backend/commands/explain.c --- b/src/backend/commands/explain.c *************** static void show_agg_keys(AggState *asta *** 81,87 **** 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, List *ancestors, ExplainState *es); static void show_sort_info(SortState *sortstate, ExplainState *es); static void show_hash_info(HashState *hashstate, ExplainState *es); --- 81,87 ---- 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, List *ancestors, ExplainState *es); static void show_sort_info(SortState *sortstate, ExplainState *es); static void show_hash_info(HashState *hashstate, ExplainState *es); *************** ExplainNode(PlanState *planstate, List * *** 905,911 **** pname = sname = "Materialize"; break; case T_Sort: ! pname = sname = "Sort"; break; case T_Group: pname = sname = "Group"; --- 905,914 ---- pname = sname = "Materialize"; break; case T_Sort: ! if (((Sort *) plan)->skipCols > 0) ! pname = sname = "Partial sort"; ! else ! pname = sname = "Sort"; break; case T_Group: pname = sname = "Group"; *************** show_sort_keys(SortState *sortstate, Lis *** 1705,1711 **** Sort *plan = (Sort *) sortstate->ss.ps.plan; show_sort_group_keys((PlanState *) sortstate, "Sort Key", ! plan->numCols, plan->sortColIdx, ancestors, es); } --- 1708,1714 ---- Sort *plan = (Sort *) sortstate->ss.ps.plan; show_sort_group_keys((PlanState *) sortstate, "Sort Key", ! plan->numCols, plan->skipCols, plan->sortColIdx, ancestors, es); } *************** show_merge_append_keys(MergeAppendState *** 1719,1725 **** MergeAppend *plan = (MergeAppend *) mstate->ps.plan; show_sort_group_keys((PlanState *) mstate, "Sort Key", ! plan->numCols, plan->sortColIdx, ancestors, es); } --- 1722,1728 ---- MergeAppend *plan = (MergeAppend *) mstate->ps.plan; show_sort_group_keys((PlanState *) mstate, "Sort Key", ! plan->numCols, 0, plan->sortColIdx, ancestors, es); } *************** show_agg_keys(AggState *astate, List *an *** 1737,1743 **** /* The key columns refer to the tlist of the child plan */ ancestors = lcons(astate, ancestors); show_sort_group_keys(outerPlanState(astate), "Group Key", ! plan->numCols, plan->grpColIdx, ancestors, es); ancestors = list_delete_first(ancestors); } --- 1740,1746 ---- /* The key columns refer to the tlist of the child plan */ ancestors = lcons(astate, ancestors); show_sort_group_keys(outerPlanState(astate), "Group Key", ! plan->numCols, 0, plan->grpColIdx, ancestors, es); ancestors = list_delete_first(ancestors); } *************** show_group_keys(GroupState *gstate, List *** 1755,1761 **** /* 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, ancestors, es); ancestors = list_delete_first(ancestors); } --- 1758,1764 ---- /* 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, ancestors, es); ancestors = list_delete_first(ancestors); } *************** show_group_keys(GroupState *gstate, List *** 1765,1777 **** * as arrays of targetlist indexes */ static void ! show_sort_group_keys(PlanState *planstate, const char *qlabel, ! int nkeys, AttrNumber *keycols, List *ancestors, ExplainState *es) { Plan *plan = planstate->plan; List *context; ! List *result = NIL; bool useprefix; int keyno; char *exprstr; --- 1768,1781 ---- * as arrays of targetlist indexes */ static void ! show_sort_group_keys(PlanState *planstate, const char *qlabel, ! int nkeys, int nPresortedKeys, AttrNumber *keycols, List *ancestors, ExplainState *es) { Plan *plan = planstate->plan; List *context; ! List *resultSort = NIL; ! List *resultPresorted = NIL; bool useprefix; int keyno; char *exprstr; *************** show_sort_group_keys(PlanState *planstat *** 1798,1807 **** /* Deparse the expression, showing any top-level cast */ exprstr = deparse_expression((Node *) target->expr, context, useprefix, true); ! result = lappend(result, exprstr); } ! ExplainPropertyList(qlabel, result, es); } /* --- 1802,1816 ---- /* Deparse the expression, showing any top-level cast */ exprstr = deparse_expression((Node *) target->expr, context, useprefix, true); ! ! if (keyno < nPresortedKeys) ! resultPresorted = lappend(resultPresorted, exprstr); ! resultSort = lappend(resultSort, exprstr); } ! ExplainPropertyList(qlabel, resultSort, es); ! if (nPresortedKeys > 0) ! ExplainPropertyList("Presorted Key", resultPresorted, es); } /* diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c new file mode 100644 index 09b2eb0..02dcd7a *** 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 + cmpSortSkipCols(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) *** 42,47 **** --- 69,78 ---- ScanDirection dir; Tuplesortstate *tuplesortstate; TupleTableSlot *slot; + Sort *plannode = (Sort *) node->ss.ps.plan; + PlanState *outerNode; + TupleDesc tupDesc; + int skipCols = plannode->skipCols; /* * get state info from node *************** 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"); --- 85,205 ---- 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. */ ! SO1_printf("ExecSort: %s\n", ! "sorting subplan"); ! /* ! * Want to scan subplan in the forward direction while creating the ! * sorted data. ! */ ! estate->es_direction = ForwardScanDirection; ! /* ! * Initialize tuplesort module. ! */ ! SO1_printf("ExecSort: %s\n", ! "calling tuplesort_begin"); ! outerNode = outerPlanState(node); ! tupDesc = ExecGetResultType(outerNode); ! if (node->tuplesortstate != NULL) ! tuplesort_end((Tuplesortstate *) node->tuplesortstate); ! 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 (skipCols == 0) { if (TupIsNull(slot)) + { + node->finished = true; break; ! } tuplesort_puttupleslot(tuplesortstate, slot); } + else 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 = cmpSortSkipCols(node, tupDesc, node->prev, slot); ! node->prev = ExecCopySlotTuple(slot); ! if (!cmp) ! break; ! } ! } ! else ! { ! if (TupIsNull(slot)) ! { ! node->finished = true; ! break; ! } ! else ! { ! node->prev = ExecCopySlotTuple(slot); ! } ! } ! } ! /* ! * Complete the sort. ! */ ! tuplesort_performsort(tuplesortstate); ! /* ! * restore to user specified direction ! */ ! estate->es_direction = dir; ! ! /* ! * finally set the sorted flag to true ! */ ! node->sort_Done = true; ! node->bounded_Done = node->bounded; ! 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 **** --- 248,256 ---- 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 e4184c5..b41213a *** 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/costsize.c b/src/backend/optimizer/path/costsize.c new file mode 100644 index 50f0852..1a38407 *** a/src/backend/optimizer/path/costsize.c --- b/src/backend/optimizer/path/costsize.c *************** cost_recursive_union(Plan *runion, Plan *** 1281,1295 **** */ 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) --- 1281,1302 ---- */ 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, *** 1319,1331 **** output_bytes = input_bytes; } ! if (output_bytes > sort_mem_bytes) { /* * We'll have to use a disk-based sort of all the tuples */ ! double npages = ceil(input_bytes / BLCKSZ); ! double nruns = (input_bytes / sort_mem_bytes) * 0.5; double mergeorder = tuplesort_merge_order(sort_mem_bytes); double log_runs; double npageaccesses; --- 1326,1367 ---- output_bytes = input_bytes; } ! if (presorted_keys > 0) ! { ! List *groupExprs = NIL; ! ListCell *l; ! int i = 0; ! ! foreach(l, pathkeys) ! { ! PathKey *key = (PathKey *)lfirst(l); ! EquivalenceMember *member = (EquivalenceMember *) ! lfirst(list_head(key->pk_eclass->ec_members)); ! ! groupExprs = lappend(groupExprs, member->em_expr); ! ! i++; ! if (i >= presorted_keys) ! break; ! } ! ! num_groups = estimate_num_groups(root, groupExprs, tuples); ! } ! else ! { ! num_groups = 1.0; ! } ! ! group_input_bytes = input_bytes / num_groups; ! group_tuples = tuples / num_groups; ! ! if (output_bytes > sort_mem_bytes && group_input_bytes > sort_mem_bytes) { /* * We'll have to use a disk-based sort of all the tuples */ ! double npages = ceil(group_input_bytes / BLCKSZ); ! double nruns = (group_input_bytes / sort_mem_bytes) * 0.5; double mergeorder = tuplesort_merge_order(sort_mem_bytes); double log_runs; double npageaccesses; *************** cost_sort(Path *path, PlannerInfo *root, *** 1335,1341 **** * * Assume about N log2 N comparisons */ ! startup_cost += comparison_cost * tuples * LOG2(tuples); /* Disk costs */ --- 1371,1377 ---- * * Assume about N log2 N comparisons */ ! group_cost = comparison_cost * group_tuples * LOG2(group_tuples); /* Disk costs */ *************** cost_sort(Path *path, PlannerInfo *root, *** 1346,1355 **** 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 --- 1382,1391 ---- 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, *** 1357,1368 **** * 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); } /* --- 1393,1404 ---- * 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); } /* *************** cost_sort(Path *path, PlannerInfo *root, *** 1373,1380 **** --- 1409,1423 ---- * here --- the upper LIMIT will pro-rate the run cost so we'd be double * counting the LIMIT otherwise. */ + startup_cost += group_cost; + rest_cost = (num_groups * (output_tuples / tuples) - 1.0) * group_cost; + if (rest_cost > 0.0) + run_cost += rest_cost; run_cost += cpu_operator_cost * tuples; + startup_cost += input_run_cost / num_groups; + run_cost += input_run_cost * ((num_groups - 1.0) / num_groups); + path->startup_cost = startup_cost; path->total_cost = startup_cost + run_cost; } *************** initial_cost_mergejoin(PlannerInfo *root *** 2075,2080 **** --- 2118,2125 ---- 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->parent->width, *************** initial_cost_mergejoin(PlannerInfo *root *** 2101,2106 **** --- 2146,2153 ---- 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->parent->width, diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c new file mode 100644 index 5b477e5..5909dfe *** a/src/backend/optimizer/path/joinpath.c --- b/src/backend/optimizer/path/joinpath.c *************** sort_inner_and_outer(PlannerInfo *root, *** 662,668 **** cur_mergeclauses = find_mergeclauses_for_pathkeys(root, outerkeys, true, ! mergeclause_list); /* Should have used them all... */ Assert(list_length(cur_mergeclauses) == list_length(mergeclause_list)); --- 662,670 ---- cur_mergeclauses = find_mergeclauses_for_pathkeys(root, outerkeys, true, ! mergeclause_list, ! NULL, ! NULL); /* Should have used them all... */ Assert(list_length(cur_mergeclauses) == list_length(mergeclause_list)); *************** match_unsorted_outer(PlannerInfo *root, *** 832,837 **** --- 834,840 ---- List *mergeclauses; List *innersortkeys; List *trialsortkeys; + List *outersortkeys; Path *cheapest_startup_inner; Path *cheapest_total_inner; int num_sortkeys; *************** match_unsorted_outer(PlannerInfo *root, *** 937,943 **** mergeclauses = find_mergeclauses_for_pathkeys(root, outerpath->pathkeys, true, ! mergeclause_list); /* * Done with this outer path if no chance for a mergejoin. --- 940,948 ---- mergeclauses = find_mergeclauses_for_pathkeys(root, outerpath->pathkeys, true, ! mergeclause_list, ! joinrel, ! &outersortkeys); /* * Done with this outer path if no chance for a mergejoin. *************** match_unsorted_outer(PlannerInfo *root, *** 961,967 **** /* Compute the required ordering of the inner path */ innersortkeys = make_inner_pathkeys_for_merge(root, mergeclauses, ! outerpath->pathkeys); /* * Generate a mergejoin on the basis of sorting the cheapest inner. --- 966,972 ---- /* Compute the required ordering of the inner path */ innersortkeys = make_inner_pathkeys_for_merge(root, mergeclauses, ! outersortkeys); /* * Generate a mergejoin on the basis of sorting the cheapest inner. *************** match_unsorted_outer(PlannerInfo *root, *** 980,986 **** restrictlist, merge_pathkeys, mergeclauses, ! NIL, innersortkeys); /* Can't do anything else if inner path needs to be unique'd */ --- 985,991 ---- restrictlist, merge_pathkeys, mergeclauses, ! outersortkeys, innersortkeys); /* Can't do anything else if inner path needs to be unique'd */ *************** match_unsorted_outer(PlannerInfo *root, *** 1038,1044 **** for (sortkeycnt = num_sortkeys; sortkeycnt > 0; sortkeycnt--) { Path *innerpath; - List *newclauses = NIL; /* * Look for an inner path ordered well enough for the first --- 1043,1048 ---- *************** match_unsorted_outer(PlannerInfo *root, *** 1055,1073 **** compare_path_costs(innerpath, cheapest_total_inner, TOTAL_COST) < 0)) { - /* Found a cheap (or even-cheaper) sorted path */ - /* Select the right mergeclauses, if we didn't already */ - if (sortkeycnt < num_sortkeys) - { - newclauses = - find_mergeclauses_for_pathkeys(root, - trialsortkeys, - false, - mergeclauses); - Assert(newclauses != NIL); - } - else - newclauses = mergeclauses; try_mergejoin_path(root, joinrel, jointype, --- 1059,1064 ---- *************** match_unsorted_outer(PlannerInfo *root, *** 1078,1086 **** innerpath, restrictlist, merge_pathkeys, ! newclauses, ! NIL, ! NIL); cheapest_total_inner = innerpath; } /* Same on the basis of cheapest startup cost ... */ --- 1069,1077 ---- innerpath, restrictlist, merge_pathkeys, ! mergeclauses, ! outersortkeys, ! innersortkeys); cheapest_total_inner = innerpath; } /* Same on the basis of cheapest startup cost ... */ *************** match_unsorted_outer(PlannerInfo *root, *** 1096,1119 **** /* Found a cheap (or even-cheaper) sorted path */ if (innerpath != cheapest_total_inner) { - /* - * Avoid rebuilding clause list if we already made one; - * saves memory in big join trees... - */ - if (newclauses == NIL) - { - if (sortkeycnt < num_sortkeys) - { - newclauses = - find_mergeclauses_for_pathkeys(root, - trialsortkeys, - false, - mergeclauses); - Assert(newclauses != NIL); - } - else - newclauses = mergeclauses; - } try_mergejoin_path(root, joinrel, jointype, --- 1087,1092 ---- *************** match_unsorted_outer(PlannerInfo *root, *** 1124,1132 **** innerpath, restrictlist, merge_pathkeys, ! newclauses, ! NIL, ! NIL); } cheapest_startup_inner = innerpath; } --- 1097,1105 ---- innerpath, restrictlist, merge_pathkeys, ! mergeclauses, ! outersortkeys, ! innersortkeys); } cheapest_startup_inner = innerpath; } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c new file mode 100644 index 9c8ede6..63c0b03 *** 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 PathKey *make_canonical_pathkey(PlannerInfo *root, *************** compare_pathkeys(List *keys1, List *keys *** 312,317 **** --- 313,344 ---- } /* + * 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,373 **** --- 395,421 ---- return matched_path; } + static int + compare_bifractional_path_costs(Path *path1, Path *path2, + double fraction1, double fraction2) + { + Cost cost1, + cost2; + + if (fraction1 <= 0.0 || fraction1 >= 1.0 || + fraction2 <= 0.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; + } + /* * get_cheapest_fractional_path_for_pathkeys * Find the cheapest path (for retrieving a specified fraction of all *************** Path * *** 386,411 **** 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; } --- 434,508 ---- get_cheapest_fractional_path_for_pathkeys(List *paths, List *pathkeys, Relids required_outer, ! double fraction, ! PlannerInfo *root, ! double tuples) { Path *matched_path = NULL; + int matched_n_common_pathkeys = 0, + costs_cmp, n_common_pathkeys, + n_pathkeys = list_length(pathkeys); ListCell *l; + List *groupExprs = NIL; + double *num_groups, matched_fraction; + int i; + + i = 0; + num_groups = (double *)palloc(sizeof(double) * list_length(pathkeys)); + foreach(l, pathkeys) + { + PathKey *key = (PathKey *)lfirst(l); + EquivalenceMember *member = (EquivalenceMember *) + lfirst(list_head(key->pk_eclass->ec_members)); + + groupExprs = lappend(groupExprs, member->em_expr); + + num_groups[i] = estimate_num_groups(root, groupExprs, tuples); + i++; + } + foreach(l, paths) { Path *path = (Path *) lfirst(l); + double current_fraction; + + n_common_pathkeys = pathkeys_common(pathkeys, path->pathkeys); + if (n_common_pathkeys < matched_n_common_pathkeys || + n_common_pathkeys == 0) + continue; + + current_fraction = fraction; + if (n_common_pathkeys < n_pathkeys) + { + current_fraction += 1.0 / num_groups[n_common_pathkeys - 1]; + current_fraction = Max(current_fraction, 1.0); + } /* * Since cost comparison is a lot cheaper than pathkey comparison, do * that first. (XXX is that still true?) */ ! if (matched_path != NULL) ! { ! costs_cmp = compare_bifractional_path_costs(matched_path, path, ! matched_fraction, current_fraction); ! } ! else ! { ! costs_cmp = 1; ! } ! if (( ! n_common_pathkeys > matched_n_common_pathkeys ! || (n_common_pathkeys == matched_n_common_pathkeys ! && 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; } *************** List * *** 965,974 **** find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, ! List *restrictinfos) { List *mergeclauses = NIL; ListCell *i; /* make sure we have eclasses cached in the clauses */ foreach(i, restrictinfos) --- 1062,1077 ---- find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, ! List *restrictinfos, ! RelOptInfo *joinrel, ! List **outersortkeys) { List *mergeclauses = NIL; ListCell *i; + bool *used = (bool *)palloc0(sizeof(bool) * list_length(restrictinfos)); + int k; + List *unusedRestrictinfos = NIL; + List *usedPathkeys = NIL; /* make sure we have eclasses cached in the clauses */ foreach(i, restrictinfos) *************** find_mergeclauses_for_pathkeys(PlannerIn *** 1021,1026 **** --- 1124,1130 ---- * deal with the case in create_mergejoin_plan(). *---------- */ + k = 0; foreach(j, restrictinfos) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(j); *************** find_mergeclauses_for_pathkeys(PlannerIn *** 1033,1039 **** --- 1137,1147 ---- clause_ec = rinfo->outer_is_left ? rinfo->right_ec : rinfo->left_ec; if (clause_ec == pathkey_ec) + { matched_restrictinfos = lappend(matched_restrictinfos, rinfo); + used[k] = true; + } + k++; } /* *************** find_mergeclauses_for_pathkeys(PlannerIn *** 1044,1049 **** --- 1152,1159 ---- if (matched_restrictinfos == NIL) break; + usedPathkeys = lappend(usedPathkeys, pathkey); + /* * If we did find usable mergeclause(s) for this sort-key position, * add them to result list. *************** find_mergeclauses_for_pathkeys(PlannerIn *** 1051,1056 **** --- 1161,1201 ---- mergeclauses = list_concat(mergeclauses, matched_restrictinfos); } + if (outersortkeys) + { + List *addPathkeys, *addMergeclauses; + + *outersortkeys = pathkeys; + + if (!mergeclauses) + return mergeclauses; + + k = 0; + foreach(i, restrictinfos) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(i); + if (!used[k]) + unusedRestrictinfos = lappend(unusedRestrictinfos, rinfo); + k++; + } + + if (!unusedRestrictinfos) + return mergeclauses; + + addPathkeys = select_outer_pathkeys_for_merge(root, + unusedRestrictinfos, joinrel); + + if (!addPathkeys) + return mergeclauses; + + addMergeclauses = find_mergeclauses_for_pathkeys(root, + addPathkeys, true, unusedRestrictinfos, NULL, NULL); + + *outersortkeys = list_concat(usedPathkeys, addPathkeys); + mergeclauses = list_concat(mergeclauses, addMergeclauses); + + } + return mergeclauses; } *************** right_merge_direction(PlannerInfo *root, *** 1457,1472 **** 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); } return 0; /* path ordering not useful */ --- 1602,1621 ---- 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 n; } return 0; /* path ordering not useful */ diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c new file mode 100644 index f2c122d..a300342 *** a/src/backend/optimizer/plan/createplan.c --- b/src/backend/optimizer/plan/createplan.c *************** static MergeJoin *make_mergejoin(List *t *** 149,154 **** --- 149,155 ---- Plan *lefttree, Plan *righttree, JoinType jointype); static Sort *make_sort(PlannerInfo *root, Plan *lefttree, int numCols, + List *pathkeys, int skipCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples); *************** create_merge_append_plan(PlannerInfo *ro *** 774,779 **** --- 775,781 ---- Oid *sortOperators; Oid *collations; bool *nullsFirst; + int n_common_pathkeys; /* Build the child plan */ subplan = create_plan_recurse(root, subpath); *************** create_merge_append_plan(PlannerInfo *ro *** 807,814 **** numsortkeys * sizeof(bool)) == 0); /* Now, insert a Sort node if subplan isn't sufficiently ordered */ ! if (!pathkeys_contained_in(pathkeys, subpath->pathkeys)) subplan = (Plan *) make_sort(root, subplan, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, best_path->limit_tuples); --- 809,818 ---- numsortkeys * sizeof(bool)) == 0); /* Now, insert a Sort node if subplan isn't sufficiently ordered */ ! n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys); ! if (n_common_pathkeys < list_length(pathkeys)) subplan = (Plan *) make_sort(root, subplan, numsortkeys, + pathkeys, n_common_pathkeys, sortColIdx, sortOperators, collations, nullsFirst, best_path->limit_tuples); *************** create_mergejoin_plan(PlannerInfo *root, *** 2184,2192 **** disuse_physical_tlist(root, outer_plan, best_path->jpath.outerjoinpath); outer_plan = (Plan *) make_sort_from_pathkeys(root, ! outer_plan, ! best_path->outersortkeys, ! -1.0); outerpathkeys = best_path->outersortkeys; } else --- 2188,2198 ---- disuse_physical_tlist(root, outer_plan, best_path->jpath.outerjoinpath); outer_plan = (Plan *) make_sort_from_pathkeys(root, ! outer_plan, ! best_path->outersortkeys, ! -1.0, ! pathkeys_common(best_path->outersortkeys, ! best_path->jpath.outerjoinpath->pathkeys)); outerpathkeys = best_path->outersortkeys; } else *************** create_mergejoin_plan(PlannerInfo *root, *** 2197,2205 **** disuse_physical_tlist(root, inner_plan, best_path->jpath.innerjoinpath); inner_plan = (Plan *) make_sort_from_pathkeys(root, ! inner_plan, ! best_path->innersortkeys, ! -1.0); innerpathkeys = best_path->innersortkeys; } else --- 2203,2213 ---- disuse_physical_tlist(root, inner_plan, best_path->jpath.innerjoinpath); inner_plan = (Plan *) make_sort_from_pathkeys(root, ! inner_plan, ! best_path->innersortkeys, ! -1.0, ! pathkeys_common(best_path->innersortkeys, ! best_path->jpath.innerjoinpath->pathkeys)); innerpathkeys = best_path->innersortkeys; } else *************** make_mergejoin(List *tlist, *** 3739,3744 **** --- 3747,3753 ---- */ static Sort * make_sort(PlannerInfo *root, Plan *lefttree, int numCols, + List *pathkeys, int skipCols, AttrNumber *sortColIdx, Oid *sortOperators, Oid *collations, bool *nullsFirst, double limit_tuples) *************** make_sort(PlannerInfo *root, Plan *leftt *** 3748,3754 **** Path sort_path; /* dummy for result of cost_sort */ copy_plan_costsize(plan, lefttree); /* only care about copying size */ ! cost_sort(&sort_path, root, NIL, lefttree->total_cost, lefttree->plan_rows, lefttree->plan_width, --- 3757,3764 ---- Path sort_path; /* dummy for result of cost_sort */ copy_plan_costsize(plan, lefttree); /* only care about copying size */ ! cost_sort(&sort_path, root, pathkeys, skipCols, ! lefttree->startup_cost, lefttree->total_cost, lefttree->plan_rows, lefttree->plan_width, *************** make_sort(PlannerInfo *root, Plan *leftt *** 3762,3767 **** --- 3772,3778 ---- 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; --- 4101,4107 ---- */ 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); } --- 4121,4127 ---- &nullsFirst); /* Now build the Sort node */ ! return make_sort(root, lefttree, numsortkeys, pathkeys, skipCols, sortColIdx, sortOperators, collations, nullsFirst, limit_tuples); } *************** make_sort_from_sortclauses(PlannerInfo * *** 4153,4159 **** numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } --- 4164,4170 ---- numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, NIL, 0, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } *************** Sort * *** 4175,4181 **** make_sort_from_groupcols(PlannerInfo *root, List *groupcls, AttrNumber *grpColIdx, ! Plan *lefttree) { List *sub_tlist = lefttree->targetlist; ListCell *l; --- 4186,4193 ---- make_sort_from_groupcols(PlannerInfo *root, List *groupcls, AttrNumber *grpColIdx, ! Plan *lefttree, ! List *pathkeys, int skipCols) { List *sub_tlist = lefttree->targetlist; ListCell *l; *************** make_sort_from_groupcols(PlannerInfo *ro *** 4208,4214 **** numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } --- 4220,4226 ---- numsortkeys++; } ! return make_sort(root, lefttree, numsortkeys, pathkeys, skipCols, sortColIdx, sortOperators, collations, nullsFirst, -1.0); } diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c new file mode 100644 index 53fc238..4675402 *** a/src/backend/optimizer/plan/planagg.c --- b/src/backend/optimizer/plan/planagg.c *************** build_minmax_path(PlannerInfo *root, Min *** 494,500 **** get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist, subroot->query_pathkeys, NULL, ! path_fraction); if (!sorted_path) return false; --- 494,502 ---- get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist, subroot->query_pathkeys, NULL, ! path_fraction, ! subroot, ! final_rel->rows); 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 1da4b2f..df5563a *** a/src/backend/optimizer/plan/planner.c --- b/src/backend/optimizer/plan/planner.c *************** grouping_planner(PlannerInfo *root, doub *** 1349,1355 **** get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist, root->query_pathkeys, NULL, ! tuple_fraction); /* Don't consider same path in both guises; just wastes effort */ if (sorted_path == cheapest_path) --- 1349,1357 ---- get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist, root->query_pathkeys, NULL, ! tuple_fraction, ! root, ! path_rows); /* Don't consider same path in both guises; just wastes effort */ if (sorted_path == cheapest_path) *************** grouping_planner(PlannerInfo *root, doub *** 1365,1374 **** if (sorted_path) { Path sort_path; /* dummy for result of cost_sort */ if (root->query_pathkeys == NIL || ! pathkeys_contained_in(root->query_pathkeys, ! cheapest_path->pathkeys)) { /* No sort needed for cheapest path */ sort_path.startup_cost = cheapest_path->startup_cost; --- 1367,1380 ---- if (sorted_path) { Path sort_path; /* dummy for result of cost_sort */ + Path partial_sort_path; /* dummy for result of cost_sort */ + int n_common_pathkeys; + + n_common_pathkeys = pathkeys_common(root->query_pathkeys, + cheapest_path->pathkeys); if (root->query_pathkeys == NIL || ! n_common_pathkeys == list_length(root->query_pathkeys)) { /* No sort needed for cheapest path */ sort_path.startup_cost = cheapest_path->startup_cost; *************** grouping_planner(PlannerInfo *root, doub *** 1378,1389 **** { /* Figure cost for sorting */ cost_sort(&sort_path, root, root->query_pathkeys, cheapest_path->total_cost, path_rows, path_width, 0.0, work_mem, root->limit_tuples); } ! if (compare_fractional_path_costs(sorted_path, &sort_path, tuple_fraction) > 0) { /* Presorted path is a loser */ --- 1384,1418 ---- { /* Figure cost for sorting */ cost_sort(&sort_path, root, root->query_pathkeys, + n_common_pathkeys, + cheapest_path->startup_cost, cheapest_path->total_cost, path_rows, path_width, 0.0, work_mem, root->limit_tuples); } ! n_common_pathkeys = pathkeys_common(root->query_pathkeys, ! sorted_path->pathkeys); ! ! if (root->query_pathkeys == NIL || ! n_common_pathkeys == list_length(root->query_pathkeys)) ! { ! /* No sort needed for cheapest path */ ! partial_sort_path.startup_cost = sorted_path->startup_cost; ! partial_sort_path.total_cost = sorted_path->total_cost; ! } ! else ! { ! /* Figure cost for sorting */ ! cost_sort(&partial_sort_path, root, root->query_pathkeys, ! n_common_pathkeys, ! sorted_path->startup_cost, ! sorted_path->total_cost, ! path_rows, path_width, ! 0.0, work_mem, root->limit_tuples); ! } ! ! if (compare_fractional_path_costs(&partial_sort_path, &sort_path, tuple_fraction) > 0) { /* Presorted path is a loser */ *************** grouping_planner(PlannerInfo *root, doub *** 1464,1476 **** * results. */ bool need_sort_for_grouping = false; result_plan = create_plan(root, best_path); current_pathkeys = best_path->pathkeys; /* Detect if we'll need an explicit sort for grouping */ if (parse->groupClause && !use_hashed_grouping && ! !pathkeys_contained_in(root->group_pathkeys, current_pathkeys)) { need_sort_for_grouping = true; --- 1493,1508 ---- * results. */ bool need_sort_for_grouping = false; + int n_common_pathkeys_grouping; result_plan = create_plan(root, best_path); current_pathkeys = best_path->pathkeys; /* Detect if we'll need an explicit sort for grouping */ + n_common_pathkeys_grouping = pathkeys_common(root->group_pathkeys, + current_pathkeys); if (parse->groupClause && !use_hashed_grouping && ! n_common_pathkeys_grouping < list_length(root->group_pathkeys)) { need_sort_for_grouping = true; *************** grouping_planner(PlannerInfo *root, doub *** 1564,1570 **** make_sort_from_groupcols(root, parse->groupClause, groupColIdx, ! result_plan); current_pathkeys = root->group_pathkeys; } aggstrategy = AGG_SORTED; --- 1596,1604 ---- make_sort_from_groupcols(root, parse->groupClause, groupColIdx, ! result_plan, ! root->group_pathkeys, ! n_common_pathkeys_grouping); current_pathkeys = root->group_pathkeys; } aggstrategy = AGG_SORTED; *************** grouping_planner(PlannerInfo *root, doub *** 1607,1613 **** make_sort_from_groupcols(root, parse->groupClause, groupColIdx, ! result_plan); current_pathkeys = root->group_pathkeys; } --- 1641,1649 ---- make_sort_from_groupcols(root, parse->groupClause, groupColIdx, ! result_plan, ! root->group_pathkeys, ! n_common_pathkeys_grouping); current_pathkeys = root->group_pathkeys; } *************** grouping_planner(PlannerInfo *root, doub *** 1724,1736 **** if (window_pathkeys) { Sort *sort_plan; sort_plan = make_sort_from_pathkeys(root, result_plan, window_pathkeys, ! -1.0); ! if (!pathkeys_contained_in(window_pathkeys, ! current_pathkeys)) { /* we do indeed need to sort */ result_plan = (Plan *) sort_plan; --- 1760,1776 ---- if (window_pathkeys) { Sort *sort_plan; + int n_common_pathkeys; + + n_common_pathkeys = pathkeys_common(window_pathkeys, + current_pathkeys); sort_plan = make_sort_from_pathkeys(root, result_plan, window_pathkeys, ! -1.0, ! n_common_pathkeys); ! if (n_common_pathkeys < list_length(window_pathkeys)) { /* we do indeed need to sort */ result_plan = (Plan *) sort_plan; *************** grouping_planner(PlannerInfo *root, doub *** 1876,1894 **** { if (list_length(root->distinct_pathkeys) >= list_length(root->sort_pathkeys)) ! current_pathkeys = root->distinct_pathkeys; else { ! current_pathkeys = root->sort_pathkeys; /* Assert checks that parser didn't mess up... */ Assert(pathkeys_contained_in(root->distinct_pathkeys, ! current_pathkeys)); } result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, ! current_pathkeys, ! -1.0); } result_plan = (Plan *) make_unique(result_plan, --- 1916,1936 ---- { if (list_length(root->distinct_pathkeys) >= list_length(root->sort_pathkeys)) ! needed_pathkeys = root->distinct_pathkeys; else { ! needed_pathkeys = root->sort_pathkeys; /* Assert checks that parser didn't mess up... */ Assert(pathkeys_contained_in(root->distinct_pathkeys, ! needed_pathkeys)); } result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, ! needed_pathkeys, ! -1.0, ! pathkeys_common(needed_pathkeys, current_pathkeys)); ! current_pathkeys = needed_pathkeys; } result_plan = (Plan *) make_unique(result_plan, *************** grouping_planner(PlannerInfo *root, doub *** 1904,1915 **** */ 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; } } --- 1946,1960 ---- */ if (parse->sortClause) { ! int common = pathkeys_common(root->sort_pathkeys, current_pathkeys); ! ! if (common < list_length(root->sort_pathkeys)) { result_plan = (Plan *) make_sort_from_pathkeys(root, result_plan, root->sort_pathkeys, ! limit_tuples, ! common); current_pathkeys = root->sort_pathkeys; } } *************** choose_hashed_grouping(PlannerInfo *root *** 2654,2659 **** --- 2699,2705 ---- List *current_pathkeys; Path hashed_p; Path sorted_p; + int n_common_pathkeys; /* * Executor doesn't support hashed aggregation with DISTINCT or ORDER BY *************** choose_hashed_grouping(PlannerInfo *root *** 2735,2741 **** path_rows); /* Result of hashed agg is always unsorted */ if (target_pathkeys) ! cost_sort(&hashed_p, root, target_pathkeys, hashed_p.total_cost, dNumGroups, path_width, 0.0, work_mem, limit_tuples); --- 2781,2788 ---- path_rows); /* Result of hashed agg is always unsorted */ if (target_pathkeys) ! cost_sort(&hashed_p, root, target_pathkeys, 0, ! hashed_p.startup_cost, hashed_p.total_cost, dNumGroups, path_width, 0.0, work_mem, limit_tuples); *************** choose_hashed_grouping(PlannerInfo *root *** 2751,2759 **** sorted_p.total_cost = cheapest_path->total_cost; current_pathkeys = cheapest_path->pathkeys; } ! if (!pathkeys_contained_in(root->group_pathkeys, current_pathkeys)) { ! cost_sort(&sorted_p, root, root->group_pathkeys, sorted_p.total_cost, path_rows, path_width, 0.0, work_mem, -1.0); current_pathkeys = root->group_pathkeys; --- 2798,2809 ---- sorted_p.total_cost = cheapest_path->total_cost; current_pathkeys = cheapest_path->pathkeys; } ! ! n_common_pathkeys = pathkeys_common(root->group_pathkeys, current_pathkeys); ! if (n_common_pathkeys < list_length(root->group_pathkeys)) { ! cost_sort(&sorted_p, root, root->group_pathkeys, ! n_common_pathkeys, sorted_p.startup_cost, sorted_p.total_cost, path_rows, path_width, 0.0, work_mem, -1.0); current_pathkeys = root->group_pathkeys; *************** choose_hashed_grouping(PlannerInfo *root *** 2768,2777 **** cost_group(&sorted_p, root, numGroupCols, dNumGroups, sorted_p.startup_cost, sorted_p.total_cost, path_rows); /* The Agg or Group node will preserve ordering */ ! if (target_pathkeys && ! !pathkeys_contained_in(target_pathkeys, current_pathkeys)) ! cost_sort(&sorted_p, root, target_pathkeys, sorted_p.total_cost, dNumGroups, path_width, 0.0, work_mem, limit_tuples); --- 2818,2829 ---- cost_group(&sorted_p, root, numGroupCols, dNumGroups, sorted_p.startup_cost, sorted_p.total_cost, path_rows); + /* The Agg or Group node will preserve ordering */ ! n_common_pathkeys = pathkeys_common(target_pathkeys, current_pathkeys); ! if (target_pathkeys && n_common_pathkeys < list_length(target_pathkeys)) ! cost_sort(&sorted_p, root, target_pathkeys, n_common_pathkeys, ! sorted_p.startup_cost, sorted_p.total_cost, dNumGroups, path_width, 0.0, work_mem, limit_tuples); *************** choose_hashed_distinct(PlannerInfo *root *** 2824,2829 **** --- 2876,2882 ---- List *needed_pathkeys; Path hashed_p; Path sorted_p; + int n_common_pathkeys; /* * If we have a sortable DISTINCT ON clause, we always use sorting. This *************** choose_hashed_distinct(PlannerInfo *root *** 2889,2895 **** * need to charge for the final sort. */ if (parse->sortClause) ! cost_sort(&hashed_p, root, root->sort_pathkeys, hashed_p.total_cost, dNumDistinctRows, path_width, 0.0, work_mem, limit_tuples); --- 2942,2949 ---- * need to charge for the final sort. */ if (parse->sortClause) ! cost_sort(&hashed_p, root, root->sort_pathkeys, 0, ! hashed_p.startup_cost, hashed_p.total_cost, dNumDistinctRows, path_width, 0.0, work_mem, limit_tuples); *************** choose_hashed_distinct(PlannerInfo *root *** 2906,2928 **** needed_pathkeys = root->sort_pathkeys; else needed_pathkeys = root->distinct_pathkeys; ! if (!pathkeys_contained_in(needed_pathkeys, current_pathkeys)) { if (list_length(root->distinct_pathkeys) >= list_length(root->sort_pathkeys)) current_pathkeys = root->distinct_pathkeys; else current_pathkeys = root->sort_pathkeys; ! cost_sort(&sorted_p, root, current_pathkeys, sorted_p.total_cost, path_rows, path_width, 0.0, work_mem, -1.0); } cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows, sorted_p.startup_cost, sorted_p.total_cost, path_rows); if (parse->sortClause && ! !pathkeys_contained_in(root->sort_pathkeys, current_pathkeys)) ! cost_sort(&sorted_p, root, root->sort_pathkeys, sorted_p.total_cost, dNumDistinctRows, path_width, 0.0, work_mem, limit_tuples); --- 2960,2989 ---- needed_pathkeys = root->sort_pathkeys; else needed_pathkeys = root->distinct_pathkeys; ! ! n_common_pathkeys = pathkeys_common(needed_pathkeys, current_pathkeys); ! if (n_common_pathkeys < list_length(needed_pathkeys)) { if (list_length(root->distinct_pathkeys) >= list_length(root->sort_pathkeys)) current_pathkeys = root->distinct_pathkeys; else current_pathkeys = root->sort_pathkeys; ! cost_sort(&sorted_p, root, current_pathkeys, ! n_common_pathkeys, sorted_p.startup_cost, sorted_p.total_cost, path_rows, path_width, 0.0, work_mem, -1.0); } cost_group(&sorted_p, root, numDistinctCols, dNumDistinctRows, sorted_p.startup_cost, sorted_p.total_cost, path_rows); + + + n_common_pathkeys = pathkeys_common(root->sort_pathkeys, current_pathkeys); if (parse->sortClause && ! n_common_pathkeys < list_length(root->sort_pathkeys)) ! cost_sort(&sorted_p, root, root->sort_pathkeys, n_common_pathkeys, ! sorted_p.startup_cost, sorted_p.total_cost, dNumDistinctRows, path_width, 0.0, work_mem, limit_tuples); *************** plan_cluster_use_sort(Oid tableOid, Oid *** 3712,3719 **** /* Estimate the cost of seq scan + sort */ seqScanPath = create_seqscan_path(root, rel, NULL); ! cost_sort(&seqScanAndSortPath, root, NIL, ! seqScanPath->total_cost, rel->tuples, rel->width, comparisonCost, maintenance_work_mem, -1.0); /* Estimate the cost of index scan */ --- 3773,3781 ---- /* Estimate the cost of seq scan + sort */ seqScanPath = create_seqscan_path(root, rel, NULL); ! cost_sort(&seqScanAndSortPath, root, NIL, 0, ! seqScanPath->startup_cost, seqScanPath->total_cost, ! rel->tuples, rel->width, comparisonCost, maintenance_work_mem, -1.0); /* Estimate the cost of index scan */ diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c new file mode 100644 index e249628..b0b5471 *** a/src/backend/optimizer/prep/prepunion.c --- b/src/backend/optimizer/prep/prepunion.c *************** choose_hashed_setop(PlannerInfo *root, L *** 859,865 **** sorted_p.startup_cost = input_plan->startup_cost; sorted_p.total_cost = input_plan->total_cost; /* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */ ! cost_sort(&sorted_p, root, NIL, sorted_p.total_cost, input_plan->plan_rows, input_plan->plan_width, 0.0, work_mem, -1.0); cost_group(&sorted_p, root, numGroupCols, dNumGroups, --- 859,866 ---- sorted_p.startup_cost = input_plan->startup_cost; sorted_p.total_cost = input_plan->total_cost; /* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */ ! cost_sort(&sorted_p, root, NIL, 0, ! sorted_p.startup_cost, sorted_p.total_cost, input_plan->plan_rows, input_plan->plan_width, 0.0, work_mem, -1.0); cost_group(&sorted_p, root, numGroupCols, dNumGroups, diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c new file mode 100644 index a7169ef..3d0a842 *** a/src/backend/optimizer/util/pathnode.c --- b/src/backend/optimizer/util/pathnode.c *************** create_merge_append_path(PlannerInfo *ro *** 971,980 **** foreach(l, subpaths) { Path *subpath = (Path *) lfirst(l); pathnode->path.rows += subpath->rows; ! if (pathkeys_contained_in(pathkeys, subpath->pathkeys)) { /* Subpath is adequately ordered, we won't need to sort it */ input_startup_cost += subpath->startup_cost; --- 971,981 ---- foreach(l, subpaths) { Path *subpath = (Path *) lfirst(l); + int n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys); pathnode->path.rows += subpath->rows; ! 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 *** 988,993 **** --- 989,996 ---- cost_sort(&sort_path, root, pathkeys, + n_common_pathkeys, + subpath->startup_cost, subpath->total_cost, subpath->parent->tuples, subpath->parent->width, *************** create_unique_path(PlannerInfo *root, Re *** 1343,1349 **** /* * Estimate cost for sort+unique implementation */ ! cost_sort(&sort_path, root, NIL, subpath->total_cost, rel->rows, rel->width, --- 1346,1353 ---- /* * Estimate cost for sort+unique implementation */ ! cost_sort(&sort_path, root, NIL, 0, ! subpath->startup_cost, subpath->total_cost, rel->rows, rel->width, diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c new file mode 100644 index 52f05e6..6a09138 *** a/src/backend/utils/sort/tuplesort.c --- b/src/backend/utils/sort/tuplesort.c *************** free_sort_tuple(Tuplesortstate *state, S *** 3525,3527 **** --- 3525,3534 ---- 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 2a7b36e..76aab79 *** a/src/include/nodes/execnodes.h --- b/src/include/nodes/execnodes.h *************** typedef struct SortState *** 1664,1671 **** --- 1664,1673 ---- 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/cost.h b/src/include/optimizer/cost.h new file mode 100644 index 444ab74..e98fb0c *** a/src/include/optimizer/cost.h --- b/src/include/optimizer/cost.h *************** extern void cost_ctescan(Path *path, Pla *** 88,95 **** RelOptInfo *baserel, ParamPathInfo *param_info); extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm); extern void cost_sort(Path *path, PlannerInfo *root, ! List *pathkeys, Cost input_cost, double tuples, int width, ! Cost comparison_cost, int sort_mem, double limit_tuples); extern void cost_merge_append(Path *path, PlannerInfo *root, List *pathkeys, int n_streams, --- 88,96 ---- RelOptInfo *baserel, ParamPathInfo *param_info); extern void cost_recursive_union(Plan *runion, Plan *nrterm, Plan *rterm); extern void cost_sort(Path *path, PlannerInfo *root, ! List *pathkeys, int presorted_keys, ! Cost input_startup_cost, Cost input_total_cost, ! double tuples, int width, Cost comparison_cost, int sort_mem, double limit_tuples); extern void cost_merge_append(Path *path, PlannerInfo *root, List *pathkeys, int n_streams, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h new file mode 100644 index 999adaa..043641d *** a/src/include/optimizer/paths.h --- b/src/include/optimizer/paths.h *************** typedef enum *** 157,169 **** 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, --- 157,172 ---- 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, ! PlannerInfo *root, ! double tuples); extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index, ScanDirection scandir); extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr, *************** extern void update_mergeclause_eclasses( *** 185,191 **** extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, ! List *restrictinfos); extern List *select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel); --- 188,196 ---- extern List *find_mergeclauses_for_pathkeys(PlannerInfo *root, List *pathkeys, bool outer_keys, ! List *restrictinfos, ! RelOptInfo *joinrel, ! List **outerpathkeys); extern List *select_outer_pathkeys_for_merge(PlannerInfo *root, List *mergeclauses, RelOptInfo *joinrel); diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h new file mode 100644 index ba7ae7c..d33c615 *** a/src/include/optimizer/planmain.h --- b/src/include/optimizer/planmain.h *************** extern RecursiveUnion *make_recursive_un *** 50,60 **** Plan *lefttree, Plan *righttree, int wtParam, List *distinctList, long numGroups); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, ! List *pathkeys, double limit_tuples); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree); extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls, ! AttrNumber *grpColIdx, Plan *lefttree); extern Agg *make_agg(PlannerInfo *root, List *tlist, List *qual, AggStrategy aggstrategy, const AggClauseCosts *aggcosts, int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators, --- 50,61 ---- Plan *lefttree, Plan *righttree, int wtParam, List *distinctList, long numGroups); extern Sort *make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, ! List *pathkeys, double limit_tuples, int skipCols); extern Sort *make_sort_from_sortclauses(PlannerInfo *root, List *sortcls, Plan *lefttree); extern Sort *make_sort_from_groupcols(PlannerInfo *root, List *groupcls, ! AttrNumber *grpColIdx, Plan *lefttree, List *pathkeys, ! int skipCols); extern Agg *make_agg(PlannerInfo *root, List *tlist, List *qual, AggStrategy aggstrategy, const AggClauseCosts *aggcosts, int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators, diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h new file mode 100644 index 5f87254..5a65cd2 *** 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 *** 111,116 **** --- 112,119 ---- 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