On Thu, Nov 27, 2014 at 10:33 AM, Scholz Maik (CM-AI/ECB2) < maik.sch...@de.bosch.com> wrote:
> Hi, > > I like to use a recursive query for analyzing a table with a tree like > data structure. > In my table t1, each row has a column with the parent rowed/o value. > Functional, the queries working fine, but because of the expected size of > t1, > i like to help the query planer with the parent-child relation by creating > this index. > "CREATE INDEX IF NOT EXISTS i_t1 ON t1 (p_o)" > > root/o=1 > child/o=2;p_o=1 > child/o=3;p_o=1 > child/o=4;p_o=1 > child/o=5;p_o=4 > child/o=6;p_o=4 > child/o=7;p_o=4 > > In practice: Q4 is much faster then Q6 because of using the "AUTOMATIC > COVERING INDEX (id=?)". > > My question: > Why is the index i_t1 not used in Q6? > Without doing a detailed analysis of your queries, my first guess would be that you need to change the type declaration on p_o to be INTEGER instead of TEXT, since it is referencing an integer. p_o INTEGER REFERENCES t1(o), That one change might be enough of a hint to the SQLite query planner to help it do a better job. Secondarily, it seems like the SQL-ish thing to do seems like it would be to set p_o to NULL (instead of 0) when the row has no parent. This probably won't make the query run any faster, though. > > Maik > > Example: > Q1:) > BEGIN TRANSACTION; > CREATE TABLE "t1" ( > `o` INTEGER, > `p_o` TEXT NOT NULL, > `a` TEXT NOT NULL, > `id` TEXT NOT NULL, > `tag` TEXT, > PRIMARY KEY(o) > ); > INSERT INTO `t1` VALUES(103903,0,18,59207,2); > INSERT INTO `t1` VALUES(103904,103903,18,59207,516); > INSERT INTO `t1` VALUES(103905,103903,18,59207,5); > INSERT INTO `t1` VALUES(103906,103903,18,59207,545); > INSERT INTO `t1` VALUES(103907,103906,18,59207,8576); > INSERT INTO `t1` VALUES(103908,103906,18,59207,8484); > INSERT INTO `t1` VALUES(103909,103908,18,59207,9344); > INSERT INTO `t1` VALUES(103910,103908,18,59207,9345); > INSERT INTO `t1` VALUES(103911,103908,18,59207,9253); > INSERT INTO `t1` VALUES(103912,103911,18,59207,9600); > INSERT INTO `t1` VALUES(103913,103906,18,59207,8476); > INSERT INTO `t1` VALUES(103914,103913,18,59207,7297); > INSERT INTO `t1` VALUES(103915,103913,18,59207,7185); > INSERT INTO `t1` VALUES(103916,103915,18,59207,4353); > INSERT INTO `t1` VALUES(103917,103913,18,59207,7186); > INSERT INTO `t1` VALUES(103918,103917,18,59207,4609); > INSERT INTO `t1` VALUES(103919,103913,18,59207,7193); > INSERT INTO `t1` VALUES(103920,103919,18,59207,6444); > INSERT INTO `t1` VALUES(103921,103920,18,59207,11392); > INSERT INTO `t1` VALUES(103922,103920,18,59207,11393); > INSERT INTO `t1` VALUES(103923,103906,18,59207,8476); > COMMIT; > > Q2:) > CREATE INDEX IF NOT EXISTS i_t1 ON t1 (p_o) > > sqlite> select * from t1; > "103903" "0" "18" "59207" "2" > "103904" "103903" "18" "59207" "516" > "103905" "103903" "18" "59207" "5" > "103906" "103903" "18" "59207" "545" > "103907" "103906" "18" "59207" "8576" > "103908" "103906" "18" "59207" "8484" > "103909" "103908" "18" "59207" "9344" > "103910" "103908" "18" "59207" "9345" > "103911" "103908" "18" "59207" "9253" > "103912" "103911" "18" "59207" "9600" > "103913" "103906" "18" "59207" "8476" > "103914" "103913" "18" "59207" "7297" > "103915" "103913" "18" "59207" "7185" > "103916" "103915" "18" "59207" "4353" > "103917" "103913" "18" "59207" "7186" > "103918" "103917" "18" "59207" "4609" > "103919" "103913" "18" "59207" "7193" > "103920" "103919" "18" "59207" "6444" > "103921" "103920" "18" "59207" "11392" > "103922" "103920" "18" "59207" "11393" > "103923" "103906" "18" "59207" "8476" > > Q3:) > EXPLAIN QUERY PLAN WITH RECURSIVE > tn(o,level,roottag,id,path) AS ( > SELECT o,0,tag,id,printf('%04p',tag&0xff) AS path FROM t1 WHERE > unlikely(p_o=0) AND (tag=0x02 OR tag=0x03) > UNION > SELECT t1.o,tn.level+1,tn.roottag,tn.id > ,printf('%s.%04p',tn.path,t1.tag&0xff) > FROM t1,tn > WHERE tn.id=t1.id AND tn.o=t1.p_o > ) > SELECT * FROM tn; > > =>Remark: The relation "tn.id=t1.id" is optional! > > "2" "0" "0" "SEARCH TABLE t1 USING INDEX i_t1 (p_o=?)" > "3" "0" "1" "SCAN TABLE tn" > "3" "1" "0" "SEARCH TABLE t1 USING AUTOMATIC COVERING INDEX > (id=?)" > "1" "0" "0" "COMPOUND SUBQUERIES 0 AND 0 USING TEMP B-TREE > (UNION)" > "0" "0" "0" "SCAN SUBQUERY 1" > > Q4:) > WITH RECURSIVE > tn(o,level,roottag,id,path) AS ( > SELECT o,0,tag,id,printf('%04p',tag&0xff) AS path FROM t1 WHERE > unlikely(p_o=0) AND (tag=0x02 OR tag=0x03) > UNION > SELECT t1.o,tn.level+1,tn.roottag,tn.id > ,printf('%s.%04p',tn.path,t1.tag&0xff) > FROM t1,tn > WHERE tn.id=t1.id AND tn.o=t1.p_o > ) > SELECT * FROM tn; > > "103903" "0" "2" "59207" "0002" > "103905" "1" "2" "59207" "0002.0005" > "103904" "1" "2" "59207" "0002.0004" > "103906" "1" "2" "59207" "0002.0021" > "103913" "2" "2" "59207" "0002.0021.001C" > "103923" "2" "2" "59207" "0002.0021.001C" > "103908" "2" "2" "59207" "0002.0021.0024" > "103907" "2" "2" "59207" "0002.0021.0080" > "103915" "3" "2" "59207" "0002.0021.001C.0011" > "103917" "3" "2" "59207" "0002.0021.001C.0012" > "103919" "3" "2" "59207" "0002.0021.001C.0019" > "103914" "3" "2" "59207" "0002.0021.001C.0081" > "103911" "3" "2" "59207" "0002.0021.0024.0025" > "103909" "3" "2" "59207" "0002.0021.0024.0080" > "103910" "3" "2" "59207" "0002.0021.0024.0081" > "103916" "4" "2" "59207" "0002.0021.001C.0011.0001" > "103918" "4" "2" "59207" "0002.0021.001C.0012.0001" > "103920" "4" "2" "59207" "0002.0021.001C.0019.002C" > "103912" "4" "2" "59207" "0002.0021.0024.0025.0080" > "103921" "5" "2" "59207" "0002.0021.001C.0019.002C.0080" > "103922" "5" "2" "59207" "0002.0021.001C.0019.002C.0081" > > Q5:) > EXPLAIN QUERY PLAN WITH RECURSIVE > tn(o,level,roottag,id,path) AS ( > SELECT o,0,tag,id,printf('%04p',tag&0xff) AS path FROM t1 WHERE > unlikely(p_o=0) AND (tag=0x02 OR tag=0x03) > UNION > SELECT t1.o,tn.level+1,tn.roottag,tn.id > ,printf('%s.%04p',tn.path,t1.tag&0xff) > FROM t1,tn > WHERE tn.o=t1.p_o > ) > SELECT * FROM tn; > > "2" "0" "0" "SEARCH TABLE t1 USING INDEX i_t1 (p_o=?)" > "3" "0" "0" "SCAN TABLE t1" > "3" "1" "1" "SCAN TABLE tn" > "1" "0" "0" "COMPOUND SUBQUERIES 0 AND 0 USING TEMP B-TREE > (UNION)" > "0" "0" "0" "SCAN SUBQUERY 1" > > Q6:) > WITH RECURSIVE > tn(o,level,roottag,id,path) AS ( > SELECT o,0,tag,id,printf('%04p',tag&0xff) AS path FROM t1 WHERE > unlikely(p_o=0) AND (tag=0x02 OR tag=0x03) > UNION > SELECT t1.o,tn.level+1,tn.roottag,tn.id > ,printf('%s.%04p',tn.path,t1.tag&0xff) > FROM t1,tn > WHERE tn.o=t1.p_o > ) > SELECT * FROM tn; > > "103903" "0" "2" "59207" "0002" > "103904" "1" "2" "59207" "0002.0004" > "103905" "1" "2" "59207" "0002.0005" > "103906" "1" "2" "59207" "0002.0021" > "103907" "2" "2" "59207" "0002.0021.0080" > "103908" "2" "2" "59207" "0002.0021.0024" > "103913" "2" "2" "59207" "0002.0021.001C" > "103923" "2" "2" "59207" "0002.0021.001C" > "103909" "3" "2" "59207" "0002.0021.0024.0080" > "103910" "3" "2" "59207" "0002.0021.0024.0081" > "103911" "3" "2" "59207" "0002.0021.0024.0025" > "103914" "3" "2" "59207" "0002.0021.001C.0081" > "103915" "3" "2" "59207" "0002.0021.001C.0011" > "103917" "3" "2" "59207" "0002.0021.001C.0012" > "103919" "3" "2" "59207" "0002.0021.001C.0019" > "103912" "4" "2" "59207" "0002.0021.0024.0025.0080" > "103916" "4" "2" "59207" "0002.0021.001C.0011.0001" > "103918" "4" "2" "59207" "0002.0021.001C.0012.0001" > "103920" "4" "2" "59207" "0002.0021.001C.0019.002C" > "103921" "5" "2" "59207" "0002.0021.001C.0019.002C.0080" > "103922" "5" "2" "59207" "0002.0021.001C.0019.002C.0081" > > Q7:) > ANALYZE > > Q8:) > EXPLAIN QUERY PLAN WITH RECURSIVE > tn(o,level,roottag,id,path) AS ( > SELECT o,0,tag,id,printf('%04p',tag&0xff) AS path FROM t1 WHERE > unlikely(p_o=0) AND (tag=0x02 OR tag=0x03) > UNION > SELECT t1.o,tn.level+1,tn.roottag,tn.id > ,printf('%s.%04p',tn.path,t1.tag&0xff) > FROM t1,tn > WHERE tn.o=t1.p_o > ) > SELECT * FROM tn; > > "2" "0" "0" "SEARCH TABLE t1 USING INDEX i_t1 (p_o=?)" > "3" "0" "0" "SCAN TABLE t1" > "3" "1" "1" "SCAN TABLE tn" > "1" "0" "0" "COMPOUND SUBQUERIES 0 AND 0 USING TEMP B-TREE > (UNION)" > "0" "0" "0" "SCAN SUBQUERY 1" > > > _______________________________________________ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users > -- D. Richard Hipp d...@sqlite.org _______________________________________________ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users