pluggable compression support

Hi,

While hacking on the indirect toast support I felt the need to find out
how make compression formats pluggable to make sure .

In
http://archives.postgresql.org/message-id/20130605150144.GD28067%40alap2.anarazel.de
I submitted an initial patch that showed some promising results.

Here's a more cleaned up version which isn't intermingled with indirect
toast tuple support anymore.

It still contains a guc as described in the above message to control the
algorithm used for compressing new tuples but I think we should remove
that guc after testing.

Greetings,

Andres Freund

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

On 06/14/2013 04:01 PM, Andres Freund wrote:
> It still contains a guc as described in the above message to control the
> algorithm used for compressing new tuples but I think we should remove
> that guc after testing.

Did you add the storage attribute?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 2013-06-14 17:12:01 -0700, Josh Berkus wrote:
> On 06/14/2013 04:01 PM, Andres Freund wrote:
> > It still contains a guc as described in the above message to control the
> > algorithm used for compressing new tuples but I think we should remove
> > that guc after testing.
>
> Did you add the storage attribute?

No. I think as long as we only have pglz and one new algorithm (even if
that is lz4 instead of the current snappy) we should just always use the
new algorithm. Unless I missed it nobody seemed to have voiced a
contrary position?
For testing/evaluation the guc seems to be sufficient.

If we want to make it configurable on a per column basis I think the way
to go is to add a new column to pg_attribute and split compression
related things out of attstorage into attcompression.
That's a fair amount of work and it includes a minor compatibility break
in the catalog format, so I'd prefer not to do it until there's a good
reason to do so.

Greetings,

Andres Freund

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

> No. I think as long as we only have pglz and one new algorithm (even if
> that is lz4 instead of the current snappy) we should just always use the
> new algorithm. Unless I missed it nobody seemed to have voiced a
> contrary position?
> For testing/evaluation the guc seems to be sufficient.

Then it's not "pluggable", is it? It's "upgradable compression
support", if anything. Which is fine, but let's not confuse people.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 2013-06-14 17:35:02 -0700, Josh Berkus wrote:
>
> > No. I think as long as we only have pglz and one new algorithm (even if
> > that is lz4 instead of the current snappy) we should just always use the
> > new algorithm. Unless I missed it nobody seemed to have voiced a
> > contrary position?
> > For testing/evaluation the guc seems to be sufficient.
>
> Then it's not "pluggable", is it? It's "upgradable compression
> support", if anything. Which is fine, but let's not confuse people.

The point is that it's pluggable on the storage level in the sense of
that several different algorithms can coexist and new ones can
relatively easily added.
That part is what seems to have blocked progress for quite a while
now. So fixing that seems to be the interesting thing.

I am happy enough to do the work of making it configurable if we want it
to be... But I have zap interest of doing it and throw it away in the
end because we decide we don't need it.

Greetings,

Andres Freund

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

On Fri, Jun 14, 2013 at 8:45 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2013-06-14 17:35:02 -0700, Josh Berkus wrote:
>>
>> > No. I think as long as we only have pglz and one new algorithm (even if
>> > that is lz4 instead of the current snappy) we should just always use the
>> > new algorithm. Unless I missed it nobody seemed to have voiced a
>> > contrary position?
>> > For testing/evaluation the guc seems to be sufficient.
>>
>> Then it's not "pluggable", is it? It's "upgradable compression
>> support", if anything. Which is fine, but let's not confuse people.
>
> The point is that it's pluggable on the storage level in the sense of
> that several different algorithms can coexist and new ones can
> relatively easily added.
> That part is what seems to have blocked progress for quite a while
> now. So fixing that seems to be the interesting thing.
>
> I am happy enough to do the work of making it configurable if we want it
> to be... But I have zap interest of doing it and throw it away in the
> end because we decide we don't need it.

I don't think we need it. I think what we need is to decide is which
algorithm is legally OK to use. And then put it in.

In the past, we've had a great deal of speculation about that legal
question from people who are not lawyers. Maybe it would be valuable
to get some opinions from people who ARE lawyers. Tom and Heikki both
work for real big companies which, I'm guessing, have substantial
legal departments; perhaps they could pursue getting the algorithms of
possible interest vetted. Or, I could try to find out whether it's
possible do something similar through EnterpriseDB.

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

On 06/14/2013 06:56 PM, Robert Haas wrote:
>
> On Fri, Jun 14, 2013 at 8:45 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> On 2013-06-14 17:35:02 -0700, Josh Berkus wrote:
>>>
>>>> No. I think as long as we only have pglz and one new algorithm (even if
>>>> that is lz4 instead of the current snappy) we should just always use the
>>>> new algorithm. Unless I missed it nobody seemed to have voiced a
>>>> contrary position?
>>>> For testing/evaluation the guc seems to be sufficient.
>>>
>>> Then it's not "pluggable", is it? It's "upgradable compression
>>> support", if anything. Which is fine, but let's not confuse people.
>>
>> The point is that it's pluggable on the storage level in the sense of
>> that several different algorithms can coexist and new ones can
>> relatively easily added.
>> That part is what seems to have blocked progress for quite a while
>> now. So fixing that seems to be the interesting thing.
>>
>> I am happy enough to do the work of making it configurable if we want it
>> to be... But I have zap interest of doing it and throw it away in the
>> end because we decide we don't need it.
>
> I don't think we need it. I think what we need is to decide is which
> algorithm is legally OK to use. And then put it in.
>
> In the past, we've had a great deal of speculation about that legal
> question from people who are not lawyers. Maybe it would be valuable
> to get some opinions from people who ARE lawyers. Tom and Heikki both
> work for real big companies which, I'm guessing, have substantial
> legal departments; perhaps they could pursue getting the algorithms of
> possible interest vetted. Or, I could try to find out whether it's
> possible do something similar through EnterpriseDB.

