Major revision of sort-node handling: push knowledge of query

sort order down into planner, instead of handling it only at the very top
level of the planner.  This fixes many things.  An explicit sort is now
avoided if there is a cheaper alternative (typically an indexscan) not
only for ORDER BY, but also for the internal sort of GROUP BY.  It works
even when there is no other reason (such as a WHERE condition) to consider
the indexscan.  It works for indexes on functions.  It works for indexes
on functions, backwards.  It's just so cool...

CAUTION: I have changed the representation of SortClause nodes, therefore
THIS UPDATE BREAKS STORED RULES.  You will need to initdb.

4 files changed, 144 insertions, 132 deletions

diff --git a/src/backend/parser/analyze.c b/src/backend/parser/analyze.c
index e3c9feb677c..2c4d1c7a7e8 100644
--- a/src/backend/parser/analyze.c
+++ b/src/backend/parser/analyze.c
@@ -5,7 +5,7 @@
  *
  * Copyright (c) 1994, Regents of the University of California
  *
- *	$Id: analyze.c,v 1.117 1999/08/15 06:46:49 thomas Exp $
+ *	$Id: analyze.c,v 1.118 1999/08/21 03:48:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -293,7 +293,6 @@ transformInsertStmt(ParseState *pstate, InsertStmt *stmt)
 	 */
 	qry->sortClause = transformSortClause(pstate,
 										  NIL,
-										  NIL,
 										  qry->targetList,
 										  qry->uniqueFlag);
 
@@ -1039,7 +1038,6 @@ transformSelectStmt(ParseState *pstate, SelectStmt *stmt)
 
 	qry->sortClause = transformSortClause(pstate,
 										  stmt->sortClause,
-										  NIL,
 										  qry->targetList,
 										  qry->uniqueFlag);
 
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index 3cca6d681fc..a5007822976 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_agg.c,v 1.27 1999/08/16 02:10:13 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_agg.c,v 1.28 1999/08/21 03:48:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -154,7 +154,7 @@ parseCheckAggregates(ParseState *pstate, Query *qry)
 		GroupClause *grpcl = lfirst(tl);
 		Node		*expr;
 
-		expr = (Node *) get_groupclause_expr(grpcl, qry->targetList);
+		expr = get_sortgroupclause_expr(grpcl, qry->targetList);
 		if (contain_agg_clause(expr))
 			elog(ERROR, "Aggregates not allowed in GROUP BY clause");
 		groupClauses = lcons(expr, groupClauses);
