| Index: third_party/sqlite/src/src/where.c
|
| diff --git a/third_party/sqlite/src/src/where.c b/third_party/sqlite/src/src/where.c
|
| new file mode 100644
|
| index 0000000000000000000000000000000000000000..cf30d94d671bb81ef361cb6ac5b7a1aae392f395
|
| --- /dev/null
|
| +++ b/third_party/sqlite/src/src/where.c
|
| @@ -0,0 +1,4985 @@
|
| +/*
|
| +** 2001 September 15
|
| +**
|
| +** The author disclaims copyright to this source code. In place of
|
| +** a legal notice, here is a blessing:
|
| +**
|
| +** May you do good and not evil.
|
| +** May you find forgiveness for yourself and forgive others.
|
| +** May you share freely, never taking more than you give.
|
| +**
|
| +*************************************************************************
|
| +** This module contains C code that generates VDBE code used to process
|
| +** the WHERE clause of SQL statements. This module is responsible for
|
| +** generating the code that loops through a table looking for applicable
|
| +** rows. Indices are selected and used to speed the search when doing
|
| +** so is applicable. Because this module is responsible for selecting
|
| +** indices, you might also think of this module as the "query optimizer".
|
| +*/
|
| +#include "sqliteInt.h"
|
| +
|
| +
|
| +/*
|
| +** Trace output macros
|
| +*/
|
| +#if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
|
| +int sqlite3WhereTrace = 0;
|
| +#endif
|
| +#if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
|
| +# define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X
|
| +#else
|
| +# define WHERETRACE(X)
|
| +#endif
|
| +
|
| +/* Forward reference
|
| +*/
|
| +typedef struct WhereClause WhereClause;
|
| +typedef struct WhereMaskSet WhereMaskSet;
|
| +typedef struct WhereOrInfo WhereOrInfo;
|
| +typedef struct WhereAndInfo WhereAndInfo;
|
| +typedef struct WhereCost WhereCost;
|
| +
|
| +/*
|
| +** The query generator uses an array of instances of this structure to
|
| +** help it analyze the subexpressions of the WHERE clause. Each WHERE
|
| +** clause subexpression is separated from the others by AND operators,
|
| +** usually, or sometimes subexpressions separated by OR.
|
| +**
|
| +** All WhereTerms are collected into a single WhereClause structure.
|
| +** The following identity holds:
|
| +**
|
| +** WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm
|
| +**
|
| +** When a term is of the form:
|
| +**
|
| +** X <op> <expr>
|
| +**
|
| +** where X is a column name and <op> is one of certain operators,
|
| +** then WhereTerm.leftCursor and WhereTerm.u.leftColumn record the
|
| +** cursor number and column number for X. WhereTerm.eOperator records
|
| +** the <op> using a bitmask encoding defined by WO_xxx below. The
|
| +** use of a bitmask encoding for the operator allows us to search
|
| +** quickly for terms that match any of several different operators.
|
| +**
|
| +** A WhereTerm might also be two or more subterms connected by OR:
|
| +**
|
| +** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
|
| +**
|
| +** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
|
| +** and the WhereTerm.u.pOrInfo field points to auxiliary information that
|
| +** is collected about the
|
| +**
|
| +** If a term in the WHERE clause does not match either of the two previous
|
| +** categories, then eOperator==0. The WhereTerm.pExpr field is still set
|
| +** to the original subexpression content and wtFlags is set up appropriately
|
| +** but no other fields in the WhereTerm object are meaningful.
|
| +**
|
| +** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
|
| +** but they do so indirectly. A single WhereMaskSet structure translates
|
| +** cursor number into bits and the translated bit is stored in the prereq
|
| +** fields. The translation is used in order to maximize the number of
|
| +** bits that will fit in a Bitmask. The VDBE cursor numbers might be
|
| +** spread out over the non-negative integers. For example, the cursor
|
| +** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet
|
| +** translates these sparse cursor numbers into consecutive integers
|
| +** beginning with 0 in order to make the best possible use of the available
|
| +** bits in the Bitmask. So, in the example above, the cursor numbers
|
| +** would be mapped into integers 0 through 7.
|
| +**
|
| +** The number of terms in a join is limited by the number of bits
|
| +** in prereqRight and prereqAll. The default is 64 bits, hence SQLite
|
| +** is only able to process joins with 64 or fewer tables.
|
| +*/
|
| +typedef struct WhereTerm WhereTerm;
|
| +struct WhereTerm {
|
| + Expr *pExpr; /* Pointer to the subexpression that is this term */
|
| + int iParent; /* Disable pWC->a[iParent] when this term disabled */
|
| + int leftCursor; /* Cursor number of X in "X <op> <expr>" */
|
| + union {
|
| + int leftColumn; /* Column number of X in "X <op> <expr>" */
|
| + WhereOrInfo *pOrInfo; /* Extra information if eOperator==WO_OR */
|
| + WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
|
| + } u;
|
| + u16 eOperator; /* A WO_xx value describing <op> */
|
| + u8 wtFlags; /* TERM_xxx bit flags. See below */
|
| + u8 nChild; /* Number of children that must disable us */
|
| + WhereClause *pWC; /* The clause this term is part of */
|
| + Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
|
| + Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */
|
| +};
|
| +
|
| +/*
|
| +** Allowed values of WhereTerm.wtFlags
|
| +*/
|
| +#define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */
|
| +#define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
|
| +#define TERM_CODED 0x04 /* This term is already coded */
|
| +#define TERM_COPIED 0x08 /* Has a child */
|
| +#define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
|
| +#define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
|
| +#define TERM_OR_OK 0x40 /* Used during OR-clause processing */
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +# define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
|
| +#else
|
| +# define TERM_VNULL 0x00 /* Disabled if not using stat2 */
|
| +#endif
|
| +
|
| +/*
|
| +** An instance of the following structure holds all information about a
|
| +** WHERE clause. Mostly this is a container for one or more WhereTerms.
|
| +*/
|
| +struct WhereClause {
|
| + Parse *pParse; /* The parser context */
|
| + WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */
|
| + Bitmask vmask; /* Bitmask identifying virtual table cursors */
|
| + u8 op; /* Split operator. TK_AND or TK_OR */
|
| + int nTerm; /* Number of terms */
|
| + int nSlot; /* Number of entries in a[] */
|
| + WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
|
| +#if defined(SQLITE_SMALL_STACK)
|
| + WhereTerm aStatic[1]; /* Initial static space for a[] */
|
| +#else
|
| + WhereTerm aStatic[8]; /* Initial static space for a[] */
|
| +#endif
|
| +};
|
| +
|
| +/*
|
| +** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
|
| +** a dynamically allocated instance of the following structure.
|
| +*/
|
| +struct WhereOrInfo {
|
| + WhereClause wc; /* Decomposition into subterms */
|
| + Bitmask indexable; /* Bitmask of all indexable tables in the clause */
|
| +};
|
| +
|
| +/*
|
| +** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
|
| +** a dynamically allocated instance of the following structure.
|
| +*/
|
| +struct WhereAndInfo {
|
| + WhereClause wc; /* The subexpression broken out */
|
| +};
|
| +
|
| +/*
|
| +** An instance of the following structure keeps track of a mapping
|
| +** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
|
| +**
|
| +** The VDBE cursor numbers are small integers contained in
|
| +** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
|
| +** clause, the cursor numbers might not begin with 0 and they might
|
| +** contain gaps in the numbering sequence. But we want to make maximum
|
| +** use of the bits in our bitmasks. This structure provides a mapping
|
| +** from the sparse cursor numbers into consecutive integers beginning
|
| +** with 0.
|
| +**
|
| +** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
|
| +** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
|
| +**
|
| +** For example, if the WHERE clause expression used these VDBE
|
| +** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
|
| +** would map those cursor numbers into bits 0 through 5.
|
| +**
|
| +** Note that the mapping is not necessarily ordered. In the example
|
| +** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
|
| +** 57->5, 73->4. Or one of 719 other combinations might be used. It
|
| +** does not really matter. What is important is that sparse cursor
|
| +** numbers all get mapped into bit numbers that begin with 0 and contain
|
| +** no gaps.
|
| +*/
|
| +struct WhereMaskSet {
|
| + int n; /* Number of assigned cursor values */
|
| + int ix[BMS]; /* Cursor assigned to each bit */
|
| +};
|
| +
|
| +/*
|
| +** A WhereCost object records a lookup strategy and the estimated
|
| +** cost of pursuing that strategy.
|
| +*/
|
| +struct WhereCost {
|
| + WherePlan plan; /* The lookup strategy */
|
| + double rCost; /* Overall cost of pursuing this search strategy */
|
| + Bitmask used; /* Bitmask of cursors used by this plan */
|
| +};
|
| +
|
| +/*
|
| +** Bitmasks for the operators that indices are able to exploit. An
|
| +** OR-ed combination of these values can be used when searching for
|
| +** terms in the where clause.
|
| +*/
|
| +#define WO_IN 0x001
|
| +#define WO_EQ 0x002
|
| +#define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
|
| +#define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
|
| +#define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
|
| +#define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
|
| +#define WO_MATCH 0x040
|
| +#define WO_ISNULL 0x080
|
| +#define WO_OR 0x100 /* Two or more OR-connected terms */
|
| +#define WO_AND 0x200 /* Two or more AND-connected terms */
|
| +#define WO_NOOP 0x800 /* This term does not restrict search space */
|
| +
|
| +#define WO_ALL 0xfff /* Mask of all possible WO_* values */
|
| +#define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
|
| +
|
| +/*
|
| +** Value for wsFlags returned by bestIndex() and stored in
|
| +** WhereLevel.wsFlags. These flags determine which search
|
| +** strategies are appropriate.
|
| +**
|
| +** The least significant 12 bits is reserved as a mask for WO_ values above.
|
| +** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
|
| +** But if the table is the right table of a left join, WhereLevel.wsFlags
|
| +** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as
|
| +** the "op" parameter to findTerm when we are resolving equality constraints.
|
| +** ISNULL constraints will then not be used on the right table of a left
|
| +** join. Tickets #2177 and #2189.
|
| +*/
|
| +#define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */
|
| +#define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */
|
| +#define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */
|
| +#define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */
|
| +#define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */
|
| +#define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */
|
| +#define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */
|
| +#define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */
|
| +#define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */
|
| +#define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */
|
| +#define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */
|
| +#define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */
|
| +#define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */
|
| +#define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */
|
| +#define WHERE_REVERSE 0x02000000 /* Scan in reverse order */
|
| +#define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */
|
| +#define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */
|
| +#define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */
|
| +#define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */
|
| +
|
| +/*
|
| +** Initialize a preallocated WhereClause structure.
|
| +*/
|
| +static void whereClauseInit(
|
| + WhereClause *pWC, /* The WhereClause to be initialized */
|
| + Parse *pParse, /* The parsing context */
|
| + WhereMaskSet *pMaskSet /* Mapping from table cursor numbers to bitmasks */
|
| +){
|
| + pWC->pParse = pParse;
|
| + pWC->pMaskSet = pMaskSet;
|
| + pWC->nTerm = 0;
|
| + pWC->nSlot = ArraySize(pWC->aStatic);
|
| + pWC->a = pWC->aStatic;
|
| + pWC->vmask = 0;
|
| +}
|
| +
|
| +/* Forward reference */
|
| +static void whereClauseClear(WhereClause*);
|
| +
|
| +/*
|
| +** Deallocate all memory associated with a WhereOrInfo object.
|
| +*/
|
| +static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
|
| + whereClauseClear(&p->wc);
|
| + sqlite3DbFree(db, p);
|
| +}
|
| +
|
| +/*
|
| +** Deallocate all memory associated with a WhereAndInfo object.
|
| +*/
|
| +static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
|
| + whereClauseClear(&p->wc);
|
| + sqlite3DbFree(db, p);
|
| +}
|
| +
|
| +/*
|
| +** Deallocate a WhereClause structure. The WhereClause structure
|
| +** itself is not freed. This routine is the inverse of whereClauseInit().
|
| +*/
|
| +static void whereClauseClear(WhereClause *pWC){
|
| + int i;
|
| + WhereTerm *a;
|
| + sqlite3 *db = pWC->pParse->db;
|
| + for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
|
| + if( a->wtFlags & TERM_DYNAMIC ){
|
| + sqlite3ExprDelete(db, a->pExpr);
|
| + }
|
| + if( a->wtFlags & TERM_ORINFO ){
|
| + whereOrInfoDelete(db, a->u.pOrInfo);
|
| + }else if( a->wtFlags & TERM_ANDINFO ){
|
| + whereAndInfoDelete(db, a->u.pAndInfo);
|
| + }
|
| + }
|
| + if( pWC->a!=pWC->aStatic ){
|
| + sqlite3DbFree(db, pWC->a);
|
| + }
|
| +}
|
| +
|
| +/*
|
| +** Add a single new WhereTerm entry to the WhereClause object pWC.
|
| +** The new WhereTerm object is constructed from Expr p and with wtFlags.
|
| +** The index in pWC->a[] of the new WhereTerm is returned on success.
|
| +** 0 is returned if the new WhereTerm could not be added due to a memory
|
| +** allocation error. The memory allocation failure will be recorded in
|
| +** the db->mallocFailed flag so that higher-level functions can detect it.
|
| +**
|
| +** This routine will increase the size of the pWC->a[] array as necessary.
|
| +**
|
| +** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
|
| +** for freeing the expression p is assumed by the WhereClause object pWC.
|
| +** This is true even if this routine fails to allocate a new WhereTerm.
|
| +**
|
| +** WARNING: This routine might reallocate the space used to store
|
| +** WhereTerms. All pointers to WhereTerms should be invalidated after
|
| +** calling this routine. Such pointers may be reinitialized by referencing
|
| +** the pWC->a[] array.
|
| +*/
|
| +static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
|
| + WhereTerm *pTerm;
|
| + int idx;
|
| + testcase( wtFlags & TERM_VIRTUAL ); /* EV: R-00211-15100 */
|
| + if( pWC->nTerm>=pWC->nSlot ){
|
| + WhereTerm *pOld = pWC->a;
|
| + sqlite3 *db = pWC->pParse->db;
|
| + pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
|
| + if( pWC->a==0 ){
|
| + if( wtFlags & TERM_DYNAMIC ){
|
| + sqlite3ExprDelete(db, p);
|
| + }
|
| + pWC->a = pOld;
|
| + return 0;
|
| + }
|
| + memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
|
| + if( pOld!=pWC->aStatic ){
|
| + sqlite3DbFree(db, pOld);
|
| + }
|
| + pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
|
| + }
|
| + pTerm = &pWC->a[idx = pWC->nTerm++];
|
| + pTerm->pExpr = p;
|
| + pTerm->wtFlags = wtFlags;
|
| + pTerm->pWC = pWC;
|
| + pTerm->iParent = -1;
|
| + return idx;
|
| +}
|
| +
|
| +/*
|
| +** This routine identifies subexpressions in the WHERE clause where
|
| +** each subexpression is separated by the AND operator or some other
|
| +** operator specified in the op parameter. The WhereClause structure
|
| +** is filled with pointers to subexpressions. For example:
|
| +**
|
| +** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
|
| +** \________/ \_______________/ \________________/
|
| +** slot[0] slot[1] slot[2]
|
| +**
|
| +** The original WHERE clause in pExpr is unaltered. All this routine
|
| +** does is make slot[] entries point to substructure within pExpr.
|
| +**
|
| +** In the previous sentence and in the diagram, "slot[]" refers to
|
| +** the WhereClause.a[] array. The slot[] array grows as needed to contain
|
| +** all terms of the WHERE clause.
|
| +*/
|
| +static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
|
| + pWC->op = (u8)op;
|
| + if( pExpr==0 ) return;
|
| + if( pExpr->op!=op ){
|
| + whereClauseInsert(pWC, pExpr, 0);
|
| + }else{
|
| + whereSplit(pWC, pExpr->pLeft, op);
|
| + whereSplit(pWC, pExpr->pRight, op);
|
| + }
|
| +}
|
| +
|
| +/*
|
| +** Initialize an expression mask set (a WhereMaskSet object)
|
| +*/
|
| +#define initMaskSet(P) memset(P, 0, sizeof(*P))
|
| +
|
| +/*
|
| +** Return the bitmask for the given cursor number. Return 0 if
|
| +** iCursor is not in the set.
|
| +*/
|
| +static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
|
| + int i;
|
| + assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 );
|
| + for(i=0; i<pMaskSet->n; i++){
|
| + if( pMaskSet->ix[i]==iCursor ){
|
| + return ((Bitmask)1)<<i;
|
| + }
|
| + }
|
| + return 0;
|
| +}
|
| +
|
| +/*
|
| +** Create a new mask for cursor iCursor.
|
| +**
|
| +** There is one cursor per table in the FROM clause. The number of
|
| +** tables in the FROM clause is limited by a test early in the
|
| +** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
|
| +** array will never overflow.
|
| +*/
|
| +static void createMask(WhereMaskSet *pMaskSet, int iCursor){
|
| + assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
|
| + pMaskSet->ix[pMaskSet->n++] = iCursor;
|
| +}
|
| +
|
| +/*
|
| +** This routine walks (recursively) an expression tree and generates
|
| +** a bitmask indicating which tables are used in that expression
|
| +** tree.
|
| +**
|
| +** In order for this routine to work, the calling function must have
|
| +** previously invoked sqlite3ResolveExprNames() on the expression. See
|
| +** the header comment on that routine for additional information.
|
| +** The sqlite3ResolveExprNames() routines looks for column names and
|
| +** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
|
| +** the VDBE cursor number of the table. This routine just has to
|
| +** translate the cursor numbers into bitmask values and OR all
|
| +** the bitmasks together.
|
| +*/
|
| +static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
|
| +static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
|
| +static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
|
| + Bitmask mask = 0;
|
| + if( p==0 ) return 0;
|
| + if( p->op==TK_COLUMN ){
|
| + mask = getMask(pMaskSet, p->iTable);
|
| + return mask;
|
| + }
|
| + mask = exprTableUsage(pMaskSet, p->pRight);
|
| + mask |= exprTableUsage(pMaskSet, p->pLeft);
|
| + if( ExprHasProperty(p, EP_xIsSelect) ){
|
| + mask |= exprSelectTableUsage(pMaskSet, p->x.pSelect);
|
| + }else{
|
| + mask |= exprListTableUsage(pMaskSet, p->x.pList);
|
| + }
|
| + return mask;
|
| +}
|
| +static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
|
| + int i;
|
| + Bitmask mask = 0;
|
| + if( pList ){
|
| + for(i=0; i<pList->nExpr; i++){
|
| + mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
|
| + }
|
| + }
|
| + return mask;
|
| +}
|
| +static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
|
| + Bitmask mask = 0;
|
| + while( pS ){
|
| + mask |= exprListTableUsage(pMaskSet, pS->pEList);
|
| + mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
|
| + mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
|
| + mask |= exprTableUsage(pMaskSet, pS->pWhere);
|
| + mask |= exprTableUsage(pMaskSet, pS->pHaving);
|
| + pS = pS->pPrior;
|
| + }
|
| + return mask;
|
| +}
|
| +
|
| +/*
|
| +** Return TRUE if the given operator is one of the operators that is
|
| +** allowed for an indexable WHERE clause term. The allowed operators are
|
| +** "=", "<", ">", "<=", ">=", and "IN".
|
| +**
|
| +** IMPLEMENTATION-OF: R-59926-26393 To be usable by an index a term must be
|
| +** of one of the following forms: column = expression column > expression
|
| +** column >= expression column < expression column <= expression
|
| +** expression = column expression > column expression >= column
|
| +** expression < column expression <= column column IN
|
| +** (expression-list) column IN (subquery) column IS NULL
|
| +*/
|
| +static int allowedOp(int op){
|
| + assert( TK_GT>TK_EQ && TK_GT<TK_GE );
|
| + assert( TK_LT>TK_EQ && TK_LT<TK_GE );
|
| + assert( TK_LE>TK_EQ && TK_LE<TK_GE );
|
| + assert( TK_GE==TK_EQ+4 );
|
| + return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
|
| +}
|
| +
|
| +/*
|
| +** Swap two objects of type TYPE.
|
| +*/
|
| +#define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
|
| +
|
| +/*
|
| +** Commute a comparison operator. Expressions of the form "X op Y"
|
| +** are converted into "Y op X".
|
| +**
|
| +** If a collation sequence is associated with either the left or right
|
| +** side of the comparison, it remains associated with the same side after
|
| +** the commutation. So "Y collate NOCASE op X" becomes
|
| +** "X collate NOCASE op Y". This is because any collation sequence on
|
| +** the left hand side of a comparison overrides any collation sequence
|
| +** attached to the right. For the same reason the EP_ExpCollate flag
|
| +** is not commuted.
|
| +*/
|
| +static void exprCommute(Parse *pParse, Expr *pExpr){
|
| + u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
|
| + u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
|
| + assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
|
| + pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
|
| + pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
|
| + SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
|
| + pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
|
| + pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
|
| + SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
|
| + if( pExpr->op>=TK_GT ){
|
| + assert( TK_LT==TK_GT+2 );
|
| + assert( TK_GE==TK_LE+2 );
|
| + assert( TK_GT>TK_EQ );
|
| + assert( TK_GT<TK_LE );
|
| + assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
|
| + pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
|
| + }
|
| +}
|
| +
|
| +/*
|
| +** Translate from TK_xx operator to WO_xx bitmask.
|
| +*/
|
| +static u16 operatorMask(int op){
|
| + u16 c;
|
| + assert( allowedOp(op) );
|
| + if( op==TK_IN ){
|
| + c = WO_IN;
|
| + }else if( op==TK_ISNULL ){
|
| + c = WO_ISNULL;
|
| + }else{
|
| + assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
|
| + c = (u16)(WO_EQ<<(op-TK_EQ));
|
| + }
|
| + assert( op!=TK_ISNULL || c==WO_ISNULL );
|
| + assert( op!=TK_IN || c==WO_IN );
|
| + assert( op!=TK_EQ || c==WO_EQ );
|
| + assert( op!=TK_LT || c==WO_LT );
|
| + assert( op!=TK_LE || c==WO_LE );
|
| + assert( op!=TK_GT || c==WO_GT );
|
| + assert( op!=TK_GE || c==WO_GE );
|
| + return c;
|
| +}
|
| +
|
| +/*
|
| +** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
|
| +** where X is a reference to the iColumn of table iCur and <op> is one of
|
| +** the WO_xx operator codes specified by the op parameter.
|
| +** Return a pointer to the term. Return 0 if not found.
|
| +*/
|
| +static WhereTerm *findTerm(
|
| + WhereClause *pWC, /* The WHERE clause to be searched */
|
| + int iCur, /* Cursor number of LHS */
|
| + int iColumn, /* Column number of LHS */
|
| + Bitmask notReady, /* RHS must not overlap with this mask */
|
| + u32 op, /* Mask of WO_xx values describing operator */
|
| + Index *pIdx /* Must be compatible with this index, if not NULL */
|
| +){
|
| + WhereTerm *pTerm;
|
| + int k;
|
| + assert( iCur>=0 );
|
| + op &= WO_ALL;
|
| + for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
|
| + if( pTerm->leftCursor==iCur
|
| + && (pTerm->prereqRight & notReady)==0
|
| + && pTerm->u.leftColumn==iColumn
|
| + && (pTerm->eOperator & op)!=0
|
| + ){
|
| + if( pIdx && pTerm->eOperator!=WO_ISNULL ){
|
| + Expr *pX = pTerm->pExpr;
|
| + CollSeq *pColl;
|
| + char idxaff;
|
| + int j;
|
| + Parse *pParse = pWC->pParse;
|
| +
|
| + idxaff = pIdx->pTable->aCol[iColumn].affinity;
|
| + if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
|
| +
|
| + /* Figure out the collation sequence required from an index for
|
| + ** it to be useful for optimising expression pX. Store this
|
| + ** value in variable pColl.
|
| + */
|
| + assert(pX->pLeft);
|
| + pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
|
| + assert(pColl || pParse->nErr);
|
| +
|
| + for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
|
| + if( NEVER(j>=pIdx->nColumn) ) return 0;
|
| + }
|
| + if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
|
| + }
|
| + return pTerm;
|
| + }
|
| + }
|
| + return 0;
|
| +}
|
| +
|
| +/* Forward reference */
|
| +static void exprAnalyze(SrcList*, WhereClause*, int);
|
| +
|
| +/*
|
| +** Call exprAnalyze on all terms in a WHERE clause.
|
| +**
|
| +**
|
| +*/
|
| +static void exprAnalyzeAll(
|
| + SrcList *pTabList, /* the FROM clause */
|
| + WhereClause *pWC /* the WHERE clause to be analyzed */
|
| +){
|
| + int i;
|
| + for(i=pWC->nTerm-1; i>=0; i--){
|
| + exprAnalyze(pTabList, pWC, i);
|
| + }
|
| +}
|
| +
|
| +#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
|
| +/*
|
| +** Check to see if the given expression is a LIKE or GLOB operator that
|
| +** can be optimized using inequality constraints. Return TRUE if it is
|
| +** so and false if not.
|
| +**
|
| +** In order for the operator to be optimizible, the RHS must be a string
|
| +** literal that does not begin with a wildcard.
|
| +*/
|
| +static int isLikeOrGlob(
|
| + Parse *pParse, /* Parsing and code generating context */
|
| + Expr *pExpr, /* Test this expression */
|
| + Expr **ppPrefix, /* Pointer to TK_STRING expression with pattern prefix */
|
| + int *pisComplete, /* True if the only wildcard is % in the last character */
|
| + int *pnoCase /* True if uppercase is equivalent to lowercase */
|
| +){
|
| + const char *z = 0; /* String on RHS of LIKE operator */
|
| + Expr *pRight, *pLeft; /* Right and left size of LIKE operator */
|
| + ExprList *pList; /* List of operands to the LIKE operator */
|
| + int c; /* One character in z[] */
|
| + int cnt; /* Number of non-wildcard prefix characters */
|
| + char wc[3]; /* Wildcard characters */
|
| + sqlite3 *db = pParse->db; /* Database connection */
|
| + sqlite3_value *pVal = 0;
|
| + int op; /* Opcode of pRight */
|
| +
|
| + if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
|
| + return 0;
|
| + }
|
| +#ifdef SQLITE_EBCDIC
|
| + if( *pnoCase ) return 0;
|
| +#endif
|
| + pList = pExpr->x.pList;
|
| + pLeft = pList->a[1].pExpr;
|
| + if( pLeft->op!=TK_COLUMN || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ){
|
| + /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
|
| + ** be the name of an indexed column with TEXT affinity. */
|
| + return 0;
|
| + }
|
| + assert( pLeft->iColumn!=(-1) ); /* Because IPK never has AFF_TEXT */
|
| +
|
| + pRight = pList->a[0].pExpr;
|
| + op = pRight->op;
|
| + if( op==TK_REGISTER ){
|
| + op = pRight->op2;
|
| + }
|
| + if( op==TK_VARIABLE ){
|
| + Vdbe *pReprepare = pParse->pReprepare;
|
| + int iCol = pRight->iColumn;
|
| + pVal = sqlite3VdbeGetValue(pReprepare, iCol, SQLITE_AFF_NONE);
|
| + if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){
|
| + z = (char *)sqlite3_value_text(pVal);
|
| + }
|
| + sqlite3VdbeSetVarmask(pParse->pVdbe, iCol); /* IMP: R-23257-02778 */
|
| + assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );
|
| + }else if( op==TK_STRING ){
|
| + z = pRight->u.zToken;
|
| + }
|
| + if( z ){
|
| + cnt = 0;
|
| + while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
|
| + cnt++;
|
| + }
|
| + if( cnt!=0 && 255!=(u8)z[cnt-1] ){
|
| + Expr *pPrefix;
|
| + *pisComplete = c==wc[0] && z[cnt+1]==0;
|
| + pPrefix = sqlite3Expr(db, TK_STRING, z);
|
| + if( pPrefix ) pPrefix->u.zToken[cnt] = 0;
|
| + *ppPrefix = pPrefix;
|
| + if( op==TK_VARIABLE ){
|
| + Vdbe *v = pParse->pVdbe;
|
| + sqlite3VdbeSetVarmask(v, pRight->iColumn); /* IMP: R-23257-02778 */
|
| + if( *pisComplete && pRight->u.zToken[1] ){
|
| + /* If the rhs of the LIKE expression is a variable, and the current
|
| + ** value of the variable means there is no need to invoke the LIKE
|
| + ** function, then no OP_Variable will be added to the program.
|
| + ** This causes problems for the sqlite3_bind_parameter_name()
|
| + ** API. To workaround them, add a dummy OP_Variable here.
|
| + */
|
| + int r1 = sqlite3GetTempReg(pParse);
|
| + sqlite3ExprCodeTarget(pParse, pRight, r1);
|
| + sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);
|
| + sqlite3ReleaseTempReg(pParse, r1);
|
| + }
|
| + }
|
| + }else{
|
| + z = 0;
|
| + }
|
| + }
|
| +
|
| + sqlite3ValueFree(pVal);
|
| + return (z!=0);
|
| +}
|
| +#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
|
| +
|
| +
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| +/*
|
| +** Check to see if the given expression is of the form
|
| +**
|
| +** column MATCH expr
|
| +**
|
| +** If it is then return TRUE. If not, return FALSE.
|
| +*/
|
| +static int isMatchOfColumn(
|
| + Expr *pExpr /* Test this expression */
|
| +){
|
| + ExprList *pList;
|
| +
|
| + if( pExpr->op!=TK_FUNCTION ){
|
| + return 0;
|
| + }
|
| + if( sqlite3StrICmp(pExpr->u.zToken,"match")!=0 ){
|
| + return 0;
|
| + }
|
| + pList = pExpr->x.pList;
|
| + if( pList->nExpr!=2 ){
|
| + return 0;
|
| + }
|
| + if( pList->a[1].pExpr->op != TK_COLUMN ){
|
| + return 0;
|
| + }
|
| + return 1;
|
| +}
|
| +#endif /* SQLITE_OMIT_VIRTUALTABLE */
|
| +
|
| +/*
|
| +** If the pBase expression originated in the ON or USING clause of
|
| +** a join, then transfer the appropriate markings over to derived.
|
| +*/
|
| +static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
|
| + pDerived->flags |= pBase->flags & EP_FromJoin;
|
| + pDerived->iRightJoinTable = pBase->iRightJoinTable;
|
| +}
|
| +
|
| +#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
|
| +/*
|
| +** Analyze a term that consists of two or more OR-connected
|
| +** subterms. So in:
|
| +**
|
| +** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
|
| +** ^^^^^^^^^^^^^^^^^^^^
|
| +**
|
| +** This routine analyzes terms such as the middle term in the above example.
|
| +** A WhereOrTerm object is computed and attached to the term under
|
| +** analysis, regardless of the outcome of the analysis. Hence:
|
| +**
|
| +** WhereTerm.wtFlags |= TERM_ORINFO
|
| +** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
|
| +**
|
| +** The term being analyzed must have two or more of OR-connected subterms.
|
| +** A single subterm might be a set of AND-connected sub-subterms.
|
| +** Examples of terms under analysis:
|
| +**
|
| +** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
|
| +** (B) x=expr1 OR expr2=x OR x=expr3
|
| +** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
|
| +** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
|
| +** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
|
| +**
|
| +** CASE 1:
|
| +**
|
| +** If all subterms are of the form T.C=expr for some single column of C
|
| +** a single table T (as shown in example B above) then create a new virtual
|
| +** term that is an equivalent IN expression. In other words, if the term
|
| +** being analyzed is:
|
| +**
|
| +** x = expr1 OR expr2 = x OR x = expr3
|
| +**
|
| +** then create a new virtual term like this:
|
| +**
|
| +** x IN (expr1,expr2,expr3)
|
| +**
|
| +** CASE 2:
|
| +**
|
| +** If all subterms are indexable by a single table T, then set
|
| +**
|
| +** WhereTerm.eOperator = WO_OR
|
| +** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
|
| +**
|
| +** A subterm is "indexable" if it is of the form
|
| +** "T.C <op> <expr>" where C is any column of table T and
|
| +** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
|
| +** A subterm is also indexable if it is an AND of two or more
|
| +** subsubterms at least one of which is indexable. Indexable AND
|
| +** subterms have their eOperator set to WO_AND and they have
|
| +** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
|
| +**
|
| +** From another point of view, "indexable" means that the subterm could
|
| +** potentially be used with an index if an appropriate index exists.
|
| +** This analysis does not consider whether or not the index exists; that
|
| +** is something the bestIndex() routine will determine. This analysis
|
| +** only looks at whether subterms appropriate for indexing exist.
|
| +**
|
| +** All examples A through E above all satisfy case 2. But if a term
|
| +** also statisfies case 1 (such as B) we know that the optimizer will
|
| +** always prefer case 1, so in that case we pretend that case 2 is not
|
| +** satisfied.
|
| +**
|
| +** It might be the case that multiple tables are indexable. For example,
|
| +** (E) above is indexable on tables P, Q, and R.
|
| +**
|
| +** Terms that satisfy case 2 are candidates for lookup by using
|
| +** separate indices to find rowids for each subterm and composing
|
| +** the union of all rowids using a RowSet object. This is similar
|
| +** to "bitmap indices" in other database engines.
|
| +**
|
| +** OTHERWISE:
|
| +**
|
| +** If neither case 1 nor case 2 apply, then leave the eOperator set to
|
| +** zero. This term is not useful for search.
|
| +*/
|
| +static void exprAnalyzeOrTerm(
|
| + SrcList *pSrc, /* the FROM clause */
|
| + WhereClause *pWC, /* the complete WHERE clause */
|
| + int idxTerm /* Index of the OR-term to be analyzed */
|
| +){
|
| + Parse *pParse = pWC->pParse; /* Parser context */
|
| + sqlite3 *db = pParse->db; /* Database connection */
|
| + WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */
|
| + Expr *pExpr = pTerm->pExpr; /* The expression of the term */
|
| + WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
|
| + int i; /* Loop counters */
|
| + WhereClause *pOrWc; /* Breakup of pTerm into subterms */
|
| + WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */
|
| + WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */
|
| + Bitmask chngToIN; /* Tables that might satisfy case 1 */
|
| + Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
|
| +
|
| + /*
|
| + ** Break the OR clause into its separate subterms. The subterms are
|
| + ** stored in a WhereClause structure containing within the WhereOrInfo
|
| + ** object that is attached to the original OR clause term.
|
| + */
|
| + assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
|
| + assert( pExpr->op==TK_OR );
|
| + pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
|
| + if( pOrInfo==0 ) return;
|
| + pTerm->wtFlags |= TERM_ORINFO;
|
| + pOrWc = &pOrInfo->wc;
|
| + whereClauseInit(pOrWc, pWC->pParse, pMaskSet);
|
| + whereSplit(pOrWc, pExpr, TK_OR);
|
| + exprAnalyzeAll(pSrc, pOrWc);
|
| + if( db->mallocFailed ) return;
|
| + assert( pOrWc->nTerm>=2 );
|
| +
|
| + /*
|
| + ** Compute the set of tables that might satisfy cases 1 or 2.
|
| + */
|
| + indexable = ~(Bitmask)0;
|
| + chngToIN = ~(pWC->vmask);
|
| + for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
|
| + if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
|
| + WhereAndInfo *pAndInfo;
|
| + assert( pOrTerm->eOperator==0 );
|
| + assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
|
| + chngToIN = 0;
|
| + pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
|
| + if( pAndInfo ){
|
| + WhereClause *pAndWC;
|
| + WhereTerm *pAndTerm;
|
| + int j;
|
| + Bitmask b = 0;
|
| + pOrTerm->u.pAndInfo = pAndInfo;
|
| + pOrTerm->wtFlags |= TERM_ANDINFO;
|
| + pOrTerm->eOperator = WO_AND;
|
| + pAndWC = &pAndInfo->wc;
|
| + whereClauseInit(pAndWC, pWC->pParse, pMaskSet);
|
| + whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
|
| + exprAnalyzeAll(pSrc, pAndWC);
|
| + testcase( db->mallocFailed );
|
| + if( !db->mallocFailed ){
|
| + for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
|
| + assert( pAndTerm->pExpr );
|
| + if( allowedOp(pAndTerm->pExpr->op) ){
|
| + b |= getMask(pMaskSet, pAndTerm->leftCursor);
|
| + }
|
| + }
|
| + }
|
| + indexable &= b;
|
| + }
|
| + }else if( pOrTerm->wtFlags & TERM_COPIED ){
|
| + /* Skip this term for now. We revisit it when we process the
|
| + ** corresponding TERM_VIRTUAL term */
|
| + }else{
|
| + Bitmask b;
|
| + b = getMask(pMaskSet, pOrTerm->leftCursor);
|
| + if( pOrTerm->wtFlags & TERM_VIRTUAL ){
|
| + WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
|
| + b |= getMask(pMaskSet, pOther->leftCursor);
|
| + }
|
| + indexable &= b;
|
| + if( pOrTerm->eOperator!=WO_EQ ){
|
| + chngToIN = 0;
|
| + }else{
|
| + chngToIN &= b;
|
| + }
|
| + }
|
| + }
|
| +
|
| + /*
|
| + ** Record the set of tables that satisfy case 2. The set might be
|
| + ** empty.
|
| + */
|
| + pOrInfo->indexable = indexable;
|
| + pTerm->eOperator = indexable==0 ? 0 : WO_OR;
|
| +
|
| + /*
|
| + ** chngToIN holds a set of tables that *might* satisfy case 1. But
|
| + ** we have to do some additional checking to see if case 1 really
|
| + ** is satisfied.
|
| + **
|
| + ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
|
| + ** that there is no possibility of transforming the OR clause into an
|
| + ** IN operator because one or more terms in the OR clause contain
|
| + ** something other than == on a column in the single table. The 1-bit
|
| + ** case means that every term of the OR clause is of the form
|
| + ** "table.column=expr" for some single table. The one bit that is set
|
| + ** will correspond to the common table. We still need to check to make
|
| + ** sure the same column is used on all terms. The 2-bit case is when
|
| + ** the all terms are of the form "table1.column=table2.column". It
|
| + ** might be possible to form an IN operator with either table1.column
|
| + ** or table2.column as the LHS if either is common to every term of
|
| + ** the OR clause.
|
| + **
|
| + ** Note that terms of the form "table.column1=table.column2" (the
|
| + ** same table on both sizes of the ==) cannot be optimized.
|
| + */
|
| + if( chngToIN ){
|
| + int okToChngToIN = 0; /* True if the conversion to IN is valid */
|
| + int iColumn = -1; /* Column index on lhs of IN operator */
|
| + int iCursor = -1; /* Table cursor common to all terms */
|
| + int j = 0; /* Loop counter */
|
| +
|
| + /* Search for a table and column that appears on one side or the
|
| + ** other of the == operator in every subterm. That table and column
|
| + ** will be recorded in iCursor and iColumn. There might not be any
|
| + ** such table and column. Set okToChngToIN if an appropriate table
|
| + ** and column is found but leave okToChngToIN false if not found.
|
| + */
|
| + for(j=0; j<2 && !okToChngToIN; j++){
|
| + pOrTerm = pOrWc->a;
|
| + for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
|
| + assert( pOrTerm->eOperator==WO_EQ );
|
| + pOrTerm->wtFlags &= ~TERM_OR_OK;
|
| + if( pOrTerm->leftCursor==iCursor ){
|
| + /* This is the 2-bit case and we are on the second iteration and
|
| + ** current term is from the first iteration. So skip this term. */
|
| + assert( j==1 );
|
| + continue;
|
| + }
|
| + if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ){
|
| + /* This term must be of the form t1.a==t2.b where t2 is in the
|
| + ** chngToIN set but t1 is not. This term will be either preceeded
|
| + ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
|
| + ** and use its inversion. */
|
| + testcase( pOrTerm->wtFlags & TERM_COPIED );
|
| + testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
|
| + assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
|
| + continue;
|
| + }
|
| + iColumn = pOrTerm->u.leftColumn;
|
| + iCursor = pOrTerm->leftCursor;
|
| + break;
|
| + }
|
| + if( i<0 ){
|
| + /* No candidate table+column was found. This can only occur
|
| + ** on the second iteration */
|
| + assert( j==1 );
|
| + assert( (chngToIN&(chngToIN-1))==0 );
|
| + assert( chngToIN==getMask(pMaskSet, iCursor) );
|
| + break;
|
| + }
|
| + testcase( j==1 );
|
| +
|
| + /* We have found a candidate table and column. Check to see if that
|
| + ** table and column is common to every term in the OR clause */
|
| + okToChngToIN = 1;
|
| + for(; i>=0 && okToChngToIN; i--, pOrTerm++){
|
| + assert( pOrTerm->eOperator==WO_EQ );
|
| + if( pOrTerm->leftCursor!=iCursor ){
|
| + pOrTerm->wtFlags &= ~TERM_OR_OK;
|
| + }else if( pOrTerm->u.leftColumn!=iColumn ){
|
| + okToChngToIN = 0;
|
| + }else{
|
| + int affLeft, affRight;
|
| + /* If the right-hand side is also a column, then the affinities
|
| + ** of both right and left sides must be such that no type
|
| + ** conversions are required on the right. (Ticket #2249)
|
| + */
|
| + affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
|
| + affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
|
| + if( affRight!=0 && affRight!=affLeft ){
|
| + okToChngToIN = 0;
|
| + }else{
|
| + pOrTerm->wtFlags |= TERM_OR_OK;
|
| + }
|
| + }
|
| + }
|
| + }
|
| +
|
| + /* At this point, okToChngToIN is true if original pTerm satisfies
|
| + ** case 1. In that case, construct a new virtual term that is
|
| + ** pTerm converted into an IN operator.
|
| + **
|
| + ** EV: R-00211-15100
|
| + */
|
| + if( okToChngToIN ){
|
| + Expr *pDup; /* A transient duplicate expression */
|
| + ExprList *pList = 0; /* The RHS of the IN operator */
|
| + Expr *pLeft = 0; /* The LHS of the IN operator */
|
| + Expr *pNew; /* The complete IN operator */
|
| +
|
| + for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
|
| + if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
|
| + assert( pOrTerm->eOperator==WO_EQ );
|
| + assert( pOrTerm->leftCursor==iCursor );
|
| + assert( pOrTerm->u.leftColumn==iColumn );
|
| + pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
|
| + pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
|
| + pLeft = pOrTerm->pExpr->pLeft;
|
| + }
|
| + assert( pLeft!=0 );
|
| + pDup = sqlite3ExprDup(db, pLeft, 0);
|
| + pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0, 0);
|
| + if( pNew ){
|
| + int idxNew;
|
| + transferJoinMarkings(pNew, pExpr);
|
| + assert( !ExprHasProperty(pNew, EP_xIsSelect) );
|
| + pNew->x.pList = pList;
|
| + idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + testcase( idxNew==0 );
|
| + exprAnalyze(pSrc, pWC, idxNew);
|
| + pTerm = &pWC->a[idxTerm];
|
| + pWC->a[idxNew].iParent = idxTerm;
|
| + pTerm->nChild = 1;
|
| + }else{
|
| + sqlite3ExprListDelete(db, pList);
|
| + }
|
| + pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */
|
| + }
|
| + }
|
| +}
|
| +#endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
|
| +
|
| +
|
| +/*
|
| +** The input to this routine is an WhereTerm structure with only the
|
| +** "pExpr" field filled in. The job of this routine is to analyze the
|
| +** subexpression and populate all the other fields of the WhereTerm
|
| +** structure.
|
| +**
|
| +** If the expression is of the form "<expr> <op> X" it gets commuted
|
| +** to the standard form of "X <op> <expr>".
|
| +**
|
| +** If the expression is of the form "X <op> Y" where both X and Y are
|
| +** columns, then the original expression is unchanged and a new virtual
|
| +** term of the form "Y <op> X" is added to the WHERE clause and
|
| +** analyzed separately. The original term is marked with TERM_COPIED
|
| +** and the new term is marked with TERM_DYNAMIC (because it's pExpr
|
| +** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
|
| +** is a commuted copy of a prior term.) The original term has nChild=1
|
| +** and the copy has idxParent set to the index of the original term.
|
| +*/
|
| +static void exprAnalyze(
|
| + SrcList *pSrc, /* the FROM clause */
|
| + WhereClause *pWC, /* the WHERE clause */
|
| + int idxTerm /* Index of the term to be analyzed */
|
| +){
|
| + WhereTerm *pTerm; /* The term to be analyzed */
|
| + WhereMaskSet *pMaskSet; /* Set of table index masks */
|
| + Expr *pExpr; /* The expression to be analyzed */
|
| + Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */
|
| + Bitmask prereqAll; /* Prerequesites of pExpr */
|
| + Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */
|
| + Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */
|
| + int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */
|
| + int noCase = 0; /* LIKE/GLOB distinguishes case */
|
| + int op; /* Top-level operator. pExpr->op */
|
| + Parse *pParse = pWC->pParse; /* Parsing context */
|
| + sqlite3 *db = pParse->db; /* Database connection */
|
| +
|
| + if( db->mallocFailed ){
|
| + return;
|
| + }
|
| + pTerm = &pWC->a[idxTerm];
|
| + pMaskSet = pWC->pMaskSet;
|
| + pExpr = pTerm->pExpr;
|
| + prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
|
| + op = pExpr->op;
|
| + if( op==TK_IN ){
|
| + assert( pExpr->pRight==0 );
|
| + if( ExprHasProperty(pExpr, EP_xIsSelect) ){
|
| + pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);
|
| + }else{
|
| + pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);
|
| + }
|
| + }else if( op==TK_ISNULL ){
|
| + pTerm->prereqRight = 0;
|
| + }else{
|
| + pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
|
| + }
|
| + prereqAll = exprTableUsage(pMaskSet, pExpr);
|
| + if( ExprHasProperty(pExpr, EP_FromJoin) ){
|
| + Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
|
| + prereqAll |= x;
|
| + extraRight = x-1; /* ON clause terms may not be used with an index
|
| + ** on left table of a LEFT JOIN. Ticket #3015 */
|
| + }
|
| + pTerm->prereqAll = prereqAll;
|
| + pTerm->leftCursor = -1;
|
| + pTerm->iParent = -1;
|
| + pTerm->eOperator = 0;
|
| + if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
|
| + Expr *pLeft = pExpr->pLeft;
|
| + Expr *pRight = pExpr->pRight;
|
| + if( pLeft->op==TK_COLUMN ){
|
| + pTerm->leftCursor = pLeft->iTable;
|
| + pTerm->u.leftColumn = pLeft->iColumn;
|
| + pTerm->eOperator = operatorMask(op);
|
| + }
|
| + if( pRight && pRight->op==TK_COLUMN ){
|
| + WhereTerm *pNew;
|
| + Expr *pDup;
|
| + if( pTerm->leftCursor>=0 ){
|
| + int idxNew;
|
| + pDup = sqlite3ExprDup(db, pExpr, 0);
|
| + if( db->mallocFailed ){
|
| + sqlite3ExprDelete(db, pDup);
|
| + return;
|
| + }
|
| + idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + if( idxNew==0 ) return;
|
| + pNew = &pWC->a[idxNew];
|
| + pNew->iParent = idxTerm;
|
| + pTerm = &pWC->a[idxTerm];
|
| + pTerm->nChild = 1;
|
| + pTerm->wtFlags |= TERM_COPIED;
|
| + }else{
|
| + pDup = pExpr;
|
| + pNew = pTerm;
|
| + }
|
| + exprCommute(pParse, pDup);
|
| + pLeft = pDup->pLeft;
|
| + pNew->leftCursor = pLeft->iTable;
|
| + pNew->u.leftColumn = pLeft->iColumn;
|
| + testcase( (prereqLeft | extraRight) != prereqLeft );
|
| + pNew->prereqRight = prereqLeft | extraRight;
|
| + pNew->prereqAll = prereqAll;
|
| + pNew->eOperator = operatorMask(pDup->op);
|
| + }
|
| + }
|
| +
|
| +#ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
|
| + /* If a term is the BETWEEN operator, create two new virtual terms
|
| + ** that define the range that the BETWEEN implements. For example:
|
| + **
|
| + ** a BETWEEN b AND c
|
| + **
|
| + ** is converted into:
|
| + **
|
| + ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
|
| + **
|
| + ** The two new terms are added onto the end of the WhereClause object.
|
| + ** The new terms are "dynamic" and are children of the original BETWEEN
|
| + ** term. That means that if the BETWEEN term is coded, the children are
|
| + ** skipped. Or, if the children are satisfied by an index, the original
|
| + ** BETWEEN term is skipped.
|
| + */
|
| + else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
|
| + ExprList *pList = pExpr->x.pList;
|
| + int i;
|
| + static const u8 ops[] = {TK_GE, TK_LE};
|
| + assert( pList!=0 );
|
| + assert( pList->nExpr==2 );
|
| + for(i=0; i<2; i++){
|
| + Expr *pNewExpr;
|
| + int idxNew;
|
| + pNewExpr = sqlite3PExpr(pParse, ops[i],
|
| + sqlite3ExprDup(db, pExpr->pLeft, 0),
|
| + sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);
|
| + idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + testcase( idxNew==0 );
|
| + exprAnalyze(pSrc, pWC, idxNew);
|
| + pTerm = &pWC->a[idxTerm];
|
| + pWC->a[idxNew].iParent = idxTerm;
|
| + }
|
| + pTerm->nChild = 2;
|
| + }
|
| +#endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
|
| +
|
| +#if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
|
| + /* Analyze a term that is composed of two or more subterms connected by
|
| + ** an OR operator.
|
| + */
|
| + else if( pExpr->op==TK_OR ){
|
| + assert( pWC->op==TK_AND );
|
| + exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
|
| + pTerm = &pWC->a[idxTerm];
|
| + }
|
| +#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
|
| +
|
| +#ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
|
| + /* Add constraints to reduce the search space on a LIKE or GLOB
|
| + ** operator.
|
| + **
|
| + ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
|
| + **
|
| + ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
|
| + **
|
| + ** The last character of the prefix "abc" is incremented to form the
|
| + ** termination condition "abd".
|
| + */
|
| + if( pWC->op==TK_AND
|
| + && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase)
|
| + ){
|
| + Expr *pLeft; /* LHS of LIKE/GLOB operator */
|
| + Expr *pStr2; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
|
| + Expr *pNewExpr1;
|
| + Expr *pNewExpr2;
|
| + int idxNew1;
|
| + int idxNew2;
|
| + CollSeq *pColl; /* Collating sequence to use */
|
| +
|
| + pLeft = pExpr->x.pList->a[1].pExpr;
|
| + pStr2 = sqlite3ExprDup(db, pStr1, 0);
|
| + if( !db->mallocFailed ){
|
| + u8 c, *pC; /* Last character before the first wildcard */
|
| + pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
|
| + c = *pC;
|
| + if( noCase ){
|
| + /* The point is to increment the last character before the first
|
| + ** wildcard. But if we increment '@', that will push it into the
|
| + ** alphabetic range where case conversions will mess up the
|
| + ** inequality. To avoid this, make sure to also run the full
|
| + ** LIKE on all candidate expressions by clearing the isComplete flag
|
| + */
|
| + if( c=='A'-1 ) isComplete = 0; /* EV: R-64339-08207 */
|
| +
|
| +
|
| + c = sqlite3UpperToLower[c];
|
| + }
|
| + *pC = c + 1;
|
| + }
|
| + pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, noCase ? "NOCASE" : "BINARY",0);
|
| + pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
|
| + sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
|
| + pStr1, 0);
|
| + idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + testcase( idxNew1==0 );
|
| + exprAnalyze(pSrc, pWC, idxNew1);
|
| + pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
|
| + sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
|
| + pStr2, 0);
|
| + idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + testcase( idxNew2==0 );
|
| + exprAnalyze(pSrc, pWC, idxNew2);
|
| + pTerm = &pWC->a[idxTerm];
|
| + if( isComplete ){
|
| + pWC->a[idxNew1].iParent = idxTerm;
|
| + pWC->a[idxNew2].iParent = idxTerm;
|
| + pTerm->nChild = 2;
|
| + }
|
| + }
|
| +#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
|
| +
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + /* Add a WO_MATCH auxiliary term to the constraint set if the
|
| + ** current expression is of the form: column MATCH expr.
|
| + ** This information is used by the xBestIndex methods of
|
| + ** virtual tables. The native query optimizer does not attempt
|
| + ** to do anything with MATCH functions.
|
| + */
|
| + if( isMatchOfColumn(pExpr) ){
|
| + int idxNew;
|
| + Expr *pRight, *pLeft;
|
| + WhereTerm *pNewTerm;
|
| + Bitmask prereqColumn, prereqExpr;
|
| +
|
| + pRight = pExpr->x.pList->a[0].pExpr;
|
| + pLeft = pExpr->x.pList->a[1].pExpr;
|
| + prereqExpr = exprTableUsage(pMaskSet, pRight);
|
| + prereqColumn = exprTableUsage(pMaskSet, pLeft);
|
| + if( (prereqExpr & prereqColumn)==0 ){
|
| + Expr *pNewExpr;
|
| + pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
|
| + 0, sqlite3ExprDup(db, pRight, 0), 0);
|
| + idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
|
| + testcase( idxNew==0 );
|
| + pNewTerm = &pWC->a[idxNew];
|
| + pNewTerm->prereqRight = prereqExpr;
|
| + pNewTerm->leftCursor = pLeft->iTable;
|
| + pNewTerm->u.leftColumn = pLeft->iColumn;
|
| + pNewTerm->eOperator = WO_MATCH;
|
| + pNewTerm->iParent = idxTerm;
|
| + pTerm = &pWC->a[idxTerm];
|
| + pTerm->nChild = 1;
|
| + pTerm->wtFlags |= TERM_COPIED;
|
| + pNewTerm->prereqAll = pTerm->prereqAll;
|
| + }
|
| + }
|
| +#endif /* SQLITE_OMIT_VIRTUALTABLE */
|
| +
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| + /* When sqlite_stat2 histogram data is available an operator of the
|
| + ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
|
| + ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
|
| + ** virtual term of that form.
|
| + **
|
| + ** Note that the virtual term must be tagged with TERM_VNULL. This
|
| + ** TERM_VNULL tag will suppress the not-null check at the beginning
|
| + ** of the loop. Without the TERM_VNULL flag, the not-null check at
|
| + ** the start of the loop will prevent any results from being returned.
|
| + */
|
| + if( pExpr->op==TK_NOTNULL
|
| + && pExpr->pLeft->op==TK_COLUMN
|
| + && pExpr->pLeft->iColumn>=0
|
| + ){
|
| + Expr *pNewExpr;
|
| + Expr *pLeft = pExpr->pLeft;
|
| + int idxNew;
|
| + WhereTerm *pNewTerm;
|
| +
|
| + pNewExpr = sqlite3PExpr(pParse, TK_GT,
|
| + sqlite3ExprDup(db, pLeft, 0),
|
| + sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);
|
| +
|
| + idxNew = whereClauseInsert(pWC, pNewExpr,
|
| + TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
|
| + if( idxNew ){
|
| + pNewTerm = &pWC->a[idxNew];
|
| + pNewTerm->prereqRight = 0;
|
| + pNewTerm->leftCursor = pLeft->iTable;
|
| + pNewTerm->u.leftColumn = pLeft->iColumn;
|
| + pNewTerm->eOperator = WO_GT;
|
| + pNewTerm->iParent = idxTerm;
|
| + pTerm = &pWC->a[idxTerm];
|
| + pTerm->nChild = 1;
|
| + pTerm->wtFlags |= TERM_COPIED;
|
| + pNewTerm->prereqAll = pTerm->prereqAll;
|
| + }
|
| + }
|
| +#endif /* SQLITE_ENABLE_STAT2 */
|
| +
|
| + /* Prevent ON clause terms of a LEFT JOIN from being used to drive
|
| + ** an index for tables to the left of the join.
|
| + */
|
| + pTerm->prereqRight |= extraRight;
|
| +}
|
| +
|
| +/*
|
| +** Return TRUE if any of the expressions in pList->a[iFirst...] contain
|
| +** a reference to any table other than the iBase table.
|
| +*/
|
| +static int referencesOtherTables(
|
| + ExprList *pList, /* Search expressions in ths list */
|
| + WhereMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
|
| + int iFirst, /* Be searching with the iFirst-th expression */
|
| + int iBase /* Ignore references to this table */
|
| +){
|
| + Bitmask allowed = ~getMask(pMaskSet, iBase);
|
| + while( iFirst<pList->nExpr ){
|
| + if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
|
| + return 1;
|
| + }
|
| + }
|
| + return 0;
|
| +}
|
| +
|
| +
|
| +/*
|
| +** This routine decides if pIdx can be used to satisfy the ORDER BY
|
| +** clause. If it can, it returns 1. If pIdx cannot satisfy the
|
| +** ORDER BY clause, this routine returns 0.
|
| +**
|
| +** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
|
| +** left-most table in the FROM clause of that same SELECT statement and
|
| +** the table has a cursor number of "base". pIdx is an index on pTab.
|
| +**
|
| +** nEqCol is the number of columns of pIdx that are used as equality
|
| +** constraints. Any of these columns may be missing from the ORDER BY
|
| +** clause and the match can still be a success.
|
| +**
|
| +** All terms of the ORDER BY that match against the index must be either
|
| +** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
|
| +** index do not need to satisfy this constraint.) The *pbRev value is
|
| +** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
|
| +** the ORDER BY clause is all ASC.
|
| +*/
|
| +static int isSortingIndex(
|
| + Parse *pParse, /* Parsing context */
|
| + WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
|
| + Index *pIdx, /* The index we are testing */
|
| + int base, /* Cursor number for the table to be sorted */
|
| + ExprList *pOrderBy, /* The ORDER BY clause */
|
| + int nEqCol, /* Number of index columns with == constraints */
|
| + int wsFlags, /* Index usages flags */
|
| + int *pbRev /* Set to 1 if ORDER BY is DESC */
|
| +){
|
| + int i, j; /* Loop counters */
|
| + int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
|
| + int nTerm; /* Number of ORDER BY terms */
|
| + struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
|
| + sqlite3 *db = pParse->db;
|
| +
|
| + assert( pOrderBy!=0 );
|
| + nTerm = pOrderBy->nExpr;
|
| + assert( nTerm>0 );
|
| +
|
| + /* Argument pIdx must either point to a 'real' named index structure,
|
| + ** or an index structure allocated on the stack by bestBtreeIndex() to
|
| + ** represent the rowid index that is part of every table. */
|
| + assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
|
| +
|
| + /* Match terms of the ORDER BY clause against columns of
|
| + ** the index.
|
| + **
|
| + ** Note that indices have pIdx->nColumn regular columns plus
|
| + ** one additional column containing the rowid. The rowid column
|
| + ** of the index is also allowed to match against the ORDER BY
|
| + ** clause.
|
| + */
|
| + for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
|
| + Expr *pExpr; /* The expression of the ORDER BY pTerm */
|
| + CollSeq *pColl; /* The collating sequence of pExpr */
|
| + int termSortOrder; /* Sort order for this term */
|
| + int iColumn; /* The i-th column of the index. -1 for rowid */
|
| + int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
|
| + const char *zColl; /* Name of the collating sequence for i-th index term */
|
| +
|
| + pExpr = pTerm->pExpr;
|
| + if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
|
| + /* Can not use an index sort on anything that is not a column in the
|
| + ** left-most table of the FROM clause */
|
| + break;
|
| + }
|
| + pColl = sqlite3ExprCollSeq(pParse, pExpr);
|
| + if( !pColl ){
|
| + pColl = db->pDfltColl;
|
| + }
|
| + if( pIdx->zName && i<pIdx->nColumn ){
|
| + iColumn = pIdx->aiColumn[i];
|
| + if( iColumn==pIdx->pTable->iPKey ){
|
| + iColumn = -1;
|
| + }
|
| + iSortOrder = pIdx->aSortOrder[i];
|
| + zColl = pIdx->azColl[i];
|
| + }else{
|
| + iColumn = -1;
|
| + iSortOrder = 0;
|
| + zColl = pColl->zName;
|
| + }
|
| + if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
|
| + /* Term j of the ORDER BY clause does not match column i of the index */
|
| + if( i<nEqCol ){
|
| + /* If an index column that is constrained by == fails to match an
|
| + ** ORDER BY term, that is OK. Just ignore that column of the index
|
| + */
|
| + continue;
|
| + }else if( i==pIdx->nColumn ){
|
| + /* Index column i is the rowid. All other terms match. */
|
| + break;
|
| + }else{
|
| + /* If an index column fails to match and is not constrained by ==
|
| + ** then the index cannot satisfy the ORDER BY constraint.
|
| + */
|
| + return 0;
|
| + }
|
| + }
|
| + assert( pIdx->aSortOrder!=0 || iColumn==-1 );
|
| + assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
|
| + assert( iSortOrder==0 || iSortOrder==1 );
|
| + termSortOrder = iSortOrder ^ pTerm->sortOrder;
|
| + if( i>nEqCol ){
|
| + if( termSortOrder!=sortOrder ){
|
| + /* Indices can only be used if all ORDER BY terms past the
|
| + ** equality constraints are all either DESC or ASC. */
|
| + return 0;
|
| + }
|
| + }else{
|
| + sortOrder = termSortOrder;
|
| + }
|
| + j++;
|
| + pTerm++;
|
| + if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
|
| + /* If the indexed column is the primary key and everything matches
|
| + ** so far and none of the ORDER BY terms to the right reference other
|
| + ** tables in the join, then we are assured that the index can be used
|
| + ** to sort because the primary key is unique and so none of the other
|
| + ** columns will make any difference
|
| + */
|
| + j = nTerm;
|
| + }
|
| + }
|
| +
|
| + *pbRev = sortOrder!=0;
|
| + if( j>=nTerm ){
|
| + /* All terms of the ORDER BY clause are covered by this index so
|
| + ** this index can be used for sorting. */
|
| + return 1;
|
| + }
|
| + if( pIdx->onError!=OE_None && i==pIdx->nColumn
|
| + && (wsFlags & WHERE_COLUMN_NULL)==0
|
| + && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
|
| + /* All terms of this index match some prefix of the ORDER BY clause
|
| + ** and the index is UNIQUE and no terms on the tail of the ORDER BY
|
| + ** clause reference other tables in a join. If this is all true then
|
| + ** the order by clause is superfluous. Not that if the matching
|
| + ** condition is IS NULL then the result is not necessarily unique
|
| + ** even on a UNIQUE index, so disallow those cases. */
|
| + return 1;
|
| + }
|
| + return 0;
|
| +}
|
| +
|
| +/*
|
| +** Prepare a crude estimate of the logarithm of the input value.
|
| +** The results need not be exact. This is only used for estimating
|
| +** the total cost of performing operations with O(logN) or O(NlogN)
|
| +** complexity. Because N is just a guess, it is no great tragedy if
|
| +** logN is a little off.
|
| +*/
|
| +static double estLog(double N){
|
| + double logN = 1;
|
| + double x = 10;
|
| + while( N>x ){
|
| + logN += 1;
|
| + x *= 10;
|
| + }
|
| + return logN;
|
| +}
|
| +
|
| +/*
|
| +** Two routines for printing the content of an sqlite3_index_info
|
| +** structure. Used for testing and debugging only. If neither
|
| +** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
|
| +** are no-ops.
|
| +*/
|
| +#if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
|
| +static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
|
| + int i;
|
| + if( !sqlite3WhereTrace ) return;
|
| + for(i=0; i<p->nConstraint; i++){
|
| + sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
|
| + i,
|
| + p->aConstraint[i].iColumn,
|
| + p->aConstraint[i].iTermOffset,
|
| + p->aConstraint[i].op,
|
| + p->aConstraint[i].usable);
|
| + }
|
| + for(i=0; i<p->nOrderBy; i++){
|
| + sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
|
| + i,
|
| + p->aOrderBy[i].iColumn,
|
| + p->aOrderBy[i].desc);
|
| + }
|
| +}
|
| +static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
|
| + int i;
|
| + if( !sqlite3WhereTrace ) return;
|
| + for(i=0; i<p->nConstraint; i++){
|
| + sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
|
| + i,
|
| + p->aConstraintUsage[i].argvIndex,
|
| + p->aConstraintUsage[i].omit);
|
| + }
|
| + sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
|
| + sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
|
| + sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
|
| + sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
|
| +}
|
| +#else
|
| +#define TRACE_IDX_INPUTS(A)
|
| +#define TRACE_IDX_OUTPUTS(A)
|
| +#endif
|
| +
|
| +/*
|
| +** Required because bestIndex() is called by bestOrClauseIndex()
|
| +*/
|
| +static void bestIndex(
|
| + Parse*, WhereClause*, struct SrcList_item*,
|
| + Bitmask, Bitmask, ExprList*, WhereCost*);
|
| +
|
| +/*
|
| +** This routine attempts to find an scanning strategy that can be used
|
| +** to optimize an 'OR' expression that is part of a WHERE clause.
|
| +**
|
| +** The table associated with FROM clause term pSrc may be either a
|
| +** regular B-Tree table or a virtual table.
|
| +*/
|
| +static void bestOrClauseIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to search */
|
| + Bitmask notReady, /* Mask of cursors not available for indexing */
|
| + Bitmask notValid, /* Cursors not available for any purpose */
|
| + ExprList *pOrderBy, /* The ORDER BY clause */
|
| + WhereCost *pCost /* Lowest cost query plan */
|
| +){
|
| +#ifndef SQLITE_OMIT_OR_OPTIMIZATION
|
| + const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
|
| + const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
|
| + WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
|
| + WhereTerm *pTerm; /* A single term of the WHERE clause */
|
| +
|
| + /* No OR-clause optimization allowed if the INDEXED BY or NOT INDEXED clauses
|
| + ** are used */
|
| + if( pSrc->notIndexed || pSrc->pIndex!=0 ){
|
| + return;
|
| + }
|
| +
|
| + /* Search the WHERE clause terms for a usable WO_OR term. */
|
| + for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
|
| + if( pTerm->eOperator==WO_OR
|
| + && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
|
| + && (pTerm->u.pOrInfo->indexable & maskSrc)!=0
|
| + ){
|
| + WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
|
| + WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
|
| + WhereTerm *pOrTerm;
|
| + int flags = WHERE_MULTI_OR;
|
| + double rTotal = 0;
|
| + double nRow = 0;
|
| + Bitmask used = 0;
|
| +
|
| + for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
|
| + WhereCost sTermCost;
|
| + WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
|
| + (pOrTerm - pOrWC->a), (pTerm - pWC->a)
|
| + ));
|
| + if( pOrTerm->eOperator==WO_AND ){
|
| + WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
|
| + bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost);
|
| + }else if( pOrTerm->leftCursor==iCur ){
|
| + WhereClause tempWC;
|
| + tempWC.pParse = pWC->pParse;
|
| + tempWC.pMaskSet = pWC->pMaskSet;
|
| + tempWC.op = TK_AND;
|
| + tempWC.a = pOrTerm;
|
| + tempWC.nTerm = 1;
|
| + bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost);
|
| + }else{
|
| + continue;
|
| + }
|
| + rTotal += sTermCost.rCost;
|
| + nRow += sTermCost.plan.nRow;
|
| + used |= sTermCost.used;
|
| + if( rTotal>=pCost->rCost ) break;
|
| + }
|
| +
|
| + /* If there is an ORDER BY clause, increase the scan cost to account
|
| + ** for the cost of the sort. */
|
| + if( pOrderBy!=0 ){
|
| + WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
|
| + rTotal, rTotal+nRow*estLog(nRow)));
|
| + rTotal += nRow*estLog(nRow);
|
| + }
|
| +
|
| + /* If the cost of scanning using this OR term for optimization is
|
| + ** less than the current cost stored in pCost, replace the contents
|
| + ** of pCost. */
|
| + WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
|
| + if( rTotal<pCost->rCost ){
|
| + pCost->rCost = rTotal;
|
| + pCost->used = used;
|
| + pCost->plan.nRow = nRow;
|
| + pCost->plan.wsFlags = flags;
|
| + pCost->plan.u.pTerm = pTerm;
|
| + }
|
| + }
|
| + }
|
| +#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
|
| +}
|
| +
|
| +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
|
| +/*
|
| +** Return TRUE if the WHERE clause term pTerm is of a form where it
|
| +** could be used with an index to access pSrc, assuming an appropriate
|
| +** index existed.
|
| +*/
|
| +static int termCanDriveIndex(
|
| + WhereTerm *pTerm, /* WHERE clause term to check */
|
| + struct SrcList_item *pSrc, /* Table we are trying to access */
|
| + Bitmask notReady /* Tables in outer loops of the join */
|
| +){
|
| + char aff;
|
| + if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
|
| + if( pTerm->eOperator!=WO_EQ ) return 0;
|
| + if( (pTerm->prereqRight & notReady)!=0 ) return 0;
|
| + aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
|
| + if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
|
| + return 1;
|
| +}
|
| +#endif
|
| +
|
| +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
|
| +/*
|
| +** If the query plan for pSrc specified in pCost is a full table scan
|
| +** and indexing is allows (if there is no NOT INDEXED clause) and it
|
| +** possible to construct a transient index that would perform better
|
| +** than a full table scan even when the cost of constructing the index
|
| +** is taken into account, then alter the query plan to use the
|
| +** transient index.
|
| +*/
|
| +static void bestAutomaticIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to search */
|
| + Bitmask notReady, /* Mask of cursors that are not available */
|
| + WhereCost *pCost /* Lowest cost query plan */
|
| +){
|
| + double nTableRow; /* Rows in the input table */
|
| + double logN; /* log(nTableRow) */
|
| + double costTempIdx; /* per-query cost of the transient index */
|
| + WhereTerm *pTerm; /* A single term of the WHERE clause */
|
| + WhereTerm *pWCEnd; /* End of pWC->a[] */
|
| + Table *pTable; /* Table tht might be indexed */
|
| +
|
| + if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
|
| + /* Automatic indices are disabled at run-time */
|
| + return;
|
| + }
|
| + if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
|
| + /* We already have some kind of index in use for this query. */
|
| + return;
|
| + }
|
| + if( pSrc->notIndexed ){
|
| + /* The NOT INDEXED clause appears in the SQL. */
|
| + return;
|
| + }
|
| +
|
| + assert( pParse->nQueryLoop >= (double)1 );
|
| + pTable = pSrc->pTab;
|
| + nTableRow = pTable->nRowEst;
|
| + logN = estLog(nTableRow);
|
| + costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
|
| + if( costTempIdx>=pCost->rCost ){
|
| + /* The cost of creating the transient table would be greater than
|
| + ** doing the full table scan */
|
| + return;
|
| + }
|
| +
|
| + /* Search for any equality comparison term */
|
| + pWCEnd = &pWC->a[pWC->nTerm];
|
| + for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
|
| + if( termCanDriveIndex(pTerm, pSrc, notReady) ){
|
| + WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
|
| + pCost->rCost, costTempIdx));
|
| + pCost->rCost = costTempIdx;
|
| + pCost->plan.nRow = logN + 1;
|
| + pCost->plan.wsFlags = WHERE_TEMP_INDEX;
|
| + pCost->used = pTerm->prereqRight;
|
| + break;
|
| + }
|
| + }
|
| +}
|
| +#else
|
| +# define bestAutomaticIndex(A,B,C,D,E) /* no-op */
|
| +#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
|
| +
|
| +
|
| +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
|
| +/*
|
| +** Generate code to construct the Index object for an automatic index
|
| +** and to set up the WhereLevel object pLevel so that the code generator
|
| +** makes use of the automatic index.
|
| +*/
|
| +static void constructAutomaticIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to get the next index */
|
| + Bitmask notReady, /* Mask of cursors that are not available */
|
| + WhereLevel *pLevel /* Write new index here */
|
| +){
|
| + int nColumn; /* Number of columns in the constructed index */
|
| + WhereTerm *pTerm; /* A single term of the WHERE clause */
|
| + WhereTerm *pWCEnd; /* End of pWC->a[] */
|
| + int nByte; /* Byte of memory needed for pIdx */
|
| + Index *pIdx; /* Object describing the transient index */
|
| + Vdbe *v; /* Prepared statement under construction */
|
| + int regIsInit; /* Register set by initialization */
|
| + int addrInit; /* Address of the initialization bypass jump */
|
| + Table *pTable; /* The table being indexed */
|
| + KeyInfo *pKeyinfo; /* Key information for the index */
|
| + int addrTop; /* Top of the index fill loop */
|
| + int regRecord; /* Register holding an index record */
|
| + int n; /* Column counter */
|
| + int i; /* Loop counter */
|
| + int mxBitCol; /* Maximum column in pSrc->colUsed */
|
| + CollSeq *pColl; /* Collating sequence to on a column */
|
| + Bitmask idxCols; /* Bitmap of columns used for indexing */
|
| + Bitmask extraCols; /* Bitmap of additional columns */
|
| +
|
| + /* Generate code to skip over the creation and initialization of the
|
| + ** transient index on 2nd and subsequent iterations of the loop. */
|
| + v = pParse->pVdbe;
|
| + assert( v!=0 );
|
| + regIsInit = ++pParse->nMem;
|
| + addrInit = sqlite3VdbeAddOp1(v, OP_If, regIsInit);
|
| + sqlite3VdbeAddOp2(v, OP_Integer, 1, regIsInit);
|
| +
|
| + /* Count the number of columns that will be added to the index
|
| + ** and used to match WHERE clause constraints */
|
| + nColumn = 0;
|
| + pTable = pSrc->pTab;
|
| + pWCEnd = &pWC->a[pWC->nTerm];
|
| + idxCols = 0;
|
| + for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
|
| + if( termCanDriveIndex(pTerm, pSrc, notReady) ){
|
| + int iCol = pTerm->u.leftColumn;
|
| + Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
|
| + testcase( iCol==BMS );
|
| + testcase( iCol==BMS-1 );
|
| + if( (idxCols & cMask)==0 ){
|
| + nColumn++;
|
| + idxCols |= cMask;
|
| + }
|
| + }
|
| + }
|
| + assert( nColumn>0 );
|
| + pLevel->plan.nEq = nColumn;
|
| +
|
| + /* Count the number of additional columns needed to create a
|
| + ** covering index. A "covering index" is an index that contains all
|
| + ** columns that are needed by the query. With a covering index, the
|
| + ** original table never needs to be accessed. Automatic indices must
|
| + ** be a covering index because the index will not be updated if the
|
| + ** original table changes and the index and table cannot both be used
|
| + ** if they go out of sync.
|
| + */
|
| + extraCols = pSrc->colUsed & (~idxCols | (((Bitmask)1)<<(BMS-1)));
|
| + mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol;
|
| + testcase( pTable->nCol==BMS-1 );
|
| + testcase( pTable->nCol==BMS-2 );
|
| + for(i=0; i<mxBitCol; i++){
|
| + if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
|
| + }
|
| + if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
|
| + nColumn += pTable->nCol - BMS + 1;
|
| + }
|
| + pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;
|
| +
|
| + /* Construct the Index object to describe this index */
|
| + nByte = sizeof(Index);
|
| + nByte += nColumn*sizeof(int); /* Index.aiColumn */
|
| + nByte += nColumn*sizeof(char*); /* Index.azColl */
|
| + nByte += nColumn; /* Index.aSortOrder */
|
| + pIdx = sqlite3DbMallocZero(pParse->db, nByte);
|
| + if( pIdx==0 ) return;
|
| + pLevel->plan.u.pIdx = pIdx;
|
| + pIdx->azColl = (char**)&pIdx[1];
|
| + pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
|
| + pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
|
| + pIdx->zName = "auto-index";
|
| + pIdx->nColumn = nColumn;
|
| + pIdx->pTable = pTable;
|
| + n = 0;
|
| + idxCols = 0;
|
| + for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
|
| + if( termCanDriveIndex(pTerm, pSrc, notReady) ){
|
| + int iCol = pTerm->u.leftColumn;
|
| + Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
|
| + if( (idxCols & cMask)==0 ){
|
| + Expr *pX = pTerm->pExpr;
|
| + idxCols |= cMask;
|
| + pIdx->aiColumn[n] = pTerm->u.leftColumn;
|
| + pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
|
| + pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY";
|
| + n++;
|
| + }
|
| + }
|
| + }
|
| + assert( (u32)n==pLevel->plan.nEq );
|
| +
|
| + /* Add additional columns needed to make the automatic index into
|
| + ** a covering index */
|
| + for(i=0; i<mxBitCol; i++){
|
| + if( extraCols & (((Bitmask)1)<<i) ){
|
| + pIdx->aiColumn[n] = i;
|
| + pIdx->azColl[n] = "BINARY";
|
| + n++;
|
| + }
|
| + }
|
| + if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
|
| + for(i=BMS-1; i<pTable->nCol; i++){
|
| + pIdx->aiColumn[n] = i;
|
| + pIdx->azColl[n] = "BINARY";
|
| + n++;
|
| + }
|
| + }
|
| + assert( n==nColumn );
|
| +
|
| + /* Create the automatic index */
|
| + pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
|
| + assert( pLevel->iIdxCur>=0 );
|
| + sqlite3VdbeAddOp4(v, OP_OpenAutoindex, pLevel->iIdxCur, nColumn+1, 0,
|
| + (char*)pKeyinfo, P4_KEYINFO_HANDOFF);
|
| + VdbeComment((v, "for %s", pTable->zName));
|
| +
|
| + /* Fill the automatic index with content */
|
| + addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
|
| + regRecord = sqlite3GetTempReg(pParse);
|
| + sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
|
| + sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
|
| + sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
|
| + sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1);
|
| + sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
|
| + sqlite3VdbeJumpHere(v, addrTop);
|
| + sqlite3ReleaseTempReg(pParse, regRecord);
|
| +
|
| + /* Jump here when skipping the initialization */
|
| + sqlite3VdbeJumpHere(v, addrInit);
|
| +}
|
| +#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
|
| +
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| +/*
|
| +** Allocate and populate an sqlite3_index_info structure. It is the
|
| +** responsibility of the caller to eventually release the structure
|
| +** by passing the pointer returned by this function to sqlite3_free().
|
| +*/
|
| +static sqlite3_index_info *allocateIndexInfo(
|
| + Parse *pParse,
|
| + WhereClause *pWC,
|
| + struct SrcList_item *pSrc,
|
| + ExprList *pOrderBy
|
| +){
|
| + int i, j;
|
| + int nTerm;
|
| + struct sqlite3_index_constraint *pIdxCons;
|
| + struct sqlite3_index_orderby *pIdxOrderBy;
|
| + struct sqlite3_index_constraint_usage *pUsage;
|
| + WhereTerm *pTerm;
|
| + int nOrderBy;
|
| + sqlite3_index_info *pIdxInfo;
|
| +
|
| + WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
|
| +
|
| + /* Count the number of possible WHERE clause constraints referring
|
| + ** to this virtual table */
|
| + for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
|
| + if( pTerm->leftCursor != pSrc->iCursor ) continue;
|
| + assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
|
| + testcase( pTerm->eOperator==WO_IN );
|
| + testcase( pTerm->eOperator==WO_ISNULL );
|
| + if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
|
| + nTerm++;
|
| + }
|
| +
|
| + /* If the ORDER BY clause contains only columns in the current
|
| + ** virtual table then allocate space for the aOrderBy part of
|
| + ** the sqlite3_index_info structure.
|
| + */
|
| + nOrderBy = 0;
|
| + if( pOrderBy ){
|
| + for(i=0; i<pOrderBy->nExpr; i++){
|
| + Expr *pExpr = pOrderBy->a[i].pExpr;
|
| + if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
|
| + }
|
| + if( i==pOrderBy->nExpr ){
|
| + nOrderBy = pOrderBy->nExpr;
|
| + }
|
| + }
|
| +
|
| + /* Allocate the sqlite3_index_info structure
|
| + */
|
| + pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
|
| + + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
|
| + + sizeof(*pIdxOrderBy)*nOrderBy );
|
| + if( pIdxInfo==0 ){
|
| + sqlite3ErrorMsg(pParse, "out of memory");
|
| + /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
|
| + return 0;
|
| + }
|
| +
|
| + /* Initialize the structure. The sqlite3_index_info structure contains
|
| + ** many fields that are declared "const" to prevent xBestIndex from
|
| + ** changing them. We have to do some funky casting in order to
|
| + ** initialize those fields.
|
| + */
|
| + pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
|
| + pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
|
| + pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
|
| + *(int*)&pIdxInfo->nConstraint = nTerm;
|
| + *(int*)&pIdxInfo->nOrderBy = nOrderBy;
|
| + *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
|
| + *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
|
| + *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
|
| + pUsage;
|
| +
|
| + for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
|
| + if( pTerm->leftCursor != pSrc->iCursor ) continue;
|
| + assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
|
| + testcase( pTerm->eOperator==WO_IN );
|
| + testcase( pTerm->eOperator==WO_ISNULL );
|
| + if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
|
| + pIdxCons[j].iColumn = pTerm->u.leftColumn;
|
| + pIdxCons[j].iTermOffset = i;
|
| + pIdxCons[j].op = (u8)pTerm->eOperator;
|
| + /* The direct assignment in the previous line is possible only because
|
| + ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
|
| + ** following asserts verify this fact. */
|
| + assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
|
| + assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
|
| + assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
|
| + assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
|
| + assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
|
| + assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
|
| + assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
|
| + j++;
|
| + }
|
| + for(i=0; i<nOrderBy; i++){
|
| + Expr *pExpr = pOrderBy->a[i].pExpr;
|
| + pIdxOrderBy[i].iColumn = pExpr->iColumn;
|
| + pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
|
| + }
|
| +
|
| + return pIdxInfo;
|
| +}
|
| +
|
| +/*
|
| +** The table object reference passed as the second argument to this function
|
| +** must represent a virtual table. This function invokes the xBestIndex()
|
| +** method of the virtual table with the sqlite3_index_info pointer passed
|
| +** as the argument.
|
| +**
|
| +** If an error occurs, pParse is populated with an error message and a
|
| +** non-zero value is returned. Otherwise, 0 is returned and the output
|
| +** part of the sqlite3_index_info structure is left populated.
|
| +**
|
| +** Whether or not an error is returned, it is the responsibility of the
|
| +** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
|
| +** that this is required.
|
| +*/
|
| +static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
|
| + sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
|
| + int i;
|
| + int rc;
|
| +
|
| + WHERETRACE(("xBestIndex for %s\n", pTab->zName));
|
| + TRACE_IDX_INPUTS(p);
|
| + rc = pVtab->pModule->xBestIndex(pVtab, p);
|
| + TRACE_IDX_OUTPUTS(p);
|
| +
|
| + if( rc!=SQLITE_OK ){
|
| + if( rc==SQLITE_NOMEM ){
|
| + pParse->db->mallocFailed = 1;
|
| + }else if( !pVtab->zErrMsg ){
|
| + sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
|
| + }else{
|
| + sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
|
| + }
|
| + }
|
| + sqlite3_free(pVtab->zErrMsg);
|
| + pVtab->zErrMsg = 0;
|
| +
|
| + for(i=0; i<p->nConstraint; i++){
|
| + if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
|
| + sqlite3ErrorMsg(pParse,
|
| + "table %s: xBestIndex returned an invalid plan", pTab->zName);
|
| + }
|
| + }
|
| +
|
| + return pParse->nErr;
|
| +}
|
| +
|
| +
|
| +/*
|
| +** Compute the best index for a virtual table.
|
| +**
|
| +** The best index is computed by the xBestIndex method of the virtual
|
| +** table module. This routine is really just a wrapper that sets up
|
| +** the sqlite3_index_info structure that is used to communicate with
|
| +** xBestIndex.
|
| +**
|
| +** In a join, this routine might be called multiple times for the
|
| +** same virtual table. The sqlite3_index_info structure is created
|
| +** and initialized on the first invocation and reused on all subsequent
|
| +** invocations. The sqlite3_index_info structure is also used when
|
| +** code is generated to access the virtual table. The whereInfoDelete()
|
| +** routine takes care of freeing the sqlite3_index_info structure after
|
| +** everybody has finished with it.
|
| +*/
|
| +static void bestVirtualIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to search */
|
| + Bitmask notReady, /* Mask of cursors not available for index */
|
| + Bitmask notValid, /* Cursors not valid for any purpose */
|
| + ExprList *pOrderBy, /* The order by clause */
|
| + WhereCost *pCost, /* Lowest cost query plan */
|
| + sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
|
| +){
|
| + Table *pTab = pSrc->pTab;
|
| + sqlite3_index_info *pIdxInfo;
|
| + struct sqlite3_index_constraint *pIdxCons;
|
| + struct sqlite3_index_constraint_usage *pUsage;
|
| + WhereTerm *pTerm;
|
| + int i, j;
|
| + int nOrderBy;
|
| + double rCost;
|
| +
|
| + /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
|
| + ** malloc in allocateIndexInfo() fails and this function returns leaving
|
| + ** wsFlags in an uninitialized state, the caller may behave unpredictably.
|
| + */
|
| + memset(pCost, 0, sizeof(*pCost));
|
| + pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
|
| +
|
| + /* If the sqlite3_index_info structure has not been previously
|
| + ** allocated and initialized, then allocate and initialize it now.
|
| + */
|
| + pIdxInfo = *ppIdxInfo;
|
| + if( pIdxInfo==0 ){
|
| + *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
|
| + }
|
| + if( pIdxInfo==0 ){
|
| + return;
|
| + }
|
| +
|
| + /* At this point, the sqlite3_index_info structure that pIdxInfo points
|
| + ** to will have been initialized, either during the current invocation or
|
| + ** during some prior invocation. Now we just have to customize the
|
| + ** details of pIdxInfo for the current invocation and pass it to
|
| + ** xBestIndex.
|
| + */
|
| +
|
| + /* The module name must be defined. Also, by this point there must
|
| + ** be a pointer to an sqlite3_vtab structure. Otherwise
|
| + ** sqlite3ViewGetColumnNames() would have picked up the error.
|
| + */
|
| + assert( pTab->azModuleArg && pTab->azModuleArg[0] );
|
| + assert( sqlite3GetVTable(pParse->db, pTab) );
|
| +
|
| + /* Set the aConstraint[].usable fields and initialize all
|
| + ** output variables to zero.
|
| + **
|
| + ** aConstraint[].usable is true for constraints where the right-hand
|
| + ** side contains only references to tables to the left of the current
|
| + ** table. In other words, if the constraint is of the form:
|
| + **
|
| + ** column = expr
|
| + **
|
| + ** and we are evaluating a join, then the constraint on column is
|
| + ** only valid if all tables referenced in expr occur to the left
|
| + ** of the table containing column.
|
| + **
|
| + ** The aConstraints[] array contains entries for all constraints
|
| + ** on the current table. That way we only have to compute it once
|
| + ** even though we might try to pick the best index multiple times.
|
| + ** For each attempt at picking an index, the order of tables in the
|
| + ** join might be different so we have to recompute the usable flag
|
| + ** each time.
|
| + */
|
| + pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
|
| + pUsage = pIdxInfo->aConstraintUsage;
|
| + for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
|
| + j = pIdxCons->iTermOffset;
|
| + pTerm = &pWC->a[j];
|
| + pIdxCons->usable = (pTerm->prereqRight¬Ready) ? 0 : 1;
|
| + }
|
| + memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
|
| + if( pIdxInfo->needToFreeIdxStr ){
|
| + sqlite3_free(pIdxInfo->idxStr);
|
| + }
|
| + pIdxInfo->idxStr = 0;
|
| + pIdxInfo->idxNum = 0;
|
| + pIdxInfo->needToFreeIdxStr = 0;
|
| + pIdxInfo->orderByConsumed = 0;
|
| + /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
|
| + pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
|
| + nOrderBy = pIdxInfo->nOrderBy;
|
| + if( !pOrderBy ){
|
| + pIdxInfo->nOrderBy = 0;
|
| + }
|
| +
|
| + if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
|
| + return;
|
| + }
|
| +
|
| + pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
|
| + for(i=0; i<pIdxInfo->nConstraint; i++){
|
| + if( pUsage[i].argvIndex>0 ){
|
| + pCost->used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
|
| + }
|
| + }
|
| +
|
| + /* If there is an ORDER BY clause, and the selected virtual table index
|
| + ** does not satisfy it, increase the cost of the scan accordingly. This
|
| + ** matches the processing for non-virtual tables in bestBtreeIndex().
|
| + */
|
| + rCost = pIdxInfo->estimatedCost;
|
| + if( pOrderBy && pIdxInfo->orderByConsumed==0 ){
|
| + rCost += estLog(rCost)*rCost;
|
| + }
|
| +
|
| + /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
|
| + ** inital value of lowestCost in this loop. If it is, then the
|
| + ** (cost<lowestCost) test below will never be true.
|
| + **
|
| + ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
|
| + ** is defined.
|
| + */
|
| + if( (SQLITE_BIG_DBL/((double)2))<rCost ){
|
| + pCost->rCost = (SQLITE_BIG_DBL/((double)2));
|
| + }else{
|
| + pCost->rCost = rCost;
|
| + }
|
| + pCost->plan.u.pVtabIdx = pIdxInfo;
|
| + if( pIdxInfo->orderByConsumed ){
|
| + pCost->plan.wsFlags |= WHERE_ORDERBY;
|
| + }
|
| + pCost->plan.nEq = 0;
|
| + pIdxInfo->nOrderBy = nOrderBy;
|
| +
|
| + /* Try to find a more efficient access pattern by using multiple indexes
|
| + ** to optimize an OR expression within the WHERE clause.
|
| + */
|
| + bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
|
| +}
|
| +#endif /* SQLITE_OMIT_VIRTUALTABLE */
|
| +
|
| +/*
|
| +** Argument pIdx is a pointer to an index structure that has an array of
|
| +** SQLITE_INDEX_SAMPLES evenly spaced samples of the first indexed column
|
| +** stored in Index.aSample. These samples divide the domain of values stored
|
| +** the index into (SQLITE_INDEX_SAMPLES+1) regions.
|
| +** Region 0 contains all values less than the first sample value. Region
|
| +** 1 contains values between the first and second samples. Region 2 contains
|
| +** values between samples 2 and 3. And so on. Region SQLITE_INDEX_SAMPLES
|
| +** contains values larger than the last sample.
|
| +**
|
| +** If the index contains many duplicates of a single value, then it is
|
| +** possible that two or more adjacent samples can hold the same value.
|
| +** When that is the case, the smallest possible region code is returned
|
| +** when roundUp is false and the largest possible region code is returned
|
| +** when roundUp is true.
|
| +**
|
| +** If successful, this function determines which of the regions value
|
| +** pVal lies in, sets *piRegion to the region index (a value between 0
|
| +** and SQLITE_INDEX_SAMPLES+1, inclusive) and returns SQLITE_OK.
|
| +** Or, if an OOM occurs while converting text values between encodings,
|
| +** SQLITE_NOMEM is returned and *piRegion is undefined.
|
| +*/
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +static int whereRangeRegion(
|
| + Parse *pParse, /* Database connection */
|
| + Index *pIdx, /* Index to consider domain of */
|
| + sqlite3_value *pVal, /* Value to consider */
|
| + int roundUp, /* Return largest valid region if true */
|
| + int *piRegion /* OUT: Region of domain in which value lies */
|
| +){
|
| + assert( roundUp==0 || roundUp==1 );
|
| + if( ALWAYS(pVal) ){
|
| + IndexSample *aSample = pIdx->aSample;
|
| + int i = 0;
|
| + int eType = sqlite3_value_type(pVal);
|
| +
|
| + if( eType==SQLITE_INTEGER || eType==SQLITE_FLOAT ){
|
| + double r = sqlite3_value_double(pVal);
|
| + for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
|
| + if( aSample[i].eType==SQLITE_NULL ) continue;
|
| + if( aSample[i].eType>=SQLITE_TEXT ) break;
|
| + if( roundUp ){
|
| + if( aSample[i].u.r>r ) break;
|
| + }else{
|
| + if( aSample[i].u.r>=r ) break;
|
| + }
|
| + }
|
| + }else if( eType==SQLITE_NULL ){
|
| + i = 0;
|
| + if( roundUp ){
|
| + while( i<SQLITE_INDEX_SAMPLES && aSample[i].eType==SQLITE_NULL ) i++;
|
| + }
|
| + }else{
|
| + sqlite3 *db = pParse->db;
|
| + CollSeq *pColl;
|
| + const u8 *z;
|
| + int n;
|
| +
|
| + /* pVal comes from sqlite3ValueFromExpr() so the type cannot be NULL */
|
| + assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
|
| +
|
| + if( eType==SQLITE_BLOB ){
|
| + z = (const u8 *)sqlite3_value_blob(pVal);
|
| + pColl = db->pDfltColl;
|
| + assert( pColl->enc==SQLITE_UTF8 );
|
| + }else{
|
| + pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
|
| + if( pColl==0 ){
|
| + sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
|
| + *pIdx->azColl);
|
| + return SQLITE_ERROR;
|
| + }
|
| + z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
|
| + if( !z ){
|
| + return SQLITE_NOMEM;
|
| + }
|
| + assert( z && pColl && pColl->xCmp );
|
| + }
|
| + n = sqlite3ValueBytes(pVal, pColl->enc);
|
| +
|
| + for(i=0; i<SQLITE_INDEX_SAMPLES; i++){
|
| + int c;
|
| + int eSampletype = aSample[i].eType;
|
| + if( eSampletype==SQLITE_NULL || eSampletype<eType ) continue;
|
| + if( (eSampletype!=eType) ) break;
|
| +#ifndef SQLITE_OMIT_UTF16
|
| + if( pColl->enc!=SQLITE_UTF8 ){
|
| + int nSample;
|
| + char *zSample = sqlite3Utf8to16(
|
| + db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
|
| + );
|
| + if( !zSample ){
|
| + assert( db->mallocFailed );
|
| + return SQLITE_NOMEM;
|
| + }
|
| + c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
|
| + sqlite3DbFree(db, zSample);
|
| + }else
|
| +#endif
|
| + {
|
| + c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
|
| + }
|
| + if( c-roundUp>=0 ) break;
|
| + }
|
| + }
|
| +
|
| + assert( i>=0 && i<=SQLITE_INDEX_SAMPLES );
|
| + *piRegion = i;
|
| + }
|
| + return SQLITE_OK;
|
| +}
|
| +#endif /* #ifdef SQLITE_ENABLE_STAT2 */
|
| +
|
| +/*
|
| +** If expression pExpr represents a literal value, set *pp to point to
|
| +** an sqlite3_value structure containing the same value, with affinity
|
| +** aff applied to it, before returning. It is the responsibility of the
|
| +** caller to eventually release this structure by passing it to
|
| +** sqlite3ValueFree().
|
| +**
|
| +** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
|
| +** is an SQL variable that currently has a non-NULL value bound to it,
|
| +** create an sqlite3_value structure containing this value, again with
|
| +** affinity aff applied to it, instead.
|
| +**
|
| +** If neither of the above apply, set *pp to NULL.
|
| +**
|
| +** If an error occurs, return an error code. Otherwise, SQLITE_OK.
|
| +*/
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +static int valueFromExpr(
|
| + Parse *pParse,
|
| + Expr *pExpr,
|
| + u8 aff,
|
| + sqlite3_value **pp
|
| +){
|
| + if( pExpr->op==TK_VARIABLE
|
| + || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
|
| + ){
|
| + int iVar = pExpr->iColumn;
|
| + sqlite3VdbeSetVarmask(pParse->pVdbe, iVar); /* IMP: R-23257-02778 */
|
| + *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
|
| + return SQLITE_OK;
|
| + }
|
| + return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
|
| +}
|
| +#endif
|
| +
|
| +/*
|
| +** This function is used to estimate the number of rows that will be visited
|
| +** by scanning an index for a range of values. The range may have an upper
|
| +** bound, a lower bound, or both. The WHERE clause terms that set the upper
|
| +** and lower bounds are represented by pLower and pUpper respectively. For
|
| +** example, assuming that index p is on t1(a):
|
| +**
|
| +** ... FROM t1 WHERE a > ? AND a < ? ...
|
| +** |_____| |_____|
|
| +** | |
|
| +** pLower pUpper
|
| +**
|
| +** If either of the upper or lower bound is not present, then NULL is passed in
|
| +** place of the corresponding WhereTerm.
|
| +**
|
| +** The nEq parameter is passed the index of the index column subject to the
|
| +** range constraint. Or, equivalently, the number of equality constraints
|
| +** optimized by the proposed index scan. For example, assuming index p is
|
| +** on t1(a, b), and the SQL query is:
|
| +**
|
| +** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
|
| +**
|
| +** then nEq should be passed the value 1 (as the range restricted column,
|
| +** b, is the second left-most column of the index). Or, if the query is:
|
| +**
|
| +** ... FROM t1 WHERE a > ? AND a < ? ...
|
| +**
|
| +** then nEq should be passed 0.
|
| +**
|
| +** The returned value is an integer between 1 and 100, inclusive. A return
|
| +** value of 1 indicates that the proposed range scan is expected to visit
|
| +** approximately 1/100th (1%) of the rows selected by the nEq equality
|
| +** constraints (if any). A return value of 100 indicates that it is expected
|
| +** that the range scan will visit every row (100%) selected by the equality
|
| +** constraints.
|
| +**
|
| +** In the absence of sqlite_stat2 ANALYZE data, each range inequality
|
| +** reduces the search space by 3/4ths. Hence a single constraint (x>?)
|
| +** results in a return of 25 and a range constraint (x>? AND x<?) results
|
| +** in a return of 6.
|
| +*/
|
| +static int whereRangeScanEst(
|
| + Parse *pParse, /* Parsing & code generating context */
|
| + Index *p, /* The index containing the range-compared column; "x" */
|
| + int nEq, /* index into p->aCol[] of the range-compared column */
|
| + WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */
|
| + WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */
|
| + int *piEst /* OUT: Return value */
|
| +){
|
| + int rc = SQLITE_OK;
|
| +
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +
|
| + if( nEq==0 && p->aSample ){
|
| + sqlite3_value *pLowerVal = 0;
|
| + sqlite3_value *pUpperVal = 0;
|
| + int iEst;
|
| + int iLower = 0;
|
| + int iUpper = SQLITE_INDEX_SAMPLES;
|
| + int roundUpUpper = 0;
|
| + int roundUpLower = 0;
|
| + u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
|
| +
|
| + if( pLower ){
|
| + Expr *pExpr = pLower->pExpr->pRight;
|
| + rc = valueFromExpr(pParse, pExpr, aff, &pLowerVal);
|
| + assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
|
| + roundUpLower = (pLower->eOperator==WO_GT) ?1:0;
|
| + }
|
| + if( rc==SQLITE_OK && pUpper ){
|
| + Expr *pExpr = pUpper->pExpr->pRight;
|
| + rc = valueFromExpr(pParse, pExpr, aff, &pUpperVal);
|
| + assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
|
| + roundUpUpper = (pUpper->eOperator==WO_LE) ?1:0;
|
| + }
|
| +
|
| + if( rc!=SQLITE_OK || (pLowerVal==0 && pUpperVal==0) ){
|
| + sqlite3ValueFree(pLowerVal);
|
| + sqlite3ValueFree(pUpperVal);
|
| + goto range_est_fallback;
|
| + }else if( pLowerVal==0 ){
|
| + rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
|
| + if( pLower ) iLower = iUpper/2;
|
| + }else if( pUpperVal==0 ){
|
| + rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
|
| + if( pUpper ) iUpper = (iLower + SQLITE_INDEX_SAMPLES + 1)/2;
|
| + }else{
|
| + rc = whereRangeRegion(pParse, p, pUpperVal, roundUpUpper, &iUpper);
|
| + if( rc==SQLITE_OK ){
|
| + rc = whereRangeRegion(pParse, p, pLowerVal, roundUpLower, &iLower);
|
| + }
|
| + }
|
| + WHERETRACE(("range scan regions: %d..%d\n", iLower, iUpper));
|
| +
|
| + iEst = iUpper - iLower;
|
| + testcase( iEst==SQLITE_INDEX_SAMPLES );
|
| + assert( iEst<=SQLITE_INDEX_SAMPLES );
|
| + if( iEst<1 ){
|
| + *piEst = 50/SQLITE_INDEX_SAMPLES;
|
| + }else{
|
| + *piEst = (iEst*100)/SQLITE_INDEX_SAMPLES;
|
| + }
|
| + sqlite3ValueFree(pLowerVal);
|
| + sqlite3ValueFree(pUpperVal);
|
| + return rc;
|
| + }
|
| +range_est_fallback:
|
| +#else
|
| + UNUSED_PARAMETER(pParse);
|
| + UNUSED_PARAMETER(p);
|
| + UNUSED_PARAMETER(nEq);
|
| +#endif
|
| + assert( pLower || pUpper );
|
| + *piEst = 100;
|
| + if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 4;
|
| + if( pUpper ) *piEst /= 4;
|
| + return rc;
|
| +}
|
| +
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +/*
|
| +** Estimate the number of rows that will be returned based on
|
| +** an equality constraint x=VALUE and where that VALUE occurs in
|
| +** the histogram data. This only works when x is the left-most
|
| +** column of an index and sqlite_stat2 histogram data is available
|
| +** for that index. When pExpr==NULL that means the constraint is
|
| +** "x IS NULL" instead of "x=VALUE".
|
| +**
|
| +** Write the estimated row count into *pnRow and return SQLITE_OK.
|
| +** If unable to make an estimate, leave *pnRow unchanged and return
|
| +** non-zero.
|
| +**
|
| +** This routine can fail if it is unable to load a collating sequence
|
| +** required for string comparison, or if unable to allocate memory
|
| +** for a UTF conversion required for comparison. The error is stored
|
| +** in the pParse structure.
|
| +*/
|
| +static int whereEqualScanEst(
|
| + Parse *pParse, /* Parsing & code generating context */
|
| + Index *p, /* The index whose left-most column is pTerm */
|
| + Expr *pExpr, /* Expression for VALUE in the x=VALUE constraint */
|
| + double *pnRow /* Write the revised row estimate here */
|
| +){
|
| + sqlite3_value *pRhs = 0; /* VALUE on right-hand side of pTerm */
|
| + int iLower, iUpper; /* Range of histogram regions containing pRhs */
|
| + u8 aff; /* Column affinity */
|
| + int rc; /* Subfunction return code */
|
| + double nRowEst; /* New estimate of the number of rows */
|
| +
|
| + assert( p->aSample!=0 );
|
| + aff = p->pTable->aCol[p->aiColumn[0]].affinity;
|
| + if( pExpr ){
|
| + rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
|
| + if( rc ) goto whereEqualScanEst_cancel;
|
| + }else{
|
| + pRhs = sqlite3ValueNew(pParse->db);
|
| + }
|
| + if( pRhs==0 ) return SQLITE_NOTFOUND;
|
| + rc = whereRangeRegion(pParse, p, pRhs, 0, &iLower);
|
| + if( rc ) goto whereEqualScanEst_cancel;
|
| + rc = whereRangeRegion(pParse, p, pRhs, 1, &iUpper);
|
| + if( rc ) goto whereEqualScanEst_cancel;
|
| + WHERETRACE(("equality scan regions: %d..%d\n", iLower, iUpper));
|
| + if( iLower>=iUpper ){
|
| + nRowEst = p->aiRowEst[0]/(SQLITE_INDEX_SAMPLES*2);
|
| + if( nRowEst<*pnRow ) *pnRow = nRowEst;
|
| + }else{
|
| + nRowEst = (iUpper-iLower)*p->aiRowEst[0]/SQLITE_INDEX_SAMPLES;
|
| + *pnRow = nRowEst;
|
| + }
|
| +
|
| +whereEqualScanEst_cancel:
|
| + sqlite3ValueFree(pRhs);
|
| + return rc;
|
| +}
|
| +#endif /* defined(SQLITE_ENABLE_STAT2) */
|
| +
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| +/*
|
| +** Estimate the number of rows that will be returned based on
|
| +** an IN constraint where the right-hand side of the IN operator
|
| +** is a list of values. Example:
|
| +**
|
| +** WHERE x IN (1,2,3,4)
|
| +**
|
| +** Write the estimated row count into *pnRow and return SQLITE_OK.
|
| +** If unable to make an estimate, leave *pnRow unchanged and return
|
| +** non-zero.
|
| +**
|
| +** This routine can fail if it is unable to load a collating sequence
|
| +** required for string comparison, or if unable to allocate memory
|
| +** for a UTF conversion required for comparison. The error is stored
|
| +** in the pParse structure.
|
| +*/
|
| +static int whereInScanEst(
|
| + Parse *pParse, /* Parsing & code generating context */
|
| + Index *p, /* The index whose left-most column is pTerm */
|
| + ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
|
| + double *pnRow /* Write the revised row estimate here */
|
| +){
|
| + sqlite3_value *pVal = 0; /* One value from list */
|
| + int iLower, iUpper; /* Range of histogram regions containing pRhs */
|
| + u8 aff; /* Column affinity */
|
| + int rc = SQLITE_OK; /* Subfunction return code */
|
| + double nRowEst; /* New estimate of the number of rows */
|
| + int nSpan = 0; /* Number of histogram regions spanned */
|
| + int nSingle = 0; /* Histogram regions hit by a single value */
|
| + int nNotFound = 0; /* Count of values that are not constants */
|
| + int i; /* Loop counter */
|
| + u8 aSpan[SQLITE_INDEX_SAMPLES+1]; /* Histogram regions that are spanned */
|
| + u8 aSingle[SQLITE_INDEX_SAMPLES+1]; /* Histogram regions hit once */
|
| +
|
| + assert( p->aSample!=0 );
|
| + aff = p->pTable->aCol[p->aiColumn[0]].affinity;
|
| + memset(aSpan, 0, sizeof(aSpan));
|
| + memset(aSingle, 0, sizeof(aSingle));
|
| + for(i=0; i<pList->nExpr; i++){
|
| + sqlite3ValueFree(pVal);
|
| + rc = valueFromExpr(pParse, pList->a[i].pExpr, aff, &pVal);
|
| + if( rc ) break;
|
| + if( pVal==0 || sqlite3_value_type(pVal)==SQLITE_NULL ){
|
| + nNotFound++;
|
| + continue;
|
| + }
|
| + rc = whereRangeRegion(pParse, p, pVal, 0, &iLower);
|
| + if( rc ) break;
|
| + rc = whereRangeRegion(pParse, p, pVal, 1, &iUpper);
|
| + if( rc ) break;
|
| + if( iLower>=iUpper ){
|
| + aSingle[iLower] = 1;
|
| + }else{
|
| + assert( iLower>=0 && iUpper<=SQLITE_INDEX_SAMPLES );
|
| + while( iLower<iUpper ) aSpan[iLower++] = 1;
|
| + }
|
| + }
|
| + if( rc==SQLITE_OK ){
|
| + for(i=nSpan=0; i<=SQLITE_INDEX_SAMPLES; i++){
|
| + if( aSpan[i] ){
|
| + nSpan++;
|
| + }else if( aSingle[i] ){
|
| + nSingle++;
|
| + }
|
| + }
|
| + nRowEst = (nSpan*2+nSingle)*p->aiRowEst[0]/(2*SQLITE_INDEX_SAMPLES)
|
| + + nNotFound*p->aiRowEst[1];
|
| + if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
|
| + *pnRow = nRowEst;
|
| + WHERETRACE(("IN row estimate: nSpan=%d, nSingle=%d, nNotFound=%d, est=%g\n",
|
| + nSpan, nSingle, nNotFound, nRowEst));
|
| + }
|
| + sqlite3ValueFree(pVal);
|
| + return rc;
|
| +}
|
| +#endif /* defined(SQLITE_ENABLE_STAT2) */
|
| +
|
| +
|
| +/*
|
| +** Find the best query plan for accessing a particular table. Write the
|
| +** best query plan and its cost into the WhereCost object supplied as the
|
| +** last parameter.
|
| +**
|
| +** The lowest cost plan wins. The cost is an estimate of the amount of
|
| +** CPU and disk I/O needed to process the requested result.
|
| +** Factors that influence cost include:
|
| +**
|
| +** * The estimated number of rows that will be retrieved. (The
|
| +** fewer the better.)
|
| +**
|
| +** * Whether or not sorting must occur.
|
| +**
|
| +** * Whether or not there must be separate lookups in the
|
| +** index and in the main table.
|
| +**
|
| +** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
|
| +** the SQL statement, then this function only considers plans using the
|
| +** named index. If no such plan is found, then the returned cost is
|
| +** SQLITE_BIG_DBL. If a plan is found that uses the named index,
|
| +** then the cost is calculated in the usual way.
|
| +**
|
| +** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
|
| +** in the SELECT statement, then no indexes are considered. However, the
|
| +** selected plan may still take advantage of the built-in rowid primary key
|
| +** index.
|
| +*/
|
| +static void bestBtreeIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to search */
|
| + Bitmask notReady, /* Mask of cursors not available for indexing */
|
| + Bitmask notValid, /* Cursors not available for any purpose */
|
| + ExprList *pOrderBy, /* The ORDER BY clause */
|
| + WhereCost *pCost /* Lowest cost query plan */
|
| +){
|
| + int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
|
| + Index *pProbe; /* An index we are evaluating */
|
| + Index *pIdx; /* Copy of pProbe, or zero for IPK index */
|
| + int eqTermMask; /* Current mask of valid equality operators */
|
| + int idxEqTermMask; /* Index mask of valid equality operators */
|
| + Index sPk; /* A fake index object for the primary key */
|
| + unsigned int aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
|
| + int aiColumnPk = -1; /* The aColumn[] value for the sPk index */
|
| + int wsFlagMask; /* Allowed flags in pCost->plan.wsFlag */
|
| +
|
| + /* Initialize the cost to a worst-case value */
|
| + memset(pCost, 0, sizeof(*pCost));
|
| + pCost->rCost = SQLITE_BIG_DBL;
|
| +
|
| + /* If the pSrc table is the right table of a LEFT JOIN then we may not
|
| + ** use an index to satisfy IS NULL constraints on that table. This is
|
| + ** because columns might end up being NULL if the table does not match -
|
| + ** a circumstance which the index cannot help us discover. Ticket #2177.
|
| + */
|
| + if( pSrc->jointype & JT_LEFT ){
|
| + idxEqTermMask = WO_EQ|WO_IN;
|
| + }else{
|
| + idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
|
| + }
|
| +
|
| + if( pSrc->pIndex ){
|
| + /* An INDEXED BY clause specifies a particular index to use */
|
| + pIdx = pProbe = pSrc->pIndex;
|
| + wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
|
| + eqTermMask = idxEqTermMask;
|
| + }else{
|
| + /* There is no INDEXED BY clause. Create a fake Index object in local
|
| + ** variable sPk to represent the rowid primary key index. Make this
|
| + ** fake index the first in a chain of Index objects with all of the real
|
| + ** indices to follow */
|
| + Index *pFirst; /* First of real indices on the table */
|
| + memset(&sPk, 0, sizeof(Index));
|
| + sPk.nColumn = 1;
|
| + sPk.aiColumn = &aiColumnPk;
|
| + sPk.aiRowEst = aiRowEstPk;
|
| + sPk.onError = OE_Replace;
|
| + sPk.pTable = pSrc->pTab;
|
| + aiRowEstPk[0] = pSrc->pTab->nRowEst;
|
| + aiRowEstPk[1] = 1;
|
| + pFirst = pSrc->pTab->pIndex;
|
| + if( pSrc->notIndexed==0 ){
|
| + /* The real indices of the table are only considered if the
|
| + ** NOT INDEXED qualifier is omitted from the FROM clause */
|
| + sPk.pNext = pFirst;
|
| + }
|
| + pProbe = &sPk;
|
| + wsFlagMask = ~(
|
| + WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
|
| + );
|
| + eqTermMask = WO_EQ|WO_IN;
|
| + pIdx = 0;
|
| + }
|
| +
|
| + /* Loop over all indices looking for the best one to use
|
| + */
|
| + for(; pProbe; pIdx=pProbe=pProbe->pNext){
|
| + const unsigned int * const aiRowEst = pProbe->aiRowEst;
|
| + double cost; /* Cost of using pProbe */
|
| + double nRow; /* Estimated number of rows in result set */
|
| + double log10N; /* base-10 logarithm of nRow (inexact) */
|
| + int rev; /* True to scan in reverse order */
|
| + int wsFlags = 0;
|
| + Bitmask used = 0;
|
| +
|
| + /* The following variables are populated based on the properties of
|
| + ** index being evaluated. They are then used to determine the expected
|
| + ** cost and number of rows returned.
|
| + **
|
| + ** nEq:
|
| + ** Number of equality terms that can be implemented using the index.
|
| + ** In other words, the number of initial fields in the index that
|
| + ** are used in == or IN or NOT NULL constraints of the WHERE clause.
|
| + **
|
| + ** nInMul:
|
| + ** The "in-multiplier". This is an estimate of how many seek operations
|
| + ** SQLite must perform on the index in question. For example, if the
|
| + ** WHERE clause is:
|
| + **
|
| + ** WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
|
| + **
|
| + ** SQLite must perform 9 lookups on an index on (a, b), so nInMul is
|
| + ** set to 9. Given the same schema and either of the following WHERE
|
| + ** clauses:
|
| + **
|
| + ** WHERE a = 1
|
| + ** WHERE a >= 2
|
| + **
|
| + ** nInMul is set to 1.
|
| + **
|
| + ** If there exists a WHERE term of the form "x IN (SELECT ...)", then
|
| + ** the sub-select is assumed to return 25 rows for the purposes of
|
| + ** determining nInMul.
|
| + **
|
| + ** bInEst:
|
| + ** Set to true if there was at least one "x IN (SELECT ...)" term used
|
| + ** in determining the value of nInMul. Note that the RHS of the
|
| + ** IN operator must be a SELECT, not a value list, for this variable
|
| + ** to be true.
|
| + **
|
| + ** estBound:
|
| + ** An estimate on the amount of the table that must be searched. A
|
| + ** value of 100 means the entire table is searched. Range constraints
|
| + ** might reduce this to a value less than 100 to indicate that only
|
| + ** a fraction of the table needs searching. In the absence of
|
| + ** sqlite_stat2 ANALYZE data, a single inequality reduces the search
|
| + ** space to 1/4rd its original size. So an x>? constraint reduces
|
| + ** estBound to 25. Two constraints (x>? AND x<?) reduce estBound to 6.
|
| + **
|
| + ** bSort:
|
| + ** Boolean. True if there is an ORDER BY clause that will require an
|
| + ** external sort (i.e. scanning the index being evaluated will not
|
| + ** correctly order records).
|
| + **
|
| + ** bLookup:
|
| + ** Boolean. True if a table lookup is required for each index entry
|
| + ** visited. In other words, true if this is not a covering index.
|
| + ** This is always false for the rowid primary key index of a table.
|
| + ** For other indexes, it is true unless all the columns of the table
|
| + ** used by the SELECT statement are present in the index (such an
|
| + ** index is sometimes described as a covering index).
|
| + ** For example, given the index on (a, b), the second of the following
|
| + ** two queries requires table b-tree lookups in order to find the value
|
| + ** of column c, but the first does not because columns a and b are
|
| + ** both available in the index.
|
| + **
|
| + ** SELECT a, b FROM tbl WHERE a = 1;
|
| + ** SELECT a, b, c FROM tbl WHERE a = 1;
|
| + */
|
| + int nEq; /* Number of == or IN terms matching index */
|
| + int bInEst = 0; /* True if "x IN (SELECT...)" seen */
|
| + int nInMul = 1; /* Number of distinct equalities to lookup */
|
| + int estBound = 100; /* Estimated reduction in search space */
|
| + int nBound = 0; /* Number of range constraints seen */
|
| + int bSort = 0; /* True if external sort required */
|
| + int bLookup = 0; /* True if not a covering index */
|
| + WhereTerm *pTerm; /* A single term of the WHERE clause */
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| + WhereTerm *pFirstTerm = 0; /* First term matching the index */
|
| +#endif
|
| +
|
| + /* Determine the values of nEq and nInMul */
|
| + for(nEq=0; nEq<pProbe->nColumn; nEq++){
|
| + int j = pProbe->aiColumn[nEq];
|
| + pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
|
| + if( pTerm==0 ) break;
|
| + wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
|
| + if( pTerm->eOperator & WO_IN ){
|
| + Expr *pExpr = pTerm->pExpr;
|
| + wsFlags |= WHERE_COLUMN_IN;
|
| + if( ExprHasProperty(pExpr, EP_xIsSelect) ){
|
| + /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */
|
| + nInMul *= 25;
|
| + bInEst = 1;
|
| + }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
|
| + /* "x IN (value, value, ...)" */
|
| + nInMul *= pExpr->x.pList->nExpr;
|
| + }
|
| + }else if( pTerm->eOperator & WO_ISNULL ){
|
| + wsFlags |= WHERE_COLUMN_NULL;
|
| + }
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| + if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
|
| +#endif
|
| + used |= pTerm->prereqRight;
|
| + }
|
| +
|
| + /* Determine the value of estBound. */
|
| + if( nEq<pProbe->nColumn && pProbe->bUnordered==0 ){
|
| + int j = pProbe->aiColumn[nEq];
|
| + if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
|
| + WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
|
| + WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
|
| + whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &estBound);
|
| + if( pTop ){
|
| + nBound = 1;
|
| + wsFlags |= WHERE_TOP_LIMIT;
|
| + used |= pTop->prereqRight;
|
| + }
|
| + if( pBtm ){
|
| + nBound++;
|
| + wsFlags |= WHERE_BTM_LIMIT;
|
| + used |= pBtm->prereqRight;
|
| + }
|
| + wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
|
| + }
|
| + }else if( pProbe->onError!=OE_None ){
|
| + testcase( wsFlags & WHERE_COLUMN_IN );
|
| + testcase( wsFlags & WHERE_COLUMN_NULL );
|
| + if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
|
| + wsFlags |= WHERE_UNIQUE;
|
| + }
|
| + }
|
| +
|
| + /* If there is an ORDER BY clause and the index being considered will
|
| + ** naturally scan rows in the required order, set the appropriate flags
|
| + ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
|
| + ** will scan rows in a different order, set the bSort variable. */
|
| + if( pOrderBy ){
|
| + if( (wsFlags & WHERE_COLUMN_IN)==0
|
| + && pProbe->bUnordered==0
|
| + && isSortingIndex(pParse, pWC->pMaskSet, pProbe, iCur, pOrderBy,
|
| + nEq, wsFlags, &rev)
|
| + ){
|
| + wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
|
| + wsFlags |= (rev ? WHERE_REVERSE : 0);
|
| + }else{
|
| + bSort = 1;
|
| + }
|
| + }
|
| +
|
| + /* If currently calculating the cost of using an index (not the IPK
|
| + ** index), determine if all required column data may be obtained without
|
| + ** using the main table (i.e. if the index is a covering
|
| + ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
|
| + ** wsFlags. Otherwise, set the bLookup variable to true. */
|
| + if( pIdx && wsFlags ){
|
| + Bitmask m = pSrc->colUsed;
|
| + int j;
|
| + for(j=0; j<pIdx->nColumn; j++){
|
| + int x = pIdx->aiColumn[j];
|
| + if( x<BMS-1 ){
|
| + m &= ~(((Bitmask)1)<<x);
|
| + }
|
| + }
|
| + if( m==0 ){
|
| + wsFlags |= WHERE_IDX_ONLY;
|
| + }else{
|
| + bLookup = 1;
|
| + }
|
| + }
|
| +
|
| + /*
|
| + ** Estimate the number of rows of output. For an "x IN (SELECT...)"
|
| + ** constraint, do not let the estimate exceed half the rows in the table.
|
| + */
|
| + nRow = (double)(aiRowEst[nEq] * nInMul);
|
| + if( bInEst && nRow*2>aiRowEst[0] ){
|
| + nRow = aiRowEst[0]/2;
|
| + nInMul = (int)(nRow / aiRowEst[nEq]);
|
| + }
|
| +
|
| +#ifdef SQLITE_ENABLE_STAT2
|
| + /* If the constraint is of the form x=VALUE and histogram
|
| + ** data is available for column x, then it might be possible
|
| + ** to get a better estimate on the number of rows based on
|
| + ** VALUE and how common that value is according to the histogram.
|
| + */
|
| + if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 ){
|
| + if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
|
| + testcase( pFirstTerm->eOperator==WO_EQ );
|
| + testcase( pFirstTerm->eOperator==WO_ISNULL );
|
| + whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
|
| + }else if( pFirstTerm->eOperator==WO_IN && bInEst==0 ){
|
| + whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
|
| + }
|
| + }
|
| +#endif /* SQLITE_ENABLE_STAT2 */
|
| +
|
| + /* Adjust the number of output rows and downward to reflect rows
|
| + ** that are excluded by range constraints.
|
| + */
|
| + nRow = (nRow * (double)estBound) / (double)100;
|
| + if( nRow<1 ) nRow = 1;
|
| +
|
| + /* Experiments run on real SQLite databases show that the time needed
|
| + ** to do a binary search to locate a row in a table or index is roughly
|
| + ** log10(N) times the time to move from one row to the next row within
|
| + ** a table or index. The actual times can vary, with the size of
|
| + ** records being an important factor. Both moves and searches are
|
| + ** slower with larger records, presumably because fewer records fit
|
| + ** on one page and hence more pages have to be fetched.
|
| + **
|
| + ** The ANALYZE command and the sqlite_stat1 and sqlite_stat2 tables do
|
| + ** not give us data on the relative sizes of table and index records.
|
| + ** So this computation assumes table records are about twice as big
|
| + ** as index records
|
| + */
|
| + if( (wsFlags & WHERE_NOT_FULLSCAN)==0 ){
|
| + /* The cost of a full table scan is a number of move operations equal
|
| + ** to the number of rows in the table.
|
| + **
|
| + ** We add an additional 4x penalty to full table scans. This causes
|
| + ** the cost function to err on the side of choosing an index over
|
| + ** choosing a full scan. This 4x full-scan penalty is an arguable
|
| + ** decision and one which we expect to revisit in the future. But
|
| + ** it seems to be working well enough at the moment.
|
| + */
|
| + cost = aiRowEst[0]*4;
|
| + }else{
|
| + log10N = estLog(aiRowEst[0]);
|
| + cost = nRow;
|
| + if( pIdx ){
|
| + if( bLookup ){
|
| + /* For an index lookup followed by a table lookup:
|
| + ** nInMul index searches to find the start of each index range
|
| + ** + nRow steps through the index
|
| + ** + nRow table searches to lookup the table entry using the rowid
|
| + */
|
| + cost += (nInMul + nRow)*log10N;
|
| + }else{
|
| + /* For a covering index:
|
| + ** nInMul index searches to find the initial entry
|
| + ** + nRow steps through the index
|
| + */
|
| + cost += nInMul*log10N;
|
| + }
|
| + }else{
|
| + /* For a rowid primary key lookup:
|
| + ** nInMult table searches to find the initial entry for each range
|
| + ** + nRow steps through the table
|
| + */
|
| + cost += nInMul*log10N;
|
| + }
|
| + }
|
| +
|
| + /* Add in the estimated cost of sorting the result. Actual experimental
|
| + ** measurements of sorting performance in SQLite show that sorting time
|
| + ** adds C*N*log10(N) to the cost, where N is the number of rows to be
|
| + ** sorted and C is a factor between 1.95 and 4.3. We will split the
|
| + ** difference and select C of 3.0.
|
| + */
|
| + if( bSort ){
|
| + cost += nRow*estLog(nRow)*3;
|
| + }
|
| +
|
| + /**** Cost of using this index has now been computed ****/
|
| +
|
| + /* If there are additional constraints on this table that cannot
|
| + ** be used with the current index, but which might lower the number
|
| + ** of output rows, adjust the nRow value accordingly. This only
|
| + ** matters if the current index is the least costly, so do not bother
|
| + ** with this step if we already know this index will not be chosen.
|
| + ** Also, never reduce the output row count below 2 using this step.
|
| + **
|
| + ** It is critical that the notValid mask be used here instead of
|
| + ** the notReady mask. When computing an "optimal" index, the notReady
|
| + ** mask will only have one bit set - the bit for the current table.
|
| + ** The notValid mask, on the other hand, always has all bits set for
|
| + ** tables that are not in outer loops. If notReady is used here instead
|
| + ** of notValid, then a optimal index that depends on inner joins loops
|
| + ** might be selected even when there exists an optimal index that has
|
| + ** no such dependency.
|
| + */
|
| + if( nRow>2 && cost<=pCost->rCost ){
|
| + int k; /* Loop counter */
|
| + int nSkipEq = nEq; /* Number of == constraints to skip */
|
| + int nSkipRange = nBound; /* Number of < constraints to skip */
|
| + Bitmask thisTab; /* Bitmap for pSrc */
|
| +
|
| + thisTab = getMask(pWC->pMaskSet, iCur);
|
| + for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
|
| + if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
|
| + if( (pTerm->prereqAll & notValid)!=thisTab ) continue;
|
| + if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
|
| + if( nSkipEq ){
|
| + /* Ignore the first nEq equality matches since the index
|
| + ** has already accounted for these */
|
| + nSkipEq--;
|
| + }else{
|
| + /* Assume each additional equality match reduces the result
|
| + ** set size by a factor of 10 */
|
| + nRow /= 10;
|
| + }
|
| + }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
|
| + if( nSkipRange ){
|
| + /* Ignore the first nSkipRange range constraints since the index
|
| + ** has already accounted for these */
|
| + nSkipRange--;
|
| + }else{
|
| + /* Assume each additional range constraint reduces the result
|
| + ** set size by a factor of 3. Indexed range constraints reduce
|
| + ** the search space by a larger factor: 4. We make indexed range
|
| + ** more selective intentionally because of the subjective
|
| + ** observation that indexed range constraints really are more
|
| + ** selective in practice, on average. */
|
| + nRow /= 3;
|
| + }
|
| + }else if( pTerm->eOperator!=WO_NOOP ){
|
| + /* Any other expression lowers the output row count by half */
|
| + nRow /= 2;
|
| + }
|
| + }
|
| + if( nRow<2 ) nRow = 2;
|
| + }
|
| +
|
| +
|
| + WHERETRACE((
|
| + "%s(%s): nEq=%d nInMul=%d estBound=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
|
| + " notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
|
| + pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),
|
| + nEq, nInMul, estBound, bSort, bLookup, wsFlags,
|
| + notReady, log10N, nRow, cost, used
|
| + ));
|
| +
|
| + /* If this index is the best we have seen so far, then record this
|
| + ** index and its cost in the pCost structure.
|
| + */
|
| + if( (!pIdx || wsFlags)
|
| + && (cost<pCost->rCost || (cost<=pCost->rCost && nRow<pCost->plan.nRow))
|
| + ){
|
| + pCost->rCost = cost;
|
| + pCost->used = used;
|
| + pCost->plan.nRow = nRow;
|
| + pCost->plan.wsFlags = (wsFlags&wsFlagMask);
|
| + pCost->plan.nEq = nEq;
|
| + pCost->plan.u.pIdx = pIdx;
|
| + }
|
| +
|
| + /* If there was an INDEXED BY clause, then only that one index is
|
| + ** considered. */
|
| + if( pSrc->pIndex ) break;
|
| +
|
| + /* Reset masks for the next index in the loop */
|
| + wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
|
| + eqTermMask = idxEqTermMask;
|
| + }
|
| +
|
| + /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
|
| + ** is set, then reverse the order that the index will be scanned
|
| + ** in. This is used for application testing, to help find cases
|
| + ** where application behaviour depends on the (undefined) order that
|
| + ** SQLite outputs rows in in the absence of an ORDER BY clause. */
|
| + if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
|
| + pCost->plan.wsFlags |= WHERE_REVERSE;
|
| + }
|
| +
|
| + assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
|
| + assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
|
| + assert( pSrc->pIndex==0
|
| + || pCost->plan.u.pIdx==0
|
| + || pCost->plan.u.pIdx==pSrc->pIndex
|
| + );
|
| +
|
| + WHERETRACE(("best index is: %s\n",
|
| + ((pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" :
|
| + pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
|
| + ));
|
| +
|
| + bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
|
| + bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
|
| + pCost->plan.wsFlags |= eqTermMask;
|
| +}
|
| +
|
| +/*
|
| +** Find the query plan for accessing table pSrc->pTab. Write the
|
| +** best query plan and its cost into the WhereCost object supplied
|
| +** as the last parameter. This function may calculate the cost of
|
| +** both real and virtual table scans.
|
| +*/
|
| +static void bestIndex(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + struct SrcList_item *pSrc, /* The FROM clause term to search */
|
| + Bitmask notReady, /* Mask of cursors not available for indexing */
|
| + Bitmask notValid, /* Cursors not available for any purpose */
|
| + ExprList *pOrderBy, /* The ORDER BY clause */
|
| + WhereCost *pCost /* Lowest cost query plan */
|
| +){
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + if( IsVirtual(pSrc->pTab) ){
|
| + sqlite3_index_info *p = 0;
|
| + bestVirtualIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost,&p);
|
| + if( p->needToFreeIdxStr ){
|
| + sqlite3_free(p->idxStr);
|
| + }
|
| + sqlite3DbFree(pParse->db, p);
|
| + }else
|
| +#endif
|
| + {
|
| + bestBtreeIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
|
| + }
|
| +}
|
| +
|
| +/*
|
| +** Disable a term in the WHERE clause. Except, do not disable the term
|
| +** if it controls a LEFT OUTER JOIN and it did not originate in the ON
|
| +** or USING clause of that join.
|
| +**
|
| +** Consider the term t2.z='ok' in the following queries:
|
| +**
|
| +** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
|
| +** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
|
| +** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
|
| +**
|
| +** The t2.z='ok' is disabled in the in (2) because it originates
|
| +** in the ON clause. The term is disabled in (3) because it is not part
|
| +** of a LEFT OUTER JOIN. In (1), the term is not disabled.
|
| +**
|
| +** IMPLEMENTATION-OF: R-24597-58655 No tests are done for terms that are
|
| +** completely satisfied by indices.
|
| +**
|
| +** Disabling a term causes that term to not be tested in the inner loop
|
| +** of the join. Disabling is an optimization. When terms are satisfied
|
| +** by indices, we disable them to prevent redundant tests in the inner
|
| +** loop. We would get the correct results if nothing were ever disabled,
|
| +** but joins might run a little slower. The trick is to disable as much
|
| +** as we can without disabling too much. If we disabled in (1), we'd get
|
| +** the wrong answer. See ticket #813.
|
| +*/
|
| +static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
|
| + if( pTerm
|
| + && (pTerm->wtFlags & TERM_CODED)==0
|
| + && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
|
| + ){
|
| + pTerm->wtFlags |= TERM_CODED;
|
| + if( pTerm->iParent>=0 ){
|
| + WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
|
| + if( (--pOther->nChild)==0 ){
|
| + disableTerm(pLevel, pOther);
|
| + }
|
| + }
|
| + }
|
| +}
|
| +
|
| +/*
|
| +** Code an OP_Affinity opcode to apply the column affinity string zAff
|
| +** to the n registers starting at base.
|
| +**
|
| +** As an optimization, SQLITE_AFF_NONE entries (which are no-ops) at the
|
| +** beginning and end of zAff are ignored. If all entries in zAff are
|
| +** SQLITE_AFF_NONE, then no code gets generated.
|
| +**
|
| +** This routine makes its own copy of zAff so that the caller is free
|
| +** to modify zAff after this routine returns.
|
| +*/
|
| +static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
|
| + Vdbe *v = pParse->pVdbe;
|
| + if( zAff==0 ){
|
| + assert( pParse->db->mallocFailed );
|
| + return;
|
| + }
|
| + assert( v!=0 );
|
| +
|
| + /* Adjust base and n to skip over SQLITE_AFF_NONE entries at the beginning
|
| + ** and end of the affinity string.
|
| + */
|
| + while( n>0 && zAff[0]==SQLITE_AFF_NONE ){
|
| + n--;
|
| + base++;
|
| + zAff++;
|
| + }
|
| + while( n>1 && zAff[n-1]==SQLITE_AFF_NONE ){
|
| + n--;
|
| + }
|
| +
|
| + /* Code the OP_Affinity opcode if there is anything left to do. */
|
| + if( n>0 ){
|
| + sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
|
| + sqlite3VdbeChangeP4(v, -1, zAff, n);
|
| + sqlite3ExprCacheAffinityChange(pParse, base, n);
|
| + }
|
| +}
|
| +
|
| +
|
| +/*
|
| +** Generate code for a single equality term of the WHERE clause. An equality
|
| +** term can be either X=expr or X IN (...). pTerm is the term to be
|
| +** coded.
|
| +**
|
| +** The current value for the constraint is left in register iReg.
|
| +**
|
| +** For a constraint of the form X=expr, the expression is evaluated and its
|
| +** result is left on the stack. For constraints of the form X IN (...)
|
| +** this routine sets up a loop that will iterate over all values of X.
|
| +*/
|
| +static int codeEqualityTerm(
|
| + Parse *pParse, /* The parsing context */
|
| + WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
|
| + WhereLevel *pLevel, /* When level of the FROM clause we are working on */
|
| + int iTarget /* Attempt to leave results in this register */
|
| +){
|
| + Expr *pX = pTerm->pExpr;
|
| + Vdbe *v = pParse->pVdbe;
|
| + int iReg; /* Register holding results */
|
| +
|
| + assert( iTarget>0 );
|
| + if( pX->op==TK_EQ ){
|
| + iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
|
| + }else if( pX->op==TK_ISNULL ){
|
| + iReg = iTarget;
|
| + sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
|
| +#ifndef SQLITE_OMIT_SUBQUERY
|
| + }else{
|
| + int eType;
|
| + int iTab;
|
| + struct InLoop *pIn;
|
| +
|
| + assert( pX->op==TK_IN );
|
| + iReg = iTarget;
|
| + eType = sqlite3FindInIndex(pParse, pX, 0);
|
| + iTab = pX->iTable;
|
| + sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
|
| + assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
|
| + if( pLevel->u.in.nIn==0 ){
|
| + pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
|
| + }
|
| + pLevel->u.in.nIn++;
|
| + pLevel->u.in.aInLoop =
|
| + sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
|
| + sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
|
| + pIn = pLevel->u.in.aInLoop;
|
| + if( pIn ){
|
| + pIn += pLevel->u.in.nIn - 1;
|
| + pIn->iCur = iTab;
|
| + if( eType==IN_INDEX_ROWID ){
|
| + pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
|
| + }else{
|
| + pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
|
| + }
|
| + sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
|
| + }else{
|
| + pLevel->u.in.nIn = 0;
|
| + }
|
| +#endif
|
| + }
|
| + disableTerm(pLevel, pTerm);
|
| + return iReg;
|
| +}
|
| +
|
| +/*
|
| +** Generate code that will evaluate all == and IN constraints for an
|
| +** index.
|
| +**
|
| +** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
|
| +** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
|
| +** The index has as many as three equality constraints, but in this
|
| +** example, the third "c" value is an inequality. So only two
|
| +** constraints are coded. This routine will generate code to evaluate
|
| +** a==5 and b IN (1,2,3). The current values for a and b will be stored
|
| +** in consecutive registers and the index of the first register is returned.
|
| +**
|
| +** In the example above nEq==2. But this subroutine works for any value
|
| +** of nEq including 0. If nEq==0, this routine is nearly a no-op.
|
| +** The only thing it does is allocate the pLevel->iMem memory cell and
|
| +** compute the affinity string.
|
| +**
|
| +** This routine always allocates at least one memory cell and returns
|
| +** the index of that memory cell. The code that
|
| +** calls this routine will use that memory cell to store the termination
|
| +** key value of the loop. If one or more IN operators appear, then
|
| +** this routine allocates an additional nEq memory cells for internal
|
| +** use.
|
| +**
|
| +** Before returning, *pzAff is set to point to a buffer containing a
|
| +** copy of the column affinity string of the index allocated using
|
| +** sqlite3DbMalloc(). Except, entries in the copy of the string associated
|
| +** with equality constraints that use NONE affinity are set to
|
| +** SQLITE_AFF_NONE. This is to deal with SQL such as the following:
|
| +**
|
| +** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
|
| +** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
|
| +**
|
| +** In the example above, the index on t1(a) has TEXT affinity. But since
|
| +** the right hand side of the equality constraint (t2.b) has NONE affinity,
|
| +** no conversion should be attempted before using a t2.b value as part of
|
| +** a key to search the index. Hence the first byte in the returned affinity
|
| +** string in this example would be set to SQLITE_AFF_NONE.
|
| +*/
|
| +static int codeAllEqualityTerms(
|
| + Parse *pParse, /* Parsing context */
|
| + WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
|
| + WhereClause *pWC, /* The WHERE clause */
|
| + Bitmask notReady, /* Which parts of FROM have not yet been coded */
|
| + int nExtraReg, /* Number of extra registers to allocate */
|
| + char **pzAff /* OUT: Set to point to affinity string */
|
| +){
|
| + int nEq = pLevel->plan.nEq; /* The number of == or IN constraints to code */
|
| + Vdbe *v = pParse->pVdbe; /* The vm under construction */
|
| + Index *pIdx; /* The index being used for this loop */
|
| + int iCur = pLevel->iTabCur; /* The cursor of the table */
|
| + WhereTerm *pTerm; /* A single constraint term */
|
| + int j; /* Loop counter */
|
| + int regBase; /* Base register */
|
| + int nReg; /* Number of registers to allocate */
|
| + char *zAff; /* Affinity string to return */
|
| +
|
| + /* This module is only called on query plans that use an index. */
|
| + assert( pLevel->plan.wsFlags & WHERE_INDEXED );
|
| + pIdx = pLevel->plan.u.pIdx;
|
| +
|
| + /* Figure out how many memory cells we will need then allocate them.
|
| + */
|
| + regBase = pParse->nMem + 1;
|
| + nReg = pLevel->plan.nEq + nExtraReg;
|
| + pParse->nMem += nReg;
|
| +
|
| + zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
|
| + if( !zAff ){
|
| + pParse->db->mallocFailed = 1;
|
| + }
|
| +
|
| + /* Evaluate the equality constraints
|
| + */
|
| + assert( pIdx->nColumn>=nEq );
|
| + for(j=0; j<nEq; j++){
|
| + int r1;
|
| + int k = pIdx->aiColumn[j];
|
| + pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
|
| + if( NEVER(pTerm==0) ) break;
|
| + /* The following true for indices with redundant columns.
|
| + ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
|
| + testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
|
| + testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
|
| + if( r1!=regBase+j ){
|
| + if( nReg==1 ){
|
| + sqlite3ReleaseTempReg(pParse, regBase);
|
| + regBase = r1;
|
| + }else{
|
| + sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
|
| + }
|
| + }
|
| + testcase( pTerm->eOperator & WO_ISNULL );
|
| + testcase( pTerm->eOperator & WO_IN );
|
| + if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
|
| + Expr *pRight = pTerm->pExpr->pRight;
|
| + sqlite3ExprCodeIsNullJump(v, pRight, regBase+j, pLevel->addrBrk);
|
| + if( zAff ){
|
| + if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_NONE ){
|
| + zAff[j] = SQLITE_AFF_NONE;
|
| + }
|
| + if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
|
| + zAff[j] = SQLITE_AFF_NONE;
|
| + }
|
| + }
|
| + }
|
| + }
|
| + *pzAff = zAff;
|
| + return regBase;
|
| +}
|
| +
|
| +#ifndef SQLITE_OMIT_EXPLAIN
|
| +/*
|
| +** This routine is a helper for explainIndexRange() below
|
| +**
|
| +** pStr holds the text of an expression that we are building up one term
|
| +** at a time. This routine adds a new term to the end of the expression.
|
| +** Terms are separated by AND so add the "AND" text for second and subsequent
|
| +** terms only.
|
| +*/
|
| +static void explainAppendTerm(
|
| + StrAccum *pStr, /* The text expression being built */
|
| + int iTerm, /* Index of this term. First is zero */
|
| + const char *zColumn, /* Name of the column */
|
| + const char *zOp /* Name of the operator */
|
| +){
|
| + if( iTerm ) sqlite3StrAccumAppend(pStr, " AND ", 5);
|
| + sqlite3StrAccumAppend(pStr, zColumn, -1);
|
| + sqlite3StrAccumAppend(pStr, zOp, 1);
|
| + sqlite3StrAccumAppend(pStr, "?", 1);
|
| +}
|
| +
|
| +/*
|
| +** Argument pLevel describes a strategy for scanning table pTab. This
|
| +** function returns a pointer to a string buffer containing a description
|
| +** of the subset of table rows scanned by the strategy in the form of an
|
| +** SQL expression. Or, if all rows are scanned, NULL is returned.
|
| +**
|
| +** For example, if the query:
|
| +**
|
| +** SELECT * FROM t1 WHERE a=1 AND b>2;
|
| +**
|
| +** is run and there is an index on (a, b), then this function returns a
|
| +** string similar to:
|
| +**
|
| +** "a=? AND b>?"
|
| +**
|
| +** The returned pointer points to memory obtained from sqlite3DbMalloc().
|
| +** It is the responsibility of the caller to free the buffer when it is
|
| +** no longer required.
|
| +*/
|
| +static char *explainIndexRange(sqlite3 *db, WhereLevel *pLevel, Table *pTab){
|
| + WherePlan *pPlan = &pLevel->plan;
|
| + Index *pIndex = pPlan->u.pIdx;
|
| + int nEq = pPlan->nEq;
|
| + int i, j;
|
| + Column *aCol = pTab->aCol;
|
| + int *aiColumn = pIndex->aiColumn;
|
| + StrAccum txt;
|
| +
|
| + if( nEq==0 && (pPlan->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
|
| + return 0;
|
| + }
|
| + sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
|
| + txt.db = db;
|
| + sqlite3StrAccumAppend(&txt, " (", 2);
|
| + for(i=0; i<nEq; i++){
|
| + explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "=");
|
| + }
|
| +
|
| + j = i;
|
| + if( pPlan->wsFlags&WHERE_BTM_LIMIT ){
|
| + explainAppendTerm(&txt, i++, aCol[aiColumn[j]].zName, ">");
|
| + }
|
| + if( pPlan->wsFlags&WHERE_TOP_LIMIT ){
|
| + explainAppendTerm(&txt, i, aCol[aiColumn[j]].zName, "<");
|
| + }
|
| + sqlite3StrAccumAppend(&txt, ")", 1);
|
| + return sqlite3StrAccumFinish(&txt);
|
| +}
|
| +
|
| +/*
|
| +** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
|
| +** command. If the query being compiled is an EXPLAIN QUERY PLAN, a single
|
| +** record is added to the output to describe the table scan strategy in
|
| +** pLevel.
|
| +*/
|
| +static void explainOneScan(
|
| + Parse *pParse, /* Parse context */
|
| + SrcList *pTabList, /* Table list this loop refers to */
|
| + WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */
|
| + int iLevel, /* Value for "level" column of output */
|
| + int iFrom, /* Value for "from" column of output */
|
| + u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
|
| +){
|
| + if( pParse->explain==2 ){
|
| + u32 flags = pLevel->plan.wsFlags;
|
| + struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
|
| + Vdbe *v = pParse->pVdbe; /* VM being constructed */
|
| + sqlite3 *db = pParse->db; /* Database handle */
|
| + char *zMsg; /* Text to add to EQP output */
|
| + sqlite3_int64 nRow; /* Expected number of rows visited by scan */
|
| + int iId = pParse->iSelectId; /* Select id (left-most output column) */
|
| + int isSearch; /* True for a SEARCH. False for SCAN. */
|
| +
|
| + if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_ONETABLE_ONLY) ) return;
|
| +
|
| + isSearch = (pLevel->plan.nEq>0)
|
| + || (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0
|
| + || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX));
|
| +
|
| + zMsg = sqlite3MPrintf(db, "%s", isSearch?"SEARCH":"SCAN");
|
| + if( pItem->pSelect ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s SUBQUERY %d", zMsg,pItem->iSelectId);
|
| + }else{
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s TABLE %s", zMsg, pItem->zName);
|
| + }
|
| +
|
| + if( pItem->zAlias ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
|
| + }
|
| + if( (flags & WHERE_INDEXED)!=0 ){
|
| + char *zWhere = explainIndexRange(db, pLevel, pItem->pTab);
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s USING %s%sINDEX%s%s%s", zMsg,
|
| + ((flags & WHERE_TEMP_INDEX)?"AUTOMATIC ":""),
|
| + ((flags & WHERE_IDX_ONLY)?"COVERING ":""),
|
| + ((flags & WHERE_TEMP_INDEX)?"":" "),
|
| + ((flags & WHERE_TEMP_INDEX)?"": pLevel->plan.u.pIdx->zName),
|
| + zWhere
|
| + );
|
| + sqlite3DbFree(db, zWhere);
|
| + }else if( flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s USING INTEGER PRIMARY KEY", zMsg);
|
| +
|
| + if( flags&WHERE_ROWID_EQ ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid=?)", zMsg);
|
| + }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>? AND rowid<?)", zMsg);
|
| + }else if( flags&WHERE_BTM_LIMIT ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>?)", zMsg);
|
| + }else if( flags&WHERE_TOP_LIMIT ){
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid<?)", zMsg);
|
| + }
|
| + }
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
|
| + sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
|
| + pVtabIdx->idxNum, pVtabIdx->idxStr);
|
| + }
|
| +#endif
|
| + if( wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX) ){
|
| + testcase( wctrlFlags & WHERE_ORDERBY_MIN );
|
| + nRow = 1;
|
| + }else{
|
| + nRow = (sqlite3_int64)pLevel->plan.nRow;
|
| + }
|
| + zMsg = sqlite3MAppendf(db, zMsg, "%s (~%lld rows)", zMsg, nRow);
|
| + sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
|
| + }
|
| +}
|
| +#else
|
| +# define explainOneScan(u,v,w,x,y,z)
|
| +#endif /* SQLITE_OMIT_EXPLAIN */
|
| +
|
| +
|
| +/*
|
| +** Generate code for the start of the iLevel-th loop in the WHERE clause
|
| +** implementation described by pWInfo.
|
| +*/
|
| +static Bitmask codeOneLoopStart(
|
| + WhereInfo *pWInfo, /* Complete information about the WHERE clause */
|
| + int iLevel, /* Which level of pWInfo->a[] should be coded */
|
| + u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
|
| + Bitmask notReady /* Which tables are currently available */
|
| +){
|
| + int j, k; /* Loop counters */
|
| + int iCur; /* The VDBE cursor for the table */
|
| + int addrNxt; /* Where to jump to continue with the next IN case */
|
| + int omitTable; /* True if we use the index only */
|
| + int bRev; /* True if we need to scan in reverse order */
|
| + WhereLevel *pLevel; /* The where level to be coded */
|
| + WhereClause *pWC; /* Decomposition of the entire WHERE clause */
|
| + WhereTerm *pTerm; /* A WHERE clause term */
|
| + Parse *pParse; /* Parsing context */
|
| + Vdbe *v; /* The prepared stmt under constructions */
|
| + struct SrcList_item *pTabItem; /* FROM clause term being coded */
|
| + int addrBrk; /* Jump here to break out of the loop */
|
| + int addrCont; /* Jump here to continue with next cycle */
|
| + int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
|
| + int iReleaseReg = 0; /* Temp register to free before returning */
|
| +
|
| + pParse = pWInfo->pParse;
|
| + v = pParse->pVdbe;
|
| + pWC = pWInfo->pWC;
|
| + pLevel = &pWInfo->a[iLevel];
|
| + pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
|
| + iCur = pTabItem->iCursor;
|
| + bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
|
| + omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0
|
| + && (wctrlFlags & WHERE_FORCE_TABLE)==0;
|
| +
|
| + /* Create labels for the "break" and "continue" instructions
|
| + ** for the current loop. Jump to addrBrk to break out of a loop.
|
| + ** Jump to cont to go immediately to the next iteration of the
|
| + ** loop.
|
| + **
|
| + ** When there is an IN operator, we also have a "addrNxt" label that
|
| + ** means to continue with the next IN value combination. When
|
| + ** there are no IN operators in the constraints, the "addrNxt" label
|
| + ** is the same as "addrBrk".
|
| + */
|
| + addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
|
| + addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
|
| +
|
| + /* If this is the right table of a LEFT OUTER JOIN, allocate and
|
| + ** initialize a memory cell that records if this table matches any
|
| + ** row of the left table of the join.
|
| + */
|
| + if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
|
| + pLevel->iLeftJoin = ++pParse->nMem;
|
| + sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
|
| + VdbeComment((v, "init LEFT JOIN no-match flag"));
|
| + }
|
| +
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
|
| + /* Case 0: The table is a virtual-table. Use the VFilter and VNext
|
| + ** to access the data.
|
| + */
|
| + int iReg; /* P3 Value for OP_VFilter */
|
| + sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
|
| + int nConstraint = pVtabIdx->nConstraint;
|
| + struct sqlite3_index_constraint_usage *aUsage =
|
| + pVtabIdx->aConstraintUsage;
|
| + const struct sqlite3_index_constraint *aConstraint =
|
| + pVtabIdx->aConstraint;
|
| +
|
| + sqlite3ExprCachePush(pParse);
|
| + iReg = sqlite3GetTempRange(pParse, nConstraint+2);
|
| + for(j=1; j<=nConstraint; j++){
|
| + for(k=0; k<nConstraint; k++){
|
| + if( aUsage[k].argvIndex==j ){
|
| + int iTerm = aConstraint[k].iTermOffset;
|
| + sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
|
| + break;
|
| + }
|
| + }
|
| + if( k==nConstraint ) break;
|
| + }
|
| + sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
|
| + sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
|
| + sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
|
| + pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
|
| + pVtabIdx->needToFreeIdxStr = 0;
|
| + for(j=0; j<nConstraint; j++){
|
| + if( aUsage[j].omit ){
|
| + int iTerm = aConstraint[j].iTermOffset;
|
| + disableTerm(pLevel, &pWC->a[iTerm]);
|
| + }
|
| + }
|
| + pLevel->op = OP_VNext;
|
| + pLevel->p1 = iCur;
|
| + pLevel->p2 = sqlite3VdbeCurrentAddr(v);
|
| + sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
|
| + sqlite3ExprCachePop(pParse, 1);
|
| + }else
|
| +#endif /* SQLITE_OMIT_VIRTUALTABLE */
|
| +
|
| + if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
|
| + /* Case 1: We can directly reference a single row using an
|
| + ** equality comparison against the ROWID field. Or
|
| + ** we reference multiple rows using a "rowid IN (...)"
|
| + ** construct.
|
| + */
|
| + iReleaseReg = sqlite3GetTempReg(pParse);
|
| + pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
|
| + assert( pTerm!=0 );
|
| + assert( pTerm->pExpr!=0 );
|
| + assert( pTerm->leftCursor==iCur );
|
| + assert( omitTable==0 );
|
| + testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
|
| + addrNxt = pLevel->addrNxt;
|
| + sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
|
| + sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
|
| + sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
|
| + VdbeComment((v, "pk"));
|
| + pLevel->op = OP_Noop;
|
| + }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
|
| + /* Case 2: We have an inequality comparison against the ROWID field.
|
| + */
|
| + int testOp = OP_Noop;
|
| + int start;
|
| + int memEndValue = 0;
|
| + WhereTerm *pStart, *pEnd;
|
| +
|
| + assert( omitTable==0 );
|
| + pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
|
| + pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
|
| + if( bRev ){
|
| + pTerm = pStart;
|
| + pStart = pEnd;
|
| + pEnd = pTerm;
|
| + }
|
| + if( pStart ){
|
| + Expr *pX; /* The expression that defines the start bound */
|
| + int r1, rTemp; /* Registers for holding the start boundary */
|
| +
|
| + /* The following constant maps TK_xx codes into corresponding
|
| + ** seek opcodes. It depends on a particular ordering of TK_xx
|
| + */
|
| + const u8 aMoveOp[] = {
|
| + /* TK_GT */ OP_SeekGt,
|
| + /* TK_LE */ OP_SeekLe,
|
| + /* TK_LT */ OP_SeekLt,
|
| + /* TK_GE */ OP_SeekGe
|
| + };
|
| + assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
|
| + assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
|
| + assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
|
| +
|
| + testcase( pStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + pX = pStart->pExpr;
|
| + assert( pX!=0 );
|
| + assert( pStart->leftCursor==iCur );
|
| + r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
|
| + sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
|
| + VdbeComment((v, "pk"));
|
| + sqlite3ExprCacheAffinityChange(pParse, r1, 1);
|
| + sqlite3ReleaseTempReg(pParse, rTemp);
|
| + disableTerm(pLevel, pStart);
|
| + }else{
|
| + sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
|
| + }
|
| + if( pEnd ){
|
| + Expr *pX;
|
| + pX = pEnd->pExpr;
|
| + assert( pX!=0 );
|
| + assert( pEnd->leftCursor==iCur );
|
| + testcase( pEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + memEndValue = ++pParse->nMem;
|
| + sqlite3ExprCode(pParse, pX->pRight, memEndValue);
|
| + if( pX->op==TK_LT || pX->op==TK_GT ){
|
| + testOp = bRev ? OP_Le : OP_Ge;
|
| + }else{
|
| + testOp = bRev ? OP_Lt : OP_Gt;
|
| + }
|
| + disableTerm(pLevel, pEnd);
|
| + }
|
| + start = sqlite3VdbeCurrentAddr(v);
|
| + pLevel->op = bRev ? OP_Prev : OP_Next;
|
| + pLevel->p1 = iCur;
|
| + pLevel->p2 = start;
|
| + if( pStart==0 && pEnd==0 ){
|
| + pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
|
| + }else{
|
| + assert( pLevel->p5==0 );
|
| + }
|
| + if( testOp!=OP_Noop ){
|
| + iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
|
| + sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
|
| + sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
|
| + sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
|
| + sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
|
| + }
|
| + }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
|
| + /* Case 3: A scan using an index.
|
| + **
|
| + ** The WHERE clause may contain zero or more equality
|
| + ** terms ("==" or "IN" operators) that refer to the N
|
| + ** left-most columns of the index. It may also contain
|
| + ** inequality constraints (>, <, >= or <=) on the indexed
|
| + ** column that immediately follows the N equalities. Only
|
| + ** the right-most column can be an inequality - the rest must
|
| + ** use the "==" and "IN" operators. For example, if the
|
| + ** index is on (x,y,z), then the following clauses are all
|
| + ** optimized:
|
| + **
|
| + ** x=5
|
| + ** x=5 AND y=10
|
| + ** x=5 AND y<10
|
| + ** x=5 AND y>5 AND y<10
|
| + ** x=5 AND y=5 AND z<=10
|
| + **
|
| + ** The z<10 term of the following cannot be used, only
|
| + ** the x=5 term:
|
| + **
|
| + ** x=5 AND z<10
|
| + **
|
| + ** N may be zero if there are inequality constraints.
|
| + ** If there are no inequality constraints, then N is at
|
| + ** least one.
|
| + **
|
| + ** This case is also used when there are no WHERE clause
|
| + ** constraints but an index is selected anyway, in order
|
| + ** to force the output order to conform to an ORDER BY.
|
| + */
|
| + static const u8 aStartOp[] = {
|
| + 0,
|
| + 0,
|
| + OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
|
| + OP_Last, /* 3: (!start_constraints && startEq && bRev) */
|
| + OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */
|
| + OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */
|
| + OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */
|
| + OP_SeekLe /* 7: (start_constraints && startEq && bRev) */
|
| + };
|
| + static const u8 aEndOp[] = {
|
| + OP_Noop, /* 0: (!end_constraints) */
|
| + OP_IdxGE, /* 1: (end_constraints && !bRev) */
|
| + OP_IdxLT /* 2: (end_constraints && bRev) */
|
| + };
|
| + int nEq = pLevel->plan.nEq; /* Number of == or IN terms */
|
| + int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
|
| + int regBase; /* Base register holding constraint values */
|
| + int r1; /* Temp register */
|
| + WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
|
| + WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
|
| + int startEq; /* True if range start uses ==, >= or <= */
|
| + int endEq; /* True if range end uses ==, >= or <= */
|
| + int start_constraints; /* Start of range is constrained */
|
| + int nConstraint; /* Number of constraint terms */
|
| + Index *pIdx; /* The index we will be using */
|
| + int iIdxCur; /* The VDBE cursor for the index */
|
| + int nExtraReg = 0; /* Number of extra registers needed */
|
| + int op; /* Instruction opcode */
|
| + char *zStartAff; /* Affinity for start of range constraint */
|
| + char *zEndAff; /* Affinity for end of range constraint */
|
| +
|
| + pIdx = pLevel->plan.u.pIdx;
|
| + iIdxCur = pLevel->iIdxCur;
|
| + k = pIdx->aiColumn[nEq]; /* Column for inequality constraints */
|
| +
|
| + /* If this loop satisfies a sort order (pOrderBy) request that
|
| + ** was passed to this function to implement a "SELECT min(x) ..."
|
| + ** query, then the caller will only allow the loop to run for
|
| + ** a single iteration. This means that the first row returned
|
| + ** should not have a NULL value stored in 'x'. If column 'x' is
|
| + ** the first one after the nEq equality constraints in the index,
|
| + ** this requires some special handling.
|
| + */
|
| + if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
|
| + && (pLevel->plan.wsFlags&WHERE_ORDERBY)
|
| + && (pIdx->nColumn>nEq)
|
| + ){
|
| + /* assert( pOrderBy->nExpr==1 ); */
|
| + /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
|
| + isMinQuery = 1;
|
| + nExtraReg = 1;
|
| + }
|
| +
|
| + /* Find any inequality constraint terms for the start and end
|
| + ** of the range.
|
| + */
|
| + if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
|
| + pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
|
| + nExtraReg = 1;
|
| + }
|
| + if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
|
| + pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
|
| + nExtraReg = 1;
|
| + }
|
| +
|
| + /* Generate code to evaluate all constraint terms using == or IN
|
| + ** and store the values of those terms in an array of registers
|
| + ** starting at regBase.
|
| + */
|
| + regBase = codeAllEqualityTerms(
|
| + pParse, pLevel, pWC, notReady, nExtraReg, &zStartAff
|
| + );
|
| + zEndAff = sqlite3DbStrDup(pParse->db, zStartAff);
|
| + addrNxt = pLevel->addrNxt;
|
| +
|
| + /* If we are doing a reverse order scan on an ascending index, or
|
| + ** a forward order scan on a descending index, interchange the
|
| + ** start and end terms (pRangeStart and pRangeEnd).
|
| + */
|
| + if( nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC) ){
|
| + SWAP(WhereTerm *, pRangeEnd, pRangeStart);
|
| + }
|
| +
|
| + testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
|
| + testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
|
| + testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
|
| + testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
|
| + startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
|
| + endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
|
| + start_constraints = pRangeStart || nEq>0;
|
| +
|
| + /* Seek the index cursor to the start of the range. */
|
| + nConstraint = nEq;
|
| + if( pRangeStart ){
|
| + Expr *pRight = pRangeStart->pExpr->pRight;
|
| + sqlite3ExprCode(pParse, pRight, regBase+nEq);
|
| + if( (pRangeStart->wtFlags & TERM_VNULL)==0 ){
|
| + sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
|
| + }
|
| + if( zStartAff ){
|
| + if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
|
| + /* Since the comparison is to be performed with no conversions
|
| + ** applied to the operands, set the affinity to apply to pRight to
|
| + ** SQLITE_AFF_NONE. */
|
| + zStartAff[nEq] = SQLITE_AFF_NONE;
|
| + }
|
| + if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){
|
| + zStartAff[nEq] = SQLITE_AFF_NONE;
|
| + }
|
| + }
|
| + nConstraint++;
|
| + testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + }else if( isMinQuery ){
|
| + sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
|
| + nConstraint++;
|
| + startEq = 0;
|
| + start_constraints = 1;
|
| + }
|
| + codeApplyAffinity(pParse, regBase, nConstraint, zStartAff);
|
| + op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
|
| + assert( op!=0 );
|
| + testcase( op==OP_Rewind );
|
| + testcase( op==OP_Last );
|
| + testcase( op==OP_SeekGt );
|
| + testcase( op==OP_SeekGe );
|
| + testcase( op==OP_SeekLe );
|
| + testcase( op==OP_SeekLt );
|
| + sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
|
| +
|
| + /* Load the value for the inequality constraint at the end of the
|
| + ** range (if any).
|
| + */
|
| + nConstraint = nEq;
|
| + if( pRangeEnd ){
|
| + Expr *pRight = pRangeEnd->pExpr->pRight;
|
| + sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
|
| + sqlite3ExprCode(pParse, pRight, regBase+nEq);
|
| + if( (pRangeEnd->wtFlags & TERM_VNULL)==0 ){
|
| + sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
|
| + }
|
| + if( zEndAff ){
|
| + if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){
|
| + /* Since the comparison is to be performed with no conversions
|
| + ** applied to the operands, set the affinity to apply to pRight to
|
| + ** SQLITE_AFF_NONE. */
|
| + zEndAff[nEq] = SQLITE_AFF_NONE;
|
| + }
|
| + if( sqlite3ExprNeedsNoAffinityChange(pRight, zEndAff[nEq]) ){
|
| + zEndAff[nEq] = SQLITE_AFF_NONE;
|
| + }
|
| + }
|
| + codeApplyAffinity(pParse, regBase, nEq+1, zEndAff);
|
| + nConstraint++;
|
| + testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
|
| + }
|
| + sqlite3DbFree(pParse->db, zStartAff);
|
| + sqlite3DbFree(pParse->db, zEndAff);
|
| +
|
| + /* Top of the loop body */
|
| + pLevel->p2 = sqlite3VdbeCurrentAddr(v);
|
| +
|
| + /* Check if the index cursor is past the end of the range. */
|
| + op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
|
| + testcase( op==OP_Noop );
|
| + testcase( op==OP_IdxGE );
|
| + testcase( op==OP_IdxLT );
|
| + if( op!=OP_Noop ){
|
| + sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
|
| + sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
|
| + }
|
| +
|
| + /* If there are inequality constraints, check that the value
|
| + ** of the table column that the inequality contrains is not NULL.
|
| + ** If it is, jump to the next iteration of the loop.
|
| + */
|
| + r1 = sqlite3GetTempReg(pParse);
|
| + testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
|
| + testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
|
| + if( (pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
|
| + sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
|
| + sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
|
| + }
|
| + sqlite3ReleaseTempReg(pParse, r1);
|
| +
|
| + /* Seek the table cursor, if required */
|
| + disableTerm(pLevel, pRangeStart);
|
| + disableTerm(pLevel, pRangeEnd);
|
| + if( !omitTable ){
|
| + iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
|
| + sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
|
| + sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
|
| + sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */
|
| + }
|
| +
|
| + /* Record the instruction used to terminate the loop. Disable
|
| + ** WHERE clause terms made redundant by the index range scan.
|
| + */
|
| + if( pLevel->plan.wsFlags & WHERE_UNIQUE ){
|
| + pLevel->op = OP_Noop;
|
| + }else if( bRev ){
|
| + pLevel->op = OP_Prev;
|
| + }else{
|
| + pLevel->op = OP_Next;
|
| + }
|
| + pLevel->p1 = iIdxCur;
|
| + }else
|
| +
|
| +#ifndef SQLITE_OMIT_OR_OPTIMIZATION
|
| + if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
|
| + /* Case 4: Two or more separately indexed terms connected by OR
|
| + **
|
| + ** Example:
|
| + **
|
| + ** CREATE TABLE t1(a,b,c,d);
|
| + ** CREATE INDEX i1 ON t1(a);
|
| + ** CREATE INDEX i2 ON t1(b);
|
| + ** CREATE INDEX i3 ON t1(c);
|
| + **
|
| + ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
|
| + **
|
| + ** In the example, there are three indexed terms connected by OR.
|
| + ** The top of the loop looks like this:
|
| + **
|
| + ** Null 1 # Zero the rowset in reg 1
|
| + **
|
| + ** Then, for each indexed term, the following. The arguments to
|
| + ** RowSetTest are such that the rowid of the current row is inserted
|
| + ** into the RowSet. If it is already present, control skips the
|
| + ** Gosub opcode and jumps straight to the code generated by WhereEnd().
|
| + **
|
| + ** sqlite3WhereBegin(<term>)
|
| + ** RowSetTest # Insert rowid into rowset
|
| + ** Gosub 2 A
|
| + ** sqlite3WhereEnd()
|
| + **
|
| + ** Following the above, code to terminate the loop. Label A, the target
|
| + ** of the Gosub above, jumps to the instruction right after the Goto.
|
| + **
|
| + ** Null 1 # Zero the rowset in reg 1
|
| + ** Goto B # The loop is finished.
|
| + **
|
| + ** A: <loop body> # Return data, whatever.
|
| + **
|
| + ** Return 2 # Jump back to the Gosub
|
| + **
|
| + ** B: <after the loop>
|
| + **
|
| + */
|
| + WhereClause *pOrWc; /* The OR-clause broken out into subterms */
|
| + SrcList *pOrTab; /* Shortened table list or OR-clause generation */
|
| +
|
| + int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
|
| + int regRowset = 0; /* Register for RowSet object */
|
| + int regRowid = 0; /* Register holding rowid */
|
| + int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */
|
| + int iRetInit; /* Address of regReturn init */
|
| + int untestedTerms = 0; /* Some terms not completely tested */
|
| + int ii;
|
| +
|
| + pTerm = pLevel->plan.u.pTerm;
|
| + assert( pTerm!=0 );
|
| + assert( pTerm->eOperator==WO_OR );
|
| + assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
|
| + pOrWc = &pTerm->u.pOrInfo->wc;
|
| + pLevel->op = OP_Return;
|
| + pLevel->p1 = regReturn;
|
| +
|
| + /* Set up a new SrcList ni pOrTab containing the table being scanned
|
| + ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
|
| + ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
|
| + */
|
| + if( pWInfo->nLevel>1 ){
|
| + int nNotReady; /* The number of notReady tables */
|
| + struct SrcList_item *origSrc; /* Original list of tables */
|
| + nNotReady = pWInfo->nLevel - iLevel - 1;
|
| + pOrTab = sqlite3StackAllocRaw(pParse->db,
|
| + sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
|
| + if( pOrTab==0 ) return notReady;
|
| + pOrTab->nAlloc = (i16)(nNotReady + 1);
|
| + pOrTab->nSrc = pOrTab->nAlloc;
|
| + memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
|
| + origSrc = pWInfo->pTabList->a;
|
| + for(k=1; k<=nNotReady; k++){
|
| + memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
|
| + }
|
| + }else{
|
| + pOrTab = pWInfo->pTabList;
|
| + }
|
| +
|
| + /* Initialize the rowset register to contain NULL. An SQL NULL is
|
| + ** equivalent to an empty rowset.
|
| + **
|
| + ** Also initialize regReturn to contain the address of the instruction
|
| + ** immediately following the OP_Return at the bottom of the loop. This
|
| + ** is required in a few obscure LEFT JOIN cases where control jumps
|
| + ** over the top of the loop into the body of it. In this case the
|
| + ** correct response for the end-of-loop code (the OP_Return) is to
|
| + ** fall through to the next instruction, just as an OP_Next does if
|
| + ** called on an uninitialized cursor.
|
| + */
|
| + if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
|
| + regRowset = ++pParse->nMem;
|
| + regRowid = ++pParse->nMem;
|
| + sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
|
| + }
|
| + iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
|
| +
|
| + for(ii=0; ii<pOrWc->nTerm; ii++){
|
| + WhereTerm *pOrTerm = &pOrWc->a[ii];
|
| + if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
|
| + WhereInfo *pSubWInfo; /* Info for single OR-term scan */
|
| + /* Loop through table entries that match term pOrTerm. */
|
| + pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrTerm->pExpr, 0,
|
| + WHERE_OMIT_OPEN | WHERE_OMIT_CLOSE |
|
| + WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
|
| + if( pSubWInfo ){
|
| + explainOneScan(
|
| + pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
|
| + );
|
| + if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
|
| + int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
|
| + int r;
|
| + r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,
|
| + regRowid);
|
| + sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset,
|
| + sqlite3VdbeCurrentAddr(v)+2, r, iSet);
|
| + }
|
| + sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
|
| +
|
| + /* The pSubWInfo->untestedTerms flag means that this OR term
|
| + ** contained one or more AND term from a notReady table. The
|
| + ** terms from the notReady table could not be tested and will
|
| + ** need to be tested later.
|
| + */
|
| + if( pSubWInfo->untestedTerms ) untestedTerms = 1;
|
| +
|
| + /* Finish the loop through table entries that match term pOrTerm. */
|
| + sqlite3WhereEnd(pSubWInfo);
|
| + }
|
| + }
|
| + }
|
| + sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
|
| + sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
|
| + sqlite3VdbeResolveLabel(v, iLoopBody);
|
| +
|
| + if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
|
| + if( !untestedTerms ) disableTerm(pLevel, pTerm);
|
| + }else
|
| +#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
|
| +
|
| + {
|
| + /* Case 5: There is no usable index. We must do a complete
|
| + ** scan of the entire table.
|
| + */
|
| + static const u8 aStep[] = { OP_Next, OP_Prev };
|
| + static const u8 aStart[] = { OP_Rewind, OP_Last };
|
| + assert( bRev==0 || bRev==1 );
|
| + assert( omitTable==0 );
|
| + pLevel->op = aStep[bRev];
|
| + pLevel->p1 = iCur;
|
| + pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
|
| + pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
|
| + }
|
| + notReady &= ~getMask(pWC->pMaskSet, iCur);
|
| +
|
| + /* Insert code to test every subexpression that can be completely
|
| + ** computed using the current set of tables.
|
| + **
|
| + ** IMPLEMENTATION-OF: R-49525-50935 Terms that cannot be satisfied through
|
| + ** the use of indices become tests that are evaluated against each row of
|
| + ** the relevant input tables.
|
| + */
|
| + for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
|
| + Expr *pE;
|
| + testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
|
| + testcase( pTerm->wtFlags & TERM_CODED );
|
| + if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
|
| + if( (pTerm->prereqAll & notReady)!=0 ){
|
| + testcase( pWInfo->untestedTerms==0
|
| + && (pWInfo->wctrlFlags & WHERE_ONETABLE_ONLY)!=0 );
|
| + pWInfo->untestedTerms = 1;
|
| + continue;
|
| + }
|
| + pE = pTerm->pExpr;
|
| + assert( pE!=0 );
|
| + if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
|
| + continue;
|
| + }
|
| + sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
|
| + pTerm->wtFlags |= TERM_CODED;
|
| + }
|
| +
|
| + /* For a LEFT OUTER JOIN, generate code that will record the fact that
|
| + ** at least one row of the right table has matched the left table.
|
| + */
|
| + if( pLevel->iLeftJoin ){
|
| + pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
|
| + sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
|
| + VdbeComment((v, "record LEFT JOIN hit"));
|
| + sqlite3ExprCacheClear(pParse);
|
| + for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
|
| + testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
|
| + testcase( pTerm->wtFlags & TERM_CODED );
|
| + if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
|
| + if( (pTerm->prereqAll & notReady)!=0 ){
|
| + assert( pWInfo->untestedTerms );
|
| + continue;
|
| + }
|
| + assert( pTerm->pExpr );
|
| + sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
|
| + pTerm->wtFlags |= TERM_CODED;
|
| + }
|
| + }
|
| + sqlite3ReleaseTempReg(pParse, iReleaseReg);
|
| +
|
| + return notReady;
|
| +}
|
| +
|
| +#if defined(SQLITE_TEST)
|
| +/*
|
| +** The following variable holds a text description of query plan generated
|
| +** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
|
| +** overwrites the previous. This information is used for testing and
|
| +** analysis only.
|
| +*/
|
| +char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
|
| +static int nQPlan = 0; /* Next free slow in _query_plan[] */
|
| +
|
| +#endif /* SQLITE_TEST */
|
| +
|
| +
|
| +/*
|
| +** Free a WhereInfo structure
|
| +*/
|
| +static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
|
| + if( ALWAYS(pWInfo) ){
|
| + int i;
|
| + for(i=0; i<pWInfo->nLevel; i++){
|
| + sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
|
| + if( pInfo ){
|
| + /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
|
| + if( pInfo->needToFreeIdxStr ){
|
| + sqlite3_free(pInfo->idxStr);
|
| + }
|
| + sqlite3DbFree(db, pInfo);
|
| + }
|
| + if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){
|
| + Index *pIdx = pWInfo->a[i].plan.u.pIdx;
|
| + if( pIdx ){
|
| + sqlite3DbFree(db, pIdx->zColAff);
|
| + sqlite3DbFree(db, pIdx);
|
| + }
|
| + }
|
| + }
|
| + whereClauseClear(pWInfo->pWC);
|
| + sqlite3DbFree(db, pWInfo);
|
| + }
|
| +}
|
| +
|
| +
|
| +/*
|
| +** Generate the beginning of the loop used for WHERE clause processing.
|
| +** The return value is a pointer to an opaque structure that contains
|
| +** information needed to terminate the loop. Later, the calling routine
|
| +** should invoke sqlite3WhereEnd() with the return value of this function
|
| +** in order to complete the WHERE clause processing.
|
| +**
|
| +** If an error occurs, this routine returns NULL.
|
| +**
|
| +** The basic idea is to do a nested loop, one loop for each table in
|
| +** the FROM clause of a select. (INSERT and UPDATE statements are the
|
| +** same as a SELECT with only a single table in the FROM clause.) For
|
| +** example, if the SQL is this:
|
| +**
|
| +** SELECT * FROM t1, t2, t3 WHERE ...;
|
| +**
|
| +** Then the code generated is conceptually like the following:
|
| +**
|
| +** foreach row1 in t1 do \ Code generated
|
| +** foreach row2 in t2 do |-- by sqlite3WhereBegin()
|
| +** foreach row3 in t3 do /
|
| +** ...
|
| +** end \ Code generated
|
| +** end |-- by sqlite3WhereEnd()
|
| +** end /
|
| +**
|
| +** Note that the loops might not be nested in the order in which they
|
| +** appear in the FROM clause if a different order is better able to make
|
| +** use of indices. Note also that when the IN operator appears in
|
| +** the WHERE clause, it might result in additional nested loops for
|
| +** scanning through all values on the right-hand side of the IN.
|
| +**
|
| +** There are Btree cursors associated with each table. t1 uses cursor
|
| +** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
|
| +** And so forth. This routine generates code to open those VDBE cursors
|
| +** and sqlite3WhereEnd() generates the code to close them.
|
| +**
|
| +** The code that sqlite3WhereBegin() generates leaves the cursors named
|
| +** in pTabList pointing at their appropriate entries. The [...] code
|
| +** can use OP_Column and OP_Rowid opcodes on these cursors to extract
|
| +** data from the various tables of the loop.
|
| +**
|
| +** If the WHERE clause is empty, the foreach loops must each scan their
|
| +** entire tables. Thus a three-way join is an O(N^3) operation. But if
|
| +** the tables have indices and there are terms in the WHERE clause that
|
| +** refer to those indices, a complete table scan can be avoided and the
|
| +** code will run much faster. Most of the work of this routine is checking
|
| +** to see if there are indices that can be used to speed up the loop.
|
| +**
|
| +** Terms of the WHERE clause are also used to limit which rows actually
|
| +** make it to the "..." in the middle of the loop. After each "foreach",
|
| +** terms of the WHERE clause that use only terms in that loop and outer
|
| +** loops are evaluated and if false a jump is made around all subsequent
|
| +** inner loops (or around the "..." if the test occurs within the inner-
|
| +** most loop)
|
| +**
|
| +** OUTER JOINS
|
| +**
|
| +** An outer join of tables t1 and t2 is conceptally coded as follows:
|
| +**
|
| +** foreach row1 in t1 do
|
| +** flag = 0
|
| +** foreach row2 in t2 do
|
| +** start:
|
| +** ...
|
| +** flag = 1
|
| +** end
|
| +** if flag==0 then
|
| +** move the row2 cursor to a null row
|
| +** goto start
|
| +** fi
|
| +** end
|
| +**
|
| +** ORDER BY CLAUSE PROCESSING
|
| +**
|
| +** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
|
| +** if there is one. If there is no ORDER BY clause or if this routine
|
| +** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
|
| +**
|
| +** If an index can be used so that the natural output order of the table
|
| +** scan is correct for the ORDER BY clause, then that index is used and
|
| +** *ppOrderBy is set to NULL. This is an optimization that prevents an
|
| +** unnecessary sort of the result set if an index appropriate for the
|
| +** ORDER BY clause already exists.
|
| +**
|
| +** If the where clause loops cannot be arranged to provide the correct
|
| +** output order, then the *ppOrderBy is unchanged.
|
| +*/
|
| +WhereInfo *sqlite3WhereBegin(
|
| + Parse *pParse, /* The parser context */
|
| + SrcList *pTabList, /* A list of all tables to be scanned */
|
| + Expr *pWhere, /* The WHERE clause */
|
| + ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
|
| + u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */
|
| +){
|
| + int i; /* Loop counter */
|
| + int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
|
| + int nTabList; /* Number of elements in pTabList */
|
| + WhereInfo *pWInfo; /* Will become the return value of this function */
|
| + Vdbe *v = pParse->pVdbe; /* The virtual database engine */
|
| + Bitmask notReady; /* Cursors that are not yet positioned */
|
| + WhereMaskSet *pMaskSet; /* The expression mask set */
|
| + WhereClause *pWC; /* Decomposition of the WHERE clause */
|
| + struct SrcList_item *pTabItem; /* A single entry from pTabList */
|
| + WhereLevel *pLevel; /* A single level in the pWInfo list */
|
| + int iFrom; /* First unused FROM clause element */
|
| + int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */
|
| + sqlite3 *db; /* Database connection */
|
| +
|
| + /* The number of tables in the FROM clause is limited by the number of
|
| + ** bits in a Bitmask
|
| + */
|
| + testcase( pTabList->nSrc==BMS );
|
| + if( pTabList->nSrc>BMS ){
|
| + sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
|
| + return 0;
|
| + }
|
| +
|
| + /* This function normally generates a nested loop for all tables in
|
| + ** pTabList. But if the WHERE_ONETABLE_ONLY flag is set, then we should
|
| + ** only generate code for the first table in pTabList and assume that
|
| + ** any cursors associated with subsequent tables are uninitialized.
|
| + */
|
| + nTabList = (wctrlFlags & WHERE_ONETABLE_ONLY) ? 1 : pTabList->nSrc;
|
| +
|
| + /* Allocate and initialize the WhereInfo structure that will become the
|
| + ** return value. A single allocation is used to store the WhereInfo
|
| + ** struct, the contents of WhereInfo.a[], the WhereClause structure
|
| + ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
|
| + ** field (type Bitmask) it must be aligned on an 8-byte boundary on
|
| + ** some architectures. Hence the ROUND8() below.
|
| + */
|
| + db = pParse->db;
|
| + nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
|
| + pWInfo = sqlite3DbMallocZero(db,
|
| + nByteWInfo +
|
| + sizeof(WhereClause) +
|
| + sizeof(WhereMaskSet)
|
| + );
|
| + if( db->mallocFailed ){
|
| + sqlite3DbFree(db, pWInfo);
|
| + pWInfo = 0;
|
| + goto whereBeginError;
|
| + }
|
| + pWInfo->nLevel = nTabList;
|
| + pWInfo->pParse = pParse;
|
| + pWInfo->pTabList = pTabList;
|
| + pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
|
| + pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
|
| + pWInfo->wctrlFlags = wctrlFlags;
|
| + pWInfo->savedNQueryLoop = pParse->nQueryLoop;
|
| + pMaskSet = (WhereMaskSet*)&pWC[1];
|
| +
|
| + /* Split the WHERE clause into separate subexpressions where each
|
| + ** subexpression is separated by an AND operator.
|
| + */
|
| + initMaskSet(pMaskSet);
|
| + whereClauseInit(pWC, pParse, pMaskSet);
|
| + sqlite3ExprCodeConstants(pParse, pWhere);
|
| + whereSplit(pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */
|
| +
|
| + /* Special case: a WHERE clause that is constant. Evaluate the
|
| + ** expression and either jump over all of the code or fall thru.
|
| + */
|
| + if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
|
| + sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
|
| + pWhere = 0;
|
| + }
|
| +
|
| + /* Assign a bit from the bitmask to every term in the FROM clause.
|
| + **
|
| + ** When assigning bitmask values to FROM clause cursors, it must be
|
| + ** the case that if X is the bitmask for the N-th FROM clause term then
|
| + ** the bitmask for all FROM clause terms to the left of the N-th term
|
| + ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
|
| + ** its Expr.iRightJoinTable value to find the bitmask of the right table
|
| + ** of the join. Subtracting one from the right table bitmask gives a
|
| + ** bitmask for all tables to the left of the join. Knowing the bitmask
|
| + ** for all tables to the left of a left join is important. Ticket #3015.
|
| + **
|
| + ** Configure the WhereClause.vmask variable so that bits that correspond
|
| + ** to virtual table cursors are set. This is used to selectively disable
|
| + ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
|
| + ** with virtual tables.
|
| + **
|
| + ** Note that bitmasks are created for all pTabList->nSrc tables in
|
| + ** pTabList, not just the first nTabList tables. nTabList is normally
|
| + ** equal to pTabList->nSrc but might be shortened to 1 if the
|
| + ** WHERE_ONETABLE_ONLY flag is set.
|
| + */
|
| + assert( pWC->vmask==0 && pMaskSet->n==0 );
|
| + for(i=0; i<pTabList->nSrc; i++){
|
| + createMask(pMaskSet, pTabList->a[i].iCursor);
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + if( ALWAYS(pTabList->a[i].pTab) && IsVirtual(pTabList->a[i].pTab) ){
|
| + pWC->vmask |= ((Bitmask)1 << i);
|
| + }
|
| +#endif
|
| + }
|
| +#ifndef NDEBUG
|
| + {
|
| + Bitmask toTheLeft = 0;
|
| + for(i=0; i<pTabList->nSrc; i++){
|
| + Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
|
| + assert( (m-1)==toTheLeft );
|
| + toTheLeft |= m;
|
| + }
|
| + }
|
| +#endif
|
| +
|
| + /* Analyze all of the subexpressions. Note that exprAnalyze() might
|
| + ** add new virtual terms onto the end of the WHERE clause. We do not
|
| + ** want to analyze these virtual terms, so start analyzing at the end
|
| + ** and work forward so that the added virtual terms are never processed.
|
| + */
|
| + exprAnalyzeAll(pTabList, pWC);
|
| + if( db->mallocFailed ){
|
| + goto whereBeginError;
|
| + }
|
| +
|
| + /* Chose the best index to use for each table in the FROM clause.
|
| + **
|
| + ** This loop fills in the following fields:
|
| + **
|
| + ** pWInfo->a[].pIdx The index to use for this level of the loop.
|
| + ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx
|
| + ** pWInfo->a[].nEq The number of == and IN constraints
|
| + ** pWInfo->a[].iFrom Which term of the FROM clause is being coded
|
| + ** pWInfo->a[].iTabCur The VDBE cursor for the database table
|
| + ** pWInfo->a[].iIdxCur The VDBE cursor for the index
|
| + ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term
|
| + **
|
| + ** This loop also figures out the nesting order of tables in the FROM
|
| + ** clause.
|
| + */
|
| + notReady = ~(Bitmask)0;
|
| + andFlags = ~0;
|
| + WHERETRACE(("*** Optimizer Start ***\n"));
|
| + for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
|
| + WhereCost bestPlan; /* Most efficient plan seen so far */
|
| + Index *pIdx; /* Index for FROM table at pTabItem */
|
| + int j; /* For looping over FROM tables */
|
| + int bestJ = -1; /* The value of j */
|
| + Bitmask m; /* Bitmask value for j or bestJ */
|
| + int isOptimal; /* Iterator for optimal/non-optimal search */
|
| + int nUnconstrained; /* Number tables without INDEXED BY */
|
| + Bitmask notIndexed; /* Mask of tables that cannot use an index */
|
| +
|
| + memset(&bestPlan, 0, sizeof(bestPlan));
|
| + bestPlan.rCost = SQLITE_BIG_DBL;
|
| + WHERETRACE(("*** Begin search for loop %d ***\n", i));
|
| +
|
| + /* Loop through the remaining entries in the FROM clause to find the
|
| + ** next nested loop. The loop tests all FROM clause entries
|
| + ** either once or twice.
|
| + **
|
| + ** The first test is always performed if there are two or more entries
|
| + ** remaining and never performed if there is only one FROM clause entry
|
| + ** to choose from. The first test looks for an "optimal" scan. In
|
| + ** this context an optimal scan is one that uses the same strategy
|
| + ** for the given FROM clause entry as would be selected if the entry
|
| + ** were used as the innermost nested loop. In other words, a table
|
| + ** is chosen such that the cost of running that table cannot be reduced
|
| + ** by waiting for other tables to run first. This "optimal" test works
|
| + ** by first assuming that the FROM clause is on the inner loop and finding
|
| + ** its query plan, then checking to see if that query plan uses any
|
| + ** other FROM clause terms that are notReady. If no notReady terms are
|
| + ** used then the "optimal" query plan works.
|
| + **
|
| + ** Note that the WhereCost.nRow parameter for an optimal scan might
|
| + ** not be as small as it would be if the table really were the innermost
|
| + ** join. The nRow value can be reduced by WHERE clause constraints
|
| + ** that do not use indices. But this nRow reduction only happens if the
|
| + ** table really is the innermost join.
|
| + **
|
| + ** The second loop iteration is only performed if no optimal scan
|
| + ** strategies were found by the first iteration. This second iteration
|
| + ** is used to search for the lowest cost scan overall.
|
| + **
|
| + ** Previous versions of SQLite performed only the second iteration -
|
| + ** the next outermost loop was always that with the lowest overall
|
| + ** cost. However, this meant that SQLite could select the wrong plan
|
| + ** for scripts such as the following:
|
| + **
|
| + ** CREATE TABLE t1(a, b);
|
| + ** CREATE TABLE t2(c, d);
|
| + ** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
|
| + **
|
| + ** The best strategy is to iterate through table t1 first. However it
|
| + ** is not possible to determine this with a simple greedy algorithm.
|
| + ** Since the cost of a linear scan through table t2 is the same
|
| + ** as the cost of a linear scan through table t1, a simple greedy
|
| + ** algorithm may choose to use t2 for the outer loop, which is a much
|
| + ** costlier approach.
|
| + */
|
| + nUnconstrained = 0;
|
| + notIndexed = 0;
|
| + for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
|
| + Bitmask mask; /* Mask of tables not yet ready */
|
| + for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
|
| + int doNotReorder; /* True if this table should not be reordered */
|
| + WhereCost sCost; /* Cost information from best[Virtual]Index() */
|
| + ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
|
| +
|
| + doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
|
| + if( j!=iFrom && doNotReorder ) break;
|
| + m = getMask(pMaskSet, pTabItem->iCursor);
|
| + if( (m & notReady)==0 ){
|
| + if( j==iFrom ) iFrom++;
|
| + continue;
|
| + }
|
| + mask = (isOptimal ? m : notReady);
|
| + pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
|
| + if( pTabItem->pIndex==0 ) nUnconstrained++;
|
| +
|
| + WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
|
| + j, isOptimal));
|
| + assert( pTabItem->pTab );
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + if( IsVirtual(pTabItem->pTab) ){
|
| + sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
|
| + bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
|
| + &sCost, pp);
|
| + }else
|
| +#endif
|
| + {
|
| + bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
|
| + &sCost);
|
| + }
|
| + assert( isOptimal || (sCost.used¬Ready)==0 );
|
| +
|
| + /* If an INDEXED BY clause is present, then the plan must use that
|
| + ** index if it uses any index at all */
|
| + assert( pTabItem->pIndex==0
|
| + || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
|
| + || sCost.plan.u.pIdx==pTabItem->pIndex );
|
| +
|
| + if( isOptimal && (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
|
| + notIndexed |= m;
|
| + }
|
| +
|
| + /* Conditions under which this table becomes the best so far:
|
| + **
|
| + ** (1) The table must not depend on other tables that have not
|
| + ** yet run.
|
| + **
|
| + ** (2) A full-table-scan plan cannot supercede indexed plan unless
|
| + ** the full-table-scan is an "optimal" plan as defined above.
|
| + **
|
| + ** (3) All tables have an INDEXED BY clause or this table lacks an
|
| + ** INDEXED BY clause or this table uses the specific
|
| + ** index specified by its INDEXED BY clause. This rule ensures
|
| + ** that a best-so-far is always selected even if an impossible
|
| + ** combination of INDEXED BY clauses are given. The error
|
| + ** will be detected and relayed back to the application later.
|
| + ** The NEVER() comes about because rule (2) above prevents
|
| + ** An indexable full-table-scan from reaching rule (3).
|
| + **
|
| + ** (4) The plan cost must be lower than prior plans or else the
|
| + ** cost must be the same and the number of rows must be lower.
|
| + */
|
| + if( (sCost.used¬Ready)==0 /* (1) */
|
| + && (bestJ<0 || (notIndexed&m)!=0 /* (2) */
|
| + || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
|
| + || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
|
| + && (nUnconstrained==0 || pTabItem->pIndex==0 /* (3) */
|
| + || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
|
| + && (bestJ<0 || sCost.rCost<bestPlan.rCost /* (4) */
|
| + || (sCost.rCost<=bestPlan.rCost
|
| + && sCost.plan.nRow<bestPlan.plan.nRow))
|
| + ){
|
| + WHERETRACE(("=== table %d is best so far"
|
| + " with cost=%g and nRow=%g\n",
|
| + j, sCost.rCost, sCost.plan.nRow));
|
| + bestPlan = sCost;
|
| + bestJ = j;
|
| + }
|
| + if( doNotReorder ) break;
|
| + }
|
| + }
|
| + assert( bestJ>=0 );
|
| + assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
|
| + WHERETRACE(("*** Optimizer selects table %d for loop %d"
|
| + " with cost=%g and nRow=%g\n",
|
| + bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));
|
| + if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
|
| + *ppOrderBy = 0;
|
| + }
|
| + andFlags &= bestPlan.plan.wsFlags;
|
| + pLevel->plan = bestPlan.plan;
|
| + testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
|
| + testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
|
| + if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
|
| + pLevel->iIdxCur = pParse->nTab++;
|
| + }else{
|
| + pLevel->iIdxCur = -1;
|
| + }
|
| + notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
|
| + pLevel->iFrom = (u8)bestJ;
|
| + if( bestPlan.plan.nRow>=(double)1 ){
|
| + pParse->nQueryLoop *= bestPlan.plan.nRow;
|
| + }
|
| +
|
| + /* Check that if the table scanned by this loop iteration had an
|
| + ** INDEXED BY clause attached to it, that the named index is being
|
| + ** used for the scan. If not, then query compilation has failed.
|
| + ** Return an error.
|
| + */
|
| + pIdx = pTabList->a[bestJ].pIndex;
|
| + if( pIdx ){
|
| + if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
|
| + sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
|
| + goto whereBeginError;
|
| + }else{
|
| + /* If an INDEXED BY clause is used, the bestIndex() function is
|
| + ** guaranteed to find the index specified in the INDEXED BY clause
|
| + ** if it find an index at all. */
|
| + assert( bestPlan.plan.u.pIdx==pIdx );
|
| + }
|
| + }
|
| + }
|
| + WHERETRACE(("*** Optimizer Finished ***\n"));
|
| + if( pParse->nErr || db->mallocFailed ){
|
| + goto whereBeginError;
|
| + }
|
| +
|
| + /* If the total query only selects a single row, then the ORDER BY
|
| + ** clause is irrelevant.
|
| + */
|
| + if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
|
| + *ppOrderBy = 0;
|
| + }
|
| +
|
| + /* If the caller is an UPDATE or DELETE statement that is requesting
|
| + ** to use a one-pass algorithm, determine if this is appropriate.
|
| + ** The one-pass algorithm only works if the WHERE clause constraints
|
| + ** the statement to update a single row.
|
| + */
|
| + assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
|
| + if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
|
| + pWInfo->okOnePass = 1;
|
| + pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
|
| + }
|
| +
|
| + /* Open all tables in the pTabList and any indices selected for
|
| + ** searching those tables.
|
| + */
|
| + sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
|
| + notReady = ~(Bitmask)0;
|
| + pWInfo->nRowOut = (double)1;
|
| + for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
|
| + Table *pTab; /* Table to open */
|
| + int iDb; /* Index of database containing table/index */
|
| +
|
| + pTabItem = &pTabList->a[pLevel->iFrom];
|
| + pTab = pTabItem->pTab;
|
| + pLevel->iTabCur = pTabItem->iCursor;
|
| + pWInfo->nRowOut *= pLevel->plan.nRow;
|
| + iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
|
| + if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
|
| + /* Do nothing */
|
| + }else
|
| +#ifndef SQLITE_OMIT_VIRTUALTABLE
|
| + if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
|
| + const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
|
| + int iCur = pTabItem->iCursor;
|
| + sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
|
| + }else
|
| +#endif
|
| + if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
|
| + && (wctrlFlags & WHERE_OMIT_OPEN)==0 ){
|
| + int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
|
| + sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
|
| + testcase( pTab->nCol==BMS-1 );
|
| + testcase( pTab->nCol==BMS );
|
| + if( !pWInfo->okOnePass && pTab->nCol<BMS ){
|
| + Bitmask b = pTabItem->colUsed;
|
| + int n = 0;
|
| + for(; b; b=b>>1, n++){}
|
| + sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1,
|
| + SQLITE_INT_TO_PTR(n), P4_INT32);
|
| + assert( n<=pTab->nCol );
|
| + }
|
| + }else{
|
| + sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
|
| + }
|
| +#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
|
| + if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
|
| + constructAutomaticIndex(pParse, pWC, pTabItem, notReady, pLevel);
|
| + }else
|
| +#endif
|
| + if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
|
| + Index *pIx = pLevel->plan.u.pIdx;
|
| + KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
|
| + int iIdxCur = pLevel->iIdxCur;
|
| + assert( pIx->pSchema==pTab->pSchema );
|
| + assert( iIdxCur>=0 );
|
| + sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
|
| + (char*)pKey, P4_KEYINFO_HANDOFF);
|
| + VdbeComment((v, "%s", pIx->zName));
|
| + }
|
| + sqlite3CodeVerifySchema(pParse, iDb);
|
| + notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor);
|
| + }
|
| + pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
|
| + if( db->mallocFailed ) goto whereBeginError;
|
| +
|
| + /* Generate the code to do the search. Each iteration of the for
|
| + ** loop below generates code for a single nested loop of the VM
|
| + ** program.
|
| + */
|
| + notReady = ~(Bitmask)0;
|
| + for(i=0; i<nTabList; i++){
|
| + pLevel = &pWInfo->a[i];
|
| + explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
|
| + notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady);
|
| + pWInfo->iContinue = pLevel->addrCont;
|
| + }
|
| +
|
| +#ifdef SQLITE_TEST /* For testing and debugging use only */
|
| + /* Record in the query plan information about the current table
|
| + ** and the index used to access it (if any). If the table itself
|
| + ** is not used, its name is just '{}'. If no index is used
|
| + ** the index is listed as "{}". If the primary key is used the
|
| + ** index name is '*'.
|
| + */
|
| + for(i=0; i<nTabList; i++){
|
| + char *z;
|
| + int n;
|
| + pLevel = &pWInfo->a[i];
|
| + pTabItem = &pTabList->a[pLevel->iFrom];
|
| + z = pTabItem->zAlias;
|
| + if( z==0 ) z = pTabItem->pTab->zName;
|
| + n = sqlite3Strlen30(z);
|
| + if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
|
| + if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
|
| + memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
|
| + nQPlan += 2;
|
| + }else{
|
| + memcpy(&sqlite3_query_plan[nQPlan], z, n);
|
| + nQPlan += n;
|
| + }
|
| + sqlite3_query_plan[nQPlan++] = ' ';
|
| + }
|
| + testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
|
| + testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
|
| + if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
|
| + memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
|
| + nQPlan += 2;
|
| + }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
|
| + n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
|
| + if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
|
| + memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
|
| + nQPlan += n;
|
| + sqlite3_query_plan[nQPlan++] = ' ';
|
| + }
|
| + }else{
|
| + memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
|
| + nQPlan += 3;
|
| + }
|
| + }
|
| + while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
|
| + sqlite3_query_plan[--nQPlan] = 0;
|
| + }
|
| + sqlite3_query_plan[nQPlan] = 0;
|
| + nQPlan = 0;
|
| +#endif /* SQLITE_TEST // Testing and debugging use only */
|
| +
|
| + /* Record the continuation address in the WhereInfo structure. Then
|
| + ** clean up and return.
|
| + */
|
| + return pWInfo;
|
| +
|
| + /* Jump here if malloc fails */
|
| +whereBeginError:
|
| + if( pWInfo ){
|
| + pParse->nQueryLoop = pWInfo->savedNQueryLoop;
|
| + whereInfoFree(db, pWInfo);
|
| + }
|
| + return 0;
|
| +}
|
| +
|
| +/*
|
| +** Generate the end of the WHERE loop. See comments on
|
| +** sqlite3WhereBegin() for additional information.
|
| +*/
|
| +void sqlite3WhereEnd(WhereInfo *pWInfo){
|
| + Parse *pParse = pWInfo->pParse;
|
| + Vdbe *v = pParse->pVdbe;
|
| + int i;
|
| + WhereLevel *pLevel;
|
| + SrcList *pTabList = pWInfo->pTabList;
|
| + sqlite3 *db = pParse->db;
|
| +
|
| + /* Generate loop termination code.
|
| + */
|
| + sqlite3ExprCacheClear(pParse);
|
| + for(i=pWInfo->nLevel-1; i>=0; i--){
|
| + pLevel = &pWInfo->a[i];
|
| + sqlite3VdbeResolveLabel(v, pLevel->addrCont);
|
| + if( pLevel->op!=OP_Noop ){
|
| + sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
|
| + sqlite3VdbeChangeP5(v, pLevel->p5);
|
| + }
|
| + if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
|
| + struct InLoop *pIn;
|
| + int j;
|
| + sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
|
| + for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
|
| + sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
|
| + sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
|
| + sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
|
| + }
|
| + sqlite3DbFree(db, pLevel->u.in.aInLoop);
|
| + }
|
| + sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
|
| + if( pLevel->iLeftJoin ){
|
| + int addr;
|
| + addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
|
| + assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
|
| + || (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 );
|
| + if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
|
| + sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
|
| + }
|
| + if( pLevel->iIdxCur>=0 ){
|
| + sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
|
| + }
|
| + if( pLevel->op==OP_Return ){
|
| + sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
|
| + }else{
|
| + sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
|
| + }
|
| + sqlite3VdbeJumpHere(v, addr);
|
| + }
|
| + }
|
| +
|
| + /* The "break" point is here, just past the end of the outer loop.
|
| + ** Set it.
|
| + */
|
| + sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
|
| +
|
| + /* Close all of the cursors that were opened by sqlite3WhereBegin.
|
| + */
|
| + assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
|
| + for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
|
| + struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
|
| + Table *pTab = pTabItem->pTab;
|
| + assert( pTab!=0 );
|
| + if( (pTab->tabFlags & TF_Ephemeral)==0
|
| + && pTab->pSelect==0
|
| + && (pWInfo->wctrlFlags & WHERE_OMIT_CLOSE)==0
|
| + ){
|
| + int ws = pLevel->plan.wsFlags;
|
| + if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
|
| + sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
|
| + }
|
| + if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
|
| + sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
|
| + }
|
| + }
|
| +
|
| + /* If this scan uses an index, make code substitutions to read data
|
| + ** from the index in preference to the table. Sometimes, this means
|
| + ** the table need never be read from. This is a performance boost,
|
| + ** as the vdbe level waits until the table is read before actually
|
| + ** seeking the table cursor to the record corresponding to the current
|
| + ** position in the index.
|
| + **
|
| + ** Calls to the code generator in between sqlite3WhereBegin and
|
| + ** sqlite3WhereEnd will have created code that references the table
|
| + ** directly. This loop scans all that code looking for opcodes
|
| + ** that reference the table and converts them into opcodes that
|
| + ** reference the index.
|
| + */
|
| + if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){
|
| + int k, j, last;
|
| + VdbeOp *pOp;
|
| + Index *pIdx = pLevel->plan.u.pIdx;
|
| +
|
| + assert( pIdx!=0 );
|
| + pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
|
| + last = sqlite3VdbeCurrentAddr(v);
|
| + for(k=pWInfo->iTop; k<last; k++, pOp++){
|
| + if( pOp->p1!=pLevel->iTabCur ) continue;
|
| + if( pOp->opcode==OP_Column ){
|
| + for(j=0; j<pIdx->nColumn; j++){
|
| + if( pOp->p2==pIdx->aiColumn[j] ){
|
| + pOp->p2 = j;
|
| + pOp->p1 = pLevel->iIdxCur;
|
| + break;
|
| + }
|
| + }
|
| + assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
|
| + || j<pIdx->nColumn );
|
| + }else if( pOp->opcode==OP_Rowid ){
|
| + pOp->p1 = pLevel->iIdxCur;
|
| + pOp->opcode = OP_IdxRowid;
|
| + }
|
| + }
|
| + }
|
| + }
|
| +
|
| + /* Final cleanup
|
| + */
|
| + pParse->nQueryLoop = pWInfo->savedNQueryLoop;
|
| + whereInfoFree(db, pWInfo);
|
| + return;
|
| +}
|
|
|
Chromium Code Reviews
Issue 694353003:
Get `gn gen` to succeed on Windows (Closed)
Base URL: https://github.com/domokit/mojo.git@master