Date: Sun, 2 Oct 2005 21:38:43 +0200
From: Martijn van Oosterhout <kleptog@svana.org>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Ron Peacetree <rjpeace@earthlink.net>,
	pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] A Better External Sort?
Message-ID: <20051002193835.GJ30492@svana.org>
Reply-To: Martijn van Oosterhout <kleptog@svana.org>
References: 
 <18329659.1128188552696.JavaMail.root@elwamui-polski.atl.sa.earthlink.net>
	<20051001215602.GG13830@svana.org> <29837.1128223567@sss.pgh.pa.us>
	<20051002123240.GA30492@svana.org>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="opg8F0UgoHELSI+9"
Content-Disposition: inline
In-Reply-To: <20051002123240.GA30492@svana.org>
User-Agent: Mutt/1.3.28i


--opg8F0UgoHELSI+9
Content-Type: multipart/mixed; boundary="4vpci17Ql0Nrbul2"
Content-Disposition: inline


--4vpci17Ql0Nrbul2
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

Ok, I tried two optimisations:

1. By creating a special version of comparetup_index for single key
integer indexes. Create an index_get_attr with byval and len args. By
using fetch_att and specifying the values at compile time, gcc
optimises the whole call to about 12 instructions of assembly rather
than the usual mess.

2. By specifying: -Winline -finline-limit-1500 (only on tuplesort.c).
This causes inlineApplySortFunction() to be inlined, like the code
obviously expects it to be.

default build (baseline)                    235 seconds
-finline only                               217 seconds (7% better)
comparetup_index_fastbyval4 only            221 seconds (6% better)
comparetup_index_fastbyval4 and -finline    203 seconds (13.5% better)

This is indexing the integer sequence column on a 2.7 million row
table. The times are as given by gprof and so exclude system call time.

Basically, I recommend adding "-Winline -finline-limit-1500" to the
default build while we discuss other options.

comparetup_index_fastbyval4 patch attached per example.
--=20
Martijn van Oosterhout   <kleptog@svana.org>   http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

--4vpci17Ql0Nrbul2
Content-Type: text/plain; charset=us-ascii
Content-Disposition: attachment; filename="fastindex.patch"
Content-Transfer-Encoding: quoted-printable

--- pgsql-clean/src/include/access/itup.h	2005-10-02 21:30:20.327464320 +02=
00
+++ pgsql-sort/src/include/access/itup.h	2005-10-02 16:04:00.000000000 +0200
@@ -126,6 +126,34 @@
 	) \
 )
=20
+#define index_get_attr(tup, attnum, tupleDesc, attbyval, attlen, isnull) \
+( \
+	AssertMacro(PointerIsValid(isnull) && (attnum) > 0), \
+	*(isnull) =3D false, \
+	!IndexTupleHasNulls(tup) ? \
+	( \
+		(tupleDesc)->attrs[(attnum)-1]->attcacheoff >=3D 0 ? \
+		( \
+			fetch_att((char *) (tup) + IndexInfoFindDataOffset((tup)->t_info) \
+				+ (tupleDesc)->attrs[(attnum)-1]->attcacheoff, attbyval, attlen) \
+		) \
+		: \
+			nocache_index_getattr((tup), (attnum), (tupleDesc), (isnull)) \
+	) \
+	: \
+	( \
+		(att_isnull((attnum)-1, (char *)(tup) + sizeof(IndexTupleData))) ? \
+		( \
+			*(isnull) =3D true, \
+			(Datum)NULL \
+		) \
+		: \
+		( \
+			nocache_index_getattr((tup), (attnum), (tupleDesc), (isnull)) \
+		) \
+	) \
+)
+
=20
 /* routines in indextuple.c */
 extern IndexTuple index_form_tuple(TupleDesc tupleDescriptor,
--- pgsql-clean/src/backend/utils/sort/tuplesort.c	2005-09-24 23:23:39.0000=
00000 +0200
+++ pgsql-sort/src/backend/utils/sort/tuplesort.c	2005-10-02 21:29:39.34908=
6302 +0200
@@ -375,6 +375,8 @@
 			 unsigned int len);
 static int comparetup_index(Tuplesortstate *state,
 				 const void *a, const void *b);
