[elephant-devel] Fwd: some patches

Thu Aug 2 21:55:04 UTC 2007

Yes, I think I understand this.  However, a costly alternative does
exist:  just never let
BDB use its own order.  Always impose one that we can compute in lisp.
Then in 
BDB you store a (position,value) pair instead of a value, and either
ensure that BDB 
sorts on the first part of the binary representation of the position the
way you want it to,
or you add a lot of logic into the "cursor-next" operation.  This is how
it is done on the 
CLSQL side.

It is almost certainly a bit slower, and it is certainly a bit harder to
code.

There is a hidden danger in relying upon an order based on the
serialized value---namely,
you can now not swap out serializers without drastic side effects.
Since one of the main
ways that we can improve performance is by writing better serializers
(and, in particular,
serializers that are specific to particular data types), this seems like
a bad idea.

It seems to me that the root of the problem is that BDB does indeed
order based on a 
serialized value.  That is what we should remove.  Certainly, if someone
were to write 
a Pure-LISP backend, which I hope will occur eventually, it would seem
silly for them to 
have to respect an artifact inherited from BDB, when part of the purpose
of such a project
is to escape dependence on BDB.

Forgive me if I'm confused but I assert that we should reverse your
argument: we should
force BDB to be isomorphic to a lisp sorter, not build a lisp sorted
isomorphic to BDB.

On Tue, 2007-07-31 at 15:24 -0400, Ian Eslick wrote:

> 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  
> >> <henrik at evahjelte.com> > Date: Jul 23, 2007 11:28 PM > Subject:  
> >> some patches > To: elephant-devel at 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 at common-lisp.net > http://common- 
> >> lisp.net/mailman/listinfo/elephant-devel  
> >> _______________________________________________ elephant-devel  
> >> site list elephant-devel at common-lisp.net http://common-lisp.net/ 
> >> mailman/listinfo/elephant-devel
> > _______________________________________________
> > elephant-devel site list
> > elephant-devel at common-lisp.net
> > http://common-lisp.net/mailman/listinfo/elephant-devel
> 
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20070802/668c8f50/attachment-0001.html>