Thread: RFC: array_agg() per SQL:200n
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
"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
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 > -----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
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. +