[elephant-devel] A Modest Proposal

[Ian Eslick]

I think I meant 'dictionary' when I said table - I don't use relational
databases very often so the association isn't that strong for me!

However BTrees support two extra functions that are important for
writing query languages and probably in other operations.  One is that
the traversal is _ordered_, a second is an ability to index _to a point
in an ordering_ and perform successor/predecessor operations from that
point.  (i.e. retrieve objects with slot A between 10 and 20 and a
pointer in slot B to Obj C).

Given that you're seeking to disk, these optimizations are critical to
performance on large datasets.

Persistent sets are clean, but completely unordered.  I think the
sequence datastructure in BDB could be used to implement something like
this, but for now it could be done easily, but more expensively, on top
of an index.  The nice thing, I imagine, is that they just contain ID's
so you can do intersection/difference/append quite easily.  I think you
could do the same with SQL, although I don't know if there's an
efficient SQL implementation unless you can incrementally update the
internal structure of blobs without reading all the data into memory.

Ian


Robert L. Read wrote:
> On Sat, 2006-09-09 at 12:57 -0400, Ian Eslick wrote:
>> So what is the right persistent collection model?  We want something
>> that plays nicely with transactions, doesn't place any onerous
>> performance burden on backends and plays nicely with the existing BDB
>> and SQL implementations.
>>
>
> I strongly support a more abstract model, and I would recommend the
> "Dictionary" as the
> correct abstract model.  (That's what we called it back in CS when I
> was in college.)  The
> hashtable is an implementation of the Dictionary that is so close it's
> hard to remember that
> Dictionary is abstract and hashtable is just one of several
> implementation mechanisms (
> for example, a btree is another.)
>
> I would tend to oppose any notion of "tables".  To me, that is just
> circling back around to
> a relational model; CLSQL and its object-relational mapping partially
> covers that territory.
>
> The "btree" is not very abstract --- it is what BDB uses, and
> therefore was a fine object
> to expose at the time.
>
> Dictionaries of course can support iterators, and one has to have a
> way iterating over
> all of the objects in the collection.  I tend to prefer the "apply
> this function to every object
> in a certain model" to the language of iterators, but in practice it's
> mostly the same.
>
> I only briefly looked at the AllegroStore stuff; but the notion of a
> "persistent set" seems
> quite clean.
>
> But please don't let my comments dissuade others from commenting.
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel