Optimize partial TOAST decompression

Started by Binguo Baoover 6 years ago30 messages
#1Binguo Bao
djydewang@gmail.com
1 attachment(s)

Hi, hackers!
I'm a student participating in GSoC 2019 and my project is related to TOAST
slices.
When I'm getting familiar with the postgresql codebase, I find that
PG_DETOAST_DATUM_SLICE, when to run on a compressed TOAST entry, will fetch
all compressed data chunks then extract the relevant slice. Obviously, this
is unnecessary, we only need to fetch the data chunks we need.

The patch optimizes partial TOAST decompression.
For an example of the improvement possible, this trivial example:
---------------------------------------------------------------------
create table slicingtest (
id serial primary key,
a text
);

insert into slicingtest (a) select
repeat('1234567890-=abcdefghijklmnopqrstuvwxyz', 1000000) as a from
generate_series(1,100);
\timing
select sum(length(substr(a, 0, 20))) from slicingtest;
---------------------------------------------------------------------
environment: Linux 4.15.0-33-generic #36~16.04.1-Ubuntu x86_64 GNU/Linux
On master, I get
Time: 28.123 ms (Take ten times average)
With the patch, I get
Time: 2.306 ms (take ten times average)

This seems to have a 10x improvement. If the number of toast data chunks is
more, I believe that patch can play a greater role, there are about 200
related TOAST data chunks for each entry in the case.

Related discussion:
/messages/by-id/CACowWR07EDm7Y4m2kbhN_jnys=BBf9A6768RyQdKm_=NpkcaWg@mail.gmail.com

Best regards, Binguo Bao.

Attachments:

0001-Optimize-partial-TOAST-decompression.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression.patchDownload
From a7c99439ffe309526b57fe26ab367e4b7bf62f39 Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..7d30538 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -273,8 +273,11 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		/*
+		 * Be sure to get enough compressed slice
+		 * and compressed marker will get set automatically
+		 */
+		preslice = toast_fetch_datum_slice(attr, 0, sliceoffset + slicelength + 1);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -2031,7 +2034,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2076,9 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2091,7 +2094,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
-- 
2.7.4

#2Andrey Borodin
x4mmm@yandex-team.ru
In reply to: Binguo Bao (#1)
Re: Optimize partial TOAST decompression

Hi, Binguo!

2 июня 2019 г., в 19:48, Binguo Bao <djydewang@gmail.com> написал(а):

Hi, hackers!

....

This seems to have a 10x improvement. If the number of toast data chunks is more, I believe that patch can play a greater role, there are about 200 related TOAST data chunks for each entry in the case.

That's really cool that you could produce meaningful patch long before end of GSoC!

I'll describe what is going on a little:
1. We have compressed value, which resides in TOAST table.
2. We want only some fraction of this value. We want some prefix with length L.
3. Previously Paul Ramsey submitted patch that omits decompression of value beyond desired L bytes.
4. Binguo's patch tries to do not fetch compressed data which will not bee needed to decompressor. In fact it fetches L bytes from TOAST table.

This is not correct: L bytes of compressed data do not always can be decoded into at least L bytes of data. At worst we have one control byte per 8 bytes of literal bytes. This means at most we need (L*9 + 8) / 8 bytes with current pglz format.

Also, I'm not sure you use SET_VARSIZE_COMPRESSED correctly...

Best regards, Andrey Borodin.

#3Binguo Bao
djydewang@gmail.com
In reply to: Andrey Borodin (#2)
1 attachment(s)
Re: Optimize partial TOAST decompression

This is not correct: L bytes of compressed data do not always can be

decoded into at least L bytes of data. At worst we have one control byte
per 8 bytes of literal bytes. This means at most we need (L*9 + 8) / 8
bytes with current pglz format.

Good catch! I've corrected the related code in the patch.

Also, I'm not sure you use SET_VARSIZE_COMPRESSED correctly...

I followed the code in toast_fetch_datum function[1]https://github.com/postgres/postgres/blob/master/src/backend/access/heap/tuptoaster.c#L1898, and I didn't see any
wrong with it.

Best regards, Binguo Bao

[1]: https://github.com/postgres/postgres/blob/master/src/backend/access/heap/tuptoaster.c#L1898
https://github.com/postgres/postgres/blob/master/src/backend/access/heap/tuptoaster.c#L1898

Andrey Borodin <x4mmm@yandex-team.ru> 于2019年6月23日周日 下午5:23写道:

Show quoted text

Hi, Binguo!

2 июня 2019 г., в 19:48, Binguo Bao <djydewang@gmail.com> написал(а):

Hi, hackers!

....

This seems to have a 10x improvement. If the number of toast data chunks

is more, I believe that patch can play a greater role, there are about 200
related TOAST data chunks for each entry in the case.

That's really cool that you could produce meaningful patch long before end
of GSoC!

I'll describe what is going on a little:
1. We have compressed value, which resides in TOAST table.
2. We want only some fraction of this value. We want some prefix with
length L.
3. Previously Paul Ramsey submitted patch that omits decompression of
value beyond desired L bytes.
4. Binguo's patch tries to do not fetch compressed data which will not bee
needed to decompressor. In fact it fetches L bytes from TOAST table.

This is not correct: L bytes of compressed data do not always can be
decoded into at least L bytes of data. At worst we have one control byte
per 8 bytes of literal bytes. This means at most we need (L*9 + 8) / 8
bytes with current pglz format.

Also, I'm not sure you use SET_VARSIZE_COMPRESSED correctly...

Best regards, Andrey Borodin.

Attachments:

0001-Optimize-partial-TOAST-decompression-2.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression-2.patchDownload
From 505dcc4fdef18710c98718685180190056b4d9ed Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 34 +++++++++++++++++++++++++++-------
 1 file changed, 27 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..89ffc2d 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -262,6 +262,8 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 	struct varlena *result;
 	char	   *attrdata;
 	int32		attrsize;
+	int32 		needsize;
+	int32 		max_compressed_size;
 
 	if (VARATT_IS_EXTERNAL_ONDISK(attr))
 	{
@@ -273,8 +275,22 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		needsize = sliceoffset + slicelength;
+		if (needsize > (INT_MAX / 9))
+		{
+			/* Approximate to avoid overflow */
+			max_compressed_size = (needsize / 8 + 1) * 9;
+		}
+		else
+		{
+			max_compressed_size = (needsize * 9) / 8 + 1;
+		}
+
+		/*
+		 * Be sure to get enough compressed slice
+		 * and compressed marker will get set automatically
+		 */
+		preslice = toast_fetch_datum_slice(attr, 0, max_compressed_size);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -2031,7 +2047,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2089,9 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2091,7 +2107,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
-- 
2.7.4

#4Andrey Borodin
x4mmm@yandex-team.ru
In reply to: Binguo Bao (#3)
Re: Optimize partial TOAST decompression

Hi!
Please, do not use top-posting, i.e. reply style where you quote whole message under your response. It makes reading of archives terse.

24 июня 2019 г., в 7:53, Binguo Bao <djydewang@gmail.com> написал(а):

This is not correct: L bytes of compressed data do not always can be decoded into at least L bytes of data. At worst we have one control byte per 8 bytes of literal bytes. This means at most we need (L*9 + 8) / 8 bytes with current pglz format.

Good catch! I've corrected the related code in the patch.
...
<0001-Optimize-partial-TOAST-decompression-2.patch>

I've took a look into the code.
I think we should extract function for computation of max_compressed_size and put it somewhere along with pglz code. Just in case something will change something about pglz so that they would not forget about compression algorithm assumption.

Also I suggest just using 64 bit computation to avoid overflows. And I think it worth to check if max_compressed_size is whole data and use min of (max_compressed_size, uncompressed_data_size).

Also you declared needsize and max_compressed_size too far from use. But this will be solved by function extraction anyway.

Thanks!

Best regards, Andrey Borodin.

#5Binguo Bao
djydewang@gmail.com
In reply to: Andrey Borodin (#4)
1 attachment(s)
Re: Optimize partial TOAST decompression

Hi!

Andrey Borodin <x4mmm@yandex-team.ru> 于2019年6月29日周六 下午9:48写道:

Hi!
Please, do not use top-posting, i.e. reply style where you quote whole
message under your response. It makes reading of archives terse.

24 июня 2019 г., в 7:53, Binguo Bao <djydewang@gmail.com> написал(а):

This is not correct: L bytes of compressed data do not always can be

decoded into at least L bytes of data. At worst we have one control byte
per 8 bytes of literal bytes. This means at most we need (L*9 + 8) / 8
bytes with current pglz format.

Good catch! I've corrected the related code in the patch.
...
<0001-Optimize-partial-TOAST-decompression-2.patch>

I've took a look into the code.
I think we should extract function for computation of max_compressed_size
and put it somewhere along with pglz code. Just in case something will
change something about pglz so that they would not forget about compression
algorithm assumption.

Also I suggest just using 64 bit computation to avoid overflows. And I
think it worth to check if max_compressed_size is whole data and use min of
(max_compressed_size, uncompressed_data_size).

Also you declared needsize and max_compressed_size too far from use. But
this will be solved by function extraction anyway.

Thanks!

Best regards, Andrey Borodin.

Thanks for the suggestion.
I've extracted function for computation for max_compressed_size and put the
function into pg_lzcompress.c.

Best regards, Binguo Bao.

Attachments:

0001-Optimize-partial-TOAST-decompression-3.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression-3.patchDownload
From 79a1b4c292a0629df9d7ba3dc04e879aadca7a61 Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 24 +++++++++++++++++-------
 src/common/pg_lzcompress.c           | 22 ++++++++++++++++++++++
 src/include/common/pg_lzcompress.h   |  1 +
 3 files changed, 40 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..684f1b2 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -266,6 +266,7 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 	if (VARATT_IS_EXTERNAL_ONDISK(attr))
 	{
 		struct varatt_external toast_pointer;
+		int32 max_size;
 
 		VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
@@ -273,8 +274,13 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+												toast_pointer.va_rawsize);
+		/*
+		 * Be sure to get enough compressed slice
+		 * and compressed marker will get set automatically
+		 */
+		preslice = toast_fetch_datum_slice(attr, 0, max_size);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -2031,7 +2037,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2079,9 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2091,7 +2097,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b398..2b5f112 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,25 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ * 		Calculate the maximum size of the compressed slice corresponding to the
+ * 		raw slice. Return the maximum size, or raw size if maximum size is greater
+ * 		than raw size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size)
+{
+	int32 result;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	result = (int32)((int64)raw_slice_size * 9 + 8) / 8;
+	return result > raw_size ? raw_size : result;
+}
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 5555764..cda3e1d 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.7.4

#6Paul Ramsey
pramsey@cleverelephant.ca
In reply to: Binguo Bao (#5)
Re: Optimize partial TOAST decompression

On Mon, Jul 1, 2019 at 6:46 AM Binguo Bao <djydewang@gmail.com> wrote:

Andrey Borodin <x4mmm@yandex-team.ru> 于2019年6月29日周六 下午9:48写道:
I've took a look into the code.
I think we should extract function for computation of max_compressed_size and put it somewhere along with pglz code. Just in case something will change something about pglz so that they would not forget about compression algorithm assumption.

Also I suggest just using 64 bit computation to avoid overflows. And I think it worth to check if max_compressed_size is whole data and use min of (max_compressed_size, uncompressed_data_size).

Also you declared needsize and max_compressed_size too far from use. But this will be solved by function extraction anyway.

Thanks for the suggestion.
I've extracted function for computation for max_compressed_size and put the function into pg_lzcompress.c.

This looks good to me. A little commentary around why
pglz_maximum_compressed_size() returns a universally correct answer
(there's no way the compressed size can ever be larger than this
because...) would be nice for peasants like myself.

If you're looking to continue down this code line in your next patch,
the next TODO item is a little more involved: a user-land (ala
PG_DETOAST_DATUM) iterator API for access of TOAST datums would allow
the optimization of searching of large objects like JSONB types, and
so on, where the thing you are looking for is not at a known location
in the object. So, things like looking for a particular substring in a
string, or looking for a particular key in a JSONB. "Iterate until you
find the thing." would allow optimization of some code lines that
currently require full decompression of the objects.

P.

#7Binguo Bao
djydewang@gmail.com
In reply to: Paul Ramsey (#6)
1 attachment(s)
Re: Optimize partial TOAST decompression

Paul Ramsey <pramsey@cleverelephant.ca> 于2019年7月2日周二 下午10:46写道:

This looks good to me. A little commentary around why
pglz_maximum_compressed_size() returns a universally correct answer
(there's no way the compressed size can ever be larger than this
because...) would be nice for peasants like myself.

If you're looking to continue down this code line in your next patch,
the next TODO item is a little more involved: a user-land (ala
PG_DETOAST_DATUM) iterator API for access of TOAST datums would allow
the optimization of searching of large objects like JSONB types, and
so on, where the thing you are looking for is not at a known location
in the object. So, things like looking for a particular substring in a
string, or looking for a particular key in a JSONB. "Iterate until you
find the thing." would allow optimization of some code lines that
currently require full decompression of the objects.

P.

Thanks for your comment. I've updated the patch.
As for the iterator API, I've implemented a de-TOAST iterator actually[0]/messages/by-id/CAL-OGks_onzpc9M9bXPCztMofWULcFkyeCeKiAgXzwRL8kXiag@mail.gmail.com.
And I’m looking for more of its application scenarios and perfecting it.
Any comments would be much appreciated.

Best Regards, Binguo Bao.

[0]: /messages/by-id/CAL-OGks_onzpc9M9bXPCztMofWULcFkyeCeKiAgXzwRL8kXiag@mail.gmail.com
/messages/by-id/CAL-OGks_onzpc9M9bXPCztMofWULcFkyeCeKiAgXzwRL8kXiag@mail.gmail.com

Attachments:

0001-Optimize-partial-TOAST-decompression-4.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression-4.patchDownload
From 2e4e2838937ec6fa1404fe529e7ed303e391d1b2 Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 24 +++++++++++++++++-------
 src/common/pg_lzcompress.c           | 26 ++++++++++++++++++++++++++
 src/include/common/pg_lzcompress.h   |  1 +
 3 files changed, 44 insertions(+), 7 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..684f1b2 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -266,6 +266,7 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 	if (VARATT_IS_EXTERNAL_ONDISK(attr))
 	{
 		struct varatt_external toast_pointer;
+		int32 max_size;
 
 		VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
@@ -273,8 +274,13 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+												toast_pointer.va_rawsize);
+		/*
+		 * Be sure to get enough compressed slice
+		 * and compressed marker will get set automatically
+		 */
+		preslice = toast_fetch_datum_slice(attr, 0, max_size);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -2031,7 +2037,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2079,9 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2091,7 +2097,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b398..80ed17a 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,29 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ * 		Calculate the maximum size of the compressed slice corresponding to the
+ * 		raw slice. Return the maximum size, or raw size if maximum size is larger
+ * 		than raw size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size)
+{
+	int32 result;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	result = (int32)((int64)raw_slice_size * 9 + 8) / 8;
+
+	/*
+	 * Note that compressed size will never be larger than raw size.
+	 */
+	return result > raw_size ? raw_size : result;
+}
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 5555764..cda3e1d 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.7.4

#8Andrey Borodin
x4mmm@yandex-team.ru
In reply to: Binguo Bao (#7)
Re: Optimize partial TOAST decompression

3 июля 2019 г., в 18:06, Binguo Bao <djydewang@gmail.com> написал(а):

Paul Ramsey <pramsey@cleverelephant.ca> 于2019年7月2日周二 下午10:46写道:
This looks good to me. A little commentary around why
pglz_maximum_compressed_size() returns a universally correct answer
(there's no way the compressed size can ever be larger than this
because...) would be nice for peasants like myself.
...

Thanks for your comment. I've updated the patch.

Thanks Biguo and Paul! From my POV patch looks ready for committer, so I switched state on CF.

Best regards, Andrey Borodin.

#9Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Andrey Borodin (#8)
Re: Optimize partial TOAST decompression

On Thu, Jul 04, 2019 at 11:10:24AM +0200, Andrey Borodin wrote:

3 июля 2019 г., в 18:06, Binguo Bao <djydewang@gmail.com> написал(а):

Paul Ramsey <pramsey@cleverelephant.ca> 于2019年7月2日周二 下午10:46写道:
This looks good to me. A little commentary around why
pglz_maximum_compressed_size() returns a universally correct answer
(there's no way the compressed size can ever be larger than this
because...) would be nice for peasants like myself.
...

Thanks for your comment. I've updated the patch.

Thanks Biguo and Paul! From my POV patch looks ready for committer, so I switched state on CF.

I've done a bit of testing and benchmaring on this patch today, and
there's a bug somewhere, making it look like there are corrupted data.

What I'm seeing is this:

CREATE TABLE t (a text);

-- attached is data for one row
COPY t FROM '/tmp/t.data';

SELECT length(substr(a,1000)) from t;
psql: ERROR: compressed data is corrupted

SELECT length(substr(a,0,1000)) from t;
length
--------
999
(1 row)

SELECT length(substr(a,1000)) from t;
psql: ERROR: invalid memory alloc request size 2018785106

That's quite bizarre behavior - it does work with a prefix, but not with
suffix. And the exact ERROR changes after the prefix query. (Of course,
on master it works in all cases.)

The backtrace (with the patch applied) looks like this:

#0 toast_decompress_datum (attr=0x12572e0) at tuptoaster.c:2291
#1 toast_decompress_datum (attr=0x12572e0) at tuptoaster.c:2277
#2 0x00000000004c3b08 in heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0, slicelength=-1) at tuptoaster.c:315
#3 0x000000000085c1e5 in pg_detoast_datum_slice (datum=<optimized out>, first=<optimized out>, count=<optimized out>) at fmgr.c:1767
#4 0x0000000000833b7a in text_substring (str=133761519127512, start=0, length=<optimized out>, length_not_specified=<optimized out>) at varlena.c:956
...

I've only observed this with a very small number of rows (the data is
generated randomly with different compressibility etc.), so I'm only
attaching one row that exhibits this issue.

My guess is toast_fetch_datum_slice() gets confused by the headers or
something, or something like that. FWIW the new code added to this
function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#10Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tomas Vondra (#9)
2 attachment(s)
Re: Optimize partial TOAST decompression

Of course, I forgot to attach the files, so here they are.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachments:

t.data.gzapplication/gzipDownload
bt.txttext/plain; charset=us-asciiDownload
#11Binguo Bao
djydewang@gmail.com
In reply to: Tomas Vondra (#9)
1 attachment(s)
Re: Optimize partial TOAST decompression

Tomas Vondra <tomas.vondra@2ndquadrant.com> 于2019年7月5日周五 上午1:46写道:

I've done a bit of testing and benchmaring on this patch today, and
there's a bug somewhere, making it look like there are corrupted data.

What I'm seeing is this:

CREATE TABLE t (a text);

-- attached is data for one row
COPY t FROM '/tmp/t.data';

SELECT length(substr(a,1000)) from t;
psql: ERROR: compressed data is corrupted

SELECT length(substr(a,0,1000)) from t;
length
--------
999
(1 row)

SELECT length(substr(a,1000)) from t;
psql: ERROR: invalid memory alloc request size 2018785106

That's quite bizarre behavior - it does work with a prefix, but not with
suffix. And the exact ERROR changes after the prefix query. (Of course,
on master it works in all cases.)

The backtrace (with the patch applied) looks like this:

#0 toast_decompress_datum (attr=0x12572e0) at tuptoaster.c:2291
#1 toast_decompress_datum (attr=0x12572e0) at tuptoaster.c:2277
#2 0x00000000004c3b08 in heap_tuple_untoast_attr_slice (attr=<optimized
out>, sliceoffset=0, slicelength=-1) at tuptoaster.c:315
#3 0x000000000085c1e5 in pg_detoast_datum_slice (datum=<optimized out>,
first=<optimized out>, count=<optimized out>) at fmgr.c:1767
#4 0x0000000000833b7a in text_substring (str=133761519127512, start=0,
length=<optimized out>, length_not_specified=<optimized out>) at
varlena.c:956
...

I've only observed this with a very small number of rows (the data is
generated randomly with different compressibility etc.), so I'm only
attaching one row that exhibits this issue.

My guess is toast_fetch_datum_slice() gets confused by the headers or
something, or something like that. FWIW the new code added to this
function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, Tomas!
Thanks for your testing and the suggestion.

That's quite bizarre behavior - it does work with a prefix, but not with

suffix. And the exact ERROR changes after the prefix query.

I think bug is caused by "#2 0x00000000004c3b08 in
heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0,
slicelength=-1) at tuptoaster.c:315",
since I ignore the case where slicelength is negative, and I've appended
some comments for heap_tuple_untoast_attr_slice for the case.

FWIW the new code added to this

function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

I've added more comments to explain the code's behavior.
Besides, I also modified the macro "TOAST_COMPRESS_RAWDATA" to
"TOAST_COMPRESS_DATA" since
it is used to get toast compressed data rather than raw data.

Best Regards, Binguo Bao.

Attachments:

0001-Optimize-partial-TOAST-decompression-5.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression-5.patchDownload
From bcf04278b4d5956cd5f5fdab0d954b36adfd0022 Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 57 ++++++++++++++++++++++++++++--------
 src/common/pg_lzcompress.c           | 26 ++++++++++++++++
 src/include/common/pg_lzcompress.h   |  1 +
 3 files changed, 72 insertions(+), 12 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..1eb6cca 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -61,7 +61,8 @@ typedef struct toast_compress_header
  */
 #define TOAST_COMPRESS_HDRSZ		((int32) sizeof(toast_compress_header))
 #define TOAST_COMPRESS_RAWSIZE(ptr) (((toast_compress_header *) (ptr))->rawsize)
-#define TOAST_COMPRESS_RAWDATA(ptr) \
+#define TOAST_COMPRESS_SIZE(ptr)	((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)
+#define TOAST_COMPRESS_DATA(ptr) \
 	(((char *) (ptr)) + TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_SET_RAWSIZE(ptr, len) \
 	(((toast_compress_header *) (ptr))->rawsize = (len))
@@ -252,6 +253,8 @@ heap_tuple_untoast_attr(struct varlena *attr)
  *
  *		Public entry point to get back part of a toasted value
  *		from compression or external storage.
+ *
+ * Note if slicelength is negative, return suffix of the value.
  * ----------
  */
 struct varlena *
@@ -273,8 +276,23 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		/*
+		 * If only need the prefix slice, fetch enough datums to decompress.
+		 * Otherwise, fetch all datums.
+		 */
+		if (slicelength > 0 && sliceoffset >= 0)
+		{
+			int32 max_size;
+			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+													TOAST_COMPRESS_SIZE(attr));
+			/*
+			 * Be sure to get enough compressed slice
+			 * and compressed marker will get set automatically
+			 */
+			preslice = toast_fetch_datum_slice(attr, 0, max_size);
+		}
+		else
+			preslice = toast_fetch_datum(attr);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -1391,7 +1409,7 @@ toast_compress_datum(Datum value)
 	 */
 	len = pglz_compress(VARDATA_ANY(DatumGetPointer(value)),
 						valsize,
-						TOAST_COMPRESS_RAWDATA(tmp),
+						TOAST_COMPRESS_DATA(tmp),
 						PGLZ_strategy_default);
 	if (len >= 0 &&
 		len + TOAST_COMPRESS_HDRSZ < valsize - 2)
@@ -2031,7 +2049,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2091,10 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum,
+	 * since we can decompress the prefix raw data from it.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2086,12 +2105,26 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 		length = 0;
 	}
 
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) && length > 0)
+	{
+		/*
+		 * If we are going to fetch the compressed external datum slice
+		 * at the start of the object, also should fetch rawsize field used
+		 * to record the size of the raw data.
+		 */
+		length = length + sizeof(int32);
+	}
+
 	if (((sliceoffset + length) > attrsize) || length < 0)
 		length = attrsize - sliceoffset;
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
@@ -2274,8 +2307,8 @@ toast_decompress_datum(struct varlena *attr)
 		palloc(TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 	SET_VARSIZE(result, TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 
-	if (pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
-						VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
+	if (pglz_decompress(TOAST_COMPRESS_DATA(attr),
+						TOAST_COMPRESS_SIZE(attr),
 						VARDATA(result),
 						TOAST_COMPRESS_RAWSIZE(attr), true) < 0)
 		elog(ERROR, "compressed data is corrupted");
@@ -2301,7 +2334,7 @@ toast_decompress_datum_slice(struct varlena *attr, int32 slicelength)
 
 	result = (struct varlena *) palloc(slicelength + VARHDRSZ);
 
-	rawsize = pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
+	rawsize = pglz_decompress(TOAST_COMPRESS_DATA(attr),
 							  VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
 							  VARDATA(result),
 							  slicelength, false);
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b398..ac7d66d 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,29 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ * 		Calculate the maximum size of the compressed slice corresponding to the
+ * 		raw slice. Return the maximum size, or total compressed size if maximum
+ * 		size is larger than total compressed size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 raw_slice_size, int32 total_compressed_size)
+{
+	int32 result;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	result = (int32)((int64)raw_slice_size * 9 + 8) / 8;
+
+	/*
+	 * Note that slice compressed size will never be larger than total compressed size.
+	 */
+	return result > total_compressed_size ? total_compressed_size: result;
+}
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 5555764..cda3e1d 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.7.4

#12Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Binguo Bao (#11)
4 attachment(s)
Re: Optimize partial TOAST decompression

On Sat, Jul 06, 2019 at 02:27:56AM +0800, Binguo Bao wrote:

Hi, Tomas!
Thanks for your testing and the suggestion.

That's quite bizarre behavior - it does work with a prefix, but not with

suffix. And the exact ERROR changes after the prefix query.

I think bug is caused by "#2 0x00000000004c3b08 in
heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0,
slicelength=-1) at tuptoaster.c:315",
since I ignore the case where slicelength is negative, and I've appended
some comments for heap_tuple_untoast_attr_slice for the case.

FWIW the new code added to this

function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

I've added more comments to explain the code's behavior.
Besides, I also modified the macro "TOAST_COMPRESS_RAWDATA" to
"TOAST_COMPRESS_DATA" since
it is used to get toast compressed data rather than raw data.

Thanks, this seems to address the issue - I can no longer reproduce the
crashes, allowing the benchmark to complete. I'm attaching the script I
used and spreadsheet with a summary of results.

For the cases I've tested (100k - 10M values, different compressibility,
different prefix/length values), the results are kinda mixed - many
cases got much faster (~2x), but other cases got slower too. We're
however talking about queries taking a couple of miliseconds, so in
absolute numbers the differences are small.

