Thread: RFC: array_agg() per SQL:200n

RFC: array_agg() per SQL:200n

From
Neil Conway
Date:
I recently noticed that SQL:200n[1] defines a new aggregate function,
array_agg(). The relevant portions of the spec are:

p. 66: "If ARRAY_AGG is specified, then an array value with one element
formed from the <value expression> evaluated for each row that
qualifies."

p. 556: <array aggregate function> ::= ARRAY_AGG <left paren>     <value expression> [ ORDER BY <sort specification
list>] <right paren>
 

p. 564 discusses the required behavior. The result of array_agg() is an
array with one element per input value, sorted according to the optional
ORDER BY clause. NULL input values are included in the array, and the
result for an empty group is NULL, not an empty array. Note that per
page 66, I'd expect array values in the input to array_agg() not to be
flattened.

I'd like to implement array_agg() for 8.4. In the past, we've talked
about moving the array_accum() example aggregate into the backend[2].
Now that there's SQL-standard syntax, that's another reason to do it --
I think this is clearly useful functionality.

The previous discussion got tied up in how to expose the aggregate's
transition value to the type system. The problem is that the aggregate
wants to use a transition value that is not a SQL-level type, to allow
efficient array append operations. Various solutions were mooted about,
typically involving a pass-by-val pseudotype used to hold a pointer to
the C struct holding the transition state.

AFAIK the conclusion reached by the previous thread was that to be type
safe, you'd need one distinct pseudotype per aggregate function, along
with some way to let the planner distinguish this class of pseudotypes
from other types (in order to apply the heuristic that functions like
these are likely to consume more memory). You could identify this class
by an additional column in pg_type, but I think we'd need a lot of
machinery to do this properly (e.g. to allow these types to be created
via SQL). I wonder if this isn't over-engineering: the simple approach
originally followed by Stephen Frost was to declare the transition value
as, say, int8, and just disallow the transition and final functions from
being called outside an aggregate context. AFAIK this would be safe,
although of course it is ugly.

To parse the ORDER BY clause, we'd need to special-case array_agg() in
the grammar, which is a bit unfortunate. Implementation-wise, because
there is no way to lazily evaluate an array expression, I don't think
there's much to be gained by using the tuplesort infrastructure -- we'll
need to materialize the entire array into memory when the final function
is called anyway. Therefore, a simpler approach might be to just
accumulate inputs in the transition function as usual, and then qsort()
them in the final function. We could also have the planner arrange for
the sort to be skipped if it knows that the input to the aggregate will
be delivered in a compatible ordering.

Comments welcome.

-Neil

[1] http://www.wiscorp.com/SQLStandards.html ; apparently SQL:200n is
likely to become SQL:2008 without further changes.

[2] http://archives.postgresql.org/pgsql-hackers/2006-10/msg00362.php
http://archives.postgresql.org/pgsql-patches/2006-10/msg00059.php
http://archives.postgresql.org/pgsql-hackers/2006-10/msg00683.php




Re: RFC: array_agg() per SQL:200n

From
Gregory Stark
Date:
"Neil Conway" <neilc@samurai.com> writes:

> AFAIK the conclusion reached by the previous thread was that to be type
> safe, you'd need one distinct pseudotype per aggregate function, along
> with some way to let the planner distinguish this class of pseudotypes
> from other types (in order to apply the heuristic that functions like
> these are likely to consume more memory). You could identify this class
> by an additional column in pg_type, but I think we'd need a lot of
> machinery to do this properly (e.g. to allow these types to be created
> via SQL). I wonder if this isn't over-engineering: the simple approach
> originally followed by Stephen Frost was to declare the transition value
> as, say, int8, and just disallow the transition and final functions from
> being called outside an aggregate context. AFAIK this would be safe,
> although of course it is ugly.

The alternative is to use the regular array type and have the implementation
of it have some magic behind the scenes.

I was already thinking we might need some magic like this for read-only cases
like:

select * where i in array[1,3,5,...]

or 

for i in 1..nvar = arrayvar[i]...
end

Both of these are O(n^2) (assuming the size of the array and the number of
loop iterations are both n). Each array IN scan or index lookup is O(n).

These cases might be easier to deal with, my idea was to memoize the array
contents in a hash data structure referenced by the parse tree fnextra
pointer. The array functions would check their function call site's fnextra
pointer to see if the array has previously been cached in the more efficient
form and is the same array and then use either hash probes for the IN case or
a C datum array for the latter case.

Could the same be done by the aggregate call site where the aggregate's type
is a plain anyarray like normal, but the array_accum call would look at the
call site and stash the actual contents there in a linked list or tuplesort?
The actual anyarray data type would just have a flag saying "the data's over
there".

