Threaded Sorting

On 4 Oct 2002 at 9:46, Hans-J�rgen Sch�nig wrote:

Did anybody think about threaded sorting so far?
Assume an SMP machine. In the case of building an index or in the case
of sorting a lot of data there is just one backend working. Therefore
just one CPU is used.
What about starting a thread for every temporary file being created?
This way CREATE INDEX could use many CPUs.
Maybe this is worth thinking about because it will speed up huge
databases and enterprise level computing.

I have a better plan. I have a thread architecture ready which acts as generic
thread templates. Even the function pointers in the thread can be altered on
the fly.

I suggest we use some such architecture for threading. It can be used in any
module without hardcoding things. Like say in sorting we assign exclusive
jobs/data ranges to threads then there would be minimum locking and one thread
could merge the results.. Something like that.

All it takes to change entry functions to accept one more parameter that
indicates range of values to act upon. In non-threaded version, it's not there
because the function acts on entire data set.

Further more, with this model threading support can be turned off easily. In
non-threaded model, a wrapper function can call the entry point in series with
necessary arguments. So postgresql does not have to deal with not-so-good-
enough thread implementations. Keeping tradition to conservative defaults we
can set default threads to off..

The code is in C++ but it's hardly couple of pages. I can convert it to C and
post it if required..

Let me know..

Bye
Shridhar

--
Parkinson's Fourth Law: The number of people in any working group tends to
increase regardless of the amount of work to be done.

=?ISO-8859-1?Q?Hans-J=FCrgen_Sch=F6nig?= <postgres@cybertec.at> writes:

Did anybody think about threaded sorting so far?
Assume an SMP machine. In the case of building an index or in the case
of sorting a lot of data there is just one backend working. Therefore
just one CPU is used.
What about starting a thread for every temporary file being created?
This way CREATE INDEX could use many CPUs.

In my experience, once you have enough data to force a temp file to be
used, the sort algorithm is I/O bound anyway. Throwing more CPUs at it
won't help much.

regards, tom lane

I wouldn't hold your breath for any form of threading. Since PostgreSQL
is process based, you might consider having a pool of sort processes
which address this but I doubt you'll get anywhere talking about threads
here.

Greg

Greg Copeland wrote:

I wouldn't hold your breath for any form of threading. Since PostgreSQL
is process based, you might consider having a pool of sort processes
which address this but I doubt you'll get anywhere talking about threads
here.

Greg

I came across the problem yesterday. We thought about SMP and did some
tests on huge tables. The postmaster was running full speed to get the
stuff sorted - even on an IDE system.
I asked my friends who are doing a lot of work with Oracle on huge SMP
machines. I was told that Oracle has a mechanism which can run efficient
sorts on SMP machines. It seems to speed up sorting a lot.

If we could reduce the time needed to build up an index by 25% it would
be a wonderful thing. Just think of a scenario:
1 thread: 24 hours
many threads: 18 hours

We could gain 6 hours which is a LOT.
We have many people running PostgreSQL on systems having wonderful IO
systems - in this case IO is not the bottleneck anymore.

I had a brief look at the code used for sorting. It is very well
documented so maybe it is worth thinking about a parallel algorithm.

When talking about threads: A pool of processes for sorting? Maybe this
could be useful but I doubt if it the best solution to avoid overhead.
Somewhere in the TODO it says that there will be experiments with a
threaded backend. This make me think that threads are not a big no no.

Hans

--
*Cybertec Geschwinde u Schoenig*
Ludo-Hartmannplatz 1/14, A-1160 Vienna, Austria
Tel: +43/1/913 68 09; +43/664/233 90 75
www.postgresql.at <http://www.postgresql.at&gt;, cluster.postgresql.at
<http://cluster.postgresql.at&gt;, www.cybertec.at
<http://www.cybertec.at&gt;, kernel.cybertec.at <http://kernel.cybertec.at&gt;

On Fri, 2002-10-04 at 09:40, Hans-Jürgen Schönig wrote:

I had a brief look at the code used for sorting. It is very well
documented so maybe it is worth thinking about a parallel algorithm.

When talking about threads: A pool of processes for sorting? Maybe this
could be useful but I doubt if it the best solution to avoid overhead.
Somewhere in the TODO it says that there will be experiments with a
threaded backend. This make me think that threads are not a big no no.

Hans

That was a fork IIRC. Threading is not used in baseline PostgreSQL nor
is there any such plans that I'm aware of. People from time to time ask
about threads for this or that and are always told what I'm telling
you. The use of threads leads to portability issues not to mention
PostgreSQL is entirely built around the process model.

Tom is right to dismiss the notion of adding additional CPUs to
something that is already I/O bound, however, the concept it self should
not be dismissed. Applying multiple CPUs to a sort operation is well
accepted and understood technology.