That does not mean the optimization is useless - but the example shared
at the beginning of this thread is quite extreme, as the values are
extremely compressible. Each value is ~38MB (in plaintext), but a table
with 100 such values has only ~40MB. Tha's 100:1 compression ratio,
which I think is not typical for real-world data sets.

The data I've used are less extreme, depending on the fraction of random
data in values.

I went through the code too. I've reworder a couple of comments and code
style issues, but there are a couple of more serious issues.

1) Why rename TOAST_COMPRESS_RAWDATA to TOAST_COMPRESS_DATA?

This seems unnecessary, and it discards the clear hint that it's about
accessing the *raw* data, and the relation to TOAST_COMPRESS_RAWSIZE.
IMHO we should keep the original naming.

2) pglz_maximum_compressed_size signatures are confusing

There are two places with pglz_maximum_compressed_size signature, and
those places are kinda out of sync when it comes to parameter names:

int32
pglz_maximum_compressed_size(int32 raw_slice_size,
int32 total_compressed_size)

extern
int32 pglz_maximum_compressed_size(int32 raw_slice_size,
int32 raw_size);

Also, pg_lzcompress.c has no concept of a "slice" because it only deals
with simple compression, slicing is responsibility of the tuptoaster. So
we should not mix those two, not even in comments.

I propose tweaks per the attached patch - I think it makes the code
clearer, and it's mostly cosmetic stuff. But I haven't tested the
changes beyond "it compiles".

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachments:

0001-Optimize-partial-TOAST-decompression.patchtext/plain; charset=us-asciiDownload
From d50ae41bf1d1c4e2786a55a610300606c1ec43a5 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Sat, 6 Jul 2019 15:41:37 +0200
Subject: [PATCH 1/2] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 57 ++++++++++++++++++++++------
 src/common/pg_lzcompress.c           | 26 +++++++++++++
 src/include/common/pg_lzcompress.h   |  1 +
 3 files changed, 72 insertions(+), 12 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91d1c..1eb6ccaca2 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -61,7 +61,8 @@ typedef struct toast_compress_header
  */
 #define TOAST_COMPRESS_HDRSZ		((int32) sizeof(toast_compress_header))
 #define TOAST_COMPRESS_RAWSIZE(ptr) (((toast_compress_header *) (ptr))->rawsize)
-#define TOAST_COMPRESS_RAWDATA(ptr) \
+#define TOAST_COMPRESS_SIZE(ptr)	((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)
+#define TOAST_COMPRESS_DATA(ptr) \
 	(((char *) (ptr)) + TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_SET_RAWSIZE(ptr, len) \
 	(((toast_compress_header *) (ptr))->rawsize = (len))
@@ -252,6 +253,8 @@ heap_tuple_untoast_attr(struct varlena *attr)
  *
  *		Public entry point to get back part of a toasted value
  *		from compression or external storage.
+ *
+ * Note if slicelength is negative, return suffix of the value.
  * ----------
  */
 struct varlena *
@@ -273,8 +276,23 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		/*
+		 * If only need the prefix slice, fetch enough datums to decompress.
+		 * Otherwise, fetch all datums.
+		 */
+		if (slicelength > 0 && sliceoffset >= 0)
+		{
+			int32 max_size;
+			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+													TOAST_COMPRESS_SIZE(attr));
+			/*
+			 * Be sure to get enough compressed slice
+			 * and compressed marker will get set automatically
+			 */
+			preslice = toast_fetch_datum_slice(attr, 0, max_size);
+		}
+		else
+			preslice = toast_fetch_datum(attr);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -1391,7 +1409,7 @@ toast_compress_datum(Datum value)
 	 */
 	len = pglz_compress(VARDATA_ANY(DatumGetPointer(value)),
 						valsize,
-						TOAST_COMPRESS_RAWDATA(tmp),
+						TOAST_COMPRESS_DATA(tmp),
 						PGLZ_strategy_default);
 	if (len >= 0 &&
 		len + TOAST_COMPRESS_HDRSZ < valsize - 2)
@@ -2031,7 +2049,8 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datum slices at the start of the object.
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2091,10 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum,
+	 * since we can decompress the prefix raw data from it.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2086,12 +2105,26 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 		length = 0;
 	}
 
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) && length > 0)
+	{
+		/*
+		 * If we are going to fetch the compressed external datum slice
+		 * at the start of the object, also should fetch rawsize field used
+		 * to record the size of the raw data.
+		 */
+		length = length + sizeof(int32);
+	}
+
 	if (((sliceoffset + length) > attrsize) || length < 0)
 		length = attrsize - sliceoffset;
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	} else {
+		SET_VARSIZE(result, length + VARHDRSZ);
+	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
@@ -2274,8 +2307,8 @@ toast_decompress_datum(struct varlena *attr)
 		palloc(TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 	SET_VARSIZE(result, TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 
-	if (pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
-						VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
+	if (pglz_decompress(TOAST_COMPRESS_DATA(attr),
+						TOAST_COMPRESS_SIZE(attr),
 						VARDATA(result),
 						TOAST_COMPRESS_RAWSIZE(attr), true) < 0)
 		elog(ERROR, "compressed data is corrupted");
@@ -2301,7 +2334,7 @@ toast_decompress_datum_slice(struct varlena *attr, int32 slicelength)
 
 	result = (struct varlena *) palloc(slicelength + VARHDRSZ);
 
-	rawsize = pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
+	rawsize = pglz_decompress(TOAST_COMPRESS_DATA(attr),
 							  VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
 							  VARDATA(result),
 							  slicelength, false);
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b3987d0..ac7d66db77 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,29 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ * 		Calculate the maximum size of the compressed slice corresponding to the
+ * 		raw slice. Return the maximum size, or total compressed size if maximum
+ * 		size is larger than total compressed size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 raw_slice_size, int32 total_compressed_size)
+{
+	int32 result;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	result = (int32)((int64)raw_slice_size * 9 + 8) / 8;
+
+	/*
+	 * Note that slice compressed size will never be larger than total compressed size.
+	 */
+	return result > total_compressed_size ? total_compressed_size: result;
+}
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 555576436c..cda3e1d364 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.20.1

0002-review-reworks.patchtext/plain; charset=us-asciiDownload
From 34a17fd6df4f531527b976df043aed6fb5b6add0 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Sat, 6 Jul 2019 16:39:17 +0200
Subject: [PATCH 2/2] review reworks

---
 src/backend/access/heap/tuptoaster.c | 47 +++++++++++++++-------------
 src/common/pg_lzcompress.c           | 19 +++++------
 src/include/common/pg_lzcompress.h   |  2 +-
 3 files changed, 37 insertions(+), 31 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 1eb6ccaca2..809a52196c 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -62,7 +62,7 @@ typedef struct toast_compress_header
 #define TOAST_COMPRESS_HDRSZ		((int32) sizeof(toast_compress_header))
 #define TOAST_COMPRESS_RAWSIZE(ptr) (((toast_compress_header *) (ptr))->rawsize)
 #define TOAST_COMPRESS_SIZE(ptr)	((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)
-#define TOAST_COMPRESS_DATA(ptr) \
+#define TOAST_COMPRESS_RAWDATA(ptr) \
 	(((char *) (ptr)) + TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_SET_RAWSIZE(ptr, len) \
 	(((toast_compress_header *) (ptr))->rawsize = (len))
@@ -254,7 +254,7 @@ heap_tuple_untoast_attr(struct varlena *attr)
  *		Public entry point to get back part of a toasted value
  *		from compression or external storage.
  *
- * Note if slicelength is negative, return suffix of the value.
+ * Note: when slicelength is negative, return suffix of the value.
  * ----------
  */
 struct varlena *
@@ -277,17 +277,23 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
 		/*
-		 * If only need the prefix slice, fetch enough datums to decompress.
-		 * Otherwise, fetch all datums.
+		 * When a prefix of the value is requested, fetch enough slices to
+		 * decompress. Otherwise, fetch all slices.
 		 */
 		if (slicelength > 0 && sliceoffset >= 0)
 		{
 			int32 max_size;
+
+			/*
+			 * Determine maximum amount of compressed data needed for a prefix
+			 * of a given length (after decompression).
+			 */
 			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
 													TOAST_COMPRESS_SIZE(attr));
+
 			/*
-			 * Be sure to get enough compressed slice
-			 * and compressed marker will get set automatically
+			 * Fetch enough compressed slices, compressed marker will get set
+			 * automatically.
 			 */
 			preslice = toast_fetch_datum_slice(attr, 0, max_size);
 		}
@@ -1409,7 +1415,7 @@ toast_compress_datum(Datum value)
 	 */
 	len = pglz_compress(VARDATA_ANY(DatumGetPointer(value)),
 						valsize,
-						TOAST_COMPRESS_DATA(tmp),
+						TOAST_COMPRESS_RAWDATA(tmp),
 						PGLZ_strategy_default);
 	if (len >= 0 &&
 		len + TOAST_COMPRESS_HDRSZ < valsize - 2)
@@ -2050,7 +2056,8 @@ toast_fetch_datum(struct varlena *attr)
  *	in the toast relation
  *
  *	Note that this function supports non-compressed external datums
- *	and compressed external datum slices at the start of the object.
+ *	and compressed external datums (in which case the requrested slice
+ *  has to be a prefix, i.e. sliceoffset has to be 0).
  * ----------
  */
 static struct varlena *
@@ -2092,7 +2099,8 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 
 	/*
 	 * It's meaningful to fetch slices at the start of a compressed datum,
-	 * since we can decompress the prefix raw data from it.
+	 * since we can decompress the prefix raw data without decompressing the
+	 * whole value.
 	 */
 	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
@@ -2105,26 +2113,23 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 		length = 0;
 	}
 
+	/*
+	 * When fetching a prefix of a compressed external datum, account for
+	 * the rawsize tracking amount of raw data (it's stored at the beginning
+	 * as an int32 value).
+	 */
 	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) && length > 0)
