Re: No merge sort?

I tried general, but no response. Anyone here can shed some light on the
issue? Do I need to code merge sort into postgresql?

----- Forwarded message from Taral <taral(at)taral(dot)net> -----

From: Taral <taral(at)taral(dot)net>
To: pgsql-general(at)postgresql(dot)org
Date: Wed, 12 Mar 2003 17:54:35 -0600
Subject: [GENERAL] No merge sort?
Message-ID: <20030312235435(dot)GA3007(at)taral(dot)net>

I have a table "test" that looks like this:

CREATE TABLE test (
id BIGINT,
time INTEGER
);

There is an index:

CREATE INDEX idx ON test(id, time);

The table has been loaded with 2M rows, where time ranges sequentially
from 0 to 1999999 and id is random values from 0 to 49999.

This query:

SELECT * FROM idx WHERE id IN (...) AND time > 198000 AND time < 199800
ORDER BY time DESC LIMIT 20;

has an EXPLAIN ANALYZE of:

Limit (cost=3635.28..3635.28 rows=20 width=12) (actual time=22.94...22.96 rows=14 loops=1)
-> Sort (cost=3635.28..3635.28 rows=23 width=12) (actual time=22.93..22.93 rows=14 loops=1)
-> Index Scan using idx, idx, ..., idx, idx on test (cost=0.00...3634.77 rows=23 width=12) (actual time=1.01..22.10 rows=14 loops=1)
Total runtime: 29.12 msec

This query:

SELECT * FROM idx WHERE id IN (...) AND time < 199800 ORDER BY time DESC
LIMIT 20;

has an EXPLAIN ANALYZE of:

Limit (cost=14516.46..14516.46 rows=20 width=12) (actual time=1448..83..1448.86 rows=20 loops=1)
-> Sort (cost=14516.46..14516.46 rows=2527 width=12) (actual time=1448.82..1448.83 rows=21 loops=1)
-> Index Scan using idx, idx, ..., idx, idx on test (cost=0.00...14373.67 rows=2527 width=12) (actual time=0.14..1437.33 rows=2048 loops=1)
Total runtime: 1454.62 msec

Since the index will output 'time' sorted data for each 'id', why isn't
a merge sort being used here? A merge sort would reduce the execution
time back to 30 ms.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

Taral <taral(at)taral(dot)net> writes:
> Do I need to code merge sort into postgresql?

Seems like a waste of effort to me. I find this example less than
compelling --- the case that could be sped up is quite narrow,
and the potential performance gain not all that large. (A sort
is a sort however you slice it, with O(N log N) runtime...)

Also, the direction we'd likely be going in in future is to merge
multiple indexscans using bitmap techniques, so that the output
ordering of the scans couldn't be counted on anyway.

regards, tom lane

On Thu, Mar 13, 2003 at 04:28:34PM -0500, Tom Lane wrote:
> Seems like a waste of effort to me. I find this example less than
> compelling --- the case that could be sped up is quite narrow,
> and the potential performance gain not all that large. (A sort
> is a sort however you slice it, with O(N log N) runtime...)

Actually, it's O(N) time. The index can produce "time" sorted data for
each "id" in linear time, and the merge sort can merge them in linear
time. Also, the existing system insists on loading _all_ candidate rows
whereas this method can benefit from the limit.

