This document describes the xBestIndex method
of a {link: wiki?p=VirtualTables virtual table}
implementation.
If you have not already read about VirtualTables
you should do so before reading this page.
You might also want to read about the
{link: wiki?p=VirtualTableMethods other virtual table methods}
prior to perusing the following text.

_: *Note* The xBestIndex method is called when a statement is being prepared
(ie before sqlite3_step() is ever called).  This also means that if you
call sqlite3_reset() on a statement then xBestIndex will not be called again.
Consequently if you reuse statements or cache them, the index information
originally returned is used and not later updated.

The xBestIndex method has a prototype like this:

  int (*xBestIndex)(sqlite3_vtab *pVTab, sqlite3_index_info*);

The SQLite core communicates with the xBestIndex method
by filling in certain fields of the sqlite3_index_info
structure and passing a pointer to that structure into
xBestIndex as the second parameter.  The xBestIndex method
fills out other fields of this structure which forms the
reply.
The sqlite3_index_info structure looks like this:

  struct sqlite3_index_info {
    /* Inputs */
    const int nConstraint;     /* Number of entries in aConstraint */
    const struct sqlite3_index_constraint {
       int iColumn;              /* Column on left-hand side of constraint */
       unsigned char op;         /* Constraint operator */
       unsigned char usable;     /* True if this constraint is usable */
       int iTermOffset;          /* Used internally - xBestIndex should ignore */
    } *const aConstraint;      /* Table of WHERE clause constraints */
    const int nOrderBy;        /* Number of terms in the ORDER BY clause */
    const struct sqlite3_index_orderby {
       int iColumn;              /* Column number */
       unsigned char desc;       /* True for DESC.  False for ASC. */
    } *const aOrderBy;         /* The ORDER BY clause */

    /* Outputs */
    struct sqlite3_index_constraint_usage {
      int argvIndex;           /* if >0, constraint is part of argv to xFilter */
      unsigned char omit;      /* Do not code a test for this constraint */
    } *const aConstraintUsage;
    int idxNum;                /* Number used to identify the index */
    char *idxStr;              /* String, possibly obtained from sqlite3_malloc */
    int needToFreeIdxStr;      /* Free idxStr using sqlite3_free() if true */
    int orderByConsumed;       /* True if output is already ordered */
    double estimatedCost;      /* Estimated cost of using this index */
  };

In addition, there are some defined constants:

  #define SQLITE_INDEX_CONSTRAINT_EQ    2
  #define SQLITE_INDEX_CONSTRAINT_GT    4
  #define SQLITE_INDEX_CONSTRAINT_LE    8
  #define SQLITE_INDEX_CONSTRAINT_LT    16
  #define SQLITE_INDEX_CONSTRAINT_GE    32
  #define SQLITE_INDEX_CONSTRAINT_MATCH 64

The SQLite core calls the xBestIndex method when it is compiling a
query that involves a virtual table.  In other words,
SQLite calls this method when it is running sqlite3_prepare().
By calling this method, the SQLite core is saying to the
virtual table that it needs to access some subset of the
rows in the virtual table and it wants to know the most
efficient way to do that access.  The xBestIndex method replies
with information that the SQLite core can then use to
conduct an efficient search of the virtual table.

While compiling a single SQL query,
the SQLite core might call xBestIndex multiple times
with different settings in sqlite3_index_info.
The SQLite core will then select the combination
that appears to give the best performance.

*Inputs*

Before calling this method, the SQLite core initializes
an instance of the sqlite3_index_info structure with
information about the query that it is currently trying
to process.  This information derives mainly from
the WHERE clause and ORDER BY or GROUP BY clauses
of the query, but also from any ON or USING clauses
if the query is a join.  The information that the
SQLite core provides to the xBestIndex method is
held in the part of the structure that is marked
as "Inputs".  The "Outputs" section is initialized
to zero.

The main thing that the SQLite core is trying to
communicate to the virtual table is the constraints
that are available to limit the number of rows
that need to be searched.  The aConstraint[] array
contains one entry for each constraint.  There will
be exactly nConstraint entries in that array.

