Minor performance improvement in transition to external sort

Started by Jeremy Harrisalmost 12 years ago19 messages
#1Jeremy Harris
jgh@wizmail.org
1 attachment(s)

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

--
Cheers,
Jeremy

Attachments:

dtext/plain; charset=UTF-8; name=dDownload
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 8b520c1..2ea7b2d 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -1211,7 +1211,8 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
 				(void) grow_memtuples(state);
 				Assert(state->memtupcount < state->memtupsize);
 			}
-			state->memtuples[state->memtupcount++] = *tuple;
+			state->memtuples[state->memtupcount] = *tuple;
+			state->memtuples[state->memtupcount++].tupindex = 0;
 
 			/*
 			 * Check if it's time to switch over to a bounded heapsort. We do
@@ -1884,23 +1885,47 @@ inittapes(Tuplesortstate *state)
 	state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
 
 	/*
-	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple is
-	 * marked as belonging to run number zero.
-	 *
-	 * NOTE: we pass false for checkIndex since there's no point in comparing
-	 * indexes in this step, even though we do intend the indexes to be part
-	 * of the sort key...
+	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple was
+	 * marked as belonging to run number zero on input; we don't compare that.
 	 */
 	ntuples = state->memtupcount;
-	state->memtupcount = 0;		/* make the heap empty */
-	for (j = 0; j < ntuples; j++)
 	{
-		/* Must copy source tuple to avoid possible overwrite */
-		SortTuple	stup = state->memtuples[j];
+		SortTuple * m = state->memtuples;
 
-		tuplesort_heap_insert(state, &stup, 0, false);
+		for (j = (ntuples-2)/2;	/* comb the array from the last heap parent */
+			 j >= 0;			/* to the start */
+			 j--)
+		{
+			int root = j;
+			int child, swap = 0;
+			SortTuple ptup = m[root];
+
+			while ((child = root*2 + 1) <= ntuples-1)
+			{	/* root has at least one child. Check left-child */
+				if (COMPARETUP(state, &ptup, &m[child]) < 0)
+				{									/* [root] < [lchild] */
+					if (  ++child <= ntuples-1		/* check right-child */
+					   && COMPARETUP(state, &ptup, &m[child]) > 0)
+						swap = child;
+					else
+						break;						/* [root] smallest */
+				}
+				else
+				{
+					swap = child;
+					if (  ++child <= ntuples-1		/* check right-child */
+					   && COMPARETUP(state, &m[swap], &m[child]) > 0)
+						swap = child;
+				}
+				/* [swap] is smallest of three; move into the parent slot */
+				m[root] = m[swap];
+				root = swap;			/* and repeat with the child subtree */
+			}
+			if (swap)
+				m[swap] = ptup;
+			/* This and all heap nodes after are now well-positioned */
+		}
 	}
-	Assert(state->memtupcount == ntuples);
 
 	state->currentRun = 0;
 
