Documentation Source Text

  SELECT name FROM people WHERE height>=180;
}

PARAGRAPH {
  Because the left-most column of the index does not appear in the
  WHERE clause of the query, one is tempted to conclude that the
  index is not usable here.  But SQLite is able to use the index.
  Conceptually, what SQLite does in this case is transform the
  query into something like the following:
}

CODE {
  SELECT name FROM people
   WHERE role IN (SELECT DISTINCT role FROM people)
     AND height>=180;
}
................................................................................
CODE {
  SELECT name FROM people WHERE role='teacher' AND height>=180
  UNION ALL
  SELECT name FROM people WHERE role='student' AND height>=180;
}

PARAGRAPH {
  The key word above is "conceptually".  SQLite does not really transform
  the query.  But the transformations help to convey a sense of how
  SQLite goes about running the query.  The plan goes like this:
  SQLite locates the first possible value for "role", which it
  can do by rewinding the "people_idx1" index to the beginning and reading
  the first record.  SQLite stores this first "role" value in an
  internal variable that we will here call "$role".  Then SQLite
  runs a query like: "SELECT name FROM people WHERE role=$role AND height>=180".
  This query has an equality constraint on the left-most column of the
  index and so the index can be used to resolve that query.  Once
  that query is finished, SQLite then uses the "people_idx1" index to
  locate the next value of the "role" column, using code that is logically
  similar to "SELECT role FROM people WHERE role>$role".  This new "role"
  value overwrites the $role variable, and the process repeats until all
  possible values for "role" have been examined.
}

PARAGRAPH {
  We call this kind of index usage a "skip-scan" because the database
  engine is basically doing a full scan of the index but it optimizes the
  scan (making it less than "full") by occasionally jumping ahead to the
  next candidate value.
}

PARAGRAPH {
  SQLite might use a skip-scan on an index if it knows that the first
  one or more columns contain only a small number of distinct values.
  If there are too many
  distinct values in the left-most columns of the index, then it would
  be faster to do an ordinary full table scan, and so SQLite will choose
  that option instead.

}

PARAGRAPH {
  The only way that SQLite can know that the left-most columns of an index
  have few distinct values is if the [ANALYZE] command has been run
  on the database.
  Without the results of ANALYZE, SQLite has to guess at the "shape" of
  the data in the table, and the default guess is that there are many
  distinct values for the left-most column of an index, far too many
  to make a skip-scan practical.  Hence, a skip-scan is never used on a

  database that has not been analyzed.
}

HEADING 1 {Joins} joins

PARAGRAPH {
  ^The ON and USING clauses of an inner join are converted into additional
  terms of the WHERE clause prior to WHERE clause analysis described

  SELECT name FROM people WHERE height>=180;
}

PARAGRAPH {
  Because the left-most column of the index does not appear in the
  WHERE clause of the query, one is tempted to conclude that the
  index is not usable here.  But SQLite is able to use the index.
  Conceptually, SQLite uses the index as if the query were more
  like the following:
}

CODE {
  SELECT name FROM people
   WHERE role IN (SELECT DISTINCT role FROM people)
     AND height>=180;
}
................................................................................
CODE {
  SELECT name FROM people WHERE role='teacher' AND height>=180
  UNION ALL
  SELECT name FROM people WHERE role='student' AND height>=180;
}

PARAGRAPH {
  The alternative query formulations shown above are conceptual only.
  SQLite does not really transform the query. 
  The actual query plan is like this:
  SQLite locates the first possible value for "role", which it
  can do by rewinding the "people_idx1" index to the beginning and reading
  the first record.  SQLite stores this first "role" value in an
  internal variable that we will here call "$role".  Then SQLite
  runs a query like: "SELECT name FROM people WHERE role=$role AND height>=180".
  This query has an equality constraint on the left-most column of the
  index and so the index can be used to resolve that query.  Once
  that query is finished, SQLite then uses the "people_idx1" index to
  locate the next value of the "role" column, using code that is logically
  similar to "SELECT role FROM people WHERE role>$role LIMIT 1".
  This new "role" value overwrites the $role variable, and the process
  repeats until all possible values for "role" have been examined.
}

PARAGRAPH {
  We call this kind of index usage a "skip-scan" because the database
  engine is basically doing a full scan of the index but it optimizes the
  scan (making it less than "full") by occasionally skipping ahead to the
  next candidate value.
}

PARAGRAPH {
  SQLite might use a skip-scan on an index if it knows that the first
  one or more columns contain many duplication values.
  If there are too few duplicates
  in the left-most columns of the index, then it would
  be faster to simply step ahead to the next value, and thus do
  a full table scan, than to do a binary search on an index to locate
  the next left-column value.
}

PARAGRAPH {
  The only way that SQLite can know that the left-most columns of an index
  have many duplicate is if the [ANALYZE] command has been run
  on the database.
  Without the results of ANALYZE, SQLite has to guess at the "shape" of
  the data in the table, and the default guess is that there are an average
  of 10 duplicates for every value in the left-most column of the index.
  But skip-scan only becomes profitable (it only gets to be faster than
  a full table scan) when the number of duplicates is about 18 or more.
  Hence, a skip-scan is never used on a database that has not been analyzed.
}

HEADING 1 {Joins} joins

PARAGRAPH {
  ^The ON and USING clauses of an inner join are converted into additional
  terms of the WHERE clause prior to WHERE clause analysis described