Annotation of embedaddon/sqlite3/src/where.c, revision 1.1
1.1 ! misho 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 responsible 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: #include "sqliteInt.h"
! 20:
! 21:
! 22: /*
! 23: ** Trace output macros
! 24: */
! 25: #if defined(SQLITE_TEST) || defined(SQLITE_DEBUG)
! 26: int sqlite3WhereTrace = 0;
! 27: #endif
! 28: #if defined(SQLITE_TEST) && defined(SQLITE_DEBUG)
! 29: # define WHERETRACE(X) if(sqlite3WhereTrace) sqlite3DebugPrintf X
! 30: #else
! 31: # define WHERETRACE(X)
! 32: #endif
! 33:
! 34: /* Forward reference
! 35: */
! 36: typedef struct WhereClause WhereClause;
! 37: typedef struct WhereMaskSet WhereMaskSet;
! 38: typedef struct WhereOrInfo WhereOrInfo;
! 39: typedef struct WhereAndInfo WhereAndInfo;
! 40: typedef struct WhereCost WhereCost;
! 41:
! 42: /*
! 43: ** The query generator uses an array of instances of this structure to
! 44: ** help it analyze the subexpressions of the WHERE clause. Each WHERE
! 45: ** clause subexpression is separated from the others by AND operators,
! 46: ** usually, or sometimes subexpressions separated by OR.
! 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.u.leftColumn record the
! 59: ** cursor number and column number for X. WhereTerm.eOperator 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: ** A WhereTerm might also be two or more subterms connected by OR:
! 65: **
! 66: ** (t1.X <op> <expr>) OR (t1.Y <op> <expr>) OR ....
! 67: **
! 68: ** In this second case, wtFlag as the TERM_ORINFO set and eOperator==WO_OR
! 69: ** and the WhereTerm.u.pOrInfo field points to auxiliary information that
! 70: ** is collected about the
! 71: **
! 72: ** If a term in the WHERE clause does not match either of the two previous
! 73: ** categories, then eOperator==0. The WhereTerm.pExpr field is still set
! 74: ** to the original subexpression content and wtFlags is set up appropriately
! 75: ** but no other fields in the WhereTerm object are meaningful.
! 76: **
! 77: ** When eOperator!=0, prereqRight and prereqAll record sets of cursor numbers,
! 78: ** but they do so indirectly. A single WhereMaskSet structure translates
! 79: ** cursor number into bits and the translated bit is stored in the prereq
! 80: ** fields. The translation is used in order to maximize the number of
! 81: ** bits that will fit in a Bitmask. The VDBE cursor numbers might be
! 82: ** spread out over the non-negative integers. For example, the cursor
! 83: ** numbers might be 3, 8, 9, 10, 20, 23, 41, and 45. The WhereMaskSet
! 84: ** translates these sparse cursor numbers into consecutive integers
! 85: ** beginning with 0 in order to make the best possible use of the available
! 86: ** bits in the Bitmask. So, in the example above, the cursor numbers
! 87: ** would be mapped into integers 0 through 7.
! 88: **
! 89: ** The number of terms in a join is limited by the number of bits
! 90: ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite
! 91: ** is only able to process joins with 64 or fewer tables.
! 92: */
! 93: typedef struct WhereTerm WhereTerm;
! 94: struct WhereTerm {
! 95: Expr *pExpr; /* Pointer to the subexpression that is this term */
! 96: int iParent; /* Disable pWC->a[iParent] when this term disabled */
! 97: int leftCursor; /* Cursor number of X in "X <op> <expr>" */
! 98: union {
! 99: int leftColumn; /* Column number of X in "X <op> <expr>" */
! 100: WhereOrInfo *pOrInfo; /* Extra information if eOperator==WO_OR */
! 101: WhereAndInfo *pAndInfo; /* Extra information if eOperator==WO_AND */
! 102: } u;
! 103: u16 eOperator; /* A WO_xx value describing <op> */
! 104: u8 wtFlags; /* TERM_xxx bit flags. See below */
! 105: u8 nChild; /* Number of children that must disable us */
! 106: WhereClause *pWC; /* The clause this term is part of */
! 107: Bitmask prereqRight; /* Bitmask of tables used by pExpr->pRight */
! 108: Bitmask prereqAll; /* Bitmask of tables referenced by pExpr */
! 109: };
! 110:
! 111: /*
! 112: ** Allowed values of WhereTerm.wtFlags
! 113: */
! 114: #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */
! 115: #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */
! 116: #define TERM_CODED 0x04 /* This term is already coded */
! 117: #define TERM_COPIED 0x08 /* Has a child */
! 118: #define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */
! 119: #define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */
! 120: #define TERM_OR_OK 0x40 /* Used during OR-clause processing */
! 121: #ifdef SQLITE_ENABLE_STAT3
! 122: # define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */
! 123: #else
! 124: # define TERM_VNULL 0x00 /* Disabled if not using stat3 */
! 125: #endif
! 126:
! 127: /*
! 128: ** An instance of the following structure holds all information about a
! 129: ** WHERE clause. Mostly this is a container for one or more WhereTerms.
! 130: **
! 131: ** Explanation of pOuter: For a WHERE clause of the form
! 132: **
! 133: ** a AND ((b AND c) OR (d AND e)) AND f
! 134: **
! 135: ** There are separate WhereClause objects for the whole clause and for
! 136: ** the subclauses "(b AND c)" and "(d AND e)". The pOuter field of the
! 137: ** subclauses points to the WhereClause object for the whole clause.
! 138: */
! 139: struct WhereClause {
! 140: Parse *pParse; /* The parser context */
! 141: WhereMaskSet *pMaskSet; /* Mapping of table cursor numbers to bitmasks */
! 142: Bitmask vmask; /* Bitmask identifying virtual table cursors */
! 143: WhereClause *pOuter; /* Outer conjunction */
! 144: u8 op; /* Split operator. TK_AND or TK_OR */
! 145: u16 wctrlFlags; /* Might include WHERE_AND_ONLY */
! 146: int nTerm; /* Number of terms */
! 147: int nSlot; /* Number of entries in a[] */
! 148: WhereTerm *a; /* Each a[] describes a term of the WHERE cluase */
! 149: #if defined(SQLITE_SMALL_STACK)
! 150: WhereTerm aStatic[1]; /* Initial static space for a[] */
! 151: #else
! 152: WhereTerm aStatic[8]; /* Initial static space for a[] */
! 153: #endif
! 154: };
! 155:
! 156: /*
! 157: ** A WhereTerm with eOperator==WO_OR has its u.pOrInfo pointer set to
! 158: ** a dynamically allocated instance of the following structure.
! 159: */
! 160: struct WhereOrInfo {
! 161: WhereClause wc; /* Decomposition into subterms */
! 162: Bitmask indexable; /* Bitmask of all indexable tables in the clause */
! 163: };
! 164:
! 165: /*
! 166: ** A WhereTerm with eOperator==WO_AND has its u.pAndInfo pointer set to
! 167: ** a dynamically allocated instance of the following structure.
! 168: */
! 169: struct WhereAndInfo {
! 170: WhereClause wc; /* The subexpression broken out */
! 171: };
! 172:
! 173: /*
! 174: ** An instance of the following structure keeps track of a mapping
! 175: ** between VDBE cursor numbers and bits of the bitmasks in WhereTerm.
! 176: **
! 177: ** The VDBE cursor numbers are small integers contained in
! 178: ** SrcList_item.iCursor and Expr.iTable fields. For any given WHERE
! 179: ** clause, the cursor numbers might not begin with 0 and they might
! 180: ** contain gaps in the numbering sequence. But we want to make maximum
! 181: ** use of the bits in our bitmasks. This structure provides a mapping
! 182: ** from the sparse cursor numbers into consecutive integers beginning
! 183: ** with 0.
! 184: **
! 185: ** If WhereMaskSet.ix[A]==B it means that The A-th bit of a Bitmask
! 186: ** corresponds VDBE cursor number B. The A-th bit of a bitmask is 1<<A.
! 187: **
! 188: ** For example, if the WHERE clause expression used these VDBE
! 189: ** cursors: 4, 5, 8, 29, 57, 73. Then the WhereMaskSet structure
! 190: ** would map those cursor numbers into bits 0 through 5.
! 191: **
! 192: ** Note that the mapping is not necessarily ordered. In the example
! 193: ** above, the mapping might go like this: 4->3, 5->1, 8->2, 29->0,
! 194: ** 57->5, 73->4. Or one of 719 other combinations might be used. It
! 195: ** does not really matter. What is important is that sparse cursor
! 196: ** numbers all get mapped into bit numbers that begin with 0 and contain
! 197: ** no gaps.
! 198: */
! 199: struct WhereMaskSet {
! 200: int n; /* Number of assigned cursor values */
! 201: int ix[BMS]; /* Cursor assigned to each bit */
! 202: };
! 203:
! 204: /*
! 205: ** A WhereCost object records a lookup strategy and the estimated
! 206: ** cost of pursuing that strategy.
! 207: */
! 208: struct WhereCost {
! 209: WherePlan plan; /* The lookup strategy */
! 210: double rCost; /* Overall cost of pursuing this search strategy */
! 211: Bitmask used; /* Bitmask of cursors used by this plan */
! 212: };
! 213:
! 214: /*
! 215: ** Bitmasks for the operators that indices are able to exploit. An
! 216: ** OR-ed combination of these values can be used when searching for
! 217: ** terms in the where clause.
! 218: */
! 219: #define WO_IN 0x001
! 220: #define WO_EQ 0x002
! 221: #define WO_LT (WO_EQ<<(TK_LT-TK_EQ))
! 222: #define WO_LE (WO_EQ<<(TK_LE-TK_EQ))
! 223: #define WO_GT (WO_EQ<<(TK_GT-TK_EQ))
! 224: #define WO_GE (WO_EQ<<(TK_GE-TK_EQ))
! 225: #define WO_MATCH 0x040
! 226: #define WO_ISNULL 0x080
! 227: #define WO_OR 0x100 /* Two or more OR-connected terms */
! 228: #define WO_AND 0x200 /* Two or more AND-connected terms */
! 229: #define WO_NOOP 0x800 /* This term does not restrict search space */
! 230:
! 231: #define WO_ALL 0xfff /* Mask of all possible WO_* values */
! 232: #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */
! 233:
! 234: /*
! 235: ** Value for wsFlags returned by bestIndex() and stored in
! 236: ** WhereLevel.wsFlags. These flags determine which search
! 237: ** strategies are appropriate.
! 238: **
! 239: ** The least significant 12 bits is reserved as a mask for WO_ values above.
! 240: ** The WhereLevel.wsFlags field is usually set to WO_IN|WO_EQ|WO_ISNULL.
! 241: ** But if the table is the right table of a left join, WhereLevel.wsFlags
! 242: ** is set to WO_IN|WO_EQ. The WhereLevel.wsFlags field can then be used as
! 243: ** the "op" parameter to findTerm when we are resolving equality constraints.
! 244: ** ISNULL constraints will then not be used on the right table of a left
! 245: ** join. Tickets #2177 and #2189.
! 246: */
! 247: #define WHERE_ROWID_EQ 0x00001000 /* rowid=EXPR or rowid IN (...) */
! 248: #define WHERE_ROWID_RANGE 0x00002000 /* rowid<EXPR and/or rowid>EXPR */
! 249: #define WHERE_COLUMN_EQ 0x00010000 /* x=EXPR or x IN (...) or x IS NULL */
! 250: #define WHERE_COLUMN_RANGE 0x00020000 /* x<EXPR and/or x>EXPR */
! 251: #define WHERE_COLUMN_IN 0x00040000 /* x IN (...) */
! 252: #define WHERE_COLUMN_NULL 0x00080000 /* x IS NULL */
! 253: #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */
! 254: #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */
! 255: #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */
! 256: #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */
! 257: #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */
! 258: #define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */
! 259: #define WHERE_IDX_ONLY 0x00800000 /* Use index only - omit table */
! 260: #define WHERE_ORDERBY 0x01000000 /* Output will appear in correct order */
! 261: #define WHERE_REVERSE 0x02000000 /* Scan in reverse order */
! 262: #define WHERE_UNIQUE 0x04000000 /* Selects no more than one row */
! 263: #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */
! 264: #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */
! 265: #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */
! 266: #define WHERE_DISTINCT 0x40000000 /* Correct order for DISTINCT */
! 267:
! 268: /*
! 269: ** Initialize a preallocated WhereClause structure.
! 270: */
! 271: static void whereClauseInit(
! 272: WhereClause *pWC, /* The WhereClause to be initialized */
! 273: Parse *pParse, /* The parsing context */
! 274: WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmasks */
! 275: u16 wctrlFlags /* Might include WHERE_AND_ONLY */
! 276: ){
! 277: pWC->pParse = pParse;
! 278: pWC->pMaskSet = pMaskSet;
! 279: pWC->pOuter = 0;
! 280: pWC->nTerm = 0;
! 281: pWC->nSlot = ArraySize(pWC->aStatic);
! 282: pWC->a = pWC->aStatic;
! 283: pWC->vmask = 0;
! 284: pWC->wctrlFlags = wctrlFlags;
! 285: }
! 286:
! 287: /* Forward reference */
! 288: static void whereClauseClear(WhereClause*);
! 289:
! 290: /*
! 291: ** Deallocate all memory associated with a WhereOrInfo object.
! 292: */
! 293: static void whereOrInfoDelete(sqlite3 *db, WhereOrInfo *p){
! 294: whereClauseClear(&p->wc);
! 295: sqlite3DbFree(db, p);
! 296: }
! 297:
! 298: /*
! 299: ** Deallocate all memory associated with a WhereAndInfo object.
! 300: */
! 301: static void whereAndInfoDelete(sqlite3 *db, WhereAndInfo *p){
! 302: whereClauseClear(&p->wc);
! 303: sqlite3DbFree(db, p);
! 304: }
! 305:
! 306: /*
! 307: ** Deallocate a WhereClause structure. The WhereClause structure
! 308: ** itself is not freed. This routine is the inverse of whereClauseInit().
! 309: */
! 310: static void whereClauseClear(WhereClause *pWC){
! 311: int i;
! 312: WhereTerm *a;
! 313: sqlite3 *db = pWC->pParse->db;
! 314: for(i=pWC->nTerm-1, a=pWC->a; i>=0; i--, a++){
! 315: if( a->wtFlags & TERM_DYNAMIC ){
! 316: sqlite3ExprDelete(db, a->pExpr);
! 317: }
! 318: if( a->wtFlags & TERM_ORINFO ){
! 319: whereOrInfoDelete(db, a->u.pOrInfo);
! 320: }else if( a->wtFlags & TERM_ANDINFO ){
! 321: whereAndInfoDelete(db, a->u.pAndInfo);
! 322: }
! 323: }
! 324: if( pWC->a!=pWC->aStatic ){
! 325: sqlite3DbFree(db, pWC->a);
! 326: }
! 327: }
! 328:
! 329: /*
! 330: ** Add a single new WhereTerm entry to the WhereClause object pWC.
! 331: ** The new WhereTerm object is constructed from Expr p and with wtFlags.
! 332: ** The index in pWC->a[] of the new WhereTerm is returned on success.
! 333: ** 0 is returned if the new WhereTerm could not be added due to a memory
! 334: ** allocation error. The memory allocation failure will be recorded in
! 335: ** the db->mallocFailed flag so that higher-level functions can detect it.
! 336: **
! 337: ** This routine will increase the size of the pWC->a[] array as necessary.
! 338: **
! 339: ** If the wtFlags argument includes TERM_DYNAMIC, then responsibility
! 340: ** for freeing the expression p is assumed by the WhereClause object pWC.
! 341: ** This is true even if this routine fails to allocate a new WhereTerm.
! 342: **
! 343: ** WARNING: This routine might reallocate the space used to store
! 344: ** WhereTerms. All pointers to WhereTerms should be invalidated after
! 345: ** calling this routine. Such pointers may be reinitialized by referencing
! 346: ** the pWC->a[] array.
! 347: */
! 348: static int whereClauseInsert(WhereClause *pWC, Expr *p, u8 wtFlags){
! 349: WhereTerm *pTerm;
! 350: int idx;
! 351: testcase( wtFlags & TERM_VIRTUAL ); /* EV: R-00211-15100 */
! 352: if( pWC->nTerm>=pWC->nSlot ){
! 353: WhereTerm *pOld = pWC->a;
! 354: sqlite3 *db = pWC->pParse->db;
! 355: pWC->a = sqlite3DbMallocRaw(db, sizeof(pWC->a[0])*pWC->nSlot*2 );
! 356: if( pWC->a==0 ){
! 357: if( wtFlags & TERM_DYNAMIC ){
! 358: sqlite3ExprDelete(db, p);
! 359: }
! 360: pWC->a = pOld;
! 361: return 0;
! 362: }
! 363: memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
! 364: if( pOld!=pWC->aStatic ){
! 365: sqlite3DbFree(db, pOld);
! 366: }
! 367: pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
! 368: }
! 369: pTerm = &pWC->a[idx = pWC->nTerm++];
! 370: pTerm->pExpr = p;
! 371: pTerm->wtFlags = wtFlags;
! 372: pTerm->pWC = pWC;
! 373: pTerm->iParent = -1;
! 374: return idx;
! 375: }
! 376:
! 377: /*
! 378: ** This routine identifies subexpressions in the WHERE clause where
! 379: ** each subexpression is separated by the AND operator or some other
! 380: ** operator specified in the op parameter. The WhereClause structure
! 381: ** is filled with pointers to subexpressions. For example:
! 382: **
! 383: ** WHERE a=='hello' AND coalesce(b,11)<10 AND (c+12!=d OR c==22)
! 384: ** \________/ \_______________/ \________________/
! 385: ** slot[0] slot[1] slot[2]
! 386: **
! 387: ** The original WHERE clause in pExpr is unaltered. All this routine
! 388: ** does is make slot[] entries point to substructure within pExpr.
! 389: **
! 390: ** In the previous sentence and in the diagram, "slot[]" refers to
! 391: ** the WhereClause.a[] array. The slot[] array grows as needed to contain
! 392: ** all terms of the WHERE clause.
! 393: */
! 394: static void whereSplit(WhereClause *pWC, Expr *pExpr, int op){
! 395: pWC->op = (u8)op;
! 396: if( pExpr==0 ) return;
! 397: if( pExpr->op!=op ){
! 398: whereClauseInsert(pWC, pExpr, 0);
! 399: }else{
! 400: whereSplit(pWC, pExpr->pLeft, op);
! 401: whereSplit(pWC, pExpr->pRight, op);
! 402: }
! 403: }
! 404:
! 405: /*
! 406: ** Initialize an expression mask set (a WhereMaskSet object)
! 407: */
! 408: #define initMaskSet(P) memset(P, 0, sizeof(*P))
! 409:
! 410: /*
! 411: ** Return the bitmask for the given cursor number. Return 0 if
! 412: ** iCursor is not in the set.
! 413: */
! 414: static Bitmask getMask(WhereMaskSet *pMaskSet, int iCursor){
! 415: int i;
! 416: assert( pMaskSet->n<=(int)sizeof(Bitmask)*8 );
! 417: for(i=0; i<pMaskSet->n; i++){
! 418: if( pMaskSet->ix[i]==iCursor ){
! 419: return ((Bitmask)1)<<i;
! 420: }
! 421: }
! 422: return 0;
! 423: }
! 424:
! 425: /*
! 426: ** Create a new mask for cursor iCursor.
! 427: **
! 428: ** There is one cursor per table in the FROM clause. The number of
! 429: ** tables in the FROM clause is limited by a test early in the
! 430: ** sqlite3WhereBegin() routine. So we know that the pMaskSet->ix[]
! 431: ** array will never overflow.
! 432: */
! 433: static void createMask(WhereMaskSet *pMaskSet, int iCursor){
! 434: assert( pMaskSet->n < ArraySize(pMaskSet->ix) );
! 435: pMaskSet->ix[pMaskSet->n++] = iCursor;
! 436: }
! 437:
! 438: /*
! 439: ** This routine walks (recursively) an expression tree and generates
! 440: ** a bitmask indicating which tables are used in that expression
! 441: ** tree.
! 442: **
! 443: ** In order for this routine to work, the calling function must have
! 444: ** previously invoked sqlite3ResolveExprNames() on the expression. See
! 445: ** the header comment on that routine for additional information.
! 446: ** The sqlite3ResolveExprNames() routines looks for column names and
! 447: ** sets their opcodes to TK_COLUMN and their Expr.iTable fields to
! 448: ** the VDBE cursor number of the table. This routine just has to
! 449: ** translate the cursor numbers into bitmask values and OR all
! 450: ** the bitmasks together.
! 451: */
! 452: static Bitmask exprListTableUsage(WhereMaskSet*, ExprList*);
! 453: static Bitmask exprSelectTableUsage(WhereMaskSet*, Select*);
! 454: static Bitmask exprTableUsage(WhereMaskSet *pMaskSet, Expr *p){
! 455: Bitmask mask = 0;
! 456: if( p==0 ) return 0;
! 457: if( p->op==TK_COLUMN ){
! 458: mask = getMask(pMaskSet, p->iTable);
! 459: return mask;
! 460: }
! 461: mask = exprTableUsage(pMaskSet, p->pRight);
! 462: mask |= exprTableUsage(pMaskSet, p->pLeft);
! 463: if( ExprHasProperty(p, EP_xIsSelect) ){
! 464: mask |= exprSelectTableUsage(pMaskSet, p->x.pSelect);
! 465: }else{
! 466: mask |= exprListTableUsage(pMaskSet, p->x.pList);
! 467: }
! 468: return mask;
! 469: }
! 470: static Bitmask exprListTableUsage(WhereMaskSet *pMaskSet, ExprList *pList){
! 471: int i;
! 472: Bitmask mask = 0;
! 473: if( pList ){
! 474: for(i=0; i<pList->nExpr; i++){
! 475: mask |= exprTableUsage(pMaskSet, pList->a[i].pExpr);
! 476: }
! 477: }
! 478: return mask;
! 479: }
! 480: static Bitmask exprSelectTableUsage(WhereMaskSet *pMaskSet, Select *pS){
! 481: Bitmask mask = 0;
! 482: while( pS ){
! 483: SrcList *pSrc = pS->pSrc;
! 484: mask |= exprListTableUsage(pMaskSet, pS->pEList);
! 485: mask |= exprListTableUsage(pMaskSet, pS->pGroupBy);
! 486: mask |= exprListTableUsage(pMaskSet, pS->pOrderBy);
! 487: mask |= exprTableUsage(pMaskSet, pS->pWhere);
! 488: mask |= exprTableUsage(pMaskSet, pS->pHaving);
! 489: if( ALWAYS(pSrc!=0) ){
! 490: int i;
! 491: for(i=0; i<pSrc->nSrc; i++){
! 492: mask |= exprSelectTableUsage(pMaskSet, pSrc->a[i].pSelect);
! 493: mask |= exprTableUsage(pMaskSet, pSrc->a[i].pOn);
! 494: }
! 495: }
! 496: pS = pS->pPrior;
! 497: }
! 498: return mask;
! 499: }
! 500:
! 501: /*
! 502: ** Return TRUE if the given operator is one of the operators that is
! 503: ** allowed for an indexable WHERE clause term. The allowed operators are
! 504: ** "=", "<", ">", "<=", ">=", and "IN".
! 505: **
! 506: ** IMPLEMENTATION-OF: R-59926-26393 To be usable by an index a term must be
! 507: ** of one of the following forms: column = expression column > expression
! 508: ** column >= expression column < expression column <= expression
! 509: ** expression = column expression > column expression >= column
! 510: ** expression < column expression <= column column IN
! 511: ** (expression-list) column IN (subquery) column IS NULL
! 512: */
! 513: static int allowedOp(int op){
! 514: assert( TK_GT>TK_EQ && TK_GT<TK_GE );
! 515: assert( TK_LT>TK_EQ && TK_LT<TK_GE );
! 516: assert( TK_LE>TK_EQ && TK_LE<TK_GE );
! 517: assert( TK_GE==TK_EQ+4 );
! 518: return op==TK_IN || (op>=TK_EQ && op<=TK_GE) || op==TK_ISNULL;
! 519: }
! 520:
! 521: /*
! 522: ** Swap two objects of type TYPE.
! 523: */
! 524: #define SWAP(TYPE,A,B) {TYPE t=A; A=B; B=t;}
! 525:
! 526: /*
! 527: ** Commute a comparison operator. Expressions of the form "X op Y"
! 528: ** are converted into "Y op X".
! 529: **
! 530: ** If a collation sequence is associated with either the left or right
! 531: ** side of the comparison, it remains associated with the same side after
! 532: ** the commutation. So "Y collate NOCASE op X" becomes
! 533: ** "X collate NOCASE op Y". This is because any collation sequence on
! 534: ** the left hand side of a comparison overrides any collation sequence
! 535: ** attached to the right. For the same reason the EP_ExpCollate flag
! 536: ** is not commuted.
! 537: */
! 538: static void exprCommute(Parse *pParse, Expr *pExpr){
! 539: u16 expRight = (pExpr->pRight->flags & EP_ExpCollate);
! 540: u16 expLeft = (pExpr->pLeft->flags & EP_ExpCollate);
! 541: assert( allowedOp(pExpr->op) && pExpr->op!=TK_IN );
! 542: pExpr->pRight->pColl = sqlite3ExprCollSeq(pParse, pExpr->pRight);
! 543: pExpr->pLeft->pColl = sqlite3ExprCollSeq(pParse, pExpr->pLeft);
! 544: SWAP(CollSeq*,pExpr->pRight->pColl,pExpr->pLeft->pColl);
! 545: pExpr->pRight->flags = (pExpr->pRight->flags & ~EP_ExpCollate) | expLeft;
! 546: pExpr->pLeft->flags = (pExpr->pLeft->flags & ~EP_ExpCollate) | expRight;
! 547: SWAP(Expr*,pExpr->pRight,pExpr->pLeft);
! 548: if( pExpr->op>=TK_GT ){
! 549: assert( TK_LT==TK_GT+2 );
! 550: assert( TK_GE==TK_LE+2 );
! 551: assert( TK_GT>TK_EQ );
! 552: assert( TK_GT<TK_LE );
! 553: assert( pExpr->op>=TK_GT && pExpr->op<=TK_GE );
! 554: pExpr->op = ((pExpr->op-TK_GT)^2)+TK_GT;
! 555: }
! 556: }
! 557:
! 558: /*
! 559: ** Translate from TK_xx operator to WO_xx bitmask.
! 560: */
! 561: static u16 operatorMask(int op){
! 562: u16 c;
! 563: assert( allowedOp(op) );
! 564: if( op==TK_IN ){
! 565: c = WO_IN;
! 566: }else if( op==TK_ISNULL ){
! 567: c = WO_ISNULL;
! 568: }else{
! 569: assert( (WO_EQ<<(op-TK_EQ)) < 0x7fff );
! 570: c = (u16)(WO_EQ<<(op-TK_EQ));
! 571: }
! 572: assert( op!=TK_ISNULL || c==WO_ISNULL );
! 573: assert( op!=TK_IN || c==WO_IN );
! 574: assert( op!=TK_EQ || c==WO_EQ );
! 575: assert( op!=TK_LT || c==WO_LT );
! 576: assert( op!=TK_LE || c==WO_LE );
! 577: assert( op!=TK_GT || c==WO_GT );
! 578: assert( op!=TK_GE || c==WO_GE );
! 579: return c;
! 580: }
! 581:
! 582: /*
! 583: ** Search for a term in the WHERE clause that is of the form "X <op> <expr>"
! 584: ** where X is a reference to the iColumn of table iCur and <op> is one of
! 585: ** the WO_xx operator codes specified by the op parameter.
! 586: ** Return a pointer to the term. Return 0 if not found.
! 587: */
! 588: static WhereTerm *findTerm(
! 589: WhereClause *pWC, /* The WHERE clause to be searched */
! 590: int iCur, /* Cursor number of LHS */
! 591: int iColumn, /* Column number of LHS */
! 592: Bitmask notReady, /* RHS must not overlap with this mask */
! 593: u32 op, /* Mask of WO_xx values describing operator */
! 594: Index *pIdx /* Must be compatible with this index, if not NULL */
! 595: ){
! 596: WhereTerm *pTerm;
! 597: int k;
! 598: assert( iCur>=0 );
! 599: op &= WO_ALL;
! 600: for(; pWC; pWC=pWC->pOuter){
! 601: for(pTerm=pWC->a, k=pWC->nTerm; k; k--, pTerm++){
! 602: if( pTerm->leftCursor==iCur
! 603: && (pTerm->prereqRight & notReady)==0
! 604: && pTerm->u.leftColumn==iColumn
! 605: && (pTerm->eOperator & op)!=0
! 606: ){
! 607: if( iColumn>=0 && pIdx && pTerm->eOperator!=WO_ISNULL ){
! 608: Expr *pX = pTerm->pExpr;
! 609: CollSeq *pColl;
! 610: char idxaff;
! 611: int j;
! 612: Parse *pParse = pWC->pParse;
! 613:
! 614: idxaff = pIdx->pTable->aCol[iColumn].affinity;
! 615: if( !sqlite3IndexAffinityOk(pX, idxaff) ) continue;
! 616:
! 617: /* Figure out the collation sequence required from an index for
! 618: ** it to be useful for optimising expression pX. Store this
! 619: ** value in variable pColl.
! 620: */
! 621: assert(pX->pLeft);
! 622: pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
! 623: assert(pColl || pParse->nErr);
! 624:
! 625: for(j=0; pIdx->aiColumn[j]!=iColumn; j++){
! 626: if( NEVER(j>=pIdx->nColumn) ) return 0;
! 627: }
! 628: if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[j]) ) continue;
! 629: }
! 630: return pTerm;
! 631: }
! 632: }
! 633: }
! 634: return 0;
! 635: }
! 636:
! 637: /* Forward reference */
! 638: static void exprAnalyze(SrcList*, WhereClause*, int);
! 639:
! 640: /*
! 641: ** Call exprAnalyze on all terms in a WHERE clause.
! 642: **
! 643: **
! 644: */
! 645: static void exprAnalyzeAll(
! 646: SrcList *pTabList, /* the FROM clause */
! 647: WhereClause *pWC /* the WHERE clause to be analyzed */
! 648: ){
! 649: int i;
! 650: for(i=pWC->nTerm-1; i>=0; i--){
! 651: exprAnalyze(pTabList, pWC, i);
! 652: }
! 653: }
! 654:
! 655: #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
! 656: /*
! 657: ** Check to see if the given expression is a LIKE or GLOB operator that
! 658: ** can be optimized using inequality constraints. Return TRUE if it is
! 659: ** so and false if not.
! 660: **
! 661: ** In order for the operator to be optimizible, the RHS must be a string
! 662: ** literal that does not begin with a wildcard.
! 663: */
! 664: static int isLikeOrGlob(
! 665: Parse *pParse, /* Parsing and code generating context */
! 666: Expr *pExpr, /* Test this expression */
! 667: Expr **ppPrefix, /* Pointer to TK_STRING expression with pattern prefix */
! 668: int *pisComplete, /* True if the only wildcard is % in the last character */
! 669: int *pnoCase /* True if uppercase is equivalent to lowercase */
! 670: ){
! 671: const char *z = 0; /* String on RHS of LIKE operator */
! 672: Expr *pRight, *pLeft; /* Right and left size of LIKE operator */
! 673: ExprList *pList; /* List of operands to the LIKE operator */
! 674: int c; /* One character in z[] */
! 675: int cnt; /* Number of non-wildcard prefix characters */
! 676: char wc[3]; /* Wildcard characters */
! 677: sqlite3 *db = pParse->db; /* Database connection */
! 678: sqlite3_value *pVal = 0;
! 679: int op; /* Opcode of pRight */
! 680:
! 681: if( !sqlite3IsLikeFunction(db, pExpr, pnoCase, wc) ){
! 682: return 0;
! 683: }
! 684: #ifdef SQLITE_EBCDIC
! 685: if( *pnoCase ) return 0;
! 686: #endif
! 687: pList = pExpr->x.pList;
! 688: pLeft = pList->a[1].pExpr;
! 689: if( pLeft->op!=TK_COLUMN || sqlite3ExprAffinity(pLeft)!=SQLITE_AFF_TEXT ){
! 690: /* IMP: R-02065-49465 The left-hand side of the LIKE or GLOB operator must
! 691: ** be the name of an indexed column with TEXT affinity. */
! 692: return 0;
! 693: }
! 694: assert( pLeft->iColumn!=(-1) ); /* Because IPK never has AFF_TEXT */
! 695:
! 696: pRight = pList->a[0].pExpr;
! 697: op = pRight->op;
! 698: if( op==TK_REGISTER ){
! 699: op = pRight->op2;
! 700: }
! 701: if( op==TK_VARIABLE ){
! 702: Vdbe *pReprepare = pParse->pReprepare;
! 703: int iCol = pRight->iColumn;
! 704: pVal = sqlite3VdbeGetValue(pReprepare, iCol, SQLITE_AFF_NONE);
! 705: if( pVal && sqlite3_value_type(pVal)==SQLITE_TEXT ){
! 706: z = (char *)sqlite3_value_text(pVal);
! 707: }
! 708: sqlite3VdbeSetVarmask(pParse->pVdbe, iCol);
! 709: assert( pRight->op==TK_VARIABLE || pRight->op==TK_REGISTER );
! 710: }else if( op==TK_STRING ){
! 711: z = pRight->u.zToken;
! 712: }
! 713: if( z ){
! 714: cnt = 0;
! 715: while( (c=z[cnt])!=0 && c!=wc[0] && c!=wc[1] && c!=wc[2] ){
! 716: cnt++;
! 717: }
! 718: if( cnt!=0 && 255!=(u8)z[cnt-1] ){
! 719: Expr *pPrefix;
! 720: *pisComplete = c==wc[0] && z[cnt+1]==0;
! 721: pPrefix = sqlite3Expr(db, TK_STRING, z);
! 722: if( pPrefix ) pPrefix->u.zToken[cnt] = 0;
! 723: *ppPrefix = pPrefix;
! 724: if( op==TK_VARIABLE ){
! 725: Vdbe *v = pParse->pVdbe;
! 726: sqlite3VdbeSetVarmask(v, pRight->iColumn);
! 727: if( *pisComplete && pRight->u.zToken[1] ){
! 728: /* If the rhs of the LIKE expression is a variable, and the current
! 729: ** value of the variable means there is no need to invoke the LIKE
! 730: ** function, then no OP_Variable will be added to the program.
! 731: ** This causes problems for the sqlite3_bind_parameter_name()
! 732: ** API. To workaround them, add a dummy OP_Variable here.
! 733: */
! 734: int r1 = sqlite3GetTempReg(pParse);
! 735: sqlite3ExprCodeTarget(pParse, pRight, r1);
! 736: sqlite3VdbeChangeP3(v, sqlite3VdbeCurrentAddr(v)-1, 0);
! 737: sqlite3ReleaseTempReg(pParse, r1);
! 738: }
! 739: }
! 740: }else{
! 741: z = 0;
! 742: }
! 743: }
! 744:
! 745: sqlite3ValueFree(pVal);
! 746: return (z!=0);
! 747: }
! 748: #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
! 749:
! 750:
! 751: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 752: /*
! 753: ** Check to see if the given expression is of the form
! 754: **
! 755: ** column MATCH expr
! 756: **
! 757: ** If it is then return TRUE. If not, return FALSE.
! 758: */
! 759: static int isMatchOfColumn(
! 760: Expr *pExpr /* Test this expression */
! 761: ){
! 762: ExprList *pList;
! 763:
! 764: if( pExpr->op!=TK_FUNCTION ){
! 765: return 0;
! 766: }
! 767: if( sqlite3StrICmp(pExpr->u.zToken,"match")!=0 ){
! 768: return 0;
! 769: }
! 770: pList = pExpr->x.pList;
! 771: if( pList->nExpr!=2 ){
! 772: return 0;
! 773: }
! 774: if( pList->a[1].pExpr->op != TK_COLUMN ){
! 775: return 0;
! 776: }
! 777: return 1;
! 778: }
! 779: #endif /* SQLITE_OMIT_VIRTUALTABLE */
! 780:
! 781: /*
! 782: ** If the pBase expression originated in the ON or USING clause of
! 783: ** a join, then transfer the appropriate markings over to derived.
! 784: */
! 785: static void transferJoinMarkings(Expr *pDerived, Expr *pBase){
! 786: pDerived->flags |= pBase->flags & EP_FromJoin;
! 787: pDerived->iRightJoinTable = pBase->iRightJoinTable;
! 788: }
! 789:
! 790: #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
! 791: /*
! 792: ** Analyze a term that consists of two or more OR-connected
! 793: ** subterms. So in:
! 794: **
! 795: ** ... WHERE (a=5) AND (b=7 OR c=9 OR d=13) AND (d=13)
! 796: ** ^^^^^^^^^^^^^^^^^^^^
! 797: **
! 798: ** This routine analyzes terms such as the middle term in the above example.
! 799: ** A WhereOrTerm object is computed and attached to the term under
! 800: ** analysis, regardless of the outcome of the analysis. Hence:
! 801: **
! 802: ** WhereTerm.wtFlags |= TERM_ORINFO
! 803: ** WhereTerm.u.pOrInfo = a dynamically allocated WhereOrTerm object
! 804: **
! 805: ** The term being analyzed must have two or more of OR-connected subterms.
! 806: ** A single subterm might be a set of AND-connected sub-subterms.
! 807: ** Examples of terms under analysis:
! 808: **
! 809: ** (A) t1.x=t2.y OR t1.x=t2.z OR t1.y=15 OR t1.z=t3.a+5
! 810: ** (B) x=expr1 OR expr2=x OR x=expr3
! 811: ** (C) t1.x=t2.y OR (t1.x=t2.z AND t1.y=15)
! 812: ** (D) x=expr1 OR (y>11 AND y<22 AND z LIKE '*hello*')
! 813: ** (E) (p.a=1 AND q.b=2 AND r.c=3) OR (p.x=4 AND q.y=5 AND r.z=6)
! 814: **
! 815: ** CASE 1:
! 816: **
! 817: ** If all subterms are of the form T.C=expr for some single column of C
! 818: ** a single table T (as shown in example B above) then create a new virtual
! 819: ** term that is an equivalent IN expression. In other words, if the term
! 820: ** being analyzed is:
! 821: **
! 822: ** x = expr1 OR expr2 = x OR x = expr3
! 823: **
! 824: ** then create a new virtual term like this:
! 825: **
! 826: ** x IN (expr1,expr2,expr3)
! 827: **
! 828: ** CASE 2:
! 829: **
! 830: ** If all subterms are indexable by a single table T, then set
! 831: **
! 832: ** WhereTerm.eOperator = WO_OR
! 833: ** WhereTerm.u.pOrInfo->indexable |= the cursor number for table T
! 834: **
! 835: ** A subterm is "indexable" if it is of the form
! 836: ** "T.C <op> <expr>" where C is any column of table T and
! 837: ** <op> is one of "=", "<", "<=", ">", ">=", "IS NULL", or "IN".
! 838: ** A subterm is also indexable if it is an AND of two or more
! 839: ** subsubterms at least one of which is indexable. Indexable AND
! 840: ** subterms have their eOperator set to WO_AND and they have
! 841: ** u.pAndInfo set to a dynamically allocated WhereAndTerm object.
! 842: **
! 843: ** From another point of view, "indexable" means that the subterm could
! 844: ** potentially be used with an index if an appropriate index exists.
! 845: ** This analysis does not consider whether or not the index exists; that
! 846: ** is something the bestIndex() routine will determine. This analysis
! 847: ** only looks at whether subterms appropriate for indexing exist.
! 848: **
! 849: ** All examples A through E above all satisfy case 2. But if a term
! 850: ** also statisfies case 1 (such as B) we know that the optimizer will
! 851: ** always prefer case 1, so in that case we pretend that case 2 is not
! 852: ** satisfied.
! 853: **
! 854: ** It might be the case that multiple tables are indexable. For example,
! 855: ** (E) above is indexable on tables P, Q, and R.
! 856: **
! 857: ** Terms that satisfy case 2 are candidates for lookup by using
! 858: ** separate indices to find rowids for each subterm and composing
! 859: ** the union of all rowids using a RowSet object. This is similar
! 860: ** to "bitmap indices" in other database engines.
! 861: **
! 862: ** OTHERWISE:
! 863: **
! 864: ** If neither case 1 nor case 2 apply, then leave the eOperator set to
! 865: ** zero. This term is not useful for search.
! 866: */
! 867: static void exprAnalyzeOrTerm(
! 868: SrcList *pSrc, /* the FROM clause */
! 869: WhereClause *pWC, /* the complete WHERE clause */
! 870: int idxTerm /* Index of the OR-term to be analyzed */
! 871: ){
! 872: Parse *pParse = pWC->pParse; /* Parser context */
! 873: sqlite3 *db = pParse->db; /* Database connection */
! 874: WhereTerm *pTerm = &pWC->a[idxTerm]; /* The term to be analyzed */
! 875: Expr *pExpr = pTerm->pExpr; /* The expression of the term */
! 876: WhereMaskSet *pMaskSet = pWC->pMaskSet; /* Table use masks */
! 877: int i; /* Loop counters */
! 878: WhereClause *pOrWc; /* Breakup of pTerm into subterms */
! 879: WhereTerm *pOrTerm; /* A Sub-term within the pOrWc */
! 880: WhereOrInfo *pOrInfo; /* Additional information associated with pTerm */
! 881: Bitmask chngToIN; /* Tables that might satisfy case 1 */
! 882: Bitmask indexable; /* Tables that are indexable, satisfying case 2 */
! 883:
! 884: /*
! 885: ** Break the OR clause into its separate subterms. The subterms are
! 886: ** stored in a WhereClause structure containing within the WhereOrInfo
! 887: ** object that is attached to the original OR clause term.
! 888: */
! 889: assert( (pTerm->wtFlags & (TERM_DYNAMIC|TERM_ORINFO|TERM_ANDINFO))==0 );
! 890: assert( pExpr->op==TK_OR );
! 891: pTerm->u.pOrInfo = pOrInfo = sqlite3DbMallocZero(db, sizeof(*pOrInfo));
! 892: if( pOrInfo==0 ) return;
! 893: pTerm->wtFlags |= TERM_ORINFO;
! 894: pOrWc = &pOrInfo->wc;
! 895: whereClauseInit(pOrWc, pWC->pParse, pMaskSet, pWC->wctrlFlags);
! 896: whereSplit(pOrWc, pExpr, TK_OR);
! 897: exprAnalyzeAll(pSrc, pOrWc);
! 898: if( db->mallocFailed ) return;
! 899: assert( pOrWc->nTerm>=2 );
! 900:
! 901: /*
! 902: ** Compute the set of tables that might satisfy cases 1 or 2.
! 903: */
! 904: indexable = ~(Bitmask)0;
! 905: chngToIN = ~(pWC->vmask);
! 906: for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0 && indexable; i--, pOrTerm++){
! 907: if( (pOrTerm->eOperator & WO_SINGLE)==0 ){
! 908: WhereAndInfo *pAndInfo;
! 909: assert( pOrTerm->eOperator==0 );
! 910: assert( (pOrTerm->wtFlags & (TERM_ANDINFO|TERM_ORINFO))==0 );
! 911: chngToIN = 0;
! 912: pAndInfo = sqlite3DbMallocRaw(db, sizeof(*pAndInfo));
! 913: if( pAndInfo ){
! 914: WhereClause *pAndWC;
! 915: WhereTerm *pAndTerm;
! 916: int j;
! 917: Bitmask b = 0;
! 918: pOrTerm->u.pAndInfo = pAndInfo;
! 919: pOrTerm->wtFlags |= TERM_ANDINFO;
! 920: pOrTerm->eOperator = WO_AND;
! 921: pAndWC = &pAndInfo->wc;
! 922: whereClauseInit(pAndWC, pWC->pParse, pMaskSet, pWC->wctrlFlags);
! 923: whereSplit(pAndWC, pOrTerm->pExpr, TK_AND);
! 924: exprAnalyzeAll(pSrc, pAndWC);
! 925: pAndWC->pOuter = pWC;
! 926: testcase( db->mallocFailed );
! 927: if( !db->mallocFailed ){
! 928: for(j=0, pAndTerm=pAndWC->a; j<pAndWC->nTerm; j++, pAndTerm++){
! 929: assert( pAndTerm->pExpr );
! 930: if( allowedOp(pAndTerm->pExpr->op) ){
! 931: b |= getMask(pMaskSet, pAndTerm->leftCursor);
! 932: }
! 933: }
! 934: }
! 935: indexable &= b;
! 936: }
! 937: }else if( pOrTerm->wtFlags & TERM_COPIED ){
! 938: /* Skip this term for now. We revisit it when we process the
! 939: ** corresponding TERM_VIRTUAL term */
! 940: }else{
! 941: Bitmask b;
! 942: b = getMask(pMaskSet, pOrTerm->leftCursor);
! 943: if( pOrTerm->wtFlags & TERM_VIRTUAL ){
! 944: WhereTerm *pOther = &pOrWc->a[pOrTerm->iParent];
! 945: b |= getMask(pMaskSet, pOther->leftCursor);
! 946: }
! 947: indexable &= b;
! 948: if( pOrTerm->eOperator!=WO_EQ ){
! 949: chngToIN = 0;
! 950: }else{
! 951: chngToIN &= b;
! 952: }
! 953: }
! 954: }
! 955:
! 956: /*
! 957: ** Record the set of tables that satisfy case 2. The set might be
! 958: ** empty.
! 959: */
! 960: pOrInfo->indexable = indexable;
! 961: pTerm->eOperator = indexable==0 ? 0 : WO_OR;
! 962:
! 963: /*
! 964: ** chngToIN holds a set of tables that *might* satisfy case 1. But
! 965: ** we have to do some additional checking to see if case 1 really
! 966: ** is satisfied.
! 967: **
! 968: ** chngToIN will hold either 0, 1, or 2 bits. The 0-bit case means
! 969: ** that there is no possibility of transforming the OR clause into an
! 970: ** IN operator because one or more terms in the OR clause contain
! 971: ** something other than == on a column in the single table. The 1-bit
! 972: ** case means that every term of the OR clause is of the form
! 973: ** "table.column=expr" for some single table. The one bit that is set
! 974: ** will correspond to the common table. We still need to check to make
! 975: ** sure the same column is used on all terms. The 2-bit case is when
! 976: ** the all terms are of the form "table1.column=table2.column". It
! 977: ** might be possible to form an IN operator with either table1.column
! 978: ** or table2.column as the LHS if either is common to every term of
! 979: ** the OR clause.
! 980: **
! 981: ** Note that terms of the form "table.column1=table.column2" (the
! 982: ** same table on both sizes of the ==) cannot be optimized.
! 983: */
! 984: if( chngToIN ){
! 985: int okToChngToIN = 0; /* True if the conversion to IN is valid */
! 986: int iColumn = -1; /* Column index on lhs of IN operator */
! 987: int iCursor = -1; /* Table cursor common to all terms */
! 988: int j = 0; /* Loop counter */
! 989:
! 990: /* Search for a table and column that appears on one side or the
! 991: ** other of the == operator in every subterm. That table and column
! 992: ** will be recorded in iCursor and iColumn. There might not be any
! 993: ** such table and column. Set okToChngToIN if an appropriate table
! 994: ** and column is found but leave okToChngToIN false if not found.
! 995: */
! 996: for(j=0; j<2 && !okToChngToIN; j++){
! 997: pOrTerm = pOrWc->a;
! 998: for(i=pOrWc->nTerm-1; i>=0; i--, pOrTerm++){
! 999: assert( pOrTerm->eOperator==WO_EQ );
! 1000: pOrTerm->wtFlags &= ~TERM_OR_OK;
! 1001: if( pOrTerm->leftCursor==iCursor ){
! 1002: /* This is the 2-bit case and we are on the second iteration and
! 1003: ** current term is from the first iteration. So skip this term. */
! 1004: assert( j==1 );
! 1005: continue;
! 1006: }
! 1007: if( (chngToIN & getMask(pMaskSet, pOrTerm->leftCursor))==0 ){
! 1008: /* This term must be of the form t1.a==t2.b where t2 is in the
! 1009: ** chngToIN set but t1 is not. This term will be either preceeded
! 1010: ** or follwed by an inverted copy (t2.b==t1.a). Skip this term
! 1011: ** and use its inversion. */
! 1012: testcase( pOrTerm->wtFlags & TERM_COPIED );
! 1013: testcase( pOrTerm->wtFlags & TERM_VIRTUAL );
! 1014: assert( pOrTerm->wtFlags & (TERM_COPIED|TERM_VIRTUAL) );
! 1015: continue;
! 1016: }
! 1017: iColumn = pOrTerm->u.leftColumn;
! 1018: iCursor = pOrTerm->leftCursor;
! 1019: break;
! 1020: }
! 1021: if( i<0 ){
! 1022: /* No candidate table+column was found. This can only occur
! 1023: ** on the second iteration */
! 1024: assert( j==1 );
! 1025: assert( (chngToIN&(chngToIN-1))==0 );
! 1026: assert( chngToIN==getMask(pMaskSet, iCursor) );
! 1027: break;
! 1028: }
! 1029: testcase( j==1 );
! 1030:
! 1031: /* We have found a candidate table and column. Check to see if that
! 1032: ** table and column is common to every term in the OR clause */
! 1033: okToChngToIN = 1;
! 1034: for(; i>=0 && okToChngToIN; i--, pOrTerm++){
! 1035: assert( pOrTerm->eOperator==WO_EQ );
! 1036: if( pOrTerm->leftCursor!=iCursor ){
! 1037: pOrTerm->wtFlags &= ~TERM_OR_OK;
! 1038: }else if( pOrTerm->u.leftColumn!=iColumn ){
! 1039: okToChngToIN = 0;
! 1040: }else{
! 1041: int affLeft, affRight;
! 1042: /* If the right-hand side is also a column, then the affinities
! 1043: ** of both right and left sides must be such that no type
! 1044: ** conversions are required on the right. (Ticket #2249)
! 1045: */
! 1046: affRight = sqlite3ExprAffinity(pOrTerm->pExpr->pRight);
! 1047: affLeft = sqlite3ExprAffinity(pOrTerm->pExpr->pLeft);
! 1048: if( affRight!=0 && affRight!=affLeft ){
! 1049: okToChngToIN = 0;
! 1050: }else{
! 1051: pOrTerm->wtFlags |= TERM_OR_OK;
! 1052: }
! 1053: }
! 1054: }
! 1055: }
! 1056:
! 1057: /* At this point, okToChngToIN is true if original pTerm satisfies
! 1058: ** case 1. In that case, construct a new virtual term that is
! 1059: ** pTerm converted into an IN operator.
! 1060: **
! 1061: ** EV: R-00211-15100
! 1062: */
! 1063: if( okToChngToIN ){
! 1064: Expr *pDup; /* A transient duplicate expression */
! 1065: ExprList *pList = 0; /* The RHS of the IN operator */
! 1066: Expr *pLeft = 0; /* The LHS of the IN operator */
! 1067: Expr *pNew; /* The complete IN operator */
! 1068:
! 1069: for(i=pOrWc->nTerm-1, pOrTerm=pOrWc->a; i>=0; i--, pOrTerm++){
! 1070: if( (pOrTerm->wtFlags & TERM_OR_OK)==0 ) continue;
! 1071: assert( pOrTerm->eOperator==WO_EQ );
! 1072: assert( pOrTerm->leftCursor==iCursor );
! 1073: assert( pOrTerm->u.leftColumn==iColumn );
! 1074: pDup = sqlite3ExprDup(db, pOrTerm->pExpr->pRight, 0);
! 1075: pList = sqlite3ExprListAppend(pWC->pParse, pList, pDup);
! 1076: pLeft = pOrTerm->pExpr->pLeft;
! 1077: }
! 1078: assert( pLeft!=0 );
! 1079: pDup = sqlite3ExprDup(db, pLeft, 0);
! 1080: pNew = sqlite3PExpr(pParse, TK_IN, pDup, 0, 0);
! 1081: if( pNew ){
! 1082: int idxNew;
! 1083: transferJoinMarkings(pNew, pExpr);
! 1084: assert( !ExprHasProperty(pNew, EP_xIsSelect) );
! 1085: pNew->x.pList = pList;
! 1086: idxNew = whereClauseInsert(pWC, pNew, TERM_VIRTUAL|TERM_DYNAMIC);
! 1087: testcase( idxNew==0 );
! 1088: exprAnalyze(pSrc, pWC, idxNew);
! 1089: pTerm = &pWC->a[idxTerm];
! 1090: pWC->a[idxNew].iParent = idxTerm;
! 1091: pTerm->nChild = 1;
! 1092: }else{
! 1093: sqlite3ExprListDelete(db, pList);
! 1094: }
! 1095: pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */
! 1096: }
! 1097: }
! 1098: }
! 1099: #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */
! 1100:
! 1101:
! 1102: /*
! 1103: ** The input to this routine is an WhereTerm structure with only the
! 1104: ** "pExpr" field filled in. The job of this routine is to analyze the
! 1105: ** subexpression and populate all the other fields of the WhereTerm
! 1106: ** structure.
! 1107: **
! 1108: ** If the expression is of the form "<expr> <op> X" it gets commuted
! 1109: ** to the standard form of "X <op> <expr>".
! 1110: **
! 1111: ** If the expression is of the form "X <op> Y" where both X and Y are
! 1112: ** columns, then the original expression is unchanged and a new virtual
! 1113: ** term of the form "Y <op> X" is added to the WHERE clause and
! 1114: ** analyzed separately. The original term is marked with TERM_COPIED
! 1115: ** and the new term is marked with TERM_DYNAMIC (because it's pExpr
! 1116: ** needs to be freed with the WhereClause) and TERM_VIRTUAL (because it
! 1117: ** is a commuted copy of a prior term.) The original term has nChild=1
! 1118: ** and the copy has idxParent set to the index of the original term.
! 1119: */
! 1120: static void exprAnalyze(
! 1121: SrcList *pSrc, /* the FROM clause */
! 1122: WhereClause *pWC, /* the WHERE clause */
! 1123: int idxTerm /* Index of the term to be analyzed */
! 1124: ){
! 1125: WhereTerm *pTerm; /* The term to be analyzed */
! 1126: WhereMaskSet *pMaskSet; /* Set of table index masks */
! 1127: Expr *pExpr; /* The expression to be analyzed */
! 1128: Bitmask prereqLeft; /* Prerequesites of the pExpr->pLeft */
! 1129: Bitmask prereqAll; /* Prerequesites of pExpr */
! 1130: Bitmask extraRight = 0; /* Extra dependencies on LEFT JOIN */
! 1131: Expr *pStr1 = 0; /* RHS of LIKE/GLOB operator */
! 1132: int isComplete = 0; /* RHS of LIKE/GLOB ends with wildcard */
! 1133: int noCase = 0; /* LIKE/GLOB distinguishes case */
! 1134: int op; /* Top-level operator. pExpr->op */
! 1135: Parse *pParse = pWC->pParse; /* Parsing context */
! 1136: sqlite3 *db = pParse->db; /* Database connection */
! 1137:
! 1138: if( db->mallocFailed ){
! 1139: return;
! 1140: }
! 1141: pTerm = &pWC->a[idxTerm];
! 1142: pMaskSet = pWC->pMaskSet;
! 1143: pExpr = pTerm->pExpr;
! 1144: prereqLeft = exprTableUsage(pMaskSet, pExpr->pLeft);
! 1145: op = pExpr->op;
! 1146: if( op==TK_IN ){
! 1147: assert( pExpr->pRight==0 );
! 1148: if( ExprHasProperty(pExpr, EP_xIsSelect) ){
! 1149: pTerm->prereqRight = exprSelectTableUsage(pMaskSet, pExpr->x.pSelect);
! 1150: }else{
! 1151: pTerm->prereqRight = exprListTableUsage(pMaskSet, pExpr->x.pList);
! 1152: }
! 1153: }else if( op==TK_ISNULL ){
! 1154: pTerm->prereqRight = 0;
! 1155: }else{
! 1156: pTerm->prereqRight = exprTableUsage(pMaskSet, pExpr->pRight);
! 1157: }
! 1158: prereqAll = exprTableUsage(pMaskSet, pExpr);
! 1159: if( ExprHasProperty(pExpr, EP_FromJoin) ){
! 1160: Bitmask x = getMask(pMaskSet, pExpr->iRightJoinTable);
! 1161: prereqAll |= x;
! 1162: extraRight = x-1; /* ON clause terms may not be used with an index
! 1163: ** on left table of a LEFT JOIN. Ticket #3015 */
! 1164: }
! 1165: pTerm->prereqAll = prereqAll;
! 1166: pTerm->leftCursor = -1;
! 1167: pTerm->iParent = -1;
! 1168: pTerm->eOperator = 0;
! 1169: if( allowedOp(op) && (pTerm->prereqRight & prereqLeft)==0 ){
! 1170: Expr *pLeft = pExpr->pLeft;
! 1171: Expr *pRight = pExpr->pRight;
! 1172: if( pLeft->op==TK_COLUMN ){
! 1173: pTerm->leftCursor = pLeft->iTable;
! 1174: pTerm->u.leftColumn = pLeft->iColumn;
! 1175: pTerm->eOperator = operatorMask(op);
! 1176: }
! 1177: if( pRight && pRight->op==TK_COLUMN ){
! 1178: WhereTerm *pNew;
! 1179: Expr *pDup;
! 1180: if( pTerm->leftCursor>=0 ){
! 1181: int idxNew;
! 1182: pDup = sqlite3ExprDup(db, pExpr, 0);
! 1183: if( db->mallocFailed ){
! 1184: sqlite3ExprDelete(db, pDup);
! 1185: return;
! 1186: }
! 1187: idxNew = whereClauseInsert(pWC, pDup, TERM_VIRTUAL|TERM_DYNAMIC);
! 1188: if( idxNew==0 ) return;
! 1189: pNew = &pWC->a[idxNew];
! 1190: pNew->iParent = idxTerm;
! 1191: pTerm = &pWC->a[idxTerm];
! 1192: pTerm->nChild = 1;
! 1193: pTerm->wtFlags |= TERM_COPIED;
! 1194: }else{
! 1195: pDup = pExpr;
! 1196: pNew = pTerm;
! 1197: }
! 1198: exprCommute(pParse, pDup);
! 1199: pLeft = pDup->pLeft;
! 1200: pNew->leftCursor = pLeft->iTable;
! 1201: pNew->u.leftColumn = pLeft->iColumn;
! 1202: testcase( (prereqLeft | extraRight) != prereqLeft );
! 1203: pNew->prereqRight = prereqLeft | extraRight;
! 1204: pNew->prereqAll = prereqAll;
! 1205: pNew->eOperator = operatorMask(pDup->op);
! 1206: }
! 1207: }
! 1208:
! 1209: #ifndef SQLITE_OMIT_BETWEEN_OPTIMIZATION
! 1210: /* If a term is the BETWEEN operator, create two new virtual terms
! 1211: ** that define the range that the BETWEEN implements. For example:
! 1212: **
! 1213: ** a BETWEEN b AND c
! 1214: **
! 1215: ** is converted into:
! 1216: **
! 1217: ** (a BETWEEN b AND c) AND (a>=b) AND (a<=c)
! 1218: **
! 1219: ** The two new terms are added onto the end of the WhereClause object.
! 1220: ** The new terms are "dynamic" and are children of the original BETWEEN
! 1221: ** term. That means that if the BETWEEN term is coded, the children are
! 1222: ** skipped. Or, if the children are satisfied by an index, the original
! 1223: ** BETWEEN term is skipped.
! 1224: */
! 1225: else if( pExpr->op==TK_BETWEEN && pWC->op==TK_AND ){
! 1226: ExprList *pList = pExpr->x.pList;
! 1227: int i;
! 1228: static const u8 ops[] = {TK_GE, TK_LE};
! 1229: assert( pList!=0 );
! 1230: assert( pList->nExpr==2 );
! 1231: for(i=0; i<2; i++){
! 1232: Expr *pNewExpr;
! 1233: int idxNew;
! 1234: pNewExpr = sqlite3PExpr(pParse, ops[i],
! 1235: sqlite3ExprDup(db, pExpr->pLeft, 0),
! 1236: sqlite3ExprDup(db, pList->a[i].pExpr, 0), 0);
! 1237: idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
! 1238: testcase( idxNew==0 );
! 1239: exprAnalyze(pSrc, pWC, idxNew);
! 1240: pTerm = &pWC->a[idxTerm];
! 1241: pWC->a[idxNew].iParent = idxTerm;
! 1242: }
! 1243: pTerm->nChild = 2;
! 1244: }
! 1245: #endif /* SQLITE_OMIT_BETWEEN_OPTIMIZATION */
! 1246:
! 1247: #if !defined(SQLITE_OMIT_OR_OPTIMIZATION) && !defined(SQLITE_OMIT_SUBQUERY)
! 1248: /* Analyze a term that is composed of two or more subterms connected by
! 1249: ** an OR operator.
! 1250: */
! 1251: else if( pExpr->op==TK_OR ){
! 1252: assert( pWC->op==TK_AND );
! 1253: exprAnalyzeOrTerm(pSrc, pWC, idxTerm);
! 1254: pTerm = &pWC->a[idxTerm];
! 1255: }
! 1256: #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
! 1257:
! 1258: #ifndef SQLITE_OMIT_LIKE_OPTIMIZATION
! 1259: /* Add constraints to reduce the search space on a LIKE or GLOB
! 1260: ** operator.
! 1261: **
! 1262: ** A like pattern of the form "x LIKE 'abc%'" is changed into constraints
! 1263: **
! 1264: ** x>='abc' AND x<'abd' AND x LIKE 'abc%'
! 1265: **
! 1266: ** The last character of the prefix "abc" is incremented to form the
! 1267: ** termination condition "abd".
! 1268: */
! 1269: if( pWC->op==TK_AND
! 1270: && isLikeOrGlob(pParse, pExpr, &pStr1, &isComplete, &noCase)
! 1271: ){
! 1272: Expr *pLeft; /* LHS of LIKE/GLOB operator */
! 1273: Expr *pStr2; /* Copy of pStr1 - RHS of LIKE/GLOB operator */
! 1274: Expr *pNewExpr1;
! 1275: Expr *pNewExpr2;
! 1276: int idxNew1;
! 1277: int idxNew2;
! 1278: CollSeq *pColl; /* Collating sequence to use */
! 1279:
! 1280: pLeft = pExpr->x.pList->a[1].pExpr;
! 1281: pStr2 = sqlite3ExprDup(db, pStr1, 0);
! 1282: if( !db->mallocFailed ){
! 1283: u8 c, *pC; /* Last character before the first wildcard */
! 1284: pC = (u8*)&pStr2->u.zToken[sqlite3Strlen30(pStr2->u.zToken)-1];
! 1285: c = *pC;
! 1286: if( noCase ){
! 1287: /* The point is to increment the last character before the first
! 1288: ** wildcard. But if we increment '@', that will push it into the
! 1289: ** alphabetic range where case conversions will mess up the
! 1290: ** inequality. To avoid this, make sure to also run the full
! 1291: ** LIKE on all candidate expressions by clearing the isComplete flag
! 1292: */
! 1293: if( c=='A'-1 ) isComplete = 0; /* EV: R-64339-08207 */
! 1294:
! 1295:
! 1296: c = sqlite3UpperToLower[c];
! 1297: }
! 1298: *pC = c + 1;
! 1299: }
! 1300: pColl = sqlite3FindCollSeq(db, SQLITE_UTF8, noCase ? "NOCASE" : "BINARY",0);
! 1301: pNewExpr1 = sqlite3PExpr(pParse, TK_GE,
! 1302: sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
! 1303: pStr1, 0);
! 1304: idxNew1 = whereClauseInsert(pWC, pNewExpr1, TERM_VIRTUAL|TERM_DYNAMIC);
! 1305: testcase( idxNew1==0 );
! 1306: exprAnalyze(pSrc, pWC, idxNew1);
! 1307: pNewExpr2 = sqlite3PExpr(pParse, TK_LT,
! 1308: sqlite3ExprSetColl(sqlite3ExprDup(db,pLeft,0), pColl),
! 1309: pStr2, 0);
! 1310: idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);
! 1311: testcase( idxNew2==0 );
! 1312: exprAnalyze(pSrc, pWC, idxNew2);
! 1313: pTerm = &pWC->a[idxTerm];
! 1314: if( isComplete ){
! 1315: pWC->a[idxNew1].iParent = idxTerm;
! 1316: pWC->a[idxNew2].iParent = idxTerm;
! 1317: pTerm->nChild = 2;
! 1318: }
! 1319: }
! 1320: #endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */
! 1321:
! 1322: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 1323: /* Add a WO_MATCH auxiliary term to the constraint set if the
! 1324: ** current expression is of the form: column MATCH expr.
! 1325: ** This information is used by the xBestIndex methods of
! 1326: ** virtual tables. The native query optimizer does not attempt
! 1327: ** to do anything with MATCH functions.
! 1328: */
! 1329: if( isMatchOfColumn(pExpr) ){
! 1330: int idxNew;
! 1331: Expr *pRight, *pLeft;
! 1332: WhereTerm *pNewTerm;
! 1333: Bitmask prereqColumn, prereqExpr;
! 1334:
! 1335: pRight = pExpr->x.pList->a[0].pExpr;
! 1336: pLeft = pExpr->x.pList->a[1].pExpr;
! 1337: prereqExpr = exprTableUsage(pMaskSet, pRight);
! 1338: prereqColumn = exprTableUsage(pMaskSet, pLeft);
! 1339: if( (prereqExpr & prereqColumn)==0 ){
! 1340: Expr *pNewExpr;
! 1341: pNewExpr = sqlite3PExpr(pParse, TK_MATCH,
! 1342: 0, sqlite3ExprDup(db, pRight, 0), 0);
! 1343: idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC);
! 1344: testcase( idxNew==0 );
! 1345: pNewTerm = &pWC->a[idxNew];
! 1346: pNewTerm->prereqRight = prereqExpr;
! 1347: pNewTerm->leftCursor = pLeft->iTable;
! 1348: pNewTerm->u.leftColumn = pLeft->iColumn;
! 1349: pNewTerm->eOperator = WO_MATCH;
! 1350: pNewTerm->iParent = idxTerm;
! 1351: pTerm = &pWC->a[idxTerm];
! 1352: pTerm->nChild = 1;
! 1353: pTerm->wtFlags |= TERM_COPIED;
! 1354: pNewTerm->prereqAll = pTerm->prereqAll;
! 1355: }
! 1356: }
! 1357: #endif /* SQLITE_OMIT_VIRTUALTABLE */
! 1358:
! 1359: #ifdef SQLITE_ENABLE_STAT3
! 1360: /* When sqlite_stat3 histogram data is available an operator of the
! 1361: ** form "x IS NOT NULL" can sometimes be evaluated more efficiently
! 1362: ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a
! 1363: ** virtual term of that form.
! 1364: **
! 1365: ** Note that the virtual term must be tagged with TERM_VNULL. This
! 1366: ** TERM_VNULL tag will suppress the not-null check at the beginning
! 1367: ** of the loop. Without the TERM_VNULL flag, the not-null check at
! 1368: ** the start of the loop will prevent any results from being returned.
! 1369: */
! 1370: if( pExpr->op==TK_NOTNULL
! 1371: && pExpr->pLeft->op==TK_COLUMN
! 1372: && pExpr->pLeft->iColumn>=0
! 1373: ){
! 1374: Expr *pNewExpr;
! 1375: Expr *pLeft = pExpr->pLeft;
! 1376: int idxNew;
! 1377: WhereTerm *pNewTerm;
! 1378:
! 1379: pNewExpr = sqlite3PExpr(pParse, TK_GT,
! 1380: sqlite3ExprDup(db, pLeft, 0),
! 1381: sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0);
! 1382:
! 1383: idxNew = whereClauseInsert(pWC, pNewExpr,
! 1384: TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL);
! 1385: if( idxNew ){
! 1386: pNewTerm = &pWC->a[idxNew];
! 1387: pNewTerm->prereqRight = 0;
! 1388: pNewTerm->leftCursor = pLeft->iTable;
! 1389: pNewTerm->u.leftColumn = pLeft->iColumn;
! 1390: pNewTerm->eOperator = WO_GT;
! 1391: pNewTerm->iParent = idxTerm;
! 1392: pTerm = &pWC->a[idxTerm];
! 1393: pTerm->nChild = 1;
! 1394: pTerm->wtFlags |= TERM_COPIED;
! 1395: pNewTerm->prereqAll = pTerm->prereqAll;
! 1396: }
! 1397: }
! 1398: #endif /* SQLITE_ENABLE_STAT */
! 1399:
! 1400: /* Prevent ON clause terms of a LEFT JOIN from being used to drive
! 1401: ** an index for tables to the left of the join.
! 1402: */
! 1403: pTerm->prereqRight |= extraRight;
! 1404: }
! 1405:
! 1406: /*
! 1407: ** Return TRUE if any of the expressions in pList->a[iFirst...] contain
! 1408: ** a reference to any table other than the iBase table.
! 1409: */
! 1410: static int referencesOtherTables(
! 1411: ExprList *pList, /* Search expressions in ths list */
! 1412: WhereMaskSet *pMaskSet, /* Mapping from tables to bitmaps */
! 1413: int iFirst, /* Be searching with the iFirst-th expression */
! 1414: int iBase /* Ignore references to this table */
! 1415: ){
! 1416: Bitmask allowed = ~getMask(pMaskSet, iBase);
! 1417: while( iFirst<pList->nExpr ){
! 1418: if( (exprTableUsage(pMaskSet, pList->a[iFirst++].pExpr)&allowed)!=0 ){
! 1419: return 1;
! 1420: }
! 1421: }
! 1422: return 0;
! 1423: }
! 1424:
! 1425: /*
! 1426: ** This function searches the expression list passed as the second argument
! 1427: ** for an expression of type TK_COLUMN that refers to the same column and
! 1428: ** uses the same collation sequence as the iCol'th column of index pIdx.
! 1429: ** Argument iBase is the cursor number used for the table that pIdx refers
! 1430: ** to.
! 1431: **
! 1432: ** If such an expression is found, its index in pList->a[] is returned. If
! 1433: ** no expression is found, -1 is returned.
! 1434: */
! 1435: static int findIndexCol(
! 1436: Parse *pParse, /* Parse context */
! 1437: ExprList *pList, /* Expression list to search */
! 1438: int iBase, /* Cursor for table associated with pIdx */
! 1439: Index *pIdx, /* Index to match column of */
! 1440: int iCol /* Column of index to match */
! 1441: ){
! 1442: int i;
! 1443: const char *zColl = pIdx->azColl[iCol];
! 1444:
! 1445: for(i=0; i<pList->nExpr; i++){
! 1446: Expr *p = pList->a[i].pExpr;
! 1447: if( p->op==TK_COLUMN
! 1448: && p->iColumn==pIdx->aiColumn[iCol]
! 1449: && p->iTable==iBase
! 1450: ){
! 1451: CollSeq *pColl = sqlite3ExprCollSeq(pParse, p);
! 1452: if( ALWAYS(pColl) && 0==sqlite3StrICmp(pColl->zName, zColl) ){
! 1453: return i;
! 1454: }
! 1455: }
! 1456: }
! 1457:
! 1458: return -1;
! 1459: }
! 1460:
! 1461: /*
! 1462: ** This routine determines if pIdx can be used to assist in processing a
! 1463: ** DISTINCT qualifier. In other words, it tests whether or not using this
! 1464: ** index for the outer loop guarantees that rows with equal values for
! 1465: ** all expressions in the pDistinct list are delivered grouped together.
! 1466: **
! 1467: ** For example, the query
! 1468: **
! 1469: ** SELECT DISTINCT a, b, c FROM tbl WHERE a = ?
! 1470: **
! 1471: ** can benefit from any index on columns "b" and "c".
! 1472: */
! 1473: static int isDistinctIndex(
! 1474: Parse *pParse, /* Parsing context */
! 1475: WhereClause *pWC, /* The WHERE clause */
! 1476: Index *pIdx, /* The index being considered */
! 1477: int base, /* Cursor number for the table pIdx is on */
! 1478: ExprList *pDistinct, /* The DISTINCT expressions */
! 1479: int nEqCol /* Number of index columns with == */
! 1480: ){
! 1481: Bitmask mask = 0; /* Mask of unaccounted for pDistinct exprs */
! 1482: int i; /* Iterator variable */
! 1483:
! 1484: if( pIdx->zName==0 || pDistinct==0 || pDistinct->nExpr>=BMS ) return 0;
! 1485: testcase( pDistinct->nExpr==BMS-1 );
! 1486:
! 1487: /* Loop through all the expressions in the distinct list. If any of them
! 1488: ** are not simple column references, return early. Otherwise, test if the
! 1489: ** WHERE clause contains a "col=X" clause. If it does, the expression
! 1490: ** can be ignored. If it does not, and the column does not belong to the
! 1491: ** same table as index pIdx, return early. Finally, if there is no
! 1492: ** matching "col=X" expression and the column is on the same table as pIdx,
! 1493: ** set the corresponding bit in variable mask.
! 1494: */
! 1495: for(i=0; i<pDistinct->nExpr; i++){
! 1496: WhereTerm *pTerm;
! 1497: Expr *p = pDistinct->a[i].pExpr;
! 1498: if( p->op!=TK_COLUMN ) return 0;
! 1499: pTerm = findTerm(pWC, p->iTable, p->iColumn, ~(Bitmask)0, WO_EQ, 0);
! 1500: if( pTerm ){
! 1501: Expr *pX = pTerm->pExpr;
! 1502: CollSeq *p1 = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
! 1503: CollSeq *p2 = sqlite3ExprCollSeq(pParse, p);
! 1504: if( p1==p2 ) continue;
! 1505: }
! 1506: if( p->iTable!=base ) return 0;
! 1507: mask |= (((Bitmask)1) << i);
! 1508: }
! 1509:
! 1510: for(i=nEqCol; mask && i<pIdx->nColumn; i++){
! 1511: int iExpr = findIndexCol(pParse, pDistinct, base, pIdx, i);
! 1512: if( iExpr<0 ) break;
! 1513: mask &= ~(((Bitmask)1) << iExpr);
! 1514: }
! 1515:
! 1516: return (mask==0);
! 1517: }
! 1518:
! 1519:
! 1520: /*
! 1521: ** Return true if the DISTINCT expression-list passed as the third argument
! 1522: ** is redundant. A DISTINCT list is redundant if the database contains a
! 1523: ** UNIQUE index that guarantees that the result of the query will be distinct
! 1524: ** anyway.
! 1525: */
! 1526: static int isDistinctRedundant(
! 1527: Parse *pParse,
! 1528: SrcList *pTabList,
! 1529: WhereClause *pWC,
! 1530: ExprList *pDistinct
! 1531: ){
! 1532: Table *pTab;
! 1533: Index *pIdx;
! 1534: int i;
! 1535: int iBase;
! 1536:
! 1537: /* If there is more than one table or sub-select in the FROM clause of
! 1538: ** this query, then it will not be possible to show that the DISTINCT
! 1539: ** clause is redundant. */
! 1540: if( pTabList->nSrc!=1 ) return 0;
! 1541: iBase = pTabList->a[0].iCursor;
! 1542: pTab = pTabList->a[0].pTab;
! 1543:
! 1544: /* If any of the expressions is an IPK column on table iBase, then return
! 1545: ** true. Note: The (p->iTable==iBase) part of this test may be false if the
! 1546: ** current SELECT is a correlated sub-query.
! 1547: */
! 1548: for(i=0; i<pDistinct->nExpr; i++){
! 1549: Expr *p = pDistinct->a[i].pExpr;
! 1550: if( p->op==TK_COLUMN && p->iTable==iBase && p->iColumn<0 ) return 1;
! 1551: }
! 1552:
! 1553: /* Loop through all indices on the table, checking each to see if it makes
! 1554: ** the DISTINCT qualifier redundant. It does so if:
! 1555: **
! 1556: ** 1. The index is itself UNIQUE, and
! 1557: **
! 1558: ** 2. All of the columns in the index are either part of the pDistinct
! 1559: ** list, or else the WHERE clause contains a term of the form "col=X",
! 1560: ** where X is a constant value. The collation sequences of the
! 1561: ** comparison and select-list expressions must match those of the index.
! 1562: */
! 1563: for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
! 1564: if( pIdx->onError==OE_None ) continue;
! 1565: for(i=0; i<pIdx->nColumn; i++){
! 1566: int iCol = pIdx->aiColumn[i];
! 1567: if( 0==findTerm(pWC, iBase, iCol, ~(Bitmask)0, WO_EQ, pIdx)
! 1568: && 0>findIndexCol(pParse, pDistinct, iBase, pIdx, i)
! 1569: ){
! 1570: break;
! 1571: }
! 1572: }
! 1573: if( i==pIdx->nColumn ){
! 1574: /* This index implies that the DISTINCT qualifier is redundant. */
! 1575: return 1;
! 1576: }
! 1577: }
! 1578:
! 1579: return 0;
! 1580: }
! 1581:
! 1582: /*
! 1583: ** This routine decides if pIdx can be used to satisfy the ORDER BY
! 1584: ** clause. If it can, it returns 1. If pIdx cannot satisfy the
! 1585: ** ORDER BY clause, this routine returns 0.
! 1586: **
! 1587: ** pOrderBy is an ORDER BY clause from a SELECT statement. pTab is the
! 1588: ** left-most table in the FROM clause of that same SELECT statement and
! 1589: ** the table has a cursor number of "base". pIdx is an index on pTab.
! 1590: **
! 1591: ** nEqCol is the number of columns of pIdx that are used as equality
! 1592: ** constraints. Any of these columns may be missing from the ORDER BY
! 1593: ** clause and the match can still be a success.
! 1594: **
! 1595: ** All terms of the ORDER BY that match against the index must be either
! 1596: ** ASC or DESC. (Terms of the ORDER BY clause past the end of a UNIQUE
! 1597: ** index do not need to satisfy this constraint.) The *pbRev value is
! 1598: ** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if
! 1599: ** the ORDER BY clause is all ASC.
! 1600: */
! 1601: static int isSortingIndex(
! 1602: Parse *pParse, /* Parsing context */
! 1603: WhereMaskSet *pMaskSet, /* Mapping from table cursor numbers to bitmaps */
! 1604: Index *pIdx, /* The index we are testing */
! 1605: int base, /* Cursor number for the table to be sorted */
! 1606: ExprList *pOrderBy, /* The ORDER BY clause */
! 1607: int nEqCol, /* Number of index columns with == constraints */
! 1608: int wsFlags, /* Index usages flags */
! 1609: int *pbRev /* Set to 1 if ORDER BY is DESC */
! 1610: ){
! 1611: int i, j; /* Loop counters */
! 1612: int sortOrder = 0; /* XOR of index and ORDER BY sort direction */
! 1613: int nTerm; /* Number of ORDER BY terms */
! 1614: struct ExprList_item *pTerm; /* A term of the ORDER BY clause */
! 1615: sqlite3 *db = pParse->db;
! 1616:
! 1617: if( !pOrderBy ) return 0;
! 1618: if( wsFlags & WHERE_COLUMN_IN ) return 0;
! 1619: if( pIdx->bUnordered ) return 0;
! 1620:
! 1621: nTerm = pOrderBy->nExpr;
! 1622: assert( nTerm>0 );
! 1623:
! 1624: /* Argument pIdx must either point to a 'real' named index structure,
! 1625: ** or an index structure allocated on the stack by bestBtreeIndex() to
! 1626: ** represent the rowid index that is part of every table. */
! 1627: assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
! 1628:
! 1629: /* Match terms of the ORDER BY clause against columns of
! 1630: ** the index.
! 1631: **
! 1632: ** Note that indices have pIdx->nColumn regular columns plus
! 1633: ** one additional column containing the rowid. The rowid column
! 1634: ** of the index is also allowed to match against the ORDER BY
! 1635: ** clause.
! 1636: */
! 1637: for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<=pIdx->nColumn; i++){
! 1638: Expr *pExpr; /* The expression of the ORDER BY pTerm */
! 1639: CollSeq *pColl; /* The collating sequence of pExpr */
! 1640: int termSortOrder; /* Sort order for this term */
! 1641: int iColumn; /* The i-th column of the index. -1 for rowid */
! 1642: int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */
! 1643: const char *zColl; /* Name of the collating sequence for i-th index term */
! 1644:
! 1645: pExpr = pTerm->pExpr;
! 1646: if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){
! 1647: /* Can not use an index sort on anything that is not a column in the
! 1648: ** left-most table of the FROM clause */
! 1649: break;
! 1650: }
! 1651: pColl = sqlite3ExprCollSeq(pParse, pExpr);
! 1652: if( !pColl ){
! 1653: pColl = db->pDfltColl;
! 1654: }
! 1655: if( pIdx->zName && i<pIdx->nColumn ){
! 1656: iColumn = pIdx->aiColumn[i];
! 1657: if( iColumn==pIdx->pTable->iPKey ){
! 1658: iColumn = -1;
! 1659: }
! 1660: iSortOrder = pIdx->aSortOrder[i];
! 1661: zColl = pIdx->azColl[i];
! 1662: }else{
! 1663: iColumn = -1;
! 1664: iSortOrder = 0;
! 1665: zColl = pColl->zName;
! 1666: }
! 1667: if( pExpr->iColumn!=iColumn || sqlite3StrICmp(pColl->zName, zColl) ){
! 1668: /* Term j of the ORDER BY clause does not match column i of the index */
! 1669: if( i<nEqCol ){
! 1670: /* If an index column that is constrained by == fails to match an
! 1671: ** ORDER BY term, that is OK. Just ignore that column of the index
! 1672: */
! 1673: continue;
! 1674: }else if( i==pIdx->nColumn ){
! 1675: /* Index column i is the rowid. All other terms match. */
! 1676: break;
! 1677: }else{
! 1678: /* If an index column fails to match and is not constrained by ==
! 1679: ** then the index cannot satisfy the ORDER BY constraint.
! 1680: */
! 1681: return 0;
! 1682: }
! 1683: }
! 1684: assert( pIdx->aSortOrder!=0 || iColumn==-1 );
! 1685: assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
! 1686: assert( iSortOrder==0 || iSortOrder==1 );
! 1687: termSortOrder = iSortOrder ^ pTerm->sortOrder;
! 1688: if( i>nEqCol ){
! 1689: if( termSortOrder!=sortOrder ){
! 1690: /* Indices can only be used if all ORDER BY terms past the
! 1691: ** equality constraints are all either DESC or ASC. */
! 1692: return 0;
! 1693: }
! 1694: }else{
! 1695: sortOrder = termSortOrder;
! 1696: }
! 1697: j++;
! 1698: pTerm++;
! 1699: if( iColumn<0 && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
! 1700: /* If the indexed column is the primary key and everything matches
! 1701: ** so far and none of the ORDER BY terms to the right reference other
! 1702: ** tables in the join, then we are assured that the index can be used
! 1703: ** to sort because the primary key is unique and so none of the other
! 1704: ** columns will make any difference
! 1705: */
! 1706: j = nTerm;
! 1707: }
! 1708: }
! 1709:
! 1710: *pbRev = sortOrder!=0;
! 1711: if( j>=nTerm ){
! 1712: /* All terms of the ORDER BY clause are covered by this index so
! 1713: ** this index can be used for sorting. */
! 1714: return 1;
! 1715: }
! 1716: if( pIdx->onError!=OE_None && i==pIdx->nColumn
! 1717: && (wsFlags & WHERE_COLUMN_NULL)==0
! 1718: && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
! 1719: /* All terms of this index match some prefix of the ORDER BY clause
! 1720: ** and the index is UNIQUE and no terms on the tail of the ORDER BY
! 1721: ** clause reference other tables in a join. If this is all true then
! 1722: ** the order by clause is superfluous. Not that if the matching
! 1723: ** condition is IS NULL then the result is not necessarily unique
! 1724: ** even on a UNIQUE index, so disallow those cases. */
! 1725: return 1;
! 1726: }
! 1727: return 0;
! 1728: }
! 1729:
! 1730: /*
! 1731: ** Prepare a crude estimate of the logarithm of the input value.
! 1732: ** The results need not be exact. This is only used for estimating
! 1733: ** the total cost of performing operations with O(logN) or O(NlogN)
! 1734: ** complexity. Because N is just a guess, it is no great tragedy if
! 1735: ** logN is a little off.
! 1736: */
! 1737: static double estLog(double N){
! 1738: double logN = 1;
! 1739: double x = 10;
! 1740: while( N>x ){
! 1741: logN += 1;
! 1742: x *= 10;
! 1743: }
! 1744: return logN;
! 1745: }
! 1746:
! 1747: /*
! 1748: ** Two routines for printing the content of an sqlite3_index_info
! 1749: ** structure. Used for testing and debugging only. If neither
! 1750: ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
! 1751: ** are no-ops.
! 1752: */
! 1753: #if !defined(SQLITE_OMIT_VIRTUALTABLE) && defined(SQLITE_DEBUG)
! 1754: static void TRACE_IDX_INPUTS(sqlite3_index_info *p){
! 1755: int i;
! 1756: if( !sqlite3WhereTrace ) return;
! 1757: for(i=0; i<p->nConstraint; i++){
! 1758: sqlite3DebugPrintf(" constraint[%d]: col=%d termid=%d op=%d usabled=%d\n",
! 1759: i,
! 1760: p->aConstraint[i].iColumn,
! 1761: p->aConstraint[i].iTermOffset,
! 1762: p->aConstraint[i].op,
! 1763: p->aConstraint[i].usable);
! 1764: }
! 1765: for(i=0; i<p->nOrderBy; i++){
! 1766: sqlite3DebugPrintf(" orderby[%d]: col=%d desc=%d\n",
! 1767: i,
! 1768: p->aOrderBy[i].iColumn,
! 1769: p->aOrderBy[i].desc);
! 1770: }
! 1771: }
! 1772: static void TRACE_IDX_OUTPUTS(sqlite3_index_info *p){
! 1773: int i;
! 1774: if( !sqlite3WhereTrace ) return;
! 1775: for(i=0; i<p->nConstraint; i++){
! 1776: sqlite3DebugPrintf(" usage[%d]: argvIdx=%d omit=%d\n",
! 1777: i,
! 1778: p->aConstraintUsage[i].argvIndex,
! 1779: p->aConstraintUsage[i].omit);
! 1780: }
! 1781: sqlite3DebugPrintf(" idxNum=%d\n", p->idxNum);
! 1782: sqlite3DebugPrintf(" idxStr=%s\n", p->idxStr);
! 1783: sqlite3DebugPrintf(" orderByConsumed=%d\n", p->orderByConsumed);
! 1784: sqlite3DebugPrintf(" estimatedCost=%g\n", p->estimatedCost);
! 1785: }
! 1786: #else
! 1787: #define TRACE_IDX_INPUTS(A)
! 1788: #define TRACE_IDX_OUTPUTS(A)
! 1789: #endif
! 1790:
! 1791: /*
! 1792: ** Required because bestIndex() is called by bestOrClauseIndex()
! 1793: */
! 1794: static void bestIndex(
! 1795: Parse*, WhereClause*, struct SrcList_item*,
! 1796: Bitmask, Bitmask, ExprList*, WhereCost*);
! 1797:
! 1798: /*
! 1799: ** This routine attempts to find an scanning strategy that can be used
! 1800: ** to optimize an 'OR' expression that is part of a WHERE clause.
! 1801: **
! 1802: ** The table associated with FROM clause term pSrc may be either a
! 1803: ** regular B-Tree table or a virtual table.
! 1804: */
! 1805: static void bestOrClauseIndex(
! 1806: Parse *pParse, /* The parsing context */
! 1807: WhereClause *pWC, /* The WHERE clause */
! 1808: struct SrcList_item *pSrc, /* The FROM clause term to search */
! 1809: Bitmask notReady, /* Mask of cursors not available for indexing */
! 1810: Bitmask notValid, /* Cursors not available for any purpose */
! 1811: ExprList *pOrderBy, /* The ORDER BY clause */
! 1812: WhereCost *pCost /* Lowest cost query plan */
! 1813: ){
! 1814: #ifndef SQLITE_OMIT_OR_OPTIMIZATION
! 1815: const int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
! 1816: const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur); /* Bitmask for pSrc */
! 1817: WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm]; /* End of pWC->a[] */
! 1818: WhereTerm *pTerm; /* A single term of the WHERE clause */
! 1819:
! 1820: /* The OR-clause optimization is disallowed if the INDEXED BY or
! 1821: ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
! 1822: if( pSrc->notIndexed || pSrc->pIndex!=0 ){
! 1823: return;
! 1824: }
! 1825: if( pWC->wctrlFlags & WHERE_AND_ONLY ){
! 1826: return;
! 1827: }
! 1828:
! 1829: /* Search the WHERE clause terms for a usable WO_OR term. */
! 1830: for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
! 1831: if( pTerm->eOperator==WO_OR
! 1832: && ((pTerm->prereqAll & ~maskSrc) & notReady)==0
! 1833: && (pTerm->u.pOrInfo->indexable & maskSrc)!=0
! 1834: ){
! 1835: WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
! 1836: WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
! 1837: WhereTerm *pOrTerm;
! 1838: int flags = WHERE_MULTI_OR;
! 1839: double rTotal = 0;
! 1840: double nRow = 0;
! 1841: Bitmask used = 0;
! 1842:
! 1843: for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
! 1844: WhereCost sTermCost;
! 1845: WHERETRACE(("... Multi-index OR testing for term %d of %d....\n",
! 1846: (pOrTerm - pOrWC->a), (pTerm - pWC->a)
! 1847: ));
! 1848: if( pOrTerm->eOperator==WO_AND ){
! 1849: WhereClause *pAndWC = &pOrTerm->u.pAndInfo->wc;
! 1850: bestIndex(pParse, pAndWC, pSrc, notReady, notValid, 0, &sTermCost);
! 1851: }else if( pOrTerm->leftCursor==iCur ){
! 1852: WhereClause tempWC;
! 1853: tempWC.pParse = pWC->pParse;
! 1854: tempWC.pMaskSet = pWC->pMaskSet;
! 1855: tempWC.pOuter = pWC;
! 1856: tempWC.op = TK_AND;
! 1857: tempWC.a = pOrTerm;
! 1858: tempWC.wctrlFlags = 0;
! 1859: tempWC.nTerm = 1;
! 1860: bestIndex(pParse, &tempWC, pSrc, notReady, notValid, 0, &sTermCost);
! 1861: }else{
! 1862: continue;
! 1863: }
! 1864: rTotal += sTermCost.rCost;
! 1865: nRow += sTermCost.plan.nRow;
! 1866: used |= sTermCost.used;
! 1867: if( rTotal>=pCost->rCost ) break;
! 1868: }
! 1869:
! 1870: /* If there is an ORDER BY clause, increase the scan cost to account
! 1871: ** for the cost of the sort. */
! 1872: if( pOrderBy!=0 ){
! 1873: WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
! 1874: rTotal, rTotal+nRow*estLog(nRow)));
! 1875: rTotal += nRow*estLog(nRow);
! 1876: }
! 1877:
! 1878: /* If the cost of scanning using this OR term for optimization is
! 1879: ** less than the current cost stored in pCost, replace the contents
! 1880: ** of pCost. */
! 1881: WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
! 1882: if( rTotal<pCost->rCost ){
! 1883: pCost->rCost = rTotal;
! 1884: pCost->used = used;
! 1885: pCost->plan.nRow = nRow;
! 1886: pCost->plan.wsFlags = flags;
! 1887: pCost->plan.u.pTerm = pTerm;
! 1888: }
! 1889: }
! 1890: }
! 1891: #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
! 1892: }
! 1893:
! 1894: #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
! 1895: /*
! 1896: ** Return TRUE if the WHERE clause term pTerm is of a form where it
! 1897: ** could be used with an index to access pSrc, assuming an appropriate
! 1898: ** index existed.
! 1899: */
! 1900: static int termCanDriveIndex(
! 1901: WhereTerm *pTerm, /* WHERE clause term to check */
! 1902: struct SrcList_item *pSrc, /* Table we are trying to access */
! 1903: Bitmask notReady /* Tables in outer loops of the join */
! 1904: ){
! 1905: char aff;
! 1906: if( pTerm->leftCursor!=pSrc->iCursor ) return 0;
! 1907: if( pTerm->eOperator!=WO_EQ ) return 0;
! 1908: if( (pTerm->prereqRight & notReady)!=0 ) return 0;
! 1909: aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
! 1910: if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
! 1911: return 1;
! 1912: }
! 1913: #endif
! 1914:
! 1915: #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
! 1916: /*
! 1917: ** If the query plan for pSrc specified in pCost is a full table scan
! 1918: ** and indexing is allows (if there is no NOT INDEXED clause) and it
! 1919: ** possible to construct a transient index that would perform better
! 1920: ** than a full table scan even when the cost of constructing the index
! 1921: ** is taken into account, then alter the query plan to use the
! 1922: ** transient index.
! 1923: */
! 1924: static void bestAutomaticIndex(
! 1925: Parse *pParse, /* The parsing context */
! 1926: WhereClause *pWC, /* The WHERE clause */
! 1927: struct SrcList_item *pSrc, /* The FROM clause term to search */
! 1928: Bitmask notReady, /* Mask of cursors that are not available */
! 1929: WhereCost *pCost /* Lowest cost query plan */
! 1930: ){
! 1931: double nTableRow; /* Rows in the input table */
! 1932: double logN; /* log(nTableRow) */
! 1933: double costTempIdx; /* per-query cost of the transient index */
! 1934: WhereTerm *pTerm; /* A single term of the WHERE clause */
! 1935: WhereTerm *pWCEnd; /* End of pWC->a[] */
! 1936: Table *pTable; /* Table tht might be indexed */
! 1937:
! 1938: if( pParse->nQueryLoop<=(double)1 ){
! 1939: /* There is no point in building an automatic index for a single scan */
! 1940: return;
! 1941: }
! 1942: if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
! 1943: /* Automatic indices are disabled at run-time */
! 1944: return;
! 1945: }
! 1946: if( (pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)!=0 ){
! 1947: /* We already have some kind of index in use for this query. */
! 1948: return;
! 1949: }
! 1950: if( pSrc->notIndexed ){
! 1951: /* The NOT INDEXED clause appears in the SQL. */
! 1952: return;
! 1953: }
! 1954: if( pSrc->isCorrelated ){
! 1955: /* The source is a correlated sub-query. No point in indexing it. */
! 1956: return;
! 1957: }
! 1958:
! 1959: assert( pParse->nQueryLoop >= (double)1 );
! 1960: pTable = pSrc->pTab;
! 1961: nTableRow = pTable->nRowEst;
! 1962: logN = estLog(nTableRow);
! 1963: costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
! 1964: if( costTempIdx>=pCost->rCost ){
! 1965: /* The cost of creating the transient table would be greater than
! 1966: ** doing the full table scan */
! 1967: return;
! 1968: }
! 1969:
! 1970: /* Search for any equality comparison term */
! 1971: pWCEnd = &pWC->a[pWC->nTerm];
! 1972: for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
! 1973: if( termCanDriveIndex(pTerm, pSrc, notReady) ){
! 1974: WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
! 1975: pCost->rCost, costTempIdx));
! 1976: pCost->rCost = costTempIdx;
! 1977: pCost->plan.nRow = logN + 1;
! 1978: pCost->plan.wsFlags = WHERE_TEMP_INDEX;
! 1979: pCost->used = pTerm->prereqRight;
! 1980: break;
! 1981: }
! 1982: }
! 1983: }
! 1984: #else
! 1985: # define bestAutomaticIndex(A,B,C,D,E) /* no-op */
! 1986: #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
! 1987:
! 1988:
! 1989: #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
! 1990: /*
! 1991: ** Generate code to construct the Index object for an automatic index
! 1992: ** and to set up the WhereLevel object pLevel so that the code generator
! 1993: ** makes use of the automatic index.
! 1994: */
! 1995: static void constructAutomaticIndex(
! 1996: Parse *pParse, /* The parsing context */
! 1997: WhereClause *pWC, /* The WHERE clause */
! 1998: struct SrcList_item *pSrc, /* The FROM clause term to get the next index */
! 1999: Bitmask notReady, /* Mask of cursors that are not available */
! 2000: WhereLevel *pLevel /* Write new index here */
! 2001: ){
! 2002: int nColumn; /* Number of columns in the constructed index */
! 2003: WhereTerm *pTerm; /* A single term of the WHERE clause */
! 2004: WhereTerm *pWCEnd; /* End of pWC->a[] */
! 2005: int nByte; /* Byte of memory needed for pIdx */
! 2006: Index *pIdx; /* Object describing the transient index */
! 2007: Vdbe *v; /* Prepared statement under construction */
! 2008: int addrInit; /* Address of the initialization bypass jump */
! 2009: Table *pTable; /* The table being indexed */
! 2010: KeyInfo *pKeyinfo; /* Key information for the index */
! 2011: int addrTop; /* Top of the index fill loop */
! 2012: int regRecord; /* Register holding an index record */
! 2013: int n; /* Column counter */
! 2014: int i; /* Loop counter */
! 2015: int mxBitCol; /* Maximum column in pSrc->colUsed */
! 2016: CollSeq *pColl; /* Collating sequence to on a column */
! 2017: Bitmask idxCols; /* Bitmap of columns used for indexing */
! 2018: Bitmask extraCols; /* Bitmap of additional columns */
! 2019:
! 2020: /* Generate code to skip over the creation and initialization of the
! 2021: ** transient index on 2nd and subsequent iterations of the loop. */
! 2022: v = pParse->pVdbe;
! 2023: assert( v!=0 );
! 2024: addrInit = sqlite3CodeOnce(pParse);
! 2025:
! 2026: /* Count the number of columns that will be added to the index
! 2027: ** and used to match WHERE clause constraints */
! 2028: nColumn = 0;
! 2029: pTable = pSrc->pTab;
! 2030: pWCEnd = &pWC->a[pWC->nTerm];
! 2031: idxCols = 0;
! 2032: for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
! 2033: if( termCanDriveIndex(pTerm, pSrc, notReady) ){
! 2034: int iCol = pTerm->u.leftColumn;
! 2035: Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
! 2036: testcase( iCol==BMS );
! 2037: testcase( iCol==BMS-1 );
! 2038: if( (idxCols & cMask)==0 ){
! 2039: nColumn++;
! 2040: idxCols |= cMask;
! 2041: }
! 2042: }
! 2043: }
! 2044: assert( nColumn>0 );
! 2045: pLevel->plan.nEq = nColumn;
! 2046:
! 2047: /* Count the number of additional columns needed to create a
! 2048: ** covering index. A "covering index" is an index that contains all
! 2049: ** columns that are needed by the query. With a covering index, the
! 2050: ** original table never needs to be accessed. Automatic indices must
! 2051: ** be a covering index because the index will not be updated if the
! 2052: ** original table changes and the index and table cannot both be used
! 2053: ** if they go out of sync.
! 2054: */
! 2055: extraCols = pSrc->colUsed & (~idxCols | (((Bitmask)1)<<(BMS-1)));
! 2056: mxBitCol = (pTable->nCol >= BMS-1) ? BMS-1 : pTable->nCol;
! 2057: testcase( pTable->nCol==BMS-1 );
! 2058: testcase( pTable->nCol==BMS-2 );
! 2059: for(i=0; i<mxBitCol; i++){
! 2060: if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
! 2061: }
! 2062: if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
! 2063: nColumn += pTable->nCol - BMS + 1;
! 2064: }
! 2065: pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WO_EQ;
! 2066:
! 2067: /* Construct the Index object to describe this index */
! 2068: nByte = sizeof(Index);
! 2069: nByte += nColumn*sizeof(int); /* Index.aiColumn */
! 2070: nByte += nColumn*sizeof(char*); /* Index.azColl */
! 2071: nByte += nColumn; /* Index.aSortOrder */
! 2072: pIdx = sqlite3DbMallocZero(pParse->db, nByte);
! 2073: if( pIdx==0 ) return;
! 2074: pLevel->plan.u.pIdx = pIdx;
! 2075: pIdx->azColl = (char**)&pIdx[1];
! 2076: pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
! 2077: pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
! 2078: pIdx->zName = "auto-index";
! 2079: pIdx->nColumn = nColumn;
! 2080: pIdx->pTable = pTable;
! 2081: n = 0;
! 2082: idxCols = 0;
! 2083: for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
! 2084: if( termCanDriveIndex(pTerm, pSrc, notReady) ){
! 2085: int iCol = pTerm->u.leftColumn;
! 2086: Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
! 2087: if( (idxCols & cMask)==0 ){
! 2088: Expr *pX = pTerm->pExpr;
! 2089: idxCols |= cMask;
! 2090: pIdx->aiColumn[n] = pTerm->u.leftColumn;
! 2091: pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
! 2092: pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY";
! 2093: n++;
! 2094: }
! 2095: }
! 2096: }
! 2097: assert( (u32)n==pLevel->plan.nEq );
! 2098:
! 2099: /* Add additional columns needed to make the automatic index into
! 2100: ** a covering index */
! 2101: for(i=0; i<mxBitCol; i++){
! 2102: if( extraCols & (((Bitmask)1)<<i) ){
! 2103: pIdx->aiColumn[n] = i;
! 2104: pIdx->azColl[n] = "BINARY";
! 2105: n++;
! 2106: }
! 2107: }
! 2108: if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
! 2109: for(i=BMS-1; i<pTable->nCol; i++){
! 2110: pIdx->aiColumn[n] = i;
! 2111: pIdx->azColl[n] = "BINARY";
! 2112: n++;
! 2113: }
! 2114: }
! 2115: assert( n==nColumn );
! 2116:
! 2117: /* Create the automatic index */
! 2118: pKeyinfo = sqlite3IndexKeyinfo(pParse, pIdx);
! 2119: assert( pLevel->iIdxCur>=0 );
! 2120: sqlite3VdbeAddOp4(v, OP_OpenAutoindex, pLevel->iIdxCur, nColumn+1, 0,
! 2121: (char*)pKeyinfo, P4_KEYINFO_HANDOFF);
! 2122: VdbeComment((v, "for %s", pTable->zName));
! 2123:
! 2124: /* Fill the automatic index with content */
! 2125: addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur);
! 2126: regRecord = sqlite3GetTempReg(pParse);
! 2127: sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 1);
! 2128: sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord);
! 2129: sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
! 2130: sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1);
! 2131: sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX);
! 2132: sqlite3VdbeJumpHere(v, addrTop);
! 2133: sqlite3ReleaseTempReg(pParse, regRecord);
! 2134:
! 2135: /* Jump here when skipping the initialization */
! 2136: sqlite3VdbeJumpHere(v, addrInit);
! 2137: }
! 2138: #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
! 2139:
! 2140: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 2141: /*
! 2142: ** Allocate and populate an sqlite3_index_info structure. It is the
! 2143: ** responsibility of the caller to eventually release the structure
! 2144: ** by passing the pointer returned by this function to sqlite3_free().
! 2145: */
! 2146: static sqlite3_index_info *allocateIndexInfo(
! 2147: Parse *pParse,
! 2148: WhereClause *pWC,
! 2149: struct SrcList_item *pSrc,
! 2150: ExprList *pOrderBy
! 2151: ){
! 2152: int i, j;
! 2153: int nTerm;
! 2154: struct sqlite3_index_constraint *pIdxCons;
! 2155: struct sqlite3_index_orderby *pIdxOrderBy;
! 2156: struct sqlite3_index_constraint_usage *pUsage;
! 2157: WhereTerm *pTerm;
! 2158: int nOrderBy;
! 2159: sqlite3_index_info *pIdxInfo;
! 2160:
! 2161: WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));
! 2162:
! 2163: /* Count the number of possible WHERE clause constraints referring
! 2164: ** to this virtual table */
! 2165: for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
! 2166: if( pTerm->leftCursor != pSrc->iCursor ) continue;
! 2167: assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
! 2168: testcase( pTerm->eOperator==WO_IN );
! 2169: testcase( pTerm->eOperator==WO_ISNULL );
! 2170: if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
! 2171: if( pTerm->wtFlags & TERM_VNULL ) continue;
! 2172: nTerm++;
! 2173: }
! 2174:
! 2175: /* If the ORDER BY clause contains only columns in the current
! 2176: ** virtual table then allocate space for the aOrderBy part of
! 2177: ** the sqlite3_index_info structure.
! 2178: */
! 2179: nOrderBy = 0;
! 2180: if( pOrderBy ){
! 2181: for(i=0; i<pOrderBy->nExpr; i++){
! 2182: Expr *pExpr = pOrderBy->a[i].pExpr;
! 2183: if( pExpr->op!=TK_COLUMN || pExpr->iTable!=pSrc->iCursor ) break;
! 2184: }
! 2185: if( i==pOrderBy->nExpr ){
! 2186: nOrderBy = pOrderBy->nExpr;
! 2187: }
! 2188: }
! 2189:
! 2190: /* Allocate the sqlite3_index_info structure
! 2191: */
! 2192: pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
! 2193: + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
! 2194: + sizeof(*pIdxOrderBy)*nOrderBy );
! 2195: if( pIdxInfo==0 ){
! 2196: sqlite3ErrorMsg(pParse, "out of memory");
! 2197: /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
! 2198: return 0;
! 2199: }
! 2200:
! 2201: /* Initialize the structure. The sqlite3_index_info structure contains
! 2202: ** many fields that are declared "const" to prevent xBestIndex from
! 2203: ** changing them. We have to do some funky casting in order to
! 2204: ** initialize those fields.
! 2205: */
! 2206: pIdxCons = (struct sqlite3_index_constraint*)&pIdxInfo[1];
! 2207: pIdxOrderBy = (struct sqlite3_index_orderby*)&pIdxCons[nTerm];
! 2208: pUsage = (struct sqlite3_index_constraint_usage*)&pIdxOrderBy[nOrderBy];
! 2209: *(int*)&pIdxInfo->nConstraint = nTerm;
! 2210: *(int*)&pIdxInfo->nOrderBy = nOrderBy;
! 2211: *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint = pIdxCons;
! 2212: *(struct sqlite3_index_orderby**)&pIdxInfo->aOrderBy = pIdxOrderBy;
! 2213: *(struct sqlite3_index_constraint_usage**)&pIdxInfo->aConstraintUsage =
! 2214: pUsage;
! 2215:
! 2216: for(i=j=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
! 2217: if( pTerm->leftCursor != pSrc->iCursor ) continue;
! 2218: assert( (pTerm->eOperator&(pTerm->eOperator-1))==0 );
! 2219: testcase( pTerm->eOperator==WO_IN );
! 2220: testcase( pTerm->eOperator==WO_ISNULL );
! 2221: if( pTerm->eOperator & (WO_IN|WO_ISNULL) ) continue;
! 2222: if( pTerm->wtFlags & TERM_VNULL ) continue;
! 2223: pIdxCons[j].iColumn = pTerm->u.leftColumn;
! 2224: pIdxCons[j].iTermOffset = i;
! 2225: pIdxCons[j].op = (u8)pTerm->eOperator;
! 2226: /* The direct assignment in the previous line is possible only because
! 2227: ** the WO_ and SQLITE_INDEX_CONSTRAINT_ codes are identical. The
! 2228: ** following asserts verify this fact. */
! 2229: assert( WO_EQ==SQLITE_INDEX_CONSTRAINT_EQ );
! 2230: assert( WO_LT==SQLITE_INDEX_CONSTRAINT_LT );
! 2231: assert( WO_LE==SQLITE_INDEX_CONSTRAINT_LE );
! 2232: assert( WO_GT==SQLITE_INDEX_CONSTRAINT_GT );
! 2233: assert( WO_GE==SQLITE_INDEX_CONSTRAINT_GE );
! 2234: assert( WO_MATCH==SQLITE_INDEX_CONSTRAINT_MATCH );
! 2235: assert( pTerm->eOperator & (WO_EQ|WO_LT|WO_LE|WO_GT|WO_GE|WO_MATCH) );
! 2236: j++;
! 2237: }
! 2238: for(i=0; i<nOrderBy; i++){
! 2239: Expr *pExpr = pOrderBy->a[i].pExpr;
! 2240: pIdxOrderBy[i].iColumn = pExpr->iColumn;
! 2241: pIdxOrderBy[i].desc = pOrderBy->a[i].sortOrder;
! 2242: }
! 2243:
! 2244: return pIdxInfo;
! 2245: }
! 2246:
! 2247: /*
! 2248: ** The table object reference passed as the second argument to this function
! 2249: ** must represent a virtual table. This function invokes the xBestIndex()
! 2250: ** method of the virtual table with the sqlite3_index_info pointer passed
! 2251: ** as the argument.
! 2252: **
! 2253: ** If an error occurs, pParse is populated with an error message and a
! 2254: ** non-zero value is returned. Otherwise, 0 is returned and the output
! 2255: ** part of the sqlite3_index_info structure is left populated.
! 2256: **
! 2257: ** Whether or not an error is returned, it is the responsibility of the
! 2258: ** caller to eventually free p->idxStr if p->needToFreeIdxStr indicates
! 2259: ** that this is required.
! 2260: */
! 2261: static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){
! 2262: sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab;
! 2263: int i;
! 2264: int rc;
! 2265:
! 2266: WHERETRACE(("xBestIndex for %s\n", pTab->zName));
! 2267: TRACE_IDX_INPUTS(p);
! 2268: rc = pVtab->pModule->xBestIndex(pVtab, p);
! 2269: TRACE_IDX_OUTPUTS(p);
! 2270:
! 2271: if( rc!=SQLITE_OK ){
! 2272: if( rc==SQLITE_NOMEM ){
! 2273: pParse->db->mallocFailed = 1;
! 2274: }else if( !pVtab->zErrMsg ){
! 2275: sqlite3ErrorMsg(pParse, "%s", sqlite3ErrStr(rc));
! 2276: }else{
! 2277: sqlite3ErrorMsg(pParse, "%s", pVtab->zErrMsg);
! 2278: }
! 2279: }
! 2280: sqlite3_free(pVtab->zErrMsg);
! 2281: pVtab->zErrMsg = 0;
! 2282:
! 2283: for(i=0; i<p->nConstraint; i++){
! 2284: if( !p->aConstraint[i].usable && p->aConstraintUsage[i].argvIndex>0 ){
! 2285: sqlite3ErrorMsg(pParse,
! 2286: "table %s: xBestIndex returned an invalid plan", pTab->zName);
! 2287: }
! 2288: }
! 2289:
! 2290: return pParse->nErr;
! 2291: }
! 2292:
! 2293:
! 2294: /*
! 2295: ** Compute the best index for a virtual table.
! 2296: **
! 2297: ** The best index is computed by the xBestIndex method of the virtual
! 2298: ** table module. This routine is really just a wrapper that sets up
! 2299: ** the sqlite3_index_info structure that is used to communicate with
! 2300: ** xBestIndex.
! 2301: **
! 2302: ** In a join, this routine might be called multiple times for the
! 2303: ** same virtual table. The sqlite3_index_info structure is created
! 2304: ** and initialized on the first invocation and reused on all subsequent
! 2305: ** invocations. The sqlite3_index_info structure is also used when
! 2306: ** code is generated to access the virtual table. The whereInfoDelete()
! 2307: ** routine takes care of freeing the sqlite3_index_info structure after
! 2308: ** everybody has finished with it.
! 2309: */
! 2310: static void bestVirtualIndex(
! 2311: Parse *pParse, /* The parsing context */
! 2312: WhereClause *pWC, /* The WHERE clause */
! 2313: struct SrcList_item *pSrc, /* The FROM clause term to search */
! 2314: Bitmask notReady, /* Mask of cursors not available for index */
! 2315: Bitmask notValid, /* Cursors not valid for any purpose */
! 2316: ExprList *pOrderBy, /* The order by clause */
! 2317: WhereCost *pCost, /* Lowest cost query plan */
! 2318: sqlite3_index_info **ppIdxInfo /* Index information passed to xBestIndex */
! 2319: ){
! 2320: Table *pTab = pSrc->pTab;
! 2321: sqlite3_index_info *pIdxInfo;
! 2322: struct sqlite3_index_constraint *pIdxCons;
! 2323: struct sqlite3_index_constraint_usage *pUsage;
! 2324: WhereTerm *pTerm;
! 2325: int i, j;
! 2326: int nOrderBy;
! 2327: double rCost;
! 2328:
! 2329: /* Make sure wsFlags is initialized to some sane value. Otherwise, if the
! 2330: ** malloc in allocateIndexInfo() fails and this function returns leaving
! 2331: ** wsFlags in an uninitialized state, the caller may behave unpredictably.
! 2332: */
! 2333: memset(pCost, 0, sizeof(*pCost));
! 2334: pCost->plan.wsFlags = WHERE_VIRTUALTABLE;
! 2335:
! 2336: /* If the sqlite3_index_info structure has not been previously
! 2337: ** allocated and initialized, then allocate and initialize it now.
! 2338: */
! 2339: pIdxInfo = *ppIdxInfo;
! 2340: if( pIdxInfo==0 ){
! 2341: *ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pOrderBy);
! 2342: }
! 2343: if( pIdxInfo==0 ){
! 2344: return;
! 2345: }
! 2346:
! 2347: /* At this point, the sqlite3_index_info structure that pIdxInfo points
! 2348: ** to will have been initialized, either during the current invocation or
! 2349: ** during some prior invocation. Now we just have to customize the
! 2350: ** details of pIdxInfo for the current invocation and pass it to
! 2351: ** xBestIndex.
! 2352: */
! 2353:
! 2354: /* The module name must be defined. Also, by this point there must
! 2355: ** be a pointer to an sqlite3_vtab structure. Otherwise
! 2356: ** sqlite3ViewGetColumnNames() would have picked up the error.
! 2357: */
! 2358: assert( pTab->azModuleArg && pTab->azModuleArg[0] );
! 2359: assert( sqlite3GetVTable(pParse->db, pTab) );
! 2360:
! 2361: /* Set the aConstraint[].usable fields and initialize all
! 2362: ** output variables to zero.
! 2363: **
! 2364: ** aConstraint[].usable is true for constraints where the right-hand
! 2365: ** side contains only references to tables to the left of the current
! 2366: ** table. In other words, if the constraint is of the form:
! 2367: **
! 2368: ** column = expr
! 2369: **
! 2370: ** and we are evaluating a join, then the constraint on column is
! 2371: ** only valid if all tables referenced in expr occur to the left
! 2372: ** of the table containing column.
! 2373: **
! 2374: ** The aConstraints[] array contains entries for all constraints
! 2375: ** on the current table. That way we only have to compute it once
! 2376: ** even though we might try to pick the best index multiple times.
! 2377: ** For each attempt at picking an index, the order of tables in the
! 2378: ** join might be different so we have to recompute the usable flag
! 2379: ** each time.
! 2380: */
! 2381: pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
! 2382: pUsage = pIdxInfo->aConstraintUsage;
! 2383: for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
! 2384: j = pIdxCons->iTermOffset;
! 2385: pTerm = &pWC->a[j];
! 2386: pIdxCons->usable = (pTerm->prereqRight¬Ready) ? 0 : 1;
! 2387: }
! 2388: memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
! 2389: if( pIdxInfo->needToFreeIdxStr ){
! 2390: sqlite3_free(pIdxInfo->idxStr);
! 2391: }
! 2392: pIdxInfo->idxStr = 0;
! 2393: pIdxInfo->idxNum = 0;
! 2394: pIdxInfo->needToFreeIdxStr = 0;
! 2395: pIdxInfo->orderByConsumed = 0;
! 2396: /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
! 2397: pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
! 2398: nOrderBy = pIdxInfo->nOrderBy;
! 2399: if( !pOrderBy ){
! 2400: pIdxInfo->nOrderBy = 0;
! 2401: }
! 2402:
! 2403: if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
! 2404: return;
! 2405: }
! 2406:
! 2407: pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
! 2408: for(i=0; i<pIdxInfo->nConstraint; i++){
! 2409: if( pUsage[i].argvIndex>0 ){
! 2410: pCost->used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
! 2411: }
! 2412: }
! 2413:
! 2414: /* If there is an ORDER BY clause, and the selected virtual table index
! 2415: ** does not satisfy it, increase the cost of the scan accordingly. This
! 2416: ** matches the processing for non-virtual tables in bestBtreeIndex().
! 2417: */
! 2418: rCost = pIdxInfo->estimatedCost;
! 2419: if( pOrderBy && pIdxInfo->orderByConsumed==0 ){
! 2420: rCost += estLog(rCost)*rCost;
! 2421: }
! 2422:
! 2423: /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
! 2424: ** inital value of lowestCost in this loop. If it is, then the
! 2425: ** (cost<lowestCost) test below will never be true.
! 2426: **
! 2427: ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT
! 2428: ** is defined.
! 2429: */
! 2430: if( (SQLITE_BIG_DBL/((double)2))<rCost ){
! 2431: pCost->rCost = (SQLITE_BIG_DBL/((double)2));
! 2432: }else{
! 2433: pCost->rCost = rCost;
! 2434: }
! 2435: pCost->plan.u.pVtabIdx = pIdxInfo;
! 2436: if( pIdxInfo->orderByConsumed ){
! 2437: pCost->plan.wsFlags |= WHERE_ORDERBY;
! 2438: }
! 2439: pCost->plan.nEq = 0;
! 2440: pIdxInfo->nOrderBy = nOrderBy;
! 2441:
! 2442: /* Try to find a more efficient access pattern by using multiple indexes
! 2443: ** to optimize an OR expression within the WHERE clause.
! 2444: */
! 2445: bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
! 2446: }
! 2447: #endif /* SQLITE_OMIT_VIRTUALTABLE */
! 2448:
! 2449: #ifdef SQLITE_ENABLE_STAT3
! 2450: /*
! 2451: ** Estimate the location of a particular key among all keys in an
! 2452: ** index. Store the results in aStat as follows:
! 2453: **
! 2454: ** aStat[0] Est. number of rows less than pVal
! 2455: ** aStat[1] Est. number of rows equal to pVal
! 2456: **
! 2457: ** Return SQLITE_OK on success.
! 2458: */
! 2459: static int whereKeyStats(
! 2460: Parse *pParse, /* Database connection */
! 2461: Index *pIdx, /* Index to consider domain of */
! 2462: sqlite3_value *pVal, /* Value to consider */
! 2463: int roundUp, /* Round up if true. Round down if false */
! 2464: tRowcnt *aStat /* OUT: stats written here */
! 2465: ){
! 2466: tRowcnt n;
! 2467: IndexSample *aSample;
! 2468: int i, eType;
! 2469: int isEq = 0;
! 2470: i64 v;
! 2471: double r, rS;
! 2472:
! 2473: assert( roundUp==0 || roundUp==1 );
! 2474: assert( pIdx->nSample>0 );
! 2475: if( pVal==0 ) return SQLITE_ERROR;
! 2476: n = pIdx->aiRowEst[0];
! 2477: aSample = pIdx->aSample;
! 2478: eType = sqlite3_value_type(pVal);
! 2479:
! 2480: if( eType==SQLITE_INTEGER ){
! 2481: v = sqlite3_value_int64(pVal);
! 2482: r = (i64)v;
! 2483: for(i=0; i<pIdx->nSample; i++){
! 2484: if( aSample[i].eType==SQLITE_NULL ) continue;
! 2485: if( aSample[i].eType>=SQLITE_TEXT ) break;
! 2486: if( aSample[i].eType==SQLITE_INTEGER ){
! 2487: if( aSample[i].u.i>=v ){
! 2488: isEq = aSample[i].u.i==v;
! 2489: break;
! 2490: }
! 2491: }else{
! 2492: assert( aSample[i].eType==SQLITE_FLOAT );
! 2493: if( aSample[i].u.r>=r ){
! 2494: isEq = aSample[i].u.r==r;
! 2495: break;
! 2496: }
! 2497: }
! 2498: }
! 2499: }else if( eType==SQLITE_FLOAT ){
! 2500: r = sqlite3_value_double(pVal);
! 2501: for(i=0; i<pIdx->nSample; i++){
! 2502: if( aSample[i].eType==SQLITE_NULL ) continue;
! 2503: if( aSample[i].eType>=SQLITE_TEXT ) break;
! 2504: if( aSample[i].eType==SQLITE_FLOAT ){
! 2505: rS = aSample[i].u.r;
! 2506: }else{
! 2507: rS = aSample[i].u.i;
! 2508: }
! 2509: if( rS>=r ){
! 2510: isEq = rS==r;
! 2511: break;
! 2512: }
! 2513: }
! 2514: }else if( eType==SQLITE_NULL ){
! 2515: i = 0;
! 2516: if( aSample[0].eType==SQLITE_NULL ) isEq = 1;
! 2517: }else{
! 2518: assert( eType==SQLITE_TEXT || eType==SQLITE_BLOB );
! 2519: for(i=0; i<pIdx->nSample; i++){
! 2520: if( aSample[i].eType==SQLITE_TEXT || aSample[i].eType==SQLITE_BLOB ){
! 2521: break;
! 2522: }
! 2523: }
! 2524: if( i<pIdx->nSample ){
! 2525: sqlite3 *db = pParse->db;
! 2526: CollSeq *pColl;
! 2527: const u8 *z;
! 2528: if( eType==SQLITE_BLOB ){
! 2529: z = (const u8 *)sqlite3_value_blob(pVal);
! 2530: pColl = db->pDfltColl;
! 2531: assert( pColl->enc==SQLITE_UTF8 );
! 2532: }else{
! 2533: pColl = sqlite3GetCollSeq(db, SQLITE_UTF8, 0, *pIdx->azColl);
! 2534: if( pColl==0 ){
! 2535: sqlite3ErrorMsg(pParse, "no such collation sequence: %s",
! 2536: *pIdx->azColl);
! 2537: return SQLITE_ERROR;
! 2538: }
! 2539: z = (const u8 *)sqlite3ValueText(pVal, pColl->enc);
! 2540: if( !z ){
! 2541: return SQLITE_NOMEM;
! 2542: }
! 2543: assert( z && pColl && pColl->xCmp );
! 2544: }
! 2545: n = sqlite3ValueBytes(pVal, pColl->enc);
! 2546:
! 2547: for(; i<pIdx->nSample; i++){
! 2548: int c;
! 2549: int eSampletype = aSample[i].eType;
! 2550: if( eSampletype<eType ) continue;
! 2551: if( eSampletype!=eType ) break;
! 2552: #ifndef SQLITE_OMIT_UTF16
! 2553: if( pColl->enc!=SQLITE_UTF8 ){
! 2554: int nSample;
! 2555: char *zSample = sqlite3Utf8to16(
! 2556: db, pColl->enc, aSample[i].u.z, aSample[i].nByte, &nSample
! 2557: );
! 2558: if( !zSample ){
! 2559: assert( db->mallocFailed );
! 2560: return SQLITE_NOMEM;
! 2561: }
! 2562: c = pColl->xCmp(pColl->pUser, nSample, zSample, n, z);
! 2563: sqlite3DbFree(db, zSample);
! 2564: }else
! 2565: #endif
! 2566: {
! 2567: c = pColl->xCmp(pColl->pUser, aSample[i].nByte, aSample[i].u.z, n, z);
! 2568: }
! 2569: if( c>=0 ){
! 2570: if( c==0 ) isEq = 1;
! 2571: break;
! 2572: }
! 2573: }
! 2574: }
! 2575: }
! 2576:
! 2577: /* At this point, aSample[i] is the first sample that is greater than
! 2578: ** or equal to pVal. Or if i==pIdx->nSample, then all samples are less
! 2579: ** than pVal. If aSample[i]==pVal, then isEq==1.
! 2580: */
! 2581: if( isEq ){
! 2582: assert( i<pIdx->nSample );
! 2583: aStat[0] = aSample[i].nLt;
! 2584: aStat[1] = aSample[i].nEq;
! 2585: }else{
! 2586: tRowcnt iLower, iUpper, iGap;
! 2587: if( i==0 ){
! 2588: iLower = 0;
! 2589: iUpper = aSample[0].nLt;
! 2590: }else{
! 2591: iUpper = i>=pIdx->nSample ? n : aSample[i].nLt;
! 2592: iLower = aSample[i-1].nEq + aSample[i-1].nLt;
! 2593: }
! 2594: aStat[1] = pIdx->avgEq;
! 2595: if( iLower>=iUpper ){
! 2596: iGap = 0;
! 2597: }else{
! 2598: iGap = iUpper - iLower;
! 2599: }
! 2600: if( roundUp ){
! 2601: iGap = (iGap*2)/3;
! 2602: }else{
! 2603: iGap = iGap/3;
! 2604: }
! 2605: aStat[0] = iLower + iGap;
! 2606: }
! 2607: return SQLITE_OK;
! 2608: }
! 2609: #endif /* SQLITE_ENABLE_STAT3 */
! 2610:
! 2611: /*
! 2612: ** If expression pExpr represents a literal value, set *pp to point to
! 2613: ** an sqlite3_value structure containing the same value, with affinity
! 2614: ** aff applied to it, before returning. It is the responsibility of the
! 2615: ** caller to eventually release this structure by passing it to
! 2616: ** sqlite3ValueFree().
! 2617: **
! 2618: ** If the current parse is a recompile (sqlite3Reprepare()) and pExpr
! 2619: ** is an SQL variable that currently has a non-NULL value bound to it,
! 2620: ** create an sqlite3_value structure containing this value, again with
! 2621: ** affinity aff applied to it, instead.
! 2622: **
! 2623: ** If neither of the above apply, set *pp to NULL.
! 2624: **
! 2625: ** If an error occurs, return an error code. Otherwise, SQLITE_OK.
! 2626: */
! 2627: #ifdef SQLITE_ENABLE_STAT3
! 2628: static int valueFromExpr(
! 2629: Parse *pParse,
! 2630: Expr *pExpr,
! 2631: u8 aff,
! 2632: sqlite3_value **pp
! 2633: ){
! 2634: if( pExpr->op==TK_VARIABLE
! 2635: || (pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE)
! 2636: ){
! 2637: int iVar = pExpr->iColumn;
! 2638: sqlite3VdbeSetVarmask(pParse->pVdbe, iVar);
! 2639: *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
! 2640: return SQLITE_OK;
! 2641: }
! 2642: return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
! 2643: }
! 2644: #endif
! 2645:
! 2646: /*
! 2647: ** This function is used to estimate the number of rows that will be visited
! 2648: ** by scanning an index for a range of values. The range may have an upper
! 2649: ** bound, a lower bound, or both. The WHERE clause terms that set the upper
! 2650: ** and lower bounds are represented by pLower and pUpper respectively. For
! 2651: ** example, assuming that index p is on t1(a):
! 2652: **
! 2653: ** ... FROM t1 WHERE a > ? AND a < ? ...
! 2654: ** |_____| |_____|
! 2655: ** | |
! 2656: ** pLower pUpper
! 2657: **
! 2658: ** If either of the upper or lower bound is not present, then NULL is passed in
! 2659: ** place of the corresponding WhereTerm.
! 2660: **
! 2661: ** The nEq parameter is passed the index of the index column subject to the
! 2662: ** range constraint. Or, equivalently, the number of equality constraints
! 2663: ** optimized by the proposed index scan. For example, assuming index p is
! 2664: ** on t1(a, b), and the SQL query is:
! 2665: **
! 2666: ** ... FROM t1 WHERE a = ? AND b > ? AND b < ? ...
! 2667: **
! 2668: ** then nEq should be passed the value 1 (as the range restricted column,
! 2669: ** b, is the second left-most column of the index). Or, if the query is:
! 2670: **
! 2671: ** ... FROM t1 WHERE a > ? AND a < ? ...
! 2672: **
! 2673: ** then nEq should be passed 0.
! 2674: **
! 2675: ** The returned value is an integer divisor to reduce the estimated
! 2676: ** search space. A return value of 1 means that range constraints are
! 2677: ** no help at all. A return value of 2 means range constraints are
! 2678: ** expected to reduce the search space by half. And so forth...
! 2679: **
! 2680: ** In the absence of sqlite_stat3 ANALYZE data, each range inequality
! 2681: ** reduces the search space by a factor of 4. Hence a single constraint (x>?)
! 2682: ** results in a return of 4 and a range constraint (x>? AND x<?) results
! 2683: ** in a return of 16.
! 2684: */
! 2685: static int whereRangeScanEst(
! 2686: Parse *pParse, /* Parsing & code generating context */
! 2687: Index *p, /* The index containing the range-compared column; "x" */
! 2688: int nEq, /* index into p->aCol[] of the range-compared column */
! 2689: WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */
! 2690: WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */
! 2691: double *pRangeDiv /* OUT: Reduce search space by this divisor */
! 2692: ){
! 2693: int rc = SQLITE_OK;
! 2694:
! 2695: #ifdef SQLITE_ENABLE_STAT3
! 2696:
! 2697: if( nEq==0 && p->nSample ){
! 2698: sqlite3_value *pRangeVal;
! 2699: tRowcnt iLower = 0;
! 2700: tRowcnt iUpper = p->aiRowEst[0];
! 2701: tRowcnt a[2];
! 2702: u8 aff = p->pTable->aCol[p->aiColumn[0]].affinity;
! 2703:
! 2704: if( pLower ){
! 2705: Expr *pExpr = pLower->pExpr->pRight;
! 2706: rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
! 2707: assert( pLower->eOperator==WO_GT || pLower->eOperator==WO_GE );
! 2708: if( rc==SQLITE_OK
! 2709: && whereKeyStats(pParse, p, pRangeVal, 0, a)==SQLITE_OK
! 2710: ){
! 2711: iLower = a[0];
! 2712: if( pLower->eOperator==WO_GT ) iLower += a[1];
! 2713: }
! 2714: sqlite3ValueFree(pRangeVal);
! 2715: }
! 2716: if( rc==SQLITE_OK && pUpper ){
! 2717: Expr *pExpr = pUpper->pExpr->pRight;
! 2718: rc = valueFromExpr(pParse, pExpr, aff, &pRangeVal);
! 2719: assert( pUpper->eOperator==WO_LT || pUpper->eOperator==WO_LE );
! 2720: if( rc==SQLITE_OK
! 2721: && whereKeyStats(pParse, p, pRangeVal, 1, a)==SQLITE_OK
! 2722: ){
! 2723: iUpper = a[0];
! 2724: if( pUpper->eOperator==WO_LE ) iUpper += a[1];
! 2725: }
! 2726: sqlite3ValueFree(pRangeVal);
! 2727: }
! 2728: if( rc==SQLITE_OK ){
! 2729: if( iUpper<=iLower ){
! 2730: *pRangeDiv = (double)p->aiRowEst[0];
! 2731: }else{
! 2732: *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
! 2733: }
! 2734: WHERETRACE(("range scan regions: %u..%u div=%g\n",
! 2735: (u32)iLower, (u32)iUpper, *pRangeDiv));
! 2736: return SQLITE_OK;
! 2737: }
! 2738: }
! 2739: #else
! 2740: UNUSED_PARAMETER(pParse);
! 2741: UNUSED_PARAMETER(p);
! 2742: UNUSED_PARAMETER(nEq);
! 2743: #endif
! 2744: assert( pLower || pUpper );
! 2745: *pRangeDiv = (double)1;
! 2746: if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= (double)4;
! 2747: if( pUpper ) *pRangeDiv *= (double)4;
! 2748: return rc;
! 2749: }
! 2750:
! 2751: #ifdef SQLITE_ENABLE_STAT3
! 2752: /*
! 2753: ** Estimate the number of rows that will be returned based on
! 2754: ** an equality constraint x=VALUE and where that VALUE occurs in
! 2755: ** the histogram data. This only works when x is the left-most
! 2756: ** column of an index and sqlite_stat3 histogram data is available
! 2757: ** for that index. When pExpr==NULL that means the constraint is
! 2758: ** "x IS NULL" instead of "x=VALUE".
! 2759: **
! 2760: ** Write the estimated row count into *pnRow and return SQLITE_OK.
! 2761: ** If unable to make an estimate, leave *pnRow unchanged and return
! 2762: ** non-zero.
! 2763: **
! 2764: ** This routine can fail if it is unable to load a collating sequence
! 2765: ** required for string comparison, or if unable to allocate memory
! 2766: ** for a UTF conversion required for comparison. The error is stored
! 2767: ** in the pParse structure.
! 2768: */
! 2769: static int whereEqualScanEst(
! 2770: Parse *pParse, /* Parsing & code generating context */
! 2771: Index *p, /* The index whose left-most column is pTerm */
! 2772: Expr *pExpr, /* Expression for VALUE in the x=VALUE constraint */
! 2773: double *pnRow /* Write the revised row estimate here */
! 2774: ){
! 2775: sqlite3_value *pRhs = 0; /* VALUE on right-hand side of pTerm */
! 2776: u8 aff; /* Column affinity */
! 2777: int rc; /* Subfunction return code */
! 2778: tRowcnt a[2]; /* Statistics */
! 2779:
! 2780: assert( p->aSample!=0 );
! 2781: assert( p->nSample>0 );
! 2782: aff = p->pTable->aCol[p->aiColumn[0]].affinity;
! 2783: if( pExpr ){
! 2784: rc = valueFromExpr(pParse, pExpr, aff, &pRhs);
! 2785: if( rc ) goto whereEqualScanEst_cancel;
! 2786: }else{
! 2787: pRhs = sqlite3ValueNew(pParse->db);
! 2788: }
! 2789: if( pRhs==0 ) return SQLITE_NOTFOUND;
! 2790: rc = whereKeyStats(pParse, p, pRhs, 0, a);
! 2791: if( rc==SQLITE_OK ){
! 2792: WHERETRACE(("equality scan regions: %d\n", (int)a[1]));
! 2793: *pnRow = a[1];
! 2794: }
! 2795: whereEqualScanEst_cancel:
! 2796: sqlite3ValueFree(pRhs);
! 2797: return rc;
! 2798: }
! 2799: #endif /* defined(SQLITE_ENABLE_STAT3) */
! 2800:
! 2801: #ifdef SQLITE_ENABLE_STAT3
! 2802: /*
! 2803: ** Estimate the number of rows that will be returned based on
! 2804: ** an IN constraint where the right-hand side of the IN operator
! 2805: ** is a list of values. Example:
! 2806: **
! 2807: ** WHERE x IN (1,2,3,4)
! 2808: **
! 2809: ** Write the estimated row count into *pnRow and return SQLITE_OK.
! 2810: ** If unable to make an estimate, leave *pnRow unchanged and return
! 2811: ** non-zero.
! 2812: **
! 2813: ** This routine can fail if it is unable to load a collating sequence
! 2814: ** required for string comparison, or if unable to allocate memory
! 2815: ** for a UTF conversion required for comparison. The error is stored
! 2816: ** in the pParse structure.
! 2817: */
! 2818: static int whereInScanEst(
! 2819: Parse *pParse, /* Parsing & code generating context */
! 2820: Index *p, /* The index whose left-most column is pTerm */
! 2821: ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
! 2822: double *pnRow /* Write the revised row estimate here */
! 2823: ){
! 2824: int rc = SQLITE_OK; /* Subfunction return code */
! 2825: double nEst; /* Number of rows for a single term */
! 2826: double nRowEst = (double)0; /* New estimate of the number of rows */
! 2827: int i; /* Loop counter */
! 2828:
! 2829: assert( p->aSample!=0 );
! 2830: for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
! 2831: nEst = p->aiRowEst[0];
! 2832: rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
! 2833: nRowEst += nEst;
! 2834: }
! 2835: if( rc==SQLITE_OK ){
! 2836: if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
! 2837: *pnRow = nRowEst;
! 2838: WHERETRACE(("IN row estimate: est=%g\n", nRowEst));
! 2839: }
! 2840: return rc;
! 2841: }
! 2842: #endif /* defined(SQLITE_ENABLE_STAT3) */
! 2843:
! 2844:
! 2845: /*
! 2846: ** Find the best query plan for accessing a particular table. Write the
! 2847: ** best query plan and its cost into the WhereCost object supplied as the
! 2848: ** last parameter.
! 2849: **
! 2850: ** The lowest cost plan wins. The cost is an estimate of the amount of
! 2851: ** CPU and disk I/O needed to process the requested result.
! 2852: ** Factors that influence cost include:
! 2853: **
! 2854: ** * The estimated number of rows that will be retrieved. (The
! 2855: ** fewer the better.)
! 2856: **
! 2857: ** * Whether or not sorting must occur.
! 2858: **
! 2859: ** * Whether or not there must be separate lookups in the
! 2860: ** index and in the main table.
! 2861: **
! 2862: ** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
! 2863: ** the SQL statement, then this function only considers plans using the
! 2864: ** named index. If no such plan is found, then the returned cost is
! 2865: ** SQLITE_BIG_DBL. If a plan is found that uses the named index,
! 2866: ** then the cost is calculated in the usual way.
! 2867: **
! 2868: ** If a NOT INDEXED clause (pSrc->notIndexed!=0) was attached to the table
! 2869: ** in the SELECT statement, then no indexes are considered. However, the
! 2870: ** selected plan may still take advantage of the built-in rowid primary key
! 2871: ** index.
! 2872: */
! 2873: static void bestBtreeIndex(
! 2874: Parse *pParse, /* The parsing context */
! 2875: WhereClause *pWC, /* The WHERE clause */
! 2876: struct SrcList_item *pSrc, /* The FROM clause term to search */
! 2877: Bitmask notReady, /* Mask of cursors not available for indexing */
! 2878: Bitmask notValid, /* Cursors not available for any purpose */
! 2879: ExprList *pOrderBy, /* The ORDER BY clause */
! 2880: ExprList *pDistinct, /* The select-list if query is DISTINCT */
! 2881: WhereCost *pCost /* Lowest cost query plan */
! 2882: ){
! 2883: int iCur = pSrc->iCursor; /* The cursor of the table to be accessed */
! 2884: Index *pProbe; /* An index we are evaluating */
! 2885: Index *pIdx; /* Copy of pProbe, or zero for IPK index */
! 2886: int eqTermMask; /* Current mask of valid equality operators */
! 2887: int idxEqTermMask; /* Index mask of valid equality operators */
! 2888: Index sPk; /* A fake index object for the primary key */
! 2889: tRowcnt aiRowEstPk[2]; /* The aiRowEst[] value for the sPk index */
! 2890: int aiColumnPk = -1; /* The aColumn[] value for the sPk index */
! 2891: int wsFlagMask; /* Allowed flags in pCost->plan.wsFlag */
! 2892:
! 2893: /* Initialize the cost to a worst-case value */
! 2894: memset(pCost, 0, sizeof(*pCost));
! 2895: pCost->rCost = SQLITE_BIG_DBL;
! 2896:
! 2897: /* If the pSrc table is the right table of a LEFT JOIN then we may not
! 2898: ** use an index to satisfy IS NULL constraints on that table. This is
! 2899: ** because columns might end up being NULL if the table does not match -
! 2900: ** a circumstance which the index cannot help us discover. Ticket #2177.
! 2901: */
! 2902: if( pSrc->jointype & JT_LEFT ){
! 2903: idxEqTermMask = WO_EQ|WO_IN;
! 2904: }else{
! 2905: idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
! 2906: }
! 2907:
! 2908: if( pSrc->pIndex ){
! 2909: /* An INDEXED BY clause specifies a particular index to use */
! 2910: pIdx = pProbe = pSrc->pIndex;
! 2911: wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
! 2912: eqTermMask = idxEqTermMask;
! 2913: }else{
! 2914: /* There is no INDEXED BY clause. Create a fake Index object in local
! 2915: ** variable sPk to represent the rowid primary key index. Make this
! 2916: ** fake index the first in a chain of Index objects with all of the real
! 2917: ** indices to follow */
! 2918: Index *pFirst; /* First of real indices on the table */
! 2919: memset(&sPk, 0, sizeof(Index));
! 2920: sPk.nColumn = 1;
! 2921: sPk.aiColumn = &aiColumnPk;
! 2922: sPk.aiRowEst = aiRowEstPk;
! 2923: sPk.onError = OE_Replace;
! 2924: sPk.pTable = pSrc->pTab;
! 2925: aiRowEstPk[0] = pSrc->pTab->nRowEst;
! 2926: aiRowEstPk[1] = 1;
! 2927: pFirst = pSrc->pTab->pIndex;
! 2928: if( pSrc->notIndexed==0 ){
! 2929: /* The real indices of the table are only considered if the
! 2930: ** NOT INDEXED qualifier is omitted from the FROM clause */
! 2931: sPk.pNext = pFirst;
! 2932: }
! 2933: pProbe = &sPk;
! 2934: wsFlagMask = ~(
! 2935: WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
! 2936: );
! 2937: eqTermMask = WO_EQ|WO_IN;
! 2938: pIdx = 0;
! 2939: }
! 2940:
! 2941: /* Loop over all indices looking for the best one to use
! 2942: */
! 2943: for(; pProbe; pIdx=pProbe=pProbe->pNext){
! 2944: const tRowcnt * const aiRowEst = pProbe->aiRowEst;
! 2945: double cost; /* Cost of using pProbe */
! 2946: double nRow; /* Estimated number of rows in result set */
! 2947: double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */
! 2948: int rev; /* True to scan in reverse order */
! 2949: int wsFlags = 0;
! 2950: Bitmask used = 0;
! 2951:
! 2952: /* The following variables are populated based on the properties of
! 2953: ** index being evaluated. They are then used to determine the expected
! 2954: ** cost and number of rows returned.
! 2955: **
! 2956: ** nEq:
! 2957: ** Number of equality terms that can be implemented using the index.
! 2958: ** In other words, the number of initial fields in the index that
! 2959: ** are used in == or IN or NOT NULL constraints of the WHERE clause.
! 2960: **
! 2961: ** nInMul:
! 2962: ** The "in-multiplier". This is an estimate of how many seek operations
! 2963: ** SQLite must perform on the index in question. For example, if the
! 2964: ** WHERE clause is:
! 2965: **
! 2966: ** WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
! 2967: **
! 2968: ** SQLite must perform 9 lookups on an index on (a, b), so nInMul is
! 2969: ** set to 9. Given the same schema and either of the following WHERE
! 2970: ** clauses:
! 2971: **
! 2972: ** WHERE a = 1
! 2973: ** WHERE a >= 2
! 2974: **
! 2975: ** nInMul is set to 1.
! 2976: **
! 2977: ** If there exists a WHERE term of the form "x IN (SELECT ...)", then
! 2978: ** the sub-select is assumed to return 25 rows for the purposes of
! 2979: ** determining nInMul.
! 2980: **
! 2981: ** bInEst:
! 2982: ** Set to true if there was at least one "x IN (SELECT ...)" term used
! 2983: ** in determining the value of nInMul. Note that the RHS of the
! 2984: ** IN operator must be a SELECT, not a value list, for this variable
! 2985: ** to be true.
! 2986: **
! 2987: ** rangeDiv:
! 2988: ** An estimate of a divisor by which to reduce the search space due
! 2989: ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE
! 2990: ** data, a single inequality reduces the search space to 1/4rd its
! 2991: ** original size (rangeDiv==4). Two inequalities reduce the search
! 2992: ** space to 1/16th of its original size (rangeDiv==16).
! 2993: **
! 2994: ** bSort:
! 2995: ** Boolean. True if there is an ORDER BY clause that will require an
! 2996: ** external sort (i.e. scanning the index being evaluated will not
! 2997: ** correctly order records).
! 2998: **
! 2999: ** bLookup:
! 3000: ** Boolean. True if a table lookup is required for each index entry
! 3001: ** visited. In other words, true if this is not a covering index.
! 3002: ** This is always false for the rowid primary key index of a table.
! 3003: ** For other indexes, it is true unless all the columns of the table
! 3004: ** used by the SELECT statement are present in the index (such an
! 3005: ** index is sometimes described as a covering index).
! 3006: ** For example, given the index on (a, b), the second of the following
! 3007: ** two queries requires table b-tree lookups in order to find the value
! 3008: ** of column c, but the first does not because columns a and b are
! 3009: ** both available in the index.
! 3010: **
! 3011: ** SELECT a, b FROM tbl WHERE a = 1;
! 3012: ** SELECT a, b, c FROM tbl WHERE a = 1;
! 3013: */
! 3014: int nEq; /* Number of == or IN terms matching index */
! 3015: int bInEst = 0; /* True if "x IN (SELECT...)" seen */
! 3016: int nInMul = 1; /* Number of distinct equalities to lookup */
! 3017: double rangeDiv = (double)1; /* Estimated reduction in search space */
! 3018: int nBound = 0; /* Number of range constraints seen */
! 3019: int bSort = !!pOrderBy; /* True if external sort required */
! 3020: int bDist = !!pDistinct; /* True if index cannot help with DISTINCT */
! 3021: int bLookup = 0; /* True if not a covering index */
! 3022: WhereTerm *pTerm; /* A single term of the WHERE clause */
! 3023: #ifdef SQLITE_ENABLE_STAT3
! 3024: WhereTerm *pFirstTerm = 0; /* First term matching the index */
! 3025: #endif
! 3026:
! 3027: /* Determine the values of nEq and nInMul */
! 3028: for(nEq=0; nEq<pProbe->nColumn; nEq++){
! 3029: int j = pProbe->aiColumn[nEq];
! 3030: pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
! 3031: if( pTerm==0 ) break;
! 3032: wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
! 3033: testcase( pTerm->pWC!=pWC );
! 3034: if( pTerm->eOperator & WO_IN ){
! 3035: Expr *pExpr = pTerm->pExpr;
! 3036: wsFlags |= WHERE_COLUMN_IN;
! 3037: if( ExprHasProperty(pExpr, EP_xIsSelect) ){
! 3038: /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */
! 3039: nInMul *= 25;
! 3040: bInEst = 1;
! 3041: }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
! 3042: /* "x IN (value, value, ...)" */
! 3043: nInMul *= pExpr->x.pList->nExpr;
! 3044: }
! 3045: }else if( pTerm->eOperator & WO_ISNULL ){
! 3046: wsFlags |= WHERE_COLUMN_NULL;
! 3047: }
! 3048: #ifdef SQLITE_ENABLE_STAT3
! 3049: if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
! 3050: #endif
! 3051: used |= pTerm->prereqRight;
! 3052: }
! 3053:
! 3054: /* If the index being considered is UNIQUE, and there is an equality
! 3055: ** constraint for all columns in the index, then this search will find
! 3056: ** at most a single row. In this case set the WHERE_UNIQUE flag to
! 3057: ** indicate this to the caller.
! 3058: **
! 3059: ** Otherwise, if the search may find more than one row, test to see if
! 3060: ** there is a range constraint on indexed column (nEq+1) that can be
! 3061: ** optimized using the index.
! 3062: */
! 3063: if( nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
! 3064: testcase( wsFlags & WHERE_COLUMN_IN );
! 3065: testcase( wsFlags & WHERE_COLUMN_NULL );
! 3066: if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
! 3067: wsFlags |= WHERE_UNIQUE;
! 3068: }
! 3069: }else if( pProbe->bUnordered==0 ){
! 3070: int j = (nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[nEq]);
! 3071: if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
! 3072: WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
! 3073: WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
! 3074: whereRangeScanEst(pParse, pProbe, nEq, pBtm, pTop, &rangeDiv);
! 3075: if( pTop ){
! 3076: nBound = 1;
! 3077: wsFlags |= WHERE_TOP_LIMIT;
! 3078: used |= pTop->prereqRight;
! 3079: testcase( pTop->pWC!=pWC );
! 3080: }
! 3081: if( pBtm ){
! 3082: nBound++;
! 3083: wsFlags |= WHERE_BTM_LIMIT;
! 3084: used |= pBtm->prereqRight;
! 3085: testcase( pBtm->pWC!=pWC );
! 3086: }
! 3087: wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
! 3088: }
! 3089: }
! 3090:
! 3091: /* If there is an ORDER BY clause and the index being considered will
! 3092: ** naturally scan rows in the required order, set the appropriate flags
! 3093: ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
! 3094: ** will scan rows in a different order, set the bSort variable. */
! 3095: if( isSortingIndex(
! 3096: pParse, pWC->pMaskSet, pProbe, iCur, pOrderBy, nEq, wsFlags, &rev)
! 3097: ){
! 3098: bSort = 0;
! 3099: wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
! 3100: wsFlags |= (rev ? WHERE_REVERSE : 0);
! 3101: }
! 3102:
! 3103: /* If there is a DISTINCT qualifier and this index will scan rows in
! 3104: ** order of the DISTINCT expressions, clear bDist and set the appropriate
! 3105: ** flags in wsFlags. */
! 3106: if( isDistinctIndex(pParse, pWC, pProbe, iCur, pDistinct, nEq) ){
! 3107: bDist = 0;
! 3108: wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT;
! 3109: }
! 3110:
! 3111: /* If currently calculating the cost of using an index (not the IPK
! 3112: ** index), determine if all required column data may be obtained without
! 3113: ** using the main table (i.e. if the index is a covering
! 3114: ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
! 3115: ** wsFlags. Otherwise, set the bLookup variable to true. */
! 3116: if( pIdx && wsFlags ){
! 3117: Bitmask m = pSrc->colUsed;
! 3118: int j;
! 3119: for(j=0; j<pIdx->nColumn; j++){
! 3120: int x = pIdx->aiColumn[j];
! 3121: if( x<BMS-1 ){
! 3122: m &= ~(((Bitmask)1)<<x);
! 3123: }
! 3124: }
! 3125: if( m==0 ){
! 3126: wsFlags |= WHERE_IDX_ONLY;
! 3127: }else{
! 3128: bLookup = 1;
! 3129: }
! 3130: }
! 3131:
! 3132: /*
! 3133: ** Estimate the number of rows of output. For an "x IN (SELECT...)"
! 3134: ** constraint, do not let the estimate exceed half the rows in the table.
! 3135: */
! 3136: nRow = (double)(aiRowEst[nEq] * nInMul);
! 3137: if( bInEst && nRow*2>aiRowEst[0] ){
! 3138: nRow = aiRowEst[0]/2;
! 3139: nInMul = (int)(nRow / aiRowEst[nEq]);
! 3140: }
! 3141:
! 3142: #ifdef SQLITE_ENABLE_STAT3
! 3143: /* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
! 3144: ** and we do not think that values of x are unique and if histogram
! 3145: ** data is available for column x, then it might be possible
! 3146: ** to get a better estimate on the number of rows based on
! 3147: ** VALUE and how common that value is according to the histogram.
! 3148: */
! 3149: if( nRow>(double)1 && nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){
! 3150: assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
! 3151: if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
! 3152: testcase( pFirstTerm->eOperator==WO_EQ );
! 3153: testcase( pFirstTerm->eOperator==WO_ISNULL );
! 3154: whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &nRow);
! 3155: }else if( bInEst==0 ){
! 3156: assert( pFirstTerm->eOperator==WO_IN );
! 3157: whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &nRow);
! 3158: }
! 3159: }
! 3160: #endif /* SQLITE_ENABLE_STAT3 */
! 3161:
! 3162: /* Adjust the number of output rows and downward to reflect rows
! 3163: ** that are excluded by range constraints.
! 3164: */
! 3165: nRow = nRow/rangeDiv;
! 3166: if( nRow<1 ) nRow = 1;
! 3167:
! 3168: /* Experiments run on real SQLite databases show that the time needed
! 3169: ** to do a binary search to locate a row in a table or index is roughly
! 3170: ** log10(N) times the time to move from one row to the next row within
! 3171: ** a table or index. The actual times can vary, with the size of
! 3172: ** records being an important factor. Both moves and searches are
! 3173: ** slower with larger records, presumably because fewer records fit
! 3174: ** on one page and hence more pages have to be fetched.
! 3175: **
! 3176: ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do
! 3177: ** not give us data on the relative sizes of table and index records.
! 3178: ** So this computation assumes table records are about twice as big
! 3179: ** as index records
! 3180: */
! 3181: if( (wsFlags & WHERE_NOT_FULLSCAN)==0 ){
! 3182: /* The cost of a full table scan is a number of move operations equal
! 3183: ** to the number of rows in the table.
! 3184: **
! 3185: ** We add an additional 4x penalty to full table scans. This causes
! 3186: ** the cost function to err on the side of choosing an index over
! 3187: ** choosing a full scan. This 4x full-scan penalty is an arguable
! 3188: ** decision and one which we expect to revisit in the future. But
! 3189: ** it seems to be working well enough at the moment.
! 3190: */
! 3191: cost = aiRowEst[0]*4;
! 3192: }else{
! 3193: log10N = estLog(aiRowEst[0]);
! 3194: cost = nRow;
! 3195: if( pIdx ){
! 3196: if( bLookup ){
! 3197: /* For an index lookup followed by a table lookup:
! 3198: ** nInMul index searches to find the start of each index range
! 3199: ** + nRow steps through the index
! 3200: ** + nRow table searches to lookup the table entry using the rowid
! 3201: */
! 3202: cost += (nInMul + nRow)*log10N;
! 3203: }else{
! 3204: /* For a covering index:
! 3205: ** nInMul index searches to find the initial entry
! 3206: ** + nRow steps through the index
! 3207: */
! 3208: cost += nInMul*log10N;
! 3209: }
! 3210: }else{
! 3211: /* For a rowid primary key lookup:
! 3212: ** nInMult table searches to find the initial entry for each range
! 3213: ** + nRow steps through the table
! 3214: */
! 3215: cost += nInMul*log10N;
! 3216: }
! 3217: }
! 3218:
! 3219: /* Add in the estimated cost of sorting the result. Actual experimental
! 3220: ** measurements of sorting performance in SQLite show that sorting time
! 3221: ** adds C*N*log10(N) to the cost, where N is the number of rows to be
! 3222: ** sorted and C is a factor between 1.95 and 4.3. We will split the
! 3223: ** difference and select C of 3.0.
! 3224: */
! 3225: if( bSort ){
! 3226: cost += nRow*estLog(nRow)*3;
! 3227: }
! 3228: if( bDist ){
! 3229: cost += nRow*estLog(nRow)*3;
! 3230: }
! 3231:
! 3232: /**** Cost of using this index has now been computed ****/
! 3233:
! 3234: /* If there are additional constraints on this table that cannot
! 3235: ** be used with the current index, but which might lower the number
! 3236: ** of output rows, adjust the nRow value accordingly. This only
! 3237: ** matters if the current index is the least costly, so do not bother
! 3238: ** with this step if we already know this index will not be chosen.
! 3239: ** Also, never reduce the output row count below 2 using this step.
! 3240: **
! 3241: ** It is critical that the notValid mask be used here instead of
! 3242: ** the notReady mask. When computing an "optimal" index, the notReady
! 3243: ** mask will only have one bit set - the bit for the current table.
! 3244: ** The notValid mask, on the other hand, always has all bits set for
! 3245: ** tables that are not in outer loops. If notReady is used here instead
! 3246: ** of notValid, then a optimal index that depends on inner joins loops
! 3247: ** might be selected even when there exists an optimal index that has
! 3248: ** no such dependency.
! 3249: */
! 3250: if( nRow>2 && cost<=pCost->rCost ){
! 3251: int k; /* Loop counter */
! 3252: int nSkipEq = nEq; /* Number of == constraints to skip */
! 3253: int nSkipRange = nBound; /* Number of < constraints to skip */
! 3254: Bitmask thisTab; /* Bitmap for pSrc */
! 3255:
! 3256: thisTab = getMask(pWC->pMaskSet, iCur);
! 3257: for(pTerm=pWC->a, k=pWC->nTerm; nRow>2 && k; k--, pTerm++){
! 3258: if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
! 3259: if( (pTerm->prereqAll & notValid)!=thisTab ) continue;
! 3260: if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
! 3261: if( nSkipEq ){
! 3262: /* Ignore the first nEq equality matches since the index
! 3263: ** has already accounted for these */
! 3264: nSkipEq--;
! 3265: }else{
! 3266: /* Assume each additional equality match reduces the result
! 3267: ** set size by a factor of 10 */
! 3268: nRow /= 10;
! 3269: }
! 3270: }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
! 3271: if( nSkipRange ){
! 3272: /* Ignore the first nSkipRange range constraints since the index
! 3273: ** has already accounted for these */
! 3274: nSkipRange--;
! 3275: }else{
! 3276: /* Assume each additional range constraint reduces the result
! 3277: ** set size by a factor of 3. Indexed range constraints reduce
! 3278: ** the search space by a larger factor: 4. We make indexed range
! 3279: ** more selective intentionally because of the subjective
! 3280: ** observation that indexed range constraints really are more
! 3281: ** selective in practice, on average. */
! 3282: nRow /= 3;
! 3283: }
! 3284: }else if( pTerm->eOperator!=WO_NOOP ){
! 3285: /* Any other expression lowers the output row count by half */
! 3286: nRow /= 2;
! 3287: }
! 3288: }
! 3289: if( nRow<2 ) nRow = 2;
! 3290: }
! 3291:
! 3292:
! 3293: WHERETRACE((
! 3294: "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n"
! 3295: " notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n",
! 3296: pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"),
! 3297: nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags,
! 3298: notReady, log10N, nRow, cost, used
! 3299: ));
! 3300:
! 3301: /* If this index is the best we have seen so far, then record this
! 3302: ** index and its cost in the pCost structure.
! 3303: */
! 3304: if( (!pIdx || wsFlags)
! 3305: && (cost<pCost->rCost || (cost<=pCost->rCost && nRow<pCost->plan.nRow))
! 3306: ){
! 3307: pCost->rCost = cost;
! 3308: pCost->used = used;
! 3309: pCost->plan.nRow = nRow;
! 3310: pCost->plan.wsFlags = (wsFlags&wsFlagMask);
! 3311: pCost->plan.nEq = nEq;
! 3312: pCost->plan.u.pIdx = pIdx;
! 3313: }
! 3314:
! 3315: /* If there was an INDEXED BY clause, then only that one index is
! 3316: ** considered. */
! 3317: if( pSrc->pIndex ) break;
! 3318:
! 3319: /* Reset masks for the next index in the loop */
! 3320: wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
! 3321: eqTermMask = idxEqTermMask;
! 3322: }
! 3323:
! 3324: /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
! 3325: ** is set, then reverse the order that the index will be scanned
! 3326: ** in. This is used for application testing, to help find cases
! 3327: ** where application behaviour depends on the (undefined) order that
! 3328: ** SQLite outputs rows in in the absence of an ORDER BY clause. */
! 3329: if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
! 3330: pCost->plan.wsFlags |= WHERE_REVERSE;
! 3331: }
! 3332:
! 3333: assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
! 3334: assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
! 3335: assert( pSrc->pIndex==0
! 3336: || pCost->plan.u.pIdx==0
! 3337: || pCost->plan.u.pIdx==pSrc->pIndex
! 3338: );
! 3339:
! 3340: WHERETRACE(("best index is: %s\n",
! 3341: ((pCost->plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ? "none" :
! 3342: pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
! 3343: ));
! 3344:
! 3345: bestOrClauseIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost);
! 3346: bestAutomaticIndex(pParse, pWC, pSrc, notReady, pCost);
! 3347: pCost->plan.wsFlags |= eqTermMask;
! 3348: }
! 3349:
! 3350: /*
! 3351: ** Find the query plan for accessing table pSrc->pTab. Write the
! 3352: ** best query plan and its cost into the WhereCost object supplied
! 3353: ** as the last parameter. This function may calculate the cost of
! 3354: ** both real and virtual table scans.
! 3355: */
! 3356: static void bestIndex(
! 3357: Parse *pParse, /* The parsing context */
! 3358: WhereClause *pWC, /* The WHERE clause */
! 3359: struct SrcList_item *pSrc, /* The FROM clause term to search */
! 3360: Bitmask notReady, /* Mask of cursors not available for indexing */
! 3361: Bitmask notValid, /* Cursors not available for any purpose */
! 3362: ExprList *pOrderBy, /* The ORDER BY clause */
! 3363: WhereCost *pCost /* Lowest cost query plan */
! 3364: ){
! 3365: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 3366: if( IsVirtual(pSrc->pTab) ){
! 3367: sqlite3_index_info *p = 0;
! 3368: bestVirtualIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, pCost,&p);
! 3369: if( p->needToFreeIdxStr ){
! 3370: sqlite3_free(p->idxStr);
! 3371: }
! 3372: sqlite3DbFree(pParse->db, p);
! 3373: }else
! 3374: #endif
! 3375: {
! 3376: bestBtreeIndex(pParse, pWC, pSrc, notReady, notValid, pOrderBy, 0, pCost);
! 3377: }
! 3378: }
! 3379:
! 3380: /*
! 3381: ** Disable a term in the WHERE clause. Except, do not disable the term
! 3382: ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
! 3383: ** or USING clause of that join.
! 3384: **
! 3385: ** Consider the term t2.z='ok' in the following queries:
! 3386: **
! 3387: ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
! 3388: ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
! 3389: ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
! 3390: **
! 3391: ** The t2.z='ok' is disabled in the in (2) because it originates
! 3392: ** in the ON clause. The term is disabled in (3) because it is not part
! 3393: ** of a LEFT OUTER JOIN. In (1), the term is not disabled.
! 3394: **
! 3395: ** IMPLEMENTATION-OF: R-24597-58655 No tests are done for terms that are
! 3396: ** completely satisfied by indices.
! 3397: **
! 3398: ** Disabling a term causes that term to not be tested in the inner loop
! 3399: ** of the join. Disabling is an optimization. When terms are satisfied
! 3400: ** by indices, we disable them to prevent redundant tests in the inner
! 3401: ** loop. We would get the correct results if nothing were ever disabled,
! 3402: ** but joins might run a little slower. The trick is to disable as much
! 3403: ** as we can without disabling too much. If we disabled in (1), we'd get
! 3404: ** the wrong answer. See ticket #813.
! 3405: */
! 3406: static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
! 3407: if( pTerm
! 3408: && (pTerm->wtFlags & TERM_CODED)==0
! 3409: && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))
! 3410: ){
! 3411: pTerm->wtFlags |= TERM_CODED;
! 3412: if( pTerm->iParent>=0 ){
! 3413: WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];
! 3414: if( (--pOther->nChild)==0 ){
! 3415: disableTerm(pLevel, pOther);
! 3416: }
! 3417: }
! 3418: }
! 3419: }
! 3420:
! 3421: /*
! 3422: ** Code an OP_Affinity opcode to apply the column affinity string zAff
! 3423: ** to the n registers starting at base.
! 3424: **
! 3425: ** As an optimization, SQLITE_AFF_NONE entries (which are no-ops) at the
! 3426: ** beginning and end of zAff are ignored. If all entries in zAff are
! 3427: ** SQLITE_AFF_NONE, then no code gets generated.
! 3428: **
! 3429: ** This routine makes its own copy of zAff so that the caller is free
! 3430: ** to modify zAff after this routine returns.
! 3431: */
! 3432: static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
! 3433: Vdbe *v = pParse->pVdbe;
! 3434: if( zAff==0 ){
! 3435: assert( pParse->db->mallocFailed );
! 3436: return;
! 3437: }
! 3438: assert( v!=0 );
! 3439:
! 3440: /* Adjust base and n to skip over SQLITE_AFF_NONE entries at the beginning
! 3441: ** and end of the affinity string.
! 3442: */
! 3443: while( n>0 && zAff[0]==SQLITE_AFF_NONE ){
! 3444: n--;
! 3445: base++;
! 3446: zAff++;
! 3447: }
! 3448: while( n>1 && zAff[n-1]==SQLITE_AFF_NONE ){
! 3449: n--;
! 3450: }
! 3451:
! 3452: /* Code the OP_Affinity opcode if there is anything left to do. */
! 3453: if( n>0 ){
! 3454: sqlite3VdbeAddOp2(v, OP_Affinity, base, n);
! 3455: sqlite3VdbeChangeP4(v, -1, zAff, n);
! 3456: sqlite3ExprCacheAffinityChange(pParse, base, n);
! 3457: }
! 3458: }
! 3459:
! 3460:
! 3461: /*
! 3462: ** Generate code for a single equality term of the WHERE clause. An equality
! 3463: ** term can be either X=expr or X IN (...). pTerm is the term to be
! 3464: ** coded.
! 3465: **
! 3466: ** The current value for the constraint is left in register iReg.
! 3467: **
! 3468: ** For a constraint of the form X=expr, the expression is evaluated and its
! 3469: ** result is left on the stack. For constraints of the form X IN (...)
! 3470: ** this routine sets up a loop that will iterate over all values of X.
! 3471: */
! 3472: static int codeEqualityTerm(
! 3473: Parse *pParse, /* The parsing context */
! 3474: WhereTerm *pTerm, /* The term of the WHERE clause to be coded */
! 3475: WhereLevel *pLevel, /* When level of the FROM clause we are working on */
! 3476: int iTarget /* Attempt to leave results in this register */
! 3477: ){
! 3478: Expr *pX = pTerm->pExpr;
! 3479: Vdbe *v = pParse->pVdbe;
! 3480: int iReg; /* Register holding results */
! 3481:
! 3482: assert( iTarget>0 );
! 3483: if( pX->op==TK_EQ ){
! 3484: iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
! 3485: }else if( pX->op==TK_ISNULL ){
! 3486: iReg = iTarget;
! 3487: sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
! 3488: #ifndef SQLITE_OMIT_SUBQUERY
! 3489: }else{
! 3490: int eType;
! 3491: int iTab;
! 3492: struct InLoop *pIn;
! 3493:
! 3494: assert( pX->op==TK_IN );
! 3495: iReg = iTarget;
! 3496: eType = sqlite3FindInIndex(pParse, pX, 0);
! 3497: iTab = pX->iTable;
! 3498: sqlite3VdbeAddOp2(v, OP_Rewind, iTab, 0);
! 3499: assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
! 3500: if( pLevel->u.in.nIn==0 ){
! 3501: pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
! 3502: }
! 3503: pLevel->u.in.nIn++;
! 3504: pLevel->u.in.aInLoop =
! 3505: sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
! 3506: sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
! 3507: pIn = pLevel->u.in.aInLoop;
! 3508: if( pIn ){
! 3509: pIn += pLevel->u.in.nIn - 1;
! 3510: pIn->iCur = iTab;
! 3511: if( eType==IN_INDEX_ROWID ){
! 3512: pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg);
! 3513: }else{
! 3514: pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg);
! 3515: }
! 3516: sqlite3VdbeAddOp1(v, OP_IsNull, iReg);
! 3517: }else{
! 3518: pLevel->u.in.nIn = 0;
! 3519: }
! 3520: #endif
! 3521: }
! 3522: disableTerm(pLevel, pTerm);
! 3523: return iReg;
! 3524: }
! 3525:
! 3526: /*
! 3527: ** Generate code that will evaluate all == and IN constraints for an
! 3528: ** index.
! 3529: **
! 3530: ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
! 3531: ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10
! 3532: ** The index has as many as three equality constraints, but in this
! 3533: ** example, the third "c" value is an inequality. So only two
! 3534: ** constraints are coded. This routine will generate code to evaluate
! 3535: ** a==5 and b IN (1,2,3). The current values for a and b will be stored
! 3536: ** in consecutive registers and the index of the first register is returned.
! 3537: **
! 3538: ** In the example above nEq==2. But this subroutine works for any value
! 3539: ** of nEq including 0. If nEq==0, this routine is nearly a no-op.
! 3540: ** The only thing it does is allocate the pLevel->iMem memory cell and
! 3541: ** compute the affinity string.
! 3542: **
! 3543: ** This routine always allocates at least one memory cell and returns
! 3544: ** the index of that memory cell. The code that
! 3545: ** calls this routine will use that memory cell to store the termination
! 3546: ** key value of the loop. If one or more IN operators appear, then
! 3547: ** this routine allocates an additional nEq memory cells for internal
! 3548: ** use.
! 3549: **
! 3550: ** Before returning, *pzAff is set to point to a buffer containing a
! 3551: ** copy of the column affinity string of the index allocated using
! 3552: ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
! 3553: ** with equality constraints that use NONE affinity are set to
! 3554: ** SQLITE_AFF_NONE. This is to deal with SQL such as the following:
! 3555: **
! 3556: ** CREATE TABLE t1(a TEXT PRIMARY KEY, b);
! 3557: ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
! 3558: **
! 3559: ** In the example above, the index on t1(a) has TEXT affinity. But since
! 3560: ** the right hand side of the equality constraint (t2.b) has NONE affinity,
! 3561: ** no conversion should be attempted before using a t2.b value as part of
! 3562: ** a key to search the index. Hence the first byte in the returned affinity
! 3563: ** string in this example would be set to SQLITE_AFF_NONE.
! 3564: */
! 3565: static int codeAllEqualityTerms(
! 3566: Parse *pParse, /* Parsing context */
! 3567: WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */
! 3568: WhereClause *pWC, /* The WHERE clause */
! 3569: Bitmask notReady, /* Which parts of FROM have not yet been coded */
! 3570: int nExtraReg, /* Number of extra registers to allocate */
! 3571: char **pzAff /* OUT: Set to point to affinity string */
! 3572: ){
! 3573: int nEq = pLevel->plan.nEq; /* The number of == or IN constraints to code */
! 3574: Vdbe *v = pParse->pVdbe; /* The vm under construction */
! 3575: Index *pIdx; /* The index being used for this loop */
! 3576: int iCur = pLevel->iTabCur; /* The cursor of the table */
! 3577: WhereTerm *pTerm; /* A single constraint term */
! 3578: int j; /* Loop counter */
! 3579: int regBase; /* Base register */
! 3580: int nReg; /* Number of registers to allocate */
! 3581: char *zAff; /* Affinity string to return */
! 3582:
! 3583: /* This module is only called on query plans that use an index. */
! 3584: assert( pLevel->plan.wsFlags & WHERE_INDEXED );
! 3585: pIdx = pLevel->plan.u.pIdx;
! 3586:
! 3587: /* Figure out how many memory cells we will need then allocate them.
! 3588: */
! 3589: regBase = pParse->nMem + 1;
! 3590: nReg = pLevel->plan.nEq + nExtraReg;
! 3591: pParse->nMem += nReg;
! 3592:
! 3593: zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
! 3594: if( !zAff ){
! 3595: pParse->db->mallocFailed = 1;
! 3596: }
! 3597:
! 3598: /* Evaluate the equality constraints
! 3599: */
! 3600: assert( pIdx->nColumn>=nEq );
! 3601: for(j=0; j<nEq; j++){
! 3602: int r1;
! 3603: int k = pIdx->aiColumn[j];
! 3604: pTerm = findTerm(pWC, iCur, k, notReady, pLevel->plan.wsFlags, pIdx);
! 3605: if( NEVER(pTerm==0) ) break;
! 3606: /* The following true for indices with redundant columns.
! 3607: ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
! 3608: testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
! 3609: testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 3610: r1 = codeEqualityTerm(pParse, pTerm, pLevel, regBase+j);
! 3611: if( r1!=regBase+j ){
! 3612: if( nReg==1 ){
! 3613: sqlite3ReleaseTempReg(pParse, regBase);
! 3614: regBase = r1;
! 3615: }else{
! 3616: sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
! 3617: }
! 3618: }
! 3619: testcase( pTerm->eOperator & WO_ISNULL );
! 3620: testcase( pTerm->eOperator & WO_IN );
! 3621: if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){
! 3622: Expr *pRight = pTerm->pExpr->pRight;
! 3623: sqlite3ExprCodeIsNullJump(v, pRight, regBase+j, pLevel->addrBrk);
! 3624: if( zAff ){
! 3625: if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_NONE ){
! 3626: zAff[j] = SQLITE_AFF_NONE;
! 3627: }
! 3628: if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
! 3629: zAff[j] = SQLITE_AFF_NONE;
! 3630: }
! 3631: }
! 3632: }
! 3633: }
! 3634: *pzAff = zAff;
! 3635: return regBase;
! 3636: }
! 3637:
! 3638: #ifndef SQLITE_OMIT_EXPLAIN
! 3639: /*
! 3640: ** This routine is a helper for explainIndexRange() below
! 3641: **
! 3642: ** pStr holds the text of an expression that we are building up one term
! 3643: ** at a time. This routine adds a new term to the end of the expression.
! 3644: ** Terms are separated by AND so add the "AND" text for second and subsequent
! 3645: ** terms only.
! 3646: */
! 3647: static void explainAppendTerm(
! 3648: StrAccum *pStr, /* The text expression being built */
! 3649: int iTerm, /* Index of this term. First is zero */
! 3650: const char *zColumn, /* Name of the column */
! 3651: const char *zOp /* Name of the operator */
! 3652: ){
! 3653: if( iTerm ) sqlite3StrAccumAppend(pStr, " AND ", 5);
! 3654: sqlite3StrAccumAppend(pStr, zColumn, -1);
! 3655: sqlite3StrAccumAppend(pStr, zOp, 1);
! 3656: sqlite3StrAccumAppend(pStr, "?", 1);
! 3657: }
! 3658:
! 3659: /*
! 3660: ** Argument pLevel describes a strategy for scanning table pTab. This
! 3661: ** function returns a pointer to a string buffer containing a description
! 3662: ** of the subset of table rows scanned by the strategy in the form of an
! 3663: ** SQL expression. Or, if all rows are scanned, NULL is returned.
! 3664: **
! 3665: ** For example, if the query:
! 3666: **
! 3667: ** SELECT * FROM t1 WHERE a=1 AND b>2;
! 3668: **
! 3669: ** is run and there is an index on (a, b), then this function returns a
! 3670: ** string similar to:
! 3671: **
! 3672: ** "a=? AND b>?"
! 3673: **
! 3674: ** The returned pointer points to memory obtained from sqlite3DbMalloc().
! 3675: ** It is the responsibility of the caller to free the buffer when it is
! 3676: ** no longer required.
! 3677: */
! 3678: static char *explainIndexRange(sqlite3 *db, WhereLevel *pLevel, Table *pTab){
! 3679: WherePlan *pPlan = &pLevel->plan;
! 3680: Index *pIndex = pPlan->u.pIdx;
! 3681: int nEq = pPlan->nEq;
! 3682: int i, j;
! 3683: Column *aCol = pTab->aCol;
! 3684: int *aiColumn = pIndex->aiColumn;
! 3685: StrAccum txt;
! 3686:
! 3687: if( nEq==0 && (pPlan->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ){
! 3688: return 0;
! 3689: }
! 3690: sqlite3StrAccumInit(&txt, 0, 0, SQLITE_MAX_LENGTH);
! 3691: txt.db = db;
! 3692: sqlite3StrAccumAppend(&txt, " (", 2);
! 3693: for(i=0; i<nEq; i++){
! 3694: explainAppendTerm(&txt, i, aCol[aiColumn[i]].zName, "=");
! 3695: }
! 3696:
! 3697: j = i;
! 3698: if( pPlan->wsFlags&WHERE_BTM_LIMIT ){
! 3699: char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName;
! 3700: explainAppendTerm(&txt, i++, z, ">");
! 3701: }
! 3702: if( pPlan->wsFlags&WHERE_TOP_LIMIT ){
! 3703: char *z = (j==pIndex->nColumn ) ? "rowid" : aCol[aiColumn[j]].zName;
! 3704: explainAppendTerm(&txt, i, z, "<");
! 3705: }
! 3706: sqlite3StrAccumAppend(&txt, ")", 1);
! 3707: return sqlite3StrAccumFinish(&txt);
! 3708: }
! 3709:
! 3710: /*
! 3711: ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
! 3712: ** command. If the query being compiled is an EXPLAIN QUERY PLAN, a single
! 3713: ** record is added to the output to describe the table scan strategy in
! 3714: ** pLevel.
! 3715: */
! 3716: static void explainOneScan(
! 3717: Parse *pParse, /* Parse context */
! 3718: SrcList *pTabList, /* Table list this loop refers to */
! 3719: WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */
! 3720: int iLevel, /* Value for "level" column of output */
! 3721: int iFrom, /* Value for "from" column of output */
! 3722: u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */
! 3723: ){
! 3724: if( pParse->explain==2 ){
! 3725: u32 flags = pLevel->plan.wsFlags;
! 3726: struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom];
! 3727: Vdbe *v = pParse->pVdbe; /* VM being constructed */
! 3728: sqlite3 *db = pParse->db; /* Database handle */
! 3729: char *zMsg; /* Text to add to EQP output */
! 3730: sqlite3_int64 nRow; /* Expected number of rows visited by scan */
! 3731: int iId = pParse->iSelectId; /* Select id (left-most output column) */
! 3732: int isSearch; /* True for a SEARCH. False for SCAN. */
! 3733:
! 3734: if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_ONETABLE_ONLY) ) return;
! 3735:
! 3736: isSearch = (pLevel->plan.nEq>0)
! 3737: || (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0
! 3738: || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX));
! 3739:
! 3740: zMsg = sqlite3MPrintf(db, "%s", isSearch?"SEARCH":"SCAN");
! 3741: if( pItem->pSelect ){
! 3742: zMsg = sqlite3MAppendf(db, zMsg, "%s SUBQUERY %d", zMsg,pItem->iSelectId);
! 3743: }else{
! 3744: zMsg = sqlite3MAppendf(db, zMsg, "%s TABLE %s", zMsg, pItem->zName);
! 3745: }
! 3746:
! 3747: if( pItem->zAlias ){
! 3748: zMsg = sqlite3MAppendf(db, zMsg, "%s AS %s", zMsg, pItem->zAlias);
! 3749: }
! 3750: if( (flags & WHERE_INDEXED)!=0 ){
! 3751: char *zWhere = explainIndexRange(db, pLevel, pItem->pTab);
! 3752: zMsg = sqlite3MAppendf(db, zMsg, "%s USING %s%sINDEX%s%s%s", zMsg,
! 3753: ((flags & WHERE_TEMP_INDEX)?"AUTOMATIC ":""),
! 3754: ((flags & WHERE_IDX_ONLY)?"COVERING ":""),
! 3755: ((flags & WHERE_TEMP_INDEX)?"":" "),
! 3756: ((flags & WHERE_TEMP_INDEX)?"": pLevel->plan.u.pIdx->zName),
! 3757: zWhere
! 3758: );
! 3759: sqlite3DbFree(db, zWhere);
! 3760: }else if( flags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
! 3761: zMsg = sqlite3MAppendf(db, zMsg, "%s USING INTEGER PRIMARY KEY", zMsg);
! 3762:
! 3763: if( flags&WHERE_ROWID_EQ ){
! 3764: zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid=?)", zMsg);
! 3765: }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
! 3766: zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>? AND rowid<?)", zMsg);
! 3767: }else if( flags&WHERE_BTM_LIMIT ){
! 3768: zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid>?)", zMsg);
! 3769: }else if( flags&WHERE_TOP_LIMIT ){
! 3770: zMsg = sqlite3MAppendf(db, zMsg, "%s (rowid<?)", zMsg);
! 3771: }
! 3772: }
! 3773: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 3774: else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
! 3775: sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
! 3776: zMsg = sqlite3MAppendf(db, zMsg, "%s VIRTUAL TABLE INDEX %d:%s", zMsg,
! 3777: pVtabIdx->idxNum, pVtabIdx->idxStr);
! 3778: }
! 3779: #endif
! 3780: if( wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX) ){
! 3781: testcase( wctrlFlags & WHERE_ORDERBY_MIN );
! 3782: nRow = 1;
! 3783: }else{
! 3784: nRow = (sqlite3_int64)pLevel->plan.nRow;
! 3785: }
! 3786: zMsg = sqlite3MAppendf(db, zMsg, "%s (~%lld rows)", zMsg, nRow);
! 3787: sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg, P4_DYNAMIC);
! 3788: }
! 3789: }
! 3790: #else
! 3791: # define explainOneScan(u,v,w,x,y,z)
! 3792: #endif /* SQLITE_OMIT_EXPLAIN */
! 3793:
! 3794:
! 3795: /*
! 3796: ** Generate code for the start of the iLevel-th loop in the WHERE clause
! 3797: ** implementation described by pWInfo.
! 3798: */
! 3799: static Bitmask codeOneLoopStart(
! 3800: WhereInfo *pWInfo, /* Complete information about the WHERE clause */
! 3801: int iLevel, /* Which level of pWInfo->a[] should be coded */
! 3802: u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */
! 3803: Bitmask notReady, /* Which tables are currently available */
! 3804: Expr *pWhere /* Complete WHERE clause */
! 3805: ){
! 3806: int j, k; /* Loop counters */
! 3807: int iCur; /* The VDBE cursor for the table */
! 3808: int addrNxt; /* Where to jump to continue with the next IN case */
! 3809: int omitTable; /* True if we use the index only */
! 3810: int bRev; /* True if we need to scan in reverse order */
! 3811: WhereLevel *pLevel; /* The where level to be coded */
! 3812: WhereClause *pWC; /* Decomposition of the entire WHERE clause */
! 3813: WhereTerm *pTerm; /* A WHERE clause term */
! 3814: Parse *pParse; /* Parsing context */
! 3815: Vdbe *v; /* The prepared stmt under constructions */
! 3816: struct SrcList_item *pTabItem; /* FROM clause term being coded */
! 3817: int addrBrk; /* Jump here to break out of the loop */
! 3818: int addrCont; /* Jump here to continue with next cycle */
! 3819: int iRowidReg = 0; /* Rowid is stored in this register, if not zero */
! 3820: int iReleaseReg = 0; /* Temp register to free before returning */
! 3821:
! 3822: pParse = pWInfo->pParse;
! 3823: v = pParse->pVdbe;
! 3824: pWC = pWInfo->pWC;
! 3825: pLevel = &pWInfo->a[iLevel];
! 3826: pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
! 3827: iCur = pTabItem->iCursor;
! 3828: bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
! 3829: omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0
! 3830: && (wctrlFlags & WHERE_FORCE_TABLE)==0;
! 3831:
! 3832: /* Create labels for the "break" and "continue" instructions
! 3833: ** for the current loop. Jump to addrBrk to break out of a loop.
! 3834: ** Jump to cont to go immediately to the next iteration of the
! 3835: ** loop.
! 3836: **
! 3837: ** When there is an IN operator, we also have a "addrNxt" label that
! 3838: ** means to continue with the next IN value combination. When
! 3839: ** there are no IN operators in the constraints, the "addrNxt" label
! 3840: ** is the same as "addrBrk".
! 3841: */
! 3842: addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
! 3843: addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v);
! 3844:
! 3845: /* If this is the right table of a LEFT OUTER JOIN, allocate and
! 3846: ** initialize a memory cell that records if this table matches any
! 3847: ** row of the left table of the join.
! 3848: */
! 3849: if( pLevel->iFrom>0 && (pTabItem[0].jointype & JT_LEFT)!=0 ){
! 3850: pLevel->iLeftJoin = ++pParse->nMem;
! 3851: sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
! 3852: VdbeComment((v, "init LEFT JOIN no-match flag"));
! 3853: }
! 3854:
! 3855: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 3856: if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
! 3857: /* Case 0: The table is a virtual-table. Use the VFilter and VNext
! 3858: ** to access the data.
! 3859: */
! 3860: int iReg; /* P3 Value for OP_VFilter */
! 3861: sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
! 3862: int nConstraint = pVtabIdx->nConstraint;
! 3863: struct sqlite3_index_constraint_usage *aUsage =
! 3864: pVtabIdx->aConstraintUsage;
! 3865: const struct sqlite3_index_constraint *aConstraint =
! 3866: pVtabIdx->aConstraint;
! 3867:
! 3868: sqlite3ExprCachePush(pParse);
! 3869: iReg = sqlite3GetTempRange(pParse, nConstraint+2);
! 3870: for(j=1; j<=nConstraint; j++){
! 3871: for(k=0; k<nConstraint; k++){
! 3872: if( aUsage[k].argvIndex==j ){
! 3873: int iTerm = aConstraint[k].iTermOffset;
! 3874: sqlite3ExprCode(pParse, pWC->a[iTerm].pExpr->pRight, iReg+j+1);
! 3875: break;
! 3876: }
! 3877: }
! 3878: if( k==nConstraint ) break;
! 3879: }
! 3880: sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
! 3881: sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
! 3882: sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrBrk, iReg, pVtabIdx->idxStr,
! 3883: pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
! 3884: pVtabIdx->needToFreeIdxStr = 0;
! 3885: for(j=0; j<nConstraint; j++){
! 3886: if( aUsage[j].omit ){
! 3887: int iTerm = aConstraint[j].iTermOffset;
! 3888: disableTerm(pLevel, &pWC->a[iTerm]);
! 3889: }
! 3890: }
! 3891: pLevel->op = OP_VNext;
! 3892: pLevel->p1 = iCur;
! 3893: pLevel->p2 = sqlite3VdbeCurrentAddr(v);
! 3894: sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
! 3895: sqlite3ExprCachePop(pParse, 1);
! 3896: }else
! 3897: #endif /* SQLITE_OMIT_VIRTUALTABLE */
! 3898:
! 3899: if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
! 3900: /* Case 1: We can directly reference a single row using an
! 3901: ** equality comparison against the ROWID field. Or
! 3902: ** we reference multiple rows using a "rowid IN (...)"
! 3903: ** construct.
! 3904: */
! 3905: iReleaseReg = sqlite3GetTempReg(pParse);
! 3906: pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
! 3907: assert( pTerm!=0 );
! 3908: assert( pTerm->pExpr!=0 );
! 3909: assert( pTerm->leftCursor==iCur );
! 3910: assert( omitTable==0 );
! 3911: testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 3912: iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, iReleaseReg);
! 3913: addrNxt = pLevel->addrNxt;
! 3914: sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
! 3915: sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
! 3916: sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
! 3917: VdbeComment((v, "pk"));
! 3918: pLevel->op = OP_Noop;
! 3919: }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
! 3920: /* Case 2: We have an inequality comparison against the ROWID field.
! 3921: */
! 3922: int testOp = OP_Noop;
! 3923: int start;
! 3924: int memEndValue = 0;
! 3925: WhereTerm *pStart, *pEnd;
! 3926:
! 3927: assert( omitTable==0 );
! 3928: pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
! 3929: pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
! 3930: if( bRev ){
! 3931: pTerm = pStart;
! 3932: pStart = pEnd;
! 3933: pEnd = pTerm;
! 3934: }
! 3935: if( pStart ){
! 3936: Expr *pX; /* The expression that defines the start bound */
! 3937: int r1, rTemp; /* Registers for holding the start boundary */
! 3938:
! 3939: /* The following constant maps TK_xx codes into corresponding
! 3940: ** seek opcodes. It depends on a particular ordering of TK_xx
! 3941: */
! 3942: const u8 aMoveOp[] = {
! 3943: /* TK_GT */ OP_SeekGt,
! 3944: /* TK_LE */ OP_SeekLe,
! 3945: /* TK_LT */ OP_SeekLt,
! 3946: /* TK_GE */ OP_SeekGe
! 3947: };
! 3948: assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */
! 3949: assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */
! 3950: assert( TK_GE==TK_GT+3 ); /* ... is correcct. */
! 3951:
! 3952: testcase( pStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 3953: pX = pStart->pExpr;
! 3954: assert( pX!=0 );
! 3955: assert( pStart->leftCursor==iCur );
! 3956: r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
! 3957: sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1);
! 3958: VdbeComment((v, "pk"));
! 3959: sqlite3ExprCacheAffinityChange(pParse, r1, 1);
! 3960: sqlite3ReleaseTempReg(pParse, rTemp);
! 3961: disableTerm(pLevel, pStart);
! 3962: }else{
! 3963: sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
! 3964: }
! 3965: if( pEnd ){
! 3966: Expr *pX;
! 3967: pX = pEnd->pExpr;
! 3968: assert( pX!=0 );
! 3969: assert( pEnd->leftCursor==iCur );
! 3970: testcase( pEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 3971: memEndValue = ++pParse->nMem;
! 3972: sqlite3ExprCode(pParse, pX->pRight, memEndValue);
! 3973: if( pX->op==TK_LT || pX->op==TK_GT ){
! 3974: testOp = bRev ? OP_Le : OP_Ge;
! 3975: }else{
! 3976: testOp = bRev ? OP_Lt : OP_Gt;
! 3977: }
! 3978: disableTerm(pLevel, pEnd);
! 3979: }
! 3980: start = sqlite3VdbeCurrentAddr(v);
! 3981: pLevel->op = bRev ? OP_Prev : OP_Next;
! 3982: pLevel->p1 = iCur;
! 3983: pLevel->p2 = start;
! 3984: if( pStart==0 && pEnd==0 ){
! 3985: pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
! 3986: }else{
! 3987: assert( pLevel->p5==0 );
! 3988: }
! 3989: if( testOp!=OP_Noop ){
! 3990: iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
! 3991: sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
! 3992: sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
! 3993: sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
! 3994: sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
! 3995: }
! 3996: }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
! 3997: /* Case 3: A scan using an index.
! 3998: **
! 3999: ** The WHERE clause may contain zero or more equality
! 4000: ** terms ("==" or "IN" operators) that refer to the N
! 4001: ** left-most columns of the index. It may also contain
! 4002: ** inequality constraints (>, <, >= or <=) on the indexed
! 4003: ** column that immediately follows the N equalities. Only
! 4004: ** the right-most column can be an inequality - the rest must
! 4005: ** use the "==" and "IN" operators. For example, if the
! 4006: ** index is on (x,y,z), then the following clauses are all
! 4007: ** optimized:
! 4008: **
! 4009: ** x=5
! 4010: ** x=5 AND y=10
! 4011: ** x=5 AND y<10
! 4012: ** x=5 AND y>5 AND y<10
! 4013: ** x=5 AND y=5 AND z<=10
! 4014: **
! 4015: ** The z<10 term of the following cannot be used, only
! 4016: ** the x=5 term:
! 4017: **
! 4018: ** x=5 AND z<10
! 4019: **
! 4020: ** N may be zero if there are inequality constraints.
! 4021: ** If there are no inequality constraints, then N is at
! 4022: ** least one.
! 4023: **
! 4024: ** This case is also used when there are no WHERE clause
! 4025: ** constraints but an index is selected anyway, in order
! 4026: ** to force the output order to conform to an ORDER BY.
! 4027: */
! 4028: static const u8 aStartOp[] = {
! 4029: 0,
! 4030: 0,
! 4031: OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */
! 4032: OP_Last, /* 3: (!start_constraints && startEq && bRev) */
! 4033: OP_SeekGt, /* 4: (start_constraints && !startEq && !bRev) */
! 4034: OP_SeekLt, /* 5: (start_constraints && !startEq && bRev) */
! 4035: OP_SeekGe, /* 6: (start_constraints && startEq && !bRev) */
! 4036: OP_SeekLe /* 7: (start_constraints && startEq && bRev) */
! 4037: };
! 4038: static const u8 aEndOp[] = {
! 4039: OP_Noop, /* 0: (!end_constraints) */
! 4040: OP_IdxGE, /* 1: (end_constraints && !bRev) */
! 4041: OP_IdxLT /* 2: (end_constraints && bRev) */
! 4042: };
! 4043: int nEq = pLevel->plan.nEq; /* Number of == or IN terms */
! 4044: int isMinQuery = 0; /* If this is an optimized SELECT min(x).. */
! 4045: int regBase; /* Base register holding constraint values */
! 4046: int r1; /* Temp register */
! 4047: WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */
! 4048: WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */
! 4049: int startEq; /* True if range start uses ==, >= or <= */
! 4050: int endEq; /* True if range end uses ==, >= or <= */
! 4051: int start_constraints; /* Start of range is constrained */
! 4052: int nConstraint; /* Number of constraint terms */
! 4053: Index *pIdx; /* The index we will be using */
! 4054: int iIdxCur; /* The VDBE cursor for the index */
! 4055: int nExtraReg = 0; /* Number of extra registers needed */
! 4056: int op; /* Instruction opcode */
! 4057: char *zStartAff; /* Affinity for start of range constraint */
! 4058: char *zEndAff; /* Affinity for end of range constraint */
! 4059:
! 4060: pIdx = pLevel->plan.u.pIdx;
! 4061: iIdxCur = pLevel->iIdxCur;
! 4062: k = (nEq==pIdx->nColumn ? -1 : pIdx->aiColumn[nEq]);
! 4063:
! 4064: /* If this loop satisfies a sort order (pOrderBy) request that
! 4065: ** was passed to this function to implement a "SELECT min(x) ..."
! 4066: ** query, then the caller will only allow the loop to run for
! 4067: ** a single iteration. This means that the first row returned
! 4068: ** should not have a NULL value stored in 'x'. If column 'x' is
! 4069: ** the first one after the nEq equality constraints in the index,
! 4070: ** this requires some special handling.
! 4071: */
! 4072: if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
! 4073: && (pLevel->plan.wsFlags&WHERE_ORDERBY)
! 4074: && (pIdx->nColumn>nEq)
! 4075: ){
! 4076: /* assert( pOrderBy->nExpr==1 ); */
! 4077: /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
! 4078: isMinQuery = 1;
! 4079: nExtraReg = 1;
! 4080: }
! 4081:
! 4082: /* Find any inequality constraint terms for the start and end
! 4083: ** of the range.
! 4084: */
! 4085: if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
! 4086: pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
! 4087: nExtraReg = 1;
! 4088: }
! 4089: if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
! 4090: pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
! 4091: nExtraReg = 1;
! 4092: }
! 4093:
! 4094: /* Generate code to evaluate all constraint terms using == or IN
! 4095: ** and store the values of those terms in an array of registers
! 4096: ** starting at regBase.
! 4097: */
! 4098: regBase = codeAllEqualityTerms(
! 4099: pParse, pLevel, pWC, notReady, nExtraReg, &zStartAff
! 4100: );
! 4101: zEndAff = sqlite3DbStrDup(pParse->db, zStartAff);
! 4102: addrNxt = pLevel->addrNxt;
! 4103:
! 4104: /* If we are doing a reverse order scan on an ascending index, or
! 4105: ** a forward order scan on a descending index, interchange the
! 4106: ** start and end terms (pRangeStart and pRangeEnd).
! 4107: */
! 4108: if( (nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC))
! 4109: || (bRev && pIdx->nColumn==nEq)
! 4110: ){
! 4111: SWAP(WhereTerm *, pRangeEnd, pRangeStart);
! 4112: }
! 4113:
! 4114: testcase( pRangeStart && pRangeStart->eOperator & WO_LE );
! 4115: testcase( pRangeStart && pRangeStart->eOperator & WO_GE );
! 4116: testcase( pRangeEnd && pRangeEnd->eOperator & WO_LE );
! 4117: testcase( pRangeEnd && pRangeEnd->eOperator & WO_GE );
! 4118: startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
! 4119: endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
! 4120: start_constraints = pRangeStart || nEq>0;
! 4121:
! 4122: /* Seek the index cursor to the start of the range. */
! 4123: nConstraint = nEq;
! 4124: if( pRangeStart ){
! 4125: Expr *pRight = pRangeStart->pExpr->pRight;
! 4126: sqlite3ExprCode(pParse, pRight, regBase+nEq);
! 4127: if( (pRangeStart->wtFlags & TERM_VNULL)==0 ){
! 4128: sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
! 4129: }
! 4130: if( zStartAff ){
! 4131: if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){
! 4132: /* Since the comparison is to be performed with no conversions
! 4133: ** applied to the operands, set the affinity to apply to pRight to
! 4134: ** SQLITE_AFF_NONE. */
! 4135: zStartAff[nEq] = SQLITE_AFF_NONE;
! 4136: }
! 4137: if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){
! 4138: zStartAff[nEq] = SQLITE_AFF_NONE;
! 4139: }
! 4140: }
! 4141: nConstraint++;
! 4142: testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 4143: }else if( isMinQuery ){
! 4144: sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
! 4145: nConstraint++;
! 4146: startEq = 0;
! 4147: start_constraints = 1;
! 4148: }
! 4149: codeApplyAffinity(pParse, regBase, nConstraint, zStartAff);
! 4150: op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
! 4151: assert( op!=0 );
! 4152: testcase( op==OP_Rewind );
! 4153: testcase( op==OP_Last );
! 4154: testcase( op==OP_SeekGt );
! 4155: testcase( op==OP_SeekGe );
! 4156: testcase( op==OP_SeekLe );
! 4157: testcase( op==OP_SeekLt );
! 4158: sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
! 4159:
! 4160: /* Load the value for the inequality constraint at the end of the
! 4161: ** range (if any).
! 4162: */
! 4163: nConstraint = nEq;
! 4164: if( pRangeEnd ){
! 4165: Expr *pRight = pRangeEnd->pExpr->pRight;
! 4166: sqlite3ExprCacheRemove(pParse, regBase+nEq, 1);
! 4167: sqlite3ExprCode(pParse, pRight, regBase+nEq);
! 4168: if( (pRangeEnd->wtFlags & TERM_VNULL)==0 ){
! 4169: sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt);
! 4170: }
! 4171: if( zEndAff ){
! 4172: if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){
! 4173: /* Since the comparison is to be performed with no conversions
! 4174: ** applied to the operands, set the affinity to apply to pRight to
! 4175: ** SQLITE_AFF_NONE. */
! 4176: zEndAff[nEq] = SQLITE_AFF_NONE;
! 4177: }
! 4178: if( sqlite3ExprNeedsNoAffinityChange(pRight, zEndAff[nEq]) ){
! 4179: zEndAff[nEq] = SQLITE_AFF_NONE;
! 4180: }
! 4181: }
! 4182: codeApplyAffinity(pParse, regBase, nEq+1, zEndAff);
! 4183: nConstraint++;
! 4184: testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
! 4185: }
! 4186: sqlite3DbFree(pParse->db, zStartAff);
! 4187: sqlite3DbFree(pParse->db, zEndAff);
! 4188:
! 4189: /* Top of the loop body */
! 4190: pLevel->p2 = sqlite3VdbeCurrentAddr(v);
! 4191:
! 4192: /* Check if the index cursor is past the end of the range. */
! 4193: op = aEndOp[(pRangeEnd || nEq) * (1 + bRev)];
! 4194: testcase( op==OP_Noop );
! 4195: testcase( op==OP_IdxGE );
! 4196: testcase( op==OP_IdxLT );
! 4197: if( op!=OP_Noop ){
! 4198: sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
! 4199: sqlite3VdbeChangeP5(v, endEq!=bRev ?1:0);
! 4200: }
! 4201:
! 4202: /* If there are inequality constraints, check that the value
! 4203: ** of the table column that the inequality contrains is not NULL.
! 4204: ** If it is, jump to the next iteration of the loop.
! 4205: */
! 4206: r1 = sqlite3GetTempReg(pParse);
! 4207: testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
! 4208: testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
! 4209: if( (pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
! 4210: sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
! 4211: sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
! 4212: }
! 4213: sqlite3ReleaseTempReg(pParse, r1);
! 4214:
! 4215: /* Seek the table cursor, if required */
! 4216: disableTerm(pLevel, pRangeStart);
! 4217: disableTerm(pLevel, pRangeEnd);
! 4218: if( !omitTable ){
! 4219: iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
! 4220: sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg);
! 4221: sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
! 4222: sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */
! 4223: }
! 4224:
! 4225: /* Record the instruction used to terminate the loop. Disable
! 4226: ** WHERE clause terms made redundant by the index range scan.
! 4227: */
! 4228: if( pLevel->plan.wsFlags & WHERE_UNIQUE ){
! 4229: pLevel->op = OP_Noop;
! 4230: }else if( bRev ){
! 4231: pLevel->op = OP_Prev;
! 4232: }else{
! 4233: pLevel->op = OP_Next;
! 4234: }
! 4235: pLevel->p1 = iIdxCur;
! 4236: }else
! 4237:
! 4238: #ifndef SQLITE_OMIT_OR_OPTIMIZATION
! 4239: if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
! 4240: /* Case 4: Two or more separately indexed terms connected by OR
! 4241: **
! 4242: ** Example:
! 4243: **
! 4244: ** CREATE TABLE t1(a,b,c,d);
! 4245: ** CREATE INDEX i1 ON t1(a);
! 4246: ** CREATE INDEX i2 ON t1(b);
! 4247: ** CREATE INDEX i3 ON t1(c);
! 4248: **
! 4249: ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
! 4250: **
! 4251: ** In the example, there are three indexed terms connected by OR.
! 4252: ** The top of the loop looks like this:
! 4253: **
! 4254: ** Null 1 # Zero the rowset in reg 1
! 4255: **
! 4256: ** Then, for each indexed term, the following. The arguments to
! 4257: ** RowSetTest are such that the rowid of the current row is inserted
! 4258: ** into the RowSet. If it is already present, control skips the
! 4259: ** Gosub opcode and jumps straight to the code generated by WhereEnd().
! 4260: **
! 4261: ** sqlite3WhereBegin(<term>)
! 4262: ** RowSetTest # Insert rowid into rowset
! 4263: ** Gosub 2 A
! 4264: ** sqlite3WhereEnd()
! 4265: **
! 4266: ** Following the above, code to terminate the loop. Label A, the target
! 4267: ** of the Gosub above, jumps to the instruction right after the Goto.
! 4268: **
! 4269: ** Null 1 # Zero the rowset in reg 1
! 4270: ** Goto B # The loop is finished.
! 4271: **
! 4272: ** A: <loop body> # Return data, whatever.
! 4273: **
! 4274: ** Return 2 # Jump back to the Gosub
! 4275: **
! 4276: ** B: <after the loop>
! 4277: **
! 4278: */
! 4279: WhereClause *pOrWc; /* The OR-clause broken out into subterms */
! 4280: SrcList *pOrTab; /* Shortened table list or OR-clause generation */
! 4281:
! 4282: int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */
! 4283: int regRowset = 0; /* Register for RowSet object */
! 4284: int regRowid = 0; /* Register holding rowid */
! 4285: int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */
! 4286: int iRetInit; /* Address of regReturn init */
! 4287: int untestedTerms = 0; /* Some terms not completely tested */
! 4288: int ii; /* Loop counter */
! 4289: Expr *pAndExpr = 0; /* An ".. AND (...)" expression */
! 4290:
! 4291: pTerm = pLevel->plan.u.pTerm;
! 4292: assert( pTerm!=0 );
! 4293: assert( pTerm->eOperator==WO_OR );
! 4294: assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
! 4295: pOrWc = &pTerm->u.pOrInfo->wc;
! 4296: pLevel->op = OP_Return;
! 4297: pLevel->p1 = regReturn;
! 4298:
! 4299: /* Set up a new SrcList ni pOrTab containing the table being scanned
! 4300: ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
! 4301: ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
! 4302: */
! 4303: if( pWInfo->nLevel>1 ){
! 4304: int nNotReady; /* The number of notReady tables */
! 4305: struct SrcList_item *origSrc; /* Original list of tables */
! 4306: nNotReady = pWInfo->nLevel - iLevel - 1;
! 4307: pOrTab = sqlite3StackAllocRaw(pParse->db,
! 4308: sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
! 4309: if( pOrTab==0 ) return notReady;
! 4310: pOrTab->nAlloc = (i16)(nNotReady + 1);
! 4311: pOrTab->nSrc = pOrTab->nAlloc;
! 4312: memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
! 4313: origSrc = pWInfo->pTabList->a;
! 4314: for(k=1; k<=nNotReady; k++){
! 4315: memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
! 4316: }
! 4317: }else{
! 4318: pOrTab = pWInfo->pTabList;
! 4319: }
! 4320:
! 4321: /* Initialize the rowset register to contain NULL. An SQL NULL is
! 4322: ** equivalent to an empty rowset.
! 4323: **
! 4324: ** Also initialize regReturn to contain the address of the instruction
! 4325: ** immediately following the OP_Return at the bottom of the loop. This
! 4326: ** is required in a few obscure LEFT JOIN cases where control jumps
! 4327: ** over the top of the loop into the body of it. In this case the
! 4328: ** correct response for the end-of-loop code (the OP_Return) is to
! 4329: ** fall through to the next instruction, just as an OP_Next does if
! 4330: ** called on an uninitialized cursor.
! 4331: */
! 4332: if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
! 4333: regRowset = ++pParse->nMem;
! 4334: regRowid = ++pParse->nMem;
! 4335: sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
! 4336: }
! 4337: iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
! 4338:
! 4339: /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y
! 4340: ** Then for every term xN, evaluate as the subexpression: xN AND z
! 4341: ** That way, terms in y that are factored into the disjunction will
! 4342: ** be picked up by the recursive calls to sqlite3WhereBegin() below.
! 4343: */
! 4344: if( pWC->nTerm>1 ){
! 4345: pAndExpr = sqlite3ExprAlloc(pParse->db, TK_AND, 0, 0);
! 4346: pAndExpr->pRight = pWhere;
! 4347: }
! 4348:
! 4349: for(ii=0; ii<pOrWc->nTerm; ii++){
! 4350: WhereTerm *pOrTerm = &pOrWc->a[ii];
! 4351: if( pOrTerm->leftCursor==iCur || pOrTerm->eOperator==WO_AND ){
! 4352: WhereInfo *pSubWInfo; /* Info for single OR-term scan */
! 4353: Expr *pOrExpr = pOrTerm->pExpr;
! 4354: if( pAndExpr ){
! 4355: pAndExpr->pLeft = pOrExpr;
! 4356: pOrExpr = pAndExpr;
! 4357: }
! 4358: /* Loop through table entries that match term pOrTerm. */
! 4359: pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
! 4360: WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
! 4361: WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY);
! 4362: if( pSubWInfo ){
! 4363: explainOneScan(
! 4364: pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
! 4365: );
! 4366: if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
! 4367: int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
! 4368: int r;
! 4369: r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur,
! 4370: regRowid);
! 4371: sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset,
! 4372: sqlite3VdbeCurrentAddr(v)+2, r, iSet);
! 4373: }
! 4374: sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
! 4375:
! 4376: /* The pSubWInfo->untestedTerms flag means that this OR term
! 4377: ** contained one or more AND term from a notReady table. The
! 4378: ** terms from the notReady table could not be tested and will
! 4379: ** need to be tested later.
! 4380: */
! 4381: if( pSubWInfo->untestedTerms ) untestedTerms = 1;
! 4382:
! 4383: /* Finish the loop through table entries that match term pOrTerm. */
! 4384: sqlite3WhereEnd(pSubWInfo);
! 4385: }
! 4386: }
! 4387: }
! 4388: sqlite3DbFree(pParse->db, pAndExpr);
! 4389: sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
! 4390: sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrBrk);
! 4391: sqlite3VdbeResolveLabel(v, iLoopBody);
! 4392:
! 4393: if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
! 4394: if( !untestedTerms ) disableTerm(pLevel, pTerm);
! 4395: }else
! 4396: #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
! 4397:
! 4398: {
! 4399: /* Case 5: There is no usable index. We must do a complete
! 4400: ** scan of the entire table.
! 4401: */
! 4402: static const u8 aStep[] = { OP_Next, OP_Prev };
! 4403: static const u8 aStart[] = { OP_Rewind, OP_Last };
! 4404: assert( bRev==0 || bRev==1 );
! 4405: assert( omitTable==0 );
! 4406: pLevel->op = aStep[bRev];
! 4407: pLevel->p1 = iCur;
! 4408: pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
! 4409: pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
! 4410: }
! 4411: notReady &= ~getMask(pWC->pMaskSet, iCur);
! 4412:
! 4413: /* Insert code to test every subexpression that can be completely
! 4414: ** computed using the current set of tables.
! 4415: **
! 4416: ** IMPLEMENTATION-OF: R-49525-50935 Terms that cannot be satisfied through
! 4417: ** the use of indices become tests that are evaluated against each row of
! 4418: ** the relevant input tables.
! 4419: */
! 4420: for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
! 4421: Expr *pE;
! 4422: testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
! 4423: testcase( pTerm->wtFlags & TERM_CODED );
! 4424: if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
! 4425: if( (pTerm->prereqAll & notReady)!=0 ){
! 4426: testcase( pWInfo->untestedTerms==0
! 4427: && (pWInfo->wctrlFlags & WHERE_ONETABLE_ONLY)!=0 );
! 4428: pWInfo->untestedTerms = 1;
! 4429: continue;
! 4430: }
! 4431: pE = pTerm->pExpr;
! 4432: assert( pE!=0 );
! 4433: if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){
! 4434: continue;
! 4435: }
! 4436: sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
! 4437: pTerm->wtFlags |= TERM_CODED;
! 4438: }
! 4439:
! 4440: /* For a LEFT OUTER JOIN, generate code that will record the fact that
! 4441: ** at least one row of the right table has matched the left table.
! 4442: */
! 4443: if( pLevel->iLeftJoin ){
! 4444: pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
! 4445: sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
! 4446: VdbeComment((v, "record LEFT JOIN hit"));
! 4447: sqlite3ExprCacheClear(pParse);
! 4448: for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){
! 4449: testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* IMP: R-30575-11662 */
! 4450: testcase( pTerm->wtFlags & TERM_CODED );
! 4451: if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
! 4452: if( (pTerm->prereqAll & notReady)!=0 ){
! 4453: assert( pWInfo->untestedTerms );
! 4454: continue;
! 4455: }
! 4456: assert( pTerm->pExpr );
! 4457: sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
! 4458: pTerm->wtFlags |= TERM_CODED;
! 4459: }
! 4460: }
! 4461: sqlite3ReleaseTempReg(pParse, iReleaseReg);
! 4462:
! 4463: return notReady;
! 4464: }
! 4465:
! 4466: #if defined(SQLITE_TEST)
! 4467: /*
! 4468: ** The following variable holds a text description of query plan generated
! 4469: ** by the most recent call to sqlite3WhereBegin(). Each call to WhereBegin
! 4470: ** overwrites the previous. This information is used for testing and
! 4471: ** analysis only.
! 4472: */
! 4473: char sqlite3_query_plan[BMS*2*40]; /* Text of the join */
! 4474: static int nQPlan = 0; /* Next free slow in _query_plan[] */
! 4475:
! 4476: #endif /* SQLITE_TEST */
! 4477:
! 4478:
! 4479: /*
! 4480: ** Free a WhereInfo structure
! 4481: */
! 4482: static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
! 4483: if( ALWAYS(pWInfo) ){
! 4484: int i;
! 4485: for(i=0; i<pWInfo->nLevel; i++){
! 4486: sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
! 4487: if( pInfo ){
! 4488: /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
! 4489: if( pInfo->needToFreeIdxStr ){
! 4490: sqlite3_free(pInfo->idxStr);
! 4491: }
! 4492: sqlite3DbFree(db, pInfo);
! 4493: }
! 4494: if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){
! 4495: Index *pIdx = pWInfo->a[i].plan.u.pIdx;
! 4496: if( pIdx ){
! 4497: sqlite3DbFree(db, pIdx->zColAff);
! 4498: sqlite3DbFree(db, pIdx);
! 4499: }
! 4500: }
! 4501: }
! 4502: whereClauseClear(pWInfo->pWC);
! 4503: sqlite3DbFree(db, pWInfo);
! 4504: }
! 4505: }
! 4506:
! 4507:
! 4508: /*
! 4509: ** Generate the beginning of the loop used for WHERE clause processing.
! 4510: ** The return value is a pointer to an opaque structure that contains
! 4511: ** information needed to terminate the loop. Later, the calling routine
! 4512: ** should invoke sqlite3WhereEnd() with the return value of this function
! 4513: ** in order to complete the WHERE clause processing.
! 4514: **
! 4515: ** If an error occurs, this routine returns NULL.
! 4516: **
! 4517: ** The basic idea is to do a nested loop, one loop for each table in
! 4518: ** the FROM clause of a select. (INSERT and UPDATE statements are the
! 4519: ** same as a SELECT with only a single table in the FROM clause.) For
! 4520: ** example, if the SQL is this:
! 4521: **
! 4522: ** SELECT * FROM t1, t2, t3 WHERE ...;
! 4523: **
! 4524: ** Then the code generated is conceptually like the following:
! 4525: **
! 4526: ** foreach row1 in t1 do \ Code generated
! 4527: ** foreach row2 in t2 do |-- by sqlite3WhereBegin()
! 4528: ** foreach row3 in t3 do /
! 4529: ** ...
! 4530: ** end \ Code generated
! 4531: ** end |-- by sqlite3WhereEnd()
! 4532: ** end /
! 4533: **
! 4534: ** Note that the loops might not be nested in the order in which they
! 4535: ** appear in the FROM clause if a different order is better able to make
! 4536: ** use of indices. Note also that when the IN operator appears in
! 4537: ** the WHERE clause, it might result in additional nested loops for
! 4538: ** scanning through all values on the right-hand side of the IN.
! 4539: **
! 4540: ** There are Btree cursors associated with each table. t1 uses cursor
! 4541: ** number pTabList->a[0].iCursor. t2 uses the cursor pTabList->a[1].iCursor.
! 4542: ** And so forth. This routine generates code to open those VDBE cursors
! 4543: ** and sqlite3WhereEnd() generates the code to close them.
! 4544: **
! 4545: ** The code that sqlite3WhereBegin() generates leaves the cursors named
! 4546: ** in pTabList pointing at their appropriate entries. The [...] code
! 4547: ** can use OP_Column and OP_Rowid opcodes on these cursors to extract
! 4548: ** data from the various tables of the loop.
! 4549: **
! 4550: ** If the WHERE clause is empty, the foreach loops must each scan their
! 4551: ** entire tables. Thus a three-way join is an O(N^3) operation. But if
! 4552: ** the tables have indices and there are terms in the WHERE clause that
! 4553: ** refer to those indices, a complete table scan can be avoided and the
! 4554: ** code will run much faster. Most of the work of this routine is checking
! 4555: ** to see if there are indices that can be used to speed up the loop.
! 4556: **
! 4557: ** Terms of the WHERE clause are also used to limit which rows actually
! 4558: ** make it to the "..." in the middle of the loop. After each "foreach",
! 4559: ** terms of the WHERE clause that use only terms in that loop and outer
! 4560: ** loops are evaluated and if false a jump is made around all subsequent
! 4561: ** inner loops (or around the "..." if the test occurs within the inner-
! 4562: ** most loop)
! 4563: **
! 4564: ** OUTER JOINS
! 4565: **
! 4566: ** An outer join of tables t1 and t2 is conceptally coded as follows:
! 4567: **
! 4568: ** foreach row1 in t1 do
! 4569: ** flag = 0
! 4570: ** foreach row2 in t2 do
! 4571: ** start:
! 4572: ** ...
! 4573: ** flag = 1
! 4574: ** end
! 4575: ** if flag==0 then
! 4576: ** move the row2 cursor to a null row
! 4577: ** goto start
! 4578: ** fi
! 4579: ** end
! 4580: **
! 4581: ** ORDER BY CLAUSE PROCESSING
! 4582: **
! 4583: ** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,
! 4584: ** if there is one. If there is no ORDER BY clause or if this routine
! 4585: ** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.
! 4586: **
! 4587: ** If an index can be used so that the natural output order of the table
! 4588: ** scan is correct for the ORDER BY clause, then that index is used and
! 4589: ** *ppOrderBy is set to NULL. This is an optimization that prevents an
! 4590: ** unnecessary sort of the result set if an index appropriate for the
! 4591: ** ORDER BY clause already exists.
! 4592: **
! 4593: ** If the where clause loops cannot be arranged to provide the correct
! 4594: ** output order, then the *ppOrderBy is unchanged.
! 4595: */
! 4596: WhereInfo *sqlite3WhereBegin(
! 4597: Parse *pParse, /* The parser context */
! 4598: SrcList *pTabList, /* A list of all tables to be scanned */
! 4599: Expr *pWhere, /* The WHERE clause */
! 4600: ExprList **ppOrderBy, /* An ORDER BY clause, or NULL */
! 4601: ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */
! 4602: u16 wctrlFlags /* One of the WHERE_* flags defined in sqliteInt.h */
! 4603: ){
! 4604: int i; /* Loop counter */
! 4605: int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */
! 4606: int nTabList; /* Number of elements in pTabList */
! 4607: WhereInfo *pWInfo; /* Will become the return value of this function */
! 4608: Vdbe *v = pParse->pVdbe; /* The virtual database engine */
! 4609: Bitmask notReady; /* Cursors that are not yet positioned */
! 4610: WhereMaskSet *pMaskSet; /* The expression mask set */
! 4611: WhereClause *pWC; /* Decomposition of the WHERE clause */
! 4612: struct SrcList_item *pTabItem; /* A single entry from pTabList */
! 4613: WhereLevel *pLevel; /* A single level in the pWInfo list */
! 4614: int iFrom; /* First unused FROM clause element */
! 4615: int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */
! 4616: sqlite3 *db; /* Database connection */
! 4617:
! 4618: /* The number of tables in the FROM clause is limited by the number of
! 4619: ** bits in a Bitmask
! 4620: */
! 4621: testcase( pTabList->nSrc==BMS );
! 4622: if( pTabList->nSrc>BMS ){
! 4623: sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);
! 4624: return 0;
! 4625: }
! 4626:
! 4627: /* This function normally generates a nested loop for all tables in
! 4628: ** pTabList. But if the WHERE_ONETABLE_ONLY flag is set, then we should
! 4629: ** only generate code for the first table in pTabList and assume that
! 4630: ** any cursors associated with subsequent tables are uninitialized.
! 4631: */
! 4632: nTabList = (wctrlFlags & WHERE_ONETABLE_ONLY) ? 1 : pTabList->nSrc;
! 4633:
! 4634: /* Allocate and initialize the WhereInfo structure that will become the
! 4635: ** return value. A single allocation is used to store the WhereInfo
! 4636: ** struct, the contents of WhereInfo.a[], the WhereClause structure
! 4637: ** and the WhereMaskSet structure. Since WhereClause contains an 8-byte
! 4638: ** field (type Bitmask) it must be aligned on an 8-byte boundary on
! 4639: ** some architectures. Hence the ROUND8() below.
! 4640: */
! 4641: db = pParse->db;
! 4642: nByteWInfo = ROUND8(sizeof(WhereInfo)+(nTabList-1)*sizeof(WhereLevel));
! 4643: pWInfo = sqlite3DbMallocZero(db,
! 4644: nByteWInfo +
! 4645: sizeof(WhereClause) +
! 4646: sizeof(WhereMaskSet)
! 4647: );
! 4648: if( db->mallocFailed ){
! 4649: sqlite3DbFree(db, pWInfo);
! 4650: pWInfo = 0;
! 4651: goto whereBeginError;
! 4652: }
! 4653: pWInfo->nLevel = nTabList;
! 4654: pWInfo->pParse = pParse;
! 4655: pWInfo->pTabList = pTabList;
! 4656: pWInfo->iBreak = sqlite3VdbeMakeLabel(v);
! 4657: pWInfo->pWC = pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo];
! 4658: pWInfo->wctrlFlags = wctrlFlags;
! 4659: pWInfo->savedNQueryLoop = pParse->nQueryLoop;
! 4660: pMaskSet = (WhereMaskSet*)&pWC[1];
! 4661:
! 4662: /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via
! 4663: ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */
! 4664: if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0;
! 4665:
! 4666: /* Split the WHERE clause into separate subexpressions where each
! 4667: ** subexpression is separated by an AND operator.
! 4668: */
! 4669: initMaskSet(pMaskSet);
! 4670: whereClauseInit(pWC, pParse, pMaskSet, wctrlFlags);
! 4671: sqlite3ExprCodeConstants(pParse, pWhere);
! 4672: whereSplit(pWC, pWhere, TK_AND); /* IMP: R-15842-53296 */
! 4673:
! 4674: /* Special case: a WHERE clause that is constant. Evaluate the
! 4675: ** expression and either jump over all of the code or fall thru.
! 4676: */
! 4677: if( pWhere && (nTabList==0 || sqlite3ExprIsConstantNotJoin(pWhere)) ){
! 4678: sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, SQLITE_JUMPIFNULL);
! 4679: pWhere = 0;
! 4680: }
! 4681:
! 4682: /* Assign a bit from the bitmask to every term in the FROM clause.
! 4683: **
! 4684: ** When assigning bitmask values to FROM clause cursors, it must be
! 4685: ** the case that if X is the bitmask for the N-th FROM clause term then
! 4686: ** the bitmask for all FROM clause terms to the left of the N-th term
! 4687: ** is (X-1). An expression from the ON clause of a LEFT JOIN can use
! 4688: ** its Expr.iRightJoinTable value to find the bitmask of the right table
! 4689: ** of the join. Subtracting one from the right table bitmask gives a
! 4690: ** bitmask for all tables to the left of the join. Knowing the bitmask
! 4691: ** for all tables to the left of a left join is important. Ticket #3015.
! 4692: **
! 4693: ** Configure the WhereClause.vmask variable so that bits that correspond
! 4694: ** to virtual table cursors are set. This is used to selectively disable
! 4695: ** the OR-to-IN transformation in exprAnalyzeOrTerm(). It is not helpful
! 4696: ** with virtual tables.
! 4697: **
! 4698: ** Note that bitmasks are created for all pTabList->nSrc tables in
! 4699: ** pTabList, not just the first nTabList tables. nTabList is normally
! 4700: ** equal to pTabList->nSrc but might be shortened to 1 if the
! 4701: ** WHERE_ONETABLE_ONLY flag is set.
! 4702: */
! 4703: assert( pWC->vmask==0 && pMaskSet->n==0 );
! 4704: for(i=0; i<pTabList->nSrc; i++){
! 4705: createMask(pMaskSet, pTabList->a[i].iCursor);
! 4706: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 4707: if( ALWAYS(pTabList->a[i].pTab) && IsVirtual(pTabList->a[i].pTab) ){
! 4708: pWC->vmask |= ((Bitmask)1 << i);
! 4709: }
! 4710: #endif
! 4711: }
! 4712: #ifndef NDEBUG
! 4713: {
! 4714: Bitmask toTheLeft = 0;
! 4715: for(i=0; i<pTabList->nSrc; i++){
! 4716: Bitmask m = getMask(pMaskSet, pTabList->a[i].iCursor);
! 4717: assert( (m-1)==toTheLeft );
! 4718: toTheLeft |= m;
! 4719: }
! 4720: }
! 4721: #endif
! 4722:
! 4723: /* Analyze all of the subexpressions. Note that exprAnalyze() might
! 4724: ** add new virtual terms onto the end of the WHERE clause. We do not
! 4725: ** want to analyze these virtual terms, so start analyzing at the end
! 4726: ** and work forward so that the added virtual terms are never processed.
! 4727: */
! 4728: exprAnalyzeAll(pTabList, pWC);
! 4729: if( db->mallocFailed ){
! 4730: goto whereBeginError;
! 4731: }
! 4732:
! 4733: /* Check if the DISTINCT qualifier, if there is one, is redundant.
! 4734: ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to
! 4735: ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT.
! 4736: */
! 4737: if( pDistinct && isDistinctRedundant(pParse, pTabList, pWC, pDistinct) ){
! 4738: pDistinct = 0;
! 4739: pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE;
! 4740: }
! 4741:
! 4742: /* Chose the best index to use for each table in the FROM clause.
! 4743: **
! 4744: ** This loop fills in the following fields:
! 4745: **
! 4746: ** pWInfo->a[].pIdx The index to use for this level of the loop.
! 4747: ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx
! 4748: ** pWInfo->a[].nEq The number of == and IN constraints
! 4749: ** pWInfo->a[].iFrom Which term of the FROM clause is being coded
! 4750: ** pWInfo->a[].iTabCur The VDBE cursor for the database table
! 4751: ** pWInfo->a[].iIdxCur The VDBE cursor for the index
! 4752: ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term
! 4753: **
! 4754: ** This loop also figures out the nesting order of tables in the FROM
! 4755: ** clause.
! 4756: */
! 4757: notReady = ~(Bitmask)0;
! 4758: andFlags = ~0;
! 4759: WHERETRACE(("*** Optimizer Start ***\n"));
! 4760: for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
! 4761: WhereCost bestPlan; /* Most efficient plan seen so far */
! 4762: Index *pIdx; /* Index for FROM table at pTabItem */
! 4763: int j; /* For looping over FROM tables */
! 4764: int bestJ = -1; /* The value of j */
! 4765: Bitmask m; /* Bitmask value for j or bestJ */
! 4766: int isOptimal; /* Iterator for optimal/non-optimal search */
! 4767: int nUnconstrained; /* Number tables without INDEXED BY */
! 4768: Bitmask notIndexed; /* Mask of tables that cannot use an index */
! 4769:
! 4770: memset(&bestPlan, 0, sizeof(bestPlan));
! 4771: bestPlan.rCost = SQLITE_BIG_DBL;
! 4772: WHERETRACE(("*** Begin search for loop %d ***\n", i));
! 4773:
! 4774: /* Loop through the remaining entries in the FROM clause to find the
! 4775: ** next nested loop. The loop tests all FROM clause entries
! 4776: ** either once or twice.
! 4777: **
! 4778: ** The first test is always performed if there are two or more entries
! 4779: ** remaining and never performed if there is only one FROM clause entry
! 4780: ** to choose from. The first test looks for an "optimal" scan. In
! 4781: ** this context an optimal scan is one that uses the same strategy
! 4782: ** for the given FROM clause entry as would be selected if the entry
! 4783: ** were used as the innermost nested loop. In other words, a table
! 4784: ** is chosen such that the cost of running that table cannot be reduced
! 4785: ** by waiting for other tables to run first. This "optimal" test works
! 4786: ** by first assuming that the FROM clause is on the inner loop and finding
! 4787: ** its query plan, then checking to see if that query plan uses any
! 4788: ** other FROM clause terms that are notReady. If no notReady terms are
! 4789: ** used then the "optimal" query plan works.
! 4790: **
! 4791: ** Note that the WhereCost.nRow parameter for an optimal scan might
! 4792: ** not be as small as it would be if the table really were the innermost
! 4793: ** join. The nRow value can be reduced by WHERE clause constraints
! 4794: ** that do not use indices. But this nRow reduction only happens if the
! 4795: ** table really is the innermost join.
! 4796: **
! 4797: ** The second loop iteration is only performed if no optimal scan
! 4798: ** strategies were found by the first iteration. This second iteration
! 4799: ** is used to search for the lowest cost scan overall.
! 4800: **
! 4801: ** Previous versions of SQLite performed only the second iteration -
! 4802: ** the next outermost loop was always that with the lowest overall
! 4803: ** cost. However, this meant that SQLite could select the wrong plan
! 4804: ** for scripts such as the following:
! 4805: **
! 4806: ** CREATE TABLE t1(a, b);
! 4807: ** CREATE TABLE t2(c, d);
! 4808: ** SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
! 4809: **
! 4810: ** The best strategy is to iterate through table t1 first. However it
! 4811: ** is not possible to determine this with a simple greedy algorithm.
! 4812: ** Since the cost of a linear scan through table t2 is the same
! 4813: ** as the cost of a linear scan through table t1, a simple greedy
! 4814: ** algorithm may choose to use t2 for the outer loop, which is a much
! 4815: ** costlier approach.
! 4816: */
! 4817: nUnconstrained = 0;
! 4818: notIndexed = 0;
! 4819: for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){
! 4820: Bitmask mask; /* Mask of tables not yet ready */
! 4821: for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
! 4822: int doNotReorder; /* True if this table should not be reordered */
! 4823: WhereCost sCost; /* Cost information from best[Virtual]Index() */
! 4824: ExprList *pOrderBy; /* ORDER BY clause for index to optimize */
! 4825: ExprList *pDist; /* DISTINCT clause for index to optimize */
! 4826:
! 4827: doNotReorder = (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
! 4828: if( j!=iFrom && doNotReorder ) break;
! 4829: m = getMask(pMaskSet, pTabItem->iCursor);
! 4830: if( (m & notReady)==0 ){
! 4831: if( j==iFrom ) iFrom++;
! 4832: continue;
! 4833: }
! 4834: mask = (isOptimal ? m : notReady);
! 4835: pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
! 4836: pDist = (i==0 ? pDistinct : 0);
! 4837: if( pTabItem->pIndex==0 ) nUnconstrained++;
! 4838:
! 4839: WHERETRACE(("=== trying table %d with isOptimal=%d ===\n",
! 4840: j, isOptimal));
! 4841: assert( pTabItem->pTab );
! 4842: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 4843: if( IsVirtual(pTabItem->pTab) ){
! 4844: sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
! 4845: bestVirtualIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
! 4846: &sCost, pp);
! 4847: }else
! 4848: #endif
! 4849: {
! 4850: bestBtreeIndex(pParse, pWC, pTabItem, mask, notReady, pOrderBy,
! 4851: pDist, &sCost);
! 4852: }
! 4853: assert( isOptimal || (sCost.used¬Ready)==0 );
! 4854:
! 4855: /* If an INDEXED BY clause is present, then the plan must use that
! 4856: ** index if it uses any index at all */
! 4857: assert( pTabItem->pIndex==0
! 4858: || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
! 4859: || sCost.plan.u.pIdx==pTabItem->pIndex );
! 4860:
! 4861: if( isOptimal && (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
! 4862: notIndexed |= m;
! 4863: }
! 4864:
! 4865: /* Conditions under which this table becomes the best so far:
! 4866: **
! 4867: ** (1) The table must not depend on other tables that have not
! 4868: ** yet run.
! 4869: **
! 4870: ** (2) A full-table-scan plan cannot supercede indexed plan unless
! 4871: ** the full-table-scan is an "optimal" plan as defined above.
! 4872: **
! 4873: ** (3) All tables have an INDEXED BY clause or this table lacks an
! 4874: ** INDEXED BY clause or this table uses the specific
! 4875: ** index specified by its INDEXED BY clause. This rule ensures
! 4876: ** that a best-so-far is always selected even if an impossible
! 4877: ** combination of INDEXED BY clauses are given. The error
! 4878: ** will be detected and relayed back to the application later.
! 4879: ** The NEVER() comes about because rule (2) above prevents
! 4880: ** An indexable full-table-scan from reaching rule (3).
! 4881: **
! 4882: ** (4) The plan cost must be lower than prior plans or else the
! 4883: ** cost must be the same and the number of rows must be lower.
! 4884: */
! 4885: if( (sCost.used¬Ready)==0 /* (1) */
! 4886: && (bestJ<0 || (notIndexed&m)!=0 /* (2) */
! 4887: || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
! 4888: || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
! 4889: && (nUnconstrained==0 || pTabItem->pIndex==0 /* (3) */
! 4890: || NEVER((sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
! 4891: && (bestJ<0 || sCost.rCost<bestPlan.rCost /* (4) */
! 4892: || (sCost.rCost<=bestPlan.rCost
! 4893: && sCost.plan.nRow<bestPlan.plan.nRow))
! 4894: ){
! 4895: WHERETRACE(("=== table %d is best so far"
! 4896: " with cost=%g and nRow=%g\n",
! 4897: j, sCost.rCost, sCost.plan.nRow));
! 4898: bestPlan = sCost;
! 4899: bestJ = j;
! 4900: }
! 4901: if( doNotReorder ) break;
! 4902: }
! 4903: }
! 4904: assert( bestJ>=0 );
! 4905: assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
! 4906: WHERETRACE(("*** Optimizer selects table %d for loop %d"
! 4907: " with cost=%g and nRow=%g\n",
! 4908: bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow));
! 4909: /* The ALWAYS() that follows was added to hush up clang scan-build */
! 4910: if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 && ALWAYS(ppOrderBy) ){
! 4911: *ppOrderBy = 0;
! 4912: }
! 4913: if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
! 4914: assert( pWInfo->eDistinct==0 );
! 4915: pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
! 4916: }
! 4917: andFlags &= bestPlan.plan.wsFlags;
! 4918: pLevel->plan = bestPlan.plan;
! 4919: testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
! 4920: testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
! 4921: if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
! 4922: pLevel->iIdxCur = pParse->nTab++;
! 4923: }else{
! 4924: pLevel->iIdxCur = -1;
! 4925: }
! 4926: notReady &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
! 4927: pLevel->iFrom = (u8)bestJ;
! 4928: if( bestPlan.plan.nRow>=(double)1 ){
! 4929: pParse->nQueryLoop *= bestPlan.plan.nRow;
! 4930: }
! 4931:
! 4932: /* Check that if the table scanned by this loop iteration had an
! 4933: ** INDEXED BY clause attached to it, that the named index is being
! 4934: ** used for the scan. If not, then query compilation has failed.
! 4935: ** Return an error.
! 4936: */
! 4937: pIdx = pTabList->a[bestJ].pIndex;
! 4938: if( pIdx ){
! 4939: if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
! 4940: sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
! 4941: goto whereBeginError;
! 4942: }else{
! 4943: /* If an INDEXED BY clause is used, the bestIndex() function is
! 4944: ** guaranteed to find the index specified in the INDEXED BY clause
! 4945: ** if it find an index at all. */
! 4946: assert( bestPlan.plan.u.pIdx==pIdx );
! 4947: }
! 4948: }
! 4949: }
! 4950: WHERETRACE(("*** Optimizer Finished ***\n"));
! 4951: if( pParse->nErr || db->mallocFailed ){
! 4952: goto whereBeginError;
! 4953: }
! 4954:
! 4955: /* If the total query only selects a single row, then the ORDER BY
! 4956: ** clause is irrelevant.
! 4957: */
! 4958: if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){
! 4959: *ppOrderBy = 0;
! 4960: }
! 4961:
! 4962: /* If the caller is an UPDATE or DELETE statement that is requesting
! 4963: ** to use a one-pass algorithm, determine if this is appropriate.
! 4964: ** The one-pass algorithm only works if the WHERE clause constraints
! 4965: ** the statement to update a single row.
! 4966: */
! 4967: assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
! 4968: if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
! 4969: pWInfo->okOnePass = 1;
! 4970: pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
! 4971: }
! 4972:
! 4973: /* Open all tables in the pTabList and any indices selected for
! 4974: ** searching those tables.
! 4975: */
! 4976: sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
! 4977: notReady = ~(Bitmask)0;
! 4978: pWInfo->nRowOut = (double)1;
! 4979: for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
! 4980: Table *pTab; /* Table to open */
! 4981: int iDb; /* Index of database containing table/index */
! 4982:
! 4983: pTabItem = &pTabList->a[pLevel->iFrom];
! 4984: pTab = pTabItem->pTab;
! 4985: pLevel->iTabCur = pTabItem->iCursor;
! 4986: pWInfo->nRowOut *= pLevel->plan.nRow;
! 4987: iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
! 4988: if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
! 4989: /* Do nothing */
! 4990: }else
! 4991: #ifndef SQLITE_OMIT_VIRTUALTABLE
! 4992: if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
! 4993: const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
! 4994: int iCur = pTabItem->iCursor;
! 4995: sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
! 4996: }else
! 4997: #endif
! 4998: if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
! 4999: && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){
! 5000: int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
! 5001: sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
! 5002: testcase( pTab->nCol==BMS-1 );
! 5003: testcase( pTab->nCol==BMS );
! 5004: if( !pWInfo->okOnePass && pTab->nCol<BMS ){
! 5005: Bitmask b = pTabItem->colUsed;
! 5006: int n = 0;
! 5007: for(; b; b=b>>1, n++){}
! 5008: sqlite3VdbeChangeP4(v, sqlite3VdbeCurrentAddr(v)-1,
! 5009: SQLITE_INT_TO_PTR(n), P4_INT32);
! 5010: assert( n<=pTab->nCol );
! 5011: }
! 5012: }else{
! 5013: sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
! 5014: }
! 5015: #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
! 5016: if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
! 5017: constructAutomaticIndex(pParse, pWC, pTabItem, notReady, pLevel);
! 5018: }else
! 5019: #endif
! 5020: if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
! 5021: Index *pIx = pLevel->plan.u.pIdx;
! 5022: KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
! 5023: int iIdxCur = pLevel->iIdxCur;
! 5024: assert( pIx->pSchema==pTab->pSchema );
! 5025: assert( iIdxCur>=0 );
! 5026: sqlite3VdbeAddOp4(v, OP_OpenRead, iIdxCur, pIx->tnum, iDb,
! 5027: (char*)pKey, P4_KEYINFO_HANDOFF);
! 5028: VdbeComment((v, "%s", pIx->zName));
! 5029: }
! 5030: sqlite3CodeVerifySchema(pParse, iDb);
! 5031: notReady &= ~getMask(pWC->pMaskSet, pTabItem->iCursor);
! 5032: }
! 5033: pWInfo->iTop = sqlite3VdbeCurrentAddr(v);
! 5034: if( db->mallocFailed ) goto whereBeginError;
! 5035:
! 5036: /* Generate the code to do the search. Each iteration of the for
! 5037: ** loop below generates code for a single nested loop of the VM
! 5038: ** program.
! 5039: */
! 5040: notReady = ~(Bitmask)0;
! 5041: for(i=0; i<nTabList; i++){
! 5042: pLevel = &pWInfo->a[i];
! 5043: explainOneScan(pParse, pTabList, pLevel, i, pLevel->iFrom, wctrlFlags);
! 5044: notReady = codeOneLoopStart(pWInfo, i, wctrlFlags, notReady, pWhere);
! 5045: pWInfo->iContinue = pLevel->addrCont;
! 5046: }
! 5047:
! 5048: #ifdef SQLITE_TEST /* For testing and debugging use only */
! 5049: /* Record in the query plan information about the current table
! 5050: ** and the index used to access it (if any). If the table itself
! 5051: ** is not used, its name is just '{}'. If no index is used
! 5052: ** the index is listed as "{}". If the primary key is used the
! 5053: ** index name is '*'.
! 5054: */
! 5055: for(i=0; i<nTabList; i++){
! 5056: char *z;
! 5057: int n;
! 5058: pLevel = &pWInfo->a[i];
! 5059: pTabItem = &pTabList->a[pLevel->iFrom];
! 5060: z = pTabItem->zAlias;
! 5061: if( z==0 ) z = pTabItem->pTab->zName;
! 5062: n = sqlite3Strlen30(z);
! 5063: if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){
! 5064: if( pLevel->plan.wsFlags & WHERE_IDX_ONLY ){
! 5065: memcpy(&sqlite3_query_plan[nQPlan], "{}", 2);
! 5066: nQPlan += 2;
! 5067: }else{
! 5068: memcpy(&sqlite3_query_plan[nQPlan], z, n);
! 5069: nQPlan += n;
! 5070: }
! 5071: sqlite3_query_plan[nQPlan++] = ' ';
! 5072: }
! 5073: testcase( pLevel->plan.wsFlags & WHERE_ROWID_EQ );
! 5074: testcase( pLevel->plan.wsFlags & WHERE_ROWID_RANGE );
! 5075: if( pLevel->plan.wsFlags & (WHERE_ROWID_EQ|WHERE_ROWID_RANGE) ){
! 5076: memcpy(&sqlite3_query_plan[nQPlan], "* ", 2);
! 5077: nQPlan += 2;
! 5078: }else if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
! 5079: n = sqlite3Strlen30(pLevel->plan.u.pIdx->zName);
! 5080: if( n+nQPlan < sizeof(sqlite3_query_plan)-2 ){
! 5081: memcpy(&sqlite3_query_plan[nQPlan], pLevel->plan.u.pIdx->zName, n);
! 5082: nQPlan += n;
! 5083: sqlite3_query_plan[nQPlan++] = ' ';
! 5084: }
! 5085: }else{
! 5086: memcpy(&sqlite3_query_plan[nQPlan], "{} ", 3);
! 5087: nQPlan += 3;
! 5088: }
! 5089: }
! 5090: while( nQPlan>0 && sqlite3_query_plan[nQPlan-1]==' ' ){
! 5091: sqlite3_query_plan[--nQPlan] = 0;
! 5092: }
! 5093: sqlite3_query_plan[nQPlan] = 0;
! 5094: nQPlan = 0;
! 5095: #endif /* SQLITE_TEST // Testing and debugging use only */
! 5096:
! 5097: /* Record the continuation address in the WhereInfo structure. Then
! 5098: ** clean up and return.
! 5099: */
! 5100: return pWInfo;
! 5101:
! 5102: /* Jump here if malloc fails */
! 5103: whereBeginError:
! 5104: if( pWInfo ){
! 5105: pParse->nQueryLoop = pWInfo->savedNQueryLoop;
! 5106: whereInfoFree(db, pWInfo);
! 5107: }
! 5108: return 0;
! 5109: }
! 5110:
! 5111: /*
! 5112: ** Generate the end of the WHERE loop. See comments on
! 5113: ** sqlite3WhereBegin() for additional information.
! 5114: */
! 5115: void sqlite3WhereEnd(WhereInfo *pWInfo){
! 5116: Parse *pParse = pWInfo->pParse;
! 5117: Vdbe *v = pParse->pVdbe;
! 5118: int i;
! 5119: WhereLevel *pLevel;
! 5120: SrcList *pTabList = pWInfo->pTabList;
! 5121: sqlite3 *db = pParse->db;
! 5122:
! 5123: /* Generate loop termination code.
! 5124: */
! 5125: sqlite3ExprCacheClear(pParse);
! 5126: for(i=pWInfo->nLevel-1; i>=0; i--){
! 5127: pLevel = &pWInfo->a[i];
! 5128: sqlite3VdbeResolveLabel(v, pLevel->addrCont);
! 5129: if( pLevel->op!=OP_Noop ){
! 5130: sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
! 5131: sqlite3VdbeChangeP5(v, pLevel->p5);
! 5132: }
! 5133: if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
! 5134: struct InLoop *pIn;
! 5135: int j;
! 5136: sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
! 5137: for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
! 5138: sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
! 5139: sqlite3VdbeAddOp2(v, OP_Next, pIn->iCur, pIn->addrInTop);
! 5140: sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
! 5141: }
! 5142: sqlite3DbFree(db, pLevel->u.in.aInLoop);
! 5143: }
! 5144: sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
! 5145: if( pLevel->iLeftJoin ){
! 5146: int addr;
! 5147: addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
! 5148: assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
! 5149: || (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 );
! 5150: if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
! 5151: sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
! 5152: }
! 5153: if( pLevel->iIdxCur>=0 ){
! 5154: sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
! 5155: }
! 5156: if( pLevel->op==OP_Return ){
! 5157: sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
! 5158: }else{
! 5159: sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrFirst);
! 5160: }
! 5161: sqlite3VdbeJumpHere(v, addr);
! 5162: }
! 5163: }
! 5164:
! 5165: /* The "break" point is here, just past the end of the outer loop.
! 5166: ** Set it.
! 5167: */
! 5168: sqlite3VdbeResolveLabel(v, pWInfo->iBreak);
! 5169:
! 5170: /* Close all of the cursors that were opened by sqlite3WhereBegin.
! 5171: */
! 5172: assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
! 5173: for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
! 5174: struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
! 5175: Table *pTab = pTabItem->pTab;
! 5176: assert( pTab!=0 );
! 5177: if( (pTab->tabFlags & TF_Ephemeral)==0
! 5178: && pTab->pSelect==0
! 5179: && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
! 5180: ){
! 5181: int ws = pLevel->plan.wsFlags;
! 5182: if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
! 5183: sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
! 5184: }
! 5185: if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
! 5186: sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
! 5187: }
! 5188: }
! 5189:
! 5190: /* If this scan uses an index, make code substitutions to read data
! 5191: ** from the index in preference to the table. Sometimes, this means
! 5192: ** the table need never be read from. This is a performance boost,
! 5193: ** as the vdbe level waits until the table is read before actually
! 5194: ** seeking the table cursor to the record corresponding to the current
! 5195: ** position in the index.
! 5196: **
! 5197: ** Calls to the code generator in between sqlite3WhereBegin and
! 5198: ** sqlite3WhereEnd will have created code that references the table
! 5199: ** directly. This loop scans all that code looking for opcodes
! 5200: ** that reference the table and converts them into opcodes that
! 5201: ** reference the index.
! 5202: */
! 5203: if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 && !db->mallocFailed){
! 5204: int k, j, last;
! 5205: VdbeOp *pOp;
! 5206: Index *pIdx = pLevel->plan.u.pIdx;
! 5207:
! 5208: assert( pIdx!=0 );
! 5209: pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
! 5210: last = sqlite3VdbeCurrentAddr(v);
! 5211: for(k=pWInfo->iTop; k<last; k++, pOp++){
! 5212: if( pOp->p1!=pLevel->iTabCur ) continue;
! 5213: if( pOp->opcode==OP_Column ){
! 5214: for(j=0; j<pIdx->nColumn; j++){
! 5215: if( pOp->p2==pIdx->aiColumn[j] ){
! 5216: pOp->p2 = j;
! 5217: pOp->p1 = pLevel->iIdxCur;
! 5218: break;
! 5219: }
! 5220: }
! 5221: assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
! 5222: || j<pIdx->nColumn );
! 5223: }else if( pOp->opcode==OP_Rowid ){
! 5224: pOp->p1 = pLevel->iIdxCur;
! 5225: pOp->opcode = OP_IdxRowid;
! 5226: }
! 5227: }
! 5228: }
! 5229: }
! 5230:
! 5231: /* Final cleanup
! 5232: */
! 5233: pParse->nQueryLoop = pWInfo->savedNQueryLoop;
! 5234: whereInfoFree(db, pWInfo);
! 5235: return;
! 5236: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to where.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src