#2Michael Paquier
michael.paquier@gmail.com
In reply to: Jeremy Harris (#1)
Re: Minor performance improvement in transition to external sort

On Wed, Feb 5, 2014 at 7:22 AM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

It looks interesting but it is too late to have that in 9.4... You
should definitely add this patch to the next commit fest so as it is
not lost in the void:
https://commitfest.postgresql.org/action/commitfest_view?id=22
Regards,
--
Michael

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

#3Robert Haas
robertmhaas@gmail.com
In reply to: Jeremy Harris (#1)
Re: Minor performance improvement in transition to external sort

On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
n); doing that n times is therefore O(n lg n). Your patch likewise
implements an outer loop which runs O(n) times and an inner loop which
runs at most O(lg n) times, so a naive analysis of that algorithm also
comes out to O(n lg n). Wikipedia's article on
http://en.wikipedia.org/wiki/Heapsort explains why a tighter bound is
possible for the siftdown case.

I think I tested something like this at some point and concluded that
it didn't really help much, because building the initial heap was a
pretty small part of the runtime of a large sort. It may still be
worth doing, though.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

#4Jeremy Harris
jgh@wizmail.org
In reply to: Robert Haas (#3)
1 attachment(s)
Re: Minor performance improvement in transition to external sort

On 05/02/14 21:56, Robert Haas wrote:

On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
n); doing that n times is therefore O(n lg n). Your patch likewise
implements an outer loop which runs O(n) times and an inner loop which
runs at most O(lg n) times, so a naive analysis of that algorithm also
comes out to O(n lg n).

The patch implements a siftdown. Measurements attached.
--
Cheers,
Jeremy

Attachments:

results.csvtext/csv; name=results.csvDownload
#5Robert Haas
robertmhaas@gmail.com
In reply to: Jeremy Harris (#4)
Re: Minor performance improvement in transition to external sort

On Thu, Feb 6, 2014 at 4:22 AM, Jeremy Harris <jgh@wizmail.org> wrote:

On 05/02/14 21:56, Robert Haas wrote:

On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
n); doing that n times is therefore O(n lg n). Your patch likewise
implements an outer loop which runs O(n) times and an inner loop which
runs at most O(lg n) times, so a naive analysis of that algorithm also
comes out to O(n lg n).

The patch implements a siftdown. Measurements attached.

Uh, this spreadsheet is useless. You haven't explained how these
numbers were generated, or what the columns in the spreadsheet
actually mean. Ideally, you should include enough information that
someone else can try to reproduce your results.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

#6Jeff Janes
jeff.janes@gmail.com
In reply to: Jeremy Harris (#1)
Re: Minor performance improvement in transition to external sort

On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Thanks for working on this. Several times I've wondered why we didn't use
siftdown for heapifying, as it is a well known optimization. How big of
sets were you sorting in each case? Was it always just slightly bigger
than would fit in work_mem? Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets? We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a first pass.

The name of the attached patch is a bit unfortunate. And I'm not sure what
you are doing with tupindex, the change there doesn't seem to be necessary
to the rest of your work, so some explanation on that would be helpful.

The project coding style usually has comments in blocks before loops on
which they comment, rather than interspersed throughout the clauses of the
"for" statement.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

Siftdown is linear in all cases. Siftup may be linear in the typical case,
but is n log n in the worst case.

Another optimization that is possible is to do only one comparison at each
level (between the two children) all the way down the heap, and then
compare the parent to the chain of smallest children in reverse order.
This can substantially reduce the number of comparisons on average,
because most tuples sift most of the way down the heap (because most of the
tuples are at the bottom of the heap). Robert submitted a patch to do this
in the main siftdown routine (which for some reason is
named tuplesort_heap_siftup, rather than siftdown), and I found it a
substantial improvement but it never got pushed forward. I think Robert
was concerned it might make some obscure cases worse rather than better,
and no one put it through enough serious testing to overcome that concern.

(Also, I think you should make your siftdown code look more like the
existing siftdown code.)

Cheers,

Jeff

#7Jeremy Harris
jgh@wizmail.org
In reply to: Jeff Janes (#6)
Re: Minor performance improvement in transition to external sort

On 06/02/14 18:21, Jeff Janes wrote:

How big of
sets were you sorting in each case?

Big enough to go external. The timings and compare-counts given are
purely for the heapify stage not the total for the sort, so are
constrained by the work_mem not by the sort size per se.

I'm limited to working on a small machine, so the work_mem value
of 1e+6 is approaching my top limit of sort-time pain unless I rip the
heapify out into a test harness. What range of work_mem is it useful
to test over?

Was it always just slightly bigger
than would fit in work_mem?

I didn't check.

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets?

Not yet, but I can. What variety of pipe-organ shape is of
interest (I can think of several that might be called that)?

We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a first pass.

OK.

The name of the attached patch is a bit unfortunate.

Is there a project standard for this?

And I'm not sure what
you are doing with tupindex, the change there doesn't seem to be necessary
to the rest of your work, so some explanation on that would be helpful.

I'll add commentary.

The project coding style usually has comments in blocks before loops on
which they comment, rather than interspersed throughout the clauses of the
"for" statement.

I'll adjust that.

Another optimization that is possible is to do only one comparison at each
level (between the two children) all the way down the heap, and then
compare the parent to the chain of smallest children in reverse order.
This can substantially reduce the number of comparisons on average,
because most tuples sift most of the way down the heap (because most of the
tuples are at the bottom of the heap).

Sounds interesting; I'll see if I can get that going.

(Also, I think you should make your siftdown code look more like the
existing siftdown code.)

A function called by the outer loop? Can do; the existing does that
because the function is called from multiple places but this will only
be used the once.

Thanks for the review.
--
Jeremy

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

#8Jeremy Harris
jgh@wizmail.org
In reply to: Robert Haas (#5)
Re: Minor performance improvement in transition to external sort

On 06/02/14 14:22, Robert Haas wrote:

On Thu, Feb 6, 2014 at 4:22 AM, Jeremy Harris <jgh@wizmail.org> wrote:

On 05/02/14 21:56, Robert Haas wrote:

On Tue, Feb 4, 2014 at 5:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Both algorithms appear to be O(n) (contradicting Wikipedia's claim
that a siftup heapify is O(n log n)).

I think Wikipedia is right. Inserting an a tuple into a heap is O(lg
n); doing that n times is therefore O(n lg n). Your patch likewise
implements an outer loop which runs O(n) times and an inner loop which
runs at most O(lg n) times, so a naive analysis of that algorithm also
comes out to O(n lg n).

The patch implements a siftdown. Measurements attached.

Uh, this spreadsheet is useless. You haven't explained how these
numbers were generated, or what the columns in the spreadsheet
actually mean. Ideally, you should include enough information that
someone else can try to reproduce your results.

I'm sorry I wasn't clear.

Test code was groups of the form:

set work_mem to 1024;
CREATE TABLE jgh (i integer);
INSERT INTO jgh (i) SELECT 20000 * random() FROM generate_series(1, 20000);
VACUUM ANALYZE jgh;
explain analyze SELECT * FROM jgh ORDER BY i;
set enable_siftdown_heapify to off;
explain analyze SELECT * FROM jgh ORDER BY i;
set enable_siftdown_heapify to on;
DROP TABLE jgh;

.. for the tabulated work_mem, and scaled values for the INSERT.

Compares were counted for the heapify stage (only), and timings
taken using pg_rusage_init() before and pg_rusage_show() after
it. Times are in seconds.

Baseline value for compares and time used 858ec11858.
Sift-down compares and time are for the patch.

"Baseline K cmps" is compares divided by work_mem (which should
be a scaled version of compares-per-tuple being heapified) pre-patch.
"Siftdown K cmps" is likewise with the patch.

"K ratio cmps" is the ratio (patched compares)/(unpatched compares).

Repeat for time measurements.

--
Cheers,
Jeremy

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

#9Jeremy Harris
jgh@wizmail.org
In reply to: Jeremy Harris (#7)
1 attachment(s)
Re: Minor performance improvement in transition to external sort

On 06/02/14 22:12, Jeremy Harris wrote:

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets?

Summary (low numbers better):

Random ints: 83% compares, level on time.
Sorted ints: level compares, 70% time.
Reverse-sorted ints: 10% compares, 15% time (!)
Constant ints: 200% compares, 360% time (ouch, and not O(n))
Pipe-organ ints: 80% compares, 107% time
Random text: 83% compares, 106% time

--
Cheers,
Jeremy

Attachments:

siftdown_performance.odsapplication/vnd.oasis.opendocument.spreadsheet; name=siftdown_performance.odsDownload
#10Robert Haas
robertmhaas@gmail.com
In reply to: Jeremy Harris (#9)
Re: Minor performance improvement in transition to external sort

On Fri, Feb 7, 2014 at 4:28 PM, Jeremy Harris <jgh@wizmail.org> wrote:

On 06/02/14 22:12, Jeremy Harris wrote:

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets?

Summary (low numbers better):

Random ints: 83% compares, level on time.
Sorted ints: level compares, 70% time.
Reverse-sorted ints: 10% compares, 15% time (!)
Constant ints: 200% compares, 360% time (ouch, and not O(n))
Pipe-organ ints: 80% compares, 107% time
Random text: 83% compares, 106% time

This is kind of what I expected to happen. The problem is that it's
hard to make some cases better without making other cases worse. I
suspect (hope?) there's some simple fix for the constant-int case.
But the last two cases are trickier. It seems intuitively that
reducing comparisons ought to reduce runtime, but if I'm reading the
results, the runtime actually went up even though the number of
comparisons went down. This is hard to account for, but we probably
need to at least understand why that's happening. I feel like this
algorithm ought to be a win, but these data don't provide a compelling
case for change.

I wonder if it would be worth trying this test with text data as well.
Text comparisons are much more expensive than integer comparisons, so
the effect of saving comparisons ought to be more visible there.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

#11Jeremy Harris
jgh@wizmail.org
In reply to: Jeff Janes (#6)
4 attachment(s)
Re: Minor performance improvement in transition to external sort

On 06/02/14 18:21, Jeff Janes wrote:

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets? We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a first pass.

Attached is version 2 of the patch, which fixes the performance on
constant-input.

Summary (low numbers better, vs 858ec11):

Random ints: 83% compares, level on time.
Sorted ints: level compares, 70% time.
Reverse-sorted ints: 10% compares, 15% time (!)
Constant ints: level compares, 75% time
Pipe-organ ints: 80% compares, 107% time
Random text: 83% compares, 106% time

Another optimization that is possible is to do only one comparison at each
level (between the two children) all the way down the heap, and then
compare the parent to the chain of smallest children in reverse order.
This can substantially reduce the number of comparisons on average,
because most tuples sift most of the way down the heap (because most of the
tuples are at the bottom of the heap). Robert submitted a patch to do this
in the main siftdown routine (which for some reason is
named tuplesort_heap_siftup, rather than siftdown), and I found it a
substantial improvement but it never got pushed forward. I think Robert
was concerned it might make some obscure cases worse rather than better,
and no one put it through enough serious testing to overcome that concern.

I've done an implementation of this (also attached: siftdown_bounce).
Summary:

Random ints: 72% compares, 104% time.
Sorted ints: 200% compares, 270% time. (ouch)
Reverse-sorted ints: 7% compares, 12% time
Constant ints: 150% compares, 275% time
Pipe-organ ints: 93% compares, 115% time
Random text: 72% compares, 91% time

- I don't like the performance on already-sorted input. Thinking
into this, a sorted array is already a well-formed heap so optimal
behaviour is a single compare per item (lacking the global knowledge).
This "bounce" method will always do a full walk down the tree and
back, hence the poor behaviour. Unless the planner can tell
the sort when sorted input is possible I don't think we dare use
this despite the benefit on random input.

The tests were run with an instrumented variant of each patch, counting
compares and time for just the heapify portion of the inittapes()
routine. Test script (jgh.sql and results spreadsheet) also attached.
--
Cheers,
Jeremy

Attachments:

heapify_siftdown_v2.patchtext/x-patch; name=heapify_siftdown_v2.patchDownload
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 8b520c1..f687baa 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -464,6 +464,7 @@ static void sort_bounded_heap(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_siftdown(Tuplesortstate *state, int start);
 static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
 static void markrunend(Tuplesortstate *state, int tapenum);
 static int comparetup_heap(const SortTuple *a, const SortTuple *b,
@@ -1205,13 +1206,16 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
 			 * still one free slot remaining --- if we fail, there'll still be
 			 * room to store the incoming tuple, and then we'll switch to
 			 * tape-based operation.
+			 * Set the tape-number to zero here as it makes the code cleaner
+			 * for converting from internal to external sort.
 			 */
 			if (state->memtupcount >= state->memtupsize - 1)
 			{
 				(void) grow_memtuples(state);
 				Assert(state->memtupcount < state->memtupsize);
 			}
-			state->memtuples[state->memtupcount++] = *tuple;
+			state->memtuples[state->memtupcount] = *tuple;
+			state->memtuples[state->memtupcount++].tupindex = 0;
 
 			/*
 			 * Check if it's time to switch over to a bounded heapsort. We do
@@ -1826,7 +1830,6 @@ static void
 inittapes(Tuplesortstate *state)
 {
 	int			maxTapes,
-				ntuples,
 				j;
 	int64		tapeSpace;
 
@@ -1884,23 +1887,15 @@ inittapes(Tuplesortstate *state)
 	state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
 
 	/*
-	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple is
-	 * marked as belonging to run number zero.
-	 *
-	 * NOTE: we pass false for checkIndex since there's no point in comparing
-	 * indexes in this step, even though we do intend the indexes to be part
-	 * of the sort key...
+	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple was
+	 * marked as belonging to run number zero on input; we don't compare that.
+	 * We comb the array starting at the last heap parent and working back to the
+	 * start; for each such item we sift it down to its proper heap position.
+	 * After each iteration the start slot and all heap slots below make a
+	 * well-formed heap.
 	 */
-	ntuples = state->memtupcount;
-	state->memtupcount = 0;		/* make the heap empty */
-	for (j = 0; j < ntuples; j++)
-	{
-		/* Must copy source tuple to avoid possible overwrite */
-		SortTuple	stup = state->memtuples[j];
-
-		tuplesort_heap_insert(state, &stup, 0, false);
-	}
-	Assert(state->memtupcount == ntuples);
+	for (j = (state->memtupcount-2)/2; j >= 0; j--)
+		tuplesort_heap_siftdown(state, j);
 
 	state->currentRun = 0;
 
@@ -2749,6 +2744,51 @@ tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
 	memtuples[i] = *tuple;
 }
 
+/*
+ * The tuple at state->memtuples[start] is being added in the heap,
+ * which is well-formed for all larger indices.  Return with the
+ * heap well-formed for this and all larger indices.
+ *
+ * Working down from the start point: find the smallest tuple
+ * of it and its children.  If the current is the smallest, we're
+ * done. Else, move the smallest into the current slot and repeat
+ * with the subtree of the smallest.  When the current becomes
+ * smallest place it in the vacated slot.
+ */
+static void
+tuplesort_heap_siftdown(Tuplesortstate *state, int start)
+{
+	SortTuple * m = state->memtuples;
+	int ntuples = state->memtupcount;
+	int root = start;
+	int child, swap = 0;
+	SortTuple ptup = m[root];
+
+	while ((child = root*2 + 1) <= ntuples-1)
+	{
+		if (COMPARETUP(state, &ptup, &m[child]) <= 0)
+		{
+			if (  ++child <= ntuples-1
+				 && COMPARETUP(state, &ptup, &m[child]) > 0)
+				swap = child;
+			else
+				break;
+		}
+		else
+		{
+			swap = child;
+			if (  ++child <= ntuples-1
+				 && COMPARETUP(state, &m[swap], &m[child]) > 0)
+				swap = child;
+		}
+
+		m[root] = m[swap];
+		root = swap;
+	}
+	if (swap)
+		m[swap] = ptup;
+}
+
 
 /*
  * Tape interface routines
siftdown_bounce.patchtext/x-patch; name=siftdown_bounce.patchDownload
diff --git a/src/backend/utils/sort/tuplesort.c b/src/backend/utils/sort/tuplesort.c
index 8b520c1..8de3dbd 100644
--- a/src/backend/utils/sort/tuplesort.c
+++ b/src/backend/utils/sort/tuplesort.c
@@ -464,6 +464,7 @@ static void sort_bounded_heap(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_siftdown(Tuplesortstate *state, int start);
 static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
 static void markrunend(Tuplesortstate *state, int tapenum);
 static int comparetup_heap(const SortTuple *a, const SortTuple *b,
@@ -1205,13 +1206,16 @@ puttuple_common(Tuplesortstate *state, SortTuple *tuple)
 			 * still one free slot remaining --- if we fail, there'll still be
 			 * room to store the incoming tuple, and then we'll switch to
 			 * tape-based operation.
+			 * Set the tape-number to zero here as it makes the code cleaner
+			 * for converting from internal to external sort.
 			 */
 			if (state->memtupcount >= state->memtupsize - 1)
 			{
 				(void) grow_memtuples(state);
 				Assert(state->memtupcount < state->memtupsize);
 			}
-			state->memtuples[state->memtupcount++] = *tuple;
+			state->memtuples[state->memtupcount] = *tuple;
+			state->memtuples[state->memtupcount++].tupindex = 0;
 
 			/*
 			 * Check if it's time to switch over to a bounded heapsort. We do
@@ -1826,7 +1830,6 @@ static void
 inittapes(Tuplesortstate *state)
 {
 	int			maxTapes,
-				ntuples,
 				j;
 	int64		tapeSpace;
 
@@ -1884,23 +1887,15 @@ inittapes(Tuplesortstate *state)
 	state->tp_tapenum = (int *) palloc0(maxTapes * sizeof(int));
 
 	/*
-	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple is
-	 * marked as belonging to run number zero.
-	 *
-	 * NOTE: we pass false for checkIndex since there's no point in comparing
-	 * indexes in this step, even though we do intend the indexes to be part
-	 * of the sort key...
+	 * Convert the unsorted contents of memtuples[] into a heap. Each tuple was
+	 * marked as belonging to run number zero on input; we don't compare that.
+	 * We comb the array starting at the last heap parent and working back to the
+	 * start; for each such item we sift it down to its proper heap position.
+	 * After each iteration the start slot and all heap slots below make a
+	 * well-formed heap.
 	 */
-	ntuples = state->memtupcount;
-	state->memtupcount = 0;		/* make the heap empty */
-	for (j = 0; j < ntuples; j++)
-	{
-		/* Must copy source tuple to avoid possible overwrite */
-		SortTuple	stup = state->memtuples[j];
-
-		tuplesort_heap_insert(state, &stup, 0, false);
-	}
-	Assert(state->memtupcount == ntuples);
+	for (j = (state->memtupcount-2)/2; j >= 0; j--)
+		tuplesort_heap_siftdown(state, j);
 
 	state->currentRun = 0;
 
@@ -2749,6 +2744,55 @@ tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex)
 	memtuples[i] = *tuple;
 }
 
+/*
+ * The tuple at state->memtuples[start] is being added in the heap,
+ * which is well-formed for all larger indices.  Return with the
+ * heap well-formed for this and all larger indices.
+ *
+ * Working down from the start point: follow the smallest-child path
+ * down to the leaf, then back up until the new item is larger. Insert
+ * here, promoting all children one layer as far as the start slot.
+ */
+static inline void
+tuplesort_heap_siftdown(Tuplesortstate *state, int start)
+{
+	SortTuple * m = state->memtuples;
+	int ntup = state->memtupcount;
+	int par = start, child;
+	SortTuple tup, tup2;
+
+  /* Work down the smallest-child path to the leaf */
+	while ((child = par*2 + 1) < ntup)
+		par = child+1 < ntup  &&  COMPARETUP(state, &m[child], &m[child+1]) > 0
+				? child+1 : child;
+	child = par;
+
+	/* Work up until new item is larger or equal */
+	/*XXX Do we want early or late stop on equal? 
+			Early is fewer compares but more data-moves.
+			Late is fewer data-moves but more compares.
+			Assume compares are expensive, so early is best.
+	*/
+	while (child > start && COMPARETUP(state, &m[start], &m[child]) < 0)
+		child = (child-1)/2;
+
+	/* Insert here */
+	if (child != start)
+	{
+		tup = m[child];
+		m[child] = m[start];
+
+		while ((child = (child-1)/2) > start)
+		{
+			tup2 = m[child];
+			m[child] = tup;
+			tup = tup2;
+		}
+
+		m[start] = tup;
+	}
+}
+
 
 /*
  * Tape interface routines
jgh.sqlapplication/sql; name=jgh.sqlDownload
siftdown_performance.odsapplication/vnd.oasis.opendocument.spreadsheet; name=siftdown_performance.odsDownload
PK]{ID�l9�..mimetypeapplication/vnd.oasis.opendocument.spreadsheetPK]{IDBZ�SK%K%Thumbnails/thumbnail.png�PNG


IHDR�c�N*%IDATx����VU������P;"��G���$���P��2S��L�d+�CHsQpYF&p������!���?�hTLBbL
T��ZT�b��g|��9��{����}w9�?��}�{�y�}x��~x~����_��wu��z��3E)����{����3E)���e��m������z���Gg�R�-����;��s��5�������LQj�����LQj��L\pA��_����������S������e����c�V�Z�h��#~���>���
����������5k�������q�������.y�E�_is������k�����k�����/������-[F�~�a��.0���/������O������n�z��i:���}������=��#���g����S�L�2}�t�sSS��i��x��.�g��->���L�4i��9���'���'Onoo����}�Y���H7�������^�r�J����K.������?��������g:��i���;�����c3�[��Vss��$c��C=4r����w������/?y���+h���] Z��0z�hr&r���z��'O2�#�����3����c#g�=���v�jkk�����
/]��������m�6:��Ar�3f$��~#]�|�n9�w���~��emmm�+���O^y�����;s�LMM�?����C��q�~�����C���}�#���]v�����:z������v����it�a��_��Wc���=�:u�.���6l��������{+Yd �����/��:j�(�@�X|;�sM��Yg����.��rr���g���+t�><[ZZ�����?��n������+^��7�����[nY�z��F��>/�t��tL�OO<�})l�����O�8q������u�]'����~���}�����g��&����|���O_p��J_�I��P�m:�L����?��:DN�P����>����?�wHz�D����~�3���;���s�����K�.���c�@#�.$>�u�
�?}>��G�
��y�|��VT�"��R���L3�0��o�������m���m�~g2,��G�m�fqN�����/�j��W_}�����D�MMM��'�"`^J��]�[��]lcR	��,������!����Y�f��m��Y(�n�����n�g��
����J2��mL*��x�u9'CH�rZ�"�L����9s
n�������������B6662�S��!C����d�����K/-��q���������6&��L^��2�\�~�����.]����F��gfW��T�3��<�Z����v�����LQj�����LQj�����LQj�����LQj�����LQj�~g2q�555�f�z��G�G���y���~gJ:�sj���W\q9�IT�0a�/��I��k�y����������1�[���$U�3]��9s�$)�o�������'�b�����M�1�T��
GI:�L���D�.[�l������������G�1	�I��
Gyu��*�6��9���o;v,f����k��c������l�_��5g\�~��"V��ysm9�8��Eu�����z��3E�):S��������&�@6?_~����|���=���I�������S�Ly��g��/���Hy	���u�f��=~�xN%�(4�:C3�K�03���o<��S��z�����c���m�{=��i��d�9^�t����~�aZ�����{��O|������SY��L�������7����n��m���yBC�3o��6������������]}����1��������%~�������_z�%:���k����hy:0��
��4������o���l��������z�����������Xg���%�e���^K�<�@��4>�lt�g����O~�����>�):�U|���C�������H�)ZZd~���u��t�.����|�+�%����}�;������b�������W?���_y���c�.Z�H:���m�{=����v1�#;w�\�A�y����3��'����i4��'�s>������t|D�=���{�������/�]
�L��/�0�C�7��O?���>�m��e��^Oeg�����kJy�����J��e������]������3!��<�������*x>�lt�gDQj�����LQjRv&�^�G�9��������|���k
<�����Q�~���$	%�i��.�&��T��;v���Z��_��W�[��L�o��
/��=[w�S�N�8q�_�~t��P�8>�T�^�p<FP���[-�F�V*;�D/��>}���_>k���k�s|�C��z� �`��\��0�<)s��K�,��Z����Tv&�^�����{�nzi�������/|�c��%�� �`��\��0�<)s���V3*�������Tv&�^����0f��[n���ZG��������	�s��i<>�T�^�p<FP�������������� Q�xy?$=�!w�D����Rza�y����l�{�3*�F�zF4���LQj�w&�:�$�����k-ZD�"F,����Y��R2*#�A���El�`7dx��p�uJ����8�:�$�����/}�K555#��tq�B�f0�~����������P����!�A&q�
7,Y���7�x���U�4��d!.J	X�:��a�2<dN8�C.�Xzprdk����g�z��)���<x~k�Y�,�lS�0�
2'��!�l,=8��Hf_�����?�����/`������?q�������H�_�����u(������\P�����_-`��x��a�B�f0���aqV��9@���	����Q6�����)JM������L	p1L;t����%��]r�%���-����a 1#�C��Yk�H�J��8i��%�j���L	p1Lkmme�&fw��_�����a����@bF��P18����|�'�Uv�Q���I�}c�f���;�:+����W��pc���F<�0op��V��D5Rv&7`��a��� ����V^1#���g�Z6J�q�ZeJ�H��0`
����L�
X����5r.�K p,$fz�3k-���~op���a#�eeT'������4����y��'����AbF����u�jjj2	�������@���3E�):S���I��C��0�x}>3����u���T�l3=)�8�@���+��BB	�bs6�5t��3I�w�f�Z��`}>���O���N%�6#��2��S��BB	����F��. U���"f���3x�O�w*Y��^J�q^�T^H(�Y����x
]@��LR �L��,X��)�����W�\��N%�6#�K�0��"OU__����
^7��x
]@��LR�.���M�������;���X�'��;�,��@/%�8�x*	J`6x��6�5t��3I�w)0�x}>3�w~)���2�)�y�Sy!�f���h#^���U��3E�):S���I��C��v�Z�jkk�!d>�����o�4��,#=|���l����po��c��y!pP�ZKZ��R�#g����1�0`@�2��'��'��4��,#=�����-���m;C�*�X�S�D��-F
��}�0m���v/C�3��[0
#0�H�a��H������%(K3��A��L)�w�vUWW,C�|��?9�af��8�x�;?]X/��d���G�*8SJ��4�]�T�!�Iw��\���e��#�E��������������~���R�2������\Up���;�i�*��2i~��e���������vf��	^�oq����Row�����)JM
�$L�1��q��D�I�H���Hi��])���x~����x1����������6J-7��Ib<x�|��_�P�vw6l�;��?���VOa0w�}7�/��Q^L�'��?died���R�
#g�����=�/Ch�Ruu�;�5Rj��K)f��-<�d{�U��
OJA�����E��Ib<x�|B���K����o���F.�0�_�=�*^L%�/�`,#�W*�J��$����'F�����������[������`�K���l�(/�"y��-!K+#�mLi���8��x�/�j�����)�3�����)���������+�?��)�DEg�RSt�(5:+	"C�XSS�����������cV+�22z�����h���6�x��*��_���.�T�0)!8mL�$N��	����1illl�������]Jw~+��^�	���V��mf�o����J%	����g+���E98eq0C��g���7��[i�;����@���^:�B��@�kcVI���Y�$aI�q�J<*��y������A�������j��dzed�>�	�r�)�m�����������$a�qhcz��@g�0eABC���2��J{&Lp�O�
��ezed�����n��N�����2W�������RI�2���F)��(���LY���Fo�N%%��[;�z��g��C{�.�C3��*Y��[���IFe�1=�8��(5Eg�RSt�(5:��|8%��aZUC>�c���LS�����#-�M�������J�f�k.���
g��rmt&������0-��!�4���}c�HKo�i�=�����"�Y��K��a#����LR�a)��aZ0Uc>�d���LSN��1�RB4�%�=������4?�(�[����kc�3I�wRV+�4s&/Uc>�i��'���E)o��������J���RO�$�WLFq-��@g��KY��8�$�?�c�f�Zp�}c^c]��m:����y/{+)"����do6�Zns�@g������LUc>�i��'�7���pio�����R��w~�Q�7�2��k�6F4���LQj����@g�4d)��3��C%��i�2�?n���l=7y�=36������b��K*������X[��-i��wR��g"G�"3� J��:M[F���M1u�M�]y�=36����#_��%h�T�Q������7z�h�%�!K�~x��� �!N�i�2�?n���l���_����5?��������=���nc�0�HK��"�8\0"G�eq�N����!pSL����h�\��\��}K�.��c���6�����4d)����<9����(U������e���S��d�������\����+b��K*������X�=�c�	�����:�e	�yv��,�Q+�N����:osio�{��7�T�1�[K���aI���*O��������S	@ �W.2	z���V��T��0���x�"gb��������^���q~<V�����=�[��hBo�B �W.���V��T�����Q�Ll����18N�`�ei8��c��8��T�Q�!��@R���&�t<sfI��b�D�4��$����!~�n��8������`��ZK+8�����c�3!o@D��^��;L���_��V�����0���x�"grc��Mf��:XxY�������x?]t��}���r��L��)�@��M���M�a��j�x�f��Z�Q�Ll��M�_�8�������p0�o����!����)�X��7`
_J)�g�D��Z	Sy3M�u�Ir�e0�q"��H������p0�o����3�h JM�����)JM��L�w�����s��������3��������t����k���������f����L�l�2z�ojj�<yr{{;=�z���m��/7�N�>����p�B3�����R�U�D$}��%o���"�����G�<yr���L$_�1c�5�\�s�Nz�'��a����GVC����xz�!�lkk�n��G�u����������C���=:p���#�n��
�F�"w9s�}&����k_|��<�^���7!*1�T�?/���WWWG_v�W���!���2e�
7�0q����6d��A��8q�������;�O�>����V��5g������3����W�O���8`�����K��LQ�F�����)JM��$�N������k%���)=F�+��f��G!�6*;��;�����{����bD�T"1�R��`�mz��`c�_s�z�e���bDe�����`�mpC���|Kt&o	��������0E���R"1�!���
.s�Q�o��3I�S���2��kY��Q)�H���%I�+���Q������$�N��CU�������=F2*��H��Q�a�Y6F4���LQjRv&���_������0��GI��2�`���l���ug��?��4���f�"�()��S�{z���al���LR�'3����Y��2hK�������d���Y���sx�~[ZZ*�u���A[RFo�&������lt{3+;rd�H�6�����@�QRFo�&��� �~���3!�p�K0#Q_�Z�����)�	�=�*�F79��(5Eg�RSt�(5�;�[Ko��I���(Gr\(o������[m��<�eg���������d,C�������1��J�������[K/�����g,C�������1��J���
��;���^��,�X��S�-=���cx�|�W��Vo�D�����(�w����e;U���]8������V�,�i��^�2�!�TyKve�.�J���(�@���3E�):S����	�F2�<t�P�D��G��/��lF=���F)���E���a4 C�����!�<-��
!^zO��
zJ+�F)��H���@J��Z!���!�K�)�Q@O1��U	6��[��L��<CK�DK�����
z�u(�J���JegB����-
� ���W�B������:�&�Os+��	�dh�m���]��Go��W�S����X��O�����)JM������LX��a�xC���������T*���i�:�&-Pi�Jg���3�[�jU�Dfetey~\K*�Wv��tz��*�hR��9k�>��x"��q������T*���i���;lDP��JegB��������`"�2���Rye�N��(�\�XT���
�� ��3�����X"���S������q-�T^����u�M6"�t�I�	J#X��a�	A��ZR���S��������X�u���gEg�R��3!�@��Zk��5�����xB�7xN�+r�T^���*kU��	�%7P��� ��@-�.(X����<�J������V���l�
Tp&�V�j-^��p��Qc�7����T*��lW��*�FdK��Tp&�V�j1w���.5�x��7�d��\G*�Wv���Zn#�%��n��3!���8P����'
�!d�����2�A�#��+;�Ue�
��j�a�JgB�aq����/j~���8�T*��lW��Ph#p�VDQj�����LQjRp&)����7�`BN�����uR������@���H`����[�@<g�2M�����/�X�!'���I����2=��`�������x
�$e��1�5zp-X����%X'��X��p��1�k#�oq��I�4�ck��H�`�T*/x��@�/X��bm��-n ��3I��x�`m���rr���Ry�k��_�a���K���F
�$e��1���e19���Ry�k��;p`����$#��*Q�����)JM���Y������x555yCqZ�������P����8�R������e���Z�o	t&�"�H?<�-����H��
��r�=Vx!��7�AqF����voY��r�=�F���[�#-Q��x��3g�,R�������w
	qo�>;U
��aR�in+�F����HK<�-����\�!'g��RFl�S���L{��-����Y�����<]��P@�����"$���6(����R�/o9�a#BK��&���?*H�yoy��P@)i�	���
�3*�����[�G������@���3E�):S���	F��yk	��Ddq^�)5C���3Iz���m�P�bm|�����
3�4g�	F��yk��B��y������$��}������+��y�����q��%K`��::�������� Z,���R3d�[pfz
���e���r@9��������}b����0��	�5)=��9�+�bq.���!������=��r@9������/��Q�3!���><��������|N�
A�X��?�f����~&)@������V��t���%�F]::�����Ol>�7�bq.���KQ�����=�U�6N�0��Xr.�4�h JM�����L�Q�x��
!V��Y���A�*Fx��]��Ma0w�q��\�bl=�F���aXQ-89���3��/��x���=HY�o0�+��)�B���=�Fo9I�[���9���3������[�n5K���b�7��K��ca�%z��n9I��Q��0G�Z ��������@�
^�?���/�K�)���E2*��><��D�1�����%����H-���\FB_sa ��/����{�����\$�RM�ka�tqcR)D�@g������)&`E+��+���J����E2*���Z�7a���ic"����qQ%*:S���3E�)�31�������5$r�`��N�[�\�&�f�J��n0WF�t�{�2�=�F������v��XI�4�1�6lX�:y����J�9��j�f{��2��s�� �	��6J`V�w
+��� f�W����N.��r)�kS���MyI*��m���z� ���iXb|����u�p	��w�\J���`�cS^���t�@?7/�31���cG��4�1����C��K��
���Z����*��^�L`O���7��'��L��:��aj���N�[�%��%�m���Q.��^�L`�z��^0�F���LQj�����w&������2��J����������p^���)��Y���+����i�����-�g�~�������{���u���*=��
<���`{{;=��S�O�655�Zt���<	=�466._���i���O'���]vON����RE8�2OytGO�<�a��'��L7���X���(��M�6M�:�|h��<���k���$�����s'=�K����6l=���=���i�]�v����qz��:S@iX]���0z�h:���:z������Y���}o��1tS�3x����w�&o5j�k�����.��9r���3���K$�'�M�_�l��:�L��#`����3v��y����������>:r��={���6g��,}~����)S�����/��<��c'Nlii�W�2h��{���'����;wn�>}���m���9��}���[�t|���K���������������L�.q�����|����)��(:S���3E����M3��3)IEND�B`�PK]{IDsettings.xml�Z[S�:~?���������v���ZZ�}K4$LJ�����}��hm�������[�u�XkMO�C�3��#J������@�Q�����6vO��N���`��^B"v9Bn�;�8�����3R��#^! ��"�
� Y���]�
�]cD���@��R*%I����Q6,�u]/MW[=J�p]Q��/EQJJ���
�T��4�����|aM�.������\��c	����_NU;S��������U�^�qG.���K#e�(&�\DD(U���'���/��(��|����c�dk�D�`���������� �E��c�/���j/M���b�u4�I�_R�&C@��Q���)���] -���������F�1���P��L��U��7��k���q�r�2�L���0W����(�"�!�+
}I����L����ox���d�a�
���7g�Z�ZY��%n���@�Q!h�#����+Qr���8^F�*ZV7���[�D?��h�dh��]J1D�
���+.���x���o����o��+)Z;���/��Y���{����U������Q�]������2`�K�d��t�`��e���<#��3��N����u�;T�Y�����S��i�Be�h_��r�kVi.U�Cb���Y1B�D"���6��F������p�������K-�\vt�5n����0	������d�
h~e�-��>!��~N����4tf��q{B��Q����U����
�����1��?2����$�P�'E<��:���511�E�O�����vX����2bp�ML<��T��(�����?[��@��1o�0b�����J��%j��P����8<:�!�D�>�K������������\baoh|�WO�]\�����
�����G�0;������j6�{���&��P��uKs���Et?��z!���31C]�;�{C}=�qj#�X��>V��3��{�������Z ���,c���Wf�\����]m<�Bi��Eo�mU�~v��6�'�\O����n�k=��~?�������vk�;��G�n~���j9��8�~:�a��5d�t"��n���Qk������;�rz�q���;]�j��Z�qjW�<t�As�p���R���3����^�L�50����z��&�^\|=t����_f�����O*�
*e>�60�mI��5� �_H��j�M�%"O�T���������e���|��3S(�#)�U+x����)�*��O�R����PK���w��$PK]{IDcontent.xml�}ks\Ir�w��	:��>�YY�������
�V�����P(0@�/^��������.tfM%p	��D���s��=Y�s�7����7?�n�����{������������������(�������\�{w~�����������������_}u�-���7n���>�;�����ru������7�����}���Y�����/�/����~��=��5����|���)����nO>r_\c1�_�������.��]c�/oN��������/���������o?~��������B)����-��m�����)�����bU?��-,��&�ru��WcB��p���������������������F_�����{�����F�O8�e�gS����;��*���k/O�h|���?�/�?���������Y5��T�����/������z����	�5���?���d����������'�OO.N�����4���q��������&�����~�
�;k�������������.��p��������.3��Kh^ix{������&��|���[l?�_^����v����lo(�qo�F�!>��|��?��O�����O�|��5f�H���#�����������%c���������bz������;����-�5��;|B����������os}}ty�7���7�>x��u���'��������w|�������}����������M,�Oz0\�o~��������������V�w��
q������+��������o�tr�O�&���������������(�~���O����_]a"�.�>���}qs~�������t��}�r��N����a=��@���~u�K0������o��O�N��k��z�,��uu�??�\���o�������:��OXo� ����m�����|���"{~z4���V�����N�a�a�K��.��l^���G7���n��Ww���������_��_�C�oX?z������g����	pz9��)l������"���[J^��?c������n6d	����p{��0��CT����V����c�&����[]���_�\=|�����w�1����3��?����/q��=�9y�:��w'.�]���	��������k<�w�o��]^��;]���9T��}�owZ������7�H�������������p�����o.���!�{��������[����}����~���?��z�����a����_}����i������a��U]8���N���	2X�j���b������1�?��
��>��k&�N.��_�]���:����9N:V'�������������������<�	���";y{r��#��}d��:N��f����S
��~����8����/�ptr��u��_�~Z��x�*������U�y)YGL��������]�.���O}nk, ��f����M;�KN�p���c�^��|������R��.��L�/���b3�T�����_	��H�<\"�|)h�����~��u��d�����
�4���\�����T��5���g���'�[O���NN�y]	}��.�-�=��{���YGN���_�����{��8������z�J�wG���if|�#����7����=�Z��������7[#'VG�?�����o�����f����w{�������.�Q"}�������o������?��~�v����}�|s-����������V�
'~E��gD�+
���G������%�����n
��x������������_��ru��a\�Uz�,���9�?�au���q�����O�V�W�QW��������+��;m���g��} ~!5�^���h�~�������~��p��~���Uy��q��hG�/L����~�<�:���=�S���w�'��V������)|{�5��y/�<D�)R�Yc�
,��9W�(�H�l���V�`�����.N�{s�����m�����������;��;�EJ����.1<�<����Nt�[�� WLd�|~�����)��������gkK��qM���l�g�W��}�<�`C(���o����'��9+7�	1>��
�!������S�"�EHZ,��a��"����
+q~��4	9����F�KF0�����d��F�F��z�@�4�'�rL�'������so��;���)D]l.����������@�S|�q�����
�)X)�F���c
U�G~:���y��,�~��z���n��&���ufv��)�(��`/�����p�����}v���w�Q�������������������=��j��:�xC�zTgs������u\���z�pV0�w�����e"�"]��1�`��Gw��8��������	����i�w%J�)���Iq�g~�<r������d����!��\���:L�]�9�B�/��_�	J�����V(T/18~>�����R�/Y	���(�)=���?6��Z
dfp[F���lA?P	b6�cMl=������A�&e|�\.E2��>�Z�p��[��"uH'�
o�B���aN��`�u ��V���g�7�,����+�Ao\69fMV
:o�A,r>��AW��A�F��tJ8/�I�(4������S�|	8r�C/�gG ��x#�)R��R�cn
P��Y�L�Rk-��`
s,K�z���4��HT����J���8������p�� ���A�	���E1����j��~��hR�>�^�X*�KJ6�:!38Eh�����j��L���YCuX��<s�z�F�c�1Xi��*�yRw���:fbg��(IP1��.��mr}��w�+	��%�_��DV�%���%�����K6�K.��~��`���uX�B�����_MI�������N2�"���:V�����Gej��
Z��v�Q�:V/#�0����J�'���9�'�dJa�V:�J���D��GZe��a��}��~�$�T�b���Z|�,	�JB���]��9�[+��$�mk��x�r
UZ6�Hj�u��te�E�����������K�ki���!��r
�*�X6H���Y�s��g>Y���L�
��g
�}��3�@e���@YH�dVw[�
����,t@/�f�s�iZ�g�}������J�����M0��u�	z���3��k����?W
s��V�I�����5j{
$���8D������Cu�
C�]a(��L��<����VHl��~h	)c]p���Z��,$7���O��cU(-��>�`�H����;��vuw}{�2 ���k���<9��#��$��n�R���{�!�����B$9�[��lUt}����)� ���8������]�K#K������\�����%#����6�[��hj�&��v�h	g�
�?��-�'AHq��d
<��h�w���)�:�����Xd�s�u��-��b|����E�����x���c����g��Q��x�2E*r�D��e�7�lI6��:,���D�F�SaF~������-�C����/[�g����X�?��/�{%��W��3�����kK��,�2��H��}��`�D6���aI�f%*���qZ�9���0������\�LO�"�a�O���y?	��X�Pr�������	�WN��0���`�hL��TZ3��N� �|�a���[��#�~R�Y�������u.pO$
���;��8�p���4���Tx-��"������?Z]���K����>F�x�
�#;Y���K��O�76���l�-���D��&�Y������8S�Q��Zi�?a_�����I_'�Z�8�����"�J���Gq�D

��:�%���4�Q>Jh�W���
���I�f%B�5�oy�y�����3������)�<��IZ�?/�'-�+��b���R$#�W�����F]��	_��1������ #�vM�U���*�JTiT�B�d-seT
��p0�-�����@:��y������d������z5E`&8���E�j�g���_5�9e�%��F
�*�@���T�����*���
��<�d���f�~^E�Drr�Sp�R�To��"0S
|Dc����u����i���Su�)#)����f���J�^n�@�u����V:?(�D�������aE��u����PN9�Z,��>�P�+_�L`6�8���)��Z��r�;
�r�:7'R_ZA) ��k|����dn�a����R`s19��!3����;Jj��y�R���N��z���P���2K��=3���qu{�z���1�������[���5Ro/�X�I��^W�%p���P�|��!g-��#]�u����F�()=H�=W�c��C��s�"����*!�lS����D�������q�.����@Z����q>7������S�"�{�������`��(����������9�9Q�=�s ��=�t��VS���a
�����I
���.��/-���<�wHv����#��Is�6���B����� z�z�B�@��d2F�sFu=���B���{$����~�#�����E �]��t���l��6��*��U����?I������'2Y?�
���:�
���
������|=,����y������j(Xk�9��|�X���-��1v����9QK=$u�s��,�uX%��[BB��j���k��'�e��|��wSmj����i_���I?���}+T�2�����R0���X6�y��W�<��^��l,�M�(V-#6��o�-�J�b@
:'j�W�B*�%��:o�Ap1���*�?�����IB��$���N��UH���6J�]a������W�84���`��
Q
��E"t3J@R��Y^MZ��e�I|����:98R�9Q�Z\48��/��*x�}��K|�'�0��	�Z���T�|����Zw�^J�'��wAOu:��u������YX�Lbf��`�76�VsW�8JL��M�VN������uZ=U����u^���������[:oK��55qC�b
pfXI `��%r����ZvQ�9SH�=�u�C�PZB�W^f�2�����X�������������Z�y�t��8���������DfGE�Y.=oQ��+
8��)� �'@VH���$��P��a�6o��fQ �`��^kq1J,;OC��(��/d;3Gq�X����B�(d��S���\��k�$��#w���6�Ip�$�;*
������������5��/�p��0��)	[��.
&��#V������� A?��|gg���K�+�I��}�����u��Z	��<{���r���<��VS��d��@
V���I�o��N�l�?��B�]](8hu!�T�0(#%h�4���)r��7M�Twr�-�*�D�{]*p��]������a6�"��1�e
���Z�����-���J�H8A�.2��6Z�Z�:�f���`������^*I�+I�!2���
=��������d�-�)���F���la�6��s�z�8/��!����@�{�����������su�#�����?���Uk�^�����9�H�]����W�
�^^������|������Wx�����)� 9��**��Z�ge�EX��X�"YL��8~	���w�l���|��V]�HEv��M)Mw��d�1�
��z�yq�>���^c��[��!��B��-���{���"�c�}�6X�5I��S�9���<B�o�k�4G��	����v>�H���������>}/��������"*X�q|R������I�'�������Q�k�d���_����m�1f��)T���0�xN�Z�93����(<�,`}��yyg>�C.|�a��xG�Pw��<d�aRB�l!���O�����]	�T
�`��1�,�:�s����u��c�\����������cT�tm^���v�r����l���w�o%�?���0/[�������c��������?D����a�YXrT�%��vP��y/p(����(!3�A(X��I����^f�����}�99���n��(�������IW'����C}��5�d%���������Z,1�`R���������VY����rX�< ��P?�������s�C��%������!�7�'5]�����sr�u��������9�+���hcrTr����X=�K&��!i-��(#�9���kU�y�m�s�Q��jX��`�b���j����0L9G��-������c�K?&L�O��l�������Wc2P��AQ��9��O��3RW!�U�G�e�@�� ��k�`�:�q%cj@�[��:;mn-N(n��e��ja=�c�5 �P��������y�L|4&�$��:V��b�V���/j��SF�sL�.k�j�$�075�4Ad�����gX����F�j���>�@;�X�RxP����r�}�%`6����x��	�"=p�0��S���wN9�aR����`���D�A���N�Z����B������v>S�&����}��>�J@�^9V�0�cj��^O%��?������������~�}����Y?����������_����z�@,d��c�"�N`n����+���Q#�a�sYU+�@� ��WwW��k*��eX�cQo?X�q�FR
�P?Y�Kp��;���j��
�
H8�=��������6�i��A|mj�;5[#��_6(4��/�z�����
�^�R����I�D=����D#���h��?�_������-���;S�/�� ������@������[�����z:7��)���0��5R��"��Z�qf�\7�B�Q��!(X��/�Z��=�8u�{f�����@��	��6M|�~���?����@�=����zL6�V^/2^E`�!�'�n�B�8�9P�X(��P�B��z���C��,/����
PD�!�j@�]
pY�j�%�+$!l�>X�g������z��?���)����Yf%�P=�s�bD�Z�b��B���
�0XKKH�D
���:��3��cX���)����`��0������@&%\��%�H\�=gp.�c����k/��j��,<Eb)���)T����7k�`��1���B�����E0i	�����!_���PO>w�����[g!��7��?nJ@���C�$��������D�r��0�.vo��-B���<S����`2�d�l���Uc�j5�^�`�����enP�bF�g� ��~9�$���|S9H�!��r��w[�d�pyT ����u F�����9�X��:���Z��@�����)3��� ��p�c�h���g��0Xi�,��LQ�:V/#83`O��Z �$����T	js0����V
:�f���l��k%D��-��A*G!���:�C�z����x�� ��������Pj�i�1I�U�?�	��Z3�TG)���:V/#`��4k	�#���D�G�N1�)��:� t��Pg����]�a�a_��,	��l���$[�$��PK>J&���k:�/	�g�x&^$�sc�E���
��V�DoBI�]�M�ZN,~��B��Z��"u�����T,�T`��V:���B*9��S�~�[���0n��z����
���MgM��@-H��a���r��/@�zZ��������p�l��8�F(��@������)�[��d2s��$[6	�)w�Te�u�r~}��B���QI�A����(��	�[���q���R��@�c9t�.8u����������������Y?��5�K����@.��1U#�NE�D�J��h�Z1�Sj�^6,������G2�(�6��.�y!�Sk����2��,�8�ko��������8�uq�?��.������qt�.��7J��@�_b	�O6/o����
��H=�s!�J�J��&PS�^6|`:4N��l��xQ�u�<8km����D���[�wgq�}��+�l�~��|�����8ot�����@O��wqXl5=N���LCR(�7��"�(/��O�u�b�yw��KF�����U�'�]�D���������c��p7��C*P7�����0�'�`����M�*��u�������]���Q����Y}�2G���eH5K�
U#=���c�� ��r�g+e�P�|d����@�& ($������D��`�X�������2``�����(%�T��FpP �`��7��<�3A(_�N���e�!�q��)T��\������R���<oFB���p����E~H��K����u�Db�4������F�l��M�
A_��X�)�d W�dP=���������R����z<��abjKU�d}
Uc���� �9�%���H�\�����f���������.���R�$�0L��Z�xS\���!z_�2\�xVH ��~`R`!�l���Zg��$�C���*`�
�<��{���]�gmh�!�d>���~�g6�`�����W2��e�W�.nF0X���.��"�W[qp%�����7��C2%��u\���[$"������8@�zV����������H�y��v��\D����a����?9�4��N���+�u�ZFX�0�Im���vI"�����+9�@n��Q��� 8���|�4�VH��~� $�gOl�7�,$�C�!���|hY5���0�s���@^�j�_����`��s���(���b�2bL`7,��VL��@�$�M!����"��9� t���!�\|S��y=�& ����Y��(1����z@z@9��4M����M"7���������������X�����\����0X��q��0�`����v
�*	��3I|�v�n���%���$��LF�\K)W��jJ��~�&XkB����O���r��t6@��g@�(�zf����wpO9����k!���W�`�,��<y�~�&X+'�8������ix�Pp�L6�8`�T:o��pb�J���Qn���-����@YH��R��P^`�@�c9��i0&D��J���_������q����{_�8��.W����'����-�O�����}����gx�O�z����������	����%���c:k��UxOw�=OW^�~��0~��U�~`z�������#����xv��^�ex��������+"�}������������?����o��_���c/�^���]��4�KV���#���U���x}����\	���gE�����������Y���|��"�?�[]�_�F]%���K_�?�~���_�����u�5���}	��szys����"���������/��j_�5>���W�������K������j��:�`����4
���5�31S�b6�C��Vu���?h�pU������r/����n������
�-JfM�&\u!4")�]���^�A���<$c��!�$�g��	��8���6�>��e�T�����` 1����^�H�l���D6j�������9����[v��`K�vp�� {\������:��H�����[����'�$q*H�_^��g`�X[�2���H=�����\(T���C���<�2�*�#����`%
'gD�1b���l���;��1g*�hw.��E6'��d��s5?iZ`���1�d�������S��3%MXu�y��c�l���GY�Y��������e�Y+0����E��O�J��d��G1������
��('��C�"��X�����18�/��F��L����	YB�0;
���b�����P=�
�-��`%��j���z�P�|�`�e-j-�����p"r+^
��=x�L�qX,x~'(��as	������u���D[�Z��N��{��T
kQv>����n{)�@W���Y�!�;&�Q���-l���4O1�%��x���L����f�^$���B|�r��5�F�x�����Q�����u2Dla�����n�� �4i�{�������TG�Z?d���>cC|g��v]����������j@$����c3b��
������'p"v��C*����xC����&��0�����a�N��-��6Aqf��7�k;9��W�[��T-�`���J�%�`�aQ��H`N(V���r�{��t��VG}��}�����
kQ;9�����br��W(��c�JL��1���h
�d�_�F��Q��~`��p��R6.��_['��r���$p�U-�L��f���`��5�j���]�` 9���Ys��z	\3�)Xm����@b�71����5�<
#��[b��^�3���=�H����d6��~`��3>����lP��
��@���Df��;�8�@������_��ZLf-^)��k�RN�(�NX�s�V�IuZ��dj���H\�&v����b�V�Z��xK�xN�y.��R�|F�v�Z;����������$G�;��#���q�T����-����l�>.�0���`-2���,w��+-T����d�M�ZNl�1
7'�E�$��X�.����I6���0����[�w���)��eG�}��~ha&&��d�^b����r�ua�s��ym���O�/z�q�V
�|�����g4}��������
��R�T[��LJ�
T-m�o�<�Fj�b6�yd���J$��@$���h'�>�Y_0��;�n����+Y����$�j�~�����������dK���(Q��{�W)�����7����oq-[�����[��y����q��Y�e�v��4R �t!)OkA����x����m���G���j�>@��B;e$C���0'YW�j'��?����f��=s��B��g|{�y��u�HE"%2BB��%��i�*��$���[��O�h@��19_��`�d�s�������� ���L	�3���{�����<���YM(T��s�{rYP"r�V�))�P�|����-&']�	�r=��_��;���BJm.��F�$�j!?@���`,������D\=�ct�C`L��S_���,�|����B������b���3L�1
�K�
�J�����IeE�����.����y����c�5����"���z�����������N���Ux�JN|t���C��_��Bq�D0��r
U�0�A
��p�Q��
'��U�����`-J'���&JO9����l=��;o�\);R��
��0C4��la?D�\����@�J����C�����Q�z���ka�\!GL��u��Y����S������/sQq!�����W��N"(+mUZ����F�z�-�'Q�`�i��OB�l!?��u;����
U9�$[r�vB��\5.*Y�#����q�\l������X5X��6ZS�b:��c��/��1
��uR?Y�\k�u��u�\��;?�F3X�7]D��h����Z-���=��|jD�R;�������:W�A�������gb��p����u���q�}X���}�_��1�Ucv�S�O�Z�N�'+�iM�^��q?/�w�1��&���K����ja?��gI\l���2;����+���s,XM�h!&����\|<���4�kQ���8�+Md��x8��j��bNlrOQ����.zV����Gc!�V? -n����v�ao�^]������0����_�An�)�����*�S�?9t��XN�<T��h��f���1Y�R�+�`-.��%�����V���q����j��P������XoI�i�
R�b]*�?���;��/}�����1��~a�
�IJ��~����.Bi��R%x�����E�ip5��j����M/J�36Y��������Y?S��!}���5��"�6}��V��!�x&����5-�WeG�,'���Y�Yp�_1�6����U��aqO����a^�0?�w6Z���T��Z��{�z���K����O[���z�V�h7����:x������^p"�h��L�p�:�P�|�0O�Z'T���HDVY<����h������dK����Q9I�Z���C$�h�+9� Q��:�~���T�L!�XZ����fG�3pv��12�HE*O��:R'~6L��eL
��GA�b�����I��D�1�eW����w���x�\�$�p�H���e��th�����9�n��tx��S���.�PUc`=�$QH*B_��$�<s�
U\L�.�::���f��L�j�C~�b'[��9)��H:V��PW;��;���#n�l	�#t���p?M�&��]
G�V�5k��l�z	�{cM�����}������@�P=Fw��F�J���s?}�������e�^0�DXN$��n]I>
��Gz�x!�e�S�h������V���c��$c=���T�aMF4@�_�Yx;����#O�z��m�(�F�gI9��2�s������[	!iKr$�r"��D�9���]�3z�-�kq���@S`a�a_��?����%D�Ar�t��Z�:x_m����d��c�y�;L�j��W��[hH|=k-E�����`��@u�`w��j&���WN$���L)n�n�F����;+6[���j����"��v����?M��@@^/YRr���u�(��=��[�Q�3 �l��j����M%s)h�F�.8�+-��!0�-n��rb���E�$�r"��D�P��=�#]�����M�&�
~w���b-�OR{*>�X{��PZrEj'�Xtp9������Y'���gb�B��Yy�d�U�v��UQ5Xi=�OCMm��r���P�`���$�r"��D�6:W�fB��{�-�'��X�,r<�xh��))�Z��&w,���������A�NJ��U!�m(!L��q'��b���T�Vd�`�%�}d�^���������J`�+e�`-���~N��������������C������%�8���a���s�1�hJ���iEi?������xg���hz����u8�k�����`�e��3y�X��Iq��W�<��V��	�k^9+�'����J��L������*|��W�����x�?��a_��?I����!@i��#x�~����'[7�skP3���3�z��������}��t^�_����c��;yd����V'v�!27�j�b6$�{�T^�TS^���/p����)�$^~�I����������%�Rr���/x� ��r����'����wa�b���N��.���p[���5R1��X*u��8i��T�e����(��vzcs��xa�i�����'o}.89k���28i�z����dW�����j��BN.�|���,�~�M��~_���lo>E*2xb#�O��Q^��2!
���h���rz�^��K`�)_��`�qtZ��"j����zL>�j�y�r�����gb���P
�c/'p�WS�Bm��#Q
U�m����&@��I��R�����^Y��]YI�K�;D��
	���������At�r���K�����������h�����}�|��>�S��e�<�A�J�+8�l�_S��X�"_� �M�Q^����V�����p7|`j�%q)����[-��=��r@�����bt�o��#�C��En	�cBsd���-�6)T���l�lV?g0�J��c4L"�P=F��I+��������b��-	G��X`v������^]�]�$����8�b��la?D�����
D(G�:	���k��%��%vnsl�8#���%���X����^�V?�������9�=�K�Z�N
(/�l�S�uf3�a��xG�I����>�X��Z�rz�	�7oUN'��:r��dC�?�����?�2?1��|��)�Uc��2�����\������U�����P���$|�J-[L����Z���-���u1O.��5�q�NJ��C�^j�|���*��RK�.R�c�~�i������r����:V���n������d��.�Q���{e��9�<�F��j��|��+1=�w�l�I���}��B�l!?H���Rg/0f'��r���=N~m���$�2��fG���X`����ZDf�	L+a
��|u��Q�:V��q$��|N�E�P;���v���2�P�v������j/9��7��0�9��W ������n�n9���)�:�{(���b������������<���"��p��%3�*y�T_[���:Xm6S�������O�� n��10��
#��;�w���J����<C��-�	���S���aOBR9�j@T��M��k�&��+������o��\=����w..��Oo����\��u�=����_��D�����w��X����=A�s���4S�f6�v?�^�TaA$b��,;����W����v+E����z�"����������$)��E���3:Q��{���3jB=)+i�0?��$�����H\��L%�O�g�g�U�T��`?F��!�q��z
i<M�^����h�����x/P"���qR��p������b��L�('�Z�\;�p��:?�����Z7O	�a�t�*rW�����]��`.�M���(�|�7��t`A$[C*� 9U:��;��aDN���L^{���}N������X��>��M�%���^���;;O�j"����G]�l
������D���*�#�{�T��r��^�Ry�Z�"�7m�w���9f�8�����s�����RR,S��s��@�%?��\�Y'w�������&%�#
�c0<���jA�]����P�|����-r �WI�*��j��s�0��;�z$C�{Oi��V��� �c�L.��)CMJ'��:,�j�!B��d�^�3��s�s0��D��)�P=
�i|� 5K��k`����ct��9���+�Dj���Q(��Q��2z�}�Xk����0�7��lA?��b|Fb��K���(�4jr����+���lZ�k�S������Rb:]�\3�X5����t�*r���3#���`�rl�D�y=��+�j���-u��-S�9��{oy=���H�39�0l�N��-��=�#��k������#��J�8�K �M���g�+Q�B�=x�X5"���lcb'<���H����,�8#��$���v�$��"��D�!3
��~A����n�����tP�;fG��Pka?L�1U��oi/4��jr�H�>��'i���2_������u���h)���������)>�X��D�]�3��D�zE�6m���l���xG�9;����R*�Q;i�Z�R{L9��
���v����#��3���q���/����,��\����`-*o�r����+���l61�57�j9��wQ�k�;������g\.�[���{���)��>�J��w����~��dg�i-�j�;u@�CGz��G��r�[�~z��i��xK`�O����������#P�uPV:f��������r�5y
�"xhF����6d���g^��������������Y�a�p�}���!��w����E�$+�C��		���X��%�v�Wo���������g���W�}��wH_��/���Qq+�@89��Iv3=������>ggCo�E��(�gA\X�pe��_1�����C�
����7�SI^�`?U���8���8#�hM�
1�����b��2�Vc����7����C]	�-�L�z����������� �'<��z���/��Z��#	��D����S�l=�+��R�����k���l:�4��IB��$Z�*�����B:ph_��������q���[�G���=s�S;E��V���<S�V�3h�-<B1E�e���R��l�
��+J�X��}��G����x�
��T���x.��<��I:��4���6bI��2���$��q
m=�ck����g����h�[�5T�� ��2+�#����B��aMbn�M������I�%B���mL�!�G�y�
������-�E����Dc-�O����jYc�]@s\N��.�	|Lx��K�����3ga�`������F_�IN�;���.��<O�z�����S�����y"�U���&:�l�
���"��kB��#��E�k~��e��������9�s%�8��	�q�j�\�`!���j��C�������>
Uc0�G�=j�J.�b5���#�������Z�N��$�]Ur�u�	��������&�2R��A:!_��?M����K1�'Z�Q�N*���ggK���BiI��R����pv0SW8���)V��$f����d	s't���`|����	B����*I$W�@�EC���,��h������E������:��Z���N� VW���0MR'}X�\\=]Z���R@��k)?W�:?�[;^�j��M����������z
����3�U'Q����*I�V��]��!���5��z�-�o�;-���� �;�H��-�O3�u��<�X�*���I��T�����|C"Z��_�LL��j��������ef���V������,E�Z��>�_����4VI�����pU�k[`Z��x��}��D�_��>�#A_����Gj�����:i�z���lr1a=�h%�M�7f���CPGV�C8���0���&+����a�`���D�i.1kq;��K�V~�g,�\zfj����v���>y�}�;ulA?D�XM8�]kSC����`�\��b���u�c������g����l�m\7�J+!��Q���������\�Zk��W���n
��wd&�|��c9��hL��;o�L��-����;iH[�,�d�&��P$F����4�=�x�C�T���	M�%�O}0���@�d_�����>�'3������d���s��V?����������+�_���������~�����~�������%~=�������PK?�3��C�^PK]{IDmeta.xml��OO�0��|���5���Uc%FZ�8!�$nUj]�kW�C��~���Z����7���\��&���
�AX�����<��kt'nj���%p�d��=�6K�6�����[�����������_�|4������A�c<p���/�E������X�Q%����f���``p�����C
�e$���h����#���{�w^)���]����m��������gH��b�ZI�:@0B����T�t���/���eURR����;�����x�[��@\�(v��mw���W�U�]��w� #Nov�����������O��Kj�.����O��C����_��<��b�����vk ����AM�cf��r}��vXe.�E�������/PK4���PK]{ID
styles.xml�Ym��6��SZ H���lo+k/�m
l�4I[���%��D���u����dR"�O[��i����������p����K���� ,[����-��,"Y��~������|u����8�XX�8N!gEPM���gC)���D�g�(h��T5��M5W����wb����l�����iq��j,��i�<fS��
���	Y�#A:,�(�����y����~�_�O\�Z�j�
./9U�(t1�r���g���)h*?�mR������ �zQ�9.��y9�Q���_�drv����-���L��������"j��HlG���}���7������$�%U�I>y��i�3T�Au����-��{�?	�s"0o������(��!����p�N��Fs��Q��.�9����;Pgn��V�t���Y
Mx
B����c�����h�����\j�����J�9 �����\1+��:v��.���)D�Y���������CZG�(bH���]9��k
]��q������b�\�B�D8����*Qf���Krk��@�Sl�7(���:��)������x��U���r-�N�3�-d{�'E�B�D�Pv�L�4�g��Ky�V3���8�N7lK���P�����,�~��O%�~#��8��cb��r����2��XF��U/�����������:�N�)�5<G%�['�p�� ��US�/,w"R��N�e���o�����eI�������~����p������
��h��������^���K�����
hK�����/U���\U}P��"R����; �����!��	�E$!���B>��������R��|��]�����W���-��M;b�����?
����
B
�Q'������}z�z6������b�P������c����2�b/����V�Sb7�YY}�/KX)���$y����!Z���$�����sZ����|8�����c��������;'�H�����K�Z�����x����������E���j�������kM���m�*t�U
������(a�h����G�5.N�2�y����DiR��&:bj
�3����5�`�D#�=��&*A��P-��o{L�-4�P��g~/u�����n%:�����1�/�>M`��@�$%��$�S����)&w�9<Ob$�����|1�E�ve �������G{1�%���������f��/Iu8�H�Y�n���T�_y}�n�)����N�8t��r.�<���=��S��I�W�'e�Q���cL���n���b� |����d[��}#{m5�x3�r�=�kt{��	!_�x�aw��T>?Kx������b0!v��Q���-��|�:�-W9�VVs��S?
���ze��<���B�;��e����'�u�m����N��D�B�:���h��'RT��kW����n�yJ\Es�~A���[�+��������#yG�N�e�eM
���������J���"iW�����5�z����')�=�I��~|B�yOY}�'���>Pl�a�D�&����'Dk���:B�������i��B8Y��t����������y5	�|mi��y��]KG����/x��b�z��_.}�Z�>f�C�������������j�Vc�P�����m��oPKw�=^{
PK]{IDmanifest.rdf���n�0��<�e��@/r(��j��5�X/������VQ�������F3�����a�����T4c)%�Hh��+:�.���:���+��j���*�wn*9_��-7l���(x��<O�"��8qH���	�Bi��|9��	fWQt���y� =��:���
a�R��� ��@�	L��t��NK�3��Q9�����`����<`�+�������^����\��|�hz�czu����#�`�2�O��;y���.�����vDl@��g�����UG�PK��h��PK]{IDConfigurations2/toolpanel/PK]{IDConfigurations2/progressbar/PK]{ID'Configurations2/accelerator/current.xmlPKPK]{IDConfigurations2/floater/PK]{IDConfigurations2/images/Bitmaps/PK]{IDConfigurations2/toolbar/PK]{IDConfigurations2/menubar/PK]{IDConfigurations2/statusbar/PK]{IDConfigurations2/popupmenu/PK]{IDMETA-INF/manifest.xml�TKn� �����fU�8YT�	�P<v�`@�%�/��OU�������cXm�7{��"v�E>���������{�*6��*t����>�����QGC�4������hKd��^��.����X/�+��<��?��C��M�w�P�@���3-t����5\��{y,ouJJLO;j�����O4����)�w��`FPS~s�
�:�;�VSz���������A��?�sL�~��
�UO�9�"n,�AKe���Y����;��_�$����E��W��W��PKB�d� EPK]{ID�l9�..mimetypePK]{IDBZ�SK%K%TThumbnails/thumbnail.pngPK]{ID���w��$�%settings.xmlPK]{ID?�3��C�^+content.xmlPK]{ID4����nmeta.xmlPK]{IDw�=^{

|pstyles.xmlPK]{ID��h��/wmanifest.rdfPK]{IDnxConfigurations2/toolpanel/PK]{ID�xConfigurations2/progressbar/PK]{ID'�xConfigurations2/accelerator/current.xmlPK]{ID7yConfigurations2/floater/PK]{IDmyConfigurations2/images/Bitmaps/PK]{ID�yConfigurations2/toolbar/PK]{ID�yConfigurations2/menubar/PK]{IDzConfigurations2/statusbar/PK]{IDNzConfigurations2/popupmenu/PK]{IDB�d� E�zMETA-INF/manifest.xmlPKp�{
#12Jeremy Harris
jgh@wizmail.org
In reply to: Jeremy Harris (#11)
Re: Minor performance improvement in transition to external sort

On 09/02/14 17:11, Jeremy Harris wrote:

On 06/02/14 18:21, Jeff Janes wrote:

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets? We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a first pass.

Attached is version 2 of the patch, which fixes the performance on
constant-input.

Having beaten on this some more I'm prepared to abandon it.

The wallclock time, for random input, drifts up at larger N
(compared to the existing code) despite the number of comparisons
being consistently less.

Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.

It might be worthwhile for a seriously expensive comparison function;
say, more than 50 clocks. For integers and md5-strings it isn't.
--
Cheers,
Jeremy

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

#13Robert Haas
robertmhaas@gmail.com
In reply to: Jeremy Harris (#12)
Re: Minor performance improvement in transition to external sort

On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh@wizmail.org> wrote:

On 09/02/14 17:11, Jeremy Harris wrote:

On 06/02/14 18:21, Jeff Janes wrote:

Did you try sorting already-sorted, reverse
sorted, or pipe-organ shaped data sets? We will also need to test it on
strings. I usually use md5(random()::text) to generate strings for such
purposes, at least for a first pass.

Attached is version 2 of the patch, which fixes the performance on
constant-input.

Having beaten on this some more I'm prepared to abandon it.

The wallclock time, for random input, drifts up at larger N
(compared to the existing code) despite the number of comparisons
being consistently less.

Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.

Can you explain this further? This seems like an important clue that
could be useful when trying to optimize this code, but I'm a little
unclear which part of the operation has more cache misses with your
changes and why.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

#14Jeremy Harris
jgh@wizmail.org
In reply to: Robert Haas (#13)
Re: Minor performance improvement in transition to external sort

On 24/02/14 17:38, Robert Haas wrote:

On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh@wizmail.org> wrote:

Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.

Can you explain this further? This seems like an important clue that
could be useful when trying to optimize this code, but I'm a little
unclear which part of the operation has more cache misses with your
changes and why.

In the patched version, for the heapify operation the outer loop
starts at the last heap-parent tuple and works backward to the
start of the tuples array. A copy is taken of the SortTuple being
operated on for the inner loop to use. This copy suffers cache misses.

(The inner loop operates on elements between the copy source and the
end of the array).

In the original, the outer loop runs the array in increasing index
order. Again a copy is taken of the SortTuple for the inner loop
to use. This copy does not appear to take significant cache misses.

(The inner loop operates on elements between the copy source and
the start of the array).

--
Cheers,
Jeremy

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

#15Robert Haas
robertmhaas@gmail.com
In reply to: Jeremy Harris (#14)
Re: Minor performance improvement in transition to external sort

On Tue, Feb 25, 2014 at 2:55 PM, Jeremy Harris <jgh@wizmail.org> wrote:

On 24/02/14 17:38, Robert Haas wrote:

On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh@wizmail.org> wrote:

Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.

Can you explain this further? This seems like an important clue that
could be useful when trying to optimize this code, but I'm a little
unclear which part of the operation has more cache misses with your
changes and why.

In the patched version, for the heapify operation the outer loop
starts at the last heap-parent tuple and works backward to the
start of the tuples array. A copy is taken of the SortTuple being
operated on for the inner loop to use. This copy suffers cache misses.

(The inner loop operates on elements between the copy source and the
end of the array).

In the original, the outer loop runs the array in increasing index
order. Again a copy is taken of the SortTuple for the inner loop
to use. This copy does not appear to take significant cache misses.

(The inner loop operates on elements between the copy source and
the start of the array).

Do you have any theory as to why this happens in one case but not the other?

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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

#16Jeremy Harris
jgh@wizmail.org
In reply to: Robert Haas (#15)
Re: Minor performance improvement in transition to external sort

On 26/02/14 03:08, Robert Haas wrote:

On Tue, Feb 25, 2014 at 2:55 PM, Jeremy Harris <jgh@wizmail.org> wrote:

On 24/02/14 17:38, Robert Haas wrote:

On Thu, Feb 20, 2014 at 7:27 PM, Jeremy Harris <jgh@wizmail.org> wrote:

Run under cachegrind, it takes about N/10 last-level cache misses,
all for the new item being introduced to the heap. The existing
code takes none at all.

Can you explain this further? This seems like an important clue that
could be useful when trying to optimize this code, but I'm a little
unclear which part of the operation has more cache misses with your
changes and why.

In the patched version, for the heapify operation the outer loop
starts at the last heap-parent tuple and works backward to the
start of the tuples array. A copy is taken of the SortTuple being
operated on for the inner loop to use. This copy suffers cache misses.

(The inner loop operates on elements between the copy source and the
end of the array).

In the original, the outer loop runs the array in increasing index
order. Again a copy is taken of the SortTuple for the inner loop
to use. This copy does not appear to take significant cache misses.

(The inner loop operates on elements between the copy source and
the start of the array).

Do you have any theory as to why this happens in one case but not the other?

Nope. Only really wild stuff requiring the cpu memory channel
recognising the forward scan (despite the inner loop) and not
the backward one - and ignoring prefetch instructions, which I
experimented with.
--
Cheers,
Jeremy

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

#17Simon Riggs
simon@2ndQuadrant.com
In reply to: Jeff Janes (#6)
Re: Minor performance improvement in transition to external sort

On 6 February 2014 18:21, Jeff Janes <jeff.janes@gmail.com> wrote:

On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Thanks for working on this.

+1

Your patch isn't linked properly from the CF manager though.

If you like patches like this then there's a long(er) list of
optimizations already proposed previously around sorting. It would be
good to have someone work through them for external sorts. I believe
Noah is working on parallel internal sort (as an aside).

There's also an optimization possible for merge joins where we use the
output of the first sort as an additional filter on the second sort.
That can help when we're going to join two disjoint tables.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

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

#18Bruce Momjian
bruce@momjian.us
In reply to: Simon Riggs (#17)
Re: Minor performance improvement in transition to external sort

On Thu, Apr 10, 2014 at 06:03:15PM +0100, Simon Riggs wrote:

On 6 February 2014 18:21, Jeff Janes <jeff.janes@gmail.com> wrote:

On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Thanks for working on this.

+1

Your patch isn't linked properly from the CF manager though.

If you like patches like this then there's a long(er) list of
optimizations already proposed previously around sorting. It would be
good to have someone work through them for external sorts. I believe
Noah is working on parallel internal sort (as an aside).

There's also an optimization possible for merge joins where we use the
output of the first sort as an additional filter on the second sort.
That can help when we're going to join two disjoint tables.

Where should this be recorded? TODO? Commitfest manager?

--
Bruce Momjian <bruce@momjian.us> http://momjian.us
EnterpriseDB http://enterprisedb.com

+ Everyone has their own god. +

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

#19Robert Haas
robertmhaas@gmail.com
In reply to: Bruce Momjian (#18)
Re: Minor performance improvement in transition to external sort

On Wed, Apr 16, 2014 at 7:38 PM, Bruce Momjian <bruce@momjian.us> wrote:

On Thu, Apr 10, 2014 at 06:03:15PM +0100, Simon Riggs wrote:

On 6 February 2014 18:21, Jeff Janes <jeff.janes@gmail.com> wrote:

On Tue, Feb 4, 2014 at 2:22 PM, Jeremy Harris <jgh@wizmail.org> wrote:

The attached patch replaces the existing siftup method for heapify with
a siftdown method. Tested with random integers it does 18% fewer
compares and takes 10% less time for the heapify, over the work_mem
range 1024 to 1048576.

Thanks for working on this.

+1

Your patch isn't linked properly from the CF manager though.

If you like patches like this then there's a long(er) list of
optimizations already proposed previously around sorting. It would be
good to have someone work through them for external sorts. I believe
Noah is working on parallel internal sort (as an aside).

There's also an optimization possible for merge joins where we use the
output of the first sort as an additional filter on the second sort.
That can help when we're going to join two disjoint tables.

Where should this be recorded? TODO? Commitfest manager?

IIUC, the original patch was withdrawn; any remaining action items
should probably go to TODO. I'm not sure which specific idea you're
referring to, though.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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