Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort"

On 07/30/2015 04:05 AM, Peter Geoghegan wrote:

Patch -- "quicksort with spillover"
=========================

With the attached patch, I propose to add an additional, better "one
run special case" optimization. This new special case "splits" the
single run into 2 "subruns". One of the runs is comprised of whatever
tuples were in memory when the caller finished passing tuples to
tuplesort. To sort that, we use quicksort, which in general has
various properties that make it much faster than heapsort -- it's a
cache oblivious algorithm, which is important these days. The other
"subrun" is whatever tuples were on-tape when tuplesort_performsort()
was called. This will often be a minority of the total, but certainly
never much more than half. This is already sorted when
tuplesort_performsort() is reached. This spillover is already inserted
at the front of the sorted-on-tape tuples, and so already has
reasonably good cache characteristics.

With the patch, we perform an on-the-fly merge that is somewhat
similar to the existing (unaffected) "merge sort" TSS_FINALMERGE case,
except that one of the runs is in memory, and is potentially much
larger than the on-tape/disk run (but never much smaller), and is
quicksorted. The existing "merge sort" case similarly is only used
when the caller specified !randomAccess.

Hmm. You don't really need to merge the in-memory array into the tape,
as you know that all the tuples in the in-memory must come after the
tuples already on the tape. You can just return all the tuples from the
tape first, and then all the tuples from the array.

So here's a shorter/different explanation of this optimization: When
it's time to perform the sort, instead of draining the in-memory heap
one tuple at a time to the last tape, you sort the heap with quicksort,
and pretend that the sorted heap belongs to the last tape, after all the
other tuples in the tape.

Some questions/thoughts on that:

Isn't that optimization applicable even when you have multiple runs?
Quicksorting the heap and keeping it as an array in memory is surely
always faster than heapsorting and pushing it to the tape.

I think it'd make sense to structure the code differently, to match the
way I described this optimization above. Instead of adding a new
tuplesort state for this, abstract this in the logical tape code. Add a
function to attach an in-memory "tail" to a tape, and have
LogicalTapeRead() read from the tail after reading the on-disk tape. The
rest of the code wouldn't need to care that sometimes part of the tape
is actually in memory.

It should be pretty easy to support randomAccess too. If you think of
the in-memory heap as a tail of the last tape, you can easily move
backwards from the in-memory heap back to the on-disk tape, too.

+	 * Note that there might actually be 2 runs, but only the
+	 * contents of one of them went to tape, and so we can
+	 * safely "pretend" that there is only 1 run (since we're
+	 * about to give up on the idea of the memtuples array being
+	 * a heap).  This means that if our sort happened to require
+	 * random access, the similar "single run" optimization
+	 * below (which sets TSS_SORTEDONTAPE) might not be used at
+	 * all.  This is because dumping all tuples out might have
+	 * forced an otherwise equivalent randomAccess case to
+	 * acknowledge a second run, which we can avoid.

Is that really true? We don't start a second run until we have to, i.e.
when it's time to dump the first tuple of the second run to tape. So I
don't think the case you describe above, where you have two runs but
only one of them has tuples on disk, can actually happen.

Performance
==========

Impressive!

Predictability
==========

Even more impressive!

Future work
=========

As an extra optimization, you could delay quicksorting the in-memory
array until it's time to read the first tuple from it. If the caller
reads only the top-N tuples from the sort for some reason (other than
LIMIT, which we already optimize for), that could avoid a lot of work.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 30 July 2015 at 08:00, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Hmm. You don't really need to merge the in-memory array into the tape, as
you know that all the tuples in the in-memory must come after the tuples
already on the tape. You can just return all the tuples from the tape
first, and then all the tuples from the array.

Agreed

This is a good optimization for the common case where tuples are mostly
already in order. We could increase the usefulness of this by making UPDATE
pick blocks that are close to a tuple's original block, rather than putting
them near the end of a relation.

So here's a shorter/different explanation of this optimization: When it's
time to perform the sort, instead of draining the in-memory heap one tuple
at a time to the last tape, you sort the heap with quicksort, and pretend
that the sorted heap belongs to the last tape, after all the other tuples
in the tape.

