Subject: Re: Considering additional sort specialisation functions for PG16

From: John Naylor <[email-masked]>
Date: Thu, 26 Jan 2023 17:29:25 +0700

On Tue, Aug 23, 2022 at 1:13 PM John Naylor <[email-masked]>
wrote:
>
> On Tue, Aug 23, 2022 at 11:24 AM David Rowley <[email-masked]>
wrote:
> >
> > On Tue, 23 Aug 2022 at 15:22, John Naylor <[email-masked]>
wrote:
> > > Did you happen to see
https://www.postgresql.org/message-id/CAFBsxsFhq8VUSkUL5YO17cFXbCPwtbbxBu%2Bd9MFrrsssfDXm3Q%40mail.gmail.com
> >
> > I missed that.  It looks like a much more promising idea than what I
> > came up with. I've not looked at your code yet, but I'm interested and
> > will aim to look soon.
>
> Note that I haven't actually implemented this idea yet, just tried to
> model the effects by lobotomizing the current comparators. I think
> it's worth pursuing and will try to come back to it this cycle, but if
> you or anyone else wants to try, that's fine of course.

Coming back to this, I wanted to sketch out this idea in a bit more detail.

Have two memtuple arrays, one for first sortkey null and one for first
sortkey non-null:
- Qsort the non-null array, including whatever specialization is available.
Existing specialized comparators could ignore nulls (and their ordering)
taking less space in the binary.
- Only if there is more than one sort key, qsort the null array. Ideally at
some point we would have a method of ignoring the first sortkey (this is an
existing opportunity that applies elsewhere as well).
- To handle two arrays, grow_memtuples() would need some adjustment, as
would any callers that read the final result of an in-memory sort -- they
would need to retrieve the tuples starting with the appropriate array
depending on NULLS FIRST/LAST behavior.

I believe external merges wouldn't have to do anything different, since
when writing out the tapes, we read from the arrays in the right order.

(One could extend this idea further and have two pools of tapes for null
and non-null first sortkey, that are merged separately, in the right order.
That sounds like quite a bit more complexity than is worth, however.)

--
John Naylor
EDB: http://www.enterprisedb.com

---

From: Pavel Borisov <[email-masked]>
Date: Thu, 26 Jan 2023 15:13:24 +0400

Hi, John!
Generally, I like the separation of non-null values before sorting and
would like to join as a reviewer when we come to patch. I have only a
small question:

> - Only if there is more than one sort key, qsort the null array. Ideally at some point we would have a method of ignoring the first sortkey (this is an existing opportunity that applies elsewhere as well).
Should we need to sort by the second sort key provided the first one
in NULL by standard or by some part of the code relying on this? I
suppose NULL values in the first sort key mean attribute values are
undefined and there is no preferred order between these tuples, even
if their second sort keys are different.

And maybe (unlikely IMO) we need some analog of NULLS DISCTICNT/NOT
DISTINCT in this scope?

Kind regards,
Pavel Borisov,
Supabase.

---

From: John Naylor <[email-masked]>
Date: Thu, 26 Jan 2023 19:06:55 +0700

On Thu, Jan 26, 2023 at 6:14 PM Pavel Borisov <[email-masked]>
wrote:

> > - Only if there is more than one sort key, qsort the null array.
Ideally at some point we would have a method of ignoring the first sortkey
(this is an existing opportunity that applies elsewhere as well).

> in NULL by standard or by some part of the code relying on this? I

I'm not sure I quite understand the question.

If there is more than one sort key, and the specialized comparison on the
first key gives a definitive zero result, it falls back to comparing all
keys from the full tuple. (The sorttuple struct only contains the first
sortkey, which might actually be an abbreviated key.) A possible
optimization, relevant here and also elsewhere, is to compare only using
keys starting from key2. But note: if the first key is abbreviated, a zero
result is not definitive, and we must check the first key's full value from
the tuple.

> if their second sort keys are different.

There is in fact a preferred order between these tuples -- the second key
is the tie breaker in this case.

---

