Обсуждение: Joins on TID

I decided to spend an afternoon seeing exactly how much work would be
needed to support parameterized TID scans, ie nestloop-with-inner-TID-
scan joins, as has been speculated about before, most recently here:

https://www.postgresql.org/message-id/flat/CAMqTPq%3DhNg0GYFU0X%2BxmuKy8R2ARk1%2BA_uQpS%2BMnf71MYpBKzg%40mail.gmail.com

It turns out it's not that bad, less than 200 net new lines of code
(all of it in the planner; the executor seems to require no work).

Much of the code churn is because tidpath.c is so ancient and crufty.
It was mostly ignoring the RestrictInfo infrastructure, in particular
emitting the list of tidquals as just bare clauses not RestrictInfos.
I had to change that in order to avoid inefficiencies in some places.

I haven't really looked at how much of a merge problem there'll be
with Edmund Horner's work for TID range scans.  My feeling about it
is that we might be best off treating that as a totally separate
code path, because the requirements are significantly different (for
instance, a range scan needs AND semantics not OR semantics for the
list of quals to apply).

            regards, tom lane

diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 480fd25..88780c0 100644
*** a/src/backend/optimizer/path/costsize.c
--- b/src/backend/optimizer/path/costsize.c
*************** cost_tidscan(Path *path, PlannerInfo *ro
*** 1202,1216 ****
      ntuples = 0;
      foreach(l, tidquals)
      {
!         if (IsA(lfirst(l), ScalarArrayOpExpr))
          {
              /* Each element of the array yields 1 tuple */
!             ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) lfirst(l);
              Node       *arraynode = (Node *) lsecond(saop->args);

              ntuples += estimate_array_length(arraynode);
          }
!         else if (IsA(lfirst(l), CurrentOfExpr))
          {
              /* CURRENT OF yields 1 tuple */
              isCurrentOf = true;
--- 1202,1219 ----
      ntuples = 0;
      foreach(l, tidquals)
      {
!         RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
!         Expr       *qual = rinfo->clause;
!
!         if (IsA(qual, ScalarArrayOpExpr))
          {
              /* Each element of the array yields 1 tuple */
!             ScalarArrayOpExpr *saop = (ScalarArrayOpExpr *) qual;
              Node       *arraynode = (Node *) lsecond(saop->args);

              ntuples += estimate_array_length(arraynode);
          }
!         else if (IsA(qual, CurrentOfExpr))
          {
              /* CURRENT OF yields 1 tuple */
              isCurrentOf = true;
diff --git a/src/backend/optimizer/path/tidpath.c b/src/backend/optimizer/path/tidpath.c
index 3bb5b8d..335de0a 100644
*** a/src/backend/optimizer/path/tidpath.c
--- b/src/backend/optimizer/path/tidpath.c
***************
*** 12,29 ****
   * this allows
   *        WHERE ctid IN (tid1, tid2, ...)
   *
   * We also support "WHERE CURRENT OF cursor" conditions (CurrentOfExpr),
   * which amount to "CTID = run-time-determined-TID".  These could in
   * theory be translated to a simple comparison of CTID to the result of
   * a function, but in practice it works better to keep the special node
   * representation all the way through to execution.
   *
-  * There is currently no special support for joins involving CTID; in
-  * particular nothing corresponding to best_inner_indexscan().  Since it's
-  * not very useful to store TIDs of one table in another table, there
-  * doesn't seem to be enough use-case to justify adding a lot of code
-  * for that.
-  *
   *
   * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
--- 12,28 ----
   * this allows
   *        WHERE ctid IN (tid1, tid2, ...)
   *
+  * As with indexscans, our definition of "pseudoconstant" is pretty liberal:
+  * we allow anything that doesn't involve a volatile function or a Var of
+  * the relation under consideration.  Vars belonging to other relations of
+  * the query are allowed, giving rise to parameterized TID scans.
+  *
   * We also support "WHERE CURRENT OF cursor" conditions (CurrentOfExpr),
   * which amount to "CTID = run-time-determined-TID".  These could in
   * theory be translated to a simple comparison of CTID to the result of
   * a function, but in practice it works better to keep the special node
   * representation all the way through to execution.
   *
   *
   * Portions Copyright (c) 1996-2018, PostgreSQL Global Development Group
   * Portions Copyright (c) 1994, Regents of the University of California
***************
*** 44,125 ****
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
  #include "optimizer/restrictinfo.h"


! static bool IsTidEqualClause(OpExpr *node, int varno);
! static bool IsTidEqualAnyClause(ScalarArrayOpExpr *node, int varno);
! static List *TidQualFromExpr(Node *expr, int varno);
! static List *TidQualFromBaseRestrictinfo(RelOptInfo *rel);
!

  /*
!  * Check to see if an opclause is of the form
   *        CTID = pseudoconstant
   * or
   *        pseudoconstant = CTID
!  *
!  * We check that the CTID Var belongs to relation "varno".  That is probably
!  * redundant considering this is only applied to restriction clauses, but
!  * let's be safe.
   */
  static bool
! IsTidEqualClause(OpExpr *node, int varno)
  {
      Node       *arg1,
                 *arg2,
                 *other;
!     Var           *var;

      /* Operator must be tideq */
      if (node->opno != TIDEqualOperator)
          return false;
!     if (list_length(node->args) != 2)
!         return false;
      arg1 = linitial(node->args);
      arg2 = lsecond(node->args);

      /* Look for CTID as either argument */
      other = NULL;
!     if (arg1 && IsA(arg1, Var))
      {
!         var = (Var *) arg1;
!         if (var->varattno == SelfItemPointerAttributeNumber &&
!             var->vartype == TIDOID &&
!             var->varno == varno &&
!             var->varlevelsup == 0)
!             other = arg2;
      }
!     if (!other && arg2 && IsA(arg2, Var))
      {
!         var = (Var *) arg2;
!         if (var->varattno == SelfItemPointerAttributeNumber &&
!             var->vartype == TIDOID &&
!             var->varno == varno &&
!             var->varlevelsup == 0)
!             other = arg1;
      }
      if (!other)
          return false;
-     if (exprType(other) != TIDOID)
-         return false;            /* probably can't happen */

      /* The other argument must be a pseudoconstant */
!     if (!is_pseudo_constant_clause(other))
          return false;

      return true;                /* success */
  }

  /*
!  * Check to see if a clause is of the form
   *        CTID = ANY (pseudoconstant_array)
   */
  static bool
! IsTidEqualAnyClause(ScalarArrayOpExpr *node, int varno)
  {
      Node       *arg1,
                 *arg2;

      /* Operator must be tideq */
      if (node->opno != TIDEqualOperator)
          return false;
--- 43,139 ----
  #include "optimizer/pathnode.h"
  #include "optimizer/paths.h"
  #include "optimizer/restrictinfo.h"
+ #include "optimizer/var.h"


! /*
!  * Does this Var represent the CTID column of the specified baserel?
!  */
! static inline bool
! IsCTIDVar(Var *var, RelOptInfo *rel)
! {
!     /* The vartype check is strictly paranoia */
!     if (var->varattno == SelfItemPointerAttributeNumber &&
!         var->vartype == TIDOID &&
!         var->varno == rel->relid &&
!         var->varlevelsup == 0)
!         return true;
!     return false;
! }

  /*
!  * Check to see if a RestrictInfo is of the form
   *        CTID = pseudoconstant
   * or
   *        pseudoconstant = CTID
!  * where the CTID Var belongs to relation "rel", and nothing on the
!  * other side of the clause does.
   */
  static bool
! IsTidEqualClause(RestrictInfo *rinfo, RelOptInfo *rel)
  {
+     OpExpr       *node;
      Node       *arg1,
                 *arg2,
                 *other;
!     Relids        other_relids;
!
!     /* Must be an OpExpr */
!     if (!is_opclause(rinfo->clause))
!         return false;
!     node = (OpExpr *) rinfo->clause;

      /* Operator must be tideq */
      if (node->opno != TIDEqualOperator)
          return false;
!     Assert(list_length(node->args) == 2);
      arg1 = linitial(node->args);
      arg2 = lsecond(node->args);

      /* Look for CTID as either argument */
      other = NULL;
!     other_relids = NULL;
!     if (arg1 && IsA(arg1, Var) &&
!         IsCTIDVar((Var *) arg1, rel))
      {
!         other = arg2;
!         other_relids = rinfo->right_relids;
      }
!     if (!other && arg2 && IsA(arg2, Var) &&
!         IsCTIDVar((Var *) arg2, rel))
      {
!         other = arg1;
!         other_relids = rinfo->left_relids;
      }
      if (!other)
          return false;

      /* The other argument must be a pseudoconstant */
!     if (bms_is_member(rel->relid, other_relids) ||
!         contain_volatile_functions(other))
          return false;

      return true;                /* success */
  }

  /*
!  * Check to see if a RestrictInfo is of the form
   *        CTID = ANY (pseudoconstant_array)
+  * where the CTID Var belongs to relation "rel", and nothing on the
+  * other side of the clause does.
   */
  static bool
! IsTidEqualAnyClause(RestrictInfo *rinfo, RelOptInfo *rel)
  {
+     ScalarArrayOpExpr *node;
      Node       *arg1,
                 *arg2;

+     /* Must be a ScalarArrayOpExpr */
+     if (!(rinfo->clause && IsA(rinfo->clause, ScalarArrayOpExpr)))
+         return false;
+     node = (ScalarArrayOpExpr *) rinfo->clause;
+
      /* Operator must be tideq */
      if (node->opno != TIDEqualOperator)
          return false;
*************** IsTidEqualAnyClause(ScalarArrayOpExpr *n
*** 130,246 ****
      arg2 = lsecond(node->args);

      /* CTID must be first argument */
!     if (arg1 && IsA(arg1, Var))
      {
!         Var           *var = (Var *) arg1;

!         if (var->varattno == SelfItemPointerAttributeNumber &&
!             var->vartype == TIDOID &&
!             var->varno == varno &&
!             var->varlevelsup == 0)
!         {
!             /* The other argument must be a pseudoconstant */
!             if (is_pseudo_constant_clause(arg2))
!                 return true;    /* success */
!         }
      }

      return false;
  }

  /*
!  *    Extract a set of CTID conditions from the given qual expression
   *
!  *    Returns a List of CTID qual expressions (with implicit OR semantics
!  *    across the list), or NIL if there are no usable conditions.
   *
!  *    If the expression is an AND clause, we can use a CTID condition
!  *    from any sub-clause.  If it is an OR clause, we must be able to
!  *    extract a CTID condition from every sub-clause, or we can't use it.
   *
!  *    In theory, in the AND case we could get CTID conditions from different
!  *    sub-clauses, in which case we could try to pick the most efficient one.
!  *    In practice, such usage seems very unlikely, so we don't bother; we
!  *    just exit as soon as we find the first candidate.
   */
  static List *
! TidQualFromExpr(Node *expr, int varno)
  {
      List       *rlst = NIL;
      ListCell   *l;

!     if (is_opclause(expr))
!     {
!         /* base case: check for tideq opclause */
!         if (IsTidEqualClause((OpExpr *) expr, varno))
!             rlst = list_make1(expr);
!     }
!     else if (expr && IsA(expr, ScalarArrayOpExpr))
!     {
!         /* another base case: check for tid = ANY clause */
!         if (IsTidEqualAnyClause((ScalarArrayOpExpr *) expr, varno))
!             rlst = list_make1(expr);
!     }
!     else if (expr && IsA(expr, CurrentOfExpr))
!     {
!         /* another base case: check for CURRENT OF on this rel */
!         if (((CurrentOfExpr *) expr)->cvarno == varno)
!             rlst = list_make1(expr);
!     }
!     else if (and_clause(expr))
!     {
!         foreach(l, ((BoolExpr *) expr)->args)
!         {
!             rlst = TidQualFromExpr((Node *) lfirst(l), varno);
!             if (rlst)
!                 break;
!         }
!     }
!     else if (or_clause(expr))
      {
!         foreach(l, ((BoolExpr *) expr)->args)
          {
!             List       *frtn = TidQualFromExpr((Node *) lfirst(l), varno);

!             if (frtn)
!                 rlst = list_concat(rlst, frtn);
!             else
              {
!                 if (rlst)
!                     list_free(rlst);
!                 rlst = NIL;
!                 break;
              }
          }
      }
      return rlst;
  }

  /*
!  *    Extract a set of CTID conditions from the rel's baserestrictinfo list
   */
! static List *
! TidQualFromBaseRestrictinfo(RelOptInfo *rel)
  {
-     List       *rlst = NIL;
      ListCell   *l;

!     foreach(l, rel->baserestrictinfo)
      {
!         RestrictInfo *rinfo = (RestrictInfo *) lfirst(l);

          /*
!          * If clause must wait till after some lower-security-level
!          * restriction clause, reject it.
           */
!         if (!restriction_is_securely_promotable(rinfo, rel))
              continue;

!         rlst = TidQualFromExpr((Node *) rinfo->clause, rel->relid);
!         if (rlst)
!             break;
      }
!     return rlst;
  }

  /*
--- 144,373 ----
      arg2 = lsecond(node->args);

      /* CTID must be first argument */
!     if (arg1 && IsA(arg1, Var) &&
!         IsCTIDVar((Var *) arg1, rel))
      {
!         /* The other argument must be a pseudoconstant */
!         if (bms_is_member(rel->relid, pull_varnos(arg2)) ||
!             contain_volatile_functions(arg2))
!             return false;

!         return true;            /* success */
      }

      return false;
  }

  /*
!  * Check to see if a RestrictInfo is a CurrentOfExpr referencing "rel".
!  */
! static bool
! IsCurrentOfClause(RestrictInfo *rinfo, RelOptInfo *rel)
! {
!     CurrentOfExpr *node;
!
!     /* Must be a CurrentOfExpr */
!     if (!(rinfo->clause && IsA(rinfo->clause, CurrentOfExpr)))
!         return false;
!     node = (CurrentOfExpr *) rinfo->clause;
!
!     /* If it references this rel, we're good */
!     if (node->cvarno == rel->relid)
!         return true;
!
!     return false;
! }
!
! /*
!  * Extract a set of CTID conditions from the given RestrictInfo
   *
!  * Returns a List of CTID qual RestrictInfos for the specified rel (with
!  * implicit OR semantics across the list), or NIL if there are no usable
!  * conditions.
   *
!  * This function considers only base cases; AND/OR combination is handled
!  * below.  Therefore the returned List never has more than one element.
!  * (Using a List may seem a bit weird, but it simplifies the caller.)
!  */
! static List *
! TidQualFromRestrictInfo(RestrictInfo *rinfo, RelOptInfo *rel)
! {
!     /*
!      * We may ignore pseudoconstant clauses (they can't contain Vars, so could
!      * not match anyway).
!      */
!     if (rinfo->pseudoconstant)
!         return NIL;
!
!     /*
!      * If clause must wait till after some lower-security-level restriction
!      * clause, reject it.
!      */
!     if (!restriction_is_securely_promotable(rinfo, rel))
!         return NIL;
!
!     /*
!      * Check all base cases.  If we get a match, return the clause.
!      */
!     if (IsTidEqualClause(rinfo, rel) ||
!         IsTidEqualAnyClause(rinfo, rel) ||
!         IsCurrentOfClause(rinfo, rel))
!         return list_make1(rinfo);
!
!     return NIL;
! }
!
! /*
!  * Extract a set of CTID conditions from implicit-AND List of RestrictInfos
   *
!  * Returns a List of CTID qual RestrictInfos for the specified rel (with
!  * implicit OR semantics across the list), or NIL if there are no usable
!  * conditions.
!  *
!  * This function is just concerned with handling AND/OR recursion.
   */
  static List *
! TidQualFromRestrictInfoList(List *rlist, RelOptInfo *rel)
  {
      List       *rlst = NIL;
      ListCell   *l;

!     foreach(l, rlist)
      {
!         RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
!
!         if (restriction_is_or_clause(rinfo))
          {
!             ListCell   *j;

!             /*
!              * We must be able to extract a CTID condition from every
!              * sub-clause of an OR, or we can't use it.
!              */
!             foreach(j, ((BoolExpr *) rinfo->orclause)->args)
              {
!                 Node       *orarg = (Node *) lfirst(j);
!                 List       *sublist;
!
!                 /* OR arguments should be ANDs or sub-RestrictInfos */
!                 if (and_clause(orarg))
!                 {
!                     List       *andargs = ((BoolExpr *) orarg)->args;
!
!                     /* Recurse in case there are sub-ORs */
!                     sublist = TidQualFromRestrictInfoList(andargs, rel);
!                 }
!                 else
!                 {
!                     RestrictInfo *rinfo = castNode(RestrictInfo, orarg);
!
!                     Assert(!restriction_is_or_clause(rinfo));
!                     sublist = TidQualFromRestrictInfo(rinfo, rel);
!                 }
!
!                 /*
!                  * If nothing found in this arm, we can't do anything with
!                  * this OR clause.
!                  */
!                 if (sublist == NIL)
!                 {
!                     rlst = NIL; /* forget anything we had */
!                     break;        /* out of loop over OR args */
!                 }
!
!                 /*
!                  * OK, continue constructing implicitly-OR'ed result list.
!                  */
!                 rlst = list_concat(rlst, sublist);
              }
          }
+         else
+         {
+             /* Not an OR clause, so handle base cases */
+             rlst = TidQualFromRestrictInfo(rinfo, rel);
+         }
+
+         /*
+          * Stop as soon as we find any usable CTID condition.  In theory we
+          * could get CTID equality conditions from different AND'ed clauses,
+          * in which case we could try to pick the most efficient one.  In
+          * practice, such usage seems very unlikely, so we don't bother; we
+          * just exit as soon as we find the first candidate.
+          */
+         if (rlst)
+             break;
      }
+
      return rlst;
  }

  /*
!  * Given a list of join clauses involving our rel, create a parameterized
!  * TidPath for each one that is a suitable TidEqual clause.
!  *
!  * In principle we could combine clauses that reference the same outer rels,
!  * but it doesn't seem like such cases would arise often enough to be worth
!  * troubling over.
   */
! static void
! BuildParameterizedTidPaths(PlannerInfo *root, RelOptInfo *rel, List *clauses)
  {
      ListCell   *l;

!     foreach(l, clauses)
      {
!         RestrictInfo *rinfo = lfirst_node(RestrictInfo, l);
!         List       *tidquals;
!         Relids        required_outer;

          /*
!          * Validate whether each clause is actually usable; we must check this
!          * even when examining clauses generated from an EquivalenceClass,
!          * since they might not satisfy the restriction on not having Vars of
!          * our rel on the other side, or somebody might've built an operator
!          * class that accepts type "tid" but has other operators in it.
!          *
!          * We currently consider only TidEqual join clauses.  In principle we
!          * might find a suitable ScalarArrayOpExpr in the rel's joininfo list,
!          * but it seems unlikely to be worth checking for.
           */
!         if (!IsTidEqualClause(rinfo, rel))
              continue;

!         /*
!          * Check if clause can be moved to this rel; this is probably
!          * redundant when considering EC-derived clauses, but we must check it
!          * for "loose" join clauses.
!          */
!         if (!join_clause_is_movable_to(rinfo, rel))
!             continue;
!
!         /* OK, make list of clauses for this path */
!         tidquals = list_make1(rinfo);
!
!         /* Compute required outer rels for this path */
!         required_outer = bms_union(rinfo->required_relids, rel->lateral_relids);
!         required_outer = bms_del_member(required_outer, rel->relid);
!
!         add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
!                                                    required_outer));
      }
! }
!
! /*
!  * Test whether an EquivalenceClass member matches our rel's CTID Var.
!  *
!  * This is a callback for use by generate_implied_equalities_for_column.
!  */
! static bool
! ec_member_matches_ctid(PlannerInfo *root, RelOptInfo *rel,
!                        EquivalenceClass *ec, EquivalenceMember *em,
!                        void *arg)
! {
!     if (em->em_expr && IsA(em->em_expr, Var) &&
!         IsCTIDVar((Var *) em->em_expr, rel))
!         return true;
!     return false;
  }

  /*
*************** TidQualFromBaseRestrictinfo(RelOptInfo *
*** 252,270 ****
  void
  create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
  {
-     Relids        required_outer;
      List       *tidquals;

      /*
!      * We don't support pushing join clauses into the quals of a tidscan, but
!      * it could still have required parameterization due to LATERAL refs in
!      * its tlist.
       */
!     required_outer = rel->lateral_relids;
!
!     tidquals = TidQualFromBaseRestrictinfo(rel);

      if (tidquals)
          add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
                                                     required_outer));
  }