Some questions/thoughts on that:

Isn't that optimization applicable even when you have multiple runs?
Quicksorting the heap and keeping it as an array in memory is surely always
faster than heapsorting and pushing it to the tape.

It's about use of memory. If you have multiple runs on tape, then they will
need to be merged and you need memory to do that efficiently. If there are
tuples in the last batch still in memory then it can work, but it depends
upon how full memory is from the last batch and how many batches there are.

--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/&gt;
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 07/30/2015 01:47 PM, Simon Riggs wrote:

On 30 July 2015 at 08:00, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

So here's a shorter/different explanation of this optimization: When it's
time to perform the sort, instead of draining the in-memory heap one tuple
at a time to the last tape, you sort the heap with quicksort, and pretend
that the sorted heap belongs to the last tape, after all the other tuples
in the tape.

Some questions/thoughts on that:

Isn't that optimization applicable even when you have multiple runs?
Quicksorting the heap and keeping it as an array in memory is surely always
faster than heapsorting and pushing it to the tape.

It's about use of memory. If you have multiple runs on tape, then they will
need to be merged and you need memory to do that efficiently. If there are
tuples in the last batch still in memory then it can work, but it depends
upon how full memory is from the last batch and how many batches there are.

True, you need a heap to hold the next tuple from each tape in the merge
step. To avoid exceeding work_mem, you'd need to push some tuples from
the in-memory array to the tape to make room for that. In practice,
though, the memory needed for the merge step's heap is tiny. Even if you
merge 1000 tapes, you only need memory for 1000 tuples in the heap. But
yeah, you'll need some logic to share/divide the in-memory array between
the heap and the "in-memory tail" of the last tape.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Thu, Jul 30, 2015 at 12:09 PM, Heikki Linnakangas <hlinnaka@iki.fi>
wrote:

True, you need a heap to hold the next tuple from each tape in the merge
step. To avoid exceeding work_mem, you'd need to push some tuples from the
in-memory array to the tape to make room for that. In practice, though, the
memory needed for the merge step's heap is tiny. Even if you merge 1000
tapes, you only need memory for 1000 tuples in the heap. But yeah, you'll
need some logic to share/divide the in-memory array between the heap and
the "in-memory tail" of the last tape.

It's a bit worse than that because we buffer up a significant chunk of the
tape to avoid randomly seeking between tapes after every tuple read. But I
think in today's era of large memory we don't need anywhere near the entire
work_mem just to buffer to avoid random access. Something simple like a
fixed buffer size per tape probably much less than 1MB/tape.

I'm a bit confused where the big win comes from though. Is what's going on
that the external sort only exceeded memory by a small amount so nearly
all the tuples are still in memory?

--
greg

On 30 July 2015 at 12:26, Greg Stark <stark@mit.edu> wrote:

On Thu, Jul 30, 2015 at 12:09 PM, Heikki Linnakangas <hlinnaka@iki.fi>
wrote:

True, you need a heap to hold the next tuple from each tape in the merge
step. To avoid exceeding work_mem, you'd need to push some tuples from the
in-memory array to the tape to make room for that. In practice, though, the
memory needed for the merge step's heap is tiny. Even if you merge 1000
tapes, you only need memory for 1000 tuples in the heap. But yeah, you'll
need some logic to share/divide the in-memory array between the heap and
the "in-memory tail" of the last tape.

It's a bit worse than that because we buffer up a significant chunk of the
tape to avoid randomly seeking between tapes after every tuple read. But I
think in today's era of large memory we don't need anywhere near the entire
work_mem just to buffer to avoid random access. Something simple like a
fixed buffer size per tape probably much less than 1MB/tape.

MERGE_BUFFER_SIZE is currently 0.25 MB, but there was benefit seen above
that. I'd say we should scale that up to 1 MB if memory allows.

Yes, that could be tiny for small number of runs. I mention it because
Heikki's comment that we could use this in the general case would not be
true for larger numbers of runs. Number of runs decreases quickly with more
memory anyway, so the technique is mostly good for larger memory but
certainly not for small memory allocations.

