On Thu, Jan 26, 2023 at 9:11 AM David Rowley <dgrowle...@gmail.com> wrote: > > I'm unsure if 69749243 might be partially to blame here as it favours > single-key sorts. If you look at qsort_tuple_signed_compare(), you'll > see that the tiebreak function will be called only when it's needed > and there are > 1 sort keys. The comparetup function will re-compare > the first key all over again. If I get some more time I'll run the > tests again with the sort specialisation code disabled to see if the > situation is the same or not.
> I've attached the benchmark script that I used and also a copy of the > patch with a GUC added solely to allow easier benchmarking of patched > vs unpatched. I've attached a cleaned up v2 (*) of a patch to avoid rechecking the first column if a specialized comparator already did so, and the results of the "bench_windowsort" benchmark. Here, master vs. patch refers to skipping the first column recheck, and on/off is the dev guc from David's last patch. In my test, orderby_windowclause_pushdown caused 6 regressions by itself. Not rechecking seems to eliminate the regression in 4 cases, and reduce it in the other 2 cases. For those 2 cases (10e6 rows, random, mod 10 and 100), it might be worthwhile to "zoom in" with more measurements, but haven't done that yet. * v1 was here, but I thought it best to keep everything in the same thread, and that thread is nominally about a different kind of specialization: https://www.postgresql.org/message-id/CAFBsxsFdFpzyBekxxkiA4vXnLpw-wcaQXz%3DEAP4pzkZMo91-MA%40mail.gmail.com -- John Naylor EDB: http://www.enterprisedb.com
From d051fc02cfae4053d22ae5f87f767636c2e6ff7f Mon Sep 17 00:00:00 2001
From: John Naylor <john.nay...@postgresql.org>
Date: Mon, 30 Jan 2023 17:10:00 +0700
Subject: [PATCH v2] Split out fallback functionality from comparetup*
functions
Previously, if a specialized comparator find equal datum1 keys,
the comparetup function would call the full comparator on the
datum before proceeding with either the unabbreviated first key
or the second key.
Add a comparetup_fallback field for these that call special
fallback functions. The existing comparetup functions just call
ApplySortComparator where we can, than call our new fallback.
---
src/backend/utils/sort/tuplesort.c | 6 +-
src/backend/utils/sort/tuplesortvariants.c | 109 ++++++++++++++++-----
src/include/utils/tuplesort.h | 7 ++
3 files changed, 93 insertions(+), 29 deletions(-)
diff --git a/src/backend/utils/sort/tuplesort.c
b/src/backend/utils/sort/tuplesort.c
index 9ca9835aab..54f64d6c2d 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -513,7 +513,7 @@ qsort_tuple_unsigned_compare(SortTuple *a, SortTuple *b,
Tuplesortstate *state)
if (state->base.onlyKey != NULL)
return 0;
- return state->base.comparetup(a, b, state);
+ return state->base.comparetup_fallback(a, b, state);
}
#if SIZEOF_DATUM >= 8
@@ -537,7 +537,7 @@ qsort_tuple_signed_compare(SortTuple *a, SortTuple *b,
Tuplesortstate *state)
if (state->base.onlyKey != NULL)
return 0;
- return state->base.comparetup(a, b, state);
+ return state->base.comparetup_fallback(a, b, state);
}
#endif
@@ -561,7 +561,7 @@ qsort_tuple_int32_compare(SortTuple *a, SortTuple *b,
Tuplesortstate *state)
if (state->base.onlyKey != NULL)
return 0;
- return state->base.comparetup(a, b, state);
+ return state->base.comparetup_fallback(a, b, state);
}
/*
diff --git a/src/backend/utils/sort/tuplesortvariants.c
b/src/backend/utils/sort/tuplesortvariants.c
index eb6cfcfd00..4b49cd0a8d 100644
--- a/src/backend/utils/sort/tuplesortvariants.c
+++ b/src/backend/utils/sort/tuplesortvariants.c
@@ -47,18 +47,24 @@ static void removeabbrev_datum(Tuplesortstate *state,
SortTuple *stups,
int count);
static int comparetup_heap(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+static int comparetup_heap_fallback(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void writetup_heap(Tuplesortstate *state, LogicalTape *tape,
SortTuple *stup);
static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
LogicalTape *tape, unsigned
int len);
static int comparetup_cluster(const SortTuple *a, const SortTuple *b,
Tuplesortstate
*state);
+static int comparetup_cluster_fallback(const SortTuple *a, const SortTuple
*b,
+ Tuplesortstate
*state);
static void writetup_cluster(Tuplesortstate *state, LogicalTape *tape,
SortTuple *stup);
static void readtup_cluster(Tuplesortstate *state, SortTuple *stup,
LogicalTape *tape,
unsigned int tuplen);
static int comparetup_index_btree(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+static int comparetup_index_btree_fallback(const SortTuple *a, const
SortTuple *b,
+
Tuplesortstate *state);
static int comparetup_index_hash(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
static void writetup_index(Tuplesortstate *state, LogicalTape *tape,
@@ -67,6 +73,8 @@ static void readtup_index(Tuplesortstate *state, SortTuple
*stup,
LogicalTape *tape, unsigned
int len);
static int comparetup_datum(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state);
+static int comparetup_datum_fallback(const SortTuple *a, const SortTuple
*b,
+ Tuplesortstate *state);
static void writetup_datum(Tuplesortstate *state, LogicalTape *tape,
SortTuple *stup);
static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
@@ -165,6 +173,7 @@ tuplesort_begin_heap(TupleDesc tupDesc,
base->removeabbrev = removeabbrev_heap;
base->comparetup = comparetup_heap;
+ base->comparetup_fallback = comparetup_heap_fallback;
base->writetup = writetup_heap;
base->readtup = readtup_heap;
base->haveDatum1 = true;
@@ -242,6 +251,7 @@ tuplesort_begin_cluster(TupleDesc tupDesc,
base->removeabbrev = removeabbrev_cluster;
base->comparetup = comparetup_cluster;
+ base->comparetup_fallback = comparetup_cluster_fallback;
base->writetup = writetup_cluster;
base->readtup = readtup_cluster;
base->freestate = freestate_cluster;
@@ -351,6 +361,7 @@ tuplesort_begin_index_btree(Relation heapRel,
base->removeabbrev = removeabbrev_index;
base->comparetup = comparetup_index_btree;
+ base->comparetup_fallback = comparetup_index_btree_fallback;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -431,6 +442,8 @@ tuplesort_begin_index_hash(Relation heapRel,
base->removeabbrev = removeabbrev_index;
base->comparetup = comparetup_index_hash;
+ /* Only one sort column, so no fallback */
+ base->comparetup_fallback = NULL;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -476,6 +489,7 @@ tuplesort_begin_index_gist(Relation heapRel,
base->removeabbrev = removeabbrev_index;
base->comparetup = comparetup_index_btree;
+ base->comparetup_fallback = comparetup_index_btree_fallback;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -546,6 +560,7 @@ tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid
sortCollation,
base->removeabbrev = removeabbrev_datum;
base->comparetup = comparetup_datum;
+ base->comparetup_fallback = comparetup_datum_fallback;
base->writetup = writetup_datum;
base->readtup = readtup_datum;
base->haveDatum1 = true;
@@ -931,16 +946,7 @@ comparetup_heap(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
{
TuplesortPublic *base = TuplesortstateGetPublic(state);
SortSupport sortKey = base->sortKeys;
- HeapTupleData ltup;
- HeapTupleData rtup;
- TupleDesc tupDesc;
- int nkey;
int32 compare;
- AttrNumber attno;
- Datum datum1,
- datum2;
- bool isnull1,
- isnull2;
/* Compare the leading sort key */
@@ -951,6 +957,25 @@ comparetup_heap(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
return compare;
/* Compare additional sort keys */
+ return comparetup_heap_fallback(a, b, state);
+}
+
+static int
+comparetup_heap_fallback(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
+{
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ SortSupport sortKey = base->sortKeys;
+ HeapTupleData ltup;
+ HeapTupleData rtup;
+ TupleDesc tupDesc;
+ int nkey;
+ int32 compare;
+ AttrNumber attno;
+ Datum datum1,
+ datum2;
+ bool isnull1,
+ isnull2;
+
ltup.t_len = ((MinimalTuple) a->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
ltup.t_data = (HeapTupleHeader) ((char *) a->tuple -
MINIMAL_TUPLE_OFFSET);
rtup.t_len = ((MinimalTuple) b->tuple)->t_len + MINIMAL_TUPLE_OFFSET;
@@ -1061,6 +1086,27 @@ removeabbrev_cluster(Tuplesortstate *state, SortTuple
*stups, int count)
static int
comparetup_cluster(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
+{
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ SortSupport sortKey = base->sortKeys;
+ int32 compare;
+
+ /* Compare the leading sort key, if it's simple */
+ if (base->haveDatum1)
+ {
+ compare = ApplySortComparator(a->datum1, a->isnull1,
+
b->datum1, b->isnull1,
+
sortKey);
+ if (compare != 0)
+ return compare;
+ }
+
+ return comparetup_cluster_fallback(a, b, state);
+}
+
+static int
+comparetup_cluster_fallback(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state)
{
TuplesortPublic *base = TuplesortstateGetPublic(state);
TuplesortClusterArg *arg = (TuplesortClusterArg *) base->arg;
@@ -1069,13 +1115,12 @@ comparetup_cluster(const SortTuple *a, const SortTuple
*b,
HeapTuple rtup;
TupleDesc tupDesc;
int nkey;
- int32 compare;
+ int32 compare = 0;
Datum datum1,
datum2;
bool isnull1,
isnull2;
- /* Be prepared to compare additional sort keys */
ltup = (HeapTuple) a->tuple;
rtup = (HeapTuple) b->tuple;
tupDesc = arg->tupDesc;
@@ -1083,12 +1128,6 @@ comparetup_cluster(const SortTuple *a, const SortTuple
*b,
/* Compare the leading sort key, if it's simple */
if (base->haveDatum1)
{
- compare = ApplySortComparator(a->datum1, a->isnull1,
-
b->datum1, b->isnull1,
-
sortKey);
- if (compare != 0)
- return compare;
-
if (sortKey->abbrev_converter)
{
AttrNumber leading =
arg->indexInfo->ii_IndexAttrNumbers[0];
@@ -1269,6 +1308,25 @@ comparetup_index_btree(const SortTuple *a, const
SortTuple *b,
* treatment for equal keys at the end.
*/
TuplesortPublic *base = TuplesortstateGetPublic(state);
+ SortSupport sortKey = base->sortKeys;
+ int32 compare;
+
+ /* Compare the leading sort key */
+ compare = ApplySortComparator(a->datum1, a->isnull1,
+ b->datum1,
b->isnull1,
+ sortKey);
+ if (compare != 0)
+ return compare;
+
+ /* Compare additional sort keys */
+ return comparetup_index_btree_fallback(a, b, state);
+}
+
+static int
+comparetup_index_btree_fallback(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state)
+{
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
TuplesortIndexBTreeArg *arg = (TuplesortIndexBTreeArg *) base->arg;
SortSupport sortKey = base->sortKeys;
IndexTuple tuple1;
@@ -1283,15 +1341,6 @@ comparetup_index_btree(const SortTuple *a, const
SortTuple *b,
bool isnull1,
isnull2;
-
- /* Compare the leading sort key */
- compare = ApplySortComparator(a->datum1, a->isnull1,
- b->datum1,
b->isnull1,
- sortKey);
- if (compare != 0)
- return compare;
-
- /* Compare additional sort keys */
tuple1 = (IndexTuple) a->tuple;
tuple2 = (IndexTuple) b->tuple;
keysz = base->nKeys;
@@ -1527,6 +1576,14 @@ comparetup_datum(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
return compare;
/* if we have abbreviations, then "tuple" has the original value */
+ return comparetup_datum_fallback(a, b, state);
+}
+
+static int
+comparetup_datum_fallback(const SortTuple *a, const SortTuple *b,
Tuplesortstate *state)
+{
+ TuplesortPublic *base = TuplesortstateGetPublic(state);
+ int32 compare = 0;
if (base->sortKeys->abbrev_converter)
compare =
ApplySortAbbrevFullComparator(PointerGetDatum(a->tuple), a->isnull1,
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index 12578e42bc..15967aa8e3 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -162,6 +162,13 @@ typedef struct
*/
SortTupleComparator comparetup;
+ /*
+ * Fall back to the full tuple for comparison, but only compare the
first
+ * sortkey if it was abbreviated. Otherwise, only compare second and
later
+ * sortkeys.
+ */
+ SortTupleComparator comparetup_fallback;
+
/*
* Alter datum1 representation in the SortTuple's array back from the
* abbreviated key to the first column value.
--
2.39.1
window-sort-bench-jcn-20230213.ods
Description: application/vnd.oasis.opendocument.spreadsheet