We have IP legal representation through Software in the Public interest
who pretty much specializes in this type of thing.

Should I follow up? If so, I need a summary of the exact question
including licenses etc.

JD

>

--
Command Prompt, Inc. - http://www.commandprompt.com/ 509-416-6579
PostgreSQL Support, Training, Professional Services and Development
High Availability, Oracle Conversion, Postgres-XC, @cmdpromptinc
For my dreams of your image that blossoms
a rose in the deeps of my heart. - W.B. Yeats

On 2013-06-14 21:56:52 -0400, Robert Haas wrote:
> I don't think we need it. I think what we need is to decide is which
> algorithm is legally OK to use. And then put it in.
>
> In the past, we've had a great deal of speculation about that legal
> question from people who are not lawyers. Maybe it would be valuable
> to get some opinions from people who ARE lawyers. Tom and Heikki both
> work for real big companies which, I'm guessing, have substantial
> legal departments; perhaps they could pursue getting the algorithms of
> possible interest vetted. Or, I could try to find out whether it's
> possible do something similar through EnterpriseDB.

I personally don't think the legal arguments holds all that much water
for snappy and lz4. But then the opinion of a european non-lawyer doesn't
hold much either.
Both are widely used by a large number open and closed projects, some of
which have patent grant clauses in their licenses. E.g. hadoop,
cassandra use lz4, and I'd be surprised if the companies behind those
have opened themselves to litigation.

I think we should preliminarily decide which algorithm to use before we
get lawyers involved. I'd surprised if they can make such a analysis
faster than we can rule out one of them via benchmarks.

Will post an updated patch that includes lz4 as well.

Greetings,

Andres Freund

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

On 06/15/2013 03:56 AM, Robert Haas wrote:
> On Fri, Jun 14, 2013 at 8:45 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> On 2013-06-14 17:35:02 -0700, Josh Berkus wrote:
>>>> No. I think as long as we only have pglz and one new algorithm (even if
>>>> that is lz4 instead of the current snappy) we should just always use the
>>>> new algorithm. Unless I missed it nobody seemed to have voiced a
>>>> contrary position?
>>>> For testing/evaluation the guc seems to be sufficient.
>>> Then it's not "pluggable", is it? It's "upgradable compression
>>> support", if anything. Which is fine, but let's not confuse people.
>> The point is that it's pluggable on the storage level in the sense of
>> that several different algorithms can coexist and new ones can
>> relatively easily added.
>> That part is what seems to have blocked progress for quite a while
>> now. So fixing that seems to be the interesting thing.
>>
>> I am happy enough to do the work of making it configurable if we want it
>> to be... But I have zap interest of doing it and throw it away in the
>> end because we decide we don't need it.
> I don't think we need it. I think what we need is to decide is which
> algorithm is legally OK to use. And then put it in.
If it were truly pluggable - that is just load a .dll, set a GUG and start
using it - then the selection of algorithms would be much
wider as several slow-but-high-compression ones under GPL could be
used as well, similar to how currently PostGIS works.

gzip and bzip2 are the first two that came in mind, but I am sure there
are more.

> In the past, we've had a great deal of speculation about that legal
> question from people who are not lawyers. Maybe it would be valuable
> to get some opinions from people who ARE lawyers.
Making a truly pluggable compression API delegates this question
to end users.

Delegation is good, as it lets you get done more :)

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 06/15/2013 02:20 AM, Andres Freund wrote:
> On 2013-06-14 17:12:01 -0700, Josh Berkus wrote:
>> On 06/14/2013 04:01 PM, Andres Freund wrote:
>>> It still contains a guc as described in the above message to control the
>>> algorithm used for compressing new tuples but I think we should remove
>>> that guc after testing.
>> Did you add the storage attribute?
> No. I think as long as we only have pglz and one new algorithm (even if
> that is lz4 instead of the current snappy) we should just always use the
> new algorithm. Unless I missed it nobody seemed to have voiced a
> contrary position?
> For testing/evaluation the guc seems to be sufficient.
If not significantly harder than what you currently do, I'd prefer a
true pluggable compression support which is

a) dynamically configurable , say by using a GUG

and

b) self-describing, that is, the compressed data should have enough
info to determine how to decompress it.

additionally it *could* have the property Simon proposed earlier
of *uncompressed* pages having some predetermined size, so we
could retain optimisations of substring() even on compressed TOAST
values.

the latter of course could also be achieved by adding offset
column to toast tables as well.

One more idea - if we are already changing toast table structure, we
could introduce a notion of "compress block", which could run over
several storage pages for much improved compression compared
to compressing only a single page at a time.

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 2013-06-15 13:25:49 +0200, Hannu Krosing wrote:
> On 06/15/2013 02:20 AM, Andres Freund wrote:
> > On 2013-06-14 17:12:01 -0700, Josh Berkus wrote:
> >> On 06/14/2013 04:01 PM, Andres Freund wrote:
> >>> It still contains a guc as described in the above message to control the
> >>> algorithm used for compressing new tuples but I think we should remove
> >>> that guc after testing.
> >> Did you add the storage attribute?
> > No. I think as long as we only have pglz and one new algorithm (even if
> > that is lz4 instead of the current snappy) we should just always use the
> > new algorithm. Unless I missed it nobody seemed to have voiced a
> > contrary position?
> > For testing/evaluation the guc seems to be sufficient.