If you don't want to code it, I will. I need it for the livejournal
mysql->postgresql transition. (No, mysql doesn't do it right either.)
But a few pointers to the right places to look in the code would be
helpful.

> Also, the direction we'd likely be going in in future is to merge
> multiple indexscans using bitmap techniques, so that the output
> ordering of the scans couldn't be counted on anyway.

I don't understand this. What do these bitmap techniques do?

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

Taral <taral(at)taral(dot)net> writes:
> On Thu, Mar 13, 2003 at 04:28:34PM -0500, Tom Lane wrote:
>> Seems like a waste of effort to me. I find this example less than
>> compelling --- the case that could be sped up is quite narrow,
>> and the potential performance gain not all that large. (A sort
>> is a sort however you slice it, with O(N log N) runtime...)

> Actually, it's O(N) time.

Only if you assume a fixed number of input streams.

>> Also, the direction we'd likely be going in in future is to merge
>> multiple indexscans using bitmap techniques, so that the output
>> ordering of the scans couldn't be counted on anyway.

> I don't understand this. What do these bitmap techniques do?

The idea is you look at the index to make a list of main-table tuple
positions you are interested in, which you represent compactly as a
compressed bitmap. (There is some finagling needed because PG actually
uses block/line number rather than a pure tuple number to identify
tuples, but you can fake it with a reasonably small amount of overhead.)
Then you can combine multiple index inputs by ANDing or ORing bitmaps
(the OR case applies to your example). Finally, you traverse the heap,
accessing the desired rows in heap-location order. This loses in terms
of producing presorted output --- but it often saves enough in I/O costs
to more than justify doing the sort in memory.

regards, tom lane

On Thu, Mar 13, 2003 at 10:30:27PM -0500, Tom Lane wrote:
> The idea is you look at the index to make a list of main-table tuple
> positions you are interested in, which you represent compactly as a
> compressed bitmap. (There is some finagling needed because PG actually
> uses block/line number rather than a pure tuple number to identify
> tuples, but you can fake it with a reasonably small amount of overhead.)
> Then you can combine multiple index inputs by ANDing or ORing bitmaps
> (the OR case applies to your example). Finally, you traverse the heap,
> accessing the desired rows in heap-location order. This loses in terms
> of producing presorted output --- but it often saves enough in I/O costs
> to more than justify doing the sort in memory.

And it loses bigtime in the case of LIMIT. If the unlimited query
returns 4,000 records and I only want 20, you're retrieving 200x too
much data from disk.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

Same setup, different query:

test=> explain select max(time) from test where id = '1';
NOTICE: QUERY PLAN:

Aggregate (cost=5084.67..5084.67 rows=1 width=0)
-> Index Scan using idx on test (cost=0.00..5081.33 rows=1333 width=0)

Since the index is (id, time), why isn't the index being used to
retrieve the maximum value?

On Thu, Mar 13, 2003 at 03:10:49PM -0600, Taral wrote:
> I have a table "test" that looks like this:
>
> CREATE TABLE test (
> id BIGINT,
> time INTEGER
> );
>
> There is an index:
>
> CREATE INDEX idx ON test(id, time);
>
> The table has been loaded with 2M rows, where time ranges sequentially
> from 0 to 1999999 and id is random values from 0 to 49999.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

Taral <taral(at)taral(dot)net> writes:
> On Thu, Mar 13, 2003 at 10:30:27PM -0500, Tom Lane wrote:
>> The idea is you look at the index to make a list of main-table tuple
>> positions you are interested in, which you represent compactly as a
>> compressed bitmap. [snip]

> And it loses bigtime in the case of LIMIT. If the unlimited query
> returns 4,000 records and I only want 20, you're retrieving 200x too
> much data from disk.

Sure. That's why we have a planner that distinguishes between startup
cost and total cost, and interpolates when a LIMIT is involved. But
if this mergesort idea only helps for small-limit cases, that's another
restriction on its scope of usefulness...

regards, tom lane

On Fri, Mar 14, 2003 at 10:43:30PM -0500, Tom Lane wrote:
> Sure. That's why we have a planner that distinguishes between startup
> cost and total cost, and interpolates when a LIMIT is involved. But
> if this mergesort idea only helps for small-limit cases, that's another
> restriction on its scope of usefulness...

I don't think so, since even in the non-limit case it avoids having to
do a full sort if the number of initial streams is finite and small (as
in the case I demonstrated), reducing time complexity to O(N).

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

On Fri, Mar 14, 2003 at 14:19:46 -0600,
Taral <taral(at)taral(dot)net> wrote:
> Same setup, different query:
>
> test=> explain select max(time) from test where id = '1';
> NOTICE: QUERY PLAN:
>
> Aggregate (cost=5084.67..5084.67 rows=1 width=0)
> -> Index Scan using idx on test (cost=0.00..5081.33 rows=1333 width=0)
>
> Since the index is (id, time), why isn't the index being used to
> retrieve the maximum value?

It looks like an index scan is being done.

If the index was on (time, id) instead of (id, time), then you could get
a further speed up by rewriting the query as:
select time from test where id = '1' order by time desc limit 1;

On Sat, Mar 15, 2003 at 09:23:28AM -0600, Bruno Wolff III wrote:
> On Fri, Mar 14, 2003 at 14:19:46 -0600,
> Taral <taral(at)taral(dot)net> wrote:
> > Same setup, different query:
> >
> > test=> explain select max(time) from test where id = '1';
> > NOTICE: QUERY PLAN:
> >
> > Aggregate (cost=5084.67..5084.67 rows=1 width=0)
> > -> Index Scan using idx on test (cost=0.00..5081.33 rows=1333 width=0)
> >
> > Since the index is (id, time), why isn't the index being used to
> > retrieve the maximum value?
>
> It looks like an index scan is being done.
>
> If the index was on (time, id) instead of (id, time), then you could get
> a further speed up by rewriting the query as:
> select time from test where id = '1' order by time desc limit 1;

Yes, that's exactly it. It's an index _scan_. It should simply be able
to read the maximum straight from the btree.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

On Mon, Mar 17, 2003 at 11:23:47 -0600,
Taral <taral(at)taral(dot)net> wrote:
> On Sat, Mar 15, 2003 at 09:23:28AM -0600, Bruno Wolff III wrote:
> > On Fri, Mar 14, 2003 at 14:19:46 -0600,
> > Taral <taral(at)taral(dot)net> wrote:
> > > Same setup, different query:
> > >
> > > test=> explain select max(time) from test where id = '1';
> > > NOTICE: QUERY PLAN:
> > >
> > > Aggregate (cost=5084.67..5084.67 rows=1 width=0)
> > > -> Index Scan using idx on test (cost=0.00..5081.33 rows=1333 width=0)
> > >
> > > Since the index is (id, time), why isn't the index being used to
> > > retrieve the maximum value?
> >
> > It looks like an index scan is being done.
> >
> > If the index was on (time, id) instead of (id, time), then you could get
> > a further speed up by rewriting the query as:
> > select time from test where id = '1' order by time desc limit 1;
>
> Yes, that's exactly it. It's an index _scan_. It should simply be able
> to read the maximum straight from the btree.

max and min don't use indexes. They are generic aggregate functions and
postgres doesn't have the special knowledge to know that for those
aggregate functions and index can be used. You can get around this
by rewriting the query as I previously indicated.

For more details on why things are this way, search the archives. This
topic comes up a lot.

I was also mistaken about have to switch the index around for this case.
It should work the way you have it (if you rewrite the query).

On Mon, Mar 17, 2003 at 11:23:47AM -0600, Taral wrote:
> Yes, that's exactly it. It's an index _scan_. It should simply be able
> to read the maximum straight from the btree.

Still doesn't work, even with rewritten query. It sort a
Limit(Sort(Index Scan)), with 1333 rows being pulled from the index.

--
Taral <taral(at)taral(dot)net>
This message is digitally signed. Please PGP encrypt mail to me.
"Most parents have better things to do with their time than take care of
their children." -- Me

AFAIK, there are only 3 general purpose internal sorting techniques
that have O(n) behavior:
1= Insertion Sort for "almost sorted" lists. Since "almost sorted" is
a fuzzy concept, let's make the first approximation definition that no
more than n^(1/2) of the elements can be disordered. There are better
definitions in the literature, but I don't remember them off the top
of my head.

2= Sorts from the class of Address Calculation, Counting, or
Distribution Sort. These need to be able to carry out something more
complex than simply a comparison in order to achieve O(n), and
therefore have high constants in their execution. For large enough n
though, these are the performance kings.

3= Straight Radix Sort where you minimize the number of passes by
using a base much greater than two for the the radix. Usually octal
or hexidecimal. On a 32b or 64b system, this approach will let you
sort in 2 passes.

All of the above have potentially nasty trade-offs in comparision to
the standard heavily tuned median-of-three quicksort used by the sort
unix command. Nonetheless, I could see some value in providing all of
these with PostgeSQL (including a decent port of the unix sort routine
for the Win folks). I'll note in passing that quicksort's Achille's
heel is that it's unstable (all of the rest are stable), which can be
a problem in a DB.

In the general case there's a few papers out there that state you can
sort in O(n) if you can throw O(n^2) space at the problem. That
implies to me that for DB's, we are not going to be able to use O(n)
algorithms for most of our needs.

As for external sorts, everything I've ever read says that some sort
of merge technique is used: balanced, multiway, or polyphase. In all
cases, I've seen comments to the effect that reading some part of the
data into internal buffers, sorting them, and then merging them with
already sorted data is the best practice.

All of this seems to imply that instead of mergesort (which is
stable), PostgreSQL might be better off with the 4 sorts I've listed
plus a viciously efficient merge utility for combining partial results
that do fit into memory into result files on disk that don't.

Or am I crazy?

Ron Peacetree

"Ron Peacetree" <rjpeace(at)earthlink(dot)net> writes:

> AFAIK, there are only 3 general purpose internal sorting techniques
> that have O(n) behavior:

Strictly speaking there are no sorting algorithms that have worst-case time
behaviour better than O(nlog(n)). Period.

The typical kind-of O(n) sorts involve either special-case inputs (almost
sorted), or only work if you ignore some aspect of the input size (radix
sort).

So, for example, for radix sort the log(n) factor comes precisely from having
to have log(n) passes. If you use octal that might go to log(n)/8 but it's
still O(log(n)).

If you assume your input fields are limited to a fixed size then O() notation
loses meaning. You can always sort in linear time by just storing bit flags in
a big vector and then scanning your (fixed-size) vector to read out the
values.

However databases cannot assume fixed size inputs. Regardless of whether it's
on a 32 or 64 bit system postgres still has to sort much larger data
structures. floats are typically 64 - 96 bytes, bigints can be arbitrarily
large.

In fact posgres can sort user-defined datatypes as long as they have < and =
operators. (Actually I'm not sure on the precise constraint.)

Oh, and just to add one last fly in the ointment, postgres has to be able to
sort large datasets that don't even fit in memory. That means storing
temporary data on disk and minimizing the times data has to move from disk to
memory and back. Some alogorithms are better at that than others.

--
greg

On Mon, Apr 07, 2003 at 03:36:10PM -0400, Greg Stark wrote:
> "Ron Peacetree" <rjpeace(at)earthlink(dot)net> writes:
>
> > AFAIK, there are only 3 general purpose internal sorting techniques
> > that have O(n) behavior:
>
> Strictly speaking there are no sorting algorithms that have worst-case time
> behaviour better than O(nlog(n)). Period.
>

Not true.

http://www.elsewhere.org/jargon/html/entry/bogo-sort.html

-Jay 'Eraserhead' Felice

P.S. <g>

Ron Peacetree wrote:
> AFAIK, there are only 3 general purpose internal sorting techniques
> that have O(n) behavior:

Hum? NO "general purpose" sorting technique has O(n) behaviour.

The theoretical best scenario, _in general_, is O(n log n).

Insertion sort is expected to provide O(n^2) behaviour, and radix-like
schemes get arbitrarily memory hungry and have bad pathological results.

> All of the above have potentially nasty trade-offs in comparision to
> the standard heavily tuned median-of-three quicksort used by the sort
> unix command. Nonetheless, I could see some value in providing all of
> these with PostgeSQL (including a decent port of the unix sort routine
> for the Win folks). I'll note in passing that quicksort's Achille's
> heel is that it's unstable (all of the rest are stable), which can be
> a problem in a DB.

Making one sort algorithm work very efficiently is quite likely to be a
lot more effective than frittering away time trying to get some special
cases (that you can't regularly use) to work acceptably.

> All of this seems to imply that instead of mergesort (which is
> stable), PostgreSQL might be better off with the 4 sorts I've listed
> plus a viciously efficient merge utility for combining partial results
> that do fit into memory into result files on disk that don't.
>
> Or am I crazy?

More than likely. It is highly likely that it will typically take more
computational effort to figure out that one of the 4 sorts provided
/any/ improvement than any computational effort they would save.

That's a /very/ common problem. There's also a fair chance, seen in
practice, that the action of collecting additional statistics to improve
query optimization will cost more than the savings provided by the
optimizations.
--
(concatenate 'string "cbbrowne" "@acm.org")
http://www3.sympatico.ca/cbbrowne/wp.html
When ever in doubt consult a song. --JT Fletcher

<cbbrowne(at)cbbrowne(dot)com> wrote in message
news:20030407202001(dot)1EC3C58E0D(at)cbbrowne(dot)com(dot)(dot)(dot)
> Ron Peacetree wrote:
> > AFAIK, there are only 3 general purpose internal sorting
techniques
> > that have O(n) behavior:
>
> Hum? NO "general purpose" sorting technique has O(n) behaviour.
>
> The theoretical best scenario, _in general_, is O(n log n).
The O(log(n!)) bound is only for comparison based sorts operating on
arbitarily disordered input. There are general techniques that can
sort in O(n) time if we can "break" either assumption. In a DB, we
often are dealing with data that is only slightly disordered, or we
are have enough meta knowledge that we can use more powerful ordering
operators than simple comparisons, or both.

> Insertion sort is expected to provide O(n^2) behaviour, and
radix-like
> schemes get arbitrarily memory hungry and have bad pathological
results.
>
None of these comments is accurate.
The sources for the following discussion are
A= Vol 3 of Knuth 2nd ed, (ISBN 0-201-89685-0)
B= Sedgewick's Algorithms in C, (0-201-51425-7)
C= Handbook of Algorithms and Data Structures 2nd ed by Gonnet and
Baeza-Yates. (0-201-41607-7)

1= Insertion sort is O(n) for "almost sorted" input.
p103 of Sedgewick. There's also discussion on this in Knuth.

2= Distribution Sort and it's "cousins" which use more powerful
ordering operators than simply comparisons are a= reasonably general,
and b= O(n).
Look in all three references.

3= A proper implementation of straight Radix sort using 8b or 16b at a
time a= is NOT pathological, and b= is O(n).
Sedgewick is the most blunt about it on p142-143, but Knuth discusses
this as well.

All of the above are stable, which quicksort is not. There are no
"pessimal" inputs for any of the above that will force worst case
behavior. For quicksort there are (they are =very= unlikely however).
In real world terms, if you can use any of these approaches you should
be able to internally sort your data between 2X and 3X faster.

Unfortunately, most of us do not have the luxury of working with
Memory Resident DB's. In the real world, disk access is an important
part of our DB sorting efforts, and that changes things. Very fast
internal sorting routines combined with multidisk merging algorithms
that minimize overall disk I/O while maximizing the sequential nature
of that I/O are the best we can do overall in such a situation.

<cbbrowne(at)cbbrowne(dot)com> wrote in message
news:20030407202001(dot)1EC3C58E0D(at)cbbrowne(dot)com(dot)(dot)(dot)
> It is highly likely that it will typically take more
> computational effort to figure out that one of the 4 sorts provided
> /any/ improvement than any computational effort they would save.
>
> That's a /very/ common problem. There's also a fair chance, seen in
> practice, that the action of collecting additional statistics to
improve
> query optimization will cost more than the savings provided by the
> optimizations.
>
"Back in the Day" I heard similar arguments when discussing whether
there should be support for hashing [O(n)], interpolation search
[O(lglg(n))], binary search [O(lg(n))], and sequential search [O(n)]
or for only some subset of these for a DB system I was working on. To
make a long story short, it was worth it to have support for all of
them because the "useful domain" of each was reasonably large and
reasonably unique compared to the others.

I submit a similar situation exists for sorting. (and yes, I've been
here before too ;-)

Giving end users of PostgreSQL a reasonable set of tools for building
high performance applications is just good business.

"Ron Peacetree" <rjpeace(at)earthlink(dot)net> wrote in message
news:%cqka(dot)13403$ey1(dot)1154620(at)newsread1(dot)prod(dot)itd(dot)earthlink(dot)net(dot)(dot)(dot)
> <cbbrowne(at)cbbrowne(dot)com> wrote in message
> news:20030407202001(dot)1EC3C58E0D(at)cbbrowne(dot)com(dot)(dot)(dot)
> > It is highly likely that it will typically take more
> > computational effort to figure out that one of the 4 sorts
provided
> > /any/ improvement than any computational effort they would save.
> >
> > That's a /very/ common problem. There's also a fair chance, seen
in
> > practice, that the action of collecting additional statistics to
> improve
> > query optimization will cost more than the savings provided by the
> > optimizations.
> >
> "Back in the Day" I heard similar arguments when discussing whether
> there should be support for hashing [O(n)], interpolation search
TYPO ALERT: hashing is, of course, O(1)