Thread: Alternative variable length structure

Alternative variable length structure

From
ITAGAKI Takahiro
Date:
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

Re: Alternative variable length structure

From
Josh Berkus
Date:
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


Re: Alternative variable length structure

From
Rod Taylor
Date:
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.

-- 



Re: Alternative variable length structure

From
Andrew Dunstan
Date:

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


Re: Alternative variable length structure

From
"J. Andrew Rogers"
Date:
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




Re: Alternative variable length structure

From
ITAGAKI Takahiro
Date:
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




Re: Alternative variable length structure

From
Tom Lane
Date:
ITAGAKI Takahiro <itagaki.takahiro@lab.ntt.co.jp> 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


Re: Alternative variable length structure

From
Manfred Koizar
Date:
On Thu, 08 Sep 2005 18:02:44 +0900, ITAGAKI Takahiro
<itagaki.takahiro@lab.ntt.co.jp> 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 |
+  * | 1111---- |        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 |  *
|ec1111-- |        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.

ServusManfred


Re: Alternative variable length structure

From
Tom Lane
Date:
Manfred Koizar <mkoi-pg@aon.at> 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


Re: Alternative variable length structure

From
Bruce Momjian
Date:
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 EnterpriseDB    http://www.enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +


Re: Alternative variable length structure

From
"Jim C. Nasby"
Date:
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
>   EnterpriseDB    http://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      jnasby@pervasive.com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461


Re: Alternative variable length structure

From
Bruce Momjian
Date:
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
> >   EnterpriseDB    http://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      jnasby@pervasive.com
> Pervasive Software      http://pervasive.com    work: 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 majordomo@postgresql.org so that your
>        message can get through to the mailing list cleanly
> 

--  Bruce Momjian   http://candle.pha.pa.us EnterpriseDB    http://www.enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +


Re: Alternative variable length structure

From
"Jim C. Nasby"
Date:
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      jnasby@pervasive.com
Pervasive Software      http://pervasive.com    work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461


Re: Alternative variable length structure

From
Bruce Momjian
Date:
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      jnasby@pervasive.com
> Pervasive Software      http://pervasive.com    work: 512-231-6117
> vcard: http://jim.nasby.net/pervasive.vcf       cell: 512-569-9461
> 

--  Bruce Momjian   http://candle.pha.pa.us EnterpriseDB    http://www.enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +


Re: Alternative variable length structure

From
Neil Conway
Date:
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




Re: Alternative variable length structure

From
ITAGAKI Takahiro
Date:
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




Re: Alternative variable length structure

From
Tom Lane
Date:
Neil Conway <neilc@samurai.com> 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