Re: [sqlite] Spatial searches
Besides the suggestions from Dennis below, please search the archives for emails by me on doing exactly this. I achieved fairly decent performance on a database of 7.5 million rows doing lookups on 250k rectangles. I was working on a quad-Xeon server with 4 Gb ram and Win XP, using Perl to work on SQLite. The entire task would take about 23 hours... the performance was nearly linear... slowing down slightly as more records were processed. On 8/24/07, Dennis Cote <[EMAIL PROTECTED]> wrote: > David Thieme wrote: > > Scott, > > Yes, the SELECT is very simple, but slow. I have tens of thousands of > > records and I need the data very fast (embedded realtime system). Some > > databases natively support spatial searches, using KD-trees or R-Trees or > > Quad-trees to improve the search speed. I found an article that explains > > how to implement a custom-spatial search in SQL 2007: > > "Using Table Valued Functions in SQL Server > >2005 to Implement a Spatial Data Library" > > But the solution is very specific to SQL server. I thought there might be > > other tricks that might be common for implementing a fast spatial search in > > a database that doesn't natively support this feature. > > > David, > > SQLite has no direct support for spatial searches, but you should be > able to get reasonable results for a table with thousands of records > using a couple of indexes on the latitude and longitude of the points, > assuming your range is a reasonably small part of your total search space. > > Given a schema like this: > > create table pts ( > id integer primary key, > lat real, > lng real, > data text > ); > > You can create two indexes that will speed up the searches for points > within a rectangle. > > create index lat_idx on pts(lat); > create index lng_idx on pts(lng); > > Now, to do the search you can use a query like this: > > select * from pts where id in > ( > select id from pts where lat between :min_lat and :max_lat > intersect > select id from pts where lng between :min_lng and :max_lng > ); > > If you use explain query plan you can see how this will be executed: > > sqlite> explain query plan select * from pts where id in >...> ( >...> select id from pts where lat between :min_lat and :max_lat >...> intersect >...> select id from pts where lng between :min_lng and :max_lng >...> ); > 0|0|TABLE pts USING PRIMARY KEY > 0|0|TABLE pts WITH INDEX lat_idx > 0|0|TABLE pts WITH INDEX lng_idx > > Or in all its excruciating detail using explain: > > sqlite> explain select * from pts where id in >...> ( >...> select id from pts where lat between :min_lat and :max_lat >...> intersect >...> select id from pts where lng between :min_lng and :max_lng >...> ); > addr opcode p1 p2 p3 > -- -- -- > - > 0 Goto0 78 > 1 Integer 0 0 > 2 OpenRead0 2 > 3 SetNumColumns 0 4 > 4 MemLoad 0 0 > 5 If 0 63 > 6 MemInt 1 0 > 7 OpenEphemeral 3 0 keyinfo(1,BINARY) > 8 SetNumColumns 3 1 > 9 OpenEphemeral 4 1 keyinfo(1,BINARY) > 10Integer 0 0 > 11OpenRead6 3 keyinfo(1,BINARY) > 12SetNumColumns 6 2 > 13Variable2 0 :max_lat > 14IsNull -1 29 > 15MakeRecord 1 0 e > 16MemStore2 1 > 17Variable1 0 :min_lat > 18IsNull -1 29 > 19MakeRecord 1 0 e > 20MoveGe 6 29 > 21MemLoad 2 0 > 22IdxGE 6 29 + > 23Column 6 0 > 24IsNull 1 28 > 25IdxRowid6 0 > 26MakeRecord 1 0 > 27IdxInsert 4 0 > 28Next6 21 > 29Close 6 0 > 30OpenEphemeral 5 1 keyinfo(1,BINARY) > 31Integer 0 0 > 32OpenRead7 4 keyinfo(1,BINARY) > 33SetNumColumns 7 2 > 34Variable4 0 :max_lng > 35IsNull -1 50 > 36MakeRecord 1 0 e > 37MemStore4 1 > 38Variable3 0 :min_lng > 39IsNull
Re: [sqlite] Spatial searches
David Thieme wrote:
Scott,
Yes, the SELECT is very simple, but slow. I have tens of thousands of
records and I need the data very fast (embedded realtime system). Some
databases natively support spatial searches, using KD-trees or R-Trees or
Quad-trees to improve the search speed. I found an article that explains
how to implement a custom-spatial search in SQL 2007:
"Using Table Valued Functions in SQL Server
2005 to Implement a Spatial Data Library"
But the solution is very specific to SQL server. I thought there might be
other tricks that might be common for implementing a fast spatial search in
a database that doesn't natively support this feature.
David,
SQLite has no direct support for spatial searches, but you should be
able to get reasonable results for a table with thousands of records
using a couple of indexes on the latitude and longitude of the points,
assuming your range is a reasonably small part of your total search space.
Given a schema like this:
create table pts (
id integer primary key,
lat real,
lng real,
data text
);
You can create two indexes that will speed up the searches for points
within a rectangle.
create index lat_idx on pts(lat);
create index lng_idx on pts(lng);
Now, to do the search you can use a query like this:
select * from pts where id in
(
select id from pts where lat between :min_lat and :max_lat
intersect
select id from pts where lng between :min_lng and :max_lng
);
If you use explain query plan you can see how this will be executed:
sqlite> explain query plan select * from pts where id in
...> (
...> select id from pts where lat between :min_lat and :max_lat
...> intersect
...> select id from pts where lng between :min_lng and :max_lng
...> );
0|0|TABLE pts USING PRIMARY KEY
0|0|TABLE pts WITH INDEX lat_idx
0|0|TABLE pts WITH INDEX lng_idx
Or in all its excruciating detail using explain:
sqlite> explain select * from pts where id in
...> (
...> select id from pts where lat between :min_lat and :max_lat
...> intersect
...> select id from pts where lng between :min_lng and :max_lng
...> );
addr opcode p1 p2 p3
-- -- --
-
0 Goto0 78
1 Integer 0 0
2 OpenRead0 2
3 SetNumColumns 0 4
4 MemLoad 0 0
5 If 0 63
6 MemInt 1 0
7 OpenEphemeral 3 0 keyinfo(1,BINARY)
8 SetNumColumns 3 1
9 OpenEphemeral 4 1 keyinfo(1,BINARY)
10Integer 0 0
11OpenRead6 3 keyinfo(1,BINARY)
12SetNumColumns 6 2
13Variable2 0 :max_lat
14IsNull -1 29
15MakeRecord 1 0 e
16MemStore2 1
17Variable1 0 :min_lat
18IsNull -1 29
19MakeRecord 1 0 e
20MoveGe 6 29
21MemLoad 2 0
22IdxGE 6 29 +
23Column 6 0
24IsNull 1 28
25IdxRowid6 0
26MakeRecord 1 0
27IdxInsert 4 0
28Next6 21
29Close 6 0
30OpenEphemeral 5 1 keyinfo(1,BINARY)
31Integer 0 0
32OpenRead7 4 keyinfo(1,BINARY)
33SetNumColumns 7 2
34Variable4 0 :max_lng
35IsNull -1 50
36MakeRecord 1 0 e
37MemStore4 1
38Variable3 0 :min_lng
39IsNull -1 50
40MakeRecord 1 0 e
41MoveGe 7 50
42MemLoad 4 0
43IdxGE 7 50 +
44Column 7 0
45IsNull 1 49
46IdxRowid7 0
47MakeRecord 1 0
48IdxInsert 5 0
49Next7 42
50Close 7 0
51Rewind 4 61
52RowKey 4 0
53NotFound5 60
54Column 4 0
55NotNull -1 58
56Pop 1 0
57Goto0 60
58MakeRecord
RE: [sqlite] Spatial searches
Scott, Yes, the SELECT is very simple, but slow. I have tens of thousands of records and I need the data very fast (embedded realtime system). Some databases natively support spatial searches, using KD-trees or R-Trees or Quad-trees to improve the search speed. I found an article that explains how to implement a custom-spatial search in SQL 2007: "Using Table Valued Functions in SQL Server 2005 to Implement a Spatial Data Library" But the solution is very specific to SQL server. I thought there might be other tricks that might be common for implementing a fast spatial search in a database that doesn't natively support this feature. Thanks in advance, David -Original Message- From: Scott Baker [mailto:[EMAIL PROTECTED] Sent: Thursday, August 23, 2007 10:52 AM To: sqlite-users@sqlite.org Subject: Re: [sqlite] Spatial searches David Thieme wrote: > I've been looking for a WinCE embedded database that supports spatial > searches. We are already using SQLite for a very small application; we're > hoping that someone may have some tricks/hints on how to implement fast > searches on spatial data with SQLite. A typical search would be finding > items whose lat/lon falls within a given rectangle (e.g., hotel's closest to > my car). If not, can someone recommend a WinCE database engine that > supports spatial searches? Wouldn't that be something simple like... SELECT Foo WHERE Lat > 1.2 AND LAT < 1.4 AND LONG > 5.6 AND LONG < 6.0? That'll give you a rectangle of values pretty easy. In fact I've implemented that in another database. Pretty easy really. -- Scott Baker - Canby Telcom RHCE - System Administrator - 503.266.8253 - To unsubscribe, send email to [EMAIL PROTECTED] - - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Spatial searches
On Thu, 23 Aug 2007 10:03:00 -0700, David Thieme wrote: >I've been looking for a WinCE embedded database that supports spatial >searches. We are already using SQLite for a very small application; we're >hoping that someone may have some tricks/hints on how to implement fast >searches on spatial data with SQLite. A typical search would be finding >items whose lat/lon falls within a given rectangle (e.g., hotel's closest to >my car). If not, can someone recommend a WinCE database engine that >supports spatial searches? > >David What is wrong with: select * from SpacialData where (SpacialData.PointLatitude <= CurrentLatitude + LatOffset) and (SpacialData.PointLatitude >= CurrentLatitude - LatOffset) and (SpacialData.PointLongitude <= CurrentLongitude + LonOffset) and (SpacialData.PointLongitude >= CurrentLongitude - LonOffset); Chris - To unsubscribe, send email to [EMAIL PROTECTED] -
Re: [sqlite] Spatial searches
David Thieme wrote: > I've been looking for a WinCE embedded database that supports spatial > searches. We are already using SQLite for a very small application; we're > hoping that someone may have some tricks/hints on how to implement fast > searches on spatial data with SQLite. A typical search would be finding > items whose lat/lon falls within a given rectangle (e.g., hotel's closest to > my car). If not, can someone recommend a WinCE database engine that > supports spatial searches? Wouldn't that be something simple like... SELECT Foo WHERE Lat > 1.2 AND LAT < 1.4 AND LONG > 5.6 AND LONG < 6.0? That'll give you a rectangle of values pretty easy. In fact I've implemented that in another database. Pretty easy really. -- Scott Baker - Canby Telcom RHCE - System Administrator - 503.266.8253 - To unsubscribe, send email to [EMAIL PROTECTED] -
[sqlite] Spatial searches
I've been looking for a WinCE embedded database that supports spatial searches. We are already using SQLite for a very small application; we're hoping that someone may have some tricks/hints on how to implement fast searches on spatial data with SQLite. A typical search would be finding items whose lat/lon falls within a given rectangle (e.g., hotel's closest to my car). If not, can someone recommend a WinCE database engine that supports spatial searches? David
