exprAnalyze(pSrc, pMaskSet, pWC, idxNew1);    pNewExpr2 = sqlite3Expr(TK_LT, sqlite3ExprDup(pLeft), pStr2, 0);    idxNew2 = whereClauseInsert(pWC, pNewExpr2, TERM_VIRTUAL|TERM_DYNAMIC);    exprAnalyze(pSrc, pMaskSet, pWC, idxNew2);    pTerm = &pWC->a[idxTerm];    if( isComplete ){      pWC->a[idxNew1].iParent = idxTerm;      pWC->a[idxNew2].iParent = idxTerm;      pTerm->nChild = 2;    }  }#endif /* SQLITE_OMIT_LIKE_OPTIMIZATION */}/*** This routine decides if pIdx can be used to satisfy the ORDER BY** clause.  If it can, it returns 1.  If pIdx cannot satisfy the** ORDER BY clause, this routine returns 0.**** pOrderBy is an ORDER BY clause from a SELECT statement.  pTab is the** left-most table in the FROM clause of that same SELECT statement and** the table has a cursor number of "base".  pIdx is an index on pTab.**** nEqCol is the number of columns of pIdx that are used as equality** constraints.  Any of these columns may be missing from the ORDER BY** clause and the match can still be a success.**** All terms of the ORDER BY that match against the index must be either** ASC or DESC.  (Terms of the ORDER BY clause past the end of a UNIQUE** index do not need to satisfy this constraint.)  The *pbRev value is** set to 1 if the ORDER BY clause is all DESC and it is set to 0 if** the ORDER BY clause is all ASC.*/static int isSortingIndex(  Parse *pParse,          /* Parsing context */  Index *pIdx,            /* The index we are testing */  int base,               /* Cursor number for the table to be sorted */  ExprList *pOrderBy,     /* The ORDER BY clause */  int nEqCol,             /* Number of index columns with == constraints */  int *pbRev              /* Set to 1 if ORDER BY is DESC */){  int i, j;                       /* Loop counters */  int sortOrder = 0;              /* XOR of index and ORDER BY sort direction */  int nTerm;                      /* Number of ORDER BY terms */  struct ExprList_item *pTerm;    /* A term of the ORDER BY clause */  sqlite3 *db = pParse->db;  assert( pOrderBy!=0 );  nTerm = pOrderBy->nExpr;  assert( nTerm>0 );  /* Match terms of the ORDER BY clause against columns of  ** the index.  */  for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){    Expr *pExpr;       /* The expression of the ORDER BY pTerm */    CollSeq *pColl;    /* The collating sequence of pExpr */    int termSortOrder; /* Sort order for this term */    pExpr = pTerm->pExpr;    if( pExpr->op!=TK_COLUMN || pExpr->iTable!=base ){      /* Can not use an index sort on anything that is not a column in the      ** left-most table of the FROM clause */      return 0;    }    pColl = sqlite3ExprCollSeq(pParse, pExpr);    if( !pColl ) pColl = db->pDfltColl;    if( pExpr->iColumn!=pIdx->aiColumn[i] ||         sqlite3StrICmp(pColl->zName, pIdx->azColl[i]) ){      /* Term j of the ORDER BY clause does not match column i of the index */      if( i<nEqCol ){        /* If an index column that is constrained by == fails to match an        ** ORDER BY term, that is OK.  Just ignore that column of the index        */        continue;      }else{        /* If an index column fails to match and is not constrained by ==        ** then the index cannot satisfy the ORDER BY constraint.        */        return 0;      }    }    assert( pIdx->aSortOrder!=0 );    assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );    assert( pIdx->aSortOrder[i]==0 || pIdx->aSortOrder[i]==1 );    termSortOrder = pIdx->aSortOrder[i] ^ pTerm->sortOrder;    if( i>nEqCol ){      if( termSortOrder!=sortOrder ){        /* Indices can only be used if all ORDER BY terms past the        ** equality constraints are all either DESC or ASC. */        return 0;      }    }else{      sortOrder = termSortOrder;    }    j++;    pTerm++;  }  /* The index can be used for sorting if all terms of the ORDER BY clause  ** are covered.  */  if( j>=nTerm ){    *pbRev = sortOrder!=0;    return 1;  }  return 0;}/*** Check table to see if the ORDER BY clause in pOrderBy can be satisfied** by sorting in order of ROWID.  Return true if so and set *pbRev to be** true for reverse ROWID and false for forward ROWID order.*/static int sortableByRowid(  int base,               /* Cursor number for table to be sorted */  ExprList *pOrderBy,     /* The ORDER BY clause */  int *pbRev              /* Set to 1 if ORDER BY is DESC */){  Expr *p;  assert( pOrderBy!=0 );  assert( pOrderBy->nExpr>0 );  p = pOrderBy->a[0].pExpr;  if( pOrderBy->nExpr==1 && p->op==TK_COLUMN && p->iTable==base          && p->iColumn==-1 ){    *pbRev = pOrderBy->a[0].sortOrder;    return 1;  }  return 0;}/*** Prepare a crude estimate of the logarithm of the input value.** The results need not be exact.  This is only used for estimating** the total cost of performing operatings with O(logN) or O(NlogN)** complexity.  Because N is just a guess, it is no great tragedy if** logN is a little off.*/static double estLog(double N){  double logN = 1;  double x = 10;  while( N>x ){    logN += 1;    x *= 10;  }  return logN;}/*** Find the best index for accessing a particular table.  Return a pointer** to the index, flags that describe how the index should be used, the** number of equality constraints, and the "cost" for this index.**** The lowest cost index wins.  The cost is an estimate of the amount of** CPU and disk I/O need to process the request using the selected index.** Factors that influence cost include:****    *  The estimated number of rows that will be retrieved.  (The**       fewer the better.)****    *  Whether or not sorting must occur.****    *  Whether or not there must be separate lookups in the**       index and in the main table.***/static double bestIndex(  Parse *pParse,              /* The parsing context */  WhereClause *pWC,           /* The WHERE clause */  struct SrcList_item *pSrc,  /* The FROM clause term to search */  Bitmask notReady,           /* Mask of cursors that are not available */  ExprList *pOrderBy,         /* The order by clause */  Index **ppIndex,            /* Make *ppIndex point to the best index */  int *pFlags,                /* Put flags describing this choice in *pFlags */  int *pnEq                   /* Put the number of == or IN constraints here */){  WhereTerm *pTerm;  Index *bestIdx = 0;         /* Index that gives the lowest cost */  double lowestCost;          /* The cost of using bestIdx */  int bestFlags = 0;          /* Flags associated with bestIdx */  int bestNEq = 0;            /* Best value for nEq */  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */  Index *pProbe;              /* An index we are evaluating */  int rev;                    /* True to scan in reverse order */  int flags;                  /* Flags associated with pProbe */  int nEq;                    /* Number of == or IN constraints */  double cost;                /* Cost of using pProbe */  TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady));  lowestCost = SQLITE_BIG_DBL;  pProbe = pSrc->pTab->pIndex;  /* If the table has no indices and there are no terms in the where  ** clause that refer to the ROWID, then we will never be able to do  ** anything other than a full table scan on this table.  We might as  ** well put it first in the join order.  That way, perhaps it can be  ** referenced by other tables in the join.  */  if( pProbe==0 &&     findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&     (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, &rev)) ){    *pFlags = 0;    *ppIndex = 0;    *pnEq = 0;    return 0.0;  }  /* Check for a rowid=EXPR or rowid IN (...) constraints  */  pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);  if( pTerm ){    Expr *pExpr;    *ppIndex = 0;    bestFlags = WHERE_ROWID_EQ;    if( pTerm->eOperator & WO_EQ ){      /* Rowid== is always the best pick.  Look no further.  Because only      ** a single row is generated, output is always in sorted order */      *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;      *pnEq = 1;      TRACE(("... best is rowid\n"));      return 0.0;    }else if( (pExpr = pTerm->pExpr)->pList!=0 ){      /* Rowid IN (LIST): cost is NlogN where N is the number of list      ** elements.  */      lowestCost = pExpr->pList->nExpr;      lowestCost *= estLog(lowestCost);    }else{      /* Rowid IN (SELECT): cost is NlogN where N is the number of rows      ** in the result of the inner select.  We have no way to estimate      ** that value so make a wild guess. */      lowestCost = 200;    }    TRACE(("... rowid IN cost: %.9g\n", lowestCost));  }  /* Estimate the cost of a table scan.  If we do not know how many  ** entries are in the table, use 1 million as a guess.  */  cost = pProbe ? pProbe->aiRowEst[0] : 1000000;  TRACE(("... table scan base cost: %.9g\n", cost));  flags = WHERE_ROWID_RANGE;  /* Check for constraints on a range of rowids in a table scan.  */  pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);  if( pTerm ){    if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){      flags |= WHERE_TOP_LIMIT;      cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds or rows */    }    if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){      flags |= WHERE_BTM_LIMIT;      cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */    }    TRACE(("... rowid range reduces cost to %.9g\n", cost));  }else{    flags = 0;  }  /* If the table scan does not satisfy the ORDER BY clause, increase  ** the cost by NlogN to cover the expense of sorting. */  if( pOrderBy ){    if( sortableByRowid(iCur, pOrderBy, &rev) ){      flags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;      if( rev ){        flags |= WHERE_REVERSE;      }    }else{      cost += cost*estLog(cost);      TRACE(("... sorting increases cost to %.9g\n", cost));    }  }  if( cost<lowestCost ){    lowestCost = cost;    bestFlags = flags;  }  /* Look at each index.  */  for(; pProbe; pProbe=pProbe->pNext){    int i;                       /* Loop counter */    double inMultiplier = 1;    TRACE(("... index %s:\n", pProbe->zName));    /* Count the number of columns in the index that are satisfied    ** by x=EXPR constraints or x IN (...) constraints.    */    flags = 0;    for(i=0; i<pProbe->nColumn; i++){      int j = pProbe->aiColumn[i];      pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN, pProbe);      if( pTerm==0 ) break;      flags |= WHERE_COLUMN_EQ;      if( pTerm->eOperator & WO_IN ){        Expr *pExpr = pTerm->pExpr;        flags |= WHERE_COLUMN_IN;        if( pExpr->pSelect!=0 ){          inMultiplier *= 100;        }else if( pExpr->pList!=0 ){          inMultiplier *= pExpr->pList->nExpr + 1;        }      }    }    cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier);    nEq = i;    if( pProbe->onError!=OE_None && (flags & WHERE_COLUMN_IN)==0         && nEq==pProbe->nColumn ){      flags |= WHERE_UNIQUE;    }    TRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost));    /* Look for range constraints    */    if( nEq<pProbe->nColumn ){      int j = pProbe->aiColumn[nEq];      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);      if( pTerm ){        flags |= WHERE_COLUMN_RANGE;        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){          flags |= WHERE_TOP_LIMIT;          cost /= 3;        }        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){          flags |= WHERE_BTM_LIMIT;          cost /= 3;        }        TRACE(("...... range reduces cost to %.9g\n", cost));      }    }    /* Add the additional cost of sorting if that is a factor.    */    if( pOrderBy ){      if( (flags & WHERE_COLUMN_IN)==0 &&           isSortingIndex(pParse,pProbe,iCur,pOrderBy,nEq,&rev) ){        if( flags==0 ){          flags = WHERE_COLUMN_RANGE;        }        flags |= WHERE_ORDERBY;        if( rev ){          flags |= WHERE_REVERSE;        }      }else{        cost += cost*estLog(cost);        TRACE(("...... orderby increases cost to %.9g\n", cost));      }    }    /* Check to see if we can get away with using just the index without    ** ever reading the table.  If that is the case, then halve the    ** cost of this index.    */    if( flags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){      Bitmask m = pSrc->colUsed;      int j;      for(j=0; j<pProbe->nColumn; j++){        int x = pProbe->aiColumn[j];        if( x<BMS-1 ){          m &= ~(((Bitmask)1)<<x);        }      }      if( m==0 ){        flags |= WHERE_IDX_ONLY;        cost /= 2;        TRACE(("...... idx-only reduces cost to %.9g\n", cost));