Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Thu, Jul 23, 2015 at 11:44 AM, Peter Geoghegan p...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
2015-07-23 Robert Haas robertmh...@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? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
2015-07-24 Nicolas Barbier nicolas.barb...@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? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Wed, Jul 22, 2015 at 3:17 PM, Peter Geoghegan p...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Thu, Jul 23, 2015 at 11:28 AM, Robert Haas robertmh...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Thu, Jul 23, 2015 at 8:19 AM, Robert Haas robertmh...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Tue, Jul 21, 2015 at 4:06 PM, Peter Geoghegan p...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Eliminating CREATE INDEX comparator TID tie-breaker overhead
On Wed, Jul 22, 2015 at 11:03 AM, Robert Haas robertmh...@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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] 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.1205726...@sss.pgh.pa.us -- Peter Geoghegan From 22e3aa14436d3c4ca8ccde2cc55777c6207fd9f0 Mon Sep 17 00:00:00 2001 From: Peter Geoghegan peter.geoghega...@gmail.com Date: Thu, 16 Jul 2015 22:26:01 -0700 Subject: [PATCH] Cache-aware index sort comparator tie-breakers For the B-Tree and hash index build sort cases only, tuplesort previously performed a tie-breaker on ItemPointer (heap physical order). This may later provide some performance benefits for index scans. However, it implied significant overhead during index builds, because additional pointer chasing (to the IndexTuple tuple proper) was required in the comparators, which adds significant memory latency where the tuple proper does not otherwise need to be
