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

[Robert L. Read]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/elephant-devel/attachments/20070531/7ee62693/attachment.html>