Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Feb 17, 2016 at 2:12 AM, Robert Haas  wrote:
> Committed, except I left out one comment hunk that I wasn't convinced about.

Thank you.


-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Wed, Dec 23, 2015 at 12:19 PM, Peter Geoghegan  wrote:
> On Tue, Dec 22, 2015 at 2:59 PM, Robert Haas  wrote:
>> OK, so I've gone ahead and committed and back-patched that.  Can you
>> please rebase and repost the remainder as a 9.6 proposal?
>
> I attach a rebased patch for 9.6 only.

Committed, except I left out one comment hunk that I wasn't convinced about.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Michael Paquier]

On Tue, Feb 16, 2016 at 5:58 AM, Alvaro Herrera
 wrote:
> Peter Geoghegan wrote:
>
>> Michael (the CF manager at the time) remembered to change the status
>> to "Ready for Committer" again; you see this entry immediately
>> afterwards:
>>
>> "New status: Ready for Committer"
>>
>> but I gather from the CF app history that Alvaro (the current CF
>> manager) did not remember to do that second step when he later moved
>> the patch to the "next" (current) CF. Or maybe he just wasn't aware of
>> this quirk of the CF app.

I recall switching this patch as "Ready for committer" based on the
status of the thread.

> That seems a bug in the CF app to me.
>
> (FWIW I'm not the "current" CF manager, because the CF I managed is
> already over.  I'm not sure that we know who the manager for the
> upcoming one is.)

When a patch with status "Ready for committer" on CF N is moved to CF
(N+1), its status is automatically changed to "Needs Review". That's
something to be aware of when cleaning up the CF app entries.
-- 
Michael


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Tom Lane]

Alvaro Herrera  writes:
> (FWIW I'm not the "current" CF manager, because the CF I managed is
> already over.  I'm not sure that we know who the manager for the
> upcoming one is.)

We had a vict^H^H^H^Hvolunteer a few days ago:

http://www.postgresql.org/message-id/56b91a6d.6030...@pgmasters.net

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Mon, Feb 15, 2016 at 12:58 PM, Alvaro Herrera
 wrote:
> (FWIW I'm not the "current" CF manager, because the CF I managed is
> already over.  I'm not sure that we know who the manager for the
> upcoming one is.)

It's pretty easy to forget that this was the first time in a long time
that the CF wasn't closed because the next CF began.  :-)


-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Alvaro Herrera]

Peter Geoghegan wrote:

> Michael (the CF manager at the time) remembered to change the status
> to "Ready for Committer" again; you see this entry immediately
> afterwards:
> 
> "New status: Ready for Committer"
> 
> but I gather from the CF app history that Alvaro (the current CF
> manager) did not remember to do that second step when he later moved
> the patch to the "next" (current) CF. Or maybe he just wasn't aware of
> this quirk of the CF app.

That seems a bug in the CF app to me.

(FWIW I'm not the "current" CF manager, because the CF I managed is
already over.  I'm not sure that we know who the manager for the
upcoming one is.)

-- 
Álvaro Herrerahttp://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Tue, Dec 22, 2015 at 10:49 PM, Peter Geoghegan  wrote:
> I attach a rebased patch for 9.6 only.

I marked the patch -- my own patch -- "Ready for Committer". I'm the
third person to have marked the patch "Ready for Committer", even
though no committer bounced the patch back for review by the reviewer,
Andreas:

https://commitfest.postgresql.org/9/300/

First Andreas did so, then Michael, and finally myself. The problem is
that you see things like this:

"Closed in commitfest 2015-11 with status: Moved to next CF"

Michael (the CF manager at the time) remembered to change the status
to "Ready for Committer" again; you see this entry immediately
afterwards:

"New status: Ready for Committer"

but I gather from the CF app history that Alvaro (the current CF
manager) did not remember to do that second step when he later moved
the patch to the "next" (current) CF. Or maybe he just wasn't aware of
this quirk of the CF app.

I don't have a problem with having to resubmit a patch to the next CF
manually, but it's easy to miss that the status has been changed from
"Ready for Committer" to "Needs Review". I don't think anyone ever
argued for that, and this patch was accidentally in "Needs Review"
state for about 5 days. Can we fix it?

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Tue, Dec 22, 2015 at 10:49 AM, Peter Geoghegan  wrote:
> On Tue, Dec 22, 2015 at 9:31 AM, Robert Haas  wrote:
>>> It has some nice properties, because unsigned integers are so simple
>>> and flexible. For example, we can do it with int4 sometimes, and then
>>> compare two attributes at once on 64-bit platforms. Maybe the second
>>> attribute (the second set of 4 bytes) isn't an int4, though -- it's
>>> any other type's abbreviated key (which can be assumed to have a
>>> compatible representation). That's one more advanced possibility.
>>
>> Yikes.
>
> I'm not suggesting we'd want to do that immediately, or even at all.
> My point is -- stuff like this becomes possible. My intuition is that
> it might come up in a bunch of places.

I had a better idea, that is based on the same intuition that we can
leverage the flexibility of that standardized representation of
abbreviated keys to the hilt.

We use one bit to represent whether this is the first run, or a
subsequent run (in a world where replacement selection is only used
for "quicksort with spillover", and run number isn't that
interesting), and another bit to represent NULLness. These are the
most significant and second most significant bits, respectively. Fill
all remaining bits with your unsigned abbreviated key representation,
without regard to the underlying details of the type. Now, you just
found a way to cut the size of SortTuples significantly, to just two
pointers (whereas with alignment considerations, SortTuples currently
consume enough memory to store 3 pointers). You also just found a way
of significantly cutting the number of instructions that are needed
for the hot code path, because you don't really need an
abbreviation-based ApplySortComparator() inline function to interpret
things through -- whether or not NULLs are first or last, and how
NULLs are considered generally is all baked into the abbreviated
representation from the start.

This is certainly speculative stuff, and having multiple versions of
SortTuple would be inconvenient, but the point again is that there are
considerable upsides to a standardized representation (abbreviated
keys always being compared as unsigned integers), and no downsides.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Tue, Dec 22, 2015 at 9:31 AM, Robert Haas  wrote:
>> It has some nice properties, because unsigned integers are so simple
>> and flexible. For example, we can do it with int4 sometimes, and then
>> compare two attributes at once on 64-bit platforms. Maybe the second
>> attribute (the second set of 4 bytes) isn't an int4, though -- it's
>> any other type's abbreviated key (which can be assumed to have a
>> compatible representation). That's one more advanced possibility.
>
> Yikes.

I'm not suggesting we'd want to do that immediately, or even at all.
My point is -- stuff like this becomes possible. My intuition is that
it might come up in a bunch of places.

>> Another issue is that abbreviated keys in indexes are probably not
>> going to take 8 bytes, because they'll go in the ItemId array. It's
>> likely to be very useful to be able to take the first two bytes, and
>> know that a uint16 comparison is all that is needed, and have a basis
>> to perform an interpolation search rather than a binary search
>> (although that needs to be adaptive to different distributions, I
>> think it could be an effective technique -- there are many cache
>> misses for binary searches on internal B-Tree pages).
>
> Hmm, that seems iffy to me.  There are plenty of data sets where 8
> bytes is enough to get some meaningful information about what part of
> the keyspace you're in, but 2 bytes isn't.

Your experience with abbreviated keys for sorting is unlikely to
perfectly carry over here. That's because the 2 bytes are only put in
the internal pages (typically less than 1% of the total). These
internal pages typically have relatively low density anyway (we don't
use the The B* tree technique), so I think that the level of bloat
would be tiny. At the same time, these are the range of values that
naturally have very wide fan-out. For example, the entire range of
values in the index is represented at the root page.

All of that having been said, yes, it could still be useless. But
then, the overhead will still tend to be nill, due to the fact that
abbreviated key generation can be so effectively amortized (it happens
only once, per page split), and because branch prediction will tend to
remove any penalty.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Tue, Dec 22, 2015 at 12:31 PM, Robert Haas  wrote:
> On Mon, Dec 21, 2015 at 2:55 PM, Peter Geoghegan  wrote:
>> On Mon, Dec 21, 2015 at 10:53 AM, Robert Haas  wrote:
>>> PFA my proposal for comment changes for 9.5 and master.  This is based
>>> on your 0001, but I edited somewhat.  Please let me know your
>>> thoughts.  I am not willing to go further and rearrange actual code in
>>> 9.5 at this point; it just isn't necessary.
>>
>> Fine by me. But this revision hasn't made the important point at all
>> -- which is that 0002 is safe. That's a stronger guarantee than the
>> abbreviated key representation being pass-by-value.
>
> Right.  I don't think that we should back-patch that stuff into 9.5.

OK, so I've gone ahead and committed and back-patched that.  Can you
please rebase and repost the remainder as a 9.6 proposal?

Thanks,

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Tue, Dec 22, 2015 at 2:59 PM, Robert Haas  wrote:
>> Right.  I don't think that we should back-patch that stuff into 9.5.
>
> OK, so I've gone ahead and committed and back-patched that.  Can you
> please rebase and repost the remainder as a 9.6 proposal?

OK. I don't know why you didn't acknowledge in your revision to
sortsupport.h that bitwise inequality must be a reliable proxy for
authoritative value inequality, which is a stronger restriction than
mandating that abbreviated keys always be pass-by-value, but I'm not
going to argue.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Tue, Dec 22, 2015 at 2:59 PM, Robert Haas  wrote:
> OK, so I've gone ahead and committed and back-patched that.  Can you
> please rebase and repost the remainder as a 9.6 proposal?

I attach a rebased patch for 9.6 only.


-- 
Peter Geoghegan
From 4bc33a602822ef0d56222f03174d71bbb4cd126b Mon Sep 17 00:00:00 2001
From: Peter Geoghegan 
Date: Thu, 9 Jul 2015 15:59:07 -0700
Subject: [PATCH] Reuse abbreviated keys in ordered [set] aggregates

When processing ordered aggregates following a sort that could make use
of the abbreviated key optimization, only call the equality operator to
compare successive pairs of tuples when their abbreviated keys were not
equal.  Only strict abbreviated key binary inequality is considered,
which is safe.
---
 src/backend/catalog/index.c|  2 +-
 src/backend/executor/nodeAgg.c | 20 ++---
 src/backend/executor/nodeSort.c|  2 +-
 src/backend/utils/adt/orderedsetaggs.c | 33 ++-
 src/backend/utils/sort/tuplesort.c | 76 --
 src/include/utils/tuplesort.h  |  4 +-
 6 files changed, 95 insertions(+), 42 deletions(-)

diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c10be3d..c6737c2 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -3073,7 +3073,7 @@ validate_index_heapscan(Relation heapRelation,
 			}
 
 			tuplesort_empty = !tuplesort_getdatum(state->tuplesort, true,
-  _val, _isnull);
+  _val, _isnull, NULL);
 			Assert(tuplesort_empty || !ts_isnull);
 			if (!tuplesort_empty)
 			{
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 2e36855..f007c38 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -539,7 +539,8 @@ fetch_input_tuple(AggState *aggstate)
 
 	if (aggstate->sort_in)
 	{
-		if (!tuplesort_gettupleslot(aggstate->sort_in, true, aggstate->sort_slot))
+		if (!tuplesort_gettupleslot(aggstate->sort_in, true, aggstate->sort_slot,
+	NULL))
 			return NULL;
 		slot = aggstate->sort_slot;
 	}
@@ -894,8 +895,8 @@ advance_aggregates(AggState *aggstate, AggStatePerGroup pergroup)
  * The one-input case is handled separately from the multi-input case
  * for performance reasons: for single by-value inputs, such as the
  * common case of count(distinct id), the tuplesort_getdatum code path
- * is around 300% faster.  (The speedup for by-reference types is less
- * but still noticeable.)
+ * is around 300% faster.  (The speedup for by-reference types without
+ * abbreviated key support is less but still noticeable.)
  *
  * This function handles only one grouping set (already set in
  * aggstate->current_set).
@@ -913,6 +914,8 @@ process_ordered_aggregate_single(AggState *aggstate,
 	MemoryContext workcontext = aggstate->tmpcontext->ecxt_per_tuple_memory;
 	MemoryContext oldContext;
 	bool		isDistinct = (pertrans->numDistinctCols > 0);
+	Datum		newAbbrevVal = (Datum) 0;
+	Datum		oldAbbrevVal = (Datum) 0;
 	FunctionCallInfo fcinfo = >transfn_fcinfo;
 	Datum	   *newVal;
 	bool	   *isNull;
@@ -932,7 +935,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 	 */
 
 	while (tuplesort_getdatum(pertrans->sortstates[aggstate->current_set],
-			  true, newVal, isNull))
+			  true, newVal, isNull, ))
 	{
 		/*
 		 * Clear and select the working context for evaluation of the equality
@@ -950,6 +953,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 			haveOldVal &&
 			((oldIsNull && *isNull) ||
 			 (!oldIsNull && !*isNull &&
+			  oldAbbrevVal == newAbbrevVal &&
 			  DatumGetBool(FunctionCall2(>equalfns[0],
 		 oldVal, *newVal)
 		{
@@ -965,6 +969,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 pfree(DatumGetPointer(oldVal));
 			/* and remember the new one for subsequent equality checks */
 			oldVal = *newVal;
+			oldAbbrevVal = newAbbrevVal;
 			oldIsNull = *isNull;
 			haveOldVal = true;
 		}
