Index: src/backend/utils/sort/tuplesort.c
===================================================================
RCS file: /projects/cvsroot/pgsql/src/backend/utils/sort/tuplesort.c,v
retrieving revision 1.57
diff -c -r1.57 tuplesort.c
*** src/backend/utils/sort/tuplesort.c	5 Jan 2006 01:56:29 -0000	1.57
--- src/backend/utils/sort/tuplesort.c	25 Jan 2006 23:53:31 -0000
***************
*** 120,130 ****
  } TupSortStatus;
  
  /*
!  * We use a seven-tape polyphase merge, which is the "sweet spot" on the
!  * tapes-to-passes curve according to Knuth's figure 70 (section 5.4.2).
   */
! #define MAXTAPES		7		/* Knuth's T */
! #define TAPERANGE		(MAXTAPES-1)	/* Knuth's P */
  
  /*
   * Private state of a Tuplesort operation.
--- 120,186 ----
  } TupSortStatus;
  
  /*
!  * Knuth's results suggest that a seven-tape polyphase merge is the 
!  * "sweet spot" on the tapes-to-passes curve according to Knuth's 
!  * figure 70 (section 5.4.2). Prior to 8.2 we always used 7 logical tapes.
!  * From 8.2, if we have sufficient memory, we use more logical tapes
!  * because this reduces the cost of additional merge passes. But we must
!  * keep a reasonably sized preread buffer for each tape, or we lose the
!  * performance gains from sequential disk I/O (readahead). So there is an
!  * optimal merge buffer size reflecting the trade-off between these two 
!  * issues. 
!  *
!  * If we have fewer runs than we have tapes we can avoid merging
!  * runs altogether and move directly to the final merge. In this case, we
!  * can take advantage of a larger preread buffer. We also note that the
!  * wasted memory from unused Tapestates is unlikely to have negative 
!  * performance effects, so we do not need fully dynamic tape allocation.
!  * So we calculate NumTapes = MaxTapes at start, with MaxTapes >= MINTAPES
!  *
!  * The size of the Tapestate array is assumed to be small in comparison
!  * with the tuplearrays, so this is not tracked, just as in pre-8.2
!  * releases.
!  */
! int MaxTapes;		/* Knuth's T */
! int TapeRange;		/* Knuth's P */
! #define MINTAPES    7
! #define OPTIMAL_MERGE_BUFFER_SIZE   (BLCKSZ * 32)
! /*
!  * Private state of a one logical tape in an external Tuplesort operation
   */
! typedef struct Tapestate
! {
! 	/*
! 	 * These variables are only used during merge passes.  mergeactive[i] is
! 	 * true if we are reading an input run from (actual) tape number i and
! 	 * have not yet exhausted that run.  mergenext[i] is the memtuples index
! 	 * of the next pre-read tuple (next to be loaded into the heap) for tape
! 	 * i, or 0 if we are out of pre-read tuples.  mergelast[i] similarly
! 	 * points to the last pre-read tuple from each tape. mergeavailmem[i] is
! 	 * the amount of unused space allocated for tape i. mergefreelist and
! 	 * mergefirstfree keep track of unused locations in the memtuples[] array.
! 	 * memtupindex[] links together pre-read tuples for each tape as well as
! 	 * recycled locations in mergefreelist. It is OK to use 0 as a null link
! 	 * in these lists, because memtuples[0] is part of the merge heap and is
! 	 * never a pre-read tuple.
! 	 */
! 	bool		mergeactive;	      /* Active input run source? */
! 	int			mergenext;	          /* first preread tuple for each source */
! 	int			mergelast;	          /* last preread tuple for each source */
! 	long		mergeavailmem;	      /* availMem for prereading tapes */
! 
! 	/*
! 	 * Variables for Algorithm D.  The index into these arrays is a logical
!      * tape number. Be careful to keep "logical" and "actual" tape numbers 
!      * straight!
! 	 */
! 	int			tp_fib;      	      /* Target Fibonacci run counts (A[]) */
! 	int			tp_runs;         	  /* # of real runs on each tape */
! 	int			tp_dummy;        	  /* # of dummy runs for each tape (D[]) */
! 	int			tp_tapenum;           /* Actual tape numbers (TAPE[]) */
! } TapeStateData;
! 
! typedef TapeStateData *Tapestate;
  
  /*
   * Private state of a Tuplesort operation.
***************
*** 179,185 ****
  	 * SORTEDINMEM, the tuples are in final sorted order; in states BUILDRUNS
  	 * and FINALMERGE, the tuples are organized in "heap" order per Algorithm
  	 * H.  (Note that memtupcount only counts the tuples that are part of the
! 	 * heap --- during merge passes, memtuples[] entries beyond TAPERANGE are
  	 * never in the heap and are used to hold pre-read tuples.)  In state
  	 * SORTEDONTAPE, the array is not used.
  	 */
