Aggregate ORDER BY patch

Andrew Gierth wrote:

Herewith a patch to implement agg(foo ORDER BY bar) with or without
DISTINCT, etc.

What does that mean? Aggregate functions are supposed to be commutative,
right?

No artificial restrictions are imposed on what
syntactical combinations are allowed. However, ORDER BY is not allowed
with aggregates used as window functions (as per the existing
restriction on DISTINCT).

How is this different from window functions?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

On Fri, Nov 13, 2009 at 7:54 AM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:

Andrew Gierth wrote:

Herewith a patch to implement agg(foo ORDER BY bar) with or without
DISTINCT, etc.

What does that mean? Aggregate functions are supposed to be commutative,
right?

We certainly have non-commutative agggregates currently, notably array_agg()

I suspect it would be good to have a flag marking the commutative ones

--
greg

On fre, 2009-11-13 at 03:16 +0000, Andrew Gierth wrote:

Caveat: as discussed earlier, this patch changes the behaviour of
array_agg(DISTINCT x) when applied to NULL inputs. Formerly, the NULLs
were unconditionally skipped; now, they are treated just like DISTINCT
or GROUP BY normally do.

The right answer to that should be in the SQL standard.

Peter Eisentraut <peter_e@gmx.net> writes:

On fre, 2009-11-13 at 03:16 +0000, Andrew Gierth wrote:

Caveat: as discussed earlier, this patch changes the behaviour of
array_agg(DISTINCT x) when applied to NULL inputs. Formerly, the NULLs
were unconditionally skipped; now, they are treated just like DISTINCT
or GROUP BY normally do.

The right answer to that should be in the SQL standard.

It's not. The standard defines the behavior of certain specific
aggregates; it doesn't provide general rules that would apply to
user-defined aggregates. In particular, all the standard aggregates
are strict and so they just ignore nulls anyhow. The proposed change
would only affect the behavior of aggregates with non-strict transition
functions.

regards, tom lane

Greg Stark <gsstark@mit.edu> writes:

On Fri, Nov 13, 2009 at 7:54 AM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:

Andrew Gierth wrote:

Herewith a patch to implement agg(foo ORDER BY bar) with or without
DISTINCT, etc.

What does that mean? Aggregate functions are supposed to be commutative,
right?

We certainly have non-commutative agggregates currently, notably array_agg()

Right. The fact that none of the standard aggregates are
order-sensitive doesn't mean that it's not useful to have user-defined
ones that are. Currently we suggest fetching from an ordered sub-select
if you want to use an aggregate that is input order sensitive. This
patch just provides an alternative (and equally nonstandard) notation
for that.

I'm not entirely convinced that adding ORDER BY here is a good idea,
partly because it goes so far beyond the spec and partly because it's
not going to be easily optimizable. But I can see that there is a
use-case.

regards, tom lane

On fre, 2009-11-13 at 10:01 -0500, Tom Lane wrote:

Peter Eisentraut <peter_e@gmx.net> writes:

On fre, 2009-11-13 at 03:16 +0000, Andrew Gierth wrote:

Caveat: as discussed earlier, this patch changes the behaviour of
array_agg(DISTINCT x) when applied to NULL inputs. Formerly, the NULLs
were unconditionally skipped; now, they are treated just like DISTINCT
or GROUP BY normally do.

The right answer to that should be in the SQL standard.

It's not. The standard defines the behavior of certain specific
aggregates; it doesn't provide general rules that would apply to
user-defined aggregates.

But array_agg is in the standard.

On fre, 2009-11-13 at 10:35 -0500, Tom Lane wrote:

I'm not entirely convinced that adding ORDER BY here is a good idea,
partly because it goes so far beyond the spec

This is exactly the syntax that is in the spec AFAICT.

On Fri, Nov 13, 2009 at 10:35 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Greg Stark <gsstark@mit.edu> writes:

On Fri, Nov 13, 2009 at 7:54 AM, Heikki Linnakangas
<heikki.linnakangas@enterprisedb.com> wrote:

Andrew Gierth wrote:

Herewith a patch to implement agg(foo ORDER BY bar) with or without
DISTINCT, etc.

What does that mean? Aggregate functions are supposed to be commutative,
right?

We certainly have non-commutative agggregates currently, notably array_agg()

