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

Reply via email to