sqlite - very slow performance of WHERE EXISTS without index on EXISTS
The unique index on tbl2.col2 isn't adding any new information that a full table scan wouldn't give it


That is true; the question is, how many table scans do you think are there?

SQLite documentation will tell you that its optimizer is capable of only nested-loop joins, so regardless of whether it is smart enough to rewrite the EXISTS subquery into a join1 or will naively evaluate the predicate for each row of the driving table, you will still end up doing 4.5 million table scans, each retrieving on average 50K rows.

In the presence of a unique index on tbl2.col2 this turns into 4.5 million index seeks using the B-tree, each requiring only 2-3 logical I/O operations and retrieving exactly one row, which is 11 orders of magnitude less I/O.



1 - Which would not make any difference anyway, since it would then rewrite that join into a combination of simple predicates against the two tables.