SQLite Forum

Query planner fails to use obvious index
SQLite is gives consideration to two algorithms for this query:

  1.  Scan the "test" table (which is already in "id" order) looking
      for the first entry for which key_id>=1.  The scan stops as soon
      as any entry with key_id>=1 is seen because it knows that entry will have
      the smallest possible "id" value.

  2.  Do a search for the first entry in the test_key_idx table with key_id>=1
      and then scan that entry and all subsequent entries, looking for the
      smallest "id" value.  All index entries with key_id>=1 must be scanned
      in this case since we never know which one will have the smallest value
      for "id".

The choice of algorithm is not obvious here.  Algorithm 1 will work best
if most entries have key_id>=1 and algorithm 2 will work best if most entries
have key_id<1.  The query planner does not normally know what the distribution
of key_id values is, so it does not normally have a good way to decide which
algorithm is best.

The "normally" in the previous sentence means "unless you compile with
SQLITE_ENABLE_STAT4 and run ANALYZE". If you do compile with SQLITE_ENABLE_STAT4
and run ANALYZE prior to your query, then the query planner does have some
notion of the distribution of key_id values, and it does appear to choose
the better algorithm depending on that distribution.