Re: Performance Improvement by reducing WAL for Update Operation

On 11 January 2013 15:57, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:

>>>> I've moved this to the next CF. I'm planning to review this one first.
>>
>>> Thank you.
>
>> Just reviewing the patch now, making more sense with comments added.

> Making more sense, but not yet making complete sense.

> I'd like you to revisit the patch comments since some of them are completely unreadable.

I have modified most of the comments in code.

The changes in attached patch are as below:

1. Introduced Encoded WAL Tuple (EWT) to refer to delta encoded tuple for update operation.

It can rename to one of below:

a. WAL Encoded Tuple (WET)

b. Delta Encoded WAL Tuple (DEWT)

c. Delta WAL Encoded Tuple (DWET)

d. any others?

2. I have kept the wording related to compression in modified docs, but i have tried to copy parts completely.

IMO this is required as there are some changes w.r.t LZ compression like for New Data.

3. There is small coding change as it has been overwritten by one of my previous patch patches.

Calculation of approximate length for encoded wal tuple.

Previous Patch:

if ((bp + (2 * new_tup_bitmaplen)) - bstart >= result_max)

New Patch:

if ((bp + (2 + new_tup_bitmaplen)) - bstart >= result_max)

The previous patch calculation was valid if we could have exactly used LZ format.

With Regards,

Amit Kapila.

On Monday, January 21, 2013 9:32 PM Amit kapila wrote:
On 11 January 2013 15:57, Simon Riggs <simon(at)2ndquadrant(dot)com> wrote:

>>>>> I've moved this to the next CF. I'm planning to review this one first.
>>
>>>> Thank you.
>
>>> Just reviewing the patch now, making more sense with comments added.

>> Making more sense, but not yet making complete sense.

>> I'd like you to revisit the patch comments since some of them are
completely unreadable.
 
>I have modified most of the comments in code.
>The changes in attached patch are as below:
 

Rebased the patch as per HEAD.
 
With Regards,
Amit Kapila.

On 28.01.2013 15:39, Amit Kapila wrote:
> Rebased the patch as per HEAD.

I don't like the way heap_delta_encode has intimate knowledge of how the
lz compression works. It feels like a violent punch through the
abstraction layers.

Ideally, you would just pass the old and new tuple to pglz as char *,
and pglz code would find the common parts. But I guess that's too slow,
as that's what I originally suggested and you rejected that approach.
But even if that's not possible on performance grounds, we don't need to
completely blow up the abstraction. pglz can still do the encoding - the
caller just needs to pass it the attribute boundaries to consider for
matches, so that it doesn't need to scan them byte by byte.

I came up with the attached patch. I wrote it to demonstrate the API,
I'm not 100% sure the result after decoding is correct.

- Heikki

On Tuesday, January 29, 2013 2:53 AM Heikki Linnakangas wrote:
> On 28.01.2013 15:39, Amit Kapila wrote:
> > Rebased the patch as per HEAD.
>
> I don't like the way heap_delta_encode has intimate knowledge of how
> the lz compression works. It feels like a violent punch through the
> abstraction layers.
>
> Ideally, you would just pass the old and new tuple to pglz as char *,
> and pglz code would find the common parts. But I guess that's too slow,
> as that's what I originally suggested and you rejected that approach.
> But even if that's not possible on performance grounds, we don't need
> to completely blow up the abstraction. pglz can still do the encoding -
> the caller just needs to pass it the attribute boundaries to consider
> for matches, so that it doesn't need to scan them byte by byte.
>
> I came up with the attached patch. I wrote it to demonstrate the API,
> I'm not 100% sure the result after decoding is correct.

I have checked the patch code, found few problems.

1. History will be old tuple, in that case below call needs to be changed
/* return pglz_compress_with_history((char *) oldtup->t_data,
oldtup->t_len,

(char *) newtup->t_data, newtup->t_len,

offsets, noffsets, (PGLZ_Header *) encdata,

&strategy);*/
return pglz_compress_with_history((char *) newtup->t_data,
newtup->t_len,

(char *) oldtup->t_data, oldtup->t_len,

offsets, noffsets, (PGLZ_Header *) encdata,

&strategy);
2. The offset array is beginning of each column offset. In that case below
needs to be changed.

offsets[noffsets++] = off;

off = att_addlength_pointer(off, thisatt->attlen, tp + off);

if (thisatt->attlen <= 0)
slow = true; /* can't use attcacheoff
anymore */

// offsets[noffsets++] = off;
}

Apart from this, some of the test cases are failing which I need to check.

I have debugged the new code, it appears to me that this will not be as
efficient as the current approach of patch.
It needs to build hash table for history reference and comparison which can
add overhead as compare to existing approach. I am taking the Performance
and WAL Reduction data.

Can there be another way with which current patch code can be made better,
so that we don't need to change the encoding approach, as I am having
feeling that this might not be performance wise equally good.

With Regards,
Amit Kapila.

On 29.01.2013 11:58, Amit Kapila wrote:
> Can there be another way with which current patch code can be made better,
> so that we don't need to change the encoding approach, as I am having
> feeling that this might not be performance wise equally good.

The point is that I don't want to heap_delta_encode() to know the
internals of pglz compression. You could probably make my patch more
like yours in behavior by also passing an array of offsets in the new
tuple to check, and only checking for matches as those offsets.

- Heikki

On Tuesday, January 29, 2013 3:53 PM Heikki Linnakangas wrote:
> On 29.01.2013 11:58, Amit Kapila wrote:
> > Can there be another way with which current patch code can be made
> better,
> > so that we don't need to change the encoding approach, as I am having
> > feeling that this might not be performance wise equally good.
>
> The point is that I don't want to heap_delta_encode() to know the
> internals of pglz compression. You could probably make my patch more
> like yours in behavior by also passing an array of offsets in the new
> tuple to check, and only checking for matches as those offsets.

I think it makes sense, because if we have offsets of both new and old
tuple, we
can internally use memcmp to compare columns and use same algorithm for
encoding.
I will change the patch according to this suggestion.

With Regards,
Amit Kapila.

On Tuesday, January 29, 2013 7:42 PM Amit Kapila wrote:
> On Tuesday, January 29, 2013 3:53 PM Heikki Linnakangas wrote:
> > On 29.01.2013 11:58, Amit Kapila wrote:
> > > Can there be another way with which current patch code can be made
> > better,
> > > so that we don't need to change the encoding approach, as I am
> having
> > > feeling that this might not be performance wise equally good.
> >
> > The point is that I don't want to heap_delta_encode() to know the
> > internals of pglz compression. You could probably make my patch more
> > like yours in behavior by also passing an array of offsets in the new
> > tuple to check, and only checking for matches as those offsets.
>
> I think it makes sense, because if we have offsets of both new and old
> tuple, we
> can internally use memcmp to compare columns and use same algorithm for
> encoding.
> I will change the patch according to this suggestion.

I have modified the patch as per above suggestion.
Apart from passing new and old tuple offsets, I have passed bitmaplength
also, as we need
to copy the bitmap of new tuple as it is into Encoded WAL Tuple.

Please see if such API design is okay?

I shall update the README and send the performance/WAL Reduction data for
modified patch tomorrow.

With Regards,
Amit Kapila.

On Wednesday, January 30, 2013 8:32 PM Amit Kapila wrote:
> On Tuesday, January 29, 2013 7:42 PM Amit Kapila wrote:
> > On Tuesday, January 29, 2013 3:53 PM Heikki Linnakangas wrote:
> > > On 29.01.2013 11:58, Amit Kapila wrote:
> > > > Can there be another way with which current patch code can be
> made
> > > better,
> > > > so that we don't need to change the encoding approach, as I am
> > having
> > > > feeling that this might not be performance wise equally good.
> > >
> > > The point is that I don't want to heap_delta_encode() to know the
> > > internals of pglz compression. You could probably make my patch
> more
> > > like yours in behavior by also passing an array of offsets in the
> > > new tuple to check, and only checking for matches as those offsets.
> >
> > I think it makes sense, because if we have offsets of both new and
> old
> > tuple, we can internally use memcmp to compare columns and use same
> > algorithm for encoding.
> > I will change the patch according to this suggestion.
>
> I have modified the patch as per above suggestion.
> Apart from passing new and old tuple offsets, I have passed
> bitmaplength also, as we need to copy the bitmap of new tuple as it is
> into Encoded WAL Tuple.
>
> Please see if such API design is okay?
>
> I shall update the README and send the performance/WAL Reduction data
> for modified patch tomorrow.

Updated patch including comments and README is attached with this mail.
This patch contain exactly same design behavior as per previous.
It takes care of API design suggestion of Heikki.

The performance data is similar, as it is not complete, I shall send that
tomorrow.

With Regards,
Amit Kapila.

On Thursday, January 31, 2013 6:44 PM Amit Kapila wrote:
> On Wednesday, January 30, 2013 8:32 PM Amit Kapila wrote:
> > On Tuesday, January 29, 2013 7:42 PM Amit Kapila wrote:
> > > On Tuesday, January 29, 2013 3:53 PM Heikki Linnakangas wrote:
> > > > On 29.01.2013 11:58, Amit Kapila wrote:
> > > > > Can there be another way with which current patch code can be
> > made
> > > > better,
> > > > > so that we don't need to change the encoding approach, as I am
> > > having
> > > > > feeling that this might not be performance wise equally good.
> > > >
> > > > The point is that I don't want to heap_delta_encode() to know the
> > > > internals of pglz compression. You could probably make my patch
> > more
> > > > like yours in behavior by also passing an array of offsets in the
> > > > new tuple to check, and only checking for matches as those
> offsets.
> > >
> > > I think it makes sense, because if we have offsets of both new and
> > old
> > > tuple, we can internally use memcmp to compare columns and use same
> > > algorithm for encoding.
> > > I will change the patch according to this suggestion.
> >
> > I have modified the patch as per above suggestion.
> > Apart from passing new and old tuple offsets, I have passed
> > bitmaplength also, as we need to copy the bitmap of new tuple as it
> is
> > into Encoded WAL Tuple.
> >
> > Please see if such API design is okay?
> >
> > I shall update the README and send the performance/WAL Reduction data
> > for modified patch tomorrow.
>
> Updated patch including comments and README is attached with this mail.
> This patch contain exactly same design behavior as per previous.
> It takes care of API design suggestion of Heikki.
>
> The performance data is similar, as it is not complete, I shall send
> that tomorrow.

Performance data for the patch is attached with this mail.
Conclusions from the readings (these are same as my previous patch):

1. With orignal pgbench there is a max 7% WAL reduction with not much
performance difference.
2. With 250 record pgbench there is a max wal reduction of 35% with not much
performance difference.
3. With 500 and above record size in pgbench there is an improvement in the
performance and wal reduction both.

If the record size increases there is a gain in performance and wal size is
reduced as well.

Performance data for synchronous_commit = on is under progress, I shall post
it once it is done.
I am expecting it to be same as previous.

With Regards,
Amit Kapila.

On Friday, February 01, 2013 6:37 PM Amit Kapila wrote:
> On Thursday, January 31, 2013 6:44 PM Amit Kapila wrote:
> > On Wednesday, January 30, 2013 8:32 PM Amit Kapila wrote:
> > > On Tuesday, January 29, 2013 7:42 PM Amit Kapila wrote:
> > > > On Tuesday, January 29, 2013 3:53 PM Heikki Linnakangas wrote:
> > > > > On 29.01.2013 11:58, Amit Kapila wrote:
> > > > > > Can there be another way with which current patch code can be
> > > made
> > > > > better,
> > > > > > so that we don't need to change the encoding approach, as I
> am
> > > > having
> > > > > > feeling that this might not be performance wise equally good.
> > > > >
> > > > > The point is that I don't want to heap_delta_encode() to know
> > > > > the internals of pglz compression. You could probably make my
> > > > > patch
> > > more
> > > > > like yours in behavior by also passing an array of offsets in
> > > > > the new tuple to check, and only checking for matches as those
> > offsets.
> > > >
> > > > I think it makes sense, because if we have offsets of both new
> and
> > > old
> > > > tuple, we can internally use memcmp to compare columns and use
> > > > same algorithm for encoding.
> > > > I will change the patch according to this suggestion.
> > >
> > > I have modified the patch as per above suggestion.
> > > Apart from passing new and old tuple offsets, I have passed
> > > bitmaplength also, as we need to copy the bitmap of new tuple as it
> > is
> > > into Encoded WAL Tuple.
> > >
> > > Please see if such API design is okay?
> > >
> > > I shall update the README and send the performance/WAL Reduction
> > > data for modified patch tomorrow.
> >
> > Updated patch including comments and README is attached with this
> mail.
> > This patch contain exactly same design behavior as per previous.
> > It takes care of API design suggestion of Heikki.
> >
> > The performance data is similar, as it is not complete, I shall send
> > that tomorrow.
>
> Performance data for the patch is attached with this mail.
> Conclusions from the readings (these are same as my previous patch):
>
> 1. With orignal pgbench there is a max 7% WAL reduction with not much
> performance difference.
> 2. With 250 record pgbench there is a max wal reduction of 35% with not
> much performance difference.
> 3. With 500 and above record size in pgbench there is an improvement in
> the performance and wal reduction both.
>
> If the record size increases there is a gain in performance and wal
> size is reduced as well.
>
> Performance data for synchronous_commit = on is under progress, I shall
> post it once it is done.
> I am expecting it to be same as previous.

Please find the performance readings for synchronous_commit = on.

Each run is taken for 20 min.

Conclusions from the readings with synchronous commit on mode:

1. With orignal pgbench there is a max 2% WAL reduction with not much
performance difference.
2. With 500 record pgbench there is a max wal reduction of 3% with not much
performance difference.
3. With 1800 record size in pgbench there is both an improvement in the
performance (approx 3%) as well as wal reduction (44%).

If the record size increases there is a very good reduction in WAL size.

Please provide your feedback.

With Regards,
Amit Kapila.

On 02/05/2013 11:53 PM, Amit Kapila wrote:
>> Performance data for the patch is attached with this mail.
>> Conclusions from the readings (these are same as my previous patch):
>>
>> 1. With orignal pgbench there is a max 7% WAL reduction with not much
>> performance difference.
>> 2. With 250 record pgbench there is a max wal reduction of 35% with not
>> much performance difference.
>> 3. With 500 and above record size in pgbench there is an improvement in
>> the performance and wal reduction both.
>>
>> If the record size increases there is a gain in performance and wal
>> size is reduced as well.
>>
>> Performance data for synchronous_commit = on is under progress, I shall
>> post it once it is done.
>> I am expecting it to be same as previous.
> Please find the performance readings for synchronous_commit = on.
>
> Each run is taken for 20 min.
>
> Conclusions from the readings with synchronous commit on mode:
>
> 1. With orignal pgbench there is a max 2% WAL reduction with not much
> performance difference.
> 2. With 500 record pgbench there is a max wal reduction of 3% with not much
> performance difference.
> 3. With 1800 record size in pgbench there is both an improvement in the
> performance (approx 3%) as well as wal reduction (44%).
>
> If the record size increases there is a very good reduction in WAL size.

The stats look fairly sane. I'm a little concerned about the apparent
trend of falling TPS in the patched vs original tests for the 1-client
test as record size increases, but it's only 0.0%->0.2%->0.4%, and the
0.4% case made other config changes too. Nonetheless, it might be wise
to check with really big records and see if the trend continues.

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

On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> >> Performance data for the patch is attached with this mail.
> >> Conclusions from the readings (these are same as my previous patch):
> >>
> >> 1. With orignal pgbench there is a max 7% WAL reduction with not
> much
> >> performance difference.
> >> 2. With 250 record pgbench there is a max wal reduction of 35% with
> not
> >> much performance difference.
> >> 3. With 500 and above record size in pgbench there is an improvement
> in
> >> the performance and wal reduction both.
> >>
> >> If the record size increases there is a gain in performance and wal
> >> size is reduced as well.
> >>
> >> Performance data for synchronous_commit = on is under progress, I
> shall
> >> post it once it is done.
> >> I am expecting it to be same as previous.
> > Please find the performance readings for synchronous_commit = on.
> >
> > Each run is taken for 20 min.
> >
> > Conclusions from the readings with synchronous commit on mode:
> >
> > 1. With orignal pgbench there is a max 2% WAL reduction with not much
> > performance difference.
> > 2. With 500 record pgbench there is a max wal reduction of 3% with
> not much
> > performance difference.
> > 3. With 1800 record size in pgbench there is both an improvement in
> the
> > performance (approx 3%) as well as wal reduction (44%).
> >
> > If the record size increases there is a very good reduction in WAL
> size.
>
> The stats look fairly sane. I'm a little concerned about the apparent
> trend of falling TPS in the patched vs original tests for the 1-client
> test as record size increases, but it's only 0.0%->0.2%->0.4%, and the
> 0.4% case made other config changes too. Nonetheless, it might be wise
> to check with really big records and see if the trend continues.

For bigger size (~2000) records, it goes into toast, for which we don't do
this optimization.
This optimization is mainly for medium size records.

With Regards,
Amit Kapila.

On 04.03.2013 06:39, Amit Kapila wrote:
> On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
>> On 02/05/2013 11:53 PM, Amit Kapila wrote:
>>>> Performance data for the patch is attached with this mail.
>>>> Conclusions from the readings (these are same as my previous patch):
>>>>
>>>> 1. With orignal pgbench there is a max 7% WAL reduction with not
>> much
>>>> performance difference.
>>>> 2. With 250 record pgbench there is a max wal reduction of 35% with
>> not
>>>> much performance difference.
>>>> 3. With 500 and above record size in pgbench there is an improvement
>> in
>>>> the performance and wal reduction both.
>>>>
>>>> If the record size increases there is a gain in performance and wal
>>>> size is reduced as well.
>>>>
>>>> Performance data for synchronous_commit = on is under progress, I
>> shall
>>>> post it once it is done.
>>>> I am expecting it to be same as previous.
>>> Please find the performance readings for synchronous_commit = on.
>>>
>>> Each run is taken for 20 min.
>>>
>>> Conclusions from the readings with synchronous commit on mode:
>>>
>>> 1. With orignal pgbench there is a max 2% WAL reduction with not much
>>> performance difference.
>>> 2. With 500 record pgbench there is a max wal reduction of 3% with
>> not much
>>> performance difference.
>>> 3. With 1800 record size in pgbench there is both an improvement in
>> the
>>> performance (approx 3%) as well as wal reduction (44%).
>>>
>>> If the record size increases there is a very good reduction in WAL
>> size.
>>
>> The stats look fairly sane. I'm a little concerned about the apparent
>> trend of falling TPS in the patched vs original tests for the 1-client
>> test as record size increases, but it's only 0.0%->0.2%->0.4%, and the
>> 0.4% case made other config changes too. Nonetheless, it might be wise
>> to check with really big records and see if the trend continues.
>
> For bigger size (~2000) records, it goes into toast, for which we don't do
> this optimization.
> This optimization is mainly for medium size records.

I've been doing investigating the pglz option further, and doing
performance comparisons of the pglz approach and this patch. I'll begin
with some numbers:

unpatched (63d283ecd0bc5078594a64dfbae29276072cdf45):

testname | wal_generated | duration

-----------------------------------------+---------------+------------------
two short fields, no change | 1245525360 | 9.94613695144653
two short fields, one changed | 1245536528 | 10.146910905838
two short fields, both changed | 1245523160 | 11.2332470417023
one short and one long field, no change | 1054926504 | 5.90477800369263
ten tiny fields, all changed | 1411774608 | 13.4536008834839
hundred tiny fields, all changed | 635739680 | 7.57448387145996
hundred tiny fields, half changed | 636930560 | 7.56888699531555
hundred tiny fields, half nulled | 573751120 | 6.68991994857788

Amit's wal_update_changes_v10.patch:

testname | wal_generated | duration

-----------------------------------------+---------------+------------------
two short fields, no change | 1249722112 | 13.0558869838715
two short fields, one changed | 1246145408 | 12.9947438240051
two short fields, both changed | 1245951056 | 13.0262880325317
one short and one long field, no change | 678480664 | 5.70031690597534
ten tiny fields, all changed | 1328873920 | 20.0167419910431
hundred tiny fields, all changed | 638149416 | 14.4236788749695
hundred tiny fields, half changed | 635560504 | 14.8770561218262
hundred tiny fields, half nulled | 558468352 | 16.2437210083008

pglz-with-micro-optimizations-1.patch:

testname | wal_generated |
duration
-----------------------------------------+---------------+------------------
two short fields, no change | 1245519008 | 11.6702048778534
two short fields, one changed | 1245756904 | 11.3233819007874
two short fields, both changed | 1249711088 | 11.6836447715759
one short and one long field, no change | 664741392 | 6.44810795783997
ten tiny fields, all changed | 1328085568 | 13.9679481983185
hundred tiny fields, all changed | 635974088 | 9.15514206886292
hundred tiny fields, half changed | 636309040 | 9.13769292831421
hundred tiny fields, half nulled | 496396448 | 8.77351498603821

In each test, a table is created with a large number of identical rows,
and fillfactor=50. Then a full-table UPDATE is performed, and the UPDATE
is timed. Duration is the time spent in the UPDATE (lower is better),
and wal_generated is the amount of WAL generated by the updates (lower
is better).

The summary is that Amit's patch is a small win in terms of CPU usage,
in the best case where the table has few columns, with one large column
that is not updated. In all other cases it just adds overhead. In terms
of WAL size, you get a big gain in the same best case scenario.

Attached is a different version of this patch, which uses the pglz
algorithm to spot the similarities between the old and new tuple,
instead of having explicit knowledge of where the column boundaries are.
This has the advantage that it will spot similarities, and be able to
compress, in more cases. For example, you can see a reduction in WAL
size in the "hundred tiny fields, half nulled" test case above.

The attached patch also just adds overhead in most cases, but the
overhead is much smaller in the worst case. I think that's the right
tradeoff here - we want to avoid scenarios where performance falls off
the cliff. That said, if you usually just get a slowdown, we certainly
can't make this the default, and if we can't turn it on by default, this
probably just isn't worth it.

The attached patch contains the variable-hash-size changes I posted in
the "Optimizing pglz compressor". But in the delta encoding function, it
goes further than that, and contains some further micro-optimizations:
the hash is calculated in a rolling fashion, and it uses a specialized
version of the pglz_hist_add macro that knows that the input can't
exceed 4096 bytes. Those changes shaved off some cycles, but you could
probably do more. One idea is to only add every 10 bytes or so to the
history lookup table; that would sacrifice some compressibility for speed.

If you could squeeze pglz_delta_encode function to be cheap enough that
we could enable this by default, this would be pretty cool patch. Or at
least, the overhead in the cases that you get no compression needs to be
brought down, to about 2-5 % at most I think. If it can't be done
easily, I feel that this probably needs to be dropped.

PS. I haven't done much testing of WAL redo, so it's quite possible that
the encoding is actually buggy, or that decoding is slow. But I don't
think there's anything so fundamentally wrong that it would affect the
performance results much.

- Heikki