> If not significantly harder than what you currently do, I'd prefer a
> true pluggable compression support which is

> a) dynamically configurable , say by using a GUG

> and

> b) self-describing, that is, the compressed data should have enough
> info to determine how to decompress it.

Could you perhaps actually read the the description and the discussion
before making wild suggestions? Possibly even the patch.
Compressed toast datums now *do* have an identifier of the compression
algorithm used. That's how we can discern between pglz and whatever
algorithm we come up with.

But those identifiers should be *small* (since they are added to all
Datums) and they need to be stable, even across pg_upgrade. So I think
making this user configurable would be grave error at this point.

> additionally it *could* have the property Simon proposed earlier
> of *uncompressed* pages having some predetermined size, so we
> could retain optimisations of substring() even on compressed TOAST
> values.

We are not changing the toast format here, so I don't think that's
applicable. That's a completely separate feature.

> the latter of course could also be achieved by adding offset
> column to toast tables as well.

> One more idea - if we are already changing toast table structure, we
> could introduce a notion of "compress block", which could run over
> several storage pages for much improved compression compared
> to compressing only a single page at a time.

We aren't changing the toast table structure. And we can't easily do so,
think of pg_upgrade.
Besides, toast always has compressed datums over several chunks. What
would be beneficial would be to compress in a way that you can compress
several datums together, but that's several magnitudes more complex and
is unrelated to this feature.

Greetings,

Andres Freund

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

On 2013-06-15 13:11:47 +0200, Hannu Krosing wrote:
> If it were truly pluggable - that is just load a .dll, set a GUG and start
> using it

Ok. I officially rechristen the patchset to 'extensible compression
support'.

> - then the selection of algorithms would be much
> wider as several slow-but-high-compression ones under GPL could be
> used as well, similar to how currently PostGIS works.

> gzip and bzip2 are the first two that came in mind, but I am sure there
> are more.

gzip barely has a higher compression ratio than lz4 and is a magnitude
slower decompressing, so I don't think it's interesting.
I personally think bzip2 is too slow to be useful, even for
decompression. What might be useful is something like lzma, but it's
implementation is so complex that I don't really want to touch it.

> > In the past, we've had a great deal of speculation about that legal
> > question from people who are not lawyers. Maybe it would be valuable
> > to get some opinions from people who ARE lawyers.
> Making a truly pluggable compression API delegates this question
> to end users.
>
> Delegation is good, as it lets you get done more :)

No. It increases the features complexity by a magnitude. That's not
good. And it means that about nobody but a few expert users will benefit
from it, so I am pretty strongly opposed.

You suddently need to solve the question of how the identifiers for
compression formats are allocated and preserved across pg_upgrade and
across machines.

Greetings,

Andres Freund

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

On 06/15/2013 01:56 PM, Andres Freund wrote:
> On 2013-06-15 13:25:49 +0200, Hannu Krosing wrote:
>> On 06/15/2013 02:20 AM, Andres Freund wrote:
>>> On 2013-06-14 17:12:01 -0700, Josh Berkus wrote:
>>>> On 06/14/2013 04:01 PM, Andres Freund wrote:
>>>>> It still contains a guc as described in the above message to control the
>>>>> algorithm used for compressing new tuples but I think we should remove
>>>>> that guc after testing.
>>>> Did you add the storage attribute?
>>> No. I think as long as we only have pglz and one new algorithm (even if
>>> that is lz4 instead of the current snappy) we should just always use the
>>> new algorithm. Unless I missed it nobody seemed to have voiced a
>>> contrary position?
>>> For testing/evaluation the guc seems to be sufficient.
>> If not significantly harder than what you currently do, I'd prefer a
>> true pluggable compression support which is
>> a) dynamically configurable , say by using a GUG
>> and
>> b) self-describing, that is, the compressed data should have enough
>> info to determine how to decompress it.
> Could you perhaps actually read the the description and the discussion
> before making wild suggestions? Possibly even the patch.
> Compressed toast datums now *do* have an identifier of the compression
> algorithm used.
> That's how we can discern between pglz and whatever
> algorithm we come up with.
Claiming that the algorithm will be one of only two (current and
"whatever algorithm we come up with ") suggests that it is
only one bit, which is undoubtedly too little for having a "pluggable"
compression API :)

> But those identifiers should be *small* (since they are added to all
> Datums)
if there will be any alignment at all between the datums, then
one byte will be lost in the noise ("remember: nobody will need
more than 256 compression algorithms")
OTOH, if you plan to put these format markers in the compressed
stream and change the compression algorithm while reading it, I am lost.
> and they need to be stable, even across pg_upgrade. So I think
> making this user configurable would be grave error at this point.
"at this point" in what sense ?
>
>> additionally it *could* have the property Simon proposed earlier
>> of *uncompressed* pages having some predetermined size, so we
>> could retain optimisations of substring() even on compressed TOAST
>> values.
> We are not changing the toast format here, so I don't think that's
> applicable. That's a completely separate feature.
>
>> the latter of course could also be achieved by adding offset
>> column to toast tables as well.
>> One more idea - if we are already changing toast table structure, we
>> could introduce a notion of "compress block", which could run over
>> several storage pages for much improved compression compared
>> to compressing only a single page at a time.
> We aren't changing the toast table structure. And we can't easily do so,
> think of pg_upgrade.
Where was the page for "features rejected based on of pg_upgrade" ;)
> Besides, toast always has compressed datums over several chunks. What
> would be beneficial would be to compress in a way that you can compress
> several datums together, but that's several magnitudes more complex and
> is unrelated to this feature.
>
> Greetings,
>
> Andres Freund
>

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 06/15/2013 02:02 PM, Andres Freund wrote:
> On 2013-06-15 13:11:47 +0200, Hannu Krosing wrote:
>> If it were truly pluggable - that is just load a .dll, set a GUG and start
>> using it
> Ok. I officially rechristen the patchset to 'extensible compression
> support'.
>
>> - then the selection of algorithms would be much
>> wider as several slow-but-high-compression ones under GPL could be
>> used as well, similar to how currently PostGIS works.
>> gzip and bzip2 are the first two that came in mind, but I am sure there
>> are more.
> gzip barely has a higher compression ratio than lz4 and is a magnitude
> slower decompressing, so I don't think it's interesting.
> I personally think bzip2 is too slow to be useful, even for
> decompression.
with low compression settings gzip and bzip2 seem to decompress at the
same speed :
http://pokecraft.first-world.info/wiki/Quick_Benchmark:_Gzip_vs_Bzip2_vs_LZMA_vs_XZ_vs_LZ4_vs_LZO

