SEO

*blink* Tapes?! I thought that was a typo...
If our sort is code based on sorting tapes, we've made a mistake. HDs
are not tapes, and Polyphase Merge Sort and it's brethren are not the
best choices for HD based sorts.

Useful references to this point:
Knuth, Vol 3 section 5.4.9, (starts p356 of 2ed)
Tharp, ISBN 0-471-60521-2, starting p352
Folk, Zoellick, and Riccardi, ISBN 0-201-87401-6, chapter 8 (starts p289)

The winners of the "Daytona" version of Jim Gray's sorting contest, for
general purpose external sorting algorithms that are of high enough quality
to be offered commercially, also demonstrate a number of better ways to
attack external sorting using HDs.

The big take aways from all this are:
1= As in Polyphase Merge Sort, optimum External HD Merge Sort
performance is obtained by using Replacement Selection and creating
buffers of different lengths for later merging. The values are different.

2= Using multiple HDs split into different functions, IOW _not_ simply
as RAIDs, is a big win.
A big enough win that we should probably consider having a config option
to pg that allows the use of HD(s) or RAID set(s) dedicated as temporary
work area(s).

3= If the Key is small compared record size, Radix or Distribution
Counting based algorithms are worth considering.

The good news is all this means it's easy to demonstrate that we can
improve the performance of our sorting functionality.

Assuming we get the abyssmal physical IO performance fixed...
(because until we do, _nothing_ is going to help us as much)

Ron


-----Original Message-----
From: Tom Lane <tgl@sss.pgh.pa.us>
Sent: Oct 1, 2005 2:01 AM
Subject: Re: [HACKERS] [PERFORM] A Better External Sort?

"Jeffrey W. Baker" <jwbaker@acm.org> writes:
> I think the largest speedup will be to dump the multiphase merge and
> merge all tapes in one pass, no matter how large M. Currently M is
> capped at 6, so a sort of 60GB with 1GB sort memory needs 13 passes over
> the tape. It could be done in a single pass heap merge with N*log(M)
> comparisons, and, more importantly, far less input and output.

I had more or less despaired of this thread yielding any usable ideas
:-( but I think you have one here. The reason the current code uses a
six-way merge is that Knuth's figure 70 (p. 273 of volume 3 first
edition) shows that there's not much incremental gain from using more
tapes ... if you are in the regime where number of runs is much greater
than number of tape drives. But if you can stay in the regime where
only one merge pass is needed, that is obviously a win.

I don't believe we can simply legislate that there be only one merge
pass. That would mean that, if we end up with N runs after the initial
run-forming phase, we need to fit N tuples in memory --- no matter how
large N is, or how small work_mem is. But it seems like a good idea to
try to use an N-way merge where N is as large as work_mem will allow.
We'd not have to decide on the value of N until after we've completed
the run-forming phase, at which time we've already seen every tuple
once, and so we can compute a safe value for N as work_mem divided by
largest_tuple_size. (Tape I/O buffers would have to be counted too
of course.)

It's been a good while since I looked at the sort code, and so I don't
recall if there are any fundamental reasons for having a compile-time-
constant value of the merge order rather than choosing it at runtime.
My guess is that any inefficiencies added by making it variable would
be well repaid by the potential savings in I/O.

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

Ron Peacetree wrote:

>The good news is all this means it's easy to demonstrate that we can
>improve the performance of our sorting functionality.
>
>Assuming we get the abyssmal physical IO performance fixed...
>(because until we do, _nothing_ is going to help us as much)
>
>
>

I for one would be paying more attention if such a demonstration were
forthcoming, in the form of a viable patch and some benchmark results.

cheers

andrew

---------------------------(end of broadcast)---------------------------
TIP 6: explain analyze is your friend

On Sat, Oct 01, 2005 at 10:22:40AM -0400, Ron Peacetree wrote:
> Assuming we get the abyssmal physical IO performance fixed...
> (because until we do, _nothing_ is going to help us as much)

I'm still not convinced this is the major problem. For example, in my
totally unscientific tests on an oldish machine I have here:

Direct filesystem copy to /dev/null
21MB/s 10% user 50% system (dual cpu, so the system is using a whole CPU)

COPY TO /dev/null WITH binary
13MB/s 55% user 45% system (ergo, CPU bound)

COPY TO /dev/null
4.4MB/s 60% user 40% system

\copy to /dev/null in psql
6.5MB/s 60% user 40% system

This machine is a bit strange setup, not sure why fs copy is so slow.
As to why \copy is faster than COPY, I have no idea, but it is
repeatable. And actually turning the tuples into a printable format is
the most expensive. But it does point out that the whole process is
probably CPU bound more than anything else.

So, I don't think physical I/O is the problem. It's something further
up the call tree. I wouldn't be surprised at all it it had to do with
the creation and destruction of tuples. The cost of comparing tuples
should not be underestimated.
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFDPrcXIB7bNG8LQkwRAulpAJ9Qk9yKddvygb0qb5BofJ y6dD4yTwCfRTXG
GuqPRZ9u7pNqZet021m5h34=
=0vBS
-----END PGP SIGNATURE-----

On Wed, Oct 05, 2005 at 05:41:25AM -0400, Michael Stone wrote:
> On Sat, Oct 01, 2005 at 06:19:41PM +0200, Martijn van Oosterhout wrote:
> >COPY TO /dev/null WITH binary
> >13MB/s 55% user 45% system (ergo, CPU bound)
> [snip]
> >the most expensive. But it does point out that the whole process is
> >probably CPU bound more than anything else.
>
> Note that 45% of that cpu usage is system--which is where IO overhead
> would end up being counted. Until you profile where you system time is
> going it's premature to say it isn't an IO problem.

It's a dual CPU system, so 50% is the limit for a single process. Since
system usage < user, PostgreSQL is the limiter. Sure, the system is
taking a lot of time, but PostgreSQL is still the limiting factor.

Anyway, the later measurements using gprof exclude system time
altogether and it still shows CPU being the limiting factor. Fact is,
extracting tuples from pages is expensive.
--
Martijn van Oosterhout <kleptog@svana.org> http://svana.org/kleptog/
> Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a
> tool for doing 5% of the work and then sitting around waiting for someone
> else to do the other 95% so you can sue them.

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQFDQ6+rIB7bNG8LQkwRAtX6AKCNa7sgu1nH5L01TE02lc H2rdk2/wCfaeP1
i2wioGSUf1rEbRJjZLtuTL0=
=zdXF
-----END PGP SIGNATURE-----