partial-sort-basic-9.patch
application/octet-stream
Filename: partial-sort-basic-9.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/nodeAgg.c | 0 | 0 |
| src/backend/executor/nodeSort.c | 0 | 0 |
| src/backend/nodes/copyfuncs.c | 0 | 0 |
| src/backend/nodes/outfuncs.c | 0 | 0 |
| src/backend/nodes/readfuncs.c | 0 | 0 |
| src/backend/optimizer/path/costsize.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/adt/orderedsetaggs.c | 0 | 0 |
| src/backend/utils/adt/selfuncs.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/nodes/relation.h | 0 | 0 |
| src/include/optimizer/cost.h | 0 | 0 |
| src/include/optimizer/pathnode.h | 0 | 0 |
| src/include/optimizer/paths.h | 0 | 0 |
| src/include/utils/selfuncs.h | 0 | 0 |
| src/include/utils/tuplesort.h | 0 | 0 |
| src/test/regress/expected/aggregates.out | 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 1247433..d2955b7
*** a/src/backend/commands/explain.c
--- b/src/backend/commands/explain.c
*************** static void show_grouping_set_keys(PlanS
*** 91,97 ****
static void show_group_keys(GroupState *gstate, List *ancestors,
ExplainState *es);
static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es);
static void show_sortorder_options(StringInfo buf, Node *sortexpr,
--- 91,97 ----
static void show_group_keys(GroupState *gstate, List *ancestors,
ExplainState *es);
static void show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, int nPresortedKeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es);
static void show_sortorder_options(StringInfo buf, Node *sortexpr,
*************** show_sort_keys(SortState *sortstate, Lis
*** 1810,1816 ****
Sort *plan = (Sort *) sortstate->ss.ps.plan;
show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! plan->numCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
--- 1810,1816 ----
Sort *plan = (Sort *) sortstate->ss.ps.plan;
show_sort_group_keys((PlanState *) sortstate, "Sort Key",
! plan->numCols, plan->skipCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
*************** show_merge_append_keys(MergeAppendState
*** 1826,1832 ****
MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
show_sort_group_keys((PlanState *) mstate, "Sort Key",
! plan->numCols, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
--- 1826,1832 ----
MergeAppend *plan = (MergeAppend *) mstate->ps.plan;
show_sort_group_keys((PlanState *) mstate, "Sort Key",
! plan->numCols, 0, plan->sortColIdx,
plan->sortOperators, plan->collations,
plan->nullsFirst,
ancestors, es);
*************** show_agg_keys(AggState *astate, List *an
*** 1850,1856 ****
show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
else
show_sort_group_keys(outerPlanState(astate), "Group Key",
! plan->numCols, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
--- 1850,1856 ----
show_grouping_sets(outerPlanState(astate), plan, ancestors, es);
else
show_sort_group_keys(outerPlanState(astate), "Group Key",
! plan->numCols, 0, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
*************** show_grouping_set_keys(PlanState *planst
*** 1906,1912 ****
if (sortnode)
{
show_sort_group_keys(planstate, "Sort Key",
! sortnode->numCols, sortnode->sortColIdx,
sortnode->sortOperators, sortnode->collations,
sortnode->nullsFirst,
ancestors, es);
--- 1906,1912 ----
if (sortnode)
{
show_sort_group_keys(planstate, "Sort Key",
! sortnode->numCols, 0, sortnode->sortColIdx,
sortnode->sortOperators, sortnode->collations,
sortnode->nullsFirst,
ancestors, es);
*************** show_group_keys(GroupState *gstate, List
*** 1963,1969 ****
/* The key columns refer to the tlist of the child plan */
ancestors = lcons(gstate, ancestors);
show_sort_group_keys(outerPlanState(gstate), "Group Key",
! plan->numCols, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
ancestors = list_delete_first(ancestors);
--- 1963,1969 ----
/* The key columns refer to the tlist of the child plan */
ancestors = lcons(gstate, ancestors);
show_sort_group_keys(outerPlanState(gstate), "Group Key",
! plan->numCols, 0, plan->grpColIdx,
NULL, NULL, NULL,
ancestors, es);
ancestors = list_delete_first(ancestors);
*************** show_group_keys(GroupState *gstate, List
*** 1976,1988 ****
*/
static void
show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es)
{
Plan *plan = planstate->plan;
List *context;
List *result = NIL;
StringInfoData sortkeybuf;
bool useprefix;
int keyno;
--- 1976,1989 ----
*/
static void
show_sort_group_keys(PlanState *planstate, const char *qlabel,
! int nkeys, int nPresortedKeys, AttrNumber *keycols,
Oid *sortOperators, Oid *collations, bool *nullsFirst,
List *ancestors, ExplainState *es)
{
Plan *plan = planstate->plan;
List *context;
List *result = NIL;
+ List *resultPresorted = NIL;
StringInfoData sortkeybuf;
bool useprefix;
int keyno;
*************** show_sort_group_keys(PlanState *planstat
*** 2022,2030 ****
--- 2023,2035 ----
nullsFirst[keyno]);
/* Emit one property-list item per sort key */
result = lappend(result, pstrdup(sortkeybuf.data));
+ if (keyno < nPresortedKeys)
+ resultPresorted = lappend(resultPresorted, exprstr);
}
ExplainPropertyList(qlabel, result, es);
+ if (nPresortedKeys > 0)
+ ExplainPropertyList("Presorted Key", resultPresorted, es);
}
/*
*************** show_sort_info(SortState *sortstate, Exp
*** 2172,2183 ****
--- 2177,2197 ----
appendStringInfoSpaces(es->str, es->indent * 2);
appendStringInfo(es->str, "Sort Method: %s %s: %ldkB\n",
sortMethod, spaceType, spaceUsed);
+ if (sortstate->skipKeys)
+ {
+ appendStringInfoSpaces(es->str, es->indent * 2);
+ appendStringInfo(es->str, "Sort groups: %ld\n",
+ sortstate->groupsCount);
+ }
}
else
{
ExplainPropertyText("Sort Method", sortMethod, es);
ExplainPropertyLong("Sort Space Used", spaceUsed, es);
ExplainPropertyText("Sort Space Type", spaceType, es);
+ if (sortstate->skipKeys)
+ ExplainPropertyLong("Sort groups: %ld",
+ sortstate->groupsCount, es);
}
}
}
diff --git a/src/backend/executor/execAmi.c b/src/backend/executor/execAmi.c
new file mode 100644
index 2587ef7..4e7c222
*** a/src/backend/executor/execAmi.c
--- b/src/backend/executor/execAmi.c
*************** ExecSupportsMarkRestore(Path *pathnode)
*** 395,403 ****
case T_IndexScan:
case T_IndexOnlyScan:
case T_Material:
- case T_Sort:
return true;
case T_CustomScan:
Assert(IsA(pathnode, CustomPath));
if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
--- 395,409 ----
case T_IndexScan:
case T_IndexOnlyScan:
case T_Material:
return true;
+ case T_Sort:
+ /* With skipCols sort node holds only last bucket */
+ if (((SortPath *)pathnode)->skipCols == 0)
+ return true;
+ else
+ return false;
+
case T_CustomScan:
Assert(IsA(pathnode, CustomPath));
if (((CustomPath *) pathnode)->flags & CUSTOMPATH_SUPPORT_MARK_RESTORE)
*************** ExecSupportsBackwardScan(Plan *node)
*** 510,519 ****
return false;
case T_Material:
- case T_Sort:
/* these don't evaluate tlist */
return true;
case T_LockRows:
case T_Limit:
/* these don't evaluate tlist */
--- 516,531 ----
return false;
case T_Material:
/* these don't evaluate tlist */
return true;
+ case T_Sort:
+ /* With skipCols sort node holds only last bucket */
+ if (((Sort *)node)->skipCols == 0)
+ return true;
+ else
+ return false;
+
case T_LockRows:
case T_Limit:
/* these don't evaluate tlist */
*************** IndexSupportsBackwardScan(Oid indexid)
*** 566,577 ****
}
/*
! * ExecMaterializesOutput - does a plan type materialize its output?
*
! * Returns true if the plan node type is one that automatically materializes
! * its output (typically by keeping it in a tuplestore). For such plans,
! * a rescan without any parameter change will have zero startup cost and
! * very low per-tuple cost.
*/
bool
ExecMaterializesOutput(NodeTag plantype)
--- 578,589 ----
}
/*
! * ExecMaterializesOutput - can a plan type materialize its output?
*
! * Returns true if the plan node type can materialize its output. When this
! * function returns true, it should be rechecked for Plan node itself using
! * ExecPlanMaterializesOutput function. It might appears that despite this
! * plan type can materialize output, particular plan does not.
*/
bool
ExecMaterializesOutput(NodeTag plantype)
*************** ExecMaterializesOutput(NodeTag plantype)
*** 582,587 ****
--- 594,601 ----
case T_FunctionScan:
case T_CteScan:
case T_WorkTableScan:
+ return true;
+
case T_Sort:
return true;
*************** ExecMaterializesOutput(NodeTag plantype)
*** 591,593 ****
--- 605,630 ----
return false;
}
+
+ /*
+ * ExecPlanMaterializesOutput - does a plan materialize its output?
+ *
+ * Returns true if the plan node isautomatically materializes its output
+ * (typically by keeping it in a tuplestore). For such plans, a rescan without
+ * any parameter change will have zero startup cost and very low per-tuple cost.
+ */
+ bool
+ ExecPlanMaterializesOutput(Plan *node)
+ {
+ if (node->type == T_Sort)
+ {
+ if (((Sort *)node)->skipCols == 0)
+ return true;
+ else
+ return false;
+ }
+ else
+ {
+ return ExecMaterializesOutput(node->type);
+ }
+ }
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
new file mode 100644
index ce2fc28..d2c04e5
*** a/src/backend/executor/nodeAgg.c
--- b/src/backend/executor/nodeAgg.c
*************** initialize_phase(AggState *aggstate, int
*** 567,572 ****
--- 567,573 ----
sortnode->collations,
sortnode->nullsFirst,
work_mem,
+ false,
false);
}
*************** initialize_aggregate(AggState *aggstate,
*** 645,651 ****
pertrans->sortOperators,
pertrans->sortCollations,
pertrans->sortNullsFirst,
! work_mem, false);
}
/*
--- 646,652 ----
pertrans->sortOperators,
pertrans->sortCollations,
pertrans->sortNullsFirst,
! work_mem, false, false);
}
/*
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
new file mode 100644
index a34dcc5..2369980
*** a/src/backend/executor/nodeSort.c
--- b/src/backend/executor/nodeSort.c
***************
*** 15,25 ****
--- 15,113 ----
#include "postgres.h"
+ #include "access/htup_details.h"
#include "executor/execdebug.h"
#include "executor/nodeSort.h"
#include "miscadmin.h"
+ #include "utils/lsyscache.h"
#include "utils/tuplesort.h"
+ /*
+ * Check if first "skipCols" sort values are equal.
+ */
+ static bool
+ cmpSortSkipCols(SortState *node, TupleDesc tupDesc, HeapTuple a, TupleTableSlot *b)
+ {
+ int n = ((Sort *)node->ss.ps.plan)->skipCols, i;
+
+ for (i = 0; i < n; i++)
+ {
+ Datum datumA, datumB, result;
+ bool isnullA, isnullB;
+ AttrNumber attno = node->skipKeys[i].attno;
+ SkipKeyData *key;
+
+ datumA = heap_getattr(a, attno, tupDesc, &isnullA);
+ datumB = slot_getattr(b, attno, &isnullB);
+
+ /* Special case for NULL-vs-NULL, else use standard comparison */
+ if (isnullA || isnullB)
+ {
+ if (isnullA == isnullB)
+ continue;
+ else
+ return false;
+ }
+
+ key = &node->skipKeys[i];
+
+ key->fcinfo.arg[0] = datumA;
+ key->fcinfo.arg[1] = datumB;
+
+ /* just for paranoia's sake, we reset isnull each time */
+ key->fcinfo.isnull = false;
+
+ result = FunctionCallInvoke(&key->fcinfo);
+
+ /* Check for null result, since caller is clearly not expecting one */
+ if (key->fcinfo.isnull)
+ elog(ERROR, "function %u returned NULL", key->flinfo.fn_oid);
+
+ if (!DatumGetBool(result))
+ return false;
+ }
+ return true;
+ }
+
+ /*
+ * Prepare information for skipKeys comparison.
+ */
+ static void
+ prepareSkipCols(Sort *plannode, SortState *node)
+ {
+ int skipCols = plannode->skipCols, i;
+
+ node->skipKeys = (SkipKeyData *)palloc(skipCols * sizeof(SkipKeyData));
+
+ for (i = 0; i < skipCols; i++)
+ {
+ Oid equalityOp, equalityFunc;
+ SkipKeyData *key;
+
+ key = &node->skipKeys[i];
+ key->attno = plannode->sortColIdx[i];
+
+ equalityOp = get_equality_op_for_ordering_op(
+ plannode->sortOperators[i], NULL);
+ if (!OidIsValid(equalityOp))
+ elog(ERROR, "missing equality operator for ordering operator %u",
+ plannode->sortOperators[i]);
+
+ equalityFunc = get_opcode(equalityOp);
+ if (!OidIsValid(equalityFunc))
+ elog(ERROR, "missing function for operator %u", equalityOp);
+
+ /* Lookup the comparison function */
+ fmgr_info_cxt(equalityFunc, &key->flinfo, CurrentMemoryContext);
+
+ /* We can initialize the callinfo just once and re-use it */
+ InitFunctionCallInfoData(key->fcinfo, &key->flinfo, 2,
+ plannode->collations[i], NULL, NULL);
+ key->fcinfo.argnull[0] = false;
+ key->fcinfo.argnull[1] = false;
+ }
+ }
+
/* ----------------------------------------------------------------
* ExecSort
*************** ExecSort(SortState *node)
*** 42,47 ****
--- 130,140 ----
ScanDirection dir;
Tuplesortstate *tuplesortstate;
TupleTableSlot *slot;
+ Sort *plannode = (Sort *) node->ss.ps.plan;
+ PlanState *outerNode;
+ TupleDesc tupDesc;
+ int skipCols = plannode->skipCols;
+ int64 nTuples = 0;
/*
* get state info from node
*************** ExecSort(SortState *node)
*** 54,87 ****
tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
/*
* If first time through, read all tuples from outer plan and pass them to
* tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
*/
! if (!node->sort_Done)
! {
! Sort *plannode = (Sort *) node->ss.ps.plan;
! PlanState *outerNode;
! TupleDesc tupDesc;
!
! SO1_printf("ExecSort: %s\n",
! "sorting subplan");
! /*
! * Want to scan subplan in the forward direction while creating the
! * sorted data.
! */
! estate->es_direction = ForwardScanDirection;
! /*
! * Initialize tuplesort module.
! */
! SO1_printf("ExecSort: %s\n",
! "calling tuplesort_begin");
! outerNode = outerPlanState(node);
! tupDesc = ExecGetResultType(outerNode);
tuplesortstate = tuplesort_begin_heap(tupDesc,
plannode->numCols,
plannode->sortColIdx,
--- 147,189 ----
tuplesortstate = (Tuplesortstate *) node->tuplesortstate;
/*
+ * Return next tuple from sorted set if any.
+ */
+ if (node->sort_Done)
+ {
+ slot = node->ss.ps.ps_ResultTupleSlot;
+ if (tuplesort_gettupleslot(tuplesortstate,
+ ScanDirectionIsForward(dir),
+ slot, NULL) || node->finished)
+ return slot;
+ }
+
+ /*
* If first time through, read all tuples from outer plan and pass them to
* tuplesort.c. Subsequent calls just fetch tuples from tuplesort.
*/
! SO1_printf("ExecSort: %s\n",
! "sorting subplan");
! /*
! * Want to scan subplan in the forward direction while creating the
! * sorted data.
! */
! estate->es_direction = ForwardScanDirection;
! /*
! * Initialize tuplesort module.
! */
! SO1_printf("ExecSort: %s\n",
! "calling tuplesort_begin");
! outerNode = outerPlanState(node);
! tupDesc = ExecGetResultType(outerNode);
+ if (skipCols == 0)
+ {
+ /* Regular case: no skip cols */
tuplesortstate = tuplesort_begin_heap(tupDesc,
plannode->numCols,
plannode->sortColIdx,
*************** ExecSort(SortState *node)
*** 89,132 ****
plannode->collations,
plannode->nullsFirst,
work_mem,
! node->randomAccess);
! if (node->bounded)
! tuplesort_set_bound(tuplesortstate, node->bound);
node->tuplesortstate = (void *) tuplesortstate;
! /*
! * Scan the subplan and feed all the tuples to tuplesort.
! */
! for (;;)
{
! slot = ExecProcNode(outerNode);
if (TupIsNull(slot))
break;
!
tuplesort_puttupleslot(tuplesortstate, slot);
}
! /*
! * Complete the sort.
! */
! tuplesort_performsort(tuplesortstate);
! /*
! * restore to user specified direction
! */
! estate->es_direction = dir;
! /*
! * finally set the sorted flag to true
! */
! node->sort_Done = true;
! node->bounded_Done = node->bounded;
! node->bound_Done = node->bound;
! SO1_printf("ExecSort: %s\n", "sorting done");
}
SO1_printf("ExecSort: %s\n",
"retrieving tuple from tuplesort");
--- 191,342 ----
plannode->collations,
plannode->nullsFirst,
work_mem,
! node->randomAccess,
! false);
node->tuplesortstate = (void *) tuplesortstate;
! if (node->bounded)
! tuplesort_set_bound(tuplesortstate, node->bound);
! }
! else
! {
! /* Partial sort case */
! if (node->tuplesortstate == NULL)
! {
! /*
! * We are going to process the first group of presorted data.
! * Initialize support structures for cmpSortSkipCols - already
! * sorted columns.
! */
! prepareSkipCols(plannode, node);
! /*
! * Only pass on remaining columns that are unsorted. Skip
! * abbreviated keys usage for partial sort. We unlikely will have
! * huge groups with partial sort. Therefore usage of abbreviated
! * keys would be likely a waste of time.
! */
! tuplesortstate = tuplesort_begin_heap(
! tupDesc,
! plannode->numCols - skipCols,
! &(plannode->sortColIdx[skipCols]),
! &(plannode->sortOperators[skipCols]),
! &(plannode->collations[skipCols]),
! &(plannode->nullsFirst[skipCols]),
! work_mem,
! false,
! true);
! node->tuplesortstate = (void *) tuplesortstate;
! node->groupsCount++;
! }
! else
{
! /* Next group of presorted data */
! tuplesort_reset((Tuplesortstate *) node->tuplesortstate);
! node->groupsCount++;
! }
!
! /* Calculate remaining bound for bounded sort */
! if (node->bounded)
! tuplesort_set_bound(tuplesortstate, node->bound - node->bound_Done);
! }
!
! /*
! * Put next group of tuples where skipCols sort values are equal to
! * tuplesort.
! */
! for (;;)
! {
! slot = ExecProcNode(outerNode);
+ if (skipCols == 0)
+ {
+ /* Regular sort case: put all tuples to the tuplesort */
if (TupIsNull(slot))
+ {
+ node->finished = true;
break;
! }
tuplesort_puttupleslot(tuplesortstate, slot);
+ nTuples++;
}
+ else
+ {
+ /* Partial sort case: put group of presorted data to the tuplesort */
+ if (!node->prev)
+ {
+ /* First tuple */
+ if (TupIsNull(slot))
+ {
+ node->finished = true;
+ break;
+ }
+ else
+ {
+ node->prev = ExecCopySlotTuple(slot);
+ }
+ }
+ else
+ {
+ /* Put previous tuple into tuplesort */
+ ExecStoreTuple(node->prev, node->ss.ps.ps_ResultTupleSlot, InvalidBuffer, false);
+ tuplesort_puttupleslot(tuplesortstate, node->ss.ps.ps_ResultTupleSlot);
+ nTuples++;
! if (TupIsNull(slot))
! {
! node->finished = true;
! break;
! }
! else
! {
! bool cmp;
! cmp = cmpSortSkipCols(node, tupDesc, node->prev, slot);
! /* Replace previous tuple with current one */
! heap_freetuple(node->prev);
! node->prev = ExecCopySlotTuple(slot);
! /*
! * When skipCols are not equal then group of presorted data
! * is finished
! */
! if (!cmp)
! break;
! }
! }
! }
! }
!
! /*
! * Complete the sort.
! */
! tuplesort_performsort(tuplesortstate);
!
! /*
! * restore to user specified direction
! */
! estate->es_direction = dir;
!
! /*
! * finally set the sorted flag to true
! */
! node->sort_Done = true;
! node->bounded_Done = node->bounded;
!
! /*
! * Adjust bound_Done with number of tuples we've actually sorted.
! */
! if (node->bounded)
! {
! if (node->finished)
! node->bound_Done = node->bound;
! else
! node->bound_Done = Min(node->bound, node->bound_Done + nTuples);
}
+ SO1_printf("ExecSort: %s\n", "sorting done");
+
SO1_printf("ExecSort: %s\n",
"retrieving tuple from tuplesort");
*************** ExecInitSort(Sort *node, EState *estate,
*** 157,162 ****
--- 367,381 ----
"initializing sort node");
/*
+ * skipCols can't be used with either EXEC_FLAG_REWIND, EXEC_FLAG_BACKWARD
+ * or EXEC_FLAG_MARK, because we hold only current bucket in
+ * tuplesortstate.
+ */
+ Assert(node->skipCols == 0 || (eflags & (EXEC_FLAG_REWIND |
+ EXEC_FLAG_BACKWARD |
+ EXEC_FLAG_MARK)) == 0);
+
+ /*
* create state structure
*/
sortstate = makeNode(SortState);
*************** ExecInitSort(Sort *node, EState *estate,
*** 174,180 ****
--- 393,404 ----
sortstate->bounded = false;
sortstate->sort_Done = false;
+ sortstate->finished = false;
sortstate->tuplesortstate = NULL;
+ sortstate->prev = NULL;
+ sortstate->bound_Done = 0;
+ sortstate->groupsCount = 0;
+ sortstate->skipKeys = NULL;
/*
* Miscellaneous initialization
*************** ExecReScanSort(SortState *node)
*** 318,323 ****
--- 542,548 ----
node->sort_Done = false;
tuplesort_end((Tuplesortstate *) node->tuplesortstate);
node->tuplesortstate = NULL;
+ node->bound_Done = 0;
/*
* if chgParam of subnode is not null then plan will be re-scanned by
diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c
new file mode 100644
index 4f39dad..f8e1596
*** a/src/backend/nodes/copyfuncs.c
--- b/src/backend/nodes/copyfuncs.c
*************** _copySort(const Sort *from)
*** 832,837 ****
--- 832,838 ----
CopyPlanFields((const Plan *) from, (Plan *) newnode);
COPY_SCALAR_FIELD(numCols);
+ COPY_SCALAR_FIELD(skipCols);
COPY_POINTER_FIELD(sortColIdx, from->numCols * sizeof(AttrNumber));
COPY_POINTER_FIELD(sortOperators, from->numCols * sizeof(Oid));
COPY_POINTER_FIELD(collations, from->numCols * sizeof(Oid));
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
new file mode 100644
index 90fecb1..24b5993
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outSort(StringInfo str, const Sort *nod
*** 794,799 ****
--- 794,800 ----
_outPlanInfo(str, (const Plan *) node);
WRITE_INT_FIELD(numCols);
+ WRITE_INT_FIELD(skipCols);
appendStringInfoString(str, " :sortColIdx");
for (i = 0; i < node->numCols; i++)
diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c
new file mode 100644
index 894a48f..e90a7d4
*** a/src/backend/nodes/readfuncs.c
--- b/src/backend/nodes/readfuncs.c
*************** _readSort(void)
*** 1967,1972 ****
--- 1967,1973 ----
ReadCommonPlan(&local_node->plan);
READ_INT_FIELD(numCols);
+ READ_INT_FIELD(skipCols);
READ_ATTRNUMBER_ARRAY(sortColIdx, local_node->numCols);
READ_OID_ARRAY(sortOperators, local_node->numCols);
READ_OID_ARRAY(collations, local_node->numCols);
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
new file mode 100644
index 2a49639..30d7327
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_recursive_union(Path *runion, Path
*** 1429,1434 ****
--- 1429,1441 ----
* Determines and returns the cost of sorting a relation, including
* the cost of reading the input data.
*
+ * Sort could be either full sort of relation or partial sort when we already
+ * have data presorted by some of required pathkeys. In the second case
+ * we estimate number of groups which source data is divided to by presorted
+ * pathkeys. And then estimate cost of sorting each individual group assuming
+ * data is divided into group uniformly. Also, if LIMIT is specified then
+ * we have to pull from source and sort only some of total groups.
+ *
* If the total volume of data to sort is less than sort_mem, we will do
* an in-memory sort, which requires no I/O and about t*log2(t) tuple
* comparisons for t tuples.
*************** cost_recursive_union(Path *runion, Path
*** 1455,1461 ****
* work that has to be done to prepare the inputs to the comparison operators.
*
* 'pathkeys' is a list of sort keys
! * 'input_cost' is the total cost for reading the input data
* 'tuples' is the number of tuples in the relation
* 'width' is the average tuple width in bytes
* 'comparison_cost' is the extra cost per comparison, if any
--- 1462,1469 ----
* work that has to be done to prepare the inputs to the comparison operators.
*
* 'pathkeys' is a list of sort keys
! * 'input_startup_cost' is the startup cost for reading the input data
! * 'input_total_cost' is the total cost for reading the input data
* 'tuples' is the number of tuples in the relation
* 'width' is the average tuple width in bytes
* 'comparison_cost' is the extra cost per comparison, if any
*************** cost_recursive_union(Path *runion, Path
*** 1471,1485 ****
*/
void
cost_sort(Path *path, PlannerInfo *root,
! List *pathkeys, Cost input_cost, double tuples, int width,
! Cost comparison_cost, int sort_mem,
double limit_tuples)
{
! Cost startup_cost = input_cost;
! Cost run_cost = 0;
double input_bytes = relation_byte_size(tuples, width);
double output_bytes;
double output_tuples;
long sort_mem_bytes = sort_mem * 1024L;
if (!enable_sort)
--- 1479,1500 ----
*/
void
cost_sort(Path *path, PlannerInfo *root,
! List *pathkeys, int presorted_keys,
! Cost input_startup_cost, Cost input_total_cost,
! double tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples)
{
! Cost startup_cost = input_startup_cost;
! Cost run_cost = 0,
! rest_cost,
! group_cost,
! input_run_cost = input_total_cost - input_startup_cost;
double input_bytes = relation_byte_size(tuples, width);
double output_bytes;
double output_tuples;
+ double num_groups,
+ group_input_bytes,
+ group_tuples;
long sort_mem_bytes = sort_mem * 1024L;
if (!enable_sort)
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1509,1521 ****
output_bytes = input_bytes;
}
! if (output_bytes > sort_mem_bytes)
{
/*
* We'll have to use a disk-based sort of all the tuples
*/
! double npages = ceil(input_bytes / BLCKSZ);
! double nruns = input_bytes / sort_mem_bytes;
double mergeorder = tuplesort_merge_order(sort_mem_bytes);
double log_runs;
double npageaccesses;
--- 1524,1573 ----
output_bytes = input_bytes;
}
! /*
! * Estimate number of groups which dataset is divided by presorted keys.
! */
! if (presorted_keys > 0)
! {
! List *presortedExprs = NIL;
! ListCell *l;
! int i = 0;
!
! /* Extract presorted keys as list of expressions */
! foreach(l, pathkeys)
! {
! PathKey *key = (PathKey *)lfirst(l);
! EquivalenceMember *member = (EquivalenceMember *)
! lfirst(list_head(key->pk_eclass->ec_members));
!
! presortedExprs = lappend(presortedExprs, member->em_expr);
!
! i++;
! if (i >= presorted_keys)
! break;
! }
!
! /* Estimate number of groups with equal presorted keys */
! num_groups = estimate_num_groups(root, presortedExprs, tuples, NULL);
! }
! else
! {
! num_groups = 1.0;
! }
!
! /*
! * Estimate average cost of sorting of one group where presorted keys are
! * equal.
! */
! group_input_bytes = input_bytes / num_groups;
! group_tuples = tuples / num_groups;
! if (output_bytes > sort_mem_bytes && group_input_bytes > sort_mem_bytes)
{
/*
* We'll have to use a disk-based sort of all the tuples
*/
! double npages = ceil(group_input_bytes / BLCKSZ);
! double nruns = group_input_bytes / sort_mem_bytes;
double mergeorder = tuplesort_merge_order(sort_mem_bytes);
double log_runs;
double npageaccesses;
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1525,1531 ****
*
* Assume about N log2 N comparisons
*/
! startup_cost += comparison_cost * tuples * LOG2(tuples);
/* Disk costs */
--- 1577,1583 ----
*
* Assume about N log2 N comparisons
*/
! group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
/* Disk costs */
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1536,1545 ****
log_runs = 1.0;
npageaccesses = 2.0 * npages * log_runs;
/* Assume 3/4ths of accesses are sequential, 1/4th are not */
! startup_cost += npageaccesses *
(seq_page_cost * 0.75 + random_page_cost * 0.25);
}
! else if (tuples > 2 * output_tuples || input_bytes > sort_mem_bytes)
{
/*
* We'll use a bounded heap-sort keeping just K tuples in memory, for
--- 1588,1597 ----
log_runs = 1.0;
npageaccesses = 2.0 * npages * log_runs;
/* Assume 3/4ths of accesses are sequential, 1/4th are not */
! group_cost += npageaccesses *
(seq_page_cost * 0.75 + random_page_cost * 0.25);
}
! else if (group_tuples > 2 * output_tuples || group_input_bytes > sort_mem_bytes)
{
/*
* We'll use a bounded heap-sort keeping just K tuples in memory, for
*************** cost_sort(Path *path, PlannerInfo *root,
*** 1547,1560 ****
* factor is a bit higher than for quicksort. Tweak it so that the
* cost curve is continuous at the crossover point.
*/
! startup_cost += comparison_cost * tuples * LOG2(2.0 * output_tuples);
}
else
{
/* We'll use plain quicksort on all the input tuples */
! startup_cost += comparison_cost * tuples * LOG2(tuples);
}
/*
* Also charge a small amount (arbitrarily set equal to operator cost) per
* extracted tuple. We don't charge cpu_tuple_cost because a Sort node
--- 1599,1624 ----
* factor is a bit higher than for quicksort. Tweak it so that the
* cost curve is continuous at the crossover point.
*/
! group_cost = comparison_cost * group_tuples * LOG2(2.0 * output_tuples);
}
else
{
/* We'll use plain quicksort on all the input tuples */
! group_cost = comparison_cost * group_tuples * LOG2(group_tuples);
}
+ /* Add per group cost of fetching tuples from input */
+ group_cost += input_run_cost / num_groups;
+
+ /*
+ * We've to sort first group to start output from node. Sorting rest of
+ * groups are required to return all the other tuples.
+ */
+ startup_cost += group_cost;
+ rest_cost = (num_groups * (output_tuples / tuples) - 1.0) * group_cost;
+ if (rest_cost > 0.0)
+ run_cost += rest_cost;
+
/*
* Also charge a small amount (arbitrarily set equal to operator cost) per
* extracted tuple. We don't charge cpu_tuple_cost because a Sort node
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2307,2312 ****
--- 2371,2378 ----
cost_sort(&sort_path,
root,
outersortkeys,
+ pathkeys_common(outer_path->pathkeys, outersortkeys),
+ outer_path->startup_cost,
outer_path->total_cost,
outer_path_rows,
outer_path->pathtarget->width,
*************** initial_cost_mergejoin(PlannerInfo *root
*** 2333,2338 ****
--- 2399,2406 ----
cost_sort(&sort_path,
root,
innersortkeys,
+ pathkeys_common(inner_path->pathkeys, innersortkeys),
+ inner_path->startup_cost,
inner_path->total_cost,
inner_path_rows,
inner_path->pathtarget->width,
*************** cost_subplan(PlannerInfo *root, SubPlan
*** 3067,3073 ****
* every time.
*/
if (subplan->parParam == NIL &&
! ExecMaterializesOutput(nodeTag(plan)))
sp_cost.startup += plan->startup_cost;
else
sp_cost.per_tuple += plan->startup_cost;
--- 3135,3141 ----
* every time.
*/
if (subplan->parParam == NIL &&
! ExecPlanMaterializesOutput(plan))
sp_cost.startup += plan->startup_cost;
else
sp_cost.per_tuple += plan->startup_cost;
diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c
new file mode 100644
index 4436ac1..d60c421
*** a/src/backend/optimizer/path/pathkeys.c
--- b/src/backend/optimizer/path/pathkeys.c
***************
*** 26,31 ****
--- 26,32 ----
#include "optimizer/paths.h"
#include "optimizer/tlist.h"
#include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys);
*************** compare_pathkeys(List *keys1, List *keys
*** 309,314 ****
--- 310,341 ----
}
/*
+ * pathkeys_common
+ * Returns length of longest common prefix of keys1 and keys2.
+ */
+ int
+ pathkeys_common(List *keys1, List *keys2)
+ {
+ int n;
+ ListCell *key1,
+ *key2;
+ n = 0;
+
+ forboth(key1, keys1, key2, keys2)
+ {
+ PathKey *pathkey1 = (PathKey *) lfirst(key1);
+ PathKey *pathkey2 = (PathKey *) lfirst(key2);
+
+ if (pathkey1 != pathkey2)
+ return n;
+ n++;
+ }
+
+ return n;
+ }
+
+
+ /*
* pathkeys_contained_in
* Common special case of compare_pathkeys: we just want to know
* if keys2 are at least as well sorted as keys1.
*************** get_cheapest_path_for_pathkeys(List *pat
*** 368,375 ****
/*
* get_cheapest_fractional_path_for_pathkeys
* Find the cheapest path (for retrieving a specified fraction of all
! * the tuples) that satisfies the given pathkeys and parameterization.
! * Return NULL if no such path.
*
* See compare_fractional_path_costs() for the interpretation of the fraction
* parameter.
--- 395,406 ----
/*
* get_cheapest_fractional_path_for_pathkeys
* Find the cheapest path (for retrieving a specified fraction of all
! * the tuples) that satisfies given parameterization and at least partially
! * satisfies the given pathkeys. Return NULL if no path found.
! * If pathkeys are satisfied partially then we would have to do partial
! * sort in order to satisfy pathkeys completely. Since partial sort
! * consumes data by presorted groups, we would have to consume more data
! * than in the case of fully presorted path.
*
* See compare_fractional_path_costs() for the interpretation of the fraction
* parameter.
*************** get_cheapest_path_for_pathkeys(List *pat
*** 378,409 ****
* 'pathkeys' represents a required ordering (in canonical form!)
* 'required_outer' denotes allowable outer relations for parameterized paths
* 'fraction' is the fraction of the total tuples expected to be retrieved
*/
Path *
get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
Relids required_outer,
! double fraction)
{
Path *matched_path = NULL;
ListCell *l;
foreach(l, paths)
{
Path *path = (Path *) lfirst(l);
/*
! * Since cost comparison is a lot cheaper than pathkey comparison, do
! * that first. (XXX is that still true?)
*/
! if (matched_path != NULL &&
! compare_fractional_path_costs(matched_path, path, fraction) <= 0)
! continue;
! if (pathkeys_contained_in(pathkeys, path->pathkeys) &&
bms_is_subset(PATH_REQ_OUTER(path), required_outer))
matched_path = path;
}
return matched_path;
}
--- 409,480 ----
* 'pathkeys' represents a required ordering (in canonical form!)
* 'required_outer' denotes allowable outer relations for parameterized paths
* 'fraction' is the fraction of the total tuples expected to be retrieved
+ * 'num_groups' array of group numbers which pathkeys divide data to. Should
+ * be estimated using estimate_partialsort_groups().
*/
Path *
get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
Relids required_outer,
! double fraction,
! double *num_groups)
{
Path *matched_path = NULL;
+ int matched_n_common_pathkeys = 0,
+ costs_cmp, n_common_pathkeys,
+ n_pathkeys = list_length(pathkeys);
ListCell *l;
+ double matched_fraction;
foreach(l, paths)
{
Path *path = (Path *) lfirst(l);
+ double current_fraction;
+
+ n_common_pathkeys = pathkeys_common(pathkeys, path->pathkeys);
+
+ if (n_pathkeys != 0 && n_common_pathkeys == 0)
+ continue;
/*
! * Partial sort consumes data not per tuple but per presorted group.
! * Increase fraction of tuples we have to read from source path by
! * one presorted group.
*/
! current_fraction = fraction;
! if (n_common_pathkeys < n_pathkeys)
! {
! current_fraction += 1.0 / num_groups[n_common_pathkeys - 1];
! current_fraction = Min(current_fraction, 1.0);
! }
! /*
! * Do cost comparison assuming paths could have different number
! * of required pathkeys and therefore different fraction of tuples
! * to fetch.
! */
! if (matched_path != NULL)
! {
! costs_cmp = compare_bifractional_path_costs(matched_path, path,
! matched_fraction, current_fraction);
! }
! else
! {
! costs_cmp = 1;
! }
!
! /*
! * Cheaper path with matching outer becomes a new leader.
! */
! if (costs_cmp > 0 &&
bms_is_subset(PATH_REQ_OUTER(path), required_outer))
+ {
matched_path = path;
+ matched_n_common_pathkeys = n_common_pathkeys;
+ matched_fraction = current_fraction;
+ }
}
+
return matched_path;
}
*************** right_merge_direction(PlannerInfo *root,
*** 1448,1456 ****
* Count the number of pathkeys that are useful for meeting the
* query's requested output ordering.
*
! * Unlike merge pathkeys, this is an all-or-nothing affair: it does us
! * no good to order by just the first key(s) of the requested ordering.
! * So the result is always either 0 or list_length(root->query_pathkeys).
*/
static int
pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
--- 1519,1526 ----
* Count the number of pathkeys that are useful for meeting the
* query's requested output ordering.
*
! * Returns number of pathkeys that maches given argument. Others can be
! * satisfied by partial sort.
*/
static int
pathkeys_useful_for_ordering(PlannerInfo *root, List *pathkeys)
*************** pathkeys_useful_for_ordering(PlannerInfo
*** 1461,1473 ****
if (pathkeys == NIL)
return 0; /* unordered path */
! if (pathkeys_contained_in(root->query_pathkeys, pathkeys))
! {
! /* It's useful ... or at least the first N keys are */
! return list_length(root->query_pathkeys);
! }
!
! return 0; /* path ordering not useful */
}
/*
--- 1531,1542 ----
if (pathkeys == NIL)
return 0; /* unordered path */
! /*
! * Return the number of path keys in common, or 0 if there are none. Any
! * first common pathkeys could be useful for ordering because we can use
! * partial sort.
! */
! return pathkeys_common(root->query_pathkeys, pathkeys);
}
/*
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
new file mode 100644
index 47158f6..4421615
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** static MergeJoin *make_mergejoin(List *t
*** 226,232 ****
bool *mergenullsfirst,
Plan *lefttree, Plan *righttree,
JoinType jointype);
! static Sort *make_sort(Plan *lefttree, int numCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst);
static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
--- 226,232 ----
bool *mergenullsfirst,
Plan *lefttree, Plan *righttree,
JoinType jointype);
! static Sort *make_sort(Plan *lefttree, int numCols, int skipCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst);
static Plan *prepare_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
*************** static Plan *prepare_sort_from_pathkeys(
*** 241,250 ****
static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
TargetEntry *tle,
Relids relids);
! static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys);
static Sort *make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
! Plan *lefttree);
static Material *make_material(Plan *lefttree);
static WindowAgg *make_windowagg(List *tlist, Index winref,
int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
--- 241,252 ----
static EquivalenceMember *find_ec_member_for_tle(EquivalenceClass *ec,
TargetEntry *tle,
Relids relids);
! static Sort *make_sort_from_pathkeys(Plan *lefttree, List *pathkeys,
! int skipCols);
static Sort *make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
! Plan *lefttree,
! int skipCols);
static Material *make_material(Plan *lefttree);
static WindowAgg *make_windowagg(List *tlist, Index winref,
int partNumCols, AttrNumber *partColIdx, Oid *partOperators,
*************** create_merge_append_plan(PlannerInfo *ro
*** 1062,1067 ****
--- 1064,1070 ----
Oid *sortOperators;
Oid *collations;
bool *nullsFirst;
+ int n_common_pathkeys;
/* Build the child plan */
/* Must insist that all children return the same tlist */
*************** create_merge_append_plan(PlannerInfo *ro
*** 1096,1104 ****
numsortkeys * sizeof(bool)) == 0);
/* Now, insert a Sort node if subplan isn't sufficiently ordered */
! if (!pathkeys_contained_in(pathkeys, subpath->pathkeys))
{
Sort *sort = make_sort(subplan, numsortkeys,
sortColIdx, sortOperators,
collations, nullsFirst);
--- 1099,1109 ----
numsortkeys * sizeof(bool)) == 0);
/* Now, insert a Sort node if subplan isn't sufficiently ordered */
! n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys);
! if (n_common_pathkeys < list_length(pathkeys))
{
Sort *sort = make_sort(subplan, numsortkeys,
+ n_common_pathkeys,
sortColIdx, sortOperators,
collations, nullsFirst);
*************** create_sort_plan(PlannerInfo *root, Sort
*** 1504,1509 ****
--- 1509,1515 ----
{
Sort *plan;
Plan *subplan;
+ int n_common_pathkeys;
/*
* We don't want any excess columns in the sorted tuples, so request a
*************** create_sort_plan(PlannerInfo *root, Sort
*** 1513,1519 ****
subplan = create_plan_recurse(root, best_path->subpath,
flags | CP_SMALL_TLIST);
! plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys);
copy_generic_path_info(&plan->plan, (Path *) best_path);
--- 1519,1529 ----
subplan = create_plan_recurse(root, best_path->subpath,
flags | CP_SMALL_TLIST);
! n_common_pathkeys = pathkeys_common(best_path->path.pathkeys,
! best_path->subpath->pathkeys);
!
! plan = make_sort_from_pathkeys(subplan, best_path->path.pathkeys,
! n_common_pathkeys);
copy_generic_path_info(&plan->plan, (Path *) best_path);
*************** create_groupingsets_plan(PlannerInfo *ro
*** 1759,1765 ****
sort_plan = (Plan *)
make_sort_from_groupcols(groupClause,
new_grpColIdx,
! subplan);
agg_plan = (Plan *) make_agg(NIL,
NIL,
--- 1769,1776 ----
sort_plan = (Plan *)
make_sort_from_groupcols(groupClause,
new_grpColIdx,
! subplan,
! 0);
agg_plan = (Plan *) make_agg(NIL,
NIL,
*************** create_mergejoin_plan(PlannerInfo *root,
*** 3586,3593 ****
*/
if (best_path->outersortkeys)
{
! Sort *sort = make_sort_from_pathkeys(outer_plan,
! best_path->outersortkeys);
label_sort_with_costsize(root, sort, -1.0);
outer_plan = (Plan *) sort;
--- 3597,3610 ----
*/
if (best_path->outersortkeys)
{
! Sort *sort;
! int n_common_pathkeys;
!
! n_common_pathkeys = pathkeys_common(best_path->outersortkeys,
! best_path->jpath.outerjoinpath->pathkeys);
!
! sort = make_sort_from_pathkeys(outer_plan, best_path->outersortkeys,
! n_common_pathkeys);
label_sort_with_costsize(root, sort, -1.0);
outer_plan = (Plan *) sort;
*************** create_mergejoin_plan(PlannerInfo *root,
*** 3598,3605 ****
if (best_path->innersortkeys)
{
! Sort *sort = make_sort_from_pathkeys(inner_plan,
! best_path->innersortkeys);
label_sort_with_costsize(root, sort, -1.0);
inner_plan = (Plan *) sort;
--- 3615,3628 ----
if (best_path->innersortkeys)
{
! Sort *sort;
! int n_common_pathkeys;
!
! n_common_pathkeys = pathkeys_common(best_path->innersortkeys,
! best_path->jpath.innerjoinpath->pathkeys);
!
! sort = make_sort_from_pathkeys(inner_plan, best_path->innersortkeys,
! n_common_pathkeys);
label_sort_with_costsize(root, sort, -1.0);
inner_plan = (Plan *) sort;
*************** label_sort_with_costsize(PlannerInfo *ro
*** 4617,4623 ****
Plan *lefttree = plan->plan.lefttree;
Path sort_path; /* dummy for result of cost_sort */
! cost_sort(&sort_path, root, NIL,
lefttree->total_cost,
lefttree->plan_rows,
lefttree->plan_width,
--- 4640,4647 ----
Plan *lefttree = plan->plan.lefttree;
Path sort_path; /* dummy for result of cost_sort */
! cost_sort(&sort_path, root, NIL, 0,
! lefttree->startup_cost,
lefttree->total_cost,
lefttree->plan_rows,
lefttree->plan_width,
*************** make_mergejoin(List *tlist,
*** 5139,5145 ****
* nullsFirst arrays already.
*/
static Sort *
! make_sort(Plan *lefttree, int numCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst)
{
--- 5163,5169 ----
* nullsFirst arrays already.
*/
static Sort *
! make_sort(Plan *lefttree, int numCols, int skipCols,
AttrNumber *sortColIdx, Oid *sortOperators,
Oid *collations, bool *nullsFirst)
{
*************** make_sort(Plan *lefttree, int numCols,
*** 5151,5156 ****
--- 5175,5181 ----
plan->lefttree = lefttree;
plan->righttree = NULL;
node->numCols = numCols;
+ node->skipCols = skipCols;
node->sortColIdx = sortColIdx;
node->sortOperators = sortOperators;
node->collations = collations;
*************** find_ec_member_for_tle(EquivalenceClass
*** 5477,5483 ****
* 'pathkeys' is the list of pathkeys by which the result is to be sorted
*/
static Sort *
! make_sort_from_pathkeys(Plan *lefttree, List *pathkeys)
{
int numsortkeys;
AttrNumber *sortColIdx;
--- 5502,5508 ----
* 'pathkeys' is the list of pathkeys by which the result is to be sorted
*/
static Sort *
! make_sort_from_pathkeys(Plan *lefttree, List *pathkeys, int skipCols)
{
int numsortkeys;
AttrNumber *sortColIdx;
*************** make_sort_from_pathkeys(Plan *lefttree,
*** 5497,5503 ****
&nullsFirst);
/* Now build the Sort node */
! return make_sort(lefttree, numsortkeys,
sortColIdx, sortOperators,
collations, nullsFirst);
}
--- 5522,5528 ----
&nullsFirst);
/* Now build the Sort node */
! return make_sort(lefttree, numsortkeys, skipCols,
sortColIdx, sortOperators,
collations, nullsFirst);
}
*************** make_sort_from_sortclauses(List *sortcls
*** 5540,5546 ****
numsortkeys++;
}
! return make_sort(lefttree, numsortkeys,
sortColIdx, sortOperators,
collations, nullsFirst);
}
--- 5565,5571 ----
numsortkeys++;
}
! return make_sort(lefttree, numsortkeys, 0,
sortColIdx, sortOperators,
collations, nullsFirst);
}
*************** make_sort_from_sortclauses(List *sortcls
*** 5561,5567 ****
static Sort *
make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
! Plan *lefttree)
{
List *sub_tlist = lefttree->targetlist;
ListCell *l;
--- 5586,5593 ----
static Sort *
make_sort_from_groupcols(List *groupcls,
AttrNumber *grpColIdx,
! Plan *lefttree,
! int skipCols)
{
List *sub_tlist = lefttree->targetlist;
ListCell *l;
*************** make_sort_from_groupcols(List *groupcls,
*** 5594,5600 ****
numsortkeys++;
}
! return make_sort(lefttree, numsortkeys,
sortColIdx, sortOperators,
collations, nullsFirst);
}
--- 5620,5626 ----
numsortkeys++;
}
! return make_sort(lefttree, numsortkeys, skipCols,
sortColIdx, sortOperators,
collations, nullsFirst);
}
diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c
new file mode 100644
index 805aae7..094d28f
*** a/src/backend/optimizer/plan/planagg.c
--- b/src/backend/optimizer/plan/planagg.c
***************
*** 44,49 ****
--- 44,50 ----
#include "parser/parse_clause.h"
#include "rewrite/rewriteManip.h"
#include "utils/lsyscache.h"
+ #include "utils/selfuncs.h"
#include "utils/syscache.h"
*************** build_minmax_path(PlannerInfo *root, Min
*** 344,349 ****
--- 345,351 ----
Path *sorted_path;
Cost path_cost;
double path_fraction;
+ double *psort_num_groups;
/*
* We are going to construct what is effectively a sub-SELECT query, so
*************** build_minmax_path(PlannerInfo *root, Min
*** 454,464 ****
else
path_fraction = 1.0;
sorted_path =
get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
subroot->query_pathkeys,
NULL,
! path_fraction);
if (!sorted_path)
return false;
--- 456,470 ----
else
path_fraction = 1.0;
+ psort_num_groups = estimate_pathkeys_groups(subroot->query_pathkeys,
+ subroot,
+ final_rel->rows);
sorted_path =
get_cheapest_fractional_path_for_pathkeys(final_rel->pathlist,
subroot->query_pathkeys,
NULL,
! path_fraction,
! psort_num_groups);
if (!sorted_path)
return false;
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
new file mode 100644
index 174210b..2a4398c
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** create_grouping_paths(PlannerInfo *root,
*** 3638,3651 ****
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
! bool is_sorted;
! is_sorted = pathkeys_contained_in(root->group_pathkeys,
! path->pathkeys);
! if (path == cheapest_path || is_sorted)
{
/* Sort the cheapest-total path if it isn't already sorted */
! if (!is_sorted)
path = (Path *) create_sort_path(root,
grouped_rel,
path,
--- 3638,3651 ----
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
! int n_common_pathkeys;
! n_common_pathkeys = pathkeys_common(root->group_pathkeys,
! path->pathkeys);
! if (path == cheapest_path || n_common_pathkeys > 0)
{
/* Sort the cheapest-total path if it isn't already sorted */
! if (n_common_pathkeys < list_length(root->group_pathkeys))
path = (Path *) create_sort_path(root,
grouped_rel,
path,
*************** create_ordered_paths(PlannerInfo *root,
*** 4301,4313 ****
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
! bool is_sorted;
! is_sorted = pathkeys_contained_in(root->sort_pathkeys,
! path->pathkeys);
! if (path == cheapest_input_path || is_sorted)
{
! if (!is_sorted)
{
/* An explicit sort here can take advantage of LIMIT */
path = (Path *) create_sort_path(root,
--- 4301,4313 ----
foreach(lc, input_rel->pathlist)
{
Path *path = (Path *) lfirst(lc);
! int n_common_pathkeys;
! n_common_pathkeys = pathkeys_common(root->sort_pathkeys,
! path->pathkeys);
! if (path == cheapest_input_path || n_common_pathkeys > 0)
{
! if (n_common_pathkeys < list_length(root->sort_pathkeys))
{
/* An explicit sort here can take advantage of LIMIT */
path = (Path *) create_sort_path(root,
*************** plan_cluster_use_sort(Oid tableOid, Oid
*** 5281,5288 ****
/* Estimate the cost of seq scan + sort */
seqScanPath = create_seqscan_path(root, rel, NULL, 0);
! cost_sort(&seqScanAndSortPath, root, NIL,
! seqScanPath->total_cost, rel->tuples, rel->reltarget->width,
comparisonCost, maintenance_work_mem, -1.0);
/* Estimate the cost of index scan */
--- 5281,5289 ----
/* Estimate the cost of seq scan + sort */
seqScanPath = create_seqscan_path(root, rel, NULL, 0);
! cost_sort(&seqScanAndSortPath, root, NIL, 0,
! seqScanPath->startup_cost, seqScanPath->total_cost,
! rel->tuples, rel->reltarget->width,
comparisonCost, maintenance_work_mem, -1.0);
/* Estimate the cost of index scan */
diff --git a/src/backend/optimizer/plan/subselect.c b/src/backend/optimizer/plan/subselect.c
new file mode 100644
index 6edefb1..cc3788f
*** a/src/backend/optimizer/plan/subselect.c
--- b/src/backend/optimizer/plan/subselect.c
*************** build_subplan(PlannerInfo *root, Plan *p
*** 838,844 ****
* unnecessarily, so we don't.
*/
else if (splan->parParam == NIL && enable_material &&
! !ExecMaterializesOutput(nodeTag(plan)))
plan = materialize_finished_plan(plan);
result = (Node *) splan;
--- 838,844 ----
* unnecessarily, so we don't.
*/
else if (splan->parParam == NIL && enable_material &&
! !ExecPlanMaterializesOutput(plan))
plan = materialize_finished_plan(plan);
result = (Node *) splan;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
new file mode 100644
index b714783..4b36822
*** a/src/backend/optimizer/prep/prepunion.c
--- b/src/backend/optimizer/prep/prepunion.c
*************** choose_hashed_setop(PlannerInfo *root, L
*** 964,970 ****
sorted_p.startup_cost = input_path->startup_cost;
sorted_p.total_cost = input_path->total_cost;
/* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
! cost_sort(&sorted_p, root, NIL, sorted_p.total_cost,
input_path->rows, input_path->pathtarget->width,
0.0, work_mem, -1.0);
cost_group(&sorted_p, root, numGroupCols, dNumGroups,
--- 964,971 ----
sorted_p.startup_cost = input_path->startup_cost;
sorted_p.total_cost = input_path->total_cost;
/* XXX cost_sort doesn't actually look at pathkeys, so just pass NIL */
! cost_sort(&sorted_p, root, NIL, 0,
! sorted_p.startup_cost, sorted_p.total_cost,
input_path->rows, input_path->pathtarget->width,
0.0, work_mem, -1.0);
cost_group(&sorted_p, root, numGroupCols, dNumGroups,
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
new file mode 100644
index abb7507..52fbecc
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** compare_path_costs(Path *path1, Path *pa
*** 95,101 ****
}
/*
! * compare_path_fractional_costs
* Return -1, 0, or +1 according as path1 is cheaper, the same cost,
* or more expensive than path2 for fetching the specified fraction
* of the total tuples.
--- 95,101 ----
}
/*
! * compare_fractional_path_costs
* Return -1, 0, or +1 according as path1 is cheaper, the same cost,
* or more expensive than path2 for fetching the specified fraction
* of the total tuples.
*************** compare_fractional_path_costs(Path *path
*** 124,129 ****
--- 124,170 ----
}
/*
+ * compare_bifractional_path_costs
+ * Return -1, 0, or +1 according as fetching the fraction1 tuples of path1 is
+ * cheaper, the same cost, or more expensive than fetching fraction2 tuples
+ * of path2.
+ *
+ * fraction1 and fraction2 are fractions of total tuples between 0 and 1.
+ * If fraction is <= 0 or > 1, we interpret it as 1, ie, we select the
+ * path with the cheaper total_cost.
+ */
+
+ /*
+ * Compare cost of two paths assuming different fractions of tuples be returned
+ * from each paths.
+ */
+ int
+ compare_bifractional_path_costs(Path *path1, Path *path2,
+ double fraction1, double fraction2)
+ {
+ Cost cost1,
+ cost2;
+
+ if (fraction1 <= 0.0 || fraction1 >= 1.0)
+ fraction1 = 1.0;
+ if (fraction2 <= 0.0 || fraction2 >= 1.0)
+ fraction2 = 1.0;
+
+ if (fraction1 == 1.0 && fraction2 == 1.0)
+ return compare_path_costs(path1, path2, TOTAL_COST);
+
+ cost1 = path1->startup_cost +
+ fraction1 * (path1->total_cost - path1->startup_cost);
+ cost2 = path2->startup_cost +
+ fraction2 * (path2->total_cost - path2->startup_cost);
+ if (cost1 < cost2)
+ return -1;
+ if (cost1 > cost2)
+ return +1;
+ return 0;
+ }
+
+ /*
* compare_path_costs_fuzzily
* Compare the costs of two paths to see if either can be said to
* dominate the other.
*************** create_merge_append_path(PlannerInfo *ro
*** 1296,1307 ****
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
pathnode->path.rows += subpath->rows;
pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
subpath->parallel_safe;
! if (pathkeys_contained_in(pathkeys, subpath->pathkeys))
{
/* Subpath is adequately ordered, we won't need to sort it */
input_startup_cost += subpath->startup_cost;
--- 1337,1349 ----
foreach(l, subpaths)
{
Path *subpath = (Path *) lfirst(l);
+ int n_common_pathkeys = pathkeys_common(pathkeys, subpath->pathkeys);
pathnode->path.rows += subpath->rows;
pathnode->path.parallel_safe = pathnode->path.parallel_safe &&
subpath->parallel_safe;
! if (n_common_pathkeys == list_length(pathkeys))
{
/* Subpath is adequately ordered, we won't need to sort it */
input_startup_cost += subpath->startup_cost;
*************** create_merge_append_path(PlannerInfo *ro
*** 1315,1320 ****
--- 1357,1364 ----
cost_sort(&sort_path,
root,
pathkeys,
+ n_common_pathkeys,
+ subpath->startup_cost,
subpath->total_cost,
subpath->parent->tuples,
subpath->pathtarget->width,
*************** create_unique_path(PlannerInfo *root, Re
*** 1551,1557 ****
/*
* Estimate cost for sort+unique implementation
*/
! cost_sort(&sort_path, root, NIL,
subpath->total_cost,
rel->rows,
subpath->pathtarget->width,
--- 1595,1602 ----
/*
* Estimate cost for sort+unique implementation
*/
! cost_sort(&sort_path, root, NIL, 0,
! subpath->startup_cost,
subpath->total_cost,
rel->rows,
subpath->pathtarget->width,
*************** create_sort_path(PlannerInfo *root,
*** 2337,2342 ****
--- 2382,2392 ----
double limit_tuples)
{
SortPath *pathnode = makeNode(SortPath);
+ int n_common_pathkeys;
+
+ n_common_pathkeys = pathkeys_common(subpath->pathkeys, pathkeys);
+
+ Assert(n_common_pathkeys < list_length(pathkeys));
pathnode->path.pathtype = T_Sort;
pathnode->path.parent = rel;
*************** create_sort_path(PlannerInfo *root,
*** 2349,2358 ****
subpath->parallel_safe;
pathnode->path.parallel_workers = subpath->parallel_workers;
pathnode->path.pathkeys = pathkeys;
pathnode->subpath = subpath;
! cost_sort(&pathnode->path, root, pathkeys,
subpath->total_cost,
subpath->rows,
subpath->pathtarget->width,
--- 2399,2411 ----
subpath->parallel_safe;
pathnode->path.parallel_workers = subpath->parallel_workers;
pathnode->path.pathkeys = pathkeys;
+ pathnode->skipCols = n_common_pathkeys;
pathnode->subpath = subpath;
! cost_sort(&pathnode->path, root,
! pathkeys, n_common_pathkeys,
! subpath->startup_cost,
subpath->total_cost,
subpath->rows,
subpath->pathtarget->width,
*************** create_groupingsets_path(PlannerInfo *ro
*** 2624,2630 ****
break;
/* Account for cost of sort, but don't charge input cost again */
! cost_sort(&sort_path, root, NIL,
0.0,
subpath->rows,
subpath->pathtarget->width,
--- 2677,2684 ----
break;
/* Account for cost of sort, but don't charge input cost again */
! cost_sort(&sort_path, root, NIL, 0,
! 0.0,
0.0,
subpath->rows,
subpath->pathtarget->width,
diff --git a/src/backend/utils/adt/orderedsetaggs.c b/src/backend/utils/adt/orderedsetaggs.c
new file mode 100644
index fe44d56..8d1717c
*** a/src/backend/utils/adt/orderedsetaggs.c
--- b/src/backend/utils/adt/orderedsetaggs.c
*************** ordered_set_startup(FunctionCallInfo fci
*** 276,282 ****
qstate->sortOperators,
qstate->sortCollations,
qstate->sortNullsFirsts,
! work_mem, false);
else
osastate->sortstate = tuplesort_begin_datum(qstate->sortColType,
qstate->sortOperator,
--- 276,282 ----
qstate->sortOperators,
qstate->sortCollations,
qstate->sortNullsFirsts,
! work_mem, false, false);
else
osastate->sortstate = tuplesort_begin_datum(qstate->sortColType,
qstate->sortOperator,
diff --git a/src/backend/utils/adt/selfuncs.c b/src/backend/utils/adt/selfuncs.c
new file mode 100644
index 56943f2..213d045
*** a/src/backend/utils/adt/selfuncs.c
--- b/src/backend/utils/adt/selfuncs.c
*************** estimate_num_groups(PlannerInfo *root, L
*** 3506,3511 ****
--- 3506,3547 ----
}
/*
+ * estimate_pathkeys_groups - Estimate number of groups which dataset is
+ * divided to by pathkeys.
+ *
+ * Returns an array of group numbers. i'th element of array is number of groups
+ * which first i pathkeys divides dataset into. Actually is a convenience
+ * wrapper over estimate_num_groups().
+ */
+ double *
+ estimate_pathkeys_groups(List *pathkeys, PlannerInfo *root, double tuples)
+ {
+ ListCell *l;
+ List *groupExprs = NIL;
+ double *result;
+ int i;
+
+ /*
+ * Get number of groups for each prefix of pathkeys.
+ */
+ i = 0;
+ result = (double *) palloc(sizeof(double) * list_length(pathkeys));
+ foreach(l, pathkeys)
+ {
+ PathKey *key = (PathKey *)lfirst(l);
+ EquivalenceMember *member = (EquivalenceMember *)
+ linitial(key->pk_eclass->ec_members);
+
+ groupExprs = lappend(groupExprs, member->em_expr);
+
+ result[i] = estimate_num_groups(root, groupExprs, tuples, NULL);
+ i++;
+ }
+
+ return result;
+ }
+
+ /*
* Estimate hash bucketsize fraction (ie, number of entries in a bucket
* divided by total tuples in relation) if the specified expression is used
* as a hash key.
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
new file mode 100644
index d600670..1de488e
*** a/src/backend/utils/sort/tuplesort.c
--- b/src/backend/utils/sort/tuplesort.c
*************** struct Tuplesortstate
*** 262,267 ****
--- 262,272 ----
int64 allowedMem; /* total memory allowed, in bytes */
int maxTapes; /* number of tapes (Knuth's T) */
int tapeRange; /* maxTapes-1 (Knuth's P) */
+ TupSortStatus maxStatus; /* maximum status reached between sort groups */
+ int64 maxMem; /* maximum amount of memory used between
+ sort groups */
+ bool maxMemOnDisk; /* is maxMem value for on-disk memory */
+ MemoryContext maincontext;
MemoryContext sortcontext; /* memory context holding most sort data */
MemoryContext tuplecontext; /* sub-context of sortcontext for tuple data */
LogicalTapeSet *tapeset; /* logtape.c object for tapes in a temp file */
*************** static void readtup_datum(Tuplesortstate
*** 612,617 ****
--- 617,625 ----
int tapenum, unsigned int len);
static void movetup_datum(void *dest, void *src, unsigned int len);
static void free_sort_tuple(Tuplesortstate *state, SortTuple *stup);
+ static void tuplesort_free(Tuplesortstate *state, bool delete);
+ static void tuplesort_updatemax(Tuplesortstate *state);
+
/*
* Special versions of qsort just for SortTuple objects. qsort_tuple() sorts
*************** static Tuplesortstate *
*** 646,664 ****
tuplesort_begin_common(int workMem, bool randomAccess)
{
Tuplesortstate *state;
MemoryContext sortcontext;
MemoryContext tuplecontext;
MemoryContext oldcontext;
/*
! * Create a working memory context for this sort operation. All data
! * needed by the sort will live inside this context.
*/
! sortcontext = AllocSetContextCreate(CurrentMemoryContext,
"TupleSort main",
ALLOCSET_DEFAULT_SIZES);
/*
* Caller tuple (e.g. IndexTuple) memory context.
*
* A dedicated child context used exclusively for caller passed tuples
--- 654,683 ----
tuplesort_begin_common(int workMem, bool randomAccess)
{
Tuplesortstate *state;
+ MemoryContext maincontext;
MemoryContext sortcontext;
MemoryContext tuplecontext;
MemoryContext oldcontext;
/*
! * Memory context surviving tuplesort_reset. This memory context holds
! * data which is useful to keep while sorting multiple similar batches.
*/
! maincontext = AllocSetContextCreate(CurrentMemoryContext,
"TupleSort main",
ALLOCSET_DEFAULT_SIZES);
/*
+ * Create a working memory context for one sort operation. The content of
+ * this context is deleted by tuplesort_reset.
+ */
+ sortcontext = AllocSetContextCreate(maincontext,
+ "TupleSort sort",
+ ALLOCSET_DEFAULT_MINSIZE,
+ ALLOCSET_DEFAULT_INITSIZE,
+ ALLOCSET_DEFAULT_MAXSIZE);
+
+ /*
* Caller tuple (e.g. IndexTuple) memory context.
*
* A dedicated child context used exclusively for caller passed tuples
*************** tuplesort_begin_common(int workMem, bool
*** 675,681 ****
* Make the Tuplesortstate within the per-sort context. This way, we
* don't need a separate pfree() operation for it at shutdown.
*/
! oldcontext = MemoryContextSwitchTo(sortcontext);
state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
--- 694,700 ----
* Make the Tuplesortstate within the per-sort context. This way, we
* don't need a separate pfree() operation for it at shutdown.
*/
! oldcontext = MemoryContextSwitchTo(maincontext);
state = (Tuplesortstate *) palloc0(sizeof(Tuplesortstate));
*************** tuplesort_begin_common(int workMem, bool
*** 693,698 ****
--- 712,718 ----
state->availMem = state->allowedMem;
state->sortcontext = sortcontext;
state->tuplecontext = tuplecontext;
+ state->maincontext = maincontext;
state->tapeset = NULL;
state->memtupcount = 0;
*************** tuplesort_begin_heap(TupleDesc tupDesc,
*** 733,745 ****
int nkeys, AttrNumber *attNums,
Oid *sortOperators, Oid *sortCollations,
bool *nullsFirstFlags,
! int workMem, bool randomAccess)
{
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
int i;
! oldcontext = MemoryContextSwitchTo(state->sortcontext);
AssertArg(nkeys > 0);
--- 753,766 ----
int nkeys, AttrNumber *attNums,
Oid *sortOperators, Oid *sortCollations,
bool *nullsFirstFlags,
! int workMem, bool randomAccess,
! bool skipAbbrev)
{
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
int i;
! oldcontext = MemoryContextSwitchTo(state->maincontext);
AssertArg(nkeys > 0);
*************** tuplesort_begin_heap(TupleDesc tupDesc,
*** 782,788 ****
sortKey->ssup_nulls_first = nullsFirstFlags[i];
sortKey->ssup_attno = attNums[i];
/* Convey if abbreviation optimization is applicable in principle */
! sortKey->abbreviate = (i == 0);
PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
}
--- 803,809 ----
sortKey->ssup_nulls_first = nullsFirstFlags[i];
sortKey->ssup_attno = attNums[i];
/* Convey if abbreviation optimization is applicable in principle */
! sortKey->abbreviate = (i == 0) && !skipAbbrev;
PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
}
*************** tuplesort_begin_cluster(TupleDesc tupDes
*** 813,819 ****
Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
! oldcontext = MemoryContextSwitchTo(state->sortcontext);
#ifdef TRACE_SORT
if (trace_sort)
--- 834,840 ----
Assert(indexRel->rd_rel->relam == BTREE_AM_OID);
! oldcontext = MemoryContextSwitchTo(state->maincontext);
#ifdef TRACE_SORT
if (trace_sort)
*************** tuplesort_begin_index_btree(Relation hea
*** 905,911 ****
MemoryContext oldcontext;
int i;
! oldcontext = MemoryContextSwitchTo(state->sortcontext);
#ifdef TRACE_SORT
if (trace_sort)
--- 926,932 ----
MemoryContext oldcontext;
int i;
! oldcontext = MemoryContextSwitchTo(state->maincontext);
#ifdef TRACE_SORT
if (trace_sort)
*************** tuplesort_begin_index_hash(Relation heap
*** 979,985 ****
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
! oldcontext = MemoryContextSwitchTo(state->sortcontext);
#ifdef TRACE_SORT
if (trace_sort)
--- 1000,1006 ----
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
! oldcontext = MemoryContextSwitchTo(state->maincontext);
#ifdef TRACE_SORT
if (trace_sort)
*************** tuplesort_begin_datum(Oid datumType, Oid
*** 1017,1023 ****
int16 typlen;
bool typbyval;
! oldcontext = MemoryContextSwitchTo(state->sortcontext);
#ifdef TRACE_SORT
if (trace_sort)
--- 1038,1044 ----
int16 typlen;
bool typbyval;
! oldcontext = MemoryContextSwitchTo(state->maincontext);
#ifdef TRACE_SORT
if (trace_sort)
*************** tuplesort_set_bound(Tuplesortstate *stat
*** 1129,1144 ****
}
/*
! * tuplesort_end
! *
! * Release resources and clean up.
*
! * NOTE: after calling this, any pointers returned by tuplesort_getXXX are
! * pointing to garbage. Be careful not to attempt to use or free such
! * pointers afterwards!
*/
! void
! tuplesort_end(Tuplesortstate *state)
{
/* context swap probably not needed, but let's be safe */
MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
--- 1150,1161 ----
}
/*
! * tuplesort_free
*
! * Internal routine for freeing resources of tuplesort.
*/
! static void
! tuplesort_free(Tuplesortstate *state, bool delete)
{
/* context swap probably not needed, but let's be safe */
MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
*************** tuplesort_end(Tuplesortstate *state)
*** 1197,1203 ****
* Free the per-sort memory context, thereby releasing all working memory,
* including the Tuplesortstate struct itself.
*/
! MemoryContextDelete(state->sortcontext);
}
/*
--- 1214,1307 ----
* Free the per-sort memory context, thereby releasing all working memory,
* including the Tuplesortstate struct itself.
*/
! if (delete)
! {
! MemoryContextDelete(state->maincontext);
! }
! else
! {
! MemoryContextResetOnly(state->sortcontext);
! MemoryContextResetOnly(state->tuplecontext);
! }
! }
!
! /*
! * tuplesort_end
! *
! * Release resources and clean up.
! *
! * NOTE: after calling this, any pointers returned by tuplesort_getXXX are
! * pointing to garbage. Be careful not to attempt to use or free such
! * pointers afterwards!
! */
! void
! tuplesort_end(Tuplesortstate *state)
! {
! tuplesort_free(state, true);
! }
!
! /*
! * tuplesort_updatemax
! *
! * Update maximum resource usage statistics.
! */
! static void
! tuplesort_updatemax(Tuplesortstate *state)
! {
! int64 memUsed;
! bool memUsedOnDisk;
!
! /*
! * Note: it might seem we should provide both memory and disk usage for a
! * disk-based sort. However, the current code doesn't track memory space
! * accurately once we have begun to return tuples to the caller (since we
! * don't account for pfree's the caller is expected to do), so we cannot
! * rely on availMem in a disk sort. This does not seem worth the overhead
! * to fix. Is it worth creating an API for the memory context code to
! * tell us how much is actually used in sortcontext?
! */
! if (state->tapeset)
! {
! memUsedOnDisk = true;
! memUsed = LogicalTapeSetBlocks(state->tapeset) * BLCKSZ;
! }
! else
! {
! memUsedOnDisk = false;
! memUsed = state->allowedMem - state->availMem;
! }
!
! state->maxStatus = Max(state->maxStatus, state->status);
! if (memUsed > state->maxMem)
! {
! state->maxMem = memUsed;
! state->maxMemOnDisk = memUsedOnDisk;
! }
! }
!
! /*
! * tuplesort_reset
! *
! * Reset the tuplesort. Reset all the data in the tuplesort, but leave the
! * meta-information in. After tuplesort_reset, tuplesort is ready to start
! * a new sort. It allows evade recreation of tuple sort (and save resources)
! * when sorting multiple small batches.
! */
! void
! tuplesort_reset(Tuplesortstate *state)
! {
! tuplesort_updatemax(state);
! tuplesort_free(state, false);
! state->status = TSS_INITIAL;
! state->memtupcount = 0;
! state->boundUsed = false;
! state->tapeset = NULL;
! state->currentRun = 0;
! state->result_tape = -1;
! state->bounded = false;
! state->batchUsed = false;
! state->availMem = state->allowedMem;
! USEMEM(state, GetMemoryChunkSpace(state->memtuples));
}
/*
*************** tuplesort_get_stats(Tuplesortstate *stat
*** 3574,3600 ****
const char **spaceType,
long *spaceUsed)
{
! /*
! * Note: it might seem we should provide both memory and disk usage for a
! * disk-based sort. However, the current code doesn't track memory space
! * accurately once we have begun to return tuples to the caller (since we
! * don't account for pfree's the caller is expected to do), so we cannot
! * rely on availMem in a disk sort. This does not seem worth the overhead
! * to fix. Is it worth creating an API for the memory context code to
! * tell us how much is actually used in sortcontext?
! */
! if (state->tapeset)
! {
*spaceType = "Disk";
- *spaceUsed = LogicalTapeSetBlocks(state->tapeset) * (BLCKSZ / 1024);
- }
else
- {
*spaceType = "Memory";
! *spaceUsed = (state->allowedMem - state->availMem + 1023) / 1024;
! }
! switch (state->status)
{
case TSS_SORTEDINMEM:
if (state->boundUsed)
--- 3678,3692 ----
const char **spaceType,
long *spaceUsed)
{
! tuplesort_updatemax(state);
!
! if (state->maxMemOnDisk)
*spaceType = "Disk";
else
*spaceType = "Memory";
! *spaceUsed = (state->maxMem + 1023) / 1024;
! switch (state->maxStatus)
{
case TSS_SORTEDINMEM:
if (state->boundUsed)
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
new file mode 100644
index 39521ed..f172330
*** a/src/include/executor/executor.h
--- b/src/include/executor/executor.h
*************** extern void ExecRestrPos(PlanState *node
*** 107,112 ****
--- 107,113 ----
extern bool ExecSupportsMarkRestore(struct Path *pathnode);
extern bool ExecSupportsBackwardScan(Plan *node);
extern bool ExecMaterializesOutput(NodeTag plantype);
+ extern bool ExecPlanMaterializesOutput(Plan *node);
/*
* prototypes from functions in execCurrent.c
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
new file mode 100644
index e28477d..0bd2add
*** a/src/include/nodes/execnodes.h
--- b/src/include/nodes/execnodes.h
*************** typedef struct MaterialState
*** 1773,1778 ****
--- 1773,1792 ----
Tuplestorestate *tuplestorestate;
} MaterialState;
+
+ /* ----------------
+ * When performing sorting by multiple keys input dataset could be already
+ * presorted by some prefix of these keys. We call them "skip keys".
+ * SkipKeyData represents information about one such key.
+ * ----------------
+ */
+ typedef struct SkipKeyData
+ {
+ FmgrInfo flinfo; /* comparison function info */
+ FunctionCallInfoData fcinfo; /* comparison function call info */
+ OffsetNumber attno; /* attribute number in tuple */
+ } SkipKeyData;
+
/* ----------------
* SortState information
* ----------------
*************** typedef struct SortState
*** 1784,1792 ****
--- 1798,1811 ----
bool bounded; /* is the result set bounded? */
int64 bound; /* if bounded, how many tuples are needed */
bool sort_Done; /* sort completed yet? */
+ bool finished; /* fetching tuples from outer node
+ is finished ? */
bool bounded_Done; /* value of bounded we did the sort with */
int64 bound_Done; /* value of bound we did the sort with */
void *tuplesortstate; /* private state of tuplesort.c */
+ SkipKeyData *skipKeys; /* keys, dataset is presorted by */
+ long groupsCount; /* number of groups with equal skip keys */
+ HeapTuple prev; /* previous tuple from outer node */
} SortState;
/* ---------------------
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
new file mode 100644
index e2fbc7d..ffab23f
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
*************** typedef struct Sort
*** 673,678 ****
--- 673,679 ----
{
Plan plan;
int numCols; /* number of sort-key columns */
+ int skipCols;
AttrNumber *sortColIdx; /* their indexes in the target list */
Oid *sortOperators; /* OIDs of operators to sort them by */
Oid *collations; /* OIDs of collations */
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
new file mode 100644
index 2709cc7..76b4365
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct SortPath
*** 1307,1312 ****
--- 1307,1313 ----
{
Path path;
Path *subpath; /* path representing input source */
+ int skipCols;
} SortPath;
/*
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
new file mode 100644
index 2a4df2f..516357f
*** a/src/include/optimizer/cost.h
--- b/src/include/optimizer/cost.h
*************** extern void cost_ctescan(Path *path, Pla
*** 95,102 ****
RelOptInfo *baserel, ParamPathInfo *param_info);
extern void cost_recursive_union(Path *runion, Path *nrterm, Path *rterm);
extern void cost_sort(Path *path, PlannerInfo *root,
! List *pathkeys, Cost input_cost, double tuples, int width,
! Cost comparison_cost, int sort_mem,
double limit_tuples);
extern void cost_merge_append(Path *path, PlannerInfo *root,
List *pathkeys, int n_streams,
--- 95,103 ----
RelOptInfo *baserel, ParamPathInfo *param_info);
extern void cost_recursive_union(Path *runion, Path *nrterm, Path *rterm);
extern void cost_sort(Path *path, PlannerInfo *root,
! List *pathkeys, int presorted_keys,
! Cost input_startup_cost, Cost input_total_cost,
! double tuples, int width, Cost comparison_cost, int sort_mem,
double limit_tuples);
extern void cost_merge_append(Path *path, PlannerInfo *root,
List *pathkeys, int n_streams,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
new file mode 100644
index 71d9154..1b19dd0
*** a/src/include/optimizer/pathnode.h
--- b/src/include/optimizer/pathnode.h
*************** extern int compare_path_costs(Path *path
*** 24,29 ****
--- 24,31 ----
CostSelector criterion);
extern int compare_fractional_path_costs(Path *path1, Path *path2,
double fraction);
+ extern int compare_bifractional_path_costs(Path *path1, Path *path2,
+ double fraction1, double fraction2);
extern void set_cheapest(RelOptInfo *parent_rel);
extern void add_path(RelOptInfo *parent_rel, Path *new_path);
extern bool add_path_precheck(RelOptInfo *parent_rel,
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
new file mode 100644
index 44abe83..2695080
*** a/src/include/optimizer/paths.h
--- b/src/include/optimizer/paths.h
*************** typedef enum
*** 175,187 ****
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
CostSelector cost_criterion);
extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
Relids required_outer,
! double fraction);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
ScanDirection scandir);
extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
--- 175,189 ----
extern PathKeysComparison compare_pathkeys(List *keys1, List *keys2);
extern bool pathkeys_contained_in(List *keys1, List *keys2);
+ extern int pathkeys_common(List *keys1, List *keys2);
extern Path *get_cheapest_path_for_pathkeys(List *paths, List *pathkeys,
Relids required_outer,
CostSelector cost_criterion);
extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
List *pathkeys,
Relids required_outer,
! double fraction,
! double *num_groups);
extern List *build_index_pathkeys(PlannerInfo *root, IndexOptInfo *index,
ScanDirection scandir);
extern List *build_expression_pathkey(PlannerInfo *root, Expr *expr,
diff --git a/src/include/utils/selfuncs.h b/src/include/utils/selfuncs.h
new file mode 100644
index 8e0d317..06c0d7d
*** a/src/include/utils/selfuncs.h
--- b/src/include/utils/selfuncs.h
*************** extern void mergejoinscansel(PlannerInfo
*** 230,235 ****
--- 230,238 ----
extern double estimate_num_groups(PlannerInfo *root, List *groupExprs,
double input_rows, List **pgset);
+ extern double *estimate_pathkeys_groups(List *pathkeys, PlannerInfo *root,
+ double tuples);
+
extern Selectivity estimate_hash_bucketsize(PlannerInfo *root, Node *hashkey,
double nbuckets);
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
new file mode 100644
index 5cecd6d..6476504
*** a/src/include/utils/tuplesort.h
--- b/src/include/utils/tuplesort.h
*************** extern Tuplesortstate *tuplesort_begin_h
*** 62,68 ****
int nkeys, AttrNumber *attNums,
Oid *sortOperators, Oid *sortCollations,
bool *nullsFirstFlags,
! int workMem, bool randomAccess);
extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
Relation indexRel,
int workMem, bool randomAccess);
--- 62,69 ----
int nkeys, AttrNumber *attNums,
Oid *sortOperators, Oid *sortCollations,
bool *nullsFirstFlags,
! int workMem, bool randomAccess,
! bool skipAbbrev);
extern Tuplesortstate *tuplesort_begin_cluster(TupleDesc tupDesc,
Relation indexRel,
int workMem, bool randomAccess);
*************** extern bool tuplesort_skiptuples(Tupleso
*** 106,111 ****
--- 107,114 ----
extern void tuplesort_end(Tuplesortstate *state);
+ extern void tuplesort_reset(Tuplesortstate *state);
+
extern void tuplesort_get_stats(Tuplesortstate *state,
const char **sortMethod,
const char **spaceType,
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
new file mode 100644
index 45208a6..85cb8f3
*** a/src/test/regress/expected/aggregates.out
--- b/src/test/regress/expected/aggregates.out
*************** group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.y,t
*** 995,1009 ****
explain (costs off) select t1.*,t2.x,t2.z
from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
! QUERY PLAN
! -------------------------------------------------------
! HashAggregate
Group Key: t1.a, t1.b, t2.x, t2.z
! -> Merge Join
! Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
! -> Index Scan using t1_pkey on t1
! -> Index Scan using t2_pkey on t2
! (6 rows)
-- Cannot optimize when PK is deferrable
explain (costs off) select * from t3 group by a,b,c;
--- 995,1012 ----
explain (costs off) select t1.*,t2.x,t2.z
from t1 inner join t2 on t1.a = t2.x and t1.b = t2.y
group by t1.a,t1.b,t1.c,t1.d,t2.x,t2.z;
! QUERY PLAN
! -------------------------------------------------------------
! Group
Group Key: t1.a, t1.b, t2.x, t2.z
! -> Sort
! Sort Key: t1.a, t1.b, t2.z
! Presorted Key: t1.a, t1.b
! -> Merge Join
! Merge Cond: ((t1.a = t2.x) AND (t1.b = t2.y))
! -> Index Scan using t1_pkey on t1
! -> Index Scan using t2_pkey on t2
! (9 rows)
-- Cannot optimize when PK is deferrable
explain (costs off) select * from t3 group by a,b,c;
diff --git a/src/test/regress/expected/inherit.out b/src/test/regress/expected/inherit.out
new file mode 100644
index d8b5b1d..752f1b6
*** a/src/test/regress/expected/inherit.out
--- b/src/test/regress/expected/inherit.out
*************** ORDER BY thousand, tenthous;
*** 1359,1366 ****
-> Index Only Scan using tenk1_thous_tenthous on tenk1
-> Sort
Sort Key: tenk1_1.thousand, tenk1_1.thousand
-> Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (6 rows)
explain (costs off)
SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
--- 1359,1367 ----
-> Index Only Scan using tenk1_thous_tenthous on tenk1
-> Sort
Sort Key: tenk1_1.thousand, tenk1_1.thousand
+ Presorted Key: tenk1_1.thousand
-> Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
! (7 rows)
explain (costs off)
SELECT thousand, tenthous, thousand+tenthous AS x FROM tenk1
*************** ORDER BY x, y;
*** 1443,1450 ****
-> Index Only Scan using tenk1_thous_tenthous on tenk1 a
-> Sort
Sort Key: b.unique2, b.unique2
-> Index Only Scan using tenk1_unique2 on tenk1 b
! (6 rows)
-- exercise rescan code path via a repeatedly-evaluated subquery
explain (costs off)
--- 1444,1452 ----
-> Index Only Scan using tenk1_thous_tenthous on tenk1 a
-> Sort
Sort Key: b.unique2, b.unique2
+ Presorted Key: b.unique2
-> Index Only Scan using tenk1_unique2 on tenk1 b
! (7 rows)
-- exercise rescan code path via a repeatedly-evaluated subquery
explain (costs off)