Proposed patch for qual pushdown into UNION/INTERSECT

Seems to work in preliminary testing, but I'd like someone else to
give it a try before I decide it works. Patch is against CVS tip.

regards, tom lane

*** src/backend/optimizer/path/allpaths.c.orig Thu Jun 20 16:29:29 2002
--- src/backend/optimizer/path/allpaths.c Thu Aug 29 03:40:36 2002
***************
*** 46,51 ****
--- 46,56 ----
RangeTblEntry *rte);
static RelOptInfo *make_one_rel_by_joins(Query *root, int levels_needed,
List *initial_rels);
+ static bool subquery_is_pushdown_safe(Query *subquery, Query *topquery);
+ static bool recurse_pushdown_safe(Node *setOp, Query *topquery);
+ static void subquery_push_qual(Query *subquery, Index rti, Node *qual);
+ static void recurse_push_qual(Node *setOp, Query *topquery,
+ Index rti, Node *qual);


/*
***************
*** 297,327 ****
* generate a better plan for the subquery than evaluating all the
* subquery output rows and then filtering them.
*
! * There are several cases where we cannot push down clauses:
! *
! * 1. If the subquery contains set ops (UNION/INTERSECT/EXCEPT) we do not
! * push down any qual clauses, since the planner doesn't support quals
! * at the top level of a setop. (With suitable analysis we could try
! * to push the quals down into the component queries of the setop, but
! * getting it right seems nontrivial. Work on this later.)
! *
! * 2. If the subquery has a LIMIT clause or a DISTINCT ON clause, we must
! * not push down any quals, since that could change the set of rows
! * returned. (Actually, we could push down quals into a DISTINCT ON
! * subquery if they refer only to DISTINCT-ed output columns, but
! * checking that seems more work than it's worth. In any case, a
! * plain DISTINCT is safe to push down past.)
! *
! * 3. If the subquery has any functions returning sets in its target list,
! * we do not push down any quals, since the quals
! * might refer to those tlist items, which would mean we'd introduce
! * functions-returning-sets into the subquery's WHERE/HAVING quals.
! * (It'd be sufficient to not push down quals that refer to those
! * particular tlist items, but that's much clumsier to check.)
! *
! * 4. We do not push down clauses that contain subselects, mainly because
! * I'm not sure it will work correctly (the subplan hasn't yet
! * transformed sublinks to subselects).
*
* Non-pushed-down clauses will get evaluated as qpquals of the
* SubqueryScan node.
--- 302,312 ----
* generate a better plan for the subquery than evaluating all the
* subquery output rows and then filtering them.
*
! * There are several cases where we cannot push down clauses.
! * Restrictions involving the subquery are checked by
! * subquery_is_pushdown_safe(). Also, we do not push down clauses that
! * contain subselects, mainly because I'm not sure it will work correctly
! * (the subplan hasn't yet transformed sublinks to subselects).
*
* Non-pushed-down clauses will get evaluated as qpquals of the
* SubqueryScan node.
***************
*** 329,339 ****
* XXX Are there any cases where we want to make a policy decision not to
* push down, because it'd result in a worse plan?
*/
! if (subquery->setOperations == NULL &&
! subquery->limitOffset == NULL &&
! subquery->limitCount == NULL &&
! !has_distinct_on_clause(subquery) &&
! !expression_returns_set((Node *) subquery->targetList))
{
/* OK to consider pushing down individual quals */
List *upperrestrictlist = NIL;
--- 314,321 ----
* XXX Are there any cases where we want to make a policy decision not to
* push down, because it'd result in a worse plan?
*/
! if (rel->baserestrictinfo != NIL &&
! subquery_is_pushdown_safe(subquery, subquery))
{
/* OK to consider pushing down individual quals */
List *upperrestrictlist = NIL;
***************
*** 351,375 ****
}
else
{
! /*
! * We need to replace Vars in the clause (which must refer
! * to outputs of the subquery) with copies of the
! * subquery's targetlist expressions. Note that at this
! * point, any uplevel Vars in the clause should have been
! * replaced with Params, so they need no work.
! */
! clause = ResolveNew(clause, rti, 0,
! subquery->targetList,
! CMD_SELECT, 0);
! subquery->havingQual = make_and_qual(subquery->havingQual,
! clause);
!
! /*
! * We need not change the subquery's hasAggs or
! * hasSublinks flags, since we can't be pushing down any
! * aggregates that weren't there before, and we don't push
! * down subselects at all.
! */
}
}
rel->baserestrictinfo = upperrestrictlist;
--- 333,340 ----
}
else
{
! /* Push it down */
! subquery_push_qual(subquery, rti, clause);
}
}
rel->baserestrictinfo = upperrestrictlist;
***************
*** 547,553 ****
--- 512,694 ----
}