(an interesting thing there is memory usage, but I guess it is just an
artefact of outer layers around the algorithm)

and if better compression translates to more speed depends heavily on
disk speeds :

http://www.citusdata.com/blog/64-zfs-compression claims quite big
performance increases from using gzip, even with its slow decompression"

> What might be useful is something like lzma, but it's
> implementation is so complex that I don't really want to touch it.
>
>>> In the past, we've had a great deal of speculation about that legal
>>> question from people who are not lawyers. Maybe it would be valuable
>>> to get some opinions from people who ARE lawyers.
>> Making a truly pluggable compression API delegates this question
>> to end users.
>>
>> Delegation is good, as it lets you get done more :)
> No. It increases the features complexity by a magnitude. That's not
> good. And it means that about nobody but a few expert users will benefit
> from it, so I am pretty strongly opposed.
>
> You suddently need to solve the question of how the identifiers for
> compression formats are allocated and preserved across pg_upgrade and
> across machines.
This is something similar we already need to do for any non-builtin type
OID.
>
> Greetings,
>
> Andres Freund
>

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 2013-06-15 14:11:54 +0200, Hannu Krosing wrote:
> > Could you perhaps actually read the the description and the discussion
> > before making wild suggestions? Possibly even the patch.
> > Compressed toast datums now *do* have an identifier of the compression
> > algorithm used.
> > That's how we can discern between pglz and whatever
> > algorithm we come up with.
> Claiming that the algorithm will be one of only two (current and
> "whatever algorithm we come up with ") suggests that it is
> only one bit, which is undoubtedly too little for having a "pluggable"
> compression API :)

No, I am thinking 127 + 2 possibly algorithms for now. If we need more
the space used for the algorithm can be extended transparently at that
point.

> > But those identifiers should be *small* (since they are added to all
> > Datums)

> if there will be any alignment at all between the datums, then
> one byte will be lost in the noise ("remember: nobody will need
> more than 256 compression algorithms")

No. There's no additional alignment involved here.

> OTOH, if you plan to put these format markers in the compressed
> stream and change the compression algorithm while reading it, I am
> lost.

The marker *needs* to be in the compressed stream. When decompressing a
datum we only only get passed the varlena.

> > and they need to be stable, even across pg_upgrade. So I think
> > making this user configurable would be grave error at this point.

> "at this point" in what sense ?

If we add another algorithm with different tradeofs we can have a column
attribute for choosing the algorithm. If there proofs to be a need to
add more configurabily, we can do that at that point.

Greetings,

Andres Freund

On Saturday, June 15, 2013 3:50 PM Andres Freund wrote:
On 2013-06-14 21:56:52 -0400, Robert Haas wrote:
>> I don't think we need it. I think what we need is to decide is which
>> algorithm is legally OK to use. And then put it in.
>>
>> In the past, we've had a great deal of speculation about that legal
>> question from people who are not lawyers. Maybe it would be valuable
>> to get some opinions from people who ARE lawyers. Tom and Heikki both
>> work for real big companies which, I'm guessing, have substantial
>> legal departments; perhaps they could pursue getting the algorithms of
>> possible interest vetted. Or, I could try to find out whether it's
>> possible do something similar through EnterpriseDB.

> I personally don't think the legal arguments holds all that much water
> for snappy and lz4. But then the opinion of a european non-lawyer doesn't
> hold much either.
> Both are widely used by a large number open and closed projects, some of
> which have patent grant clauses in their licenses. E.g. hadoop,
> cassandra use lz4, and I'd be surprised if the companies behind those
> have opened themselves to litigation.

> I think we should preliminarily decide which algorithm to use before we
> get lawyers involved. I'd surprised if they can make such a analysis
> faster than we can rule out one of them via benchmarks.

I have also tried to use snappy for patch "Performance Improvement by reducing WAL for Update Operation".
It has shown very good results and performed very well for all the tests asked by Heikki.
Results are at below link:
http://www.postgresql.org/message-id/009001ce2c6e$9bea4790$d3bed6b0$@kapila@huawei.com

I think if we can get snappy into core, it can be used for more things.
I wanted to try it for FPW as well.

With Regards,
Amit Kapila.

On Sat, Jun 15, 2013 at 8:11 AM, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:
> Claiming that the algorithm will be one of only two (current and
> "whatever algorithm we come up with ") suggests that it is
> only one bit, which is undoubtedly too little for having a "pluggable"
> compression API :)

See http://www.postgresql.org/message-id/20130607143053.GJ29964@alap2.anarazel.de

