>From: Josh Berkus <josh@agliodbs.com>
>ent: Sep 27, 2005 12:15 PM
>To: Ron Peacetree <rjpeace@earthlink.net>
>Subject: Re: [HACKERS] [PERFORM] A Better External Sort?
>
>I've somehow missed part of this thread, which is a shame since this is
>an area of primary concern for me.
>
>Your suggested algorithm seems to be designed to relieve I/O load by
>making more use of the CPU. (if I followed it correctly).
>
The goal is to minimize all IO load. Not just HD IO load, but also RAM
IO load. Particularly random access IO load of any type (for instance:
"the pointer chasing problem").
In addition, the design replaces explicit data or explicit key manipulation
with the creation of a smaller, far more CPU and IO efficient data
structure (essentially a CPU cache friendly Btree index) of the sorted
order of the data.
That Btree can be used to generate a physical reordering of the data
in one pass, but that's the weakest use for it. The more powerful
uses involve allowing the Btree to persist and using it for more
efficient re-searches or combining it with other such Btrees (either as
a step in task distribution across multiple CPUs or as a more efficient
way to do things like joins by manipulating these Btrees rather than
the actual records.)
>However, that's not PostgreSQL's problem; currently for us external
>sort is a *CPU-bound* operation, half of which is value comparisons.
>(oprofiles available if anyone cares)
>
>So we need to look, instead, at algorithms which make better use of
>work_mem to lower CPU activity, possibly even at the expense of I/O.
>
I suspect that even the highly efficient sorting code we have is
suffering more pessimal CPU IO behavior than what I'm presenting.
Jim Gray's external sorting contest web site points out that memory IO
has become a serious problem for most of the contest entries.
Also, I'll bet the current code manipulates more data.
Finally, there's the possibilty of reusing the product of this work to a
degree and in ways that we can't with our current sorting code.
Now all we need is resources and time to create a prototype.
Since I'm not likely to have either any time soon, I'm hoping that
I'll be able to explain this well enough that others can test it.
*sigh* I _never_ have enough time or resources any more...
Ron