--- 235,241 ----
  	 * SORTEDINMEM, the tuples are in final sorted order; in states BUILDRUNS
  	 * and FINALMERGE, the tuples are organized in "heap" order per Algorithm
  	 * H.  (Note that memtupcount only counts the tuples that are part of the
! 	 * heap --- during merge passes, memtuples[] entries beyond TapeRange are
  	 * never in the heap and are used to hold pre-read tuples.)  In state
  	 * SORTEDONTAPE, the array is not used.
  	 */
***************
*** 205,243 ****
  	int			currentRun;
  
  	/*
! 	 * These variables are only used during merge passes.  mergeactive[i] is
! 	 * true if we are reading an input run from (actual) tape number i and
! 	 * have not yet exhausted that run.  mergenext[i] is the memtuples index
! 	 * of the next pre-read tuple (next to be loaded into the heap) for tape
! 	 * i, or 0 if we are out of pre-read tuples.  mergelast[i] similarly
! 	 * points to the last pre-read tuple from each tape. mergeavailmem[i] is
! 	 * the amount of unused space allocated for tape i. mergefreelist and
! 	 * mergefirstfree keep track of unused locations in the memtuples[] array.
! 	 * memtupindex[] links together pre-read tuples for each tape as well as
! 	 * recycled locations in mergefreelist. It is OK to use 0 as a null link
! 	 * in these lists, because memtuples[0] is part of the merge heap and is
! 	 * never a pre-read tuple.
! 	 */
! 	bool		mergeactive[MAXTAPES];	/* Active input run source? */
! 	int			mergenext[MAXTAPES];	/* first preread tuple for each source */
! 	int			mergelast[MAXTAPES];	/* last preread tuple for each source */
! 	long		mergeavailmem[MAXTAPES];		/* availMem for prereading
! 												 * tapes */
  	long		spacePerTape;	/* actual per-tape target usage */
  	int			mergefreelist;	/* head of freelist of recycled slots */
  	int			mergefirstfree; /* first slot never used in this merge */
  
  	/*
  	 * Variables for Algorithm D.  Note that destTape is a "logical" tape
! 	 * number, ie, an index into the tp_xxx[] arrays.  Be careful to keep
  	 * "logical" and "actual" tape numbers straight!
  	 */
  	int			Level;			/* Knuth's l */
  	int			destTape;		/* current output tape (Knuth's j, less 1) */
- 	int			tp_fib[MAXTAPES];		/* Target Fibonacci run counts (A[]) */
- 	int			tp_runs[MAXTAPES];		/* # of real runs on each tape */
- 	int			tp_dummy[MAXTAPES];		/* # of dummy runs for each tape (D[]) */
- 	int			tp_tapenum[MAXTAPES];	/* Actual tape numbers (TAPE[]) */
  
  	/*
  	 * These variables are used after completion of sorting to keep track of
--- 261,281 ----
  	int			currentRun;
  
  	/*
! 	 * These variables are only used during merge passes
!      */
!     Tapestate  *logtapes;       /* array of pointers to palloc'd tapes */
  	long		spacePerTape;	/* actual per-tape target usage */
  	int			mergefreelist;	/* head of freelist of recycled slots */
  	int			mergefirstfree; /* first slot never used in this merge */
  
+ 
  	/*
  	 * Variables for Algorithm D.  Note that destTape is a "logical" tape
! 	 * number, ie, an index into the Tapesortstate arrays.  Be careful to keep
  	 * "logical" and "actual" tape numbers straight!
  	 */
  	int			Level;			/* Knuth's l */
  	int			destTape;		/* current output tape (Knuth's j, less 1) */
  
  	/*
  	 * These variables are used after completion of sorting to keep track of
***************
*** 972,980 ****
  				/* returned tuple is no longer counted in our memory space */
  				tuplen = GetMemoryChunkSpace(tup);
  				state->availMem += tuplen;
! 				state->mergeavailmem[srcTape] += tuplen;
  				tuplesort_heap_siftup(state, false);