--
Simon Riggs http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/&gt;
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On Wed, Jul 29, 2015 at 9:05 PM, Peter Geoghegan <pg@heroku.com> wrote:

The behavior of external sorts that do not require any merge step due
to only having one run (what EXPLAIN ANALYZE output shows as an
"external sort", and not a "merge sort") seems like an area that can
be significantly improved upon. As noted in code comments, this
optimization did not appear in The Art of Computer Programming, Volume
III. It's not an unreasonable idea, but it doesn't work well on modern
machines due to using heapsort, which is known to use the cache
ineffectively. It also often implies significant additional I/O for
little or no benefit. I suspect that all the reports we've heard of
smaller work_mem sizes improving sort performance are actually down to
this one-run optimization *hurting* performance.

Very interesting. And great performance numbers. Thanks for taking
the time to investigate this - really cool.

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

On Thu, Jul 30, 2015 at 12:00 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Hmm. You don't really need to merge the in-memory array into the tape, as
you know that all the tuples in the in-memory must come after the tuples
already on the tape. You can just return all the tuples from the tape first,
and then all the tuples from the array.

It's more complicated than it appears, I think. Tuples may be variable
sized. WRITETUP() performs a pfree(), and gives us back a variable
amount of availMem. What if we dumped a single, massive, outlier tuple
out when a caller passes it and it goes to the root of the heap? We'd
dump that massive tuple in one go (this would be an incremental
dumptuples() call, which we still do in the patch), making things
!LACKMEM() again, but by an usually comfortable margin. We read in a
few more regular tuples, but we're done consuming tuples before things
ever get LACKMEM() again (no more dumping needed, at least with this
patch applied).

What prevents the tuple at the top of the in-memory heap at the point
of tuplesort_performsort() (say, one of the ones added to the heap as
our glut of memory was *partially* consumed) being less than the
last/greatest tuple on tape? If the answer is "nothing", a merge step
is clearly required.

This is not a problem when every single tuple is dumped, but that
doesn't happen anymore. I probably should have shown more tests, that
tested HeapTuple sorts (not just datum tuple sorts). I agree that
things at least usually happen as you describe, FWIW.

I think it'd make sense to structure the code differently, to match the way
I described this optimization above. Instead of adding a new tuplesort state
for this, abstract this in the logical tape code. Add a function to attach
an in-memory "tail" to a tape, and have LogicalTapeRead() read from the tail
after reading the on-disk tape. The rest of the code wouldn't need to care
that sometimes part of the tape is actually in memory.

I'll need to think about all of that. Certainly, quicksorting runs in
a more general way seems like a very promising idea, and I know that
this patch does not go far enough. But it also add this idea of not
dumping out most tuples, which seems impossible to generalize further,
so maybe it's a useful special case to start from for that reason (and
also because it's where the pain is currently felt most often).

+        * Note that there might actually be 2 runs, but only the
+        * contents of one of them went to tape, and so we can
+        * safely "pretend" that there is only 1 run (since we're
+        * about to give up on the idea of the memtuples array being
+        * a heap).  This means that if our sort happened to require
+        * random access, the similar "single run" optimization
+        * below (which sets TSS_SORTEDONTAPE) might not be used at
+        * all.  This is because dumping all tuples out might have
+        * forced an otherwise equivalent randomAccess case to
+        * acknowledge a second run, which we can avoid.

Is that really true? We don't start a second run until we have to, i.e. when
it's time to dump the first tuple of the second run to tape. So I don't
think the case you describe above, where you have two runs but only one of
them has tuples on disk, can actually happen.

I think we're talking about two slightly different things. I agree
that I am avoiding "starting" a second run because I am avoiding
dumping tuples, just as you say (I describe this as avoiding
"acknowledging" a second run). But there could still be SortTuples
that have a tupindex that is > 0 (they could be 1, to be specific).
It's pretty clear from looking at the TSS_BUILDRUNS case within
puttuple_common() that this is true. So, if instead you define
"starting" a tuple as adding a sortTuple with a tupindex that is > 0,
then yes, this comment is true.

