Thread: Eliminating CREATE INDEX comparator TID tie-breaker overhead

I have one more idea for accelerating sorting-related operations that
is both fairly effective and relatively easy to implement. This just
about clears my backlog of those, though.

There is an open item on the TODO list entitled "Consider whether
duplicate keys should be sorted by block/offset" [1].

Currently, comparetup_index_btree() and comparetup_index_hash() do a
tie-breaker on ItemPointer (heap TID). This started as insurance
against bad qsort() implementations that do badly with many equal
keys, but it was also thought that there is some value in having equal
keys be in physical (heap) order. Clearly the first concern has been
obsolete since 2006, when a high quality qsort() was added to
Postgres, but the second concern is probably still valid.

Overhead
-------------

Tom said in 2008 that the CREATE INDEX overhead of doing this may be
about 7% [2]. It seems even worse now, presumably due to SortSupport
reducing costs elsewhere. Several years ago, I suggested ripping out
the tie-breaker too, but didn't get very far with that idea due to the
potential downsides for index scans. I'm not about to revisit the
discussion from 2011 about whether or not it should be torn out. I'd
rather just (mostly) fix the real problem without changing the
behavior of comparetup_index_btree() (or comparetup_index_hash()).

The real problem is that we do pointer chasing to get to the
IndexTuple ("tuple proper"), where we might get away with only
examining the SortTuple, as would happen in comparetup_heap() in the
event of an equivalent heap tuplesort, for example. The added memory
latency hurts lower cardinality attributes (when only one attribute
appears in the Index definition and the IndexTuple isn't cache
resident), and wastes memory bandwidth on the system, which is
something that there is virtually never enough of.

Patch
=====

Attached patch adds a new tie-breaker which is used only when the
tuples being sorted still fit in memory. Currently, the field
SortTuple.tupindex has a different purpose depending on whether we're
building initial runs or merging runs. However, SortTuple.tupindex
currently has no purpose when a sort can complete entirely in memory,
so that case is available to support a third meaning:
SortTuple.tupindex can be used to hold a simple ordinal number. When
our status is TSS_INITIAL (when we qsort()), this is used as a proxy
for what the TID tie-breaker would ordinarily return.

This reliably preserves the existing behavior because index tuplesort
clients invariably scan heap tuples in physical order, and so nothing
is lost.

Performance
-----------------

The patch can make CREATE INDEX with an unlogged B-Tree index with a
single int4 attribute as much as 15% faster (although I think under
10% is much more likely). That seems like an improvement that makes
the patch worthwhile.

Design considerations and consequences
--------------------------------------------------------

I don't think that there is much point in getting rid of
SortTuple.tupindex for in-memory sorts, which this patch closes off
the possibility of. I tested the performance of a SortTuple struct
with only a datum1 and "tuple proper" for in-memory sorting at one
time, and it was disappointing, and in any case unworkably invasive.

I also don't think it's worth worrying about the fact that tupindex is
assigned an ordinal number even in cases where it won't be used inside
the comparator. The overhead has to be indistinguishable from zero
anyway, and the right place to put that assignment happens to be where
there is generic TSS_INITIAL copying within puttuple_common().

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.

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.

[1] https://wiki.postgresql.org/wiki/Todo#Sorting
[2] http://www.postgresql.org/message-id/23321.1205726381@sss.pgh.pa.us
--
Peter Geoghegan

On Tue, Jul 21, 2015 at 4:06 PM, Peter Geoghegan <pg@heroku.com> wrote:
> Design considerations and consequences
> --------------------------------------------------------

Good write-up.

> 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?

> 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.

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

On Wed, Jul 22, 2015 at 11:03 AM, Robert Haas <robertmhaas@gmail.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

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

On Thu, Jul 23, 2015 at 8:19 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> 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.

I don't know where this idea came from, because I'm already supporting
the requirement for the external sorting case, where doing this is too
much of a burden. That is entirely unchanged, and so such differences
are clearly already respected. Any new patch likely to care about this
(e.g. parallel internal sorts) will probably naturally not be affected
by it anyway, just because they'll add a new tuplesort state, or
because multiple "memtuples" arrays will be filled in parallel, but
still in sequential order, and so everything works out just the same.
Aside from that, the author might have to spend 5 minutes thinking
about it. I don't see the problem.

