On 12/27/2011 10:39 AM, Bo Peng wrote:
The schema of my test tables is as follows:
CREATE TABLE tableA (id INT, pos INT);
CREATE TABLE tableB (start INT, end INT);
CREATE INDEX tableA_idx on tableA (pos asc);
CREATE INDEX tableB_idx on tableB (start asc, end asc);
CREATE TABLE ids (id INT);
tableA saves position of about 8 million objects, and table B saves
about 40 thousand ranges. I need to find out all ids in tableA that
falls into one of the ranges in tableB, and insert the results into
table ids.
If you need to do this with any regularity, you should look at R-Tree
module:
http://www.sqlite.org/rtree.html
I am using a query
INSERT INTO ids SELECT id FROM tableA, tableB WHERE pos BETWEEN start AND end;
with indexes on tableA.pos and tableB.start, tableB.end (combined),
this query takes hours to execute.
An index on tableB(start, end) can only be used to satisfy one condition
(pos >= start). After that, it's a linear scan.
Is there anyway to optimize this
query? My understanding is that, if the query takes each pos and
compare it to all ranges, it will be slow. If it takes each range and
get all pos fall into the range, the query will be much faster.
Try changing the order of tables in the FROM clause:
SELECT id FROM tableB, tableA WHERE pos BETWEEN start AND end;
All other things being equal (and here SQLite has no reason to believe
they are not), SQLite tends to scan on the left hand side of the join,
and search on the right hand side.
Alternatively, drop an index on TableB(start, end). It doesn't help much
anyway, and without it, things are no longer equal and SQLite should
choose the plan you want.
Note that, unless you know that ranges don't overlap, you may be getting
duplicate IDs. You may want to change your query to
SELECT DISTINCT id FROM tableB, tableA WHERE pos BETWEEN start AND end;
I have
tried to 'EXPLAIN' the query but I do not understand the output
Use EXPLAIN QUERY PLAN instead. This produces a human-readable summary
of the plan.
--
Igor Tandetnik
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