The important thing is that since we're not dumping every tuple, it
doesn't matter whether or not a that TSS_BUILDRUNS case within
puttuple_common() ever took the "currentRun + 1" insertion path (which
can easily happen), provided things aren't so skewed that it ends up
on tape even without dumping all tuples (which seems much less
likely). As I've said, this optimization will occur a lot more often
then the existing one run optimization (assuming !randomAccess), as a
nice side benefit of not dumping every tuple. Quicksort does not use
HEAPCOMPARE(), so clearly having multiple runs in that "subrun" is a
non-issue.

Whether or not we say that a second run "started", or that there was
merely the "unfulfilled intent to start a new, second run" is just
semantics. While I certainly care about semantics, my point is that we
agree that this useful "pretend there is only one run" thing happens
(I think). The existing one run optimization only really occurs when
the range of values in the set of tuples is well characterized by the
tuple values observed during initial heapification, which is bad. Or
would be bad, if the existing optimization was good. :-)

Performance
==========

Impressive!

Predictability
==========

Even more impressive!

Thanks!

As an extra optimization, you could delay quicksorting the in-memory array
until it's time to read the first tuple from it. If the caller reads only
the top-N tuples from the sort for some reason (other than LIMIT, which we
already optimize for), that could avoid a lot of work.

Won't comment on that yet, since it's predicated on the merge step
being unnecessary. I need to think about this some more.

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

On Thu, Jul 30, 2015 at 11:32 AM, Robert Haas <robertmhaas@gmail.com> wrote:

Very interesting. And great performance numbers. Thanks for taking
the time to investigate this - really cool.

Thanks.

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

On Thu, Jul 30, 2015 at 4:26 AM, Greg Stark <stark@mit.edu> wrote:

I'm a bit confused where the big win comes from though. Is what's going on
that the external sort only exceeded memory by a small amount so nearly all
the tuples are still in memory?

Yes, that's why this can be much faster just as the work_mem threshold
is crossed. You get an "almost internal" sort, which means you can
mostly quicksort, and you can avoid dumping most tuples. It's still a
pretty nice win when less than half of tuples fit in memory, though --
just not as nice. Below that, the optimization isn't used.

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

On Thu, Jul 30, 2015 at 3:47 AM, Simon Riggs <simon@2ndquadrant.com> wrote:

This is a good optimization for the common case where tuples are mostly
already in order. We could increase the usefulness of this by making UPDATE
pick blocks that are close to a tuple's original block, rather than putting
them near the end of a relation.

Not sure what you mean here.

So here's a shorter/different explanation of this optimization: When it's
time to perform the sort, instead of draining the in-memory heap one tuple
at a time to the last tape, you sort the heap with quicksort, and pretend
that the sorted heap belongs to the last tape, after all the other tuples in
the tape.

Some questions/thoughts on that:

Isn't that optimization applicable even when you have multiple runs?
Quicksorting the heap and keeping it as an array in memory is surely always
faster than heapsorting and pushing it to the tape.

It's about use of memory. If you have multiple runs on tape, then they will
need to be merged and you need memory to do that efficiently. If there are
tuples in the last batch still in memory then it can work, but it depends
upon how full memory is from the last batch and how many batches there are.

I agree that this optimization has a lot to do with exploiting the
fact that you don't need to free the memtuples array for future runs
because you've already received all tuples (or keep space free for
previous runs). I think that we should still use quicksort on runs
where this optimization doesn't work out, but I also still think that
that's a different idea. Doing what I've proposed here when there are
multiple runs seems less valuable, if only because you're not going to
avoid that much writing.

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

On Thu, Jul 30, 2015 at 4:01 PM, Peter Geoghegan <pg@heroku.com> wrote:

On Thu, Jul 30, 2015 at 12:00 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Hmm. You don't really need to merge the in-memory array into the tape, as
you know that all the tuples in the in-memory must come after the tuples
already on the tape. You can just return all the tuples from the tape first,
and then all the tuples from the array.

