On 4 October 2010 07:36, Hitoshi Harada <umi.tan...@gmail.com> wrote: > 2010/10/4 Greg Stark <gsst...@mit.edu>: >> On Sun, Oct 3, 2010 at 7:06 AM, Hitoshi Harada <umi.tan...@gmail.com> wrote: >>> And I'm now thinking about how to make median happen in window >>> aggregate. >> >> If you were to do this by extending tuplesort what extra features >> would tuplesort need? > > I don't think we need to extend tuplesort when we do it. IMO this can > make happen by fetching all the values in the frame and performing > sort once, then getting current position and calculate median. The > only thing I consider is to mark and to go to the demanded position in > tuplesort like tuplestore, but actually we can manage to median() > without such facilities. >
I dont' think that works, because the ORDER BY in the WINDOW doesn't necessarily match the sort order that the median function needs. Consider for example: select a, median(a) over(order by a desc) from generate_series(1,10) as g(a); a | median ----+-------------------- 10 | 10 9 | 9.5000000000000000 8 | 9 7 | 8.5000000000000000 6 | 8 5 | 7.5000000000000000 4 | 7 3 | 6.5000000000000000 2 | 6 1 | 5.5000000000000000 (10 rows) That requires a new sort for each row. I generated this with a minor tweak to Pavel's patch to just restart the tuplesort each time (the "quick-fix" solution). The problem is that performance really sucks, because it is an O(n^2 log(n)) algorithm. I don't see an easy way around that without significant new infrastructure, as Greg describes, or a completely different algorithm. >> How do existing windowed aggregates work if you specify an order by on >> the aggregate? Do they resort for every output row? > Isn't the issue that they don't need to sort, so they all work unchanged. Regards, Dean > I don't know the true specification of median() nor the behavior of it > in other RDBs, but I bet median is median and ORDER BY in window > clause doesn't affect its result. ORDER BY specifies only the frame > boundary. > > Regards, > > > > -- > Hitoshi Harada > > -- > Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) > To make changes to your subscription: > http://www.postgresql.org/mailpref/pgsql-hackers > -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
