On Mon, Aug 3, 2015 at 3:33 PM, Peter Geoghegan <p...@heroku.com> wrote: >> 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. > > 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 don't think that's what Heikki is talking about. He can correct me if I'm wrong, but what I think he's saying is that we should try to exploit the fact that we've already determined which in-memory tuples can be part of the current run and which in-memory tuples must become part of the next run. Suppose half the tuples in memory can become part of the current run and the other half must become part of the next run. If we throw all of those tuples into a single bucket and quicksort it, we're losing the benefit of the comparisons we did to figure out which tuples go in which runs. Instead, we could quicksort the current-run tuples and, separately, quick-sort the next-run tuples. Ignore the current-run tuples completely until the tape is empty, and then merge them with any next-run tuples that remain. I'm not sure if there's any reason to believe that would be faster than your approach. In general, sorting is O(n lg n) so sorting two arrays that are each half as large figures to be slightly faster than sorting one big array. But the difference may not amount to much. -- 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