--  Gregory Stark EnterpriseDB          http://www.enterprisedb.com Ask me about EnterpriseDB's On-Demand Production
Tuning


Re: RFC: array_agg() per SQL:200n

From
Jeff Davis
Date:
On Sun, 2008-01-27 at 22:11 -0800, Neil Conway wrote:
> p. 564 discusses the required behavior. The result of array_agg() is an
> array with one element per input value, sorted according to the optional
> ORDER BY clause. NULL input values are included in the array, and the
> result for an empty group is NULL, not an empty array. Note that per
> page 66, I'd expect array values in the input to array_agg() not to be
> flattened.

Should there be an inverse operator (a SRF, in this case) that returns a
set from an array?

Regards,Jeff Davis



Re: RFC: array_agg() per SQL:200n

From
Joe Conway
Date:
Jeff Davis wrote:
> On Sun, 2008-01-27 at 22:11 -0800, Neil Conway wrote:
>> p. 564 discusses the required behavior. The result of array_agg() is an
>> array with one element per input value, sorted according to the optional
>> ORDER BY clause. NULL input values are included in the array, and the
>> result for an empty group is NULL, not an empty array. Note that per
>> page 66, I'd expect array values in the input to array_agg() not to be
>> flattened.
> 
> Should there be an inverse operator (a SRF, in this case) that returns a
> set from an array?

Yes -- see UNNEST

Joe


Re: RFC: array_agg() per SQL:200n

From
"Hitoshi Harada"
Date:
yet another inverse function I wrote before, though it applies for only 1D
array.

typedef struct _enuminfo{ArrayType    *data;char        *ptr;int16        typlen;bool        typbyval;char
typalign;
} EnumInfo;

