partial-sort-3.patch
application/octet-stream
Filename: partial-sort-3.patch
Type: application/octet-stream
Part: 0
Message:
Re: PoC: Partial sort
Patch
Format: unified
| File | + | − |
|---|---|---|
| src/backend/commands/explain.c | 0 | 0 |
| src/backend/executor/nodeSort.c | 0 | 0 |
| src/backend/nodes/copyfuncs.c | 0 | 0 |
| src/backend/optimizer/path/costsize.c | 0 | 0 |
| src/backend/optimizer/path/joinpath.c | 0 | 0 |
| src/backend/optimizer/path/pathkeys.c | 0 | 0 |
| src/backend/optimizer/plan/createplan.c | 0 | 0 |
| src/backend/optimizer/plan/planagg.c | 0 | 0 |
| src/backend/optimizer/plan/planner.c | 0 | 0 |
| src/backend/optimizer/prep/prepunion.c | 0 | 0 |
| src/backend/optimizer/util/pathnode.c | 0 | 0 |
| src/backend/utils/sort/tuplesort.c | 0 | 0 |
| src/include/nodes/execnodes.h | 0 | 0 |
| src/include/nodes/plannodes.h | 0 | 0 |
| src/include/optimizer/cost.h | 0 | 0 |
| src/include/optimizer/paths.h | 0 | 0 |
| src/include/optimizer/planmain.h | 0 | 0 |
| src/include/utils/tuplesort.h | 0 | 0 |
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..1693d46
*** 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,75 ----
ScanDirection dir;
Tuplesortstate *tuplesortstate;
TupleTableSlot *slot;
+ int skipCols = ((Sort *)node->ss.ps.plan)->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");
--- 82,206 ----
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);
! 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 ****
--- 249,257 ----
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