On 01-01-18 12:18, Luuk wrote: > On 01-01-18 03:14, Shane Dev wrote: >> Hello, >> >> I have a directed acyclic graph defined as follows - >> >> sqlite> .sch >> CREATE TABLE nodes(id integer primary key, description text); >> CREATE TABLE edges(parent not null references nodes, child not null >> references nodes, primary key(parent, child)); >> >> Now I want to find the "roots" of the graph - i.e nodes which are not >> children of other nodes - >> >> select * from nodes where not exists (select * from edges where child= >> nodes.id); >> >> This works but is very slow when there are a million nodes and edges. > Changing this to: > > select * from nodes where not exists (select 1 from edges where child= > nodes.id); > > saved in my test about 10% of time > >> Is there any way to speed it up?
Above is the same as what Clemens already mentioned ... sqlite> explain query plan select * from nodes where not exists (select * from edges where child=nodes.id); 0|0|0|SCAN TABLE nodes 0|0|0|EXECUTE CORRELATED SCALAR SUBQUERY 1 1|0|0|SCAN TABLE edges Run Time: real 0.009 user 0.000000 sys 0.000000 sqlite> sqlite> explain query plan select * from nodes where not exists (select 1 from edges where child=nodes.id); 0|0|0|SCAN TABLE nodes 0|0|0|EXECUTE CORRELATED SCALAR SUBQUERY 1 1|0|0|SCAN TABLE edges USING COVERING INDEX iedges Run Time: real 0.003 user 0.000000 sys 0.000000 sqlite> _______________________________________________ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
