Hello Richard!
Thank you very much!! It works! :-)
D. Richard Hipp schrieb:
> On Jan 7, 2009, at 6:11 PM, Lukas Haase wrote:
>
>> Hello,
>>
>> Can somebody tell me why this (simple) query take so much time? This
>> query does nothing more than querying a table and JOINing two other
>> tables together.
>>
>> SELECT
>> ti1.topicID AS topicID,
>> ti2.topic_textID AS parent,
>> n.level,
>> n.level_order
>> FROM navigation AS n
>> LEFT JOIN topic_ids AS ti1 ON ti1.topicID = n.topicID
>> LEFT JOIN topic_ids AS ti2 ON ti2.topicID = n.parent_topicID
>> WHERE ti1.topic_textID = 'XXXXX';
>
> SQLite should be running this query in O(NlogN).
>
> If you change the first LEFT JOIN to a plain old JOIN (which should
> give equivalent results by virtue of the WHERE clause restricting
> ti1.topic_textID to not be NULL) then it should run in O(logN) - much
> faster. Try it and let me know.
Indeed. 0-10 milliseconds instead of 500-800 :-)
But may you tell me why this works and where you have this information?
I know the O-notation but I do not know /why/ this boosts down to log(n)...
I have other queries which worry me. But that trick did not help in
these cases :-(
Especially I have problems with a self-join. In a table I have defined
groups of elements ("printgroup"):
CREATE TABLE printgroup(
topicID INTEGER,
printgroup INTEGER,
PRIMARY KEY(topicID, printgroup)
);
I think these indices are not necessary because both fields are primary
keys anyway.
CREATE INDEX topicID ON printgroup(topicID);
CREATE INDEX pprintgroup ON printgroup(printgroup);
When I know one element of a group (given by topicID) I want to find all
other elements in the same group:
SELECT t.topic, t.length
FROM printgroup AS pg1
LEFT JOIN printgroup AS pg2 ON pg1.printgroup = pg2.printgroup
LEFT JOIN topics AS t ON t.topicID = pg2.topicID
LEFT JOIN topic_ids AS ti ON ti.topicID = pg1.topicID
WHERE ti.topic_textID = 'XXXX'
ORDER BY pg2.topicID ASC;
The table "topics" just contains the actual data for each topicID
(t.topic with length t.length).
This query takes a few seconds (und to minutes) with "sqlite3.exe" and
even much longer in my application (sqlite with CppSQlite3): Up to 15
minutes!
Mimicking your magic above I tried to leave out the "LEFT" in the
self-joins but it did not change anything :-(
And unfortunately, the optimization FAQ [1] is very incomplete, at least
at the interesting points (indices) :-(
Thank you again and best regards,
Luke
[1] http://web.utk.edu/~jplyon/sqlite/SQLite_optimization_FAQ.html
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
