Replace inefficient _bt_invokestrat calls with direct calls to the

appropriate btree three-way comparison routine.  Not clear why the
three-way comparison routines were being used in some paths and not
others in btree --- incomplete changes by someone long ago, maybe?
Anyway, this makes for a nice speedup in CREATE INDEX.

7 files changed, 265 insertions, 287 deletions

diff --git a/src/backend/access/nbtree/nbtinsert.c b/src/backend/access/nbtree/nbtinsert.c
index a4153288dd7..463a0f00fe3 100644
--- a/src/backend/access/nbtree/nbtinsert.c
+++ b/src/backend/access/nbtree/nbtinsert.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.54 2000/01/26 05:55:58 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtinsert.c,v 1.55 2000/02/18 06:32:33 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -20,8 +20,11 @@
 
 
 static InsertIndexResult _bt_insertonpg(Relation rel, Buffer buf, BTStack stack, int keysz, ScanKey scankey, BTItem btitem, BTItem afteritem);
-static Buffer _bt_split(Relation rel, Buffer buf, OffsetNumber firstright);
-static OffsetNumber _bt_findsplitloc(Relation rel, Page page, OffsetNumber start, OffsetNumber maxoff, Size llimit);
+static Buffer _bt_split(Relation rel, Size keysz, ScanKey scankey,
+						Buffer buf, OffsetNumber firstright);
+static OffsetNumber _bt_findsplitloc(Relation rel, Size keysz, ScanKey scankey,
+									 Page page, OffsetNumber start,
+									 OffsetNumber maxoff, Size llimit);
 static void _bt_newroot(Relation rel, Buffer lbuf, Buffer rbuf);
 static OffsetNumber _bt_pgaddtup(Relation rel, Buffer buf, int keysz, ScanKey itup_scankey, Size itemsize, BTItem btitem, BTItem afteritem);
 static bool _bt_goesonpg(Relation rel, Buffer buf, Size keysz, ScanKey scankey, BTItem afteritem);
