I have an extremely large database (contacts has ~3 billion entries, people has ~280 million entries, and the other tables have a negligible number of entries). Most other queries I've run are really fast. However, I've encountered a more complicated query that's really slow. I'm wondering if there's any way to speed this up.

First of all, here is my schema:

CREATE TABLE activities (id INTEGER PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE contacts (
        id INTEGER PRIMARY KEY,
        person1_id INTEGER NOT NULL,
        person2_id INTEGER NOT NULL,
        duration REAL NOT NULL, -- hours
        activity_id INTEGER NOT NULL
    --  FOREIGN_KEY(person1_id) REFERENCES people(id),
    --  FOREIGN_KEY(person2_id) REFERENCES people(id)
    );
CREATE TABLE people (
        id INTEGER PRIMARY KEY,
        state_id INTEGER NOT NULL,
        county_id INTEGER NOT NULL,
        age INTEGER NOT NULL,
        gender TEXT NOT NULL, -- M or F
        income INTEGER NOT NULL
    --  FOREIGN_KEY(state_id) REFERENCES states(id)
    );
CREATE TABLE states (
        id INTEGER PRIMARY KEY,
        name TEXT NOT NULL,
        abbreviation TEXT NOT NULL
    );
CREATE INDEX activities_name_index on activities(name);
CREATE INDEX contacts_activity_id_index on contacts(activity_id);
CREATE INDEX contacts_duration_index on contacts(duration);
CREATE INDEX contacts_person1_id_index on contacts(person1_id);
CREATE INDEX contacts_person2_id_index on contacts(person2_id);
CREATE INDEX people_age_index on people(age);
CREATE INDEX people_county_id_index on people(county_id);
CREATE INDEX people_gender_index on people(gender);
CREATE INDEX people_income_index on people(income);
CREATE INDEX people_state_id_index on people(state_id);
CREATE INDEX states_abbreviation_index on states(abbreviation);
CREATE INDEX states_name_index on states(name);

Note that I've created an index on every column in the database. I don't care about the size of the database; speed is all I care about.

Here's an example of a query that, as expected, runs almost instantly:

SELECT count(*) FROM people, states WHERE people.state_id=states.id and states.abbreviation='IA';

Here's the troublesome query:

SELECT * FROM contacts WHERE rowid IN
    (SELECT contacts.rowid FROM contacts, people, states
        WHERE contacts.person1_id=people.id AND people.state_id=states.id AND states.name='Kansas'
            INTERSECT
    SELECT contacts.rowid FROM contacts, people, states
        WHERE contacts.person2_id=people.id AND people.state_id=states.id AND states.name='Missouri');

Now, what I think would happen is that each subquery would use each relevant index I've created to speed this up. However, when I show the query plan, I see this:

sqlite> EXPLAIN QUERY PLAN SELECT * FROM contacts WHERE rowid IN (SELECT contacts.rowid FROM contacts, people, states WHERE contacts.person1_id=people.id AND people.state_id=states.id AND states.name='Kansas' INTERSECT SELECT contacts.rowid FROM contacts, people, states WHERE contacts.person2_id=people.id AND people.state_id=states.id AND states.name='Missouri');
0|0|0|SEARCH TABLE contacts USING INTEGER PRIMARY KEY (rowid=?) (~25 rows)
0|0|0|EXECUTE LIST SUBQUERY 1
2|0|2|SEARCH TABLE states USING COVERING INDEX states_name_index (name=?) (~1 rows)
2|1|1|SEARCH TABLE people USING COVERING INDEX people_state_id_index (state_id=?) (~5569556 rows)
2|2|0|SEARCH TABLE contacts USING COVERING INDEX contacts_person1_id_index (person1_id=?) (~12 rows)
3|0|2|SEARCH TABLE states USING COVERING INDEX states_name_index (name=?) (~1 rows)
3|1|1|SEARCH TABLE people USING COVERING INDEX people_state_id_index (state_id=?) (~5569556 rows)
3|2|0|SEARCH TABLE contacts USING COVERING INDEX contacts_person2_id_index (person2_id=?) (~12 rows)
1|0|0|COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (INTERSECT)

In fact, if I show the query plan for the first query I posted, I get this:

sqlite> EXPLAIN QUERY PLAN SELECT count(*) FROM people, states WHERE people.state_id=states.id and states.abbreviation='IA';
0|0|1|SEARCH TABLE states USING COVERING INDEX states_abbreviation_index (abbreviation=?) (~1 rows)
0|1|0|SEARCH TABLE people USING COVERING INDEX people_state_id_index (state_id=?) (~5569556 rows)

Why is SQLite using covering indices instead of the indices I created? Shouldn't the search in the people table be able to happen in log(n) time given state_id which in turn is found in log(n) time?