@@ -1002,6 +1007,8 @@ process_ordered_aggregate_multi(AggState *aggstate,
 	TupleTableSlot *slot2 = pertrans->uniqslot;
 	int			numTransInputs = pertrans->numTransInputs;
 	int			numDistinctCols = pertrans->numDistinctCols;
+	Datum		newAbbrevVal = (Datum) 0;
+	Datum		oldAbbrevVal = (Datum) 0;
 	bool		haveOldValue = false;
 	int			i;
 
@@ -1012,7 +1019,7 @@ process_ordered_aggregate_multi(AggState *aggstate,
 		ExecClearTuple(slot2);
 
 	while (tuplesort_gettupleslot(pertrans->sortstates[aggstate->current_set],
-  true, slot1))
+  true, slot1, ))
 	{
 		/*
 		 * Extract the first numTransInputs columns as datums to pass to the
@@ -1023,6 +1030,7 @@ process_ordered_aggregate_multi(AggState *aggstate,
 
 		if (numDistinctCols == 0 ||
 			!haveOldValue ||
+			newAbbrevVal != oldAbbrevVal ||
 			!execTuplesMatch(slot1, slot2,
 			 numDistinctCols,
 			 pertrans->sortColIdx,
@@ -1046,6 +1054,8 @@ process_ordered_aggregate_multi(AggState *aggstate,

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Mon, Dec 21, 2015 at 2:55 PM, Peter Geoghegan  wrote:
> On Mon, Dec 21, 2015 at 10:53 AM, Robert Haas  wrote:
>> PFA my proposal for comment changes for 9.5 and master.  This is based
>> on your 0001, but I edited somewhat.  Please let me know your
>> thoughts.  I am not willing to go further and rearrange actual code in
>> 9.5 at this point; it just isn't necessary.
>
> Fine by me. But this revision hasn't made the important point at all
> -- which is that 0002 is safe. That's a stronger guarantee than the
> abbreviated key representation being pass-by-value.

Right.  I don't think that we should back-patch that stuff into 9.5.

>> Looking at this whole system again, I wonder if we're missing a trick
>> here.  How about if we decree from on high that the abbreviated-key
>> comparator is always just the application of an integer comparison
>> operator?  The only abbreviation function that we have right now that
>> wouldn't be happy with that is the one for numeric, and that looks
>> like it could be fixed.
>
> I gather you mean that we'd decree that they were always compared
> using a text or uuid style 3-way unsigned integer comparison, allowing
> us to hardcode that.

Right.

>> Then we could hard-code knowledge of this
>> representation in tuplesort.c in such a way that it wouldn't need to
>> call a comparator function at all - instead of doing
>> ApplySortComparator() and then maybe ApplySortAbbrevFullComparator(),
>> it would do something like:
>>
>> if (using_abbreviation && (compare = ApplyAbbrevComparator(...)) != 0)
>> return compare;
>>
>> I'm not sure if that would save enough cycles vs. the status quo to be
>> worth bothering with, but it seems like it might.  You may have a
>> better feeling for that than I do.
>
> I like this idea. I thought of it myself already, actually.
>
> It has some nice properties, because unsigned integers are so simple
> and flexible. For example, we can do it with int4 sometimes, and then
> compare two attributes at once on 64-bit platforms. Maybe the second
> attribute (the second set of 4 bytes) isn't an int4, though -- it's
> any other type's abbreviated key (which can be assumed to have a
> compatible representation). That's one more advanced possibility.

Yikes.

> It seems worthwhile because numeric is the odd one out. Once I or
> someone else gets around to adding network types, which could happen
> in 9.6, then we are done (because there is already a pending patch
> that adds support for remaining character-like types and alternative
> opclasses). I really don't foresee much additional use of abbreviated
> keys beyond these cases. There'd be a small but nice boost by not
> doing pointer chasing for the abbreviated key comparison, I imagine,
> but that benefit would be felt everywhere. Numeric is the odd one out
> currently, but as you say it can be fixed, and I foresee no other
> trouble from any other opclass/type that cares about abbreviation.
>
> Another issue is that abbreviated keys in indexes are probably not
> going to take 8 bytes, because they'll go in the ItemId array. It's
> likely to be very useful to be able to take the first two bytes, and
> know that a uint16 comparison is all that is needed, and have a basis
> to perform an interpolation search rather than a binary search
> (although that needs to be adaptive to different distributions, I
> think it could be an effective technique -- there are many cache
> misses for binary searches on internal B-Tree pages).

Hmm, that seems iffy to me.  There are plenty of data sets where 8
bytes is enough to get some meaningful information about what part of
the keyspace you're in, but 2 bytes isn't.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Mon, Dec 21, 2015 at 10:53 AM, Robert Haas  wrote:
> PFA my proposal for comment changes for 9.5 and master.  This is based
> on your 0001, but I edited somewhat.  Please let me know your
> thoughts.  I am not willing to go further and rearrange actual code in
> 9.5 at this point; it just isn't necessary.

Fine by me. But this revision hasn't made the important point at all
-- which is that 0002 is safe. That's a stronger guarantee than the
abbreviated key representation being pass-by-value.

> Looking at this whole system again, I wonder if we're missing a trick
> here.  How about if we decree from on high that the abbreviated-key
> comparator is always just the application of an integer comparison
> operator?  The only abbreviation function that we have right now that
> wouldn't be happy with that is the one for numeric, and that looks
> like it could be fixed.

I gather you mean that we'd decree that they were always compared
using a text or uuid style 3-way unsigned integer comparison, allowing
us to hardcode that.

> Then we could hard-code knowledge of this
> representation in tuplesort.c in such a way that it wouldn't need to
> call a comparator function at all - instead of doing
> ApplySortComparator() and then maybe ApplySortAbbrevFullComparator(),
> it would do something like:
>
> if (using_abbreviation && (compare = ApplyAbbrevComparator(...)) != 0)
> return compare;
>
> I'm not sure if that would save enough cycles vs. the status quo to be
> worth bothering with, but it seems like it might.  You may have a
> better feeling for that than I do.

I like this idea. I thought of it myself already, actually.

It has some nice properties, because unsigned integers are so simple
and flexible. For example, we can do it with int4 sometimes, and then
compare two attributes at once on 64-bit platforms. Maybe the second
attribute (the second set of 4 bytes) isn't an int4, though -- it's
any other type's abbreviated key (which can be assumed to have a
compatible representation). That's one more advanced possibility.

It seems worthwhile because numeric is the odd one out. Once I or
someone else gets around to adding network types, which could happen
in 9.6, then we are done (because there is already a pending patch
that adds support for remaining character-like types and alternative
opclasses). I really don't foresee much additional use of abbreviated
keys beyond these cases. There'd be a small but nice boost by not
doing pointer chasing for the abbreviated key comparison, I imagine,
but that benefit would be felt everywhere. Numeric is the odd one out
currently, but as you say it can be fixed, and I foresee no other
trouble from any other opclass/type that cares about abbreviation.

Another issue is that abbreviated keys in indexes are probably not
going to take 8 bytes, because they'll go in the ItemId array. It's
likely to be very useful to be able to take the first two bytes, and
know that a uint16 comparison is all that is needed, and have a basis
to perform an interpolation search rather than a binary search
(although that needs to be adaptive to different distributions, I
think it could be an effective technique -- there are many cache
misses for binary searches on internal B-Tree pages).

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Fri, Dec 18, 2015 at 2:22 PM, Peter Geoghegan  wrote:
> On Fri, Dec 18, 2015 at 9:35 AM, Robert Haas  wrote:
>>> Attached revision updates both the main commit (the optimization), and
>>> the backpatch commit (updated the contract).
>>
>> -   /* abbreviation is possible here only for by-reference types */
>> +   /*
>> +* Abbreviation is possible here only for by-reference types.
>> Note that a
>> +* pass-by-value representation for abbreviated values is forbidden, 
>> but
>> +* that's a distinct, generic restriction imposed by the SortSupport
>> +* contract.
>>
>> I think that you have not written what you meant to write here.  I
>> think what you mean is "Note that a pass-by-REFERENCE representation
>> for abbreviated values is forbidden...".
>
> You're right. Sorry about that.

PFA my proposal for comment changes for 9.5 and master.  This is based
on your 0001, but I edited somewhat.  Please let me know your
thoughts.  I am not willing to go further and rearrange actual code in
9.5 at this point; it just isn't necessary.

Looking at this whole system again, I wonder if we're missing a trick
here.  How about if we decree from on high that the abbreviated-key
comparator is always just the application of an integer comparison
operator?  The only abbreviation function that we have right now that
wouldn't be happy with that is the one for numeric, and that looks
like it could be fixed.  Then we could hard-code knowledge of this
representation in tuplesort.c in such a way that it wouldn't need to
call a comparator function at all - instead of doing
ApplySortComparator() and then maybe ApplySortAbbrevFullComparator(),
it would do something like:

if (using_abbreviation && (compare = ApplyAbbrevComparator(...)) != 0)
return compare;

I'm not sure if that would save enough cycles vs. the status quo to be
worth bothering with, but it seems like it might.  You may have a
better feeling for that than I do.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 6572af8..cf1cdcb 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -930,7 +930,14 @@ tuplesort_begin_datum(Oid datumType, Oid sortOperator, Oid sortCollation,
 	state->sortKeys->ssup_collation = sortCollation;
 	state->sortKeys->ssup_nulls_first = nullsFirstFlag;
 
-	/* abbreviation is possible here only for by-reference types */
+	/*
+	 * Abbreviation is possible here only for by-reference types.  In theory,
+	 * a pass-by-value datatype could have an abbreviated form that is cheaper
+	 * to compare.  In a tuple sort, we could support that, because we can
+	 * always extract the original datum from the tuple is needed.  Here, we
+	 * can't, because a datum sort only stores a single copy of the datum;
+	 * the "tuple" field of each sortTuple is NULL.
+	 */
 	state->sortKeys->abbreviate = !typbyval;
 
 	PrepareSortSupportFromOrderingOp(sortOperator, state->sortKeys);
@@ -1271,7 +1278,7 @@ tuplesort_putindextuplevalues(Tuplesortstate *state, Relation rel,
 		 * Store ordinary Datum representation, or NULL value.  If there is a
 		 * converter it won't expect NULL values, and cost model is not
 		 * required to account for NULL, so in that case we avoid calling
-		 * converter and just set datum1 to "void" representation (to be
+		 * converter and just set datum1 to zeroed representation (to be
 		 * consistent).
 		 */
 		stup.datum1 = original;
@@ -3155,7 +3162,7 @@ copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup)
 		 * Store ordinary Datum representation, or NULL value.  If there is a
 		 * converter it won't expect NULL values, and cost model is not
 		 * required to account for NULL, so in that case we avoid calling
-		 * converter and just set datum1 to "void" representation (to be
+		 * converter and just set datum1 to zeroed representation (to be
 		 * consistent).
 		 */
 		stup->datum1 = original;
@@ -3397,7 +3404,7 @@ copytup_cluster(Tuplesortstate *state, SortTuple *stup, void *tup)
 		 * Store ordinary Datum representation, or NULL value.  If there is a
 		 * converter it won't expect NULL values, and cost model is not
 		 * required to account for NULL, so in that case we avoid calling
-		 * converter and just set datum1 to "void" representation (to be
+		 * converter and just set datum1 to zeroed representation (to be
 		 * consistent).
 		 */
 		stup->datum1 = original;
@@ -3701,7 +3708,7 @@ copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup)
 		 * Store ordinary Datum representation, or NULL value.  If there is a
 		 * converter it won't expect NULL values, and cost model is not
 		 * required to account for NULL, so in that case we avoid calling
-		 * converter and just set datum1 to "void" representation (to be
+		 * converter and just set datum1 to zeroed 

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Thu, Dec 17, 2015 at 11:43 PM, Peter Geoghegan  wrote:
> On Wed, Dec 16, 2015 at 12:04 PM, Peter Geoghegan  wrote:
>>> What kind of state is that?  Can't we define this in terms of what it
>>> is rather than how it gets that way?
>>
>> It's zeroed.
>>
>> I guess we can update everything, including existing comments, to reflect 
>> that.

Thanks, this looks much easier to understand from here.

> Attached revision updates both the main commit (the optimization), and
> the backpatch commit (updated the contract).

-   /* abbreviation is possible here only for by-reference types */
+   /*
+* Abbreviation is possible here only for by-reference types.
Note that a
+* pass-by-value representation for abbreviated values is forbidden, but
+* that's a distinct, generic restriction imposed by the SortSupport
+* contract.

I think that you have not written what you meant to write here.  I
think what you mean is "Note that a pass-by-REFERENCE representation
for abbreviated values is forbidden...".

+   /*
+* If we produced only one initial run (quite likely if the total data
+* volume is between 1X and 2X workMem), we can just use that
tape as the
+* finished output, rather than doing a useless merge.  (This obvious
+* optimization is not in Knuth's algorithm.)
+*/
+   if (state->currentRun == 1)
+   {
+   state->result_tape = state->tp_tapenum[state->destTape];
+   /* must freeze and rewind the finished output tape */
+   LogicalTapeFreeze(state->tapeset, state->result_tape);
+   state->status = TSS_SORTEDONTAPE;
+   return;
+   }

I don't understand the point of moving this code.  If there's some
reason to do this after rewinding the tapes rather than beforehand, I
think we should articulate that reason in the comment block.

The last hunk in your 0001 patch properly belongs in 0002.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Fri, Dec 18, 2015 at 9:35 AM, Robert Haas  wrote:
>> Attached revision updates both the main commit (the optimization), and
>> the backpatch commit (updated the contract).
>
> -   /* abbreviation is possible here only for by-reference types */
> +   /*
> +* Abbreviation is possible here only for by-reference types.
> Note that a
> +* pass-by-value representation for abbreviated values is forbidden, 
> but
> +* that's a distinct, generic restriction imposed by the SortSupport
> +* contract.
>
> I think that you have not written what you meant to write here.  I
> think what you mean is "Note that a pass-by-REFERENCE representation
> for abbreviated values is forbidden...".

You're right. Sorry about that.

> +   /*
> +* If we produced only one initial run (quite likely if the total data
> +* volume is between 1X and 2X workMem), we can just use that
> tape as the
> +* finished output, rather than doing a useless merge.  (This obvious
> +* optimization is not in Knuth's algorithm.)
> +*/
> +   if (state->currentRun == 1)
> +   {
> +   state->result_tape = state->tp_tapenum[state->destTape];
> +   /* must freeze and rewind the finished output tape */
> +   LogicalTapeFreeze(state->tapeset, state->result_tape);
> +   state->status = TSS_SORTEDONTAPE;
> +   return;
> +   }
>
> I don't understand the point of moving this code.  If there's some
> reason to do this after rewinding the tapes rather than beforehand, I
> think we should articulate that reason in the comment block.

I thought that was made clear by the 0001 commit message. Think of
what happens when we don't disable abbreviated in the final
TSS_SORTEDONTAPE phase should the "if (state->currentRun == 1)" path
have been taken (but *not* the path that also ends in
TSS_SORTEDONTAPE, when caller requires randomAccess but we spill to
tape, or any other case). What happens is: The code in 0002 gets
confused, and attempts to pass back a pointer value as an "abbreviated
key". That's a bug.

> The last hunk in your 0001 patch properly belongs in 0002.

You could certainly argue that the last hunk of 0001 belongs in 0002.
I only moved it to 0001 when I realized that we might as well keep the
branches in sync, since the ordering is insignificant from a 9.5
perspective (although it might still be tidier), and there is a need
to backpatch anyway. I'm not insisting on doing it that way.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Dec 16, 2015 at 12:04 PM, Peter Geoghegan  wrote:
>> What kind of state is that?  Can't we define this in terms of what it
>> is rather than how it gets that way?
>
> It's zeroed.
>
> I guess we can update everything, including existing comments, to reflect 
> that.

Attached revision updates both the main commit (the optimization), and
the backpatch commit (updated the contract).

Changes:

* Changes commit intended for backpatch to 9.5 to use new "zeroed"
terminology (not "void" representation).

* Puts fix within mergerun() (for this patch) in the same backpatch
commit. We might as well keep this consistent, even though the
correctness of 9.5 does not actually hinge upon having this change --
there is zero risk of breaking something in 9.5, and avoiding
backpatching this part can only lead to confusion in the future.

* Some minor tweaks to tuplesort.c. Make sure that
tuplesort_putdatum() zeroes datum1 directly for NULL values. Comment
tweaks.

* Add comment to the datum case, discussing restriction there.

I was wrong when I said that the datum sort case currently tacitly
acknowledges as possible/useful something that the revised SortSupport
contract will forbid (I wrote that e-mail in haste).

What I propose to make the SortSupport contract forbid here is
abbreviated keys that are *themselves* pass-by-reference. It is true
that today, we do not support pass-by-value types with abbreviated
keys for the datum case only (such opclass support could be slightly
useful for float8, for example -- int8 comparisons of an alternative
representation might be decisively cheaper). But that existing
restriction is entirely distinct to the new restriction I propose to
create. It seems like this distinction should be pointed out in
passing, which I've done.

-- 
Peter Geoghegan
From c740eac2a4ba42ac2b5ab34c342534ff8d944666 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan 
Date: Mon, 6 Jul 2015 13:37:26 -0700
Subject: [PATCH 2/2] Reuse abbreviated keys in ordered [set] aggregates

When processing ordered aggregates following a sort that could make use
of the abbreviated key optimization, only call the equality operator to
compare successive pairs of tuples when their abbreviated keys were not
equal.  Only strict abbreviated key binary inequality is considered,
which is safe.
---
 src/backend/catalog/index.c|  2 +-
 src/backend/executor/nodeAgg.c | 20 
 src/backend/executor/nodeSort.c|  2 +-
 src/backend/utils/adt/orderedsetaggs.c | 33 +
 src/backend/utils/sort/tuplesort.c | 44 --
 src/include/utils/tuplesort.h  |  4 ++--
 6 files changed, 79 insertions(+), 26 deletions(-)

diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index c10be3d..c6737c2 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -3073,7 +3073,7 @@ validate_index_heapscan(Relation heapRelation,
 			}
 
 			tuplesort_empty = !tuplesort_getdatum(state->tuplesort, true,
-  _val, _isnull);
+  _val, _isnull, NULL);
 			Assert(tuplesort_empty || !ts_isnull);
 			if (!tuplesort_empty)
 			{
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 2e36855..2972180 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -539,7 +539,8 @@ fetch_input_tuple(AggState *aggstate)
 
 	if (aggstate->sort_in)
 	{
-		if (!tuplesort_gettupleslot(aggstate->sort_in, true, aggstate->sort_slot))
+		if (!tuplesort_gettupleslot(aggstate->sort_in, true,
+	aggstate->sort_slot, NULL))
 			return NULL;
 		slot = aggstate->sort_slot;
 	}
@@ -894,8 +895,8 @@ advance_aggregates(AggState *aggstate, AggStatePerGroup pergroup)
  * The one-input case is handled separately from the multi-input case
  * for performance reasons: for single by-value inputs, such as the
  * common case of count(distinct id), the tuplesort_getdatum code path
- * is around 300% faster.  (The speedup for by-reference types is less
- * but still noticeable.)
+ * is around 300% faster.  (The speedup for by-reference types without
+ * abbreviated key support is less but still noticeable.)
  *
  * This function handles only one grouping set (already set in
  * aggstate->current_set).
@@ -913,6 +914,8 @@ process_ordered_aggregate_single(AggState *aggstate,
 	MemoryContext workcontext = aggstate->tmpcontext->ecxt_per_tuple_memory;
 	MemoryContext oldContext;
 	bool		isDistinct = (pertrans->numDistinctCols > 0);
+	Datum		newAbbrevVal = (Datum) 0;
+	Datum		oldAbbrevVal = (Datum) 0;
 	FunctionCallInfo fcinfo = >transfn_fcinfo;
 	Datum	   *newVal;
 	bool	   *isNull;
@@ -932,7 +935,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 	 */
 
 	while (tuplesort_getdatum(pertrans->sortstates[aggstate->current_set],
-			  true, newVal, isNull))
+			  true, newVal, isNull, ))
 	{
 		/*
 		 * Clear and select the working 

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Wed, Dec 9, 2015 at 5:15 PM, Peter Geoghegan  wrote:
> On Wed, Dec 9, 2015 at 11:31 AM, Robert Haas  wrote:
>> I find the references to a "void" representation in this patch to be
>> completely opaque.  I see that there are some such references in
>> tuplesort.c already, and most likely they were put there by commits
>> that I did, so I guess I have nobody but myself to blame, but I don't
>> know what this means, and I don't think we should let this terminology
>> proliferate.
>>
>> My understanding is that the "void" representation is intended to
>> whatever Datum we originally got, which might be a pointer.  Why not
>> just say that instead of referring to it this way?
>
> That isn't what is intended. "void" is the state that macros like
> index_getattr() leave NULL leading attributes (that go in the
> SortTuple.datum1 field) in.

What kind of state is that?  Can't we define this in terms of what it
is rather than how it gets that way?

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Dec 16, 2015 at 9:36 AM, Robert Haas  wrote:
>> That isn't what is intended. "void" is the state that macros like
>> index_getattr() leave NULL leading attributes (that go in the
>> SortTuple.datum1 field) in.
>
> What kind of state is that?  Can't we define this in terms of what it
> is rather than how it gets that way?

It's zeroed.

I guess we can update everything, including existing comments, to reflect that.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Dec 9, 2015 at 2:15 PM, Peter Geoghegan  wrote:
> I think that you're missing that patch 0001 formally forbids
> abbreviated keys that are pass-by-value, by revising the contract
> (this is proposed for backpatch to 9.5 -- only comments are changed).
> This is already something that is all but forbidden, although the
> datum case does tacitly acknowledge the possibility by not allowing
> abbreviation to work with the pass-by-value-and-yet-abbreviated case.
>
> I think that this revision is also useful for putting abbreviated keys
> in indexes, something that may happen yet.

I'm also depending on this for the "quicksort for every sort run" patch, BTW:

+   /*
+* Kludge:  Trigger abbreviated tie-breaker if in-memory tuples
+* use abbreviation (writing tuples to tape never preserves
+* abbreviated keys).  Do this by assigning in-memory
+* abbreviated tuple to tape tuple directly.
+*
+* It doesn't seem worth generating a new abbreviated key for
+* the tape tuple, and this approach is simpler than
+* "unabbreviating" the memtuple tuple from a "common" routine
+* like this.
+*/
+   if (state->sortKeys != NULL &&
state->sortKeys->abbrev_converter != NULL)
+   stup->datum1 = state->memtuples[state->current].datum1;

I could, as an alternative approach, revise tuplesort so that
self-comparison works (something we currently assert against [1]),
something that would probably *also* require and update to the
sortsupport.h contract, but this seemed simpler and more general.

In general, I think that there are plenty of reasons to forbid
pass-by-reference abbreviated keys (where the abbreviated comparator
itself is a pointer, something much more complicated than an integer
3-way comparison or similar).

[1] Commit c5a03256c
-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Robert Haas]

On Sat, Oct 10, 2015 at 9:03 PM, Peter Geoghegan  wrote:
> On Fri, Sep 25, 2015 at 2:39 PM, Jeff Janes  wrote:
>> This needs a rebase, there are several conflicts in 
>> src/backend/executor/nodeAgg.c
>
> I attached a revised version of the second patch in the series, fixing
> this bitrot.
>
> I also noticed a bug in tuplesort's TSS_SORTEDONTAPE case with the
> previous patch, where no final on-the-fly merge step is required (no
> merge step is required whatsoever, because replacement selection
> managed to produce only one run). The function mergeruns() previously
> only "abandoned" abbreviated ahead of any merge step iff there was
> one. When there was only one run (not requiring a merge) it happened
> to continue to keep its state consistent with abbreviated keys still
> being in use. It didn't matter before, because abbreviated keys were
> only for tuplesort to compare, but that's different now.
>
> That bug is fixed in this revision by reordering things within
> mergeruns(). The previous order of the two things that were switched
> is not at all significant (I should know, I wrote that code).

I find the references to a "void" representation in this patch to be
completely opaque.  I see that there are some such references in
tuplesort.c already, and most likely they were put there by commits
that I did, so I guess I have nobody but myself to blame, but I don't
know what this means, and I don't think we should let this terminology
proliferate.

My understanding is that the "void" representation is intended to
whatever Datum we originally got, which might be a pointer.  Why not
just say that instead of referring to it this way?

My understanding is also that it's OK if the abbreviated key stays the
same even though the value has changed, but that the reverse could
cause queries to return wrong answers.  The first part of that
justifies why this is safe when no abbreviation is available: we'll
return an abbreviated value of 0 for everything, but that's fine.
However, using the original Datum (which might be a pointer) seems
unsafe, because two binary-identical values could be stored at
different addresses and thus have different pointer representations.

I'm probably missing something here, so clue me in...

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Dec 9, 2015 at 11:31 AM, Robert Haas  wrote:
> I find the references to a "void" representation in this patch to be
> completely opaque.  I see that there are some such references in
> tuplesort.c already, and most likely they were put there by commits
> that I did, so I guess I have nobody but myself to blame, but I don't
> know what this means, and I don't think we should let this terminology
> proliferate.
>
> My understanding is that the "void" representation is intended to
> whatever Datum we originally got, which might be a pointer.  Why not
> just say that instead of referring to it this way?

That isn't what is intended. "void" is the state that macros like
index_getattr() leave NULL leading attributes (that go in the
SortTuple.datum1 field) in. However, the function tuplesort_putdatum()
requires callers to initialize their Datum to 0 now, which is new. A
"void" representation is a would-be NULL pointer in the case of
pass-by-value types, and a NULL pointer for pass-by-reference types.

> My understanding is also that it's OK if the abbreviated key stays the
> same even though the value has changed, but that the reverse could
> cause queries to return wrong answers.  The first part of that
> justifies why this is safe when no abbreviation is available: we'll
> return an abbreviated value of 0 for everything, but that's fine.
> However, using the original Datum (which might be a pointer) seems
> unsafe, because two binary-identical values could be stored at
> different addresses and thus have different pointer representations.
>
> I'm probably missing something here, so clue me in...

I think that you're missing that patch 0001 formally forbids
abbreviated keys that are pass-by-value, by revising the contract
(this is proposed for backpatch to 9.5 -- only comments are changed).
This is already something that is all but forbidden, although the
datum case does tacitly acknowledge the possibility by not allowing
abbreviation to work with the pass-by-value-and-yet-abbreviated case.

I think that this revision is also useful for putting abbreviated keys
in indexes, something that may happen yet.

-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Wed, Dec 9, 2015 at 2:15 PM, Peter Geoghegan  wrote:
> I think that you're missing that patch 0001 formally forbids
> abbreviated keys that are pass-by-value

Sorry. I do of course mean it forbids abbreviated keys that are *not*
pass-by-value (that are pass-by-reference).


-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Andreas Karlsson]

Hi,

I have reviewed this patch and it still applies to master, compiles and 
passes the test suite.


I like the goal of the patch, making use of the already existing 
abbreviation machinery in more cases is something we should do and the 
patch itself looks clean.


I can also confirm the roughly 25% speedup in the best case (numerics 
which are all distinct) with no measurable slowdown in the worst case.


Given this speedup and the small size of the patch I think we should 
apply it. I will set this patch to "Ready for Commiter".


Andreas


--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Sun, Dec 6, 2015 at 7:14 PM, Andreas Karlsson  wrote:
> I can also confirm the roughly 25% speedup in the best case (numerics which
> are all distinct) with no measurable slowdown in the worst case.
>
> Given this speedup and the small size of the patch I think we should apply
> it. I will set this patch to "Ready for Commiter".

Thanks for the review, Andreas.


-- 
Peter Geoghegan


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] Re: Reusing abbreviated keys during second pass of ordered [set] aggregates

[Peter Geoghegan]

On Fri, Sep 25, 2015 at 2:39 PM, Jeff Janes  wrote:
> This needs a rebase, there are several conflicts in 
> src/backend/executor/nodeAgg.c

I attached a revised version of the second patch in the series, fixing
this bitrot.

I also noticed a bug in tuplesort's TSS_SORTEDONTAPE case with the
previous patch, where no final on-the-fly merge step is required (no
merge step is required whatsoever, because replacement selection
managed to produce only one run). The function mergeruns() previously
only "abandoned" abbreviated ahead of any merge step iff there was
one. When there was only one run (not requiring a merge) it happened
to continue to keep its state consistent with abbreviated keys still
being in use. It didn't matter before, because abbreviated keys were
only for tuplesort to compare, but that's different now.

That bug is fixed in this revision by reordering things within
mergeruns(). The previous order of the two things that were switched
is not at all significant (I should know, I wrote that code).

Thanks
-- 
Peter Geoghegan
From a82f0f723e1f5206d9c19b1b277acc0625aa54b1 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan 
Date: Mon, 6 Jul 2015 13:37:26 -0700
Subject: [PATCH 2/2] Reuse abbreviated keys in ordered [set] aggregates

When processing ordered aggregates following a sort that could make use
of the abbreviated key optimization, only call the equality operator to
compare successive pairs of tuples when their abbreviated keys were not
equal.  Only strict abbreviated key binary inequality is considered,
which is safe.
---
 src/backend/catalog/index.c|  2 +-
 src/backend/executor/nodeAgg.c | 20 ++---
 src/backend/executor/nodeSort.c|  2 +-
 src/backend/utils/adt/orderedsetaggs.c | 33 ++-
 src/backend/utils/sort/tuplesort.c | 74 +++---
 src/include/utils/tuplesort.h  |  4 +-
 6 files changed, 93 insertions(+), 42 deletions(-)

diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index e59b163..bb61018 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -3024,7 +3024,7 @@ validate_index_heapscan(Relation heapRelation,
 			}
 
 			tuplesort_empty = !tuplesort_getdatum(state->tuplesort, true,
-  _val, _isnull);
+  _val, _isnull, NULL);
 			Assert(tuplesort_empty || !ts_isnull);
 			indexcursor = (ItemPointer) DatumGetPointer(ts_val);
 		}
