-
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.