Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

On Fri, Feb 10, 2012 at 10:30 AM, Peter Geoghegan  wrote:
> [ new patch ]

I spent quite a bit of time looking at this today - the patch
specifically, and the issue of making quicksort fast more generally.
It seemed to me that if we're going to have separate copies of the
quicksort code for tuple sorting, we might as well go whole hog and
specialize those copies to the particular needs of tuplesort.c as much
as possible.  Accordingly, I whacked the code around so that it knows
that it is sorting SortTuple objects and need not conditionalize at
runtime on the size of the objects being swapped.  You suggested
upthread that this might be worthwhile, and it seems that it is, so I
think we should do it.

Your patch removes the CHECK_FOR_INTERRUPTS() call from
comparetup_heap, which is no good.  However, since I'd already decided
to specialize the copies of quicksort intended for sorting as much as
possible, it made sense to me to refactor things so that the qsort
routine itself, rather than the comparator, is responsible for calling
CHECK_FOR_INTERRUPTS().  This slightly reduces the number of times we
CHECK_FOR_INTERRUPTS(), but never allows more than a few comparisons
before doing it.

I find that your pg_always_inline macro is equivalent to just plain
inline on my system (MacOS X v10.6.8, gcc 4.2.1).  It seems to need
something like this:

+#elif __GNUC__
+#define pg_always_inline inline __attribute__((always_inline))

...but I'm not very happy about relying on that, because I don't know
that it will work on every gcc version (never mind non-gcc compilers),
and I'm not convinced it's actually improving performance even on this
one.  The documentation seems to indicate that this is intended to
force inlining even when not optimizing, which may have something to
do with the lack of effect: that's not really the point here anyway.
What I did instead is to replace template_qsort_arg.h with a script
called gen_qsort_tuple.pl, which generates a file called qsort_tuple.c
that tuplesort.c then #includes.  This seems more flexible to me than
the macro-based approach.  In particular, it allows me to generate
versions of qsort with different call signatures.  The attached patch
generates two:

static void qsort_tuple(SortTuple *a, size_t n, SortTupleComparator
cmp_tuple, Tuplesortstate *state);
static void qsort_ssup(SortTuple *a, size_t n, SortSupport ssup);

The first of these is a drop-in replacement for qsort_arg() - any
tuplesort can use it, not just heap sorts.  But it is faster than
qsort_arg() because of the specializations for the SortTuple data
type.  The second handles the special case where we are sorting by a
single key that has an associated SortSupport object.  In this case we
don't need to carry the overhead of passing around the Tuplesortstate
and dereferencing it, nor do we need the SortTupleComparator: we can
just pass the SortSupport itself.  Maybe there's a way to get this
effect using macros, but I couldn't figure it out.  At any rate, at
least for the single-key case, this approach effectively forces the
comparator to be inlined without requiring pg_always_inline.

With this patch, I get the following results, as compared with your
2012-02-10 version and master, using the same test cases I tested
before.

select * from nodups order by g offset 10001;
tps on master: 289.471274, 289.967984, 289.595958
tps on 2012-02-10 version: 359.150280, 356.284723, 356.888900
tps on attached version: 388.212793, 386.085083, 386.867478

select * from twocol order by a, b offset 10000;
tps on master: 261.676611, 260.440886, 259.529362
tps on 2012-02-10 version: 283.941312, 279.981723, 283.140208
tps on attached version: 283.146463, 278.344827, 280.727798

select * from f8 order by g offset 10000;
tps on master: 228.299924, 222.650355, 227.408506
tps on 2012-02-10 version: 260.289273, 257.181035, 256.377456
tps on attached version: 276.985299, 275.341575, 274.428095

There's some variation (which I can't account for) between the results
on master now and the results on master before - possibly just code
shifting around between cache lines due to unrelated changes, or maybe
some inadvertent change in my test setup.  But it looks to me like
your 2012-02-10 version, without any type-specific optimizations, does
pretty much just as well on multi-key sorting as your previous
version, which had them - or if there is a difference, it's pretty
small.

