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: [EMAIL PROTECTED] [mailto:pgsql-hackers- > [EMAIL PROTECTED] 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- > [EMAIL PROTECTED] > Subject: Re: [HACKERS] Which qsort is used > > The test is O(n) > > > -----Original Message----- > > From: Tom Lane [mailto:[EMAIL PROTECTED] > > Sent: Tuesday, December 13, 2005 10:51 AM > > To: Dann Corbit > > Cc: Qingqing Zhou; Luke Lonergan; Neil Conway; Bruce Momjian; pgsql- > > [EMAIL PROTECTED] > > Subject: Re: [HACKERS] Which qsort is used > > > > "Dann Corbit" <[EMAIL PROTECTED]> 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
