SQLite Forum

The following script demonstrates the problem.  I am adding the script to this
forum thread to save is as  part of the historical record:

~~~
/* Adjust $N and $NSUB as necessary to increase/descrease the
** problem size.  $NSUB was $N/10 in the original problem */
.param set $N 10000
.param set $NSUB 1000
CREATE TABLE node(node_id INTEGER PRIMARY KEY);
CREATE TABLE edge(node_from INT, node_to INT);
CREATE TABLE sub_nodes(node_id INTEGER PRIMARY KEY);
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO node(node_id) SELECT NULL FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO edge(node_from, node_to) SELECT i, i+1 FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$N )
  INSERT INTO edge(node_from, node_to)
    SELECT i, abs((i*1103515245 + 12345) % $N) FROM s;
WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<$NSUB )
  REPLACE INTO sub_nodes(node_id) SELECT abs(i) FROM s;
CREATE INDEX edge_from_to ON edge(node_from,node_to);
CREATE INDEX edge_to_from ON edge(node_to,node_from);
ANALYZE;

.mode box
SELECT * FROM sqlite_stat1;
.stats vmstep
.eqp on
.echo on

SELECT count(*) FROM edge 
 WHERE node_from IN sub_nodes AND node_to IN sub_nodes;

SELECT count(*) FROM edge 
 WHERE +node_from IN sub_nodes AND node_to IN sub_nodes;

SELECT count(*) FROM edge NOT INDEXED
 WHERE node_from IN sub_nodes AND node_to IN sub_nodes;
~~~