[elephant-devel] Re: Derived Indicies

[Ian Eslick]

Hi Alex,

You make a good point below.  I haven't dealt with these kind of small  
subsets from large sets using multiple parameters problems in a large  
system.  However, if we take a page from Robert's book about using  
lisp as the query engine - how would we solve this problem just with  
lisp objects?

Given that in Elephant, the cost of a btree instance is negligable,  
one way to do this is the just have a set of messages for each user in  
a user slot (a pset or set-valued slot).  Rather than creating a  
message with a relational connection to a user, we just create a  
message and add it to the user's collection of messages.  Of course to  
get the full efficiency you want, we'd have to make a sorted-pset that  
sorts on some fn of the elements.

I'd like to think about different metaphors for solving these problems  
so we don't end up turning Elephant's interface into a less efficient  
variation of an ORM!

Ian

On Mar 23, 2008, at 5:27 PM, Alex Mizrahi wrote:

> IE> unnecessary.  If you have messages indexed by time than you can  
> simply
> IE> walk the index and filter by user until you have a web page  
> worth of
> IE> messages.
>
> worst case behaviour is very bad -- to prove that there are no  
> messages, it
> will have to scan all of them..
> what's even worse, this worst case is quite frequent -- many users  
> actually
> have empty inboxes.
>
> IE>   A scan, even of an index, may not be fast enough so you could  
> do an
> IE> intersection of user-to values with an ordered list of recent  
> messages.
>
> you mean reading oids from user-to index and scanning/filtering
> modification-time index with them?
> this will mean same worst case.
> of course sufficiently smart system can see which list is less, but  
> still
> with thousands of messages and thousands of users this is going to  
> be quite
> slow.
>
> IE> This should perform similarly to a SQL engine which many ORM  
> systems
> IE> use for queries like this.
>
> i thought in SQL DBMS expression like "create index tree11_idx on
> tree11(qi,value)"
> builds ordered list (btree) of pairs pretty much as in derived index  
> i've
> described, and this will make lookups on both values fast.
>

Quite right.

>
>
> _______________________________________________
> elephant-devel site list
> elephant-devel at common-lisp.net
> http://common-lisp.net/mailman/listinfo/elephant-devel