Each constraint will correspond to a term in the
WHERE clause or in a USING or ON clause that is
of the form

     column  OP  EXPR

Where "column" is a column in the virtual table,
OP is an operator like "=" or "<", and EXPR is
an arbitrary expression.  So, for example, if
the WHERE clause contained a term like this:

     a = 5

Then one of the constraints would be on the "a"
column with operator "=" and an expression of "5".
Constraints are not a literal representation of
the WHERE clause.  The query optimizer translates
the WHERE clause in order to extract as many
constraints as it can.  So, for example, if the
WHERE clause contained something like this:

     x BETWEEN 10 AND 100 AND 999>y

The query optimizer would translate this into
three separate constraints:

     x >= 10
     x <= 100
     y < 999

For each constraint, the aConstraint[].iColumn
field indicates which column appears on the
left-hand side of the constraint.  The first
column of the virtual table is column 0.  The
rowid of the virtual table is column -1.
The aConstraint[].op field indicates which
operator is used.  The SQLITE_INDEX_CONSTRAINT_*
constants map integer constants into operator
values.

The aConstraint[] array contains information about
all constraints that apply to the virtual table.
But some of the constraints might not be usable
because of the way tables are ordered in a join.
The xBestIndex method should therefore only consider
constraints that have a aConstraint[].usable flag
which is true.

In addition to WHERE clause constraints, the
SQLite core also tells the xBestIndex method about
the ORDER BY clause.  (In an aggregate query, the
SQLite core might put in GROUP BY clause information
in place of the ORDER BY clause information, but this
fact should not make any difference to the xBestIndex
method.)  If all terms of the ORDER BY clause are
columns in the virtual table, then nOrderBy will
be the number of terms in the ORDER BY clause
and the aOrderBy[] array will identify the column
for each term in the order by clause and whether or
not that column is ASC or DESC.

*Outputs*

Given all of the information above, the job of the
xBestIndex method it to figure out the best way to
search the virtual table.

The xBestIndex method fills
the idxNum and idxStr fields with information
that communicates an indexing strategy to the xFilter method.
The information in idxNum and idxStr is arbitrary as far as
the SQLite core is concerned.  The SQLite core just copies
the information through to the xFilter method.  Any
desired meaning can be assigned to idxNum and idxStr
as long as xBestIndex and xFilter agree on what that
meaning is.

The idxStr value can be a string obtained from
sqlite3_mprintf().  If this is the case, then the
needToFreeIdxStr flag should be set to true so that
the SQLite core will know to call sqlite3_free() on
that string when it has finished with it, and thus
avoid a memory leak.

If the virtual table will output rows in the order
specified by the ORDER BY clause, then the
orderByConsumed flag should be set to true.  If
the output is not automatically in the correct order
then orderByConsumed should be left in its default
false setting.  This will indicate to the SQLite core
that it will need to do a separate sorting pass over
the data after it comes out of the virtual table.

The estimatedCost field should be set to the estimated
number of disk access operations required to execute
this query against the virtual table.  The SQLite core
will often call xBestIndex multiple times with different
constraints, obtain multiple cost estimates, then choose
the query plan that gives the lowest estimate.

The aConstraintUsage[] array contains one element for
each of the nConstraint constraints in the inputs section
of the sqlite3_index_info structure.  The aConstraintUsage[]
array is used by xBestIndex to tell the core how it is
using the constraints.

The xBestIndex method may set aConstraintUsage[].argvIndex
entries to values greater than one.  Exactly one
entry should be set to 1, another to 2, another to 3,
and so forth up to as many or as few as the xBestIndex
method wants.  The EXPR of the corresponding constraints
will then be passed in as the argv[] parameters to xFilter.

For example, if the aConstraint[3].argvIndex is set to 1,
then when xFilter is called, the argv[0] passed to
xFilter will have the EXPR value of the aConstraint[3]
constraint.

By default, the SQLite core double checks all constraints
on each row of the virtual table that it receives.  If
such a check is redundant, the xBestFilter method can
suppress that check by setting aConstraintUsage[].omit.