From: | Don Baccus <dhogaza(at)pacifier(dot)com> |
---|---|
To: | "Roberto Cornacchia" <rob(dot)c(at)virgilio(dot)it>, tgl(at)sss(dot)pgh(dot)pa(dot)us |
Cc: | pgsql-hackers(at)postgreSQL(dot)org |
Subject: | Re: [HACKERS] Re: about 7.0 LIMIT optimization |
Date: | 2000-02-24 01:33:15 |
Message-ID: | 3.0.1.32.20000223173315.0170ba80@mail.pacifier.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
At 07:10 PM 2/23/00 -0500, Roberto Cornacchia wrote:
>Of course, if you have an index there is no problem.
>It is even true that if you don't have an index there is no way to avoid
the sort, but in that case we use a specialized sort, which does much less
comparisons.
>For example, if you want the 10 best rows from 100000, these are the
average numbers of comparisons:
>
>QuickSort: 1.6E+14
>SortStop: 1.5E+11
This makes sense ... you can stop once you can guarantee that the first
ten rows are in proper order. I'm not familiar with the algorithm
but not terribly surprised that one exists.
- Don Baccus, Portland OR <dhogaza(at)pacifier(dot)com>
Nature photos, on-line guides, Pacific Northwest
Rare Bird Alert Service and other goodies at
http://donb.photo.net.
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2000-02-24 02:14:53 | Re: [HACKERS] interesting observatation regarding views and V7.0 |
Previous Message | Don Baccus | 2000-02-24 01:15:20 | Re: [HACKERS] interesting observatation regarding views and V7.0 |