Re: [google-gears] Re: spatial/location searching - Scott Hess - com.googlegroups.google-gears

6 messages in com.googlegroups.google-gearsRe: [google-gears] Re: spatial/locati...

From	Sent On	Attachments
Steve Nelson	20 Aug 2007 15:04
Scott Hess	20 Aug 2007 15:11
Steve Nelson	20 Aug 2007 18:01
Scott Hess	21 Aug 2007 07:37
Steve Nelson	21 Aug 2007 15:11
Scott Hess	23 Aug 2007 11:13

Subject:	Re: [google-gears] Re: spatial/location searching
From:	Scott Hess (sh....@google.com)
Date:	08/21/2007 07:37:27 AM
List:	com.googlegroups.google-gears

You can certainly have more than one index on a table. I believe that an individual statement cannot use more than one index on a table. If your schema was in place and you ran:

SELECT polygonID FROM PolygonPoints WHERE longitude BETWEEN ? AND ? AND latitude BETWEEN ? and ?

it will only use one of the indices, and will simply scan the matched rows to filter out what doesn't match otherwise. But, if you had an index:

CREATE INDEX INDEX_polygonLATLNG on polygonPoints(latitude, longitude)

then the above statement could use the index to speed up finding matching latitudes, and then scan the same index for longitude matches. Still not optimal, but locality will probably be better than it would be doing the scan on the main table. The impact will probably depend on the relative table and index sizes.

As far as a special-purpose spatial index ... no, there's nothing in there. At this time there are no plans to press for such a feature from the Gears side.

-scott

On 8/20/07, Steve Nelson <m....@secretagents.com> wrote:

I'm pretty sure you can have more than one index on a table. I just tried it and it appears to work fine. Here are a couple of my tables with a couple indexes on the same table:

CREATE TABLE Polygons ( [polygonID] [char] (35) NOT NULL PRIMARY KEY, [name] [char] (50) NULL )

CREATE TABLE PolygonPoints ( [polygonPointID] [char] (35) NOT NULL PRIMARY KEY, [polygonID] [char] (35) NOT NULL, [longitude] [float] NOT NULL, [latitude] [float] NOT NULL)

CREATE INDEX INDEX_polygonLAT on polygonPoints(latitude)

CREATE INDEX INDEX_polygonLNG on polygonPoints(longitude)

There doesn't appear to be a clustered versus non-clustered index in sqlite from what i can tell, maybe i'm wrong. But regardless the index is simply going to speed up the processing time. The bigger question is if there is a better way to search within a polygon besides a square around the polygon.

On 8/20/07, Scott Hess <sh....@google.com> wrote:

I think that SQLite can't use two indexes at that same time. So if you had an x index and a y index, it could use one of them, but not the other. So it might be worth your while to optimize towards that in some manner (which manner I don't immediately see, but I suspect there's something you could do).

You might also want to think on interesting ways to encode coordinates. In SQLite, if you have an index other than INTEGER PRIMARY KEY, then you'll have a b-tree for the index, plus a b-tree for the table. So if your WHERE clause uses the x index, it will first generate a bunch of rowids from the index, then read the data in those rows to satisfy the y part. If you used an index on x,y (both in the index), it might be able to satisfy more of the WHERE clause from the index data. Or the index might get too big and bloated :-).

On 8/20/07, Steve Nelson <m....@secretagents.com> wrote:

Yeah that's what I'm thinking too. I think what i'm going to try to do is make a bounding box based on the max and min latitudes and longitudes for a polygon, then loop through those results and use google maps to determine the exact matches. It won't be extremely fast, but should work.

On 8/20/07, Chris Prince < cpri...@google.com> wrote:

If you want to find all items within a rectangular viewport, you could assign each row an (x, y) position and query for (x >= A1, x <= A2, y

= A3, y <= A4)

If you have a non-rectangular viewport, you could use the rectangular bounding box around that viewport.

On 8/20/07, Steve Nelson < m....@secretagents.com> wrote:

I've just started integrating google gears into a google maps application. I'm curious if anyone has attempted to do spatial algorithms with SQLite? Such as searching within a polygon, or closest to a point etc.