First, thank you all for the answers.
UNIQUE(col1, col4, col5, col2),
Adding this would surely make the query run faster -- provided that SQLite chooses the right index. But I also use the UNIQUE(col1, col4, col5) constraint to ensure the uniqueness of these three columns. So instead I should have both UNIQUE(col1, col4, col5), UNIQUE(col1, col4, col5, col2), but this would waste my disk space. I am wondering how can MySQL 4.1 be so fast compared to SQLite 3? MySQL answers my query in 0.02 seconds, and SQLite answers in more than 28 seconds. I guess that MySQL doesn't do any magic either (i.e. it operates in O(Klog N) time, which appears to be just 0.02 seconds), but MySQL recognises that it should use the UNIQUE(col1, col4, col5) index, while SQLite poorly chooses some other index, maybe the PRIMARY KEY(col1, col2, col3, col4, col5), which is just wrong. Can someone confirm that the SQLite is using the wrong index? Is it possible to deterministically rewrite the query to force SQLite use the right index?