Support parameterized TidPaths.

Up to now we've not worried much about joins where the join key is a
relation's CTID column, reasoning that storing a table's CTIDs in some
other table would be pretty useless.  However, there are use-cases for
this sort of query involving self-joins, so that argument doesn't really
hold water.

This patch allows generating plans for joins on CTID that use a nestloop
with inner TidScan, similar to what we might do with an index on the join
column.  This is the most efficient way to join when the outer side of
the nestloop is expected to yield relatively few rows.

This change requires upgrading tidpath.c and the generated TidPaths
to work with RestrictInfos instead of bare qual clauses, but that's
long-postponed technical debt anyway.

Discussion: https://postgr.es/m/17443.1545435266@sss.pgh.pa.us

1 files changed, 56 insertions, 11 deletions

diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 91cf78233d5..9e918793271 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -3083,18 +3083,72 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 	TidScan    *scan_plan;
 	Index		scan_relid = best_path->path.parent->relid;
 	List	   *tidquals = best_path->tidquals;
-	List	   *ortidquals;
 
 	/* it should be a base rel... */
 	Assert(scan_relid > 0);
 	Assert(best_path->path.parent->rtekind == RTE_RELATION);
 
+	/*
+	 * The qpqual list must contain all restrictions not enforced by the
+	 * tidquals list.  Since tidquals has OR semantics, we have to be careful
+	 * about matching it up to scan_clauses.  It's convenient to handle the
+	 * single-tidqual case separately from the multiple-tidqual case.  In the
+	 * single-tidqual case, we look through the scan_clauses while they are
+	 * still in RestrictInfo form, and drop any that are redundant with the
+	 * tidqual.
+	 *
+	 * In normal cases simple pointer equality checks will be enough to spot
+	 * duplicate RestrictInfos, so we try that first.
+	 *
+	 * Another common case is that a scan_clauses entry is generated from the
+	 * same EquivalenceClass as some tidqual, and is therefore redundant with
+	 * it, though not equal.
+	 *
+	 * Unlike indexpaths, we don't bother with predicate_implied_by(); the
+	 * number of cases where it could win are pretty small.
+	 */
+	if (list_length(tidquals) == 1)
+	{
+		List	   *qpqual = NIL;
+		ListCell   *l;
+
+		foreach(l, scan_clauses)
+		{
+			RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
+
+			if (rinfo->pseudoconstant)
+				continue;		/* we may drop pseudoconstants here */
+			if (list_member_ptr(tidquals, rinfo))
+				continue;		/* simple duplicate */
+			if (is_redundant_derived_clause(rinfo, tidquals))
+				continue;		/* derived from same EquivalenceClass */
+			qpqual = lappend(qpqual, rinfo);
+		}
+		scan_clauses = qpqual;
+	}
+
 	/* Sort clauses into best execution order */
 	scan_clauses = order_qual_clauses(root, scan_clauses);
 
-	/* Reduce RestrictInfo list to bare expressions; ignore pseudoconstants */
+	/* Reduce RestrictInfo lists to bare expressions; ignore pseudoconstants */
+	tidquals = extract_actual_clauses(tidquals, false);
 	scan_clauses = extract_actual_clauses(scan_clauses, false);
 
+	/*
+	 * If we have multiple tidquals, it's more convenient to remove duplicate
+	 * scan_clauses after stripping the RestrictInfos.  In this situation,
+	 * because the tidquals represent OR sub-clauses, they could not have come
+	 * from EquivalenceClasses so we don't have to worry about matching up
+	 * non-identical clauses.  On the other hand, because tidpath.c will have
+	 * extracted those sub-clauses from some OR clause and built its own list,
+	 * we will certainly not have pointer equality to any scan clause.  So
+	 * convert the tidquals list to an explicit OR clause and see if we can
+	 * match it via equal() to any scan clause.
+	 */
+	if (list_length(tidquals) > 1)
+		scan_clauses = list_difference(scan_clauses,
+									   list_make1(make_orclause(tidquals)));
+
 	/* Replace any outer-relation variables with nestloop params */
 	if (best_path->path.param_info)
 	{
@@ -3104,15 +3158,6 @@ create_tidscan_plan(PlannerInfo *root, TidPath *best_path,
 			replace_nestloop_params(root, (Node *) scan_clauses);
 	}
 
-	/*
-	 * Remove any clauses that are TID quals.  This is a bit tricky since the
-	 * tidquals list has implicit OR semantics.
-	 */
-	ortidquals = tidquals;
-	if (list_length(ortidquals) > 1)
-		ortidquals = list_make1(make_orclause(ortidquals));
-	scan_clauses = list_difference(scan_clauses, ortidquals);
-
 	scan_plan = make_tidscan(tlist,
 							 scan_clauses,
 							 scan_relid,