Re: Performance Improvement by reducing WAL for Update Operation

On 01/29/2014 02:21 PM, Amit Kapila wrote:
> On Wed, Jan 29, 2014 at 3:41 PM, Heikki Linnakangas
> <hlinnakangas@vmware.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