Re: range_adjacent and discrete ranges

I wrote:
> I did a little bit of performance testing on an x86_64 machine (Fedora 14),
> and found that the time to execute a clause like
>     WHERE int4range(1,2) -|- int4range(x, 10000000)
> (x being an integer Var) grows from 0.37 us to 0.56 us if we adopt the
> patched version of range_adjacent.  With float8 ranges it grows from
> 0.35 us to 0.54 us.  So these are noticeable penalties but they don't
> seem like show-stoppers.  Since the alternative is to document that
> the apparent freedom to choose a canonicalization policy is illusory,
> I'm inclined to think we should change it.

It occurred to me that we can easily buy back the extra time for range
types that don't have a canonical function (ie, continuous ranges).
If there's no such function, it's impossible for B..C to normalize to
empty when B < C, so we can skip the extra logic.  The attached version
is no slower than the original code for continuous ranges, and doesn't
seem measurably different from my previous patch for discrete ranges.

            regards, tom lane

*** /home/postgres/pgsql/src/backend/utils/adt/rangetypes.c    Tue Nov 22 23:18:51 2011
--- new/rangetypes.c    Wed Nov 23 16:29:20 2011
***************
*** 699,704 ****
--- 699,706 ----
                  upper2;
      bool        empty1,
                  empty2;
+     RangeType  *r3;
+     int            cmp;

      /* Different types should be prevented by ANYRANGE matching rules */
      if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
***************
*** 714,736 ****
          PG_RETURN_BOOL(false);

      /*
!      * For two ranges to be adjacent, the lower boundary of one range has to
!      * match the upper boundary of the other. However, the inclusivity of
!      * those two boundaries must also be different.
       *
!      * The semantics for range_cmp_bounds aren't quite what we need here, so
!      * we do the comparison more directly.
       */
!     if (lower1.inclusive != upper2.inclusive)
      {
!         if (range_cmp_bound_values(typcache, &lower1, &upper2) == 0)
!             PG_RETURN_BOOL(true);
      }

!     if (upper1.inclusive != lower2.inclusive)
      {
!         if (range_cmp_bound_values(typcache, &upper1, &lower2) == 0)
!             PG_RETURN_BOOL(true);
      }

      PG_RETURN_BOOL(false);
--- 716,774 ----
          PG_RETURN_BOOL(false);

      /*
!      * Given two ranges A..B and C..D, where B < C, the ranges are adjacent
!      * if and only if the range B..C is empty, where inclusivity of these two
!      * bounds is inverted compared to the original bounds.  For discrete
!      * ranges, we have to rely on the canonicalization function to normalize
!      * B..C to empty if it contains no elements of the subtype.  (If there is
!      * no canonicalization function, it's impossible for such a range to
!      * normalize to empty, so we needn't bother to try.)
!      *
!      * If B == C, the ranges are adjacent only if these bounds have different
!      * inclusive flags (i.e., exactly one of the ranges includes the common
!      * boundary point).
       *
!      * And if B > C then the ranges cannot be adjacent in this order, but we
!      * must consider the other order (i.e., check D <= A).
       */
!     cmp = range_cmp_bound_values(typcache, &upper1, &lower2);
!     if (cmp < 0)
!     {
!         /* in a continuous subtype, there are assumed to be points between */
!         if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
!             PG_RETURN_BOOL(false);
!         /* flip the inclusion flags */
!         upper1.inclusive = !upper1.inclusive;
!         lower2.inclusive = !lower2.inclusive;
!         /* change upper/lower labels to avoid Assert failures */
!         upper1.lower = true;
!         lower2.lower = false;
!         r3 = make_range(typcache, &upper1, &lower2, false);
!         PG_RETURN_BOOL(RangeIsEmpty(r3));
!     }
!     if (cmp == 0)
      {
!         PG_RETURN_BOOL(upper1.inclusive != lower2.inclusive);
      }

!     cmp = range_cmp_bound_values(typcache, &upper2, &lower1);
!     if (cmp < 0)
!     {
!         /* in a continuous subtype, there are assumed to be points between */
!         if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
!             PG_RETURN_BOOL(false);
!         /* flip the inclusion flags */
!         upper2.inclusive = !upper2.inclusive;
!         lower1.inclusive = !lower1.inclusive;
!         /* change upper/lower labels to avoid Assert failures */
!         upper2.lower = true;
!         lower1.lower = false;
!         r3 = make_range(typcache, &upper2, &lower1, false);
!         PG_RETURN_BOOL(RangeIsEmpty(r3));
!     }
!     if (cmp == 0)
      {
!         PG_RETURN_BOOL(upper2.inclusive != lower1.inclusive);
      }

      PG_RETURN_BOOL(false);