/*****************************************************************************
+ * PUSHING QUALS DOWN INTO SUBQUERIES
+ *****************************************************************************/
+
+ /*
+ * subquery_is_pushdown_safe - is a subquery safe for pushing down quals?
+ *
+ * subquery is the particular component query being checked. topquery
+ * is the top component of a set-operations tree (the same Query if no
+ * set-op is involved).
+ *
+ * Conditions checked here:
+ *
+ * 1. If the subquery has a LIMIT clause or a DISTINCT ON clause, we must
+ * not push down any quals, since that could change the set of rows
+ * returned. (Actually, we could push down quals into a DISTINCT ON
+ * subquery if they refer only to DISTINCT-ed output columns, but
+ * checking that seems more work than it's worth. In any case, a
+ * plain DISTINCT is safe to push down past.)
*
+ * 2. If the subquery has any functions returning sets in its target list,
+ * we do not push down any quals, since the quals
+ * might refer to those tlist items, which would mean we'd introduce
+ * functions-returning-sets into the subquery's WHERE/HAVING quals.
+ * (It'd be sufficient to not push down quals that refer to those
+ * particular tlist items, but that's much clumsier to check.)
+ *
+ * 3. If the subquery contains EXCEPT or EXCEPT ALL set ops we cannot push
+ * quals into it, because that would change the results. For subqueries
+ * using UNION/UNION ALL/INTERSECT/INTERSECT ALL, we can push the quals
+ * into each component query, so long as all the component queries share
+ * identical output types. (That restriction could probably be relaxed,
+ * but it would take much more code to include type coercion code into
+ * the quals, and I'm also concerned about possible semantic gotchas.)
+ */
+ static bool
+ subquery_is_pushdown_safe(Query *subquery, Query *topquery)
+ {
+ SetOperationStmt *topop;
+
+ /* Check points 1 and 2 */
+ if (subquery->limitOffset != NULL ||
+ subquery->limitCount != NULL ||
+ has_distinct_on_clause(subquery) ||
+ expression_returns_set((Node *) subquery->targetList))
+ return false;
+
+ /* Are we at top level, or looking at a setop component? */
+ if (subquery == topquery)
+ {
+ /* Top level, so check any component queries */
+ if (subquery->setOperations != NULL)
+ if (!recurse_pushdown_safe(subquery->setOperations, topquery))
+ return false;
+ }
+ else
+ {
+ /* Setop component must not have more components (too weird) */
+ if (subquery->setOperations != NULL)
+ return false;
+ /* Setop component output types must match top level */
+ topop = (SetOperationStmt *) topquery->setOperations;
+ Assert(topop && IsA(topop, SetOperationStmt));
+ if (!tlist_same_datatypes(subquery->targetList,
+ topop->colTypes,
+ true))
+ return false;
+
+ }
+ return true;
+ }
+
+ /*
+ * Helper routine to recurse through setOperations tree
+ */
+ static bool
+ recurse_pushdown_safe(Node *setOp, Query *topquery)
+ {
+ if (IsA(setOp, RangeTblRef))
+ {
+ RangeTblRef *rtr = (RangeTblRef *) setOp;
+ RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
+ Query *subquery = rte->subquery;
+
+ Assert(subquery != NULL);
+ return subquery_is_pushdown_safe(subquery, topquery);
+ }
+ else if (IsA(setOp, SetOperationStmt))
+ {
+ SetOperationStmt *op = (SetOperationStmt *) setOp;
+
+ /* EXCEPT is no good */
+ if (op->op == SETOP_EXCEPT)
+ return false;
+ /* Else recurse */
+ if (!recurse_pushdown_safe(op->larg, topquery))
+ return false;
+ if (!recurse_pushdown_safe(op->rarg, topquery))
+ return false;
+ }
+ else
+ {
+ elog(ERROR, "recurse_pushdown_safe: unexpected node %d",
+ (int) nodeTag(setOp));
+ }
+ return true;
+ }
+
+ /*
+ * subquery_push_qual - push down a qual that we have determined is safe
+ */
+ static void
+ subquery_push_qual(Query *subquery, Index rti, Node *qual)
+ {
+ if (subquery->setOperations != NULL)
+ {
+ /* Recurse to push it separately to each component query */
+ recurse_push_qual(subquery->setOperations, subquery, rti, qual);
+ }
+ else
+ {
+ /*
+ * We need to replace Vars in the qual (which must refer
+ * to outputs of the subquery) with copies of the
+ * subquery's targetlist expressions. Note that at this
+ * point, any uplevel Vars in the qual should have been
+ * replaced with Params, so they need no work.
+ *
+ * This step also ensures that when we are pushing into a setop
+ * tree, each component query gets its own copy of the qual.
+ */
+ qual = ResolveNew(qual, rti, 0,
+ subquery->targetList,
+ CMD_SELECT, 0);
+ subquery->havingQual = make_and_qual(subquery->havingQual,
+ qual);
+
+ /*
+ * We need not change the subquery's hasAggs or
+ * hasSublinks flags, since we can't be pushing down any
+ * aggregates that weren't there before, and we don't push
+ * down subselects at all.
+ */
+ }
+ }
+
+ /*
+ * Helper routine to recurse through setOperations tree
+ */
+ static void
+ recurse_push_qual(Node *setOp, Query *topquery,
+ Index rti, Node *qual)
+ {
+ if (IsA(setOp, RangeTblRef))
+ {
+ RangeTblRef *rtr = (RangeTblRef *) setOp;
+ RangeTblEntry *rte = rt_fetch(rtr->rtindex, topquery->rtable);
+ Query *subquery = rte->subquery;
+
+ Assert(subquery != NULL);
+ subquery_push_qual(subquery, rti, qual);
+ }
+ else if (IsA(setOp, SetOperationStmt))
+ {
+ SetOperationStmt *op = (SetOperationStmt *) setOp;
+
+ recurse_push_qual(op->larg, topquery, rti, qual);
+ recurse_push_qual(op->rarg, topquery, rti, qual);
+ }
+ else
+ {
+ elog(ERROR, "recurse_push_qual: unexpected node %d",
+ (int) nodeTag(setOp));
+ }
+ }
+
+ /*****************************************************************************
+ * DEBUG SUPPORT
*****************************************************************************/

