Thread: 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
Attachment
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
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. --
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
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
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
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
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
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
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. +
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
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. +
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
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. +
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
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
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