--- 379,428 ----
  void
  create_tidscan_paths(PlannerInfo *root, RelOptInfo *rel)
  {
      List       *tidquals;

      /*
!      * If any suitable quals exist in the rel's baserestrict list, generate a
!      * plain (unparameterized) TidPath with them.
       */
!     tidquals = TidQualFromRestrictInfoList(rel->baserestrictinfo, rel);

      if (tidquals)
+     {
+         /*
+          * This path uses no join clauses, but it could still have required
+          * parameterization due to LATERAL refs in its tlist.
+          */
+         Relids        required_outer = rel->lateral_relids;
+
          add_path(rel, (Path *) create_tidscan_path(root, rel, tidquals,
                                                     required_outer));
+     }
+
+     /*
+      * Try to generate parameterized TidPaths using equality clauses extracted
+      * from EquivalenceClasses.  (This is important since simple "t1.ctid =
+      * t2.ctid" clauses will turn into ECs.)
+      */
+     if (rel->has_eclass_joins)
+     {
+         List       *clauses;
+
+         /* Generate clauses, skipping any that join to lateral_referencers */
+         clauses = generate_implied_equalities_for_column(root,
+                                                          rel,
+                                                          ec_member_matches_ctid,
+                                                          NULL,
+                                                          rel->lateral_referencers);
+
+         /* Generate a path for each usable join clause */
+         BuildParameterizedTidPaths(root, rel, clauses);
+     }
+
+     /*
+      * Also consider parameterized TidPaths using "loose" join quals.  Quals
+      * of the form "t1.ctid = t2.ctid" would turn into these if they are outer
+      * join quals, for example.
+      */
+     BuildParameterizedTidPaths(root, rel, rel->joininfo);
  }
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 91cf782..af9de0f 100644
*** a/src/backend/optimizer/plan/createplan.c
--- b/src/backend/optimizer/plan/createplan.c
*************** create_tidscan_plan(PlannerInfo *root, T
*** 3083,3098 ****
      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);

      /* 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);

      /* Replace any outer-relation variables with nestloop params */
