On Fri, Aug 12, 2016 at 4:30 PM, Peter Geoghegan <p...@heroku.com> wrote:
> Doesn't tuplesort_heap_siftup() actually shift-down?
>
> The Wikipedia article on heaps [1] lists "shift-down" (never "sift
> down", FWIW) as a common operation on a heap:
>
> "shift-down: move a node down in the tree, similar to shift-up; used
> to restore heap condition after deletion or replacement."
>
> This seems to be what tuplesort_heap_siftup() actually does (among
> other things; its job is to compact the heap following caller
> returning the root, where caller leaves a "hole" at the root position
> 0).

Heikki (CC'd) and I discussed this privately today, and we were in
agreement that this needs to be fixed, so I wrote a patch, which I
attach here.


-- 
Peter Geoghegan
From b747c088e5ad7fb831e21e6d3a503f594cbc8e12 Mon Sep 17 00:00:00 2001
From: Peter Geoghegan <p...@bowt.ie>
Date: Wed, 7 Sep 2016 13:51:38 -0700
Subject: [PATCH] Rename tuplesort_heap_siftup function

tuplesort_heap_siftup is renamed to tuplesort_heap_compact.  The name
tuplesort_heap_siftup did not accurately represent the underlying
behavior.  The function shifts down, rather than sifting (shifting up).

The new name is chosen to describe the function at a slightly higher
level, since the underlying heap operation is just an implementation
detail.
---
 src/backend/utils/sort/tuplesort.c | 28 +++++++++++++---------------
 1 file changed, 13 insertions(+), 15 deletions(-)

diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index aa8e0e4..02d4b6b 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -570,7 +570,7 @@ static void sort_bounded_heap(Tuplesortstate *state);
 static void tuplesort_sort_memtuples(Tuplesortstate *state);
 static void tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple,
 					  int tupleindex, bool checkIndex);
-static void tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex);
+static void tuplesort_heap_compact(Tuplesortstate *state, bool checkIndex);
 static void reversedirection(Tuplesortstate *state);
 static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
 static void markrunend(Tuplesortstate *state, int tapenum);
@@ -1617,9 +1617,9 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
 			}
 			else
 			{
-				/* discard top of heap, sift up, insert new tuple */
+				/* discard root of heap to compact, insert new tuple */
 				free_sort_tuple(state, &state->memtuples[0]);
-				tuplesort_heap_siftup(state, false);
+				tuplesort_heap_compact(state, false);
 				tuplesort_heap_insert(state, tuple, 0, false);
 			}
 			break;
@@ -1987,7 +1987,7 @@ tuplesort_gettuple_common(Tuplesortstate *state, bool forward,
 				 * more generally.
 				 */
 				*stup = state->memtuples[0];
-				tuplesort_heap_siftup(state, false);
+				tuplesort_heap_compact(state, false);
 				if ((tupIndex = state->mergenext[srcTape]) == 0)
 				{
 					/*
@@ -2642,8 +2642,7 @@ mergeonerun(Tuplesortstate *state)
 		/* 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);
+		tuplesort_heap_compact(state, false);
 		if ((tupIndex = state->mergenext[srcTape]) == 0)
 		{
 			/* out of preloaded data on this tape, try to read more */
@@ -3275,13 +3274,12 @@ dumptuples(Tuplesortstate *state, bool alltuples)
 			 * Still holding out for a case favorable to replacement
 			 * selection. Still incrementally spilling using heap.
 			 *
-			 * Dump the heap's frontmost entry, and sift up to remove it from
-			 * the heap.
+			 * Dump the heap's root entry, and remove it from the heap.
 			 */
 			Assert(state->memtupcount > 0);
 			WRITETUP(state, state->tp_tapenum[state->destTape],
 					 &state->memtuples[0]);
-			tuplesort_heap_siftup(state, true);
+			tuplesort_heap_compact(state, true);
 		}
 		else
 		{
@@ -3663,7 +3661,7 @@ make_bounded_heap(Tuplesortstate *state)
 			if (state->memtupcount > state->bound)
 			{
 				free_sort_tuple(state, &state->memtuples[0]);
-				tuplesort_heap_siftup(state, false);
+				tuplesort_heap_compact(state, false);
 			}
 		}
 	}
@@ -3693,8 +3691,8 @@ sort_bounded_heap(Tuplesortstate *state)
 	{
 		SortTuple	stup = state->memtuples[0];
 
-		/* this sifts-up the next-largest entry and decreases memtupcount */
-		tuplesort_heap_siftup(state, false);
+		/* this puts next-largest entry at root, and decreases memtupcount */
+		tuplesort_heap_compact(state, false);
 		state->memtuples[state->memtupcount] = stup;
 	}
 	state->memtupcount = tupcount;
@@ -3784,10 +3782,10 @@ tuplesort_heap_insert(Tuplesortstate *state, SortTuple *tuple,
 
 /*
  * The tuple at state->memtuples[0] has been removed from the heap.
- * Decrement memtupcount, and sift up to maintain the heap invariant.
+ * Decrement memtupcount, and shift down to maintain the heap invariant.
  */
 static void
-tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
+tuplesort_heap_compact(Tuplesortstate *state, bool checkIndex)
 {
 	SortTuple  *memtuples = state->memtuples;
 	SortTuple  *tuple;
@@ -3801,7 +3799,7 @@ tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
 	CHECK_FOR_INTERRUPTS();
 
 	n = state->memtupcount;
-	tuple = &memtuples[n];		/* tuple that must be reinserted */
+	tuple = &memtuples[n];		/* tuple that must be relocated */
 	i = 0;						/* i is where the "hole" is */
 	for (;;)
 	{
-- 
2.7.4

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

Reply via email to