Spatial indexing in mnesia

[David Gould]

On Wed, Jan 03, 2001 at 06:44:40PM -0500, Shawn Pearce wrote:
> Has anyone ever considered storing spatial data in mnesia?  It requires
> creating a different style of indexing than dets must use for lookup of
> records....
> 
> Oracle implements their spatial indexes as an auxiliary table that
> stores each node of the spatial index tree as a row in the table.  This
> table is then indexed using traditional b*-tree indexes for performance.

Informix and Illustra before it, and Postgresql before that (and I think
maybe also DB2) do this using multidimensional indexes, usually based on
R-trees. 

> We'd like to stay with mnesia, but we're running into the trouble of
> overloading mnesia's log writer, and being faced with the need to do
> spatial data.
> 
> I'm afraid performance will suck if we have to implement a spatial index
> as a standard dets table, as we'd be doing 20 or 30 read calls to mnesia
> just to do the lookup in the spatial index, then turn around and perform
> another read call to load the actual record we wanted.  Doing this for
> a few hundred lookups at a time will choke mnesia as far as reading
> goes, right?
> 
> Is this like ``far out there research'' type stuff to be doing with such
> a high-level language as Erlang?  Mnesia is great, but it strikes me
> that its performance is limited by the language's own constraints of
> lists and tuples, none of which can be fixed-length or blocked together
> like one can do in C.

I think the thing to do might be to either implement R-trees in Erlang and
add it to Mnesia, or to write a port driver that used an external R-Tree 
library or server. Might be able to use postgresql directly, or borrow the
R-tree code from it (assuming they haven't done anything foolish like fail
to maintain it...).

-dg

-- 
David Gould                                                 dg@REDACTED
SuSE, Inc.,  580 2cd St. #210,  Oakland, CA 94607          510.628.3380
why would you want to own /dev/null? "ooo! ooo! look! i stole nothing!
i'm the thief of nihilism! i'm the new god of zen monks."