At this point, perhaps Tom or one of the other core developers having
insight in this area would be willing to address how readily such a
mechanism could could be put in place.

Also, don't be so fast to dismiss what the process model can do. There
is not reason to believe that having a process pool would not be able to
perform wonderful things if implemented properly. Basically, the notion
would be that the backend processing the query would solicit assistance
from the sort pool if one or more processes were available. At that
point, several methods could be employed to divide the work. Some form
of threshold would also have to be created to prevent the pool from
being used when a single backend is capable of addressing the need.
Basically the idea is, you only have the pool assist with large tuple
counts and then, only when resources are available and resource are
available from within the pool. By doing this, you avoid additional
overhead for small sort efforts and gain when it matters the most.

Regards,

Greg

Threads are not the best solutions when it comes to portability. A
prefer a process model as well.
My concern was that a process model might be a bit too slow for that but
if we had processes in memory this would be wonderful thing.
Using it for small amounts of data is pretty useless - I totally agree
but when it comes to huge amounts of data it can be useful.

It is a mechanism for huge installations with a lot of data.

Hans

That was a fork IIRC. Threading is not used in baseline PostgreSQL nor
is there any such plans that I'm aware of. People from time to time ask
about threads for this or that and are always told what I'm telling
you. The use of threads leads to portability issues not to mention
PostgreSQL is entirely built around the process model.

Tom is right to dismiss the notion of adding additional CPUs to
something that is already I/O bound, however, the concept it self should
not be dismissed. Applying multiple CPUs to a sort operation is well
accepted and understood technology.

At this point, perhaps Tom or one of the other core developers having
insight in this area would be willing to address how readily such a
mechanism could could be put in place.

Also, don't be so fast to dismiss what the process model can do. There
is not reason to believe that having a process pool would not be able to
perform wonderful things if implemented properly. Basically, the notion
would be that the backend processing the query would solicit assistance
from the sort pool if one or more processes were available. At that
point, several methods could be employed to divide the work. Some form
of threshold would also have to be created to prevent the pool from
being used when a single backend is capable of addressing the need.
Basically the idea is, you only have the pool assist with large tuple
counts and then, only when resources are available and resource are
available from within the pool. By doing this, you avoid additional
overhead for small sort efforts and gain when it matters the most.

Regards,

Greg

--
*Cybertec Geschwinde u Schoenig*
Ludo-Hartmannplatz 1/14, A-1160 Vienna, Austria
Tel: +43/1/913 68 09; +43/664/233 90 75
www.postgresql.at <http://www.postgresql.at&gt;, cluster.postgresql.at
<http://cluster.postgresql.at&gt;, www.cybertec.at
<http://www.cybertec.at&gt;, kernel.cybertec.at <http://kernel.cybertec.at&gt;

On Fri, 2002-10-04 at 10:37, Hans-Jürgen Schönig wrote:

My concern was that a process model might be a bit too slow for that but
if we had processes in memory this would be wonderful thing.

Yes, that's the point of having a pool. The idea is not only do you
avoid process creation and destruction which is notoriously expensive on
many platforms, they would sit idle until signaled to begin working on
it's assigned sort operation. Ideally, these would be configurable
options which would include items such as, pool size (maximum number of
processes in the pool), max concurrency level (maximum number of process
from the pool which can contribute to a single backend) and tuple count
threshold (threshold which triggers solicition for assistance from the
sort pool).

Using it for small amounts of data is pretty useless - I totally agree
but when it comes to huge amounts of data it can be useful.

It is a mechanism for huge installations with a lot of data.

Hans

Agreed. Thus the importance of being able to specify some type of
meaningful threshold.

Any of the core developers wanna chime in here on this concept?

Greg

Hans-J���rgen Sch���nig wrote:

Did anybody think about threaded sorting so far?
Assume an SMP machine. In the case of building an index or in the case
of sorting a lot of data there is just one backend working. Therefore
just one CPU is used.
What about starting a thread for every temporary file being created?
This way CREATE INDEX could use many CPUs.
Maybe this is worth thinking about because it will speed up huge
databases and enterprise level computing.

We haven't thought about it yet because there are too many buggy thread
implementations. We are probably just now getting to a point where we
can consider it. However, lots of databases have moved to threads for
all sorts of things and ended up with a royal mess of code. Threads
can only improve things in a few areas of the backend so it would be
nice if we could limit the exposure to threads to those areas; sorting
could certainly be one of them, but frankly, I think disk I/O is our
limiting factore there. I would be interested to see some tests that
showed otherwise.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Threads are bad - I know ...
I like the idea of a pool of processes instead of threads - from my
point of view this would be useful.

