Dear Maintainer,

The BTREE comparison function is used by the library both to determine record
order within the database and to determine lexicographic identity of the keys
themselves. The second usage contradicts the documentation claim that it
is "reasonable for a comparison function to not examine an entire key in
some applications".

In my application, the database is keyed by interval, i.e. an <offset, extent>
pair. In such a database two keys will compare "equal" if two intervals
intersect, lesser if they do not intersect and the first interval
lies below the second, or greater if they do not intersect and the first lies
above. Thus, the constraint that the BTREE comparison function "must cause the
keys in the database to be well-ordered" is met.

However, the database implementation is also, improperly, utilizing the
comparison function to determine lexicographical order of the keys themselves.
This results in mishandling of the key content in some cases.

For example, in my application:

DB->put <0,10>
DBC->open(DB)
DBC->get(DBC, key:<0,0>, DB_SET_RANGE) returns the record with key <0,10>
DBC->del(DBC)
DB->put(DB, key:<0,5>, DB_NOOVERWITE)
DBC->get(DBC, ..., DB_NEXT) erroneously returns a record with key <0,10>

Oops! The returned record key reflects the deleted record instead of the
record just inserted. As a side note, this record with the
resurrected key does reflect a change in the data value.

What happened? Internally, the second DB->put has discovered a deleted
record and then improperly applied the BTREE comparison function to test
for lexicographic order of the key content itself. Since my comparison function
has returned "equal" it has decided to reuse the old content instead of copying
what the caller supplied.

This usage is both a tighter contraint than the documentation requirement
for a comparison function that reflects "well-ordered" and erroneous since
the documentation also says:

It is reasonable for a comparison function to not examine an entire key in
some applications, which implies partial keys may be specified to the Berkeley
DB interfaces. When partial keys are specified to Berkeley DB, interfaces
which retrieve data items based on a user-specified key (for example,
DB->get() and DBC->get() with the DB_SET flag), will modify the
user-specified key by returning the actual key stored in the database.

Please find a reproducer attached below. I compile with -std=c99 and, of
course, link it using -ldbd. Just create a directory named "DB" in the
current working directory and run the binary with no arguments. It will
print a few lines documenting what it is attempting and eventually (very
quickly) fail with an error reflecting attempted insertion of a record with
a key that conflicts with one already present. That "already present" record is
one that suffered from the resurrected key-content mishandling described above.

* Lee Ward:

Well-ordering requires anti-symmetry, that is compare(A, B) <= 0 and
compare(B, A) <= 0 should imply A = B.  Your example violates that if
A and B intersect because compare(A, B) and compare(B, A) are both
zero, yet you want to treat A and B as distinct.

Agreed. It's defined over a set though. What is that set? I am thinking the set is all keys currently in the database together with the key I am attempting to insert. Are you saying, instead, that the set is all possible keys simultaneously?

* Lee Ward:

I thought about this some more.  Obviously, Berkeley DB assumes that
if two keys compare equal, then one as good as the other.  I don't
know how thoroughly this assumption is built into Berkeley DB.  I
think this some something you need to raise with Oracle (and I'm not
sure if Debian will ever ship newer Berkeley DB versions due lack of
licensing clarity).