Right.  The fact that none of the standard aggregates are
order-sensitive doesn't mean that it's not useful to have user-defined
ones that are.  Currently we suggest fetching from an ordered sub-select
if you want to use an aggregate that is input order sensitive.  This
patch just provides an alternative (and equally nonstandard) notation
for that.

I'm not entirely convinced that adding ORDER BY here is a good idea,
partly because it goes so far beyond the spec and partly because it's
not going to be easily optimizable.  But I can see that there is a
use-case.

Yeah, for sure. I currently handle this, when necessary, by using
subselects, but it would sure be nice to have a more compact notation,
if there's a good way to do that.

...Robert

"Heikki" == Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:

Herewith a patch to implement agg(foo ORDER BY bar) with or
without DISTINCT, etc.

Heikki> What does that mean? Aggregate functions are supposed to be
Heikki> commutative, right?

The SQL spec defines two non-commutative aggregates that we implement:

array_agg(x ORDER BY ...)
xmlagg(x ORDER BY ...)

In addition, of course, we allow user-defined aggregates, which are
perfectly free to be non-commutative.

--
Andrew (irc:RhodiumToad)

"Peter" == Peter Eisentraut <peter_e@gmx.net> writes:

I'm not entirely convinced that adding ORDER BY here is a good idea,
partly because it goes so far beyond the spec

Peter> This is exactly the syntax that is in the spec AFAICT.

Right. The spec defines this syntax for array_agg and xmlagg (only).
The patch goes beyond the spec in that it allows ORDER BY for any
aggregate at all, and also allows combination of ORDER BY and DISTINCT
(the spec only allows DISTINCT with <general set operation> which
doesn't include array_agg or xmlagg, so there is nowhere that both are
allowed).

But it would be entirely unreasonable, the way postgres works, to
implement ORDER BY for only specific aggregates.

(Note also that combining ORDER BY and DISTINCT can change the
behaviour of DISTINCT. e.g. foo(distinct x order by x using <<<) will
use whatever definition of equality is implied by the hypothetical <<<
operator when comparing values of x for distinctness.)

As for the null handling, the spec is no help there for this reason:
it allows DISTINCT only for <general set operation>, and for all
<general set operation>s whether DISTINCT or not, NULLs are always
discarded from the input before processing (i.e. the behaviour we
implement for strict aggregates). So even the fact that we allow
array_agg(distinct x) at all is going beyond the spec and therefore
doesn't have a defined result.

--
Andrew (irc:RhodiumToad)

Andrew Gierth <andrew@tao11.riddles.org.uk> writes:

"Peter" == Peter Eisentraut <peter_e@gmx.net> writes:
Peter> This is exactly the syntax that is in the spec AFAICT.

Right. The spec defines this syntax for array_agg and xmlagg (only).

Cool, I had forgotten that they added that in the latest revisions.
I withdraw the complaint that this patch goes too far beyond the spec.

But it would be entirely unreasonable, the way postgres works, to
implement ORDER BY for only specific aggregates.

Quite. This is another instance of the thing I complained of before,
that the SQL committee likes to define the behavior of specific
aggregates instead of inducing a generic aggregate-behavior definition.
So we're on our own to extract one, and this proposal seems pretty
reasonable to me: it's useful and it's consistent with the query-level
behavior of DISTINCT and ORDER BY.

regards, tom lane

On Friday 13 November 2009 16:35:08 Tom Lane wrote:

Greg Stark <gsstark@mit.edu> writes:

On Fri, Nov 13, 2009 at 7:54 AM, Heikki Linnakangas

<heikki.linnakangas@enterprisedb.com> wrote:

Andrew Gierth wrote:

Herewith a patch to implement agg(foo ORDER BY bar) with or without
DISTINCT, etc.

What does that mean? Aggregate functions are supposed to be commutative,
right?

We certainly have non-commutative agggregates currently, notably
array_agg()

Right. The fact that none of the standard aggregates are
order-sensitive doesn't mean that it's not useful to have user-defined
ones that are. Currently we suggest fetching from an ordered sub-select
if you want to use an aggregate that is input order sensitive. This
patch just provides an alternative (and equally nonstandard) notation
for that.

I'm not entirely convinced that adding ORDER BY here is a good idea,
partly because it goes so far beyond the spec and partly because it's
not going to be easily optimizable. But I can see that there is a
use-case.