! 				if ((tupIndex = state->mergenext[srcTape]) == 0)
  				{
  					/*
  					 * out of preloaded data on this tape, try to read more
--- 1010,1018 ----
  				/* returned tuple is no longer counted in our memory space */
  				tuplen = GetMemoryChunkSpace(tup);
  				state->availMem += tuplen;
! 				state->logtapes[srcTape]->mergeavailmem += tuplen;
  				tuplesort_heap_siftup(state, false);
! 				if ((tupIndex = state->logtapes[srcTape]->mergenext) == 0)
  				{
  					/*
  					 * out of preloaded data on this tape, try to read more
***************
*** 984,997 ****
  					/*
  					 * if still no data, we've reached end of run on this tape
  					 */
! 					if ((tupIndex = state->mergenext[srcTape]) == 0)
  						return tup;
  				}
  				/* pull next preread tuple from list, insert in heap */
  				newtup = state->memtuples[tupIndex];
! 				state->mergenext[srcTape] = state->memtupindex[tupIndex];
! 				if (state->mergenext[srcTape] == 0)
! 					state->mergelast[srcTape] = 0;
  				state->memtupindex[tupIndex] = state->mergefreelist;
  				state->mergefreelist = tupIndex;
  				tuplesort_heap_insert(state, newtup, srcTape, false);
--- 1022,1035 ----
  					/*
  					 * if still no data, we've reached end of run on this tape
  					 */
! 					if ((tupIndex = state->logtapes[srcTape]->mergenext) == 0)
  						return tup;
  				}
  				/* pull next preread tuple from list, insert in heap */
  				newtup = state->memtuples[tupIndex];
! 				state->logtapes[srcTape]->mergenext = state->memtupindex[tupIndex];
! 				if (state->logtapes[srcTape]->mergenext == 0)
! 					state->logtapes[srcTape]->mergelast = 0;
  				state->memtupindex[tupIndex] = state->mergefreelist;
  				state->mergefreelist = tupIndex;
  				tuplesort_heap_insert(state, newtup, srcTape, false);
***************
*** 1053,1065 ****
  	int			ntuples,
  				j;
  
  #ifdef TRACE_SORT
  	if (trace_sort)
! 		elog(LOG, "switching to external sort: %s",
  			 pg_rusage_show(&state->ru_start));
  #endif
  
! 	state->tapeset = LogicalTapeSetCreate(MAXTAPES);
  
  	/*
  	 * Allocate the memtupindex array, same size as memtuples.
--- 1091,1129 ----
  	int			ntuples,
  				j;
  
+     /* 
+      * Calculate number of tapes based on memory limits. We need to have
+      * MaxTapes to be at least MINTAPES. It can be set higher than this to
+      * reduce the number of merge passes, but we must allow a large enough
+      * memory buffer for each tape to maximise the effects of sequential
+      * I/O during the merge phase
+      */
+     MaxTapes = (int) state->allowedMem / OPTIMAL_MERGE_BUFFER_SIZE;
+     if (MaxTapes < MINTAPES)
+     {
+         MaxTapes = MINTAPES;
+     }
+     TapeRange = MaxTapes - 1;
+ 
  #ifdef TRACE_SORT
  	if (trace_sort)
! 		elog(LOG, "switching to external sort: (ntapes=%u) %s", MaxTapes,
  			 pg_rusage_show(&state->ru_start));
  #endif
  
!     /*
!      * Allocate the Tapestate array
!      */
! 	state->logtapes = (Tapestate *) palloc0(MaxTapes * sizeof(Tapestate));
!     /*
!      * Allocate a fixed number of tapes, rather than dynamic allocation
!      */
! 	for (j = 0; j < MaxTapes; j++)
! 	{
!         state->logtapes[j] = (Tapestate) palloc0(sizeof(TapeStateData));
!     }
! 
! 	state->tapeset = LogicalTapeSetCreate(MaxTapes);
  
  	/*
  	 * Allocate the memtupindex array, same size as memtuples.
***************
*** 1087,1101 ****
  	/*
  	 * Initialize variables of Algorithm D (step D1).
  	 */
! 	for (j = 0; j < MAXTAPES; j++)
  	{
! 		state->tp_fib[j] = 1;
! 		state->tp_runs[j] = 0;
! 		state->tp_dummy[j] = 1;
! 		state->tp_tapenum[j] = j;
  	}
! 	state->tp_fib[TAPERANGE] = 0;
! 	state->tp_dummy[TAPERANGE] = 0;
  
  	state->Level = 1;
  	state->destTape = 0;
--- 1151,1165 ----
  	/*
  	 * Initialize variables of Algorithm D (step D1).
  	 */
! 	for (j = 0; j < MaxTapes; j++)
  	{
! 		state->logtapes[j]->tp_fib = 1;
! 		state->logtapes[j]->tp_runs = 0;
! 		state->logtapes[j]->tp_dummy = 1;
! 		state->logtapes[j]->tp_tapenum = j;
  	}