-	{
-		/*
-		 * If we are going to fetch the compressed external datum slice
-		 * at the start of the object, also should fetch rawsize field used
-		 * to record the size of the raw data.
-		 */
 		length = length + sizeof(int32);
-	}
 
 	if (((sliceoffset + length) > attrsize) || length < 0)
 		length = attrsize - sliceoffset;
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer)) {
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
-	} else {
+	else
 		SET_VARSIZE(result, length + VARHDRSZ);
-	}
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
@@ -2307,7 +2312,7 @@ toast_decompress_datum(struct varlena *attr)
 		palloc(TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 	SET_VARSIZE(result, TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 
-	if (pglz_decompress(TOAST_COMPRESS_DATA(attr),
+	if (pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
 						TOAST_COMPRESS_SIZE(attr),
 						VARDATA(result),
 						TOAST_COMPRESS_RAWSIZE(attr), true) < 0)
@@ -2334,7 +2339,7 @@ toast_decompress_datum_slice(struct varlena *attr, int32 slicelength)
 
 	result = (struct varlena *) palloc(slicelength + VARHDRSZ);
 
-	rawsize = pglz_decompress(TOAST_COMPRESS_DATA(attr),
+	rawsize = pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
 							  VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
 							  VARDATA(result),
 							  slicelength, false);
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index ac7d66db77..18766ade02 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -773,27 +773,28 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 }
 
 
-
 /* ----------
  * pglz_max_compressed_size -
  *
- * 		Calculate the maximum size of the compressed slice corresponding to the
- * 		raw slice. Return the maximum size, or total compressed size if maximum
- * 		size is larger than total compressed size.
+ *		Calculate the maximum compressed size for a given amount of raw data.
+ *		Return the maximum size, or total compressed size if maximum size is
+ *		larger than total compressed size.
  * ----------
  */
 int32
-pglz_maximum_compressed_size(int32 raw_slice_size, int32 total_compressed_size)
+pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size)
 {
-	int32 result;
+	int32 compressed_size;
 
 	/*
 	 * Use int64 to prevent overflow during calculation.
 	 */
-	result = (int32)((int64)raw_slice_size * 9 + 8) / 8;
+	compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;
 
 	/*
-	 * Note that slice compressed size will never be larger than total compressed size.
+	 * Maximum compressed size can't be larger than total compressed size.
 	 */
-	return result > total_compressed_size ? total_compressed_size: result;
+	compressed_size = Min(compressed_size, total_compressed_size);
+
+	return compressed_size;
 }
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index cda3e1d364..e59fe2eaea 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,6 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
-extern int32 pglz_maximum_compressed_size(int32 raw_slice_size, int32 raw_size);
+extern int32 pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.20.1

random-bench2.shapplication/x-shDownload
comparison.odsapplication/vnd.oasis.opendocument.spreadsheetDownload
PKbi�N�l9�..mimetypeapplication/vnd.oasis.opendocument.spreadsheetPKbi�N��_��"�"Thumbnails/thumbnail.png�PNG


IHDR�:<PLTE

	 	$48&) < .%50"""/0/0((0006<8:33888JUF'T.X0cj!w$#D-&L2)Y7;B=0\='f:'r>0`>5[A.k@*{C5gD7uJ>{QKYL44T//[;;kezxc77DDDEJGFMHKLKGVLVJJTUUUXVYSS[[[D`LJhSC|T[b]Rt\^e`W|bhGGdYYuHHyTTgggirlnupvggrrrtzuv|xzrr{{{�*�5�.�2�5�B.�I1�N;�R6�S:�[=�`>�bF�YD�]L�`J�b]�hR�hG�cC�hT�lY�qP�nX�ua�le�ql�zx�{c�xa�zr�V�wb�~~��f��y��~��k��v��z������  �""���%%�))�LL�[[�TT�hh�xx�hh�ww�[[�jj�ss�ff�zz����..�22�11����44�;;�nn�ss�yy��~~���������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������������0:��IDATx��]���f7��l�%��#��$&�����D��z�h
aX1	 �,���\�A�5�����P����J����0��(�cIM	%��0������V�g����|����:]�i����:����@��?PQ��~��WZ���E@|v������Z�<��g��d��s_54�3�}|�9q����#���#������������)�gq�i����sA+�}�_WLG��_���B�� ��4|�e�&�����64��u�i*0e��h��-V3e�+�Q�K��A��������O���R[Nj�L��%B/���Jcd�)��Wj�h��dy�
�
�W�>1��$`5@�4�1��O���U@�gh����*�!,��C�7���R�/W[*W��xY���#�R
d>�00�R:���L3e������I��
������M��o�,a�iC�'��j@��[_LRM�<�<���j?c(k�$���3"��Xydp��s@Ve/hc������gs@�r|��7i�19Z5YZ-7l�����ex,���y���|��4]E��UtYB�q����k�4��q~?�s~xD�=��f`�E�~��O��y�U�4C�$��cV�NY8����� ��tT�����7�R����I�b�[<s�_�R��z)u�&��#�����`S,e3l���,�9/=/�G��$Z`<����+�=�M�t�@*	�@�<�L�4�O��e�E�L���
��q~�iJr�u�I>����lZ�yC�N��~��-��PG��c��Zm�S��V^���1����@���LdE����d��&���.�����e^��$ 	�R�3���!V��J�"$����4[�Il���D�|
j��h����i~��u�J��"i���(B��O�6W������b��2�A��A�t���&��
�%�>�h�
X>;�>����a����-���Dl���K3���nh���+��S
��%���bjF~���NA�C	���_�G��k�K���%8��!��lZV�LP$����e&��i~�������	<Fq�kC/��SZ�?-��=�6������W����W�o�_��!|�c�8
���\�5���A`���y�{C5}�>>y���a�4/y~���/w��������f�}���EC�����'���������-�������G`Z�T]be���g��-������WtP����?�[���y���l	u�9��7����u�C�'��C�a�l�#.��?%w�G�L�g��4;������!�B������{�.�������Oc��~��u^w��a�-��������~WS��;B���D5��5�jai��<C,��Y@�: �r���S��I���1������M��:k�7����um��D]2^N������"y��)���U���<}k������l���9��l�"�|t��(}�?s���HglzR�6�d���UjkP^��)��tu�Nl�����R��f�g[l����g��.�'��8�
A�*�D�l}����r�
����lo4�S6�D��Jm�����:�p���M�;�l�{K���1T�������j2L�`�C^�$���QW���'y�*c�hu�>��aQ�����v��)(��k�}�>f�Mw����I
������JtS���,V�ddc"��4������E�E�%*���K�OC�9����|u���Wh-`�N��\������h�THP���|��X_�y?R�s�%�]]%;(Y�.�A��#O�o`���@3�.�s��^�<��B��l���u��c7�Eq$Qa�����������5��I5u�}	���^����H(
G\�>�<���86Hq\�P�S}��j�_���N.Z�Z.W��!&l,�t��� iN,2�W���������tM����Z�r����j,�`�^#o)��!����5�7�G�|���������P8��5�^�=��H���G����������-��QW���4-�4�@�v�S�J�'DQ��+.D�;�#����r�
Z�Rg���t�[��E{����x��n����(v�Gbf}��cF]�X9`�����m��0�#��^������ko���5G��>����
��l�� k�2�\�"��7�Z��5o��a<�k��x�u�$�>�����-Z.��v�bq��6_�}�kz���F�nk�����b�00:������j,�J�J�*�r��.������n����=�&���C�R����c���]$>��<S{d[��g�56��z���m���\5$I�b��b4y;���9�m���#�.v�e|�b������!�)%X�.
D�)9��
�C0yDW�vep�;����w���a�s#qdx������w_��+GTT�����
8��}�<�����BG�3��Oj��I����/���7<����lx��
/?���^����`�7 ��To�����V�(�����d��oxd���_�������g�|gg0n�
�(�bSt�@�^����\�~|���~�����X)3	���!|�)j��~����������a���<��
/>���b����E����<4"�A -Te�����X��G�1�a�������!y^x��a%[�����v�7m��AR����_��{#�c������#{|�s��#}�~����6]w�!W�~�K��8r���z����G��
��.��6WL�:��Z�+_*����?��������>���Ol����mn�
1u
e�eZ��������_y���|��������|������T�Y�^����������~��������]o��i�(��2p��'6>	-��K/}c#���/=��zcQ���I������7��D��������������\����}���I8�t�*��x��n*��Q��UH�
�z��R�����g���D��M\8�g���/$���[?<��( :IA��K���g�<Mq;���(�E��cvvf�'<e���s?�L����s/0��B?L
HeOP�����i���������75��� %�U�%�'�.J�o�FD��IK"p}xB�s�-LK��K�~4���BB	'N����kT�k}$&�R*l��w>�����c{�$�t��yl`���I�K������N�<q�����������=��5�����[W�[�;�\w����'��^���u�N�v>���Xd`c��,R��^��A�A�f��z�����g��X�v��5]'OrhF]�Yhd��i���)��5��O�����kV�Y={���
�r* X�&e�@/n���Y�;m'���s��k�\�0���Y�CKE��i��;��}�����=��7��^w��7N>s��]n����������'ncq���H�.f�+Gs�;Rq3J��}��*���x�5$'[��	lg�g����S��N���*@l<�KS]M��$SU�)+�;v ��l'h�����>dO�V��T�����G�MR�{������;rc��E��y������n��<N'l��'h��@����y�B�H�M�m�6 |����C��,������V�-�bXw���<�%��G ��8�/��T{��G%u��>�)cg���=������t\&u�CKp��v��E[M'�^z�7t�~�8�x���IC��f�s�]iigy��X?�w�>�{��j?���K������TVc��_-��uw���������w?���@�G���-�A���P����mM����V�����������Z��?��G�u����d��=�H�R���[�p���������_|���3Zny���3w������t'!��>f'��X�q�Ci����?}�������?3Zf��y����>��<N#�E��.��4Td�<�g
��<?��C7��5�����g3�����K��A�+>�]�E����� �'��f���|������w<����W�3�fp��8�gt���"��)-�y��L	�?�o�r�C��qk���j�y�s	a��n�A��>�-�9r���=��?�>_Y����_�#W�|����Z�#-�5�~���+��N���~���548����|����+S�q�K'������q�J�Q�����6����{���w�W_=�����}���c����~���������je'l1����\}�UK�������z��Iw����rLrQq�0��
�-J��V	>��Uw,]��K�i��c����u��1#y��8jz8�$Y�Ar4�������i3i�Uc�,�c��Ic�r�<�,�0���#,���UeG`3��y�)�K��������eb�D����%;�����WP�@��C�=_b[��cl�`��H�@i��U<��n�W�_��na�R���q\��,I0�
�y�QY��@^��]���l����%`�+��%e��������[0�n���u�����^�L��PUZ#TZ%�J��F���G�`0�'�W�_T��ZWW���-X�`����G������rW��'`�tR�J~�K��.�*����3e�-���F�_�`T�F���Q���
�H.�MC�(�����x�`'�����!{Hi���/�-�h��q�G�>���76/�RN��A&^-s�����[S� -��?c�����|���Quu�<����yD�'Y<k �y��-@
������[�!��8����eK�����>���u�/X4~\����(������\�g	�S���?,����?�G��Y��������WUVy�m����(C�����d��_?n��+��_7z>|��	
6W�2�'J[,�]7n>[���w�<��(l���wI��;�yF-;v,t��W��JT��%�?j���M���-�`����\������N��2y�}��3@�������E�4-g:^Exwg���-�+cC;�?V�
1�/.����++�#�������<(�^����`��S��9e���S��/^�9QuE^#�^:��S�,^�|��	?��|���A~����l�$>_�<�&��R_?f����&M����~�������V��+��������%S��L����K�}��9
(��e��t#O�R�9e�U���'��Y|g����X��E.n	e$>%>_�������w.��_���{�������q���/�q�;4��1��+mU�}������e<{?����
���K�4w������o$������	GB"Q������gd�!��������[�i���m_�5��fO����H�W���D���7���
y;��&��_�P����^���8y��������n��`�{Q�{,��E����r���y�/`����^��czG���f����f�&X��U��OK�p���#!�7����Dv��|����t�����;�?�P�&O���������g�����5���
k�;�����C��m�=����8T�����l�2�sYY<y���	�����%
w��[�����r�I@%�:�;y4�Wy�{��Z|���V~u����g�t�<�@�+�J���!O��y,jX��pk���{����S�p�<�y��5���]&R���n�����7Lx���+�]{��e��N��:?QR(���3���$��<O}��S����
?�p��
���r�u?:�z?�TU`������,X����<�h�d��

,[����
+�7���V�!8�y�����Vf��v�M������V��[��U�����U�_^(���6Tx)����&�}���������{�5������V=�`�-�2-�H�"���2Y��W5�
��~��{'�s�=f,��a������H������p�p��B��1��4K�z���?����
�����A}�����H2{����`�dO���!k�L�����	.�q��'/����f;�|�}[A-��h����2����u?���}�5
_�����mi�,��|����d�#-��3+��U9����=6�3�k�5����{�}�@d��e73���}�����p���wya3���;#�3�Z�������V0CK��XY�y�Gr�0g���VUV��S�rkaC�(L�&���e',��c�i�ze��������i������Y�F�>����^z����M�~x����'�d�)���	�UG��w�Z��7kNGI�������6�����4=f��XS,{�O�*��g/���?��G�+>�00:+�X�RI�����'������w�&������^�#�#Z��_L�&
���T��M�w^�kS|�zO��VQ������7��H�����s�t]�Rjg��n���O:�� ��eXO$
���~��`
-m����{���h�����E��u��?��HW����.���<F{�T�����A�V�����mk;z������?��h��G���5��"��k(��PHiy���=�������;g6,��9�]}b����Y��
%�9D�Y�2�Y�`>����X���lx2���s�~v��.�=Oj����b:�E]�E/�(b��h[�l��V���us����kZi�A
hy!�$�$���I��f�q�+���u)��F_��6��s]��mi>���,J�����@��0"��|�t�~>�������9�W�={�������8��z'�]�_���9Y��$q��sn~�������oMO����2�0@�v0������u�Skq�ik7��y�(S���j��+Xr�o�?��c��8�{���~������	�L6| �ytRB���T���<�@��R�1�<��`vN�����]{�w���Z���}���O��"���u���1�\���4�XOj�DS����a�~%u�&�F�nPI�a�+�������8�Ob>���������=��������~��9�y�����LS��U�'�%2�
V:$������pV3������J�;a�o�
�p�>N��3����������?�����3��� �`;gTY$`�ga���;���&U��U�'�~���-�F�-6�P8-�e�K�D��>S�84�1G��ws~���L��i�Z
��c!�
������<�
�R��IJ*EH���$�[�H��=����{��O]���P����cO=�?���p3L`G,tf��x`Z�����q������������7�W�����}(��O
�L�����?[����V��<x���-�����T���c�J<��v�<��cv�-�l����_LB��-1�������h,u+���1���b\�pS0������1���+�d���,z;��1�y�VX�NOl��]�b��c�[?��������O����"��d{:c�g�m�5�p���ygl��$LeO�?���2	�.>FA����������i�]��2�*
Icp?M��"��h�]�����l�;��j�6����K��L
(����!�}�{��!xv�3����]i�H�xs��|����n���5�=�k�����?F�I4�������HGv�;�w��td&9G�_��LNs&��?�k����{��������!�#By�J��Jql�������H$@���x�=+vr*�:��@�}���2�����j��>6T������/�!3�P�>�'�(�����w�������S�D��?x�\�E����S�S��C��8�)�Q����p}9Q��b��WA��q�������Y��}�����"[����8q��?p�V��C���:$*mFI�Fb�v�&�-�r�,�nw������#�����L�G�}�g$�`�3M������]����>�����'�x�g�;�0��nTb��3��y6}��������P���^����=�M�6��i��E���%����N��3!�(���{���V�6��X�v;��A��~s���
`�i��b�z��|�����:�L51<�K��l�k��~�&�
�U;�nl����������������f�>g�F���^�
s��~_��7�:�>�:��e����)_�?�G���HIEND�B`�PKbi�NConfigurations2/toolpanel/PKbi�NConfigurations2/menubar/PKbi�NConfigurations2/statusbar/PKbi�NConfigurations2/floater/PKbi�NConfigurations2/toolbar/PKbi�NConfigurations2/images/Bitmaps/PKbi�NConfigurations2/progressbar/PKbi�NConfigurations2/popupmenu/PKbi�NConfigurations2/accelerator/PKbi�Nmeta.xml���n�0E��
��V"��EH
�EV	R�.��!��-M$9_=]���K��;�IU���
^�:it�hDP�!��F����7�*��"90axw��#�6����U��jfZ'������U��i6�����w�~zb�}�Id���,��]Q�/���j���`tp�F����C��u$c��h����]LH����>X!��6�C�������3
���<F�z�c����p��pCZ��I���Q�hm��$E��
�PT���l�fy�f��q�Vx�fW���N���[?%����C����q�I�����@� 6�y�{���8�h�G�����y�c���4�v'k~����/�T"L���������y���������N�%h.rPj��E�.e���A����+��~��PK�<s�LPKbi�N
styles.xml�Zmo�6��_a����%�m{��m]�mP�����%J&J�E���~GR��7Gqb��$�������/��	�1�	K/���w8
XH����t{��;W��.X��B��
7w�N����tV<�1��|���3�X�S#4��3��Q���+�--�V����,Z�_Y�m���M_a�Nm���������$C����R�~�t�Bd3��l6��d�x������fK����8U�0�0�r��
G��&X���I�mR�J���	��j�qpW�e?E�L%��q��Z�4K�{��WSe�O�Ih�&H,;�{���I����]^���Z[�*�$���F�����T)��]�;����������
's���%�,i#
p#.^��7h.������8c\��D���3.Ku)�]�r�@c��P0g�A�B��k�7/*�l?�SO����W`�{S���k�<.o[��.;M�f�9���U4�C�*�{����X	���J�Z�0�&�KRH2��,�J���D�����'�\yW��Y�c�L����9#w��
q@����x��@_K#/����r~������4!����e,��������Z����5O�!y^AdD�^����~��pFB���
^�� �i`+���w����y�(]��K+
��l���_�����%�Z�b{e4���uL�c��(�([��/����LO���
I.P*�g��L�h�I�Sfv$a�f��
�0�S5@�
�}���U��Q�
�5��������o7M��>M��;'�K��%�/RN�u�b������{�J�4_7�S
������� �����Z�E��Os�7��;/�n�?1�{�=��2��
�[]�+uTP��z��P���WP0~	���������7��K��FC+
��R��y� �3���
b0:�w�������{1~������������k��{���	|�neT�W)QcM6���=�k���(������
.�IqcN�t9'�2�s�?|
7����������oq�^� �G�5c"}���*(����!	��4��}�>�c��0~P�,��~�Fl0*c: �s(Z	���2�P
?�Q~����`,<Hwa�!5�����������c��
^	�K�S�R4�>�L�''�Wt�,�t�$$Z���$���Cw�uR�)�~����w�g�XG��(J���%���92��='
8��P�vH.L�(Z;�:�m��4A����J�d/m�S��WG��5S~��E�?��Ii�S
<P�A�����U�!�c���7��|\�k���H8V������"�5�9�0�T�"0�hn=�l}�!�)�}�@\<&�#���3V�� �����dw�]^��lq)<	$p��Qc�a+Qq�]���P3-��[��r���X��Yb��	c��O5�C�e��������i	�1LQ��_�^]0!��g���4�������g0S�����=^#
=�7�?E�~,4���Y����������U}�.��$�����?�I�&_�g������������R����:hir�����vMV���k�������#Y��Z�e���q��������l���|d���&U����5x����7	�0;n0k6
1a:�J���?�������TV��J�Y�~�0%��`�go�XP����G@������v�3g�������
	��40��?S?��miT���r�0�����tj��#���^�^�����PKi��P�(PKbi�N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��PKbi�Nsettings.xml�ZQs�H~�_a�n�&�F*�e����������m�V�2LS3����@s�@bR�U<Y�u���_3\~Y���!)���<95j�mt(_t���M�������sj������U]�R�Y���4��]��D"�49qA��6��f>����W������T�3� N���F���4���Gm�s�8�T��sS��d(;k���7��Fm�������.���]n
�?u��
cS�^]�����<E�H�?��J:c�@����j����+�wz�x	�.��U9�QG-��?5;�����@�T�������u�xu�X���A�,Ect~��!Cp�$��J�0zaB4��i��sJtD�rt���G�����/$�1J��"�;5����s��T���8DA"W�Y��Ot 9	KG$:E�����"T�B}�	�}[�D���i���[p���N�*������*�n��?��F)4�C���$�v���Y@Xa_Eo����.h�x�]9��!����&8SX�;�]�#X{�ekN��0�r�u��b�H�F��F���!T�PBE!LQ���;#4�#T�P1B�#�b����f���8������o���ZgdlFD������Y���&uh�Jyw)s$�!f~���Y�

���*��e���HM�V�����������2$R{��|����#�@�jS�������;C&-Hr|!F�����]����<,���t�"��'�'��N�b`�N��Li& ure�@�>��vI�t�q$�����2��������:1|M�����@Nfg����l����?��/��������>��=���g�m`%PY�C|�}�eK�V~���>���|�"�04XAl���a
��k���=�m�%��D��g$�q��A�I�7#��W��1C}��;�T��#�3�8���|���HK}��T�[�9%���~���sD���M�k���G����p��W�[��L~_��0�gDe���������s4v�YN9�!���3���Y�z>����\��)([�����<����c���7�����h�n���4O��cJ�����*����������{+�?DZ�$�Sw�����C�F�'��PKq���y�,PKbi�NMETA-INF/manifest.xml��An� E�9���2�YU(N�z���Qr�b+N\U�b);`���|�fw�]u�����}�wV�^[��}��?�n���
��DrZT����a9��*�$Q��$��@������/G��n�fWi��<��NNB�g��J����J�Io�mA�F�����`�������d�����0���h�j�h�
��v'�|���G�)DP:��%(�c�PY�MK�{�b{����\���rgHk���)#/9�ly;WXf^���QQz�K��P^�����&�8H�g�����������@T�������oPK9�3,PKbi�Ncontent.xml��[s]G�&�>���'z���������MR������8��h��e�A�u����-�2�7e��T���*[��J$��?�����O�������_�����O����{�������j�Y��������w�������w�������g���{�����w��^~�/_�t������o�������_?|������~�S_S����k�7������ga��n�����(��?{�7��<�?������?���Q����������������������V���o����|�����~�������O?�����Z����a��~���������o��������s;��?��p�p�]��%��������?����ov����� pQ1y?���_��?�gk�?�_������=[�f�_���W����n��f��c������_���������T�����
s�������R�,�}^�3&<_��H��w��y��������������������r�9H<�����C����?��/��A����?��=>�����?��"�f���7��?�������&�E����xw����|�7��[�����������g���_�~T�����C��on��_�������,D����k����#	������������O�^/f`�������
������}���@5����G��4�~e�������������{��{PP���&��������8T����}�?:����������{�����a�7w�}���}�����_|>���n��}�������������Z���������1�?]������g�����_���o~�{��|$������������}����y��W?�y��?n������������������on�q���{��k��4g��~�p�C�u���}���o�g�?�6[��u����7?=������g�������B��������?���������~���_>���������?}w����oo������������������x��0����~���k�_����~�0�7tU�o������������_����������p�����?����p�����?�+v{�����o���������>|�Z���o���������~����>���5���������.������E��o�}b�W$������@��o���p��Y[,�o�={�7W���������<��Z\���������9�����ZG�o������?���7�U�����go�q������J���_w�p?Vz�)����k�����t���������������Y�����-���2�����[����W���p���F`/B1~3��{HE�c�����B���[)�
h�����C��F����MC�^���z�����r�_/=�����l���m��n`����
���i������z�������~�f����V?_+��i������>?_��0M";���������j�m��y����oe��.}��`[9����kR+����y�����>J���p}�Y+�|��y�{�p�<�mi�d��j+?���i����X��V�S��:����'�����miu��������}�%�>7_qd�>w_q��z���'��>��#s�|�M�V�y��O��\O��m�K��#����>�X�Z��O������P/�����?N��M� ��)|+�
�����r�?G��bo7]ay�9�\a�[�%P�a�W�9�a�S�(�O���>�o%��'��>=60<Y��������O��	_�K�%��\�����O���u�|m���7�v�����,�x{����oo����\����������^���������w����������������"�E�����O�v�/lH����I���������~�K�����+��FcC��7�������`E���������v������e+%s>Z��-��+���
~��y�}
�����o���g�p�5�C��?���}h�������?�iX���_?������f��K�-h������-����������������_��\��s���������_�����������������5<� �y�d���q��~�HP�`�[!7[�_-�mc����|�p>���n�{���O�r�������SX�����w?4YVv=M#-�G�U����B��[/�����?��}�C����?��}�C��|}�b���[�(���.{�}�����������du��5����6����_��������o��������=��K_Q���"����oH����C1���q��"?��Z�Gt����t;btv2�YS��e>8k�t����	���s��l������#��T�l45���yc�m�����3%W��Ott�9y�����}�n_�w��k����`������;��]����m�!��o�C�P�Flu��8��rD�it���r	���;��t������>��<?�]q�N����l��TcDve��wJ���n<��N�}r7�Aw���`V�s5���I��s�\g5��p1xLzr�wA�]�t��Z`�ruO���$�.U�\�� �jr�O���"��t�r�+��YDQ����&��U���L������$�^���^t�!�:��y���^t�T��BL	���cK�l��	3?�<���l��(�((6���k���E����\�
;bx��
�T������k8 �bW����J��+;��ZC�{������:�FX�5�A�B��:�e!��m�$pV�k��b_�9��c�|!Q���8 (t�j6��h8=k���Pu�sA���b�x0��#�f�`}t�Y�7$ BC���
���P�W0U[CqBP��4��R5)�j�:k��Ty��H��H�o�x�g*`j# �k��m�8'(�5*U�?0�����Q�!�a8��'e<�S.��5G����Ti���BHU<�}�BqEP\��=P��D��Mm�5�q����P�����v{�$0^�NF�!;F2�5\��Jy��9l�;�)��p
]����
��
Qa�">�V�\����-��bG�� �!�
uk'h���U�09�-+��4�����S�����c��dkw����E��y[J01W�[F#������e�h��ci�5�����3\I4����C��*�S�In������8Ri����H.IBN���c��X�Q��
���j�Q'��J��K���[d�VK����8�]z6�l ��vk����8S)��S�!T�Vr*���9Aq�3Q>8�}�"-�����������1���X�K��R�F9�:y�=~����RmE�5�`��[d}�	�k�^�TP�R�[;/	������d��[/^����'|&����g�2��,[�3$�3$�)���|�.:��5e�w�1
;Y�d��z#�mS��`����X���c�}�#�T2����8��l�e 0^h`$�Mtp=�X$0jj�2��Ca"��j,^�V��q��(AhT,`��t.	�C
�
�@,�=���8��(��j�x��D�U��8&(�U�;B �SH�C��][f��'*�.�P!����h 0N5F��X]�6�*�Gl�3g�x���o-����8�hT�Wb��H���� (.T
!x���,Kk����
�7	_�2������
E��"�
j������
���VW��^2�K����1��2���+5��W��(H��S�����g��&f
��	��5nW{���b������bG������:dl]K���f/r)1&��s"���s�A��AQ�������[�/yA`������6bU����MS�}�F������D���t*��+f���n�m (U(��.�	?�+� 0�T*�k����B��MU���8��n�OX��,���ZNAq�R)��
x�p����{J`�j6���|�������g���+�\���-Y�s��\u0l��Q�Va�I������Pi��1�PS�u{����xC��
����=�_W��@3nH	#����k�fl`"����?/	����H�F,-[+��iy�_�t(L��\�-)�v|{����ZkX�������PE��	�X0�\���E{Pg6�%�v4��Lb��������.���l��6Y��������#����
7�R�s9�h���� 0^�NWu.�\_�i��>A�����s��:,������N�Aq�R)L�&�R�o�a�q�Q)��3XK���86����#��[z�XeuM@n0����j���)��������;�����
�����J:%�N�{��7&x�5�qFP��P@�R�������  �UV"�~A�6����(��N`���ek����
EE(�o%���_tW�=��
��Q1)�����
�s�M�j�><a���K�����\	��V���~C_M���
���C��,oXr�����00_���
Mi����r���������[b���;��]@�$����
�a�L�]�nW�'��� ��&g$�5#�n���S��"�_q!��7t�~A��P��.��U�I��.-?b��>A��@m���h17N}����1�����h�B�,�R$%#c�Wx�x9���I��%�m�Aw�A�M��J@)��2V���;V<kc���M����#�	Aw������������e���t��/�����w���
V���;���d��)�^���T83��;������'��l���� �.4{WL��gl��$o���j�}wI�]���]�p!���2u����JeU�+n�l�xvd����Z�����"�4�K81��{�s4��Y��F���!�^�T�]���D���S��qb�G�Z7�H�"	�A��>��-Q���i�
cGokK-��DIg��eD���f;�u=8L�
B��k�+S�=�oO�O��C���a@����
���B�Q2�8����C)M��P�=��&�
��h��r���q�����;��$v��yr����;T��y�z�<��	+����w������������%K���j��vu)dL���-��	�q�:M�_��=	Vb���p����;UmN�	1;��$r���p���w��Wm*K����iZ�Eq���^(p�or���5nCKq\��Sr���n���h��A�.)�K�� J�����,�+��J�op��Ct6l��������p!F�m����\�K�^��}������	��@^�6��\sv�e����K�:G��X��X�#l�qn����kJC�P;rv*�D����t�j1J�>���f?J�� ��dc
��1R:�R:E�O��Zq���~x���N��N��_H��Gj�����k9{j�����SL6���C�R���v��848`����������H2�L�XJ�h�7�M!��u2���6*�*��u��E�%������P��PQ(bH�[��88QuFh��X��h.�[����'73*�2*��
N��HWtA5y����X����+����|�$�Y�R�)�s�>U���3�K�S�J���B�#8���&�E������Q��QQ9|%M�^Eq\�p@\Q�������d����ap��y��� �-����%��R����qZ��
�j�"��x���_����e����w���Sq�Sq�+B�l6�
��n�t�0�����.x�N���h���Kq���#S��a2��r�Y��)G)�����`G����C�8J���a����q�PLE���D!�c_�#o��N��(b�6���
�����J�d�wm��c#��(���W#��)��<�I)G)��s���.��(�U�Q*�R*������3�N�G��o'���~��V,A�)���)��H�8J���K8Y&dc$�����<�,�$|
�I����	�q��(NRNp��(
���q�2���r�\	E��Jj3��(�����
c��^��+��J����egf����)�k��q����f$���Rq�R�mGH�������W�+�h��	������{���S��S���R5KIu{��v(�9p<��d���������T<�T8p�,�[�hB���lS��T��TQ��G����$aoP�����_�8v!'�����5%#�)�}
l��x��"0�%�z@q��#�T�49$�`�����_1���<v�\���Q��QQ�N��bECq|K
��8���~��k�&����zBq���,�\�l�$�^C��S��T�Y���(�,�����)���l)�z�r�l$P��~���N�)s]�dm��0�q�s�
���	eF<��F&�S&E���u�	��T$��M��������n\rVH������8�u�������}<�RT��VW=x�<SIo��z���x���3�Mr%k$o}����J<�i#�(�49�NX(�#�$	6J[2%P2E��1����	�F�*�]�cW�5���m0��"��M���dJ�d�_����h�O��W��)��)
|p��������[F�����<�\!@O�G���P	�L��[
v��������L	�LQ�s�`bu���Z��r�(�#�f���}Ed[V%PVE��%L�'��\���@Y����6�4b���U	�UQ���6����}|��FZ%PZE��>�{
�{�Z�4����S�*������/8�NT]��0\P*g��{�����fZ%PZE��!�o#�K
���U�UT�!Z���"mq��5r��l��G'���Q�x�@y�����������Wmi^Q�t�U���$��*Ob&���L�f�}c#�\�|����|,��`1pj���i.6�������8�g�����i46����WM�5����	!���Q|{r|���o��Qz�N��.���^h����]�VI�eC���S|�|%���L�:�h�����x��J=3�������4��A=)�C>c+ec�=�A�l��(�#
>���!�)�I���&V8���;������� ���A�y��wB����"��3�Y����M�|����zb#�MDE�M(�
����;S�_�.b�P(QR���~n��s��\�.���|882���m�wA�]�����gct[��t�]R|���/&�qq4���&�m��~S|W:�:a/��n�,�o��S|���"#����"�lH����{��O|���;?�-�����+�Q�f������R���"��K�a>�76Q,)"p���Mv�Vk1N2�����CP�V���K2�d���]�oW�/$���C��]�<"(;X��3�Q|{r|H1�Z�b9����d����{��?��6�"���&�;7����u��S��I�Y1N���;��+�@�}�_�%��C�R|�*�	�I�� G��t�Q|G*�s������E9&#S|���K��RM��[��5�	�w�R����9Xp��D����
�yJ��������\��/�r��l��(�3
����KrY���Z���S|�|6�����P�(w���wA�]������&gYS���%�w��/KMg�-FTi3d:8�w��g�G���\E���rM�]����` �c&�S|/U�|���#E���<mN��R�g��v~CO��j6�������������f�)eU�=v)6�IB�2�[�e�)p`�h�<�	`(��uQ������&A��0�M�����X�(�=�vTlfm6�
GI���:�'S�G��&[1+�/��Z�a�S����J��=&V$��2yr��)���+_qp"�B6�*�������8T��(��+�u��=�q2�r2�l!*��voe��{��{�\���L�.>��(�T�
�D�)%bZ�+dl����8U��y'L��"���-����8��G��b?�lb)�R�\��d��h�*���-���%�<��/(��5�x���R���ZS7����T�����
�[��m�WW����Gc
6��n�9o�����V�G������X�����%��R����c5�\-����������1$�j�tn�����"��^�F�F�}��F_BZ~���lD�l�G��rM)��/Hfo���R�*�'�"�%/9H��~�Q{�f����n�?�����Bu@��&���<NR�������b!R�������-hP*5fp&}�8�\����yHq�H1���#�����tD�t��x�Pc��cc+�W��`�B����M(�~$�?����	�q"��q|���nH�z���pJq��pX�a|F�r[��(�3�1���P`W ������\(���ZZ>�h�m�C����.����K��R�8����C���l;O�P>Bs>��(�_��$!4���)�k�~�\B4�'>�f�7�U^R/U�a��<���L](������(���1��3b!��^�CT�CT
�j<>�q������cG����m	&c�d����m�Jy�~`�6v(f�%��F��!*�!4��B���JuS!��!*�!8 0�!�����-��}�c_u���+W�dRq�����8�������r��"�1KK����8���q5�_�s����K�x���8R���
���y��R��}k�)�c�^c�M1��Dp�4�!*�!4zS��!l�+H�r?N)�S,bs�D���}�%�3��L��x�����]�>�Zz�����|��.F���/pi����>O��K��m��^R�����`q'&���@(����!*�!Tv�
 ��wH���uMq\��UE�nn|.����|��8^��D�.���heQmQK�zEq����qE�]�dM�6������<�y
'��$��>>����A��[��;��G�%;���L<6mA�Kq��q���s.�\���l�Aq�ipX0LJ&� ��n[��/(�8�4�FyS��t����}�c_�#z��cGLV��4����8P�UD&U�iE��-]�C��P�����8���(������'�[|�R4�7���8�U�`�,��+9IJZ��@��
G��n0[�j�YwJa�����f�w�$��gFPg��H9�b�@�������S������k�&@k	��B������O>K
��,^R�:���3B�����(�+�5^.��p6��e��<����|����p�O�Li�����x�����M�85$U�9oy>^Q�T8*\�1��V�[�
�������q�rVU�`<����]�i���������	'�/�l�'Aq��p`�6�1��U[���8�48
��.�������f_P/�8,:��8,�F�s����Oq�kp��� ��{�m-����8������b��L^`�bK{uHq��#��]11cS�mq]G��
G�1��UzY���Y����:W��tHWI�C�����D��K-�yQ�J�l�S��T�5b����$����Fq��n�d�/�Or{�<����6����l�kDr
���qAq\�n2��%����t{\R����)A��q���n�+��J��x�*e������)�k������\�/����UY/)����H���k�E|���_Q�T8�
���Pd����%���:V�QV�i����!���L��RZ�J8�J(p@����.��)���4
��8vu�M,�Z���dvW����8��8�z�����I��V��w+�(+���+Su	�a������Oq�kpD�E�L�.����h���8P���p�s\	�����q�;�8��V������1mS%e%4ze<�P���&rdbK����8V��&���k#z�M�7(����p<|�(�;I���������fo�/>�(1�m��3��L��bJ����**�S�XGK8JKh�U����8��E���&u_P��p_����9�Z��K��R�6��J*�l����+��Ju��i�����h�k��Z��T����M�&�BZ�QZB��y���L������^Q�T8�w9Af�i�����G��G���$���J���Cj7����yJtxM{����cY�h��1�~������op\mu�1���fd�|���f�*��$�m����*�L�=�oO�|��p�W�N�,�������������GI9�����>������5�8�����"���@����cD�%II]�����R|�*�	���C�s~�H�
����;��Kp���s�|�0�MF�n��c��X�������l��	�O�%W����;Q�>;3���%c%�e������;U��R2�>��Z/	h[�M�wF��i��"j��f�6�:���U6�',��9��}D���w��4�l�Yy��*C9�g���.Ug������IH�&S|7��+
�J�rF�0�����%eU�l��)�k�vZ�
�B�����7�K���N;�5�cf	&�uOM�h��0��{���C.>�����<����y����7�����>��y����go��}�F)���~H�:��X�
���q��mA��b�w�f�M�������	���#����&g8���[�4=b��.����>c����"�j��=���Q|{*|[��\q �����q�#|q�(���Ol�R�I/me��l��)�}���x�b
��,�7[0��P|��g���%$2Do�M��
�yH�*O�K��5�**�ks�6���w��O�]�%[�����	�6�;���u��sN84!�4���M�N(��~�C�S���S
�T��!j���c.�3��L��U�S�K�O��/���
`)p��1�]�R8�����.t
j�I���u����wI�]*�!��C
�Y'#N�x�� p������F��k
�Z��T�^l��<=�%��R���L�0I�\������@�7���*ZRm{?��5&	�@[�&�)R�)jJ��#u��*���6-5��8vT8��w���8Z�~�R�r����S�a�dI���?��o{��
_�_\L�s����?m��"�����h�KQ����f���������&Q$��@P*s�X��-��)�A�)�C���>*>GoE�V��
���;��3�8���KF�*
�:�'R�Gu�p�/v'�[o��=�8Nt��]����mlL��)�)x���kJ#I�sC�Q�g*M������q@b�:*'R*G�Q)A����r���u�M���
H�5[\t�2�1w�%x���Mc~0�H�u�L������C���i{}�"�`�&�xLi.��^�ZyI���m��$��
i�(RNE�#��/�a�]K��p*����J��J�d�����$!��Xg�cG�c~��� �� e�	-��.�����Z�Y�����dC�qZ�(�=@lD�kp������J����w��jK	8�`Km��)�}�Fy��f��s%j�2�=�8T�_7�I��-D��i�Di>g�v[��M�D�$J�h�U�s�=���Nmi�Di�y�)S�elE�)�NiJ�VQ���O�X�\��W�Z%QZEu���v�����*eUeUt1�%q�A�mC�s��\���9�D�������8.t*��|,	�W�I�DI���&�F�$�xkV%QVEg�\�"H�<����*��*JPl�	EomC^R/��D
�f�e��-���@^��T�M���%+���rx~��f%Sf%k���{0��6c[�;��
G�A7!�X���l�+l���U�0p	a�@
Q���$�{#��)����#|"��d�$�Q�J�������!)f�����m���)����
��z��,�{��<=�8��	��T!�_���W��WQ����&<���U2�U4������`;}Q�v�T����.����*H�j����-{��P':}��a'�"rF\O����s��S�M�E�cX�LY�V\�!�E�S6���)�s���)km��	tmSU2eUT�Qs����LlQ5bU2eUtnU�I{��-��)����w�b�uUn��d������nU$�F�X��d���6<m��Wu���U��U�m���f#y���HA#��J��J�4H,6`�\��������:Z�PZE��g��Fj%��-��]�cW�c��!��W���Q�J���f�j����3r�O�9��B0��J�)�Y�@�[�}�c_��p���P��W��U
�UT
��r�������R|�J|):���i<�F^�P^Ec0r��#�|��h�c��X�O��*�83r[N�	�q���3B���N=ON�N)�S�`�3��m$�n$V
%VT���ll���+�+*���S?��IR�����8.t�VJ��^���F�����_����sL#�u�J�����p�Sp��-�����M1.��*~�C�:Z�PZE��d����[�����8^)�s�s���N;V�IL���x3�R)�R5�����w�� *��-�w(�
�-�S��$K��-�R)����mI��������]*�]4���`)1/�l!L�0����Bu�,��.y�V'�|;fPV�t����,c!��QT>4b���w��W��G�����~�&�R������%�b�,�i*�i4�2�16f,��u�k��xLq�.�8<V�@@��<���Dw�L����\
��)OS)O�;O.�T
 _6��^�Q|g�fA����S�*�ot?x�4�d�~�xA^�6�e����w�
�yI�]*�_��5L�zr�������g�D���u�<�1�yM^�b?�bM���'ga^R�/uj�[5f��o��IX�G:|�%����gM��Q�&��f>�yT:��
���95�]���u���9v(�<�+6��$�u���]
oWL�.y�C��5]�A;�(�=>��.W�Po���
�R��Q#��b����T��j�|u��k�Z_t}�0/����a55�(*`hs�6�;��u�/��MN�	����
����;�\��� �\I�F10���;V]��j�4x���OG�	RQ|':�t��9��"��@�S��T���}���0��r��Q�g:���W���DD��yN������|*�P���G���
���(��U�(n�@�K��Rw�l�6X���kr=lGE�]��y�5v��1��m�FE�]��K�������QQ|/u���R�9�8�'7���{��O�e�������~�k�,����S��m�c��:5y|����Y{;������e��(8h�������+&0�����W��Y�{��
���Js�}�Z�����F�P�������[n�>������M�����	�Gn:C��8P��\�is�%{Q�NiY|tHq��n���bM4�fOM�%�(�#�1�s;pg�s�j�d��8��Se3���u(my<N(��ZA�|��&�JK����xdcR�X�G$���L,�L4@��9[�m|�d�|�*�s��\ewK	��Kt�j~%�����Q)V���
 �LUojw/)�K�{
V�:�����������w.T���F
^S���H��ds�V�T��v��8^�p�Xj���N���i	��J���
�UM�?��p�)N��G�'�7t�]N)c^����-���cG����q<F�p_I�����R���0��~8IV�d�����8�T8lM/�j�5�-k^P/4zU-���UE�U�����Oq�kp���S8�/��R[6�Q6Bu<2v��'�$���2�=�8U8�@�fo[���q������a2x/[k�~Lak`8l����BF��R�8NT��l0�^����,li�N)�S��0���|
��(����fh|I�Ve�9�q����� ���Z���Bi�
\��fQ���^]R����u~�M�,no�r�;���V+������Q�5�q���0C$xP/Y�l��2�K�b�g��!������* 5���2��&�w��:F�SF�+�1��u�XpdDI-�mz������p��"X7�Qj��)#!�1O����h����7}O��0�T�a`CRI�X�4����*���B�v�h�u���������	�#8�||�����q����]up@��g{�����J�2�.��A,saZ�bG���\A�c��z�J�r�f�S�e��hl\�oK]�O(��^�b,X-��j�V���FJl/NF���h����8S���>�����<��qNq��p���m�� ����>��8.Tz���
��X�+:-)�K��R��U&�j0a�lm��r�;�1��
��F�_������P������F4�YGIxJI�����;��&n������)�+����o�^�sb$:�Z�I�I��)��I9yvA�T��Y�rbv�&�\C1�D+�V�N4��8v5�Q}v.@�h2�"I�n��Q{*5g4�)�*�=V"PVB�`���w1��#�V�������_���FR��4����8�t���.��~���hy@)�C�S�����qDqi�
�l
��5m)=���8��3\�~&Q%n~l����8Q������b���m���R���fwn��3%�%T���T��_�e��)�s�c�1�(���h$OK���8.t��;oA�������%�%T�P�p�d��((+�rS�p<��UR�x��q��Qr,����.a�Z^/)����(�n5��s���D���
NdFj"�"��7l�gEJ�����������sp��/���=��8�P;��+�c1�C����m�Kq�jpT�g�D�SV����--)-��Qkt1����I�h�Hi	���&����"�j-y�}�c_u@"h���$��R�����@�X	G�dz"��l�hwHa��f�D[2�w[�%"�%@|J&Y�U�K�
�mG���Nu>{��+-��	�q�R,�����A4�i��)�q��Q�/�5>�,iL���?�0��0��������e(:�m�7"e%4�KI)_m�v�q�D���f?l	)��p���-i�JD�Jhp��R4X�"��k�J"RRB���>�y�mS%"%%t8L�.+�Y�Y�^��*��%oD����%%"%%T8R���$Q����u��	0�N}��3�"=�k#D;U��z��
oG�c�r|^v��R��|�����Bn�FIRF�v�����Q|{r|�W��1�E����l�^P|/T�����:Y��&��6���U�/'�+�Gu!JH{e��a��@���TB��3�V�	�!�w��WK���6�����\<��4
�0}*�3Z�������
<���U�Q=��`�$��=��NT`N`�`fd�$[���t�R|��h�G��������l��(�3�����d=S|�:���V�������i�0�w��?�O>�:`n��%�w�;~�����D6�y+�S�W�"��=����	�
Sx����<=Wl�~��m�6L��Tm�����e�b-��m�6L�������`6��;���O�M����3e���A��RJ��TQ�?b��������&�`���	c&gJ�)���0����%!�2�_:q8S
L����V�(�JF�*��e����B�{q���uBG��o�N�����/�$�C���K%�L��S�������(���wH���_L��������(�K�t�p��F?��W�r�"�����<p8SL@l��g�2���	�w�2���`�u��,��cs���L	01��e�����~D^����Q|g|������%3�@���9�w��O4.�_���l���gJ�i���q$(�j��7!�7��%�w���2�@EpB=v�\M�o�8�)��/�����������)�k���;�S1)%�l���K���j�,\��}�F�/����<p8SLu=�bK�8�L��n7�|>�bL�]:�7�PN�(.=��{�&���V�-�fw(�
I���CTw��w�K��;���b����23s�������J8��_Y��&T�D�J�(T,D�R�G�
��2Q~���W�}�%�I*Q������8���b���s��,��S�������o���F�%��p���
�
�m4U��V$8���6�m�B	�*Rw8�?A���)������c�j	8aCR�����)�q�: �Z�m�&��9:b�`�(�3��el�PV�V�K]Z`�S�*}��S>lse$
sK����P���J�����	����������T9p.�-%
���W����L9a�����w{
q
�DT@`'�T6�*�\n���P�C$�l������Ym�r��8^�p_�<x=�(�������p[d\)�QhH�a�Hos���j:�t������[WP<gS��,A��:��R�C�����d+Z:5{��B5	��l��A�����v#�Q)���"�mpx����M��}�c_���
(
��-��L�[�vT�v(p���������B� :6y���vT�v��a�O�m6e��m��#��H�O�Z[L��*J�R&1�#;*%;48$�oC�k����Dg�r9_���,���S)��9�d�l��z�'��G��x�pJL��������!�+�qD�56�{
��J�
��X=�JpEr�h�,K��J�

����8T^K�t�(�+�������\(������)�k�~��!���bZY�a��:�r���	�![��(o��~��8^�._05�'�>��F�����v�A���s`C���J:���Hw(�9�y^�����]�cW�#$�����$�#4�8(�=�~@Ps-�B(#j��$�w�A��P���Yob�Q�o-o�}�c_s�s��a�*Q�c���(�
�b����m��d~L����w�����q���d��CF�W�#��H�O9%0o��$��%�c��Xs�]�Txl6��h�Z��'��J�B8���TE�my�O)�S�~X[b6)FP-I�~����Lu���O_V�������F�b�!������$�FIE�a<(��=�8�(`��"����`d#�A�]��������7�yZ�xPW�}r��%��������8�)�k�?�]����+�������x���X}������-���x������,r�����z	��<�3u9XJzXE���c^���$��rK%��8v48��7��
V`�^�����<�7|��{r�:��R�C�I�\L-&+$=F8�/(�*}������%��hIN�S��}���M���e������������Zl�5J8�F}�7����>�X�K�y=M�X(�#�F��f�T�$���ib�q���K��E�������D�!���%${[��R�Cs��>t���,{m�ub#�a)���&�l5dlM$i;n�VM�S��{�y��R��������q���j�%��p���.<IKI�y�!88N>�w 9O-�����R��� �?I�^�1i���n?���|4.g���u�����..p6�:e�jM����0^�`���9
�DAY���%=�"��V��,a�~�d�*��#=%=8���+���WA�qK�`������
d8���D�M�q�(�=9�ev��PM�6�HGI�>����Icb���m�������X �}�U�k���P5`����1I�4�����p�����&���"�"2��zDqipDc x���4��ul�S�*9�\��6n���MG@S'#�@�)�`?J��Jq����c2$0�J�Hz8Jzh��z]'���b�)�s��v�)�Ip���p������N�K	3�$��������T��R����Y����,��8�T�f�!{g����izm^S�:�VpL_���i)���p���mG�{3�����g��xEq���G�an��C��cI��#�����^���&�Rs��$��i"�����Q|I�F�+N1�h���R������.z�}�[^7{��G�b;wg��tl2rt3��)���7����N%��zl���G���X0���S-qP�����Y+�7e�����������0�-�9���>QG:}�9��]*�J�][��S�C�o9��:��&��][��S�C�#e�}��uK����� �s�Z�&x��dB�F��S�C�Ob��A�2V�K
[��9�q��"D�$�ml��Xh�[tAq\���GG���`V�����A�]�����,nS�e�u��������;�0e{�-����'#���L�Mpi���)�����f0�&g$8����p@j���NVZ0n$���#=�u<z�Y���.=��m���M�H	��,����E�?(�1?�6L��v4�L���P]6l2b�]�oW���
��1�"���m���aF���'�7W��0u��J.�&���
��
^�'����-a�i�v�Sx�*�4b� +ei��c���@e=!����"��������C��Pe=1p��
\p|��'����w��r�)�M�X�1��1�w��'��!�h�n�R�M�N(��}	��b�_DXM����wJ�����R���������Oe����;���s��
������n�z�Sx�x�
����.��0/��F=���z���ER������wI�]���-��d�<O*�N�����w��g"��n@Yt��������V]�F�(')���	�K����z�.`��ZD�3��c�����^)�?,���l��.��-]��O�����7o����}��n���o~X��������o�}����������#��������w��o�����s|E����g��o�������~���|��[,�B����g����2��z����[���n���g�W��w3�?���_�������|�k%�����y5����_=rn~�_�IZ�������w7?�}����T�
u��y����o����w~��-Q��o�!����
����l��?���s�o4go�q����������uw��1����$�GE=�5������m�	�F�?L���}���Q�����pvn�������c�[!7[��������o�}���[���o�����\��u��}��Q����,i��i���h�*\�XS(]�`�%[�������o��������o����o�lK�:G��ty����7��>�C�'}�%��-��jF�����'�G�%,N���������V���]�-f2�:�~�����/0�b�~r��
}�����/���nz���C����v��o�DGk����R��h�,;xsc���j���Yv��s���4/���������h��6����������dG[?3���d��'S��~�����
��d�P'����gd�l}������";����b�-^��������sQW��8'<38�6���?N�Y����^8�Y�,;6�����	��������Z�,�g��p��E��20�q��n����r�����DD �g!iZ�/��e�����c}�v�������[�J��v�i]��#���p�����Z���!f�]�h'��qr����l/����,���$������N��r�f��������_V��t���3	��l���+\���>�6�l���u��0|���)�+���Bf�^1��1�����;=k�=r��E�o<r��t�;��o ��tW���{��u��)���Y��v��3��d7�|]���:�VH$H�uo���"���ZW ����:))~�����ic��fr
�h/��O�}�����9�������G�~��T�	[�vR���c���"���S�>0/��|�����#�'������x%�q!��n%�1>aF�+�/�����]B�"�|���������o�6�d���8�c�J�1�����|S��l�/��&��y���u
���h/�H��L'c����������1���3�vrv��5�u��!Nk{�|��l/�S�����e?
x
L�|��ut���[�l��d�_d%�IGl_���d;q>�Mk� ~��,����rY��ZH���]�v��+�J����������]D���L�i���y9f����u���������u����;.�4�v#esb:��h?�(��,��<sW��1�v����^�h'��M�2=�Y��g{�n��o<�Y��g����J��g�n&�#�y��1�L�3��~~�g�L+�^~y�\�|����yl��t�f�~�L�c%�k!f��Z��f!�l�H%y�-�����;�~���y���Uu
��8��l�O_\|;d�
O������X��7�6X���'y�8��d�����E���:9�����{���L�E���g���";�:���L_}k����&�At�}
<�'����O`����+�^�G������^�G�,��{%��E�Sf�+�^�������c�k�B(�G��&�J������:yf��J���l������}b���S�hl�������$Y��U�j~���T<�i%/�M���,��7�F�[�J�����L�e����d���,9X��d���"�����-�i2�������!:ff�����e���%k^�"�\,��m^�*�+�Jv���~��d��Xn�^�����)��K��M�E�Z=g�d#��j�|����6V��O/�����+����N!3��6�AA4�����,���}�]��A��)����K��ML����d'B�N�Y����(��/M�h��%I�����d����0�������|d�O�h�$z���F>��XEw�������Sf�,�%;i���l�Et�E
��a��X�d+;�i����~�^D;]�f��ED��V�Y7Yfn�J���`.S�R��l��@���]�vZD	�4�d;��
X�y^�~!����4����}>���'�I����b�����~S��0�j%;:z����d�����7Kv�$L!f������!�v0k����~0��b�UA��,K�%�E�����������G�����0��-���A����h/�k��qP�����7����+�N)�m�;k��3��X���Y�_�P#��d���a��H��Cf6\�%{E
��tt��tJ"��p�QXQ�����Q�w��${iR�v(E�^7�����������)r�$-�cU:f�0K�����%;iRb��/��m��\e>X/��#���>��[\�
s6�"��8��q�Yt�]
�Om/����z���Q�l���60�������d�u�+�^ow�2��d���a�Xw��C`�����S�\1��P�����>���e�h�e���1���}6�(���,��:����,���9pv%;�&n�O����U���,���������h�q8�$~%;�&��q]�Y��A0l{`z5�,�94�����M�N��h/�gyp;.����n�9�������c�����(3/d��r���-�DwudN`�%{���[����>���":��6������n1�����#����g�n�({B�OA����;��7��~��n����qr�.��d����Qt�Mb�h_d��q��P���vff�-��\���	[DG��<n>�"�����?��Zz��e�h�>�a^�l���F�����It��@K�RwJ�O��8���/o������;6
%/Ny�6Zd\���
�gv��%�~�0e&%<K����UM�T�G�'�������������YX��c��x�b��yeJ��Yt���#5���<lQd���,:�B+�T�Yt����l���{8q�����>@��+���g���	���h��O���Y���$�>N�2�o�'��;�"�/�7��C,{$�|"����5Nf�-�%�.�-n���
���/���	���,:z[��f������)r����h�3�#}���/&�����t�;R%G	f���0U�s�,9����q�Gf�����9%Go�a.n�����Z��3?y[��-�c-��{(f��_�O���������@C��aI���������
�>�������#�YD�"23��%�,T�I����^�#;?v��3Uf{�Y��Vv�\�12��(���(�+�`��&v�h�c����%;}��1ff�>���h�v�� �c��Y��	��v �g	y2���d�E���v�{u<IS���h�e8v��E��2�F_D;-�O�����v:��!f��,��x��:�
�k.�%-��Q��y��uczf>�,���t�if�n:�-#���/�r\P��V8f��,����;���Z��L��������A��I���0Kv����A�h�o�,g�%�����C��|k��%
vcfld��Y��S[�s��4�X�noE���%����Q3��E�K��{�����;b���?nJ�2��yc����Ds��'�E{i�{�����9�x������n|[�5�
����[�;�$X^,H�af^����"�#��-���1��h���^��T�O�9�`�����$�f�NZQ������v����\I^��^�0��,���W&o8�v:���w��_�����+��r�y�(�k�[������d�g�n�)�;��^=�p;��u���0Y�Y��Vdf��,�M+�V%��^L:h���e��]:y�X�t{�`�j`{� ��|D�(��k����K���4%f2�,�I#����ug�N��a�,��<ln#�Y��1�\�5�v�����m��������Ff_Z��XvZ����L�����Zn��,���J���Y�����f�^��P������`yi?��`�S�d�x�s
H��
n������S�
��.������sP{,�����
e��!����2Enc�Y������E��
s��R��/�������\v�f���_����1(�R&��Jv�?�id�d7s�����j��~{u����2e(�kO��g�w9K~�:��qN��N�����EQ��A�W�)��g>�,����gO���J������Zzvv����P����5�vS��m�9��[�c��f����h��Z�#e|����DI/��m�Gw���s5Sa���IGB����$���s�#q3B�~��6�e��q8���og���iH-�7����;���G�O���o����T��"���SS��������y�
�@r��q��xyw�O�u	Bv�^���}��r'NM���Ie�:����0��Yr���s��g���.��`r=�����5����K�2[%.�
�'i����f�m�_�w�}�p�����#X���7�^��������O������>uu��509�Eyv3?/o����s8����9��mks�L�r�������J��>`�*st�,9X�<�����Yt����[7�6����s�o�������������r��v�{���g������V�c-�M�%&K���6/q����G$�)3���d[@��x�d%;Vc�.���d�n1�����+��t��xm��>����]��x~^��y��_������_`[,���";v�0
�w��l�&�����i�d'm����N� �K������"��Y4���x%;V�q���XD;eR��r�&f�N�T#l7��eG['�nE��k�l�q����9M�;p����f&f���l�<(2�_�J����;�p��Y��B���]o+�^���uZD�S��&_d��h����O�p�s|Jv�\���& �����s����Da���d���y
��<��OXnQ�,�/:5�"�Ev�DdxZd�8A�O�����<En��,�+����3K���������Op�Y�d{]4�=4~%�/�p�Xy�O�gT,���	f��"���OLe%�k!�A�+�~_$0O�J�K�'z����k�}i�~w6��cV</�_(��v��w6Mf5�Jv��]�9U^����0U�(�E��69v	�JvtD��3������h�mX����E�W<�'��;Zd���������'2�)�"��j`/+�^��c��dG��N���,��q�iv\W~����0�=���"����J���L����bb�n�1>�2�Sef������<%� �Y�������BD���v�"s�Jv����1�����t)NL�?K���<yf&�JvtD'f����(�����;�x�(&��vRhc���B���>��W���	��d�(��z)��S�l�h�d2_�����/�����:�w�A���~@���Da�-��6�;�u%;(�x�������
��f4Kv�Q��4.�d����)q��Ev�V%�&f���6X����w��,��
�����gNV[D�.����|�l�
�Q����Jvp�b��,�]D;�rn���`�d�B`��d[3����[���gq��d���`���3_o%;��B��lY��l�,\��i���:B�Iy,�c���L�g���v��w-�d,PR������+�'8�{�u�����uL��d�����I������0��Yr�� Z,���h��/�ybk��e>J,�c�����%:H��>]�*�%�,9X��&a������m�s+��6/@d�5+y�����B����.���.��-�.0_\����[w�e
�W���":vy��#�":��y�(��V��=�\'�VV����.���_����-O�;�k�m`��[�1�_-���������O��h����H�M�b�&T�S���7�v��������l'�~2<�@�>KH�g������
3�b�������YH��j����<1�2�����u��8��Y��v����]p����;�3��h�)1�a~�E������L>X�vR�b�������+��g������mb�4�l��>��r'|-�_����#�EfW������7��rZL�Q�]r�^G�M�[������������������%�i���"������|%���.������lFa~�Y�����c�^��!��2��l7��1)�E���-�^��h'����k-��6�ppwe�����L��g%�/������]���"���������~)�w�V|?��$��F
����_gI� ��I/��sk��n/"L�{�����=�z��4����h?�`w)B�^N�a���%�,��k��rA`-<��ZD�1����a���yg���E�=T�,�0���K�������X����+���J���U��l?�;3�kW���o�����b<�n}��~7{�����73(�%�n�H�E���U��J��fd��>Kv�8���,�M3�S��c3���Y���D&�8Kv����,�����h?<2+YW��|pv���T�����^D;�5����m>�������l?�3�H�d{y�~b7�E�~�7�
�J�#��|��E���_�#��>�D�\���Y����LT�<���"�i����Xd�q�L����f�'����2��Y��fXv��l��T�P��o�ke���~	�.O�['2���������~/����{v�E���]�&t��{�(��l?�;1��J������r^��3��[8����������V����'��tp3I�+�f����~lq��fS�^�(9vq6O��Xfm�<I��7�q�,:���)q�����q[�F�dzg�)�����2�x���X��]��7J��zi����Yr�����;;���xvb��_D�4qS�Qr��"7�i��]��,:��U���m�g��6�Z3Y�(����/h����";x��.��9��m�@�<Rp2�MV�O,��8�Ut9���[s�F��D�0+�mD�����.����
����fep��Yt��q�x�<�����p�V/
����f��:������,:Z�
��E��:���1J��t�;7%�[��/��r�O�:?Uv����������"��c�'�,��%k&�'s�k$�:l���"]D�n-C���G;�1���'a+��4�������c�N���'����P^��+���g�N�&c��w�h�!��n�����%O��,��}'����%�� 3��hj�u�+3Ky���-��1K��-O������ O��T��-�B�r�+��?"��9����c�'��4Ynq�,�I�1C��h����a��{g�nG;3C�E�����c������o�*7����Sp�3c�Y��W�;Q�!�����f��|(\${�d���<K���+�d���oY?1Y�Y��������ld��z�"=f��,���x���Et���#qQ��7�S��
���=�M�%��81��Y���\�q�h�����������6�v�
!4af.�_����>��=d�t121_�Q��%_�-�Q��Mp���Yt�����Y���X���,��sg^�(8��e=���M�9�fU����d?�����v3n����*���}����q���N�9b����4%����Z�Ff7�E��2C����_D������E��2�d�A�"��7��6����o�+�lg6xD�n��h(���3��,��'��g�Yt4�^�E�(���g6�%�i[Y�����s��Ml'�v�������,~2��P����x���":��r&�:K�:���$d����2Y�g8K�bb:��h7�9s��f�n��f:-���������:��������?+~�=]���~�,�kL��k�X�
3s��v�4z��&�7K�r�3�k��u�G�D���K���l����w6Kw�6����i�����
�b�)��$�����L���� ������N���SZ����q�� �/:���7�q�H����s���\�C�IYB���������E���v8K�I�����:�YN*"��l)����A�~;*��'z+�Q]O�:�D1�P��r�R�ZtR��
�l:)*�-��P����������P�I�z�������|7'{KN~�Hv>;��*��n���Aa��[N����V���J�y�.���,���.N�6�};*2#��*;�_�@?������]u��]���;*2��1��JD�j���hl<��E���i���uJ���5����N�`\�)-P���X����C�m=|����|����VGc�\�LS�FF�9:�)��~z|�%<�<�N:x��|^xw4z�-p������`�J�q�z7}��	���ow4v�e+��U�����o>�0���4��e����z�0�t4��+�Y����n�����h�y��C$'7n���Bu�9�{����������~���?�{��~��7�H��`���]����o����_~��f}�O/�Y���������/�/���o�e��	���������
�����p�{8��/|�RE�O����|���������j��>���W�^>�~��Hg�J[9���X�/�3q�J����J�����������������r/��{�
^~��>���_~t������?}���<`����
f||�����n1&M�\�:���1��N��
g��^s�}[o������m�}[o������m�=�z[g�f����Y��}>���?|����==;�����^��j�N�`��T��g�5������`{.v�����p�;����z�����>�vvL���Y���W���Ql��(�X};���l������b6�����P�����o��=����	}����h��T��s6�	���G����`����w6��(�m�F�`��_�.�
�t6��mG�����l�����6j�������`o�����#Y*P������s���4��H�M3����t\v��x�CZ�����`5����TN��������T��l������jud�`[�`e�-U9������N���Q�����/V�>xk~��'R�������n�NV�Tkt���agEkd=,����Y�!-.8�sVd�~��a��Y�i#��W3X��Ya�n�O��a�E�=4�lXT��0&�:�U��M��USt��UF'uk��wT�C���
�5X���������(�9����;������`U��
-�����"r:f�:�Nc���"�JV��v�_Y]�I���2�
j�5�.����NV�b`��������(���hk_
��UP���b�c������/?���`EO���������BJ,y�T�g�;?h�@gU�c���+z1��Hxt��(�i3�Y��H��(��<?��nu,��6X�����O:+2$�vP��Y�#���+Z#���K+�ns����6��}��U�l����
�G�4���X���B������E:����2��������`�����3�:*��,quT�>j�sGu9��W����|��|��b�6���vT��p�cvV�>v�vx���*�q���N{pV��.���vgUQ�b�A�������`�����R\�:+����`u������^
<��hPT�5�.����u#������g�g����+3*���8�?f�~5��R3-#u�'n��k28g������q�������u���y����o�
��l�w������e�����}$�\�h�w*5�O0��l�w�`��`U�����b����HU������J:���?�X�T�e,%6���O�l��
P:z�y��y+������ie$�(�G��F����i��5�f�9���'��B��������W8�x�78�Lc�<jd�������t��W^��cM�������^	O-l���`�������;dEH'�=����h�w�{���?�M�����l���X���+���h���)�&�����Wah����_���*t������������7���l~mW7���%{�I���D�������u
����� �.��}���ue�����
�L���6-6R�7�0jvRU�5�����o���a'CGc�y��JC��v�������'�V:Z��hot�	
��jjr�.�S�����r��3j�q��������R����CgE'��I�����8[������.[`'�`E�h�3���>I�8�ff��@'U�^��^RE{��L�����k���	���;�-���IUz������/������N;�:�;Pu�"�6��dF8);3�����������>)��^�vTV�*X���6���me)LG�s�l�0������	�`���1�;�����\�-��f_�`�%w��9�=�{nN�b>8��I��j�-�����5��;���2��pR�G����s�k�-��!G�3�v����lt�P`����%�����
����2��7jc6�M@g��@7;`�rGe���G���v>��{���]�j���u�6��*28�2d3��8*2#o��q&�U�Q.*,����b�OeT�6��jW�������`���d�N�������u���J�J�#�y�S�F�����d��/�h~����^wcx��IU%c�Q������Z=��H�������i7��:)�T����,s��9;�9��Q�U��2L��Ka6jGCU�C���������	�y2�`��SzR������6������up4>{(P2i�������TE}����:M��8�i���'�%��0�����+�I������T�L��w?���]XO��`�4q#�.d��d'��`���N9�A,F5���<C���v���W:�� �_Ni:�;{8�!�
�!^��o����"$����m>j\C��u�:��On���ir4��vP������L�I��62��Km��d��=�}���`��.J]M��v6���#��6n�����+��T�YO�C�k)��:�{������
m[��NEc����P���^�$[h,�������Z�
^i��06��&^'�g���6�5����4l^�x*�zVu�	?������
��<1K�F+k\�#Q�J���Oi%�EwGGc�]]KP����UG�{42���/������Z�v4����E�9�I\P����Uw@�K'�}]]�t���_,npL�\��Sa��&�=r�3��+d�����n�I%�u����&�A����0���|@�����`OGo�x3S�2������7�B�7h:�|��-��	�m��y���|�hb�/�<������'e�a'���g����L�9U�����5Rd���4Q�gN�V�NU6U}�o����.������9*'E��FlpQ4R�"e�vTdF�9'|��^�A�F;*Z��'�kv}��Z��;C�!�N��X��E#eNJ�8)�5���QU�/'7P�&
��*�ou|\?����
:hGe)�-�]V�)��6�:�[<�J:1Dz���T���T�0���
ge;���a[LGEf$>�6�����F~:���6��}�m}%ku�3q�Y"l���D44���)�-��s������F���Y �n�.�f���*#Nx���jU��S���Uq`����\|�t�^��pX�lT���:_Ao%;�
p8r�I���LN�B}x����Wd�v�UjWi���vTd�n��Q�t}%��v�i�l���L0C��S5�)Y���*��5��c;)�;7*�����+�.*����j���Z|U$x/�I�\,�y��
�Y4R���l���8���.'_�]Ge��v�H��q:����b��SO�A`V`��QY\��6����hd`}�Q]���Vdj���K�o���c�TR��E��y��	#p���jQ�52�;�"�9wK0���,������
���	84�IY4����Q���P�P����1��j[Yq��
c����|���P~�
.8)����"'e�8��N�Z���g:*2c�Lg��A����>���wTV�N��BG�(�
������&�:-����T9�* 8�;	�M�����TGc�����p
���`�����`��y����|?��]�5C'e���qR�@]�����N%k�(V��TqA�'e��J�k���z������"m|�c����{u��E�c���H��r)��>�P�?ZorNR}�'�K�~oSl����9���;`)�������k��u�+�������d�q'L]��5.�	{���^w;���������`s�������������V6��u���h���0�q2�����_#c��l����`_w�	e1;��xP�~����g��Q���(�6��vv��f�7���_5�zY�����?����?`������o�����w?�����g<=&@����u������3��bM��6X��h�y��j<G��:k��51
�{���_�����&����:���	U��tA_��&d��zJ�&�`�_p��qGc�[O�hC�����j�$<&�l���i�1�X�����6���l�������"��LG�v6���X-l������.2��W�������F��,����'�	��p�ll���'��z��l�R��kw�����p��c�U�*�v�I\��}U-*]`�`o0p��-��:)ZM�
<s��������������\<Z�,���.��Z��D+)�����-��������[g�}�R=3����Z�r,0?��j��������v9��uG��S�?6x~������^Z���l&��UR7N��3X������`�$��Pxt�p��orV`!�Q���x�ag���l��t4<��m�N����O�;��&������\��	gx6<��4)tTr�p&�T��~/03�l|���t4:����Y]���)�`u����`�s�b*0V��'���.��>����^1��.?�g�$T�"�jhN���:b�� _GU�_k��dg�����>��]��>�)ZM���Q�j*����`����VZ��lp>Q�N�x���E��zq�QUF��@������i�L6:��-������X/����b�v�F��Fg��*p]���`U�lx.�`uO����`u�$L��49�l0�����o)���'�����uT���x7�������?���l��}Y�����e��Q�jjy8�Q���*v+P.y��Y�f\Ne��������X�exe{���i�z7���*������
;����*����xr4�?�T���uV������"�t���Y��`�e�:Ch�W��|�Uh��^���)�b;:*ke�3�W��a�W�:���u583��7�7�����]��6����Q;k^[Q��F��
N��lKj�����T�@G9*����
��:*�f�)m��yg��Y��|6���@���`�]F>,�������������`�V_[�������R�g(�}����������n	k[�g�%��6:����,u��sy��0���,���t��D+p^������/�����Oh����+�%�l��S�>~������9�����EGc�KW;��+��X���F�V*��NcO������M����k"�p��l��[m�w1:�T6x��X�j��R
pG��^j������q�q�I����g�M�����N�T���7x��l~=��:��d�7�0�����c�O�!W���N�N�N(�QQm���+����Kpe8�ZtNP����G<#+��,�2����wV�R���2?��������\�o��gl0)��y,�`����v��{�v^v������F�(�O���Ez\�a�1X�!5��v8��hO+�yV�L�����D�"=������H�f�<Dm��E�Zd�����#��{+���nv;�bF8)�����Q�����*�1d��X�N�0��4P�.���*�U���[���`e�q����"3�Y'>�Smhm4�WpT�J�mp��`uq�Nu
:������l�U}��-�
u������g:�,��J�j"���Gi^�h��F�&N����,�uTX���
�:Yi����@>'eYY�IGU+c�2`�U}����*�^6�`�H���7M��E��z�`U��	o(wT}��|�Q�W����U��	�V�.���]guu��sVW���;����e��7����eJO<���h�*�Z����2��`k[Gu�w�cP���i�I�����)]y�E}"3�V��TQ]���E����$���,_�7����(��Qa��o�8+��t�AGe%�5�;*����;�z���v�;��~��Ql���w�e������3����Y�$��<��N�h"��%N��t�:���h9kN-[j�I����wRc�n;��9���������b'���a�
�_'U��������{�����VF����vV�A��k#e�@�V8*���U�����R]�+9�|O�}�Y�!���D`�������*�5/��c�A���&
��������{�����Zm�*'c�K'��s��y�������}��t��~�v5:k�f~N����f
6/�;h�����>�,(60���������/��_nh��;�ABg��[\)��Ke���S�/O��y��N+�h��['���/�����T#8��1��'��<�;���p��`o0pJ���3����,
��9����)��n��
8y�qOl��9��p���[Vz���7|�����u4|���Q'c_l�#
��D�G�k�X��B#�W]��e����5�����FF��e��
��5.c��|����5wp���9U�kNF����'42��O|<���8��6;��������Z�S�:������v4���'�u��a��T+W;.���hPJ��j��W:��q)m�l����z�/0����b#��cZ��������]�gG��J�V�.��8���]���3vsk���JEe/�� l����itR�Zv�������v���������@A&'U/j������F;y����y�~�-��g�vTfF�ME���h���}G5f��Nx9��O�eM��.(���j�-To����}���Z��h�.[��L��J���	oG;)zQ��'�dx���mGU/��mN����T��
vl8)��x���X��a��M�T�g`~�LjD����!'�=�Q�>�,����Vq:*3K^e�����:������D�;�,���V]l�'�N���4�_UF���{�W�F^-�)����_�.]�2���,��b�N����6:'u�9���*�k�����cl'�
8���io���~��"N�qj�M�&7RU�/��9^��%xY��L��q�jtEn�64�Q��=����������������_�:k�B	���d�V�J��`q�"�lz�8���ke�X�qR����l���W
����>����C����|v-�>�V���9j��W��y��6 ;��4G'GMg�d���^�v2���Wi����QuEe1���;*��/Z�qT�pWK�aG�'���
��0rR���C���6��p�/����+C/Y��V���E��^&G��H'�+�T�����e�����8�Z-=_n�,��pRw���T
����k'�]F�����P�`�r�
���������|���&��B��0�����a��E�B������&��+0�pR�?��'a~������'�XI�j��-2!x,�����o���,�F��gx;�I��l��,8���l�?���X�RI��;);��mE�qX�y���^e�I������>����
����������vv46������4�4�������e���.8�����3A�Ig72���#��(3��Y3>�bV���U����4?���UoY�{&L������_s4[;��v���p��
�
+VMO>~���4�hd��;,����h������nd�3Ya/����������&
�tku`��p4��mv��
6���:4�����f��F��������O�j|���w�����}������j��o��O������w�>����������{��������������s���PK%X5.��wPKbi�N�l9�..mimetypePKbi�N��_��"�"TThumbnails/thumbnail.pngPKbi�Nh#Configurations2/toolpanel/PKbi�N�#Configurations2/menubar/PKbi�N�#Configurations2/statusbar/PKbi�N$Configurations2/floater/PKbi�ND$Configurations2/toolbar/PKbi�Nz$Configurations2/images/Bitmaps/PKbi�N�$Configurations2/progressbar/PKbi�N�$Configurations2/popupmenu/PKbi�N)%Configurations2/accelerator/PKbi�N�<s�Lc%meta.xmlPKbi�Ni��P�(
5'styles.xmlPKbi�N��h��I.manifest.rdfPKbi�Nq���y�,�/settings.xmlPKbi�N9�3,;4META-INF/manifest.xmlPKbi�N%X5.��w�5content.xmlPKe�
#13Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tomas Vondra (#12)
2 attachment(s)
Re: Optimize partial TOAST decompression

On Sat, Jul 06, 2019 at 05:23:37PM +0200, Tomas Vondra wrote:

On Sat, Jul 06, 2019 at 02:27:56AM +0800, Binguo Bao wrote:

Hi, Tomas!
Thanks for your testing and the suggestion.

That's quite bizarre behavior - it does work with a prefix, but not with

suffix. And the exact ERROR changes after the prefix query.

I think bug is caused by "#2 0x00000000004c3b08 in
heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0,
slicelength=-1) at tuptoaster.c:315",
since I ignore the case where slicelength is negative, and I've appended
some comments for heap_tuple_untoast_attr_slice for the case.

FWIW the new code added to this

function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

I've added more comments to explain the code's behavior.
Besides, I also modified the macro "TOAST_COMPRESS_RAWDATA" to
"TOAST_COMPRESS_DATA" since
it is used to get toast compressed data rather than raw data.

Thanks, this seems to address the issue - I can no longer reproduce the
crashes, allowing the benchmark to complete. I'm attaching the script I
used and spreadsheet with a summary of results.

For the cases I've tested (100k - 10M values, different compressibility,
different prefix/length values), the results are kinda mixed - many
cases got much faster (~2x), but other cases got slower too. We're
however talking about queries taking a couple of miliseconds, so in
absolute numbers the differences are small.

That does not mean the optimization is useless - but the example shared
at the beginning of this thread is quite extreme, as the values are
extremely compressible. Each value is ~38MB (in plaintext), but a table
with 100 such values has only ~40MB. Tha's 100:1 compression ratio,
which I think is not typical for real-world data sets.

The data I've used are less extreme, depending on the fraction of random
data in values.

I went through the code too. I've reworder a couple of comments and code
style issues, but there are a couple of more serious issues.

1) Why rename TOAST_COMPRESS_RAWDATA to TOAST_COMPRESS_DATA?

This seems unnecessary, and it discards the clear hint that it's about
accessing the *raw* data, and the relation to TOAST_COMPRESS_RAWSIZE.
IMHO we should keep the original naming.

2) pglz_maximum_compressed_size signatures are confusing

There are two places with pglz_maximum_compressed_size signature, and
those places are kinda out of sync when it comes to parameter names:

int32
pglz_maximum_compressed_size(int32 raw_slice_size,
int32 total_compressed_size)

extern
int32 pglz_maximum_compressed_size(int32 raw_slice_size,
int32 raw_size);

Also, pg_lzcompress.c has no concept of a "slice" because it only deals
with simple compression, slicing is responsibility of the tuptoaster. So
we should not mix those two, not even in comments.

I propose tweaks per the attached patch - I think it makes the code
clearer, and it's mostly cosmetic stuff. But I haven't tested the
changes beyond "it compiles".

regards

FWIW I've done another round of tests with larger values (up to ~10MB)
and the larger the values the better the speedup (a bit as expected).
Attached is the script I used and a spreasheet with a summary.

We still need a patch addressing the review comments, though.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachments:

random-bench.shapplication/x-shDownload
results-large.odsapplication/vnd.oasis.opendocument.spreadsheetDownload
#14Binguo Bao
djydewang@gmail.com
In reply to: Tomas Vondra (#13)
1 attachment(s)
Re: Optimize partial TOAST decompression

Tomas Vondra <tomas.vondra@2ndquadrant.com> 于2019年7月10日周三 上午5:12写道:

On Sat, Jul 06, 2019 at 05:23:37PM +0200, Tomas Vondra wrote:

On Sat, Jul 06, 2019 at 02:27:56AM +0800, Binguo Bao wrote:

Hi, Tomas!
Thanks for your testing and the suggestion.

That's quite bizarre behavior - it does work with a prefix, but not with

suffix. And the exact ERROR changes after the prefix query.

I think bug is caused by "#2 0x00000000004c3b08 in
heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0,
slicelength=-1) at tuptoaster.c:315",
since I ignore the case where slicelength is negative, and I've appended
some comments for heap_tuple_untoast_attr_slice for the case.

FWIW the new code added to this

function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

I've added more comments to explain the code's behavior.
Besides, I also modified the macro "TOAST_COMPRESS_RAWDATA" to
"TOAST_COMPRESS_DATA" since
it is used to get toast compressed data rather than raw data.

Thanks, this seems to address the issue - I can no longer reproduce the
crashes, allowing the benchmark to complete. I'm attaching the script I
used and spreadsheet with a summary of results.

For the cases I've tested (100k - 10M values, different compressibility,
different prefix/length values), the results are kinda mixed - many
cases got much faster (~2x), but other cases got slower too. We're
however talking about queries taking a couple of miliseconds, so in
absolute numbers the differences are small.

That does not mean the optimization is useless - but the example shared
at the beginning of this thread is quite extreme, as the values are
extremely compressible. Each value is ~38MB (in plaintext), but a table
with 100 such values has only ~40MB. Tha's 100:1 compression ratio,
which I think is not typical for real-world data sets.

The data I've used are less extreme, depending on the fraction of random
data in values.

I went through the code too. I've reworder a couple of comments and code
style issues, but there are a couple of more serious issues.

1) Why rename TOAST_COMPRESS_RAWDATA to TOAST_COMPRESS_DATA?

This seems unnecessary, and it discards the clear hint that it's about
accessing the *raw* data, and the relation to TOAST_COMPRESS_RAWSIZE.
IMHO we should keep the original naming.

2) pglz_maximum_compressed_size signatures are confusing

There are two places with pglz_maximum_compressed_size signature, and
those places are kinda out of sync when it comes to parameter names:

int32
pglz_maximum_compressed_size(int32 raw_slice_size,
int32 total_compressed_size)

extern
int32 pglz_maximum_compressed_size(int32 raw_slice_size,
int32 raw_size);

Also, pg_lzcompress.c has no concept of a "slice" because it only deals
with simple compression, slicing is responsibility of the tuptoaster. So
we should not mix those two, not even in comments.

I propose tweaks per the attached patch - I think it makes the code
clearer, and it's mostly cosmetic stuff. But I haven't tested the
changes beyond "it compiles".

regards

FWIW I've done another round of tests with larger values (up to ~10MB)
and the larger the values the better the speedup (a bit as expected).
Attached is the script I used and a spreasheet with a summary.

We still need a patch addressing the review comments, though.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, Tomas!
Sorry for the late reply.
Thank you for further testing, I am trying to reproduce your first test
summary,
since I think the performance of the patch will not drop in almost all
cases.

Besides, If a value is composed of random characters,
it will be hard to be compressed, because pglz requires a 25% compression
ratio by default or not worth it.
This means that querying the value will not trigger the patch. But the
first test results show that the patch
is slower than the master when the value is composed of random characters,
which is confusing.

From the second test result, we can infer that the first test result
was indeed affected by a random disturbance in the case of a small
time-consuming.

We still need a patch addressing the review comments, though.

done:)

Attachments:

0001-Optimize-partial-TOAST-decompression-6.patchtext/x-patch; charset=US-ASCII; name=0001-Optimize-partial-TOAST-decompression-6.patchDownload
From 523786a03ae770f1edbd360a47336ce4ae619fbb Mon Sep 17 00:00:00 2001
From: BBG <djydewang@gmail.com>
Date: Sun, 2 Jun 2019 19:18:46 +0800
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/heap/tuptoaster.c | 54 ++++++++++++++++++++++++++++++------
 src/common/pg_lzcompress.c           | 27 ++++++++++++++++++
 src/include/common/pg_lzcompress.h   |  1 +
 3 files changed, 74 insertions(+), 8 deletions(-)

diff --git a/src/backend/access/heap/tuptoaster.c b/src/backend/access/heap/tuptoaster.c
index 55d6e91..809a521 100644
--- a/src/backend/access/heap/tuptoaster.c
+++ b/src/backend/access/heap/tuptoaster.c
@@ -61,6 +61,7 @@ typedef struct toast_compress_header
  */
 #define TOAST_COMPRESS_HDRSZ		((int32) sizeof(toast_compress_header))
 #define TOAST_COMPRESS_RAWSIZE(ptr) (((toast_compress_header *) (ptr))->rawsize)
+#define TOAST_COMPRESS_SIZE(ptr)	((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_RAWDATA(ptr) \
 	(((char *) (ptr)) + TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_SET_RAWSIZE(ptr, len) \
@@ -252,6 +253,8 @@ heap_tuple_untoast_attr(struct varlena *attr)
  *
  *		Public entry point to get back part of a toasted value
  *		from compression or external storage.
+ *
+ * Note: when slicelength is negative, return suffix of the value.
  * ----------
  */
 struct varlena *
@@ -273,8 +276,29 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		/*
+		 * When a prefix of the value is requested, fetch enough slices to
+		 * decompress. Otherwise, fetch all slices.
+		 */
+		if (slicelength > 0 && sliceoffset >= 0)
+		{
+			int32 max_size;
+
+			/*
+			 * Determine maximum amount of compressed data needed for a prefix
+			 * of a given length (after decompression).
+			 */
+			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+													TOAST_COMPRESS_SIZE(attr));
+
+			/*
+			 * Fetch enough compressed slices, compressed marker will get set
+			 * automatically.
+			 */
+			preslice = toast_fetch_datum_slice(attr, 0, max_size);
+		}
+		else
+			preslice = toast_fetch_datum(attr);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -2031,7 +2055,9 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datums (in which case the requrested slice
+ *  has to be a prefix, i.e. sliceoffset has to be 0).
  * ----------
  */
 static struct varlena *
@@ -2072,10 +2098,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum,
+	 * since we can decompress the prefix raw data without decompressing the
+	 * whole value.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -2086,12 +2113,23 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 		length = 0;
 	}
 
+	/*
+	 * When fetching a prefix of a compressed external datum, account for
+	 * the rawsize tracking amount of raw data (it's stored at the beginning
+	 * as an int32 value).
+	 */
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) && length > 0)
+		length = length + sizeof(int32);
+
 	if (((sliceoffset + length) > attrsize) || length < 0)
 		length = attrsize - sliceoffset;
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	else
+		SET_VARSIZE(result, length + VARHDRSZ);
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
@@ -2275,7 +2313,7 @@ toast_decompress_datum(struct varlena *attr)
 	SET_VARSIZE(result, TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 
 	if (pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
-						VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
+						TOAST_COMPRESS_SIZE(attr),
 						VARDATA(result),
 						TOAST_COMPRESS_RAWSIZE(attr), true) < 0)
 		elog(ERROR, "compressed data is corrupted");
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b398..18766ad 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,30 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ *		Calculate the maximum compressed size for a given amount of raw data.
+ *		Return the maximum size, or total compressed size if maximum size is
+ *		larger than total compressed size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size)
+{
+	int32 compressed_size;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;
+
+	/*
+	 * Maximum compressed size can't be larger than total compressed size.
+	 */
+	compressed_size = Min(compressed_size, total_compressed_size);
+
+	return compressed_size;
+}
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 5555764..e59fe2e 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.7.4

#15Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Binguo Bao (#14)
Re: Optimize partial TOAST decompression

On Wed, Jul 10, 2019 at 01:35:25PM +0800, Binguo Bao wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> 于2019年7月10日周三 上午5:12写道:

On Sat, Jul 06, 2019 at 05:23:37PM +0200, Tomas Vondra wrote:

On Sat, Jul 06, 2019 at 02:27:56AM +0800, Binguo Bao wrote:

Hi, Tomas!
Thanks for your testing and the suggestion.

That's quite bizarre behavior - it does work with a prefix, but not with

suffix. And the exact ERROR changes after the prefix query.

I think bug is caused by "#2 0x00000000004c3b08 in
heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=0,
slicelength=-1) at tuptoaster.c:315",
since I ignore the case where slicelength is negative, and I've appended
some comments for heap_tuple_untoast_attr_slice for the case.

FWIW the new code added to this

function does not adhere to our code style, and would deserve some
additional explanation of what it's doing/why. Same for the
heap_tuple_untoast_attr_slice, BTW.

I've added more comments to explain the code's behavior.
Besides, I also modified the macro "TOAST_COMPRESS_RAWDATA" to
"TOAST_COMPRESS_DATA" since
it is used to get toast compressed data rather than raw data.

Thanks, this seems to address the issue - I can no longer reproduce the
crashes, allowing the benchmark to complete. I'm attaching the script I
used and spreadsheet with a summary of results.

For the cases I've tested (100k - 10M values, different compressibility,
different prefix/length values), the results are kinda mixed - many
cases got much faster (~2x), but other cases got slower too. We're
however talking about queries taking a couple of miliseconds, so in
absolute numbers the differences are small.

That does not mean the optimization is useless - but the example shared
at the beginning of this thread is quite extreme, as the values are
extremely compressible. Each value is ~38MB (in plaintext), but a table
with 100 such values has only ~40MB. Tha's 100:1 compression ratio,
which I think is not typical for real-world data sets.

The data I've used are less extreme, depending on the fraction of random
data in values.

I went through the code too. I've reworder a couple of comments and code
style issues, but there are a couple of more serious issues.

1) Why rename TOAST_COMPRESS_RAWDATA to TOAST_COMPRESS_DATA?

This seems unnecessary, and it discards the clear hint that it's about
accessing the *raw* data, and the relation to TOAST_COMPRESS_RAWSIZE.
IMHO we should keep the original naming.

2) pglz_maximum_compressed_size signatures are confusing

There are two places with pglz_maximum_compressed_size signature, and
those places are kinda out of sync when it comes to parameter names:

int32
pglz_maximum_compressed_size(int32 raw_slice_size,
int32 total_compressed_size)

extern
int32 pglz_maximum_compressed_size(int32 raw_slice_size,
int32 raw_size);

Also, pg_lzcompress.c has no concept of a "slice" because it only deals
with simple compression, slicing is responsibility of the tuptoaster. So
we should not mix those two, not even in comments.

I propose tweaks per the attached patch - I think it makes the code
clearer, and it's mostly cosmetic stuff. But I haven't tested the
changes beyond "it compiles".

regards

FWIW I've done another round of tests with larger values (up to ~10MB)
and the larger the values the better the speedup (a bit as expected).
Attached is the script I used and a spreasheet with a summary.

We still need a patch addressing the review comments, though.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi, Tomas! Sorry for the late reply. Thank you for further testing, I
am trying to reproduce your first test summary, since I think the
performance of the patch will not drop in almost all cases.

I've done some changes to the test script since the first benchmark,
aiming to make the results more stable

1) uses larger amount of data (10x more)

2) the data set recreated for each run (to rule out random differences in
the random data affecting the runs differently)

3) minor configuration changes (more shared buffers etc.)

I don't think we need to worry about small differences (within ~5%) which
can easily be due to changes to binary layout. And otherwise results from
the second benchmark round seem much more stable.

Besides, If a value is composed of random characters,
it will be hard to be compressed, because pglz requires a 25% compression
ratio by default or not worth it.
This means that querying the value will not trigger the patch. But the
first test results show that the patch
is slower than the master when the value is composed of random characters,
which is confusing.

Yes, I know. But the values have compressible and incompressible (random)
part, so in most cases the value should be compressible, although with
various compression ratio. I have not tracked the size of the loaded data
so I don't know which cases happened to be compressed or not. I'll rerun
the test and I'll include this information.

From the second test result, we can infer that the first test result
was indeed affected by a random disturbance in the case of a small
time-consuming.

Yes, I agree.

We still need a patch addressing the review comments, though.

done:)

Thanks.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#16Alvaro Herrera
alvherre@2ndquadrant.com
In reply to: Tomas Vondra (#15)
Re: Optimize partial TOAST decompression

Hello, can you please update this patch?

--
�lvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#17Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Alvaro Herrera (#16)
1 attachment(s)
Re: Optimize partial TOAST decompression

On Wed, Sep 25, 2019 at 05:38:34PM -0300, Alvaro Herrera wrote:

Hello, can you please update this patch?

I'm not the patch author, but I've been looking at the patch recently
and I have a rebased version at hand - so attached.

FWIW I believe the patch is solid and in good shape, and it got stuck
after I reported some benchmarks showing somewhat flaky performance. I
know Binguo Bao was trying to reproduce the benchmark, and I assume the
silence means he was not successful :-(

On the larger data set the patch however performed very nicely, so maybe
I just did something stupid while running the smaller one, or maybe it's
just noise (the queries were just a couple of ms in that test). I do
plan to rerun the benchmarks and investigate a bit - if I find the patch
is fine, I'd like to commit it shortly.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachments:

0001-Optimize-partial-TOAST-decompression-7.patchtext/plain; charset=us-asciiDownload
From 7167c0e5f78d74a0c02a76748e7b8caaabe65ccd Mon Sep 17 00:00:00 2001
From: Tomas Vondra <tomas@2ndquadrant.com>
Date: Fri, 27 Sep 2019 00:51:52 +0200
Subject: [PATCH] Optimize partial TOAST decompression

---
 src/backend/access/common/detoast.c  | 53 +++++++++++++++++++++++-----
 src/common/pg_lzcompress.c           | 27 ++++++++++++++
 src/include/access/toast_internals.h |  1 +
 src/include/common/pg_lzcompress.h   |  1 +
 4 files changed, 74 insertions(+), 8 deletions(-)

diff --git a/src/backend/access/common/detoast.c b/src/backend/access/common/detoast.c
index c8b49d6a12..4727c892a8 100644
--- a/src/backend/access/common/detoast.c
+++ b/src/backend/access/common/detoast.c
@@ -196,6 +196,8 @@ heap_tuple_untoast_attr(struct varlena *attr)
  *
  *		Public entry point to get back part of a toasted value
  *		from compression or external storage.
+ *
+ * Note: when slicelength is negative, return suffix of the value.
  * ----------
  */
 struct varlena *
@@ -217,8 +219,29 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 		if (!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
 			return toast_fetch_datum_slice(attr, sliceoffset, slicelength);
 
-		/* fetch it back (compressed marker will get set automatically) */
-		preslice = toast_fetch_datum(attr);
+		/*
+		 * When a prefix of the value is requested, fetch enough slices to
+		 * decompress. Otherwise, fetch all slices.
+		 */
+		if (slicelength > 0 && sliceoffset >= 0)
+		{
+			int32 max_size;
+
+			/*
+			 * Determine maximum amount of compressed data needed for a prefix
+			 * of a given length (after decompression).
+			 */
+			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
+													TOAST_COMPRESS_SIZE(attr));
+
+			/*
+			 * Fetch enough compressed slices, compressed marker will get set
+			 * automatically.
+			 */
+			preslice = toast_fetch_datum_slice(attr, 0, max_size);
+		}
+		else
+			preslice = toast_fetch_datum(attr);
 	}
 	else if (VARATT_IS_EXTERNAL_INDIRECT(attr))
 	{
@@ -476,7 +499,9 @@ toast_fetch_datum(struct varlena *attr)
  *	Reconstruct a segment of a Datum from the chunks saved
  *	in the toast relation
  *
- *	Note that this function only supports non-compressed external datums.
+ *	Note that this function supports non-compressed external datums
+ *	and compressed external datums (in which case the requrested slice
+ *  has to be a prefix, i.e. sliceoffset has to be 0).
  * ----------
  */
 static struct varlena *
@@ -517,10 +542,11 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 	VARATT_EXTERNAL_GET_POINTER(toast_pointer, attr);
 
 	/*
-	 * It's nonsense to fetch slices of a compressed datum -- this isn't lo_*
-	 * we can't return a compressed datum which is meaningful to toast later
+	 * It's meaningful to fetch slices at the start of a compressed datum,
+	 * since we can decompress the prefix raw data without decompressing the
+	 * whole value.
 	 */
-	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer));
+	Assert(!VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) || 0 == sliceoffset);
 
 	attrsize = toast_pointer.va_extsize;
 	totalchunks = ((attrsize - 1) / TOAST_MAX_CHUNK_SIZE) + 1;
@@ -531,12 +557,23 @@ toast_fetch_datum_slice(struct varlena *attr, int32 sliceoffset, int32 length)
 		length = 0;
 	}
 
+	/*
+	 * When fetching a prefix of a compressed external datum, account for
+	 * the rawsize tracking amount of raw data (it's stored at the beginning
+	 * as an int32 value).
+	 */
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer) && length > 0)
+		length = length + sizeof(int32);
+
 	if (((sliceoffset + length) > attrsize) || length < 0)
 		length = attrsize - sliceoffset;
 
 	result = (struct varlena *) palloc(length + VARHDRSZ);
 
-	SET_VARSIZE(result, length + VARHDRSZ);
+	if (VARATT_EXTERNAL_IS_COMPRESSED(toast_pointer))
+		SET_VARSIZE_COMPRESSED(result, length + VARHDRSZ);
+	else
+		SET_VARSIZE(result, length + VARHDRSZ);
 
 	if (length == 0)
 		return result;			/* Can save a lot of work at this point! */
@@ -720,7 +757,7 @@ toast_decompress_datum(struct varlena *attr)
 	SET_VARSIZE(result, TOAST_COMPRESS_RAWSIZE(attr) + VARHDRSZ);
 
 	if (pglz_decompress(TOAST_COMPRESS_RAWDATA(attr),
-						VARSIZE(attr) - TOAST_COMPRESS_HDRSZ,
+						TOAST_COMPRESS_SIZE(attr),
 						VARDATA(result),
 						TOAST_COMPRESS_RAWSIZE(attr), true) < 0)
 		elog(ERROR, "compressed data is corrupted");
diff --git a/src/common/pg_lzcompress.c b/src/common/pg_lzcompress.c
index 988b3987d0..18766ade02 100644
--- a/src/common/pg_lzcompress.c
+++ b/src/common/pg_lzcompress.c
@@ -771,3 +771,30 @@ pglz_decompress(const char *source, int32 slen, char *dest,
 	 */
 	return (char *) dp - dest;
 }
+
+
+/* ----------
+ * pglz_max_compressed_size -
+ *
+ *		Calculate the maximum compressed size for a given amount of raw data.
+ *		Return the maximum size, or total compressed size if maximum size is
+ *		larger than total compressed size.
+ * ----------
+ */
+int32
+pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size)
+{
+	int32 compressed_size;
+
+	/*
+	 * Use int64 to prevent overflow during calculation.
+	 */
+	compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;
+
+	/*
+	 * Maximum compressed size can't be larger than total compressed size.
+	 */
+	compressed_size = Min(compressed_size, total_compressed_size);
+
+	return compressed_size;
+}
diff --git a/src/include/access/toast_internals.h b/src/include/access/toast_internals.h
index 494b07a4b1..b8703d8c94 100644
--- a/src/include/access/toast_internals.h
+++ b/src/include/access/toast_internals.h
@@ -31,6 +31,7 @@ typedef struct toast_compress_header
  */
 #define TOAST_COMPRESS_HDRSZ		((int32) sizeof(toast_compress_header))
 #define TOAST_COMPRESS_RAWSIZE(ptr) (((toast_compress_header *) (ptr))->rawsize)
+#define TOAST_COMPRESS_SIZE(ptr)	((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_RAWDATA(ptr) \
 	(((char *) (ptr)) + TOAST_COMPRESS_HDRSZ)
 #define TOAST_COMPRESS_SET_RAWSIZE(ptr, len) \
diff --git a/src/include/common/pg_lzcompress.h b/src/include/common/pg_lzcompress.h
index 555576436c..e59fe2eaea 100644
--- a/src/include/common/pg_lzcompress.h
+++ b/src/include/common/pg_lzcompress.h
@@ -87,5 +87,6 @@ extern int32 pglz_compress(const char *source, int32 slen, char *dest,
 						   const PGLZ_Strategy *strategy);
 extern int32 pglz_decompress(const char *source, int32 slen, char *dest,
 							 int32 rawsize, bool check_complete);
+extern int32 pglz_maximum_compressed_size(int32 rawsize, int32 total_compressed_size);
 
 #endif							/* _PG_LZCOMPRESS_H_ */
-- 
2.21.0

#18Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tomas Vondra (#17)
Re: Optimize partial TOAST decompression

On Fri, Sep 27, 2019 at 01:00:36AM +0200, Tomas Vondra wrote:

On Wed, Sep 25, 2019 at 05:38:34PM -0300, Alvaro Herrera wrote:

Hello, can you please update this patch?

I'm not the patch author, but I've been looking at the patch recently
and I have a rebased version at hand - so attached.

FWIW I believe the patch is solid and in good shape, and it got stuck
after I reported some benchmarks showing somewhat flaky performance. I
know Binguo Bao was trying to reproduce the benchmark, and I assume the
silence means he was not successful :-(

On the larger data set the patch however performed very nicely, so maybe
I just did something stupid while running the smaller one, or maybe it's
just noise (the queries were just a couple of ms in that test). I do
plan to rerun the benchmarks and investigate a bit - if I find the patch
is fine, I'd like to commit it shortly.

OK, I was just about to push this after polishing it a bit, but then I
noticed the patch does not address one of the points from Paul' review,
asking for comment explaining the pglz_maximum_compressed_size formula.

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

Regarding benchmarks - as I mentioned, I've repeated the tests and
everything seems fine. The results from the two usual machines are
available in [1]https://github.com/tvondra/toast-optimize. There are only very few noise-level regressions and
many very significant speedups.

I have a theory what went wrong in the first run that showed some
regressions - it's possible the machine had CPU power management
enabled. I can't check this retroactively, but it'd explain variability
for short queries, and smooth behavior on longer queries.

[1]: https://github.com/tvondra/toast-optimize

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#19Andrey Borodin
x4mmm@yandex-team.ru
In reply to: Tomas Vondra (#18)
Re: Optimize partial TOAST decompression

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during compression. pglz can consume up to 1 control byte for each 8 bytes of data in worst case.
Even if whole data is compressed well - there can be prefix compressed extremely ineffectively. Thus, if you are going to decompress rawsize bytes, you need at most compressed_size bytes of compressed input.

#20Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Andrey Borodin (#19)
Re: Optimize partial TOAST decompression

On Mon, Sep 30, 2019 at 09:20:22PM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during
compression. pglz can consume up to 1 control byte for each 8 bytes of
data in worst case.

OK, but does that actually translate in to the formula? We essentially
need to count 8-byte chunks in raw data, and multiply that by 9. Which
gives us something like

nchunks = ((rawsize + 7) / 8) * 9;

which is not quite what the patch does.

Even if whole data is compressed well - there can be prefix compressed
extremely ineffectively. Thus, if you are going to decompress rawsize
bytes, you need at most compressed_size bytes of compressed input.

OK, that explains why we can't use the PGLZ_MAX_OUTPUT macro.

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#21Andrey Borodin
x4mmm@yandex-team.ru
In reply to: Tomas Vondra (#20)
Re: Optimize partial TOAST decompression

30 сент. 2019 г., в 22:29, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

On Mon, Sep 30, 2019 at 09:20:22PM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during
compression. pglz can consume up to 1 control byte for each 8 bytes of
data in worst case.

OK, but does that actually translate in to the formula? We essentially
need to count 8-byte chunks in raw data, and multiply that by 9. Which
gives us something like

nchunks = ((rawsize + 7) / 8) * 9;

which is not quite what the patch does.

I'm afraid neither formula is correct, but all this is hair-splitting differences.

Your formula does not account for the fact that we may not need all bytes from last chunk.
Consider desired decompressed size of 3 bytes. We may need 1 control byte and 3 literals, 4 bytes total
But nchunks = 9.

Binguo's formula is appending 1 control bit per data byte and one extra control byte.
Consider size = 8 bytes. We need 1 control byte, 8 literals, 9 total.
But compressed_size = 10.

Mathematically correct formula is
compressed_size = (int32) ((int64) rawsize * 9 + 7) / 8;
Here we take one bit for each data byte, and 7 control bits for overflow.

But this equations make no big difference, each formula is safe. I'd pick one which is easier to understand and document (IMO, its nchunks = ((rawsize + 7) / 8) * 9).

Thanks!

--
Andrey Borodin
Open source RDBMS development team leader
Yandex.Cloud

#22Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Andrey Borodin (#21)
Re: Optimize partial TOAST decompression

On Tue, Oct 01, 2019 at 11:20:39AM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 22:29, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

On Mon, Sep 30, 2019 at 09:20:22PM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during
compression. pglz can consume up to 1 control byte for each 8 bytes of
data in worst case.

OK, but does that actually translate in to the formula? We essentially
need to count 8-byte chunks in raw data, and multiply that by 9. Which
gives us something like

nchunks = ((rawsize + 7) / 8) * 9;

which is not quite what the patch does.

I'm afraid neither formula is correct, but all this is hair-splitting differences.

Sure. I just want to be sure the formula is safe and we won't end up
using too low value in some corner case.

Your formula does not account for the fact that we may not need all bytes from last chunk.
Consider desired decompressed size of 3 bytes. We may need 1 control byte and 3 literals, 4 bytes total
But nchunks = 9.

OK, so essentially this means my formula works with whole chunks, i.e.
if we happen to need just a part of a decompressed chunk, we still
request enough data to decompress it whole. This way we may request up
to 7 extra bytes, which seems fine.

Binguo's formula is appending 1 control bit per data byte and one extra
control byte. Consider size = 8 bytes. We need 1 control byte, 8
literals, 9 total. But compressed_size = 10.

Mathematically correct formula is compressed_size = (int32) ((int64)
rawsize * 9 + 7) / 8; Here we take one bit for each data byte, and 7
control bits for overflow.

But this equations make no big difference, each formula is safe. I'd
pick one which is easier to understand and document (IMO, its nchunks =
((rawsize + 7) / 8) * 9).

I'd use the *mathematically correct* formula, it doesn't seem to be any
more complex, and the "one bit per byte, complete bytes" explanation
seems quite understandable.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#23Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tomas Vondra (#22)
Re: Optimize partial TOAST decompression

On Tue, Oct 01, 2019 at 12:08:05PM +0200, Tomas Vondra wrote:

On Tue, Oct 01, 2019 at 11:20:39AM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 22:29, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

On Mon, Sep 30, 2019 at 09:20:22PM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during
compression. pglz can consume up to 1 control byte for each 8 bytes of
data in worst case.

OK, but does that actually translate in to the formula? We essentially
need to count 8-byte chunks in raw data, and multiply that by 9. Which
gives us something like

nchunks = ((rawsize + 7) / 8) * 9;

which is not quite what the patch does.

I'm afraid neither formula is correct, but all this is hair-splitting differences.

Sure. I just want to be sure the formula is safe and we won't end up
using too low value in some corner case.

Your formula does not account for the fact that we may not need all bytes from last chunk.
Consider desired decompressed size of 3 bytes. We may need 1 control byte and 3 literals, 4 bytes total
But nchunks = 9.

OK, so essentially this means my formula works with whole chunks, i.e.
if we happen to need just a part of a decompressed chunk, we still
request enough data to decompress it whole. This way we may request up
to 7 extra bytes, which seems fine.

Binguo's formula is appending 1 control bit per data byte and one extra
control byte. Consider size = 8 bytes. We need 1 control byte, 8
literals, 9 total. But compressed_size = 10.

Mathematically correct formula is compressed_size = (int32) ((int64)
rawsize * 9 + 7) / 8; Here we take one bit for each data byte, and 7
control bits for overflow.

But this equations make no big difference, each formula is safe. I'd
pick one which is easier to understand and document (IMO, its nchunks =
((rawsize + 7) / 8) * 9).

I'd use the *mathematically correct* formula, it doesn't seem to be any
more complex, and the "one bit per byte, complete bytes" explanation
seems quite understandable.

Pushed.

I've ended up using the *mathematically correct* formula, hopefully
with sufficient explanation why it's correct. I've also polished a
couple more comments, and pushed like that.

Thanks to Binguo Bao for this improvement, and all the reviewers in this
thread.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#24Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tomas Vondra (#23)
Re: Optimize partial TOAST decompression

On Tue, Oct 01, 2019 at 02:34:20PM +0200, Tomas Vondra wrote:

On Tue, Oct 01, 2019 at 12:08:05PM +0200, Tomas Vondra wrote:

On Tue, Oct 01, 2019 at 11:20:39AM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 22:29, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

On Mon, Sep 30, 2019 at 09:20:22PM +0500, Andrey Borodin wrote:

30 сент. 2019 г., в 20:56, Tomas Vondra <tomas.vondra@2ndquadrant.com> написал(а):

I mean this:

/*
* Use int64 to prevent overflow during calculation.
*/
compressed_size = (int32) ((int64) rawsize * 9 + 8) / 8;

I'm not very familiar with pglz internals, but I'm a bit puzzled by
this. My first instinct was to compare it to this:

#define PGLZ_MAX_OUTPUT(_dlen) ((_dlen) + 4)

but clearly that's a very different (much simpler) formula. So why
shouldn't pglz_maximum_compressed_size simply use this macro?

compressed_size accounts for possible increase of size during
compression. pglz can consume up to 1 control byte for each 8 bytes of
data in worst case.

OK, but does that actually translate in to the formula? We essentially
need to count 8-byte chunks in raw data, and multiply that by 9. Which
gives us something like

nchunks = ((rawsize + 7) / 8) * 9;

which is not quite what the patch does.

I'm afraid neither formula is correct, but all this is hair-splitting differences.

Sure. I just want to be sure the formula is safe and we won't end up
using too low value in some corner case.

Your formula does not account for the fact that we may not need all bytes from last chunk.
Consider desired decompressed size of 3 bytes. We may need 1 control byte and 3 literals, 4 bytes total
But nchunks = 9.

OK, so essentially this means my formula works with whole chunks, i.e.
if we happen to need just a part of a decompressed chunk, we still
request enough data to decompress it whole. This way we may request up
to 7 extra bytes, which seems fine.

Binguo's formula is appending 1 control bit per data byte and one extra
control byte. Consider size = 8 bytes. We need 1 control byte, 8
literals, 9 total. But compressed_size = 10.

Mathematically correct formula is compressed_size = (int32) ((int64)
rawsize * 9 + 7) / 8; Here we take one bit for each data byte, and 7
control bits for overflow.

But this equations make no big difference, each formula is safe. I'd
pick one which is easier to understand and document (IMO, its nchunks =
((rawsize + 7) / 8) * 9).

I'd use the *mathematically correct* formula, it doesn't seem to be any
more complex, and the "one bit per byte, complete bytes" explanation
seems quite understandable.

Pushed.

I've ended up using the *mathematically correct* formula, hopefully
with sufficient explanation why it's correct. I've also polished a
couple more comments, and pushed like that.

Thanks to Binguo Bao for this improvement, and all the reviewers in this
thread.

Hmmm, this seems to trigger a failure on thorntail, which is a sparc64
machine (and it seems to pass on all x86 machines, so far). Per the
backtrace, it seems to have failed like this:

Core was generated by `postgres: parallel worker for PID 2341 '.
Program terminated with signal SIGUSR1, User defined signal 1.
#0 heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=<optimized out>, slicelength=<optimized out>) at /home/nm/farm/sparc64_deb10_gcc_64_ubsan/HEAD/pgsql.build/../pgsql/src/backend/access/common/detoast.c:235
235 max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
#0 heap_tuple_untoast_attr_slice (attr=<optimized out>, sliceoffset=<optimized out>, slicelength=<optimized out>) at /home/nm/farm/sparc64_deb10_gcc_64_ubsan/HEAD/pgsql.build/../pgsql/src/backend/access/common/detoast.c:235
#1 0x00000100003d4ae8 in ExecInterpExpr (state=0x10000d02298, econtext=0x10000d01510, isnull=0x7feffb2fd1f) at /home/nm/farm/sparc64_deb10_gcc_64_ubsan/HEAD/pgsql.build/../pgsql/src/backend/executor/execExprInterp.c:690
...

so likely on this line:

max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
TOAST_COMPRESS_SIZE(attr));

the offset+length is just intereger arithmetics, so I don't see why that
would fail. So it has to be TOAST_COMPRESS_SIZE, which is defined like
this:

#define TOAST_COMPRESS_SIZE(ptr) ((int32) VARSIZE(ptr) - TOAST_COMPRESS_HDRSZ)

I wonder if that's wrong, somehow ... Maybe it should use VARSIZE_ANY,
but then how would it work on any platform and only fail on sparc64?

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#25Tom Lane
tgl@sss.pgh.pa.us
In reply to: Tomas Vondra (#24)
Re: Optimize partial TOAST decompression

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

Hmmm, this seems to trigger a failure on thorntail, which is a sparc64
machine (and it seems to pass on all x86 machines, so far).

gharial's not happy either, and I bet if you wait a bit longer you'll
see the same on other big-endian machines.

I wonder if that's wrong, somehow ... Maybe it should use VARSIZE_ANY,
but then how would it work on any platform and only fail on sparc64?

Maybe it accidentally seems to work on little-endian, thanks to the
different definitions of varlena headers?

regards, tom lane

#26Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Tom Lane (#25)
Re: Optimize partial TOAST decompression

On Tue, Oct 01, 2019 at 10:10:37AM -0400, Tom Lane wrote:

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

Hmmm, this seems to trigger a failure on thorntail, which is a sparc64
machine (and it seems to pass on all x86 machines, so far).

gharial's not happy either, and I bet if you wait a bit longer you'll
see the same on other big-endian machines.

I wonder if that's wrong, somehow ... Maybe it should use VARSIZE_ANY,
but then how would it work on any platform and only fail on sparc64?

Maybe it accidentally seems to work on little-endian, thanks to the
different definitions of varlena headers?

Maybe. Let's see if just using VARSIZE_ANY does the trick. If not, I'll
investigate further.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

#27Tom Lane
tgl@sss.pgh.pa.us
In reply to: Tomas Vondra (#26)
Re: Optimize partial TOAST decompression

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:

On Tue, Oct 01, 2019 at 10:10:37AM -0400, Tom Lane wrote:

Maybe it accidentally seems to work on little-endian, thanks to the
different definitions of varlena headers?

Maybe. Let's see if just using VARSIZE_ANY does the trick. If not, I'll
investigate further.

FWIW, prairiedog got past that test, so whatever it is seems specific
to big-endian 64-bit. Odd.

regards, tom lane

#28Rushabh Lathia
rushabh.lathia@gmail.com
In reply to: Tom Lane (#27)
Re: Optimize partial TOAST decompression

Today I noticed strange behaviour, consider the following test:

postgres@126111=#create table foo ( a text );
CREATE TABLE
postgres@126111=#insert into foo values ( repeat('PostgreSQL is the
world''s best database and leading by an Open Source Community.', 8000));
INSERT 0 1

postgres@126111=#select substring(a from 639921 for 81) from foo;
substring
-----------

(1 row)

Before below commit:

commit 540f31680913b4e11f2caa40cafeca269cfcb22f
Author: Tomas Vondra <tomas.vondra@postgresql.org>
Date: Tue Oct 1 16:53:04 2019 +0200

Blind attempt to fix pglz_maximum_compressed_size

Commit 11a078cf87 triggered failures on big-endian machines, and the
only plausible place for an issue seems to be that TOAST_COMPRESS_SIZE
calls VARSIZE instead of VARSIZE_ANY. So try fixing that blindly.

Discussion:
/messages/by-id/20191001131803.j6uin7nho7t6vxzy@development

postgres@75761=#select substring(a from 639921 for 81) from foo;

substring

----------------------------------------------------------------------------------
PostgreSQL is the world's best database and leading by an Open Source
Community.
(1 row)

#29Tomas Vondra
tomas.vondra@2ndquadrant.com
In reply to: Rushabh Lathia (#28)
1 attachment(s)
Re: Optimize partial TOAST decompression

On Thu, Nov 14, 2019 at 03:27:42PM +0530, Rushabh Lathia wrote:

Today I noticed strange behaviour, consider the following test:

postgres@126111=#create table foo ( a text );
CREATE TABLE
postgres@126111=#insert into foo values ( repeat('PostgreSQL is the
world''s best database and leading by an Open Source Community.', 8000));
INSERT 0 1

postgres@126111=#select substring(a from 639921 for 81) from foo;
substring
-----------

(1 row)

Hmmm. I think the issue is heap_tuple_untoast_attr_slice is using the
wrong way to determine compressed size in the VARATT_IS_EXTERNAL_ONDISK
branch. It does this

max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
TOAST_COMPRESS_SIZE(attr));

But for the example you've posted TOAST_COMPRESS_SIZE(attr) returns 10,
which is obviously bogus because the TOAST table contains ~75kB of data.

I think it should be doing this instead:

max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
toast_pointer.va_extsize);

At least that fixes it for me.

I wonder if this actually explains the crashes 540f3168091 was supposed
to fix, but it just masked them instead.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Attachments:

detoasting.patchtext/plain; charset=us-asciiDownload
diff --git a/src/backend/access/common/detoast.c b/src/backend/access/common/detoast.c
index 47a03fa98b..b796406239 100644
--- a/src/backend/access/common/detoast.c
+++ b/src/backend/access/common/detoast.c
@@ -233,7 +233,7 @@ heap_tuple_untoast_attr_slice(struct varlena *attr,
 			 * of a given length (after decompression).
 			 */
 			max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
-													TOAST_COMPRESS_SIZE(attr));
+													toast_pointer.va_extsize);
 
 			/*
 			 * Fetch enough compressed slices (compressed marker will get set
#30Rushabh Lathia
rushabh.lathia@gmail.com
In reply to: Tomas Vondra (#29)
Re: Optimize partial TOAST decompression

On Thu, Nov 14, 2019 at 6:30 PM Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:

On Thu, Nov 14, 2019 at 03:27:42PM +0530, Rushabh Lathia wrote:

Today I noticed strange behaviour, consider the following test:

postgres@126111=#create table foo ( a text );
CREATE TABLE
postgres@126111=#insert into foo values ( repeat('PostgreSQL is the
world''s best database and leading by an Open Source Community.', 8000));
INSERT 0 1

postgres@126111=#select substring(a from 639921 for 81) from foo;
substring
-----------

(1 row)

Hmmm. I think the issue is heap_tuple_untoast_attr_slice is using the
wrong way to determine compressed size in the VARATT_IS_EXTERNAL_ONDISK
branch. It does this

max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
TOAST_COMPRESS_SIZE(attr));

But for the example you've posted TOAST_COMPRESS_SIZE(attr) returns 10,
which is obviously bogus because the TOAST table contains ~75kB of data.

I think it should be doing this instead:

max_size = pglz_maximum_compressed_size(sliceoffset + slicelength,
toast_pointer.va_extsize);

At least that fixes it for me.

I wonder if this actually explains the crashes 540f3168091 was supposed
to fix, but it just masked them instead.

I tested the attached patch and that fixes the issue for me.

Thanks,

--
Rushabh Lathia
www.EnterpriseDB.com