Re: Which qsort is used

I will send you an ANSI C version.

> -----Original Message-----
> From: Qingqing Zhou [mailto:zhouqq(at)cs(dot)toronto(dot)edu]
> Sent: Tuesday, December 13, 2005 1:08 PM
> To: Dann Corbit
> Cc: Tom Lane; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
> hackers(at)postgresql(dot)org
> Subject: RE: [HACKERS] Which qsort is used
>
>
>
> 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