Re: B-Tree support function number 3 (strxfrm() optimization)

On Sun, Jul 27, 2014 at 12:00 AM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> I attach a new revision.

I think that I may have missed a trick here.

It turns out that it isn't expensive to also hash original text
values, to track their cardinality using HyperLogLog - it's hardly
measurable when done at an opportune point just after strxfrm()
expansion. I was already tracking the cardinality of poor man's
normalized keys using HyperLogLog. If I track the cardinality of both
sets (original values and normalized keys), I can compare the two when
evaluating if normalization should be aborted. This is by far the most
important consideration.

This causes the optimization to be applied when sorting millions of
tuples with only a tiny number of distinct values (like, 4 or 5),
without making bad cases that we fail to abort in a timely manner any
more likely. This is still significantly profitable - over 90% faster
in one test, because the optimistic memcmp() still allows us to avoid
any strcoll() calls. It looks about the same as using the "C"
collation. Not quite the huge boost we can see, but still well
worthwhile.

In general it seems well principled to have the "should I abort
normalization?" algorithm mostly weigh how effective a proxy for full
key cardinality normalized key cardinality is. If it is a good proxy
then nothing else matters. If it's not a very good proxy, that can
only be because there are many differences beyond the first 8 bytes.
Only then will we weigh the total number of distinct normalized keys,
and as the effectiveness of normalized key cardinality as a proxy for
overall cardinality falls, our requirements for the overall number of
distinct normalized keys shoots up rapidly.

--
Peter Geoghegan