It's more complicated than it appears, I think. Tuples may be variable
sized. WRITETUP() performs a pfree(), and gives us back a variable
amount of availMem. What if we dumped a single, massive, outlier tuple
out when a caller passes it and it goes to the root of the heap? We'd
dump that massive tuple in one go (this would be an incremental
dumptuples() call, which we still do in the patch), making things
!LACKMEM() again, but by an usually comfortable margin. We read in a
few more regular tuples, but we're done consuming tuples before things
ever get LACKMEM() again (no more dumping needed, at least with this
patch applied).

What prevents the tuple at the top of the in-memory heap at the point
of tuplesort_performsort() (say, one of the ones added to the heap as
our glut of memory was *partially* consumed) being less than the
last/greatest tuple on tape? If the answer is "nothing", a merge step
is clearly required.

It's simple to prove this with the attached rough patch, intended to
be applied on top of Postgres with my patch. It hacks
tuplesort_gettuple_common() to always return tape tuples first, before
returning memtuples only when tape tuples have been totally exhausted.
If you run my cursory regression test suite with this, you'll see
serious regressions. I also attach a regression test diff file from my
development system, to save you the trouble of trying this yourself.
Note how the "count(distinct(s))" numbers get closer to being correct
(lower) as work_mem increases make tuplesort approach an internal
sort.

It's possible that we can get away with something cheaper than a merge
step, but my impression right now is that it isn't terribly expensive.
OTOH, if we can make this work with the randomAccess case by being
more clever about merging, that could be worthwhile.
--
Peter Geoghegan

On 07/31/2015 02:01 AM, Peter Geoghegan wrote:

What prevents the tuple at the top of the in-memory heap at the point
of tuplesort_performsort() (say, one of the ones added to the heap as
our glut of memory was*partially* consumed) being less than the
last/greatest tuple on tape? If the answer is "nothing", a merge step
is clearly required.

Oh, ok, I was confused on how the heap works. You could still abstract
this as "in-memory tails" of the tapes, but it's more complicated than I
thought at first:

When it's time to drain the heap, in performsort, divide the array into
two arrays, based on the run number of each tuple, and then quicksort
the arrays separately. The first array becomes the in-memory tail of the
current tape, and the second array becomes the in-memory tail of the
next tape.

You wouldn't want to actually allocate two arrays and copy SortTuples
around, but keep using the single large array, just logically divided
into two. So the bookkeeping isn't trivial, but seems doable.

Hmm, I can see another possible optimization here, in the way the heap
is managed in TSS_BUILDRUNS state. Instead of keeping a single heap,
with tupindex as the leading key, it would be more cache efficient to
keep one heap for the currentRun, and an unsorted array of tuples
belonging to currentRun + 1. When the heap becomes empty, and currentRun
is incemented, quicksort the unsorted array to become the new heap.

That's a completely separate idea from your patch, although if you did
it that way, you wouldn't need the extra step to divide the large array
into two, as you'd maintain that division all the time.

- Heikki

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 30/07/15 02:05, Peter Geoghegan wrote:

Since heapification is now a big fraction of the total cost of a sort
sometimes, even where the heap invariant need not be maintained for
any length of time afterwards, it might be worth revisiting the patch
to make that an O(n) rather than a O(log n) operation [3].

O(n log n) ?

Heapification is O(n) already, whether siftup (existing) or down.

It might be worthwhile comparing actual times with a quicksort, given
that a sorted array is trivially a well-formed heap (the reverse is not
true) and that quicksort seems to be cache-friendly. Presumably there
will be a crossover N where the cache-friendliness k reduction
loses out to the log n penalty for doing a full sort; below this
it would be useful.

You could then declare the tape buffer to be the leading tranche of
work-mem (and dump it right away) and the heap to start with the
remainder.
--
Cheers,
Jeremy

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:

Heapification is O(n) already, whether siftup (existing) or down.

That's not my impression, or what Wikipedia says. Source?

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

On 31/07/15 18:31, Robert Haas wrote:

On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:

