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

On Tue, Sep 2, 2014 at 10:27 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
> * Still doesn't address the open question of whether or not we should
> optimistically always try "memcmp() == 0" on tiebreak. I still lean
> towards "yes".

Let m be the cost of a memcmp() that fails near the end of the
strings; and let s be the cost of a strcoll that does likewise.
Clearly s > m. But approximately what is s/m on platforms where you
can test? Say, with 100 byte string, in a few different locales.

If for example s/m > 100 then it's a no-brainer, because in the worst
case we're adding 1% overhead, and in the best case we're saving 99%.
OTOH, if s/m < 2 then I almost certainly wouldn't do it, because in
the worst case we're adding >50% overhead, and in the best case we're
saving <50%. That seems like it's doubling down on the abbreviated
key stuff to work mostly all the time, and I'm not prepared to make
that bet. There is of course a lot of daylight between a 2-to-1 ratio
and a 100-to-1 ratio and I expect the real value is somewhere in the
middle (probably closer to 2); I haven't at this time made up my mind
what value would make this worthwhile, but I'd like to know what the
real numbers are.

> * Leaves open the question of what to do when we can't use the
> abbreviated keys optimization just because a datum tuplesort is
> preferred when sorting single-attribute tuples (recall that datum case
> tuplesorts cannot use abbreviated keys). We want to avail of tuplesort
> datum sorting where we can, except when abbreviated keys are
> available, which presumably tips the balance in favor of heap tuple
> sorting even when sorting on only one attribute, simply because then
> we can then use abbreviated keys. I'm thinking in particular of
> nodeAgg.c, which is an important case.

I favor leaving this issue to a future patch. The last thing this
patch needs is more changes that someone might potentially dislike.
Let's focus on getting the core thing working, and then you can
enhance it once we all agree that it is.

On the substance of this issue, I suspect that for pass-by-value data
types it can hardly be wrong to use the datum tuplesort approach; but
it's possible we will want to disable it for pass-by-reference data
types when the abbreviated-key infrastructure is available. That will
lose if it turns out that the abbreviated keys aren't capturing enough
of the entropy, but maybe we'll decide that's OK. Or maybe not. But
I don't think it's imperative that this patch make a change in that
area, and indeed, in the interest of keeping separate changes
isolated, I think it's better if it doesn't.

> There are still FIXME/TODO comments for each of these two points.
> Further, this revised/rebased patch set:
>
> * Incorporates your feedback on stylistic issues, with changes
> confined to their own commit (on top of earlier commits that are
> almost, but not quite, the same as the prior revision that your
> remarks apply to).
>
> * No longer does anything special within reversedirection_heap(),
> since that is unnecessary, as it's only used by bounded sorts, which
> aren't a useful target for abbreviated keys. This is noted. There is
> no convenient point to add a defensive assertion against this, so I
> haven't.
>
> * Updates comments in master in a broken-out way, reflecting opclass
> contract with sortsupport as established by
> 1d41739e5a04b0e93304d24d864b6bfa3efc45f2, that is convenient to apply
> to and commit in the master branch immediately.

Thanks, committed that one. The remaining patches can be squashed
into a single one, as none of them can be applied without the others.

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