I am planning to run some tests (GEQO, AIX, sorts) as soon as I have
time to do so (still too much work ahead before :( ...).
If I had time I'd love to do something for the PostgreSQL community :(.

As far as sorting is concerned: It would be fine if it was possible to
define an alternative location for temporary sort files using SET.
If you had multiple disks this would help in the case of concurrent
sorts because this way people could insert and index many tables at once
without having to access just one storage system.
This would be an easy way out of the IO limitation ... - at least for
some problems.

Hans

Bruce Momjian wrote:

We haven't thought about it yet because there are too many buggy thread
implementations. We are probably just now getting to a point where we
can consider it. However, lots of databases have moved to threads for
all sorts of things and ended up with a royal mess of code. Threads
can only improve things in a few areas of the backend so it would be
nice if we could limit the exposure to threads to those areas; sorting
could certainly be one of them, but frankly, I think disk I/O is our
limiting factore there. I would be interested to see some tests that
showed otherwise.

--
*Cybertec Geschwinde u Schoenig*
Ludo-Hartmannplatz 1/14, A-1160 Vienna, Austria
Tel: +43/1/913 68 09; +43/664/233 90 75
www.postgresql.at <http://www.postgresql.at&gt;, cluster.postgresql.at
<http://cluster.postgresql.at&gt;, www.cybertec.at
<http://www.cybertec.at&gt;, kernel.cybertec.at <http://kernel.cybertec.at&gt;

On Fri, 4 Oct 2002, Bruce Momjian wrote:

Hans-J�rgen Sch�nig wrote:

Did anybody think about threaded sorting so far?
Assume an SMP machine. In the case of building an index or in the case
of sorting a lot of data there is just one backend working. Therefore
just one CPU is used.
What about starting a thread for every temporary file being created?
This way CREATE INDEX could use many CPUs.
Maybe this is worth thinking about because it will speed up huge
databases and enterprise level computing.

We haven't thought about it yet because there are too many buggy thread
implementations. We are probably just now getting to a point where we
can consider it. However, lots of databases have moved to threads for
all sorts of things and ended up with a royal mess of code. Threads
can only improve things in a few areas of the backend so it would be
nice if we could limit the exposure to threads to those areas; sorting
could certainly be one of them, but frankly, I think disk I/O is our
limiting factore there. I would be interested to see some tests that
showed otherwise.

Wouldn't the type of disk subsystem really make a big difference here?

With a couple of U160 cards and a dozen 15krpm hard drives, I would
imagine I/O would no longer be as much of an issue as a single drive
system would be.

It seems like sometimes we consider these issues more from the one or two
SCSI drives perspective insted of the big box o drives perspective.

Hans-J���rgen Sch���nig wrote:

Threads are bad - I know ...
I like the idea of a pool of processes instead of threads - from my
point of view this would be useful.

I am planning to run some tests (GEQO, AIX, sorts) as soon as I have
time to do so (still too much work ahead before :( ...).
If I had time I'd love to do something for the PostgreSQL community :(.

As far as sorting is concerned: It would be fine if it was possible to
define an alternative location for temporary sort files using SET.
If you had multiple disks this would help in the case of concurrent
sorts because this way people could insert and index many tables at once
without having to access just one storage system.
This would be an easy way out of the IO limitation ... - at least for
some problems.

Bingo! Want to increase sorting performance, give it more I/O
bandwidth, and it will take 1/100th of the time to do threading.

Ingres had a nice feature where you could specify sort directories and
it would cycle through those directories while it did the tape sort.

Added to TODO:

* Allow sorting to use multiple work directories

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

scott.marlowe wrote:

We haven't thought about it yet because there are too many buggy thread
implementations. We are probably just now getting to a point where we
can consider it. However, lots of databases have moved to threads for
all sorts of things and ended up with a royal mess of code. Threads
can only improve things in a few areas of the backend so it would be
nice if we could limit the exposure to threads to those areas; sorting
could certainly be one of them, but frankly, I think disk I/O is our
limiting factore there. I would be interested to see some tests that
showed otherwise.

Wouldn't the type of disk subsystem really make a big difference here?

With a couple of U160 cards and a dozen 15krpm hard drives, I would
imagine I/O would no longer be as much of an issue as a single drive
system would be.

It seems like sometimes we consider these issues more from the one or two
SCSI drives perspective insted of the big box o drives perspective.

Yes, it is mostly for non-RAID drives, but also, sometimes single drives
can be faster. When you have a drive array, it isn't as easy to hit
each drive and keep it running sequentially. Of course, I don't have
any hard numbers on that. ;-)

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Bruce Momjian wrote:

scott.marlowe wrote:

<snip>

It seems like sometimes we consider these issues more from the one or two
SCSI drives perspective insted of the big box o drives perspective.

Yes, it is mostly for non-RAID drives, but also, sometimes single drives
can be faster. When you have a drive array, it isn't as easy to hit
each drive and keep it running sequentially. Of course, I don't have
any hard numbers on that. ;-)

