[ZODB-Dev] OOBTree: Persistent Objects as keys

[Toby Dickenson]

On Wednesday 06 February 2002 12:27 pm, you wrote:

>The problem occurs when Python falls back to comparing addresses.
>If we could raise an error when this happens, we could avoid building
>meaningless BTrees. (Note that a similar problem occurs when hashes
>based
>on addresses of persistenct objects are uses in has tables.)

I think its bigger than that. Using __cmp__ comparison also has problems when 
mixing unicode string and 8-bit-wide strings.

Even worse, Python reserves the right to change the order of the default 
cross-type comparison. If I remember correctly, the relative sort order of 
None and integers changed in Python 2.2. I wonder how many databases out 
there contain this mix of keys, and will break after upgrading to 2.2.

>Hm, maybe BTrees should use their own comparison algorithm
>that never compares addresses. This would be a bit of a pain, since
>given the complexity of Python's internal comparison logic. Perhaps
>the Python logic could just be copied and the bit that falls back to
>address comparison could be hacked out.

I like the C++ solution to this problem:

The comparison operators (>, >=, ==, etc) define the natural sort order. 
Cross-comparing objects for which there is no natural order (such as
comparing strings to ints, or comparing a complex number to another complex 
number) will cause a failure at compile.

However, it is also possible to define a template function less<> 
which defines a total ordering, and is used by default by the set<> and map<> 
containers (which have the same requirements as our BTrees). There is no 
requirement that this ordering be a sensible one since it is only used by 
data structures, not humans. 

Im not sure how this maps onto a Python solution for BTrees.....

The easiest solution would be to change no code, and attach a big warning to 
the documentation saying that BTree keys must have a stable strict order. 
This would require changes to broken applications: Zope would need a user 
interface for choosing the type of objects for ZCatalog FieldIndex. Thomas' 
application would need to use fatter keys which include a type code (example 
below). However, C++ experience shows that many developers will take a long 
time to fully understand this requirement placed on them.

Im not sure Jims solution (defining a BTree-specific comparison function) can 
work without breaking nice characteristics such as the equivalence of:
* btree[1]
* btree[1.0]
* btree[MyCustomLongIntegerType(1)]


Thomas: your application could use keys which are 2-tuples. The first element 
is a code (string, integer, whatever) defining object classifications. You 
must then ensure that all objects within each classification have a stable 
total order. For example, keys could be ("FooClassification",FooObject(x))