+static int comparetup_index_fastbyval4(Tuplesortstate *state,
+				 const void *a, const void *b);
 static void *copytup_index(Tuplesortstate *state, void *tup);
 static void writetup_index(Tuplesortstate *state, int tapenum, void *tup);
 static void *readtup_index(Tuplesortstate *state, int tapenum,
@@ -498,8 +500,12 @@
 					  int workMem, bool randomAccess)
 {
 	Tuplesortstate *state =3D tuplesort_begin_common(workMem, randomAccess);
+	TupleDesc	tupDes =3D RelationGetDescr(indexRel);
=20
-	state->comparetup =3D comparetup_index;
+	if( tupDes->natts =3D=3D 1 && tupDes->attrs[0]->attbyval =3D=3D 1 && tupD=
es->attrs[0]->attlen =3D=3D 4 )
+		state->comparetup =3D comparetup_index_fastbyval4;
+	else
+		state->comparetup =3D comparetup_index;
 	state->copytup =3D copytup_index;
 	state->writetup =3D writetup_index;
 	state->readtup =3D readtup_index;
@@ -2102,6 +2108,92 @@
 	return 0;
 }
=20
+static int
+comparetup_index_fastbyval4(Tuplesortstate *state, const void *a, const vo=
id *b)
+{
+	/*
+	 * This is almost the same as _bt_tuplecompare(), but we need to keep
+	 * track of whether any null fields are present.  Also see the special
+	 * treatment for equal keys at the end.
+	 */
+	IndexTuple	tuple1 =3D (IndexTuple) a;
+	IndexTuple	tuple2 =3D (IndexTuple) b;
+	Relation	rel =3D state->indexRel;
+	ScanKey		scankey =3D state->indexScanKey;
+	TupleDesc	tupDes;
+	bool		equal_hasnull =3D false;
+
+	tupDes =3D RelationGetDescr(rel);
+
+	ScanKey		entry =3D &scankey[0];
+	Datum		datum1,
+					datum2;
+	bool		isnull1,
+					isnull2;
+	int32		compare;
+
+	datum1 =3D index_get_attr(tuple1, 1, tupDes, 1, 4, &isnull1);
+	datum2 =3D index_get_attr(tuple2, 1, tupDes, 1, 4, &isnull2);
+
+	/* see comments about NULLs handling in btbuild */
+
+	/* the comparison function is always of CMP type */
+	compare =3D inlineApplySortFunction(&entry->sk_func, SORTFUNC_CMP,
+									  datum1, isnull1,
+									  datum2, isnull2);
+
+	if (compare !=3D 0)
+		return (int) compare;		/* done when we find unequal
+										 * attributes */
+
+	/* they are equal, so we only need to examine one null flag */
+	if (isnull1)
+		equal_hasnull =3D true;
+
+	/*
+	 * If btree has asked us to enforce uniqueness, complain if two equal
+	 * tuples are detected (unless there was at least one NULL field).
+	 *
+	 * It is sufficient to make the test here, because if two tuples are
+	 * equal they *must* get compared at some stage of the sort ---
+	 * otherwise the sort algorithm wouldn't have checked whether one must
+	 * appear before the other.
+	 *
+	 * Some rather brain-dead implementations of qsort will sometimes call
+	 * the comparison routine to compare a value to itself.  (At this
+	 * writing only QNX 4 is known to do such silly things.)  Don't raise
+	 * a bogus error in that case.
+	 */
+	if (state->enforceUnique && !equal_hasnull && tuple1 !=3D tuple2)
+		ereport(ERROR,
+				(errcode(ERRCODE_UNIQUE_VIOLATION),
+				 errmsg("could not create unique index"),
+				 errdetail("Table contains duplicated values.")));
+
+	/*
+	 * If key values are equal, we sort on ItemPointer.  This does not
+	 * affect validity of the finished index, but it offers cheap
+	 * insurance against performance problems with bad qsort
+	 * implementations that have trouble with large numbers of equal keys.
+	 */
+	{
+		BlockNumber blk1 =3D ItemPointerGetBlockNumber(&tuple1->t_tid);
+		BlockNumber blk2 =3D ItemPointerGetBlockNumber(&tuple2->t_tid);
+
+		if (blk1 !=3D blk2)
+			return (blk1 < blk2) ? -1 : 1;
+	}
+	{
+		OffsetNumber pos1 =3D ItemPointerGetOffsetNumber(&tuple1->t_tid);
+		OffsetNumber pos2 =3D ItemPointerGetOffsetNumber(&tuple2->t_tid);
+
+		if (pos1 !=3D pos2)
+			return (pos1 < pos2) ? -1 : 1;
+	}
+
+	return 0;
+}
+
 static void *
 copytup_index(Tuplesortstate *state, void *tup)
 {

--4vpci17Ql0Nrbul2--

--opg8F0UgoHELSI+9
Content-Type: application/pgp-signature
Content-Disposition: inline

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFDQDc6IB7bNG8LQkwRAskpAJ4oX70LIkeobYjuwjbz/pqwCHfxUACgijKl
vxCH8Kf9KpoKYYQecGqdtpg=
=M3LE
-----END PGP SIGNATURE-----

--opg8F0UgoHELSI+9--