The spec supports the ORDER BY syntax for the xmlagg aggregate...

Andres

"Heikki" == Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:

No artificial restrictions are imposed on what syntactical
combinations are allowed. However, ORDER BY is not allowed with
aggregates used as window functions (as per the existing
restriction on DISTINCT).

Heikki> How is this different from window functions?

Window functions return a row for each row of input, aggregates don't.

The reason I didn't tackle the case of aggregate functions used as
window functions is that the spec allows constructs like this:

array_agg(a order by b) over (order by c)

which can't be represented using the aggregate-as-window-function
mechanism as it currently stands, since you'd have to re-sort the
window each time.

--
Andrew (irc:RhodiumToad)

2009/11/14 Andrew Gierth <andrew@tao11.riddles.org.uk>:

"Heikki" == Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:

 >> No artificial restrictions are imposed on what syntactical
 >> combinations are allowed. However, ORDER BY is not allowed with
 >> aggregates used as window functions (as per the existing
 >> restriction on DISTINCT).

 Heikki> How is this different from window functions?

Window functions return a row for each row of input, aggregates don't.

The reason I didn't tackle the case of aggregate functions used as
window functions is that the spec allows constructs like this:

array_agg(a order by b) over (order by c)

which can't be represented using the aggregate-as-window-function
mechanism as it currently stands, since you'd have to re-sort the
window each time.

Now I'm about to send my patch to introduce more frame types,
aggregate cache mechanism in window functions may be broken sometimes,
and it is *possible* to put order-by clause in argument list if we
prepare tuplesort as in nodeAgg. But I don't see useful cases and it
seems so hard task that I'm not sold.

Regards,

--
Hitoshi Harada

2009/11/14 Tom Lane <tgl@sss.pgh.pa.us>:

Andrew Gierth <andrew@tao11.riddles.org.uk> writes:

"Peter" == Peter Eisentraut <peter_e@gmx.net> writes:
 Peter> This is exactly the syntax that is in the spec AFAICT.

Right. The spec defines this syntax for array_agg and xmlagg (only).

Cool, I had forgotten that they added that in the latest revisions.
I withdraw the complaint that this patch goes too far beyond the spec.

But it would be entirely unreasonable, the way postgres works, to
implement ORDER BY for only specific aggregates.

Quite.  This is another instance of the thing I complained of before,
that the SQL committee likes to define the behavior of specific
aggregates instead of inducing a generic aggregate-behavior definition.
So we're on our own to extract one, and this proposal seems pretty
reasonable to me: it's useful and it's consistent with the query-level
behavior of DISTINCT and ORDER BY.

It's not only in aggregates but also window function as well as plain
functions like substring(x from t). In window functions, IGNORE NULLS
is defined in spec for those first_vlaue(), last_value(), lead(),
lag(), etc. but not for generic use. I'm +1 for an approach to apply
them for generic cases.

Regards,

--
Hitoshi Harada

On Fri, Nov 13, 2009 at 5:09 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:

Quite.  This is another instance of the thing I complained of before,
that the SQL committee likes to define the behavior of specific
aggregates instead of inducing a generic aggregate-behavior definition.

I think this makes sense from the point of view of the spec authors.
They're trying to standardize the behaviour of the functions that
their existing implementations provide without creating extra demands
on themselves to implement new features. Even if some of them do
implement more general solutions the path of least resistance to
getting their syntax standardized will be the one which imposes the
least cost on the other members of the committee.

So we're on our own to extract one, and this proposal seems pretty
reasonable to me: it's useful and it's consistent with the query-level
behavior of DISTINCT and ORDER BY.

++

--
greg

Here's my first review.

The patch was in context diff format and applied cleanly with a little
3 hunks in parse_expr.c. make succeeded without any warnings and make
check passed all 121 tests.

It implements as advertised, following SQL spec with extension of both
DISTINCT clause and ORDER BY clause are available in any aggregate
functions including user defined ones. It supports VIEWs by adding
code in ruleutils.c.

Questions here:
- agglevelsup?
We have aggregate capability that all arguments from upper level query
in downer level aggregate makes aggregate call itself to upper level
call, as a constant value in downer level. What if ORDER BY clause has
downer level Vars? For example:

regression=# select (select count(t1.four order by unique1) from tenk1
limit 1) from tenk1 t1 where unique1 < 10;
?column?
----------
10000
10000
10000
10000
10000
10000
10000
10000
10000
10000
(10 rows)

regression=# select (select count(t1.four order by t1.unique1) from
tenk1 limit 1) from tenk1 t1 where unique1 < 10;
?column?
----------
10
(1 row)

Is it sane? The result is consistent but surprised me a little. No
need to raise an error?

- order by 1?
Normal ORDER BY clause accepts constant integer as TargetEntry's
resno. The patch seems not to support it.

regression=# select array_agg(four order by 1) from tenk1 where unique1 < 10;
array_agg
-----------------------
{0,2,1,2,1,0,1,3,3,0}
(1 row)

Shouldn't it be the same as normal ORDER BY?

Performance doesn't seem slowing down, though I don't have
quantitative test result.

Coding, almost all sane. Since its syntax and semantics are similar to
existing DISTINCT and ORDER BY features, parsing and transformation
code are derived from those area. The executor has few issues:

- #include in nodeAgg.c
executor/tuptable.h is added in the patch but required really?
I removed that line but still build without any warnings.

- process_ordered_aggregate_(single|multi)
It seems that the patch left process_sorted_aggregate() function as
process_ordered_aggregate_single() and added
process_ordered_aggregate_multi() for more than one input arguments
(actually target entries) case. Why have those two? Could we combine
them? Or I couldn't find convincing reason in comments.

And ParseFuncOrColumn() in parse_func.c now gets more complicated.
Since feature / semantics are similar, I bet we may share some code to
transform DISTINCT and ORDER BY with traditional code in
parse_clause.c, though I'm not sure nor don't have clear idea.
Especially, code around here

save_next_resno = pstate->p_next_resno;
pstate->p_next_resno = attno + 1;

cheats pstate to transform clauses and I felt a bit fear.

- SortGroupClause.implicit
"implicit" member was added in SortGroupClause. I didn't find clear
reason to add this. Could you show a case to clarify this?

That's it for now.

Regards,

--
Hitoshi Harada

"Hitoshi" == Hitoshi Harada <umi.tanuki@gmail.com> writes:

Hitoshi> Questions here:
Hitoshi> - agglevelsup?

Hitoshi> We have aggregate capability that all arguments from upper
Hitoshi> level query in downer level aggregate makes aggregate call
Hitoshi> itself to upper level call, as a constant value in downer
Hitoshi> level. What if ORDER BY clause has downer level Vars?

For determining what query level the aggregate belongs to, the
expressions in the ORDER BY clause are counted along with the actual
argument expressions.

Hitoshi> Is it sane? The result is consistent but surprised me a
Hitoshi> little. No need to raise an error?

What case exactly would you consider an error? When an order by
expression references a lower (more deeply nested) query level than
any of the actual arguments?

Hitoshi> - order by 1?

Hitoshi> Normal ORDER BY clause accepts constant integer as
Hitoshi> TargetEntry's resno. The patch seems not to support it.
Hitoshi> Shouldn't it be the same as normal ORDER BY?

Specifically documented. The SQL spec doesn't allow ordinal positions
in ORDER BY any more (those are a holdover from SQL92) and we don't
support them in, for example, window ORDER BY clauses.

Hitoshi> Performance doesn't seem slowing down, though I don't have
Hitoshi> quantitative test result.

The performance is intended to be no worse than DISTINCT already was,
though it's also no better.

Hitoshi> Coding, almost all sane. Since its syntax and semantics are
Hitoshi> similar to existing DISTINCT and ORDER BY features, parsing
Hitoshi> and transformation code are derived from those area. The
Hitoshi> executor has few issues:

Hitoshi> - #include in nodeAgg.c
Hitoshi> executor/tuptable.h is added in the patch but required really?
Hitoshi> I removed that line but still build without any warnings.

The code is making explicit use of various Slot calls declared in
tuptable.h. The only reason why it builds without error when you
remove that is that utils/tuplesort.h happens to include tuptable.h
indirectly.

Hitoshi> - process_ordered_aggregate_(single|multi)
Hitoshi> It seems that the patch left process_sorted_aggregate()
Hitoshi> function as process_ordered_aggregate_single() and added
Hitoshi> process_ordered_aggregate_multi() for more than one input
Hitoshi> arguments (actually target entries) case. Why have those
Hitoshi> two? Could we combine them? Or I couldn't find convincing
Hitoshi> reason in comments.

