RFC: array_agg() per SQL:200n

"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..n
var = 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

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

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

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

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/

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

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. +