Re: slow count in window query

2009/7/16 Greg Stark <gsstark(at)mit(dot)edu>:
> 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.

median() should be aggregate, not window function, shouldn't it?

>
> 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.

The WindowAgg spools rows into the tuplestore, which holds the data in
memory as far as it fits in. Do you have any idea how it stores
millons of millions of rows without tuplestore?

Regards,

--
Hitoshi Harada