>> But those identifiers should be *small* (since they are added to all
>> Datums)
> if there will be any alignment at all between the datums, then
> one byte will be lost in the noise ("remember: nobody will need
> more than 256 compression algorithms")
> OTOH, if you plan to put these format markers in the compressed
> stream and change the compression algorithm while reading it, I am lost.

The above-linked email addresses this point as well: there are bits
available in the toast pointer. But there aren't MANY bits without
increasing the storage footprint, so trying to do something that's
more general than we really need is going to cost us in terms of
on-disk footprint. Is that really worth it? And if so, why? I don't
find the idea of a trade-off between compression/decompression speed
and compression ratio to be very exciting. As Andres says, bzip2 is
impractically slow for ... almost everything. If there's a good
BSD-licensed algorithm available, let's just use it and be done. Our
current algorithm has lasted us a very long time; I see no reason to
think we'll want to change this again for another 10 years, and by
that time, we may have redesigned the storage format altogether,
making the limited extensibility of our current TOAST pointer format
moot.

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

On Sat, Jun 15, 2013 at 8:22 AM, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:
>> You suddently need to solve the question of how the identifiers for
>> compression formats are allocated and preserved across pg_upgrade and
>> across machines.
> This is something similar we already need to do for any non-builtin type
> OID.

That's true, but that code has already been written. And it's not
trivial. The code involved is CREATE/ALTER/DROP TYPE plus all the
corresponding pg_dump mechanism. To do what you're proposing here,
we'd need CREATE/ALTER/DROP COMPRESSION METHOD, and associated pg_dump
--binary-upgrade support. I think Andres is entirely right to be
skeptical about that. It will make this project about 4 times as hard
for almost no benefit.

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

On 06/16/2013 03:50 AM, Robert Haas wrote:
> On Sat, Jun 15, 2013 at 8:11 AM, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:
>> Claiming that the algorithm will be one of only two (current and
>> "whatever algorithm we come up with ") suggests that it is
>> only one bit, which is undoubtedly too little for having a "pluggable"
>> compression API :)
> See http://www.postgresql.org/message-id/20130607143053.GJ29964@alap2.anarazel.de
>
>>> But those identifiers should be *small* (since they are added to all
>>> Datums)
>> if there will be any alignment at all between the datums, then
>> one byte will be lost in the noise ("remember: nobody will need
>> more than 256 compression algorithms")
>> OTOH, if you plan to put these format markers in the compressed
>> stream and change the compression algorithm while reading it, I am lost.
> The above-linked email addresses this point as well: there are bits
> available in the toast pointer. But there aren't MANY bits without
> increasing the storage footprint, so trying to do something that's
> more general than we really need is going to cost us in terms of
> on-disk footprint. Is that really worth it? And if so, why? I don't
> find the idea of a trade-off between compression/decompression speed
> and compression ratio to be very exciting. As Andres says, bzip2 is
> impractically slow for ... almost everything. If there's a good
> BSD-licensed algorithm available, let's just use it and be done. Our
> current algorithm has lasted us a very long time;
My scepticism about current algorithm comes from a brief test
(which may have been flawed) which showed almost no compression
for plain XML fields.

It may very well be that I was doing something stupid and got
wrong results though, as I the functions to ask for toast internals
like "is this field compressed" or "what is the compressed
length of this field" are well hidden - if available at all - in our
documentation.

> I see no reason to
> think we'll want to change this again for another 10 years, and by
> that time, we may have redesigned the storage format altogether,
> making the limited extensibility of our current TOAST pointer format
> moot.
Agreed.

I just hoped that "pluggable compression support" would
be something that enables people not directly interested in
hacking the core to experiment with compression and thereby
possibly coming up with something that changes your "not
useful in next 10 years" prediction :)

Seeing that the scope of this patch is actually much narrower,
I have no objections of doing it as proposed by Andres.

--
Hannu Krosing
PostgreSQL Consultant
Performance, Scalability and High Availability
2ndQuadrant Nordic OÜ

On 15 June 2013 13:02, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2013-06-15 13:11:47 +0200, Hannu Krosing wrote:
>> If it were truly pluggable - that is just load a .dll, set a GUG and start
>> using it
>
> Ok. I officially rechristen the patchset to 'extensible compression
> support'.

+1

(I confess I was confused also.)

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

On 15 June 2013 12:25, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:

> additionally it *could* have the property Simon proposed earlier
> of *uncompressed* pages having some predetermined size, so we
> could retain optimisations of substring() even on compressed TOAST
> values.

That wasn't about having fixed size pages, it was about having a
function to determine the split points. Reason being we want to use
some intelligence to split up JSON and XML documents.

I would also like to be able to do other types of processing on fields
before they are stored.

That is probably best done as a sequence of processing transforms,
rather than a single compression module.

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

Simon Riggs wrote:
> On 15 June 2013 12:25, Hannu Krosing <hannu(at)2ndquadrant(dot)com> wrote:
>
> > additionally it *could* have the property Simon proposed earlier
> > of *uncompressed* pages having some predetermined size, so we
> > could retain optimisations of substring() even on compressed TOAST
> > values.
>
> That wasn't about having fixed size pages, it was about having a
> function to determine the split points. Reason being we want to use
> some intelligence to split up JSON and XML documents.

Maybe indexed compressed text would be useful:
http://pizzachili.dcc.uchile.cl/

--
Álvaro Herrera http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On 2013-06-15 12:20:28 +0200, Andres Freund wrote:
> On 2013-06-14 21:56:52 -0400, Robert Haas wrote:
> > I don't think we need it. I think what we need is to decide is which
> > algorithm is legally OK to use. And then put it in.
> >
> > In the past, we've had a great deal of speculation about that legal
> > question from people who are not lawyers. Maybe it would be valuable
> > to get some opinions from people who ARE lawyers. Tom and Heikki both
> > work for real big companies which, I'm guessing, have substantial
> > legal departments; perhaps they could pursue getting the algorithms of
> > possible interest vetted. Or, I could try to find out whether it's
> > possible do something similar through EnterpriseDB.
>
> I personally don't think the legal arguments holds all that much water
> for snappy and lz4. But then the opinion of a european non-lawyer doesn't
> hold much either.
> Both are widely used by a large number open and closed projects, some of
> which have patent grant clauses in their licenses. E.g. hadoop,
> cassandra use lz4, and I'd be surprised if the companies behind those
> have opened themselves to litigation.
>
> I think we should preliminarily decide which algorithm to use before we
> get lawyers involved. I'd surprised if they can make such a analysis
> faster than we can rule out one of them via benchmarks.
>
> Will post an updated patch that includes lz4 as well.

Attached.

Changes:
* add lz4 compression algorithm (2 clause bsd)
* move compression algorithms into own subdirectory
* clean up compression/decompression functions
* allow 258 compression algorithms, uses 1byte extra for any but the
first three
* don't pass a varlena to pg_lzcompress.c anymore, but data directly
* add pglz_long as a test fourth compression method that uses the +1
byte encoding
* us postgres' endian detection in snappy for compatibility with osx

Based on the benchmarks I think we should go with lz4 only for now. The
patch provides the infrastructure should somebody else want to add more
or even proper configurability.

Todo:
* windows build support
* remove toast_compression_algo guc
* remove either snappy or lz4 support
* remove pglz_long support (just there for testing)

New benchmarks:

Table size:
List of relations
Schema | Name | Type | Owner | Size | Description
--------+--------------------+-------+--------+--------+-------------
public | messages_pglz | table | andres | 526 MB |
public | messages_snappy | table | andres | 523 MB |
public | messages_lz4 | table | andres | 522 MB |
public | messages_pglz_long | table | andres | 527 MB |
(4 rows)

Workstation (2xE5520, enough s_b for everything):

Data load:
pglz: 36643.384 ms
snappy: 24626.894 ms
lz4: 23871.421 ms
pglz_long: 37097.681 ms

COPY messages_* TO '/dev/null' WITH BINARY;
pglz: 3116.083 ms
snappy: 2524.388 ms
lz4: 2349.396 ms
pglz_long: 3104.134 ms

COPY (SELECT rawtxt FROM messages_*) TO '/dev/null' WITH BINARY;
pglz: 1609.969 ms
snappy: 1031.696 ms
lz4: 886.782 ms
pglz_long: 1606.803 ms

On my elderly laptop (core 2 duo), too load shared buffers:

Data load:
pglz: 39968.381 ms
snappy: 26952.330 ms
lz4: 29225.472 ms
pglz_long: 39929.568 ms

COPY messages_* TO '/dev/null' WITH BINARY;
pglz: 3920.588 ms
snappy: 3421.938 ms
lz4: 3311.540 ms
pglz_long: 3885.920 ms

COPY (SELECT rawtxt FROM messages_*) TO '/dev/null' WITH BINARY;
pglz: 2238.145 ms
snappy: 1753.403 ms
lz4: 1638.092 ms
pglz_long: 2227.804 ms

Greetings,

Andres Freund

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

On Thu, Jun 20, 2013 at 8:09 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> On 2013-06-15 12:20:28 +0200, Andres Freund wrote:
>> On 2013-06-14 21:56:52 -0400, Robert Haas wrote:
>> > I don't think we need it. I think what we need is to decide is which
>> > algorithm is legally OK to use. And then put it in.
>> >
>> > In the past, we've had a great deal of speculation about that legal
>> > question from people who are not lawyers. Maybe it would be valuable
>> > to get some opinions from people who ARE lawyers. Tom and Heikki both
>> > work for real big companies which, I'm guessing, have substantial
>> > legal departments; perhaps they could pursue getting the algorithms of
>> > possible interest vetted. Or, I could try to find out whether it's
>> > possible do something similar through EnterpriseDB.
>>
>> I personally don't think the legal arguments holds all that much water
>> for snappy and lz4. But then the opinion of a european non-lawyer doesn't
>> hold much either.
>> Both are widely used by a large number open and closed projects, some of
>> which have patent grant clauses in their licenses. E.g. hadoop,
>> cassandra use lz4, and I'd be surprised if the companies behind those
>> have opened themselves to litigation.
>>
>> I think we should preliminarily decide which algorithm to use before we
>> get lawyers involved. I'd surprised if they can make such a analysis
>> faster than we can rule out one of them via benchmarks.
>>
>> Will post an updated patch that includes lz4 as well.
>
> Attached.
>
> Changes:
> * add lz4 compression algorithm (2 clause bsd)
> * move compression algorithms into own subdirectory
> * clean up compression/decompression functions
> * allow 258 compression algorithms, uses 1byte extra for any but the
> first three
> * don't pass a varlena to pg_lzcompress.c anymore, but data directly
> * add pglz_long as a test fourth compression method that uses the +1
> byte encoding
> * us postgres' endian detection in snappy for compatibility with osx
>
> Based on the benchmarks I think we should go with lz4 only for now. The
> patch provides the infrastructure should somebody else want to add more
> or even proper configurability.
>
> Todo:
> * windows build support
> * remove toast_compression_algo guc
> * remove either snappy or lz4 support
> * remove pglz_long support (just there for testing)
>
> New benchmarks:
>
> Table size:
> List of relations
> Schema | Name | Type | Owner | Size | Description
> --------+--------------------+-------+--------+--------+-------------
> public | messages_pglz | table | andres | 526 MB |
> public | messages_snappy | table | andres | 523 MB |
> public | messages_lz4 | table | andres | 522 MB |
> public | messages_pglz_long | table | andres | 527 MB |
> (4 rows)
>
> Workstation (2xE5520, enough s_b for everything):
>
> Data load:
> pglz: 36643.384 ms
> snappy: 24626.894 ms
> lz4: 23871.421 ms
> pglz_long: 37097.681 ms
>
> COPY messages_* TO '/dev/null' WITH BINARY;
> pglz: 3116.083 ms
> snappy: 2524.388 ms
> lz4: 2349.396 ms
> pglz_long: 3104.134 ms
>
> COPY (SELECT rawtxt FROM messages_*) TO '/dev/null' WITH BINARY;
> pglz: 1609.969 ms
> snappy: 1031.696 ms
> lz4: 886.782 ms
> pglz_long: 1606.803 ms
>
>
> On my elderly laptop (core 2 duo), too load shared buffers:
>
> Data load:
> pglz: 39968.381 ms
> snappy: 26952.330 ms
> lz4: 29225.472 ms
> pglz_long: 39929.568 ms
>
> COPY messages_* TO '/dev/null' WITH BINARY;
> pglz: 3920.588 ms
> snappy: 3421.938 ms
> lz4: 3311.540 ms
> pglz_long: 3885.920 ms
>
> COPY (SELECT rawtxt FROM messages_*) TO '/dev/null' WITH BINARY;
> pglz: 2238.145 ms
> snappy: 1753.403 ms
> lz4: 1638.092 ms
> pglz_long: 2227.804 ms

Well, the performance of both snappy and lz4 seems to be significantly
better than pglz. On these tests lz4 has a small edge but that might
not be true on other data sets. I still think the main issue is legal
review: are there any license or patent concerns about including
either of these algorithms in PG? If neither of them have issues, we
might need to experiment a little more before picking between them.
If one does and the other does not, well, then it's a short
conversation.

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

On 2013-06-25 12:22:31 -0400, Robert Haas wrote:
> On Thu, Jun 20, 2013 at 8:09 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
> > On 2013-06-15 12:20:28 +0200, Andres Freund wrote:
> >> On 2013-06-14 21:56:52 -0400, Robert Haas wrote:
> >> > I don't think we need it. I think what we need is to decide is which
> >> > algorithm is legally OK to use. And then put it in.
> >> >
> >> > In the past, we've had a great deal of speculation about that legal
> >> > question from people who are not lawyers. Maybe it would be valuable
> >> > to get some opinions from people who ARE lawyers. Tom and Heikki both
> >> > work for real big companies which, I'm guessing, have substantial
> >> > legal departments; perhaps they could pursue getting the algorithms of
> >> > possible interest vetted. Or, I could try to find out whether it's
> >> > possible do something similar through EnterpriseDB.
> >>
> >> I personally don't think the legal arguments holds all that much water
> >> for snappy and lz4. But then the opinion of a european non-lawyer doesn't
> >> hold much either.
> >> Both are widely used by a large number open and closed projects, some of
> >> which have patent grant clauses in their licenses. E.g. hadoop,
> >> cassandra use lz4, and I'd be surprised if the companies behind those
> >> have opened themselves to litigation.
> >>
> >> I think we should preliminarily decide which algorithm to use before we
> >> get lawyers involved. I'd surprised if they can make such a analysis
> >> faster than we can rule out one of them via benchmarks.
> >>
> >> Will post an updated patch that includes lz4 as well.
> >
> > Attached.
>
> Well, the performance of both snappy and lz4 seems to be significantly
> better than pglz. On these tests lz4 has a small edge but that might
> not be true on other data sets.

From what I've seen of independent benchmarks on more varying datasets
and from what I tested (without pg inbetween) lz4 usually has a bigger
margin than this, especially on decompression.
The implementation also seems to be better prepared to run on more
platforms, e.g. it didn't require any fiddling with endian.h in contrast
to snappy.
But yes, "even" snappy would be a big improvement should lz4 turn out to
be problematic and the performance difference isn't big enough to rule
one out as I'd hopped.

> I still think the main issue is legal
> review: are there any license or patent concerns about including
> either of these algorithms in PG? If neither of them have issues, we
> might need to experiment a little more before picking between them.
> If one does and the other does not, well, then it's a short
> conversation.

True. So, how do we proceed on that?

The ASF decided it was safe to use lz4 in cassandra. Does anybody have
contacts over there?

Btw, I have the feeling we hold this topic to a higher standard wrt
patent issues than other work in postgres...

Greetings,

Andres Freund

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

On 06/25/2013 11:42 AM, Andres Freund wrote:
> True. So, how do we proceed on that?
>
> The ASF decided it was safe to use lz4 in cassandra. Does anybody have
> contacts over there?
>
> Btw, I have the feeling we hold this topic to a higher standard wrt
> patent issues than other work in postgres...

We have access to attorneys, both in the US and Canada. I will proceed
to ask for real legal advice.

However, can you tell me what exactly you are concerned about? lz4 is
under the BSD license, and released by Google. Why are we worried, exactly?

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

On 2013-06-25 12:08:22 -0700, Josh Berkus wrote:
> On 06/25/2013 11:42 AM, Andres Freund wrote:
> > True. So, how do we proceed on that?
> >
> > The ASF decided it was safe to use lz4 in cassandra. Does anybody have
> > contacts over there?
> >
> > Btw, I have the feeling we hold this topic to a higher standard wrt
> > patent issues than other work in postgres...
>
> We have access to attorneys, both in the US and Canada. I will proceed
> to ask for real legal advice.

Cool!

> However, can you tell me what exactly you are concerned about? lz4 is
> under the BSD license, and released by Google.

Snappy is released/copyrighted by google. lz4 by Yann Collet.

Both are under BSD licenses (3 and 2 clause variants respectively). I
don't think we need to worry about the license.

> Why are we worried, exactly?

The concerns I heard about were all about patent issues.

Greetings,

Andres Freund

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

On Tue, Jun 25, 2013 at 4:15 PM, Andres Freund <andres(at)2ndquadrant(dot)com> wrote:
>> However, can you tell me what exactly you are concerned about? lz4 is
>> under the BSD license, and released by Google.
>
> Snappy is released/copyrighted by google. lz4 by Yann Collet.
>
> Both are under BSD licenses (3 and 2 clause variants respectively). I
> don't think we need to worry about the license.
>
>> Why are we worried, exactly?
>
> The concerns I heard about were all about patent issues.

IANAL, but patents have nothing to do with licenses. Licenses apply to
specific implementations, whereas software patents (ironically, since
they're forbidden to in general, but they do it anyway for software
patents) apply to processes. Two implementations may differ, and be
under different licenses, but the same patent may apply to both.

It's a sick state of affairs when you can implement lz4 completely
yourself and still be unclear about whether your own, clean-room
implementation is encumbered by patents or not.

A lawyer has to sift through pattent applications to know whether this
particular implementation is encumbered, and that's a very
time-consuming process (and thus very expensive).

If you can take the effort, it would be greatly beneficial I imagine.
But I think you're underestimating what those lawyers will ask for it.

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> However, can you tell me what exactly you are concerned about? lz4 is
> under the BSD license, and released by Google. Why are we worried, exactly?

Patents. The license on the code doesn't matter --- worst case, if
someone objected, we could rewrite the algorithm ourselves to get out
of an alleged copyright violation. But if someone comes after us for
a patent violation we're screwed; or at least, our users who have
terabytes of data stored with an infringing algorithm are screwed.

Andres is right that we're paying closer attention to patent risks here
than we do most places. That's because we know that the whole arena
of data compression is a minefield of patents. It would be
irresponsible not to try to check.

regards, tom lane

On 06/25/2013 12:23 PM, Tom Lane wrote:
> Josh Berkus <josh(at)agliodbs(dot)com> writes:
>> However, can you tell me what exactly you are concerned about? lz4 is
>> under the BSD license, and released by Google. Why are we worried, exactly?
>
> Patents. The license on the code doesn't matter --- worst case, if
> someone objected, we could rewrite the algorithm ourselves to get out
> of an alleged copyright violation. But if someone comes after us for
> a patent violation we're screwed; or at least, our users who have
> terabytes of data stored with an infringing algorithm are screwed.

Taking this off-list, because it is a legal matter. Particularly, it's
legally problematic to discuss patents on a public mailing list, as we
found out with the ARC patent.

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

I've been following this issue these last few months.
Having the latest and best compressors built-in is a fashionable features
these days. And for good reasons.

I'm quite amazed that this issue is still considered a "legal risk".
To put this in perspective, the *whole world* is using LZ4 by now. It's
integrated directly into Linux kernel ARM, which means every smartphone on
the planet will have this piece of software integrated right at the factory.

And that's not just Linux. HBase has it. TokuDB has it. Delphix has it.
And PostgreSQL is stuck with what, pglz ?

How come any compressor which could put some competition to pglz is
systematically pushed out of the field on the ground of unverifiable "legal
risks" ?

And why would pglz be much safer to the very same risks ? From what I can
see, pglz is more complex, and therefore exposed to many more patent risks,
than simpler lz alternatives.

Seems the debate is overly biaised in favor of pglz.

--
View this message in context: http://postgresql.1045698.n5.nabble.com/pluggable-compression-support-tp5759259p5772891.html
Sent from the PostgreSQL - hackers mailing list archive at Nabble.com.

On Mon, Sep 30, 2013 at 1:49 PM, Huchev <hugochevrain(at)gmail(dot)com> wrote:
> How come any compressor which could put some competition to pglz is
> systematically pushed out of the field on the ground of unverifiable "legal
> risks" ?

Because pglz has been around for a while and has not caused patent
trouble. The risks have been accepted and the downsides have not
materialized. Were pglz were being written and distributed starting
today, perhaps your reasoning would be more compelling, but as-is the
pglz ship has sailed for quite some time and empirically it has not
been a problem.

That said, I hope the findings are in favor of lz4 or snappy
integration. It does seem lz4 has picked up a slight edge.

On Tue, Oct 1, 2013 at 9:56 PM, Daniel Farina <daniel(at)heroku(dot)com> wrote:
> On Mon, Sep 30, 2013 at 1:49 PM, Huchev <hugochevrain(at)gmail(dot)com> wrote:
>> How come any compressor which could put some competition to pglz is
>> systematically pushed out of the field on the ground of unverifiable "legal
>> risks" ?
>
> Because pglz has been around for a while and has not caused patent
> trouble. The risks have been accepted and the downsides have not
> materialized. Were pglz were being written and distributed starting
> today, perhaps your reasoning would be more compelling, but as-is the
> pglz ship has sailed for quite some time and empirically it has not
> been a problem.
>
> That said, I hope the findings are in favor of lz4 or snappy
> integration. It does seem lz4 has picked up a slight edge.

Yeah, I'm also in favor of a new compression format, whatever we can
agree on. However, I'm uncertain we're actually moving toward that
goal in any meaningful way.

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