Re: Planning aggregates which require sorted or distinct

On Sat, 2007-01-20 at 15:58 +1100, Gavin Sherry wrote:
> On Fri, 19 Jan 2007, Tom Lane wrote:
>
> > Gavin Sherry <swm(at)alcove(dot)com(dot)au> writes:
> > > On Fri, 19 Jan 2007, Tom Lane wrote:
> > >> Er, what primary key would that be exactly? And even if you had a key,
> > >> I wouldn't call joining on it trivial; I'd call it expensive ...
> >
> > > I should have used slightly different language. What I meant to say was,
> > > both sets are primarily sorted by saledate so they can be merged back
> > > together. This is why I said it was trivial.

Yes, your fan out plan sounds best, together with the optimisation to
remove whatever you call the individual strands of the fan-out. Think of
a good name now, so we can discuss it more easily...

> Yep. I was thinking about this all morning. I think I've over engineered
> the problem in my head. Window function input just looks like a slightly
> more complex distinct aggregate input. I'll think on it more though.

I'm working on modifying Tuplestore that will allow you to store the
last N tuples, rather than all previous input. This is specifically
designed to allow Merge Join to do Mark/Restore without materializing
the whole sort set. This can also be used to materialize Windows (i.e.
<window clause> in SQL:2003), so you can store the current row plus n
PRECEDING and/or n FOLLOWING rows as appropriate. Reading from the
Window would then be similar-ish to doing a Mark/Restore pair, which we
can rename to MarkWindowStart and ReturnToWindowStart.

I'll present the prototype shortly, I've got a few bugs, but the basic
principle is working already. I'm happy to craft that to your exact
needs, so that you'll be able to press ahead with the rest of the
implementation of Windowed functions.

The Materialize node is almost unchanged, but I was thinking of renaming
it when used in this way to make the EXPLAIN more readable. Perhaps we
should call it a Materialized Window for both the MJ and Window function
cases.

This won't help with UNBOUNDED window definitions, but I imagine that
these are best handled by running aggregates which would be an O(N)
operation, rather than recalculating everything each time, which would
be O(N^2).

> To bring out a slightly different point -- and I know this is putting the
> cart before the horse -- but window functions will (potentially) output
> rows in the wrong order. I made a passing reference to this earlier. For
> example, say we have a table employees with the following data:
>
> empno | salary | age
> ====================
> 1 | 2000 | 50
> 2 | 6000 | 30
> 3 | 3000 | 20
>
> We want to answer the following: for each employee: what is their rank in
> terms of salary and what is their rank in terms of age. This query
> answers that:
>
> select empno, rank() over (order by salary) as srank,
> rank() over (order by age) as arank
> from employees order by empno;
>
> The result will be:
>
> empno | salary | age
> ====================
> 1 | 1 | 3
> 2 | 3 | 2
> 3 | 2 | 1
>
> Both window functions provide results based on the order of their input.
> So, in terms of empno, srank will output in this order: empno = 1, 3, 2;
> arank will output in this order: empno = 3, 2, 1. We need to glue these
> back together and the only way I can think how is via a synthetic key.

Anything wrong with using empno?

> Ideally, the planner would have some input on how to clue about how large
> the result set will be and the orders from the window functions so that it
> can decide whether to use nested loop, merge join or hash join to do it.
>
> Can you think of a different approach?

Sounds like figuring out and agreeing the executor issues first is the
best bet. Once we know whats to be done, extending the planner to do it
will be easier.

--
Simon Riggs
EnterpriseDB http://www.enterprisedb.com