Re: slow count in window query - Mailing list pgsql-hackers

From Hitoshi Harada
Subject Re: slow count in window query
Date
Msg-id e08cc0400907160605m54ad9843p7f76fcb71eb26acf@mail.gmail.com
Whole thread Raw
In response to Re: slow count in window query  (Greg Stark <gsstark@mit.edu>)
Responses Re: slow count in window query
List pgsql-hackers
2009/7/16 Greg Stark <gsstark@mit.edu>:
> On Wed, Jul 15, 2009 at 11:18 AM, Pavel Stehule<pavel.stehule@gmail.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


pgsql-hackers by date:

Previous
From: Tom Lane
Date:
Subject: Re: [GENERAL] pg_migrator not setting values of sequences?
Next
From: Tom Lane
Date:
Subject: Re: Review remove {join,from}_collapse_limit, add enable_join_ordering