On Thu, Nov 27, 2014 at 10:33 AM, Scholz Maik (CM-AI/ECB2) <
[email protected]> 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
> [email protected]
> http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
>
--
D. Richard Hipp
[email protected]
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