Datum array_enum(PG_FUNCTION_ARGS){FuncCallContext *funcctx;MemoryContext oldcontext;ArrayType    *input;EnumInfo
*info;Datum       result;if(SRF_IS_FIRSTCALL()){    funcctx = SRF_FIRSTCALL_INIT();    oldcontext =
 
MemoryContextSwitchTo(funcctx->multi_call_memory_ctx);        input = PG_GETARG_ARRAYTYPE_P(0);    if(ARR_NDIM(input)
!=1){        elog(ERROR, "array_enum() accepts only one dimension
 
array.");    }    funcctx->max_calls = ArrayGetNItems(ARR_NDIM(input),
ARR_DIMS(input));        info = (EnumInfo*)palloc0(sizeof(EnumInfo));    info->data =
(ArrayType*)PG_DETOAST_DATUM_COPY(input);   info->ptr = ARR_DATA_PTR(info->data);    get_typlenbyvalalign(
info->data->elemtype,        &(info->typlen),         &(info->typbyval),         &(info->typalign)    );
funcctx->user_fctx= info;        MemoryContextSwitchTo(oldcontext);}funcctx = SRF_PERCALL_SETUP();info =
funcctx->user_fctx;if(funcctx->call_cntr< funcctx->max_calls){    /* Get source element */    result =
fetch_att(info->ptr,info->typbyval, info->typlen);
 
    info->ptr = att_addlength(info->ptr, info->typlen,
PointerGetDatum(info->ptr));    info->ptr = (char *) att_align(info->ptr, info->typalign);    SRF_RETURN_NEXT(funcctx,
result);}else{   SRF_RETURN_DONE(funcctx);}
 
}

Hitoshi Harada

> -----Original Message-----
> From: pgsql-hackers-owner@postgresql.org
> [mailto:pgsql-hackers-owner@postgresql.org] On Behalf Of Joe Conway
> Sent: Tuesday, January 29, 2008 11:00 AM
> To: Jeff Davis
> Cc: Neil Conway; pgsql-hackers
> Subject: Re: [HACKERS] RFC: array_agg() per SQL:200n
> 
> Jeff Davis wrote:
> > On Sun, 2008-01-27 at 22:11 -0800, Neil Conway wrote:
> >> p. 564 discusses the required behavior. The result of array_agg() is an
> >> array with one element per input value, sorted according to the optional
> >> ORDER BY clause. NULL input values are included in the array, and the
> >> result for an empty group is NULL, not an empty array. Note that per
> >> page 66, I'd expect array values in the input to array_agg() not to be
> >> flattened.
> >
> > Should there be an inverse operator (a SRF, in this case) that returns a
> > set from an array?
> 
> Yes -- see UNNEST
> 
> Joe
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 9: In versions below 8.0, the planner will ignore your desire to
>        choose an index scan if your joining column's datatypes do not
>        match



Re: RFC: array_agg() per SQL:200n

From
Peter Eisentraut
Date:
Am Montag, 28. Januar 2008 schrieb Neil Conway:
> To parse the ORDER BY clause, we'd need to special-case array_agg() in
> the grammar

The ORDER BY clause would also used in XMLAGG, so we should try to parse this 
in a generalized way.

-- 
Peter Eisentraut
http://developer.postgresql.org/~petere/


Re: RFC: array_agg() per SQL:200n

From
Neil Conway
Date:
On Tue, 2008-01-29 at 13:06 +0100, Peter Eisentraut wrote:
> The ORDER BY clause would also used in XMLAGG, so we should try to parse this 
> in a generalized way.

Yeah, that should be doable. We could go further and expose ORDER BY to
CREATE AGGREGATE, so that users could write aggregates that are
guaranteed to see their input in a certain order. This would be rather
more complicated to implement, though (for one thing, you couldn't do
the "qsort in the final function" trick -- the input to the agg would
need to be presented in the right order, which might differ from the
ordering required by the rest of the query block. We'll need to arrange
for something vaguely similar to do window functions, though.)

-Neil




Re: RFC: array_agg() per SQL:200n

From
Bruce Momjian
Date:
Add to TODO:

* Add SQL-standard array_agg() and unnest() array functions
 http://archives.postgresql.org/pgsql-hackers/2008-01/msg01017.php


---------------------------------------------------------------------------

Neil Conway wrote:
> I recently noticed that SQL:200n[1] defines a new aggregate function,
> array_agg(). The relevant portions of the spec are:
> 
> p. 66: "If ARRAY_AGG is specified, then an array value with one element
> formed from the <value expression> evaluated for each row that
> qualifies."
> 
> p. 556: <array aggregate function> ::=
>   ARRAY_AGG <left paren>
>       <value expression> [ ORDER BY <sort specification list> ]
>   <right paren>
> 
> p. 564 discusses the required behavior. The result of array_agg() is an
> array with one element per input value, sorted according to the optional
> ORDER BY clause. NULL input values are included in the array, and the
> result for an empty group is NULL, not an empty array. Note that per
> page 66, I'd expect array values in the input to array_agg() not to be
> flattened.
> 
> I'd like to implement array_agg() for 8.4. In the past, we've talked
> about moving the array_accum() example aggregate into the backend[2].
> Now that there's SQL-standard syntax, that's another reason to do it --
> I think this is clearly useful functionality.
> 
> The previous discussion got tied up in how to expose the aggregate's
> transition value to the type system. The problem is that the aggregate
> wants to use a transition value that is not a SQL-level type, to allow
> efficient array append operations. Various solutions were mooted about,
> typically involving a pass-by-val pseudotype used to hold a pointer to
> the C struct holding the transition state.
> 
> AFAIK the conclusion reached by the previous thread was that to be type
> safe, you'd need one distinct pseudotype per aggregate function, along
> with some way to let the planner distinguish this class of pseudotypes
> from other types (in order to apply the heuristic that functions like
> these are likely to consume more memory). You could identify this class
> by an additional column in pg_type, but I think we'd need a lot of
> machinery to do this properly (e.g. to allow these types to be created
> via SQL). I wonder if this isn't over-engineering: the simple approach
> originally followed by Stephen Frost was to declare the transition value
> as, say, int8, and just disallow the transition and final functions from
> being called outside an aggregate context. AFAIK this would be safe,
> although of course it is ugly.
> 
> To parse the ORDER BY clause, we'd need to special-case array_agg() in
> the grammar, which is a bit unfortunate. Implementation-wise, because
> there is no way to lazily evaluate an array expression, I don't think
> there's much to be gained by using the tuplesort infrastructure -- we'll
> need to materialize the entire array into memory when the final function
> is called anyway. Therefore, a simpler approach might be to just
> accumulate inputs in the transition function as usual, and then qsort()
> them in the final function. We could also have the planner arrange for
> the sort to be skipped if it knows that the input to the aggregate will
> be delivered in a compatible ordering.
> 
> Comments welcome.
> 
> -Neil
> 
> [1] http://www.wiscorp.com/SQLStandards.html ; apparently SQL:200n is
> likely to become SQL:2008 without further changes.
> 
> [2] http://archives.postgresql.org/pgsql-hackers/2006-10/msg00362.php
>     http://archives.postgresql.org/pgsql-patches/2006-10/msg00059.php
>     http://archives.postgresql.org/pgsql-hackers/2006-10/msg00683.php
> 
> 
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 4: Have you searched our list archives?
> 
>                http://archives.postgresql.org

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://postgres.enterprisedb.com
 + If your life is a hard drive, Christ can be your backup. +