On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> On 04.03.2013 06:39, Amit Kapila wrote:
> > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> >>>> Performance data for the patch is attached with this mail.
> >>>> Conclusions from the readings (these are same as my previous
> patch):
> >>>>
>
> I've been doing investigating the pglz option further, and doing
> performance comparisons of the pglz approach and this patch. I'll begin
> with some numbers:
>
> unpatched (63d283ecd0bc5078594a64dfbae29276072cdf45):
>
> testname | wal_generated |
> duration
>
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1245525360 |
> 9.94613695144653
> two short fields, one changed | 1245536528 |
> 10.146910905838
> two short fields, both changed | 1245523160 |
> 11.2332470417023
> one short and one long field, no change | 1054926504 |
> 5.90477800369263
> ten tiny fields, all changed | 1411774608 |
> 13.4536008834839
> hundred tiny fields, all changed | 635739680 |
> 7.57448387145996
> hundred tiny fields, half changed | 636930560 |
> 7.56888699531555
> hundred tiny fields, half nulled | 573751120 |
> 6.68991994857788
>
> Amit's wal_update_changes_v10.patch:
>
> testname | wal_generated |
> duration
>
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1249722112 |
> 13.0558869838715
> two short fields, one changed | 1246145408 |
> 12.9947438240051
> two short fields, both changed | 1245951056 |
> 13.0262880325317
> one short and one long field, no change | 678480664 |
> 5.70031690597534
> ten tiny fields, all changed | 1328873920 |
> 20.0167419910431
> hundred tiny fields, all changed | 638149416 |
> 14.4236788749695
> hundred tiny fields, half changed | 635560504 |
> 14.8770561218262
> hundred tiny fields, half nulled | 558468352 |
> 16.2437210083008
>
> pglz-with-micro-optimizations-1.patch:
>
> testname | wal_generated |
> duration
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1245519008 |
> 11.6702048778534
> two short fields, one changed | 1245756904 |
> 11.3233819007874
> two short fields, both changed | 1249711088 |
> 11.6836447715759
> one short and one long field, no change | 664741392 |
> 6.44810795783997
> ten tiny fields, all changed | 1328085568 |
> 13.9679481983185
> hundred tiny fields, all changed | 635974088 |
> 9.15514206886292
> hundred tiny fields, half changed | 636309040 |
> 9.13769292831421
> hundred tiny fields, half nulled | 496396448 |
> 8.77351498603821

For some of the tests, it doesn't even execute main part of
compression/encoding.
The reason is that the length of tuple is less than strategy min length, so
it returns from below check
in function pglz_delta_encode()
if (strategy->match_size_good <= 0 ||
slen < strategy->min_input_size ||
slen > strategy->max_input_size)
return false;

The tests for which it doesn't execute encoding are below:
two short fields, no change
two short fields, one changed
two short fields, both changed
ten tiny fields, all changed

For above cases, the reason of difference in timings for both approaches
with original could be due to the reason that
this check is done after some processing. So I think if we check the length
in log_heap_update, then
there should not be timing difference for above test scenario's. I can check
that once.

This optimization helps only when tuple is of length > 128~200 bytes and
upto 1800 bytes (till it turns to toast), otherwise it could result in
overhead without any major WAL reduction.
Infact I think in one of my initial patch there is a check if length of
tuple is greater than 128 bytes then perform the optimization.

I shall try to run both patches for cases when length of tuple is > 128~200
bytes, as this optimization has benefits in those cases.

> In each test, a table is created with a large number of identical rows,
> and fillfactor=50. Then a full-table UPDATE is performed, and the
> UPDATE is timed. Duration is the time spent in the UPDATE (lower is
> better), and wal_generated is the amount of WAL generated by the
> updates (lower is better).
>
> The summary is that Amit's patch is a small win in terms of CPU usage,
> in the best case where the table has few columns, with one large column
> that is not updated. In all other cases it just adds overhead. In terms
> of WAL size, you get a big gain in the same best case scenario.
>
> Attached is a different version of this patch, which uses the pglz
> algorithm to spot the similarities between the old and new tuple,
> instead of having explicit knowledge of where the column boundaries
> are.
> This has the advantage that it will spot similarities, and be able to
> compress, in more cases. For example, you can see a reduction in WAL
> size in the "hundred tiny fields, half nulled" test case above.
>
> The attached patch also just adds overhead in most cases, but the
> overhead is much smaller in the worst case. I think that's the right
> tradeoff here - we want to avoid scenarios where performance falls off
> the cliff. That said, if you usually just get a slowdown, we certainly
> can't make this the default, and if we can't turn it on by default,
> this probably just isn't worth it.

As I mentioned, for smaller tuples it can be overhead without any major
benefit of WAL reduction,
so I think before doing encoding it should ensure that tuple length is
greater than some threshold length.
Yes, it can miss some cases like your test has shown for (hundred tiny
fields, half nulled),
but we might be able to safely enable it for default.

> The attached patch contains the variable-hash-size changes I posted in
> the "Optimizing pglz compressor". But in the delta encoding function,
> it goes further than that, and contains some further micro-
> optimizations:
> the hash is calculated in a rolling fashion, and it uses a specialized
> version of the pglz_hist_add macro that knows that the input can't
> exceed 4096 bytes. Those changes shaved off some cycles, but you could
> probably do more.

> One idea is to only add every 10 bytes or so to the
> history lookup table; that would sacrifice some compressibility for
> speed.

Do you mean to say roll for 10 times and then call pglz_hist_add_no_recycle
and then same
before pglz_find_match?

I shall try doing this for the tests.

> If you could squeeze pglz_delta_encode function to be cheap enough that
> we could enable this by default, this would be pretty cool patch. Or at
> least, the overhead in the cases that you get no compression needs to
> be brought down, to about 2-5 % at most I think. If it can't be done
> easily, I feel that this probably needs to be dropped.

Agreed, though it gives benefit for some of the cases, but it should not
degrade much
for any of other cases.

One more thing that any compression technique will have some overhead, so it
should be
used optimally rather then in every case. So in that regards, I think we
should do this
optimization only when it has better chance of win (like based on length of
tuple or some other criteria
where WAL tuple can be logged as-is). What is your opinion?

> PS. I haven't done much testing of WAL redo, so it's quite possible
> that the encoding is actually buggy, or that decoding is slow. But I
> don't think there's anything so fundamentally wrong that it would
> affect the performance results much.

I also don't think it will have any problem, but I can run some test to
verify the same.

With Regards,
Amit Kapila.

On 2013-03-05 23:26:59 +0200, Heikki Linnakangas wrote:
> On 04.03.2013 06:39, Amit Kapila wrote:
> >>The stats look fairly sane. I'm a little concerned about the apparent
> >>trend of falling TPS in the patched vs original tests for the 1-client
> >>test as record size increases, but it's only 0.0%->0.2%->0.4%, and the
> >>0.4% case made other config changes too. Nonetheless, it might be wise
> >>to check with really big records and see if the trend continues.
> >
> >For bigger size (~2000) records, it goes into toast, for which we don't do
> >this optimization.
> >This optimization is mainly for medium size records.
>
> I've been doing investigating the pglz option further, and doing performance
> comparisons of the pglz approach and this patch. I'll begin with some
> numbers:
>
> unpatched (63d283ecd0bc5078594a64dfbae29276072cdf45):
>
> testname | wal_generated | duration
>
> -----------------------------------------+---------------+------------------
> two short fields, no change | 1245525360 | 9.94613695144653
> two short fields, one changed | 1245536528 | 10.146910905838
> two short fields, both changed | 1245523160 | 11.2332470417023
> one short and one long field, no change | 1054926504 | 5.90477800369263
> ten tiny fields, all changed | 1411774608 | 13.4536008834839
> hundred tiny fields, all changed | 635739680 | 7.57448387145996
> hundred tiny fields, half changed | 636930560 | 7.56888699531555
> hundred tiny fields, half nulled | 573751120 | 6.68991994857788
>
> Amit's wal_update_changes_v10.patch:
>
> testname | wal_generated | duration
>
> -----------------------------------------+---------------+------------------
> two short fields, no change | 1249722112 | 13.0558869838715
> two short fields, one changed | 1246145408 | 12.9947438240051
> two short fields, both changed | 1245951056 | 13.0262880325317
> one short and one long field, no change | 678480664 | 5.70031690597534
> ten tiny fields, all changed | 1328873920 | 20.0167419910431
> hundred tiny fields, all changed | 638149416 | 14.4236788749695
> hundred tiny fields, half changed | 635560504 | 14.8770561218262
> hundred tiny fields, half nulled | 558468352 | 16.2437210083008
>
> pglz-with-micro-optimizations-1.patch:
>
> testname | wal_generated | duration
> -----------------------------------------+---------------+------------------
> two short fields, no change | 1245519008 | 11.6702048778534
> two short fields, one changed | 1245756904 | 11.3233819007874
> two short fields, both changed | 1249711088 | 11.6836447715759
> one short and one long field, no change | 664741392 | 6.44810795783997
> ten tiny fields, all changed | 1328085568 | 13.9679481983185
> hundred tiny fields, all changed | 635974088 | 9.15514206886292
> hundred tiny fields, half changed | 636309040 | 9.13769292831421
> hundred tiny fields, half nulled | 496396448 | 8.77351498603821
>
> In each test, a table is created with a large number of identical rows, and
> fillfactor=50. Then a full-table UPDATE is performed, and the UPDATE is
> timed. Duration is the time spent in the UPDATE (lower is better), and
> wal_generated is the amount of WAL generated by the updates (lower is
> better).
>
> The summary is that Amit's patch is a small win in terms of CPU usage, in
> the best case where the table has few columns, with one large column that is
> not updated. In all other cases it just adds overhead. In terms of WAL size,
> you get a big gain in the same best case scenario.
>
> Attached is a different version of this patch, which uses the pglz algorithm
> to spot the similarities between the old and new tuple, instead of having
> explicit knowledge of where the column boundaries are. This has the
> advantage that it will spot similarities, and be able to compress, in more
> cases. For example, you can see a reduction in WAL size in the "hundred tiny
> fields, half nulled" test case above.
>
> The attached patch also just adds overhead in most cases, but the overhead
> is much smaller in the worst case. I think that's the right tradeoff here -
> we want to avoid scenarios where performance falls off the cliff. That said,
> if you usually just get a slowdown, we certainly can't make this the
> default, and if we can't turn it on by default, this probably just isn't
> worth it.
>
> The attached patch contains the variable-hash-size changes I posted in the
> "Optimizing pglz compressor". But in the delta encoding function, it goes
> further than that, and contains some further micro-optimizations: the hash
> is calculated in a rolling fashion, and it uses a specialized version of the
> pglz_hist_add macro that knows that the input can't exceed 4096 bytes. Those
> changes shaved off some cycles, but you could probably do more. One idea is
> to only add every 10 bytes or so to the history lookup table; that would
> sacrifice some compressibility for speed.
>
> If you could squeeze pglz_delta_encode function to be cheap enough that we
> could enable this by default, this would be pretty cool patch. Or at least,
> the overhead in the cases that you get no compression needs to be brought
> down, to about 2-5 % at most I think. If it can't be done easily, I feel
> that this probably needs to be dropped.

While this is exciting stuff - and I find Heikki's approach more
interesting and applicable to more cases - I think this is clearly not
9.3 material anymore. There are loads of tradeoffs here which requires
substantial amount of benchmarking and its not the kind of change that
can be backed out easily during 9.3's lifecycle.

And I have to say I find 2-5% performance overhead too high...

Greetings,

Andres Freund

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

On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> On 04.03.2013 06:39, Amit Kapila wrote:
> > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> >>>> Performance data for the patch is attached with this mail.
> >>>> Conclusions from the readings (these are same as my previous
> patch):
> >>>>
>
> I've been doing investigating the pglz option further, and doing
> performance comparisons of the pglz approach and this patch. I'll begin
> with some numbers:
>
> unpatched (63d283ecd0bc5078594a64dfbae29276072cdf45):
>
> testname | wal_generated |
> duration
>
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1245525360 |
> 9.94613695144653
> two short fields, one changed | 1245536528 |
> 10.146910905838
> two short fields, both changed | 1245523160 |
> 11.2332470417023
> one short and one long field, no change | 1054926504 |
> 5.90477800369263
> ten tiny fields, all changed | 1411774608 |
> 13.4536008834839
> hundred tiny fields, all changed | 635739680 |
> 7.57448387145996
> hundred tiny fields, half changed | 636930560 |
> 7.56888699531555
> hundred tiny fields, half nulled | 573751120 |
> 6.68991994857788
>
> Amit's wal_update_changes_v10.patch:
>
> testname | wal_generated |
> duration
>
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1249722112 |
> 13.0558869838715
> two short fields, one changed | 1246145408 |
> 12.9947438240051
> two short fields, both changed | 1245951056 |
> 13.0262880325317
> one short and one long field, no change | 678480664 |
> 5.70031690597534
> ten tiny fields, all changed | 1328873920 |
> 20.0167419910431
> hundred tiny fields, all changed | 638149416 |
> 14.4236788749695
> hundred tiny fields, half changed | 635560504 |
> 14.8770561218262
> hundred tiny fields, half nulled | 558468352 |
> 16.2437210083008
>
> pglz-with-micro-optimizations-1.patch:
>
> testname | wal_generated |
> duration
> -----------------------------------------+---------------+-------------
> -
> -----------------------------------------+---------------+----
> two short fields, no change | 1245519008 |
> 11.6702048778534
> two short fields, one changed | 1245756904 |
> 11.3233819007874
> two short fields, both changed | 1249711088 |
> 11.6836447715759
> one short and one long field, no change | 664741392 |
> 6.44810795783997
> ten tiny fields, all changed | 1328085568 |
> 13.9679481983185
> hundred tiny fields, all changed | 635974088 |
> 9.15514206886292
> hundred tiny fields, half changed | 636309040 |
> 9.13769292831421
> hundred tiny fields, half nulled | 496396448 |
> 8.77351498603821
>
> In each test, a table is created with a large number of identical rows,
> and fillfactor=50. Then a full-table UPDATE is performed, and the
> UPDATE is timed. Duration is the time spent in the UPDATE (lower is
> better), and wal_generated is the amount of WAL generated by the
> updates (lower is better).

Based on your patch, I have tried some more optimizations:

Fixed bug in your patch (pglz-with-micro-optimizations-2):
1. There were some problems in recovery due to wrong length of oldtuple
passed in decode which I have corrected.

Approach -1 (pglz-with-micro-optimizations-2_roll10_32)
1. Move strategy min length (32) check in log_heap_update
2. Rolling 10 for hash as suggested by you is added.

Approach -2 (pglz-with-micro-optimizations-2_roll10_32_1hashkey)
1. This is done on top of Approach-1 changes
2. Used 1 byte data as the hash key.

Approach-3
(pglz-with-micro-optimizations-2_roll10_32_1hashkey_batch_literal)
1. This is done on top of Approach-1 and Approach-2 changes
2. Instead of doing copy of literal byte when it founds as non match with
history, do all in a batch.

