From: Ronan Dunklau <ronan.dunklau@aiven.io>
To: David Rowley <dgrowleyml@gmail.com>
Cc: James Coleman <jtc331@gmail.com>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>,
 Ranier Vilela <ranier.vf@gmail.com>, Dilip Kumar <dilipbalaut@gmail.com>
Subject: Re: [PATCH] Use optimized single-datum tuplesort in ExecSort
Date: Mon, 12 Jul 2021 15:59:42 +0200
Message-ID: <6987360.ZhFIMvCLOo@aivenronan>
Organization: aiven
In-Reply-To: 
 <CAApHDvp3a5Kv=6D+uADGUWrcTRC_QL9ZbRMqRi7h+PVKy3mPMA@mail.gmail.com>
References: <3177670.itZtoPt7T5@aivenronan> <3060002.hb0XKQ11pn@aivenronan>
 <CAApHDvp3a5Kv=6D+uADGUWrcTRC_QL9ZbRMqRi7h+PVKy3mPMA@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/mixed; boundary="nextPart10617044.nNE7uE4vYN"
Content-Transfer-Encoding: 7Bit
Archived-At: 
 <https://www.postgresql.org/message-id/6987360.ZhFIMvCLOo%40aivenronan>
Precedence: bulk

This is a multi-part message in MIME format.

--nextPart10617044.nNE7uE4vYN
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain; charset="iso-8859-1"

Le lundi 12 juillet 2021, 15:11:17 CEST David Rowley a =E9crit :
> On Wed, 7 Jul 2021 at 21:32, Ronan Dunklau <ronan.dunklau@aiven.io> wrote:
> > In the meantime I fixed some formatting issues, please find attached a =
new
> > patch.
>=20
> I started to look at this.

Thank you ! I'm attaching a new version of the patch taking your remarks in=
to=20
account.
>=20
> First I wondered how often we might be able to apply this
> optimisation, so I ran make check after adding some elog(NOTICE) calls
> to output which method is going to be used just before we do the
> tuplestore_begin_* calls.  It looks like there are 614 instances of
> Datum sorts and 4223 of tuple sorts. That's about 14.5% datum sorts.
> 223 of the 614 are byval types and the other 391 are byref. Not that
> the regression tests are a good reflection of the real world, but if
> it were then that's quite a good number of cases to be able to
> optimise.

That's an interesting stat.

