On Sat, Jan 18, 2014 at 7:22 PM, Marti Raudsepp <ma...@juffo.org> wrote:
> Total runtime: 5.418 ms
Oops, shouldn't have rushed this. Clearly the timings should have
tipped me off that it's broken. I didn't notice that cmpSortSkipCols
was re-using tuplesort's sortkeys.
Here's a patch that actually works; I added a new skipKeys attribute
to SortState. I had to extract the SortSupport-creation code from
tuplesort_begin_heap to a new function; but that's fine, because it
was already duplicated in ExecInitMergeAppend too.
I reverted the addition of tuplesort_get_sortkeys, which is not needed now.
Now the timings are:
Unpatched partial sort: 13478.158 ms
Full sort: 6802.063 ms
Patched partial sort: 6618.962 ms
Regards,
Marti
From 7d9f34c09e7836504725ff11be7e63a2fc438ae9 Mon Sep 17 00:00:00 2001
From: Marti Raudsepp <ma...@juffo.org>
Date: Mon, 13 Jan 2014 20:38:45 +0200
Subject: [PATCH] Partial sort: skip comparisons for known-equal columns
---
src/backend/executor/nodeMergeAppend.c | 18 +++++-------------
src/backend/executor/nodeSort.c | 26 +++++++++++++++++---------
src/backend/utils/sort/sortsupport.c | 29 +++++++++++++++++++++++++++++
src/backend/utils/sort/tuplesort.c | 31 +++++--------------------------
src/include/nodes/execnodes.h | 1 +
src/include/utils/sortsupport.h | 3 +++
src/include/utils/tuplesort.h | 2 --
7 files changed, 60 insertions(+), 50 deletions(-)
diff --git a/src/backend/executor/nodeMergeAppend.c b/src/backend/executor/nodeMergeAppend.c
index 74fa40d..db6ec23 100644
--- a/src/backend/executor/nodeMergeAppend.c
+++ b/src/backend/executor/nodeMergeAppend.c
@@ -126,19 +126,11 @@ ExecInitMergeAppend(MergeAppend *node, EState *estate, int eflags)
* initialize sort-key information
*/
mergestate->ms_nkeys = node->numCols;
- mergestate->ms_sortkeys = palloc0(sizeof(SortSupportData) * node->numCols);
-
- for (i = 0; i < node->numCols; i++)
- {
- SortSupport sortKey = mergestate->ms_sortkeys + i;
-
- sortKey->ssup_cxt = CurrentMemoryContext;
- sortKey->ssup_collation = node->collations[i];
- sortKey->ssup_nulls_first = node->nullsFirst[i];
- sortKey->ssup_attno = node->sortColIdx[i];
-
- PrepareSortSupportFromOrderingOp(node->sortOperators[i], sortKey);
- }
+ mergestate->ms_sortkeys = MakeSortSupportKeys(mergestate->ms_nkeys,
+ node->sortColIdx,
+ node->sortOperators,
+ node->collations,
+ node->nullsFirst);
/*
* initialize to show we have not run the subplans yet
diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
index 55cdb05..7645645 100644
--- a/src/backend/executor/nodeSort.c
+++ b/src/backend/executor/nodeSort.c
@@ -28,20 +28,19 @@ static bool
cmpSortSkipCols(SortState *node, TupleDesc tupDesc, HeapTuple a, TupleTableSlot *b)
{
int n = ((Sort *)node->ss.ps.plan)->skipCols, i;
- SortSupport sortKeys = tuplesort_get_sortkeys(node->tuplesortstate);
for (i = 0; i < n; i++)
{
Datum datumA, datumB;
bool isnullA, isnullB;
- AttrNumber attno = sortKeys[i].ssup_attno;
+ AttrNumber attno = node->skipKeys[i].ssup_attno;
datumA = heap_getattr(a, attno, tupDesc, &isnullA);
datumB = slot_getattr(b, attno, &isnullB);
if (ApplySortComparator(datumA, isnullA,
- datumB, isnullB,
- &sortKeys[i]))
+ datumB, isnullB,
+ &node->skipKeys[i]))
return false;
}
return true;
@@ -123,12 +122,21 @@ ExecSort(SortState *node)
tuplesort_reset((Tuplesortstate *) node->tuplesortstate);
else
{
+ /* Support structures for cmpSortSkipCols - already sorted columns */
+ if (skipCols)
+ node->skipKeys = MakeSortSupportKeys(skipCols,
+ plannode->sortColIdx,
+ plannode->sortOperators,
+ plannode->collations,
+ plannode->nullsFirst);
+
+ /* Only pass on remaining columns that are unsorted */
tuplesortstate = tuplesort_begin_heap(tupDesc,
- plannode->numCols,
- plannode->sortColIdx,
- plannode->sortOperators,
- plannode->collations,
- plannode->nullsFirst,
+ plannode->numCols - skipCols,
+ &(plannode->sortColIdx[skipCols]),
+ &(plannode->sortOperators[skipCols]),
+ &(plannode->collations[skipCols]),
+ &(plannode->nullsFirst[skipCols]),
work_mem,
node->randomAccess);
if (node->bounded)
diff --git a/src/backend/utils/sort/sortsupport.c b/src/backend/utils/sort/sortsupport.c
index 347f448..df82f5f 100644
--- a/src/backend/utils/sort/sortsupport.c
+++ b/src/backend/utils/sort/sortsupport.c
@@ -85,6 +85,35 @@ PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup)
}
/*
+ * Build an array of SortSupportData structures from separated arrays.
+ */
+SortSupport
+MakeSortSupportKeys(int nkeys, AttrNumber *attNums,
+ Oid *sortOperators, Oid *sortCollations,
+ bool *nullsFirstFlags)
+{
+ SortSupport sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
+ int i;
+
+ for (i = 0; i < nkeys; i++)
+ {
+ SortSupport sortKey = sortKeys + i;
+
+ AssertArg(attNums[i] != 0);
+ AssertArg(sortOperators[i] != 0);
+
+ sortKey->ssup_cxt = CurrentMemoryContext;
+ sortKey->ssup_collation = sortCollations[i];
+ sortKey->ssup_nulls_first = nullsFirstFlags[i];
+ sortKey->ssup_attno = attNums[i];
+
+ PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
+ }
+
+ return sortKeys;
+}
+
+/*
* Fill in SortSupport given an ordering operator (btree "<" or ">" operator).
*
* Caller must previously have zeroed the SortSupportData structure and then
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 9fb5a9f..738f7a1 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -604,7 +604,6 @@ tuplesort_begin_heap(TupleDesc tupDesc,
{
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
- int i;
oldcontext = MemoryContextSwitchTo(state->sortcontext);
@@ -632,24 +631,11 @@ tuplesort_begin_heap(TupleDesc tupDesc,
state->reversedirection = reversedirection_heap;
state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
-
- /* Prepare SortSupport data for each column */
- state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));
-
- for (i = 0; i < nkeys; i++)
- {
- SortSupport sortKey = state->sortKeys + i;
-
- AssertArg(attNums[i] != 0);
- AssertArg(sortOperators[i] != 0);
-
- sortKey->ssup_cxt = CurrentMemoryContext;
- sortKey->ssup_collation = sortCollations[i];
- sortKey->ssup_nulls_first = nullsFirstFlags[i];
- sortKey->ssup_attno = attNums[i];
-
- PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
- }
+ state->sortKeys = MakeSortSupportKeys(nkeys,
+ attNums,
+ sortOperators,
+ sortCollations,
+ nullsFirstFlags);
if (nkeys == 1)
state->onlyKey = state->sortKeys;
@@ -3544,10 +3530,3 @@ free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
pfree(stup->tuple);
}
-
-SortSupport
-tuplesort_get_sortkeys(Tuplesortstate *state)
-{
- return state->sortKeys;
-}
-
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 9fa1823..13a4f0f 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -1671,6 +1671,7 @@ typedef struct SortState
bool finished;
int64 bound_Done; /* value of bound we did the sort with */
void *tuplesortstate; /* private state of tuplesort.c */
+ SortSupport skipKeys; /* columns already sorted in input */
HeapTuple prev;
} SortState;
diff --git a/src/include/utils/sortsupport.h b/src/include/utils/sortsupport.h
index 13d3fbe..cd48a45 100644
--- a/src/include/utils/sortsupport.h
+++ b/src/include/utils/sortsupport.h
@@ -150,6 +150,9 @@ ApplySortComparator(Datum datum1, bool isNull1,
#endif /*-- PG_USE_INLINE || SORTSUPPORT_INCLUDE_DEFINITIONS */
/* Other functions in utils/sort/sortsupport.c */
+extern SortSupport MakeSortSupportKeys(int nkeys, AttrNumber *attNums,
+ Oid *sortOperators, Oid *sortCollations,
+ bool *nullsFirstFlags);
extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index 106c3fd..eb882d3 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -114,8 +114,6 @@ extern void tuplesort_get_stats(Tuplesortstate *state,
extern int tuplesort_merge_order(int64 allowedMem);
-extern SortSupport tuplesort_get_sortkeys(Tuplesortstate *state);
-
/*
* These routines may only be called if randomAccess was specified 'true'.
* Likewise, backwards scan in gettuple/getdatum is only allowed if
--
1.8.5.3
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