From: David Rowley <[email-masked]>
Date: Fri, 27 Jan 2023 01:14:57 +1300

On Thu, 26 Jan 2023 at 23:29, John Naylor <[email-masked]> wrote:
> Have two memtuple arrays, one for first sortkey null and one for first sortkey non-null:
> - Qsort the non-null array, including whatever specialization is available. Existing specialized comparators could ignore nulls (and their ordering) taking less space in the binary.
> - To handle two arrays, grow_memtuples() would need some adjustment, as would any callers that read the final result of an in-memory sort -- they would need to retrieve the tuples starting with the appropriate array depending on NULLS FIRST/LAST behavior.

Thanks for coming back to this. I've been thinking about this again
recently due to what was discovered in [1].  Basically, the patch on
that thread is trying to eliminate the need for the ORDER BY sort in a
query such as: SELECT a,b,row_number() over (order by a) from ab order
by a,b;  the idea is to just perform the full sort on a,b for the
WindowClause so save from having to do an Incremental Sort on b for
the ORDER BY after evaluating the window funcs.  Surprisingly (for
me), we found a bunch of cases where the performance is better to do a
sort on some of the keys, then do an Incremental sort on the remainder
rather than just doing a single sort on everything.

I don't really understand why this is fully yet, but one theory I have
is that it might be down to work_mem being larger than the CPU's L3
cache and causing more cache line misses.  With the more simple sort,
there's less swapping of items in the array because the comparison
function sees tuples as equal more often.  I did find that the gap
between the two is not as large with fewer tuples to sort.

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.

Why I'm bringing this up here is that I wondered, in addition to what
you're mentioning above, if we're making some changes to allow
multiple in-memory arrays, would it be worth going a little further
and allowing it so we could have N arrays which we'd try to keep under
L3 cache size. Maybe some new GUC could be used to know what a good
value is.  With fast enough disks, it's often faster to use smaller
values of work_mem which don't exceed L3 to keep these batches
smaller.  Keeping them in memory would remove the need to write out
tapes.

I don't really know exactly if such a feature could easily be tagged
on to what you propose above, but I feel like what you're talking
about is part of the way towards that at least, maybe at the least,
the additional work could be kept in mind when this is written so that
it's easier to extend in the future.

David

[1] https://postgr.es/m/CAApHDvpAO5H_L84kn9gCJ_hihOavtmDjimKYyftjWtF69BJ=[email-masked]
[2] https://postgr.es/m/CAApHDvqh%2BqOHk4sbvvy%3DQr2NjPqAAVYf82oXY0g%3DZ2hRpC2Vmg%40mail.gmail.com

---

From: John Naylor <[email-masked]>
Date: Fri, 27 Jan 2023 13:56:29 +0700

sortkey non-null:
> > - Qsort the non-null array, including whatever specialization is
available. Existing specialized comparators could ignore nulls (and their
ordering) taking less space in the binary.
> recently due to what was discovered in [1].

That was indeed part of the motivation for bringing this up.

> smaller.  Keeping them in memory would remove the need to write out

That's interesting. I don't know enough to guess how complex it would be to
make "external" merges agnostic about whether the tapes are on disk or in
memory.

If in-memory sorts were designed analogously to external ones,
grow_memtuples would never have to repalloc, it could just allocate a new
tape, which could further shave some cycles.

My hunch in my last email was that having separate groups of tapes for each
null/non-null first sortkey would be complex, because it increases the
number of places that have to know about nulls and their ordering. If we
wanted to go to N arrays instead of 2, and additionally wanted separate
null/non-null treatment, it seems we would still need 2 sets of arrays, one
with N non-null-first-sortkey tapes and one with M null-first-sortkey tapes.

So using 2 arrays seems like the logical first step. I'd be curious to hear
other possible development paths.

> the sort specialisations to see if and how much this is a factor for

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 haven't thought through either of these ideas in the gory detail, but I
don't yet see any big obstacles.

---

From: John Naylor <[email-masked]>
Date: Mon, 30 Jan 2023 17:32:04 +0700

think, since they're already written like this:
> 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 <[email-masked]>
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