1 /*

     2 ** 2001 September 15

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 ** This module contains C code that generates VDBE code used to process

    13 ** the WHERE clause of SQL statements.  This module is reponsible for

    14 ** generating the code that loops through a table looking for applicable

    15 ** rows.  Indices are selected and used to speed the search when doing

    16 ** so is applicable.  Because this module is responsible for selecting

    17 ** indices, you might also think of this module as the "query optimizer".

    18 **

    19 ** $Id: where.cpp 1282 2008-11-13 09:31:33Z LarsPson $

    20 */

    21 #include "sqliteInt.h"

    22 

    23 /*

    24 ** The number of bits in a Bitmask.  "BMS" means "BitMask Size".

    25 */

    26 #define BMS  (sizeof(Bitmask)*8)

    27 

    28 /*

    29 ** Trace output macros

    30 */

    31 #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)

    32 int sqlite3_where_trace = 0;

    33 # define WHERETRACE(X)  if(sqlite3_where_trace) sqlite3DebugPrintf X

    34 #else

    35 # define WHERETRACE(X)

    36 #endif

    37 

    38 /* Forward reference

    39 */

    40 typedef struct WhereClause WhereClause;

    41 typedef struct ExprMaskSet ExprMaskSet;

    42 

    43 /*

    44 ** The query generator uses an array of instances of this structure to

    45 ** help it analyze the subexpressions of the WHERE clause.  Each WHERE

    46 ** clause subexpression is separated from the others by an AND operator.

    47 **

    48 ** All WhereTerms are collected into a single WhereClause structure.  

    49 ** The following identity holds:

    50 **

    51 **        WhereTerm.pWC->a[WhereTerm.idx] == WhereTerm

    52 **

    53 ** When a term is of the form:

    54 **

    55 **              X <op> <expr>

    56 **

    57 ** where X is a column name and <op> is one of certain operators,

    58 ** then WhereTerm.leftCursor and WhereTerm.leftColumn record the

    59 ** cursor number and column number for X.  WhereTerm.operator records

    60 ** the <op> using a bitmask encoding defined by WO_xxx below.  The

    61 ** use of a bitmask encoding for the operator allows us to search

    62 ** quickly for terms that match any of several different operators.

    63 **

    64 ** prereqRight and prereqAll record sets of cursor numbers,

    65 ** but they do so indirectly.  A single ExprMaskSet structure translates

    66 ** cursor number into bits and the translated bit is stored in the prereq

    67 ** fields.  The translation is used in order to maximize the number of

    68 ** bits that will fit in a Bitmask.  The VDBE cursor numbers might be

    69 ** spread out over the non-negative integers.  For example, the cursor

    70 ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45.  The ExprMaskSet

    71 ** translates these sparse cursor numbers into consecutive integers

    72 ** beginning with 0 in order to make the best possible use of the available

    73 ** bits in the Bitmask.  So, in the example above, the cursor numbers

    74 ** would be mapped into integers 0 through 7.

    75 */

    76 typedef struct WhereTerm WhereTerm;

    77 struct WhereTerm {

    78   Expr *pExpr;            /* Pointer to the subexpression */

    79   i16 iParent;            /* Disable pWC->a[iParent] when this term disabled */

    80   i16 leftCursor;         /* Cursor number of X in "X <op> <expr>" */

    81   i16 leftColumn;         /* Column number of X in "X <op> <expr>" */

    82   u16 eOperator;          /* A WO_xx value describing <op> */

    83   u8 flags;               /* Bit flags.  See below */

    84   u8 nChild;              /* Number of children that must disable us */

    85   WhereClause *pWC;       /* The clause this term is part of */

    86   Bitmask prereqRight;    /* Bitmask of tables used by pRight */

    87   Bitmask prereqAll;      /* Bitmask of tables referenced by p */

    88 };

    89 

    90 /*

    91 ** Allowed values of WhereTerm.flags

    92 */

    93 #define TERM_DYNAMIC    0x01   /* Need to call sqlite3ExprDelete(pExpr) */

    94 #define TERM_VIRTUAL    0x02   /* Added by the optimizer.  Do not code */

    95 #define TERM_CODED      0x04   /* This term is already coded */

    96 #define TERM_COPIED     0x08   /* Has a child */

    97 #define TERM_OR_OK      0x10   /* Used during OR-clause processing */

    98 

    99 /*

   100 ** An instance of the following structure holds all information about a

   101 ** WHERE clause.  Mostly this is a container for one or more WhereTerms.

   102 */

   103 struct WhereClause {

   104   Parse *pParse;           /* The parser context */

   105   ExprMaskSet *pMaskSet;   /* Mapping of table indices to bitmasks */

   106   int nTerm;               /* Number of terms */

   107   int nSlot;               /* Number of entries in a[] */

   108   WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */

   109   WhereTerm aStatic[10];   /* Initial static space for a[] */

   110 };

   111 

   112 /*

   113 ** An instance of the following structure keeps track of a mapping

   114 ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.

   115 **

   116 ** The VDBE cursor numbers are small integers contained in 

   117 ** SrcList_item.iCursor and Expr.iTable fields.  For any given WHERE 

   118 ** clause, the cursor numbers might not begin with 0 and they might

   119 ** contain gaps in the numbering sequence.  But we want to make maximum

   120 ** use of the bits in our bitmasks.  This structure provides a mapping

   121 ** from the sparse cursor numbers into consecutive integers beginning

   122 ** with 0.

   123 **

   124 ** If ExprMaskSet.ix[A]==B it means that The A-th bit of a Bitmask

   125 ** corresponds VDBE cursor number B.  The A-th bit of a bitmask is 1<<A.

   126 **

   127 ** For example, if the WHERE clause expression used these VDBE

   128 ** cursors:  4, 5, 8, 29, 57, 73.  Then the  ExprMaskSet structure

   129 ** would map those cursor numbers into bits 0 through 5.

   130 **

   131 ** Note that the mapping is not necessarily ordered.  In the example

   132 ** above, the mapping might go like this:  4->3, 5->1, 8->2, 29->0,

   133 ** 57->5, 73->4.  Or one of 719 other combinations might be used. It

   134 ** does not really matter.  What is important is that sparse cursor

   135 ** numbers all get mapped into bit numbers that begin with 0 and contain

   136 ** no gaps.

   137 */

   138 struct ExprMaskSet {

   139   int n;                        /* Number of assigned cursor values */

   140   int ix[sizeof(Bitmask)*8];    /* Cursor assigned to each bit */

   141 };

   142 

   143 

   144 /*

   145 ** Bitmasks for the operators that indices are able to exploit.  An

   146 ** OR-ed combination of these values can be used when searching for

   147 ** terms in the where clause.

   148 */

   149 #define WO_IN     1

   150 #define WO_EQ     2

   151 #define WO_LT     (WO_EQ<<(TK_LT-TK_EQ))

   152 #define WO_LE     (WO_EQ<<(TK_LE-TK_EQ))

   153 #define WO_GT     (WO_EQ<<(TK_GT-TK_EQ))

   154 #define WO_GE     (WO_EQ<<(TK_GE-TK_EQ))

   155 #define WO_MATCH  64

   156 #define WO_ISNULL 128

   157 

   158 /*

   159 ** Value for flags returned by bestIndex().  

   160 **

   161 ** The least significant byte is reserved as a mask for WO_ values above.

   162 ** The WhereLevel.flags field is usually set to WO_IN|WO_EQ|WO_ISNULL.

   163 ** But if the table is the right table of a left join, WhereLevel.flags

   164 ** is set to WO_IN|WO_EQ.  The WhereLevel.flags field can then be used as

   165 ** the "op" parameter to findTerm when we are resolving equality constraints.

   166 ** ISNULL constraints will then not be used on the right table of a left

   167 ** join.  Tickets #2177 and #2189.

   168 */

   169 #define WHERE_ROWID_EQ     0x000100   /* rowid=EXPR or rowid IN (...) */

   170 #define WHERE_ROWID_RANGE  0x000200   /* rowid<EXPR and/or rowid>EXPR */

   171 #define WHERE_COLUMN_EQ    0x001000   /* x=EXPR or x IN (...) */

   172 #define WHERE_COLUMN_RANGE 0x002000   /* x<EXPR and/or x>EXPR */

   173 #define WHERE_COLUMN_IN    0x004000   /* x IN (...) */

   174 #define WHERE_TOP_LIMIT    0x010000   /* x<EXPR or x<=EXPR constraint */

   175 #define WHERE_BTM_LIMIT    0x020000   /* x>EXPR or x>=EXPR constraint */

   176 #define WHERE_IDX_ONLY     0x080000   /* Use index only - omit table */

   177 #define WHERE_ORDERBY      0x100000   /* Output will appear in correct order */

   178 #define WHERE_REVERSE      0x200000   /* Scan in reverse order */

   179 #define WHERE_UNIQUE       0x400000   /* Selects no more than one row */

   180 #define WHERE_VIRTUALTABLE 0x800000   /* Use virtual-table processing */

   181 

   182 /*

   183 ** Initialize a preallocated WhereClause structure.

   184 */

   185 static void whereClauseInit(

   186   WhereClause *pWC,        /* The WhereClause to be initialized */

   187   Parse *pParse,           /* The parsing context */

   188   ExprMaskSet *pMaskSet    /* Mapping from table indices to bitmasks */

   189 ){

   190   pWC->pParse = pParse;

   191   pWC->pMaskSet = pMaskSet;

   192   pWC->nTerm = 0;

   193   pWC->nSlot = ArraySize(pWC->aStatic);

   194   pWC->a = pWC->aStatic;

   195 }

   196 

   197 /*

   198 ** Deallocate a WhereClause structure.  The WhereClause structure

   199 ** itself is not freed.  This routine is the inverse of whereClauseInit().

   200 */

   201 static void whereClauseClear(WhereClause *pWC){

   202   int i;

   203   WhereTerm *a;

   204   for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){

   205     if( a->flags & TERM_DYNAMIC ){

   206       sqlite3ExprDelete(a->pExpr);

   207     }

   208   }

   209   if( pWC->a!=pWC->aStatic ){

   210     sqlite3_free(pWC->a);

   211   }

   212 }

   213 

   214 /*

   215 ** Add a new entries to the WhereClause structure.  Increase the allocated

   216 ** space as necessary.

   217 **

   218 ** If the flags argument includes TERM_DYNAMIC, then responsibility

   219 ** for freeing the expression p is assumed by the WhereClause object.

   220 **

   221 ** WARNING:  This routine might reallocate the space used to store

   222 ** WhereTerms.  All pointers to WhereTerms should be invalided after

   223 ** calling this routine.  Such pointers may be reinitialized by referencing

   224 ** the pWC->a[] array.

   225 */

   226 static int whereClauseInsert(WhereClause *pWC, Expr *p, int flags){

   227   WhereTerm *pTerm;

   228   int idx;

   229   if( pWC->nTerm>=pWC->nSlot ){

   230     WhereTerm *pOld = pWC->a;

   231     pWC->a = (WhereTerm*)sqlite3_malloc( sizeof(pWC->a[0])*pWC->nSlot*2 );

   232     if( pWC->a==0 ){

   233       pWC->pParse->db->mallocFailed = 1;

   234       if( flags & TERM_DYNAMIC ){

   235         sqlite3ExprDelete(p);

   236       }

   237       pWC->a = pOld;

   238       return 0;

   239     }

   240     memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);

   241     if( pOld!=pWC->aStatic ){

   242       sqlite3_free(pOld);

   243     }

   244     pWC->nSlot *= 2;

   245   }

   246   pTerm = &pWC->a[idx = pWC->nTerm];

   247   pWC->nTerm++;

   248   pTerm->pExpr = p;

   249   pTerm->flags = flags;

   250   pTerm->pWC = pWC;

   251   pTerm->iParent = -1;

   252   return idx;

   253 }

   254 

   255 /*

   256 ** This routine identifies subexpressions in the WHERE clause where

   257 ** each subexpression is separated by the AND operator or some other

   258 ** operator specified in the op parameter.  The WhereClause structure

   259 ** is filled with pointers to subexpressions.  For example:

   260 **

   261 **    WHERE  a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)

   262 **           \________/     \_______________/     \________________/

   263 **            slot[0]            slot[1]               slot[2]

   264 **

   265 ** The original WHERE clause in pExpr is unaltered.  All this routine

   266 ** does is make slot[] entries point to substructure within pExpr.

   267 **

   268 ** In the previous sentence and in the diagram, "slot[]" refers to

   269 ** the WhereClause.a[] array.  This array grows as needed to contain

   270 ** all terms of the WHERE clause.

   271 */

   272 static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){

   273   if( pExpr==0 ) return;

   274   if( pExpr->op!=op ){

   275     whereClauseInsert(pWC, pExpr, 0);

   276   }else{

   277     whereSplit(pWC, pExpr->pLeft, op);

   278     whereSplit(pWC, pExpr->pRight, op);

   279   }

   280 }

   281 

   282 /*

   283 ** Initialize an expression mask set

   284 */

   285 #define initMaskSet(P)  memset(P, 0, sizeof(*P))

   286 

   287 /*

   288 ** Return the bitmask for the given cursor number.  Return 0 if

   289 ** iCursor is not in the set.

   290 */

   291 static Bitmask getMask(ExprMaskSet *pMaskSet, int iCursor){

   292   int i;

   293   for(i=0; i<pMaskSet->n; i++){

   294     if( pMaskSet->ix[i]==iCursor ){

   295       return ((Bitmask)1)<<i;

   296     }

   297   }

   298   return 0;

   299 }

   300 

   301 /*

   302 ** Create a new mask for cursor iCursor.

   303 **

   304 ** There is one cursor per table in the FROM clause.  The number of

   305 ** tables in the FROM clause is limited by a test early in the

   306 ** sqlite3WhereBegin() routine.  So we know that the pMaskSet->ix[]

   307 ** array will never overflow.

   308 */

   309 static void createMask(ExprMaskSet *pMaskSet, int iCursor){

   310   assert( pMaskSet->n < ArraySize(pMaskSet->ix) );

   311   pMaskSet->ix[pMaskSet->n++] = iCursor;

   312 }

   313 

   314 /*

   315 ** This routine walks (recursively) an expression tree and generates

   316 ** a bitmask indicating which tables are used in that expression

   317 ** tree.

   318 **

   319 ** In order for this routine to work, the calling function must have

   320 ** previously invoked sqlite3ExprResolveNames() on the expression.  See

   321 ** the header comment on that routine for additional information.

   322 ** The sqlite3ExprResolveNames() routines looks for column names and

   323 ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to

   324 ** the VDBE cursor number of the table.  This routine just has to

   325 ** translate the cursor numbers into bitmask values and OR all

   326 ** the bitmasks together.

   327 */

   328 static Bitmask exprListTableUsage(ExprMaskSet*, ExprList*);

   329 static Bitmask exprSelectTableUsage(ExprMaskSet*, Select*);

   330 static Bitmask exprTableUsage(ExprMaskSet *pMaskSet, Expr *p){

   331   Bitmask mask = 0;

   332   if( p==0 ) return 0;

   333   if( p->op==TK_COLUMN ){

   334     mask = getMask(pMaskSet, p->iTable);

   335     return mask;

   336   }

   337   mask = exprTableUsage(pMaskSet, p->pRight);

   338   mask |= exprTableUsage(pMaskSet, p->pLeft);

   339   mask |= exprListTableUsage(pMaskSet, p->pList);

   340   mask |= exprSelectTableUsage(pMaskSet, p->pSelect);

   341   return mask;

   342 }

   343 static Bitmask exprListTableUsage(ExprMaskSet *pMaskSet, ExprList *pList){

   344   int i;

   345   Bitmask mask = 0;

   346   if( pList ){

   347     for(i=0; i<pList->nExpr; i++){

   348       mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);

   349     }

   350   }

   351   return mask;

   352 }

   353 static Bitmask exprSelectTableUsage(ExprMaskSet *pMaskSet, Select *pS){

   354   Bitmask mask = 0;

   355   while( pS ){

   356     mask |= exprListTableUsage(pMaskSet, pS->pEList);

   357     mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);

   358     mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);

   359     mask |= exprTableUsage(pMaskSet, pS->pWhere);

   360     mask |= exprTableUsage(pMaskSet, pS->pHaving);

   361     pS = pS->pPrior;

   362   }

   363   return mask;

   364 }

   365 

   366 /*

   367 ** Return TRUE if the given operator is one of the operators that is

   368 ** allowed for an indexable WHERE clause term.  The allowed operators are

   369 ** "=", "<", ">", "<=", ">=", and "IN".

   370 */

   371 static int allowedOp(int op){

   372   assert( TK_GT>TK_EQ && TK_GT<TK_GE );

   373   assert( TK_LT>TK_EQ && TK_LT<TK_GE );

   374   assert( TK_LE>TK_EQ && TK_LE<TK_GE );

   375   assert( TK_GE==TK_EQ+4 );

   376   return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;

   377 }

   378 

   379 /*

   380 ** Swap two objects of type T.

   381 */

   382 #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}

   383 

   384 /*

   385 ** Commute a comparision operator.  Expressions of the form "X op Y"

   386 ** are converted into "Y op X".

   387 **

   388 ** If a collation sequence is associated with either the left or right

   389 ** side of the comparison, it remains associated with the same side after

   390 ** the commutation. So "Y collate NOCASE op X" becomes 

   391 ** "X collate NOCASE op Y". This is because any collation sequence on

   392 ** the left hand side of a comparison overrides any collation sequence 

   393 ** attached to the right. For the same reason the EP_ExpCollate flag

   394 ** is not commuted.

   395 */

   396 static void exprCommute(Expr *pExpr){

   397   u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);

   398   u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);

   399   assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );

   400   SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);

   401   pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;

   402   pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;

   403   SWAP(Expr*,pExpr->pRight,pExpr->pLeft);

   404   if( pExpr->op>=TK_GT ){

   405     assert( TK_LT==TK_GT+2 );

   406     assert( TK_GE==TK_LE+2 );

   407     assert( TK_GT>TK_EQ );

   408     assert( TK_GT<TK_LE );

   409     assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );

   410     pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;

   411   }

   412 }

   413 

   414 /*

   415 ** Translate from TK_xx operator to WO_xx bitmask.

   416 */

   417 static int operatorMask(int op){

   418   int c;

   419   assert( allowedOp(op) );

   420   if( op==TK_IN ){

   421     c = WO_IN;

   422   }else if( op==TK_ISNULL ){

   423     c = WO_ISNULL;

   424   }else{

   425     c = WO_EQ<<(op-TK_EQ);

   426   }

   427   assert( op!=TK_ISNULL || c==WO_ISNULL );

   428   assert( op!=TK_IN || c==WO_IN );

   429   assert( op!=TK_EQ || c==WO_EQ );

   430   assert( op!=TK_LT || c==WO_LT );

   431   assert( op!=TK_LE || c==WO_LE );

   432   assert( op!=TK_GT || c==WO_GT );

   433   assert( op!=TK_GE || c==WO_GE );

   434   return c;

   435 }

   436 

   437 /*

   438 ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"

   439 ** where X is a reference to the iColumn of table iCur and <op> is one of

   440 ** the WO_xx operator codes specified by the op parameter.

   441 ** Return a pointer to the term.  Return 0 if not found.

   442 */

   443 static WhereTerm *findTerm(

   444   WhereClause *pWC,     /* The WHERE clause to be searched */

   445   int iCur,             /* Cursor number of LHS */

   446   int iColumn,          /* Column number of LHS */

   447   Bitmask notReady,     /* RHS must not overlap with this mask */

   448   u16 op,               /* Mask of WO_xx values describing operator */

   449   Index *pIdx           /* Must be compatible with this index, if not NULL */

   450 ){

   451   WhereTerm *pTerm;

   452   int k;

   453   for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){

   454     if( pTerm->leftCursor==iCur

   455        && (pTerm->prereqRight & notReady)==0

   456        && pTerm->leftColumn==iColumn

   457        && (pTerm->eOperator & op)!=0

   458     ){

   459       if( iCur>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){

   460         Expr *pX = pTerm->pExpr;

   461         CollSeq *pColl;

   462         char idxaff;

   463         int j;

   464         Parse *pParse = pWC->pParse;

   465 

   466         idxaff = pIdx->pTable->aCol[iColumn].affinity;

   467         if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;

   468 

   469         /* Figure out the collation sequence required from an index for

   470         ** it to be useful for optimising expression pX. Store this

   471         ** value in variable pColl.

   472         */

   473         assert(pX->pLeft);

   474         pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);

   475         if( !pColl ){

   476           pColl = pParse->db->pDfltColl;

   477         }

   478 

   479         for(j=0; j<pIdx->nColumn && pIdx->aiColumn[j]!=iColumn; j++){}

   480         assert( j<pIdx->nColumn );

   481         if( sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;

   482       }

   483       return pTerm;

   484     }

   485   }

   486   return 0;

   487 }

   488 

   489 /* Forward reference */

   490 static void exprAnalyze(SrcList*, WhereClause*, int);

   491 

   492 /*

   493 ** Call exprAnalyze on all terms in a WHERE clause.  

   494 **

   495 **

   496 */

   497 static void exprAnalyzeAll(

   498   SrcList *pTabList,       /* the FROM clause */

   499   WhereClause *pWC         /* the WHERE clause to be analyzed */

   500 ){

   501   int i;

   502   for(i=pWC->nTerm-1; i>=0; i--){

   503     exprAnalyze(pTabList, pWC, i);

   504   }

   505 }

   506 

   507 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

   508 /*

   509 ** Check to see if the given expression is a LIKE or GLOB operator that

   510 ** can be optimized using inequality constraints.  Return TRUE if it is

   511 ** so and false if not.

   512 **

   513 ** In order for the operator to be optimizible, the RHS must be a string

   514 ** literal that does not begin with a wildcard.  

   515 */

   516 static int isLikeOrGlob(

   517   sqlite3 *db,      /* The database */

   518   Expr *pExpr,      /* Test this expression */

   519   int *pnPattern,   /* Number of non-wildcard prefix characters */

   520   int *pisComplete  /* True if the only wildcard is % in the last character */

   521 ){

   522   const char *z;

   523   Expr *pRight, *pLeft;

   524   ExprList *pList;

   525   int c, cnt;

   526   int noCase;

   527   char wc[3];

   528   CollSeq *pColl;

   529 

   530   if( !sqlite3IsLikeFunction(db, pExpr, &noCase, wc) ){

   531     return 0;

   532   }

   533   pList = pExpr->pList;

   534   pRight = pList->a[0].pExpr;

   535   if( pRight->op!=TK_STRING ){

   536     return 0;

   537   }

   538   pLeft = pList->a[1].pExpr;

   539   if( pLeft->op!=TK_COLUMN ){

   540     return 0;

   541   }

   542   pColl = pLeft->pColl;

   543   if( pColl==0 ){

   544     /* TODO: Coverage testing doesn't get this case. Is it actually possible

   545     ** for an expression of type TK_COLUMN to not have an assigned collation 

   546     ** sequence at this point?

   547     */

   548     pColl = db->pDfltColl;

   549   }

   550   if( (pColl->type!=SQLITE_COLL_BINARY || noCase) &&

   551       (pColl->type!=SQLITE_COLL_NOCASE || !noCase) ){

   552     return 0;

   553   }

   554   sqlite3DequoteExpr(db, pRight);

   555   z = (char *)pRight->token.z;

   556   cnt = 0;

   557   if( z ){

   558     while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){ cnt++; }

   559   }

   560   if( cnt==0 || 255==(u8)z[cnt] ){

   561     return 0;

   562   }

   563   *pisComplete = z[cnt]==wc[0] && z[cnt+1]==0;

   564   *pnPattern = cnt;

   565   return 1;

   566 }

   567 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

   568 

   569 

   570 #ifndef SQLITE_OMIT_VIRTUALTABLE

   571 /*

   572 ** Check to see if the given expression is of the form

   573 **

   574 **         column MATCH expr

   575 **

   576 ** If it is then return TRUE.  If not, return FALSE.

   577 */

   578 static int isMatchOfColumn(

   579   Expr *pExpr      /* Test this expression */

   580 ){

   581   ExprList *pList;

   582 

   583   if( pExpr->op!=TK_FUNCTION ){

   584     return 0;

   585   }

   586   if( pExpr->token.n!=5 ||

   587        sqlite3StrNICmp((const char*)pExpr->token.z,"match",5)!=0 ){

   588     return 0;

   589   }

   590   pList = pExpr->pList;

   591   if( pList->nExpr!=2 ){

   592     return 0;

   593   }

   594   if( pList->a[1].pExpr->op != TK_COLUMN ){

   595     return 0;

   596   }

   597   return 1;

   598 }

   599 #endif /* SQLITE_OMIT_VIRTUALTABLE */

   600 

   601 /*

   602 ** If the pBase expression originated in the ON or USING clause of

   603 ** a join, then transfer the appropriate markings over to derived.

   604 */

   605 static void transferJoinMarkings(Expr *pDerived, Expr *pBase){

   606   pDerived->flags |= pBase->flags & EP_FromJoin;

   607   pDerived->iRightJoinTable = pBase->iRightJoinTable;

   608 }

   609 

   610 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

   611 /*

   612 ** Return TRUE if the given term of an OR clause can be converted

   613 ** into an IN clause.  The iCursor and iColumn define the left-hand

   614 ** side of the IN clause.

   615 **

   616 ** The context is that we have multiple OR-connected equality terms

   617 ** like this:

   618 **

   619 **           a=<expr1> OR  a=<expr2> OR b=<expr3>  OR ...

   620 **

   621 ** The pOrTerm input to this routine corresponds to a single term of

   622 ** this OR clause.  In order for the term to be a condidate for

   623 ** conversion to an IN operator, the following must be true:

   624 **

   625 **     *  The left-hand side of the term must be the column which

   626 **        is identified by iCursor and iColumn.

   627 **

   628 **     *  If the right-hand side is also a column, then the affinities

   629 **        of both right and left sides must be such that no type

   630 **        conversions are required on the right.  (Ticket #2249)

   631 **

   632 ** If both of these conditions are true, then return true.  Otherwise

   633 ** return false.

   634 */

   635 static int orTermIsOptCandidate(WhereTerm *pOrTerm, int iCursor, int iColumn){

   636   int affLeft, affRight;

   637   assert( pOrTerm->eOperator==WO_EQ );

   638   if( pOrTerm->leftCursor!=iCursor ){

   639     return 0;

   640   }

   641   if( pOrTerm->leftColumn!=iColumn ){

   642     return 0;

   643   }

   644   affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);

   645   if( affRight==0 ){

   646     return 1;

   647   }

   648   affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);

   649   if( affRight!=affLeft ){

   650     return 0;

   651   }

   652   return 1;

   653 }

   654 

   655 /*

   656 ** Return true if the given term of an OR clause can be ignored during

   657 ** a check to make sure all OR terms are candidates for optimization.

   658 ** In other words, return true if a call to the orTermIsOptCandidate()

   659 ** above returned false but it is not necessary to disqualify the

   660 ** optimization.

   661 **

   662 ** Suppose the original OR phrase was this:

   663 **

   664 **           a=4  OR  a=11  OR  a=b

   665 **

   666 ** During analysis, the third term gets flipped around and duplicate

   667 ** so that we are left with this:

   668 **

   669 **           a=4  OR  a=11  OR  a=b  OR  b=a

   670 **

   671 ** Since the last two terms are duplicates, only one of them

   672 ** has to qualify in order for the whole phrase to qualify.  When

   673 ** this routine is called, we know that pOrTerm did not qualify.

   674 ** This routine merely checks to see if pOrTerm has a duplicate that

   675 ** might qualify.  If there is a duplicate that has not yet been

   676 ** disqualified, then return true.  If there are no duplicates, or

   677 ** the duplicate has also been disqualifed, return false.

   678 */

   679 static int orTermHasOkDuplicate(WhereClause *pOr, WhereTerm *pOrTerm){

   680   if( pOrTerm->flags & TERM_COPIED ){

   681     /* This is the original term.  The duplicate is to the left had

   682     ** has not yet been analyzed and thus has not yet been disqualified. */

   683     return 1;

   684   }

   685   if( (pOrTerm->flags & TERM_VIRTUAL)!=0

   686      && (pOr->a[pOrTerm->iParent].flags & TERM_OR_OK)!=0 ){

   687     /* This is a duplicate term.  The original qualified so this one

   688     ** does not have to. */

   689     return 1;

   690   }

   691   /* This is either a singleton term or else it is a duplicate for

   692   ** which the original did not qualify.  Either way we are done for. */

   693   return 0;

   694 }

   695 #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */

   696 

   697 /*

   698 ** The input to this routine is an WhereTerm structure with only the

   699 ** "pExpr" field filled in.  The job of this routine is to analyze the

   700 ** subexpression and populate all the other fields of the WhereTerm

   701 ** structure.

   702 **

   703 ** If the expression is of the form "<expr> <op> X" it gets commuted

   704 ** to the standard form of "X <op> <expr>".  If the expression is of

   705 ** the form "X <op> Y" where both X and Y are columns, then the original

   706 ** expression is unchanged and a new virtual expression of the form

   707 ** "Y <op> X" is added to the WHERE clause and analyzed separately.

   708 */

   709 static void exprAnalyze(

   710   SrcList *pSrc,            /* the FROM clause */

   711   WhereClause *pWC,         /* the WHERE clause */

   712   int idxTerm               /* Index of the term to be analyzed */

   713 ){

   714   WhereTerm *pTerm;

   715   ExprMaskSet *pMaskSet;

   716   Expr *pExpr;

   717   Bitmask prereqLeft;

   718   Bitmask prereqAll;

   719   int nPattern;

   720   int isComplete;

   721   int op;

   722   Parse *pParse = pWC->pParse;

   723   sqlite3 *db = pParse->db;

   724 

   725   if( db->mallocFailed ){

   726     return;

   727   }

   728   pTerm = &pWC->a[idxTerm];

   729   pMaskSet = pWC->pMaskSet;

   730   pExpr = pTerm->pExpr;

   731   prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);

   732   op = pExpr->op;

   733   if( op==TK_IN ){

   734     assert( pExpr->pRight==0 );

   735     pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->pList)

   736                           | exprSelectTableUsage(pMaskSet, pExpr->pSelect);

   737   }else if( op==TK_ISNULL ){

   738     pTerm->prereqRight = 0;

   739   }else{

   740     pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);

   741   }

   742   prereqAll = exprTableUsage(pMaskSet, pExpr);

   743   if( ExprHasProperty(pExpr, EP_FromJoin) ){

   744     prereqAll |= getMask(pMaskSet, pExpr->iRightJoinTable);

   745   }

   746   pTerm->prereqAll = prereqAll;

   747   pTerm->leftCursor = -1;

   748   pTerm->iParent = -1;

   749   pTerm->eOperator = 0;

   750   if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){

   751     Expr *pLeft = pExpr->pLeft;

   752     Expr *pRight = pExpr->pRight;

   753     if( pLeft->op==TK_COLUMN ){

   754       pTerm->leftCursor = pLeft->iTable;

   755       pTerm->leftColumn = pLeft->iColumn;

   756       pTerm->eOperator = operatorMask(op);

   757     }

   758     if( pRight && pRight->op==TK_COLUMN ){

   759       WhereTerm *pNew;

   760       Expr *pDup;

   761       if( pTerm->leftCursor>=0 ){

   762         int idxNew;

   763         pDup = sqlite3ExprDup(db, pExpr);

   764         if( db->mallocFailed ){

   765           sqlite3ExprDelete(pDup);

   766           return;

   767         }

   768         idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);

   769         if( idxNew==0 ) return;

   770         pNew = &pWC->a[idxNew];

   771         pNew->iParent = idxTerm;

   772         pTerm = &pWC->a[idxTerm];

   773         pTerm->nChild = 1;

   774         pTerm->flags |= TERM_COPIED;

   775       }else{

   776         pDup = pExpr;

   777         pNew = pTerm;

   778       }

   779       exprCommute(pDup);

   780       pLeft = pDup->pLeft;

   781       pNew->leftCursor = pLeft->iTable;

   782       pNew->leftColumn = pLeft->iColumn;

   783       pNew->prereqRight = prereqLeft;

   784       pNew->prereqAll = prereqAll;

   785       pNew->eOperator = operatorMask(pDup->op);

   786     }

   787   }

   788 

   789 #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION

   790   /* If a term is the BETWEEN operator, create two new virtual terms

   791   ** that define the range that the BETWEEN implements.

   792   */

   793   else if( pExpr->op==TK_BETWEEN ){

   794     ExprList *pList = pExpr->pList;

   795     int i;

   796     static const u8 ops[] = {TK_GE, TK_LE};

   797     assert( pList!=0 );

   798     assert( pList->nExpr==2 );

   799     for(i=0; i<2; i++){

   800       Expr *pNewExpr;

   801       int idxNew;

   802       pNewExpr = sqlite3Expr(db, ops[i], sqlite3ExprDup(db, pExpr->pLeft),

   803                              sqlite3ExprDup(db, pList->a[i].pExpr), 0);

   804       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);

   805       exprAnalyze(pSrc, pWC, idxNew);

   806       pTerm = &pWC->a[idxTerm];

   807       pWC->a[idxNew].iParent = idxTerm;

   808     }

   809     pTerm->nChild = 2;

   810   }

   811 #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */

   812 

   813 #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)

   814   /* Attempt to convert OR-connected terms into an IN operator so that

   815   ** they can make use of indices.  Example:

   816   **

   817   **      x = expr1  OR  expr2 = x  OR  x = expr3

   818   **

   819   ** is converted into

   820   **

   821   **      x IN (expr1,expr2,expr3)

   822   **

   823   ** This optimization must be omitted if OMIT_SUBQUERY is defined because

   824   ** the compiler for the the IN operator is part of sub-queries.

   825   */

   826   else if( pExpr->op==TK_OR ){

   827     int ok;

   828     int i, j;

   829     int iColumn, iCursor;

   830     WhereClause sOr;

   831     WhereTerm *pOrTerm;

   832 

   833     assert( (pTerm->flags & TERM_DYNAMIC)==0 );

   834     whereClauseInit(&sOr, pWC->pParse, pMaskSet);

   835     whereSplit(&sOr, pExpr, TK_OR);

   836     exprAnalyzeAll(pSrc, &sOr);

   837     assert( sOr.nTerm>=2 );

   838     j = 0;

   839     do{

   840       assert( j<sOr.nTerm );

   841       iColumn = sOr.a[j].leftColumn;

   842       iCursor = sOr.a[j].leftCursor;

   843       ok = iCursor>=0;

   844       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){

   845         if( pOrTerm->eOperator!=WO_EQ ){

   846           goto or_not_possible;

   847         }

   848         if( orTermIsOptCandidate(pOrTerm, iCursor, iColumn) ){

   849           pOrTerm->flags |= TERM_OR_OK;

   850         }else if( orTermHasOkDuplicate(&sOr, pOrTerm) ){

   851           pOrTerm->flags &= ~TERM_OR_OK;

   852         }else{

   853           ok = 0;

   854         }

   855       }

   856     }while( !ok && (sOr.a[j++].flags & TERM_COPIED)!=0 && j<2 );

   857     if( ok ){

   858       ExprList *pList = 0;

   859       Expr *pNew, *pDup;

   860       Expr *pLeft = 0;

   861       for(i=sOr.nTerm-1, pOrTerm=sOr.a; i>=0 && ok; i--, pOrTerm++){

   862         if( (pOrTerm->flags & TERM_OR_OK)==0 ) continue;

   863         pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight);

   864         pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup, 0);

   865         pLeft = pOrTerm->pExpr->pLeft;

   866       }

   867       assert( pLeft!=0 );

   868       pDup = sqlite3ExprDup(db, pLeft);

   869       pNew = sqlite3Expr(db, TK_IN, pDup, 0, 0);

   870       if( pNew ){

   871         int idxNew;

   872         transferJoinMarkings(pNew, pExpr);

   873         pNew->pList = pList;

   874         idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);

   875         exprAnalyze(pSrc, pWC, idxNew);

   876         pTerm = &pWC->a[idxTerm];

   877         pWC->a[idxNew].iParent = idxTerm;

   878         pTerm->nChild = 1;

   879       }else{

   880         sqlite3ExprListDelete(pList);

   881       }

   882     }

   883 or_not_possible:

   884     whereClauseClear(&sOr);

   885   }

   886 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */

   887 

   888 #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION

   889   /* Add constraints to reduce the search space on a LIKE or GLOB

   890   ** operator.

   891   */

   892   if( isLikeOrGlob(db, pExpr, &nPattern, &isComplete) ){

   893     Expr *pLeft, *pRight;

   894     Expr *pStr1, *pStr2;

   895     Expr *pNewExpr1, *pNewExpr2;

   896     int idxNew1, idxNew2;

   897 

   898     pLeft = pExpr->pList->a[1].pExpr;

   899     pRight = pExpr->pList->a[0].pExpr;

   900     pStr1 = sqlite3PExpr(pParse, TK_STRING, 0, 0, 0);

   901     if( pStr1 ){

   902       sqlite3TokenCopy(db, &pStr1->token, &pRight->token);

   903       pStr1->token.n = nPattern;

   904       pStr1->flags = EP_Dequoted;

   905     }

   906     pStr2 = sqlite3ExprDup(db, pStr1);

   907     if( !db->mallocFailed ){

   908       assert( pStr2->token.dyn );

   909       ++*(u8*)&pStr2->token.z[nPattern-1];

   910     }

   911     pNewExpr1 = sqlite3PExpr(pParse, TK_GE, sqlite3ExprDup(db,pLeft), pStr1, 0);

   912     idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);

   913     exprAnalyze(pSrc, pWC, idxNew1);

   914     pNewExpr2 = sqlite3PExpr(pParse, TK_LT, sqlite3ExprDup(db,pLeft), pStr2, 0);

   915     idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);

   916     exprAnalyze(pSrc, pWC, idxNew2);

   917     pTerm = &pWC->a[idxTerm];

   918     if( isComplete ){

   919       pWC->a[idxNew1].iParent = idxTerm;

   920       pWC->a[idxNew2].iParent = idxTerm;

   921       pTerm->nChild = 2;

   922     }

   923   }

   924 #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */

   925 

   926 #ifndef SQLITE_OMIT_VIRTUALTABLE

   927   /* Add a WO_MATCH auxiliary term to the constraint set if the

   928   ** current expression is of the form:  column MATCH expr.

   929   ** This information is used by the xBestIndex methods of

   930   ** virtual tables.  The native query optimizer does not attempt

   931   ** to do anything with MATCH functions.

   932   */

   933   if( isMatchOfColumn(pExpr) ){

   934     int idxNew;

   935     Expr *pRight, *pLeft;

   936     WhereTerm *pNewTerm;

   937     Bitmask prereqColumn, prereqExpr;

   938 

   939     pRight = pExpr->pList->a[0].pExpr;

   940     pLeft = pExpr->pList->a[1].pExpr;

   941     prereqExpr = exprTableUsage(pMaskSet, pRight);

   942     prereqColumn = exprTableUsage(pMaskSet, pLeft);

   943     if( (prereqExpr & prereqColumn)==0 ){

   944       Expr *pNewExpr;

   945       pNewExpr = sqlite3Expr(db, TK_MATCH, 0, sqlite3ExprDup(db, pRight), 0);

   946       idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);

   947       pNewTerm = &pWC->a[idxNew];

   948       pNewTerm->prereqRight = prereqExpr;

   949       pNewTerm->leftCursor = pLeft->iTable;

   950       pNewTerm->leftColumn = pLeft->iColumn;

   951       pNewTerm->eOperator = WO_MATCH;

   952       pNewTerm->iParent = idxTerm;

   953       pTerm = &pWC->a[idxTerm];

   954       pTerm->nChild = 1;

   955       pTerm->flags |= TERM_COPIED;

   956       pNewTerm->prereqAll = pTerm->prereqAll;

   957     }

   958   }

   959 #endif /* SQLITE_OMIT_VIRTUALTABLE */

   960 }

   961 

   962 /*

   963 ** Return TRUE if any of the expressions in pList->a[iFirst...] contain

   964 ** a reference to any table other than the iBase table.

   965 */

   966 static int referencesOtherTables(

   967   ExprList *pList,          /* Search expressions in ths list */

   968   ExprMaskSet *pMaskSet,    /* Mapping from tables to bitmaps */

   969   int iFirst,               /* Be searching with the iFirst-th expression */

   970   int iBase                 /* Ignore references to this table */

   971 ){

   972   Bitmask allowed = ~getMask(pMaskSet, iBase);

   973   while( iFirst<pList->nExpr ){

   974     if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){

   975       return 1;

   976     }

   977   }

   978   return 0;

   979 }

   980 

   981 

   982 /*

   983 ** This routine decides if pIdx can be used to satisfy the ORDER BY

   984 ** clause.  If it can, it returns 1.  If pIdx cannot satisfy the

   985 ** ORDER BY clause, this routine returns 0.

   986 **

   987 ** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the

   988 ** left-most table in the FROM clause of that same SELECT statement and

   989 ** the table has a cursor number of "base".  pIdx is an index on pTab.

   990 **

   991 ** nEqCol is the number of columns of pIdx that are used as equality

   992 ** constraints.  Any of these columns may be missing from the ORDER BY

   993 ** clause and the match can still be a success.

   994 **

   995 ** All terms of the ORDER BY that match against the index must be either

   996 ** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE

   997 ** index do not need to satisfy this constraint.)  The *pbRev value is

   998 ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if

   999 ** the ORDER BY clause is all ASC.

  1000 */

  1001 static int isSortingIndex(

  1002   Parse *pParse,          /* Parsing context */

  1003   ExprMaskSet *pMaskSet,  /* Mapping from table indices to bitmaps */

  1004   Index *pIdx,            /* The index we are testing */

  1005   int base,               /* Cursor number for the table to be sorted */

  1006   ExprList *pOrderBy,     /* The ORDER BY clause */

  1007   int nEqCol,             /* Number of index columns with == constraints */

  1008   int *pbRev              /* Set to 1 if ORDER BY is DESC */

  1009 ){

  1010   int i, j;                       /* Loop counters */

  1011   int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */

  1012   int nTerm;                      /* Number of ORDER BY terms */

  1013   ExprList::ExprList_item *pTerm;    /* A term of the ORDER BY clause */

  1014   sqlite3 *db = pParse->db;

  1015 

  1016   assert( pOrderBy!=0 );

  1017   nTerm = pOrderBy->nExpr;

  1018   assert( nTerm>0 );

  1019 

  1020   /* Match terms of the ORDER BY clause against columns of

  1021   ** the index.

  1022   **

  1023   ** Note that indices have pIdx->nColumn regular columns plus

  1024   ** one additional column containing the rowid.  The rowid column

  1025   ** of the index is also allowed to match against the ORDER BY

  1026   ** clause.

  1027   */

  1028   for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){

  1029     Expr *pExpr;       /* The expression of the ORDER BY pTerm */

  1030     CollSeq *pColl;    /* The collating sequence of pExpr */

  1031     int termSortOrder; /* Sort order for this term */

  1032     int iColumn;       /* The i-th column of the index.  -1 for rowid */

  1033     int iSortOrder;    /* 1 for DESC, 0 for ASC on the i-th index term */

  1034     const char *zColl; /* Name of the collating sequence for i-th index term */

  1035 

  1036     pExpr = pTerm->pExpr;

  1037     if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){

  1038       /* Can not use an index sort on anything that is not a column in the

  1039       ** left-most table of the FROM clause */

  1040       break;

  1041     }

  1042     pColl = sqlite3ExprCollSeq(pParse, pExpr);

  1043     if( !pColl ){

  1044       pColl = db->pDfltColl;

  1045     }

  1046     if( i<pIdx->nColumn ){

  1047       iColumn = pIdx->aiColumn[i];

  1048       if( iColumn==pIdx->pTable->iPKey ){

  1049         iColumn = -1;

  1050       }

  1051       iSortOrder = pIdx->aSortOrder[i];

  1052       zColl = pIdx->azColl[i];

  1053     }else{

  1054       iColumn = -1;

  1055       iSortOrder = 0;

  1056       zColl = pColl->zName;

  1057     }

  1058     if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){

  1059       /* Term j of the ORDER BY clause does not match column i of the index */

  1060       if( i<nEqCol ){

  1061         /* If an index column that is constrained by == fails to match an

  1062         ** ORDER BY term, that is OK.  Just ignore that column of the index

  1063         */

  1064         continue;

  1065       }else{

  1066         /* If an index column fails to match and is not constrained by ==

  1067         ** then the index cannot satisfy the ORDER BY constraint.

  1068         */

  1069         return 0;

  1070       }

  1071     }

  1072     assert( pIdx->aSortOrder!=0 );

  1073     assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );

  1074     assert( iSortOrder==0 || iSortOrder==1 );

  1075     termSortOrder = iSortOrder ^ pTerm->sortOrder;

  1076     if( i>nEqCol ){

  1077       if( termSortOrder!=sortOrder ){

  1078         /* Indices can only be used if all ORDER BY terms past the

  1079         ** equality constraints are all either DESC or ASC. */

  1080         return 0;

  1081       }

  1082     }else{

  1083       sortOrder = termSortOrder;

  1084     }

  1085     j++;

  1086     pTerm++;

  1087     if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){

  1088       /* If the indexed column is the primary key and everything matches

  1089       ** so far and none of the ORDER BY terms to the right reference other

  1090       ** tables in the join, then we are assured that the index can be used 

  1091       ** to sort because the primary key is unique and so none of the other

  1092       ** columns will make any difference

  1093       */

  1094       j = nTerm;

  1095     }

  1096   }

  1097 

  1098   *pbRev = sortOrder!=0;

  1099   if( j>=nTerm ){

  1100     /* All terms of the ORDER BY clause are covered by this index so

  1101     ** this index can be used for sorting. */

  1102     return 1;

  1103   }

  1104   if( pIdx->onError!=OE_None && i==pIdx->nColumn

  1105       && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){

  1106     /* All terms of this index match some prefix of the ORDER BY clause

  1107     ** and the index is UNIQUE and no terms on the tail of the ORDER BY

  1108     ** clause reference other tables in a join.  If this is all true then

  1109     ** the order by clause is superfluous. */

  1110     return 1;

  1111   }

  1112   return 0;

  1113 }

  1114 

  1115 /*

  1116 ** Check table to see if the ORDER BY clause in pOrderBy can be satisfied

  1117 ** by sorting in order of ROWID.  Return true if so and set *pbRev to be

  1118 ** true for reverse ROWID and false for forward ROWID order.

  1119 */

  1120 static int sortableByRowid(

  1121   int base,               /* Cursor number for table to be sorted */

  1122   ExprList *pOrderBy,     /* The ORDER BY clause */

  1123   ExprMaskSet *pMaskSet,  /* Mapping from tables to bitmaps */

  1124   int *pbRev              /* Set to 1 if ORDER BY is DESC */

  1125 ){

  1126   Expr *p;

  1127 

  1128   assert( pOrderBy!=0 );

  1129   assert( pOrderBy->nExpr>0 );

  1130   p = pOrderBy->a[0].pExpr;

  1131   if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1

  1132     && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){

  1133     *pbRev = pOrderBy->a[0].sortOrder;

  1134     return 1;