1 /* 2 ** 2015-06-06 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. 14 ** 15 ** This file was split off from where.c on 2015-06-06 in order to reduce the 16 ** size of where.c and make it easier to edit. This file contains the routines 17 ** that actually generate the bulk of the WHERE loop code. The original where.c 18 ** file retains the code that does query planning and analysis. 19 */ 20 #include "sqliteInt.h" 21 #include "whereInt.h" 22 23 #ifndef SQLITE_OMIT_EXPLAIN 24 /* 25 ** This routine is a helper for explainIndexRange() below 26 ** 27 ** pStr holds the text of an expression that we are building up one term 28 ** at a time. This routine adds a new term to the end of the expression. 29 ** Terms are separated by AND so add the "AND" text for second and subsequent 30 ** terms only. 31 */ 32 static void explainAppendTerm( 33 StrAccum *pStr, /* The text expression being built */ 34 int iTerm, /* Index of this term. First is zero */ 35 const char *zColumn, /* Name of the column */ 36 const char *zOp /* Name of the operator */ 37 ){ 38 if( iTerm ) sqlite3StrAccumAppend(pStr, " AND ", 5); 39 sqlite3StrAccumAppendAll(pStr, zColumn); 40 sqlite3StrAccumAppend(pStr, zOp, 1); 41 sqlite3StrAccumAppend(pStr, "?", 1); 42 } 43 44 /* 45 ** Return the name of the i-th column of the pIdx index. 46 */ 47 static const char *explainIndexColumnName(Index *pIdx, int i){ 48 i = pIdx->aiColumn[i]; 49 if( i==XN_EXPR ) return "<expr>"; 50 if( i==XN_ROWID ) return "rowid"; 51 return pIdx->pTable->aCol[i].zName; 52 } 53 54 /* 55 ** Argument pLevel describes a strategy for scanning table pTab. This 56 ** function appends text to pStr that describes the subset of table 57 ** rows scanned by the strategy in the form of an SQL expression. 58 ** 59 ** For example, if the query: 60 ** 61 ** SELECT * FROM t1 WHERE a=1 AND b>2; 62 ** 63 ** is run and there is an index on (a, b), then this function returns a 64 ** string similar to: 65 ** 66 ** "a=? AND b>?" 67 */ 68 static void explainIndexRange(StrAccum *pStr, WhereLoop *pLoop){ 69 Index *pIndex = pLoop->u.btree.pIndex; 70 u16 nEq = pLoop->u.btree.nEq; 71 u16 nSkip = pLoop->nSkip; 72 int i, j; 73 74 if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return; 75 sqlite3StrAccumAppend(pStr, " (", 2); 76 for(i=0; i<nEq; i++){ 77 const char *z = explainIndexColumnName(pIndex, i); 78 if( i ) sqlite3StrAccumAppend(pStr, " AND ", 5); 79 sqlite3XPrintf(pStr, 0, i>=nSkip ? "%s=?" : "ANY(%s)", z); 80 } 81 82 j = i; 83 if( pLoop->wsFlags&WHERE_BTM_LIMIT ){ 84 const char *z = explainIndexColumnName(pIndex, i); 85 explainAppendTerm(pStr, i++, z, ">"); 86 } 87 if( pLoop->wsFlags&WHERE_TOP_LIMIT ){ 88 const char *z = explainIndexColumnName(pIndex, j); 89 explainAppendTerm(pStr, i, z, "<"); 90 } 91 sqlite3StrAccumAppend(pStr, ")", 1); 92 } 93 94 /* 95 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN 96 ** command, or if either SQLITE_DEBUG or SQLITE_ENABLE_STMT_SCANSTATUS was 97 ** defined at compile-time. If it is not a no-op, a single OP_Explain opcode 98 ** is added to the output to describe the table scan strategy in pLevel. 99 ** 100 ** If an OP_Explain opcode is added to the VM, its address is returned. 101 ** Otherwise, if no OP_Explain is coded, zero is returned. 102 */ 103 int sqlite3WhereExplainOneScan( 104 Parse *pParse, /* Parse context */ 105 SrcList *pTabList, /* Table list this loop refers to */ 106 WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */ 107 int iLevel, /* Value for "level" column of output */ 108 int iFrom, /* Value for "from" column of output */ 109 u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ 110 ){ 111 int ret = 0; 112 #if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS) 113 if( pParse->explain==2 ) 114 #endif 115 { 116 struct SrcList_item *pItem = &pTabList->a[pLevel->iFrom]; 117 Vdbe *v = pParse->pVdbe; /* VM being constructed */ 118 sqlite3 *db = pParse->db; /* Database handle */ 119 int iId = pParse->iSelectId; /* Select id (left-most output column) */ 120 int isSearch; /* True for a SEARCH. False for SCAN. */ 121 WhereLoop *pLoop; /* The controlling WhereLoop object */ 122 u32 flags; /* Flags that describe this loop */ 123 char *zMsg; /* Text to add to EQP output */ 124 StrAccum str; /* EQP output string */ 125 char zBuf[100]; /* Initial space for EQP output string */ 126 127 pLoop = pLevel->pWLoop; 128 flags = pLoop->wsFlags; 129 if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_ONETABLE_ONLY) ) return 0; 130 131 isSearch = (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 132 || ((flags&WHERE_VIRTUALTABLE)==0 && (pLoop->u.btree.nEq>0)) 133 || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX)); 134 135 sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH); 136 sqlite3StrAccumAppendAll(&str, isSearch ? "SEARCH" : "SCAN"); 137 if( pItem->pSelect ){ 138 sqlite3XPrintf(&str, 0, " SUBQUERY %d", pItem->iSelectId); 139 }else{ 140 sqlite3XPrintf(&str, 0, " TABLE %s", pItem->zName); 141 } 142 143 if( pItem->zAlias ){ 144 sqlite3XPrintf(&str, 0, " AS %s", pItem->zAlias); 145 } 146 if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){ 147 const char *zFmt = 0; 148 Index *pIdx; 149 150 assert( pLoop->u.btree.pIndex!=0 ); 151 pIdx = pLoop->u.btree.pIndex; 152 assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) ); 153 if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){ 154 if( isSearch ){ 155 zFmt = "PRIMARY KEY"; 156 } 157 }else if( flags & WHERE_PARTIALIDX ){ 158 zFmt = "AUTOMATIC PARTIAL COVERING INDEX"; 159 }else if( flags & WHERE_AUTO_INDEX ){ 160 zFmt = "AUTOMATIC COVERING INDEX"; 161 }else if( flags & WHERE_IDX_ONLY ){ 162 zFmt = "COVERING INDEX %s"; 163 }else{ 164 zFmt = "INDEX %s"; 165 } 166 if( zFmt ){ 167 sqlite3StrAccumAppend(&str, " USING ", 7); 168 sqlite3XPrintf(&str, 0, zFmt, pIdx->zName); 169 explainIndexRange(&str, pLoop); 170 } 171 }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){ 172 const char *zRangeOp; 173 if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){ 174 zRangeOp = "="; 175 }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){ 176 zRangeOp = ">? AND rowid<"; 177 }else if( flags&WHERE_BTM_LIMIT ){ 178 zRangeOp = ">"; 179 }else{ 180 assert( flags&WHERE_TOP_LIMIT); 181 zRangeOp = "<"; 182 } 183 sqlite3XPrintf(&str, 0, " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp); 184 } 185 #ifndef SQLITE_OMIT_VIRTUALTABLE 186 else if( (flags & WHERE_VIRTUALTABLE)!=0 ){ 187 sqlite3XPrintf(&str, 0, " VIRTUAL TABLE INDEX %d:%s", 188 pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr); 189 } 190 #endif 191 #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS 192 if( pLoop->nOut>=10 ){ 193 sqlite3XPrintf(&str, 0, " (~%llu rows)", sqlite3LogEstToInt(pLoop->nOut)); 194 }else{ 195 sqlite3StrAccumAppend(&str, " (~1 row)", 9); 196 } 197 #endif 198 zMsg = sqlite3StrAccumFinish(&str); 199 ret = sqlite3VdbeAddOp4(v, OP_Explain, iId, iLevel, iFrom, zMsg,P4_DYNAMIC); 200 } 201 return ret; 202 } 203 #endif /* SQLITE_OMIT_EXPLAIN */ 204 205 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS 206 /* 207 ** Configure the VM passed as the first argument with an 208 ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to 209 ** implement level pLvl. Argument pSrclist is a pointer to the FROM 210 ** clause that the scan reads data from. 211 ** 212 ** If argument addrExplain is not 0, it must be the address of an 213 ** OP_Explain instruction that describes the same loop. 214 */ 215 void sqlite3WhereAddScanStatus( 216 Vdbe *v, /* Vdbe to add scanstatus entry to */ 217 SrcList *pSrclist, /* FROM clause pLvl reads data from */ 218 WhereLevel *pLvl, /* Level to add scanstatus() entry for */ 219 int addrExplain /* Address of OP_Explain (or 0) */ 220 ){ 221 const char *zObj = 0; 222 WhereLoop *pLoop = pLvl->pWLoop; 223 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 && pLoop->u.btree.pIndex!=0 ){ 224 zObj = pLoop->u.btree.pIndex->zName; 225 }else{ 226 zObj = pSrclist->a[pLvl->iFrom].zName; 227 } 228 sqlite3VdbeScanStatus( 229 v, addrExplain, pLvl->addrBody, pLvl->addrVisit, pLoop->nOut, zObj 230 ); 231 } 232 #endif 233 234 235 /* 236 ** Disable a term in the WHERE clause. Except, do not disable the term 237 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON 238 ** or USING clause of that join. 239 ** 240 ** Consider the term t2.z='ok' in the following queries: 241 ** 242 ** (1) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok' 243 ** (2) SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok' 244 ** (3) SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok' 245 ** 246 ** The t2.z='ok' is disabled in the in (2) because it originates 247 ** in the ON clause. The term is disabled in (3) because it is not part 248 ** of a LEFT OUTER JOIN. In (1), the term is not disabled. 249 ** 250 ** Disabling a term causes that term to not be tested in the inner loop 251 ** of the join. Disabling is an optimization. When terms are satisfied 252 ** by indices, we disable them to prevent redundant tests in the inner 253 ** loop. We would get the correct results if nothing were ever disabled, 254 ** but joins might run a little slower. The trick is to disable as much 255 ** as we can without disabling too much. If we disabled in (1), we'd get 256 ** the wrong answer. See ticket #813. 257 ** 258 ** If all the children of a term are disabled, then that term is also 259 ** automatically disabled. In this way, terms get disabled if derived 260 ** virtual terms are tested first. For example: 261 ** 262 ** x GLOB 'abc*' AND x>='abc' AND x<'acd' 263 ** \___________/ \______/ \_____/ 264 ** parent child1 child2 265 ** 266 ** Only the parent term was in the original WHERE clause. The child1 267 ** and child2 terms were added by the LIKE optimization. If both of 268 ** the virtual child terms are valid, then testing of the parent can be 269 ** skipped. 270 ** 271 ** Usually the parent term is marked as TERM_CODED. But if the parent 272 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead. 273 ** The TERM_LIKECOND marking indicates that the term should be coded inside 274 ** a conditional such that is only evaluated on the second pass of a 275 ** LIKE-optimization loop, when scanning BLOBs instead of strings. 276 */ 277 static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){ 278 int nLoop = 0; 279 while( pTerm 280 && (pTerm->wtFlags & TERM_CODED)==0 281 && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin)) 282 && (pLevel->notReady & pTerm->prereqAll)==0 283 ){ 284 if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){ 285 pTerm->wtFlags |= TERM_LIKECOND; 286 }else{ 287 pTerm->wtFlags |= TERM_CODED; 288 } 289 if( pTerm->iParent<0 ) break; 290 pTerm = &pTerm->pWC->a[pTerm->iParent]; 291 pTerm->nChild--; 292 if( pTerm->nChild!=0 ) break; 293 nLoop++; 294 } 295 } 296 297 /* 298 ** Code an OP_Affinity opcode to apply the column affinity string zAff 299 ** to the n registers starting at base. 300 ** 301 ** As an optimization, SQLITE_AFF_BLOB entries (which are no-ops) at the 302 ** beginning and end of zAff are ignored. If all entries in zAff are 303 ** SQLITE_AFF_BLOB, then no code gets generated. 304 ** 305 ** This routine makes its own copy of zAff so that the caller is free 306 ** to modify zAff after this routine returns. 307 */ 308 static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){ 309 Vdbe *v = pParse->pVdbe; 310 if( zAff==0 ){ 311 assert( pParse->db->mallocFailed ); 312 return; 313 } 314 assert( v!=0 ); 315 316 /* Adjust base and n to skip over SQLITE_AFF_BLOB entries at the beginning 317 ** and end of the affinity string. 318 */ 319 while( n>0 && zAff[0]==SQLITE_AFF_BLOB ){ 320 n--; 321 base++; 322 zAff++; 323 } 324 while( n>1 && zAff[n-1]==SQLITE_AFF_BLOB ){ 325 n--; 326 } 327 328 /* Code the OP_Affinity opcode if there is anything left to do. */ 329 if( n>0 ){ 330 sqlite3VdbeAddOp2(v, OP_Affinity, base, n); 331 sqlite3VdbeChangeP4(v, -1, zAff, n); 332 sqlite3ExprCacheAffinityChange(pParse, base, n); 333 } 334 } 335 336 337 /* 338 ** Generate code for a single equality term of the WHERE clause. An equality 339 ** term can be either X=expr or X IN (...). pTerm is the term to be 340 ** coded. 341 ** 342 ** The current value for the constraint is left in register iReg. 343 ** 344 ** For a constraint of the form X=expr, the expression is evaluated and its 345 ** result is left on the stack. For constraints of the form X IN (...) 346 ** this routine sets up a loop that will iterate over all values of X. 347 */ 348 static int codeEqualityTerm( 349 Parse *pParse, /* The parsing context */ 350 WhereTerm *pTerm, /* The term of the WHERE clause to be coded */ 351 WhereLevel *pLevel, /* The level of the FROM clause we are working on */ 352 int iEq, /* Index of the equality term within this level */ 353 int bRev, /* True for reverse-order IN operations */ 354 int iTarget /* Attempt to leave results in this register */ 355 ){ 356 Expr *pX = pTerm->pExpr; 357 Vdbe *v = pParse->pVdbe; 358 int iReg; /* Register holding results */ 359 360 assert( iTarget>0 ); 361 if( pX->op==TK_EQ || pX->op==TK_IS ){ 362 iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget); 363 }else if( pX->op==TK_ISNULL ){ 364 iReg = iTarget; 365 sqlite3VdbeAddOp2(v, OP_Null, 0, iReg); 366 #ifndef SQLITE_OMIT_SUBQUERY 367 }else{ 368 int eType; 369 int iTab; 370 struct InLoop *pIn; 371 WhereLoop *pLoop = pLevel->pWLoop; 372 373 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 374 && pLoop->u.btree.pIndex!=0 375 && pLoop->u.btree.pIndex->aSortOrder[iEq] 376 ){ 377 testcase( iEq==0 ); 378 testcase( bRev ); 379 bRev = !bRev; 380 } 381 assert( pX->op==TK_IN ); 382 iReg = iTarget; 383 eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0); 384 if( eType==IN_INDEX_INDEX_DESC ){ 385 testcase( bRev ); 386 bRev = !bRev; 387 } 388 iTab = pX->iTable; 389 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); 390 VdbeCoverageIf(v, bRev); 391 VdbeCoverageIf(v, !bRev); 392 assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 ); 393 pLoop->wsFlags |= WHERE_IN_ABLE; 394 if( pLevel->u.in.nIn==0 ){ 395 pLevel->addrNxt = sqlite3VdbeMakeLabel(v); 396 } 397 pLevel->u.in.nIn++; 398 pLevel->u.in.aInLoop = 399 sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop, 400 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn); 401 pIn = pLevel->u.in.aInLoop; 402 if( pIn ){ 403 pIn += pLevel->u.in.nIn - 1; 404 pIn->iCur = iTab; 405 if( eType==IN_INDEX_ROWID ){ 406 pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iReg); 407 }else{ 408 pIn->addrInTop = sqlite3VdbeAddOp3(v, OP_Column, iTab, 0, iReg); 409 } 410 pIn->eEndLoopOp = bRev ? OP_PrevIfOpen : OP_NextIfOpen; 411 sqlite3VdbeAddOp1(v, OP_IsNull, iReg); VdbeCoverage(v); 412 }else{ 413 pLevel->u.in.nIn = 0; 414 } 415 #endif 416 } 417 disableTerm(pLevel, pTerm); 418 return iReg; 419 } 420 421 /* 422 ** Generate code that will evaluate all == and IN constraints for an 423 ** index scan. 424 ** 425 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c). 426 ** Suppose the WHERE clause is this: a==5 AND b IN (1,2,3) AND c>5 AND c<10 427 ** The index has as many as three equality constraints, but in this 428 ** example, the third "c" value is an inequality. So only two 429 ** constraints are coded. This routine will generate code to evaluate 430 ** a==5 and b IN (1,2,3). The current values for a and b will be stored 431 ** in consecutive registers and the index of the first register is returned. 432 ** 433 ** In the example above nEq==2. But this subroutine works for any value 434 ** of nEq including 0. If nEq==0, this routine is nearly a no-op. 435 ** The only thing it does is allocate the pLevel->iMem memory cell and 436 ** compute the affinity string. 437 ** 438 ** The nExtraReg parameter is 0 or 1. It is 0 if all WHERE clause constraints 439 ** are == or IN and are covered by the nEq. nExtraReg is 1 if there is 440 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that 441 ** occurs after the nEq quality constraints. 442 ** 443 ** This routine allocates a range of nEq+nExtraReg memory cells and returns 444 ** the index of the first memory cell in that range. The code that 445 ** calls this routine will use that memory range to store keys for 446 ** start and termination conditions of the loop. 447 ** key value of the loop. If one or more IN operators appear, then 448 ** this routine allocates an additional nEq memory cells for internal 449 ** use. 450 ** 451 ** Before returning, *pzAff is set to point to a buffer containing a 452 ** copy of the column affinity string of the index allocated using 453 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated 454 ** with equality constraints that use BLOB or NONE affinity are set to 455 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following: 456 ** 457 ** CREATE TABLE t1(a TEXT PRIMARY KEY, b); 458 ** SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b; 459 ** 460 ** In the example above, the index on t1(a) has TEXT affinity. But since 461 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity, 462 ** no conversion should be attempted before using a t2.b value as part of 463 ** a key to search the index. Hence the first byte in the returned affinity 464 ** string in this example would be set to SQLITE_AFF_BLOB. 465 */ 466 static int codeAllEqualityTerms( 467 Parse *pParse, /* Parsing context */ 468 WhereLevel *pLevel, /* Which nested loop of the FROM we are coding */ 469 int bRev, /* Reverse the order of IN operators */ 470 int nExtraReg, /* Number of extra registers to allocate */ 471 char **pzAff /* OUT: Set to point to affinity string */ 472 ){ 473 u16 nEq; /* The number of == or IN constraints to code */ 474 u16 nSkip; /* Number of left-most columns to skip */ 475 Vdbe *v = pParse->pVdbe; /* The vm under construction */ 476 Index *pIdx; /* The index being used for this loop */ 477 WhereTerm *pTerm; /* A single constraint term */ 478 WhereLoop *pLoop; /* The WhereLoop object */ 479 int j; /* Loop counter */ 480 int regBase; /* Base register */ 481 int nReg; /* Number of registers to allocate */ 482 char *zAff; /* Affinity string to return */ 483 484 /* This module is only called on query plans that use an index. */ 485 pLoop = pLevel->pWLoop; 486 assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 ); 487 nEq = pLoop->u.btree.nEq; 488 nSkip = pLoop->nSkip; 489 pIdx = pLoop->u.btree.pIndex; 490 assert( pIdx!=0 ); 491 492 /* Figure out how many memory cells we will need then allocate them. 493 */ 494 regBase = pParse->nMem + 1; 495 nReg = pLoop->u.btree.nEq + nExtraReg; 496 pParse->nMem += nReg; 497 498 zAff = sqlite3DbStrDup(pParse->db,sqlite3IndexAffinityStr(pParse->db,pIdx)); 499 if( !zAff ){ 500 pParse->db->mallocFailed = 1; 501 } 502 503 if( nSkip ){ 504 int iIdxCur = pLevel->iIdxCur; 505 sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur); 506 VdbeCoverageIf(v, bRev==0); 507 VdbeCoverageIf(v, bRev!=0); 508 VdbeComment((v, "begin skip-scan on %s", pIdx->zName)); 509 j = sqlite3VdbeAddOp0(v, OP_Goto); 510 pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLT:OP_SeekGT), 511 iIdxCur, 0, regBase, nSkip); 512 VdbeCoverageIf(v, bRev==0); 513 VdbeCoverageIf(v, bRev!=0); 514 sqlite3VdbeJumpHere(v, j); 515 for(j=0; j<nSkip; j++){ 516 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j); 517 testcase( pIdx->aiColumn[j]==XN_EXPR ); 518 VdbeComment((v, "%s", explainIndexColumnName(pIdx, j))); 519 } 520 } 521 522 /* Evaluate the equality constraints 523 */ 524 assert( zAff==0 || (int)strlen(zAff)>=nEq ); 525 for(j=nSkip; j<nEq; j++){ 526 int r1; 527 pTerm = pLoop->aLTerm[j]; 528 assert( pTerm!=0 ); 529 /* The following testcase is true for indices with redundant columns. 530 ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */ 531 testcase( (pTerm->wtFlags & TERM_CODED)!=0 ); 532 testcase( pTerm->wtFlags & TERM_VIRTUAL ); 533 r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j); 534 if( r1!=regBase+j ){ 535 if( nReg==1 ){ 536 sqlite3ReleaseTempReg(pParse, regBase); 537 regBase = r1; 538 }else{ 539 sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j); 540 } 541 } 542 testcase( pTerm->eOperator & WO_ISNULL ); 543 testcase( pTerm->eOperator & WO_IN ); 544 if( (pTerm->eOperator & (WO_ISNULL|WO_IN))==0 ){ 545 Expr *pRight = pTerm->pExpr->pRight; 546 if( (pTerm->wtFlags & TERM_IS)==0 && sqlite3ExprCanBeNull(pRight) ){ 547 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk); 548 VdbeCoverage(v); 549 } 550 if( zAff ){ 551 if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_BLOB ){ 552 zAff[j] = SQLITE_AFF_BLOB; 553 } 554 if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){ 555 zAff[j] = SQLITE_AFF_BLOB; 556 } 557 } 558 } 559 } 560 *pzAff = zAff; 561 return regBase; 562 } 563 564 /* 565 ** If the most recently coded instruction is a constant range contraint 566 ** that originated from the LIKE optimization, then change the P3 to be 567 ** pLoop->iLikeRepCntr and set P5. 568 ** 569 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range 570 ** expression: "x>='ABC' AND x<'abd'". But this requires that the range 571 ** scan loop run twice, once for strings and a second time for BLOBs. 572 ** The OP_String opcodes on the second pass convert the upper and lower 573 ** bound string contants to blobs. This routine makes the necessary changes 574 ** to the OP_String opcodes for that to happen. 575 */ 576 static void whereLikeOptimizationStringFixup( 577 Vdbe *v, /* prepared statement under construction */ 578 WhereLevel *pLevel, /* The loop that contains the LIKE operator */ 579 WhereTerm *pTerm /* The upper or lower bound just coded */ 580 ){ 581 if( pTerm->wtFlags & TERM_LIKEOPT ){ 582 VdbeOp *pOp; 583 assert( pLevel->iLikeRepCntr>0 ); 584 pOp = sqlite3VdbeGetOp(v, -1); 585 assert( pOp!=0 ); 586 assert( pOp->opcode==OP_String8 587 || pTerm->pWC->pWInfo->pParse->db->mallocFailed ); 588 pOp->p3 = pLevel->iLikeRepCntr; 589 pOp->p5 = 1; 590 } 591 } 592 593 594 /* 595 ** Generate code for the start of the iLevel-th loop in the WHERE clause 596 ** implementation described by pWInfo. 597 */ 598 Bitmask sqlite3WhereCodeOneLoopStart( 599 WhereInfo *pWInfo, /* Complete information about the WHERE clause */ 600 int iLevel, /* Which level of pWInfo->a[] should be coded */ 601 Bitmask notReady /* Which tables are currently available */ 602 ){ 603 int j, k; /* Loop counters */ 604 int iCur; /* The VDBE cursor for the table */ 605 int addrNxt; /* Where to jump to continue with the next IN case */ 606 int omitTable; /* True if we use the index only */ 607 int bRev; /* True if we need to scan in reverse order */ 608 WhereLevel *pLevel; /* The where level to be coded */ 609 WhereLoop *pLoop; /* The WhereLoop object being coded */ 610 WhereClause *pWC; /* Decomposition of the entire WHERE clause */ 611 WhereTerm *pTerm; /* A WHERE clause term */ 612 Parse *pParse; /* Parsing context */ 613 sqlite3 *db; /* Database connection */ 614 Vdbe *v; /* The prepared stmt under constructions */ 615 struct SrcList_item *pTabItem; /* FROM clause term being coded */ 616 int addrBrk; /* Jump here to break out of the loop */ 617 int addrCont; /* Jump here to continue with next cycle */ 618 int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ 619 int iReleaseReg = 0; /* Temp register to free before returning */ 620 621 pParse = pWInfo->pParse; 622 v = pParse->pVdbe; 623 pWC = &pWInfo->sWC; 624 db = pParse->db; 625 pLevel = &pWInfo->a[iLevel]; 626 pLoop = pLevel->pWLoop; 627 pTabItem = &pWInfo->pTabList->a[pLevel->iFrom]; 628 iCur = pTabItem->iCursor; 629 pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur); 630 bRev = (pWInfo->revMask>>iLevel)&1; 631 omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 632 && (pWInfo->wctrlFlags & WHERE_FORCE_TABLE)==0; 633 VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName)); 634 635 /* Create labels for the "break" and "continue" instructions 636 ** for the current loop. Jump to addrBrk to break out of a loop. 637 ** Jump to cont to go immediately to the next iteration of the 638 ** loop. 639 ** 640 ** When there is an IN operator, we also have a "addrNxt" label that 641 ** means to continue with the next IN value combination. When 642 ** there are no IN operators in the constraints, the "addrNxt" label 643 ** is the same as "addrBrk". 644 */ 645 addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(v); 646 addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(v); 647 648 /* If this is the right table of a LEFT OUTER JOIN, allocate and 649 ** initialize a memory cell that records if this table matches any 650 ** row of the left table of the join. 651 */ 652 if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){ 653 pLevel->iLeftJoin = ++pParse->nMem; 654 sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin); 655 VdbeComment((v, "init LEFT JOIN no-match flag")); 656 } 657 658 /* Special case of a FROM clause subquery implemented as a co-routine */ 659 if( pTabItem->fg.viaCoroutine ){ 660 int regYield = pTabItem->regReturn; 661 sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub); 662 pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); 663 VdbeCoverage(v); 664 VdbeComment((v, "next row of \"%s\"", pTabItem->pTab->zName)); 665 pLevel->op = OP_Goto; 666 }else 667 668 #ifndef SQLITE_OMIT_VIRTUALTABLE 669 if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){ 670 /* Case 1: The table is a virtual-table. Use the VFilter and VNext 671 ** to access the data. 672 */ 673 int iReg; /* P3 Value for OP_VFilter */ 674 int addrNotFound; 675 int nConstraint = pLoop->nLTerm; 676 677 sqlite3ExprCachePush(pParse); 678 iReg = sqlite3GetTempRange(pParse, nConstraint+2); 679 addrNotFound = pLevel->addrBrk; 680 for(j=0; j<nConstraint; j++){ 681 int iTarget = iReg+j+2; 682 pTerm = pLoop->aLTerm[j]; 683 if( pTerm==0 ) continue; 684 if( pTerm->eOperator & WO_IN ){ 685 codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget); 686 addrNotFound = pLevel->addrNxt; 687 }else{ 688 sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget); 689 } 690 } 691 sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg); 692 sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1); 693 sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg, 694 pLoop->u.vtab.idxStr, 695 pLoop->u.vtab.needFree ? P4_MPRINTF : P4_STATIC); 696 VdbeCoverage(v); 697 pLoop->u.vtab.needFree = 0; 698 for(j=0; j<nConstraint && j<16; j++){ 699 if( (pLoop->u.vtab.omitMask>>j)&1 ){ 700 disableTerm(pLevel, pLoop->aLTerm[j]); 701 } 702 } 703 pLevel->p1 = iCur; 704 pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext; 705 pLevel->p2 = sqlite3VdbeCurrentAddr(v); 706 sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2); 707 sqlite3ExprCachePop(pParse); 708 }else 709 #endif /* SQLITE_OMIT_VIRTUALTABLE */ 710 711 if( (pLoop->wsFlags & WHERE_IPK)!=0 712 && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0 713 ){ 714 /* Case 2: We can directly reference a single row using an 715 ** equality comparison against the ROWID field. Or 716 ** we reference multiple rows using a "rowid IN (...)" 717 ** construct. 718 */ 719 assert( pLoop->u.btree.nEq==1 ); 720 pTerm = pLoop->aLTerm[0]; 721 assert( pTerm!=0 ); 722 assert( pTerm->pExpr!=0 ); 723 assert( omitTable==0 ); 724 testcase( pTerm->wtFlags & TERM_VIRTUAL ); 725 iReleaseReg = ++pParse->nMem; 726 iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg); 727 if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg); 728 addrNxt = pLevel->addrNxt; 729 sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt); VdbeCoverage(v); 730 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg); 731 VdbeCoverage(v); 732 sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1); 733 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); 734 VdbeComment((v, "pk")); 735 pLevel->op = OP_Noop; 736 }else if( (pLoop->wsFlags & WHERE_IPK)!=0 737 && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0 738 ){ 739 /* Case 3: We have an inequality comparison against the ROWID field. 740 */ 741 int testOp = OP_Noop; 742 int start; 743 int memEndValue = 0; 744 WhereTerm *pStart, *pEnd; 745 746 assert( omitTable==0 ); 747 j = 0; 748 pStart = pEnd = 0; 749 if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++]; 750 if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++]; 751 assert( pStart!=0 || pEnd!=0 ); 752 if( bRev ){ 753 pTerm = pStart; 754 pStart = pEnd; 755 pEnd = pTerm; 756 } 757 if( pStart ){ 758 Expr *pX; /* The expression that defines the start bound */ 759 int r1, rTemp; /* Registers for holding the start boundary */ 760 761 /* The following constant maps TK_xx codes into corresponding 762 ** seek opcodes. It depends on a particular ordering of TK_xx 763 */ 764 const u8 aMoveOp[] = { 765 /* TK_GT */ OP_SeekGT, 766 /* TK_LE */ OP_SeekLE, 767 /* TK_LT */ OP_SeekLT, 768 /* TK_GE */ OP_SeekGE 769 }; 770 assert( TK_LE==TK_GT+1 ); /* Make sure the ordering.. */ 771 assert( TK_LT==TK_GT+2 ); /* ... of the TK_xx values... */ 772 assert( TK_GE==TK_GT+3 ); /* ... is correcct. */ 773 774 assert( (pStart->wtFlags & TERM_VNULL)==0 ); 775 testcase( pStart->wtFlags & TERM_VIRTUAL ); 776 pX = pStart->pExpr; 777 assert( pX!=0 ); 778 testcase( pStart->leftCursor!=iCur ); /* transitive constraints */ 779 r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp); 780 sqlite3VdbeAddOp3(v, aMoveOp[pX->op-TK_GT], iCur, addrBrk, r1); 781 VdbeComment((v, "pk")); 782 VdbeCoverageIf(v, pX->op==TK_GT); 783 VdbeCoverageIf(v, pX->op==TK_LE); 784 VdbeCoverageIf(v, pX->op==TK_LT); 785 VdbeCoverageIf(v, pX->op==TK_GE); 786 sqlite3ExprCacheAffinityChange(pParse, r1, 1); 787 sqlite3ReleaseTempReg(pParse, rTemp); 788 disableTerm(pLevel, pStart); 789 }else{ 790 sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk); 791 VdbeCoverageIf(v, bRev==0); 792 VdbeCoverageIf(v, bRev!=0); 793 } 794 if( pEnd ){ 795 Expr *pX; 796 pX = pEnd->pExpr; 797 assert( pX!=0 ); 798 assert( (pEnd->wtFlags & TERM_VNULL)==0 ); 799 testcase( pEnd->leftCursor!=iCur ); /* Transitive constraints */ 800 testcase( pEnd->wtFlags & TERM_VIRTUAL ); 801 memEndValue = ++pParse->nMem; 802 sqlite3ExprCode(pParse, pX->pRight, memEndValue); 803 if( pX->op==TK_LT || pX->op==TK_GT ){ 804 testOp = bRev ? OP_Le : OP_Ge; 805 }else{ 806 testOp = bRev ? OP_Lt : OP_Gt; 807 } 808 disableTerm(pLevel, pEnd); 809 } 810 start = sqlite3VdbeCurrentAddr(v); 811 pLevel->op = bRev ? OP_Prev : OP_Next; 812 pLevel->p1 = iCur; 813 pLevel->p2 = start; 814 assert( pLevel->p5==0 ); 815 if( testOp!=OP_Noop ){ 816 iRowidReg = ++pParse->nMem; 817 sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg); 818 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); 819 sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg); 820 VdbeCoverageIf(v, testOp==OP_Le); 821 VdbeCoverageIf(v, testOp==OP_Lt); 822 VdbeCoverageIf(v, testOp==OP_Ge); 823 VdbeCoverageIf(v, testOp==OP_Gt); 824 sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL); 825 } 826 }else if( pLoop->wsFlags & WHERE_INDEXED ){ 827 /* Case 4: A scan using an index. 828 ** 829 ** The WHERE clause may contain zero or more equality 830 ** terms ("==" or "IN" operators) that refer to the N 831 ** left-most columns of the index. It may also contain 832 ** inequality constraints (>, <, >= or <=) on the indexed 833 ** column that immediately follows the N equalities. Only 834 ** the right-most column can be an inequality - the rest must 835 ** use the "==" and "IN" operators. For example, if the 836 ** index is on (x,y,z), then the following clauses are all 837 ** optimized: 838 ** 839 ** x=5 840 ** x=5 AND y=10 841 ** x=5 AND y<10 842 ** x=5 AND y>5 AND y<10 843 ** x=5 AND y=5 AND z<=10 844 ** 845 ** The z<10 term of the following cannot be used, only 846 ** the x=5 term: 847 ** 848 ** x=5 AND z<10 849 ** 850 ** N may be zero if there are inequality constraints. 851 ** If there are no inequality constraints, then N is at 852 ** least one. 853 ** 854 ** This case is also used when there are no WHERE clause 855 ** constraints but an index is selected anyway, in order 856 ** to force the output order to conform to an ORDER BY. 857 */ 858 static const u8 aStartOp[] = { 859 0, 860 0, 861 OP_Rewind, /* 2: (!start_constraints && startEq && !bRev) */ 862 OP_Last, /* 3: (!start_constraints && startEq && bRev) */ 863 OP_SeekGT, /* 4: (start_constraints && !startEq && !bRev) */ 864 OP_SeekLT, /* 5: (start_constraints && !startEq && bRev) */ 865 OP_SeekGE, /* 6: (start_constraints && startEq && !bRev) */ 866 OP_SeekLE /* 7: (start_constraints && startEq && bRev) */ 867 }; 868 static const u8 aEndOp[] = { 869 OP_IdxGE, /* 0: (end_constraints && !bRev && !endEq) */ 870 OP_IdxGT, /* 1: (end_constraints && !bRev && endEq) */ 871 OP_IdxLE, /* 2: (end_constraints && bRev && !endEq) */ 872 OP_IdxLT, /* 3: (end_constraints && bRev && endEq) */ 873 }; 874 u16 nEq = pLoop->u.btree.nEq; /* Number of == or IN terms */ 875 int regBase; /* Base register holding constraint values */ 876 WhereTerm *pRangeStart = 0; /* Inequality constraint at range start */ 877 WhereTerm *pRangeEnd = 0; /* Inequality constraint at range end */ 878 int startEq; /* True if range start uses ==, >= or <= */ 879 int endEq; /* True if range end uses ==, >= or <= */ 880 int start_constraints; /* Start of range is constrained */ 881 int nConstraint; /* Number of constraint terms */ 882 Index *pIdx; /* The index we will be using */ 883 int iIdxCur; /* The VDBE cursor for the index */ 884 int nExtraReg = 0; /* Number of extra registers needed */ 885 int op; /* Instruction opcode */ 886 char *zStartAff; /* Affinity for start of range constraint */ 887 char cEndAff = 0; /* Affinity for end of range constraint */ 888 u8 bSeekPastNull = 0; /* True to seek past initial nulls */ 889 u8 bStopAtNull = 0; /* Add condition to terminate at NULLs */ 890 891 pIdx = pLoop->u.btree.pIndex; 892 iIdxCur = pLevel->iIdxCur; 893 assert( nEq>=pLoop->nSkip ); 894 895 /* If this loop satisfies a sort order (pOrderBy) request that 896 ** was passed to this function to implement a "SELECT min(x) ..." 897 ** query, then the caller will only allow the loop to run for 898 ** a single iteration. This means that the first row returned 899 ** should not have a NULL value stored in 'x'. If column 'x' is 900 ** the first one after the nEq equality constraints in the index, 901 ** this requires some special handling. 902 */ 903 assert( pWInfo->pOrderBy==0 904 || pWInfo->pOrderBy->nExpr==1 905 || (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 ); 906 if( (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)!=0 907 && pWInfo->nOBSat>0 908 && (pIdx->nKeyCol>nEq) 909 ){ 910 assert( pLoop->nSkip==0 ); 911 bSeekPastNull = 1; 912 nExtraReg = 1; 913 } 914 915 /* Find any inequality constraint terms for the start and end 916 ** of the range. 917 */ 918 j = nEq; 919 if( pLoop->wsFlags & WHERE_BTM_LIMIT ){ 920 pRangeStart = pLoop->aLTerm[j++]; 921 nExtraReg = 1; 922 /* Like optimization range constraints always occur in pairs */ 923 assert( (pRangeStart->wtFlags & TERM_LIKEOPT)==0 || 924 (pLoop->wsFlags & WHERE_TOP_LIMIT)!=0 ); 925 } 926 if( pLoop->wsFlags & WHERE_TOP_LIMIT ){ 927 pRangeEnd = pLoop->aLTerm[j++]; 928 nExtraReg = 1; 929 if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){ 930 assert( pRangeStart!=0 ); /* LIKE opt constraints */ 931 assert( pRangeStart->wtFlags & TERM_LIKEOPT ); /* occur in pairs */ 932 pLevel->iLikeRepCntr = ++pParse->nMem; 933 testcase( bRev ); 934 testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC ); 935 sqlite3VdbeAddOp2(v, OP_Integer, 936 bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC), 937 pLevel->iLikeRepCntr); 938 VdbeComment((v, "LIKE loop counter")); 939 pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v); 940 } 941 if( pRangeStart==0 942 && (j = pIdx->aiColumn[nEq])>=0 943 && pIdx->pTable->aCol[j].notNull==0 944 ){ 945 bSeekPastNull = 1; 946 } 947 } 948 assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 ); 949 950 /* Generate code to evaluate all constraint terms using == or IN 951 ** and store the values of those terms in an array of registers 952 ** starting at regBase. 953 */ 954 regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); 955 assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq ); 956 if( zStartAff ) cEndAff = zStartAff[nEq]; 957 addrNxt = pLevel->addrNxt; 958 959 /* If we are doing a reverse order scan on an ascending index, or 960 ** a forward order scan on a descending index, interchange the 961 ** start and end terms (pRangeStart and pRangeEnd). 962 */ 963 if( (nEq<pIdx->nKeyCol && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) 964 || (bRev && pIdx->nKeyCol==nEq) 965 ){ 966 SWAP(WhereTerm *, pRangeEnd, pRangeStart); 967 SWAP(u8, bSeekPastNull, bStopAtNull); 968 } 969 970 testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 ); 971 testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 ); 972 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 ); 973 testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 ); 974 startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE); 975 endEq = !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE); 976 start_constraints = pRangeStart || nEq>0; 977 978 /* Seek the index cursor to the start of the range. */ 979 nConstraint = nEq; 980 if( pRangeStart ){ 981 Expr *pRight = pRangeStart->pExpr->pRight; 982 sqlite3ExprCode(pParse, pRight, regBase+nEq); 983 whereLikeOptimizationStringFixup(v, pLevel, pRangeStart); 984 if( (pRangeStart->wtFlags & TERM_VNULL)==0 985 && sqlite3ExprCanBeNull(pRight) 986 ){ 987 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); 988 VdbeCoverage(v); 989 } 990 if( zStartAff ){ 991 if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_BLOB){ 992 /* Since the comparison is to be performed with no conversions 993 ** applied to the operands, set the affinity to apply to pRight to 994 ** SQLITE_AFF_BLOB. */ 995 zStartAff[nEq] = SQLITE_AFF_BLOB; 996 } 997 if( sqlite3ExprNeedsNoAffinityChange(pRight, zStartAff[nEq]) ){ 998 zStartAff[nEq] = SQLITE_AFF_BLOB; 999 } 1000 } 1001 nConstraint++; 1002 testcase( pRangeStart->wtFlags & TERM_VIRTUAL ); 1003 }else if( bSeekPastNull ){ 1004 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); 1005 nConstraint++; 1006 startEq = 0; 1007 start_constraints = 1; 1008 } 1009 codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff); 1010 op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev]; 1011 assert( op!=0 ); 1012 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); 1013 VdbeCoverage(v); 1014 VdbeCoverageIf(v, op==OP_Rewind); testcase( op==OP_Rewind ); 1015 VdbeCoverageIf(v, op==OP_Last); testcase( op==OP_Last ); 1016 VdbeCoverageIf(v, op==OP_SeekGT); testcase( op==OP_SeekGT ); 1017 VdbeCoverageIf(v, op==OP_SeekGE); testcase( op==OP_SeekGE ); 1018 VdbeCoverageIf(v, op==OP_SeekLE); testcase( op==OP_SeekLE ); 1019 VdbeCoverageIf(v, op==OP_SeekLT); testcase( op==OP_SeekLT ); 1020 1021 /* Load the value for the inequality constraint at the end of the 1022 ** range (if any). 1023 */ 1024 nConstraint = nEq; 1025 if( pRangeEnd ){ 1026 Expr *pRight = pRangeEnd->pExpr->pRight; 1027 sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); 1028 sqlite3ExprCode(pParse, pRight, regBase+nEq); 1029 whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd); 1030 if( (pRangeEnd->wtFlags & TERM_VNULL)==0 1031 && sqlite3ExprCanBeNull(pRight) 1032 ){ 1033 sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt); 1034 VdbeCoverage(v); 1035 } 1036 if( sqlite3CompareAffinity(pRight, cEndAff)!=SQLITE_AFF_BLOB 1037 && !sqlite3ExprNeedsNoAffinityChange(pRight, cEndAff) 1038 ){ 1039 codeApplyAffinity(pParse, regBase+nEq, 1, &cEndAff); 1040 } 1041 nConstraint++; 1042 testcase( pRangeEnd->wtFlags & TERM_VIRTUAL ); 1043 }else if( bStopAtNull ){ 1044 sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq); 1045 endEq = 0; 1046 nConstraint++; 1047 } 1048 sqlite3DbFree(db, zStartAff); 1049 1050 /* Top of the loop body */ 1051 pLevel->p2 = sqlite3VdbeCurrentAddr(v); 1052 1053 /* Check if the index cursor is past the end of the range. */ 1054 if( nConstraint ){ 1055 op = aEndOp[bRev*2 + endEq]; 1056 sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint); 1057 testcase( op==OP_IdxGT ); VdbeCoverageIf(v, op==OP_IdxGT ); 1058 testcase( op==OP_IdxGE ); VdbeCoverageIf(v, op==OP_IdxGE ); 1059 testcase( op==OP_IdxLT ); VdbeCoverageIf(v, op==OP_IdxLT ); 1060 testcase( op==OP_IdxLE ); VdbeCoverageIf(v, op==OP_IdxLE ); 1061 } 1062 1063 /* Seek the table cursor, if required */ 1064 disableTerm(pLevel, pRangeStart); 1065 disableTerm(pLevel, pRangeEnd); 1066 if( omitTable ){ 1067 /* pIdx is a covering index. No need to access the main table. */ 1068 }else if( HasRowid(pIdx->pTable) ){ 1069 iRowidReg = ++pParse->nMem; 1070 sqlite3VdbeAddOp2(v, OP_IdxRowid, iIdxCur, iRowidReg); 1071 sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg); 1072 if( pWInfo->eOnePass!=ONEPASS_OFF ){ 1073 sqlite3VdbeAddOp3(v, OP_NotExists, iCur, 0, iRowidReg); 1074 VdbeCoverage(v); 1075 }else{ 1076 sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg); /* Deferred seek */ 1077 } 1078 }else if( iCur!=iIdxCur ){ 1079 Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable); 1080 iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol); 1081 for(j=0; j<pPk->nKeyCol; j++){ 1082 k = sqlite3ColumnOfIndex(pIdx, pPk->aiColumn[j]); 1083 sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j); 1084 } 1085 sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont, 1086 iRowidReg, pPk->nKeyCol); VdbeCoverage(v); 1087 } 1088 1089 /* Record the instruction used to terminate the loop. Disable 1090 ** WHERE clause terms made redundant by the index range scan. 1091 */ 1092 if( pLoop->wsFlags & WHERE_ONEROW ){ 1093 pLevel->op = OP_Noop; 1094 }else if( bRev ){ 1095 pLevel->op = OP_Prev; 1096 }else{ 1097 pLevel->op = OP_Next; 1098 } 1099 pLevel->p1 = iIdxCur; 1100 pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0; 1101 if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){ 1102 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; 1103 }else{ 1104 assert( pLevel->p5==0 ); 1105 } 1106 }else 1107 1108 #ifndef SQLITE_OMIT_OR_OPTIMIZATION 1109 if( pLoop->wsFlags & WHERE_MULTI_OR ){ 1110 /* Case 5: Two or more separately indexed terms connected by OR 1111 ** 1112 ** Example: 1113 ** 1114 ** CREATE TABLE t1(a,b,c,d); 1115 ** CREATE INDEX i1 ON t1(a); 1116 ** CREATE INDEX i2 ON t1(b); 1117 ** CREATE INDEX i3 ON t1(c); 1118 ** 1119 ** SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13) 1120 ** 1121 ** In the example, there are three indexed terms connected by OR. 1122 ** The top of the loop looks like this: 1123 ** 1124 ** Null 1 # Zero the rowset in reg 1 1125 ** 1126 ** Then, for each indexed term, the following. The arguments to 1127 ** RowSetTest are such that the rowid of the current row is inserted 1128 ** into the RowSet. If it is already present, control skips the 1129 ** Gosub opcode and jumps straight to the code generated by WhereEnd(). 1130 ** 1131 ** sqlite3WhereBegin(<term>) 1132 ** RowSetTest # Insert rowid into rowset 1133 ** Gosub 2 A 1134 ** sqlite3WhereEnd() 1135 ** 1136 ** Following the above, code to terminate the loop. Label A, the target 1137 ** of the Gosub above, jumps to the instruction right after the Goto. 1138 ** 1139 ** Null 1 # Zero the rowset in reg 1 1140 ** Goto B # The loop is finished. 1141 ** 1142 ** A: <loop body> # Return data, whatever. 1143 ** 1144 ** Return 2 # Jump back to the Gosub 1145 ** 1146 ** B: <after the loop> 1147 ** 1148 ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then 1149 ** use an ephemeral index instead of a RowSet to record the primary 1150 ** keys of the rows we have already seen. 1151 ** 1152 */ 1153 WhereClause *pOrWc; /* The OR-clause broken out into subterms */ 1154 SrcList *pOrTab; /* Shortened table list or OR-clause generation */ 1155 Index *pCov = 0; /* Potential covering index (or NULL) */ 1156 int iCovCur = pParse->nTab++; /* Cursor used for index scans (if any) */ 1157 1158 int regReturn = ++pParse->nMem; /* Register used with OP_Gosub */ 1159 int regRowset = 0; /* Register for RowSet object */ 1160 int regRowid = 0; /* Register holding rowid */ 1161 int iLoopBody = sqlite3VdbeMakeLabel(v); /* Start of loop body */ 1162 int iRetInit; /* Address of regReturn init */ 1163 int untestedTerms = 0; /* Some terms not completely tested */ 1164 int ii; /* Loop counter */ 1165 u16 wctrlFlags; /* Flags for sub-WHERE clause */ 1166 Expr *pAndExpr = 0; /* An ".. AND (...)" expression */ 1167 Table *pTab = pTabItem->pTab; 1168 1169 pTerm = pLoop->aLTerm[0]; 1170 assert( pTerm!=0 ); 1171 assert( pTerm->eOperator & WO_OR ); 1172 assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); 1173 pOrWc = &pTerm->u.pOrInfo->wc; 1174 pLevel->op = OP_Return; 1175 pLevel->p1 = regReturn; 1176 1177 /* Set up a new SrcList in pOrTab containing the table being scanned 1178 ** by this loop in the a[0] slot and all notReady tables in a[1..] slots. 1179 ** This becomes the SrcList in the recursive call to sqlite3WhereBegin(). 1180 */ 1181 if( pWInfo->nLevel>1 ){ 1182 int nNotReady; /* The number of notReady tables */ 1183 struct SrcList_item *origSrc; /* Original list of tables */ 1184 nNotReady = pWInfo->nLevel - iLevel - 1; 1185 pOrTab = sqlite3StackAllocRaw(db, 1186 sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0])); 1187 if( pOrTab==0 ) return notReady; 1188 pOrTab->nAlloc = (u8)(nNotReady + 1); 1189 pOrTab->nSrc = pOrTab->nAlloc; 1190 memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem)); 1191 origSrc = pWInfo->pTabList->a; 1192 for(k=1; k<=nNotReady; k++){ 1193 memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k])); 1194 } 1195 }else{ 1196 pOrTab = pWInfo->pTabList; 1197 } 1198 1199 /* Initialize the rowset register to contain NULL. An SQL NULL is 1200 ** equivalent to an empty rowset. Or, create an ephemeral index 1201 ** capable of holding primary keys in the case of a WITHOUT ROWID. 1202 ** 1203 ** Also initialize regReturn to contain the address of the instruction 1204 ** immediately following the OP_Return at the bottom of the loop. This 1205 ** is required in a few obscure LEFT JOIN cases where control jumps 1206 ** over the top of the loop into the body of it. In this case the 1207 ** correct response for the end-of-loop code (the OP_Return) is to 1208 ** fall through to the next instruction, just as an OP_Next does if 1209 ** called on an uninitialized cursor. 1210 */ 1211 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ 1212 if( HasRowid(pTab) ){ 1213 regRowset = ++pParse->nMem; 1214 sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset); 1215 }else{ 1216 Index *pPk = sqlite3PrimaryKeyIndex(pTab); 1217 regRowset = pParse->nTab++; 1218 sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol); 1219 sqlite3VdbeSetP4KeyInfo(pParse, pPk); 1220 } 1221 regRowid = ++pParse->nMem; 1222 } 1223 iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn); 1224 1225 /* If the original WHERE clause is z of the form: (x1 OR x2 OR ...) AND y 1226 ** Then for every term xN, evaluate as the subexpression: xN AND z 1227 ** That way, terms in y that are factored into the disjunction will 1228 ** be picked up by the recursive calls to sqlite3WhereBegin() below. 1229 ** 1230 ** Actually, each subexpression is converted to "xN AND w" where w is 1231 ** the "interesting" terms of z - terms that did not originate in the 1232 ** ON or USING clause of a LEFT JOIN, and terms that are usable as 1233 ** indices. 1234 ** 1235 ** This optimization also only applies if the (x1 OR x2 OR ...) term 1236 ** is not contained in the ON clause of a LEFT JOIN. 1237 ** See ticket http://www.sqlite.org/src/info/f2369304e4 1238 */ 1239 if( pWC->nTerm>1 ){ 1240 int iTerm; 1241 for(iTerm=0; iTerm<pWC->nTerm; iTerm++){ 1242 Expr *pExpr = pWC->a[iTerm].pExpr; 1243 if( &pWC->a[iTerm] == pTerm ) continue; 1244 if( ExprHasProperty(pExpr, EP_FromJoin) ) continue; 1245 if( (pWC->a[iTerm].wtFlags & TERM_VIRTUAL)!=0 ) continue; 1246 if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue; 1247 testcase( pWC->a[iTerm].wtFlags & TERM_ORINFO ); 1248 pExpr = sqlite3ExprDup(db, pExpr, 0); 1249 pAndExpr = sqlite3ExprAnd(db, pAndExpr, pExpr); 1250 } 1251 if( pAndExpr ){ 1252 pAndExpr = sqlite3PExpr(pParse, TK_AND, 0, pAndExpr, 0); 1253 } 1254 } 1255 1256 /* Run a separate WHERE clause for each term of the OR clause. After 1257 ** eliminating duplicates from other WHERE clauses, the action for each 1258 ** sub-WHERE clause is to to invoke the main loop body as a subroutine. 1259 */ 1260 wctrlFlags = WHERE_OMIT_OPEN_CLOSE 1261 | WHERE_FORCE_TABLE 1262 | WHERE_ONETABLE_ONLY 1263 | WHERE_NO_AUTOINDEX; 1264 for(ii=0; ii<pOrWc->nTerm; ii++){ 1265 WhereTerm *pOrTerm = &pOrWc->a[ii]; 1266 if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){ 1267 WhereInfo *pSubWInfo; /* Info for single OR-term scan */ 1268 Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */ 1269 int jmp1 = 0; /* Address of jump operation */ 1270 if( pAndExpr && !ExprHasProperty(pOrExpr, EP_FromJoin) ){ 1271 pAndExpr->pLeft = pOrExpr; 1272 pOrExpr = pAndExpr; 1273 } 1274 /* Loop through table entries that match term pOrTerm. */ 1275 WHERETRACE(0xffff, ("Subplan for OR-clause:\n")); 1276 pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, 1277 wctrlFlags, iCovCur); 1278 assert( pSubWInfo || pParse->nErr || db->mallocFailed ); 1279 if( pSubWInfo ){ 1280 WhereLoop *pSubLoop; 1281 int addrExplain = sqlite3WhereExplainOneScan( 1282 pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0 1283 ); 1284 sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], addrExplain); 1285 1286 /* This is the sub-WHERE clause body. First skip over 1287 ** duplicate rows from prior sub-WHERE clauses, and record the 1288 ** rowid (or PRIMARY KEY) for the current row so that the same 1289 ** row will be skipped in subsequent sub-WHERE clauses. 1290 */ 1291 if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){ 1292 int r; 1293 int iSet = ((ii==pOrWc->nTerm-1)?-1:ii); 1294 if( HasRowid(pTab) ){ 1295 r = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iCur, regRowid, 0); 1296 jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0, 1297 r,iSet); 1298 VdbeCoverage(v); 1299 }else{ 1300 Index *pPk = sqlite3PrimaryKeyIndex(pTab); 1301 int nPk = pPk->nKeyCol; 1302 int iPk; 1303 1304 /* Read the PK into an array of temp registers. */ 1305 r = sqlite3GetTempRange(pParse, nPk); 1306 for(iPk=0; iPk<nPk; iPk++){ 1307 int iCol = pPk->aiColumn[iPk]; 1308 sqlite3ExprCodeGetColumnToReg(pParse, pTab, iCol, iCur, r+iPk); 1309 } 1310 1311 /* Check if the temp table already contains this key. If so, 1312 ** the row has already been included in the result set and 1313 ** can be ignored (by jumping past the Gosub below). Otherwise, 1314 ** insert the key into the temp table and proceed with processing 1315 ** the row. 1316 ** 1317 ** Use some of the same optimizations as OP_RowSetTest: If iSet 1318 ** is zero, assume that the key cannot already be present in 1319 ** the temp table. And if iSet is -1, assume that there is no 1320 ** need to insert the key into the temp table, as it will never 1321 ** be tested for. */ 1322 if( iSet ){ 1323 jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk); 1324 VdbeCoverage(v); 1325 } 1326 if( iSet>=0 ){ 1327 sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid); 1328 sqlite3VdbeAddOp3(v, OP_IdxInsert, regRowset, regRowid, 0); 1329 if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); 1330 } 1331 1332 /* Release the array of temp registers */ 1333 sqlite3ReleaseTempRange(pParse, r, nPk); 1334 } 1335 } 1336 1337 /* Invoke the main loop body as a subroutine */ 1338 sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody); 1339 1340 /* Jump here (skipping the main loop body subroutine) if the 1341 ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */ 1342 if( jmp1 ) sqlite3VdbeJumpHere(v, jmp1); 1343 1344 /* The pSubWInfo->untestedTerms flag means that this OR term 1345 ** contained one or more AND term from a notReady table. The 1346 ** terms from the notReady table could not be tested and will 1347 ** need to be tested later. 1348 */ 1349 if( pSubWInfo->untestedTerms ) untestedTerms = 1; 1350 1351 /* If all of the OR-connected terms are optimized using the same 1352 ** index, and the index is opened using the same cursor number 1353 ** by each call to sqlite3WhereBegin() made by this loop, it may 1354 ** be possible to use that index as a covering index. 1355 ** 1356 ** If the call to sqlite3WhereBegin() above resulted in a scan that 1357 ** uses an index, and this is either the first OR-connected term 1358 ** processed or the index is the same as that used by all previous 1359 ** terms, set pCov to the candidate covering index. Otherwise, set 1360 ** pCov to NULL to indicate that no candidate covering index will 1361 ** be available. 1362 */ 1363 pSubLoop = pSubWInfo->a[0].pWLoop; 1364 assert( (pSubLoop->wsFlags & WHERE_AUTO_INDEX)==0 ); 1365 if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0 1366 && (ii==0 || pSubLoop->u.btree.pIndex==pCov) 1367 && (HasRowid(pTab) || !IsPrimaryKeyIndex(pSubLoop->u.btree.pIndex)) 1368 ){ 1369 assert( pSubWInfo->a[0].iIdxCur==iCovCur ); 1370 pCov = pSubLoop->u.btree.pIndex; 1371 wctrlFlags |= WHERE_REOPEN_IDX; 1372 }else{ 1373 pCov = 0; 1374 } 1375 1376 /* Finish the loop through table entries that match term pOrTerm. */ 1377 sqlite3WhereEnd(pSubWInfo); 1378 } 1379 } 1380 } 1381 pLevel->u.pCovidx = pCov; 1382 if( pCov ) pLevel->iIdxCur = iCovCur; 1383 if( pAndExpr ){ 1384 pAndExpr->pLeft = 0; 1385 sqlite3ExprDelete(db, pAndExpr); 1386 } 1387 sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v)); 1388 sqlite3VdbeGoto(v, pLevel->addrBrk); 1389 sqlite3VdbeResolveLabel(v, iLoopBody); 1390 1391 if( pWInfo->nLevel>1 ) sqlite3StackFree(db, pOrTab); 1392 if( !untestedTerms ) disableTerm(pLevel, pTerm); 1393 }else 1394 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ 1395 1396 { 1397 /* Case 6: There is no usable index. We must do a complete 1398 ** scan of the entire table. 1399 */ 1400 static const u8 aStep[] = { OP_Next, OP_Prev }; 1401 static const u8 aStart[] = { OP_Rewind, OP_Last }; 1402 assert( bRev==0 || bRev==1 ); 1403 if( pTabItem->fg.isRecursive ){ 1404 /* Tables marked isRecursive have only a single row that is stored in 1405 ** a pseudo-cursor. No need to Rewind or Next such cursors. */ 1406 pLevel->op = OP_Noop; 1407 }else{ 1408 pLevel->op = aStep[bRev]; 1409 pLevel->p1 = iCur; 1410 pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); 1411 VdbeCoverageIf(v, bRev==0); 1412 VdbeCoverageIf(v, bRev!=0); 1413 pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; 1414 } 1415 } 1416 1417 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS 1418 pLevel->addrVisit = sqlite3VdbeCurrentAddr(v); 1419 #endif 1420 1421 /* Insert code to test every subexpression that can be completely 1422 ** computed using the current set of tables. 1423 */ 1424 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ 1425 Expr *pE; 1426 int skipLikeAddr = 0; 1427 testcase( pTerm->wtFlags & TERM_VIRTUAL ); 1428 testcase( pTerm->wtFlags & TERM_CODED ); 1429 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; 1430 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){ 1431 testcase( pWInfo->untestedTerms==0 1432 && (pWInfo->wctrlFlags & WHERE_ONETABLE_ONLY)!=0 ); 1433 pWInfo->untestedTerms = 1; 1434 continue; 1435 } 1436 pE = pTerm->pExpr; 1437 assert( pE!=0 ); 1438 if( pLevel->iLeftJoin && !ExprHasProperty(pE, EP_FromJoin) ){ 1439 continue; 1440 } 1441 if( pTerm->wtFlags & TERM_LIKECOND ){ 1442 assert( pLevel->iLikeRepCntr>0 ); 1443 skipLikeAddr = sqlite3VdbeAddOp1(v, OP_IfNot, pLevel->iLikeRepCntr); 1444 VdbeCoverage(v); 1445 } 1446 sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL); 1447 if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr); 1448 pTerm->wtFlags |= TERM_CODED; 1449 } 1450 1451 /* Insert code to test for implied constraints based on transitivity 1452 ** of the "==" operator. 1453 ** 1454 ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123" 1455 ** and we are coding the t1 loop and the t2 loop has not yet coded, 1456 ** then we cannot use the "t1.a=t2.b" constraint, but we can code 1457 ** the implied "t1.a=123" constraint. 1458 */ 1459 for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){ 1460 Expr *pE, *pEAlt; 1461 WhereTerm *pAlt; 1462 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; 1463 if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue; 1464 if( (pTerm->eOperator & WO_EQUIV)==0 ) continue; 1465 if( pTerm->leftCursor!=iCur ) continue; 1466 if( pLevel->iLeftJoin ) continue; 1467 pE = pTerm->pExpr; 1468 assert( !ExprHasProperty(pE, EP_FromJoin) ); 1469 assert( (pTerm->prereqRight & pLevel->notReady)!=0 ); 1470 pAlt = sqlite3WhereFindTerm(pWC, iCur, pTerm->u.leftColumn, notReady, 1471 WO_EQ|WO_IN|WO_IS, 0); 1472 if( pAlt==0 ) continue; 1473 if( pAlt->wtFlags & (TERM_CODED) ) continue; 1474 testcase( pAlt->eOperator & WO_EQ ); 1475 testcase( pAlt->eOperator & WO_IS ); 1476 testcase( pAlt->eOperator & WO_IN ); 1477 VdbeModuleComment((v, "begin transitive constraint")); 1478 pEAlt = sqlite3StackAllocRaw(db, sizeof(*pEAlt)); 1479 if( pEAlt ){ 1480 *pEAlt = *pAlt->pExpr; 1481 pEAlt->pLeft = pE->pLeft; 1482 sqlite3ExprIfFalse(pParse, pEAlt, addrCont, SQLITE_JUMPIFNULL); 1483 sqlite3StackFree(db, pEAlt); 1484 } 1485 } 1486 1487 /* For a LEFT OUTER JOIN, generate code that will record the fact that 1488 ** at least one row of the right table has matched the left table. 1489 */ 1490 if( pLevel->iLeftJoin ){ 1491 pLevel->addrFirst = sqlite3VdbeCurrentAddr(v); 1492 sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin); 1493 VdbeComment((v, "record LEFT JOIN hit")); 1494 sqlite3ExprCacheClear(pParse); 1495 for(pTerm=pWC->a, j=0; j<pWC->nTerm; j++, pTerm++){ 1496 testcase( pTerm->wtFlags & TERM_VIRTUAL ); 1497 testcase( pTerm->wtFlags & TERM_CODED ); 1498 if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; 1499 if( (pTerm->prereqAll & pLevel->notReady)!=0 ){ 1500 assert( pWInfo->untestedTerms ); 1501 continue; 1502 } 1503 assert( pTerm->pExpr ); 1504 sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL); 1505 pTerm->wtFlags |= TERM_CODED; 1506 } 1507 } 1508 1509 return pLevel->notReady; 1510 } 1511