@@ -293,10 +293,8 @@ ParseAgg(ParseState *pstate, char *aggname, Oid basetype,
 	aggref->aggname = pstrdup(aggname);
 	aggref->basetype = aggform->aggbasetype;
 	aggref->aggtype = fintype;
-
 	aggref->target = lfirst(target);
-	if (usenulls)
-		aggref->usenulls = true;
+	aggref->usenulls = usenulls;
 
 	pstate->p_hasAggs = true;
 
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index 275d131baba..234987fb5f0 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_clause.c,v 1.43 1999/08/16 02:10:13 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_clause.c,v 1.44 1999/08/21 03:48:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -34,6 +34,9 @@ static TargetEntry *findTargetlistEntry(ParseState *pstate, Node *node,
 										List *tlist, int clause);
 static void parseFromClause(ParseState *pstate, List *frmList, Node **qual);
 static char	*transformTableEntry(ParseState *pstate, RangeVar *r);
+static List *addTargetToSortList(TargetEntry *tle, List *sortlist,
+								 List *targetlist, char *opname);
+static bool exprIsInSortList(Node *expr, List *sortList, List *targetList);
 
 #ifdef ENABLE_OUTER_JOINS
 static Node *transformUsingClause(ParseState *pstate, List *onList,
@@ -464,39 +467,25 @@ List *
 transformGroupClause(ParseState *pstate, List *grouplist, List *targetlist)
 {
 	List	   *glist = NIL,
-			   *gl,
-			   *othergl;
-	int			nextgroupref = 1;
+			   *gl;
 
 	foreach(gl, grouplist)
 	{
-		TargetEntry *restarget;
-		Resdom	   *resdom;
+		TargetEntry *tle;
 
-		restarget = findTargetlistEntry(pstate, lfirst(gl),
-										targetlist, GROUP_CLAUSE);
-		resdom = restarget->resdom;
+		tle = findTargetlistEntry(pstate, lfirst(gl),
+								  targetlist, GROUP_CLAUSE);
 
 		/* avoid making duplicate grouplist entries */
-		foreach(othergl, glist)
-		{
-			GroupClause *gcl = (GroupClause *) lfirst(othergl);
-
-			if (equal(get_groupclause_expr(gcl, targetlist),
-					  restarget->expr))
-				break;
-		}
-
-		if (othergl == NIL)		/* not in grouplist already */
+		if (! exprIsInSortList(tle->expr, glist, targetlist))
 		{
 			GroupClause *grpcl = makeNode(GroupClause);
 
-			grpcl->tleGroupref = nextgroupref++;
-			resdom->resgroupref = grpcl->tleGroupref;
+			grpcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
 
-			grpcl->grpOpoid = oprid(oper("<",
-										 resdom->restype,
-										 resdom->restype, false));
+			grpcl->sortop = oprid(oper("<",
+									   tle->resdom->restype,
+									   tle->resdom->restype, false));
 
 			glist = lappend(glist, grpcl);
 		}
@@ -513,141 +502,169 @@ transformGroupClause(ParseState *pstate, List *grouplist, List *targetlist)
 List *
 transformSortClause(ParseState *pstate,
 					List *orderlist,
-					List *sortlist,
 					List *targetlist,
 					char *uniqueFlag)
 {
-	List	   *s = NIL;
-
-	while (orderlist != NIL)
-	{
-		SortGroupBy *sortby = lfirst(orderlist);
-		SortClause *sortcl = makeNode(SortClause);
-		TargetEntry *restarget;
-		Resdom	   *resdom;
-
-		restarget = findTargetlistEntry(pstate, sortby->node,
-										targetlist, ORDER_CLAUSE);
+	List	   *sortlist = NIL;
+	List	   *olitem;
 
-		sortcl->resdom = resdom = restarget->resdom;
+	/* Transform all the explicit ORDER BY clauses */
 
-		/*
-		 * if we have InvalidOid, then this is a NULL field and don't need
-		 * to sort
-		 */
-		if (resdom->restype == InvalidOid)
-			resdom->restype = INT4OID;
-
-		sortcl->opoid = oprid(oper(sortby->useOp,
-								   resdom->restype,
-								   resdom->restype, false));
-		if (sortlist == NIL)
-			s = sortlist = lcons(sortcl, NIL);
-		else
-		{
-			List	   *i;
+	foreach(olitem, orderlist)
+	{
+		SortGroupBy	   *sortby = lfirst(olitem);
+		TargetEntry	   *tle;
 
-			foreach(i, sortlist)
-			{
-				SortClause *scl = (SortClause *) lfirst(i);
+		tle = findTargetlistEntry(pstate, sortby->node,
+								  targetlist, ORDER_CLAUSE);
 
-				if (scl->resdom == sortcl->resdom)
-					break;
-			}
-			if (i == NIL)		/* not in sortlist already */
-			{
-				lnext(s) = lcons(sortcl, NIL);
-				s = lnext(s);
-			}
-			else
-				pfree(sortcl);	/* get rid of this */
-		}
-		orderlist = lnext(orderlist);
+		sortlist = addTargetToSortList(tle, sortlist, targetlist,
+									   sortby->useOp);
 	}
 
+	/* If we have a DISTINCT clause, add any necessary entries to
+	 * the sortlist to ensure that all the DISTINCT columns will be
+	 * sorted.  A subsequent UNIQUE pass will then do the right thing.
+	 */
+
 	if (uniqueFlag)
 	{
-		List	   *i;
-
 		if (uniqueFlag[0] == '*')
 		{
-
 			/*
 			 * concatenate all elements from target list that are not
 			 * already in the sortby list
 			 */
-			foreach(i, targetlist)
-			{
-				TargetEntry *tlelt = (TargetEntry *) lfirst(i);
-
-				s = sortlist;
-				while (s != NIL)
-				{
-					SortClause *sortcl = lfirst(s);
-
-					/*
-					 * We use equal() here because we are called for UNION
-					 * from the optimizer, and at that point, the sort
-					 * clause resdom pointers don't match the target list
-					 * resdom pointers
-					 */
-					if (equal(sortcl->resdom, tlelt->resdom))
-						break;
-					s = lnext(s);
-				}
-				if (s == NIL)
-				{
-					/* not a member of the sortclauses yet */
-					SortClause *sortcl = makeNode(SortClause);
-
-					if (tlelt->resdom->restype == InvalidOid)
-						tlelt->resdom->restype = INT4OID;
-
-					sortcl->resdom = tlelt->resdom;
-					sortcl->opoid = any_ordering_op(tlelt->resdom->restype);
-
-					sortlist = lappend(sortlist, sortcl);
-				}
-			}
+			sortlist = addAllTargetsToSortList(sortlist, targetlist);
 		}
 		else
 		{
-			TargetEntry *tlelt = NULL;
+			TargetEntry *tle = NULL;
 			char	   *uniqueAttrName = uniqueFlag;
+			List	   *i;
 
 			/* only create sort clause with the specified unique attribute */
 			foreach(i, targetlist)
 			{
-				tlelt = (TargetEntry *) lfirst(i);
-				if (strcmp(tlelt->resdom->resname, uniqueAttrName) == 0)
+				tle = (TargetEntry *) lfirst(i);
+				if (strcmp(tle->resdom->resname, uniqueAttrName) == 0)
 					break;
 			}
 			if (i == NIL)
 				elog(ERROR, "All fields in the UNIQUE ON clause must appear in the target list");
 
-			foreach(s, sortlist)
-			{
-				SortClause *sortcl = lfirst(s);
+			sortlist = addTargetToSortList(tle, sortlist, targetlist, NULL);
+		}
+	}
 
-				if (sortcl->resdom == tlelt->resdom)
-					break;
-			}
-			if (s == NIL)
-			{
-				/* not a member of the sortclauses yet */
-				SortClause *sortcl = makeNode(SortClause);
+	return sortlist;
+}
 
-				sortcl->resdom = tlelt->resdom;
-				sortcl->opoid = any_ordering_op(tlelt->resdom->restype);
+/*
+ * addAllTargetsToSortList
+ *		Make sure all targets in the targetlist are in the ORDER BY list,
+ *		adding the not-yet-sorted ones to the end of the list.
+ *		This is typically used to help implement SELECT DISTINCT.
+ *
+ * Returns the updated ORDER BY list.
+ */
+List *
+addAllTargetsToSortList(List *sortlist, List *targetlist)
+{
+	List	   *i;
 
-				sortlist = lappend(sortlist, sortcl);
-			}
-		}
+	foreach(i, targetlist)
+	{
+		TargetEntry *tle = (TargetEntry *) lfirst(i);
+
+		sortlist = addTargetToSortList(tle, sortlist, targetlist, NULL);
 	}
+	return sortlist;
+}
+
+/*
+ * addTargetToSortList
+ *		If the given targetlist entry isn't already in the ORDER BY list,
+ *		add it to the end of the list, using the sortop with given name
+ *		or any available sort operator if opname == NULL.
+ *
+ * Returns the updated ORDER BY list.
+ */
+static List *
+addTargetToSortList(TargetEntry *tle, List *sortlist, List *targetlist,
+					char *opname)
+{
+	/* avoid making duplicate sortlist entries */
+	if (! exprIsInSortList(tle->expr, sortlist, targetlist))
+	{
+		SortClause *sortcl = makeNode(SortClause);
+
+		sortcl->tleSortGroupRef = assignSortGroupRef(tle, targetlist);
+
+		if (opname)
+			sortcl->sortop = oprid(oper(opname,
+										tle->resdom->restype,
+										tle->resdom->restype, false));
+		else
+			sortcl->sortop = any_ordering_op(tle->resdom->restype);
 
+		sortlist = lappend(sortlist, sortcl);
+	}
 	return sortlist;
 }
 
+/*
+ * assignSortGroupRef
+ *	  Assign the targetentry an unused ressortgroupref, if it doesn't
+ *	  already have one.  Return the assigned or pre-existing refnumber.
+ *
+ * 'tlist' is the targetlist containing (or to contain) the given targetentry.
+ */
+Index
+assignSortGroupRef(TargetEntry *tle, List *tlist)
+{
+	Index		maxRef;
+	List	   *l;
+
+	if (tle->resdom->ressortgroupref)		/* already has one? */
+		return tle->resdom->ressortgroupref;
+
+	/* easiest way to pick an unused refnumber: max used + 1 */
+	maxRef = 0;
+	foreach(l, tlist)
+	{
+		Index	ref = ((TargetEntry *) lfirst(l))->resdom->ressortgroupref;
+
+		if (ref > maxRef)
+			maxRef = ref;
+	}
+	tle->resdom->ressortgroupref = maxRef + 1;
+	return tle->resdom->ressortgroupref;
+}
+
+/*
+ * exprIsInSortList
+ *		Is the given expression already in the sortlist?
+ *		Note we will say 'yes' if it is equal() to any sortlist item,
+ *		even though that might be a different targetlist member.
+ *
+ * Works for both SortClause and GroupClause lists.
+ */
+static bool
+exprIsInSortList(Node *expr, List *sortList, List *targetList)
+{
+	List	   *i;
+
+	foreach(i, sortList)
+	{
+		SortClause *scl = (SortClause *) lfirst(i);
+
+		if (equal(expr, get_sortgroupclause_expr(scl, targetList)))
+			return true;
+	}
+	return false;
+}
+
 /* transformUnionClause()
  * Transform a UNION clause.
  * Note that the union clause is actually a fully-formed select structure.
diff --git a/src/backend/parser/parse_func.c b/src/backend/parser/parse_func.c
index 344c87920bc..4a227de2c5b 100644
--- a/src/backend/parser/parse_func.c
+++ b/src/backend/parser/parse_func.c
@@ -7,7 +7,7 @@
  *
  *
  * IDENTIFICATION
- *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_func.c,v 1.52 1999/08/16 02:08:59 tgl Exp $
+ *	  $Header: /cvsroot/pgsql/src/backend/parser/parse_func.c,v 1.53 1999/08/21 03:48:55 tgl Exp $
  *
  *-------------------------------------------------------------------------
  */
@@ -63,7 +63,6 @@ static int match_argtypes(int nargs,
 			   CandidateList function_typeids,
 			   CandidateList *candidates);
 static List *setup_tlist(char *attname, Oid relid);
-static List *setup_base_tlist(Oid typeid);
 static Oid *func_select_candidate(int nargs, Oid *input_typeids,
 					  CandidateList candidates);
 static int	agg_get_candidates(char *aggname, Oid typeId, CandidateList *candidates);
@@ -1312,7 +1311,7 @@ setup_tlist(char *attname, Oid relid)
  **		Build a tlist that extracts a base type from the tuple
  **		returned by the executor.
  */
-static List *
+List *
 setup_base_tlist(Oid typeid)
 {
 	TargetEntry *tle;