partial-sort-basic-3.patch
application/octet-stream
Filename: partial-sort-basic-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/execAmi.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/plan/subselect.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/executor/executor.h | 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 |
| src/test/regress/expected/inherit.out | 0 | 0 |
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
new file mode 100644
index 7fb8a14..05cc125
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
*************** static void show_grouping_set_keys(PlanS
*** 88,94 ****
static void show_group_keys(GroupState *gstate, List *ancestors,
ExplainState *es);
static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es);
static void show_sortorder_options(StringInfo buf, Node *sortexpr,
--- 88,94 ----
static void show_group_keys(GroupState *gstate, List *ancestors,
ExplainState *es);
static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, int nPresortedKeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es);
static void show_sortorder_options(StringInfo buf, Node *sortexpr,
*************** ExplainNode(PlanState *planstate, List *
*** 901,907 ****
pname = sname = "Materialize";
break;
case T_Sort:
! pname = sname = "Sort";
break;
case T_Group:
pname = sname = "Group";
--- 901,910 ----
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
*** 1756,1762 ****
Sort *plan = (Sort *) sortstate->ss.ps.plan;
show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! plan->numCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
--- 1759,1765 ----
Sort *plan = (Sort *) sortstate->ss.ps.plan;
show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! plan->numCols, plan->skipCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
*************** show_merge_append_keys(MergeAppendState
*** 1772,1778 ****
MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
show_sort_group_keys((PlanState *) mstate, "Sort Key",
! plan->numCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
--- 1775,1781 ----
MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
show_sort_group_keys((PlanState *) mstate, "Sort Key",
! plan->numCols, 0, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
*************** show_agg_keys(AggState *astate, List *an
*** 1796,1802 ****
show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
else
show_sort_group_keys(outerPlanState(astate), "Group Key",
! plan->numCols, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
--- 1799,1805 ----
show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
else
show_sort_group_keys(outerPlanState(astate), "Group Key",
! plan->numCols, 0, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
*************** show_grouping_set_keys(PlanState *planst
*** 1852,1858 ****
if (sortnode)
{
show_sort_group_keys(planstate, "Sort Key",
! sortnode->numCols, sortnode->sortColIdx,
sortnode->sortOperators, sortnode->collations,
sortnode->nullsFirst,
ancestors, es);
--- 1855,1861 ----
if (sortnode)
{
show_sort_group_keys(planstate, "Sort Key",
! sortnode->numCols, 0, sortnode->sortColIdx,
sortnode->sortOperators, sortnode->collations,
sortnode->nullsFirst,
ancestors, es);
*************** show_group_keys(GroupState *gstate, List
*** 1909,1915 ****
/* The key columns refer to the tlist of the child plan */
ancestors = lcons(gstate, ancestors);
show_sort_group_keys(outerPlanState(gstate), "Group Key",
! plan->numCols, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
ancestors = list_delete_first(ancestors);
--- 1912,1918 ----
/* The key columns refer to the tlist of the child plan */
ancestors = lcons(gstate, ancestors);
show_sort_group_keys(outerPlanState(gstate), "Group Key",
! plan->numCols, 0, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
ancestors = list_delete_first(ancestors);
*************** show_group_keys(GroupState *gstate, List
*** 1922,1934 ****
*/
static void
show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es)
{
Plan *plan = planstate->plan;
List *context;
List *result = NIL;
StringInfoData sortkeybuf;
bool useprefix;
int keyno;
--- 1925,1938 ----
*/
static void
show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, int nPresortedKeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es)
{
Plan *plan = planstate->plan;
List *context;
List *result = NIL;
+ List *resultPresorted = NIL;
StringInfoData sortkeybuf;
bool useprefix;
int keyno;
*************** show_sort_group_keys(PlanState *planstat
*** 1968,1976 ****
--- 1972,1984 ----
nullsFirst[keyno]);
/* Emit one property-list item per sort key */
result = lappend(result, pstrdup(sortkeybuf.data));
+ if (keyno < nPresortedKeys)
+ resultPresorted = lappend(resultPresorted, exprstr);
}
ExplainPropertyList(qlabel, result, es);
+ if (nPresortedKeys > 0)
+ ExplainPropertyList("Presorted Key", resultPresorted, es);
}
/*
diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c
new file mode 100644
index 163650c..b44ce69
*** a/src/backend/executor/execAmi.c
--- b/src/backend/executor/execAmi.c
*************** ExecRestrPos(PlanState *node)
*** 382,388 ****
* know which plan types support mark/restore.
*/
bool
! ExecSupportsMarkRestore(Path *pathnode)
{
/*
* For consistency with the routines above, we do not examine the nodeTag
--- 382,388 ----
* know which plan types support mark/restore.
*/
bool
! ExecSupportsMarkRestore(Path *pathnode, Plan *node)
{
/*
* For consistency with the routines above, we do not examine the nodeTag
*************** ExecSupportsMarkRestore(Path *pathnode)
*** 394,402 ****
case T_IndexScan:
case T_IndexOnlyScan:
case T_Material:
- case T_Sort:
return true;
case T_CustomScan:
Assert(IsA(pathnode, CustomPath));
if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
--- 394,410 ----
case T_IndexScan:
case T_IndexOnlyScan:
case T_Material:
return true;
+ case T_Sort:
+ /* We shouldn't reach here without having plan node */
+ Assert(node);
+ /* With skipCols sort node holds only last bucket */
+ if (node && ((Sort *)node)->skipCols == 0)
+ return true;
+ else
+ return false;
+
case T_CustomScan:
Assert(IsA(pathnode, CustomPath));
if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
*************** ExecSupportsBackwardScan(Plan *node)
*** 498,507 ****
return false;
case T_Material:
- case T_Sort:
/* these don't evaluate tlist */
return true;
case T_LockRows:
case T_Limit:
/* these don't evaluate tlist */
--- 506,521 ----
return false;
case T_Material:
/* these don't evaluate tlist */
return true;
+ case T_Sort:
+ /* With skipCols sort node holds only last bucket */
+ if (((Sort *)node)->skipCols == 0)
+ return true;
+ else
+ return false;
+
case T_LockRows:
case T_Limit:
/* these don't evaluate tlist */
*************** IndexSupportsBackwardScan(Oid indexid)
*** 567,573 ****
* very low per-tuple cost.
*/
bool
! ExecMaterializesOutput(NodeTag plantype)
{
switch (plantype)
{
--- 581,587 ----
* very low per-tuple cost.
*/
bool
! ExecMaterializesOutput(NodeTag plantype, Plan *node)
{
switch (plantype)
{
*************** ExecMaterializesOutput(NodeTag plantype)
*** 575,583 ****
case T_FunctionScan:
case T_CteScan:
case T_WorkTableScan:
- case T_Sort:
return true;
default:
break;
}
--- 589,605 ----
case T_FunctionScan:
case T_CteScan:
case T_WorkTableScan:
return true;
+ case T_Sort:
+ /* We shouldn't reach here without having plan node */
+ Assert(node);
+ /* With skipCols sort node holds only last bucket */
+ if (node && ((Sort *)node)->skipCols == 0)
+ return true;
+ else
+ return false;
+
default:
break;
}
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
new file mode 100644
index af1dccf..7345fcb
*** a/src/backend/executor/nodeSort.c
--- b/src/backend/executor/nodeSort.c
***************
*** 15,25 ****
--- 15,109 ----
#include "postgres.h"
+ #include "access/htup_details.h"
#include "executor/execdebug.h"
#include "executor/nodeSort.h"
#include "miscadmin.h"
+ #include "utils/lsyscache.h"
#include "utils/tuplesort.h"
+ /*
+ * Check if first "skipCols" sort values are equal.
+ */
+ static bool
+ cmpSortSkipCols(SortState *node, TupleDesc tupDesc, HeapTuple a, TupleTableSlot *b)
+ {
+ int n = ((Sort *)node->ss.ps.plan)->skipCols, i;
+
+ for (i = 0; i < n; i++)
+ {
+ Datum datumA, datumB, result;
+ bool isnullA, isnullB;
+ AttrNumber attno = node->skipKeys[i].attno;
+ SkipKeyData *key;
+
+ datumA = heap_getattr(a, attno, tupDesc, &isnullA);
+ datumB = slot_getattr(b, attno, &isnullB);
+
+ if (isnullA || isnullB)
+ {
+ if (isnullA == isnullB)
+ continue;
+ else
+ return false;
+ }
+
+ key = &node->skipKeys[i];
+
+ key->fcinfo.arg[0] = datumA;
+ key->fcinfo.arg[1] = datumB;
+
+ /* just for paranoia's sake, we reset isnull each time */
+ key->fcinfo.isnull = false;
+
+ result = FunctionCallInvoke(&key->fcinfo);
+
+ /* Check for null result, since caller is clearly not expecting one */
+ if (key->fcinfo.isnull)
+ elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
+
+ if (!DatumGetBool(result))
+ return false;
+ }
+ return true;
+ }
+
+ static void
+ prepareSkipCols(Sort *plannode, SortState *node)
+ {
+ int skipCols = plannode->skipCols, i;
+
+ node->skipKeys = (SkipKeyData *)palloc(skipCols * sizeof(SkipKeyData));
+
+ for (i = 0; i < skipCols; i++)
+ {
+ Oid equalityOp, equalityFunc;
+ SkipKeyData *key;
+
+ key = &node->skipKeys[i];
+ key->attno = plannode->sortColIdx[i];
+
+ equalityOp = get_equality_op_for_ordering_op(
+ plannode->sortOperators[i], NULL);
+ if (!OidIsValid(equalityOp))
+ elog(ERROR, "missing equality operator for ordering operator %u",
+ plannode->sortOperators[i]);
+
+ equalityFunc = get_opcode(equalityOp);
+ if (!OidIsValid(equalityFunc))
+ elog(ERROR, "missing function for operator %u", equalityOp);
+
+ /* Lookup the comparison function */
+ fmgr_info_cxt(equalityFunc, &key->flinfo, CurrentMemoryContext);
+
+ /* We can initialize the callinfo just once and re-use it */
+ InitFunctionCallInfoData(key->fcinfo, &key->flinfo, 2,
+ plannode->collations[i], NULL, NULL);
+ key->fcinfo.argnull[0] = false;
+ key->fcinfo.argnull[1] = false;
+ }
+ }
+
/* ----------------------------------------------------------------
* ExecSort
*************** ExecSort(SortState *node)
*** 42,47 ****
--- 126,136 ----
ScanDirection dir;
Tuplesortstate *tuplesortstate;
TupleTableSlot *slot;
+ Sort *plannode = (Sort *) node->ss.ps.plan;
+ PlanState *outerNode;
+ TupleDesc tupDesc;
+ int skipCols = plannode->skipCols;
+ int64 nTuples = 0;
/*
* get state info from node
*************** ExecSort(SortState *node)
*** 54,132 ****
tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
/*
* If first time through, read all tuples from outer plan and pass them to
* tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
*/
! if (!node->sort_Done)
! {
! Sort *plannode = (Sort *) node->ss.ps.plan;
! PlanState *outerNode;
! TupleDesc tupDesc;
! SO1_printf("ExecSort: %s\n",
! "sorting subplan");
! /*
! * Want to scan subplan in the forward direction while creating the
! * sorted data.
! */
! estate->es_direction = ForwardScanDirection;
! /*
! * Initialize tuplesort module.
! */
! SO1_printf("ExecSort: %s\n",
! "calling tuplesort_begin");
! outerNode = outerPlanState(node);
! tupDesc = ExecGetResultType(outerNode);
tuplesortstate = tuplesort_begin_heap(tupDesc,
! plannode->numCols,
! plannode->sortColIdx,
! plannode->sortOperators,
! plannode->collations,
! plannode->nullsFirst,
work_mem,
node->randomAccess);
- if (node->bounded)
- tuplesort_set_bound(tuplesortstate, node->bound);
node->tuplesortstate = (void *) tuplesortstate;
! /*
! * Scan the subplan and feed all the tuples to tuplesort.
! */
! for (;;)
! {
! slot = ExecProcNode(outerNode);
if (TupIsNull(slot))
break;
!
tuplesort_puttupleslot(tuplesortstate, slot);
}
! /*
! * Complete the sort.
! */
! tuplesort_performsort(tuplesortstate);
! /*
! * restore to user specified direction
! */
! estate->es_direction = dir;
! /*
! * finally set the sorted flag to true
! */
! node->sort_Done = true;
! node->bounded_Done = node->bounded;
! node->bound_Done = node->bound;
! SO1_printf("ExecSort: %s\n", "sorting done");
}
SO1_printf("ExecSort: %s\n",
"retrieving tuple from tuplesort");
--- 143,286 ----
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_reset((Tuplesortstate *) node->tuplesortstate);
! else
! {
! /* Support structures for cmpSortSkipCols - already sorted columns */
! if (skipCols)
! prepareSkipCols(plannode, node);
+ /* Only pass on remaining columns that are unsorted */
tuplesortstate = tuplesort_begin_heap(tupDesc,
! plannode->numCols - skipCols,
! &(plannode->sortColIdx[skipCols]),
! &(plannode->sortOperators[skipCols]),
! &(plannode->collations[skipCols]),
! &(plannode->nullsFirst[skipCols]),
work_mem,
node->randomAccess);
node->tuplesortstate = (void *) tuplesortstate;
+ }
! if (node->bounded)
! tuplesort_set_bound(tuplesortstate, node->bound - node->bound_Done);
! /*
! * Put next group of tuples where skipCols" sort values are equal to
! * tuplesort.
! */
! for (;;)
! {
! slot = ExecProcNode(outerNode);
+ if (skipCols == 0)
+ {
if (TupIsNull(slot))
+ {
+ node->finished = true;
break;
! }
tuplesort_puttupleslot(tuplesortstate, slot);
+ nTuples++;
}
+ else if (node->prev)
+ {
+ ExecStoreTuple(node->prev, node->ss.ps.ps_ResultTupleSlot, InvalidBuffer, false);
+ tuplesort_puttupleslot(tuplesortstate, node->ss.ps.ps_ResultTupleSlot);
+ nTuples++;
! if (TupIsNull(slot))
! {
! node->finished = true;
! break;
! }
! else
! {
! bool cmp;
! cmp = cmpSortSkipCols(node, tupDesc, node->prev, slot);
! node->prev = ExecCopySlotTuple(slot);
! if (!cmp)
! break;
! }
! }
! else
! {
! if (TupIsNull(slot))
! {
! node->finished = true;
! break;
! }
! else
! {
! node->prev = ExecCopySlotTuple(slot);
! }
! }
! }
! /*
! * Complete the sort.
! */
! tuplesort_performsort(tuplesortstate);
! /*
! * restore to user specified direction
! */
! estate->es_direction = dir;
!
! /*
! * finally set the sorted flag to true
! */
! node->sort_Done = true;
! node->bounded_Done = node->bounded;
!
! /*
! * Adjust bound_Done with number of tuples we've actually sorted.
! */
! if (node->bounded)
! {
! if (node->finished)
! node->bound_Done = node->bound;
! else
! node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
}
+ SO1_printf("ExecSort: %s\n", "sorting done");
+
SO1_printf("ExecSort: %s\n",
"retrieving tuple from tuplesort");
*************** ExecInitSort(Sort *node, EState *estate,
*** 157,162 ****
--- 311,325 ----
"initializing sort node");
/*
+ * skipCols can't be used with either EXEC_FLAG_REWIND, EXEC_FLAG_BACKWARD
+ * or EXEC_FLAG_MARK, because we hold only current bucket in
+ * tuplesortstate.
+ */
+ Assert(node->skipCols == 0 || (eflags & (EXEC_FLAG_REWIND |
+ EXEC_FLAG_BACKWARD |
+ EXEC_FLAG_MARK)) == 0);
+
+ /*
* create state structure
*/
sortstate = makeNode(SortState);
*************** ExecInitSort(Sort *node, EState *estate,
*** 174,180 ****
--- 337,346 ----
sortstate->bounded = false;
sortstate->sort_Done = false;
+ sortstate->finished = false;
sortstate->tuplesortstate = NULL;
+ sortstate->prev = NULL;
+ sortstate->bound_Done = 0;
/*
* Miscellaneous initialization
*************** ExecReScanSort(SortState *node)
*** 318,323 ****
--- 484,490 ----
node->sort_Done = false;
tuplesort_end((Tuplesortstate *) node->tuplesortstate);
node->tuplesortstate = NULL;
+ node->bound_Done = 0;
/*
* if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
new file mode 100644
index c176ff9..c916072
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copySort(const Sort *from)
*** 826,831 ****
--- 826,832 ----
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 1b61fd9..a6c1c22
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_recursive_union(Plan *runion, Plan
*** 1381,1395 ****
*/
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)
--- 1381,1402 ----
*/
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,
*** 1419,1431 ****
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;
--- 1426,1472 ----
output_bytes = input_bytes;
}
! /*
! * Estimate number of groups which dataset is divided by presorted keys.
! */
! 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, NULL);
! }
! else
! {
! num_groups = 1.0;
! }
!
! /*
! * Estimate average cost of one group sorting
! */
! 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,
*** 1435,1441 ****
*
* Assume about N log2 N comparisons
*/
! startup_cost += comparison_cost * tuples * LOG2(tuples);
/* Disk costs */
--- 1476,1482 ----
*
* Assume about N log2 N comparisons
*/
! group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
/* Disk costs */
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1446,1455 ****
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
--- 1487,1496 ----
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,
*** 1457,1471 ****
* factor is a bit higher than for quicksort. Tweak it so that the
* cost curve is continuous at the crossover point.
*/
! startup_cost += comparison_cost * tuples * LOG2(2.0 * output_tuples);
}
else
{
/* We'll use plain quicksort on all the input tuples */
! startup_cost += comparison_cost * tuples * LOG2(tuples);
}
/*
* Also charge a small amount (arbitrarily set equal to operator cost) per
* extracted tuple. We don't charge cpu_tuple_cost because a Sort node
* doesn't do qual-checking or projection, so it has less overhead than
--- 1498,1523 ----
* 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);
}
/*
+ * We've to sort first group to start output from node. Sorting rest of
+ * groups are required to return all the tuples.
+ */
+ startup_cost += group_cost;
+ rest_cost = (num_groups * (output_tuples / tuples) - 1.0) * group_cost;
+ if (rest_cost > 0.0)
+ run_cost += rest_cost;
+ startup_cost += input_run_cost / num_groups;
+ run_cost += input_run_cost * ((num_groups - 1.0) / num_groups);
+
+ /*
* Also charge a small amount (arbitrarily set equal to operator cost) per
* extracted tuple. We don't charge cpu_tuple_cost because a Sort node
* doesn't do qual-checking or projection, so it has less overhead than
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2205,2210 ****
--- 2257,2264 ----
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
*** 2231,2236 ****
--- 2285,2292 ----
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,
*************** final_cost_mergejoin(PlannerInfo *root,
*** 2442,2448 ****
* it off does not entitle us to deliver an invalid plan.
*/
else if (innersortkeys == NIL &&
! !ExecSupportsMarkRestore(inner_path))
path->materialize_inner = true;
/*
--- 2498,2504 ----
* it off does not entitle us to deliver an invalid plan.
*/
else if (innersortkeys == NIL &&
! !ExecSupportsMarkRestore(inner_path, NULL))
path->materialize_inner = true;
/*
*************** cost_subplan(PlannerInfo *root, SubPlan
*** 2956,2962 ****
* every time.
*/
if (subplan->parParam == NIL &&
! ExecMaterializesOutput(nodeTag(plan)))
sp_cost.startup += plan->startup_cost;
else
sp_cost.per_tuple += plan->startup_cost;
--- 3012,3018 ----
* every time.
*/
if (subplan->parParam == NIL &&
! ExecMaterializesOutput(nodeTag(plan), plan))
sp_cost.startup += plan->startup_cost;
else
sp_cost.per_tuple += plan->startup_cost;
diff --git a/src/backend/optimizer/path/joinpath.c b/src/backend/optimizer/path/joinpath.c
new file mode 100644
index a35c881..7b762a6
*** a/src/backend/optimizer/path/joinpath.c
--- b/src/backend/optimizer/path/joinpath.c
*************** match_unsorted_outer(PlannerInfo *root,
*** 870,882 ****
}
else if (nestjoinOK)
{
/*
* Consider materializing the cheapest inner path, unless
* enable_material is off or the path in question materializes its
* output anyway.
*/
if (enable_material && inner_cheapest_total != NULL &&
! !ExecMaterializesOutput(inner_cheapest_total->pathtype))
matpath = (Path *)
create_material_path(innerrel, inner_cheapest_total);
}
--- 870,885 ----
}
else if (nestjoinOK)
{
+ if (inner_cheapest_total && inner_cheapest_total->pathtype == T_Sort)
+ elog(ERROR, "Sort");
+
/*
* Consider materializing the cheapest inner path, unless
* enable_material is off or the path in question materializes its
* output anyway.
*/
if (enable_material && inner_cheapest_total != NULL &&
! !ExecMaterializesOutput(inner_cheapest_total->pathtype, NULL))
matpath = (Path *)
create_material_path(innerrel, inner_cheapest_total);
}
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
new file mode 100644
index c6b5d78..490f343
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 21,31 ****
--- 21,33 ----
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
#include "nodes/plannodes.h"
+ #include "optimizer/cost.h"
#include "optimizer/clauses.h"
#include "optimizer/pathnode.h"
#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 ****
--- 314,345 ----
}
/*
+ * 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
*** 369,377 ****
}
/*
* get_cheapest_fractional_path_for_pathkeys
* Find the cheapest path (for retrieving a specified fraction of all
! * the tuples) that satisfies the given pathkeys and parameterization.
* Return NULL if no such path.
*
* See compare_fractional_path_costs() for the interpretation of the fraction
--- 397,432 ----
}
/*
+ * Compare cost of two paths assuming different fractions of tuples be returned
+ * from each paths.
+ */
+ 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
! * the tuples) that satisfies given parameterization and at least partially
! * satisfies the given pathkeys. Compares paths according to different
! * fraction of tuples be extracted to start with partial sort.
* Return NULL if no such path.
*
* See compare_fractional_path_costs() for the interpretation of the fraction
*************** 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;
}
--- 441,524 ----
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;
+
+ /*
+ * Get number of groups for each possible partial sort.
+ */
+ i = 0;
+ num_groups = (double *)palloc(sizeof(double) * list_length(pathkeys));
+ foreach(l, pathkeys)
+ {
+ PathKey *key = (PathKey *)lfirst(l);
+ EquivalenceMember *member = (EquivalenceMember *)
+ linitial(key->pk_eclass->ec_members);
+
+ groupExprs = lappend(groupExprs, member->em_expr);
+
+ num_groups[i] = estimate_num_groups(root, groupExprs, tuples, NULL);
+ 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;
/*
! * Estimate fraction of outer tuples be fetched to start returning
! * tuples from partial sort.
*/
! current_fraction = fraction;
! if (n_common_pathkeys < n_pathkeys)
! {
! current_fraction += 1.0 / num_groups[n_common_pathkeys - 1];
! current_fraction = Min(current_fraction, 1.0);
! }
! /*
! * Do cost comparison.
! */
! if (matched_path != NULL)
! {
! costs_cmp = compare_bifractional_path_costs(matched_path, path,
! matched_fraction, current_fraction);
! }
! else
! {
! costs_cmp = 1;
! }
!
! /*
! * Always prefer best number of common pathkeys.
! */
! 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;
}
*************** right_merge_direction(PlannerInfo *root,
*** 1450,1458 ****
* Count the number of pathkeys that are useful for meeting the
* query's requested output ordering.
*
! * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
! * no good to order by just the first key(s) of the requested ordering.
! * So the result is always either 0 or list_length(root->query_pathkeys).
*/
static int
pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
--- 1563,1570 ----
* Count the number of pathkeys that are useful for meeting the
* query's requested output ordering.
*
! * Returns number of pathkeys that maches given argument. Others can be
! * satisfied by partial sort.
*/
static int
pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
*************** pathkeys_useful_for_ordering(PlannerInfo
*** 1463,1475 ****
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 */
}
/*
--- 1575,1586 ----
if (pathkeys == NIL)
return 0; /* unordered path */
! /*
! * Return the number of path keys in common, or 0 if there are none. Any
! * first common pathkeys could be useful for ordering because we can use
! * partial sort.
! */
! return pathkeys_common(root->query_pathkeys, pathkeys);
}
/*
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
new file mode 100644
index 791b64e..4d610cf
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** static MergeJoin *make_mergejoin(List *t
*** 163,168 ****
--- 163,169 ----
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
*** 810,815 ****
--- 811,817 ----
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
*** 843,850 ****
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);
--- 845,854 ----
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,
*** 2436,2444 ****
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
--- 2440,2450 ----
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,
*** 2449,2457 ****
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
--- 2455,2465 ----
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,
*** 4021,4026 ****
--- 4029,4035 ----
*/
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
*** 4030,4036 ****
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,
--- 4039,4046 ----
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
*** 4044,4049 ****
--- 4054,4060 ----
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
*** 4372,4378 ****
*/
Sort *
make_sort_from_pathkeys(PlannerInfo *root, Plan *lefttree, List *pathkeys,
! double limit_tuples)
{
int numsortkeys;
AttrNumber *sortColIdx;
--- 4383,4389 ----
*/
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
*** 4392,4398 ****
&nullsFirst);
/* Now build the Sort node */
! return make_sort(root, lefttree, numsortkeys,
sortColIdx, sortOperators, collations,
nullsFirst, limit_tuples);
}
--- 4403,4409 ----
&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 *
*** 4435,4441 ****
numsortkeys++;
}
! return make_sort(root, lefttree, numsortkeys,
sortColIdx, sortOperators, collations,
nullsFirst, -1.0);
}
--- 4446,4452 ----
numsortkeys++;
}
! return make_sort(root, lefttree, numsortkeys, NIL, 0,
sortColIdx, sortOperators, collations,
nullsFirst, -1.0);
}
*************** Sort *
*** 4457,4463 ****
make_sort_from_groupcols(PlannerInfo *root,
List *groupcls,
AttrNumber *grpColIdx,
! Plan *lefttree)
{
List *sub_tlist = lefttree->targetlist;
ListCell *l;
--- 4468,4475 ----
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
*** 4490,4496 ****
numsortkeys++;
}
! return make_sort(root, lefttree, numsortkeys,
sortColIdx, sortOperators, collations,
nullsFirst, -1.0);
}
--- 4502,4508 ----
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 a761cfd..87efec2
*** a/src/backend/optimizer/plan/planagg.c
--- b/src/backend/optimizer/plan/planagg.c
*************** build_minmax_path(PlannerInfo *root, Min
*** 505,511 ****
get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
subroot->query_pathkeys,
NULL,
! path_fraction);
if (!sorted_path)
return false;
--- 505,513 ----
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 e1ee67c..906e8e7
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** static Plan *build_grouping_chain(Planne
*** 133,139 ****
AttrNumber *groupColIdx,
AggClauseCosts *agg_costs,
long numGroups,
! Plan *result_plan);
/*****************************************************************************
*
--- 133,141 ----
AttrNumber *groupColIdx,
AggClauseCosts *agg_costs,
long numGroups,
! Plan *result_plan,
! List *path_keys,
! int n_common_pathkeys);
/*****************************************************************************
*
*************** grouping_planner(PlannerInfo *root, doub
*** 1752,1758 ****
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)
--- 1754,1762 ----
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
*** 1768,1777 ****
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;
--- 1772,1785 ----
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
*** 1781,1792 ****
{
/* 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 */
--- 1789,1823 ----
{
/* 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
*** 1878,1890 ****
* 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;
--- 1909,1924 ----
* 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
*** 2010,2016 ****
groupColIdx,
&agg_costs,
numGroups,
! result_plan);
/*
* these are destroyed by build_grouping_chain, so make sure
--- 2044,2052 ----
groupColIdx,
&agg_costs,
numGroups,
! result_plan,
! root->group_pathkeys,
! n_common_pathkeys_grouping);
/*
* these are destroyed by build_grouping_chain, so make sure
*************** grouping_planner(PlannerInfo *root, doub
*** 2034,2040 ****
make_sort_from_groupcols(root,
parse->groupClause,
groupColIdx,
! result_plan);
current_pathkeys = root->group_pathkeys;
}
--- 2070,2078 ----
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
*** 2172,2184 ****
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;
--- 2210,2226 ----
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
*** 2325,2343 ****
{
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,
--- 2367,2387 ----
{
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
*** 2353,2364 ****
*/
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;
}
}
--- 2397,2411 ----
*/
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;
}
}
*************** build_grouping_chain(PlannerInfo *root,
*** 2462,2468 ****
AttrNumber *groupColIdx,
AggClauseCosts *agg_costs,
long numGroups,
! Plan *result_plan)
{
AttrNumber *top_grpColIdx = groupColIdx;
List *chain = NIL;
--- 2509,2517 ----
AttrNumber *groupColIdx,
AggClauseCosts *agg_costs,
long numGroups,
! Plan *result_plan,
! List *path_keys,
! int n_common_pathkeys)
{
AttrNumber *top_grpColIdx = groupColIdx;
List *chain = NIL;
*************** build_grouping_chain(PlannerInfo *root,
*** 2483,2489 ****
make_sort_from_groupcols(root,
llast(rollup_groupclauses),
top_grpColIdx,
! result_plan);
}
/*
--- 2532,2540 ----
make_sort_from_groupcols(root,
llast(rollup_groupclauses),
top_grpColIdx,
! result_plan,
! path_keys,
! n_common_pathkeys);
}
/*
*************** build_grouping_chain(PlannerInfo *root,
*** 2507,2513 ****
make_sort_from_groupcols(root,
groupClause,
new_grpColIdx,
! result_plan);
/*
* sort_plan includes the cost of result_plan over again, which is not
--- 2558,2566 ----
make_sort_from_groupcols(root,
groupClause,
new_grpColIdx,
! result_plan,
! NIL,
! 0);
/*
* sort_plan includes the cost of result_plan over again, which is not
*************** choose_hashed_grouping(PlannerInfo *root
*** 3623,3628 ****
--- 3676,3682 ----
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
*** 3704,3710 ****
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);
--- 3758,3765 ----
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
*** 3720,3728 ****
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;
--- 3775,3786 ----
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
*** 3737,3746 ****
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);
--- 3795,3806 ----
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
*** 3793,3798 ****
--- 3853,3859 ----
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
*** 3858,3864 ****
* 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);
--- 3919,3926 ----
* 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
*** 3875,3897 ****
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);
--- 3937,3966 ----
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
*** 4681,4688 ****
/* 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 */
--- 4750,4758 ----
/* 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/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
new file mode 100644
index 82414d4..474f20e
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** build_subplan(PlannerInfo *root, Plan *p
*** 823,829 ****
* unnecessarily, so we don't.
*/
else if (splan->parParam == NIL && enable_material &&
! !ExecMaterializesOutput(nodeTag(plan)))
plan = materialize_finished_plan(plan);
result = (Node *) splan;
--- 823,829 ----
* unnecessarily, so we don't.
*/
else if (splan->parParam == NIL && enable_material &&
! !ExecMaterializesOutput(nodeTag(plan), plan))
plan = materialize_finished_plan(plan);
result = (Node *) splan;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
new file mode 100644
index 8884fb1..4e84de5
*** a/src/backend/optimizer/prep/prepunion.c
--- b/src/backend/optimizer/prep/prepunion.c
*************** choose_hashed_setop(PlannerInfo *root, L
*** 863,869 ****
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,
--- 863,870 ----
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 1895a68..d895907
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** create_merge_append_path(PlannerInfo *ro
*** 996,1005 ****
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;
--- 996,1006 ----
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
*** 1013,1018 ****
--- 1014,1021 ----
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
*** 1229,1235 ****
/*
* Estimate cost for sort+unique implementation
*/
! cost_sort(&sort_path, root, NIL,
subpath->total_cost,
rel->rows,
rel->width,
--- 1232,1239 ----
/*
* 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 d532e87..e12624e
*** a/src/backend/utils/sort/tuplesort.c
--- b/src/backend/utils/sort/tuplesort.c
*************** tuplesort_end(Tuplesortstate *state)
*** 1068,1073 ****
--- 1068,1093 ----
MemoryContextDelete(state->sortcontext);
}
+ void
+ tuplesort_reset(Tuplesortstate *state)
+ {
+ int i;
+
+ if (state->tapeset)
+ LogicalTapeSetClose(state->tapeset);
+
+ for (i = 0; i < state->memtupcount; i++)
+ free_sort_tuple(state, state->memtuples + i);
+
+ state->status = TSS_INITIAL;
+ state->memtupcount = 0;
+ state->boundUsed = false;
+ state->tapeset = NULL;
+ state->currentRun = 0;
+ state->result_tape = -1;
+ state->bounded = false;
+ }
+
/*
* Grow the memtuples[] array, if possible within our memory constraint. We
* must not exceed INT_MAX tuples in memory or the caller-provided memory
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
new file mode 100644
index 4f77692..95ff06f
*** a/src/include/executor/executor.h
--- b/src/include/executor/executor.h
*************** struct Path; /* avoid including rela
*** 104,112 ****
extern void ExecReScan(PlanState *node);
extern void ExecMarkPos(PlanState *node);
extern void ExecRestrPos(PlanState *node);
! extern bool ExecSupportsMarkRestore(struct Path *pathnode);
extern bool ExecSupportsBackwardScan(Plan *node);
! extern bool ExecMaterializesOutput(NodeTag plantype);
/*
* prototypes from functions in execCurrent.c
--- 104,112 ----
extern void ExecReScan(PlanState *node);
extern void ExecMarkPos(PlanState *node);
extern void ExecRestrPos(PlanState *node);
! extern bool ExecSupportsMarkRestore(struct Path *pathnode, Plan *node);
extern bool ExecSupportsBackwardScan(Plan *node);
! extern bool ExecMaterializesOutput(NodeTag plantype, Plan *node);
/*
* prototypes from functions in execCurrent.c
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
new file mode 100644
index 23670e1..bb10360
*** a/src/include/nodes/execnodes.h
--- b/src/include/nodes/execnodes.h
*************** typedef struct MaterialState
*** 1784,1789 ****
--- 1784,1796 ----
Tuplestorestate *tuplestorestate;
} MaterialState;
+ typedef struct SkipKeyData
+ {
+ FunctionCallInfoData fcinfo;
+ FmgrInfo flinfo;
+ OffsetNumber attno;
+ } SkipKeyData;
+
/* ----------------
* SortState information
* ----------------
*************** typedef struct SortState
*** 1795,1803 ****
--- 1802,1814 ----
bool bounded; /* is the result set bounded? */
int64 bound; /* if bounded, how many tuples are needed */
bool sort_Done; /* sort completed yet? */
+ bool finished; /* fetching tuples from outer node
+ is finished ? */
bool bounded_Done; /* value of bounded we did the sort with */
int64 bound_Done; /* value of bound we did the sort with */
void *tuplesortstate; /* private state of tuplesort.c */
+ SkipKeyData *skipKeys;
+ HeapTuple prev; /* previous tuple from outer node */
} SortState;
/* ---------------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
new file mode 100644
index 92fd8e4..fc4ac40
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
*************** typedef struct Sort
*** 675,680 ****
--- 675,681 ----
{
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 25a7303..2740302
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern void cost_ctescan(Path *path, Pla
*** 95,102 ****
RelOptInfo *baserel, ParamPathInfo *param_info);
extern void cost_recursive_union(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,
--- 95,103 ----
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 87123a5..b3d0dbf
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** typedef enum
*** 165,177 ****
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,
--- 165,180 ----
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
+ extern int pathkeys_common(List *keys1, List *keys2);
extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
CostSelector cost_criterion);
extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
Relids required_outer,
! double fraction,
! PlannerInfo *root,
! double tuples);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
ScanDirection scandir);
extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
new file mode 100644
index 1fb8504..791563c
*** a/src/include/optimizer/planmain.h
--- b/src/include/optimizer/planmain.h
*************** extern RecursiveUnion *make_recursive_un
*** 51,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);
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,
--- 51,62 ----
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 de6fc56..7b47f2f
*** 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 bool tuplesort_skiptuples(Tupleso
*** 106,111 ****
--- 107,114 ----
extern void tuplesort_end(Tuplesortstate *state);
+ extern void tuplesort_reset(Tuplesortstate *state);
+
extern void tuplesort_get_stats(Tuplesortstate *state,
const char **sortMethod,
const char **spaceType,
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
new file mode 100644
index 89b6c1c..450c251
*** a/src/test/regress/expected/inherit.out
--- b/src/test/regress/expected/inherit.out
*************** ORDER BY thousand, tenthous;
*** 1357,1366 ****
Merge Append
Sort Key: tenk1.thousand, tenk1.tenthous
-> Index Only Scan using tenk1_thous_tenthous on tenk1
! -> Sort
Sort Key: tenk1_1.thousand, tenk1_1.thousand
-> Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (6 rows)
explain (costs off)
SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
--- 1357,1367 ----
Merge Append
Sort Key: tenk1.thousand, tenk1.tenthous
-> Index Only Scan using tenk1_thous_tenthous on tenk1
! -> Partial sort
Sort Key: tenk1_1.thousand, tenk1_1.thousand
+ Presorted Key: tenk1_1.thousand
-> Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (7 rows)
explain (costs off)
SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
*************** ORDER BY x, y;
*** 1441,1450 ****
Merge Append
Sort Key: a.thousand, a.tenthous
-> Index Only Scan using tenk1_thous_tenthous on tenk1 a
! -> Sort
Sort Key: b.unique2, b.unique2
-> Index Only Scan using tenk1_unique2 on tenk1 b
! (6 rows)
-- exercise rescan code path via a repeatedly-evaluated subquery
explain (costs off)
--- 1442,1452 ----
Merge Append
Sort Key: a.thousand, a.tenthous
-> Index Only Scan using tenk1_thous_tenthous on tenk1 a
! -> Partial sort
Sort Key: b.unique2, b.unique2
+ Presorted Key: b.unique2
-> Index Only Scan using tenk1_unique2 on tenk1 b
! (7 rows)
-- exercise rescan code path via a repeatedly-evaluated subquery
explain (costs off)