--- 3083,3135 ----
      TidScan    *scan_plan;
      Index        scan_relid = best_path->path.parent->relid;
      List       *tidquals = best_path->tidquals;

      /* 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, if there's more than
+      * one then it can't be said to be enforcing any one of them, and so we
+      * don't drop any scan clauses in that case.  (We could potentially try to
+      * match to restriction OR clauses, but it's not worth the trouble.)
+      *
+      * 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 lists to bare expressions; ignore pseudoconstants */
!     tidquals = extract_actual_clauses(tidquals, false);
      scan_clauses = extract_actual_clauses(scan_clauses, false);

      /* Replace any outer-relation variables with nestloop params */
*************** create_tidscan_plan(PlannerInfo *root, T
*** 3104,3118 ****
              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,
--- 3141,3146 ----
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index d50d86b..81cc9cb 100644
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** do { \
*** 3715,3726 ****
              {
                  TidPath    *tpath;

-                 /*
-                  * TidPath contains tidquals, which do not contain any
-                  * external parameters per create_tidscan_path(). So don't
-                  * bother to translate those.
-                  */
                  FLAT_COPY_PATH(tpath, path, TidPath);
                  new_path = (Path *) tpath;
              }
              break;
--- 3715,3722 ----
              {
                  TidPath    *tpath;

                  FLAT_COPY_PATH(tpath, path, TidPath);
+                 ADJUST_CHILD_ATTRS(tpath->tidquals);
                  new_path = (Path *) tpath;
              }
              break;
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index f116bc2..b7d33fc 100644
*** a/src/include/nodes/plannodes.h
--- b/src/include/nodes/plannodes.h
*************** typedef struct BitmapHeapScan
*** 478,484 ****
   *        tid scan node
   *
   * tidquals is an implicitly OR'ed list of qual expressions of the form
!  * "CTID = pseudoconstant" or "CTID = ANY(pseudoconstant_array)".
   * ----------------
   */
  typedef struct TidScan
--- 478,485 ----
   *        tid scan node
   *
   * tidquals is an implicitly OR'ed list of qual expressions of the form
!  * "CTID = pseudoconstant", or "CTID = ANY(pseudoconstant_array)",
!  * or a CurrentOfExpr for the relation.
   * ----------------
   */
  typedef struct TidScan
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 6fd2420..db3fb21 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct BitmapOrPath
*** 1229,1236 ****
   * TidPath represents a scan by TID
   *
   * tidquals is an implicitly OR'ed list of qual expressions of the form
!  * "CTID = pseudoconstant" or "CTID = ANY(pseudoconstant_array)".
!  * Note they are bare expressions, not RestrictInfos.
   */
  typedef struct TidPath
  {
--- 1229,1236 ----
   * TidPath represents a scan by TID
   *
   * tidquals is an implicitly OR'ed list of qual expressions of the form
!  * "CTID = pseudoconstant", or "CTID = ANY(pseudoconstant_array)",
!  * or a CurrentOfExpr for the relation.
   */
  typedef struct TidPath
  {
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index 521ed1b..e1d1293 100644
*** a/src/test/regress/expected/tidscan.out
--- b/src/test/regress/expected/tidscan.out
*************** WHERE (id = 3 AND ctid IN ('(0,2)', '(0,
*** 92,97 ****
--- 92,136 ----
   (0,3) |  3
  (2 rows)

+ -- joins on tid
+ EXPLAIN (COSTS OFF)
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+              QUERY PLAN
+ ------------------------------------
+  Nested Loop
+    ->  Seq Scan on tidscan t1
+          Filter: (id = 1)
+    ->  Tid Scan on tidscan t2
+          TID Cond: (ctid = t1.ctid)
+ (5 rows)
+
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+  ctid  | id | ctid  | id
+ -------+----+-------+----
+  (0,1) |  1 | (0,1) |  1
+ (1 row)
+
+ EXPLAIN (COSTS OFF)
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 LEFT JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+              QUERY PLAN
+ ------------------------------------
+  Nested Loop Left Join
+    ->  Seq Scan on tidscan t1
+          Filter: (id = 1)
+    ->  Tid Scan on tidscan t2
+          TID Cond: (t1.ctid = ctid)
+ (5 rows)
+
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 LEFT JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+  ctid  | id | ctid  | id
+ -------+----+-------+----
+  (0,1) |  1 | (0,1) |  1
+ (1 row)
+
  -- exercise backward scan and rewind
  BEGIN;
  DECLARE c CURSOR FOR
diff --git a/src/test/regress/sql/tidscan.sql b/src/test/regress/sql/tidscan.sql
index a8472e0..cc2cec3 100644
*** a/src/test/regress/sql/tidscan.sql
--- b/src/test/regress/sql/tidscan.sql
*************** WHERE (id = 3 AND ctid IN ('(0,2)', '(0,
*** 34,39 ****
--- 34,51 ----
  SELECT ctid, * FROM tidscan
  WHERE (id = 3 AND ctid IN ('(0,2)', '(0,3)')) OR (ctid = '(0,1)' AND id = 1);

+ -- joins on tid
+ EXPLAIN (COSTS OFF)
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+ EXPLAIN (COSTS OFF)
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 LEFT JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+ SELECT t1.ctid, t1.*, t2.ctid, t2.*
+ FROM tidscan t1 LEFT JOIN tidscan t2 ON t1.ctid = t2.ctid WHERE t1.id = 1;
+
  -- exercise backward scan and rewind
  BEGIN;
  DECLARE c CURSOR FOR

BTW, if we're to start taking joins on TID seriously, we should also
add the missing hash opclass for TID, so that you can do hash joins
when dealing with a lot of rows.

(In principle this also enables things like hash aggregation, though
I'm not very clear on a use-case for grouping by TID.)

            regards, tom lane

diff --git a/src/backend/utils/adt/tid.c b/src/backend/utils/adt/tid.c
index 41d540b..7b25947 100644
*** a/src/backend/utils/adt/tid.c
--- b/src/backend/utils/adt/tid.c
***************
*** 20,25 ****
--- 20,26 ----
  #include <math.h>
  #include <limits.h>

+ #include "access/hash.h"
  #include "access/heapam.h"
  #include "access/sysattr.h"
  #include "catalog/namespace.h"
*************** tidsmaller(PG_FUNCTION_ARGS)
*** 239,244 ****
--- 240,272 ----
      PG_RETURN_ITEMPOINTER(ItemPointerCompare(arg1, arg2) <= 0 ? arg1 : arg2);
  }

+ Datum
+ hashtid(PG_FUNCTION_ARGS)
+ {
+     ItemPointer key = PG_GETARG_ITEMPOINTER(0);
+
+     /*
+      * While you'll probably have a lot of trouble with a compiler that
+      * insists on appending pad space to struct ItemPointerData, we can at
+      * least make this code work, by not using sizeof(ItemPointerData).
+      * Instead rely on knowing the sizes of the component fields.
+      */
+     return hash_any((unsigned char *) key,
+                     sizeof(BlockIdData) + sizeof(OffsetNumber));
+ }
+
+ Datum
+ hashtidextended(PG_FUNCTION_ARGS)
+ {
+     ItemPointer key = PG_GETARG_ITEMPOINTER(0);
+     uint64        seed = PG_GETARG_INT64(1);
+
+     /* As above */
+     return hash_any_extended((unsigned char *) key,
+                              sizeof(BlockIdData) + sizeof(OffsetNumber),
+                              seed);
+ }
+

  /*
   *    Functions to get latest tid of a specified tuple.
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index e689c9b..436f1bd 100644
*** a/src/include/catalog/pg_amop.dat
--- b/src/include/catalog/pg_amop.dat
***************
*** 1013,1018 ****
--- 1013,1022 ----
  { amopfamily => 'hash/cid_ops', amoplefttype => 'cid', amoprighttype => 'cid',
    amopstrategy => '1', amopopr => '=(cid,cid)', amopmethod => 'hash' },

+ # tid_ops
+ { amopfamily => 'hash/tid_ops', amoplefttype => 'tid', amoprighttype => 'tid',
+   amopstrategy => '1', amopopr => '=(tid,tid)', amopmethod => 'hash' },
+
  # text_pattern_ops
  { amopfamily => 'hash/text_pattern_ops', amoplefttype => 'text',
    amoprighttype => 'text', amopstrategy => '1', amopopr => '=(text,text)',
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index bbcee26..8ddb699 100644
*** a/src/include/catalog/pg_amproc.dat
--- b/src/include/catalog/pg_amproc.dat
***************
*** 340,345 ****
--- 340,349 ----
    amprocrighttype => 'cid', amprocnum => '1', amproc => 'hashint4' },
  { amprocfamily => 'hash/cid_ops', amproclefttype => 'cid',
    amprocrighttype => 'cid', amprocnum => '2', amproc => 'hashint4extended' },
+ { amprocfamily => 'hash/tid_ops', amproclefttype => 'tid',
+   amprocrighttype => 'tid', amprocnum => '1', amproc => 'hashtid' },
+ { amprocfamily => 'hash/tid_ops', amproclefttype => 'tid',
+   amprocrighttype => 'tid', amprocnum => '2', amproc => 'hashtidextended' },
  { amprocfamily => 'hash/text_pattern_ops', amproclefttype => 'text',
    amprocrighttype => 'text', amprocnum => '1', amproc => 'hashtext' },
  { amprocfamily => 'hash/text_pattern_ops', amproclefttype => 'text',
diff --git a/src/include/catalog/pg_opclass.dat b/src/include/catalog/pg_opclass.dat
index 5178d04..c451d36 100644
*** a/src/include/catalog/pg_opclass.dat
--- b/src/include/catalog/pg_opclass.dat
***************
*** 167,172 ****
--- 167,174 ----
    opcintype => 'xid' },
  { opcmethod => 'hash', opcname => 'cid_ops', opcfamily => 'hash/cid_ops',
    opcintype => 'cid' },
+ { opcmethod => 'hash', opcname => 'tid_ops', opcfamily => 'hash/tid_ops',
+   opcintype => 'tid' },
  { opcmethod => 'hash', opcname => 'text_pattern_ops',
    opcfamily => 'hash/text_pattern_ops', opcintype => 'text',
    opcdefault => 'f' },
diff --git a/src/include/catalog/pg_operator.dat b/src/include/catalog/pg_operator.dat
index 2abd531..e8452e1 100644
*** a/src/include/catalog/pg_operator.dat
--- b/src/include/catalog/pg_operator.dat
***************
*** 204,212 ****
    oprrest => 'eqsel', oprjoin => 'eqjoinsel' },

  { oid => '387', oid_symbol => 'TIDEqualOperator', descr => 'equal',
!   oprname => '=', oprcanmerge => 't', oprleft => 'tid', oprright => 'tid',
!   oprresult => 'bool', oprcom => '=(tid,tid)', oprnegate => '<>(tid,tid)',
!   oprcode => 'tideq', oprrest => 'eqsel', oprjoin => 'eqjoinsel' },
  { oid => '402', descr => 'not equal',
    oprname => '<>', oprleft => 'tid', oprright => 'tid', oprresult => 'bool',
    oprcom => '<>(tid,tid)', oprnegate => '=(tid,tid)', oprcode => 'tidne',
--- 204,213 ----
    oprrest => 'eqsel', oprjoin => 'eqjoinsel' },

  { oid => '387', oid_symbol => 'TIDEqualOperator', descr => 'equal',
!   oprname => '=', oprcanmerge => 't', oprcanhash => 't', oprleft => 'tid',
!   oprright => 'tid', oprresult => 'bool', oprcom => '=(tid,tid)',
!   oprnegate => '<>(tid,tid)', oprcode => 'tideq', oprrest => 'eqsel',
!   oprjoin => 'eqjoinsel' },
  { oid => '402', descr => 'not equal',
    oprname => '<>', oprleft => 'tid', oprright => 'tid', oprresult => 'bool',
    oprcom => '<>(tid,tid)', oprnegate => '=(tid,tid)', oprcode => 'tidne',
diff --git a/src/include/catalog/pg_opfamily.dat b/src/include/catalog/pg_opfamily.dat
index fe8a324..c5ea37b 100644
*** a/src/include/catalog/pg_opfamily.dat
--- b/src/include/catalog/pg_opfamily.dat
***************
*** 112,117 ****
--- 112,119 ----
    opfmethod => 'hash', opfname => 'xid_ops' },
  { oid => '2226',
    opfmethod => 'hash', opfname => 'cid_ops' },
+ { oid => '2227',
+   opfmethod => 'hash', opfname => 'tid_ops' },
  { oid => '2229',
    opfmethod => 'hash', opfname => 'text_pattern_ops' },
  { oid => '2231',
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index acb0154..6e1e1df 100644
*** a/src/include/catalog/pg_proc.dat
--- b/src/include/catalog/pg_proc.dat
***************
*** 2484,2489 ****
--- 2484,2495 ----
  { oid => '2796', descr => 'smaller of two',
    proname => 'tidsmaller', prorettype => 'tid', proargtypes => 'tid tid',
    prosrc => 'tidsmaller' },
+ { oid => '2233', descr => 'hash',
+   proname => 'hashtid', prorettype => 'int4', proargtypes => 'tid',
+   prosrc => 'hashtid' },
+ { oid => '2234', descr => 'hash',
+   proname => 'hashtidextended', prorettype => 'int8', proargtypes => 'tid int8',
+   prosrc => 'hashtidextended' },

  { oid => '1296',
    proname => 'timedate_pl', prolang => '14', prorettype => 'timestamp',
diff --git a/src/test/regress/expected/tidscan.out b/src/test/regress/expected/tidscan.out
index 521ed1b..6a8afcb 100644
*** a/src/test/regress/expected/tidscan.out
--- b/src/test/regress/expected/tidscan.out
*************** EXPLAIN (ANALYZE, COSTS OFF, SUMMARY OFF
*** 176,179 ****
--- 176,223 ----
  UPDATE tidscan SET id = -id WHERE CURRENT OF c RETURNING *;
  ERROR:  cursor "c" is not positioned on a row
  ROLLBACK;
+ -- bulk joins on CTID
+ -- (these plans don't use TID scans, but this still seems like an
+ -- appropriate place for these tests)
+ EXPLAIN (COSTS OFF)
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+                QUERY PLAN
+ ----------------------------------------
+  Aggregate
+    ->  Hash Join
+          Hash Cond: (t1.ctid = t2.ctid)
+          ->  Seq Scan on tenk1 t1
+          ->  Hash
+                ->  Seq Scan on tenk1 t2
+ (6 rows)
+
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+  count
+ -------
+  10000
+ (1 row)
+
+ SET enable_hashjoin TO off;
+ EXPLAIN (COSTS OFF)
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+                QUERY PLAN
+ -----------------------------------------
+  Aggregate
+    ->  Merge Join
+          Merge Cond: (t1.ctid = t2.ctid)
+          ->  Sort
+                Sort Key: t1.ctid
+                ->  Seq Scan on tenk1 t1
+          ->  Sort
+                Sort Key: t2.ctid
+                ->  Seq Scan on tenk1 t2
+ (9 rows)
+
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+  count
+ -------
+  10000
+ (1 row)
+
+ RESET enable_hashjoin;
  DROP TABLE tidscan;
diff --git a/src/test/regress/sql/tidscan.sql b/src/test/regress/sql/tidscan.sql
index a8472e0..aa5c997 100644
*** a/src/test/regress/sql/tidscan.sql
--- b/src/test/regress/sql/tidscan.sql
*************** EXPLAIN (ANALYZE, COSTS OFF, SUMMARY OFF
*** 63,66 ****
--- 63,78 ----
  UPDATE tidscan SET id = -id WHERE CURRENT OF c RETURNING *;
  ROLLBACK;

+ -- bulk joins on CTID
+ -- (these plans don't use TID scans, but this still seems like an
+ -- appropriate place for these tests)
+ EXPLAIN (COSTS OFF)
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+ SET enable_hashjoin TO off;
+ EXPLAIN (COSTS OFF)
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+ SELECT count(*) FROM tenk1 t1 JOIN tenk1 t2 ON t1.ctid = t2.ctid;
+ RESET enable_hashjoin;
+
  DROP TABLE tidscan;

Simon Riggs <simon@2ndquadrant.com> writes:
> On Sat, 22 Dec 2018 at 04:31, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> BTW, if we're to start taking joins on TID seriously, we should also
>> add the missing hash opclass for TID, so that you can do hash joins
>> when dealing with a lot of rows.

> I don't think we are trying to do TID joins more seriously, just fix a
> special case.
> The case cited requires the batches of work to be small, so nested loops
> works fine.
> Looks to me that Edmund is trying to solve the same problem. If so, this is
> the best solution.

No, I think what Edmund is on about is unrelated, except that it touches
some of the same code.  He's interested in problems like "find the last
few tuples in this table".  You can solve that today, with e.g.
"SELECT ... WHERE ctid >= '(n,1)'", but you get a stupidly inefficient
plan.  If we think that's a use-case worth supporting then it'd be
reasonable to provide less inefficient implementation(s).

What I'm thinking about in this thread is joins on TID, which we have only
very weak support for today --- you'll basically always wind up with a
mergejoin, which requires full-table scan and sort of its inputs.  Still,
that's better than a naive nestloop, and for years we've been figuring
that that was good enough.  Several people in the other thread that
I cited felt that that isn't good enough.  But if we think it's worth
taking seriously, then IMO we need to add both parameterized scans (for
nestloop-with-inner-fetch-by-tid) and hash join, because each of those
can dominate depending on how many tuples you're joining.

            regards, tom lane

On Sat, 22 Dec 2018 at 12:34, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I decided to spend an afternoon seeing exactly how much work would be
> needed to support parameterized TID scans, ie nestloop-with-inner-TID-
> scan joins, as has been speculated about before, most recently here:
>
>
https://www.postgresql.org/message-id/flat/CAMqTPq%3DhNg0GYFU0X%2BxmuKy8R2ARk1%2BA_uQpS%2BMnf71MYpBKzg%40mail.gmail.com
>
> It turns out it's not that bad, less than 200 net new lines of code
> (all of it in the planner; the executor seems to require no work).
>
> Much of the code churn is because tidpath.c is so ancient and crufty.
> It was mostly ignoring the RestrictInfo infrastructure, in particular
> emitting the list of tidquals as just bare clauses not RestrictInfos.
> I had to change that in order to avoid inefficiencies in some places.

It seems good, and I can see you've committed it now.  (I should have
commented sooner, but it's the big summer holiday period here, which
means I have plenty of time to work on PostgreSQL, but none of my
usual resources.  In any case, I was going to say "this looks useful
and not too complicated, please go ahead".)

I did notice that multiple tidquals are no longer removed from scan_clauses:

EXPLAIN SELECT * FROM pg_class WHERE ctid = '(1,1)' OR ctid = '(2,2)';

 Tid Scan on pg_class  (cost=0.01..8.03 rows=2 width=265)
   TID Cond: ((ctid = '(1,1)'::tid) OR (ctid = '(2,2)'::tid))
   Filter: ((ctid = '(1,1)'::tid) OR (ctid = '(2,2)'::tid))

I guess if we thought it was a big deal we could attempt to recreate
the old logic with RestrictInfos.

> I haven't really looked at how much of a merge problem there'll be
> with Edmund Horner's work for TID range scans.  My feeling about it
> is that we might be best off treating that as a totally separate
> code path, because the requirements are significantly different (for
> instance, a range scan needs AND semantics not OR semantics for the
> list of quals to apply).

Well, I guess it's up to me to merge it.  I can't quite see which
parts we'd use a separate code path for.  Can you elaborate?

Edmund

Edmund Horner <ejrh00@gmail.com> writes:
> On Sat, 22 Dec 2018 at 12:34, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I decided to spend an afternoon seeing exactly how much work would be
>> needed to support parameterized TID scans, ie nestloop-with-inner-TID-
>> scan joins, as has been speculated about before, most recently here:
>> ...

> It seems good, and I can see you've committed it now.  (I should have
> commented sooner, but it's the big summer holiday period here, which
> means I have plenty of time to work on PostgreSQL, but none of my
> usual resources.  In any case, I was going to say "this looks useful
> and not too complicated, please go ahead".)

OK.

> I did notice that multiple tidquals are no longer removed from scan_clauses:
> EXPLAIN SELECT * FROM pg_class WHERE ctid = '(1,1)' OR ctid = '(2,2)';
>  Tid Scan on pg_class  (cost=0.01..8.03 rows=2 width=265)
>    TID Cond: ((ctid = '(1,1)'::tid) OR (ctid = '(2,2)'::tid))
>    Filter: ((ctid = '(1,1)'::tid) OR (ctid = '(2,2)'::tid))

I fixed that in the committed version, I believe.  (I'd been
overoptimistic about whether logic could be removed from
create_tidscan_plan.)

>> I haven't really looked at how much of a merge problem there'll be
>> with Edmund Horner's work for TID range scans.  My feeling about it
>> is that we might be best off treating that as a totally separate
>> code path, because the requirements are significantly different (for
>> instance, a range scan needs AND semantics not OR semantics for the
>> list of quals to apply).

> Well, I guess it's up to me to merge it.  I can't quite see which
> parts we'd use a separate code path for.  Can you elaborate?

The thing that's bothering me is something I hadn't really focused on
before, but which looms large now that I've thought about it: the
TID-quals list of a TidPath or TidScan has OR semantics, viz it can
directly represent

    ctid = this OR ctid = that OR ctid = the_other

as a list of tideq OpExprs.  But what you want for a range scan on
TID is implicit-AND, because you might have either a one-sided
condition, say

    ctid >= this

or a range condition

    ctid >= this AND ctid <= that

I see that what you've done to make this sort-of work in the existing
patch is to insist that a range scan have just one member at the OR-d list
level and that has to be an AND'ed sublist, but TBH I think that's a mess;
for instance I wonder whether the code works correctly if faced with cases
like

    ctid >= this OR ctid <= that

I don't think it's at all practical to have tidpath.c dealing with both
cases in one scan of the quals --- even if you can make it work, it'll be
unreasonably complicated and hard to understand.  I'd be inclined to just
have it thumb through the restrictinfo or joininfo list a second time,
looking for inequalities, and build a path for that case separately.

I suspect that on the whole, you'd be better off treating the range-scan
case as completely separate, with a different Path type and different
Plan type too (ie, separate executor support).  Yes, this would involve
some duplication of support code, but I think the end result would be
a lot cleaner and easier to understand.

            regards, tom lane