On May 14, 2008, at 10:02 AM, Robert L. Read wrote:
On Wed, 2008-05-14 at 09:40 -0400, Ian Eslick wrote:
If the BTree node binary data is stored in a lisp octet array, and
we
don't want to deserialize to compare keys, then we need to write the
procedure that you can find in libberkeley-db.c in the src/db-bdb
file. It performs a content-sensitive comparison on a byte-by-byte
basis. This has huge benefits of allowing us to do key comparisons
'in-place' without creating lisp objects. We pass this C function
to
BDB which uses it to compare keys and values directly in the binary
file pages.
I understand the value of this, but is it not possible to write the
comparator on serialized values in LISP? This would then be passed
down
to the lowest level IO operation, which is still in LISP.
I think we can do a much more elegant job, and I like your vision here.
In general I'm imagining a system that does just that as its "query
language", --- take a very lisp-like specification of a predicate and
pass it down to the lowest level I/O operation, or as low as you can
get, and apply it there. This allows us to retain the elegant
"mapcar"
and "map-reduce" strategies as basic querying mechanisms.
It would be nice to unify the comparisons in the map operators with
those in the database!!
If we make a modular serializer, that serializes on the basis of data
type, then it is indeed a challenge for the implementor to implement a
function that performs comparisons on the serialized representation of
that type...but a very worthwhile challenge, I think.
It should be since we always know the type before we consume:
(defmethod compare-serialized-< ((typetag (eql +string+)) stream1
stream2)
Use ops like read-octet and read-int32 to read data from the stream
and compare... Recurse on substructure as necessary
(let ((type1 (read-octet stream1))
(type2 (read-octet stream2)))
(if (eq type1 type2)
(compare-serialized type1 stream1 stream2)
(< type1 type2))))
Which of course is a common idiom that you could compress into:
(dispatch-on-subtype stream1 stream2)
Which returns an ordering on types or an ordering on the values of the
same types. Makes it easy to implement equal and equalp sorting
directly on top of the dbs!
This code isn't like to be terribly pretty given the preponderance of
low-level ops, but if you had a compressed data format you could
create a tag for it and dispatch your own comparison function when
that tag was reached...
Ian
_______________________________________________
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
