On Tue, Jun 3, 2008 at 1:27 PM, Christophe Leske <[EMAIL PROTECTED]> wrote:
> Hi, > > i am a new member of this list and interested in speeding up my sqlite > queries. > > I am using SQlite in a 3d environment which is close to Google Earth or > Nasa WorldWind. > > We have a city database that is being queried regurlarly depending on > the lat/long position of the viewport in order to show city names and > labels. <rest snipped> >From what I gather, you've got something very similar to the 2D-spatial problem: "I need to find cities that are within R miles of (X,Y)." This translates as "I need to find objects that are within the circle with origin (X, Y) and radius=R". This is fundamentally a collision-detection algorithm, and I have a suggestion that might help, based on the way old DOS game Doom optimized its collision detection code. Here's the setup: You divide the world into equally-sized blocks of width W and height H. Let's say, for the sake of argument, that W=1' and H=1' (this is huge, but it helps illustrate the point) Since the world is 180 degrees north-to-south and 360 degrees around the equator, this gives 64,800 blocks. So, for example: CREATE TABLE blockmap (id integer not null primary key, lat real, long real); Then you need to build a correspondence table: CREATE TABLE blockmapCity(blockmapId, cityId); A naive implementation might only mark a city's center, while a more advanced version might get fancy and have an approximate size of the city and place it in multiple blockmaps, in case it was big enough to spill over into adjacent blocks. What you do then, in order to do a lookup, is to find all of the blocks that intersect with your circle. This can be done easily with the right math. Then, once you've figured out which blocks to include, you just filter out the relevant cities from blockmapCity. Once you have *those* cities you can filter them out as precisely as you were doing before. Some notes: -- Even if you only go down to 1'-by-1' granularity, you've divided the world into 64,800 blocks. Assuming that your 840K cities are all over the globe, and that about 70% of Earth is covered by water, that means that only about 20,000 blocks would actually have cities in them. But with 840K cities, that means you're only considering about 42 cities for a single block. -- The algorithm used to prune down the set of blocks to include doesn't need to be perfect. Remember, this is all an optimization; even if you return every blockmap in the same *hemisphere*, you'd still be searching through only 420K cities instead of 840K! If you need any more help implementing something like this, go ahead and reply to the list. If you can provide a concrete set of data (for example, all or most or at least a significant number of the cities in the US) I can help put together a more concrete example. > > Plus, there are additional databases for special features, like natural > hazards and catastrophies. > > The city database has around 840.000 records, the following schema and > weights currently short under 40Mb: > > sqlite> .schema cities > CREATE TABLE Cities (NAME_DDS TEXT, CLASS_DDS NUMERIC, POPEST_DDS > NUMERIC, LONGI > TUDE_DDS NUMERIC, LATITUDE_DDS NUMERIC); > CREATE INDEX class ON Cities(CLASS_DDS ASC); > CREATE INDEX latlon on Cities(latitude_dds,longitude_dds); > > My questions are: > > - how do I speed up the queries? For small lat/long windows, and high > classes for the cities, i get long query times (e.g. about 600ms) > Is this reasonable to ask for, or IS that already a top speed for this > kind of query? > > - I have indexed latitude AND longitude,as you can see above. Is this ok? > > - I came across the EXLPAIN command, and have read an email by someone > on this list on how to analyze my queries. I should probably do that, > yet i am unfamiliar with reading the output of the Explain command. > > Thanks for your time and eventual help, > > -- > Christophe Leske > > www.multimedial.de - [EMAIL PROTECTED] > http://www.linkedin.com/in/multimedial > Lessingstr. 5 - 40227 Duesseldorf - Germany > 0211 261 32 12 - 0177 249 70 31 > > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- -- Stevie-O Real programmers use COPY CON PROGRAM.EXE _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
