Re: [HACKERS] Alternative variable length structure
I assume the conclusion from this email thread is that though the idea
is interesting, the complexity added would not be worth the saving of a
few bytes.
---
ITAGAKI Takahiro wrote:
Hi Hackers,
PostgreSQL can treat variable-length data flexibly, but therefore
it consumes more spaces if we store short data. Headers of
variable-length types use 4 bytes regardless of the data length.
My idea is to change the header itself to variable-length.
In order to reduce the size of short data, I wrote a patch to encode
lengths into the first several bits of structure. Also, the alignments
of the types were changed to 'char' from 'int'.
I know my patch is still insufficient, for example, the types cannot
be TOASTed. But I guess this compression works well for short text.
I'll appreciate any comments.
thanks.
the result of patch
# create table txttbl (v1 text, v2 text, v3 text, v4 text);
# create table strtbl (v1 string, v2 string, v3 string, v4 string);
# insert into txttbl values('A', 'B', 'C', 'D');
# insert into strtbl values('A', 'B', 'C', 'D');
# select * from pgstattuple('txttbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 57-- 28 + (5+3) + (5+3) + (5+3) + (5)
...
# select * from pgstattuple('strtbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 36-- 28 + 2 + 2 + 2 + 2
...
---
ITAGAKI Takahiro
NTT Cyber Space Laboratories
[ Attachment, skipping... ]
---(end of broadcast)---
TIP 6: explain analyze is your friend
--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDBhttp://www.enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
---(end of broadcast)---
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
Re: [HACKERS] Alternative variable length structure
On Wed, Jun 14, 2006 at 02:53:10PM -0400, Bruce Momjian wrote:
I assume the conclusion from this email thread is that though the idea
is interesting, the complexity added would not be worth the saving of a
few bytes.
Anyone do any testing?
I'm also wondering if this would be useful to allow fields larger than
1G.
---
ITAGAKI Takahiro wrote:
Hi Hackers,
PostgreSQL can treat variable-length data flexibly, but therefore
it consumes more spaces if we store short data. Headers of
variable-length types use 4 bytes regardless of the data length.
My idea is to change the header itself to variable-length.
In order to reduce the size of short data, I wrote a patch to encode
lengths into the first several bits of structure. Also, the alignments
of the types were changed to 'char' from 'int'.
I know my patch is still insufficient, for example, the types cannot
be TOASTed. But I guess this compression works well for short text.
I'll appreciate any comments.
thanks.
the result of patch
# create table txttbl (v1 text, v2 text, v3 text, v4 text);
# create table strtbl (v1 string, v2 string, v3 string, v4 string);
# insert into txttbl values('A', 'B', 'C', 'D');
# insert into strtbl values('A', 'B', 'C', 'D');
# select * from pgstattuple('txttbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 57-- 28 + (5+3) + (5+3) + (5+3) + (5)
...
# select * from pgstattuple('strtbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 36-- 28 + 2 + 2 + 2 + 2
...
---
ITAGAKI Takahiro
NTT Cyber Space Laboratories
[ Attachment, skipping... ]
---(end of broadcast)---
TIP 6: explain analyze is your friend
--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDBhttp://www.enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
---(end of broadcast)---
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
--
Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED]
Pervasive Software http://pervasive.comwork: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461
---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
Re: [HACKERS] Alternative variable length structure
Jim C. Nasby wrote:
On Wed, Jun 14, 2006 at 02:53:10PM -0400, Bruce Momjian wrote:
I assume the conclusion from this email thread is that though the idea
is interesting, the complexity added would not be worth the saving of a
few bytes.
Anyone do any testing?
I'm also wondering if this would be useful to allow fields larger than
1G.
The submitter showed the pathological case where a single char was
stored in a text field, and showed the reduced size (below). There were
no performance numbers given. It seems like an edge case, especially
since we have a char type that is a single byte.
---
ITAGAKI Takahiro wrote:
Hi Hackers,
PostgreSQL can treat variable-length data flexibly, but therefore
it consumes more spaces if we store short data. Headers of
variable-length types use 4 bytes regardless of the data length.
My idea is to change the header itself to variable-length.
In order to reduce the size of short data, I wrote a patch to encode
lengths into the first several bits of structure. Also, the alignments
of the types were changed to 'char' from 'int'.
I know my patch is still insufficient, for example, the types cannot
be TOASTed. But I guess this compression works well for short text.
I'll appreciate any comments.
thanks.
the result of patch
# create table txttbl (v1 text, v2 text, v3 text, v4 text);
# create table strtbl (v1 string, v2 string, v3 string, v4 string);
# insert into txttbl values('A', 'B', 'C', 'D');
# insert into strtbl values('A', 'B', 'C', 'D');
# select * from pgstattuple('txttbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 57-- 28 + (5+3) + (5+3) + (5+3) + (5)
...
# select * from pgstattuple('strtbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 36-- 28 + 2 + 2 + 2 + 2
...
---
ITAGAKI Takahiro
NTT Cyber Space Laboratories
[ Attachment, skipping... ]
---(end of broadcast)---
TIP 6: explain analyze is your friend
--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDBhttp://www.enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
---(end of broadcast)---
TIP 4: Have you searched our list archives?
http://archives.postgresql.org
--
Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED]
Pervasive Software http://pervasive.comwork: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461
---(end of broadcast)---
TIP 1: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to [EMAIL PROTECTED] so that your
message can get through to the mailing list cleanly
--
Bruce Momjian http://candle.pha.pa.us
EnterpriseDBhttp://www.enterprisedb.com
+ If your life is a hard drive, Christ can be your backup. +
---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] Alternative variable length structure
On Wed, Jun 14, 2006 at 04:21:34PM -0400, Bruce Momjian wrote: Jim C. Nasby wrote: On Wed, Jun 14, 2006 at 02:53:10PM -0400, Bruce Momjian wrote: I assume the conclusion from this email thread is that though the idea is interesting, the complexity added would not be worth the saving of a few bytes. Anyone do any testing? I'm also wondering if this would be useful to allow fields larger than 1G. The submitter showed the pathological case where a single char was stored in a text field, and showed the reduced size (below). There were no performance numbers given. It seems like an edge case, especially since we have a char type that is a single byte. Well, depending on how the patch works I could see it being valuable for tables that have a number of 'short' text fields, where short is less than 127 bytes. I've got some tables like that I can test on, at least to see the size difference. Not really sure what a valid performance test would be, though... I'm wondering if it would be worth trying to organize users to do testing of stuff like this. I'm sure there's lots of folks who know how to apply a patch and have test data that could benefit from patches like this. (I'm assuming this patch didn't place any substantial performance penalties into the backend...) -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Alternative variable length structure
The code churn to do this is going to be quite significant, as well a performance-wise hit perhaps, so it has to be a big win. --- Jim C. Nasby wrote: On Wed, Jun 14, 2006 at 04:21:34PM -0400, Bruce Momjian wrote: Jim C. Nasby wrote: On Wed, Jun 14, 2006 at 02:53:10PM -0400, Bruce Momjian wrote: I assume the conclusion from this email thread is that though the idea is interesting, the complexity added would not be worth the saving of a few bytes. Anyone do any testing? I'm also wondering if this would be useful to allow fields larger than 1G. The submitter showed the pathological case where a single char was stored in a text field, and showed the reduced size (below). There were no performance numbers given. It seems like an edge case, especially since we have a char type that is a single byte. Well, depending on how the patch works I could see it being valuable for tables that have a number of 'short' text fields, where short is less than 127 bytes. I've got some tables like that I can test on, at least to see the size difference. Not really sure what a valid performance test would be, though... I'm wondering if it would be worth trying to organize users to do testing of stuff like this. I'm sure there's lots of folks who know how to apply a patch and have test data that could benefit from patches like this. (I'm assuming this patch didn't place any substantial performance penalties into the backend...) -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 -- Bruce Momjian http://candle.pha.pa.us EnterpriseDBhttp://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] Alternative variable length structure
On Wed, 2006-06-14 at 16:56 -0400, Bruce Momjian wrote: The code churn to do this is going to be quite significant Why do you say that? Although the original patch posted to implement this was incomplete, it certainly wasn't very large. -Neil ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] Alternative variable length structure
Bruce Momjian pgman@candle.pha.pa.us wrote: I assume the conclusion from this email thread is that though the idea is interesting, the complexity added would not be worth the saving of a few bytes. I have same understanding about it. Besides the complexity, there is trade-off between cpu and i/o resources. Also, there is another approach in http://archives.postgresql.org/pgsql-hackers/2005-12/msg00258.php , where 2byte header version of varlena is suggested. It is more simple, but it may double intrinsic text types (shorttext, shortchar and shortvarchar). I assume it is worth the saving of a few bytes in particular for indexes on VLDBs, but my patch is still incomplete and needs more works. --- ITAGAKI Takahiro NTT Open Source Software Center ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Alternative variable length structure
Neil Conway [EMAIL PROTECTED] writes: On Wed, 2006-06-14 at 16:56 -0400, Bruce Momjian wrote: The code churn to do this is going to be quite significant Why do you say that? Although the original patch posted to implement this was incomplete, it certainly wasn't very large. IIRC, the original idea would have forced code changes on every existing varlena datatype ... not just those in our source tree, but outside users' custom types as well. You'd need a really *serious* gain to justify that. The second idea was to leave existing varlena types as-is and invent a set of small text etc datatypes alongside them. This is simply ugly (shades of Oracle's varchar2), and again there wasn't really an adequate case made why we should burden users with extra complexity. The variant I could have supported was making a 2-byte-header class of types and using it just for the few types where it would be sufficient (numeric and inet, basically). That would be transparent to everyone. Whether it's worth the trouble is not clear given that it'd only help a few datatypes, but would add cycles in critical inner loops in places like heap_deformtuple. regards, tom lane ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Alternative variable length structure
On Thu, 08 Sep 2005 18:02:44 +0900, ITAGAKI Takahiro [EMAIL PROTECTED] wrote: + * The length of varlena2 is encoded as follows: + * + * | First| Trailing | Total | Max | + * | byte | bytes| bits | length | + * +--+--+---+-+ + * | 0*** |0 | 7 | 127 | + * | 10** |1 |14 | 16K -1 | + * | 110* |2 |21 | 2M -1 | + * | 1110 |3 |28 | 256M -1 | + * | |4 |32 | 4G -1 | With external and compression flags this would look like * | ec0* |0 | 5 | 31 | * | ec10 |1 |12 | 4K -1 | * | ec110*** |2 |19 | 512K -1 | * | ec1110** |3 |26 | 64M -1 | * | ec-- |4 |32 | 4G -1 | Only a matter of taste, but I'd just waste one byte for sizes between 4K and 512K and thus get a shorter table: * | ec0* |0 | 5 | 31 | * | ec10 |1 |12 | 4K -1 | * | ec110*** |3 |27 | 128M -1 | * | ec111--- |4 |32 | 4G -1 | And you get back that one byte for sizes between 64M and 128M :-) Another possible tweak: * | 0*** |0 | 5 | 127 | * | 1ec0 |1 |12 | 4K -1 | * | 1ec10*** |3 |27 | 128M -1 | * | 1ec11--- |4 |32 | 4G -1 | I.e. drop the flags for very short strings. If these flags are needed for a string of size 32 to 127, then use a two byte header. Servus Manfred ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
Re: [HACKERS] Alternative variable length structure
Manfred Koizar [EMAIL PROTECTED] writes: I.e. drop the flags for very short strings. I don't think the interaction of this idea with TOAST has been thought through very carefully. Some points to consider: * If the 'e' (external) bit is set, the actual length is 20 or so bytes. Always. There is no need for an 'e' bit in the variants that store a longer length. * I agree with Manfred that you could blow off the case of compressing strings shorter than 128 bytes, so you really only need the 'c' bit for the longer variants. Hence, just one flag bit is needed in all cases. * The proposal to reduce the alignment to char breaks TOAST pointers, which contain fields that need to be word-aligned (at least on machines that are picky about alignment). Maybe we could just live with that, by copying the in-datum data to and from properly aligned local storage in the routines that need to access the pointer fields. It's an extra cost though, as well as a probable source of bugs that will only be noticed on non-Intel hardware. * In the 'c' case you need to store *two* lengths, the physical length and the decompressed length. Is it worth playing the same kind of game with the decompressed length? Again, you can't just do nothing because the proposal breaks word-alignment of the decompressed length. Another thing that's bothering me about this is that it'll lead to weird new coding rules that will certainly break a lot of code; notably you can't access VARDATA(x) until you've assigned the correct value to VARSIZE(x). This will be a particular pain in the neck for code that likes to fill in the data before it makes a final determination of the result size. So I'm feeling a good deal of sales resistance to the idea that this ought to replace our existing varlena representation. At least for internal use. Maybe the right way to think about this is that a compressed length word is a form of TOASTing, which we apply during toast compression and undo during PG_DETOAST_DATUM. If we did that, the changes would be vastly more localized than if we try to make all the datatype manipulation routines cope. Not sure about the speed tradeoffs involved, though. regards, tom lane ---(end of broadcast)--- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
[HACKERS] Alternative variable length structure
Hi Hackers,
PostgreSQL can treat variable-length data flexibly, but therefore
it consumes more spaces if we store short data. Headers of
variable-length types use 4 bytes regardless of the data length.
My idea is to change the header itself to variable-length.
In order to reduce the size of short data, I wrote a patch to encode
lengths into the first several bits of structure. Also, the alignments
of the types were changed to 'char' from 'int'.
I know my patch is still insufficient, for example, the types cannot
be TOASTed. But I guess this compression works well for short text.
I'll appreciate any comments.
thanks.
the result of patch
# create table txttbl (v1 text, v2 text, v3 text, v4 text);
# create table strtbl (v1 string, v2 string, v3 string, v4 string);
# insert into txttbl values('A', 'B', 'C', 'D');
# insert into strtbl values('A', 'B', 'C', 'D');
# select * from pgstattuple('txttbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 57-- 28 + (5+3) + (5+3) + (5+3) + (5)
...
# select * from pgstattuple('strtbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 36-- 28 + 2 + 2 + 2 + 2
...
---
ITAGAKI Takahiro
NTT Cyber Space Laboratories
varlena2.patch
Description: Binary data
---(end of broadcast)---
TIP 6: explain analyze is your friend
Re: [HACKERS] Alternative variable length structure
Takahiro, PostgreSQL can treat variable-length data flexibly, but therefore it consumes more spaces if we store short data. Headers of variable-length types use 4 bytes regardless of the data length. My idea is to change the header itself to variable-length. In order to reduce the size of short data, I wrote a patch to encode lengths into the first several bits of structure. Also, the alignments of the types were changed to 'char' from 'int'. I know my patch is still insufficient, for example, the types cannot be TOASTed. But I guess this compression works well for short text. Hmmm. Seems like these would be different data types from the standard ones we deal with. I can see the value for data warehousing, for example. Wouldn't this require creating, for example, a SHORTTEXT type? Or were you planning this to handle VARCHAR(6) and the like? If so, how would we deal with users who change the length via ALTER TABLE? -- Josh Berkus Aglio Database Solutions San Francisco ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] Alternative variable length structure
On Thu, 2005-09-08 at 09:53 -0700, Josh Berkus wrote: Takahiro, PostgreSQL can treat variable-length data flexibly, but therefore it consumes more spaces if we store short data. Headers of variable-length types use 4 bytes regardless of the data length. My idea is to change the header itself to variable-length. In order to reduce the size of short data, I wrote a patch to encode lengths into the first several bits of structure. Also, the alignments of the types were changed to 'char' from 'int'. I know my patch is still insufficient, for example, the types cannot be TOASTed. But I guess this compression works well for short text. Hmmm. Seems like these would be different data types from the standard ones we deal with. I can see the value for data warehousing, for example. Wouldn't this require creating, for example, a SHORTTEXT type? Or were you planning this to handle VARCHAR(6) and the like? If so, how would we deal with users who change the length via ALTER TABLE? I believe ALTER TABLE always rewrites the structure using a standard cast or another expression. -- ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Alternative variable length structure
ITAGAKI Takahiro wrote:
# select * from pgstattuple('txttbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 57-- 28 + (5+3) + (5+3) + (5+3) + (5)
...
# select * from pgstattuple('strtbl');
-[ RECORD 1 ]--+--
table_len | 8192
tuple_count| 1
tuple_len | 36-- 28 + 2 + 2 + 2 + 2
What's the break even point in datum length between the two styles of
header?
And what is the processing overhead of using variable header length?
cheers
andrew
---(end of broadcast)---
TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] Alternative variable length structure
On 9/8/05 9:53 AM, Josh Berkus josh@agliodbs.com wrote: Hmmm. Seems like these would be different data types from the standard ones we deal with. I can see the value for data warehousing, for example. Wouldn't this require creating, for example, a SHORTTEXT type? Or were you planning this to handle VARCHAR(6) and the like? If so, how would we deal with users who change the length via ALTER TABLE? If I am reading the patch correctly (and I may not be), changing the length via ALTER TABLE would not affect anything because the header length is variable per type instance in the table. This appears to be an alternate encoding for VARCHAR(n) and similar. This is not dissimilar to how ASN.1 BER prefix encodes type lengths, an encoding widely used in wire protocols. This can save quite a few bytes in many cases, particularly when storing short byte strings (for ASN.1, even integers and similar are encoded this way to shave bytes on them as well but that seems excessive). It would be useful to see how encoding/decoding cost balances out the more compact representation in terms of performance. J. Andrew Rogers ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Alternative variable length structure
Josh Berkus josh@agliodbs.com wrote: Wouldn't this require creating, for example, a SHORTTEXT type? Yes, new types are required. There are no binary compatibility between them and existing variable length types (text, bytea, etc.). But 'SHORTTEXT' is not a proper name for them. They can represent long texts though they are optimized for short ones. We might be able to optimize types further if we create different types for each length, for example, tinytext for length 256, shorttext for 64K, mediumtext for 16MB ... But I think this is not appropriate. It forces users to choose one from several text types and we will have to maintain them. Or were you planning this to handle VARCHAR(6) and the like? If the new text type wins VARCHAR in many respects, I'd like to propose to replace VARCHAR with it. --- ITAGAKI Takahiro NTT Cyber Space Laboratories ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] Alternative variable length structure
ITAGAKI Takahiro [EMAIL PROTECTED] writes: If the new text type wins VARCHAR in many respects, I'd like to propose to replace VARCHAR with it. This idea would impose fairly significant overhead in a number of places, for instance locating field starts within a tuple. It didn't appear to me that you'd even tried to measure that overhead is? Given that slot_getattr and friends are often hotspots, I don't think the costs involved can be ignored. regards, tom lane ---(end of broadcast)--- TIP 6: explain analyze is your friend
