src/wherecode.c

   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 /*
  26 ** Return the name of the i-th column of the pIdx index.
  27 */
  28 static const char *explainIndexColumnName(Index *pIdx, int i){
  29   i = pIdx->aiColumn[i];
  30   if( i==XN_EXPR ) return "<expr>";
  31   if( i==XN_ROWID ) return "rowid";
  32   return pIdx->pTable->aCol[i].zCnName;
  33 }
  34
  35 /*
  36 ** This routine is a helper for explainIndexRange() below
  37 **
  38 ** pStr holds the text of an expression that we are building up one term
  39 ** at a time.  This routine adds a new term to the end of the expression.
  40 ** Terms are separated by AND so add the "AND" text for second and subsequent
  41 ** terms only.
  42 */
  43 static void explainAppendTerm(
  44   StrAccum *pStr,             /* The text expression being built */
  45   Index *pIdx,                /* Index to read column names from */
  46   int nTerm,                  /* Number of terms */
  47   int iTerm,                  /* Zero-based index of first term. */
  48   int bAnd,                   /* Non-zero to append " AND " */
  49   const char *zOp             /* Name of the operator */
  50 ){
  51   int i;
  52
  53   assert( nTerm>=1 );
  54   if( bAnd ) sqlite3_str_append(pStr, " AND ", 5);
  55
  56   if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1);
  57   for(i=0; i<nTerm; i++){
  58     if( i ) sqlite3_str_append(pStr, ",", 1);
  59     sqlite3_str_appendall(pStr, explainIndexColumnName(pIdx, iTerm+i));
  60   }
  61   if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
  62
  63   sqlite3_str_append(pStr, zOp, 1);
  64
  65   if( nTerm>1 ) sqlite3_str_append(pStr, "(", 1);
  66   for(i=0; i<nTerm; i++){
  67     if( i ) sqlite3_str_append(pStr, ",", 1);
  68     sqlite3_str_append(pStr, "?", 1);
  69   }
  70   if( nTerm>1 ) sqlite3_str_append(pStr, ")", 1);
  71 }
  72
  73 /*
  74 ** Argument pLevel describes a strategy for scanning table pTab. This
  75 ** function appends text to pStr that describes the subset of table
  76 ** rows scanned by the strategy in the form of an SQL expression.
  77 **
  78 ** For example, if the query:
  79 **
  80 **   SELECT * FROM t1 WHERE a=1 AND b>2;
  81 **
  82 ** is run and there is an index on (a, b), then this function returns a
  83 ** string similar to:
  84 **
  85 **   "a=? AND b>?"
  86 */
  87 static void explainIndexRange(StrAccum *pStr, WhereLoop *pLoop){
  88   Index *pIndex = pLoop->u.btree.pIndex;
  89   u16 nEq = pLoop->u.btree.nEq;
  90   u16 nSkip = pLoop->nSkip;
  91   int i, j;
  92
  93   if( nEq==0 && (pLoop->wsFlags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))==0 ) return;
  94   sqlite3_str_append(pStr, " (", 2);
  95   for(i=0; i<nEq; i++){
  96     const char *z = explainIndexColumnName(pIndex, i);
  97     if( i ) sqlite3_str_append(pStr, " AND ", 5);
  98     sqlite3_str_appendf(pStr, i>=nSkip ? "%s=?" : "ANY(%s)", z);
  99   }
 100
 101   j = i;
 102   if( pLoop->wsFlags&WHERE_BTM_LIMIT ){
 103     explainAppendTerm(pStr, pIndex, pLoop->u.btree.nBtm, j, i, ">");
 104     i = 1;
 105   }
 106   if( pLoop->wsFlags&WHERE_TOP_LIMIT ){
 107     explainAppendTerm(pStr, pIndex, pLoop->u.btree.nTop, j, i, "<");
 108   }
 109   sqlite3_str_append(pStr, ")", 1);
 110 }
 111
 112 /*
 113 ** This function is a no-op unless currently processing an EXPLAIN QUERY PLAN
 114 ** command, or if stmt_scanstatus_v2() stats are enabled, or if SQLITE_DEBUG
 115 ** was defined at compile-time. If it is not a no-op, a single OP_Explain
 116 ** opcode is added to the output to describe the table scan strategy in pLevel.
 117 **
 118 ** If an OP_Explain opcode is added to the VM, its address is returned.
 119 ** Otherwise, if no OP_Explain is coded, zero is returned.
 120 */
 121 int sqlite3WhereExplainOneScan(
 122   Parse *pParse,                  /* Parse context */
 123   SrcList *pTabList,              /* Table list this loop refers to */
 124   WhereLevel *pLevel,             /* Scan to write OP_Explain opcode for */
 125   u16 wctrlFlags                  /* Flags passed to sqlite3WhereBegin() */
 126 ){
 127   int ret = 0;
 128 #if !defined(SQLITE_DEBUG)
 129   if( sqlite3ParseToplevel(pParse)->explain==2 || IS_STMT_SCANSTATUS(pParse->db) )
 130 #endif
 131   {
 132     SrcItem *pItem = &pTabList->a[pLevel->iFrom];
 133     Vdbe *v = pParse->pVdbe;      /* VM being constructed */
 134     sqlite3 *db = pParse->db;     /* Database handle */
 135     int isSearch;                 /* True for a SEARCH. False for SCAN. */
 136     WhereLoop *pLoop;             /* The controlling WhereLoop object */
 137     u32 flags;                    /* Flags that describe this loop */
 138     char *zMsg;                   /* Text to add to EQP output */
 139     StrAccum str;                 /* EQP output string */
 140     char zBuf[100];               /* Initial space for EQP output string */
 141
 142     pLoop = pLevel->pWLoop;
 143     flags = pLoop->wsFlags;
 144     if( (flags&WHERE_MULTI_OR) || (wctrlFlags&WHERE_OR_SUBCLAUSE) ) return 0;
 145
 146     isSearch = (flags&(WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0
 147             || ((flags&WHERE_VIRTUALTABLE)==0 && (pLoop->u.btree.nEq>0))
 148             || (wctrlFlags&(WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX));
 149
 150     sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
 151     str.printfFlags = SQLITE_PRINTF_INTERNAL;
 152     sqlite3_str_appendf(&str, "%s %S", isSearch ? "SEARCH" : "SCAN", pItem);
 153     if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){
 154       const char *zFmt = 0;
 155       Index *pIdx;
 156
 157       assert( pLoop->u.btree.pIndex!=0 );
 158       pIdx = pLoop->u.btree.pIndex;
 159       assert( !(flags&WHERE_AUTO_INDEX) || (flags&WHERE_IDX_ONLY) );
 160       if( !HasRowid(pItem->pTab) && IsPrimaryKeyIndex(pIdx) ){
 161         if( isSearch ){
 162           zFmt = "PRIMARY KEY";
 163         }
 164       }else if( flags & WHERE_PARTIALIDX ){
 165         zFmt = "AUTOMATIC PARTIAL COVERING INDEX";
 166       }else if( flags & WHERE_AUTO_INDEX ){
 167         zFmt = "AUTOMATIC COVERING INDEX";
 168       }else if( flags & WHERE_IDX_ONLY ){
 169         zFmt = "COVERING INDEX %s";
 170       }else{
 171         zFmt = "INDEX %s";
 172       }
 173       if( zFmt ){
 174         sqlite3_str_append(&str, " USING ", 7);
 175         sqlite3_str_appendf(&str, zFmt, pIdx->zName);
 176         explainIndexRange(&str, pLoop);
 177       }
 178     }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){
 179       char cRangeOp;
 180 #if 0  /* Better output, but breaks many tests */
 181       const Table *pTab = pItem->pTab;
 182       const char *zRowid = pTab->iPKey>=0 ? pTab->aCol[pTab->iPKey].zCnName:
 183                               "rowid";
 184 #else
 185       const char *zRowid = "rowid";
 186 #endif
 187       sqlite3_str_appendf(&str, " USING INTEGER PRIMARY KEY (%s", zRowid);
 188       if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){
 189         cRangeOp = '=';
 190       }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){
 191         sqlite3_str_appendf(&str, ">? AND %s", zRowid);
 192         cRangeOp = '<';
 193       }else if( flags&WHERE_BTM_LIMIT ){
 194         cRangeOp = '>';
 195       }else{
 196         assert( flags&WHERE_TOP_LIMIT);
 197         cRangeOp = '<';
 198       }
 199       sqlite3_str_appendf(&str, "%c?)", cRangeOp);
 200     }
 201 #ifndef SQLITE_OMIT_VIRTUALTABLE
 202     else if( (flags & WHERE_VIRTUALTABLE)!=0 ){
 203       sqlite3_str_appendf(&str, " VIRTUAL TABLE INDEX %d:%s",
 204                   pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr);
 205     }
 206 #endif
 207     if( pItem->fg.jointype & JT_LEFT ){
 208       sqlite3_str_appendf(&str, " LEFT-JOIN");
 209     }
 210 #ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
 211     if( pLoop->nOut>=10 ){
 212       sqlite3_str_appendf(&str, " (~%llu rows)",
 213              sqlite3LogEstToInt(pLoop->nOut));
 214     }else{
 215       sqlite3_str_append(&str, " (~1 row)", 9);
 216     }
 217 #endif
 218     zMsg = sqlite3StrAccumFinish(&str);
 219     sqlite3ExplainBreakpoint("",zMsg);
 220     ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
 221                             pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
 222   }
 223   return ret;
 224 }
 225
 226 /*
 227 ** Add a single OP_Explain opcode that describes a Bloom filter.
 228 **
 229 ** Or if not processing EXPLAIN QUERY PLAN and not in a SQLITE_DEBUG and/or
 230 ** SQLITE_ENABLE_STMT_SCANSTATUS build, then OP_Explain opcodes are not
 231 ** required and this routine is a no-op.
 232 **
 233 ** If an OP_Explain opcode is added to the VM, its address is returned.
 234 ** Otherwise, if no OP_Explain is coded, zero is returned.
 235 */
 236 int sqlite3WhereExplainBloomFilter(
 237   const Parse *pParse,               /* Parse context */
 238   const WhereInfo *pWInfo,           /* WHERE clause */
 239   const WhereLevel *pLevel           /* Bloom filter on this level */
 240 ){
 241   int ret = 0;
 242   SrcItem *pItem = &pWInfo->pTabList->a[pLevel->iFrom];
 243   Vdbe *v = pParse->pVdbe;      /* VM being constructed */
 244   sqlite3 *db = pParse->db;     /* Database handle */
 245   char *zMsg;                   /* Text to add to EQP output */
 246   int i;                        /* Loop counter */
 247   WhereLoop *pLoop;             /* The where loop */
 248   StrAccum str;                 /* EQP output string */
 249   char zBuf[100];               /* Initial space for EQP output string */
 250
 251   sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH);
 252   str.printfFlags = SQLITE_PRINTF_INTERNAL;
 253   sqlite3_str_appendf(&str, "BLOOM FILTER ON %S (", pItem);
 254   pLoop = pLevel->pWLoop;
 255   if( pLoop->wsFlags & WHERE_IPK ){
 256     const Table *pTab = pItem->pTab;
 257     if( pTab->iPKey>=0 ){
 258       sqlite3_str_appendf(&str, "%s=?", pTab->aCol[pTab->iPKey].zCnName);
 259     }else{
 260       sqlite3_str_appendf(&str, "rowid=?");
 261     }
 262   }else{
 263     for(i=pLoop->nSkip; i<pLoop->u.btree.nEq; i++){
 264       const char *z = explainIndexColumnName(pLoop->u.btree.pIndex, i);
 265       if( i>pLoop->nSkip ) sqlite3_str_append(&str, " AND ", 5);
 266       sqlite3_str_appendf(&str, "%s=?", z);
 267     }
 268   }
 269   sqlite3_str_append(&str, ")", 1);
 270   zMsg = sqlite3StrAccumFinish(&str);
 271   ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v),
 272                           pParse->addrExplain, 0, zMsg,P4_DYNAMIC);
 273
 274   sqlite3VdbeScanStatus(v, sqlite3VdbeCurrentAddr(v)-1, 0, 0, 0, 0);
 275   return ret;
 276 }
 277 #endif /* SQLITE_OMIT_EXPLAIN */
 278
 279 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
 280 /*
 281 ** Configure the VM passed as the first argument with an
 282 ** sqlite3_stmt_scanstatus() entry corresponding to the scan used to
 283 ** implement level pLvl. Argument pSrclist is a pointer to the FROM
 284 ** clause that the scan reads data from.
 285 **
 286 ** If argument addrExplain is not 0, it must be the address of an
 287 ** OP_Explain instruction that describes the same loop.
 288 */
 289 void sqlite3WhereAddScanStatus(
 290   Vdbe *v,                        /* Vdbe to add scanstatus entry to */
 291   SrcList *pSrclist,              /* FROM clause pLvl reads data from */
 292   WhereLevel *pLvl,               /* Level to add scanstatus() entry for */
 293   int addrExplain                 /* Address of OP_Explain (or 0) */
 294 ){
 295   if( IS_STMT_SCANSTATUS( sqlite3VdbeDb(v) ) ){
 296     const char *zObj = 0;
 297     WhereLoop *pLoop = pLvl->pWLoop;
 298     int wsFlags = pLoop->wsFlags;
 299     int viaCoroutine = 0;
 300
 301     if( (wsFlags & WHERE_VIRTUALTABLE)==0  &&  pLoop->u.btree.pIndex!=0 ){
 302       zObj = pLoop->u.btree.pIndex->zName;
 303     }else{
 304       zObj = pSrclist->a[pLvl->iFrom].zName;
 305       viaCoroutine = pSrclist->a[pLvl->iFrom].fg.viaCoroutine;
 306     }
 307     sqlite3VdbeScanStatus(
 308         v, addrExplain, pLvl->addrBody, pLvl->addrVisit, pLoop->nOut, zObj
 309     );
 310
 311     if( viaCoroutine==0 ){
 312       if( (wsFlags & (WHERE_MULTI_OR|WHERE_AUTO_INDEX))==0 ){
 313         sqlite3VdbeScanStatusRange(v, addrExplain, -1, pLvl->iTabCur);
 314       }
 315       if( wsFlags & WHERE_INDEXED ){
 316         sqlite3VdbeScanStatusRange(v, addrExplain, -1, pLvl->iIdxCur);
 317       }
 318     }else{
 319       int addr = pSrclist->a[pLvl->iFrom].addrFillSub;
 320       VdbeOp *pOp = sqlite3VdbeGetOp(v, addr-1);
 321       assert( sqlite3VdbeDb(v)->mallocFailed || pOp->opcode==OP_InitCoroutine );
 322       assert( sqlite3VdbeDb(v)->mallocFailed || pOp->p2>addr );
 323       sqlite3VdbeScanStatusRange(v, addrExplain, addr, pOp->p2-1);
 324     }
 325   }
 326 }
 327 #endif
 328
 329
 330 /*
 331 ** Disable a term in the WHERE clause.  Except, do not disable the term
 332 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
 333 ** or USING clause of that join.
 334 **
 335 ** Consider the term t2.z='ok' in the following queries:
 336 **
 337 **   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'
 338 **   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'
 339 **   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'
 340 **
 341 ** The t2.z='ok' is disabled in the in (2) because it originates
 342 ** in the ON clause.  The term is disabled in (3) because it is not part
 343 ** of a LEFT OUTER JOIN.  In (1), the term is not disabled.
 344 **
 345 ** Disabling a term causes that term to not be tested in the inner loop
 346 ** of the join.  Disabling is an optimization.  When terms are satisfied
 347 ** by indices, we disable them to prevent redundant tests in the inner
 348 ** loop.  We would get the correct results if nothing were ever disabled,
 349 ** but joins might run a little slower.  The trick is to disable as much
 350 ** as we can without disabling too much.  If we disabled in (1), we'd get
 351 ** the wrong answer.  See ticket #813.
 352 **
 353 ** If all the children of a term are disabled, then that term is also
 354 ** automatically disabled.  In this way, terms get disabled if derived
 355 ** virtual terms are tested first.  For example:
 356 **
 357 **      x GLOB 'abc*' AND x>='abc' AND x<'acd'
 358 **      \___________/     \______/     \_____/
 359 **         parent          child1       child2
 360 **
 361 ** Only the parent term was in the original WHERE clause.  The child1
 362 ** and child2 terms were added by the LIKE optimization.  If both of
 363 ** the virtual child terms are valid, then testing of the parent can be
 364 ** skipped.
 365 **
 366 ** Usually the parent term is marked as TERM_CODED.  But if the parent
 367 ** term was originally TERM_LIKE, then the parent gets TERM_LIKECOND instead.
 368 ** The TERM_LIKECOND marking indicates that the term should be coded inside
 369 ** a conditional such that is only evaluated on the second pass of a
 370 ** LIKE-optimization loop, when scanning BLOBs instead of strings.
 371 */
 372 static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){
 373   int nLoop = 0;
 374   assert( pTerm!=0 );
 375   while( (pTerm->wtFlags & TERM_CODED)==0
 376       && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_OuterON))
 377       && (pLevel->notReady & pTerm->prereqAll)==0
 378   ){
 379     if( nLoop && (pTerm->wtFlags & TERM_LIKE)!=0 ){
 380       pTerm->wtFlags |= TERM_LIKECOND;
 381     }else{
 382       pTerm->wtFlags |= TERM_CODED;
 383     }
 384 #ifdef WHERETRACE_ENABLED
 385     if( (sqlite3WhereTrace & 0x4001)==0x4001 ){
 386       sqlite3DebugPrintf("DISABLE-");
 387       sqlite3WhereTermPrint(pTerm, (int)(pTerm - (pTerm->pWC->a)));
 388     }
 389 #endif
 390     if( pTerm->iParent<0 ) break;
 391     pTerm = &pTerm->pWC->a[pTerm->iParent];
 392     assert( pTerm!=0 );
 393     pTerm->nChild--;
 394     if( pTerm->nChild!=0 ) break;
 395     nLoop++;
 396   }
 397 }
 398
 399 /*
 400 ** Code an OP_Affinity opcode to apply the column affinity string zAff
 401 ** to the n registers starting at base.
 402 **
 403 ** As an optimization, SQLITE_AFF_BLOB and SQLITE_AFF_NONE entries (which
 404 ** are no-ops) at the beginning and end of zAff are ignored.  If all entries
 405 ** in zAff are SQLITE_AFF_BLOB or SQLITE_AFF_NONE, then no code gets generated.
 406 **
 407 ** This routine makes its own copy of zAff so that the caller is free
 408 ** to modify zAff after this routine returns.
 409 */
 410 static void codeApplyAffinity(Parse *pParse, int base, int n, char *zAff){
 411   Vdbe *v = pParse->pVdbe;
 412   if( zAff==0 ){
 413     assert( pParse->db->mallocFailed );
 414     return;
 415   }
 416   assert( v!=0 );
 417
 418   /* Adjust base and n to skip over SQLITE_AFF_BLOB and SQLITE_AFF_NONE
 419   ** entries at the beginning and end of the affinity string.
 420   */
 421   assert( SQLITE_AFF_NONE<SQLITE_AFF_BLOB );
 422   while( n>0 && zAff[0]<=SQLITE_AFF_BLOB ){
 423     n--;
 424     base++;
 425     zAff++;
 426   }
 427   while( n>1 && zAff[n-1]<=SQLITE_AFF_BLOB ){
 428     n--;
 429   }
 430
 431   /* Code the OP_Affinity opcode if there is anything left to do. */
 432   if( n>0 ){
 433     sqlite3VdbeAddOp4(v, OP_Affinity, base, n, 0, zAff, n);
 434   }
 435 }
 436
 437 /*
 438 ** Expression pRight, which is the RHS of a comparison operation, is
 439 ** either a vector of n elements or, if n==1, a scalar expression.
 440 ** Before the comparison operation, affinity zAff is to be applied
 441 ** to the pRight values. This function modifies characters within the
 442 ** affinity string to SQLITE_AFF_BLOB if either:
 443 **
 444 **   * the comparison will be performed with no affinity, or
 445 **   * the affinity change in zAff is guaranteed not to change the value.
 446 */
 447 static void updateRangeAffinityStr(
 448   Expr *pRight,                   /* RHS of comparison */
 449   int n,                          /* Number of vector elements in comparison */
 450   char *zAff                      /* Affinity string to modify */
 451 ){
 452   int i;
 453   for(i=0; i<n; i++){
 454     Expr *p = sqlite3VectorFieldSubexpr(pRight, i);
 455     if( sqlite3CompareAffinity(p, zAff[i])==SQLITE_AFF_BLOB
 456      || sqlite3ExprNeedsNoAffinityChange(p, zAff[i])
 457     ){
 458       zAff[i] = SQLITE_AFF_BLOB;
 459     }
 460   }
 461 }
 462
 463
 464 /*
 465 ** pX is an expression of the form:  (vector) IN (SELECT ...)
 466 ** In other words, it is a vector IN operator with a SELECT clause on the
 467 ** LHS.  But not all terms in the vector are indexable and the terms might
 468 ** not be in the correct order for indexing.
 469 **
 470 ** This routine makes a copy of the input pX expression and then adjusts
 471 ** the vector on the LHS with corresponding changes to the SELECT so that
 472 ** the vector contains only index terms and those terms are in the correct
 473 ** order.  The modified IN expression is returned.  The caller is responsible
 474 ** for deleting the returned expression.
 475 **
 476 ** Example:
 477 **
 478 **    CREATE TABLE t1(a,b,c,d,e,f);
 479 **    CREATE INDEX t1x1 ON t1(e,c);
 480 **    SELECT * FROM t1 WHERE (a,b,c,d,e) IN (SELECT v,w,x,y,z FROM t2)
 481 **                           \_______________________________________/
 482 **                                     The pX expression
 483 **
 484 ** Since only columns e and c can be used with the index, in that order,
 485 ** the modified IN expression that is returned will be:
 486 **
 487 **        (e,c) IN (SELECT z,x FROM t2)
 488 **
 489 ** The reduced pX is different from the original (obviously) and thus is
 490 ** only used for indexing, to improve performance.  The original unaltered
 491 ** IN expression must also be run on each output row for correctness.
 492 */
 493 static Expr *removeUnindexableInClauseTerms(
 494   Parse *pParse,        /* The parsing context */
 495   int iEq,              /* Look at loop terms starting here */
 496   WhereLoop *pLoop,     /* The current loop */
 497   Expr *pX              /* The IN expression to be reduced */
 498 ){
 499   sqlite3 *db = pParse->db;
 500   Select *pSelect;            /* Pointer to the SELECT on the RHS */
 501   Expr *pNew;
 502   pNew = sqlite3ExprDup(db, pX, 0);
 503   if( db->mallocFailed==0 ){
 504     for(pSelect=pNew->x.pSelect; pSelect; pSelect=pSelect->pPrior){
 505       ExprList *pOrigRhs;         /* Original unmodified RHS */
 506       ExprList *pOrigLhs = 0;     /* Original unmodified LHS */
 507       ExprList *pRhs = 0;         /* New RHS after modifications */
 508       ExprList *pLhs = 0;         /* New LHS after mods */
 509       int i;                      /* Loop counter */
 510
 511       assert( ExprUseXSelect(pNew) );
 512       pOrigRhs = pSelect->pEList;
 513       assert( pNew->pLeft!=0 );
 514       assert( ExprUseXList(pNew->pLeft) );
 515       if( pSelect==pNew->x.pSelect ){
 516         pOrigLhs = pNew->pLeft->x.pList;
 517       }
 518       for(i=iEq; i<pLoop->nLTerm; i++){
 519         if( pLoop->aLTerm[i]->pExpr==pX ){
 520           int iField;
 521           assert( (pLoop->aLTerm[i]->eOperator & (WO_OR|WO_AND))==0 );
 522           iField = pLoop->aLTerm[i]->u.x.iField - 1;
 523           if( pOrigRhs->a[iField].pExpr==0 ) continue; /* Duplicate PK column */
 524           pRhs = sqlite3ExprListAppend(pParse, pRhs, pOrigRhs->a[iField].pExpr);
 525           pOrigRhs->a[iField].pExpr = 0;
 526           if( pOrigLhs ){
 527             assert( pOrigLhs->a[iField].pExpr!=0 );
 528             pLhs = sqlite3ExprListAppend(pParse,pLhs,pOrigLhs->a[iField].pExpr);
 529             pOrigLhs->a[iField].pExpr = 0;
 530           }
 531         }
 532       }
 533       sqlite3ExprListDelete(db, pOrigRhs);
 534       if( pOrigLhs ){
 535         sqlite3ExprListDelete(db, pOrigLhs);
 536         pNew->pLeft->x.pList = pLhs;
 537       }
 538       pSelect->pEList = pRhs;
 539       if( pLhs && pLhs->nExpr==1 ){
 540         /* Take care here not to generate a TK_VECTOR containing only a
 541         ** single value. Since the parser never creates such a vector, some
 542         ** of the subroutines do not handle this case.  */
 543         Expr *p = pLhs->a[0].pExpr;
 544         pLhs->a[0].pExpr = 0;
 545         sqlite3ExprDelete(db, pNew->pLeft);
 546         pNew->pLeft = p;
 547       }
 548       if( pSelect->pOrderBy ){
 549         /* If the SELECT statement has an ORDER BY clause, zero the
 550         ** iOrderByCol variables. These are set to non-zero when an
 551         ** ORDER BY term exactly matches one of the terms of the
 552         ** result-set. Since the result-set of the SELECT statement may
 553         ** have been modified or reordered, these variables are no longer
 554         ** set correctly.  Since setting them is just an optimization,
 555         ** it's easiest just to zero them here.  */
 556         ExprList *pOrderBy = pSelect->pOrderBy;
 557         for(i=0; i<pOrderBy->nExpr; i++){
 558           pOrderBy->a[i].u.x.iOrderByCol = 0;
 559         }
 560       }
 561
 562 #if 0
 563       printf("For indexing, change the IN expr:\n");
 564       sqlite3TreeViewExpr(0, pX, 0);
 565       printf("Into:\n");
 566       sqlite3TreeViewExpr(0, pNew, 0);
 567 #endif
 568     }
 569   }
 570   return pNew;
 571 }
 572
 573
 574 /*
 575 ** Generate code for a single equality term of the WHERE clause.  An equality
 576 ** term can be either X=expr or X IN (...).   pTerm is the term to be
 577 ** coded.
 578 **
 579 ** The current value for the constraint is left in a register, the index
 580 ** of which is returned.  An attempt is made store the result in iTarget but
 581 ** this is only guaranteed for TK_ISNULL and TK_IN constraints.  If the
 582 ** constraint is a TK_EQ or TK_IS, then the current value might be left in
 583 ** some other register and it is the caller's responsibility to compensate.
 584 **
 585 ** For a constraint of the form X=expr, the expression is evaluated in
 586 ** straight-line code.  For constraints of the form X IN (...)
 587 ** this routine sets up a loop that will iterate over all values of X.
 588 */
 589 static int codeEqualityTerm(
 590   Parse *pParse,      /* The parsing context */
 591   WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
 592   WhereLevel *pLevel, /* The level of the FROM clause we are working on */
 593   int iEq,            /* Index of the equality term within this level */
 594   int bRev,           /* True for reverse-order IN operations */
 595   int iTarget         /* Attempt to leave results in this register */
 596 ){
 597   Expr *pX = pTerm->pExpr;
 598   Vdbe *v = pParse->pVdbe;
 599   int iReg;                  /* Register holding results */
 600
 601   assert( pLevel->pWLoop->aLTerm[iEq]==pTerm );
 602   assert( iTarget>0 );
 603   if( pX->op==TK_EQ || pX->op==TK_IS ){
 604     iReg = sqlite3ExprCodeTarget(pParse, pX->pRight, iTarget);
 605   }else if( pX->op==TK_ISNULL ){
 606     iReg = iTarget;
 607     sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
 608 #ifndef SQLITE_OMIT_SUBQUERY
 609   }else{
 610     int eType = IN_INDEX_NOOP;
 611     int iTab;
 612     struct InLoop *pIn;
 613     WhereLoop *pLoop = pLevel->pWLoop;
 614     int i;
 615     int nEq = 0;
 616     int *aiMap = 0;
 617
 618     if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
 619       && pLoop->u.btree.pIndex!=0
 620       && pLoop->u.btree.pIndex->aSortOrder[iEq]
 621     ){
 622       testcase( iEq==0 );
 623       testcase( bRev );
 624       bRev = !bRev;
 625     }
 626     assert( pX->op==TK_IN );
 627     iReg = iTarget;
 628
 629     for(i=0; i<iEq; i++){
 630       if( pLoop->aLTerm[i] && pLoop->aLTerm[i]->pExpr==pX ){
 631         disableTerm(pLevel, pTerm);
 632         return iTarget;
 633       }
 634     }
 635     for(i=iEq;i<pLoop->nLTerm; i++){
 636       assert( pLoop->aLTerm[i]!=0 );
 637       if( pLoop->aLTerm[i]->pExpr==pX ) nEq++;
 638     }
 639
 640     iTab = 0;
 641     if( !ExprUseXSelect(pX) || pX->x.pSelect->pEList->nExpr==1 ){
 642       eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab);
 643     }else{
 644       Expr *pExpr = pTerm->pExpr;
 645       if( pExpr->iTable==0 || !ExprHasProperty(pExpr, EP_Subrtn) ){
 646         sqlite3 *db = pParse->db;
 647         pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX);
 648         if( !db->mallocFailed ){
 649           aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq);
 650           eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap,&iTab);
 651           pExpr->iTable = iTab;
 652         }
 653         sqlite3ExprDelete(db, pX);
 654       }else{
 655         int n = sqlite3ExprVectorSize(pX->pLeft);
 656         aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*MAX(nEq,n));
 657         eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab);
 658       }
 659       pX = pExpr;
 660     }
 661
 662     if( eType==IN_INDEX_INDEX_DESC ){
 663       testcase( bRev );
 664       bRev = !bRev;
 665     }
 666     sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
 667     VdbeCoverageIf(v, bRev);
 668     VdbeCoverageIf(v, !bRev);
 669
 670     assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
 671     pLoop->wsFlags |= WHERE_IN_ABLE;
 672     if( pLevel->u.in.nIn==0 ){
 673       pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
 674     }
 675     if( iEq>0 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)==0 ){
 676       pLoop->wsFlags |= WHERE_IN_EARLYOUT;
 677     }
 678
 679     i = pLevel->u.in.nIn;
 680     pLevel->u.in.nIn += nEq;
 681     pLevel->u.in.aInLoop =
 682        sqlite3WhereRealloc(pTerm->pWC->pWInfo,
 683                            pLevel->u.in.aInLoop,
 684                            sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
 685     pIn = pLevel->u.in.aInLoop;
 686     if( pIn ){
 687       int iMap = 0;               /* Index in aiMap[] */
 688       pIn += i;
 689       for(i=iEq;i<pLoop->nLTerm; i++){
 690         if( pLoop->aLTerm[i]->pExpr==pX ){
 691           int iOut = iReg + i - iEq;
 692           if( eType==IN_INDEX_ROWID ){
 693             pIn->addrInTop = sqlite3VdbeAddOp2(v, OP_Rowid, iTab, iOut);
 694           }else{
 695             int iCol = aiMap ? aiMap[iMap++] : 0;
 696             pIn->addrInTop = sqlite3VdbeAddOp3(v,OP_Column,iTab, iCol, iOut);
 697           }
 698           sqlite3VdbeAddOp1(v, OP_IsNull, iOut); VdbeCoverage(v);
 699           if( i==iEq ){
 700             pIn->iCur = iTab;
 701             pIn->eEndLoopOp = bRev ? OP_Prev : OP_Next;
 702             if( iEq>0 ){
 703               pIn->iBase = iReg - i;
 704               pIn->nPrefix = i;
 705             }else{
 706               pIn->nPrefix = 0;
 707             }
 708           }else{
 709             pIn->eEndLoopOp = OP_Noop;
 710           }
 711           pIn++;
 712         }
 713       }
 714       testcase( iEq>0
 715                 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)==0
 716                 && (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 );
 717       if( iEq>0
 718        && (pLoop->wsFlags & (WHERE_IN_SEEKSCAN|WHERE_VIRTUALTABLE))==0
 719       ){
 720         sqlite3VdbeAddOp3(v, OP_SeekHit, pLevel->iIdxCur, 0, iEq);
 721       }
 722     }else{
 723       pLevel->u.in.nIn = 0;
 724     }
 725     sqlite3DbFree(pParse->db, aiMap);
 726 #endif
 727   }
 728
 729   /* As an optimization, try to disable the WHERE clause term that is
 730   ** driving the index as it will always be true.  The correct answer is
 731   ** obtained regardless, but we might get the answer with fewer CPU cycles
 732   ** by omitting the term.
 733   **
 734   ** But do not disable the term unless we are certain that the term is
 735   ** not a transitive constraint.  For an example of where that does not
 736   ** work, see https://sqlite.org/forum/forumpost/eb8613976a (2021-05-04)
 737   */
 738   if( (pLevel->pWLoop->wsFlags & WHERE_TRANSCONS)==0
 739    || (pTerm->eOperator & WO_EQUIV)==0
 740   ){
 741     disableTerm(pLevel, pTerm);
 742   }
 743
 744   return iReg;
 745 }
 746
 747 /*
 748 ** Generate code that will evaluate all == and IN constraints for an
 749 ** index scan.
 750 **
 751 ** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).
 752 ** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10
 753 ** The index has as many as three equality constraints, but in this
 754 ** example, the third "c" value is an inequality.  So only two
 755 ** constraints are coded.  This routine will generate code to evaluate
 756 ** a==5 and b IN (1,2,3).  The current values for a and b will be stored
 757 ** in consecutive registers and the index of the first register is returned.
 758 **
 759 ** In the example above nEq==2.  But this subroutine works for any value
 760 ** of nEq including 0.  If nEq==0, this routine is nearly a no-op.
 761 ** The only thing it does is allocate the pLevel->iMem memory cell and
 762 ** compute the affinity string.
 763 **
 764 ** The nExtraReg parameter is 0 or 1.  It is 0 if all WHERE clause constraints
 765 ** are == or IN and are covered by the nEq.  nExtraReg is 1 if there is
 766 ** an inequality constraint (such as the "c>=5 AND c<10" in the example) that
 767 ** occurs after the nEq quality constraints.
 768 **
 769 ** This routine allocates a range of nEq+nExtraReg memory cells and returns
 770 ** the index of the first memory cell in that range. The code that
 771 ** calls this routine will use that memory range to store keys for
 772 ** start and termination conditions of the loop.
 773 ** key value of the loop.  If one or more IN operators appear, then
 774 ** this routine allocates an additional nEq memory cells for internal
 775 ** use.
 776 **
 777 ** Before returning, *pzAff is set to point to a buffer containing a
 778 ** copy of the column affinity string of the index allocated using
 779 ** sqlite3DbMalloc(). Except, entries in the copy of the string associated
 780 ** with equality constraints that use BLOB or NONE affinity are set to
 781 ** SQLITE_AFF_BLOB. This is to deal with SQL such as the following:
 782 **
 783 **   CREATE TABLE t1(a TEXT PRIMARY KEY, b);
 784 **   SELECT ... FROM t1 AS t2, t1 WHERE t1.a = t2.b;
 785 **
 786 ** In the example above, the index on t1(a) has TEXT affinity. But since
 787 ** the right hand side of the equality constraint (t2.b) has BLOB/NONE affinity,
 788 ** no conversion should be attempted before using a t2.b value as part of
 789 ** a key to search the index. Hence the first byte in the returned affinity
 790 ** string in this example would be set to SQLITE_AFF_BLOB.
 791 */
 792 static int codeAllEqualityTerms(
 793   Parse *pParse,        /* Parsing context */
 794   WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
 795   int bRev,             /* Reverse the order of IN operators */
 796   int nExtraReg,        /* Number of extra registers to allocate */
 797   char **pzAff          /* OUT: Set to point to affinity string */
 798 ){
 799   u16 nEq;                      /* The number of == or IN constraints to code */
 800   u16 nSkip;                    /* Number of left-most columns to skip */
 801   Vdbe *v = pParse->pVdbe;      /* The vm under construction */
 802   Index *pIdx;                  /* The index being used for this loop */
 803   WhereTerm *pTerm;             /* A single constraint term */
 804   WhereLoop *pLoop;             /* The WhereLoop object */
 805   int j;                        /* Loop counter */
 806   int regBase;                  /* Base register */
 807   int nReg;                     /* Number of registers to allocate */
 808   char *zAff;                   /* Affinity string to return */
 809
 810   /* This module is only called on query plans that use an index. */
 811   pLoop = pLevel->pWLoop;
 812   assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
 813   nEq = pLoop->u.btree.nEq;
 814   nSkip = pLoop->nSkip;
 815   pIdx = pLoop->u.btree.pIndex;
 816   assert( pIdx!=0 );
 817
 818   /* Figure out how many memory cells we will need then allocate them.
 819   */
 820   regBase = pParse->nMem + 1;
 821   nReg = nEq + nExtraReg;
 822   pParse->nMem += nReg;
 823
 824   zAff = sqlite3DbStrDup(pParse->db,sqlite3IndexAffinityStr(pParse->db,pIdx));
 825   assert( zAff!=0 || pParse->db->mallocFailed );
 826
 827   if( nSkip ){
 828     int iIdxCur = pLevel->iIdxCur;
 829     sqlite3VdbeAddOp3(v, OP_Null, 0, regBase, regBase+nSkip-1);
 830     sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
 831     VdbeCoverageIf(v, bRev==0);
 832     VdbeCoverageIf(v, bRev!=0);
 833     VdbeComment((v, "begin skip-scan on %s", pIdx->zName));
 834     j = sqlite3VdbeAddOp0(v, OP_Goto);
 835     assert( pLevel->addrSkip==0 );
 836     pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLT:OP_SeekGT),
 837                             iIdxCur, 0, regBase, nSkip);
 838     VdbeCoverageIf(v, bRev==0);
 839     VdbeCoverageIf(v, bRev!=0);
 840     sqlite3VdbeJumpHere(v, j);
 841     for(j=0; j<nSkip; j++){
 842       sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
 843       testcase( pIdx->aiColumn[j]==XN_EXPR );
 844       VdbeComment((v, "%s", explainIndexColumnName(pIdx, j)));
 845     }
 846   }
 847
 848   /* Evaluate the equality constraints
 849   */
 850   assert( zAff==0 || (int)strlen(zAff)>=nEq );
 851   for(j=nSkip; j<nEq; j++){
 852     int r1;
 853     pTerm = pLoop->aLTerm[j];
 854     assert( pTerm!=0 );
 855     /* The following testcase is true for indices with redundant columns.
 856     ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
 857     testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
 858     testcase( pTerm->wtFlags & TERM_VIRTUAL );
 859     r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
 860     if( r1!=regBase+j ){
 861       if( nReg==1 ){
 862         sqlite3ReleaseTempReg(pParse, regBase);
 863         regBase = r1;
 864       }else{
 865         sqlite3VdbeAddOp2(v, OP_Copy, r1, regBase+j);
 866       }
 867     }
 868     if( pTerm->eOperator & WO_IN ){
 869       if( pTerm->pExpr->flags & EP_xIsSelect ){
 870         /* No affinity ever needs to be (or should be) applied to a value
 871         ** from the RHS of an "? IN (SELECT ...)" expression. The
 872         ** sqlite3FindInIndex() routine has already ensured that the
 873         ** affinity of the comparison has been applied to the value.  */
 874         if( zAff ) zAff[j] = SQLITE_AFF_BLOB;
 875       }
 876     }else if( (pTerm->eOperator & WO_ISNULL)==0 ){
 877       Expr *pRight = pTerm->pExpr->pRight;
 878       if( (pTerm->wtFlags & TERM_IS)==0 && sqlite3ExprCanBeNull(pRight) ){
 879         sqlite3VdbeAddOp2(v, OP_IsNull, regBase+j, pLevel->addrBrk);
 880         VdbeCoverage(v);
 881       }
 882       if( pParse->nErr==0 ){
 883         assert( pParse->db->mallocFailed==0 );
 884         if( sqlite3CompareAffinity(pRight, zAff[j])==SQLITE_AFF_BLOB ){
 885           zAff[j] = SQLITE_AFF_BLOB;
 886         }
 887         if( sqlite3ExprNeedsNoAffinityChange(pRight, zAff[j]) ){
 888           zAff[j] = SQLITE_AFF_BLOB;
 889         }
 890       }
 891     }
 892   }
 893   *pzAff = zAff;
 894   return regBase;
 895 }
 896
 897 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
 898 /*
 899 ** If the most recently coded instruction is a constant range constraint
 900 ** (a string literal) that originated from the LIKE optimization, then
 901 ** set P3 and P5 on the OP_String opcode so that the string will be cast
 902 ** to a BLOB at appropriate times.
 903 **
 904 ** The LIKE optimization trys to evaluate "x LIKE 'abc%'" as a range
 905 ** expression: "x>='ABC' AND x<'abd'".  But this requires that the range
 906 ** scan loop run twice, once for strings and a second time for BLOBs.
 907 ** The OP_String opcodes on the second pass convert the upper and lower
 908 ** bound string constants to blobs.  This routine makes the necessary changes
 909 ** to the OP_String opcodes for that to happen.
 910 **
 911 ** Except, of course, if SQLITE_LIKE_DOESNT_MATCH_BLOBS is defined, then
 912 ** only the one pass through the string space is required, so this routine
 913 ** becomes a no-op.
 914 */
 915 static void whereLikeOptimizationStringFixup(
 916   Vdbe *v,                /* prepared statement under construction */
 917   WhereLevel *pLevel,     /* The loop that contains the LIKE operator */
 918   WhereTerm *pTerm        /* The upper or lower bound just coded */
 919 ){
 920   if( pTerm->wtFlags & TERM_LIKEOPT ){
 921     VdbeOp *pOp;
 922     assert( pLevel->iLikeRepCntr>0 );
 923     pOp = sqlite3VdbeGetLastOp(v);
 924     assert( pOp!=0 );
 925     assert( pOp->opcode==OP_String8
 926             || pTerm->pWC->pWInfo->pParse->db->mallocFailed );
 927     pOp->p3 = (int)(pLevel->iLikeRepCntr>>1);  /* Register holding counter */
 928     pOp->p5 = (u8)(pLevel->iLikeRepCntr&1);    /* ASC or DESC */
 929   }
 930 }
 931 #else
 932 # define whereLikeOptimizationStringFixup(A,B,C)
 933 #endif
 934
 935 #ifdef SQLITE_ENABLE_CURSOR_HINTS
 936 /*
 937 ** Information is passed from codeCursorHint() down to individual nodes of
 938 ** the expression tree (by sqlite3WalkExpr()) using an instance of this
 939 ** structure.
 940 */
 941 struct CCurHint {
 942   int iTabCur;    /* Cursor for the main table */
 943   int iIdxCur;    /* Cursor for the index, if pIdx!=0.  Unused otherwise */
 944   Index *pIdx;    /* The index used to access the table */
 945 };
 946
 947 /*
 948 ** This function is called for every node of an expression that is a candidate
 949 ** for a cursor hint on an index cursor.  For TK_COLUMN nodes that reference
 950 ** the table CCurHint.iTabCur, verify that the same column can be
 951 ** accessed through the index.  If it cannot, then set pWalker->eCode to 1.
 952 */
 953 static int codeCursorHintCheckExpr(Walker *pWalker, Expr *pExpr){
 954   struct CCurHint *pHint = pWalker->u.pCCurHint;
 955   assert( pHint->pIdx!=0 );
 956   if( pExpr->op==TK_COLUMN
 957    && pExpr->iTable==pHint->iTabCur
 958    && sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn)<0
 959   ){
 960     pWalker->eCode = 1;
 961   }
 962   return WRC_Continue;
 963 }
 964
 965 /*
 966 ** Test whether or not expression pExpr, which was part of a WHERE clause,
 967 ** should be included in the cursor-hint for a table that is on the rhs
 968 ** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the
 969 ** expression is not suitable.
 970 **
 971 ** An expression is unsuitable if it might evaluate to non NULL even if
 972 ** a TK_COLUMN node that does affect the value of the expression is set
 973 ** to NULL. For example:
 974 **
 975 **   col IS NULL
 976 **   col IS NOT NULL
 977 **   coalesce(col, 1)
 978 **   CASE WHEN col THEN 0 ELSE 1 END
 979 */
 980 static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){
 981   if( pExpr->op==TK_IS
 982    || pExpr->op==TK_ISNULL || pExpr->op==TK_ISNOT
 983    || pExpr->op==TK_NOTNULL || pExpr->op==TK_CASE
 984   ){
 985     pWalker->eCode = 1;
 986   }else if( pExpr->op==TK_FUNCTION ){
 987     int d1;
 988     char d2[4];
 989     if( 0==sqlite3IsLikeFunction(pWalker->pParse->db, pExpr, &d1, d2) ){
 990       pWalker->eCode = 1;
 991     }
 992   }
 993
 994   return WRC_Continue;
 995 }
 996
 997
 998 /*
 999 ** This function is called on every node of an expression tree used as an
1000 ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN
1001 ** that accesses any table other than the one identified by
1002 ** CCurHint.iTabCur, then do the following:
1003 **
1004 **   1) allocate a register and code an OP_Column instruction to read
1005 **      the specified column into the new register, and
1006 **
1007 **   2) transform the expression node to a TK_REGISTER node that reads
1008 **      from the newly populated register.
1009 **
1010 ** Also, if the node is a TK_COLUMN that does access the table identified
1011 ** by pCCurHint.iTabCur, and an index is being used (which we will
1012 ** know because CCurHint.pIdx!=0) then transform the TK_COLUMN into
1013 ** an access of the index rather than the original table.
1014 */
1015 static int codeCursorHintFixExpr(Walker *pWalker, Expr *pExpr){
1016   int rc = WRC_Continue;
1017   int reg;
1018   struct CCurHint *pHint = pWalker->u.pCCurHint;
1019   if( pExpr->op==TK_COLUMN ){
1020     if( pExpr->iTable!=pHint->iTabCur ){
1021       reg = ++pWalker->pParse->nMem;   /* Register for column value */
1022       reg = sqlite3ExprCodeTarget(pWalker->pParse, pExpr, reg);
1023       pExpr->op = TK_REGISTER;
1024       pExpr->iTable = reg;
1025     }else if( pHint->pIdx!=0 ){
1026       pExpr->iTable = pHint->iIdxCur;
1027       pExpr->iColumn = sqlite3TableColumnToIndex(pHint->pIdx, pExpr->iColumn);
1028       assert( pExpr->iColumn>=0 );
1029     }
1030   }else if( pExpr->pAggInfo ){
1031     rc = WRC_Prune;
1032     reg = ++pWalker->pParse->nMem;   /* Register for column value */
1033     reg = sqlite3ExprCodeTarget(pWalker->pParse, pExpr, reg);
1034     pExpr->op = TK_REGISTER;
1035     pExpr->iTable = reg;
1036   }else if( pExpr->op==TK_TRUEFALSE ){
1037     /* Do not walk disabled expressions.  tag-20230504-1 */
1038     return WRC_Prune;
1039   }
1040   return rc;
1041 }
1042
1043 /*
1044 ** Insert an OP_CursorHint instruction if it is appropriate to do so.
1045 */
1046 static void codeCursorHint(
1047   SrcItem *pTabItem,  /* FROM clause item */
1048   WhereInfo *pWInfo,    /* The where clause */
1049   WhereLevel *pLevel,   /* Which loop to provide hints for */
1050   WhereTerm *pEndRange  /* Hint this end-of-scan boundary term if not NULL */
1051 ){
1052   Parse *pParse = pWInfo->pParse;
1053   sqlite3 *db = pParse->db;
1054   Vdbe *v = pParse->pVdbe;
1055   Expr *pExpr = 0;
1056   WhereLoop *pLoop = pLevel->pWLoop;
1057   int iCur;
1058   WhereClause *pWC;
1059   WhereTerm *pTerm;
1060   int i, j;
1061   struct CCurHint sHint;
1062   Walker sWalker;
1063
1064   if( OptimizationDisabled(db, SQLITE_CursorHints) ) return;
1065   iCur = pLevel->iTabCur;
1066   assert( iCur==pWInfo->pTabList->a[pLevel->iFrom].iCursor );
1067   sHint.iTabCur = iCur;
1068   sHint.iIdxCur = pLevel->iIdxCur;
1069   sHint.pIdx = pLoop->u.btree.pIndex;
1070   memset(&sWalker, 0, sizeof(sWalker));
1071   sWalker.pParse = pParse;
1072   sWalker.u.pCCurHint = &sHint;
1073   pWC = &pWInfo->sWC;
1074   for(i=0; i<pWC->nBase; i++){
1075     pTerm = &pWC->a[i];
1076     if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
1077     if( pTerm->prereqAll & pLevel->notReady ) continue;
1078
1079     /* Any terms specified as part of the ON(...) clause for any LEFT
1080     ** JOIN for which the current table is not the rhs are omitted
1081     ** from the cursor-hint.
1082     **
1083     ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms
1084     ** that were specified as part of the WHERE clause must be excluded.
1085     ** This is to address the following:
1086     **
1087     **   SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL;
1088     **
1089     ** Say there is a single row in t2 that matches (t1.a=t2.b), but its
1090     ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is
1091     ** pushed down to the cursor, this row is filtered out, causing
1092     ** SQLite to synthesize a row of NULL values. Which does match the
1093     ** WHERE clause, and so the query returns a row. Which is incorrect.
1094     **
1095     ** For the same reason, WHERE terms such as:
1096     **
1097     **   WHERE 1 = (t2.c IS NULL)
1098     **
1099     ** are also excluded. See codeCursorHintIsOrFunction() for details.
1100     */
1101     if( pTabItem->fg.jointype & JT_LEFT ){
1102       Expr *pExpr = pTerm->pExpr;
1103       if( !ExprHasProperty(pExpr, EP_OuterON)
1104        || pExpr->w.iJoin!=pTabItem->iCursor
1105       ){
1106         sWalker.eCode = 0;
1107         sWalker.xExprCallback = codeCursorHintIsOrFunction;
1108         sqlite3WalkExpr(&sWalker, pTerm->pExpr);
1109         if( sWalker.eCode ) continue;
1110       }
1111     }else{
1112       if( ExprHasProperty(pTerm->pExpr, EP_OuterON) ) continue;
1113     }
1114
1115     /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize
1116     ** the cursor.  These terms are not needed as hints for a pure range
1117     ** scan (that has no == terms) so omit them. */
1118     if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){
1119       for(j=0; j<pLoop->nLTerm && pLoop->aLTerm[j]!=pTerm; j++){}
1120       if( j<pLoop->nLTerm ) continue;
1121     }
1122
1123     /* No subqueries or non-deterministic functions allowed */
1124     if( sqlite3ExprContainsSubquery(pTerm->pExpr) ) continue;
1125
1126     /* For an index scan, make sure referenced columns are actually in
1127     ** the index. */
1128     if( sHint.pIdx!=0 ){
1129       sWalker.eCode = 0;
1130       sWalker.xExprCallback = codeCursorHintCheckExpr;
1131       sqlite3WalkExpr(&sWalker, pTerm->pExpr);
1132       if( sWalker.eCode ) continue;
1133     }
1134
1135     /* If we survive all prior tests, that means this term is worth hinting */
1136     pExpr = sqlite3ExprAnd(pParse, pExpr, sqlite3ExprDup(db, pTerm->pExpr, 0));
1137   }
1138   if( pExpr!=0 ){
1139     sWalker.xExprCallback = codeCursorHintFixExpr;
1140     if( pParse->nErr==0 ) sqlite3WalkExpr(&sWalker, pExpr);
1141     sqlite3VdbeAddOp4(v, OP_CursorHint,
1142                       (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0,
1143                       (const char*)pExpr, P4_EXPR);
1144   }
1145 }
1146 #else
1147 # define codeCursorHint(A,B,C,D)  /* No-op */
1148 #endif /* SQLITE_ENABLE_CURSOR_HINTS */
1149
1150 /*
1151 ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains
1152 ** a rowid value just read from cursor iIdxCur, open on index pIdx. This
1153 ** function generates code to do a deferred seek of cursor iCur to the
1154 ** rowid stored in register iRowid.
1155 **
1156 ** Normally, this is just:
1157 **
1158 **   OP_DeferredSeek $iCur $iRowid
1159 **
1160 ** Which causes a seek on $iCur to the row with rowid $iRowid.
1161 **
1162 ** However, if the scan currently being coded is a branch of an OR-loop and
1163 ** the statement currently being coded is a SELECT, then additional information
1164 ** is added that might allow OP_Column to omit the seek and instead do its
1165 ** lookup on the index, thus avoiding an expensive seek operation.  To
1166 ** enable this optimization, the P3 of OP_DeferredSeek is set to iIdxCur
1167 ** and P4 is set to an array of integers containing one entry for each column
1168 ** in the table.  For each table column, if the column is the i'th
1169 ** column of the index, then the corresponding array entry is set to (i+1).
1170 ** If the column does not appear in the index at all, the array entry is set
1171 ** to 0.  The OP_Column opcode can check this array to see if the column it
1172 ** wants is in the index and if it is, it will substitute the index cursor
1173 ** and column number and continue with those new values, rather than seeking
1174 ** the table cursor.
1175 */
1176 static void codeDeferredSeek(
1177   WhereInfo *pWInfo,              /* Where clause context */
1178   Index *pIdx,                    /* Index scan is using */
1179   int iCur,                       /* Cursor for IPK b-tree */
1180   int iIdxCur                     /* Index cursor */
1181 ){
1182   Parse *pParse = pWInfo->pParse; /* Parse context */
1183   Vdbe *v = pParse->pVdbe;        /* Vdbe to generate code within */
1184
1185   assert( iIdxCur>0 );
1186   assert( pIdx->aiColumn[pIdx->nColumn-1]==-1 );
1187
1188   pWInfo->bDeferredSeek = 1;
1189   sqlite3VdbeAddOp3(v, OP_DeferredSeek, iIdxCur, 0, iCur);
1190   if( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))
1191    && DbMaskAllZero(sqlite3ParseToplevel(pParse)->writeMask)
1192   ){
1193     int i;
1194     Table *pTab = pIdx->pTable;
1195     u32 *ai = (u32*)sqlite3DbMallocZero(pParse->db, sizeof(u32)*(pTab->nCol+1));
1196     if( ai ){
1197       ai[0] = pTab->nCol;
1198       for(i=0; i<pIdx->nColumn-1; i++){
1199         int x1, x2;
1200         assert( pIdx->aiColumn[i]<pTab->nCol );
1201         x1 = pIdx->aiColumn[i];
1202         x2 = sqlite3TableColumnToStorage(pTab, x1);
1203         testcase( x1!=x2 );
1204         if( x1>=0 ) ai[x2+1] = i+1;
1205       }
1206       sqlite3VdbeChangeP4(v, -1, (char*)ai, P4_INTARRAY);
1207     }
1208   }
1209 }
1210
1211 /*
1212 ** If the expression passed as the second argument is a vector, generate
1213 ** code to write the first nReg elements of the vector into an array
1214 ** of registers starting with iReg.
1215 **
1216 ** If the expression is not a vector, then nReg must be passed 1. In
1217 ** this case, generate code to evaluate the expression and leave the
1218 ** result in register iReg.
1219 */
1220 static void codeExprOrVector(Parse *pParse, Expr *p, int iReg, int nReg){
1221   assert( nReg>0 );
1222   if( p && sqlite3ExprIsVector(p) ){
1223 #ifndef SQLITE_OMIT_SUBQUERY
1224     if( ExprUseXSelect(p) ){
1225       Vdbe *v = pParse->pVdbe;
1226       int iSelect;
1227       assert( p->op==TK_SELECT );
1228       iSelect = sqlite3CodeSubselect(pParse, p);
1229       sqlite3VdbeAddOp3(v, OP_Copy, iSelect, iReg, nReg-1);
1230     }else
1231 #endif
1232     {
1233       int i;
1234       const ExprList *pList;
1235       assert( ExprUseXList(p) );
1236       pList = p->x.pList;
1237       assert( nReg<=pList->nExpr );
1238       for(i=0; i<nReg; i++){
1239         sqlite3ExprCode(pParse, pList->a[i].pExpr, iReg+i);
1240       }
1241     }
1242   }else{
1243     assert( nReg==1 || pParse->nErr );
1244     sqlite3ExprCode(pParse, p, iReg);
1245   }
1246 }
1247
1248 /*
1249 ** The pTruth expression is always true because it is the WHERE clause
1250 ** a partial index that is driving a query loop.  Look through all of the
1251 ** WHERE clause terms on the query, and if any of those terms must be
1252 ** true because pTruth is true, then mark those WHERE clause terms as
1253 ** coded.
1254 */
1255 static void whereApplyPartialIndexConstraints(
1256   Expr *pTruth,
1257   int iTabCur,
1258   WhereClause *pWC
1259 ){
1260   int i;
1261   WhereTerm *pTerm;
1262   while( pTruth->op==TK_AND ){
1263     whereApplyPartialIndexConstraints(pTruth->pLeft, iTabCur, pWC);
1264     pTruth = pTruth->pRight;
1265   }
1266   for(i=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){
1267     Expr *pExpr;
1268     if( pTerm->wtFlags & TERM_CODED ) continue;
1269     pExpr = pTerm->pExpr;
1270     if( sqlite3ExprCompare(0, pExpr, pTruth, iTabCur)==0 ){
1271       pTerm->wtFlags |= TERM_CODED;
1272     }
1273   }
1274 }
1275
1276 /*
1277 ** This routine is called right after An OP_Filter has been generated and
1278 ** before the corresponding index search has been performed.  This routine
1279 ** checks to see if there are additional Bloom filters in inner loops that
1280 ** can be checked prior to doing the index lookup.  If there are available
1281 ** inner-loop Bloom filters, then evaluate those filters now, before the
1282 ** index lookup.  The idea is that a Bloom filter check is way faster than
1283 ** an index lookup, and the Bloom filter might return false, meaning that
1284 ** the index lookup can be skipped.
1285 **
1286 ** We know that an inner loop uses a Bloom filter because it has the
1287 ** WhereLevel.regFilter set.  If an inner-loop Bloom filter is checked,
1288 ** then clear the WhereLevel.regFilter value to prevent the Bloom filter
1289 ** from being checked a second time when the inner loop is evaluated.
1290 */
1291 static SQLITE_NOINLINE void filterPullDown(
1292   Parse *pParse,       /* Parsing context */
1293   WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
1294   int iLevel,          /* Which level of pWInfo->a[] should be coded */
1295   int addrNxt,         /* Jump here to bypass inner loops */
1296   Bitmask notReady     /* Loops that are not ready */
1297 ){
1298   while( ++iLevel < pWInfo->nLevel ){
1299     WhereLevel *pLevel = &pWInfo->a[iLevel];
1300     WhereLoop *pLoop = pLevel->pWLoop;
1301     if( pLevel->regFilter==0 ) continue;
1302     if( pLevel->pWLoop->nSkip ) continue;
1303     /*         ,--- Because sqlite3ConstructBloomFilter() has will not have set
1304     **  vvvvv--'    pLevel->regFilter if this were true. */
1305     if( NEVER(pLoop->prereq & notReady) ) continue;
1306     assert( pLevel->addrBrk==0 );
1307     pLevel->addrBrk = addrNxt;
1308     if( pLoop->wsFlags & WHERE_IPK ){
1309       WhereTerm *pTerm = pLoop->aLTerm[0];
1310       int regRowid;
1311       assert( pTerm!=0 );
1312       assert( pTerm->pExpr!=0 );
1313       testcase( pTerm->wtFlags & TERM_VIRTUAL );
1314       regRowid = sqlite3GetTempReg(pParse);
1315       regRowid = codeEqualityTerm(pParse, pTerm, pLevel, 0, 0, regRowid);
1316       sqlite3VdbeAddOp2(pParse->pVdbe, OP_MustBeInt, regRowid, addrNxt);
1317       VdbeCoverage(pParse->pVdbe);
1318       sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter,
1319                            addrNxt, regRowid, 1);
1320       VdbeCoverage(pParse->pVdbe);
1321     }else{
1322       u16 nEq = pLoop->u.btree.nEq;
1323       int r1;
1324       char *zStartAff;
1325
1326       assert( pLoop->wsFlags & WHERE_INDEXED );
1327       assert( (pLoop->wsFlags & WHERE_COLUMN_IN)==0 );
1328       r1 = codeAllEqualityTerms(pParse,pLevel,0,0,&zStartAff);
1329       codeApplyAffinity(pParse, r1, nEq, zStartAff);
1330       sqlite3DbFree(pParse->db, zStartAff);
1331       sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter,
1332                            addrNxt, r1, nEq);
1333       VdbeCoverage(pParse->pVdbe);
1334     }
1335     pLevel->regFilter = 0;
1336     pLevel->addrBrk = 0;
1337   }
1338 }
1339
1340 /*
1341 ** Generate code for the start of the iLevel-th loop in the WHERE clause
1342 ** implementation described by pWInfo.
1343 */
1344 Bitmask sqlite3WhereCodeOneLoopStart(
1345   Parse *pParse,       /* Parsing context */
1346   Vdbe *v,             /* Prepared statement under construction */
1347   WhereInfo *pWInfo,   /* Complete information about the WHERE clause */
1348   int iLevel,          /* Which level of pWInfo->a[] should be coded */
1349   WhereLevel *pLevel,  /* The current level pointer */
1350   Bitmask notReady     /* Which tables are currently available */
1351 ){
1352   int j, k;            /* Loop counters */
1353   int iCur;            /* The VDBE cursor for the table */
1354   int addrNxt;         /* Where to jump to continue with the next IN case */
1355   int bRev;            /* True if we need to scan in reverse order */
1356   WhereLoop *pLoop;    /* The WhereLoop object being coded */
1357   WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
1358   WhereTerm *pTerm;               /* A WHERE clause term */
1359   sqlite3 *db;                    /* Database connection */
1360   SrcItem *pTabItem;              /* FROM clause term being coded */
1361   int addrBrk;                    /* Jump here to break out of the loop */
1362   int addrHalt;                   /* addrBrk for the outermost loop */
1363   int addrCont;                   /* Jump here to continue with next cycle */
1364   int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
1365   int iReleaseReg = 0;      /* Temp register to free before returning */
1366   Index *pIdx = 0;          /* Index used by loop (if any) */
1367   int iLoop;                /* Iteration of constraint generator loop */
1368
1369   pWC = &pWInfo->sWC;
1370   db = pParse->db;
1371   pLoop = pLevel->pWLoop;
1372   pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
1373   iCur = pTabItem->iCursor;
1374   pLevel->notReady = notReady & ~sqlite3WhereGetMask(&pWInfo->sMaskSet, iCur);
1375   bRev = (pWInfo->revMask>>iLevel)&1;
1376   VdbeModuleComment((v, "Begin WHERE-loop%d: %s",iLevel,pTabItem->pTab->zName));
1377 #if WHERETRACE_ENABLED /* 0x4001 */
1378   if( sqlite3WhereTrace & 0x1 ){
1379     sqlite3DebugPrintf("Coding level %d of %d:  notReady=%llx  iFrom=%d\n",
1380        iLevel, pWInfo->nLevel, (u64)notReady, pLevel->iFrom);
1381     if( sqlite3WhereTrace & 0x1000 ){
1382       sqlite3WhereLoopPrint(pLoop, pWC);
1383     }
1384   }
1385   if( (sqlite3WhereTrace & 0x4001)==0x4001 ){
1386     if( iLevel==0 ){
1387       sqlite3DebugPrintf("WHERE clause being coded:\n");
1388       sqlite3TreeViewExpr(0, pWInfo->pWhere, 0);
1389     }
1390     sqlite3DebugPrintf("All WHERE-clause terms before coding:\n");
1391     sqlite3WhereClausePrint(pWC);
1392   }
1393 #endif
1394
1395   /* Create labels for the "break" and "continue" instructions
1396   ** for the current loop.  Jump to addrBrk to break out of a loop.
1397   ** Jump to cont to go immediately to the next iteration of the
1398   ** loop.
1399   **
1400   ** When there is an IN operator, we also have a "addrNxt" label that
1401   ** means to continue with the next IN value combination.  When
1402   ** there are no IN operators in the constraints, the "addrNxt" label
1403   ** is the same as "addrBrk".
1404   */
1405   addrBrk = pLevel->addrBrk = pLevel->addrNxt = sqlite3VdbeMakeLabel(pParse);
1406   addrCont = pLevel->addrCont = sqlite3VdbeMakeLabel(pParse);
1407
1408   /* If this is the right table of a LEFT OUTER JOIN, allocate and
1409   ** initialize a memory cell that records if this table matches any
1410   ** row of the left table of the join.
1411   */
1412   assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))
1413        || pLevel->iFrom>0 || (pTabItem[0].fg.jointype & JT_LEFT)==0
1414   );
1415   if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){
1416     pLevel->iLeftJoin = ++pParse->nMem;
1417     sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
1418     VdbeComment((v, "init LEFT JOIN no-match flag"));
1419   }
1420
1421   /* Compute a safe address to jump to if we discover that the table for
1422   ** this loop is empty and can never contribute content. */
1423   for(j=iLevel; j>0; j--){
1424     if( pWInfo->a[j].iLeftJoin ) break;
1425     if( pWInfo->a[j].pRJ ) break;
1426   }
1427   addrHalt = pWInfo->a[j].addrBrk;
1428
1429   /* Special case of a FROM clause subquery implemented as a co-routine */
1430   if( pTabItem->fg.viaCoroutine ){
1431     int regYield = pTabItem->regReturn;
1432     sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);
1433     pLevel->p2 =  sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk);
1434     VdbeCoverage(v);
1435     VdbeComment((v, "next row of %s", pTabItem->pTab->zName));
1436     pLevel->op = OP_Goto;
1437   }else
1438
1439 #ifndef SQLITE_OMIT_VIRTUALTABLE
1440   if(  (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
1441     /* Case 1:  The table is a virtual-table.  Use the VFilter and VNext
1442     **          to access the data.
1443     */
1444     int iReg;   /* P3 Value for OP_VFilter */
1445     int addrNotFound;
1446     int nConstraint = pLoop->nLTerm;
1447
1448     iReg = sqlite3GetTempRange(pParse, nConstraint+2);
1449     addrNotFound = pLevel->addrBrk;
1450     for(j=0; j<nConstraint; j++){
1451       int iTarget = iReg+j+2;
1452       pTerm = pLoop->aLTerm[j];
1453       if( NEVER(pTerm==0) ) continue;
1454       if( pTerm->eOperator & WO_IN ){
1455         if( SMASKBIT32(j) & pLoop->u.vtab.mHandleIn ){
1456           int iTab = pParse->nTab++;
1457           int iCache = ++pParse->nMem;
1458           sqlite3CodeRhsOfIN(pParse, pTerm->pExpr, iTab);
1459           sqlite3VdbeAddOp3(v, OP_VInitIn, iTab, iTarget, iCache);
1460         }else{
1461           codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
1462           addrNotFound = pLevel->addrNxt;
1463         }
1464       }else{
1465         Expr *pRight = pTerm->pExpr->pRight;
1466         codeExprOrVector(pParse, pRight, iTarget, 1);
1467         if( pTerm->eMatchOp==SQLITE_INDEX_CONSTRAINT_OFFSET
1468          && pLoop->u.vtab.bOmitOffset
1469         ){
1470           assert( pTerm->eOperator==WO_AUX );
1471           assert( pWInfo->pSelect!=0 );
1472           assert( pWInfo->pSelect->iOffset>0 );
1473           sqlite3VdbeAddOp2(v, OP_Integer, 0, pWInfo->pSelect->iOffset);
1474           VdbeComment((v,"Zero OFFSET counter"));
1475         }
1476       }
1477     }
1478     sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
1479     sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
1480     sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
1481                       pLoop->u.vtab.idxStr,
1482                       pLoop->u.vtab.needFree ? P4_DYNAMIC : P4_STATIC);
1483     VdbeCoverage(v);
1484     pLoop->u.vtab.needFree = 0;
1485     /* An OOM inside of AddOp4(OP_VFilter) instruction above might have freed
1486     ** the u.vtab.idxStr.  NULL it out to prevent a use-after-free */
1487     if( db->mallocFailed ) pLoop->u.vtab.idxStr = 0;
1488     pLevel->p1 = iCur;
1489     pLevel->op = pWInfo->eOnePass ? OP_Noop : OP_VNext;
1490     pLevel->p2 = sqlite3VdbeCurrentAddr(v);
1491     assert( (pLoop->wsFlags & WHERE_MULTI_OR)==0 );
1492
1493     for(j=0; j<nConstraint; j++){
1494       pTerm = pLoop->aLTerm[j];
1495       if( j<16 && (pLoop->u.vtab.omitMask>>j)&1 ){
1496         disableTerm(pLevel, pTerm);
1497         continue;
1498       }
1499       if( (pTerm->eOperator & WO_IN)!=0
1500        && (SMASKBIT32(j) & pLoop->u.vtab.mHandleIn)==0
1501        && !db->mallocFailed
1502       ){
1503         Expr *pCompare;  /* The comparison operator */
1504         Expr *pRight;    /* RHS of the comparison */
1505         VdbeOp *pOp;     /* Opcode to access the value of the IN constraint */
1506         int iIn;         /* IN loop corresponding to the j-th constraint */
1507
1508         /* Reload the constraint value into reg[iReg+j+2].  The same value
1509         ** was loaded into the same register prior to the OP_VFilter, but
1510         ** the xFilter implementation might have changed the datatype or
1511         ** encoding of the value in the register, so it *must* be reloaded.
1512         */
1513         for(iIn=0; ALWAYS(iIn<pLevel->u.in.nIn); iIn++){
1514           pOp = sqlite3VdbeGetOp(v, pLevel->u.in.aInLoop[iIn].addrInTop);
1515           if( (pOp->opcode==OP_Column && pOp->p3==iReg+j+2)
1516            || (pOp->opcode==OP_Rowid && pOp->p2==iReg+j+2)
1517           ){
1518             testcase( pOp->opcode==OP_Rowid );
1519             sqlite3VdbeAddOp3(v, pOp->opcode, pOp->p1, pOp->p2, pOp->p3);
1520             break;
1521           }
1522         }
1523
1524         /* Generate code that will continue to the next row if
1525         ** the IN constraint is not satisfied
1526         */
1527         pCompare = sqlite3PExpr(pParse, TK_EQ, 0, 0);
1528         if( !db->mallocFailed ){
1529           int iFld = pTerm->u.x.iField;
1530           Expr *pLeft = pTerm->pExpr->pLeft;
1531           assert( pLeft!=0 );
1532           if( iFld>0 ){
1533             assert( pLeft->op==TK_VECTOR );
1534             assert( ExprUseXList(pLeft) );
1535             assert( iFld<=pLeft->x.pList->nExpr );
1536             pCompare->pLeft = pLeft->x.pList->a[iFld-1].pExpr;
1537           }else{
1538             pCompare->pLeft = pLeft;
1539           }
1540           pCompare->pRight = pRight = sqlite3Expr(db, TK_REGISTER, 0);
1541           if( pRight ){
1542             pRight->iTable = iReg+j+2;
1543             sqlite3ExprIfFalse(
1544                 pParse, pCompare, pLevel->addrCont, SQLITE_JUMPIFNULL
1545             );
1546           }
1547           pCompare->pLeft = 0;
1548         }
1549         sqlite3ExprDelete(db, pCompare);
1550       }
1551     }
1552
1553     /* These registers need to be preserved in case there is an IN operator
1554     ** loop.  So we could deallocate the registers here (and potentially
1555     ** reuse them later) if (pLoop->wsFlags & WHERE_IN_ABLE)==0.  But it seems
1556     ** simpler and safer to simply not reuse the registers.
1557     **
1558     **    sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
1559     */
1560   }else
1561 #endif /* SQLITE_OMIT_VIRTUALTABLE */
1562
1563   if( (pLoop->wsFlags & WHERE_IPK)!=0
1564    && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0
1565   ){
1566     /* Case 2:  We can directly reference a single row using an
1567     **          equality comparison against the ROWID field.  Or
1568     **          we reference multiple rows using a "rowid IN (...)"
1569     **          construct.
1570     */
1571     assert( pLoop->u.btree.nEq==1 );
1572     pTerm = pLoop->aLTerm[0];
1573     assert( pTerm!=0 );
1574     assert( pTerm->pExpr!=0 );
1575     testcase( pTerm->wtFlags & TERM_VIRTUAL );
1576     iReleaseReg = ++pParse->nMem;
1577     iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
1578     if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg);
1579     addrNxt = pLevel->addrNxt;
1580     if( pLevel->regFilter ){
1581       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
1582       VdbeCoverage(v);
1583       sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt,
1584                            iRowidReg, 1);
1585       VdbeCoverage(v);
1586       filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady);
1587     }
1588     sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg);
1589     VdbeCoverage(v);
1590     pLevel->op = OP_Noop;
1591   }else if( (pLoop->wsFlags & WHERE_IPK)!=0
1592          && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0
1593   ){
1594     /* Case 3:  We have an inequality comparison against the ROWID field.
1595     */
1596     int testOp = OP_Noop;
1597     int start;
1598     int memEndValue = 0;
1599     WhereTerm *pStart, *pEnd;
1600
1601     j = 0;
1602     pStart = pEnd = 0;
1603     if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
1604     if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
1605     assert( pStart!=0 || pEnd!=0 );
1606     if( bRev ){
1607       pTerm = pStart;
1608       pStart = pEnd;
1609       pEnd = pTerm;
1610     }
1611     codeCursorHint(pTabItem, pWInfo, pLevel, pEnd);
1612     if( pStart ){
1613       Expr *pX;             /* The expression that defines the start bound */
1614       int r1, rTemp;        /* Registers for holding the start boundary */
1615       int op;               /* Cursor seek operation */
1616
1617       /* The following constant maps TK_xx codes into corresponding
1618       ** seek opcodes.  It depends on a particular ordering of TK_xx
1619       */
1620       const u8 aMoveOp[] = {
1621            /* TK_GT */  OP_SeekGT,
1622            /* TK_LE */  OP_SeekLE,
1623            /* TK_LT */  OP_SeekLT,
1624            /* TK_GE */  OP_SeekGE
1625       };
1626       assert( TK_LE==TK_GT+1 );      /* Make sure the ordering.. */
1627       assert( TK_LT==TK_GT+2 );      /*  ... of the TK_xx values... */
1628       assert( TK_GE==TK_GT+3 );      /*  ... is correct. */
1629
1630       assert( (pStart->wtFlags & TERM_VNULL)==0 );
1631       testcase( pStart->wtFlags & TERM_VIRTUAL );
1632       pX = pStart->pExpr;
1633       assert( pX!=0 );
1634       testcase( pStart->leftCursor!=iCur ); /* transitive constraints */
1635       if( sqlite3ExprIsVector(pX->pRight) ){
1636         r1 = rTemp = sqlite3GetTempReg(pParse);
1637         codeExprOrVector(pParse, pX->pRight, r1, 1);
1638         testcase( pX->op==TK_GT );
1639         testcase( pX->op==TK_GE );
1640         testcase( pX->op==TK_LT );
1641         testcase( pX->op==TK_LE );
1642         op = aMoveOp[((pX->op - TK_GT - 1) & 0x3) | 0x1];
1643         assert( pX->op!=TK_GT || op==OP_SeekGE );
1644         assert( pX->op!=TK_GE || op==OP_SeekGE );
1645         assert( pX->op!=TK_LT || op==OP_SeekLE );
1646         assert( pX->op!=TK_LE || op==OP_SeekLE );
1647       }else{
1648         r1 = sqlite3ExprCodeTemp(pParse, pX->pRight, &rTemp);
1649         disableTerm(pLevel, pStart);
1650         op = aMoveOp[(pX->op - TK_GT)];
1651       }
1652       sqlite3VdbeAddOp3(v, op, iCur, addrBrk, r1);
1653       VdbeComment((v, "pk"));
1654       VdbeCoverageIf(v, pX->op==TK_GT);
1655       VdbeCoverageIf(v, pX->op==TK_LE);
1656       VdbeCoverageIf(v, pX->op==TK_LT);
1657       VdbeCoverageIf(v, pX->op==TK_GE);
1658       sqlite3ReleaseTempReg(pParse, rTemp);
1659     }else{
1660       sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt);
1661       VdbeCoverageIf(v, bRev==0);
1662       VdbeCoverageIf(v, bRev!=0);
1663     }
1664     if( pEnd ){
1665       Expr *pX;
1666       pX = pEnd->pExpr;
1667       assert( pX!=0 );
1668       assert( (pEnd->wtFlags & TERM_VNULL)==0 );
1669       testcase( pEnd->leftCursor!=iCur ); /* Transitive constraints */
1670       testcase( pEnd->wtFlags & TERM_VIRTUAL );
1671       memEndValue = ++pParse->nMem;
1672       codeExprOrVector(pParse, pX->pRight, memEndValue, 1);
1673       if( 0==sqlite3ExprIsVector(pX->pRight)
1674        && (pX->op==TK_LT || pX->op==TK_GT)
1675       ){
1676         testOp = bRev ? OP_Le : OP_Ge;
1677       }else{
1678         testOp = bRev ? OP_Lt : OP_Gt;
1679       }
1680       if( 0==sqlite3ExprIsVector(pX->pRight) ){
1681         disableTerm(pLevel, pEnd);
1682       }
1683     }
1684     start = sqlite3VdbeCurrentAddr(v);
1685     pLevel->op = bRev ? OP_Prev : OP_Next;
1686     pLevel->p1 = iCur;
1687     pLevel->p2 = start;
1688     assert( pLevel->p5==0 );
1689     if( testOp!=OP_Noop ){
1690       iRowidReg = ++pParse->nMem;
1691       sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
1692       sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
1693       VdbeCoverageIf(v, testOp==OP_Le);
1694       VdbeCoverageIf(v, testOp==OP_Lt);
1695       VdbeCoverageIf(v, testOp==OP_Ge);
1696       VdbeCoverageIf(v, testOp==OP_Gt);
1697       sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
1698     }
1699   }else if( pLoop->wsFlags & WHERE_INDEXED ){
1700     /* Case 4: A scan using an index.
1701     **
1702     **         The WHERE clause may contain zero or more equality
1703     **         terms ("==" or "IN" operators) that refer to the N
1704     **         left-most columns of the index. It may also contain
1705     **         inequality constraints (>, <, >= or <=) on the indexed
1706     **         column that immediately follows the N equalities. Only
1707     **         the right-most column can be an inequality - the rest must
1708     **         use the "==" and "IN" operators. For example, if the
1709     **         index is on (x,y,z), then the following clauses are all
1710     **         optimized:
1711     **
1712     **            x=5
1713     **            x=5 AND y=10
1714     **            x=5 AND y<10
1715     **            x=5 AND y>5 AND y<10
1716     **            x=5 AND y=5 AND z<=10
1717     **
1718     **         The z<10 term of the following cannot be used, only
1719     **         the x=5 term:
1720     **
1721     **            x=5 AND z<10
1722     **
1723     **         N may be zero if there are inequality constraints.
1724     **         If there are no inequality constraints, then N is at
1725     **         least one.
1726     **
1727     **         This case is also used when there are no WHERE clause
1728     **         constraints but an index is selected anyway, in order
1729     **         to force the output order to conform to an ORDER BY.
1730     */
1731     static const u8 aStartOp[] = {
1732       0,
1733       0,
1734       OP_Rewind,           /* 2: (!start_constraints && startEq &&  !bRev) */
1735       OP_Last,             /* 3: (!start_constraints && startEq &&   bRev) */
1736       OP_SeekGT,           /* 4: (start_constraints  && !startEq && !bRev) */
1737       OP_SeekLT,           /* 5: (start_constraints  && !startEq &&  bRev) */
1738       OP_SeekGE,           /* 6: (start_constraints  &&  startEq && !bRev) */
1739       OP_SeekLE            /* 7: (start_constraints  &&  startEq &&  bRev) */
1740     };
1741     static const u8 aEndOp[] = {
1742       OP_IdxGE,            /* 0: (end_constraints && !bRev && !endEq) */
1743       OP_IdxGT,            /* 1: (end_constraints && !bRev &&  endEq) */
1744       OP_IdxLE,            /* 2: (end_constraints &&  bRev && !endEq) */
1745       OP_IdxLT,            /* 3: (end_constraints &&  bRev &&  endEq) */
1746     };
1747     u16 nEq = pLoop->u.btree.nEq;     /* Number of == or IN terms */
1748     u16 nBtm = pLoop->u.btree.nBtm;   /* Length of BTM vector */
1749     u16 nTop = pLoop->u.btree.nTop;   /* Length of TOP vector */
1750     int regBase;                 /* Base register holding constraint values */
1751     WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
1752     WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
1753     int startEq;                 /* True if range start uses ==, >= or <= */
1754     int endEq;                   /* True if range end uses ==, >= or <= */
1755     int start_constraints;       /* Start of range is constrained */
1756     int nConstraint;             /* Number of constraint terms */
1757     int iIdxCur;                 /* The VDBE cursor for the index */
1758     int nExtraReg = 0;           /* Number of extra registers needed */
1759     int op;                      /* Instruction opcode */
1760     char *zStartAff;             /* Affinity for start of range constraint */
1761     char *zEndAff = 0;           /* Affinity for end of range constraint */
1762     u8 bSeekPastNull = 0;        /* True to seek past initial nulls */
1763     u8 bStopAtNull = 0;          /* Add condition to terminate at NULLs */
1764     int omitTable;               /* True if we use the index only */
1765     int regBignull = 0;          /* big-null flag register */
1766     int addrSeekScan = 0;        /* Opcode of the OP_SeekScan, if any */
1767
1768     pIdx = pLoop->u.btree.pIndex;
1769     iIdxCur = pLevel->iIdxCur;
1770     assert( nEq>=pLoop->nSkip );
1771
1772     /* Find any inequality constraint terms for the start and end
1773     ** of the range.
1774     */
1775     j = nEq;
1776     if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
1777       pRangeStart = pLoop->aLTerm[j++];
1778       nExtraReg = MAX(nExtraReg, pLoop->u.btree.nBtm);
1779       /* Like optimization range constraints always occur in pairs */
1780       assert( (pRangeStart->wtFlags & TERM_LIKEOPT)==0 ||
1781               (pLoop->wsFlags & WHERE_TOP_LIMIT)!=0 );
1782     }
1783     if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
1784       pRangeEnd = pLoop->aLTerm[j++];
1785       nExtraReg = MAX(nExtraReg, pLoop->u.btree.nTop);
1786 #ifndef SQLITE_LIKE_DOESNT_MATCH_BLOBS
1787       if( (pRangeEnd->wtFlags & TERM_LIKEOPT)!=0 ){
1788         assert( pRangeStart!=0 );                     /* LIKE opt constraints */
1789         assert( pRangeStart->wtFlags & TERM_LIKEOPT );   /* occur in pairs */
1790         pLevel->iLikeRepCntr = (u32)++pParse->nMem;
1791         sqlite3VdbeAddOp2(v, OP_Integer, 1, (int)pLevel->iLikeRepCntr);
1792         VdbeComment((v, "LIKE loop counter"));
1793         pLevel->addrLikeRep = sqlite3VdbeCurrentAddr(v);
1794         /* iLikeRepCntr actually stores 2x the counter register number.  The
1795         ** bottom bit indicates whether the search order is ASC or DESC. */
1796         testcase( bRev );
1797         testcase( pIdx->aSortOrder[nEq]==SQLITE_SO_DESC );
1798         assert( (bRev & ~1)==0 );
1799         pLevel->iLikeRepCntr <<=1;
1800         pLevel->iLikeRepCntr |= bRev ^ (pIdx->aSortOrder[nEq]==SQLITE_SO_DESC);
1801       }
1802 #endif
1803       if( pRangeStart==0 ){
1804         j = pIdx->aiColumn[nEq];
1805         if( (j>=0 && pIdx->pTable->aCol[j].notNull==0) || j==XN_EXPR ){
1806           bSeekPastNull = 1;
1807         }
1808       }
1809     }
1810     assert( pRangeEnd==0 || (pRangeEnd->wtFlags & TERM_VNULL)==0 );
1811
1812     /* If the WHERE_BIGNULL_SORT flag is set, then index column nEq uses
1813     ** a non-default "big-null" sort (either ASC NULLS LAST or DESC NULLS
1814     ** FIRST). In both cases separate ordered scans are made of those
1815     ** index entries for which the column is null and for those for which
1816     ** it is not. For an ASC sort, the non-NULL entries are scanned first.
1817     ** For DESC, NULL entries are scanned first.
1818     */
1819     if( (pLoop->wsFlags & (WHERE_TOP_LIMIT|WHERE_BTM_LIMIT))==0
1820      && (pLoop->wsFlags & WHERE_BIGNULL_SORT)!=0
1821     ){
1822       assert( bSeekPastNull==0 && nExtraReg==0 && nBtm==0 && nTop==0 );
1823       assert( pRangeEnd==0 && pRangeStart==0 );
1824       testcase( pLoop->nSkip>0 );
1825       nExtraReg = 1;
1826       bSeekPastNull = 1;
1827       pLevel->regBignull = regBignull = ++pParse->nMem;
1828       if( pLevel->iLeftJoin ){
1829         sqlite3VdbeAddOp2(v, OP_Integer, 0, regBignull);
1830       }
1831       pLevel->addrBignull = sqlite3VdbeMakeLabel(pParse);
1832     }
1833
1834     /* If we are doing a reverse order scan on an ascending index, or
1835     ** a forward order scan on a descending index, interchange the
1836     ** start and end terms (pRangeStart and pRangeEnd).
1837     */
1838     if( (nEq<pIdx->nColumn && bRev==(pIdx->aSortOrder[nEq]==SQLITE_SO_ASC)) ){
1839       SWAP(WhereTerm *, pRangeEnd, pRangeStart);
1840       SWAP(u8, bSeekPastNull, bStopAtNull);
1841       SWAP(u8, nBtm, nTop);
1842     }
1843
1844     if( iLevel>0 && (pLoop->wsFlags & WHERE_IN_SEEKSCAN)!=0 ){
1845       /* In case OP_SeekScan is used, ensure that the index cursor does not
1846       ** point to a valid row for the first iteration of this loop. */
1847       sqlite3VdbeAddOp1(v, OP_NullRow, iIdxCur);
1848     }
1849
1850     /* Generate code to evaluate all constraint terms using == or IN
1851     ** and store the values of those terms in an array of registers
1852     ** starting at regBase.
1853     */
1854     codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd);
1855     regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff);
1856     assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq );
1857     if( zStartAff && nTop ){
1858       zEndAff = sqlite3DbStrDup(db, &zStartAff[nEq]);
1859     }
1860     addrNxt = (regBignull ? pLevel->addrBignull : pLevel->addrNxt);
1861
1862     testcase( pRangeStart && (pRangeStart->eOperator & WO_LE)!=0 );
1863     testcase( pRangeStart && (pRangeStart->eOperator & WO_GE)!=0 );
1864     testcase( pRangeEnd && (pRangeEnd->eOperator & WO_LE)!=0 );
1865     testcase( pRangeEnd && (pRangeEnd->eOperator & WO_GE)!=0 );
1866     startEq = !pRangeStart || pRangeStart->eOperator & (WO_LE|WO_GE);
1867     endEq =   !pRangeEnd || pRangeEnd->eOperator & (WO_LE|WO_GE);
1868     start_constraints = pRangeStart || nEq>0;
1869
1870     /* Seek the index cursor to the start of the range. */
1871     nConstraint = nEq;
1872     if( pRangeStart ){
1873       Expr *pRight = pRangeStart->pExpr->pRight;
1874       codeExprOrVector(pParse, pRight, regBase+nEq, nBtm);
1875       whereLikeOptimizationStringFixup(v, pLevel, pRangeStart);
1876       if( (pRangeStart->wtFlags & TERM_VNULL)==0
1877        && sqlite3ExprCanBeNull(pRight)
1878       ){
1879         sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1880         VdbeCoverage(v);
1881       }
1882       if( zStartAff ){
1883         updateRangeAffinityStr(pRight, nBtm, &zStartAff[nEq]);
1884       }
1885       nConstraint += nBtm;
1886       testcase( pRangeStart->wtFlags & TERM_VIRTUAL );
1887       if( sqlite3ExprIsVector(pRight)==0 ){
1888         disableTerm(pLevel, pRangeStart);
1889       }else{
1890         startEq = 1;
1891       }
1892       bSeekPastNull = 0;
1893     }else if( bSeekPastNull ){
1894       startEq = 0;
1895       sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1896       start_constraints = 1;
1897       nConstraint++;
1898     }else if( regBignull ){
1899       sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
1900       start_constraints = 1;
1901       nConstraint++;
1902     }
1903     codeApplyAffinity(pParse, regBase, nConstraint - bSeekPastNull, zStartAff);
1904     if( pLoop->nSkip>0 && nConstraint==pLoop->nSkip ){
1905       /* The skip-scan logic inside the call to codeAllEqualityConstraints()
1906       ** above has already left the cursor sitting on the correct row,
1907       ** so no further seeking is needed */
1908     }else{
1909       if( regBignull ){
1910         sqlite3VdbeAddOp2(v, OP_Integer, 1, regBignull);
1911         VdbeComment((v, "NULL-scan pass ctr"));
1912       }
1913       if( pLevel->regFilter ){
1914         sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt,
1915                              regBase, nEq);
1916         VdbeCoverage(v);
1917         filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady);
1918       }
1919
1920       op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev];
1921       assert( op!=0 );
1922       if( (pLoop->wsFlags & WHERE_IN_SEEKSCAN)!=0 && op==OP_SeekGE ){
1923         assert( regBignull==0 );
1924         /* TUNING:  The OP_SeekScan opcode seeks to reduce the number
1925         ** of expensive seek operations by replacing a single seek with
1926         ** 1 or more step operations.  The question is, how many steps
1927         ** should we try before giving up and going with a seek.  The cost
1928         ** of a seek is proportional to the logarithm of the of the number
1929         ** of entries in the tree, so basing the number of steps to try
1930         ** on the estimated number of rows in the btree seems like a good
1931         ** guess. */
1932         addrSeekScan = sqlite3VdbeAddOp1(v, OP_SeekScan,
1933                                          (pIdx->aiRowLogEst[0]+9)/10);
1934         if( pRangeStart || pRangeEnd ){
1935           sqlite3VdbeChangeP5(v, 1);
1936           sqlite3VdbeChangeP2(v, addrSeekScan, sqlite3VdbeCurrentAddr(v)+1);
1937           addrSeekScan = 0;
1938         }
1939         VdbeCoverage(v);
1940       }
1941       sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
1942       VdbeCoverage(v);
1943       VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
1944       VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
1945       VdbeCoverageIf(v, op==OP_SeekGT);  testcase( op==OP_SeekGT );
1946       VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
1947       VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );
1948       VdbeCoverageIf(v, op==OP_SeekLT);  testcase( op==OP_SeekLT );
1949
1950       assert( bSeekPastNull==0 || bStopAtNull==0 );
1951       if( regBignull ){
1952         assert( bSeekPastNull==1 || bStopAtNull==1 );
1953         assert( bSeekPastNull==!bStopAtNull );
1954         assert( bStopAtNull==startEq );
1955         sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2);
1956         op = aStartOp[(nConstraint>1)*4 + 2 + bRev];
1957         sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
1958                              nConstraint-startEq);
1959         VdbeCoverage(v);
1960         VdbeCoverageIf(v, op==OP_Rewind);  testcase( op==OP_Rewind );
1961         VdbeCoverageIf(v, op==OP_Last);    testcase( op==OP_Last );
1962         VdbeCoverageIf(v, op==OP_SeekGE);  testcase( op==OP_SeekGE );
1963         VdbeCoverageIf(v, op==OP_SeekLE);  testcase( op==OP_SeekLE );
1964         assert( op==OP_Rewind || op==OP_Last || op==OP_SeekGE || op==OP_SeekLE);
1965       }
1966     }
1967
1968     /* Load the value for the inequality constraint at the end of the
1969     ** range (if any).
1970     */
1971     nConstraint = nEq;
1972     assert( pLevel->p2==0 );
1973     if( pRangeEnd ){
1974       Expr *pRight = pRangeEnd->pExpr->pRight;
1975       assert( addrSeekScan==0 );
1976       codeExprOrVector(pParse, pRight, regBase+nEq, nTop);
1977       whereLikeOptimizationStringFixup(v, pLevel, pRangeEnd);
1978       if( (pRangeEnd->wtFlags & TERM_VNULL)==0
1979        && sqlite3ExprCanBeNull(pRight)
1980       ){
1981         sqlite3VdbeAddOp2(v, OP_IsNull, regBase+nEq, addrNxt);
1982         VdbeCoverage(v);
1983       }
1984       if( zEndAff ){
1985         updateRangeAffinityStr(pRight, nTop, zEndAff);
1986         codeApplyAffinity(pParse, regBase+nEq, nTop, zEndAff);
1987       }else{
1988         assert( pParse->db->mallocFailed );
1989       }
1990       nConstraint += nTop;
1991       testcase( pRangeEnd->wtFlags & TERM_VIRTUAL );
1992
1993       if( sqlite3ExprIsVector(pRight)==0 ){
1994         disableTerm(pLevel, pRangeEnd);
1995       }else{
1996         endEq = 1;
1997       }
1998     }else if( bStopAtNull ){
1999       if( regBignull==0 ){
2000         sqlite3VdbeAddOp2(v, OP_Null, 0, regBase+nEq);
2001         endEq = 0;
2002       }
2003       nConstraint++;
2004     }
2005     if( zStartAff ) sqlite3DbNNFreeNN(db, zStartAff);
2006     if( zEndAff ) sqlite3DbNNFreeNN(db, zEndAff);
2007
2008     /* Top of the loop body */
2009     pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2010
2011     /* Check if the index cursor is past the end of the range. */
2012     if( nConstraint ){
2013       if( regBignull ){
2014         /* Except, skip the end-of-range check while doing the NULL-scan */
2015         sqlite3VdbeAddOp2(v, OP_IfNot, regBignull, sqlite3VdbeCurrentAddr(v)+3);
2016         VdbeComment((v, "If NULL-scan 2nd pass"));
2017         VdbeCoverage(v);
2018       }
2019       op = aEndOp[bRev*2 + endEq];
2020       sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase, nConstraint);
2021       testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
2022       testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
2023       testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
2024       testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
2025       if( addrSeekScan ) sqlite3VdbeJumpHere(v, addrSeekScan);
2026     }
2027     if( regBignull ){
2028       /* During a NULL-scan, check to see if we have reached the end of
2029       ** the NULLs */
2030       assert( bSeekPastNull==!bStopAtNull );
2031       assert( bSeekPastNull+bStopAtNull==1 );
2032       assert( nConstraint+bSeekPastNull>0 );
2033       sqlite3VdbeAddOp2(v, OP_If, regBignull, sqlite3VdbeCurrentAddr(v)+2);
2034       VdbeComment((v, "If NULL-scan 1st pass"));
2035       VdbeCoverage(v);
2036       op = aEndOp[bRev*2 + bSeekPastNull];
2037       sqlite3VdbeAddOp4Int(v, op, iIdxCur, addrNxt, regBase,
2038                            nConstraint+bSeekPastNull);
2039       testcase( op==OP_IdxGT );  VdbeCoverageIf(v, op==OP_IdxGT );
2040       testcase( op==OP_IdxGE );  VdbeCoverageIf(v, op==OP_IdxGE );
2041       testcase( op==OP_IdxLT );  VdbeCoverageIf(v, op==OP_IdxLT );
2042       testcase( op==OP_IdxLE );  VdbeCoverageIf(v, op==OP_IdxLE );
2043     }
2044
2045     if( (pLoop->wsFlags & WHERE_IN_EARLYOUT)!=0 ){
2046       sqlite3VdbeAddOp3(v, OP_SeekHit, iIdxCur, nEq, nEq);
2047     }
2048
2049     /* Seek the table cursor, if required */
2050     omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0
2051            && (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0;
2052     if( omitTable ){
2053       /* pIdx is a covering index.  No need to access the main table. */
2054     }else if( HasRowid(pIdx->pTable) ){
2055       codeDeferredSeek(pWInfo, pIdx, iCur, iIdxCur);
2056     }else if( iCur!=iIdxCur ){
2057       Index *pPk = sqlite3PrimaryKeyIndex(pIdx->pTable);
2058       iRowidReg = sqlite3GetTempRange(pParse, pPk->nKeyCol);
2059       for(j=0; j<pPk->nKeyCol; j++){
2060         k = sqlite3TableColumnToIndex(pIdx, pPk->aiColumn[j]);
2061         sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, k, iRowidReg+j);
2062       }
2063       sqlite3VdbeAddOp4Int(v, OP_NotFound, iCur, addrCont,
2064                            iRowidReg, pPk->nKeyCol); VdbeCoverage(v);
2065     }
2066
2067     if( pLevel->iLeftJoin==0 ){
2068       /* If a partial index is driving the loop, try to eliminate WHERE clause
2069       ** terms from the query that must be true due to the WHERE clause of
2070       ** the partial index.
2071       **
2072       ** 2019-11-02 ticket 623eff57e76d45f6: This optimization does not work
2073       ** for a LEFT JOIN.
2074       */
2075       if( pIdx->pPartIdxWhere ){
2076         whereApplyPartialIndexConstraints(pIdx->pPartIdxWhere, iCur, pWC);
2077       }
2078     }else{
2079       testcase( pIdx->pPartIdxWhere );
2080       /* The following assert() is not a requirement, merely an observation:
2081       ** The OR-optimization doesn't work for the right hand table of
2082       ** a LEFT JOIN: */
2083       assert( (pWInfo->wctrlFlags & (WHERE_OR_SUBCLAUSE|WHERE_RIGHT_JOIN))==0 );
2084     }
2085
2086     /* Record the instruction used to terminate the loop. */
2087     if( pLoop->wsFlags & WHERE_ONEROW ){
2088       pLevel->op = OP_Noop;
2089     }else if( bRev ){
2090       pLevel->op = OP_Prev;
2091     }else{
2092       pLevel->op = OP_Next;
2093     }
2094     pLevel->p1 = iIdxCur;
2095     pLevel->p3 = (pLoop->wsFlags&WHERE_UNQ_WANTED)!=0 ? 1:0;
2096     if( (pLoop->wsFlags & WHERE_CONSTRAINT)==0 ){
2097       pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2098     }else{
2099       assert( pLevel->p5==0 );
2100     }
2101     if( omitTable ) pIdx = 0;
2102   }else
2103
2104 #ifndef SQLITE_OMIT_OR_OPTIMIZATION
2105   if( pLoop->wsFlags & WHERE_MULTI_OR ){
2106     /* Case 5:  Two or more separately indexed terms connected by OR
2107     **
2108     ** Example:
2109     **
2110     **   CREATE TABLE t1(a,b,c,d);
2111     **   CREATE INDEX i1 ON t1(a);
2112     **   CREATE INDEX i2 ON t1(b);
2113     **   CREATE INDEX i3 ON t1(c);
2114     **
2115     **   SELECT * FROM t1 WHERE a=5 OR b=7 OR (c=11 AND d=13)
2116     **
2117     ** In the example, there are three indexed terms connected by OR.
2118     ** The top of the loop looks like this:
2119     **
2120     **          Null       1                # Zero the rowset in reg 1
2121     **
2122     ** Then, for each indexed term, the following. The arguments to
2123     ** RowSetTest are such that the rowid of the current row is inserted
2124     ** into the RowSet. If it is already present, control skips the
2125     ** Gosub opcode and jumps straight to the code generated by WhereEnd().
2126     **
2127     **        sqlite3WhereBegin(<term>)
2128     **          RowSetTest                  # Insert rowid into rowset
2129     **          Gosub      2 A
2130     **        sqlite3WhereEnd()
2131     **
2132     ** Following the above, code to terminate the loop. Label A, the target
2133     ** of the Gosub above, jumps to the instruction right after the Goto.
2134     **
2135     **          Null       1                # Zero the rowset in reg 1
2136     **          Goto       B                # The loop is finished.
2137     **
2138     **       A: <loop body>                 # Return data, whatever.
2139     **
2140     **          Return     2                # Jump back to the Gosub
2141     **
2142     **       B: <after the loop>
2143     **
2144     ** Added 2014-05-26: If the table is a WITHOUT ROWID table, then
2145     ** use an ephemeral index instead of a RowSet to record the primary
2146     ** keys of the rows we have already seen.
2147     **
2148     */
2149     WhereClause *pOrWc;    /* The OR-clause broken out into subterms */
2150     SrcList *pOrTab;       /* Shortened table list or OR-clause generation */
2151     Index *pCov = 0;             /* Potential covering index (or NULL) */
2152     int iCovCur = pParse->nTab++;  /* Cursor used for index scans (if any) */
2153
2154     int regReturn = ++pParse->nMem;           /* Register used with OP_Gosub */
2155     int regRowset = 0;                        /* Register for RowSet object */
2156     int regRowid = 0;                         /* Register holding rowid */
2157     int iLoopBody = sqlite3VdbeMakeLabel(pParse);/* Start of loop body */
2158     int iRetInit;                             /* Address of regReturn init */
2159     int untestedTerms = 0;             /* Some terms not completely tested */
2160     int ii;                            /* Loop counter */
2161     Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
2162     Table *pTab = pTabItem->pTab;
2163
2164     pTerm = pLoop->aLTerm[0];
2165     assert( pTerm!=0 );
2166     assert( pTerm->eOperator & WO_OR );
2167     assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
2168     pOrWc = &pTerm->u.pOrInfo->wc;
2169     pLevel->op = OP_Return;
2170     pLevel->p1 = regReturn;
2171
2172     /* Set up a new SrcList in pOrTab containing the table being scanned
2173     ** by this loop in the a[0] slot and all notReady tables in a[1..] slots.
2174     ** This becomes the SrcList in the recursive call to sqlite3WhereBegin().
2175     */
2176     if( pWInfo->nLevel>1 ){
2177       int nNotReady;                 /* The number of notReady tables */
2178       SrcItem *origSrc;              /* Original list of tables */
2179       nNotReady = pWInfo->nLevel - iLevel - 1;
2180       pOrTab = sqlite3DbMallocRawNN(db,
2181                             sizeof(*pOrTab)+ nNotReady*sizeof(pOrTab->a[0]));
2182       if( pOrTab==0 ) return notReady;
2183       pOrTab->nAlloc = (u8)(nNotReady + 1);
2184       pOrTab->nSrc = pOrTab->nAlloc;
2185       memcpy(pOrTab->a, pTabItem, sizeof(*pTabItem));
2186       origSrc = pWInfo->pTabList->a;
2187       for(k=1; k<=nNotReady; k++){
2188         memcpy(&pOrTab->a[k], &origSrc[pLevel[k].iFrom], sizeof(pOrTab->a[k]));
2189       }
2190     }else{
2191       pOrTab = pWInfo->pTabList;
2192     }
2193
2194     /* Initialize the rowset register to contain NULL. An SQL NULL is
2195     ** equivalent to an empty rowset.  Or, create an ephemeral index
2196     ** capable of holding primary keys in the case of a WITHOUT ROWID.
2197     **
2198     ** Also initialize regReturn to contain the address of the instruction
2199     ** immediately following the OP_Return at the bottom of the loop. This
2200     ** is required in a few obscure LEFT JOIN cases where control jumps
2201     ** over the top of the loop into the body of it. In this case the
2202     ** correct response for the end-of-loop code (the OP_Return) is to
2203     ** fall through to the next instruction, just as an OP_Next does if
2204     ** called on an uninitialized cursor.
2205     */
2206     if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2207       if( HasRowid(pTab) ){
2208         regRowset = ++pParse->nMem;
2209         sqlite3VdbeAddOp2(v, OP_Null, 0, regRowset);
2210       }else{
2211         Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2212         regRowset = pParse->nTab++;
2213         sqlite3VdbeAddOp2(v, OP_OpenEphemeral, regRowset, pPk->nKeyCol);
2214         sqlite3VdbeSetP4KeyInfo(pParse, pPk);
2215       }
2216       regRowid = ++pParse->nMem;
2217     }
2218     iRetInit = sqlite3VdbeAddOp2(v, OP_Integer, 0, regReturn);
2219
2220     /* If the original WHERE clause is z of the form:  (x1 OR x2 OR ...) AND y
2221     ** Then for every term xN, evaluate as the subexpression: xN AND y
2222     ** That way, terms in y that are factored into the disjunction will
2223     ** be picked up by the recursive calls to sqlite3WhereBegin() below.
2224     **
2225     ** Actually, each subexpression is converted to "xN AND w" where w is
2226     ** the "interesting" terms of z - terms that did not originate in the
2227     ** ON or USING clause of a LEFT JOIN, and terms that are usable as
2228     ** indices.
2229     **
2230     ** This optimization also only applies if the (x1 OR x2 OR ...) term
2231     ** is not contained in the ON clause of a LEFT JOIN.
2232     ** See ticket http://www.sqlite.org/src/info/f2369304e4
2233     **
2234     ** 2022-02-04:  Do not push down slices of a row-value comparison.
2235     ** In other words, "w" or "y" may not be a slice of a vector.  Otherwise,
2236     ** the initialization of the right-hand operand of the vector comparison
2237     ** might not occur, or might occur only in an OR branch that is not
2238     ** taken.  dbsqlfuzz 80a9fade844b4fb43564efc972bcb2c68270f5d1.
2239     **
2240     ** 2022-03-03:  Do not push down expressions that involve subqueries.
2241     ** The subquery might get coded as a subroutine.  Any table-references
2242     ** in the subquery might be resolved to index-references for the index on
2243     ** the OR branch in which the subroutine is coded.  But if the subroutine
2244     ** is invoked from a different OR branch that uses a different index, such
2245     ** index-references will not work.  tag-20220303a
2246     ** https://sqlite.org/forum/forumpost/36937b197273d403
2247     */
2248     if( pWC->nTerm>1 ){
2249       int iTerm;
2250       for(iTerm=0; iTerm<pWC->nTerm; iTerm++){
2251         Expr *pExpr = pWC->a[iTerm].pExpr;
2252         if( &pWC->a[iTerm] == pTerm ) continue;
2253         testcase( pWC->a[iTerm].wtFlags & TERM_VIRTUAL );
2254         testcase( pWC->a[iTerm].wtFlags & TERM_CODED );
2255         testcase( pWC->a[iTerm].wtFlags & TERM_SLICE );
2256         if( (pWC->a[iTerm].wtFlags & (TERM_VIRTUAL|TERM_CODED|TERM_SLICE))!=0 ){
2257           continue;
2258         }
2259         if( (pWC->a[iTerm].eOperator & WO_ALL)==0 ) continue;
2260         if( ExprHasProperty(pExpr, EP_Subquery) ) continue;  /* tag-20220303a */
2261         pExpr = sqlite3ExprDup(db, pExpr, 0);
2262         pAndExpr = sqlite3ExprAnd(pParse, pAndExpr, pExpr);
2263       }
2264       if( pAndExpr ){
2265         /* The extra 0x10000 bit on the opcode is masked off and does not
2266         ** become part of the new Expr.op.  However, it does make the
2267         ** op==TK_AND comparison inside of sqlite3PExpr() false, and this
2268         ** prevents sqlite3PExpr() from applying the AND short-circuit
2269         ** optimization, which we do not want here. */
2270         pAndExpr = sqlite3PExpr(pParse, TK_AND|0x10000, 0, pAndExpr);
2271       }
2272     }
2273
2274     /* Run a separate WHERE clause for each term of the OR clause.  After
2275     ** eliminating duplicates from other WHERE clauses, the action for each
2276     ** sub-WHERE clause is to to invoke the main loop body as a subroutine.
2277     */
2278     ExplainQueryPlan((pParse, 1, "MULTI-INDEX OR"));
2279     for(ii=0; ii<pOrWc->nTerm; ii++){
2280       WhereTerm *pOrTerm = &pOrWc->a[ii];
2281       if( pOrTerm->leftCursor==iCur || (pOrTerm->eOperator & WO_AND)!=0 ){
2282         WhereInfo *pSubWInfo;           /* Info for single OR-term scan */
2283         Expr *pOrExpr = pOrTerm->pExpr; /* Current OR clause term */
2284         Expr *pDelete;                  /* Local copy of OR clause term */
2285         int jmp1 = 0;                   /* Address of jump operation */
2286         testcase( (pTabItem[0].fg.jointype & JT_LEFT)!=0
2287                && !ExprHasProperty(pOrExpr, EP_OuterON)
2288         ); /* See TH3 vtab25.400 and ticket 614b25314c766238 */
2289         pDelete = pOrExpr = sqlite3ExprDup(db, pOrExpr, 0);
2290         if( db->mallocFailed ){
2291           sqlite3ExprDelete(db, pDelete);
2292           continue;
2293         }
2294         if( pAndExpr ){
2295           pAndExpr->pLeft = pOrExpr;
2296           pOrExpr = pAndExpr;
2297         }
2298         /* Loop through table entries that match term pOrTerm. */
2299         ExplainQueryPlan((pParse, 1, "INDEX %d", ii+1));
2300         WHERETRACE(0xffffffff, ("Subplan for OR-clause:\n"));
2301         pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0, 0,
2302                                       WHERE_OR_SUBCLAUSE, iCovCur);
2303         assert( pSubWInfo || pParse->nErr );
2304         if( pSubWInfo ){
2305           WhereLoop *pSubLoop;
2306           int addrExplain = sqlite3WhereExplainOneScan(
2307               pParse, pOrTab, &pSubWInfo->a[0], 0
2308           );
2309           sqlite3WhereAddScanStatus(v, pOrTab, &pSubWInfo->a[0], addrExplain);
2310
2311           /* This is the sub-WHERE clause body.  First skip over
2312           ** duplicate rows from prior sub-WHERE clauses, and record the
2313           ** rowid (or PRIMARY KEY) for the current row so that the same
2314           ** row will be skipped in subsequent sub-WHERE clauses.
2315           */
2316           if( (pWInfo->wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
2317             int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
2318             if( HasRowid(pTab) ){
2319               sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, regRowid);
2320               jmp1 = sqlite3VdbeAddOp4Int(v, OP_RowSetTest, regRowset, 0,
2321                                           regRowid, iSet);
2322               VdbeCoverage(v);
2323             }else{
2324               Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2325               int nPk = pPk->nKeyCol;
2326               int iPk;
2327               int r;
2328
2329               /* Read the PK into an array of temp registers. */
2330               r = sqlite3GetTempRange(pParse, nPk);
2331               for(iPk=0; iPk<nPk; iPk++){
2332                 int iCol = pPk->aiColumn[iPk];
2333                 sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk);
2334               }
2335
2336               /* Check if the temp table already contains this key. If so,
2337               ** the row has already been included in the result set and
2338               ** can be ignored (by jumping past the Gosub below). Otherwise,
2339               ** insert the key into the temp table and proceed with processing
2340               ** the row.
2341               **
2342               ** Use some of the same optimizations as OP_RowSetTest: If iSet
2343               ** is zero, assume that the key cannot already be present in
2344               ** the temp table. And if iSet is -1, assume that there is no
2345               ** need to insert the key into the temp table, as it will never
2346               ** be tested for.  */
2347               if( iSet ){
2348                 jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, regRowset, 0, r, nPk);
2349                 VdbeCoverage(v);
2350               }
2351               if( iSet>=0 ){
2352                 sqlite3VdbeAddOp3(v, OP_MakeRecord, r, nPk, regRowid);
2353                 sqlite3VdbeAddOp4Int(v, OP_IdxInsert, regRowset, regRowid,
2354                                      r, nPk);
2355                 if( iSet ) sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
2356               }
2357
2358               /* Release the array of temp registers */
2359               sqlite3ReleaseTempRange(pParse, r, nPk);
2360             }
2361           }
2362
2363           /* Invoke the main loop body as a subroutine */
2364           sqlite3VdbeAddOp2(v, OP_Gosub, regReturn, iLoopBody);
2365
2366           /* Jump here (skipping the main loop body subroutine) if the
2367           ** current sub-WHERE row is a duplicate from prior sub-WHEREs. */
2368           if( jmp1 ) sqlite3VdbeJumpHere(v, jmp1);
2369
2370           /* The pSubWInfo->untestedTerms flag means that this OR term
2371           ** contained one or more AND term from a notReady table.  The
2372           ** terms from the notReady table could not be tested and will
2373           ** need to be tested later.
2374           */
2375           if( pSubWInfo->untestedTerms ) untestedTerms = 1;
2376
2377           /* If all of the OR-connected terms are optimized using the same
2378           ** index, and the index is opened using the same cursor number
2379           ** by each call to sqlite3WhereBegin() made by this loop, it may
2380           ** be possible to use that index as a covering index.
2381           **
2382           ** If the call to sqlite3WhereBegin() above resulted in a scan that
2383           ** uses an index, and this is either the first OR-connected term
2384           ** processed or the index is the same as that used by all previous
2385           ** terms, set pCov to the candidate covering index. Otherwise, set
2386           ** pCov to NULL to indicate that no candidate covering index will
2387           ** be available.
2388           */
2389           pSubLoop = pSubWInfo->a[0].pWLoop;
2390           assert( (pSubLoop->wsFlags & WHERE_AUTO_INDEX)==0 );
2391           if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0
2392            && (ii==0 || pSubLoop->u.btree.pIndex==pCov)
2393            && (HasRowid(pTab) || !IsPrimaryKeyIndex(pSubLoop->u.btree.pIndex))
2394           ){
2395             assert( pSubWInfo->a[0].iIdxCur==iCovCur );
2396             pCov = pSubLoop->u.btree.pIndex;
2397           }else{
2398             pCov = 0;
2399           }
2400           if( sqlite3WhereUsesDeferredSeek(pSubWInfo) ){
2401             pWInfo->bDeferredSeek = 1;
2402           }
2403
2404           /* Finish the loop through table entries that match term pOrTerm. */
2405           sqlite3WhereEnd(pSubWInfo);
2406           ExplainQueryPlanPop(pParse);
2407         }
2408         sqlite3ExprDelete(db, pDelete);
2409       }
2410     }
2411     ExplainQueryPlanPop(pParse);
2412     assert( pLevel->pWLoop==pLoop );
2413     assert( (pLoop->wsFlags & WHERE_MULTI_OR)!=0 );
2414     assert( (pLoop->wsFlags & WHERE_IN_ABLE)==0 );
2415     pLevel->u.pCoveringIdx = pCov;
2416     if( pCov ) pLevel->iIdxCur = iCovCur;
2417     if( pAndExpr ){
2418       pAndExpr->pLeft = 0;
2419       sqlite3ExprDelete(db, pAndExpr);
2420     }
2421     sqlite3VdbeChangeP1(v, iRetInit, sqlite3VdbeCurrentAddr(v));
2422     sqlite3VdbeGoto(v, pLevel->addrBrk);
2423     sqlite3VdbeResolveLabel(v, iLoopBody);
2424
2425     /* Set the P2 operand of the OP_Return opcode that will end the current
2426     ** loop to point to this spot, which is the top of the next containing
2427     ** loop.  The byte-code formatter will use that P2 value as a hint to
2428     ** indent everything in between the this point and the final OP_Return.
2429     ** See tag-20220407a in vdbe.c and shell.c */
2430     assert( pLevel->op==OP_Return );
2431     pLevel->p2 = sqlite3VdbeCurrentAddr(v);
2432
2433     if( pWInfo->nLevel>1 ){ sqlite3DbFreeNN(db, pOrTab); }
2434     if( !untestedTerms ) disableTerm(pLevel, pTerm);
2435   }else
2436 #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
2437
2438   {
2439     /* Case 6:  There is no usable index.  We must do a complete
2440     **          scan of the entire table.
2441     */
2442     static const u8 aStep[] = { OP_Next, OP_Prev };
2443     static const u8 aStart[] = { OP_Rewind, OP_Last };
2444     assert( bRev==0 || bRev==1 );
2445     if( pTabItem->fg.isRecursive ){
2446       /* Tables marked isRecursive have only a single row that is stored in
2447       ** a pseudo-cursor.  No need to Rewind or Next such cursors. */
2448       pLevel->op = OP_Noop;
2449     }else{
2450       codeCursorHint(pTabItem, pWInfo, pLevel, 0);
2451       pLevel->op = aStep[bRev];
2452       pLevel->p1 = iCur;
2453       pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt);
2454       VdbeCoverageIf(v, bRev==0);
2455       VdbeCoverageIf(v, bRev!=0);
2456       pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
2457     }
2458   }
2459
2460 #ifdef SQLITE_ENABLE_STMT_SCANSTATUS
2461   pLevel->addrVisit = sqlite3VdbeCurrentAddr(v);
2462 #endif
2463
2464   /* Insert code to test every subexpression that can be completely
2465   ** computed using the current set of tables.
2466   **
2467   ** This loop may run between one and three times, depending on the
2468   ** constraints to be generated. The value of stack variable iLoop
2469   ** determines the constraints coded by each iteration, as follows:
2470   **
2471   ** iLoop==1: Code only expressions that are entirely covered by pIdx.
2472   ** iLoop==2: Code remaining expressions that do not contain correlated
2473   **           sub-queries.
2474   ** iLoop==3: Code all remaining expressions.
2475   **
2476   ** An effort is made to skip unnecessary iterations of the loop.
2477   */
2478   iLoop = (pIdx ? 1 : 2);
2479   do{
2480     int iNext = 0;                /* Next value for iLoop */
2481     for(pTerm=pWC->a, j=pWC->nTerm; j>0; j--, pTerm++){
2482       Expr *pE;
2483       int skipLikeAddr = 0;
2484       testcase( pTerm->wtFlags & TERM_VIRTUAL );
2485       testcase( pTerm->wtFlags & TERM_CODED );
2486       if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2487       if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2488         testcase( pWInfo->untestedTerms==0
2489             && (pWInfo->wctrlFlags & WHERE_OR_SUBCLAUSE)!=0 );
2490         pWInfo->untestedTerms = 1;
2491         continue;
2492       }
2493       pE = pTerm->pExpr;
2494       assert( pE!=0 );
2495       if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT) ){
2496         if( !ExprHasProperty(pE,EP_OuterON|EP_InnerON) ){
2497           /* Defer processing WHERE clause constraints until after outer
2498           ** join processing.  tag-20220513a */
2499           continue;
2500         }else if( (pTabItem->fg.jointype & JT_LEFT)==JT_LEFT
2501                && !ExprHasProperty(pE,EP_OuterON) ){
2502           continue;
2503         }else{
2504           Bitmask m = sqlite3WhereGetMask(&pWInfo->sMaskSet, pE->w.iJoin);
2505           if( m & pLevel->notReady ){
2506             /* An ON clause that is not ripe */
2507             continue;
2508           }
2509         }
2510       }
2511       if( iLoop==1 && !sqlite3ExprCoveredByIndex(pE, pLevel->iTabCur, pIdx) ){
2512         iNext = 2;
2513         continue;
2514       }
2515       if( iLoop<3 && (pTerm->wtFlags & TERM_VARSELECT) ){
2516         if( iNext==0 ) iNext = 3;
2517         continue;
2518       }
2519
2520       if( (pTerm->wtFlags & TERM_LIKECOND)!=0 ){
2521         /* If the TERM_LIKECOND flag is set, that means that the range search
2522         ** is sufficient to guarantee that the LIKE operator is true, so we
2523         ** can skip the call to the like(A,B) function.  But this only works
2524         ** for strings.  So do not skip the call to the function on the pass
2525         ** that compares BLOBs. */
2526 #ifdef SQLITE_LIKE_DOESNT_MATCH_BLOBS
2527         continue;
2528 #else
2529         u32 x = pLevel->iLikeRepCntr;
2530         if( x>0 ){
2531           skipLikeAddr = sqlite3VdbeAddOp1(v, (x&1)?OP_IfNot:OP_If,(int)(x>>1));
2532           VdbeCoverageIf(v, (x&1)==1);
2533           VdbeCoverageIf(v, (x&1)==0);
2534         }
2535 #endif
2536       }
2537 #ifdef WHERETRACE_ENABLED /* 0xffffffff */
2538       if( sqlite3WhereTrace ){
2539         VdbeNoopComment((v, "WhereTerm[%d] (%p) priority=%d",
2540                          pWC->nTerm-j, pTerm, iLoop));
2541       }
2542       if( sqlite3WhereTrace & 0x4000 ){
2543         sqlite3DebugPrintf("Coding auxiliary constraint:\n");
2544         sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2545       }
2546 #endif
2547       sqlite3ExprIfFalse(pParse, pE, addrCont, SQLITE_JUMPIFNULL);
2548       if( skipLikeAddr ) sqlite3VdbeJumpHere(v, skipLikeAddr);
2549       pTerm->wtFlags |= TERM_CODED;
2550     }
2551     iLoop = iNext;
2552   }while( iLoop>0 );
2553
2554   /* Insert code to test for implied constraints based on transitivity
2555   ** of the "==" operator.
2556   **
2557   ** Example: If the WHERE clause contains "t1.a=t2.b" and "t2.b=123"
2558   ** and we are coding the t1 loop and the t2 loop has not yet coded,
2559   ** then we cannot use the "t1.a=t2.b" constraint, but we can code
2560   ** the implied "t1.a=123" constraint.
2561   */
2562   for(pTerm=pWC->a, j=pWC->nBase; j>0; j--, pTerm++){
2563     Expr *pE, sEAlt;
2564     WhereTerm *pAlt;
2565     if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2566     if( (pTerm->eOperator & (WO_EQ|WO_IS))==0 ) continue;
2567     if( (pTerm->eOperator & WO_EQUIV)==0 ) continue;
2568     if( pTerm->leftCursor!=iCur ) continue;
2569     if( pTabItem->fg.jointype & (JT_LEFT|JT_LTORJ|JT_RIGHT) ) continue;
2570     pE = pTerm->pExpr;
2571 #ifdef WHERETRACE_ENABLED /* 0x4001 */
2572     if( (sqlite3WhereTrace & 0x4001)==0x4001 ){
2573       sqlite3DebugPrintf("Coding transitive constraint:\n");
2574       sqlite3WhereTermPrint(pTerm, pWC->nTerm-j);
2575     }
2576 #endif
2577     assert( !ExprHasProperty(pE, EP_OuterON) );
2578     assert( (pTerm->prereqRight & pLevel->notReady)!=0 );
2579     assert( (pTerm->eOperator & (WO_OR|WO_AND))==0 );
2580     pAlt = sqlite3WhereFindTerm(pWC, iCur, pTerm->u.x.leftColumn, notReady,
2581                     WO_EQ|WO_IN|WO_IS, 0);
2582     if( pAlt==0 ) continue;
2583     if( pAlt->wtFlags & (TERM_CODED) ) continue;
2584     if( (pAlt->eOperator & WO_IN)
2585      && ExprUseXSelect(pAlt->pExpr)
2586      && (pAlt->pExpr->x.pSelect->pEList->nExpr>1)
2587     ){
2588       continue;
2589     }
2590     testcase( pAlt->eOperator & WO_EQ );
2591     testcase( pAlt->eOperator & WO_IS );
2592     testcase( pAlt->eOperator & WO_IN );
2593     VdbeModuleComment((v, "begin transitive constraint"));
2594     sEAlt = *pAlt->pExpr;
2595     sEAlt.pLeft = pE->pLeft;
2596     sqlite3ExprIfFalse(pParse, &sEAlt, addrCont, SQLITE_JUMPIFNULL);
2597     pAlt->wtFlags |= TERM_CODED;
2598   }
2599
2600   /* For a RIGHT OUTER JOIN, record the fact that the current row has
2601   ** been matched at least once.
2602   */
2603   if( pLevel->pRJ ){
2604     Table *pTab;
2605     int nPk;
2606     int r;
2607     int jmp1 = 0;
2608     WhereRightJoin *pRJ = pLevel->pRJ;
2609
2610     /* pTab is the right-hand table of the RIGHT JOIN.  Generate code that
2611     ** will record that the current row of that table has been matched at
2612     ** least once.  This is accomplished by storing the PK for the row in
2613     ** both the iMatch index and the regBloom Bloom filter.
2614     */
2615     pTab = pWInfo->pTabList->a[pLevel->iFrom].pTab;
2616     if( HasRowid(pTab) ){
2617       r = sqlite3GetTempRange(pParse, 2);
2618       sqlite3ExprCodeGetColumnOfTable(v, pTab, pLevel->iTabCur, -1, r+1);
2619       nPk = 1;
2620     }else{
2621       int iPk;
2622       Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2623       nPk = pPk->nKeyCol;
2624       r = sqlite3GetTempRange(pParse, nPk+1);
2625       for(iPk=0; iPk<nPk; iPk++){
2626         int iCol = pPk->aiColumn[iPk];
2627         sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+1+iPk);
2628       }
2629     }
2630     jmp1 = sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, 0, r+1, nPk);
2631     VdbeCoverage(v);
2632     VdbeComment((v, "match against %s", pTab->zName));
2633     sqlite3VdbeAddOp3(v, OP_MakeRecord, r+1, nPk, r);
2634     sqlite3VdbeAddOp4Int(v, OP_IdxInsert, pRJ->iMatch, r, r+1, nPk);
2635     sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pRJ->regBloom, 0, r+1, nPk);
2636     sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT);
2637     sqlite3VdbeJumpHere(v, jmp1);
2638     sqlite3ReleaseTempRange(pParse, r, nPk+1);
2639   }
2640
2641   /* For a LEFT OUTER JOIN, generate code that will record the fact that
2642   ** at least one row of the right table has matched the left table.
2643   */
2644   if( pLevel->iLeftJoin ){
2645     pLevel->addrFirst = sqlite3VdbeCurrentAddr(v);
2646     sqlite3VdbeAddOp2(v, OP_Integer, 1, pLevel->iLeftJoin);
2647     VdbeComment((v, "record LEFT JOIN hit"));
2648     if( pLevel->pRJ==0 ){
2649       goto code_outer_join_constraints; /* WHERE clause constraints */
2650     }
2651   }
2652
2653   if( pLevel->pRJ ){
2654     /* Create a subroutine used to process all interior loops and code
2655     ** of the RIGHT JOIN.  During normal operation, the subroutine will
2656     ** be in-line with the rest of the code.  But at the end, a separate
2657     ** loop will run that invokes this subroutine for unmatched rows
2658     ** of pTab, with all tables to left begin set to NULL.
2659     */
2660     WhereRightJoin *pRJ = pLevel->pRJ;
2661     sqlite3VdbeAddOp2(v, OP_BeginSubrtn, 0, pRJ->regReturn);
2662     pRJ->addrSubrtn = sqlite3VdbeCurrentAddr(v);
2663     assert( pParse->withinRJSubrtn < 255 );
2664     pParse->withinRJSubrtn++;
2665
2666     /* WHERE clause constraints must be deferred until after outer join
2667     ** row elimination has completed, since WHERE clause constraints apply
2668     ** to the results of the OUTER JOIN.  The following loop generates the
2669     ** appropriate WHERE clause constraint checks.  tag-20220513a.
2670     */
2671   code_outer_join_constraints:
2672     for(pTerm=pWC->a, j=0; j<pWC->nBase; j++, pTerm++){
2673       testcase( pTerm->wtFlags & TERM_VIRTUAL );
2674       testcase( pTerm->wtFlags & TERM_CODED );
2675       if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue;
2676       if( (pTerm->prereqAll & pLevel->notReady)!=0 ){
2677         assert( pWInfo->untestedTerms );
2678         continue;
2679       }
2680       if( pTabItem->fg.jointype & JT_LTORJ ) continue;
2681       assert( pTerm->pExpr );
2682       sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL);
2683       pTerm->wtFlags |= TERM_CODED;
2684     }
2685   }
2686
2687 #if WHERETRACE_ENABLED /* 0x4001 */
2688   if( sqlite3WhereTrace & 0x4000 ){
2689     sqlite3DebugPrintf("All WHERE-clause terms after coding level %d:\n",
2690                        iLevel);
2691     sqlite3WhereClausePrint(pWC);
2692   }
2693   if( sqlite3WhereTrace & 0x1 ){
2694     sqlite3DebugPrintf("End Coding level %d:  notReady=%llx\n",
2695        iLevel, (u64)pLevel->notReady);
2696   }
2697 #endif
2698   return pLevel->notReady;
2699 }
2700
2701 /*
2702 ** Generate the code for the loop that finds all non-matched terms
2703 ** for a RIGHT JOIN.
2704 */
2705 SQLITE_NOINLINE void sqlite3WhereRightJoinLoop(
2706   WhereInfo *pWInfo,
2707   int iLevel,
2708   WhereLevel *pLevel
2709 ){
2710   Parse *pParse = pWInfo->pParse;
2711   Vdbe *v = pParse->pVdbe;
2712   WhereRightJoin *pRJ = pLevel->pRJ;
2713   Expr *pSubWhere = 0;
2714   WhereClause *pWC = &pWInfo->sWC;
2715   WhereInfo *pSubWInfo;
2716   WhereLoop *pLoop = pLevel->pWLoop;
2717   SrcItem *pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
2718   SrcList sFrom;
2719   Bitmask mAll = 0;
2720   int k;
2721
2722   ExplainQueryPlan((pParse, 1, "RIGHT-JOIN %s", pTabItem->pTab->zName));
2723   sqlite3VdbeNoJumpsOutsideSubrtn(v, pRJ->addrSubrtn, pRJ->endSubrtn,
2724                                   pRJ->regReturn);
2725   for(k=0; k<iLevel; k++){
2726     int iIdxCur;
2727     mAll |= pWInfo->a[k].pWLoop->maskSelf;
2728     sqlite3VdbeAddOp1(v, OP_NullRow, pWInfo->a[k].iTabCur);
2729     iIdxCur = pWInfo->a[k].iIdxCur;
2730     if( iIdxCur ){
2731       sqlite3VdbeAddOp1(v, OP_NullRow, iIdxCur);
2732     }
2733   }
2734   if( (pTabItem->fg.jointype & JT_LTORJ)==0 ){
2735     mAll |= pLoop->maskSelf;
2736     for(k=0; k<pWC->nTerm; k++){
2737       WhereTerm *pTerm = &pWC->a[k];
2738       if( (pTerm->wtFlags & (TERM_VIRTUAL|TERM_SLICE))!=0
2739        && pTerm->eOperator!=WO_ROWVAL
2740       ){
2741         break;
2742       }
2743       if( pTerm->prereqAll & ~mAll ) continue;
2744       if( ExprHasProperty(pTerm->pExpr, EP_OuterON|EP_InnerON) ) continue;
2745       pSubWhere = sqlite3ExprAnd(pParse, pSubWhere,
2746                                  sqlite3ExprDup(pParse->db, pTerm->pExpr, 0));
2747     }
2748   }
2749   sFrom.nSrc = 1;
2750   sFrom.nAlloc = 1;
2751   memcpy(&sFrom.a[0], pTabItem, sizeof(SrcItem));
2752   sFrom.a[0].fg.jointype = 0;
2753   assert( pParse->withinRJSubrtn < 100 );
2754   pParse->withinRJSubrtn++;
2755   pSubWInfo = sqlite3WhereBegin(pParse, &sFrom, pSubWhere, 0, 0, 0,
2756                                 WHERE_RIGHT_JOIN, 0);
2757   if( pSubWInfo ){
2758     int iCur = pLevel->iTabCur;
2759     int r = ++pParse->nMem;
2760     int nPk;
2761     int jmp;
2762     int addrCont = sqlite3WhereContinueLabel(pSubWInfo);
2763     Table *pTab = pTabItem->pTab;
2764     if( HasRowid(pTab) ){
2765       sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, -1, r);
2766       nPk = 1;
2767     }else{
2768       int iPk;
2769       Index *pPk = sqlite3PrimaryKeyIndex(pTab);
2770       nPk = pPk->nKeyCol;
2771       pParse->nMem += nPk - 1;
2772       for(iPk=0; iPk<nPk; iPk++){
2773         int iCol = pPk->aiColumn[iPk];
2774         sqlite3ExprCodeGetColumnOfTable(v, pTab, iCur, iCol,r+iPk);
2775       }
2776     }
2777     jmp = sqlite3VdbeAddOp4Int(v, OP_Filter, pRJ->regBloom, 0, r, nPk);
2778     VdbeCoverage(v);
2779     sqlite3VdbeAddOp4Int(v, OP_Found, pRJ->iMatch, addrCont, r, nPk);
2780     VdbeCoverage(v);
2781     sqlite3VdbeJumpHere(v, jmp);
2782     sqlite3VdbeAddOp2(v, OP_Gosub, pRJ->regReturn, pRJ->addrSubrtn);
2783     sqlite3WhereEnd(pSubWInfo);
2784   }
2785   sqlite3ExprDelete(pParse->db, pSubWhere);
2786   ExplainQueryPlanPop(pParse);
2787   assert( pParse->withinRJSubrtn>0 );
2788   pParse->withinRJSubrtn--;
2789 }