[ZODB-Dev] BTree ranges

[Tim Peters]

[John Belmonte]
>>> Note also that with closed ranges, there is no way to specify an
>>> empty range.

[Tim]
>> You've apparently read my comments whining about this in the C
>> implementation of BTree range searches <0.9 wink>.  An empty range is
>> specified at the Python level by passing (any) min and (any) max
>> with min > max, BTW.

[John]
> I haven't read your comments, but rather computer science texts that
> explain the advantages of half-open ranges.

That's what the wink was for, of course.

> I'm going to close my end of the argument by saying that I can
> point to huge libraries, such as the C++ STL, reviewed over many
> years by professionals and academics alike, that do not contain a
> single use of closed ranges.  There is good reason for it.

There are several, but BTrees have their own use cases that must be
considered.  It's not common to march over an entire BTree one slice at a
time, or to partition a BTree into disjoint segments in any other way, and
those are use cases where half-open ranges are compelling.  A typical query
is a one-shot thing, and allowing to choose whether the bounds are inclusive
or exclusive (as ZODB4 does now) allows for direct hassle-free
implementation of

    lo <= key <= hi
    lo <  key <= hi
    lo <= key <  hi
and
    lo <  key <  hi

queries.  All of those are useful and used.  Throwing away straightforward
support for any in the name of theoretical purity probably isn't going to an
easy sell here.  I could be wrong about that, but changes in existing
behavior usually elicit howls of protest -- also for good reason.

> The use of closed ranges in the BTree containers was a mis-design,
> and it should be deprecated and then eliminated.

It's not a design I would have made myself -- BTrees were like this when I
got here.  But I've seen uses people make of them, and those convince me it
was a defensible design.  It certainly doesn't offend me.  In all, I think
adding exclude-endpoint options was the best thing we could have done.

> Although we weren't able to agree here, I still hope I'll have
> opportunities to cooperate with you in the future.

Sure!  In the end, it doesn't even matter what I think here -- you have to
convince Jim Fulton.  A general outcry of "me too!" or "no way!" on this
mailing list would feed into that, but I suspect we're just typing at each
other on this one (IIRC, nobody else has brought this up before except me,
and ZODB's BTrees have been around a long time).