The practical problem that led to the current design of index sorting
is that we cannot use lisp code to define the sorting function for
serialized values inside BDB Btrees (same problem I imagine that
Henrik had with postmodern). Instead, there is a hairy custom C
procedure that is registered with BDB that parses the serialized
format so that sorting is done first by type (symbol, string, object,
pobject, etc) followed by ordering within numeric types, strings and
symbols. Everything else is ordered based on the byte ordering of
its serialized representation.
To map across indices correctly, we need to know up front whether the
start value is less than the end value. And so we need a standard
lisp function that is isomorphic to the BDB sorting function.
Ideally postmodern would have a similar sorting function that
properly interprets the serialized format just like the BDB function
does.
I think it's best to have a single standard ordering that is as close
to lisp's notion of ordering as possible so we don't have to maintain
different orderings.
Ian
PS - It might be possible to have a lisp ordering function implement
BDB's notion of sorting by registering it as a callback, however it
would have to deserialize the BDB values each time. So the problems
with this are both stability concerns for foreign callbacks and the
performance impact of serialization/deserialization for internal BDB
operations. On the cleanliness/performance axis, I think the current
approach is the right tradeoff (it's the original one Ben made, FYI).
On Jul 31, 2007, at 12:50 PM, Robert L. Read wrote:
Personally, I think the only sensible way to handle this problem is
to require the user to
specify an ordering function. We can of course provide a default,
which will be error-prone
but tend to work most of the time.
The function called "my-generic-less-than" which is in the source
tree now could be
a starting point for a generic ordering.
On Tue, 2007-07-24 at 09:48 -0400, Ian Eslick wrote:
Robert and I have had some extended discussions on ordering in
indices. I think that all we really need to agree on is _some_
canonical ordering. If we have mixed types in an index, how should
they be ordered relative to each other? In BDB we have a C
function which implements the ordering based on the type tag and
then based on the type within it. Are you relying on a pure binary
sort in postmodern? Robert or I will get to submitting that patch
shortly. I have recently sent in a patch to lisp-compare<= so
we'll see if we had to make parallel changes. Thanks, Ian On Jul
24, 2007, at 3:50 AM, Henrik Hjelte wrote: > I sent this message
yesterday but I guess it got stuck in the mailing > list filter.
Perhaps the attachment was too big. Since my > common-lisp.net
user hhjelte does not have write access to elephant I > have
placed the patches from here instead: > darcs get http://common-
lisp.net/project/grand-prix/darcs/elephant > > ----------
Forwarded message ---------- > From: Henrik Hjelte
<[EMAIL PROTECTED]> > Date: Jul 23, 2007 11:28 PM > Subject:
some patches > To: elephant-devel@common-lisp.net > > > Here are
some darcs patches that might be of interest. I had some >
problems with map-index on db-postmodern that made me almost rip
my > hair of, but finally I made it to work again. The problem is
that > map-index for a string value rely on the ordering in the
btree > (continue-p makes use of less than for strings). The
postmodern > backend relies on how the database backend orders
things, which is not > always the same thing. Is it a necessary
feature that b-trees of > string and objects are required to be
ordered by lisp-compare<=? > > In the process of solving the bug I
have upgraded the test framework > to use FiveAM instead of RT, It
has in my opinion a very nice syntax > and some useful features to
track dependencies between tests. I hope > you agree that it
improves on things. > > /Henrik Hjelte >
_______________________________________________ > elephant-devel
site list > elephant-devel@common-lisp.net > http://common-
lisp.net/mailman/listinfo/elephant-devel
_______________________________________________ elephant-devel
site list elephant-devel@common-lisp.net http://common-lisp.net/
mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
_______________________________________________
elephant-devel site list
elephant-devel@common-lisp.net
http://common-lisp.net/mailman/listinfo/elephant-devel
