<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 TRANSITIONAL//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; CHARSET=UTF-8">
<META NAME="GENERATOR" CONTENT="GtkHTML/3.3.2">
</HEAD>
<BODY>
Yes, I think I understand this. However, a costly alternative does exist: just never let<BR>
BDB use its own order. Always impose one that we can compute in lisp. Then in <BR>
BDB you store a (position,value) pair instead of a value, and either ensure that BDB <BR>
sorts on the first part of the binary representation of the position the way you want it to,<BR>
or you add a lot of logic into the "cursor-next" operation. This is how it is done on the <BR>
CLSQL side.<BR>
<BR>
It is almost certainly a bit slower, and it is certainly a bit harder to code.<BR>
<BR>
There is a hidden danger in relying upon an order based on the serialized value---namely,<BR>
you can now not swap out serializers without drastic side effects. Since one of the main<BR>
ways that we can improve performance is by writing better serializers (and, in particular,<BR>
serializers that are specific to particular data types), this seems like a bad idea.<BR>
<BR>
It seems to me that the root of the problem is that BDB does indeed order based on a <BR>
serialized value. That is what we should remove. Certainly, if someone were to write <BR>
a Pure-LISP backend, which I hope will occur eventually, it would seem silly for them to <BR>
have to respect an artifact inherited from BDB, when part of the purpose of such a project<BR>
is to escape dependence on BDB.<BR>
<BR>
Forgive me if I'm confused but I assert that we should reverse your argument: we should<BR>
force BDB to be isomorphic to a lisp sorter, not build a lisp sorted isomorphic to BDB.<BR>
<BR>
<BR>
On Tue, 2007-07-31 at 15:24 -0400, Ian Eslick wrote:
<BLOCKQUOTE TYPE=CITE>
<PRE>
<FONT COLOR="#000000">The practical problem that led to the current design of index sorting </FONT>
<FONT COLOR="#000000">is that we cannot use lisp code to define the sorting function for </FONT>
<FONT COLOR="#000000">serialized values inside BDB Btrees (same problem I imagine that </FONT>
<FONT COLOR="#000000">Henrik had with postmodern). Instead, there is a hairy custom C </FONT>
<FONT COLOR="#000000">procedure that is registered with BDB that parses the serialized </FONT>
<FONT COLOR="#000000">format so that sorting is done first by type (symbol, string, object, </FONT>
<FONT COLOR="#000000">pobject, etc) followed by ordering within numeric types, strings and </FONT>
<FONT COLOR="#000000">symbols. Everything else is ordered based on the byte ordering of </FONT>
<FONT COLOR="#000000">its serialized representation.</FONT>
<FONT COLOR="#000000">To map across indices correctly, we need to know up front whether the </FONT>
<FONT COLOR="#000000">start value is less than the end value. And so we need a standard </FONT>
<FONT COLOR="#000000">lisp function that is isomorphic to the BDB sorting function. </FONT>
<FONT COLOR="#000000">Ideally postmodern would have a similar sorting function that </FONT>
<FONT COLOR="#000000">properly interprets the serialized format just like the BDB function </FONT>
<FONT COLOR="#000000">does.</FONT>
<FONT COLOR="#000000">I think it's best to have a single standard ordering that is as close </FONT>
<FONT COLOR="#000000">to lisp's notion of ordering as possible so we don't have to maintain </FONT>
<FONT COLOR="#000000">different orderings.</FONT>
<FONT COLOR="#000000">Ian</FONT>
<FONT COLOR="#000000">PS - It might be possible to have a lisp ordering function implement </FONT>
<FONT COLOR="#000000">BDB's notion of sorting by registering it as a callback, however it </FONT>
<FONT COLOR="#000000">would have to deserialize the BDB values each time. So the problems </FONT>
<FONT COLOR="#000000">with this are both stability concerns for foreign callbacks and the </FONT>
<FONT COLOR="#000000">performance impact of serialization/deserialization for internal BDB </FONT>
<FONT COLOR="#000000">operations. On the cleanliness/performance axis, I think the current </FONT>
<FONT COLOR="#000000">approach is the right tradeoff (it's the original one Ben made, FYI).</FONT>
<FONT COLOR="#000000">On Jul 31, 2007, at 12:50 PM, Robert L. Read wrote:</FONT>
<FONT COLOR="#000000">> Personally, I think the only sensible way to handle this problem is </FONT>
<FONT COLOR="#000000">> to require the user to</FONT>
<FONT COLOR="#000000">> specify an ordering function. We can of course provide a default, </FONT>
<FONT COLOR="#000000">> which will be error-prone</FONT>
<FONT COLOR="#000000">> but tend to work most of the time.</FONT>
<FONT COLOR="#000000">></FONT>
<FONT COLOR="#000000">> The function called "my-generic-less-than" which is in the source </FONT>
<FONT COLOR="#000000">> tree now could be</FONT>
<FONT COLOR="#000000">> a starting point for a generic ordering.</FONT>
<FONT COLOR="#000000">></FONT>
<FONT COLOR="#000000">></FONT>
<FONT COLOR="#000000">> On Tue, 2007-07-24 at 09:48 -0400, Ian Eslick wrote:</FONT>
<FONT COLOR="#000000">>> Robert and I have had some extended discussions on ordering in </FONT>
<FONT COLOR="#000000">>> indices. I think that all we really need to agree on is _some_ </FONT>
<FONT COLOR="#000000">>> canonical ordering. If we have mixed types in an index, how should </FONT>
<FONT COLOR="#000000">>> they be ordered relative to each other? In BDB we have a C </FONT>
<FONT COLOR="#000000">>> function which implements the ordering based on the type tag and </FONT>
<FONT COLOR="#000000">>> then based on the type within it. Are you relying on a pure binary </FONT>
<FONT COLOR="#000000">>> sort in postmodern? Robert or I will get to submitting that patch </FONT>
<FONT COLOR="#000000">>> shortly. I have recently sent in a patch to lisp-compare<= so </FONT>
<FONT COLOR="#000000">>> we'll see if we had to make parallel changes. Thanks, Ian On Jul </FONT>
<FONT COLOR="#000000">>> 24, 2007, at 3:50 AM, Henrik Hjelte wrote: > I sent this message </FONT>
<FONT COLOR="#000000">>> yesterday but I guess it got stuck in the mailing > list filter. </FONT>
<FONT COLOR="#000000">>> Perhaps the attachment was too big. Since my > common-lisp.net </FONT>
<FONT COLOR="#000000">>> user hhjelte does not have write access to elephant I > have </FONT>
<FONT COLOR="#000000">>> placed the patches from here instead: > darcs get <A HREF="http://common">http://common</A>- </FONT>
<FONT COLOR="#000000">>> lisp.net/project/grand-prix/darcs/elephant > > ---------- </FONT>
<FONT COLOR="#000000">>> Forwarded message ---------- > From: Henrik Hjelte </FONT>
<FONT COLOR="#000000">>> <<A HREF="mailto:henrik@evahjelte.com">henrik@evahjelte.com</A>> > Date: Jul 23, 2007 11:28 PM > Subject: </FONT>
<FONT COLOR="#000000">>> some patches > To: <A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A> > > > Here are </FONT>
<FONT COLOR="#000000">>> some darcs patches that might be of interest. I had some > </FONT>
<FONT COLOR="#000000">>> problems with map-index on db-postmodern that made me almost rip </FONT>
<FONT COLOR="#000000">>> my > hair of, but finally I made it to work again. The problem is </FONT>
<FONT COLOR="#000000">>> that > map-index for a string value rely on the ordering in the </FONT>
<FONT COLOR="#000000">>> btree > (continue-p makes use of less than for strings). The </FONT>
<FONT COLOR="#000000">>> postmodern > backend relies on how the database backend orders </FONT>
<FONT COLOR="#000000">>> things, which is not > always the same thing. Is it a necessary </FONT>
<FONT COLOR="#000000">>> feature that b-trees of > string and objects are required to be </FONT>
<FONT COLOR="#000000">>> ordered by lisp-compare<=? > > In the process of solving the bug I </FONT>
<FONT COLOR="#000000">>> have upgraded the test framework > to use FiveAM instead of RT, It </FONT>
<FONT COLOR="#000000">>> has in my opinion a very nice syntax > and some useful features to </FONT>
<FONT COLOR="#000000">>> track dependencies between tests. I hope > you agree that it </FONT>
<FONT COLOR="#000000">>> improves on things. > > /Henrik Hjelte > </FONT>
<FONT COLOR="#000000">>> _______________________________________________ > elephant-devel </FONT>
<FONT COLOR="#000000">>> site list > <A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A> > <A HREF="http://common">http://common</A>- </FONT>
<FONT COLOR="#000000">>> lisp.net/mailman/listinfo/elephant-devel </FONT>
<FONT COLOR="#000000">>> _______________________________________________ elephant-devel </FONT>
<FONT COLOR="#000000">>> site list <A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A> <A HREF="http://common-lisp.net/">http://common-lisp.net/</A> </FONT>
<FONT COLOR="#000000">>> mailman/listinfo/elephant-devel</FONT>
<FONT COLOR="#000000">> _______________________________________________</FONT>
<FONT COLOR="#000000">> elephant-devel site list</FONT>
<FONT COLOR="#000000">> <A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A></FONT>
<FONT COLOR="#000000">> <A HREF="http://common-lisp.net/mailman/listinfo/elephant-devel">http://common-lisp.net/mailman/listinfo/elephant-devel</A></FONT>
<FONT COLOR="#000000">_______________________________________________</FONT>
<FONT COLOR="#000000">elephant-devel site list</FONT>
<FONT COLOR="#000000"><A HREF="mailto:elephant-devel@common-lisp.net">elephant-devel@common-lisp.net</A></FONT>
<FONT COLOR="#000000"><A HREF="http://common-lisp.net/mailman/listinfo/elephant-devel">http://common-lisp.net/mailman/listinfo/elephant-devel</A></FONT>
</PRE>
</BLOCKQUOTE>
</BODY>
</HTML>