From: | Qingqing Zhou <zhouqq(at)cs(dot)toronto(dot)edu> |
---|---|
To: | Dann Corbit <DCorbit(at)connx(dot)com> |
Cc: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Luke Lonergan <llonergan(at)greenplum(dot)com>, Neil Conway <neilc(at)samurai(dot)com>, Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us>, pgsql-hackers(at)postgresql(dot)org |
Subject: | Re: Which qsort is used |
Date: | 2005-12-13 21:07:56 |
Message-ID: | Pine.LNX.4.58.0512131603190.27714@josh.db |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
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
From | Date | Subject | |
---|---|---|---|
Next Message | Joachim Wieland | 2005-12-13 21:32:13 | Automatic function replanning |
Previous Message | Dann Corbit | 2005-12-13 20:59:23 | Re: Which qsort is used |