>=20
> As for the patch, just a few things:
>=20
> 1. Can you add the missing braces in this if condition and the else
> condition that belongs to it.
>=20
> + if (node->is_single_val)
> + for (;;)
> + {
>=20

Done.

> 2. I think it would nicer to name the new is_single_val field
> "datumSort" instead. To me it seems more clear what it is for.

Done.

>=20
> 3. This seems to be a bug fix where byval datum sorts do not properly
> handle bounded sorts.  I think that maybe that should be fixed and
> backpatched.  I don't see anything that says Datum sorts can't be
> bounded and if there were some restriction on that I'd expect
> tuplesort_set_bound() to fail when the Tuplesortstate had been set up
> with tuplesort_begin_datum().

I've kept this as-is for now, but I will remove it from my patch if it is=20
deemed worthy of back-patching in your other thread.=20

Regards,

=2D-=20
Ronan Dunklau
--nextPart10617044.nNE7uE4vYN
Content-Disposition: attachment;
 filename="v5-0001-Allow-Sort-nodes-to-use-the-fast-single-datum-tuples.patch"
Content-Transfer-Encoding: 7Bit
Content-Type: text/x-patch; charset="UTF-8";
 name="v5-0001-Allow-Sort-nodes-to-use-the-fast-single-datum-tuples.patch"

commit 91210952cf435995c9db6b539bf29f6fd744be70
Author: Ronan Dunklau <ronan.dunklau@aiven.io>
Date:   Tue Jul 6 16:34:31 2021 +0200

    Use optimized single-datum tuplesort in ExecSort
    
    Previously, with optimization was only done in ExecAgg.
    Doing this optimization on regular sort nodes provides for a nice
    performance improvement, when the input / output tuple has only one
    attribute.

diff --git a/src/backend/executor/nodeSort.c b/src/backend/executor/nodeSort.c
index b99027e0d7..df4e79c6ba 100644
--- a/src/backend/executor/nodeSort.c
+++ b/src/backend/executor/nodeSort.c
@@ -29,6 +29,10 @@
  *		which saves the results in a temporary file or memory. After the
  *		initial call, returns a tuple from the file with each call.
  *
+ *		The tuplesort can either occur on the whole tuple (this is the nominal
+ *		case) or, when the input / output tuple consists of only one attribute,
+ *		we switch to the tuplesort_*_datum API, optimized for that specific case.
+ *
  *		Conditions:
  *		  -- none.
  *
@@ -86,31 +90,64 @@ ExecSort(PlanState *pstate)
 		outerNode = outerPlanState(node);
 		tupDesc = ExecGetResultType(outerNode);
 
-		tuplesortstate = tuplesort_begin_heap(tupDesc,
-											  plannode->numCols,
-											  plannode->sortColIdx,
-											  plannode->sortOperators,
-											  plannode->collations,
-											  plannode->nullsFirst,
-											  work_mem,
-											  NULL,
-											  node->randomAccess);
+		/*
+		 * Switch to the tuplesort_*_datum interface when we have only one
+		 * key, as it is much more efficient especially when the type is
+		 * pass-by-value.
+		 */
+		if (tupDesc->natts == 1)
+		{
+			node->datumSort = true;
+			tuplesortstate = tuplesort_begin_datum(TupleDescAttr(tupDesc, 0)->atttypid,
+												   plannode->sortOperators[0],
+												   plannode->collations[0],
+												   plannode->nullsFirst[0],
+												   work_mem,
+												   NULL,
+												   node->randomAccess);
+		}
+		else
+			tuplesortstate = tuplesort_begin_heap(tupDesc,
+												  plannode->numCols,
+												  plannode->sortColIdx,
+												  plannode->sortOperators,
+												  plannode->collations,
+												  plannode->nullsFirst,
+												  work_mem,
+												  NULL,
+												  node->randomAccess);
 		if (node->bounded)
 			tuplesort_set_bound(tuplesortstate, node->bound);
 		node->tuplesortstate = (void *) tuplesortstate;
 
 		/*
-		 * Scan the subplan and feed all the tuples to tuplesort.
+		 * Scan the subplan and feed all the tuples to tuplesort, using either
+		 * the _putdatum or _puttupleslot API as appropriate.
 		 */
-
-		for (;;)
+		if (node->datumSort)
 		{
-			slot = ExecProcNode(outerNode);
-
-			if (TupIsNull(slot))
-				break;
-
-			tuplesort_puttupleslot(tuplesortstate, slot);
+			for (;;)
+			{
+				slot = ExecProcNode(outerNode);
+
+				if (TupIsNull(slot))
+					break;
+				slot_getsomeattrs(slot, 1);
+				tuplesort_putdatum(tuplesortstate,
+								   slot->tts_values[0],
+								   slot->tts_isnull[0]);
+			}
+		}
+		else
+		{
+			for (;;)
+			{
+				slot = ExecProcNode(outerNode);
+
+				if (TupIsNull(slot))
+					break;
+				tuplesort_puttupleslot(tuplesortstate, slot);
+			}
 		}
 
 		/*
@@ -150,9 +187,18 @@ ExecSort(PlanState *pstate)
 	 * next fetch from the tuplesort.
 	 */
 	slot = node->ss.ps.ps_ResultTupleSlot;
-	(void) tuplesort_gettupleslot(tuplesortstate,
-								  ScanDirectionIsForward(dir),
-								  false, slot, NULL);
+	if (node->datumSort)
+	{
+		ExecClearTuple(slot);
+		if (tuplesort_getdatum(tuplesortstate, ScanDirectionIsForward(dir),
+							   &(slot->tts_values[0]), &(slot->tts_isnull[0]), NULL))
+			ExecStoreVirtualTuple(slot);
+	}
+	else
+		(void) tuplesort_gettupleslot(tuplesortstate,
+									  ScanDirectionIsForward(dir),
+									  false, slot, NULL);
+
 	return slot;
 }
 
@@ -191,6 +237,7 @@ ExecInitSort(Sort *node, EState *estate, int eflags)
 	sortstate->bounded = false;
 	sortstate->sort_Done = false;
 	sortstate->tuplesortstate = NULL;
+	sortstate->datumSort = false;
 
 	/*
 	 * Miscellaneous initialization
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 22972071ff..f785259da7 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -4773,6 +4773,14 @@ leader_takeover_tapes(Tuplesortstate *state)
 static void
 free_sort_tuple(Tuplesortstate *state, SortTuple *stup)
 {
-	FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
-	pfree(stup->tuple);
+	/*
+	 * If the SortTuple is actually only a single Datum, which was not copied
+	 * as it is a byval type, do not try to free it nor account for it in
+	 * memory used.
+	 */
+	if (stup->tuple)
+	{
+		FREEMEM(state, GetMemoryChunkSpace(stup->tuple));
+		pfree(stup->tuple);
+	}
 }
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 0ec5509e7e..89f944a9c4 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2151,6 +2151,7 @@ typedef struct SortState
 	int64		bound_Done;		/* value of bound we did the sort with */
 	void	   *tuplesortstate; /* private state of tuplesort.c */
 	bool		am_worker;		/* are we a worker? */
+	bool		datumSort;  /* are we using the single value optimization ? */
 	SharedSortInfo *shared_info;	/* one entry per worker */
 } SortState;
 

--nextPart10617044.nNE7uE4vYN--