Add COST and ROWS options to CREATE/ALTER FUNCTION, plus underlying pg_proc

columns procost and prorows, to allow simple user adjustment of the estimated
cost of a function call, as well as control of the estimated number of rows
returned by a set-returning function.  We might eventually wish to extend this
to allow function-specific estimation routines, but there seems to be
consensus that we should try a simple constant estimate first.  In particular
this provides a relatively simple way to control the order in which different
WHERE clauses are applied in a plan node, which is a Good Thing in view of the
fact that the recent EquivalenceClass planner rewrite made that much less
predictable than before.

1 files changed, 106 insertions, 62 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 143b04ca9cb..36f22c881c8 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -10,7 +10,7 @@
  *
  *
  * IDENTIFICATION
- *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.222 2007/01/20 20:45:39 tgl Exp $
+ *	  $PostgreSQL: pgsql/src/backend/optimizer/plan/createplan.c,v 1.223 2007/01/22 01:35:20 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -411,14 +411,15 @@ create_gating_plan(PlannerInfo *root, Plan *plan, List *quals)
 {
 	List	   *pseudoconstants;
 
+	/* Sort into desirable execution order while still in RestrictInfo form */
+	quals = order_qual_clauses(root, quals);
+
 	/* Pull out any pseudoconstant quals from the RestrictInfo list */
 	pseudoconstants = extract_actual_clauses(quals, true);
 
 	if (!pseudoconstants)
 		return plan;
 
-	pseudoconstants = order_qual_clauses(root, pseudoconstants);
-
 	return (Plan *) make_result((List *) copyObject(plan->targetlist),
 								(Node *) pseudoconstants,
 								plan);
@@ -553,6 +554,8 @@ create_result_plan(PlannerInfo *root, ResultPath *best_path)
 	Assert(best_path->path.parent == NULL);
 	tlist = NIL;
 
+	/* best_path->quals is just bare clauses */
+
 	quals = order_qual_clauses(root, best_path->quals);
 
 	return make_result(tlist, (Node *) quals, NULL);
@@ -810,12 +813,12 @@ create_seqscan_plan(PlannerInfo *root, Path *best_path,
 	Assert(scan_relid > 0);
 	Assert(best_path->parent->rtekind == RTE_RELATION);
 
-	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
-	scan_clauses = extract_actual_clauses(scan_clauses, false);
-
 	/* Sort clauses into best execution order */
 	scan_clauses = order_qual_clauses(root, scan_clauses);
 
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
 	scan_plan = make_seqscan(tlist,
 							 scan_clauses,
 							 scan_relid);
@@ -916,10 +919,6 @@ create_indexscan_plan(PlannerInfo *root,
 	 * predicate, but only in a plain SELECT; when scanning a target relation
 	 * of UPDATE/DELETE/SELECT FOR UPDATE, we must leave such quals in the
 	 * plan so that they'll be properly rechecked by EvalPlanQual testing.
-	 *
-	 * While at it, we strip off the RestrictInfos to produce a list of plain
-	 * expressions (this loop replaces extract_actual_clauses used in the
-	 * other routines in this file).  We have to ignore pseudoconstants.
 	 */
 	qpqual = NIL;
 	foreach(l, scan_clauses)
@@ -928,7 +927,7 @@ create_indexscan_plan(PlannerInfo *root,
 
 		Assert(IsA(rinfo, RestrictInfo));
 		if (rinfo->pseudoconstant)
-			continue;
+			continue;			/* we may drop pseudoconstants here */
 		if (list_member_ptr(nonlossy_indexquals, rinfo))
 			continue;
 		if (!contain_mutable_functions((Node *) rinfo->clause))
@@ -946,12 +945,15 @@ create_indexscan_plan(PlannerInfo *root,
 						continue;
 			}
 		}
-		qpqual = lappend(qpqual, rinfo->clause);
+		qpqual = lappend(qpqual, rinfo);
 	}
 
 	/* Sort clauses into best execution order */
 	qpqual = order_qual_clauses(root, qpqual);
 
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	qpqual = extract_actual_clauses(qpqual, false);
+
 	/* Finally ready to build the plan node */
 	scan_plan = make_indexscan(tlist,
 							   qpqual,
@@ -1281,6 +1283,9 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	Assert(scan_relid > 0);
 	Assert(best_path->path.parent->rtekind == RTE_RELATION);
 
+	/* Sort clauses into best execution order */
+	scan_clauses = order_qual_clauses(root, scan_clauses);
+
 	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
@@ -1293,9 +1298,6 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 		ortidquals = list_make1(make_orclause(ortidquals));
 	scan_clauses = list_difference(scan_clauses, ortidquals);
 
-	/* Sort clauses into best execution order */
-	scan_clauses = order_qual_clauses(root, scan_clauses);
-
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,
@@ -1322,12 +1324,12 @@ create_subqueryscan_plan(PlannerInfo *root, Path *best_path,
 	Assert(scan_relid > 0);
 	Assert(best_path->parent->rtekind == RTE_SUBQUERY);
 
-	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
-	scan_clauses = extract_actual_clauses(scan_clauses, false);
-
 	/* Sort clauses into best execution order */
 	scan_clauses = order_qual_clauses(root, scan_clauses);
 
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
 	scan_plan = make_subqueryscan(tlist,
 								  scan_clauses,
 								  scan_relid,
@@ -1354,12 +1356,12 @@ create_functionscan_plan(PlannerInfo *root, Path *best_path,
 	Assert(scan_relid > 0);
 	Assert(best_path->parent->rtekind == RTE_FUNCTION);
 
-	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
-	scan_clauses = extract_actual_clauses(scan_clauses, false);
-
 	/* Sort clauses into best execution order */
 	scan_clauses = order_qual_clauses(root, scan_clauses);
 
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
 	scan_plan = make_functionscan(tlist, scan_clauses, scan_relid);
 
 	copy_path_costsize(&scan_plan->scan.plan, best_path);
@@ -1383,12 +1385,12 @@ create_valuesscan_plan(PlannerInfo *root, Path *best_path,
 	Assert(scan_relid > 0);
 	Assert(best_path->parent->rtekind == RTE_VALUES);
 
-	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
-	scan_clauses = extract_actual_clauses(scan_clauses, false);
-
 	/* Sort clauses into best execution order */
 	scan_clauses = order_qual_clauses(root, scan_clauses);
 
+	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	scan_clauses = extract_actual_clauses(scan_clauses, false);
+
 	scan_plan = make_valuesscan(tlist, scan_clauses, scan_relid);
 
 	copy_path_costsize(&scan_plan->scan.plan, best_path);
@@ -1471,6 +1473,9 @@ create_nestloop_plan(PlannerInfo *root,
 		}
 	}
 
+	/* Sort join qual clauses into best execution order */
+	joinrestrictclauses = order_qual_clauses(root, joinrestrictclauses);
+
 	/* Get the join qual clauses (in plain expression form) */
 	/* Any pseudoconstant clauses are ignored here */
 	if (IS_OUTER_JOIN(best_path->jointype))
@@ -1485,10 +1490,6 @@ create_nestloop_plan(PlannerInfo *root,
 		otherclauses = NIL;
 	}
 
-	/* Sort clauses into best execution order */
-	joinclauses = order_qual_clauses(root, joinclauses);
-	otherclauses = order_qual_clauses(root, otherclauses);
-
 	join_plan = make_nestloop(tlist,
 							  joinclauses,
 							  otherclauses,
@@ -1527,18 +1528,21 @@ create_mergejoin_plan(PlannerInfo *root,
 	ListCell   *lop;
 	ListCell   *lip;
 
+	/* Sort join qual clauses into best execution order */
+	/* NB: do NOT reorder the mergeclauses */
+	joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
+
 	/* Get the join qual clauses (in plain expression form) */
 	/* Any pseudoconstant clauses are ignored here */
 	if (IS_OUTER_JOIN(best_path->jpath.jointype))
 	{
-		extract_actual_join_clauses(best_path->jpath.joinrestrictinfo,
+		extract_actual_join_clauses(joinclauses,
 									&joinclauses, &otherclauses);
 	}
 	else
 	{
 		/* We can treat all clauses alike for an inner join */
-		joinclauses = extract_actual_clauses(best_path->jpath.joinrestrictinfo,
-											 false);
+		joinclauses = extract_actual_clauses(joinclauses, false);
 		otherclauses = NIL;
 	}
 
@@ -1557,11 +1561,6 @@ create_mergejoin_plan(PlannerInfo *root,
 	mergeclauses = get_switched_clauses(best_path->path_mergeclauses,
 							 best_path->jpath.outerjoinpath->parent->relids);
 
-	/* Sort clauses into best execution order */
-	/* NB: do NOT reorder the mergeclauses */
-	joinclauses = order_qual_clauses(root, joinclauses);
-	otherclauses = order_qual_clauses(root, otherclauses);
-
 	/*
 	 * Create explicit sort nodes for the outer and inner join paths if
 	 * necessary.  The sort cost was already accounted for in the path. Make
@@ -1699,18 +1698,21 @@ create_hashjoin_plan(PlannerInfo *root,
 	HashJoin   *join_plan;
 	Hash	   *hash_plan;
 
+	/* Sort join qual clauses into best execution order */
+	joinclauses = order_qual_clauses(root, best_path->jpath.joinrestrictinfo);
+	/* There's no point in sorting the hash clauses ... */
+
 	/* Get the join qual clauses (in plain expression form) */
 	/* Any pseudoconstant clauses are ignored here */
 	if (IS_OUTER_JOIN(best_path->jpath.jointype))
 	{
-		extract_actual_join_clauses(best_path->jpath.joinrestrictinfo,
+		extract_actual_join_clauses(joinclauses,
 									&joinclauses, &otherclauses);
 	}
 	else
 	{
 		/* We can treat all clauses alike for an inner join */
-		joinclauses = extract_actual_clauses(best_path->jpath.joinrestrictinfo,
-											 false);
+		joinclauses = extract_actual_clauses(joinclauses, false);
 		otherclauses = NIL;
 	}
 
@@ -1728,11 +1730,6 @@ create_hashjoin_plan(PlannerInfo *root,
 	hashclauses = get_switched_clauses(best_path->path_hashclauses,
 							 best_path->jpath.outerjoinpath->parent->relids);
 
-	/* Sort clauses into best execution order */
-	joinclauses = order_qual_clauses(root, joinclauses);
-	otherclauses = order_qual_clauses(root, otherclauses);
-	hashclauses = order_qual_clauses(root, hashclauses);
-
 	/* We don't want any excess columns in the hashed tuples */
 	disuse_physical_tlist(inner_plan, best_path->jpath.innerjoinpath);
 
@@ -2065,35 +2062,82 @@ get_switched_clauses(List *clauses, Relids outerrelids)
  *		in at runtime.
  *
  * Ideally the order should be driven by a combination of execution cost and
- * selectivity, but unfortunately we have so little information about
- * execution cost of operators that it's really hard to do anything smart.
- * For now, we just move any quals that contain SubPlan references (but not
- * InitPlan references) to the end of the list.
+ * selectivity, but it's not immediately clear how to account for both,
+ * and given the uncertainty of the estimates the reliability of the decisions
+ * would be doubtful anyway.  So we just order by estimated per-tuple cost,
+ * being careful not to change the order when (as is often the case) the
+ * estimates are identical.
+ *
+ * Although this will work on either bare clauses or RestrictInfos, it's
+ * much faster to apply it to RestrictInfos, since it can re-use cost
+ * information that is cached in RestrictInfos.
+ *
+ * Note: some callers pass lists that contain entries that will later be
+ * removed; this is the easiest way to let this routine see RestrictInfos
+ * instead of bare clauses.  It's OK because we only sort by cost, but
+ * a cost/selectivity combination would likely do the wrong thing.
  */
 static List *
 order_qual_clauses(PlannerInfo *root, List *clauses)
 {
-	List	   *nosubplans;
-	List	   *withsubplans;
-	ListCell   *l;
+	typedef struct
+	{
+		Node   *clause;
+		Cost	cost;
+	} QualItem;
+	int			nitems = list_length(clauses);
+	QualItem   *items;
+	ListCell   *lc;
+	int			i;
+	List	   *result;
 
-	/* No need to work hard if the query is subselect-free */
-	if (!root->parse->hasSubLinks)
+	/* No need to work hard for 0 or 1 clause */
+	if (nitems <= 1)
 		return clauses;
 
-	nosubplans = NIL;
-	withsubplans = NIL;
-	foreach(l, clauses)
+	/*
+	 * Collect the items and costs into an array.  This is to avoid repeated
+	 * cost_qual_eval work if the inputs aren't RestrictInfos.
+	 */
+	items = (QualItem *) palloc(nitems * sizeof(QualItem));
+	i = 0;
+	foreach(lc, clauses)
 	{
-		Node	   *clause = (Node *) lfirst(l);
+		Node	   *clause = (Node *) lfirst(lc);
+		QualCost	qcost;
 
-		if (contain_subplans(clause))
-			withsubplans = lappend(withsubplans, clause);
-		else
-			nosubplans = lappend(nosubplans, clause);
+		cost_qual_eval_node(&qcost, clause);
+		items[i].clause = clause;
+		items[i].cost = qcost.per_tuple;
+		i++;
 	}
 
-	return list_concat(nosubplans, withsubplans);
+	/*
+	 * Sort.  We don't use qsort() because it's not guaranteed stable for
+	 * equal keys.  The expected number of entries is small enough that
+	 * a simple insertion sort should be good enough.
+	 */
+	for (i = 1; i < nitems; i++)
+	{
+		QualItem	newitem = items[i];
+		int			j;
+
+		/* insert newitem into the already-sorted subarray */
+		for (j = i; j > 0; j--)
+		{
+			if (newitem.cost >= items[j-1].cost)
+				break;
+			items[j] = items[j-1];
+		}
+		items[j] = newitem;
+	}
+
+	/* Convert back to a list */
+	result = NIL;
+	for (i = 0; i < nitems; i++)
+		result = lappend(result, items[i].clause);
+
+	return result;
 }
 
 /*