Re: Eliminating CREATE INDEX comparator TID tie-breaker overhead

On Wed, Jul 22, 2015 at 11:03 AM, Robert Haas <robertmhaas(at)gmail(dot)com> wrote:
>> I'm not concerned about synchronized scans breaking my assumption of a
>> physical ordering of heaptuples being fed to tuplesort.c. I think that
>> it is unlikely to ever be worth seriously considering this case.
>
> Why not?

The case for doing this tie-breaker is theoretical. The original
rationale for adding it is now obsolete. On the other hand, the cost
of doing it is most certainly not theoretical.

If it's absolutely necessary to preserve a guarantee that equal tuples
are in TID order (rather than at most two staggered sequential
groupings per set of equal tuples -- possible with synchronized
scans), then I suggest we detect synchronized scans and disable this
optimization. They're not especially common, so it would still be
worthwhile, in my estimation.

>> I have a hard time imagining anything (beyond synchronous scans)
>> breaking my assumption that index tuplesorts receive tuples in heap
>> physical order. If anything was to break that in the future (e.g.
>> parallelizing the heap scan for index builds), then IMV the onus
>> should be on that new case to take appropriate precautions against
>> breaking my assumption.
>
> I'm very dubious about that. There are lots of reasons why we might
> want to read tuples out of order; for example, suppose we want a
> parallel sequential scan to feed the sort.

I agree that there are many reasons to want to do that. If we ever get
parallel sorts, then having a bunch of memtuple arrays, each fed by a
worker participating in a parallel scan makes sense. Those runs could
still be sorted in physical order. Only the merge phase would have to
do pointer chasing to tie-break on the real TID, and maybe not even
then (because run number can also be a proxy for physical order when
merging, assuming some new parallel internal sort algorithm).
Actually, for tape sort/replacement selection sort, the initial heap
build (where run number 0 is assigned currently) could probably reuse
this trick. I just haven't done that because it would be significantly
more invasive and less helpful.

If it's just a matter of wanting to parallelize the heap scan for its
own sake, then I don't think that's likely to be a terribly effective
optimization for B-Tree index builds; most of the cost is always going
to be in the sort proper, which I'm targeting here. In any case, I
think that the very common case where an int4 PK index is built using
quicksort should not have to suffer to avoid a minor inconveniencing
of (say) parallel sorts.

--
Peter Geoghegan