Using the current tip of trunk (my version of a8d921136f) I get the following results (this is after analyze being run). Clearly the different spellings of the same request result in wildly different query plans and vdbe code being generated, the most efficient being the "direct join" where the planner has the most latitude to choose the nesting order. The interesting thing is that the IN form should be no less efficient that the EXISTS form, but it is. ``` sqlite> SELECT count(_rowid_) ...> FROM edge ...> WHERE node_from IN sub_nodes ...> AND node_to IN sub_nodes ...> ; QUERY PLAN |--SEARCH edge USING COVERING INDEX edge_to_from (node_to=? AND node_from=?) (~44 rows) |--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR `--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 31 0 0 Start at 31 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 3 8 0 k(3,,,) 0 root=8 iDb=0; edge_to_from 3 ColumnsUsed 3 0 0 3 0 4 Explain 4 0 0 SEARCH edge USING COVERING INDEX edge_to_from (node_to=? AND node_from=?) (~44 rows) 0 5 Noop 0 0 0 0 Begin WHERE-loop0: edge 6 Once 0 8 0 0 7 OpenRead 4 4 0 1 0 root=4 iDb=0; sub_nodes 8 Rewind 4 26 0 0 9 Rowid 4 3 0 0 r[3]=rowid 10 IsNull 3 25 0 0 if r[3]==NULL goto 25 11 Once 0 13 0 0 12 OpenRead 5 4 0 1 0 root=4 iDb=0; sub_nodes 13 Rewind 5 25 0 0 14 Rowid 5 4 0 0 r[4]=rowid 15 IsNull 4 24 0 0 if r[4]==NULL goto 24 16 SeekScan 18 19 0 0 Scan-ahead up to 18 rows 17 SeekGE 3 24 3 2 0 key=r[3..4] 18 IdxGT 3 24 3 2 0 key=r[3..4] 19 Noop 0 0 0 0 Begin WHERE-core 20 IdxRowid 3 5 0 0 r[5]=rowid 21 AggStep 0 5 1 count(1) 1 accum=r[1] step(r[5]) 22 Noop 0 0 0 0 End WHERE-core 23 Next 3 18 0 0 24 Next 5 14 0 0 25 Next 4 9 0 0 26 Noop 0 0 0 0 End WHERE-loop0: edge 27 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 28 Copy 1 6 0 0 r[6]=r[1] 29 ResultRow 6 1 0 0 output=r[6] 30 Halt 0 0 0 0 31 Transaction 0 0 7 0 1 usesStmtJournal=0 32 Goto 0 1 0 0 ┌────────────────┐ │ count(_rowid_) │ ├────────────────┤ │ 1929 │ └────────────────┘ Run Time: real 5.817 user 5.703125 sys 0.031250 sqlite> SELECT count(_rowid_) ...> FROM edge ...> WHERE +node_from IN sub_nodes ...> AND node_to IN sub_nodes ...> ; QUERY PLAN |--SEARCH edge USING COVERING INDEX edge_to_from (node_to=?) (~44 rows) |--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR `--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 35 0 0 Start at 35 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 3 8 0 k(3,,,) 2 root=8 iDb=0; edge_to_from 3 ColumnsUsed 3 0 0 3 0 4 Explain 4 0 0 SEARCH edge USING COVERING INDEX edge_to_from (node_to=?) (~44 rows) 0 5 Noop 0 0 0 0 Begin WHERE-loop0: edge 6 Once 0 8 0 0 7 OpenRead 4 4 0 1 0 root=4 iDb=0; sub_nodes 8 Rewind 4 30 0 0 9 Rowid 4 3 0 0 r[3]=rowid 10 IsNull 3 29 0 0 if r[3]==NULL goto 29 11 SeekGE 3 29 3 1 0 key=r[3] 12 IdxGT 3 29 3 1 0 key=r[3] 13 Noop 0 0 0 0 begin IN expr 14 Once 0 16 0 0 15 OpenRead 5 4 0 1 0 root=4 iDb=0; sub_nodes 16 Column 3 1 4 0 r[4]=edge.node_from 17 SeekRowid 5 28 4 0 intkey=r[4] 18 Goto 0 24 0 0 19 Goto 0 28 0 0 20 Rewind 5 28 0 0 21 Column 5 0 5 0 r[5]= 22 Ne 4 28 5 BINARY-8 0 if r[5]!=r[4] goto 28 23 Goto 0 28 0 0 end IN expr 24 Noop 0 0 0 0 Begin WHERE-core 25 IdxRowid 3 5 0 0 r[5]=rowid 26 AggStep 0 5 1 count(1) 1 accum=r[1] step(r[5]) 27 Noop 0 0 0 0 End WHERE-core 28 Next 3 12 0 0 29 Next 4 9 0 0 30 Noop 0 0 0 0 End WHERE-loop0: edge 31 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 32 Copy 1 6 0 0 r[6]=r[1] 33 ResultRow 6 1 0 0 output=r[6] 34 Halt 0 0 0 0 35 Transaction 0 0 7 0 1 usesStmtJournal=0 36 Goto 0 1 0 0 ┌────────────────┐ │ count(_rowid_) │ ├────────────────┤ │ 1929 │ └────────────────┘ Run Time: real 0.124 user 0.015625 sys 0.015625 sqlite> SELECT count(_rowid_) ...> FROM edge ...> WHERE +node_from IN sub_nodes ...> AND +node_to IN sub_nodes ...> ; QUERY PLAN |--SCAN edge (~180224 rows) |--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR `--USING ROWID SEARCH ON TABLE sub_nodes FOR IN-OPERATOR addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 39 0 0 Start at 39 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 0 3 0 2 0 root=3 iDb=0; edge 3 ColumnsUsed 0 0 0 3 0 4 Explain 4 0 0 SCAN edge (~180224 rows) 0 5 Noop 0 0 0 0 Begin WHERE-loop0: edge 6 Rewind 0 34 0 0 7 Noop 0 0 0 0 begin IN expr 8 Once 0 10 0 0 9 OpenRead 3 4 0 1 0 root=4 iDb=0; sub_nodes 10 Column 0 0 3 0 r[3]=edge.node_from 11 SeekRowid 3 33 3 0 intkey=r[3] 12 Goto 0 18 0 0 13 Goto 0 33 0 0 14 Rewind 3 33 0 0 15 Column 3 0 4 0 r[4]= 16 Ne 3 33 4 BINARY-8 0 if r[4]!=r[3] goto 33 17 Goto 0 33 0 0 end IN expr 18 Noop 0 0 0 0 begin IN expr 19 Once 0 21 0 0 20 OpenRead 4 4 0 1 0 root=4 iDb=0; sub_nodes 21 Column 0 1 4 0 r[4]=edge.node_to 22 SeekRowid 4 33 4 0 intkey=r[4] 23 Goto 0 29 0 0 24 Goto 0 33 0 0 25 Rewind 4 33 0 0 26 Column 4 0 5 0 r[5]= 27 Ne 4 33 5 BINARY-8 0 if r[5]!=r[4] goto 33 28 Goto 0 33 0 0 end IN expr 29 Noop 0 0 0 0 Begin WHERE-core 30 Rowid 0 5 0 0 r[5]=rowid 31 AggStep 0 5 1 count(1) 1 accum=r[1] step(r[5]) 32 Noop 0 0 0 0 End WHERE-core 33 Next 0 7 0 1 34 Noop 0 0 0 0 End WHERE-loop0: edge 35 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 36 Copy 1 6 0 0 r[6]=r[1] 37 ResultRow 6 1 0 0 output=r[6] 38 Halt 0 0 0 0 39 Transaction 0 0 7 0 1 usesStmtJournal=0 40 Goto 0 1 0 0 ┌────────────────┐ │ count(_rowid_) │ ├────────────────┤ │ 1929 │ └────────────────┘ Run Time: real 0.151 user 0.031250 sys 0.046875 sqlite> SELECT count(_rowid_) ...> FROM edge ...> WHERE EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_from) ...> AND EXISTS (SELECT * FROM sub_nodes WHERE node_id == node_to) ...> ; QUERY PLAN |--SCAN edge (~180224 rows) |--CORRELATED SCALAR SUBQUERY 1 | `--SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row) `--CORRELATED SCALAR SUBQUERY 2 `--SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row) addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 49 0 0 Start at 49 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 0 3 0 2 0 root=3 iDb=0; edge 3 ColumnsUsed 0 0 0 3 0 4 Explain 4 0 0 SCAN edge (~180224 rows) 0 5 Noop 0 0 0 0 Begin WHERE-loop0: edge 6 Rewind 0 44 0 0 7 Integer 21 4 0 0 r[4]=21; return address 8 Integer 0 5 0 0 r[5]=0; Init EXISTS result 9 Integer 1 6 0 0 r[6]=1; LIMIT counter 10 OpenRead 1 4 0 0 0 root=4 iDb=0; sub_nodes 11 ColumnsUsed 1 0 0 0 0 12 Explain 12 0 0 SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row) 0 13 Noop 0 0 0 0 Begin WHERE-loop0: sub_nodes 14 Column 0 0 7 0 r[7]=edge.node_from 15 SeekRowid 1 20 7 0 intkey=r[7] 16 Noop 0 0 0 0 Begin WHERE-core 17 Integer 1 5 0 0 r[5]=1 18 DecrJumpZero 6 21 0 0 if (--r[6])==0 goto 21 19 Noop 0 0 0 0 End WHERE-core 20 Noop 0 0 0 0 End WHERE-loop0: sub_nodes 21 Return 4 0 0 0 22 IfNot 5 43 1 0 23 Integer 37 9 0 0 r[9]=37; return address 24 Integer 0 10 0 0 r[10]=0; Init EXISTS result 25 Integer 1 11 0 0 r[11]=1; LIMIT counter 26 OpenRead 2 4 0 0 0 root=4 iDb=0; sub_nodes 27 ColumnsUsed 2 0 0 0 0 28 Explain 28 0 0 SEARCH sub_nodes USING INTEGER PRIMARY KEY (rowid=?) (~1 row) 0 29 Noop 0 0 0 0 Begin WHERE-loop0: sub_nodes 30 Column 0 1 12 0 r[12]=edge.node_to 31 SeekRowid 2 36 12 0 intkey=r[12] 32 Noop 0 0 0 0 Begin WHERE-core 33 Integer 1 10 0 0 r[10]=1 34 DecrJumpZero 11 37 0 0 if (--r[11])==0 goto 37 35 Noop 0 0 0 0 End WHERE-core 36 Noop 0 0 0 0 End WHERE-loop0: sub_nodes 37 Return 9 0 0 0 38 IfNot 10 43 1 0 39 Noop 0 0 0 0 Begin WHERE-core 40 Rowid 0 3 0 0 r[3]=rowid 41 AggStep 0 3 1 count(1) 1 accum=r[1] step(r[3]) 42 Noop 0 0 0 0 End WHERE-core 43 Next 0 7 0 1 44 Noop 0 0 0 0 End WHERE-loop0: edge 45 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 46 Copy 1 14 0 0 r[14]=r[1] 47 ResultRow 14 1 0 0 output=r[14] 48 Halt 0 0 0 0 49 Transaction 0 0 7 0 1 usesStmtJournal=0 50 Goto 0 1 0 0 ┌────────────────┐ │ count(_rowid_) │ ├────────────────┤ │ 1929 │ └────────────────┘ Run Time: real 0.200 user 0.078125 sys 0.046875 sqlite> SELECT count(edge._rowid_) ...> FROM edge ...> JOIN sub_nodes as s1 ON s1.node_id == node_from ...> JOIN sub_nodes as s2 ON s2.node_id == node_to ...> ; QUERY PLAN |--SCAN s1 (~9216 rows) |--SEARCH edge USING COVERING INDEX edge_from_to (node_from=?) (~2 rows) `--SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 35 0 0 Start at 35 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 1 4 0 0 0 root=4 iDb=0; sub_nodes 3 ColumnsUsed 1 0 0 0 0 4 OpenRead 3 7 0 k(3,,,) 2 root=7 iDb=0; edge_from_to 5 ColumnsUsed 3 0 0 3 0 6 OpenRead 2 4 0 0 0 root=4 iDb=0; sub_nodes 7 ColumnsUsed 2 0 0 0 0 8 Explain 8 0 0 SCAN s1 (~9216 rows) 0 9 Noop 0 0 0 0 Begin WHERE-loop0: sub_nodes 10 Rewind 1 30 0 0 11 Explain 11 0 0 SEARCH edge USING COVERING INDEX edge_from_to (node_from=?) (~2 rows) 0 12 Noop 0 0 0 0 Begin WHERE-loop1: edge 13 Rowid 1 3 0 0 r[3]=rowid 14 CursorHint 3 0 0 EQ(r[3],c0) 0 15 Rowid 1 4 0 0 r[4]=rowid 16 SeekGE 3 28 4 1 0 key=r[4] 17 IdxGT 3 28 4 1 0 key=r[4] 18 Explain 18 0 0 SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) 0 19 Noop 0 0 0 0 Begin WHERE-loop2: sub_nodes 20 Column 3 1 5 0 r[5]=edge.node_to 21 SeekRowid 2 26 5 0 intkey=r[5] 22 Noop 0 0 0 0 Begin WHERE-core 23 IdxRowid 3 6 0 0 r[6]=rowid 24 AggStep 0 6 1 count(1) 1 accum=r[1] step(r[6]) 25 Noop 0 0 0 0 End WHERE-core 26 Noop 0 0 0 0 End WHERE-loop2: sub_nodes 27 Next 3 17 0 0 28 Noop 0 0 0 0 End WHERE-loop1: edge 29 Next 1 11 0 1 30 Noop 0 0 0 0 End WHERE-loop0: sub_nodes 31 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 32 Copy 1 7 0 0 r[7]=r[1] 33 ResultRow 7 1 0 0 output=r[7] 34 Halt 0 0 0 0 35 Transaction 0 0 7 0 1 usesStmtJournal=0 36 Goto 0 1 0 0 ┌─────────────────────┐ │ count(edge._rowid_) │ ├─────────────────────┤ │ 1929 │ └─────────────────────┘ Run Time: real 0.114 user 0.015625 sys 0.000000 sqlite> SELECT count(edge._rowid_) ...> FROM edge ...> JOIN sub_nodes as s1 ON s1.node_id == +node_from ...> JOIN sub_nodes as s2 ON s2.node_id == +node_to ...> ; QUERY PLAN |--SCAN edge (~196608 rows) |--SEARCH s1 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) `--SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) addr opcode p1 p2 p3 p4 p5 comment ---- ------------- ---- ---- ---- ------------- -- ------------- 0 Init 0 31 0 0 Start at 31 1 Null 0 1 2 0 r[1..2]=NULL 2 OpenRead 0 3 0 2 0 root=3 iDb=0; edge 3 ColumnsUsed 0 0 0 3 0 4 OpenRead 1 4 0 0 0 root=4 iDb=0; sub_nodes 5 ColumnsUsed 1 0 0 0 0 6 OpenRead 2 4 0 0 0 root=4 iDb=0; sub_nodes 7 ColumnsUsed 2 0 0 0 0 8 Explain 8 0 0 SCAN edge (~196608 rows) 0 9 Noop 0 0 0 0 Begin WHERE-loop0: edge 10 Rewind 0 26 0 0 11 Explain 11 0 0 SEARCH s1 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) 0 12 Noop 0 0 0 0 Begin WHERE-loop1: sub_nodes 13 Column 0 0 3 0 r[3]=edge.node_from 14 SeekRowid 1 24 3 0 intkey=r[3] 15 Explain 15 0 0 SEARCH s2 USING INTEGER PRIMARY KEY (rowid=?) (~1 row) 0 16 Noop 0 0 0 0 Begin WHERE-loop2: sub_nodes 17 Column 0 1 4 0 r[4]=edge.node_to 18 SeekRowid 2 23 4 0 intkey=r[4] 19 Noop 0 0 0 0 Begin WHERE-core 20 Rowid 0 5 0 0 r[5]=rowid 21 AggStep 0 5 1 count(1) 1 accum=r[1] step(r[5]) 22 Noop 0 0 0 0 End WHERE-core 23 Noop 0 0 0 0 End WHERE-loop2: sub_nodes 24 Noop 0 0 0 0 End WHERE-loop1: sub_nodes 25 Next 0 11 0 1 26 Noop 0 0 0 0 End WHERE-loop0: edge 27 AggFinal 1 1 0 count(1) 0 accum=r[1] N=1 28 Copy 1 6 0 0 r[6]=r[1] 29 ResultRow 6 1 0 0 output=r[6] 30 Halt 0 0 0 0 31 Transaction 0 0 7 0 1 usesStmtJournal=0 32 Goto 0 1 0 0 ┌─────────────────────┐ │ count(edge._rowid_) │ ├─────────────────────┤ │ 1929 │ └─────────────────────┘ Run Time: real 0.138 user 0.046875 sys 0.031250 sqlite> ```