@@ -297,7 +300,7 @@ _bt_insertonpg(Relation rel,
 		hitemid = PageGetItemId(page, P_HIKEY);
 		hitem = (BTItem) PageGetItem(page, hitemid);
 		if (maxoff > P_HIKEY &&
-			!_bt_itemcmp(rel, keysz, hitem,
+			!_bt_itemcmp(rel, keysz, scankey, hitem,
 			 (BTItem) PageGetItem(page, PageGetItemId(page, P_FIRSTKEY)),
 						 BTEqualStrategyNumber))
 			elog(FATAL, "btree: bad key on the page in the chain of duplicates");
@@ -373,7 +376,8 @@ _bt_insertonpg(Relation rel,
 			{
 				itid = PageGetItemId(page, offnum);
 				chkitem = (BTItem) PageGetItem(page, itid);
-				if (!_bt_itemcmp(rel, keysz, previtem, chkitem,
+				if (!_bt_itemcmp(rel, keysz, scankey,
+								 previtem, chkitem,
 								 BTEqualStrategyNumber))
 				{
 					if (currsize > maxsize)
@@ -471,9 +475,10 @@ _bt_insertonpg(Relation rel,
 				MAXALIGN(sizeof(BTPageOpaqueData))
 				+sizeof(ItemIdData);
 			llimit /= 2;
-			firstright = _bt_findsplitloc(rel, page, start, maxoff, llimit);
+			firstright = _bt_findsplitloc(rel, keysz, scankey,
+										  page, start, maxoff, llimit);
 
-			if (_bt_itemcmp(rel, keysz,
+			if (_bt_itemcmp(rel, keysz, scankey,
 				  (BTItem) PageGetItem(page, PageGetItemId(page, start)),
 			 (BTItem) PageGetItem(page, PageGetItemId(page, firstright)),
 							BTEqualStrategyNumber))
@@ -503,7 +508,8 @@ _bt_insertonpg(Relation rel,
 						ItemPointerSet(&(stack->bts_btitem->bti_itup.t_tid),
 									   bknum, P_HIKEY);
 						pbuf = _bt_getstackbuf(rel, stack, BT_WRITE);
-						if (_bt_itemcmp(rel, keysz, stack->bts_btitem,
+						if (_bt_itemcmp(rel, keysz, scankey,
+										stack->bts_btitem,
 										(BTItem) PageGetItem(page,
 											 PageGetItemId(page, start)),
 										BTLessStrategyNumber))
@@ -519,7 +525,7 @@ _bt_insertonpg(Relation rel,
 		}
 
 		/* split the buffer into left and right halves */
-		rbuf = _bt_split(rel, buf, firstright);
+		rbuf = _bt_split(rel, keysz, scankey, buf, firstright);
 
 		/* which new page (left half or right half) gets the tuple? */
 		if (_bt_goesonpg(rel, buf, keysz, scankey, afteritem))
@@ -550,7 +556,7 @@ _bt_insertonpg(Relation rel,
 				elog(FATAL, "btree: un-shifted page is empty");
 			lowLeftItem = (BTItem) PageGetItem(page,
 										PageGetItemId(page, P_FIRSTKEY));
-			if (_bt_itemcmp(rel, keysz, lowLeftItem,
+			if (_bt_itemcmp(rel, keysz, scankey, lowLeftItem,
 				(BTItem) PageGetItem(page, PageGetItemId(page, P_HIKEY)),
 							BTEqualStrategyNumber))
 				lpageop->btpo_flags |= BTP_CHAIN;
@@ -613,7 +619,8 @@ l_spl:	;
 			{
 				ritem = (BTItem) PageGetItem(rpage,
 									   PageGetItemId(rpage, P_FIRSTKEY));
-				if (_bt_itemcmp(rel, keysz, ritem,
+				if (_bt_itemcmp(rel, keysz, scankey,
+								ritem,
 								(BTItem) PageGetItem(rpage,
 										  PageGetItemId(rpage, P_HIKEY)),
 								BTEqualStrategyNumber))
@@ -663,13 +670,16 @@ l_spl:	;
 			 * possible in splitting leftmost page) and current parent
 			 * item == new_item.		- vadim 05/27/97
 			 */
-			if (_bt_itemcmp(rel, keysz, stack->bts_btitem, new_item,
+			if (_bt_itemcmp(rel, keysz, scankey,
+							stack->bts_btitem, new_item,
 							BTGreaterStrategyNumber) ||
 				(!shifted &&
-				 _bt_itemcmp(rel, keysz, stack->bts_btitem,
-							 new_item, BTEqualStrategyNumber) &&
-				 _bt_itemcmp(rel, keysz, lowLeftItem,
-							 new_item, BTLessStrategyNumber)))
+				 _bt_itemcmp(rel, keysz, scankey,
+							 stack->bts_btitem, new_item,
+							 BTEqualStrategyNumber) &&
+				 _bt_itemcmp(rel, keysz, scankey,
+							 lowLeftItem, new_item,
+							 BTLessStrategyNumber)))
 			{
 				do_update = true;
 
@@ -831,7 +841,8 @@ l_spl:	;
  *		pin and lock on buf are maintained.
  */
 static Buffer
-_bt_split(Relation rel, Buffer buf, OffsetNumber firstright)
+_bt_split(Relation rel, Size keysz, ScanKey scankey,
+		  Buffer buf, OffsetNumber firstright)
 {
 	Buffer		rbuf;
 	Page		origpage;
@@ -915,7 +926,8 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright)
 	{
 		Size		llimit = PageGetFreeSpace(leftpage) / 2;
 
-		firstright = _bt_findsplitloc(rel, origpage, start, maxoff, llimit);
+		firstright = _bt_findsplitloc(rel, keysz, scankey,
+									  origpage, start, maxoff, llimit);
 	}
 
 	for (i = start; i <= maxoff; i = OffsetNumberNext(i))
@@ -1027,6 +1039,8 @@ _bt_split(Relation rel, Buffer buf, OffsetNumber firstright)
  */
 static OffsetNumber
 _bt_findsplitloc(Relation rel,
+				 Size keysz,
+				 ScanKey scankey,
 				 Page page,
 				 OffsetNumber start,
 				 OffsetNumber maxoff,
@@ -1039,12 +1053,10 @@ _bt_findsplitloc(Relation rel,
 	BTItem		safeitem,
 				nxtitem;
 	Size		nbytes;
-	int			natts;
 
 	if (start >= maxoff)
 		elog(FATAL, "btree: cannot split if start (%d) >= maxoff (%d)",
 			 start, maxoff);
-	natts = rel->rd_rel->relnatts;
 	saferight = start;
 	safeitemid = PageGetItemId(page, saferight);
 	nbytes = ItemIdGetLength(safeitemid) + sizeof(ItemIdData);
@@ -1064,7 +1076,7 @@ _bt_findsplitloc(Relation rel,
 		 * at isn't equal to the last safe one we saw, then it's our new
 		 * safe tuple.
 		 */
-		if (!_bt_itemcmp(rel, natts,
+		if (!_bt_itemcmp(rel, keysz, scankey,
 						 safeitem, nxtitem, BTEqualStrategyNumber))
 		{
 			safeitem = nxtitem;
@@ -1345,92 +1357,94 @@ _bt_goesonpg(Relation rel,
 }
 
 /*
- *		_bt_itemcmp() -- compare item1 to item2 using a requested
- *						 strategy (<, <=, =, >=, >)
+ *		_bt_tuplecompare() -- compare two IndexTuples,
+ *							  return -1, 0, or +1
  *
  */
-bool
-_bt_itemcmp(Relation rel,
-			Size keysz,
-			BTItem item1,
-			BTItem item2,
-			StrategyNumber strat)
+int32
+_bt_tuplecompare(Relation rel,
+				 Size keysz,
+				 ScanKey scankey,
+				 IndexTuple tuple1,
+				 IndexTuple tuple2)
 {
 	TupleDesc	tupDes;
-	IndexTuple	indexTuple1,
-				indexTuple2;
-	Datum		attrDatum1,
-				attrDatum2;
 	int			i;
-	bool		isFirstNull,
-				isSecondNull;
-	bool		compare;
-	bool		useEqual = false;
-
-	if (strat == BTLessEqualStrategyNumber)
-	{
-		useEqual = true;
-		strat = BTLessStrategyNumber;
-	}
-	else if (strat == BTGreaterEqualStrategyNumber)
-	{
-		useEqual = true;
-		strat = BTGreaterStrategyNumber;
-	}
+	int32		compare = 0;
 
 	tupDes = RelationGetDescr(rel);
-	indexTuple1 = &(item1->bti_itup);
-	indexTuple2 = &(item2->bti_itup);
 
 	for (i = 1; i <= keysz; i++)
 	{
-		attrDatum1 = index_getattr(indexTuple1, i, tupDes, &isFirstNull);
-		attrDatum2 = index_getattr(indexTuple2, i, tupDes, &isSecondNull);
+		ScanKey		entry = &scankey[i - 1];
+		Datum		attrDatum1,
+					attrDatum2;
+		bool		isFirstNull,
+					isSecondNull;
+
+		attrDatum1 = index_getattr(tuple1, i, tupDes, &isFirstNull);
+		attrDatum2 = index_getattr(tuple2, i, tupDes, &isSecondNull);
 
 		/* see comments about NULLs handling in btbuild */
-		if (isFirstNull)		/* attr in item1 is NULL */
+		if (isFirstNull)		/* attr in tuple1 is NULL */
 		{
-			if (isSecondNull)	/* attr in item2 is NULL too */
-				compare = (strat == BTEqualStrategyNumber) ? true : false;
+			if (isSecondNull)	/* attr in tuple2 is NULL too */
+				compare = 0;
 			else
-				compare = (strat == BTGreaterStrategyNumber) ? true : false;
+				compare = 1;	/* NULL ">" not-NULL */
 		}
-		else if (isSecondNull)	/* attr in item1 is NOT_NULL and */
-		{						/* and attr in item2 is NULL */
-			compare = (strat == BTLessStrategyNumber) ? true : false;
+		else if (isSecondNull)	/* attr in tuple1 is NOT_NULL and */
+		{						/* attr in tuple2 is NULL */
+			compare = -1;		/* not-NULL "<" NULL */
 		}
 		else
-			compare = _bt_invokestrat(rel, i, strat, attrDatum1, attrDatum2);
-
-		if (compare)			/* true for one of ">, <, =" */
 		{
-			if (strat != BTEqualStrategyNumber)
-				return true;
+			compare = (int32) FMGR_PTR2(&entry->sk_func,
+										attrDatum1, attrDatum2);
 		}
-		else
-/* false for one of ">, <, =" */
-		{
-			if (strat == BTEqualStrategyNumber)
-				return false;
 
-			/*
-			 * if original strat was "<=, >=" OR "<, >" but some
-			 * attribute(s) left - need to test for Equality
-			 */
-			if (useEqual || i < keysz)
-			{
-				if (isFirstNull || isSecondNull)
-					compare = (isFirstNull && isSecondNull) ? true : false;
-				else
-					compare = _bt_invokestrat(rel, i, BTEqualStrategyNumber,
-											  attrDatum1, attrDatum2);
-				if (compare)	/* item1' and item2' attributes are equal */
-					continue;	/* - try to compare next attributes */
-			}
-			return false;
-		}
+		if (compare != 0)
+			break;				/* done when we find unequal attributes */
 	}
-	return true;
+
+	return compare;
+}
+
+/*
+ *		_bt_itemcmp() -- compare two BTItems using a requested
+ *						 strategy (<, <=, =, >=, >)
+ *
+ */
+bool
+_bt_itemcmp(Relation rel,
+			Size keysz,
+			ScanKey scankey,
+			BTItem item1,
+			BTItem item2,
+			StrategyNumber strat)
+{
+	int32		compare;
+
+	compare = _bt_tuplecompare(rel, keysz, scankey,
+							   &(item1->bti_itup),
+							   &(item2->bti_itup));
+
+	switch (strat)
+	{
+		case BTLessStrategyNumber:
+			return (bool) (compare < 0);
+		case BTLessEqualStrategyNumber:
+			return (bool) (compare <= 0);
+		case BTEqualStrategyNumber:
+			return (bool) (compare == 0);
+		case BTGreaterEqualStrategyNumber:
+			return (bool) (compare >= 0);
+		case BTGreaterStrategyNumber:
+			return (bool) (compare > 0);
+	}
+
+	elog(ERROR, "_bt_itemcmp: bogus strategy %d", (int) strat);
+	return false;
 }
 
 /*
@@ -1585,7 +1599,7 @@ _bt_shift(Relation rel, Buffer buf, BTStack stack, int keysz,
 	/* init old page opaque */
 	pageop->btpo_flags = npageop->btpo_flags;	/* restore flags */
 	pageop->btpo_flags &= ~BTP_CHAIN;
-	if (_bt_itemcmp(rel, keysz, hikey, btitem, BTEqualStrategyNumber))
+	if (_bt_itemcmp(rel, keysz, scankey, hikey, btitem, BTEqualStrategyNumber))
 		pageop->btpo_flags |= BTP_CHAIN;
 	pageop->btpo_prev = npageop->btpo_prev;		/* restore prev */
 	pageop->btpo_next = nbknum; /* next points to the new page */
diff --git a/src/backend/access/nbtree/nbtsearch.c b/src/backend/access/nbtree/nbtsearch.c
index a22e042c1cf..99a172e46d8 100644
--- a/src/backend/access/nbtree/nbtsearch.c
+++ b/src/backend/access/nbtree/nbtsearch.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.56 2000/01/26 05:55:58 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsearch.c,v 1.57 2000/02/18 06:32:39 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -264,36 +264,21 @@ _bt_skeycmp(Relation rel,
 	BTItem		item;
 	IndexTuple	indexTuple;
 	TupleDesc	tupDes;
-	ScanKey		entry;
 	int			i;
-	Datum		attrDatum;
-	Datum		keyDatum;
-	bool		compare;
-	bool		isNull;
-	bool		useEqual = false;
-	bool		keyNull;
-
-	if (strat == BTLessEqualStrategyNumber)
-	{
-		useEqual = true;
-		strat = BTLessStrategyNumber;
-	}
-	else if (strat == BTGreaterEqualStrategyNumber)
-	{
-		useEqual = true;
-		strat = BTGreaterStrategyNumber;
-	}
+	int32		compare = 0;
 
 	item = (BTItem) PageGetItem(page, itemid);
 	indexTuple = &(item->bti_itup);
 
 	tupDes = RelationGetDescr(rel);
 
-	/* see if the comparison is true for all of the key attributes */
 	for (i = 1; i <= keysz; i++)
 	{
+		ScanKey		entry = &scankey[i - 1];
+		Datum		attrDatum;
+		bool		isNull;
+		Datum		keyDatum;
 
-		entry = &scankey[i - 1];
 		Assert(entry->sk_attno == i);
 		attrDatum = index_getattr(indexTuple,
 								  entry->sk_attno,
@@ -304,54 +289,40 @@ _bt_skeycmp(Relation rel,
 		/* see comments about NULLs handling in btbuild */
 		if (entry->sk_flags & SK_ISNULL)		/* key is NULL */
 		{
-			Assert(entry->sk_procedure == F_NULLVALUE);
-			keyNull = true;
 			if (isNull)
-				compare = (strat == BTEqualStrategyNumber) ? true : false;
+				compare = 0;	/* NULL key "=" NULL datum */
 			else
-				compare = (strat == BTGreaterStrategyNumber) ? true : false;
+				compare = 1;	/* NULL key ">" not-NULL datum */
 		}
 		else if (isNull)		/* key is NOT_NULL and item is NULL */
 		{
-			keyNull = false;
-			compare = (strat == BTLessStrategyNumber) ? true : false;
+			compare = -1;		/* not-NULL key "<" NULL datum */
 		}
 		else
 		{
-			keyNull = false;
-			compare = _bt_invokestrat(rel, i, strat, keyDatum, attrDatum);
+			compare = (int32) FMGR_PTR2(&entry->sk_func, keyDatum, attrDatum);
 		}
 
-		if (compare)			/* true for one of ">, <, =" */
-		{
-			if (strat != BTEqualStrategyNumber)
-				return true;
-		}
-		else
-/* false for one of ">, <, =" */
-		{
-			if (strat == BTEqualStrategyNumber)
-				return false;
+		if (compare != 0)
+			break;				/* done when we find unequal attributes */
+	}
 
-			/*
-			 * if original strat was "<=, >=" OR "<, >" but some
-			 * attribute(s) left - need to test for Equality
-			 */
-			if (useEqual || i < keysz)
-			{
-				if (keyNull || isNull)
-					compare = (keyNull && isNull) ? true : false;
-				else
-					compare = _bt_invokestrat(rel, i, BTEqualStrategyNumber,
-											  keyDatum, attrDatum);
-				if (compare)	/* key' and item' attributes are equal */
-					continue;	/* - try to compare next attributes */
-			}
-			return false;
-		}
+	switch (strat)
+	{
+		case BTLessStrategyNumber:
+			return (bool) (compare < 0);
+		case BTLessEqualStrategyNumber:
+			return (bool) (compare <= 0);
+		case BTEqualStrategyNumber:
+			return (bool) (compare == 0);
+		case BTGreaterEqualStrategyNumber:
+			return (bool) (compare >= 0);
+		case BTGreaterStrategyNumber:
+			return (bool) (compare > 0);
 	}
 
-	return true;
+	elog(ERROR, "_bt_skeycmp: bogus strategy %d", (int) strat);
+	return false;
 }
 
 /*
@@ -610,7 +581,6 @@ _bt_compare(Relation rel,
 		/* see comments about NULLs handling in btbuild */
 		if (entry->sk_flags & SK_ISNULL)		/* key is NULL */
 		{
-			Assert(entry->sk_procedure == F_NULLVALUE);
 			if (null)
 				tmpres = (long) 0;		/* NULL "=" NULL */
 			else
diff --git a/src/backend/access/nbtree/nbtsort.c b/src/backend/access/nbtree/nbtsort.c
index f92a626e178..f9cbf7121ff 100644
--- a/src/backend/access/nbtree/nbtsort.c
+++ b/src/backend/access/nbtree/nbtsort.c
@@ -28,7 +28,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.50 2000/01/26 05:55:59 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtsort.c,v 1.51 2000/02/18 06:32:39 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -69,12 +69,13 @@ struct BTSpool
 
 
 static void _bt_load(Relation index, BTSpool *btspool);
-static BTItem _bt_buildadd(Relation index, BTPageState *state, BTItem bti,
-						   int flags);
+static BTItem _bt_buildadd(Relation index, Size keysz, ScanKey scankey,
+						   BTPageState *state, BTItem bti, int flags);
 static BTItem _bt_minitem(Page opage, BlockNumber oblkno, int atend);
 static BTPageState *_bt_pagestate(Relation index, int flags,
 								  int level, bool doupper);
-static void _bt_uppershutdown(Relation index, BTPageState *state);
+static void _bt_uppershutdown(Relation index, Size keysz, ScanKey scankey,
+							  BTPageState *state);
 
 
 /*
@@ -282,7 +283,8 @@ _bt_minitem(Page opage, BlockNumber oblkno, int atend)
  * if all keys are unique, 'first' will always be the same as 'last'.
  */
 static BTItem
-_bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags)
+_bt_buildadd(Relation index, Size keysz, ScanKey scankey,
+			 BTPageState *state, BTItem bti, int flags)
 {
 	Buffer		nbuf;
 	Page		npage;
@@ -402,7 +404,7 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags)
 			nopaque->btpo_prev = BufferGetBlockNumber(obuf);
 			nopaque->btpo_next = P_NONE;
 
-			if (_bt_itemcmp(index, index->rd_att->natts,
+			if (_bt_itemcmp(index, keysz, scankey,
 			  (BTItem) PageGetItem(opage, PageGetItemId(opage, P_HIKEY)),
 			(BTItem) PageGetItem(opage, PageGetItemId(opage, P_FIRSTKEY)),
 							BTEqualStrategyNumber))
@@ -424,7 +426,7 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags)
 					_bt_pagestate(index, 0, state->btps_level + 1, true);
 			}
 			nbti = _bt_minitem(opage, BufferGetBlockNumber(obuf), 0);
-			_bt_buildadd(index, state->btps_next, nbti, 0);
+			_bt_buildadd(index, keysz, scankey, state->btps_next, nbti, 0);
 			pfree((void *) nbti);
 		}
 
@@ -454,7 +456,7 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags)
 #endif
 	if (last_bti == (BTItem) NULL)
 		first_off = P_FIRSTKEY;
-	else if (!_bt_itemcmp(index, index->rd_att->natts,
+	else if (!_bt_itemcmp(index, keysz, scankey,
 						  bti, last_bti, BTEqualStrategyNumber))
 		first_off = off;
 	last_off = off;
@@ -470,7 +472,8 @@ _bt_buildadd(Relation index, BTPageState *state, BTItem bti, int flags)
 }
 
 static void
-_bt_uppershutdown(Relation index, BTPageState *state)
+_bt_uppershutdown(Relation index, Size keysz, ScanKey scankey,
+				  BTPageState *state)
 {
 	BTPageState *s;
 	BlockNumber blkno;
@@ -499,7 +502,7 @@ _bt_uppershutdown(Relation index, BTPageState *state)
 			else
 			{
 				bti = _bt_minitem(s->btps_page, blkno, 0);
-				_bt_buildadd(index, s->btps_next, bti, 0);
+				_bt_buildadd(index, keysz, scankey, s->btps_next, bti, 0);
 				pfree((void *) bti);
 			}
 		}
@@ -521,6 +524,8 @@ static void
 _bt_load(Relation index, BTSpool *btspool)
 {
 	BTPageState *state;
+	ScanKey		skey;
+	int			natts;
 	BTItem		bti;
 	bool		should_free;
 
@@ -529,93 +534,21 @@ _bt_load(Relation index, BTSpool *btspool)
 	 */
 	state = _bt_pagestate(index, BTP_LEAF, 0, true);
 
+	skey = _bt_mkscankey_nodata(index);
+	natts = RelationGetNumberOfAttributes(index);
+
 	for (;;)
 	{
 		bti = (BTItem) tuplesort_getindextuple(btspool->sortstate, true,
 											   &should_free);
 		if (bti == (BTItem) NULL)
 			break;
-		_bt_buildadd(index, state, bti, BTP_LEAF);
+		_bt_buildadd(index, natts, skey, state, bti, BTP_LEAF);
 		if (should_free)
 			pfree((void *) bti);
 	}
 
-	_bt_uppershutdown(index, state);
-}
-
+	_bt_uppershutdown(index, natts, skey, state);
 
-/*
- * given the (appropriately side-linked) leaf pages of a btree,
- * construct the corresponding upper levels.  we do this by inserting
- * minimum keys from each page into parent pages as needed.  the
- * format of the internal pages is otherwise the same as for leaf
- * pages.
- *
- * this routine is not called during conventional bulk-loading (in
- * which case we can just build the upper levels as we create the
- * sorted bottom level).  it is only used for index recycling.
- */
-#ifdef NOT_USED
-void
-_bt_upperbuild(Relation index)
-{
-	Buffer		rbuf;
-	BlockNumber blk;
-	Page		rpage;
-	BTPageOpaque ropaque;
-	BTPageState *state;
-	BTItem		nbti;
-
-	/*
-	 * find the first leaf block.  while we're at it, clear the BTP_ROOT
-	 * flag that we set while building it (so we could find it later).
-	 */
-	rbuf = _bt_getroot(index, BT_WRITE);
-	blk = BufferGetBlockNumber(rbuf);
-	rpage = BufferGetPage(rbuf);
-	ropaque = (BTPageOpaque) PageGetSpecialPointer(rpage);
-	ropaque->btpo_flags &= ~BTP_ROOT;
-	_bt_wrtbuf(index, rbuf);
-
-	state = _bt_pagestate(index, 0, 0, true);
-
-	/* for each page... */
-	do
-	{
-#ifdef NOT_USED
-		printf("\t\tblk=%d\n", blk);
-#endif
-		rbuf = _bt_getbuf(index, blk, BT_READ);
-		rpage = BufferGetPage(rbuf);
-		ropaque = (BTPageOpaque) PageGetSpecialPointer(rpage);
-
-		/* for each item... */
-		if (!PageIsEmpty(rpage))
-		{
-
-			/*
-			 * form a new index tuple corresponding to the minimum key of
-			 * the lower page and insert it into a page at this level.
-			 */
-			nbti = _bt_minitem(rpage, blk, P_RIGHTMOST(ropaque));
-#ifdef FASTBUILD_DEBUG
-			{
-				bool		isnull;
-				Datum		d = index_getattr(&(nbti->bti_itup), 1, index->rd_att,
-											  &isnull);
-
-				printf("_bt_upperbuild: inserting <%x> at %d\n",
-					   d, state->btps_level);
-			}
-#endif
-			_bt_buildadd(index, state, nbti, 0);
-			pfree((void *) nbti);
-		}
-		blk = ropaque->btpo_next;
-		_bt_relbuf(index, rbuf, BT_READ);
-	} while (blk != P_NONE);
-
-	_bt_uppershutdown(index, state);
+	_bt_freeskey(skey);
 }
-
-#endif
diff --git a/src/backend/access/nbtree/nbtstrat.c b/src/backend/access/nbtree/nbtstrat.c
index 7fbf80dd445..57f33205fdb 100644
--- a/src/backend/access/nbtree/nbtstrat.c
+++ b/src/backend/access/nbtree/nbtstrat.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/Attic/nbtstrat.c,v 1.11 2000/01/26 05:55:59 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/Attic/nbtstrat.c,v 1.12 2000/02/18 06:32:39 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -118,6 +118,8 @@ _bt_getstrat(Relation rel,
 	return strat;
 }
 
+#ifdef NOT_USED
+
 bool
 _bt_invokestrat(Relation rel,
 				AttrNumber attno,
@@ -128,3 +130,5 @@ _bt_invokestrat(Relation rel,
 	return (RelationInvokeStrategy(rel, &BTEvaluationData, attno, strat,
 								   left, right));
 }
+
+#endif
diff --git a/src/backend/access/nbtree/nbtutils.c b/src/backend/access/nbtree/nbtutils.c
index 3d79384abdc..9d1cc7b10d0 100644
--- a/src/backend/access/nbtree/nbtutils.c
+++ b/src/backend/access/nbtree/nbtutils.c
@@ -8,7 +8,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.34 2000/01/26 05:55:59 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/access/nbtree/nbtutils.c,v 1.35 2000/02/18 06:32:39 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -23,7 +23,14 @@
 extern int	NIndexTupleProcessed;
 
 
-
+/*
+ * _bt_mkscankey
+ *		Build a scan key that contains comparison data from itup
+ *		as well as comparator routines appropriate to the key datatypes.
+ *
+ *		The result is intended for use with _bt_skeycmp() or _bt_compare(),
+ *		although it could be used with _bt_itemcmp() or _bt_tuplecompare().
+ */
 ScanKey
 _bt_mkscankey(Relation rel, IndexTuple itup)
 {
@@ -31,35 +38,67 @@ _bt_mkscankey(Relation rel, IndexTuple itup)
 	TupleDesc	itupdesc;
 	int			natts;
 	int			i;
-	Datum		arg;
 	RegProcedure proc;
+	Datum		arg;
 	bool		null;
 	bits16		flag;
 
-	natts = rel->rd_rel->relnatts;
 	itupdesc = RelationGetDescr(rel);
+	natts = RelationGetNumberOfAttributes(rel);
 
 	skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
 
 	for (i = 0; i < natts; i++)
 	{
+		proc = index_getprocid(rel, i + 1, BTORDER_PROC);
 		arg = index_getattr(itup, i + 1, itupdesc, &null);
-		if (null)
-		{
-			proc = F_NULLVALUE;
-			flag = SK_ISNULL;
-		}
-		else
-		{
-			proc = index_getprocid(rel, i + 1, BTORDER_PROC);
-			flag = 0x0;
-		}
-		ScanKeyEntryInitialize(&skey[i], flag, (AttrNumber) (i + 1), proc, arg);
+		flag = null ? SK_ISNULL : 0x0;
+		ScanKeyEntryInitialize(&skey[i],
+							   flag,
+							   (AttrNumber) (i + 1),
+							   proc,
+							   arg);
 	}
 
 	return skey;
 }
 
+/*
+ * _bt_mkscankey_nodata
+ *		Build a scan key that contains comparator routines appropriate to
+ *		the key datatypes, but no comparison data.
+ *
+ *		The result can be used with _bt_itemcmp() or _bt_tuplecompare(),
+ *		but not with _bt_skeycmp() or _bt_compare().
+ */
+ScanKey
+_bt_mkscankey_nodata(Relation rel)
+{
+	ScanKey		skey;
+	int			natts;
+	int			i;
+	RegProcedure proc;
+
+	natts = RelationGetNumberOfAttributes(rel);
+
+	skey = (ScanKey) palloc(natts * sizeof(ScanKeyData));
+
+	for (i = 0; i < natts; i++)
+	{
+		proc = index_getprocid(rel, i + 1, BTORDER_PROC);
+		ScanKeyEntryInitialize(&skey[i],
+							   SK_ISNULL,
+							   (AttrNumber) (i + 1),
+							   proc,
+							   (Datum) NULL);
+	}
+
+	return skey;
+}
+
+/*
+ * free a scan key made by either _bt_mkscankey or _bt_mkscankey_nodata.
+ */
 void
 _bt_freeskey(ScanKey skey)
 {
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 1d0ed4e9f2f..be80b246a2b 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -78,7 +78,7 @@
  * Portions Copyright (c) 1994, Regents of the University of California
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/utils/sort/tuplesort.c,v 1.5 2000/01/26 05:57:33 momjian Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/utils/sort/tuplesort.c,v 1.6 2000/02/18 06:32:30 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -253,6 +253,7 @@ struct Tuplesortstate
 	 * by tuplesort_begin_index and used only by the IndexTuple routines.
 	 */
 	Relation	indexRel;
+	ScanKey		indexScanKey;
 	bool		enforceUnique;	/* complain if we find duplicate tuples */
 
 	/*
@@ -476,6 +477,8 @@ tuplesort_begin_index(Relation indexRel,
 	state->tuplesize = tuplesize_index;
 
 	state->indexRel = indexRel;
+	/* see comments below about btree dependence of this code... */
+	state->indexScanKey = _bt_mkscankey_nodata(indexRel);
 	state->enforceUnique = enforceUnique;
 
 	return state;
@@ -1745,40 +1748,56 @@ tuplesize_heap(Tuplesortstate *state, void *tup)
 static int
 comparetup_index(Tuplesortstate *state, const void *a, const void *b)
 {
-	IndexTuple	ltup = (IndexTuple) a;
-	IndexTuple	rtup = (IndexTuple) b;
-	TupleDesc	itdesc = state->indexRel->rd_att;
-	bool		equal_isnull = false;
+	/*
+	 * This is almost the same as _bt_tuplecompare(), but we need to
+	 * keep track of whether any null fields are present.
+	 */
+	IndexTuple	tuple1 = (IndexTuple) a;
+	IndexTuple	tuple2 = (IndexTuple) b;
+	Relation	rel = state->indexRel;
+	Size		keysz = RelationGetNumberOfAttributes(rel);
+	ScanKey		scankey = state->indexScanKey;
+	TupleDesc	tupDes;
 	int			i;
+	bool		equal_hasnull = false;
 
-	for (i = 1; i <= itdesc->natts; i++)
-	{
-		Datum		lattr,
-					rattr;
-		bool		isnull1,
-					isnull2;
-
-		lattr = index_getattr(ltup, i, itdesc, &isnull1);
-		rattr = index_getattr(rtup, i, itdesc, &isnull2);
+	tupDes = RelationGetDescr(rel);
 
-		if (isnull1)
+	for (i = 1; i <= keysz; i++)
+	{
+		ScanKey		entry = &scankey[i - 1];
+		Datum		attrDatum1,
+					attrDatum2;
+		bool		isFirstNull,
+					isSecondNull;
+		int32		compare;
+
+		attrDatum1 = index_getattr(tuple1, i, tupDes, &isFirstNull);
+		attrDatum2 = index_getattr(tuple2, i, tupDes, &isSecondNull);
+
+		/* see comments about NULLs handling in btbuild */
+		if (isFirstNull)		/* attr in tuple1 is NULL */
 		{
-			if (!isnull2)
-				return 1;		/* NULL sorts after non-NULL */
-			equal_isnull = true;
-			continue;
+			if (isSecondNull)	/* attr in tuple2 is NULL too */
+			{
+				compare = 0;
+				equal_hasnull = true;
+			}
+			else
+				compare = 1;	/* NULL ">" not-NULL */
+		}
+		else if (isSecondNull)	/* attr in tuple1 is NOT_NULL and */
+		{						/* attr in tuple2 is NULL */
+			compare = -1;		/* not-NULL "<" NULL */
+		}
+		else
+		{
+			compare = (int32) FMGR_PTR2(&entry->sk_func,
+										attrDatum1, attrDatum2);
 		}
-		else if (isnull2)
-			return -1;
 
-		if (_bt_invokestrat(state->indexRel, i,
-							BTGreaterStrategyNumber,
-							lattr, rattr))
-			return 1;
-		if (_bt_invokestrat(state->indexRel, i,
-							BTGreaterStrategyNumber,
-							rattr, lattr))
-			return -1;
+		if (compare != 0)
+			return (int) compare; /* done when we find unequal attributes */
 	}
 
 	/*
@@ -1790,7 +1809,7 @@ comparetup_index(Tuplesortstate *state, const void *a, const void *b)
 	 * the sort algorithm wouldn't have checked whether one must appear
 	 * before the other.
 	 */
-	if (state->enforceUnique && !equal_isnull)
+	if (state->enforceUnique && !equal_hasnull)
 		elog(ERROR, "Cannot create unique index. Table contains non-unique values");
 
 	return 0;
diff --git a/src/include/access/nbtree.h b/src/include/access/nbtree.h
index 486d193622f..7262402dcb9 100644
--- a/src/include/access/nbtree.h
+++ b/src/include/access/nbtree.h
@@ -7,7 +7,7 @@
  * Portions Copyright (c) 1996-2000, PostgreSQL, Inc
  * Portions Copyright (c) 1994, Regents of the University of California
  *
- * $Id: nbtree.h,v 1.33 2000/01/26 05:57:50 momjian Exp $
+ * $Id: nbtree.h,v 1.34 2000/02/18 06:32:28 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -204,11 +204,11 @@ typedef struct BTPageState
  * prototypes for functions in nbtinsert.c
  */
 extern InsertIndexResult _bt_doinsert(Relation rel, BTItem btitem,
-			 bool index_is_unique, Relation heapRel);
-
- /* default is to allow duplicates */
-extern bool _bt_itemcmp(Relation rel, Size keysz, BTItem item1, BTItem item2,
-			StrategyNumber strat);
+									  bool index_is_unique, Relation heapRel);
+extern int32 _bt_tuplecompare(Relation rel, Size keysz, ScanKey scankey,
+							  IndexTuple tuple1, IndexTuple tuple2);
+extern bool _bt_itemcmp(Relation rel, Size keysz, ScanKey scankey,
+						BTItem item1, BTItem item2, StrategyNumber strat);
 
 /*
  * prototypes for functions in nbtpage.c
@@ -272,14 +272,13 @@ extern bool _bt_step(IndexScanDesc scan, Buffer *bufP, ScanDirection dir);
  * prototypes for functions in nbtstrat.c
  */
 extern StrategyNumber _bt_getstrat(Relation rel, AttrNumber attno,
-			 RegProcedure proc);
-extern bool _bt_invokestrat(Relation rel, AttrNumber attno,
-				StrategyNumber strat, Datum left, Datum right);
+								   RegProcedure proc);
 
 /*
  * prototypes for functions in nbtutils.c
  */
 extern ScanKey _bt_mkscankey(Relation rel, IndexTuple itup);
+extern ScanKey _bt_mkscankey_nodata(Relation rel);
 extern void _bt_freeskey(ScanKey skey);
 extern void _bt_freestack(BTStack stack);
 extern void _bt_orderkeys(Relation relation, BTScanOpaque so);