Re: Improving performance of geographic queries

Your reply seems to cover all the key
discussion points of the Oracle Spatial Option - aka the Spatial Data Cartridge.

There are three different flavours, dependent on version of Oracle - 7, 8.0, 8.i - 8.0 uses exactly the strategy I outlined, which is a camouflagued variant of the strategy used in version 7 - my guess is that 8.1 does exactly the same, but uses domain indexes to hide the 'two-column' table as a 'user defined index type'.

Further comments are interleaved with your reply.

--

Jonathan Lewis
Yet another Oracle-related web site: www.jlcomp.demon.co.uk

Gary Cramblitt wrote in message <3788f2d7.158666405_at_news.clark.net>...
>On Sat, 10 Jul 1999 21:15:17 +0100, "Jonathan Lewis"

>Thanks for the reply Jonathan. Something like this had occured to me.
>I wonder what kind of performance improvement this would offer? I'm
>especially worried about that innermost subselect.

I've done some experimentation with the Spatial Data Option in 8.0 which uses this method. The results are quite promising for smallish data sets. The closest approximation to your requirement would be the one where I drew 10,000 lines across an area, and then put the query:

    find all lines that go through tiles that are in the path of line X

The respone time was less than 2 seconds to identify 386 lines of which 241 actually interested line X.

>
>Have you ever done this sort of thing yourself?. I'm wondering what
>resolution the rectangles should be. I assume that would be a
>function of the average radio's circle of mobility and the average
>query. The smaller the rectangles, the better the filter, but the
>more work Oracle has to do and the more storage space is required.

Exacty - it's the usual compromise of getting a good approximation very cheaply before using heavy duty techiques on the prime suspects to find the exact answer.

>Another interesting paper divided the Earth into almost uniform
>triangles. Each triangle was subdivided into four triangles. This was
>repeated to N levels. The triangles had the interesting property that
>1) all the N-level triangles were almost uniform in area, 2) knowing
>the Id of one triangle, one can easily determine the Ids of
>neighboring triangles, and 3) the "parent" or containing triangle was
>simply the Id of a tringle with the last digit dropped. Another
>useful property of these Ids is that they index simultaneously in two
>dimensions, north-south as well as east-west.

This is almost exacly the same method as that use by Oracle, but they use 4 rectangls for their recursive descent. Were these triangles right-angled, or equilateral ? I'm also interested in the recursive numbering system - how does it handle the issue of the 'upside down' triangle in the middle ? I am also fascinated that the IDs can index an any direction at - the problem with Oracle's HHCODEs is that they have to suffer from jump discontinuities.

>Say we start by dividing the Earth into 9 rectangles. Number each
>rectangle from 1 to 9. Divide each rectangle into 9 more rectangles,
>again numbering the subrectangles from 1 to 9. The Id of each
>subrectangle is the number of the parent rectangle concatenated with
>the number of the subrectangle. Keep dividing in this manner for N
>levels. The rectangles at level N then have an Id consisting of N
>digits. To get the Id of the X-1th level, drop the Xth digit. For
>example rectangle 345 is contained in rectangles 34 and 3. Also,
>given the Id of a rectangle at any level X, we already know the Ids of
>all the subrectangles at all levels X+1 through N. For example,
>rectangle 345 contains all the rectangles between 3451 and 3460.

As above - this is actually the approach taken in the HHCODEs (hyper helical scan codes ?) introduced by Oracle in version 7, but using 2, rather than 3 units per side for obvious computational reasons.

>
>Now I'm wondering whether this extra complexity would be worth the
>trouble. Is it better to take the more straight forward approach and
>give Oracle a single constraint with a long (potentially very long)
>list of N-level Ids, and storing a lot of rows in the
>two_column_table, or is it better to generate multiple constraints
>with mixed levels as I have done above, taking advantage of the
>"contains" and "contained in" properties and storing fewer rows in the
>two_column_table?
>

In version 7, Oracle allowed for 'variable granularity' i.e. you thoughs on describing objects as lists of differently sized rectangles. This is nominally allowed in Oracle 8, but the manuals actually say something like:

    this feature exists so that you can experiment, but performance is dire.

Obviously Oracle has to cater for all sorts of generalities in their approach,
so they have to carry overheads that might be a simple nuisance for your application. The requirements of your interface may dictate the best approach
to take.

I found that the main performance issue with the SDO was generating the list of rectangles for a given object - even so, it was never very large: generating a table for 100,000 __points__ the total time required was about 1 hour 45 minutes; for 10,000 lines of 10 points each with an average of 32 rectangles traversed by each line the time was 37 minutes.

I think for the sake of the run-time queries, you probably need to investigate
a strategy that generates a table of bounding rectangles for the target area
(or at least appears to), rather than a literal list of values so that the optimiser
has a chance to select two or three different plans of execution depending on
the number of rectangles in the query area.

I suspect you don't need the Spatial Option, since you know exactly what you are trying to achieve, and have a very precise requirement - it must just
save you time writing it yourself. Received on Mon Jul 12 1999 - 03:55:03 CDT