Heapification is O(n) already, whether siftup (existing) or down.

That's not my impression, or what Wikipedia says. Source?

Measurements done last year:

/messages/by-id/52F35462.3030306@wizmail.org
(spreadsheet attachment)

/messages/by-id/52F40CE9.1070509@wizmail.org
(measurement procedure and spreadsheet explanation)

--
Cheers,
Jeremy

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On 2015-07-31 13:31:54 -0400, Robert Haas wrote:

On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:

Heapification is O(n) already, whether siftup (existing) or down.

That's not my impression, or what Wikipedia says. Source?

Building a binary heap via successive insertions is O(n log n), but
building it directly is O(n). Looks like wikipedia agrees too
https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap
I'm pretty sure that there's a bunch of places where we intentionally
build a heap at once instead successively. At least reorderbuffer.c does
so, and it looks like nodeMergeAppend as well (that's why they use
binaryheap_add_unordered and then binaryheap_build).

Greetings,

Andres Freund

--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

On Fri, Jul 31, 2015 at 12:59 AM, Heikki Linnakangas <hlinnaka@iki.fi> wrote:

Oh, ok, I was confused on how the heap works. You could still abstract this
as "in-memory tails" of the tapes, but it's more complicated than I thought
at first:

When it's time to drain the heap, in performsort, divide the array into two
arrays, based on the run number of each tuple, and then quicksort the arrays
separately. The first array becomes the in-memory tail of the current tape,
and the second array becomes the in-memory tail of the next tape.

You wouldn't want to actually allocate two arrays and copy SortTuples
around, but keep using the single large array, just logically divided into
two. So the bookkeeping isn't trivial, but seems doable.

Since you're talking about the case where we must drain all tuples
within tuplesort_performsort(), I think you're talking about a
distinct idea here (since surely you're not suggesting giving up on my
idea of avoiding dumping most tuples, which is a key strength of the
patch). That's fine, but I just want to be clear on that. Importantly,
my optimization does not care about the fact that the array may have
two runs in it, because it quicksorts the array and forgets about it
being a heap. It only cares whether or not more than one run made it
out to tape, which makes it more widely applicable than it would
otherwise be. Also, the fact that much I/O can be avoided is clearly
something that can only happen when work_mem is at least ~50% of a
work_mem setting that would have resulted in an (entirely) internal
sort.

You're talking about a new thing here, that happens when it is
necessary to dump everything and do a conventional merging of on-tape
runs. IOW, we cannot fit a significant fraction of overall tuples in
memory, and we need much of the memtuples array for the next run
(usually this ends as a TSS_FINALMERGE). That being the case
(...right?), I'm confused that you're talking about doing something
clever within tuplesort_performsort(). In the case you're targeting,
won't the vast majority of tuple dumping (through calls to
dumptuples()) occur within puttuple_common()?

I think that my optimization should probably retain it's own
state.status even if we do this (i.e. TSS_MEMTAPEMERGE should stay).

Hmm, I can see another possible optimization here, in the way the heap is
managed in TSS_BUILDRUNS state. Instead of keeping a single heap, with
tupindex as the leading key, it would be more cache efficient to keep one
heap for the currentRun, and an unsorted array of tuples belonging to
currentRun + 1. When the heap becomes empty, and currentRun is incemented,
quicksort the unsorted array to become the new heap.

That's a completely separate idea from your patch, although if you did it
that way, you wouldn't need the extra step to divide the large array into
two, as you'd maintain that division all the time.

This sounds to me like a refinement of your first idea (the idea that
I just wrote about).

I think the biggest problem with tuplesort after this patch of mine is
committed is that it is still too attached to the idea of
incrementally spilling and sifting. It makes sense to some degree
where it makes my patch possible...if we hang on to the idea of
incrementally spilling tuples on to tape in sorted order for a while,
then maybe we can hang on for long enough to quicksort most tuples,
*and* to avoid actually dumping most tuples (incremental spills make
the latter possible). But when work_mem is only, say, 10% of the
setting required for a fully internal sort, then the incremental
spilling and sifting starts to look dubious, at least to me, because
the TSS_MEMTAPEMERGE optimization added by my patch could not possibly
apply, and dumping and merging many times is inevitable.

