Re: Which qsort is used

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(at)postgresql(dot)org [mailto:pgsql-hackers-
> owner(at)postgresql(dot)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(at)postgresql(dot)org
> Subject: Re: [HACKERS] Which qsort is used
>
> The test is O(n)
>
> > -----Original Message-----
> > From: Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
> > Sent: Tuesday, December 13, 2005 10:51 AM
> > To: Dann Corbit
> > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql-
> > hackers(at)postgresql(dot)org
> > Subject: Re: [HACKERS] Which qsort is used
> >
> > "Dann Corbit" <DCorbit(at)connx(dot)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