Performance.

tuplesort_getdatum etc. seems to be substantially faster than
tuplesort_gettupleslot especially for the case where you're sorting a
pass-by-value datum such as an integer (since the datum is then stored
only in the sort tuple header and doesn't require a separate space
allocation for itself). Using a slot in all cases would have slowed
down some common cases like count(distinct id) by a measurable amount.

Cases like array_agg(x order by x) benefit from the faster code path
too.

The memory management between the two cases is sufficiently different
that combining them into one function while still maintaining the
slot vs. datum distinction would be ugly and probably error-prone.
The relatively minor duplication of logic seemed much clearer to me.

Hitoshi> And ParseFuncOrColumn() in parse_func.c now gets more
Hitoshi> complicated.

I thought very hard about breaking some of that out into a separate
function, but it wasn't initially clear which parts might have needed
access to the original raw parsetree. I'm open to opinions on this.

Hitoshi> Since feature / semantics are similar, I bet we may share
Hitoshi> some code to transform DISTINCT and ORDER BY with
Hitoshi> traditional code in parse_clause.c, though I'm not sure nor
Hitoshi> don't have clear idea. Especially, code around here

Hitoshi> save_next_resno = pstate->p_next_resno;
Hitoshi> pstate->p_next_resno = attno + 1;

Hitoshi> cheats pstate to transform clauses and I felt a bit fear.

The code that transforms RETURNING clauses does something similar with
p_next_resno.

Almost all the work of transforming the ORDER BY clause is actually
done via the existing transformSortClause (which is the reason why
p_next_resno needs to be saved and restored), the additional logic
is only for the DISTINCT case, to validate the correspondance between
DISTINCT args and ORDER BY args and to generate implicit ordering
clauses (which provide comparison function info to the executor)
when needed.

Hitoshi> - SortGroupClause.implicit
Hitoshi> "implicit" member was added in SortGroupClause. I didn't
Hitoshi> find clear reason to add this. Could you show a case to
Hitoshi> clarify this?

Without that flag or something like it, when you do

create view foo as select count(distinct x) from table;

and then display the view definition, you would get back the query as
"select count(distinct x order by x) from table" which would be
confusing and unnecessarily backwards- and forwards-incompatible.

So the code sets "implicit" for any SortGroupClause that is added for
some internal reason rather than being present in the original query,
and the deparse code in ruleutils skips such clauses.

--
Andrew.

"Andrew" == Andrew Gierth <andrew@tao11.riddles.org.uk> writes:

Andrew> Performance.

Andrew> tuplesort_getdatum etc. seems to be substantially faster than
Andrew> tuplesort_gettupleslot especially for the case where you're
Andrew> sorting a pass-by-value datum such as an integer (since the
Andrew> datum is then stored only in the sort tuple header and
Andrew> doesn't require a separate space allocation for
Andrew> itself). Using a slot in all cases would have slowed down
Andrew> some common cases like count(distinct id) by a measurable
Andrew> amount.

Andrew> Cases like array_agg(x order by x) benefit from the faster
Andrew> code path too.

Andrew> The memory management between the two cases is sufficiently
Andrew> different that combining them into one function while still
Andrew> maintaining the slot vs. datum distinction would be ugly and
Andrew> probably error-prone. The relatively minor duplication of
Andrew> logic seemed much clearer to me.

Just to quantify this, using a production-quality build (optimized and
without assertions), it turns out that the fast code path
(process_ordered_aggregate_single) is faster by 300% for pass-by-value
types, and by approximately 20% for short values of pass-by-reference
types, as compared to disabling that code path and forcing even the
one-arg case to use the slot interface.

So using the slot interface for everything would have constituted a
300% slowdown over the older code for count(distinct id), obviously
undesirable.

As it stands, I can't detect any performance regression over the
previous code.

This means that agg(x order by y) is rather noticably slower than
agg(x order by x), but this is pretty much unavoidable given how the
sorting code works.

Future performance enhancements (which I have no particular plans to
tackle) would involve having the planner consult the desired aggregate
orderings and estimating the cost of sorting as opposed to the cost of
producing a plan with the input already ordered. Also combining the
sort step for aggregates that share a single ordering.

--
Andrew (irc:RhodiumToad)