[elephant-devel] Add indexed persistent class slots to elephant?

Tue Jan 24 15:15:01 UTC 2006

Dear Ian,
    Wow.  It sounds like you are indeed deeply in to it.  I am the
maintainer, and not a primary 
author; in some ways I do not even consider myself qualified to answer.
I will happily accept
and your code, as long as the test are green and are you are expanding
the possibilities for
the users, rather than constraining them.  And documentation would be
nice.
    As to your technical questions, about the approaches to implementing
the indexing, in my
experience indexing is one of the most fluid aspects of an object space;
it is a tunable issue
that tends to change as usage pattern changes even more than the
underlying data structure.
So from my point of view I would much prefer macros or simple functions
that let you easily
add, and discard, indexes.  Of course, your observation that one does
typically index a slot
is quite correct, and it would be very convenient if such an index could
be added and dropped
very easily; if one could also implement boolean operators based on
those indexes, so much
the better.  As you state, one should be able to somehow introspect the
class and discover
the existing indexing structure; I'm not sure of the best way to do
that.
    Although I am a "Smug Lisp Weanie" and fairly well educated, I have
to admit that all
of this direct hacking of CLOS and MOP makes my head spin a little.
That is the stuff that
creates the most problems in trying to work with multiple platforms.  We
seem now to 
work with ACL and SBCL, and Andrew Blumberg is helping me solve and
OpenMCL problem
right now.  As a maintainer, I'm a little loathe to recommend even more
complexity in that part.
    However, I always believe interfaces are more important than
implementations.  The real
question is: are you conveniently (elegantly?) expanding the API to make
elephant more useful?
Whether this is done with a simple function or metaclass keywords might
actually be a side 
issue.  The code that will utilize the slot-based indexes is more
important than the code that
will create them.
    If I have a right to insist on anything, I will insist that the
indexes be easily droppable.

On Mon, 2006-01-23 at 23:09 -0500, Ian Eslick wrote:

> While diving into the elephant code to understand it better I started to 
> think about my normal usage model and that one common model is to lookup 
> objects by slot value or a range of slot values.  This seems like a very 
> common operation and that adding an initarg ':indexed' to the metaclass 
> would allow for some simple default functionality:
> 
> low-level interface:
> - define cursors over persistent-class slots as well as btrees and 
> secondary indices
> - make it easy to iterate over duplicate class+slot and class+slot+value 
> keys
> - we get an index of every persistent-object of a given class if we 
> implement
>    the right comparison operation.
> 
> mid-level interface:
> - grab sets of objects based on slot-name and slot-value or range of 
> slot values
> 
> high-level interface:
> - a simple constraint language with boolean combinators that selects 
> instances
>   based on various combinations of slot ranges or values
> - it becomes easier to compile constraints when the class contains 
> information
>   directly that tells you what indexes exist so you can do optimize the 
> query ahead
>   of time.
> 
> Supporting this requires adding an additional around method to (setf 
> slot-value-using-class) on
> persistent-slots to specialize on indexed slots and update the slot 
> index and then potentially
> adding an additional layer of cursor operators.  This is optional 
> functionality that will only slow down write, not read, operations and 
> will be backwards compatible.  It should be easy to add SQL support.  
> The benefit will be to add some nice default behavior that makes the 
> database aspect of the low-level interfaces much more directly 
> accessible to new users. 
> 
> On my local copy I've implemented the metaclass support, overloading and 
> a good chunk of the constraint language and still pass all of the 
> current tests.  I think I understand the problem well enough now to 
> query the user community for advice and buy-in.  I have yet to support 
> all the unpleasant details related to changing classes, but the 
> implications of dropping or adding an indexed slot is rather 
> straightforward so I think that finishing the implementation and writing 
> the appropriate tests isn't too much work.
> 
> The first question is whether the primary developers and users are open 
> to the addition of this feature.
> 
> If so, the big design question I'm facing at present is:
> 
> 1) Reuse the current btree infrastructure to create a btree for each 
> class that maps oids to persistent-objects and instantiate a secondary 
> index for each indexed slot using the slot accessor functions.  This is 
> the easisest to implement, but might provide somewhat poor performance 
> on create & writes.
> 
> 2) Create another underlying DB with string keys 
> "class-name+slot-name+value" => "oid"? 
> 
> 2a) - Is it better to point to oid's or directly to serialized 
> persistent-objects?  The nice thing about oid's is that later I can 
> implement join-like operations in the query language using oids without 
> having to deserialize and cache persistent objects.  Persistent-objects 
> are perhaps more convenient for direct use, however.
> 
> Comments would be greatly appreciated.  I especially invite debate if 
> others feel this is the wrong level of abstraction to work at (i.e. 
> instead write a new def macro for indexed classes and a related protocol 
> that accomplishes the same result by reusing primary and secondary 
> btrees).  The proposal above seems in good taste to me and I've already 
> invested some quality time in it, but since I'll be touching a fair bit 
> of the system to put this in I want to make sure there is support.
> 
> Ian
> 
> 
> 
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel

----
Robert L. Read, PhD                                     read &T
robertlread.net
Consider visiting Progressive Engineering:
http://robertlread.net/pe
In Austin: 912-8593                                        "Think
globally, Act locally." -- RBF


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20060124/96d5c964/attachment.html>