Data for all above approaches is in attached file "test_readings" (Apart
from your tests, I have added one more test " hundred tiny fields, first 10
changed")

Summary -
After changes of Approach-1, CPU utilization for all except 2 tests
("hundred tiny fields, all changed",
"hundred tiny fields, half changed") is either same or less. The best case
CPU utilization has decreased (which is better), but WAL reduction has
little bit increased (which is as per expectation due 10 consecutive
rollup's).

Approach-2 modifications was done to see if there is any overhead of hash
calculation.
Approach-2 & Approach-3 doesn't result into any improvements.

I have investigated the reason for CPU utilization for 2 tests and the
reason is that there is nothing to compress in the new tuple and that
information it will come to know only after it processes 75% (compression
ratio) of tuple bytes.
I think any compression algorithm will have this drawback that if data is
not compressible, it can consume time inspite
of the fact that it will not be able to compress the data.
I think most updates will update some part of tuple which will always yield
positive results.

Apart from above tests, I have run your patch against my old tests, it
yields quite positive results,
WAL Reduction is more as compare to my patch and CPU utilization is almost
similar or my patch is slightly better.
The results are in attached file "pgbench_pg_lz_mod"

The above all data is for synchronous_commit = off. I can collect the data
for synchronous_commit = on and
Performance of recovery.

Any further suggestions?

With Regards,
Amit Kapila.

On Friday, March 08, 2013 9:22 PM Amit Kapila wrote:
> On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> > On 04.03.2013 06:39, Amit Kapila wrote:
> > > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> > >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> > >>>> Performance data for the patch is attached with this mail.
> > >>>> Conclusions from the readings (these are same as my previous
> > patch):
> > >>>>
> >
> > I've been doing investigating the pglz option further, and doing
> > performance comparisons of the pglz approach and this patch. I'll
> > begin with some numbers:
> >
>
> Based on your patch, I have tried some more optimizations:
>
> Fixed bug in your patch (pglz-with-micro-optimizations-2):
> 1. There were some problems in recovery due to wrong length of oldtuple
> passed in decode which I have corrected.
>
> Approach -1 (pglz-with-micro-optimizations-2_roll10_32)
> 1. Move strategy min length (32) check in log_heap_update 2. Rolling 10
> for hash as suggested by you is added.
>
> Approach -2 (pglz-with-micro-optimizations-2_roll10_32_1hashkey)
> 1. This is done on top of Approach-1 changes 2. Used 1 byte data as the
> hash key.
>
> Approach-3
> (pglz-with-micro-optimizations-2_roll10_32_1hashkey_batch_literal)
> 1. This is done on top of Approach-1 and Approach-2 changes 2. Instead
> of doing copy of literal byte when it founds as non match with history,
> do all in a batch.
>
> Data for all above approaches is in attached file "test_readings"
> (Apart from your tests, I have added one more test " hundred tiny
> fields, first 10
> changed")
>
> Summary -
> After changes of Approach-1, CPU utilization for all except 2 tests
> ("hundred tiny fields, all changed", "hundred tiny fields, half
> changed") is either same or less. The best case CPU utilization has
> decreased (which is better), but WAL reduction has little bit increased
> (which is as per expectation due 10 consecutive rollup's).
>
> Approach-2 modifications was done to see if there is any overhead of
> hash calculation.
> Approach-2 & Approach-3 doesn't result into any improvements.
>
> I have investigated the reason for CPU utilization for 2 tests and the
> reason is that there is nothing to compress in the new tuple and that
> information it will come to know only after it processes 75%
> (compression
> ratio) of tuple bytes.
> I think any compression algorithm will have this drawback that if data
> is not compressible, it can consume time inspite of the fact that it
> will not be able to compress the data.
> I think most updates will update some part of tuple which will always
> yield positive results.
>
> Apart from above tests, I have run your patch against my old tests, it
> yields quite positive results, WAL Reduction is more as compare to my
> patch and CPU utilization is almost similar or my patch is slightly
> better.
> The results are in attached file "pgbench_pg_lz_mod"
>
> The above all data is for synchronous_commit = off. I can collect the
> data for synchronous_commit = on and Performance of recovery.

Data for synchronous_commit = on is as follows:

Find the data for heikki's test in file "test_readings_on.txt"

Result and observation is same as for synchronous_commit =off. In short,
Approach-1
as mentioned in above mail seems to be best.

Find the data for pg_bench based test's used in my previous tests in
"pgbench_pg_lz_mod_sync_commit_on.htm"
This has been done for Heikki's original patch and Approach-1.
It shows that there is very minor cpu dip (0.1%) in some cases and WAL
Reduction of (2~3%).
WAL reduction is not much as operations performed are less.

Recovery Performance
----------------------
pgbench org:

./pgbench -i -s 75 -F 80 postgres
./pgbench -c 4 -j 4 -T 600 postgres

pgbench 1800(rec size=1800):

./pgbench -i -s 10 -F 80 postgres
./pgbench -c 4 -j 4 -T 600 postgres

Recovery benchmark:

postgres org postgres pg lz
optimization
Recovery(sec) Recovery(sec)
pgbench org 11 11
pgbench 1800 16 11

This shows that with your patch recovery performance is also improved.

There is one more defect in recovery which is fixed in attached patch
pglz-with-micro-optimizations-3.patch.
In pglz_find_match(), it was going beyond maxlen for comparision due to
which encoded data was not properly written to WAL.

Finally, as per my work further to your patch, the best patch will be by
fixing recovery defects and changes for Approach-1.

With Regards,
Amit Kapila.

On Wednesday, March 13, 2013 5:50 PM Amit Kapila wrote:
> On Friday, March 08, 2013 9:22 PM Amit Kapila wrote:
> > On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> > > On 04.03.2013 06:39, Amit Kapila wrote:
> > > > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> > > >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> > > >>>> Performance data for the patch is attached with this mail.
> > > >>>> Conclusions from the readings (these are same as my previous
> > > patch):
> > > >>>>
> > >
> > > I've been doing investigating the pglz option further, and doing
> > > performance comparisons of the pglz approach and this patch. I'll
> > > begin with some numbers:
> > >
> >
> > Based on your patch, I have tried some more optimizations:
> >

Based on numbers provided by Daniel for compression methods, I tried Snappy
Algorithm for encoding
and it addresses most of your concerns that it should not degrade
performance for majority cases.

postgres orginal:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
two short fields, no change | 1232916160 | 34.0338308811188
two short fields, one changed | 1232909704 | 32.8722319602966
two short fields, both changed | 1236770128 | 35.445415019989
one short and one long field, no change | 1053000144 | 23.2983899116516
ten tiny fields, all changed | 1397452584 | 40.2718069553375
hundred tiny fields, first 10 changed | 622082664 | 21.7642788887024
hundred tiny fields, all changed | 626461528 | 20.964781999588
hundred tiny fields, half changed | 621900472 | 21.6473519802094
hundred tiny fields, half nulled | 557714752 | 19.0088789463043
(9 rows)

postgres encode wal using snappy:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
two short fields, no change | 1232915128 | 34.6910920143127
two short fields, one changed | 1238902520 | 34.2287850379944
two short fields, both changed | 1233882056 | 35.3292708396912
one short and one long field, no change | 733095168 | 20.3494939804077
ten tiny fields, all changed | 1314959744 | 38.969575881958
hundred tiny fields, first 10 changed | 483275136 | 19.6973309516907
hundred tiny fields, all changed | 481755280 | 19.7665288448334
hundred tiny fields, half changed | 488693616 | 19.7246761322021
hundred tiny fields, half nulled | 483425712 | 18.6299569606781
(9 rows)

Changes are to call snappy compress and decompress for encoding and decoding
in patch.
I am doing encoding for tup length greater than 32, as for too small tuples
it might not make much sense for encoding.

On my m/c while using snapy compress/decompress, it was giving stack
corruption for first 4 bytes, so I put below fix to proceed.
I am looking into reason of same.
1. snappy_compress - Increment the encoded data buffer with 4 bytes before
encryption starts.
2. snappy_uncompress - Decrement the 4 bytes increment done during compress.

3. snappy_uncompressed_length - Decrement the 4 bytes increment done during
compress.

For LZ compression patch, there was small problem in identifying max length
which I have corrected in separate patch
'pglz-with-micro-optimizations-4.patch'

In my opinion, there can be following ways for this patch:
1. Use LZ compression, but provide a way to user so that it can be avoided
for cases where much compression is not possible.
I see this as a viable way because most updates will update only have few
columns and rest data would be same.
2. Use snappy API's, do anyone know of standard library of snappy?
3. Provide multiple compression ways, so depending on usage, user can use
appropriate one.

Feedback?

With Regards,
Amit Kapila.

On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> On 04.03.2013 06:39, Amit Kapila wrote:
> > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> >>>> Performance data for the patch is attached with this mail.
> >>>> Conclusions from the readings (these are same as my previous
> patch):
> >>>>

> The attached patch also just adds overhead in most cases, but the
> overhead is much smaller in the worst case. I think that's the right
> tradeoff here - we want to avoid scenarios where performance falls off
> the cliff. That said, if you usually just get a slowdown, we certainly
> can't make this the default, and if we can't turn it on by default,
> this probably just isn't worth it.
>
> The attached patch contains the variable-hash-size changes I posted in
> the "Optimizing pglz compressor". But in the delta encoding function,
> it goes further than that, and contains some further micro-
> optimizations:
> the hash is calculated in a rolling fashion, and it uses a specialized
> version of the pglz_hist_add macro that knows that the input can't
> exceed 4096 bytes. Those changes shaved off some cycles, but you could
> probably do more. One idea is to only add every 10 bytes or so to the
> history lookup table; that would sacrifice some compressibility for
> speed.
>
> If you could squeeze pglz_delta_encode function to be cheap enough that
> we could enable this by default, this would be pretty cool patch. Or at
> least, the overhead in the cases that you get no compression needs to
> be brought down, to about 2-5 % at most I think. If it can't be done
> easily, I feel that this probably needs to be dropped.

After trying some more on optimizing pglz_delta_encode(), I found that if we
use new data also in history, then the results of compression
and cpu utilization are much better.

In addition to the pg lz micro optimization changes, following changes are
done in modified patch

1. The unmatched new data is also added to the history which can be
referenced later.
2. To incorporate this change in the lZ algorithm, 1 extra control bit is
needed to indicate if data is from old or new tuple

Performance Data
-----------------

Head code:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------

two short fields, no change | 1232908016 | 36.3914430141449
two short fields, one changed | 1232904040 | 36.5231261253357
two short fields, both changed | 1235215048 | 37.7455959320068
one short and one long field, no change | 1051394568 | 24.418487071991
ten tiny fields, all changed | 1395189872 | 43.2316210269928
hundred tiny fields, first 10 changed | 622156848 | 21.9155580997467
hundred tiny fields, all changed | 625962056 | 22.3296411037445
hundred tiny fields, half changed | 621901128 | 21.3881061077118
hundred tiny fields, half nulled | 557708096 | 19.4633228778839

pglz-with-micro-optimization-compress-using-newdata-1:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------

two short fields, no change | 1235992768 | 37.3365149497986
two short fields, one changed | 1240979256 | 36.897796869278
two short fields, both changed | 1236079976 | 38.4273149967194
one short and one long field, no change | 651010944 | 20.9490079879761
ten tiny fields, all changed | 1315606864 | 42.5771369934082
hundred tiny fields, first 10 changed | 459134432 | 17.4556930065155
hundred tiny fields, all changed | 456506680 | 17.8865270614624
hundred tiny fields, half changed | 454784456 | 18.0130441188812
hundred tiny fields, half nulled | 486675784 | 18.6600229740143

Observation
---------------
1. It yielded compression in more cases (refer all cases of hundred tiny
fields)
2. CPU- utilization is also better.

Performance data for pgbench related scenarios is attached in document
(pgbench_lz_opt_compress_using_newdata.htm)

1. Better reduction in WAL
2. TPS increase can be observed after records size is >=250
3. There is small performance penality for single-thread (0.04~3.45), but
when penality is 3.45 in single thread, for 8 threads TPS improvement is
high.

Do you think it matches the conditions you have in mind for further
proceeding of this patch?

Thanks to Hari Babu for helping in implementation of this idea and taking
performance data.

With Regards,
Amit Kapila.

On Friday, June 07, 2013 5:07 PM Amit Kapila wrote:
>On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
>> On 04.03.2013 06:39, Amit Kapila wrote:
>> > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
>> >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
>> >>>> Performance data for the patch is attached with this mail.
>> >>>> Conclusions from the readings (these are same as my previous
>> patch):
>> >>>>
>>
>> The attached patch also just adds overhead in most cases, but the
>> overhead is much smaller in the worst case. I think that's the right
>> tradeoff here - we want to avoid scenarios where performance falls off
>> the cliff. That said, if you usually just get a slowdown, we certainly
>> can't make this the default, and if we can't turn it on by default,
>> this probably just isn't worth it.
>>
>> The attached patch contains the variable-hash-size changes I posted in
>> the "Optimizing pglz compressor". But in the delta encoding function,
>> it goes further than that, and contains some further micro-
>> optimizations:
>> the hash is calculated in a rolling fashion, and it uses a specialized
>> version of the pglz_hist_add macro that knows that the input can't
>> exceed 4096 bytes. Those changes shaved off some cycles, but you could
>> probably do more. One idea is to only add every 10 bytes or so to the
>> history lookup table; that would sacrifice some compressibility for
>> speed.
>>
>> If you could squeeze pglz_delta_encode function to be cheap enough
>> that we could enable this by default, this would be pretty cool patch.
>> Or at least, the overhead in the cases that you get no compression
>> needs to be brought down, to about 2-5 % at most I think. If it can't
>> be done easily, I feel that this probably needs to be dropped.

>After trying some more on optimizing pglz_delta_encode(), I found that if
we use new data also in history, then the results of compression and cpu
utilization >are much better.

>In addition to the pg lz micro optimization changes, following changes are
done in modified patch

>1. The unmatched new data is also added to the history which can be
referenced later.
>2. To incorporate this change in the lZ algorithm, 1 extra control bit is
needed to indicate if data is from old or new tuple

The patch is rebased to use the new PG LZ algorithm optimization changes
which got committed recently.

Performance Data
-----------------

Head code:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------

two short fields, no change | 1232911016 | 35.1784930229187
two short fields, one changed | 1240322016 | 35.0436308383942
two short fields, both changed | 1235318352 | 35.4989421367645
one short and one long field, no change | 1042332336 | 23.4457180500031
ten tiny fields, all changed | 1395194136 | 41.9023628234863
hundred tiny fields, first 10 changed | 626725984 | 21.2999589443207
hundred tiny fields, all changed | 621899224 | 21.6676609516144
hundred tiny fields, half changed | 623998272 | 21.2745981216431
hundred tiny fields, half nulled | 557714088 | 19.5902800559998

pglz-with-micro-optimization-compress-using-newdata-2:

testname | wal_generated | duration
-----------------------------------------+---------------+------------------

two short fields, no change | 1232903384 | 35.0115969181061
two short fields, one changed | 1232906960 | 34.3333759307861
two short fields, both changed | 1232903520 | 35.7665238380432
one short and one long field, no change | 649647992 | 19.4671010971069
ten tiny fields, all changed | 1314957136 | 39.9727990627289
hundred tiny fields, first 10 changed | 458684024 | 17.8197758197784
hundred tiny fields, all changed | 461028464 | 17.3083391189575
hundred tiny fields, half changed | 456528696 | 17.1769199371338
hundred tiny fields, half nulled | 480548936 | 18.81720495224

Observation
---------------
1. It yielded compression in more cases (refer all cases of hundred tiny
fields)
2. CPU- utilization is also better.

Performance data for pgbench related scenarios is attached in document
(pgbench_lz_opt_compress_using_newdata-2.htm)

1. Better reduction in WAL
2. TPS increase can be observed after records size is >=250
3. There is small performance penality for single-thread (0.36~3.23),
but when penality is 3.23 in single thread, for 8 threads TPS improvement
is high.

Please suggest any further proceedings on this patch.

Regards,
Hari babu.

I can't comment on further direction for the patch, but since it was marked
as Needs Review in the CF app I took a quick look at it.

It patches and compiles clean against the current Git HEAD, and 'make
check' runs successfully.

Does it need documentation for the GUC variable
'wal_update_compression_ratio'?

__________________________________________________________________________________
*Mike Blackwell | Technical Analyst, Distribution Services/Rollout
Management | RR Donnelley*
1750 Wallace Ave | St Charles, IL 60174-3401
Office: 630.313.7818
Mike(dot)Blackwell(at)rrd(dot)com
http://www.rrdonnelley.com

<http://www.rrdonnelley.com/>
* <Mike(dot)Blackwell(at)rrd(dot)com>*

On Tue, Jul 2, 2013 at 2:26 AM, Hari Babu <haribabu(dot)kommi(at)huawei(dot)com> wrote:

> On Friday, June 07, 2013 5:07 PM Amit Kapila wrote:
> >On Wednesday, March 06, 2013 2:57 AM Heikki Linnakangas wrote:
> >> On 04.03.2013 06:39, Amit Kapila wrote:
> >> > On Sunday, March 03, 2013 8:19 PM Craig Ringer wrote:
> >> >> On 02/05/2013 11:53 PM, Amit Kapila wrote:
> >> >>>> Performance data for the patch is attached with this mail.
> >> >>>> Conclusions from the readings (these are same as my previous
> >> patch):
> >> >>>>
> >>
> >> The attached patch also just adds overhead in most cases, but the
> >> overhead is much smaller in the worst case. I think that's the right
> >> tradeoff here - we want to avoid scenarios where performance falls off
> >> the cliff. That said, if you usually just get a slowdown, we certainly
> >> can't make this the default, and if we can't turn it on by default,
> >> this probably just isn't worth it.
> >>
> >> The attached patch contains the variable-hash-size changes I posted in
> >> the "Optimizing pglz compressor". But in the delta encoding function,
> >> it goes further than that, and contains some further micro-
> >> optimizations:
> >> the hash is calculated in a rolling fashion, and it uses a specialized
> >> version of the pglz_hist_add macro that knows that the input can't
> >> exceed 4096 bytes. Those changes shaved off some cycles, but you could
> >> probably do more. One idea is to only add every 10 bytes or so to the
> >> history lookup table; that would sacrifice some compressibility for
> >> speed.
> >>
> >> If you could squeeze pglz_delta_encode function to be cheap enough
> >> that we could enable this by default, this would be pretty cool patch.
> >> Or at least, the overhead in the cases that you get no compression
> >> needs to be brought down, to about 2-5 % at most I think. If it can't
> >> be done easily, I feel that this probably needs to be dropped.
>
> >After trying some more on optimizing pglz_delta_encode(), I found that if
> we use new data also in history, then the results of compression and cpu
> utilization >are much better.
>
> >In addition to the pg lz micro optimization changes, following changes are
> done in modified patch
>
> >1. The unmatched new data is also added to the history which can be
> referenced later.
> >2. To incorporate this change in the lZ algorithm, 1 extra control bit is
> needed to indicate if data is from old or new tuple
>
> The patch is rebased to use the new PG LZ algorithm optimization changes
> which got committed recently.
>
> Performance Data
> -----------------
>
> Head code:
>
> testname | wal_generated | duration
>
> -----------------------------------------+---------------+------------------
>
> two short fields, no change | 1232911016 | 35.1784930229187
> two short fields, one changed | 1240322016 | 35.0436308383942
> two short fields, both changed | 1235318352 | 35.4989421367645
> one short and one long field, no change | 1042332336 | 23.4457180500031
> ten tiny fields, all changed | 1395194136 | 41.9023628234863
> hundred tiny fields, first 10 changed | 626725984 | 21.2999589443207
> hundred tiny fields, all changed | 621899224 | 21.6676609516144
> hundred tiny fields, half changed | 623998272 | 21.2745981216431
> hundred tiny fields, half nulled | 557714088 | 19.5902800559998
>
>
> pglz-with-micro-optimization-compress-using-newdata-2:
>
> testname | wal_generated | duration
>
> -----------------------------------------+---------------+------------------
>
> two short fields, no change | 1232903384 | 35.0115969181061
> two short fields, one changed | 1232906960 | 34.3333759307861
> two short fields, both changed | 1232903520 | 35.7665238380432
> one short and one long field, no change | 649647992 | 19.4671010971069
> ten tiny fields, all changed | 1314957136 | 39.9727990627289
> hundred tiny fields, first 10 changed | 458684024 | 17.8197758197784
> hundred tiny fields, all changed | 461028464 | 17.3083391189575
> hundred tiny fields, half changed | 456528696 | 17.1769199371338
> hundred tiny fields, half nulled | 480548936 | 18.81720495224
>
> Observation
> ---------------
> 1. It yielded compression in more cases (refer all cases of hundred tiny
> fields)
> 2. CPU- utilization is also better.
>
>
> Performance data for pgbench related scenarios is attached in document
> (pgbench_lz_opt_compress_using_newdata-2.htm)
>
> 1. Better reduction in WAL
> 2. TPS increase can be observed after records size is >=250
> 3. There is small performance penality for single-thread (0.36~3.23),
> but when penality is 3.23 in single thread, for 8 threads TPS
> improvement
> is high.
>
> Please suggest any further proceedings on this patch.
>
> Regards,
> Hari babu.
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>
>

On 07/08/2013 02:21 PM, Mike Blackwell wrote:
> I can't comment on further direction for the patch, but since it was marked
> as Needs Review in the CF app I took a quick look at it.
>
> It patches and compiles clean against the current Git HEAD, and 'make
> check' runs successfully.
>
> Does it need documentation for the GUC variable
> 'wal_update_compression_ratio'?

Yes.

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

On Tuesday, July 09, 2013 2:52 AM Mike Blackwell wrote:

> I can't comment on further direction for the patch, but since it was marked as Needs Review in the CF app I took a quick look at it.
Thanks for looking into it.

Last time Heikki has found test scenario's where the original patch was not performing good.
He has also proposed a different approach for WAL encoding and sent the modified patch which has comparatively less negative performance impact and
asked to check if the patch can reduce the performance impact for the scenario's mentioned by him.
After that I found that with some modification's (use new tuple data for encoding) in his approach, it eliminates the negative performance impact and
have WAL reduction for more number of cases.

I think the first thing to verify is whether the results posted can be validated in some other environment setup by another person.
The testcase used is posted at below link:
http://www.postgresql.org/message-id/51366323.8070606@vmware.com

> It patches and compiles clean against the current Git HEAD, and 'make check' runs successfully.

> Does it need documentation for the GUC variable 'wal_update_compression_ratio'?

This variable has been added to test the patch for different compression_ratio during development test.
It was not decided to have this variable permanently as part of this patch, so currently there is no documentation for it.
However if the decision comes out to be that it needs to be part of patch, then documentation for same can be updated.

With Regards,
Amit Kapila.

The only environment I have available at the moment is a virtual box.
That's probably not going to be very helpful for performance testing.

__________________________________________________________________________________
*Mike Blackwell | Technical Analyst, Distribution Services/Rollout
Management | RR Donnelley*
1750 Wallace Ave | St Charles, IL 60174-3401
Office: 630.313.7818
Mike(dot)Blackwell(at)rrd(dot)com
http://www.rrdonnelley.com

<http://www.rrdonnelley.com/>
* <Mike(dot)Blackwell(at)rrd(dot)com>*

On Mon, Jul 8, 2013 at 11:09 PM, Amit Kapila <amit(dot)kapila(at)huawei(dot)com> wrote:

>
> On Tuesday, July 09, 2013 2:52 AM Mike Blackwell wrote:
>
> > I can't comment on further direction for the patch, but since it was
> marked as Needs Review in the CF app I took a quick look at it.
> Thanks for looking into it.
>
> Last time Heikki has found test scenario's where the original patch was
> not performing good.
> He has also proposed a different approach for WAL encoding and sent the
> modified patch which has comparatively less negative performance impact and
> asked to check if the patch can reduce the performance impact for the
> scenario's mentioned by him.
> After that I found that with some modification's (use new tuple data for
> encoding) in his approach, it eliminates the negative performance impact
> and
> have WAL reduction for more number of cases.
>
> I think the first thing to verify is whether the results posted can be
> validated in some other environment setup by another person.
> The testcase used is posted at below link:
> http://www.postgresql.org/message-id/51366323.8070606@vmware.com
>
>
>
> > It patches and compiles clean against the current Git HEAD, and 'make
> check' runs successfully.
>
> > Does it need documentation for the GUC variable
> 'wal_update_compression_ratio'?
>
> This variable has been added to test the patch for different
> compression_ratio during development test.
> It was not decided to have this variable permanently as part of this
> patch, so currently there is no documentation for it.
> However if the decision comes out to be that it needs to be part of
> patch, then documentation for same can be updated.
>
> With Regards,
> Amit Kapila.
>
>
>
> --
> Sent via pgsql-hackers mailing list (pgsql-hackers(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
>

> On Wednesday, July 10, 2013 6:32 AM Mike Blackwell wrote:

> The only environment I have available at the moment is a virtual box. That's probably not going to be very helpful for performance testing.

It's okay. Anyway thanks for doing the basic test for patch.

With Regards,
Amit Kapila.

On 7/9/13 12:09 AM, Amit Kapila wrote:
> I think the first thing to verify is whether the results posted can be validated in some other environment setup by another person.
> The testcase used is posted at below link:
> http://www.postgresql.org/message-id/51366323.8070606@vmware.com

That seems easy enough to do here, Heikki's test script is excellent.
The latest patch Hari posted on July 2 has one hunk that doesn't apply
anymore now. Inside src/backend/utils/adt/pg_lzcompress.c the patch
tries to change this code:

- if (hent)
+ if (hentno != INVALID_ENTRY)

But that line looks like this now:

if (hent != INVALID_ENTRY_PTR)

Definitions of those:

#define INVALID_ENTRY 0
#define INVALID_ENTRY_PTR (&hist_entries[INVALID_ENTRY])

I'm not sure if different error handling may be needed here now due the
commit that changed this, or if the patch wasn't referring to the right
type of error originally.

--
Greg Smith 2ndQuadrant US greg(at)2ndQuadrant(dot)com Baltimore, MD
PostgreSQL Training, Services, and 24x7 Support www.2ndQuadrant.com

Greg,

* Greg Smith (greg(at)2ndQuadrant(dot)com) wrote:
> That seems easy enough to do here, Heikki's test script is
> excellent. The latest patch Hari posted on July 2 has one hunk that
> doesn't apply anymore now. Inside
> src/backend/utils/adt/pg_lzcompress.c the patch tries to change this
> code:
>
> - if (hent)
> + if (hentno != INVALID_ENTRY)

hentno certainly doesn't make much sense here- it's only used at the top
of the function to keep things a bit cleaner when extracting the address
into hent from hist_entries:

hentno = hstart[pglz_hist_idx(input, end, mask)];
hent = &hist_entries[hentno];

Indeed, as the referenced conditional is inside the following loop:

while (hent != INVALID_ENTRY_PTR)

and, since hentno == 0 implies hent == INVALID_ENTRY_PTR, the
conditional would never fail (which is what was happening prior to
Heikki commiting the fix for this, changing the conditional to what is
below).

> But that line looks like this now:
>
> if (hent != INVALID_ENTRY_PTR)

Right, this is correct- it's useful to check the new value for hent
after it's been updated by:

hent = hent->next;

and see if it's possible to drop out early.

> I'm not sure if different error handling may be needed here now due
> the commit that changed this, or if the patch wasn't referring to
> the right type of error originally.

I've not looked at anything regarding this beyond this email, but I'm
pretty confident that the change Heikki committed was the correct one.

Thanks,

Stephen

On Friday, July 19, 2013 4:11 AM Greg Smith wrote:
>On 7/9/13 12:09 AM, Amit Kapila wrote:
>> I think the first thing to verify is whether the results posted can be validated in some other environment setup by another person.
>> The testcase used is posted at below link:
>> http://www.postgresql.org/message-id/51366323.8070606@vmware.com

>That seems easy enough to do here, Heikki's test script is excellent.
>The latest patch Hari posted on July 2 has one hunk that doesn't apply
>anymore now.

The Head code change from Heikki is correct.
During the patch rebase to latest PG LZ optimization code, the above code change is missed.

Apart from the above changed some more changes are done in the patch, those are.

1. corrected some comments in the code
2. Added a validity check as source and history length combined cannot be more than or equal to 8192.

Thanks for the review, please find the latest patch attached in the mail.

Regards,
Hari babu.

The v3 patch applies perfectly here now. Attached is a spreadsheet with
test results from two platforms, a Mac laptop and a Linux server. I
used systems with high disk speed because that seemed like a worst case
for this improvement. The actual improvement for shrinking WAL should
be even better on a system with slower disks.

There are enough problems with the "hundred tiny fields" results that I
think this not quite ready for commit yet. More comments on that below.
This seems close though, close enough that I am planning to follow up
to see if the slow disk results are better.

Reviewing the wal-update-testsuite.sh test program, I think the only
case missing that would be useful to add is "ten tiny fields, one
changed". I think that one is interesting to highlight because it's
what benchmark programs like pgbench do very often.

The GUC added by the program looks like this:

postgres=# show wal_update_compression_ratio ;
wal_update_compression_ratio
------------------------------
25

Is possible to add a setting here that disables the feature altogether?
That always makes it easier to consider a commit, knowing people can
roll back the change if it makes performance worse. That would make
performance testing easier too. wal-update-testsuit.sh takes as long as
13 minutes, it's long enough that I'd like the easier to automate
comparison GUC disabling adds. If that's not practical to do given the
intrusiveness of the code, it's not really necessary. I haven't looked
at the change enough to be sure how hard this is.

On the Mac, the only case that seems to have a slowdown now is "hundred
tiny fields, half nulled". It would be nice to understand just what is
going on with that one. I got some ugly results in "two short fields,
no change" too, along with a couple of other weird results, but I think
those were testing procedure issues that can be ignored. The pgbench
throttle work I did recently highlights that I can't really make a Mac
quiet/consistent for benchmarking very well. Note that I ran all of the
Mac tests with assertions on, to try and catch platform specific bugs.
The Linux ones used the default build parameters.

On Linux "hundred tiny fields, half nulled" was also by far the worst
performing one, with a >30% increase in duration despite the 14% drop in
WAL. Exactly what's going on there really needs to be investigated
before this seems safe to commit. All of the "hundred tiny fields"
cases seem pretty bad on Linux, with the rest of them running about a
11% duration increase.

This doesn't seem ready to commit for this CF, but the number of problem
cases is getting pretty small now. Now that I've gotten more familiar
with the test programs and the feature, I can run more performance tests
on this at any time really. If updates addressing the trouble cases are
ready from Amit or Hari before the next CF, send them out and I can look
at them without waiting until that one starts. This is a very promising
looking performance feature.

--
Greg Smith 2ndQuadrant US greg(at)2ndQuadrant(dot)com Baltimore, MD
PostgreSQL Training, Services, and 24x7 Support www.2ndQuadrant.com

On 2013-07-19 10:40:01 +0530, Hari Babu wrote:
>
> On Friday, July 19, 2013 4:11 AM Greg Smith wrote:
> >On 7/9/13 12:09 AM, Amit Kapila wrote:
> >> I think the first thing to verify is whether the results posted can be validated in some other environment setup by another person.
> >> The testcase used is posted at below link:
> >> http://www.postgresql.org/message-id/51366323.8070606@vmware.com
>
> >That seems easy enough to do here, Heikki's test script is excellent.
> >The latest patch Hari posted on July 2 has one hunk that doesn't apply
> >anymore now.
>
> The Head code change from Heikki is correct.
> During the patch rebase to latest PG LZ optimization code, the above code change is missed.
>
> Apart from the above changed some more changes are done in the patch, those are.

FWIW I don't like this approach very much:

* I'd be very surprised if this doesn't make WAL replay of update heavy
workloads slower by at least factor of 2.

* It makes data recovery from WAL *noticeably* harder since data
corruption now is carried forwards and you need the old data to decode
new data

* It makes changeset extraction either more expensive or it would have
to be disabled there.

I think my primary issue is that philosophically/architecturally I am of
the opinion that a wal record should make sense of it's own without
depending on heap data. And this patch looses that.

Greetings,

Andres

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

On 7/22/13 2:57 PM, Andres Freund wrote:
> * I'd be very surprised if this doesn't make WAL replay of update heavy
> workloads slower by at least factor of 2.

I was thinking about what a benchmark of WAL replay would look like last
year. I don't think that data is captured very well yet, and it should be.

My idea was to break the benchmark into two pieces. One would take a
base backup, then run a series of tests and archive the resulting the
WAL. I doubt you can make a useful benchmark here without a usefully
populated database, that's why the base backup step is needed.

The first useful result then is to measure how long commit/archiving
took and the WAL volume, which is what's done by the test harness for
this program. Then the resulting backup would be setup for replay.
tarring up the backup and WAL archive could even give you a repeatable
test set for ones where it's only replay changes happening. Then the
main number that's useful, total replay time, would be measured.

The main thing I wanted this for wasn't for code changes; it was to
benchmark configuration changes. I'd like to be able to answer
questions like "which I/O scheduler is best for a standby" in a way that
has real test data behind it. The same approach should useful for
answering your concerns about the replay performance impact of this
change too though.

> * It makes changeset extraction either more expensive or it would have
> to be disabled there.

That argues that if committed at all, the ability to turn this off I was
asking about would be necessary. It sounds like this *could* work like
how minimal WAL archiving levels allow optimizations that are disabled
at higher ones--like the COPY into a truncated/new table cheat.

--
Greg Smith 2ndQuadrant US greg(at)2ndQuadrant(dot)com Baltimore, MD
PostgreSQL Training, Services, and 24x7 Support www.2ndQuadrant.com

On Tuesday, July 23, 2013 12:02 AM Greg Smith wrote:
> The v3 patch applies perfectly here now. Attached is a spreadsheet
> with test results from two platforms, a Mac laptop and a Linux server.
> I used systems with high disk speed because that seemed like a worst
> case for this improvement. The actual improvement for shrinking WAL
> should be even better on a system with slower disks.

You are absolutely right.
To mimic it on our system, by configuring RAMFS for database, it shows similar results.

> There are enough problems with the "hundred tiny fields" results that I
> think this not quite ready for commit yet. More comments on that
> below.
> This seems close though, close enough that I am planning to follow up
> to see if the slow disk results are better.

Thanks for going extra mile to try for slower disks.

> Reviewing the wal-update-testsuite.sh test program, I think the only
> case missing that would be useful to add is "ten tiny fields, one
> changed". I think that one is interesting to highlight because it's
> what benchmark programs like pgbench do very often.
> The GUC added by the program looks like this:
>
> postgres=# show wal_update_compression_ratio ;
> wal_update_compression_ratio
> ------------------------------
> 25
>
> Is possible to add a setting here that disables the feature altogether?

Yes, it can be done in below 2 ways:
1. Provide a new configuration parameter (wal_update_compression) to turn on/off this feature.
2. At table level user can be given option to configure

> That always makes it easier to consider a commit, knowing people can
> roll back the change if it makes performance worse. That would make
> performance testing easier too. wal-update-testsuit.sh takes as long
> as
> 13 minutes, it's long enough that I'd like the easier to automate
> comparison GUC disabling adds. If that's not practical to do given the
> intrusiveness of the code, it's not really necessary. I haven't looked
> at the change enough to be sure how hard this is.
>
> On the Mac, the only case that seems to have a slowdown now is "hundred
> tiny fields, half nulled". It would be nice to understand just what is
> going on with that one. I got some ugly results in "two short fields,
> no change" too, along with a couple of other weird results, but I think
> those were testing procedure issues that can be ignored. The pgbench
> throttle work I did recently highlights that I can't really make a Mac
> quiet/consistent for benchmarking very well. Note that I ran all of
> the Mac tests with assertions on, to try and catch platform specific
> bugs.
> The Linux ones used the default build parameters.
>
> On Linux "hundred tiny fields, half nulled" was also by far the worst
> performing one, with a >30% increase in duration despite the 14% drop
> in WAL. Exactly what's going on there really needs to be investigated
> before this seems safe to commit. All of the "hundred tiny fields"
> cases seem pretty bad on Linux, with the rest of them running about a
> 11% duration increase.

The main benefit of this patch is to reduce WAL for improving time in I/O,
But I think for faster I/O systems, the calculation to reduce WAL has overhead.
I will check how to optimize that calculation, but I think this feature should be consider
with configuration knob as it can improve many cases.

With Regards,
Amit Kapila.

On Tuesday, July 23, 2013 12:27 AM Andres Freund wrote:
> On 2013-07-19 10:40:01 +0530, Hari Babu wrote:
> >
> > On Friday, July 19, 2013 4:11 AM Greg Smith wrote:
> > >On 7/9/13 12:09 AM, Amit Kapila wrote:
> > >> I think the first thing to verify is whether the results posted
> can be validated in some other environment setup by another person.
> > >> The testcase used is posted at below link:
> > >> http://www.postgresql.org/message-
> id/51366323(dot)8070606(at)vmware(dot)com
> >
> > >That seems easy enough to do here, Heikki's test script is
> excellent.
> > >The latest patch Hari posted on July 2 has one hunk that doesn't
> apply
> > >anymore now.
> >
> > The Head code change from Heikki is correct.
> > During the patch rebase to latest PG LZ optimization code, the above
> code change is missed.
> >
> > Apart from the above changed some more changes are done in the patch,
> those are.
>
> FWIW I don't like this approach very much:
>
> * I'd be very surprised if this doesn't make WAL replay of update heavy
> workloads slower by at least factor of 2.

Yes, if you just consider the cost of replay, but it involves other
operations as well
like for standby case transfer of WAL, Write of WAL, Read from WAL and
then apply.
So among them most operation's will be benefited from reduced WAL size,
except apply where you need to decode.

> * It makes data recovery from WAL *noticeably* harder since data
> corruption now is carried forwards and you need the old data to
> decode
> new data

This is one of the reasons why this optimization is done only when the
new row goes in same page.

> * It makes changeset extraction either more expensive or it would have
> to be disabled there.

I think, if there is any such implication, we can probably have the
option of disable it

> I think my primary issue is that philosophically/architecturally I am
> of
> the opinion that a wal record should make sense of it's own without
> depending on heap data. And this patch looses that.

Is the main worry about corruption getting propagated?

With Regards,
Amit Kapila.

On 2013-07-23 18:59:11 +0530, Amit Kapila wrote:
> > * I'd be very surprised if this doesn't make WAL replay of update heavy
> > workloads slower by at least factor of 2.
>
> Yes, if you just consider the cost of replay, but it involves other
> operations as well
> like for standby case transfer of WAL, Write of WAL, Read from WAL and
> then apply.
> So among them most operation's will be benefited from reduced WAL size,
> except apply where you need to decode.

I still think it's rather unlikely that they offset those. I've seen wal
replay be a major bottleneck more than once...

> > * It makes data recovery from WAL *noticeably* harder since data
> > corruption now is carried forwards and you need the old data to
> > decode
> > new data
>
> This is one of the reasons why this optimization is done only when the
> new row goes in same page.

That doesn't help all that much. It somewhat eases recovering data if
full_page_writes are on, but it's realy hard to stitch together all
changes if the corruption occured within a 1h long checkpoint...

> > * It makes changeset extraction either more expensive or it would have
> > to be disabled there.

> I think, if there is any such implication, we can probably have the
> option of disable it

That can just be done on wal_level = logical, that's not the
problem. It's certainly not with precedence that we have wal_level
dependent optimizations.

> > I think my primary issue is that philosophically/architecturally I am
> > of
> > the opinion that a wal record should make sense of it's own without
> > depending on heap data. And this patch looses that.
>
> Is the main worry about corruption getting propagated?

Not really. It "feels" wrong to me architecturally. That's subjective, I
know.

Greetings,

Andres Freund

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

On Tuesday, July 23, 2013 7:06 PM Andres Freund wrote:
> On 2013-07-23 18:59:11 +0530, Amit Kapila wrote:
> > > * I'd be very surprised if this doesn't make WAL replay of update
> heavy
> > > workloads slower by at least factor of 2.
> >
> > Yes, if you just consider the cost of replay, but it involves
> other
> > operations as well
> > like for standby case transfer of WAL, Write of WAL, Read from
> WAL and
> > then apply.
> > So among them most operation's will be benefited from reduced WAL
> size,
> > except apply where you need to decode.
>
> I still think it's rather unlikely that they offset those. I've seen
> wal
> replay be a major bottleneck more than once...
>
> > > * It makes data recovery from WAL *noticeably* harder since data
> > > corruption now is carried forwards and you need the old data to
> > > decode
> > > new data
> >
> > This is one of the reasons why this optimization is done only when
> the
> > new row goes in same page.
>
> That doesn't help all that much. It somewhat eases recovering data if
> full_page_writes are on, but it's realy hard to stitch together all
> changes if the corruption occured within a 1h long checkpoint...

I think once a record is corrupted on page, user has to reconstruct that
page, it might be difficult
to just reconstruct a record and this optimization will not carry forward
any corruption from one to another
Page.

> > > * It makes changeset extraction either more expensive or it would
> have
> > > to be disabled there.
>
> > I think, if there is any such implication, we can probably have
> the
> > option of disable it
>
> That can just be done on wal_level = logical, that's not the
> problem. It's certainly not with precedence that we have wal_level
> dependent optimizations.

With Regards,
Amit Kapila.

On 23 July 2013 17:35 Amit Kapila wrote:
>On Tuesday, July 23, 2013 12:02 AM Greg Smith wrote:
>> The v3 patch applies perfectly here now. Attached is a spreadsheet
>> with test results from two platforms, a Mac laptop and a Linux server.
>> I used systems with high disk speed because that seemed like a worst
>> case for this improvement. The actual improvement for shrinking WAL
>> should be even better on a system with slower disks.

>You are absolutely right.
>To mimic it on our system, by configuring RAMFS for database, it shows similar results.

>> Is possible to add a setting here that disables the feature altogether?

>Yes, it can be done in below 2 ways:
>1. Provide a new configuration parameter (wal_update_compression) to turn on/off this feature.
>2. At table level user can be given option to configure

>The main benefit of this patch is to reduce WAL for improving time in I/O, But I think for faster I/O systems, the calculation to reduce WAL has overhead.
>I will check how to optimize that calculation, but I think this feature should be consider with configuration knob as it can improve many cases.

I tried to improve the performance of this feature on faster I/O systems where the calculation to reduce the WAL is an overhead, but resulted no success.
But this optimization is beneficial for a systems where the I/O is a bottleneck. To support those use cases I have added a configuration parameter "wal_update_optimization"
which is off by default. User can enable/disable this optimization for update operations based on its need. During replay of WAL record it can be identified easily as
it is an encode wal tuple or not by checking the flags.

Please let me know your suggestions on the same.

Regards,
Hari babu.

On Mon, Jul 22, 2013 at 2:31 PM, Greg Smith <greg(at)2ndquadrant(dot)com> wrote:
> On the Mac, the only case that seems to have a slowdown now is "hundred tiny
> fields, half nulled". It would be nice to understand just what is going on
> with that one. I got some ugly results in "two short fields, no change"
> too, along with a couple of other weird results, but I think those were
> testing procedure issues that can be ignored. The pgbench throttle work I
> did recently highlights that I can't really make a Mac quiet/consistent for
> benchmarking very well. Note that I ran all of the Mac tests with
> assertions on, to try and catch platform specific bugs. The Linux ones used
> the default build parameters.

Amit has been asking me to look at this patch for a while, so I
finally did. While I agree that it would be nice to get the CPU
overhead down low enough that we can turn this on by default and
forget about it, I'm not convinced that it's without value even if we
can't. Fundamentally, this patch trades away some CPU in exchanged
for decrease I/O. The testing thus far is all about whether the CPU
overhead can be made trivial, which is a good question to ask, because
if the answer is yes, then rather than trading something for something
else, we just get something for free. Win! But even if that doesn't
pan out, I think the fallback position should not be "OK, well, if we
can't get decreased I/O for free then forget it" but rather "OK, if we
can't get decreased I/O for free then let's get decreased I/O in
exchange for increased CPU usage".

I spent a little time running the tests from Heikki's script under
perf. On all three "two short fields" tests and also on the "ten tiny
fields, all changed" test, we spend about 1% of the CPU time in
pglz_delta_encode. I don't see any evidence that it's actually
compressing anything at all; it appears to be falling out where we
test the input length against the strategy, presumably because the
default strategy (which we largely copy here) doesn't try to compress
input data of less than 32 bytes. Given that this code isn't
actually compressing anything in these cases, I'm a bit confused by
Greg's report of substantial gains on "ten tiny fields, all changed"
test; how can we win if we're not compressing?

I studied the "hundred tiny fields, half nulled" test case in some
detail. Some thoughts:

- There is a comment "TODO: It would be nice to behave like the
history and the source strings were concatenated, so that you could
compress using the new data, too." If we're not already doing that,
then how are we managing to compress WAL by more than one-quarter in
the "hundred tiny fields, all changed" case? It looks to me like the
patch IS doing that, and I'm not sure it's a good idea, especially
because it's using pglz_hist_add_no_recycle rather than pglz_add_hist:
we verify that hlen + slen < 2 * PGLZ_HISTORY_SIZE but that doesn't
seem good enough. On the "hundred tiny fields, half nulled" test case,
removing that line reduces compression somewhat but also saves on CPU
cycles.

- pglz_find_match() is happy to walk all the way down even a really,
really long bucket chain. It has some code that reduces good_match
each time through, but it fails to produce a non-zero decrement once
good_match * good_drop < 100. So if we're searching an enormously
deep bucket many times in a row, and there are actually no matches,
we'll go flying down the whole linked list every time. I tried
mandating a minimum decrease of 1 and didn't observe that it made any
difference in the run time of this test case, but it still seems odd.
For the record, it's not new behavior with this patch; pglz_compress()
has the same issue as things stand today. I wonder if we ought to
decrease the good match length by a constant rather than a percentage
at each step.

- pglz_delta_encode() seems to spend about 50% of its CPU time loading
up the history data. It would be nice to find a way to reduce that
effort. I thought about maybe only making a history entry for, say,
every fourth input position rather than every one, but a quick test
seems to suggest that's a big fail, probably because it's too easy to
skip over the position where we would have made "the right" match via
some short match. But maybe there's some more sophisticated strategy
here that would work better. For example, see:

http://en.wikipedia.org/wiki/Rabin_fingerprint

The basic idea is that you use a rolling hash function to divide up
the history data into chunks of a given average size. So we scan the
history data, compute a rolling hash value at each point, and each
time the bottom N bits are zero, we consider that to be the end of a
chunk. We enter all the chunks into a hash table. The chunk size
will vary, but on the average, given a reasonably well-behaved rolling
hash function (the pglz one probably doesn't qualify) it'll happen
every 2^N bytes, so perhaps for this purpose we'd choose N to be
between 3 and 5. Then, we scan the input we want to compress and
divide it into chunks in the same way. Chunks that don't exist in the
history data get copied to the output, while those that do get
replaced with a reference to their position in the history data.

I'm not 100% certain that something like this would be better than
trying to leverage the pglz machinery, but I think it might be worth
trying. One possible advantage is that you make many fewer hash-table
entries, which reduces both the cost of setting up the hash table and
the cost of probing it; another is that if you find a hit in the hash
table, you needn't search any further: you are done; this is related
to the point that, for the most part, the processing is
chunk-at-a-time rather than character-at-a-time, which might be more
efficient. On the other hand, the compression ratio might stink, or
it might suck for some other reason: I just don't know.

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

On Tue, Nov 26, 2013 at 8:25 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Mon, Jul 22, 2013 at 2:31 PM, Greg Smith <greg(at)2ndquadrant(dot)com> wrote:
>
> I spent a little time running the tests from Heikki's script under
> perf. On all three "two short fields" tests and also on the "ten tiny
> fields, all changed" test, we spend about 1% of the CPU time in
> pglz_delta_encode. I don't see any evidence that it's actually
> compressing anything at all; it appears to be falling out where we
> test the input length against the strategy, presumably because the
> default strategy (which we largely copy here) doesn't try to compress
> input data of less than 32 bytes. Given that this code isn't
> actually compressing anything in these cases, I'm a bit confused by
> Greg's report of substantial gains on "ten tiny fields, all changed"
> test; how can we win if we're not compressing?

I think it is mainly due to variation of test data on Mac, if we see
the results of Linux, there is not much difference in results.
Also the results posted by Heikki or by me at below links doesn't show
such inconsistency for "ten tiny fields, all changed" case.

http://www.postgresql.org/message-id/51366323.8070606@vmware.com
http://www.postgresql.org/message-id/001f01ce1c14$d3af0770$7b0d1650$@kapila@huawei.com
(Refer test_readings.txt)

> I studied the "hundred tiny fields, half nulled" test case in some
> detail. Some thoughts:
>
> - There is a comment "TODO: It would be nice to behave like the
> history and the source strings were concatenated, so that you could
> compress using the new data, too." If we're not already doing that,
> then how are we managing to compress WAL by more than one-quarter in
> the "hundred tiny fields, all changed" case?

Algorithm is not doing concatenation of history and source strings,
the hash table is formed just with history data and then later
if match is not found then it is added to history, so this can be the
reason for the above result.

> It looks to me like the
> patch IS doing that, and I'm not sure it's a good idea, especially
> because it's using pglz_hist_add_no_recycle rather than pglz_add_hist:
> we verify that hlen + slen < 2 * PGLZ_HISTORY_SIZE but that doesn't
> seem good enough. On the "hundred tiny fields, half nulled" test case,
> removing that line reduces compression somewhat but also saves on CPU
> cycles.

> - pglz_find_match() is happy to walk all the way down even a really,
> really long bucket chain. It has some code that reduces good_match
> each time through, but it fails to produce a non-zero decrement once
> good_match * good_drop < 100. So if we're searching an enormously
> deep bucket many times in a row, and there are actually no matches,
> we'll go flying down the whole linked list every time. I tried
> mandating a minimum decrease of 1 and didn't observe that it made any
> difference in the run time of this test case, but it still seems odd.
> For the record, it's not new behavior with this patch; pglz_compress()
> has the same issue as things stand today. I wonder if we ought to
> decrease the good match length by a constant rather than a percentage
> at each step.
>
> - pglz_delta_encode() seems to spend about 50% of its CPU time loading
> up the history data. It would be nice to find a way to reduce that
> effort. I thought about maybe only making a history entry for, say,
> every fourth input position rather than every one, but a quick test
> seems to suggest that's a big fail, probably because it's too easy to
> skip over the position where we would have made "the right" match via
> some short match. But maybe there's some more sophisticated strategy
> here that would work better. For example, see:
>
> http://en.wikipedia.org/wiki/Rabin_fingerprint
>
> The basic idea is that you use a rolling hash function to divide up
> the history data into chunks of a given average size. So we scan the
> history data, compute a rolling hash value at each point, and each
> time the bottom N bits are zero, we consider that to be the end of a
> chunk. We enter all the chunks into a hash table. The chunk size
> will vary, but on the average, given a reasonably well-behaved rolling
> hash function (the pglz one probably doesn't qualify) it'll happen
> every 2^N bytes, so perhaps for this purpose we'd choose N to be
> between 3 and 5. Then, we scan the input we want to compress and
> divide it into chunks in the same way. Chunks that don't exist in the
> history data get copied to the output, while those that do get
> replaced with a reference to their position in the history data.
>
> I'm not 100% certain that something like this would be better than
> trying to leverage the pglz machinery, but I think it might be worth
> trying. One possible advantage is that you make many fewer hash-table
> entries, which reduces both the cost of setting up the hash table and
> the cost of probing it; another is that if you find a hit in the hash
> table, you needn't search any further: you are done; this is related
> to the point that, for the most part, the processing is
> chunk-at-a-time rather than character-at-a-time, which might be more
> efficient. On the other hand, the compression ratio might stink, or
> it might suck for some other reason: I just don't know.

I think this idea looks better than current and it will definately
improve some of the cases, but not sure we can win in all cases.
We have tried one of the similar idea (reduce size of hash and
eventually comparision) by adding every 10 bytes to the history
lookup table rather than every byte. It improved most cases but not
all cases ("hundred tiny fields, all changed",
"hundred tiny fields, half changed" test were still slow).
Patch and results are at link (refer approach-1):
http://www.postgresql.org/message-id/001f01ce1c14$d3af0770$7b0d1650$@kapila@huawei.com

Now the tough question is what are the possible options for this patch
and which one to pick:
a. optimize encoding technique, so that it can improve results in most
cases even if not all.
b. have a table level option or guc to enable/disable WAL compression.
c. use some heuristics to check if chances of compression are good,
then only perform compression.
1. apply this optimization for tuple size > 128 and < 2000
2. apply this optimization if number of modified columns are less
than 25% (some threshold number) of total columns.
I think we can get modified columns from target entry and use
it if triggers haven't changed that tuple. I remember
earlier there were concerns that this value can't be trusted
completely, but I think using it as a heuristic is not a
problem, even if this number is not right in some cases.
d. forget about this optimization and reject the patch.

I think by doing option 'b' and 'c' together can make this
optimization usable in cases where it is actually useful.

Opinions/Suggestions?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Wed, Nov 27, 2013 at 12:56 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> - There is a comment "TODO: It would be nice to behave like the
>> history and the source strings were concatenated, so that you could
>> compress using the new data, too." If we're not already doing that,
>> then how are we managing to compress WAL by more than one-quarter in
>> the "hundred tiny fields, all changed" case?
>
> Algorithm is not doing concatenation of history and source strings,
> the hash table is formed just with history data and then later
> if match is not found then it is added to history, so this can be the
> reason for the above result.

From the compressor's point of view, that's pretty much equivalent to
behaving as if those strings were concatenated.

The point is that there's a difference between using the old tuple's
history entries to compress the new tuple and using the new tuple's
own history to compress it. The former is delta-compression, which is
what we're supposedly doing here. The later is just plain
compression. That doesn't *necessarily* make it a bad idea, but they
are clearly two different things.

>> The basic idea is that you use a rolling hash function to divide up
>> the history data into chunks of a given average size. So we scan the
>> history data, compute a rolling hash value at each point, and each
>> time the bottom N bits are zero, we consider that to be the end of a
>> chunk. We enter all the chunks into a hash table. The chunk size
>> will vary, but on the average, given a reasonably well-behaved rolling
>> hash function (the pglz one probably doesn't qualify) it'll happen
>> every 2^N bytes, so perhaps for this purpose we'd choose N to be
>> between 3 and 5. Then, we scan the input we want to compress and
>> divide it into chunks in the same way. Chunks that don't exist in the
>> history data get copied to the output, while those that do get
>> replaced with a reference to their position in the history data.
>
> I think this idea looks better than current and it will definately
> improve some of the cases, but not sure we can win in all cases.
> We have tried one of the similar idea (reduce size of hash and
> eventually comparision) by adding every 10 bytes to the history
> lookup table rather than every byte. It improved most cases but not
> all cases ("hundred tiny fields, all changed",
> "hundred tiny fields, half changed" test were still slow).
> Patch and results are at link (refer approach-1):
> http://www.postgresql.org/message-id/001f01ce1c14$d3af0770$7b0d1650$@kapila@huawei.com

What you did there will, I think, tend to miss a lot of compression
opportunities. Suppose for example that the old tuple is
ABCDEFGHIJKLMNOP and the new tuple is xABCDEFGHIJKLMNOP. After
copying one literal byte we'll proceed to copy 9 more, missing the
fact that there was a long match available after the first byte. The
advantage of the fingerprinting technique is that it's supposed to be
resistant to that sort of thing.

> Now the tough question is what are the possible options for this patch
> and which one to pick:
> a. optimize encoding technique, so that it can improve results in most
> cases even if not all.
> b. have a table level option or guc to enable/disable WAL compression.
> c. use some heuristics to check if chances of compression are good,
> then only perform compression.
> 1. apply this optimization for tuple size > 128 and < 2000
> 2. apply this optimization if number of modified columns are less
> than 25% (some threshold number) of total columns.
> I think we can get modified columns from target entry and use
> it if triggers haven't changed that tuple. I remember
> earlier there were concerns that this value can't be trusted
> completely, but I think using it as a heuristic is not a
> problem, even if this number is not right in some cases.
> d. forget about this optimization and reject the patch.
> I think by doing option 'b' and 'c' together can make this
> optimization usable in cases where it is actually useful.

I agree that we probably want to do (b), and I suspect we want both a
GUC and a reloption, assuming that can be done relatively cleanly.

However, I think we should explore (a) more before we explore (c). I
think there's a good chance that we can reduce the CPU overhead of
this enough to feel comfortable having it enabled by default. If we
proceed with heuristics as in approach (c), I don't think that's the
end of the world, but I think there will be more corner cases where we
lose and have to fiddle things manually.

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

On Wed, Nov 27, 2013 at 7:35 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Wed, Nov 27, 2013 at 12:56 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>>> The basic idea is that you use a rolling hash function to divide up
>>> the history data into chunks of a given average size. So we scan the
>>> history data, compute a rolling hash value at each point, and each
>>> time the bottom N bits are zero, we consider that to be the end of a
>>> chunk. We enter all the chunks into a hash table. The chunk size
>>> will vary, but on the average, given a reasonably well-behaved rolling
>>> hash function (the pglz one probably doesn't qualify) it'll happen
>>> every 2^N bytes, so perhaps for this purpose we'd choose N to be
>>> between 3 and 5. Then, we scan the input we want to compress and
>>> divide it into chunks in the same way. Chunks that don't exist in the
>>> history data get copied to the output, while those that do get
>>> replaced with a reference to their position in the history data.
>>
>> I think this idea looks better than current and it will definately
>> improve some of the cases, but not sure we can win in all cases.
>> We have tried one of the similar idea (reduce size of hash and
>> eventually comparision) by adding every 10 bytes to the history
>> lookup table rather than every byte. It improved most cases but not
>> all cases ("hundred tiny fields, all changed",
>> "hundred tiny fields, half changed" test were still slow).
>> Patch and results are at link (refer approach-1):
>> http://www.postgresql.org/message-id/001f01ce1c14$d3af0770$7b0d1650$@kapila@huawei.com
>
> What you did there will, I think, tend to miss a lot of compression
> opportunities. Suppose for example that the old tuple is
> ABCDEFGHIJKLMNOP and the new tuple is xABCDEFGHIJKLMNOP. After
> copying one literal byte we'll proceed to copy 9 more, missing the
> fact that there was a long match available after the first byte.

That is right, but one idea to try that out was to see if we can
reduce CPU usage at cost of compression,
but we found that it didn't completely eliminate that problem.

> The
> advantage of the fingerprinting technique is that it's supposed to be
> resistant to that sort of thing.

Okay, one question arise here is that can it be better in terms of CPU
usage as compare to when
we have used hash function for every 10th byte, if you have a feeling
that it can improve situation,
I can try a prototype implementation of same to check the results.

>> Now the tough question is what are the possible options for this patch
>> and which one to pick:
>> a. optimize encoding technique, so that it can improve results in most
>> cases even if not all.
>> b. have a table level option or guc to enable/disable WAL compression.
>> c. use some heuristics to check if chances of compression are good,
>> then only perform compression.
>> 1. apply this optimization for tuple size > 128 and < 2000
>> 2. apply this optimization if number of modified columns are less
>> than 25% (some threshold number) of total columns.
>> I think we can get modified columns from target entry and use
>> it if triggers haven't changed that tuple. I remember
>> earlier there were concerns that this value can't be trusted
>> completely, but I think using it as a heuristic is not a
>> problem, even if this number is not right in some cases.
>> d. forget about this optimization and reject the patch.
>> I think by doing option 'b' and 'c' together can make this
>> optimization usable in cases where it is actually useful.
>
> I agree that we probably want to do (b), and I suspect we want both a
> GUC and a reloption, assuming that can be done relatively cleanly.
>
> However, I think we should explore (a) more before we explore (c).

Sure, but to explore (a), the scope is bit bigger. We have below
options to explore (a):
1. try to optimize existing algorithm as used in patch, which we have
tried but ofcourse we can spend some more time to see if anything more
can be tried out.
2. try fingerprint technique as suggested by you above.
3. try some other standard methods like vcdiff, lz4 etc.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Wed, Nov 27, 2013 at 9:31 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Sure, but to explore (a), the scope is bit bigger. We have below
> options to explore (a):
> 1. try to optimize existing algorithm as used in patch, which we have
> tried but ofcourse we can spend some more time to see if anything more
> can be tried out.
> 2. try fingerprint technique as suggested by you above.
> 3. try some other standard methods like vcdiff, lz4 etc.

Well, obviously, I'm hot on idea #2 and think that would be worth
spending some time on. If we can optimize the algorithm used in the
patch some more (option #1), that would be fine, too, but the code
looks pretty tight to me, so I'm not sure how successful that's likely
to be. But if you have an idea, sure.

As to #3, I took a look at lz4 and snappy but neither seems to have an
API for delta compression. vcdiff is a commonly-used output for delta
compression but doesn't directly address the question of what
algorithm to use to find matches between the old and new input; and I
suspect that when you go searching for algorithms to do that
efficiently, it's going to bring you right back to #2.

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

On 29 November 2013 03:05 Robert Haas wrote:
> On Wed, Nov 27, 2013 at 9:31 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
> wrote:
> > Sure, but to explore (a), the scope is bit bigger. We have below
> > options to explore (a):
> > 1. try to optimize existing algorithm as used in patch, which we have
> > tried but ofcourse we can spend some more time to see if anything
> more
> > can be tried out.
> > 2. try fingerprint technique as suggested by you above.
> > 3. try some other standard methods like vcdiff, lz4 etc.
>
> Well, obviously, I'm hot on idea #2 and think that would be worth
> spending some time on. If we can optimize the algorithm used in the
> patch some more (option #1), that would be fine, too, but the code
> looks pretty tight to me, so I'm not sure how successful that's likely
> to be. But if you have an idea, sure.

I tried modifying the existing patch to support the dynamic rollup as follows.
For every 32 bytes mismatch between the old and new tuple and it resets back whenever it found a match.

1. pglz-with-micro-optimization-compress-using-newdata-5:

Adds all old tuple data to history and then check for the match from new tuple.
For every 32 bytes mismatch, it checks for the match for 2 bytes once. Like this
It repeats until it found a match or end of data.

2. pglz-with-micro-optimization-compress-using-newdata_snappy_hash-1:

Adds only first byte of old tuple data to the history and then check for the match
From new tuple. If any match found, then next unmatched byte from old tuple is added
To the history and repeats the process.

If no match founds then adds the next byte of the old tuple history followed by the
Unmatched byte from new tuple data to the history.

In this case the performance is good, but if there is any forward references in the
New data with old data then it will not compress the data.

Eg- old data - 12345 abcdefgh
New data - abcdefgh 56789

The updated patches and performance data is attached in the mail.
Please let me know your suggestions.

Regards,
Hari babu.

On Mon, Dec 2, 2013 at 7:40 PM, Haribabu kommi
<haribabu(dot)kommi(at)huawei(dot)com> wrote:
> On 29 November 2013 03:05 Robert Haas wrote:
>> On Wed, Nov 27, 2013 at 9:31 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com>
>> wrote:
>
> I tried modifying the existing patch to support the dynamic rollup as follows.
> For every 32 bytes mismatch between the old and new tuple and it resets back whenever it found a match.
>
> 1. pglz-with-micro-optimization-compress-using-newdata-5:
>
> Adds all old tuple data to history and then check for the match from new tuple.
> For every 32 bytes mismatch, it checks for the match for 2 bytes once. Like this
> It repeats until it found a match or end of data.
>
> 2. pglz-with-micro-optimization-compress-using-newdata_snappy_hash-1:
>
> Adds only first byte of old tuple data to the history and then check for the match
> From new tuple. If any match found, then next unmatched byte from old tuple is added
> To the history and repeats the process.
>
> If no match founds then adds the next byte of the old tuple history followed by the
> Unmatched byte from new tuple data to the history.
>
> In this case the performance is good, but if there is any forward references in the
> New data with old data then it will not compress the data.

The performance data has still same problem that is on fast disks
(tempfs data) it is low.
I am already doing chunk-wise implementation to see if it can improve
the situation, please wait
and then we can decide what is the best way to proceed.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Nov 29, 2013 at 3:05 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Wed, Nov 27, 2013 at 9:31 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> Sure, but to explore (a), the scope is bit bigger. We have below
>> options to explore (a):
>> 1. try to optimize existing algorithm as used in patch, which we have
>> tried but ofcourse we can spend some more time to see if anything more
>> can be tried out.
>> 2. try fingerprint technique as suggested by you above.
>> 3. try some other standard methods like vcdiff, lz4 etc.
>
> Well, obviously, I'm hot on idea #2 and think that would be worth
> spending some time on. If we can optimize the algorithm used in the
> patch some more (option #1), that would be fine, too, but the code
> looks pretty tight to me, so I'm not sure how successful that's likely
> to be. But if you have an idea, sure.

I have been experimenting chunk wise delta encoding (by using
technique similar to rabin fingerprint method) from last few days and
here are results of my investigation.

Performance Data
----------------------------
Non-default settings:
autovacuum =off
checkpoint_segments =128
checkpoint_timeout = 10min

unpatched

testname | wal_generated |
duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 1054921328 | 25.5855557918549
hundred tiny fields, all changed | 634483328 | 20.8992719650269
hundred tiny fields, half changed | 635948640 | 19.8670389652252
hundred tiny fields, half nulled | 571388552 |
18.9413228034973

lz-delta-encoding

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 662984384 | 21.7335519790649
hundred tiny fields, all changed | 633944320 | 24.1207830905914
hundred tiny fields, half changed | 633944344 | 24.4657719135284
hundred tiny fields, half nulled | 492200208 |
22.0337791442871

rabin-delta-encoding

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 662235752 | 20.1823079586029
hundred tiny fields, all changed | 633950080 | 22.0473308563232
hundred tiny fields, half changed | 633950880 | 21.8351459503174
hundred tiny fields, half nulled | 508943072 |
20.9554698467255

Results Summarization
-------------------------------------
1. With Chunkwise approach, WAL reduction is almost same as with LZ
barring half nulled case which can be improved.
2. With Chunkwise approach, CPU usage is reduced to 50% in most cases
where there is less or no compression,
still there is 5~10% overhead for cases where data is not
compressible. I think there will certainly a small
overhead of forming hash table and scanning to conclude data is
non-compressible.
3. I have not tested other tests which will anyway return from top of
encoding function due to tuple length less than 32.

Main reasons of improvement
---------------------------------------------
1. lesser hash entries for old tuple and lesser calculations during
compressing of new tuple.
2. memset for data structure related to hash table for lesser size
3. Don't copy into output buffer untill we found match.

Further Actions
------------------------
1. Need to decide if this reduction in CPU usage is acceptable, do we
need enable/disable flag at table level.
2. We can do further micro-optimisations in chunk wise approach like
hash function improvement.
3. Some code improvements are pending like for cases where data to be
compressed is non-contiguous.

Attached files
---------------------
1. pgrb_delta_encoding_v1 - In heaptuple.c, there is a parameter
rabin_fingerprint_comp, set it to true for
chunkwise delta encoding and set it to false for lz encoding. By
default it is true. I wanted to provide
better way to enable both modes and tried as well but end up with this way.
2. wal-update-testsuite.sh - test script developed by Heikki to test this patch.

Note -
a. Performance is data is taken on my laptop, needs to be tested on
some better m/c
b. Attached Patch is just a prototype of chunkwise concept, code needs
to be improved and decode
handling/test is pending.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On 05 December 2013 21:16 Amit Kapila wrote:
> Note -
> a. Performance is data is taken on my laptop, needs to be tested on
> some better m/c b. Attached Patch is just a prototype of chunkwise
> concept, code needs to be improved and decode
> handling/test is pending.

I ran the performance test on linux machine and attached the results in the mail.

Regards,
Hari babu.

On Fri, Dec 6, 2013 at 12:10 PM, Haribabu kommi
<haribabu(dot)kommi(at)huawei(dot)com> wrote:
> On 05 December 2013 21:16 Amit Kapila wrote:
>> Note -
>> a. Performance is data is taken on my laptop, needs to be tested on
>> some better m/c b. Attached Patch is just a prototype of chunkwise
>> concept, code needs to be improved and decode
>> handling/test is pending.
>
> I ran the performance test on linux machine and attached the results in the mail.

This test doesn't make much sense for comparison as in chunkwise delta
encoding, I am not doing compression using new tuple
and the reason is that I want to check how good/bad it is as compare
to LZ approach for cases when data is non-compressible.
So could you please try to take readings by using patch
pgrb_delta_encoding_v1 attached in my previous mail.

For LZ delta encoding-
pgrb_delta_encoding_v1 - In heaptuple.c, there is a parameter
rabin_fingerprint_comp, set it to false, compile the code and take
readings.
This will do LZ compression.

For chunk wise delta encoding - In heaptuple.c, there is a parameter
rabin_fingerprint_comp, set it to true, compile the code and take
readings
This will operate chunk wise.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On 06 December 2013 12:29 Amit Kapila wrote:
> On Fri, Dec 6, 2013 at 12:10 PM, Haribabu kommi
> <haribabu(dot)kommi(at)huawei(dot)com> wrote:
> > On 05 December 2013 21:16 Amit Kapila wrote:
> >> Note -
> >> a. Performance is data is taken on my laptop, needs to be tested on
> >> some better m/c b. Attached Patch is just a prototype of chunkwise
> >> concept, code needs to be improved and decode
> >> handling/test is pending.
> >
> > I ran the performance test on linux machine and attached the results
> in the mail.
>
> This test doesn't make much sense for comparison as in chunkwise delta
> encoding, I am not doing compression using new tuple and the reason is
> that I want to check how good/bad it is as compare to LZ approach for
> cases when data is non-compressible.
> So could you please try to take readings by using patch
> pgrb_delta_encoding_v1 attached in my previous mail.
>
> For LZ delta encoding-
> pgrb_delta_encoding_v1 - In heaptuple.c, there is a parameter
> rabin_fingerprint_comp, set it to false, compile the code and take
> readings.
> This will do LZ compression.
>
> For chunk wise delta encoding - In heaptuple.c, there is a parameter
> rabin_fingerprint_comp, set it to true, compile the code and take
> readings
> This will operate chunk
> wise.

I ran the performance test on above patches including another patch which
Does snappy hash instead of normal hash in LZ algorithm. The performance
Readings and patch with snappy hash not including new data in compression
are attached in the mail.

The chunk wise approach is giving good performance in most of the scenarios.

Regards,
Hari babu.

On Fri, Dec 6, 2013 at 3:39 PM, Haribabu kommi
<haribabu(dot)kommi(at)huawei(dot)com> wrote:
> On 06 December 2013 12:29 Amit Kapila wrote:
>> >> Note -
>> >> a. Performance is data is taken on my laptop, needs to be tested on
>> >> some better m/c b. Attached Patch is just a prototype of chunkwise
>> >> concept, code needs to be improved and decode
>> >> handling/test is pending.
>> >
>> > I ran the performance test on linux machine and attached the results
>> in the mail.
>>
>
> I ran the performance test on above patches including another patch which
> Does snappy hash instead of normal hash in LZ algorithm. The performance
> Readings and patch with snappy hash not including new data in compression
> are attached in the mail.

Thanks for taking the data.

> The chunk wise approach is giving good performance in most of the scenarios.

Agreed, summarization of data for LZ/Chunkwise encoding especially for
non-compressible (hundred tiny fields, all changed/half changed) or less
compressible data (hundred tiny fields, half nulled) w.r.t CPU
usage is as below:

a. For hard disk, there is an overhead of 7~16% with LZ delta encoding
and there is an overhead of 5~8% with Chunk wise encoding.

b. For Tempfs (which means operate on RAM as disk), there is an
overhead of 19~26%
with LZ delta encoding and there is an overhead of 9~18% with
Chunk wise encoding.

There might be some variation of data (in your last mail the overhead
for chunkwise method for Tempfs was < 12%),
but in general the data suggests that chunk wise encoding has less
overhead than LZ encoding for non-compressible data
and for others it is better or equal.

Now, I think we have below options for this patch:
a. If the performance overhead for worst case is acceptable (we can
try to reduce some more, but don't think it will be something
drastic),
then this can be done without any flag/option.
b. Have it with table level option to enable/disable WAL compression
c. Drop this patch, as for worst cases there is some performance overhead.
d. Go back and work more on it, if there is any further suggestions
for improvement.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

This patch fails the regression tests; see attachment.

On Thu, Dec 12, 2013 at 3:43 AM, Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
> This patch fails the regression tests; see attachment.

Thanks for reporting the diffs. The reason for failures is that
still decoding for tuple is not done as mentioned in Notes section in
mail
(http://www.postgresql.org/message-id/CAA4eK1JeUbY16uwrDA2TaBkk+rLRL3Giyyqy1mVh_6CThmDR8w@mail.gmail.com)

However, to keep the sanity of patch, I will do that and post an
updated patch, but I think the main idea behind new approach at this
point is to get feedback on if such an optimization is acceptable
for worst case scenarios and if not whether we can get this done
with table level or GUC option.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Thu, Dec 12, 2013 at 12:27 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Thu, Dec 12, 2013 at 3:43 AM, Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
>> This patch fails the regression tests; see attachment.
>
> Thanks for reporting the diffs. The reason for failures is that
> still decoding for tuple is not done as mentioned in Notes section in
> mail
> (http://www.postgresql.org/message-id/CAA4eK1JeUbY16uwrDA2TaBkk+rLRL3Giyyqy1mVh_6CThmDR8w@mail.gmail.com)
>
> However, to keep the sanity of patch, I will do that and post an
> updated patch, but I think the main idea behind new approach at this
> point is to get feedback on if such an optimization is acceptable
> for worst case scenarios and if not whether we can get this done
> with table level or GUC option.

I don't understand why lack of decoding support should cause
regression tests to fail. I thought decoding was only being done
during WAL replay, a case not exercised by the regression tests.

A few other comments:

+#define PGRB_HKEY_PRIME 11 /* prime number used for
rolling hash */
+#define PGRB_HKEY_SQUARE_PRIME 11 * 11 /* prime number
used for rolling hash */
+#define PGRB_HKEY_CUBE_PRIME 11 * 11 * 11 /* prime
number used for rolling hash */

11 * 11 can't accurately be described as a prime number. Nor can 11 *
11 * 11. Please adjust the comment. Also, why 11?

It doesn't appear that pglz_hist_idx is changed except for whitespace;
please revert that hunk.

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

On Thu, Dec 12, 2013 at 8:53 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Thu, Dec 12, 2013 at 12:27 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> On Thu, Dec 12, 2013 at 3:43 AM, Peter Eisentraut <peter_e(at)gmx(dot)net> wrote:
>>> This patch fails the regression tests; see attachment.
>>
>> However, to keep the sanity of patch, I will do that and post an
>> updated patch, but I think the main idea behind new approach at this
>> point is to get feedback on if such an optimization is acceptable
>> for worst case scenarios and if not whether we can get this done
>> with table level or GUC option.
>
> I don't understand why lack of decoding support should cause
> regression tests to fail. I thought decoding was only being done
> during WAL replay, a case not exercised by the regression tests.

I had mentioned decoding, as the message in regression failures can come from
decompress/decode functions. Today, I had debugged the regression
failures and
found that they are coming from pglz_decompress() function and the
reason is that
optimizations done in pglz_find_match() to reduce the length of
'maxlen' has problem
due to which compression of data was not happening properly.
I have corrected the calculation for 'maxlen' and now compression
is happening properly
and regression tests are passed.
This problem was observed previously also and we have corrected in
one of the versions
of patch which I forgot to take care while preparing combined patch
of chunk-wise and byte
by byte encoding.

> A few other comments:
>
> +#define PGRB_HKEY_PRIME 11 /* prime number used for
> rolling hash */
> +#define PGRB_HKEY_SQUARE_PRIME 11 * 11 /* prime number
> used for rolling hash */
> +#define PGRB_HKEY_CUBE_PRIME 11 * 11 * 11 /* prime
> number used for rolling hash */
>
> 11 * 11 can't accurately be described as a prime number. Nor can 11 *
> 11 * 11. Please adjust the comment.

Fixed.

>Also, why 11?

I have tried with 11,31,101 to see which generates the better chunks
and I found 11 chooses better
chunks (with 31 and 101, there was almost no chunk, it was
considering whole data as one chunk).
The data I have used was the test data of the current test case
which we are using to evaluate this
patch. It contains mostly repetitive data, so might be we need to
test with other kind of data as well
to verify, if currently used number is okay.

> It doesn't appear that pglz_hist_idx is changed except for whitespace;
> please revert that hunk.

Fixed.

Thanks for review.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Dec 6, 2013 at 6:41 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Agreed, summarization of data for LZ/Chunkwise encoding especially for
> non-compressible (hundred tiny fields, all changed/half changed) or less
> compressible data (hundred tiny fields, half nulled) w.r.t CPU
> usage is as below:
>
> a. For hard disk, there is an overhead of 7~16% with LZ delta encoding
> and there is an overhead of 5~8% with Chunk wise encoding.
>
> b. For Tempfs (which means operate on RAM as disk), there is an
> overhead of 19~26%
> with LZ delta encoding and there is an overhead of 9~18% with
> Chunk wise encoding.
>
> There might be some variation of data (in your last mail the overhead
> for chunkwise method for Tempfs was < 12%),
> but in general the data suggests that chunk wise encoding has less
> overhead than LZ encoding for non-compressible data
> and for others it is better or equal.
>
> Now, I think we have below options for this patch:
> a. If the performance overhead for worst case is acceptable (we can
> try to reduce some more, but don't think it will be something
> drastic),
> then this can be done without any flag/option.
> b. Have it with table level option to enable/disable WAL compression
> c. Drop this patch, as for worst cases there is some performance overhead.
> d. Go back and work more on it, if there is any further suggestions
> for improvement.

Based on data posted previously for both approaches
(lz_delta, chunk_wise_encoding) and above options, I have improved
the last version of patch by keeping chunk wise approach and
provided a table level option to user.

Changes in this version of patch:
--------------------------------------------------
1. Implement decoding, it is almost similar to pglz_decompress as
the format to store encoded data is not changed much.

2. Provide a new reloption to specify Wal compression
for update operation on table
Create table tbl(c1 char(100)) With (compress_wal = true);

Alternative options:
a. compress_wal can take input as operation, e.g. 'insert', 'update',
b. use alternate syntax:
Create table tbl(c1 char(100)) Compress Wal For Update;
c. anything better?

3. Fixed below 2 defects in encoding:
a. In function pgrb_find_match(), if last byte of chunk matches,
it consider whole chunk as match.
b. If there is no match, it copies chunk as it is to encoded data,
while copying, it is ignoring last byte.
Due to defect fixes, data can vary, but I don't think there can be
any major change.

Points to consider
-----------------------------

1. As the current algorithm store the entry for same chunks at head of list,
it will always find last but one chunk (we don't store last 4 bytes) for
long matching string during match phase in encoding (pgrb_delta_encode).

We can improve it either by storing same chunks at end of list instead of at
head or by trying to find a good_match technique used in lz algorithm.
Finding good_match technique can have overhead in some of the cases
when there is actually no match.

2. Another optimization that we can do in pgrb_find_match(), is that
currently if
it doesn't find the first chunk (chunk got by hash index) matching, it
continues to find the match in other chunks. I am not sure if there is any
benefit to search for other chunks if first one is not matching.

3. We can move code from pg_lzcompress.c to some new file pg_rbcompress.c,
if we want to move, then we need to either duplicate some common macros
like pglz_out_tag or keep it common, but might be change the name.

4. Decide on min and max chunksize. (currently kept as 2 and 4 respectively).
The point to consider is that if we keep bigger chunk sizes, then it can
save us on CPU cycles, but less reduction in Wal, on the other side if we
keep it small it can have better reduction in Wal but consume more CPU
cycles.

5. kept an guc variable 'wal_update_compression_ratio', for test purpose, we
can remove it before commit.

7. docs needs to be updated, tab completion needs some work.

8. We can extend Alter Table to set compress option for table.

Thoughts/Suggestions?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

> 2. Provide a new reloption to specify Wal compression
> for update operation on table
> Create table tbl(c1 char(100)) With (compress_wal = true);
>
> Alternative options:
> a. compress_wal can take input as operation, e.g. 'insert', 'update',
> b. use alternate syntax:
> Create table tbl(c1 char(100)) Compress Wal For Update;
> c. anything better?

I think WITH (compress_wal = true) is pretty good. I don't understand
your point about taking the operation as input, because this only
applies to updates. But we could try to work "update" into the name
of the setting somehow, so as to be less likely to conflict with
future additions, like maybe wal_compress_update. I think the
alternate syntax you propose is clearly worse, because it would
involve adding new keywords, something we try to avoid.

The only possible enhancement I can think of here is to make the
setting an integer rather than a Boolean, defined as the minimum
acceptable compression ratio. A setting of 0 means always compress; a
setting of 100 means never compress; intermediate values define the
least acceptable ratio. But to be honest, I think that's overkill;
I'd be inclined to hard-code the default value of 25 in the patch and
make it a #define. The only real advantage of requiring a minimum 25%
compression percentage is that we can bail out on compression
three-quarters of the way through the tuple if we're getting nowhere.
That's fine for what it is, but the idea that users are going to see
much benefit from twaddling that number seems very dubious to me.

> Points to consider
> -----------------------------
>
> 1. As the current algorithm store the entry for same chunks at head of list,
> it will always find last but one chunk (we don't store last 4 bytes) for
> long matching string during match phase in encoding (pgrb_delta_encode).
>
> We can improve it either by storing same chunks at end of list instead of at
> head or by trying to find a good_match technique used in lz algorithm.
> Finding good_match technique can have overhead in some of the cases
> when there is actually no match.

I don't see what the good_match thing has to do with anything in the
Rabin algorithm. But I do think there might be a bug here, which is
that, unless I'm misinterpreting something, hp is NOT the end of the
chunk. After calling pgrb_hash_init(), we've looked at the first FOUR
bytes of the input. If we find that we have a zero hash value at that
point, shouldn't the chunk size be 4, not 1? And similarly if we find
it after sucking in one more byte, shouldn't the chunk size be 5, not
2? Right now, we're deciding where the chunks should end based on the
data in the chunk plus the following 3 bytes, and that seems wonky. I
would expect us to include all of those bytes in the chunk.

> 2. Another optimization that we can do in pgrb_find_match(), is that
> currently if
> it doesn't find the first chunk (chunk got by hash index) matching, it
> continues to find the match in other chunks. I am not sure if there is any
> benefit to search for other chunks if first one is not matching.

Well, if you took that out, I suspect it would hurt the compression
ratio. Unless the CPU savings are substantial, I'd leave it alone.

> 3. We can move code from pg_lzcompress.c to some new file pg_rbcompress.c,
> if we want to move, then we need to either duplicate some common macros
> like pglz_out_tag or keep it common, but might be change the name.

+1 for a new file.

> 4. Decide on min and max chunksize. (currently kept as 2 and 4 respectively).
> The point to consider is that if we keep bigger chunk sizes, then it can
> save us on CPU cycles, but less reduction in Wal, on the other side if we
> keep it small it can have better reduction in Wal but consume more CPU
> cycles.

Whoa. That seems way too small. Since PGRB_PATTERN_AFTER_BITS is 4,
the average length of a chunk is about 16 bytes. It makes little
sense to have the maximum chunk size be 25% of the expected chunk
length. I'd recommend making the maximum chunk length something like
4 * PGRB_CONST_NUM, and the minimum chunk length maybe something like
4.

> 5. kept an guc variable 'wal_update_compression_ratio', for test purpose, we
> can remove it before commit.

Let's remove it now.

> 7. docs needs to be updated, tab completion needs some work.

Tab completion can be skipped for now, but documentation is important.

> 8. We can extend Alter Table to set compress option for table.

I don't understand what you have in mind here.

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

On Fri, Jan 10, 2014 at 9:12 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> 2. Provide a new reloption to specify Wal compression
>> for update operation on table
>> Create table tbl(c1 char(100)) With (compress_wal = true);
>>
>> Alternative options:
>> a. compress_wal can take input as operation, e.g. 'insert', 'update',
>> b. use alternate syntax:
>> Create table tbl(c1 char(100)) Compress Wal For Update;
>> c. anything better?
>
> I think WITH (compress_wal = true) is pretty good. I don't understand
> your point about taking the operation as input, because this only
> applies to updates.

Yes, currently this applies to update, what I have in mind is that
in future if some one wants to use WAL compression for any other
operation like 'full_page_writes', then it can be easily extendible.

To be honest, I have not evaluated whether such a flag or compression
would make sense for full page writes, but I think it should be possible
while doing full page write (BkpBlock has RelFileNode) to check such a
flag if it's present.

> But we could try to work "update" into the name
> of the setting somehow, so as to be less likely to conflict with
> future additions, like maybe wal_compress_update. I think the
> alternate syntax you propose is clearly worse, because it would
> involve adding new keywords, something we try to avoid.

Yes, this would be better than current, I will include it in
next version of patch, unless there is any other better idea than
this one.

>
>> Points to consider
>> -----------------------------
>>
>> 1. As the current algorithm store the entry for same chunks at head of list,
>> it will always find last but one chunk (we don't store last 4 bytes) for
>> long matching string during match phase in encoding (pgrb_delta_encode).
>>
>> We can improve it either by storing same chunks at end of list instead of at
>> head or by trying to find a good_match technique used in lz algorithm.
>> Finding good_match technique can have overhead in some of the cases
>> when there is actually no match.
>
> I don't see what the good_match thing has to do with anything in the
> Rabin algorithm.

The case for which I have mentioned it is where most of the data is
repetitive and modified tuple is almost same.

For example

orignal tuple
aaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

modified tuple
ccaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb

Now let us see what will happen as per current algorithm

Step -1: Form the hash table (lets consider 4 byte chunks just for purpose
of explanation):
a. First chunk after first 4 a's (aaaa) with hash value 1024.
b. After that all the chunks will be 4 b's (bbbb) and will have
same hash value (lets call it H2), so will be mapped to same
bucket (let us call it 'B2' bucket) and hence form a list.
Every new chunk with same hash value is added to front of list,
so if go by this B2 has front element with hash value as H2
and location as 58 (last but 8 bytes, as we don't include last
4 bytes in our algorithm)

Step -2: Perform encoding for modified tuple by using hash table formed in
Step-1
a. First chunk after first 4 bytes (ccaa) with hash value 1056.
b. try to find match in hash table, no match, so proceed.
c. Next chunk with 4 b's and hash value H2, try to find a match,
it will find match in B2 bucket (at first element).
d. okay hash value matched, so it will try to match each byte.
if all bytes matched, it will consider chunk as matched_chunk.
e. Now if the chunk matches, then we try to match consecutive bytes
after chunk (in the hope of finding longer match), and in this
case, it will find a match of 8 bytes and consider match_len as 8.
f. it will increment the modified tuple (dp) to point to byte
next to match_len.
g. Again, it will consider next 4 b's as chunk and repeat step
c~f.

So here, what is happening is steps c~f are getting repeated, whereas if
we would have added same chunks at end of list in step 1b, then we
could have found the matching string just in one go (c~f).

The reason of adding the same chunk in head of list is that it uses same
technique as pglz_hist_add. Now in pglz, it will not have repeat steps
from c~f, as it has concept of good_match which leads to get this done in
one go.

Being said above, I am really not sure, how much real world data falls
in above category and should we try to optimize based on above example,
but yes it will save some CPU cycles in current test we are using.

>
>But I do think there might be a bug here, which is
> that, unless I'm misinterpreting something, hp is NOT the end of the
> chunk. After calling pgrb_hash_init(), we've looked at the first FOUR
> bytes of the input. If we find that we have a zero hash value at that
> point, shouldn't the chunk size be 4, not 1? And similarly if we find
> it after sucking in one more byte, shouldn't the chunk size be 5, not
> 2? Right now, we're deciding where the chunks should end based on the
> data in the chunk plus the following 3 bytes, and that seems wonky. I
> would expect us to include all of those bytes in the chunk.

It depends on how we define chunk, basically chunk size will be based
on the byte for which we consider hindex. The hindex for any byte is
calculated considering that byte and the following 3 bytes, so
after calling pgrb_hash_init(), even though we have looked at 4 bytes
but still the hindex is for first byte and thats why it consider
chunk size as 1, not 4.

Isn't it similar to how current pglz works, basically it also
uses next 4 bytes to calculate index (pglz_hist_idx) but still
does byte by byte comparison, here if we try to map to rabin's
delta encoding then always chunk size is 1.

If we follow the same logic to define chunk both for encoding and match,
will there be any problem?

I have tried to keep the implementation closer to previous lz delta
encoding, but if you see benefit in including the supporting bytes
(next 3 bytes) to define a chunk, then I can try to change it.

>> 2. Another optimization that we can do in pgrb_find_match(), is that
>> currently if
>> it doesn't find the first chunk (chunk got by hash index) matching, it
>> continues to find the match in other chunks. I am not sure if there is any
>> benefit to search for other chunks if first one is not matching.
>
> Well, if you took that out, I suspect it would hurt the compression
> ratio.

True, this is the reason I have kept it, but was not sure what kind
of scenarios it can benefit and whether such scenarios can be
more common for updates.

> Unless the CPU savings are substantial, I'd leave it alone.

Okay, lets leave it as it is.

>> 3. We can move code from pg_lzcompress.c to some new file pg_rbcompress.c,
>> if we want to move, then we need to either duplicate some common macros
>> like pglz_out_tag or keep it common, but might be change the name.
>
> +1 for a new file.

Okay, will take care of it in next version.

>
>> 4. Decide on min and max chunksize. (currently kept as 2 and 4 respectively).
>> The point to consider is that if we keep bigger chunk sizes, then it can
>> save us on CPU cycles, but less reduction in Wal, on the other side if we
>> keep it small it can have better reduction in Wal but consume more CPU
>> cycles.
>
> Whoa. That seems way too small. Since PGRB_PATTERN_AFTER_BITS is 4,
> the average length of a chunk is about 16 bytes. It makes little
> sense to have the maximum chunk size be 25% of the expected chunk
> length. I'd recommend making the maximum chunk length something like
> 4 * PGRB_CONST_NUM, and the minimum chunk length maybe something like
> 4.

Agreed, but I think for some strings (where it doesn't find special bit
pattern) it will create long chunks which can effect the reduction.
AFAIR, in the current test which we are using to evaluate the
performance of this patch has strings where it will do so, but on
the other side, this test might not be the case for real update strings.

I will make these modifications and report here if it affects the results.

>> 5. kept an guc variable 'wal_update_compression_ratio', for test purpose, we
>> can remove it before commit.
>
> Let's remove it now.

Sure, will remove in next version.

>
>> 7. docs needs to be updated, tab completion needs some work.
>
> Tab completion can be skipped for now, but documentation is important.

Agreed, left it for this version of patch, so that we can conclude on syntax
and then accordingly, I can mention it in docs.

>> 8. We can extend Alter Table to set compress option for table.
>
> I don't understand what you have in mind here.

Let us say user created table without this new option (compress_wal)
and later wants to enable it, so we can provide similar to what we
provide for other storage parameters.
Alter Table Set (compress_wal=true)

One more point to note that in the version of patch I posted, it has
default value for compress_wal as true, just for easiness of test,
we might want to change it to false for backeward compatibility.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Sat, Jan 11, 2014 at 1:08 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Yes, currently this applies to update, what I have in mind is that
> in future if some one wants to use WAL compression for any other
> operation like 'full_page_writes', then it can be easily extendible.
>
> To be honest, I have not evaluated whether such a flag or compression
> would make sense for full page writes, but I think it should be possible
> while doing full page write (BkpBlock has RelFileNode) to check such a
> flag if it's present.

Makes sense.

> The reason of adding the same chunk in head of list is that it uses same
> technique as pglz_hist_add. Now in pglz, it will not have repeat steps
> from c~f, as it has concept of good_match which leads to get this done in
> one go.
>
> Being said above, I am really not sure, how much real world data falls
> in above category and should we try to optimize based on above example,
> but yes it will save some CPU cycles in current test we are using.

In the Rabin algorithm, we shouldn't try to find a longer match. The
match should end at the chunk end, period. Otherwise, you lose the
shift-resistant property of the algorithm.

>>But I do think there might be a bug here, which is
>> that, unless I'm misinterpreting something, hp is NOT the end of the
>> chunk. After calling pgrb_hash_init(), we've looked at the first FOUR
>> bytes of the input. If we find that we have a zero hash value at that
>> point, shouldn't the chunk size be 4, not 1? And similarly if we find
>> it after sucking in one more byte, shouldn't the chunk size be 5, not
>> 2? Right now, we're deciding where the chunks should end based on the
>> data in the chunk plus the following 3 bytes, and that seems wonky. I
>> would expect us to include all of those bytes in the chunk.
>
> It depends on how we define chunk, basically chunk size will be based
> on the byte for which we consider hindex. The hindex for any byte is
> calculated considering that byte and the following 3 bytes, so
> after calling pgrb_hash_init(), even though we have looked at 4 bytes
> but still the hindex is for first byte and thats why it consider
> chunk size as 1, not 4.
>
> Isn't it similar to how current pglz works, basically it also
> uses next 4 bytes to calculate index (pglz_hist_idx) but still
> does byte by byte comparison, here if we try to map to rabin's
> delta encoding then always chunk size is 1.

I don't quite understand this. The point of the Rabin algorithm is to
split the old tuple up into chunks and then for those chunks in the
new tuple. For example, suppose the old tuple is
abcdefghijklmnopqrstuvwxyz. It might get split like this: abcdef
hijklmnopqrstuvw xyz. If any of those three chunks appear in the new
tuple, then we'll use them for compression. If not, we'll just copy
the literal bytes. If the chunks appear in the new tuple reordered or
shifted or with stuff inserted between one chunk at the next, we'll
still find them. Unless I'm confused, which is possible, what you're
doing is essentially looking at the string and spitting it in those
three places, but then recording the chunks as being three bytes
shorter than they really are. I don't see how that can be right.

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

On Tue, Jan 14, 2014 at 2:16 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Sat, Jan 11, 2014 at 1:08 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> Yes, currently this applies to update, what I have in mind is that
>> in future if some one wants to use WAL compression for any other
>> operation like 'full_page_writes', then it can be easily extendible.
>>
>> To be honest, I have not evaluated whether such a flag or compression
>> would make sense for full page writes, but I think it should be possible
>> while doing full page write (BkpBlock has RelFileNode) to check such a
>> flag if it's present.
>
> Makes sense.

So shall I change it to string instead of bool and keep the name as
compress_wal or compress_wal_for_opr?

>> The reason of adding the same chunk in head of list is that it uses same
>> technique as pglz_hist_add. Now in pglz, it will not have repeat steps
>> from c~f, as it has concept of good_match which leads to get this done in
>> one go.
>>
>> Being said above, I am really not sure, how much real world data falls
>> in above category and should we try to optimize based on above example,
>> but yes it will save some CPU cycles in current test we are using.
>
> In the Rabin algorithm, we shouldn't try to find a longer match. The
> match should end at the chunk end, period. Otherwise, you lose the
> shift-resistant property of the algorithm.

Okay, it will work well for cases when most chunks in tuple are due
due to special pattern in it, but it will loose out on CPU cycles in
cases where most of the chunks are due to maximum chunk boundary
and most part of new tuple matches with old tuple. The reason is that
if the algorithm have some such property of finding longer matches than
chunk boundaries, then it can save us on calculating hash again and
again when we try to find match in old tuple.
However I think it is better to go with rabin's algorithm instead of adding
optimizations based on our own assumptions, because it is difficult to
predict the real world tuple data.

>>
>> Isn't it similar to how current pglz works, basically it also
>> uses next 4 bytes to calculate index (pglz_hist_idx) but still
>> does byte by byte comparison, here if we try to map to rabin's
>> delta encoding then always chunk size is 1.
>
> I don't quite understand this. The point of the Rabin algorithm is to
> split the old tuple up into chunks and then for those chunks in the
> new tuple. For example, suppose the old tuple is
> abcdefghijklmnopqrstuvwxyz. It might get split like this: abcdef
> hijklmnopqrstuvw xyz. If any of those three chunks appear in the new
> tuple, then we'll use them for compression. If not, we'll just copy
> the literal bytes. If the chunks appear in the new tuple reordered or
> shifted or with stuff inserted between one chunk at the next, we'll
> still find them. Unless I'm confused, which is possible, what you're
> doing is essentially looking at the string and spitting it in those
> three places, but then recording the chunks as being three bytes
> shorter than they really are. I don't see how that can be right.

Today again spending some time on algorithm, I got the bug you
are pointing to and you are right in saying that chunk is shorter.
I think it should not be difficult to address this issue without affecting
most part of algorithm, let me try to handle it.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Tue, Jan 14, 2014 at 1:16 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Tue, Jan 14, 2014 at 2:16 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Sat, Jan 11, 2014 at 1:08 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>>> Yes, currently this applies to update, what I have in mind is that
>>> in future if some one wants to use WAL compression for any other
>>> operation like 'full_page_writes', then it can be easily extendible.
>>>
>>> To be honest, I have not evaluated whether such a flag or compression
>>> would make sense for full page writes, but I think it should be possible
>>> while doing full page write (BkpBlock has RelFileNode) to check such a
>>> flag if it's present.
>>
>> Makes sense.
>
> So shall I change it to string instead of bool and keep the name as
> compress_wal or compress_wal_for_opr?

No. If we add full-page-write compression in the future, that can be
a separate option. But I doubt we'd want to set that at the table
level anyway; there's no particular reason that would be good for some
tables and bad for others (whereas in this case there is such a
reason).

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

On Fri, Jan 10, 2014 at 9:12 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> 2. Provide a new reloption to specify Wal compression
>> for update operation on table
>> Create table tbl(c1 char(100)) With (compress_wal = true);
>>
>> Alternative options:
>> a. compress_wal can take input as operation, e.g. 'insert', 'update',
>> b. use alternate syntax:
>> Create table tbl(c1 char(100)) Compress Wal For Update;
>> c. anything better?
>
> I think WITH (compress_wal = true) is pretty good. I don't understand
> your point about taking the operation as input, because this only
> applies to updates. But we could try to work "update" into the name
> of the setting somehow, so as to be less likely to conflict with
> future additions, like maybe wal_compress_update. I think the
> alternate syntax you propose is clearly worse, because it would
> involve adding new keywords, something we try to avoid.

Changed name to wal_compress_update in attached version of
patch.

>
>> Points to consider
>> -----------------------------
>>
>> 1. As the current algorithm store the entry for same chunks at head of list,
>> it will always find last but one chunk (we don't store last 4 bytes) for
>> long matching string during match phase in encoding (pgrb_delta_encode).
>>
>> We can improve it either by storing same chunks at end of list instead of at
>> head or by trying to find a good_match technique used in lz algorithm.
>> Finding good_match technique can have overhead in some of the cases
>> when there is actually no match.
>
> I don't see what the good_match thing has to do with anything in the
> Rabin algorithm. But I do think there might be a bug here, which is
> that, unless I'm misinterpreting something, hp is NOT the end of the
> chunk. After calling pgrb_hash_init(), we've looked at the first FOUR
> bytes of the input. If we find that we have a zero hash value at that
> point, shouldn't the chunk size be 4, not 1? And similarly if we find
> it after sucking in one more byte, shouldn't the chunk size be 5, not
> 2? Right now, we're deciding where the chunks should end based on the
> data in the chunk plus the following 3 bytes, and that seems wonky. I
> would expect us to include all of those bytes in the chunk.

Okay, I had modified the patch to consider the the data plus following
3 bytes inside chunk. To resolve it, after calling pgrb_hash_init(), we
need to initialize chunk size as 4 and once we find the chunk, increase
the next chunk start position by adding chunk size to it. Similarly during
match phase while copying unmatched, data, make sure to copy 3
bytes ahead of current position as those will not be considered for new
chunk.

> In the Rabin algorithm, we shouldn't try to find a longer match. The
> match should end at the chunk end, period. Otherwise, you lose the
> shift-resistant property of the algorithm.

Okay for now, I have commented the code in pgrb_find_match() which
tries to find longer match after chunk boundary. The reason for just
commenting it rather than removing is that I fear it might have negative
impact on WAL reduction atleast for the cases where most of the data
is repetitive. I have done some performance test and data is at end of
mail, if you are okay with it, then I will remove this code altogether.

>> 2. Another optimization that we can do in pgrb_find_match(), is that
>> currently if
>> it doesn't find the first chunk (chunk got by hash index) matching, it
>> continues to find the match in other chunks. I am not sure if there is any
>> benefit to search for other chunks if first one is not matching.
>
> Well, if you took that out, I suspect it would hurt the compression
> ratio. Unless the CPU savings are substantial, I'd leave it alone.

I kept this code intact.

>> 3. We can move code from pg_lzcompress.c to some new file pg_rbcompress.c,
>> if we want to move, then we need to either duplicate some common macros
>> like pglz_out_tag or keep it common, but might be change the name.
>
> +1 for a new file.

Done, after moving code to new file, it looks better.

>> 4. Decide on min and max chunksize. (currently kept as 2 and 4 respectively).
>> The point to consider is that if we keep bigger chunk sizes, then it can
>> save us on CPU cycles, but less reduction in Wal, on the other side if we
>> keep it small it can have better reduction in Wal but consume more CPU
>> cycles.
>
> Whoa. That seems way too small. Since PGRB_PATTERN_AFTER_BITS is 4,
> the average length of a chunk is about 16 bytes. It makes little
> sense to have the maximum chunk size be 25% of the expected chunk
> length. I'd recommend making the maximum chunk length something like
> 4 * PGRB_CONST_NUM, and the minimum chunk length maybe something like
> 4.

Okay changed as per suggestion.

>> 5. kept an guc variable 'wal_update_compression_ratio', for test purpose, we
>> can remove it before commit.
>
> Let's remove it now.

Done.

>> 7. docs needs to be updated, tab completion needs some work.
>
> Tab completion can be skipped for now, but documentation is important.

Updated Create Table documentation.

Performance Data
-----------------------------
Non-default settings:
autovacuum =off
checkpoint_segments =128
checkpoint_timeout = 10min

Unpatched
-------------------
testname | wal_generated |
duration
----------------------------------------------------------+----------------------+------------------
one short and one long field, no change | 1054923224 | 33.101135969162

After pgrb_delta_encoding_v4
---------------------------------------------

testname | wal_generated |
duration
----------------------------------------------------------+----------------------+------------------
one short and one long field, no change | 877859144 | 30.6749138832092

Temporary Changes
(Revert Max Chunksize = 4 and logic of finding longer match)
---------------------------------------------------------------------------------------------

testname | wal_generated |
duration
----------------------------------------------------------+----------------------+------------------
one short and one long field, no change | 677337304 | 25.4048750400543

Summarization of test result:
1. If we don't try to find longer match, then it will have more tags in encoded
tuple which will increase the overall length of encoded tuple.

Note -
a. I have taken data just for one case to check whether the effect of changes
is acceptable.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Wed, Jan 15, 2014 at 5:58 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Fri, Jan 10, 2014 at 9:12 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> Performance Data
> -----------------------------
> Non-default settings:
> autovacuum =off
> checkpoint_segments =128
> checkpoint_timeout = 10min
>
> Unpatched
> -------------------
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 1054923224 | 33.101135969162
>
> After pgrb_delta_encoding_v4
> ---------------------------------------------
>
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 877859144 | 30.6749138832092
>
>
> Temporary Changes
> (Revert Max Chunksize = 4 and logic of finding longer match)
> ---------------------------------------------------------------------------------------------
>
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 677337304 | 25.4048750400543
>

Sorry, minor correction in last mail, the last data (Temporary Changes) is
just by reverting logic of finding longer match in pgrb_find_match().

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Wed, Jan 15, 2014 at 7:28 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Unpatched
> -------------------
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 1054923224 | 33.101135969162
>
> After pgrb_delta_encoding_v4
> ---------------------------------------------
>
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 877859144 | 30.6749138832092
>
>
> Temporary Changes
> (Revert Max Chunksize = 4 and logic of finding longer match)
> ---------------------------------------------------------------------------------------------
>
> testname | wal_generated |
> duration
> ----------------------------------------------------------+----------------------+------------------
> one short and one long field, no change | 677337304 | 25.4048750400543

Sure, but watch me not care.

If we're interested in taking advantage of the internal
compressibility of tuples, we can do a lot better than this patch. We
can compress the old tuple and the new tuple. We can compress
full-page images. We can compress inserted tuples. But that's not
the point of this patch.

The point of *this* patch is to exploit the fact that the old and new
tuples are likely to be very similar, NOT to squeeze out every ounce
of compression from other sources.

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

On Thu, Jan 16, 2014 at 12:49 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Wed, Jan 15, 2014 at 7:28 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> Unpatched
>> -------------------
>> testname | wal_generated |
>> duration
>> ----------------------------------------------------------+----------------------+------------------
>> one short and one long field, no change | 1054923224 | 33.101135969162
>>
>> After pgrb_delta_encoding_v4
>> ---------------------------------------------
>>
>> testname | wal_generated |
>> duration
>> ----------------------------------------------------------+----------------------+------------------
>> one short and one long field, no change | 877859144 | 30.6749138832092
>>
>>
>> Temporary Changes
>> (Revert Max Chunksize = 4 and logic of finding longer match)
>> ---------------------------------------------------------------------------------------------
>>
>> testname | wal_generated |
>> duration
>> ----------------------------------------------------------+----------------------+------------------
>> one short and one long field, no change | 677337304 | 25.4048750400543
>
> Sure, but watch me not care.
>
> If we're interested in taking advantage of the internal
> compressibility of tuples, we can do a lot better than this patch. We
> can compress the old tuple and the new tuple. We can compress
> full-page images. We can compress inserted tuples. But that's not
> the point of this patch.
>
> The point of *this* patch is to exploit the fact that the old and new
> tuples are likely to be very similar, NOT to squeeze out every ounce
> of compression from other sources.

Okay, got your point.
Another minor thing is that in latest patch which I have sent yesterday,
I have modified it such that while formation of chunks if there is a data
at end of string which doesn't have special pattern and is less than max
chunk size, we also consider that as a chunk. The reason of doing this
was that let us say if we have 104 bytes string which contains no special
bit pattern, then it will just have one 64 byte chunk and will leave the
remaining bytes, which might miss the chance of doing compression for
that data.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Thu, Jan 16, 2014 at 12:07 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Thu, Jan 16, 2014 at 12:49 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> On Wed, Jan 15, 2014 at 7:28 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>>> Unpatched
>>> -------------------
>>> testname | wal_generated |
>>> duration
>>> ----------------------------------------------------------+----------------------+------------------
>>> one short and one long field, no change | 1054923224 | 33.101135969162
>>>
>>> After pgrb_delta_encoding_v4
>>> ---------------------------------------------
>>>
>>> testname | wal_generated |
>>> duration
>>> ----------------------------------------------------------+----------------------+------------------
>>> one short and one long field, no change | 877859144 | 30.6749138832092
>>>
>>>
>>> Temporary Changes
>>> (Revert Max Chunksize = 4 and logic of finding longer match)
>>> ---------------------------------------------------------------------------------------------
>>>
>>> testname | wal_generated |
>>> duration
>>> ----------------------------------------------------------+----------------------+------------------
>>> one short and one long field, no change | 677337304 | 25.4048750400543
>>
>> Sure, but watch me not care.
>>
>> If we're interested in taking advantage of the internal
>> compressibility of tuples, we can do a lot better than this patch. We
>> can compress the old tuple and the new tuple. We can compress
>> full-page images. We can compress inserted tuples. But that's not
>> the point of this patch.
>>
>> The point of *this* patch is to exploit the fact that the old and new
>> tuples are likely to be very similar, NOT to squeeze out every ounce
>> of compression from other sources.
>
> Okay, got your point.
> Another minor thing is that in latest patch which I have sent yesterday,
> I have modified it such that while formation of chunks if there is a data
> at end of string which doesn't have special pattern and is less than max
> chunk size, we also consider that as a chunk. The reason of doing this
> was that let us say if we have 104 bytes string which contains no special
> bit pattern, then it will just have one 64 byte chunk and will leave the
> remaining bytes, which might miss the chance of doing compression for
> that data.

Yeah, that sounds right.

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

On Thu, Jan 16, 2014 at 12:07 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> Okay, got your point.
> Another minor thing is that in latest patch which I have sent yesterday,
> I have modified it such that while formation of chunks if there is a data
> at end of string which doesn't have special pattern and is less than max
> chunk size, we also consider that as a chunk. The reason of doing this
> was that let us say if we have 104 bytes string which contains no special
> bit pattern, then it will just have one 64 byte chunk and will leave the
> remaining bytes, which might miss the chance of doing compression for
> that data.

I ran Heikki's test suit on latest master and latest master plus
pgrb_delta_encoding_v4.patch on a PPC64 machine, but the results
didn't look too good. The only tests where the WAL volume changed by
more than half a percent were the "one short and one long field, no
change" test, where it dropped by 17%, but at the expense of an
increase in duration of 38%; and the "hundred tiny fields, half
nulled" test, where it dropped by 2% without a change in runtime.
Unfortunately, some of the tests where WAL didn't change significantly
took a runtime hit - in particular, "hundred tiny fields, half
changed" slowed down by 10% and "hundred tiny fields, all changed" by
8%. I've attached the full results in OpenOffice format.

Profiling the "one short and one long field, no change" test turns up
the following:

51.38% postgres pgrb_delta_encode
23.58% postgres XLogInsert
2.54% postgres heap_update
1.09% postgres LWLockRelease
0.90% postgres LWLockAcquire
0.89% postgres palloc0
0.88% postgres log_heap_update
0.84% postgres HeapTupleSatisfiesMVCC
0.75% postgres ExecModifyTable
0.73% postgres hash_search_with_hash_value

Yipes. That's a lot more than I remember this costing before. And I
don't understand why I'm seeing such a large time hit on this test
where you actually saw a significant time *reduction*. One
possibility is that you may have been running with a default
checkpoint_segments value or one that's low enough to force
checkpointing activity during the test. I ran with
checkpoint_segments=300.

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

On Mon, Jan 20, 2014 at 9:49 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>
> I ran Heikki's test suit on latest master and latest master plus
> pgrb_delta_encoding_v4.patch on a PPC64 machine, but the results
> didn't look too good. The only tests where the WAL volume changed by
> more than half a percent were the "one short and one long field, no
> change" test, where it dropped by 17%, but at the expense of an
> increase in duration of 38%; and the "hundred tiny fields, half
> nulled" test, where it dropped by 2% without a change in runtime.

> Unfortunately, some of the tests where WAL didn't change significantly
> took a runtime hit - in particular, "hundred tiny fields, half
> changed" slowed down by 10% and "hundred tiny fields, all changed" by
> 8%.

I think this part of result is positive, as with earlier approaches here the
dip was > 20%. Refer the result posted at link:
http://www.postgresql.org/message-id/51366323.8070606@vmware.com

> I've attached the full results in OpenOffice format.

> Profiling the "one short and one long field, no change" test turns up
> the following:
>
> 51.38% postgres pgrb_delta_encode
> 23.58% postgres XLogInsert
> 2.54% postgres heap_update
> 1.09% postgres LWLockRelease
> 0.90% postgres LWLockAcquire
> 0.89% postgres palloc0
> 0.88% postgres log_heap_update
> 0.84% postgres HeapTupleSatisfiesMVCC
> 0.75% postgres ExecModifyTable
> 0.73% postgres hash_search_with_hash_value
>
> Yipes. That's a lot more than I remember this costing before. And I
> don't understand why I'm seeing such a large time hit on this test
> where you actually saw a significant time *reduction*. One
> possibility is that you may have been running with a default
> checkpoint_segments value or one that's low enough to force
> checkpointing activity during the test. I ran with
> checkpoint_segments=300.

I ran with checkpoint_segments = 128 and when I ran with v4, I also
see similar WAL reduction as you are seeing, except that in my case
runtime for both are almost similar (i think in your case disk writes are
fast, so CPU overhead is more visible).
I think the major difference in above test is due to below part of code:

pgrb_find_match()
{
..
+ /* if (match_chunk)
+ {
+ while (*ip == *hp)
+ {
+ matchlen++;
+ ip++;
+ hp++;
+ }
+ } */
}

Basically if we don't go for longer match, then for test where most data
("one short and one long field, no change") is similar, it has to do below
extra steps with no advantage:
a. copy extra tags
b. calculation for rolling hash
c. finding the match
I think here major cost is due to 'a', but others might also not be free.
To confirm the theory, if we run the test by just un-commenting above
code, there can be significant change in both WAL reduction and
runtime for this test.

I have one idea to avoid the overhead of step a) which is to combine
the tags, means don't write the tag until it founds any un-matching data.
When any un-matched data is found, then combine all the previously
matched data and write it as one tag.
This should eliminate the overhead due to step a.

Can we think of anyway in which inspite of doing longer matches, we
can retain the sanctity of this approach?
One way could be to check if the match after chunk is long enough
that it matches rest of the string, but I think it can create problems
in some other cases.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Mon, Nov 25, 2013 at 6:55 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> But even if that doesn't
> pan out, I think the fallback position should not be "OK, well, if we
> can't get decreased I/O for free then forget it" but rather "OK, if we
> can't get decreased I/O for free then let's get decreased I/O in
> exchange for increased CPU usage".

While I haven't been following the development of this patch, I will
note that on the face of it the latter seem like a trade-off I'd be
quite willing to make.

--
Peter Geoghegan

On Tue, Jan 21, 2014 at 2:00 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Mon, Jan 20, 2014 at 9:49 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I ran Heikki's test suit on latest master and latest master plus
>> pgrb_delta_encoding_v4.patch on a PPC64 machine, but the results
>> didn't look too good. The only tests where the WAL volume changed by
>> more than half a percent were the "one short and one long field, no
>> change" test, where it dropped by 17%, but at the expense of an
>> increase in duration of 38%; and the "hundred tiny fields, half
>> nulled" test, where it dropped by 2% without a change in runtime.
>
>> Unfortunately, some of the tests where WAL didn't change significantly
>> took a runtime hit - in particular, "hundred tiny fields, half
>> changed" slowed down by 10% and "hundred tiny fields, all changed" by
>> 8%.
>
> I think this part of result is positive, as with earlier approaches here the
> dip was > 20%. Refer the result posted at link:
> http://www.postgresql.org/message-id/51366323.8070606@vmware.com
>
>
>> I've attached the full results in OpenOffice format.
>
>> Profiling the "one short and one long field, no change" test turns up
>> the following:
>>
>> 51.38% postgres pgrb_delta_encode
>> 23.58% postgres XLogInsert
>> 2.54% postgres heap_update
>> 1.09% postgres LWLockRelease
>> 0.90% postgres LWLockAcquire
>> 0.89% postgres palloc0
>> 0.88% postgres log_heap_update
>> 0.84% postgres HeapTupleSatisfiesMVCC
>> 0.75% postgres ExecModifyTable
>> 0.73% postgres hash_search_with_hash_value
>>
>> Yipes. That's a lot more than I remember this costing before. And I
>> don't understand why I'm seeing such a large time hit on this test
>> where you actually saw a significant time *reduction*. One
>> possibility is that you may have been running with a default
>> checkpoint_segments value or one that's low enough to force
>> checkpointing activity during the test. I ran with
>> checkpoint_segments=300.
>
> I ran with checkpoint_segments = 128 and when I ran with v4, I also
> see similar WAL reduction as you are seeing, except that in my case
> runtime for both are almost similar (i think in your case disk writes are
> fast, so CPU overhead is more visible).
> I think the major difference in above test is due to below part of code:
>
> pgrb_find_match()
> {
> ..
> + /* if (match_chunk)
> + {
> + while (*ip == *hp)
> + {
> + matchlen++;
> + ip++;
> + hp++;
> + }
> + } */
> }
>
> Basically if we don't go for longer match, then for test where most data
> ("one short and one long field, no change") is similar, it has to do below
> extra steps with no advantage:
> a. copy extra tags
> b. calculation for rolling hash
> c. finding the match
> I think here major cost is due to 'a', but others might also not be free.
> To confirm the theory, if we run the test by just un-commenting above
> code, there can be significant change in both WAL reduction and
> runtime for this test.
>
> I have one idea to avoid the overhead of step a) which is to combine
> the tags, means don't write the tag until it founds any un-matching data.
> When any un-matched data is found, then combine all the previously
> matched data and write it as one tag.
> This should eliminate the overhead due to step a.

I think that's a good thing to try. Can you code it up?

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

On Wed, Jan 22, 2014 at 12:41 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
> On Tue, Jan 21, 2014 at 2:00 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> On Mon, Jan 20, 2014 at 9:49 PM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>>> I ran Heikki's test suit on latest master and latest master plus
>>> pgrb_delta_encoding_v4.patch on a PPC64 machine, but the results
>>> didn't look too good. The only tests where the WAL volume changed by
>>> more than half a percent were the "one short and one long field, no
>>> change" test, where it dropped by 17%, but at the expense of an
>>> increase in duration of 38%; and the "hundred tiny fields, half
>>> nulled" test, where it dropped by 2% without a change in runtime.
>>
>>> Unfortunately, some of the tests where WAL didn't change significantly
>>> took a runtime hit - in particular, "hundred tiny fields, half
>>> changed" slowed down by 10% and "hundred tiny fields, all changed" by
>>> 8%.
>>
>> I think this part of result is positive, as with earlier approaches here the
>> dip was > 20%. Refer the result posted at link:
>> http://www.postgresql.org/message-id/51366323.8070606@vmware.com
>>
>> Basically if we don't go for longer match, then for test where most data
>> ("one short and one long field, no change") is similar, it has to do below
>> extra steps with no advantage:
>> a. copy extra tags
>> b. calculation for rolling hash
>> c. finding the match
>> I think here major cost is due to 'a', but others might also not be free.
>> To confirm the theory, if we run the test by just un-commenting above
>> code, there can be significant change in both WAL reduction and
>> runtime for this test.
>>
>> I have one idea to avoid the overhead of step a) which is to combine
>> the tags, means don't write the tag until it founds any un-matching data.
>> When any un-matched data is found, then combine all the previously
>> matched data and write it as one tag.
>> This should eliminate the overhead due to step a.
>
> I think that's a good thing to try. Can you code it up?

I have tried to improve algorithm in another way so that we can get
benefit of same chunks during find match (something similar to lz).
The main change is to consider chunks at fixed boundary (4 byte)
and after finding match, try to find if there is a longer match than
current chunk. While finding longer match, it still takes care that
next bigger match should be at chunk boundary. I am not
completely sure about the chunk boundary may be 8 or 16 can give
better results.

I think now we can once run with this patch on high end m/c.

Below is the data on my laptop.

Non-Default Settings
checkpoint_segments = 128
checkpoint_timeout = 15min
autovacuum = off

Before Patch

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 1054922336 | 25.4784970283508
one short and one long field, no change | 1054914728 | 45.9248871803284
one short and one long field, no change | 1054911288 | 42.0877709388733
hundred tiny fields, all changed | 633946880 | 21.4810841083527
hundred tiny fields, all changed | 633943520 | 29.5192229747772
hundred tiny fields, all changed | 633943944 | 38.1980679035187
hundred tiny fields, half changed | 633946784 | 36.0654091835022
hundred tiny fields, half changed | 638136544 | 36.231675863266
hundred tiny fields, half changed | 633944072 | 30.7445759773254
hundred tiny fields, half nulled | 570130888 | 28.6964628696442
hundred tiny fields, half nulled | 569755584 | 32.7119750976562
hundred tiny fields, half nulled | 569760312 | 32.4714169502258
(12 rows)

After Patch

testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 662239704 | 22.8768830299377
one short and one long field, no change | 662896760 | 22.466646194458
one short and one long field, no change | 662878736 | 17.6034708023071
hundred tiny fields, all changed | 633946192 | 24.5791938304901
hundred tiny fields, all changed | 634161120 | 25.7798039913177
hundred tiny fields, all changed | 633946416 | 23.761885881424
hundred tiny fields, half changed | 633945512 | 24.7001428604126
hundred tiny fields, half changed | 633947944 | 25.2069280147552
hundred tiny fields, half changed | 633946480 | 26.6489980220795
hundred tiny fields, half nulled | 492199720 | 28.7052059173584
hundred tiny fields, half nulled | 492194576 | 26.6311559677124
hundred tiny fields, half nulled | 492449408 | 25.2788209915161
(12 rows)

With above modifications, I could see ~37% WAL reduction for best case
"one short and one long field, no change" and ~13% for
"hundred tiny fields, half nulled". The duration is quite fluctuating in most
runs, so may be running it on some better m/c can give us a clear picture.

Any suggestions?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Mon, Jan 27, 2014 at 12:03 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> I think that's a good thing to try. Can you code it up?
>
> I have tried to improve algorithm in another way so that we can get
> benefit of same chunks during find match (something similar to lz).
> The main change is to consider chunks at fixed boundary (4 byte)
> and after finding match, try to find if there is a longer match than
> current chunk. While finding longer match, it still takes care that
> next bigger match should be at chunk boundary. I am not
> completely sure about the chunk boundary may be 8 or 16 can give
> better results.
>
> I think now we can once run with this patch on high end m/c.

Here are the results I got on the community PPC64 box.

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

On 01/27/2014 07:03 PM, Amit Kapila wrote:
> I have tried to improve algorithm in another way so that we can get
> benefit of same chunks during find match (something similar to lz).
> The main change is to consider chunks at fixed boundary (4 byte)
> and after finding match, try to find if there is a longer match than
> current chunk. While finding longer match, it still takes care that
> next bigger match should be at chunk boundary. I am not
> completely sure about the chunk boundary may be 8 or 16 can give
> better results.

Since you're only putting a value in the history every 4 bytes, you
wouldn't need to calculate the hash in a rolling fashion. You could just
take next four bytes, calculate hash, put it in history table. Then next
four bytes, calculate hash, and so on. Might save some cycles when
building the history table...

- Heikki

On 01/28/2014 07:01 PM, Heikki Linnakangas wrote:
> On 01/27/2014 07:03 PM, Amit Kapila wrote:
>> I have tried to improve algorithm in another way so that we can get
>> benefit of same chunks during find match (something similar to lz).
>> The main change is to consider chunks at fixed boundary (4 byte)
>> and after finding match, try to find if there is a longer match than
>> current chunk. While finding longer match, it still takes care that
>> next bigger match should be at chunk boundary. I am not
>> completely sure about the chunk boundary may be 8 or 16 can give
>> better results.
>
> Since you're only putting a value in the history every 4 bytes, you
> wouldn't need to calculate the hash in a rolling fashion. You could just
> take next four bytes, calculate hash, put it in history table. Then next
> four bytes, calculate hash, and so on. Might save some cycles when
> building the history table...

On a closer look, you're putting a chunk in the history table only every
four bytes, but you're *also* checking the history table for a match
only every four bytes. That completely destroys the shift-resistence of
the algorithm. For example, if the new tuple is an exact copy of the old
tuple, except for one additional byte in the beginning, the algorithm
would fail to recognize that. It would be good to add a test case like
that in the test suite.

You can skip bytes when building the history table, or when finding
matches, but not both. Or you could skip N bytes, and then check for
matches for the next four bytes, then skip again and so forth, as long
as you always check four consecutive bytes (because the hash function is
calculated from four bytes).

I couldn't resist the challenge, and started hacking this. First, some
observations from your latest patch (pgrb_delta_encoding_v5.patch):

1. There are a lot of comments and code that refers to "chunks", which
seem obsolete. For example, ck_size field in PGRB_HistEntry is always
set to a constant, 4, except maybe at the very end of the history
string. The algorithm has nothing to do with Rabin-Karp anymore.

2. The 'hindex' field in PGRB_HistEntry is unused. Also, ck_start_pos is
redundant with the index of the entry in the array, because the array is
filled in order. That only leaves us just the 'next' field, and that can
be represented as a int16 rather than a pointer. So, we really only need
a simple int16 array as the history entries array.

3. You're not gaining much by calculating the hash in a rolling fashion.
A single rolling step requires two multiplications and two sums, plus
shifting the variables around. Calculating the hash from scratch
requires three multiplications and three sums.

4. Given that we're not doing the Rabin-Karp variable-length chunk
thing, we could use a cheaper hash function to begin with. Like, the one
used in pglz. The multiply-by-prime method probably gives fewer
collisions than pglz's shift/xor method, but I don't think that matters
as much as computation speed. No-one has mentioned or measured the
effect of collisions in this thread; that either means that it's a
non-issue or that no-one's just realized how big a problem it is yet.
I'm guessing that it's not a problem, and if it is, it's mitigated by
only trying to find matches every N bytes; collisions would make finding
matches slower, and that's exactly what skipping helps with.

After addressing the above, we're pretty much back to PGLZ approach. I
kept the change to only find matches every four bytes, that does make
some difference. And I like having this new encoding code in a separate
file, not mingled with pglz stuff, it's sufficiently different that
that's better. I haven't done all much testing with this, so take it
with a grain of salt.

I don't know if this is better or worse than the other patches that have
been floated around, but I though I might as well share it..

- Heikki

On Wed, Jan 29, 2014 at 3:41 PM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> On 01/28/2014 07:01 PM, Heikki Linnakangas wrote:
>>
>> On 01/27/2014 07:03 PM, Amit Kapila wrote:
>>>
>>> I have tried to improve algorithm in another way so that we can get
>>> benefit of same chunks during find match (something similar to lz).
>>> The main change is to consider chunks at fixed boundary (4 byte)
>>> and after finding match, try to find if there is a longer match than
>>> current chunk. While finding longer match, it still takes care that
>>> next bigger match should be at chunk boundary. I am not
>>> completely sure about the chunk boundary may be 8 or 16 can give
>>> better results.
>>
>>
>> Since you're only putting a value in the history every 4 bytes, you
>> wouldn't need to calculate the hash in a rolling fashion. You could just
>> take next four bytes, calculate hash, put it in history table. Then next
>> four bytes, calculate hash, and so on. Might save some cycles when
>> building the history table...

First of all thanks for looking into patch.

Yes, this is right, we can save cycles by not doing rolling during hash
calculation and I was working to improve the patch on those lines. Earlier
it was their because of rabin's delta encoding where we need to check
for a special match after each byte.

>
> On a closer look, you're putting a chunk in the history table only every
> four bytes, but you're *also* checking the history table for a match only
> every four bytes. That completely destroys the shift-resistence of the
> algorithm.

You are right that it will loose the shift-resistence and even Robert has
pointed me this, that's why he wants to maintain the property of special
bytes at chunk boundaries as mentioned in Rabin encoding. The only
real reason to shift to fixed size was to improve CPU usage and I
thought most cases in Update will update the fixed length columns,
but it might not be true.

> For example, if the new tuple is an exact copy of the old tuple,
> except for one additional byte in the beginning, the algorithm would fail to
> recognize that. It would be good to add a test case like that in the test
> suite.
>
> You can skip bytes when building the history table, or when finding matches,
> but not both. Or you could skip N bytes, and then check for matches for the
> next four bytes, then skip again and so forth, as long as you always check
> four consecutive bytes (because the hash function is calculated from four
> bytes).

Can we do something like:
Build Phase
a. Calculate the hash and add the entry in history table at every 4 bytes.

Match Phase
a. Calculate the hash in rolling fashion and try to find match at every byte.
b. When match is found then skip only in chunks, something like I was
doing in find match function
+
+ /* consider only complete chunk matches. */
+ if (history_chunk_size == 0)
+ thislen += PGRB_MIN_CHUNK_SIZE;
+ }

Will this address the concern?

The main reason to process in chunks as much as possible is to save
cpu cycles. For example if we build hash table byte-by-byte, then even
for best case where most of tuple has a match, it will have reasonable
overhead due to formation of hash table.

>
> I couldn't resist the challenge, and started hacking this. First, some
> observations from your latest patch (pgrb_delta_encoding_v5.patch):
>
> 1. There are a lot of comments and code that refers to "chunks", which seem
> obsolete. For example, ck_size field in PGRB_HistEntry is always set to a
> constant, 4, except maybe at the very end of the history string. The
> algorithm has nothing to do with Rabin-Karp anymore.
>
> 2. The 'hindex' field in PGRB_HistEntry is unused. Also, ck_start_pos is
> redundant with the index of the entry in the array, because the array is
> filled in order. That only leaves us just the 'next' field, and that can be
> represented as a int16 rather than a pointer. So, we really only need a
> simple int16 array as the history entries array.
>
> 3. You're not gaining much by calculating the hash in a rolling fashion. A
> single rolling step requires two multiplications and two sums, plus shifting
> the variables around. Calculating the hash from scratch requires three
> multiplications and three sums.
>
> 4. Given that we're not doing the Rabin-Karp variable-length chunk thing, we
> could use a cheaper hash function to begin with. Like, the one used in pglz.
> The multiply-by-prime method probably gives fewer collisions than pglz's
> shift/xor method, but I don't think that matters as much as computation
> speed. No-one has mentioned or measured the effect of collisions in this
> thread; that either means that it's a non-issue or that no-one's just
> realized how big a problem it is yet. I'm guessing that it's not a problem,
> and if it is, it's mitigated by only trying to find matches every N bytes;
> collisions would make finding matches slower, and that's exactly what
> skipping helps with.
>
> After addressing the above, we're pretty much back to PGLZ approach.

Here during match phase, I think we can avoid copying literal bytes until
a match is found, that can save cycles for cases when old and new
tuple are mostly different.

> I kept
> the change to only find matches every four bytes, that does make some
> difference. And I like having this new encoding code in a separate file, not
> mingled with pglz stuff, it's sufficiently different that that's better. I
> haven't done all much testing with this, so take it with a grain of salt.
>
> I don't know if this is better or worse than the other patches that have
> been floated around, but I though I might as well share it..

Thanks for sharing the patch, I can take the data and compare it with
existing approach, if you think the explanation to change algorithm I
have given above is okay.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On 01/29/2014 02:21 PM, Amit Kapila wrote:
> On Wed, Jan 29, 2014 at 3:41 PM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>> For example, if the new tuple is an exact copy of the old tuple,
>> except for one additional byte in the beginning, the algorithm would fail to
>> recognize that. It would be good to add a test case like that in the test
>> suite.
>>
>> You can skip bytes when building the history table, or when finding matches,
>> but not both. Or you could skip N bytes, and then check for matches for the
>> next four bytes, then skip again and so forth, as long as you always check
>> four consecutive bytes (because the hash function is calculated from four
>> bytes).
>
> Can we do something like:
> Build Phase
> a. Calculate the hash and add the entry in history table at every 4 bytes.
>
> Match Phase
> a. Calculate the hash in rolling fashion and try to find match at every byte.

Sure, that'll work. However, I believe it's cheaper to add entries to
the history table at every byte, and check for a match every 4 bytes. I
think you'll get more or less the same level of compression either way,
but adding to the history table is cheaper than checking for matches,
and we'd rather do the cheap thing more often than the expensive thing.

> b. When match is found then skip only in chunks, something like I was
> doing in find match function
> +
> + /* consider only complete chunk matches. */
> + if (history_chunk_size == 0)
> + thislen += PGRB_MIN_CHUNK_SIZE;
> + }
>
> Will this address the concern?

Hmm, so when checking if a match is truly a match, you compare the
strings four bytes at a time rather than byte-by-byte? That might work,
but I don't think that's a hot spot currently. In the profiling I did,
with a "nothing matches" test case, all the cycles were spent in the
history building, and finding matches. Finding out how long a match is
was negligible. Of course, it might be a different story with input
where the encoding helps and you have matches, but I think we were doing
pretty well in those cases already.

> The main reason to process in chunks as much as possible is to save
> cpu cycles. For example if we build hash table byte-by-byte, then even
> for best case where most of tuple has a match, it will have reasonable
> overhead due to formation of hash table.

Hmm. One very simple optimization we could do is to just compare the two
strings byte by byte, before doing anything else, to find any common
prefix they might have. Then output a tag for the common prefix, and run
the normal algorithm on the rest of the strings. In many real-world
tables, the 1-2 first columns are a key that never changes, so that
might work pretty well in practice. Maybe it would also be worthwhile to
do the same for any common suffix the tuples might have.

That would fail to find matches where you e.g. update the last column to
have the same value as the first column, and change nothing else, but
that's ok. We're not aiming for the best possible compression, just
trying to avoid WAL-logging data that wasn't changed.

> Here during match phase, I think we can avoid copying literal bytes until
> a match is found, that can save cycles for cases when old and new
> tuple are mostly different.

I think the extra if's in the loop will actually cost you more cycles
than you save. You could perhaps have two copies of the main
match-finding loop though. First, loop without outputting anything,
until you find the first match. Then, output anything up to that point
as literals. Then fall into the second loop, which outputs any
non-matches byte by byte.

- Heikki

On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
<hlinnakangas(at)vmware(dot)com> wrote:
> On 01/29/2014 02:21 PM, Amit Kapila wrote:
>> b. When match is found then skip only in chunks, something like I was
>> doing in find match function
>> +
>> + /* consider only complete chunk matches. */
>> + if (history_chunk_size == 0)
>> + thislen += PGRB_MIN_CHUNK_SIZE;
>> + }
>>
>> Will this address the concern?
>
>
> Hmm, so when checking if a match is truly a match, you compare the strings
> four bytes at a time rather than byte-by-byte? That might work, but I don't
> think that's a hot spot currently. In the profiling I did, with a "nothing
> matches" test case, all the cycles were spent in the history building, and
> finding matches. Finding out how long a match is was negligible. Of course,
> it might be a different story with input where the encoding helps and you
> have matches, but I think we were doing pretty well in those cases already.

I think the way you have improve forming history tables is damn good (using
very few instructions) and we might not need to proceed chunk wise, but still
I think it might give us benefits when all or most part of the old and new tuple
matches. Also for nothing or lesser match case, I think we can skip more
frequently till we find first match.
If we don't find any match for first 4 bytes, then skip 4 bytes and if we don't
find match again for next 8 bytes, then skip 8 bytes and keep on doing the
same until we find first match. There is a chance that we miss some bytes
for compression, but it should not effect much as we are doing this only till
we find first match and during match phase we always find longest match.
I have added this concept in new version of patch and it's more easy to
add this logic after I implemented your suggestion of breaking main match
loop to 2 loops.

>
>> The main reason to process in chunks as much as possible is to save
>> cpu cycles. For example if we build hash table byte-by-byte, then even
>> for best case where most of tuple has a match, it will have reasonable
>> overhead due to formation of hash table.
>
>
> Hmm. One very simple optimization we could do is to just compare the two
> strings byte by byte, before doing anything else, to find any common prefix
> they might have. Then output a tag for the common prefix, and run the normal
> algorithm on the rest of the strings. In many real-world tables, the 1-2
> first columns are a key that never changes, so that might work pretty well
> in practice. Maybe it would also be worthwhile to do the same for any common
> suffix the tuples might have.

Is it possible to do for both prefix and suffix together, basically
the question I
have in mind is what will be deciding factor for switching from hash table
mechanism to string comparison mode for suffix. Do we switch when we find
long enough match?

Can we do this optimization after the basic version is acceptable?

>> Here during match phase, I think we can avoid copying literal bytes until
>> a match is found, that can save cycles for cases when old and new
>> tuple are mostly different.
>
>
> I think the extra if's in the loop will actually cost you more cycles than
> you save. You could perhaps have two copies of the main match-finding loop
> though. First, loop without outputting anything, until you find the first
> match. Then, output anything up to that point as literals. Then fall into
> the second loop, which outputs any non-matches byte by byte.

This is certainly better way of implementation, I have changed the patch
accordingly and I have modified patch to address your comments, except
for removing hindex from history entry structure. I believe that the way you
have done in patch back-to-pglz-like-delta-encoding-1 is better and I will
change it after understanding the logic completely.

Few observations in patch (back-to-pglz-like-delta-encoding-1):

1.
+#define pgrb_hash_unroll(_p, hindex) \
+ hindex = hindex ^ ((_p)[0] << 8)

shouldn't it shift by 6 rather than by 8.

2.
+ if (bp - bstart >= result_max)
+ return false;

I think for nothing or lesser match case it will traverse whole tuple.
Can we optimize such that if there is no match till 75%, we can bail out.
Ideally, I think if we don't find any match in first 50 to 60%, we should
come out.

3. pg_rbcompress.h is missing.

I am still working on patch back-to-pglz-like-delta-encoding-1 to see if
it works well for all cases, but thought of sharing what I have done till
now to you.

After basic verification of back-to-pglz-like-delta-encoding-1, I will
take the data with both the patches and report the same.

Please let me know your thoughts?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Thu, Jan 30, 2014 at 12:23 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>
> Few observations in patch (back-to-pglz-like-delta-encoding-1):
>
> 1.
> +#define pgrb_hash_unroll(_p, hindex) \
> + hindex = hindex ^ ((_p)[0] << 8)
>
> shouldn't it shift by 6 rather than by 8.
>
> 2.
> + if (bp - bstart >= result_max)
> + return false;
>
> I think for nothing or lesser match case it will traverse whole tuple.
> Can we optimize such that if there is no match till 75%, we can bail out.
> Ideally, I think if we don't find any match in first 50 to 60%, we should
> come out.
>
> 3. pg_rbcompress.h is missing.
>
> I am still working on patch back-to-pglz-like-delta-encoding-1 to see if
> it works well for all cases, but thought of sharing what I have done till
> now to you.
>
> After basic verification of back-to-pglz-like-delta-encoding-1, I will
> take the data with both the patches and report the same.

Apart from above, the only other thing which I found problematic is
below code in find match

+ while (*ip == *hp && thislen < maxlen)
+ thislen++;

It should be
while (*ip++ == *hp++ && thislen < maxlen)

Please confirm.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Thu, Jan 30, 2014 at 12:23 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
> <hlinnakangas(at)vmware(dot)com> wrote:
>
> After basic verification of back-to-pglz-like-delta-encoding-1, I will
> take the data with both the patches and report the same.

I have corrected the problems reported in back-to-pglz-like-delta-encoding-1
and removed hindex from pgrb_delta_encoding_v6 and attached are
new versions of both patches.

I/O Reduction Data
-----------------------------
Non-Default settings
autovacuum = off
checkpoitnt_segments = 256
checkpoint_timeout =15min

Unpatched
------------------
testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 1054917904 | 14.6407959461212
one short and one long field, no change | 1054917840 | 14.2938411235809
one short and one long field, no change | 1054916032 | 14.6062371730804
hundred tiny fields, all changed | 633950304 | 15.6165988445282
hundred tiny fields, all changed | 633943184 | 15.7330548763275
hundred tiny fields, all changed | 633943536 | 16.2008850574493
hundred tiny fields, half changed | 633946056 | 15.9042718410492
hundred tiny fields, half changed | 633949992 | 15.9494590759277
hundred tiny fields, half changed | 633948448 | 17.1421928405762
hundred tiny fields, half nulled | 569757992 | 16.0392069816589
hundred tiny fields, half nulled | 569758848 | 15.7891688346863
hundred tiny fields, half nulled | 569755144 | 16.2466349601746

Patch pgrb_delta_encoding_v7
------------------------------------------------
testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 662240016 | 12.0052649974823
one short and one long field, no change | 662570640 | 11.5202040672302
one short and one long field, no change | 662231656 | 12.2640421390533
hundred tiny fields, all changed | 633947296 | 17.0527350902557
hundred tiny fields, all changed | 633945824 | 17.1216440200806
hundred tiny fields, all changed | 633948904 | 16.8881120681763
hundred tiny fields, half changed | 633944656 | 18.0734100341797
hundred tiny fields, half changed | 633944472 | 17.0183899402618
hundred tiny fields, half changed | 633945112 | 16.6483509540558
hundred tiny fields, half nulled | 499946000 | 18.9340658187866
hundred tiny fields, half nulled | 499952408 | 18.7714779376984
hundred tiny fields, half nulled | 499953432 | 18.690948009491
(12 rows)

Patch back-to-pglz-like-delta-encoding-2
----------------------------------------------------------
testname | wal_generated | duration
-----------------------------------------+---------------+------------------
one short and one long field, no change | 662242872 | 12.7399699687958
one short and one long field, no change | 662233440 | 12.7010321617126
one short and one long field, no change | 663938992 | 13.1172158718109
hundred tiny fields, all changed | 635451832 | 17.918673992157
hundred tiny fields, all changed | 633946736 | 17.1329951286316
hundred tiny fields, all changed | 633943480 | 17.0818238258362
hundred tiny fields, half changed | 634762208 | 17.0016329288483
hundred tiny fields, half changed | 633946560 | 17.3154718875885
hundred tiny fields, half changed | 633943240 | 17.1657249927521
hundred tiny fields, half nulled | 492017488 | 27.3930599689484
hundred tiny fields, half nulled | 492016776 | 26.7517058849335
hundred tiny fields, half nulled | 493848424 | 26.6423358917236
(12 rows)

Observations
--------------------
1. With both the patches WAL reduction is similar i.e ~37% for
"one short and one long field, no change" and 12% for
"hundred tiny fields, half nulled"
2. With pgrb_delta_encoding_v7, there is ~19% CPU reduction for best
case "one short and one long field, no change".
3. With pgrb_delta_encoding_v7, there is approximately 8~9% overhead
for cases where there is no match
4. With pgrb_delta_encoding_v7, there is approximately 15~18% overhead
for "hundred tiny fields, half nulled" case
5. With back-to-pglz-like-delta-encoding-2, the data is mostly similar except
for "hundred tiny fields, half nulled" where CPU overhead is much more.

The case ("hundred tiny fields, half nulled") where CPU overhead is visible
is due to repetitive data and if take some random or different data, it will not
be there. I think the main reason for overhead is that we store last offset
of matching data in history at front, so during match, it has to traverse back
many times to find longest possible match and in real world it won't be the
case that most of history entries contain same hash index, so it should not
effect.
Finally if any user is concerned much about CPU overhead due to it, there
is a table level knob which he can use to avoid it.

Please let me know your suggestions.

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Jan 31, 2014 at 12:33 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Thu, Jan 30, 2014 at 12:23 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
>> <hlinnakangas(at)vmware(dot)com> wrote:
>>
>> After basic verification of back-to-pglz-like-delta-encoding-1, I will
>> take the data with both the patches and report the same.
>
> I have corrected the problems reported in back-to-pglz-like-delta-encoding-1
> and removed hindex from pgrb_delta_encoding_v6 and attached are
> new versions of both patches.
>
> I/O Reduction Data
> -----------------------------
> Non-Default settings
> autovacuum = off
> checkpoitnt_segments = 256
> checkpoint_timeout =15min
>
> Observations
> --------------------
> 1. With both the patches WAL reduction is similar i.e ~37% for
> "one short and one long field, no change" and 12% for
> "hundred tiny fields, half nulled"
> 2. With pgrb_delta_encoding_v7, there is ~19% CPU reduction for best
> case "one short and one long field, no change".
> 3. With pgrb_delta_encoding_v7, there is approximately 8~9% overhead
> for cases where there is no match
> 4. With pgrb_delta_encoding_v7, there is approximately 15~18% overhead
> for "hundred tiny fields, half nulled" case
> 5. With back-to-pglz-like-delta-encoding-2, the data is mostly similar except
> for "hundred tiny fields, half nulled" where CPU overhead is much more.
>
> The case ("hundred tiny fields, half nulled") where CPU overhead is visible
> is due to repetitive data and if take some random or different data, it will not
> be there.

To verify this theory, I have added one new test which is almost similar to
"hundred tiny fields, half nulled", the difference is that it has
non-repetive string
and the results are as below:

Unpatch
--------------
testname | wal_generated |
duration
------------------------------------------------------+---------------+------------------
nine short and one long field, thirty percent change | 698912496
| 12.1819660663605
nine short and one long field, thirty percent change | 698906048
| 11.9409539699554
nine short and one long field, thirty percent change | 698910904
| 11.9367880821228

Patch pgrb_delta_encoding_v7
------------------------------------------------

testname | wal_generated
| duration
------------------------------------------------------+---------------+------------------
nine short and one long field, thirty percent change | 559840840
| 11.6027710437775
nine short and one long field, thirty percent change | 559829440
| 11.8239741325378
nine short and one long field, thirty percent change | 560141352
| 11.6789472103119

Patch back-to-pglz-like-delta-encoding-2
----------------------------------------------------------

testname | wal_generated |
duration
------------------------------------------------------+---------------+------------------
nine short and one long field, thirty percent change | 544391432
| 12.3666560649872
nine short and one long field, thirty percent change | 544378616
| 11.8833730220795
nine short and one long field, thirty percent change | 544376888
| 11.9487581253052
(3 rows)

Basic idea of new test is that some part of tuple is unchanged and
other part is changed, here the unchanged part contains random string
rather than repetitive set of chars.
The new test is added with other tests in attached file.

Observation
-------------------
LZ like delta encoding has more WAL reduction and chunk wise encoding
has bit better CPU usage, but overall both are almost similar.

> I think the main reason for overhead is that we store last offset
> of matching data in history at front, so during match, it has to traverse back
> many times to find longest possible match and in real world it won't be the
> case that most of history entries contain same hash index, so it should not
> effect.

If we want to improve CPU usage for cases like "hundred tiny fields,
half nulled"
(which I think is not important), forming history table by traversing from end
rather than beginning, can serve the purpose, I have not tried it but I think
it can certainly help.

Do you think overall data is acceptable?

With Regards,
Amit Kapila.
EnterpriseDB: http://www.enterprisedb.com

On Fri, Jan 31, 2014 at 1:35 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
> On Fri, Jan 31, 2014 at 12:33 AM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>> On Thu, Jan 30, 2014 at 12:23 PM, Amit Kapila <amit(dot)kapila16(at)gmail(dot)com> wrote:
>>> On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
>>> <hlinnakangas(at)vmware(dot)com> wrote:
>>>
>>> After basic verification of back-to-pglz-like-delta-encoding-1, I will
>>> take the data with both the patches and report the same.
>>
>> I have corrected the problems reported in back-to-pglz-like-delta-encoding-1
>> and removed hindex from pgrb_delta_encoding_v6 and attached are
>> new versions of both patches.
>>
>> I/O Reduction Data
>> -----------------------------
>> Non-Default settings
>> autovacuum = off
>> checkpoitnt_segments = 256
>> checkpoint_timeout =15min
>>
>> Observations
>> --------------------
>> 1. With both the patches WAL reduction is similar i.e ~37% for
>> "one short and one long field, no change" and 12% for
>> "hundred tiny fields, half nulled"
>> 2. With pgrb_delta_encoding_v7, there is ~19% CPU reduction for best
>> case "one short and one long field, no change".
>> 3. With pgrb_delta_encoding_v7, there is approximately 8~9% overhead
>> for cases where there is no match
>> 4. With pgrb_delta_encoding_v7, there is approximately 15~18% overhead
>> for "hundred tiny fields, half nulled" case
>> 5. With back-to-pglz-like-delta-encoding-2, the data is mostly similar except
>> for "hundred tiny fields, half nulled" where CPU overhead is much more.
>>
>> I think the main reason for overhead is that we store last offset
>> of matching data in history at front, so during match, it has to traverse back
>> many times to find longest possible match and in real world it won't be the
>> case that most of history entries contain same hash index, so it should not
>> effect.
>
> If we want to improve CPU usage for cases like "hundred tiny fields,
> half nulled"
> (which I think is not important), forming history table by traversing from end
> rather than beginning, can serve the purpose, I have not tried it but I think
> it can certainly help.