! 	state->logtapes[TapeRange]->tp_fib = 0;
! 	state->logtapes[TapeRange]->tp_dummy = 0;
  
  	state->Level = 1;
  	state->destTape = 0;
***************
*** 1115,1127 ****
  	int			j;
  	int			a;
  
  	/* Step D3: advance j (destTape) */
! 	if (state->tp_dummy[state->destTape] < state->tp_dummy[state->destTape + 1])
  	{
  		state->destTape++;
  		return;
  	}
! 	if (state->tp_dummy[state->destTape] != 0)
  	{
  		state->destTape = 0;
  		return;
--- 1179,1195 ----
  	int			j;
  	int			a;
  
+     /* 
+      * If we use dynamically allocated Tapestates then allocate them here
+      */
+ 
  	/* Step D3: advance j (destTape) */
!     if (state->logtapes[state->destTape]->tp_dummy < state->logtapes[state->destTape + 1]->tp_dummy)
  	{
  		state->destTape++;
  		return;
  	}
! 	if (state->logtapes[state->destTape]->tp_dummy != 0)
  	{
  		state->destTape = 0;
  		return;
***************
*** 1129,1139 ****
  
  	/* Step D4: increase level */
  	state->Level++;
! 	a = state->tp_fib[0];
! 	for (j = 0; j < TAPERANGE; j++)
  	{
! 		state->tp_dummy[j] = a + state->tp_fib[j + 1] - state->tp_fib[j];
! 		state->tp_fib[j] = a + state->tp_fib[j + 1];
  	}
  	state->destTape = 0;
  }
--- 1197,1207 ----
  
  	/* Step D4: increase level */
  	state->Level++;
! 	a = state->logtapes[0]->tp_fib;
! 	for (j = 0; j < TapeRange; j++)
  	{
! 		state->logtapes[j]->tp_dummy = a + state->logtapes[j + 1]->tp_fib - state->logtapes[j]->tp_fib;
! 		state->logtapes[j]->tp_fib = a + state->logtapes[j + 1]->tp_fib;
  	}
  	state->destTape = 0;
  }
***************
*** 1162,1168 ****
  	 */
  	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;
--- 1230,1236 ----
  	 */
  	if (state->currentRun == 1)
  	{
! 		state->result_tape = state->logtapes[state->destTape]->tp_tapenum;
  		/* must freeze and rewind the finished output tape */
  		LogicalTapeFreeze(state->tapeset, state->result_tape);
  		state->status = TSS_SORTEDONTAPE;
***************
*** 1170,1191 ****
  	}
  
  	/* End of step D2: rewind all output tapes to prepare for merging */
