The test is designed especially for database systems, which are likely
to be clustered on data or index (and in the general case are sometimes
loaded in physically sorted order). In the clustered case, the only
time the data will not be ordered is when there has been a page split
and the statistics have not been updated.

The in-order check happens only once and there will not be a significant
performance hit for removal (except that it will be absurdly fast when
the data is already ordered or in reverse order if left as-is.)

Ordered and reverse-ordered are two cases where qsort goes quadratic
(without a test). Of course, introspective sort does not suffer from
this defect, even with the test removed.

> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org [mailtogsql-hackers-
> owner@postgresql.org] On Behalf Of Dann Corbit
> Sent: Tuesday, December 13, 2005 11:53 AM
> To: Tom Lane
> Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
> hackers@postgresql.org
> Subject: Re: [HACKERS] Which qsort is used
>
> The test is O(n)
>
> > -----Original Message-----
> > From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
> > Sent: Tuesday, December 13, 2005 10:51 AM
> > To: Dann Corbit
> > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
> > hackers@postgresql.org
> > Subject: Re: [HACKERS] Which qsort is used
> >
> > "Dann Corbit" <DCorbit@connx.com> writes:
> > > Here is a sort template (that can very easily be turned into a C
> > > routine).
> >
> > Right offhand I'd guess this to be a loser on not-quite-sorted
input,
> > because the tests it makes to try to prove the input is already
sorted
> > can add significant overhead before failing.
> >
> > regards, tom lane
>
> ---------------------------(end of
broadcast)---------------------------
> TIP 9: In versions below 8.0, the planner will ignore your desire to
> choose an index scan if your joining column's datatypes do not
> match

---------------------------(end of broadcast)---------------------------
TIP 4: Have you searched our list archives?

http://archives.postgresql.org

On Tue, 13 Dec 2005, Dann Corbit wrote:

> The test is designed especially for database systems, which are likely
> to be clustered on data or index (and in the general case are sometimes
> loaded in physically sorted order). In the clustered case, the only
> time the data will not be ordered is when there has been a page split
> and the statistics have not been updated.
>
> The in-order check happens only once and there will not be a significant
> performance hit for removal (except that it will be absurdly fast when
> the data is already ordered or in reverse order if left as-is.)
>
> Ordered and reverse-ordered are two cases where qsort goes quadratic
> (without a test). Of course, introspective sort does not suffer from
> this defect, even with the test removed.
>

Yeah, I would think O(n) in-order check doesn't matter for random data
set. For nearly-ordered set, may be not true. I am not good at C++, so can
you patch the test program with your sort method and the page-split-data
generator? I would be happy to give it a test.

Regards,
Qingqing

---------------------------(end of broadcast)---------------------------
TIP 9: In versions below 8.0, the planner will ignore your desire to
choose an index scan if your joining column's datatypes do not
match

"Dann Corbit" <DCorbit@connx.com> writes:
> The in-order check happens only once

Hm? What about that call inside qloop's loop?

regards, tom lane

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