What I think you're getting at here is that we still have a heap, but
we don't use the heap to distinguish between tuples within a run. In
other words, HEAPCOMPARE() often/always only cares about run number.
We quicksort after a deferred period of time, probably just before
dumping everything. Perhaps I've misunderstood, but I don't see much
point in quicksorting a run before being sure that you're sorting as
opposed to heapifying at that point (you're not clear on what we've
decided on once we quicksort). I think it could make sense to make
HEAPCOMPARE() not care about tuples within a run that is not
currentRun, though.

I think that anything that gives up on replacement selection's ability
to generate large runs, particularly for already sorted inputs will be
too hard a sell (not that I think that's what you proposed). That's
way, way less of an advantage than it was in the past (back when
external sorts took place using actual magnetic tape, it was a huge),
but the fact remains that it is an advantage. And so, I've been
prototyping an approach where we don't heapify once it is established
that this TSS_MEMTAPEMERGE optimization of mine cannot possibly apply.
We quicksort in batches rather than heapify.

With this approach, tuples are just added arbitrarily to the memtuples
array when status is TSS_BUILDRUNS and we decided not to heapify. When
this path is first taken (when we first decide not to heapify
memtuples anymore), we quicksort and dump the first half of memtuples
in a batch. Now, when puttuple_common() once again fills the first
half of memtuples (in the style of TSS_INITIAL), we quicksort again,
and dump the first half again. Repeat until done.

This is something that you could perhaps call "batch replacement
selection". This is not anticipated to affect the finished runs one
bit as compared to tuplesort today, because we still create a new run
(state->currentRun++) any time a value in a now-sorted batch is less
than the last (greatest) on-tape value in the currentRun. I am just
batching things -- it's the same basic algorithm with minimal use of a
heap.

I think this will help appreciably because we quicksort, but I'm not
sure yet. I think this may also help with introducing asynchronous I/O
(maybe we can reuse memtuples for that, with clever staggering of
stages during dumping, but that can come later). This is all fairly
hand-wavey, but I think it could help appreciably for the case where
sorts must produce runs to merge and avoiding dumping all tuples is
impossible.
--
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

On Sat, Aug 1, 2015 at 9:49 AM, Jeremy Harris <jgh@wizmail.org> wrote:

On 31/07/15 18:31, Robert Haas wrote:

On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:

Heapification is O(n) already, whether siftup (existing) or down.

That's not my impression, or what Wikipedia says. Source?

Measurements done last year:

/messages/by-id/52F35462.3030306@wizmail.org
(spreadsheet attachment)

/messages/by-id/52F40CE9.1070509@wizmail.org
(measurement procedure and spreadsheet explanation)

I don't think that running benchmarks is the right way to establish
the asymptotic runtime of an algorithm. I mean, if you test
quicksort, it will run in much less than O(n^2) time on almost any
input. But that does not mean that the worst-case run time is
anything other than O(n^2).

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

On Sat, Aug 1, 2015 at 9:56 AM, Andres Freund <andres@anarazel.de> wrote:

On 2015-07-31 13:31:54 -0400, Robert Haas wrote:

On Fri, Jul 31, 2015 at 7:21 AM, Jeremy Harris <jgh@wizmail.org> wrote:

Heapification is O(n) already, whether siftup (existing) or down.

That's not my impression, or what Wikipedia says. Source?

Building a binary heap via successive insertions is O(n log n), but
building it directly is O(n). Looks like wikipedia agrees too
https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap

That doesn't really address the sift-up vs. sift-down question. Maybe
I'm just confused about the terminology. I think that Wikipedia
article is saying that if you iterate from the middle element of an
unsorted array towards the beginning, establishing the heap invariant
for every item as you reach it, you will take only O(n) time. But
that is not what inittapes() does. It instead starts at the beginning
of the array and inserts each element one after the other. If this is
any different from building the heap via successive insertions, I
don't understand how.

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