Adding this single new requirement for exactly 2 extant callers does
not make tuplesort any less well encapsulated. Please don't write
wildly inaccurate summaries of what I've said, like "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". That is patently untrue.

> 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.

More than a few - sometimes more than 10%.

The second rationale was, as far as I can tell, a theoretical one that
was never experimentally validated. I'm pretty sure you could come up
with a case where not having it hurt, if you were sufficiently
creative. I'm not sure that I have the stomach for another protracted
debate about these fuzzy costs, which this patch was suppose to avoid.
However, you don't like this patch for reasons that I cannot fathom. I
think that I will have to withdraw it, and forget about cutting this
unnecessary cost from B-Tree builds.

Our priorities are different, but mine are changing; I simply don't
want to spend a lot of time arguing with you about things like this.

-- 
Peter Geoghegan

On Thu, Jul 23, 2015 at 2:19 PM, Peter Geoghegan <pg@heroku.com> wrote:
> Our priorities are different, but mine are changing; I simply don't
> want to spend a lot of time arguing with you about things like this.

Good.

If other people feel strongly about this issue, then they can weigh in
and we'll see where we end up.  If they don't, then there's no
consensus to proceed with this, and we shouldn't *have* to spend a lot
of time on it.

Also, I resent the implication that I wrote a deliberately inaccurate
summary of your position.  If it was inaccurate, it wasn't deliberate.
More likely, we simply view the situation differently.  Please assume
good faith.

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

On Thu, Jul 23, 2015 at 11:28 AM, Robert Haas <robertmhaas@gmail.com> wrote:
> If other people feel strongly about this issue, then they can weigh in
> and we'll see where we end up.  If they don't, then there's no
> consensus to proceed with this, and we shouldn't *have* to spend a lot
> of time on it.

If no one weighs in after a few days, I'll mark the patch "rejected"
in the CF app.

> Also, I resent the implication that I wrote a deliberately inaccurate
> summary of your position.  If it was inaccurate, it wasn't deliberate.
> More likely, we simply view the situation differently.  Please assume
> good faith.

You wrote "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". If you'd like me
to assume good faith in these situations, maybe you should be more
careful about your choice of words. You statement was extremely broad,
unlike the very narrow technical issue under discussion.

-- 
Peter Geoghegan

2015-07-23 Robert Haas <robertmhaas@gmail.com>:

> I think what you should do is go find out whether the second rationale
> is valid or not.

Knowing how much impact on performance such “non TID ordered” entries
have, would of course be very useful for future patch authors to know.
Especially useful would be to know whether interleaving a small number
of TID ordered streams (as would probably be generated by parallel
scans/processing) would result in an ordering that performs
significantly worse or not. I assume (but cannot prove) that in this
case the OS will understand the read pattern as being multiple streams
and prefetching will work correctly.

> 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.

Except that it will do the right thing (as in correctness), but maybe
result in not the best overall performance possible (for future
queries). I think that it is a typical property of “reasons for
performance to be good” that they rely on a lot of code that is
otherwise independent, to work together the right way.

Nicolas

--
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

2015-07-24 Nicolas Barbier <nicolas.barbier@gmail.com>:

> Especially useful would be to know whether interleaving a small number
> of TID ordered streams (as would probably be generated by parallel
> scans/processing) would result in an ordering that performs
> significantly worse or not. I assume (but cannot prove) that in this
> case the OS will understand the read pattern as being multiple streams
> and prefetching will work correctly.

OTOH, that is probably only true when there are a large number of
duplicate keys. Otherwise the order within each (small) group will
appear random, which may or may not result in a significant
performance drop. This probably also depends on whether fadvise (or
friends) are used.

Nicolas

-- 
A. Because it breaks the logical sequence of discussion.
Q. Why is top posting bad?

On Thu, Jul 23, 2015 at 11:44 AM, Peter Geoghegan <pg@heroku.com> wrote:
> If no one weighs in after a few days, I'll mark the patch "rejected"
> in the CF app.

The patch has been marked "rejected" in the CF app. I withdraw it.

Obviously I still think that the patch is worthwhile, but not if that
"while" is disproportionate to any benefit, which I suspect will be
the case if I proceed.

-- 
Peter Geoghegan