Re: slow count in window query

On Wed, Jul 15, 2009 at 11:18 AM, Pavel Stehule<pavel(dot)stehule(at)gmail(dot)com> wrote:
> postgres=# select avg(a) from (select a, row_number() over (order by
> a) as r, count(*) over () as rc from x ) p where r in
> ((rc+1)/2,(rc+2)/2) ;

How does this compare to the plain non-windowing SQL implementation:

select a from x order by a offset (select trunc(count(*)/2) from x) limit 1

(except that that only works if count(*) is odd).

Interestingly finding the median is actually O(n) using Quickselect.
Maybe we should provide a C implementation of quickselect as a window
function. I'm not sure how to wedge in the concept that the sort is
unnecessary even though the ORDER BY is specified though.

I'm also not sure how to handle this if the set has to be spooled to
disk. Quicksort and Quickselect do a lot of scans throught he data and
wouldn't perform well on disk.

--
greg
http://mit.edu/~gsstark/resume.pdf