diff --git a/src/backend/executor/nodeAgg.c b/src/backend/executor/nodeAgg.c
index 2e36855..2972180 100644
--- a/src/backend/executor/nodeAgg.c
+++ b/src/backend/executor/nodeAgg.c
@@ -539,7 +539,8 @@ fetch_input_tuple(AggState *aggstate)
 
 	if (aggstate->sort_in)
 	{
-		if (!tuplesort_gettupleslot(aggstate->sort_in, true, aggstate->sort_slot))
+		if (!tuplesort_gettupleslot(aggstate->sort_in, true,
+	aggstate->sort_slot, NULL))
 			return NULL;
 		slot = aggstate->sort_slot;
 	}
@@ -894,8 +895,8 @@ advance_aggregates(AggState *aggstate, AggStatePerGroup pergroup)
  * The one-input case is handled separately from the multi-input case
  * for performance reasons: for single by-value inputs, such as the
  * common case of count(distinct id), the tuplesort_getdatum code path
- * is around 300% faster.  (The speedup for by-reference types is less
- * but still noticeable.)
+ * is around 300% faster.  (The speedup for by-reference types without
+ * abbreviated key support is less but still noticeable.)
  *
  * This function handles only one grouping set (already set in
  * aggstate->current_set).
@@ -913,6 +914,8 @@ process_ordered_aggregate_single(AggState *aggstate,
 	MemoryContext workcontext = aggstate->tmpcontext->ecxt_per_tuple_memory;
 	MemoryContext oldContext;
 	bool		isDistinct = (pertrans->numDistinctCols > 0);
+	Datum		newAbbrevVal = (Datum) 0;
+	Datum		oldAbbrevVal = (Datum) 0;
 	FunctionCallInfo fcinfo = >transfn_fcinfo;
 	Datum	   *newVal;
 	bool	   *isNull;
@@ -932,7 +935,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 	 */
 
 	while (tuplesort_getdatum(pertrans->sortstates[aggstate->current_set],
-			  true, newVal, isNull))
+			  true, newVal, isNull, ))
 	{
 		/*
 		 * Clear and select the working context for evaluation of the equality
@@ -950,6 +953,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 			haveOldVal &&
 			((oldIsNull && *isNull) ||
 			 (!oldIsNull && !*isNull &&
+			  oldAbbrevVal == newAbbrevVal &&
 			  DatumGetBool(FunctionCall2(>equalfns[0],
 		 oldVal, *newVal)
 		{
@@ -965,6 +969,7 @@ process_ordered_aggregate_single(AggState *aggstate,
 pfree(DatumGetPointer(oldVal));
 			/* and remember the new one for subsequent equality checks */
 			oldVal = *newVal;
+			oldAbbrevVal = newAbbrevVal;
 			oldIsNull = *isNull;
 			haveOldVal = true;
 		}
@@ -1002,6 +1007,8 @@ process_ordered_aggregate_multi(AggState *aggstate,
 	TupleTableSlot *slot2 = pertrans->uniqslot;
 	int