Re: Eliminating CREATE INDEX comparator TID tie-breaker overhead

On Wed, Jul 22, 2015 at 3:17 PM, Peter Geoghegan <pg(at)heroku(dot)com> wrote:
>>> 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.

My priorities are different from yours. Your conclusion is basically
that it's OK to burden everyone who comes along and does future
development that may use the sorting code differently from the way
it's used now with dealing with this issue somehow, or deciding not to
deal with it. I have a really tough time agreeing with that;
tuplesort.c is, and should be, an abstraction layer, and people using
it from the outside should not need to worry about what happens on the
inside.

Your original post lays out two rationales for the TID comparisons,
and says that one of them is obsolete, but the other is "probably"
still valid. I think what you should do is go find out whether the
second rationale is valid or not. If it's not, we can get rid of that
code. If it is valid, then we can't. I'm not going to endorse the
notion that tuplesort.c will only DTRT if it receives tuples in TID
order; it cannot be the responsibility of the caller of the sort code
to ensure that the tuples are sorted. Even if it shaves a few
percentage points off the runtime now, the complexity it imposes on
future patch authors is, IMO, not worth it.

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