I wrote:
> On Thu, Jan 26, 2023 at 7:15 PM David Rowley <dgrowle...@gmail.com> wrote:
> > I think the slower sorts I found in [2] could also be partially caused
> > by the current sort specialisation comparators re-comparing the
> > leading column during a tie-break. I've not gotten around to disabling
> > the sort specialisations to see if and how much this is a factor for
> > that test.
>
> Right, that's worth addressing independently of the window function
consideration. I'm still swapping this area back in my head, but I believe
one issue is that state->base.onlyKey signals two things: "one sortkey, not
abbreviated". We could add a separate branch for "first key unabbreviated,
nkeys>1" -- I don't think we'd need to specialize, just branch -- and
instead of state->base.comparetup, call a set of analogous functions that
only handle keys 2 and above (comparetup_tail_* ? or possibly just add a
boolean parameter compare_first). That would not pose a huge challenge, I
think, since they're already written like this:
>
> /* Compare the leading sort key */
> compare = ApplySortComparator(...);
> if (compare != 0)
> return compare;
>
> /* Compare additional sort keys */
> ...
>
> The null/non-null separation would eliminate a bunch of branches in
inlined comparators, so we could afford to add another branch for number of
keys.
I gave this a go, and it turns out we don't need any extra branches in the
inlined comparators -- the new fallbacks are naturally written to account
for the "!onlyKey" case. If the first sortkey was abbreviated, call its
full comparator, otherwise skip to the next sortkey (if there isn't one, we
shouldn't have gotten here). The existing comparetup functions try the
simple case and then call the fallback (which could be inlined for them but
I haven't looked).
Tests pass, but I'm not sure yet if we need more tests. I don't have a
purpose-built benchmark at the moment, but I'll see if any of my existing
tests exercise this code path. I can also try the window function case
unless someone beats me to it.
--
John Naylor
EDB: http://www.enterprisedb.com
From 65b94223f8bdb726b97d695f0040c12197d5e65d 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 v1] 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 | 114 ++++++++++++++++-----
src/include/utils/tuplesort.h | 6 ++
3 files changed, 96 insertions(+), 30 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..e65ac49d9d 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,7 @@ tuplesort_begin_index_hash(Relation heapRel,
base->removeabbrev = removeabbrev_index;
base->comparetup = comparetup_index_hash;
+ base->comparetup_fallback = NULL;
base->writetup = writetup_index;
base->readtup = readtup_index;
base->haveDatum1 = true;
@@ -476,6 +488,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 +559,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 +945,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 +956,26 @@ comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
return compare;
/* Compare additional sort keys */
+ return comparetup_heap_fallback(a, b, state);
+}
+
+/* Compare the first sortkey only if it was abbreviated, then compare the rest. */
+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;
@@ -1075,7 +1121,6 @@ comparetup_cluster(const SortTuple *a, const SortTuple *b,
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];
@@ -1100,6 +1139,9 @@ comparetup_cluster(const SortTuple *a, const SortTuple *b,
datum2, isnull2,
sortKey);
}
+ else
+ compare = 0;
+
if (compare != 0 || base->nKeys == 1)
return compare;
/* Compare additional columns the hard way */
@@ -1269,6 +1311,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 +1344,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,13 +1579,21 @@ 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);
if (base->sortKeys->abbrev_converter)
- compare = ApplySortAbbrevFullComparator(PointerGetDatum(a->tuple), a->isnull1,
+ return ApplySortAbbrevFullComparator(PointerGetDatum(a->tuple), a->isnull1,
PointerGetDatum(b->tuple), b->isnull1,
base->sortKeys);
- return compare;
+ /* shouldn't get here */
+ return 0;
}
static void
diff --git a/src/include/utils/tuplesort.h b/src/include/utils/tuplesort.h
index 12578e42bc..86fa57c870 100644
--- a/src/include/utils/tuplesort.h
+++ b/src/include/utils/tuplesort.h
@@ -162,6 +162,12 @@ typedef struct
*/
SortTupleComparator comparetup;
+ /*
+ * Only compares the first sortkey if it was abbreviated and we need a
+ * tiebreaker. 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.0
