Re: Performance Improvement by reducing WAL for Update Operation

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