[elephant-devel] Is it possible to query by 2 index ranges at the same time

[lists at infoway.net]

Hi Ian,

I read the thread from a few days ago regarding OIDs. While I agree with your position, I think it's beneficial to be able to get a list of OIDs to be able to perform these kinds of operations. I think the premise from the other thread was that of "relying" on OIDs for relational purposes.

I also like the idea of where the query system may be going. But, independently of that, being able to specify something like :oid t in the get-instances-by-range function and then be able to "walk" through a set of oids, specifying the base class and the "walk" mechanism will instantiate those objects. Think of it as a primitive to the query system.

Thanks,
Daniel

On Fri, June 1, 2007 2:08 am, Ian Eslick <eslick at csail.mit.edu> said:

> That's very insightful and quite correct!  I was going to use this
> mechanism as part of the query system I want to get working for 1.0.
> This is pretty much the mechanism that relational databases use to do
> join queries and Elephant will be no different.
> 
> As a matter of discipline, I didn't want to encourage users to mess
> around with oids because of the issues outlined in an e-mail thread a
> few days ago.  There will be an internal elephant api to access this
> functionality for advanced users.  That function will essentially be
> a copy of map-inverted-index, but using cursor-get to get only the
> oid instead of cursor-pget to get the oid and primary value.  I'm
> happy to be argued out of this position, but my experience is that
> people will start to depend on this interface and then complain when
> features are added later that leads to bugs in user code.
> 
> The query system will perform these kinds of optimizations for you.
> The interface will be something like:
> 
> (map-query
>    (lambda (obj)
>       (render obj screen))
>    (select-objects (geometry)
>      where
>      (between geometry.x 10 20)
>      (between geometry.y -5 15)))
> 
> For a class named geometry with indexed slots x and y.  If x and y
> are indexed, then the query will be very efficient.  If not, then it
> will be a linear walk.  I aim to add informative statements and
> statistics to select-objects to help people optimize queries.  This
> is similar to the select clause in SQL, but will have features
> oriented towards path queries (object references) and graph queries.
> 
> The select-objects statement effectively returns a generator, which
> will probably be a list of oids, either in memory or maintained on
> disk for large query sets.
> 
> I'm open to suggestions on syntax.  I'm not happy with my current
> sketches here.
> 
> Ian
> 
> PS - If you really want to get OIDs as the user, you can using
> cursors over the inverted index to get the ranges yourself, then you
> can do exactly the intersection operation you mentioned before.  Of
> course you need the classes of the oids so selected to recover the
> objects.
> 
> On May 31, 2007, at 11:43 PM, lists at infoway.net wrote:
> 
>> Please excuse if I don't make a direct reference to Elephant
>> solving this in my comment below. However, I remembered reading
>> something just like this in AllegroCache's Reference Manual, in
>> which it said, and I quote:
>>
>> "In a database every object has a unique object identifier (oid).
>> This value can be retrieved using db- object- oid. An oid is an
>> integer. There is no way to determine the class of an object given
>> its oid.
>>
>> Usually a program need not concern itself with oids. However in
>> certain circumstances it may be convenient to work with oids. One
>> such case is when combining the results of multiple indexes over
>> the same class. You may want to ask for the set of objects whose X
>> slot is greater than 10 and whose Y slot is greater than 20. It
>> consumes fewer resources to ask for the oids of objects whose X
>> slot is greater than 10 than to ask for the objects themselves. In
>> the later case the objects retrieved have to be instantiated in the
>> object cache and there's no point in doing that if you don't need
>> all those objects. In this case you don't need all those objects
>> since you only need those objects  whose Y slot is also greater
>> then 20. Thus the optimal way to do this query is to find the
>> intersection of the oids corresponding to "X > 10" and those oids
>> with "Y > 20" and then from that intersection find the objects
>> corresponding to the oids."
>>
>> They later document the following function:
>>
>> "retrieve- from- index- range (class slot name
>>                             initial value end value
>>                            &key (db *allegrocache*) oid)
>>
>> returns all objects of the given class (a persistent class object
>> or a symbol) whose slot slot name has a value in the range
>> beginning with initial value up to but not including end value. If
>> oid is true then the object id values are returned instead of the
>> objects."
>>
>> It's interesting to note the "oid" key argument. I'm not sure if
>> Elephant's get-instances-by-range supports something like that.
>> But, a similar solution to the problem presented is:
>>
>> "We could find the oids of all the employees whose first name
>> begins with “Jo” and whose last name begins with “F”
>> using
>>
>> (intersection (retrieve-from-index-range
>>                     ‘Employee ‘first-name “Jo”
>> “Jp” :oid
>> t)
>>               (retrieve-from-index-range
>>                     ‘Employee ‘last-name “F”
>> “G”   :oid
>> t))"
>>
>> given a persistent class Employee with indices on slots first-name
>> and last-name.
>>
>> If Elephant supports something similar to the "oid" key argument,
>> it would be very useful for these kind of queries, where you can
>> get an initial result set and only create the instances of those
>> objects if/when needed.
>>
>> Just my $0.02 :)
>>
>> - Daniel
>>
>> On Thu, May 31, 2007 11:07 pm, Ian Eslick <eslick at csail.mit.edu> said:
>>
>>> Ignas,
>>>
>>> The easiest way to do this is to follow Robert's suggestion, and
>>> declare slots x and y to be indexed (assuming your parameters are
>>> slot values of a persistent objects) and then say:
>>>
>>> (remove-duplicates
>>>    (nconc (get-instances-by-range 'my-class 'x 10 20)
>>>           (get-instances-by-range 'my-class 'y -5 15)))
>>>
>>> Of course you might do a little better, performance-wise, if you
>>> filter the y value as you traverse the x range (or vice-versa).
>>> Since get-instances-by-range is just a wrapper around map-inverted-
>>> index that collects visited objects, this could be up to twice as
>>> fast, although in practice I'd expect the benefit to be marginal:
>>>
>>> (let ((matches nil))
>>>    (map-inverted-index (lambda (obj)
>>>                          (when (and (> y -5) (< y 15))
>>>                            (push obj matches)))
>>> 	              'my-class
>>>          	      'x
>>> 	              10
>>>                        20)
>>>    matches)
>>>
>>> This version avoids a second map-inverted-index operation (called by
>>> get-instances-by-range) by only collecting objects if their y
>>> coordinate is in the range.  You can wrap all this in a function like
>>> (get-objects-in-region x1 y1 x2 y2).  Map over the x or y based on
>>> which query is smaller, or which parameter is sparser.  If you don't
>>> know, then it doesn't really matter which you choose!
>>>
>>> If you get some performance comparisons of these two scenarios,
>>> please post them to the list!
>>>
>>> Regards,
>>> Ian
>>>
>>> PS - It would be interesting to see an R-tree (or one of the well-
>>> known variants such as R* or Priority R-Trees) in Elephant.  Instead
>>> of using indexed classes, you would directly implement the R-tree
>>> nodes as persistent instances and write the construction and
>>> retrieval algorithms as if they were operating on in-memory objects.
>>> Graphs are a very natural structure to implement in Elephant and the
>>> only special provision I can think of might be maintaining a
>>> persistent set of free nodes for the dynamic case.
>>>
>>> On May 31, 2007, at 10:17 PM, Robert L. Read wrote:
>>>
>>>> I'm assuming x and y are properites of a data object, which has
>>>> some other component z which
>>>> you with to retrieve, and you query is that you want to find all
>>>> the records (x,y,z) such that
>>>> (10 < x < 20) and ( -5 < y < 15).
>>>>
>>>> There is a spectrum of solutions to this problem.  However, in the
>>>> general case Elephant will
>>>> not compute this with the best possible asymptotic complexity,
>>>> although it may be better than
>>>> a relational database at doing so.
>>>>
>>>> Here is the most naive solution:
>>>>
>>>> Examine every object in the database, and report those that meet
>>>> that above condition.
>>>>
>>>> Although this may seem silly, don't knock it till you try it....it
>>>> may be perfectly reasonable.
>>>>
>>>> A second solution is to make sure that you have specified :index on
>>>> the x component
>>>> (or, without loss of generality, the y component), and then using
>>>> the "get-instance-by-range"
>>>> feature to get all of the instances within the x range, and use a
>>>> simple lisp function to discard
>>>> those for which the y component does not match.
>>>>
>>>> This will be relatively fast if the x range excludes a lot of
>>>> objects and the y range doesn't.
>>>>
>>>> It's not obvious to me that one can do better than that without
>>>> some significant coding
>>>> (For example, a "grid file" is a datastructure designed to answer
>>>> such queries efficiently.
>>>> An R-Tree is another geometric structure.)
>>>>
>>>> A relational database will not do better, in the worst case.  A
>>>> relational database will do
>>>> a better job at statistical sampling---that is, a query optimizer
>>>> should, in a huge database,
>>>> be able to decide whether it should use the "x" index or the "y"
>>>> index first based on the
>>>> selectivity of those clauses in the boolean expression.  However,
>>>> fundamentally it can't
>>>> do any better than to pick the best index, use that only examine
>>>> some of the objects, and then
>>>> look at the values of the other ones.
>>>>
>>>> On Fri, 2007-06-01 at 03:48 +0300, Ignas Mikalajunas wrote:
>>>>> Hi, i have an interesting usecase and i would like to ask whether
>>>>> i can solve it by using Elephant. I would like to index objects
>>>>> placed on a discreet 2d grid of an arbitarry size, which would
>>>>> require queries like (10 < x < 20) AND (-5 < y < 15). Is it
>>>>> possible to perform such a query with elephant? I am not sure i
>>>>> have looked in the right place, but i could not find such example
>>>>> in the manual. Ignas Mikalajūnas
>>>>> _______________________________________________ elephant-devel
>>>>> site list elephant-devel at common-lisp.net http://common-lisp.net/
>>>>> mailman/listinfo/elephant-devel
>>>> _______________________________________________
>>>> elephant-devel site list
>>>> elephant-devel at common-lisp.net
>>>> http://common-lisp.net/mailman/listinfo/elephant-devel
>>>
>>> _______________________________________________
>>> elephant-devel site list
>>> elephant-devel at common-lisp.net
>>> http://common-lisp.net/mailman/listinfo/elephant-devel
>>>
>>
>> _______________________________________________
>> elephant-devel site list
>> elephant-devel at common-lisp.net
>> http://common-lisp.net/mailman/listinfo/elephant-devel
> 
>