Overall, I think the numbers for the version I'm attaching here look
pretty good: the single-key performance is clearly better than your
last version, and the multi-key performance is very slightly worse.  I
think that slight worsening is a good trade-off, though, because this
version can use qsort_tuple() for all kinds of tuplesorts, not just
heap tuplesorts.  Still, it seems like we ought to be able to do even
better: the multi-key specialization that you had in your patch can be
coded in this framework, too, and in theory those are ndependent of
the swapcode improvements.  I tried coding up a multi-key
specialization which I believe to be quite similar to what you did,
but it didn't seem to do much.  I'm attaching it here; maybe there's
some way to improve it (or a different test case where it pays off).

It strikes me that if we wanted to take this further, we could look at
squeezing out ApplySortComparator.  For example, suppose that, upon
discovering that we can do an in-memory quicksort on a single sort
key, we make an initial pass over the data where we check whether it's
sorted and, as we go, swap all the entries with isnull1 = true to the
end of the memtuples array.  We then sort the isnull1 = true entries
with the standard comparator, and the isnull1 = false entries with an
optimized comparator that elides most of ApplySortComparator and
instead just calls the comparison function directly.  We then decide
on whether to emit the isnull1 = true entries first or last based on
NULLS FIRST/LAST, and decide whether to emit the remaining entries in
forward or reverse order based on ASC/DESC.  Or maybe not exactly that
thing, but something like that, so that we sort the null and non-null
entries separately.  The additional complexity in the read-out logic
would probably be more than offset by being able to use a simpler
comparator.

What do you think of this version?

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

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

On 9 February 2012 14:51, Robert Haas  wrote:
> I'm not sure I entirely follow all this, but I'll look at the code
> once you have it.

I have attached a revision of the patch, with the adjustments already
described. Note that I have not made this support btree tuplesorting
yet, as there is an impedance mismatch that must be resolved,
particularly with the SortSupport stuff, and I wanted to know what you
think of the multiple key specialisation first. Arguably, we could get
away with only a single specialisation - I haven't really though about
it much.

You say "Well, how often will we sort 10,000 integers?", and I think
that btree index creation is one very common and useful case, so I'd
like to look at that in more detail. I certainly don't see any reason
to not do it too.

This should give you performance for sorting multiple-keys that is
almost as good as the single-key optimisation that you found to be
more compelling. Obviously the need to actually call comparetup_heap
to look at non-leading sortkeys will vary from case to case, and this
is based on your test case, where there are no duplicates and thus no
need to ever do that. That isn't too far from representative, as I
think that in general, a majority of comparisons won't result in
equality.

-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

On 6 January 2012 21:47, Robert Haas  wrote:
> On Fri, Jan 6, 2012 at 4:14 PM, Tom Lane  wrote:
>> Admittedly, I don't have any numbers quantifying just how useful that
>> might be, but on the other hand you've not presented any evidence
>> justifying removing the behavior either.  If we believe your position
>> that indexes don't generally have lots of duplicates, then the code in
>> question will seldom be reached and therefore there would be no
>> performance benefit in removing it.

I have decided on a tactical retreat in relation to this patch. This
has been dragging on since September. I cannot risk not having the
patch accepted for 9.2, due to trying to handle both heap and btree
tuple sorting at once - the additional relatively modest improvements
for common cases that it will bring to btree index creation time do
not warrant digging my heels in to cover that case in one larger
commit. For that reason, I attach for your consideration a revision of
the patch without any support for btree index tuples whatsoever
(though I have adjusted btree tuplesort comments, and one tiny piece
of code, in a non-controversial way). I'll revisit btree sorting
towards the end of the commitfest, circumstances permitting.

As to the question of binary bloat, I have devised a pgbench-tools
workload that I think will go some way towards reassuring those who
are concerned about its distributed costs. The attached spreadsheet
has all the relevant details.

A custom scripts has been specified (details of which are evident from
benchmark results themselves). If we experienced some kind of
noticeable marginalisation of usefully cached instructions, that's
obviously where it'll show up.

Note that I have taken the preparatory step of updating some tables
with random data, rather than the sequential data that they have by
default, which, unusually for such large tables, can allow us to avail
of our pre-sorted input check optimisation, spoiling things. I did
vacuumdb immediately afterwards, immediately before the pgbench run in
each case.

I've kept the test at 8 clients/8 threads, on a machine with 4
physical cores + hyperthreading for 8 logical ("Intel Core(TM) i7 CPU
870  @ 2.93GHz", with 4 x 32 KB instruction caches, among several
other CPU caches) on a newly-initialised, throw-away database, single
run at scale 50 for 15 minutes in all cases. This is the same server
that I have used throughout.

My analysis is that although there may be a very slight regression in
non-affected queries (it's a tough call to make - how queries happen
to coincide undoubtedly muddies the waters, as does the fact that we
cut lots of time from periods in which backends hold a lot of locally
allocated sort memory - it might actually be a win for those other
queries sometimes but not others, and it appears that the margin
either way is very small), that is more than compensated for by the
benefit of the specialisations. The CPU cache is doing its fjob as
expected, and we clearly see a net benefit from its preference for
cacheing more instructions that are specialised - those sort
operations are way more expensive (if they weren't, it wouldn't cache
them so heavily). I also include results for running the same query
again and again with a single client, to put that effect in context
(though note that previous benchmarks avoiding paying a high client
overhead by using explain analyze, and indeed originally compared
pre-SortSupport Postgres, so these numbers aren't as good either).
It's unusual for a database workload to be so heavily CPU bound, so
I'd suggest that the latter benchmark is more representative than the
former. Either way, we win by some margin. If the queries didn't have
such a high client overhead, as for example with a sort node that
feeds a merge join, we'd do better still.

If a sorting specialisation is never used anyway, the overhead, for
practical purposes, is zero. I believe that sorting specialisations
are just too useful to not be a net win in almost all reasonable
cases. Why haven't I used all specialisations at once, rather than
only two (one for single int4, the other multiple)? Well, I might have
used all of them, but there was no floats available in the pgbench
tables, and besides, the chances of all of them being simultaneously
in play during any sufficiently short period for marginalisation of
CPU cache contents to be of particular concern is, in general, not all
that great.

A major systems programming language, C++, produces multiple
specialisations as its standard library's sort function is used, for
example, each of which will have separate entries in the procedure
linkage table (though various implementation-defined techniques are
frequently used to reduce the number of copies across translation
units at link time). If the programmer specifies either a different
datatype, or a different comparator (through the use of an alternative
to the default std::less_than functor/predicate), a whole new
specialisation is generated by the compiler. This does raise concerns
in relation to binary bloat, but they're reasonably well understood,
and this is the default way of doing things, for general purpose
application development. Now, I know that Postgres isn't written in
C++, and you might not find "C++ does it" to be a particularly
compelling argument, but it does go to show that these ideas are not
by any stretch of the imagination radical.

I remind everyone that the improvement seen in raw qsort_arg runtime
is fairly large, as it would have to be, in order to bring such large
though proportionally smaller improvements to each given affected
query as a whole - there are of course many other sources of overhead
involved in parsing, planning and executing affected queries.

Here is a complete detailing of the specialisations that this latest
revision produces:

int4, single key (supports date too)
int8, multiple keys (supports timestamps too, with and without TZ,
where we HAVE_INT64_TIMESTAMP)
float4, single key
float8, multiple keys
Type-generic single key specialisation. Expected to deliver some of
the same additional benefits for types that do not merit there own
specialisations but would still benefit, like name, int2, etc, but is
used all the time where applicable, even for types like text for which
it is expected that there will be no appreciable benefit.

Thoughts?
-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

On 30 December 2011 19:46, Merlin Moncure  wrote:
> On Thu, Dec 29, 2011 at 8:03 PM, Peter Geoghegan  wrote:
>> * A spreadsheet that shows the results of re-running my earlier heap
>> tuple sorting benchmark with this new patch. The improvement in the
>> query that orders by 2 columns is all that is pertinent there, when
>> considering the value of (1) and the sense in standing still for
>> controversy A.
>>
>> * A spreadsheet that shows the difference in index creation times,
>> generated with the help of the new python script.
>
> very nice.  let me save everyone the effort of opening his
> spreadsheets (which by the way both show 'HEAD/unoptimized' --
> probably not what you meant): he's showing a consistent ~50% reduction
> in running time of sort driven queries -- that's money.

Sorry, I think you may have misinterpreted the results, which is my
fault - I introduced a formatting error. In the case of the "btree"
spreadsheet, the first query on each sheet should be "create index
test on orderlines (prod_id);", and not "select * from orderlines
order by prod_id". The idea is to compare the results from each set of
binaries across pages of the spreadsheet (note that there are two
tabs). You should not compare anything between the two spreadsheets.
Revised btree results attached. The heap results that I posted do not
have any formatting errors, so they have not been revised.

-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

Progress on fast path sorting, btree index creation time

I'll try and keep this terse. I've promised to justify the number of
specialisations that are in my fast-path sorting patch, and I may yet
conclude that a reduction is appropriate. Not today though - there are
quite a few ideas in the patch (even more now), and not all have been
exhaustively evaluated. Maybe that isn't what some had hoped for right
now, but deferring publicly and definitively answering those questions
to focus on tweaking the patch has brought additional benefits. I felt
that I went too long without checking in with the community though.
The purpose of this e-mail is to:

1. Report back a further improvement in the performance benefits seen
when sorting with multiple sortkeys. The performance benefits seen for
that case were previously relatively modest; they're better now.

2. Report improvements from applying these techniques to btree index
tuplesorting (short version: they're also quite good). The data used
is exactly the same as it was in my previous benchmark; orderlines is
1538MB, and has lots of duplicates. The environment is also identical.

3. Resolve two anticipated controversies that are, respectively,
somewhat orthogonal and completely orthogonal to the binary bloat
controversy. The first (controversy A) is that I have added a new
piece of infrastructure, pg_always_inline, which, as the name
suggests, is a portable way of insisting that a function should be
invariably inlined. Portable libraries like libc have been doing this
for a long time now, and I actually use the libc macro (that expands
to __attribute__((always_inline)) ) where possible. The second
possible point of contention (controversy B) is that I have jettisoned
various protections against bad qsort implementations that I believe
are a legacy of when we used the system qsort pre-2006, that can no
longer be justified. For example, quick sort performing badly in the
face of lots of duplicates is a well understood problem today
(partitioning should stop on equal keys), and ISTM that protecting
against that outside the qsort implementation (but only for index
sorts) is wrong-headed.

The first possibly controversial adjustment (controversy A) is clearly
also the reason for (1) - that has been well isolated. I haven't got
around to quantifying the performance improvement seen due to the
second possibly controversial adjustment (controversy B), but I
believe that it can be justified as a case of effectively removing
redundant code anyway. After all, we now assert against comparing a
tuple to itself anyway, and the "cheap insurance" that existed in
comparetup_index_btree was never present in any form in
comparetup_index_heap, and we heard no complaints, AFAIK.

Attached are:

* A detailing of libc's use of __always_inline /
__attribute__((always_inline)). Note that it often appears in code
that is built for all platforms.

* The WIP patch itself, rebased to integrate with the new SortSupport
infrastructure. I've gone a bit crazy with btree specialisations, but
I suspect that's where it matters least and makes most sense.

* A new Python script for bench marking index creation, that is
similar to the other one I previously posted for bench marking sorting
heap tuples.

* A spreadsheet that shows the results of re-running my earlier heap
tuple sorting benchmark with this new patch. The improvement in the
query that orders by 2 columns is all that is pertinent there, when
considering the value of (1) and the sense in standing still for
controversy A.

* A spreadsheet that shows the difference in index creation times,
generated with the help of the new python script.

Thoughts?

I had another idea when writing this patch that I haven't developed at
all but I'll share anyway. That is, it might be a good idea to use a
balance quicksort:

http://xlinux.nist.gov/dads//HTML/balancedqsrt.html

It might be possible to get a reasonable approximation of the actual
median value of a given column with existing statistics, which could
be hinted to qsort_arg. This would do a better job of guessing an
appropriate initial pivot value for qsort than the med3 sampling
technique (what we do now, advocated by Sedgewick: use the median of
the first, middle and last elements of the current partition), though
we'd still use that med3 technique to select all other pivots, and
perhaps signal to qsort_arg "you're on your own, fall back of med3 for
the initial pivot" with a null ptr, according to some heuristic.
There's obviously a not inconsiderable impedance mismatch to resolve
if we're to do that though, so that Tuplesortstate has a pointer to
the median SortTuple.

Can I get a straw poll on how much of a problem worst-case performance
of qsort is believed to be?

In a perfect world, if it were somehow possible to know the perfect
pivots ahead of time from a histogram or something, we'd have a quick
sort variant with worst-case performance of O(n log(n)). That, or the
limited approximation that I've sketched would perhaps be worthwhile,
even if it was subject to a number of caveats. Wikipedia claims that
the worst case for quick sort is O(n log(n)) with the refinements
recommended by Sedgewick's 1978 paper, but this seems like nonsense to
me - the med3 technique is a good heuristic in practice, but it's
perfectly possible in theory for it's sampling to always get things
completely wrong (this is not an unfamiliar problem). How often it
messes up in the real world and how much it matters is something that
I wouldn't like to speculate on, though it is the main factor that
will determine if the idea is worth pursuing. I can tell you that I
have heard one person observe that it had an unpredictable runtime.
However, they might not have noticed if this patch was applied,
because in general the worse quicksort does the better this patch
does. Also, the fact that we use a median of "medians" when n > 40
(Dr. Sedgewick again, if I'm not mistaken) makes me a little skeptical
of that claim. Come to think of it, it might not be a bad idea to add
a bunch of comments to qsort_arg while I have this swapped into my
head, as it currently has no comments at all.

While I'm thinking out loud, here's another idea: Have a GUC which,
when enabled (perhaps potentially at various different granularities),
makes Timsort the in-memory sorting algorithm, as it now is by default
for Python, Java SE7 (for arrays) and the Android platform; for
certain applications, this could be a real win, and I don't think that
it would have to be invasive: it could be dropped in.

-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

On 27 January 2012 14:37, Robert Haas  wrote:
> On Fri, Jan 27, 2012 at 9:27 AM, Peter Geoghegan  wrote:
>> Well, I don't think it's all that subjective - it's more the case that
>> it is just difficult, or it gets that way as you consider more
>> specialisations.
>
> Sure it's subjective.  Two well-meaning people could have different
> opinions without either of them being "wrong".  If you do a lot of
> small, in-memory sorts, more of this stuff is going to seem worthwhile
> than if you don't.

But if you don't, then you're not going to have your cache
compromised, so the cost is limited to having to store a few tens of
kilobytes of extra binary executable data on disk, and perhaps
main-memory, that you wouldn't otherwise have to - a cost that is
virtually indistinguishable from zero. When you do eventually need to
do some in-memory sort, you get to have that go significantly faster,
and since you don't have much use for the specialisations anyway, you
get that with essentially no down-side.

The concern is a perfect storm of all specialisations being
simultaneously used such that it'd be more efficient to use a generic
qsort. I think that's pretty implausible - the general assumption is
that database applications are not frequently CPU bound. They're
assumed to be frequently memory-bound though, so any effort to reduced
memory consumption - which this patch effectively does - is probably
going to be more valuable.

Even if we suppose that the perfect storm can and does occur, on a
chip that is so starved of instruction cache that it turns out to be a
net loss, surely even then the perfect storm is a rare occurrence, and
the aggregate effect is that they benefit. Besides, Postgres
performance optimisations for which you can contrive a case that
results in a net-loss in performance are well precedented.

>> As for what types/specialisations may not make the cut, I'm
>> increasingly convinced that floats (in the following order: float4,
>> float8) should be the first to go. Aside from the fact that we cannot
>> use their specialisations for anything like dates and timestamps,
>> floats are just way less useful than integers in the context of
>> database applications, or at least those that I've been involved with.
>> As important as floats are in the broad context of computing, it's
>> usually only acceptable to store data in a database as floats within
>> scientific applications, and only then when their limitations are
>> well-understood and acceptable. I think we've all heard anecdotes at
>> one time or another, involving their limitations not being well
>> understood.
>
> While we're waiting for anyone else to weigh in with an opinion on the
> right place to draw the line here, do you want to post an updated
> patch with the changes previously discussed?

Patch is attached. I have not changed the duplicate functions. This is
because I concluded that it was the lesser of two evils to have to get
the template to generate both declarations in the header file, and
definitions in the .c file - that seemed particularly obscure. We're
never going to have to expose/duplicate any more comparators anyway.
Do you agree?

It's pretty easy to remove a specialisation at any time - just remove
less than 10 lines of code. It's also pretty difficult to determine,
with everyone's absolute confidence, where the right balance lies.
Perhaps the sensible thing to do is to not be so conservative in what
we initially commit, while clearly acknowledging that we may not have
the balance right, and that it may have to change. We then have the
entire beta part of the cycle in which to decide to roll back from
that position, without any plausible downside. If, on the other hand,
we conservatively lean towards fewer specialisations in the initial
commit, no one will complain about the lack of an improvement in
performance that they never had.

Tom's objections related to the total number of specialisations, and
their distributed costs - the very idea of full specialisations was
not objected to. I think it's fair to say that there is no controversy
at all remaining about whether or not we should have *some* number of
specialisations. Therefore, I'm going to suggest that assuming you
have no further objections to the style of the code, and no one else
voices any other objections in the next couple of days, that you
provisionally commit this latest revision with all of its
specialisations, while putting people on notice about this.

I think that possibly the one remaining blocker to tentatively
committing this with all specialisations intact is that I haven't
tested this on Windows, as I don't currently have access to a Windows
development environment. I have set one up before, but it's a huge
pain. Can anyone help me out?

-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

On 6 January 2012 21:14, Tom Lane  wrote:
> When there are lots of duplicates of a particular indexed value, the
> existing code will cause an indexscan to search them in physical order,
> whereas if we remove the existing logic it'll be random --- in
> particular, accesses to the same heap page can no longer be expected to
> be clustered.

Isn't it possible to get them in physical order anyway, by reading
them into memory in that order? Efficient quick sort implementations
are not stable, and ours is no exception, but we could perhaps come up
with a cheaper tie-breaker value at that stage, if you're determined
to maintain this behaviour. We have sufficient incentive to, as I
describe below.

> Admittedly, I don't have any numbers quantifying just how useful that
> might be, but on the other hand you've not presented any evidence
> justifying removing the behavior either.  If we believe your position
> that indexes don't generally have lots of duplicates, then the code in
> question will seldom be reached and therefore there would be no
> performance benefit in removing it.

I ran the same btree benchmark on master, but without the "cheap
insurance". The results were interesting, to say the least.

The columns indexed were the same columns and data that I've been
using all along. Initially this made sense, as the performance of
multi sort key sorts often largely hinged on being able to get away
with doing one comparison per pair of tuples - with many duplicates, I
could avoid cheating and show something closer to worst case for the
patch.

I didn't think it mattered that indexing the same columns would
produce what happened to be a not so useful index in the real world,
due to having so many duplicates - better to have figures that were
somewhat comparable for btree tuple sorting and heap tuple sorting.

When I ran the same benchmark on a server that differed from master
only in that their was no insurance, it momentarily appeared that
*all* of the gains for btree index creation came from being able to
elide the "cheap insurance", but only where it would have to be paid
for a high number of times.

I soon realised that I'd made a blunder: the code (that is, the patch
that I posed most recently) wasn't even using my specialisation for
qsorting, because the SortSupport pointer was null! I did not have
tuplesort_begin_index_btree initialise the SortSupport struct as
tuplesort_begin_heap did, so my earlier benchmark was effectively
meaningless, except that it indicated the benefits of eliding the
cheap insurance alone, if only for that not so compelling case. You
should note that the benefits of not paying for the insurance can be
very significant indeed.

Attached are figures for an identical run of the same btree python
script, but with a version of the patch that actually uses my
specialisations. Granted, these numbers are still partially predicated
on the index in question having a large number of duplicates, but it's
worth noting:

1. The gain from specialisation isn't bad; not as good as the
improvements we saw for heap tuples, but not so bad either, especially
considering that binary bloat should be much less controversial for
btree tuples.

2. The index that results from the tests is still useful; the planner
is perfectly willing to use it rather than than performing an
in-memory sort. It will also use it to satisfy a query like "select *
from orderlines where prod_id = 5", albeit via a bitmap index scan. I
took the precaution of increasing default_statistics_target to its
maximum value, as well an performing an analyze on orderlines in
advance of checking this.

Revision to this patch that fixes the bug to follow - I produced these
new numbers from a rough cut of that.

-- 
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time

Re: Progress on fast path sorting, btree index creation time