left and overleft/notright revisited: why !>> and !<< might be poor names - Mailing list pgsql-general

Just thought of this, in reference to earlier discussion about replacing
&< and &> with !<< and !>> to correct the problem w/ rtree search
strategy "replacement" at the node level.

It's possibly nit-picking but I'm that way.

Again, using 1D definitions here.

S << T can be (and I would expect, usually is) defined as "for all x in
S and y in T, x < y" or the equivalent thereof (not exist x in s, y in T
s.t. x>=y, etc).

S !>> T could be defined in at least two ways:

As logical union of << and && cases: S !>> T iff S << T or S && T
As negation of >>: S !>> T iff not (S >> T)

which looked fine, until today when I thought of this.

Consider the empty interval (n,n) (any empty interval will do, they're
all the same empty set), and any nonempty interval (and thus set) S.
For convenience I'll refer to (n,n) in its set form, {}.

Perhaps not so obviously, any of the following are true for all such S:
{} << S, S << {}, {} << {}, and conversely for >>.  This holds true for
all positional "less than" and "greater than" operations I've ever seen
defined over sets (of "ordinary numbers" if you'll pardon that).

Now, if "!>>" (the replacement for overleft) is defined in the first
way, union of << and &&, then {} !>> S is true.  On the other hand, if
"!>>" is defined in the second way, {} !>> S is false.  Hmmm.

Observations:

1. This may be irrelevant.  I don't know what the impact of attempting
to index an empty open interval (or for that matter a singleton closed
interval) in an r-tree would be, but I imagine there might be problems
finding any such interval using any of the strategy operators (except
maybe ~=).  (I'd also imagine whatever type was using the rtree would
need to pick "an" empty interval to represent all of them, but that's
another can of worms).  Whether immediately relevant or not, I feel the
usual definition for the operator should be clear, at least in comments.

2. The whole point of the operator replacement at the node level, you're
testing a box which contains some target T, rather than (in this case)
lying to the left of T.  Thus, the "left or overlap" definition for !>>
seems appropriate, which would mean that !>> really isn't the negation
of >>.

Proposal:

any of:

1. Keep !>> and !<< as "good enough", document (somewhere) that they are
properly defined as "<< or &&" and ">> or &&" respectively, and thus
aren't equivalent to !S>>T and !S<<T resp. where empty open intervals
are concerned;

2. Change the operator names to be more consistent with the definition;

3. Change the definition to !S>>T and !S<<T resp. and comment that empty
open intervals are non-indexable,

or

4. Do nothing, and assume anyone creating a data type that supports open
intervals, and then inserting an empty open interval into an r-tree
index, deserves whatever they get. :)


Thoughts?

-- Bill