Arrghh... please remember that "big bunch of drives" != "all in one
array".

It's common to have a bunch of drives and allocate different ones for
different tasks appropriately, whether in array sets, individually,
mirrored, etc.

100% totally feasible to have a separate 15k SCSI drive or two just
purely for doing sorts if it would assist in throughput.

:-)

Regards and best wishes,

Justin Clift

--
Bruce Momjian                        |  http://candle.pha.pa.us
pgman@candle.pha.pa.us               |  (610) 359-1001
+  If your life is a hard drive,     |  13 Roberts Road
+  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

--
"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
- Indira Gandhi

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Bingo! Want to increase sorting performance, give it more I/O
bandwidth, and it will take 1/100th of the time to do threading.

Added to TODO:
* Allow sorting to use multiple work directories

Yeah, I like that. Actually it should apply to all temp files not only
sorting.

A crude hack would be to allow there to be multiple pg_temp_NNN/
subdirectories (read symlinks) in a database, and then the code would
automatically switch among these.

Probably a cleaner idea would be to somehow integrate this with
tablespace management --- if you could mark some tablespaces as intended
for temp stuff, the system could round-robin among those as it creates
temp files and/or temp tables.

regards, tom lane

On Fri, 2002-10-04 at 12:26, Bruce Momjian wrote:

Added to TODO:

* Allow sorting to use multiple work directories

Why wouldn't that fall under the table space effort???

Greg

Tom Lane wrote:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Bingo! Want to increase sorting performance, give it more I/O
bandwidth, and it will take 1/100th of the time to do threading.

Added to TODO:
* Allow sorting to use multiple work directories

Yeah, I like that. Actually it should apply to all temp files not only
sorting.

A crude hack would be to allow there to be multiple pg_temp_NNN/
subdirectories (read symlinks) in a database, and then the code would
automatically switch among these.

TODO updated:

* Allow sorting/temp files to use multiple work directories

Tom, what temp files do we use that aren't for sorting; I forgot.

Probably a cleaner idea would be to somehow integrate this with
tablespace management --- if you could mark some tablespaces as intended
for temp stuff, the system could round-robin among those as it creates
temp files and/or temp tables.

Yes, tablespaces would be the place for this.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

Greg Copeland wrote:
-- Start of PGP signed section.

On Fri, 2002-10-04 at 12:26, Bruce Momjian wrote:

Added to TODO:

* Allow sorting to use multiple work directories

Why wouldn't that fall under the table space effort???

Yes, but we make it a separate item so we are sure that is implemented
as part of tablespaces.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073

I see. I just always assumed that it would be done as part of table
space effort as it's such a defacto feature.

I am curious as to why no one has commented on the other rather obvious
performance enhancement which was brought up in this thread. Allowing
for parallel sorting seems rather obvious and is a common enhancement
yet seems to of been completely dismissed as people seem to be fixated
on I/O. Go figure.

Greg

Bingo = great :).
The I/O problem seems to be solved :).

A table space concept would be top of the histlist :).

The symlink version is not very comfortable and I think it would be a
real hack.
Also: If we had a clean table space concept it would be real advantage.
In the first place it would be enough to define a directory (alter
tablespace, changing sizes etc. could be a lot of work).

How could CREATE TABLESPACE look like?
Personally I like the Oracle Syntax.

Is it already time to work on the parser for CREATE/ALTER/DROP TABLESPACE?

Hans

Tom Lane wrote:

Bruce Momjian <pgman@candle.pha.pa.us> writes:

Bingo! Want to increase sorting performance, give it more I/O
bandwidth, and it will take 1/100th of the time to do threading.

Added to TODO:
* Allow sorting to use multiple work directories

Yeah, I like that. Actually it should apply to all temp files not only
sorting.

A crude hack would be to allow there to be multiple pg_temp_NNN/
subdirectories (read symlinks) in a database, and then the code would
automatically switch among these.

Probably a cleaner idea would be to somehow integrate this with
tablespace management --- if you could mark some tablespaces as intended
for temp stuff, the system could round-robin among those as it creates
temp files and/or temp tables.

regards, tom lane

--
*Cybertec Geschwinde u Schoenig*
Ludo-Hartmannplatz 1/14, A-1160 Vienna, Austria
Tel: +43/1/913 68 09; +43/664/233 90 75
www.postgresql.at <http://www.postgresql.at&gt;, cluster.postgresql.at
<http://cluster.postgresql.at&gt;, www.cybertec.at
<http://www.cybertec.at&gt;, kernel.cybertec.at <http://kernel.cybertec.at&gt;