}    }    /* If this index has achieved the lowest cost so far, then use it.    */    if( cost < lowestCost ){      bestIdx = pProbe;      lowestCost = cost;      assert( flags!=0 );      bestFlags = flags;      bestNEq = nEq;    }  }  /* Report the best result  */  *ppIndex = bestIdx;  TRACE(("best index is %s, cost=%.9g, flags=%x, nEq=%d\n",        bestIdx ? bestIdx->zName : "(none)", lowestCost, bestFlags, bestNEq));  *pFlags = bestFlags;  *pnEq = bestNEq;  return lowestCost;}/*** Disable a term in the WHERE clause.  Except, do not disable the term** if it controls a LEFT OUTER JOIN and it did not originate in the ON** or USING clause of that join.**** Consider the term t2.z='ok' in the following queries:****   (1)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x WHERE t2.z='ok'**   (2)  SELECT * FROM t1 LEFT JOIN t2 ON t1.a=t2.x AND t2.z='ok'**   (3)  SELECT * FROM t1, t2 WHERE t1.a=t2.x AND t2.z='ok'**** The t2.z='ok' is disabled in the in (2) because it originates** in the ON clause.  The term is disabled in (3) because it is not part** of a LEFT OUTER JOIN.  In (1), the term is not disabled.**** Disabling a term causes that term to not be tested in the inner loop** of the join.  Disabling is an optimization.  When terms are satisfied** by indices, we disable them to prevent redundant tests in the inner** loop.  We would get the correct results if nothing were ever disabled,** but joins might run a little slower.  The trick is to disable as much** as we can without disabling too much.  If we disabled in (1), we'd get** the wrong answer.  See ticket #813.*/static void disableTerm(WhereLevel *pLevel, WhereTerm *pTerm){  if( pTerm      && (pTerm->flags & TERM_CODED)==0      && (pLevel->iLeftJoin==0 || ExprHasProperty(pTerm->pExpr, EP_FromJoin))  ){    pTerm->flags |= TERM_CODED;    if( pTerm->iParent>=0 ){      WhereTerm *pOther = &pTerm->pWC->a[pTerm->iParent];      if( (--pOther->nChild)==0 ){        disableTerm(pLevel, pOther);      }    }  }}/*** Generate code that builds a probe for an index.  Details:****    *  Check the top nColumn entries on the stack.  If any**       of those entries are NULL, jump immediately to brk,**       which is the loop exit, since no index entry will match**       if any part of the key is NULL. Pop (nColumn+nExtra) **       elements from the stack.****    *  Construct a probe entry from the top nColumn entries in**       the stack with affinities appropriate for index pIdx. **       Only nColumn elements are popped from the stack in this case**       (by OP_MakeRecord).***/static void buildIndexProbe(  Vdbe *v,   int nColumn,   int nExtra,   int brk,   Index *pIdx){  sqlite3VdbeAddOp(v, OP_NotNull, -nColumn, sqlite3VdbeCurrentAddr(v)+3);  sqlite3VdbeAddOp(v, OP_Pop, nColumn+nExtra, 0);  sqlite3VdbeAddOp(v, OP_Goto, 0, brk);  sqlite3VdbeAddOp(v, OP_MakeRecord, nColumn, 0);  sqlite3IndexAffinityStr(v, pIdx);}/*** Generate code for a single equality term of the WHERE clause.  An equality** term can be either X=expr or X IN (...).   pTerm is the term to be ** coded.**** The current value for the constraint is left on the top of the stack.**** For a constraint of the form X=expr, the expression is evaluated and its** result is left on the stack.  For constraints of the form X IN (...)** this routine sets up a loop that will iterate over all values of X.*/static void codeEqualityTerm(  Parse *pParse,      /* The parsing context */  WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */  int brk,            /* Jump here to abandon the loop */  WhereLevel *pLevel  /* When level of the FROM clause we are working on */){  Expr *pX = pTerm->pExpr;  if( pX->op!=TK_IN ){    assert( pX->op==TK_EQ );    sqlite3ExprCode(pParse, pX->pRight);#ifndef SQLITE_OMIT_SUBQUERY  }else{    int iTab;    int *aIn;    Vdbe *v = pParse->pVdbe;    sqlite3CodeSubselect(pParse, pX);    iTab = pX->iTable;    sqlite3VdbeAddOp(v, OP_Rewind, iTab, brk);    VdbeComment((v, "# %.*s", pX->span.n, pX->span.z));    pLevel->nIn++;    sqliteReallocOrFree((void**)&pLevel->aInLoop,                                 sizeof(pLevel->aInLoop[0])*3*pLevel->nIn);    aIn = pLevel->aInLoop;    if( aIn ){      aIn += pLevel->nIn*3 - 3;      aIn[0] = OP_Next;      aIn[1] = iTab;      aIn[2] = sqlite3VdbeAddOp(v, OP_Column, iTab, 0);    }else{      pLevel->nIn = 0;    }#endif  }  disableTerm(pLevel, pTerm);}/*** Generate code that will evaluate all == and IN constraints for an** index.  The values for all constraints are left on the stack.**** For example, consider table t1(a,b,c,d,e,f) with index i1(a,b,c).** Suppose the WHERE clause is this:  a==5 AND b IN (1,2,3) AND c>5 AND c<10** The index has as many as three equality constraints, but in this** example, the third "c" value is an inequality.  So only two ** constraints are coded.  This routine will generate code to evaluate** a==5 and b IN (1,2,3).  The current values for a and b will be left** on the stack - a is the deepest and b the shallowest.**** In the example above nEq==2.  But this subroutine works for any value** of nEq including 0.  If nEq==0, this routine is nearly a no-op.** The only thing it does is allocate the pLevel->iMem memory cell.**** This routine always allocates at least one memory cell and puts** the address of that memory cell in pLevel->iMem.  The code that** calls this routine will use pLevel->iMem to store the termination** key value of the loop.  If one or more IN operators appear, then** this routine allocates an additional nEq memory cells for internal** use.*/static void codeAllEqualityTerms(  Parse *pParse,        /* Parsing context */  WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */  WhereClause *pWC,     /* The WHERE clause */  Bitmask notReady,     /* Which parts of FROM have not yet been coded */  int brk               /* Jump here to end the loop */){  int nEq = pLevel->nEq;        /* The number of == or IN constraints to code */  int termsInMem = 0;           /* If true, store value in mem[] cells */  Vdbe *v = pParse->pVdbe;      /* The virtual machine under construction */  Index *pIdx = pLevel->pIdx;   /* The index being used for this loop */  int iCur = pLevel->iTabCur;   /* The cursor of the table */  WhereTerm *pTerm;             /* A single constraint term */  int j;                        /* Loop counter */  /* Figure out how many memory cells we will need then allocate them.  ** We always need at least one used to store the loop terminator  ** value.  If there are IN operators we'll need one for each == or  ** IN constraint.  */  pLevel->iMem = pParse->nMem++;  if( pLevel->flags & WHERE_COLUMN_IN ){    pParse->nMem += pLevel->nEq;    termsInMem = 1;  }  /* Evaluate the equality constraints  */  for(j=0; j<pIdx->nColumn; j++){    int k = pIdx->aiColumn[j];    pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN, pIdx);    if( pTerm==0 ) break;    assert( (pTerm->flags & TERM_CODED)==0 );    codeEqualityTerm(pParse, pTerm, brk, pLevel);    if( termsInMem ){      sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1);    }  }  assert( j==nEq );  /* Make sure all the constraint values are on the top of the stack  */  if( termsInMem ){    for(j=0; j<nEq; j++){      sqlite3VdbeAddOp(v, OP_MemLoad, pLevel->iMem+j+1, 0);    }  }}#if defined(SQLITE_TEST)/*** The following variable holds a text description of query plan generated** by the most recent call to sqlite3WhereBegin().  Each call to WhereBegin** overwrites the previous.  This information is used for testing and** analysis only.*/char sqlite3_query_plan[BMS*2*40];  /* Text of the join */static int nQPlan = 0;              /* Next free slow in _query_plan[] */#endif /* SQLITE_TEST *//*** Generate the beginning of the loop used for WHERE clause processing.** The return value is a pointer to an opaque structure that contains** information needed to terminate the loop.  Later, the calling routine** should invoke sqlite3WhereEnd() with the return value of this function** in order to complete the WHERE clause processing.**** If an error occurs, this routine returns NULL.**** The basic idea is to do a nested loop, one loop for each table in** the FROM clause of a select.  (INSERT and UPDATE statements are the** same as a SELECT with only a single table in the FROM clause.)  For** example, if the SQL is this:****       SELECT * FROM t1, t2, t3 WHERE ...;**** Then the code generated is conceptually like the following:****      foreach row1 in t1 do       \    Code generated**        foreach row2 in t2 do      |-- by sqlite3WhereBegin()**          foreach row3 in t3 do   /**            ...**          end                     \    Code generated**        end                        |-- by sqlite3WhereEnd()**      end                         /**** Note that the loops might not be nested in the order in which they** appear in the FROM clause if a different order is better able to make** use of indices.  Note also that when the IN operator appears in** the WHERE clause, it might result in additional nested loops for** scanning through all values on the right-hand side of the IN.**** There are Btree cursors associated with each table.  t1 uses cursor** number pTabList->a[0].iCursor.  t2 uses the cursor pTabList->a[1].iCursor.** And so forth.  This routine generates code to open those VDBE cursors** and sqlite3WhereEnd() generates the code to close them.**** The code that sqlite3WhereBegin() generates leaves the cursors named** in pTabList pointing at their appropriate entries.  The [...] code** can use OP_Column and OP_Rowid opcodes on these cursors to extract** data from the various tables of the loop.**** If the WHERE clause is empty, the foreach loops must each scan their** entire tables.  Thus a three-way join is an O(N^3) operation.  But if** the tables have indices and there are terms in the WHERE clause that** refer to those indices, a complete table scan can be avoided and the** code will run much faster.  Most of the work of this routine is checking** to see if there are indices that can be used to speed up the loop.**** Terms of the WHERE clause are also used to limit which rows actually** make it to the "..." in the middle of the loop.  After each "foreach",** terms of the WHERE clause that use only terms in that loop and outer** loops are evaluated and if false a jump is made around all subsequent** inner loops (or around the "..." if the test occurs within the inner-** most loop)**** OUTER JOINS**** An outer join of tables t1 and t2 is conceptally coded as follows:****    foreach row1 in t1 do**      flag = 0**      foreach row2 in t2 do**        start:**          ...**          flag = 1**      end**      if flag==0 then**        move the row2 cursor to a null row**        goto start**      fi**    end**** ORDER BY CLAUSE PROCESSING**** *ppOrderBy is a pointer to the ORDER BY clause of a SELECT statement,** if there is one.  If there is no ORDER BY clause or if this routine** is called from an UPDATE or DELETE statement, then ppOrderBy is NULL.**** If an index can be used so that the natural output order of the table** scan is correct for the ORDER BY clause, then that index is used and** *ppOrderBy is set to NULL.  This is an optimization that prevents an** unnecessary sort of the result set if an index appropriate for the** ORDER BY clause already exists.**** If the where clause loops cannot be arranged to provide the correct** output order, then the *ppOrderBy is unchanged.*/WhereInfo *sqlite3WhereBegin(  Parse *pParse,        /* The parser context */  SrcList *pTabList,    /* A list of all tables to be scanned */  Expr *pWhere,         /* The WHERE clause */  ExprList **ppOrderBy  /* An ORDER BY clause, or NULL */){  int i;                     /* Loop counter */  WhereInfo *pWInfo;         /* Will become the return value of this function */  Vdbe *v = pParse->pVdbe;   /* The virtual database engine */  int brk, cont = 0;         /* Addresses used during code generation */  Bitmask notReady;          /* Cursors that are not yet positioned */  WhereTerm *pTerm;          /* A single term in the WHERE clause */  ExprMaskSet maskSet;       /* The expression mask set */  WhereClause wc;            /* The WHERE clause is divided into these terms */  struct SrcList_item *pTabItem;  /* A single entry from pTabList */  WhereLevel *pLevel;             /* A single level in the pWInfo list */  int iFrom;                      /* First unused FROM clause element */  int andFlags;              /* AND-ed combination of all wc.a[].flags */  /* The number of tables in the FROM clause is limited by the number of  ** bits in a Bitmask   */  if( pTabList->nSrc>BMS ){    sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS);    return 0;  }  /* Split the WHERE clause into separate subexpressions where each  ** subexpression is separated by an AND operator.  */  initMaskSet(&maskSet);  whereClauseInit(&wc, pParse);  whereSplit(&wc, pWhere, TK_AND);      /* Allocate and initialize the WhereInfo structure that will become the  ** return value.  */  pWInfo = sqliteMalloc( sizeof(WhereInfo) + pTabList->nSrc*sizeof(WhereLevel));  if( sqlite3MallocFailed() ){    goto whereBeginNoMem;  }  pWInfo->pParse = pParse;  pWInfo->pTabList = pTabList;  pWInfo->iBreak = sqlite3VdbeMakeLabel(v);  /* Special case: a WHERE clause that is constant.  Evaluate the  ** expression and either jump over all of the code or fall thru.  */  if( pWhere && (pTabList->nSrc==0 || sqlite3ExprIsConstant(pWhere)) ){    sqlite3ExprIfFalse(pParse, pWhere, pWInfo->iBreak, 1);    pWhere = 0;  }