Create infrastructure for moving-aggregate optimization.

Until now, when executing an aggregate function as a window function
within a window with moving frame start (that is, any frame start mode
except UNBOUNDED PRECEDING), we had to recalculate the aggregate from
scratch each time the frame head moved.  This patch allows an aggregate
definition to include an alternate "moving aggregate" implementation
that includes an inverse transition function for removing rows from
the aggregate's running state.  As long as this can be done successfully,
runtime is proportional to the total number of input rows, rather than
to the number of input rows times the average frame length.

This commit includes the core infrastructure, documentation, and regression
tests using user-defined aggregates.  Follow-on commits will update some
of the built-in aggregates to use this feature.

David Rowley and Florian Pflug, reviewed by Dean Rasheed; additional
hacking by me

1 files changed, 28 insertions, 4 deletions

diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index 9613e2aec81..272d27f919e 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -1187,11 +1187,13 @@ resolve_aggregate_transtype(Oid aggfuncid,
  * For an ordered-set aggregate, remember that agg_input_types describes
  * the direct arguments followed by the aggregated arguments.
  *
- * transfn_oid and finalfn_oid identify the funcs to be called; the latter
- * may be InvalidOid.
+ * transfn_oid, invtransfn_oid and finalfn_oid identify the funcs to be
+ * called; the latter two may be InvalidOid.
  *
- * Pointers to the constructed trees are returned into *transfnexpr and
- * *finalfnexpr.  The latter is set to NULL if there's no finalfn.
+ * Pointers to the constructed trees are returned into *transfnexpr,
+ * *invtransfnexpr and *finalfnexpr. If there is no invtransfn or finalfn,
+ * the respective pointers are set to NULL.  Since use of the invtransfn is
+ * optional, NULL may be passed for invtransfnexpr.
  */
 void
 build_aggregate_fnexprs(Oid *agg_input_types,
@@ -1203,8 +1205,10 @@ build_aggregate_fnexprs(Oid *agg_input_types,
 						Oid agg_result_type,
 						Oid agg_input_collation,
 						Oid transfn_oid,
+						Oid invtransfn_oid,
 						Oid finalfn_oid,
 						Expr **transfnexpr,
+						Expr **invtransfnexpr,
 						Expr **finalfnexpr)
 {
 	Param	   *argp;
@@ -1249,6 +1253,26 @@ build_aggregate_fnexprs(Oid *agg_input_types,
 	fexpr->funcvariadic = agg_variadic;
 	*transfnexpr = (Expr *) fexpr;
 
+	/*
+	 * Build invtransfn expression if requested, with same args as transfn
+	 */
+	if (invtransfnexpr != NULL)
+	{
+		if (OidIsValid(invtransfn_oid))
+		{
+			fexpr = makeFuncExpr(invtransfn_oid,
+								 agg_state_type,
+								 args,
+								 InvalidOid,
+								 agg_input_collation,
+								 COERCE_EXPLICIT_CALL);
+			fexpr->funcvariadic = agg_variadic;
+			*invtransfnexpr = (Expr *) fexpr;
+		}
+		else
+			*invtransfnexpr = NULL;
+	}
+
 	/* see if we have a final function */
 	if (!OidIsValid(finalfn_oid))
 	{