! 	for (tapenum = 0; tapenum < TAPERANGE; tapenum++)
  		LogicalTapeRewind(state->tapeset, tapenum, false);
  
  	for (;;)
  	{
  		/* Step D5: merge runs onto tape[T] until tape[P] is empty */
! 		while (state->tp_runs[TAPERANGE - 1] || state->tp_dummy[TAPERANGE - 1])
  		{
  			bool		allDummy = true;
  			bool		allOneRun = true;
  
! 			for (tapenum = 0; tapenum < TAPERANGE; tapenum++)
  			{
! 				if (state->tp_dummy[tapenum] == 0)
  					allDummy = false;
! 				if (state->tp_runs[tapenum] + state->tp_dummy[tapenum] != 1)
  					allOneRun = false;
  			}
  
--- 1238,1259 ----
  	}
  
  	/* End of step D2: rewind all output tapes to prepare for merging */
! 	for (tapenum = 0; tapenum < TapeRange; tapenum++)
  		LogicalTapeRewind(state->tapeset, tapenum, false);
  
  	for (;;)
  	{
  		/* Step D5: merge runs onto tape[T] until tape[P] is empty */
! 		while (state->logtapes[TapeRange - 1]->tp_runs || state->logtapes[TapeRange - 1]->tp_dummy)
  		{
  			bool		allDummy = true;
  			bool		allOneRun = true;
  
! 			for (tapenum = 0; tapenum < TapeRange; tapenum++)
  			{
! 				if (state->logtapes[tapenum]->tp_dummy == 0)
  					allDummy = false;
! 				if (state->logtapes[tapenum]->tp_runs + state->logtapes[tapenum]->tp_dummy != 1)
  					allOneRun = false;
  			}
  
***************
*** 1198,1211 ****
  				Assert(!allDummy);
  				/* Initialize for the final merge pass */
  				beginmerge(state);
  				state->status = TSS_FINALMERGE;
  				return;
  			}
  			if (allDummy)
  			{
! 				state->tp_dummy[TAPERANGE]++;
! 				for (tapenum = 0; tapenum < TAPERANGE; tapenum++)
! 					state->tp_dummy[tapenum]--;
  			}
  			else
  				mergeonerun(state);
--- 1266,1284 ----
  				Assert(!allDummy);
  				/* Initialize for the final merge pass */
  				beginmerge(state);
+ #ifdef TRACE_SORT
+ 	if (trace_sort)
+ 		elog(LOG, "TSS_FINALMERGE %s",
+ 			 pg_rusage_show(&state->ru_start));
+ #endif
  				state->status = TSS_FINALMERGE;
  				return;
  			}
  			if (allDummy)
  			{
! 				state->logtapes[TapeRange]->tp_dummy++;
! 				for (tapenum = 0; tapenum < TapeRange; tapenum++)
! 					state->logtapes[tapenum]->tp_dummy--;
  			}
  			else
  				mergeonerun(state);
***************
*** 1214,1241 ****
  		if (--state->Level == 0)
  			break;
  		/* rewind output tape T to use as new input */
! 		LogicalTapeRewind(state->tapeset, state->tp_tapenum[TAPERANGE],
  						  false);
  		/* rewind used-up input tape P, and prepare it for write pass */
! 		LogicalTapeRewind(state->tapeset, state->tp_tapenum[TAPERANGE - 1],
  						  true);
! 		state->tp_runs[TAPERANGE - 1] = 0;
  
  		/*
  		 * reassign tape units per step D6; note we no longer care about A[]
  		 */
! 		svTape = state->tp_tapenum[TAPERANGE];
! 		svDummy = state->tp_dummy[TAPERANGE];
! 		svRuns = state->tp_runs[TAPERANGE];
! 		for (tapenum = TAPERANGE; tapenum > 0; tapenum--)
  		{
! 			state->tp_tapenum[tapenum] = state->tp_tapenum[tapenum - 1];
! 			state->tp_dummy[tapenum] = state->tp_dummy[tapenum - 1];
! 			state->tp_runs[tapenum] = state->tp_runs[tapenum - 1];
  		}
! 		state->tp_tapenum[0] = svTape;
! 		state->tp_dummy[0] = svDummy;
! 		state->tp_runs[0] = svRuns;
  	}
  
  	/*
--- 1287,1314 ----
  		if (--state->Level == 0)
  			break;
  		/* rewind output tape T to use as new input */
! 		LogicalTapeRewind(state->tapeset, state->logtapes[TapeRange]->tp_tapenum,
  						  false);
  		/* rewind used-up input tape P, and prepare it for write pass */
! 		LogicalTapeRewind(state->tapeset, state->logtapes[TapeRange - 1]->tp_tapenum,
  						  true);
! 		state->logtapes[TapeRange - 1]->tp_runs = 0;
  
  		/*
  		 * reassign tape units per step D6; note we no longer care about A[]
  		 */
! 		svTape = state->logtapes[TapeRange]->tp_tapenum;
! 		svDummy = state->logtapes[TapeRange]->tp_dummy;
! 		svRuns = state->logtapes[TapeRange]->tp_runs;
! 		for (tapenum = TapeRange; tapenum > 0; tapenum--)
  		{
! 			state->logtapes[tapenum]->tp_tapenum = state->logtapes[tapenum - 1]->tp_tapenum;
! 			state->logtapes[tapenum]->tp_dummy = state->logtapes[tapenum - 1]->tp_dummy;
! 			state->logtapes[tapenum]->tp_runs = state->logtapes[tapenum - 1]->tp_runs;
  		}
! 		state->logtapes[0]->tp_tapenum = svTape;
! 		state->logtapes[0]->tp_dummy = svDummy;
! 		state->logtapes[0]->tp_runs = svRuns;
  	}
  
  	/*
***************
*** 1246,1252 ****
  	 * output tape while rewinding it.	The last iteration of step D6 would be
  	 * a waste of cycles anyway...
  	 */
! 	state->result_tape = state->tp_tapenum[TAPERANGE];
  	LogicalTapeFreeze(state->tapeset, state->result_tape);
  	state->status = TSS_SORTEDONTAPE;
  }
--- 1319,1325 ----
  	 * output tape while rewinding it.	The last iteration of step D6 would be
  	 * a waste of cycles anyway...
  	 */
! 	state->result_tape = state->logtapes[TapeRange]->tp_tapenum;
  	LogicalTapeFreeze(state->tapeset, state->result_tape);
  	state->status = TSS_SORTEDONTAPE;
  }