#ifdef OPTIMIZER_DEBUG
*** src/backend/optimizer/prep/prepunion.c.orig Fri Aug 2 14:15:06 2002
--- src/backend/optimizer/prep/prepunion.c Thu Aug 29 03:16:12 2002
***************
*** 66,72 ****
static List *generate_append_tlist(List *colTypes, bool flag,
List *input_plans,
List *refnames_tlist);
- static bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK);
static Node *adjust_inherited_attrs_mutator(Node *node,
adjust_inherited_attrs_context *context);

--- 66,71 ----
***************
*** 579,585 ****
* Resjunk columns are ignored if junkOK is true; otherwise presence of
* a resjunk column will always cause a 'false' result.
*/
! static bool
tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
{
List *i;
--- 578,584 ----
* Resjunk columns are ignored if junkOK is true; otherwise presence of
* a resjunk column will always cause a 'false' result.
*/
! bool
tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK)
{
List *i;
*** src/include/optimizer/prep.h.orig Thu Jun 20 16:29:51 2002
--- src/include/optimizer/prep.h Thu Aug 29 03:16:03 2002
***************
*** 43,46 ****
--- 43,48 ----
Index old_rt_index, Oid old_relid,
Index new_rt_index, Oid new_relid);

+ extern bool tlist_same_datatypes(List *tlist, List *colTypes, bool junkOK);
+
#endif /* PREP_H */