On 01/30/2014 08:53 AM, Amit Kapila wrote:
> On Wed, Jan 29, 2014 at 8:13 PM, Heikki Linnakangas
> <hlinnakangas@vmware.com> wrote:
>> On 01/29/2014 02:21 PM, Amit Kapila wrote:
>>> 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?
I think you got it backwards. You don't switch from hash table mechanism
to string comparison. You do the prefix/suffix comparison *first*, and
run the hash table algorithm only on the "middle" part, between the
common prefix and suffix.
> Can we do this optimization after the basic version is acceptable?
I would actually suggest doing that first. Perhaps even ditch the whole
history table approach and do *only* the scan for prefix and suffix.
That's very cheap, and already covers a large fraction of UPDATEs that
real applications do. In particular, it's optimal for the case that you
update only a single column, something like "UPDATE foo SET bar = bar + 1".
I'm pretty sure the overhead of that would be negligible, so we could
always enable it. There are certainly a lot of scenarios where
prefix/suffix detection alone wouldn't help, but so what.
Attached is a quick patch for that, if you want to test it.
- Heikki