***************
*** 1260,1266 ****
  static void
  mergeonerun(Tuplesortstate *state)
  {
! 	int			destTape = state->tp_tapenum[TAPERANGE];
  	int			srcTape;
  	int			tupIndex;
  	void	   *tup;
--- 1333,1339 ----
  static void
  mergeonerun(Tuplesortstate *state)
  {
! 	int			destTape = state->logtapes[TapeRange]->tp_tapenum;
  	int			srcTape;
  	int			tupIndex;
  	void	   *tup;
***************
*** 1287,1308 ****
  		WRITETUP(state, destTape, state->memtuples[0]);
  		/* writetup adjusted total free space, now fix per-tape space */
  		spaceFreed = state->availMem - priorAvail;
! 		state->mergeavailmem[srcTape] += spaceFreed;
  		/* compact the heap */
  		tuplesort_heap_siftup(state, false);
! 		if ((tupIndex = state->mergenext[srcTape]) == 0)
  		{
  			/* out of preloaded data on this tape, try to read more */
  			mergepreread(state);
  			/* if still no data, we've reached end of run on this tape */
! 			if ((tupIndex = state->mergenext[srcTape]) == 0)
  				continue;
  		}
  		/* pull next preread tuple from list, insert in heap */
  		tup = state->memtuples[tupIndex];
! 		state->mergenext[srcTape] = state->memtupindex[tupIndex];
! 		if (state->mergenext[srcTape] == 0)
! 			state->mergelast[srcTape] = 0;
  		state->memtupindex[tupIndex] = state->mergefreelist;
  		state->mergefreelist = tupIndex;
  		tuplesort_heap_insert(state, tup, srcTape, false);
--- 1360,1381 ----
  		WRITETUP(state, destTape, state->memtuples[0]);
  		/* writetup adjusted total free space, now fix per-tape space */
  		spaceFreed = state->availMem - priorAvail;
! 		state->logtapes[srcTape]->mergeavailmem += spaceFreed;
  		/* compact the heap */
  		tuplesort_heap_siftup(state, false);
! 		if ((tupIndex = state->logtapes[srcTape]->mergenext) == 0)
  		{
  			/* out of preloaded data on this tape, try to read more */
  			mergepreread(state);
  			/* if still no data, we've reached end of run on this tape */
! 			if ((tupIndex = state->logtapes[srcTape]->mergenext) == 0)
  				continue;
  		}
  		/* pull next preread tuple from list, insert in heap */
  		tup = state->memtuples[tupIndex];
! 		state->logtapes[srcTape]->mergenext = state->memtupindex[tupIndex];
! 		if (state->logtapes[srcTape]->mergenext == 0)
! 			state->logtapes[srcTape]->mergelast = 0;
  		state->memtupindex[tupIndex] = state->mergefreelist;
  		state->mergefreelist = tupIndex;
  		tuplesort_heap_insert(state, tup, srcTape, false);
***************
*** 1313,1319 ****
  	 * output tape, and increment its count of real runs.
  	 */
  	markrunend(state, destTape);
! 	state->tp_runs[TAPERANGE]++;
  
  #ifdef TRACE_SORT
  	if (trace_sort)
--- 1386,1392 ----
  	 * output tape, and increment its count of real runs.
  	 */
  	markrunend(state, destTape);
! 	state->logtapes[TapeRange]->tp_runs++;
  
  #ifdef TRACE_SORT
  	if (trace_sort)
***************
*** 1341,1365 ****
  	Assert(state->memtupcount == 0);
  
  	/* Clear merge-pass state variables */
! 	memset(state->mergeactive, 0, sizeof(state->mergeactive));
! 	memset(state->mergenext, 0, sizeof(state->mergenext));
! 	memset(state->mergelast, 0, sizeof(state->mergelast));
! 	memset(state->mergeavailmem, 0, sizeof(state->mergeavailmem));
  	state->mergefreelist = 0;	/* nothing in the freelist */
! 	state->mergefirstfree = MAXTAPES;	/* first slot available for preread */
  
  	/* Adjust run counts and mark the active tapes */
  	activeTapes = 0;
! 	for (tapenum = 0; tapenum < TAPERANGE; tapenum++)
  	{
! 		if (state->tp_dummy[tapenum] > 0)
! 			state->tp_dummy[tapenum]--;
  		else
  		{
! 			Assert(state->tp_runs[tapenum] > 0);
! 			state->tp_runs[tapenum]--;
! 			srcTape = state->tp_tapenum[tapenum];
! 			state->mergeactive[srcTape] = true;
  			activeTapes++;
  		}
  	}
--- 1414,1441 ----
  	Assert(state->memtupcount == 0);
  
  	/* Clear merge-pass state variables */
! 	for (tapenum = 0; tapenum < MaxTapes; tapenum++)
!     {
!         state->logtapes[tapenum]->mergeactive = false;
!         state->logtapes[tapenum]->mergenext = 0;
!         state->logtapes[tapenum]->mergelast = 0;
!         state->logtapes[tapenum]->mergeavailmem = 0;
!     }
  	state->mergefreelist = 0;	/* nothing in the freelist */
! 	state->mergefirstfree = MaxTapes;	/* first slot available for preread */
  
  	/* Adjust run counts and mark the active tapes */
  	activeTapes = 0;
! 	for (tapenum = 0; tapenum < TapeRange; tapenum++)
  	{
! 		if (state->logtapes[tapenum]->tp_dummy > 0)
! 			state->logtapes[tapenum]->tp_dummy--;
  		else
  		{
! 			Assert(state->logtapes[tapenum]->tp_runs > 0);
! 			state->logtapes[tapenum]->tp_runs--;
! 			srcTape = state->logtapes[tapenum]->tp_tapenum;
! 			state->logtapes[srcTape]->mergeactive = true;
  			activeTapes++;
  		}
  	}
***************
*** 1370,1379 ****
  	 */
  	Assert(activeTapes > 0);
  	state->spacePerTape = state->availMem / activeTapes;
! 	for (srcTape = 0; srcTape < MAXTAPES; srcTape++)
  	{
! 		if (state->mergeactive[srcTape])
! 			state->mergeavailmem[srcTape] = state->spacePerTape;
  	}
  
  	/*
--- 1446,1455 ----
  	 */
  	Assert(activeTapes > 0);
  	state->spacePerTape = state->availMem / activeTapes;
! 	for (srcTape = 0; srcTape < MaxTapes; srcTape++)
  	{
! 		if (state->logtapes[srcTape]->mergeactive)
! 			state->logtapes[srcTape]->mergeavailmem = state->spacePerTape;
  	}
  
  	/*
***************
*** 1383,1399 ****
  	mergepreread(state);
  
  	/* Load the merge heap with the first tuple from each input tape */
! 	for (srcTape = 0; srcTape < MAXTAPES; srcTape++)
  	{
! 		int			tupIndex = state->mergenext[srcTape];
  		void	   *tup;
  
  		if (tupIndex)
  		{
  			tup = state->memtuples[tupIndex];
! 			state->mergenext[srcTape] = state->memtupindex[tupIndex];
! 			if (state->mergenext[srcTape] == 0)
! 				state->mergelast[srcTape] = 0;
  			state->memtupindex[tupIndex] = state->mergefreelist;
  			state->mergefreelist = tupIndex;
  			tuplesort_heap_insert(state, tup, srcTape, false);
--- 1459,1475 ----
  	mergepreread(state);
  
  	/* Load the merge heap with the first tuple from each input tape */
! 	for (srcTape = 0; srcTape < MaxTapes; srcTape++)
  	{
! 		int			tupIndex = state->logtapes[srcTape]->mergenext;
  		void	   *tup;
  
  		if (tupIndex)
  		{
  			tup = state->memtuples[tupIndex];
! 			state->logtapes[srcTape]->mergenext = state->memtupindex[tupIndex];
! 			if (state->logtapes[srcTape]->mergenext == 0)
! 				state->logtapes[srcTape]->mergelast = 0;
  			state->memtupindex[tupIndex] = state->mergefreelist;
  			state->mergefreelist = tupIndex;
  			tuplesort_heap_insert(state, tup, srcTape, false);
***************
*** 1420,1428 ****
  	long		priorAvail,
  				spaceUsed;
  
! 	for (srcTape = 0; srcTape < MAXTAPES; srcTape++)
  	{
! 		if (!state->mergeactive[srcTape])
  			continue;
  
  		/*
--- 1496,1504 ----
  	long		priorAvail,
  				spaceUsed;
  
! 	for (srcTape = 0; srcTape < MaxTapes; srcTape++)
  	{
! 		if (!state->logtapes[srcTape]->mergeactive)
  			continue;
  
  		/*
***************
*** 1431,1438 ****
  		 * adjustment?).  This avoids reading just a few tuples when the
  		 * incoming runs are not being consumed evenly.
  		 */
! 		if (state->mergenext[srcTape] != 0 &&
! 			state->mergeavailmem[srcTape] <= state->spacePerTape / 2)
  			continue;
  
  		/*
--- 1507,1514 ----
  		 * adjustment?).  This avoids reading just a few tuples when the
  		 * incoming runs are not being consumed evenly.
  		 */
! 		if (state->logtapes[srcTape]->mergenext != 0 &&
! 			state->logtapes[srcTape]->mergeavailmem <= state->spacePerTape / 2)
  			continue;
  
  		/*
***************
*** 1440,1452 ****
  		 * but ensure that we have at least one.
  		 */
  		priorAvail = state->availMem;
! 		state->availMem = state->mergeavailmem[srcTape];
! 		while (!LACKMEM(state) || state->mergenext[srcTape] == 0)
  		{
  			/* read next tuple, if any */
  			if ((tuplen = getlen(state, srcTape, true)) == 0)
  			{
! 				state->mergeactive[srcTape] = false;
  				break;
  			}
  			tup = READTUP(state, srcTape, tuplen);
--- 1516,1528 ----
  		 * but ensure that we have at least one.
  		 */
  		priorAvail = state->availMem;
! 		state->availMem = state->logtapes[srcTape]->mergeavailmem;
! 		while (!LACKMEM(state) || state->logtapes[srcTape]->mergenext == 0)
  		{
  			/* read next tuple, if any */
  			if ((tuplen = getlen(state, srcTape, true)) == 0)
  			{
! 				state->logtapes[srcTape]->mergeactive = false;
  				break;
  			}
  			tup = READTUP(state, srcTape, tuplen);
***************
*** 1476,1490 ****
  			/* store tuple, append to list for its tape */
  			state->memtuples[tupIndex] = tup;
  			state->memtupindex[tupIndex] = 0;
! 			if (state->mergelast[srcTape])
! 				state->memtupindex[state->mergelast[srcTape]] = tupIndex;
  			else
! 				state->mergenext[srcTape] = tupIndex;
! 			state->mergelast[srcTape] = tupIndex;
  		}
  		/* update per-tape and global availmem counts */
! 		spaceUsed = state->mergeavailmem[srcTape] - state->availMem;
! 		state->mergeavailmem[srcTape] = state->availMem;
  		state->availMem = priorAvail - spaceUsed;
  	}
  }
--- 1552,1566 ----
  			/* store tuple, append to list for its tape */
  			state->memtuples[tupIndex] = tup;
  			state->memtupindex[tupIndex] = 0;
! 			if (state->logtapes[srcTape]->mergelast)
! 				state->memtupindex[state->logtapes[srcTape]->mergelast] = tupIndex;
  			else
! 				state->logtapes[srcTape]->mergenext = tupIndex;
! 			state->logtapes[srcTape]->mergelast = tupIndex;
  		}
  		/* update per-tape and global availmem counts */
! 		spaceUsed = state->logtapes[srcTape]->mergeavailmem - state->availMem;
! 		state->logtapes[srcTape]->mergeavailmem = state->availMem;
  		state->availMem = priorAvail - spaceUsed;
  	}
  }
***************
*** 1516,1522 ****
  		 * heap.
  		 */
  		Assert(state->memtupcount > 0);
! 		WRITETUP(state, state->tp_tapenum[state->destTape],
  				 state->memtuples[0]);
  		tuplesort_heap_siftup(state, true);
  
--- 1592,1598 ----
  		 * heap.
  		 */
  		Assert(state->memtupcount > 0);
! 		WRITETUP(state, state->logtapes[state->destTape]->tp_tapenum,
  				 state->memtuples[0]);
  		tuplesort_heap_siftup(state, true);
  
***************
*** 1527,1542 ****
  		if (state->memtupcount == 0 ||
  			state->currentRun != state->memtupindex[0])
  		{
! 			markrunend(state, state->tp_tapenum[state->destTape]);
  			state->currentRun++;
! 			state->tp_runs[state->destTape]++;
! 			state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
  
  #ifdef TRACE_SORT
  			if (trace_sort)
! 				elog(LOG, "finished writing%s run %d: %s",
  					 (state->memtupcount == 0) ? " final" : "",
! 					 state->currentRun,
  					 pg_rusage_show(&state->ru_start));
  #endif
  
--- 1603,1618 ----
  		if (state->memtupcount == 0 ||
  			state->currentRun != state->memtupindex[0])
  		{
! 			markrunend(state, state->logtapes[state->destTape]->tp_tapenum);
  			state->currentRun++;
! 			state->logtapes[state->destTape]->tp_runs++;
! 			state->logtapes[state->destTape]->tp_dummy--; /* per Alg D step D2 */
  
  #ifdef TRACE_SORT
  			if (trace_sort)
! 				elog(LOG, "finished writing%s run %d to tape %d: %s",
  					 (state->memtupcount == 0) ? " final" : "",
! 					 state->currentRun, state->destTape,
  					 pg_rusage_show(&state->ru_start));
  #endif