/ Check-in [001539df]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Cut over the NGQP query planner. Remove lots of legacy code. This check-in compiles but does not work. The test suite gets incorrect answers and crashes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1: 001539df4b74dc1cbceb010a91407003ab4d8735
User & Date: drh 2013-05-30 17:43:19
Context
2013-05-30
19:28
The expected result in a test case can be of the form "*glob*" or "~*glob*" to match or not match the GLOB pattern. This is useful for matching EXPLAIN QUERY PLAN output that contains regular expression syntax characters like "?", "(", and ")". check-in: a3b4e261 user: drh tags: nextgen-query-plan-exp
17:43
Cut over the NGQP query planner. Remove lots of legacy code. This check-in compiles but does not work. The test suite gets incorrect answers and crashes. check-in: 001539df user: drh tags: nextgen-query-plan-exp
11:48
Merge recent trunk changes into the NGQP branch. check-in: aebe1f26 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  1985   1985   ** virtual table.  The pIdxInfo pointer contains indexing
  1986   1986   ** information for the i-th table in the FROM clause before reordering.
  1987   1987   ** All the pIdxInfo pointers are freed by whereInfoFree() in where.c.
  1988   1988   ** All other information in the i-th WhereLevel object for the i-th table
  1989   1989   ** after FROM clause ordering.
  1990   1990   */
  1991   1991   struct WhereLevel {
  1992         -  WherePlan plan;       /* query plan for this element of the FROM clause */
  1993   1992     int iLeftJoin;        /* Memory cell used to implement LEFT OUTER JOIN */
  1994   1993     int iTabCur;          /* The VDBE cursor used to access the table */
  1995   1994     int iIdxCur;          /* The VDBE cursor used to access pIdx */
  1996   1995     int addrBrk;          /* Jump here to break out of the loop */
  1997   1996     int addrNxt;          /* Jump here to start the next IN combination */
  1998   1997     int addrCont;         /* Jump here to continue with the next loop cycle */
  1999   1998     int addrFirst;        /* First instruction of interior of the loop */
  2000         -  u8 iFrom;             /* Which entry in the FROM clause */
         1999  +  u8 iFrom;       /* FIXME: Which entry in the FROM clause */
  2001   2000     u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  2002   2001     int p1, p2;           /* Operands of the opcode used to ends the loop */
  2003   2002     union {               /* Information that depends on plan.wsFlags */
  2004   2003       struct {
  2005   2004         int nIn;              /* Number of entries in aInLoop[] */
  2006   2005         struct InLoop {
  2007   2006           int iCur;              /* The VDBE cursor used by this IN operator */
  2008   2007           int addrInTop;         /* Top of the IN loop */
  2009   2008           u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
  2010   2009         } *aInLoop;           /* Information about each nested IN operator */
  2011   2010       } in;                 /* Used when plan.wsFlags&WHERE_IN_ABLE */
  2012   2011       Index *pCovidx;       /* Possible covering index for WHERE_MULTI_OR */
  2013   2012     } u;
  2014         -  double rOptCost;      /* "Optimal" cost for this level */
  2015   2013     struct WhereLoop *pWLoop;  /* The selected WhereLoop object */
  2016         -
  2017         -  /* The following field is really not part of the current level.  But
  2018         -  ** we need a place to cache virtual table index information for each
  2019         -  ** virtual table in the FROM clause and the WhereLevel structure is
  2020         -  ** a convenient place since there is one WhereLevel for each FROM clause
  2021         -  ** element.
  2022         -  */
  2023         -  sqlite3_index_info *pIdxInfo;  /* Index info for n-th source table */
  2024   2014   };
  2025   2015   
  2026   2016   /*
  2027   2017   ** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin()
  2028   2018   ** and the WhereInfo.wctrlFlags member.
  2029   2019   */
  2030   2020   #define WHERE_ORDERBY_NORMAL   0x0000 /* No-op */

Changes to src/where.c.

    56     56   */
    57     57   struct WhereLoop {
    58     58     Bitmask prereq;       /* Bitmask of other loops that must run first */
    59     59     Bitmask maskSelf;     /* Bitmask identifying table iTab */
    60     60   #ifdef SQLITE_DEBUG
    61     61     char cId;             /* Symbolic ID of this loop for debugging use */
    62     62   #endif
    63         -  u8 iTab;              /* Position in FROM clause of table coded by this loop */
           63  +  u8 iTab;              /* Position in FROM clause of table for this loop */
    64     64     u8 iSortIdx;          /* Sorting index number.  0==None */
    65     65     u16 nTerm;            /* Number of entries in aTerm[] */
    66     66     u32 wsFlags;          /* WHERE_* flags describing the plan */
    67     67     double rSetup;        /* One-time setup cost (ex: create transient index) */
    68     68     double rRun;          /* Cost of running each loop */
    69     69     double nOut;          /* Estimated number of output rows */
    70     70     union {
................................................................................
   186    186   ** An instance of the WhereScan object is used as an iterator for locating
   187    187   ** terms in the WHERE clause that are useful to the query planner.
   188    188   */
   189    189   struct WhereScan {
   190    190     WhereTerm *pCurrent;       /* Most recent match */
   191    191     WhereClause *pOrigWC;      /* Original, innermost WhereClause */
   192    192     WhereClause *pWC;          /* WhereClause currently being scanned */
   193         -  char *zCollName;           /* Must have this collating sequence, if not NULL */
          193  +  char *zCollName;           /* Required collating sequence, if not NULL */
   194    194     char idxaff;               /* Must match this affinity, if zCollName!=NULL */
   195    195     unsigned char nEquiv;      /* Number of entries in aEquiv[] */
   196    196     unsigned char iEquiv;      /* Next unused slot in aEquiv[] */
   197    197     u32 opMask;                /* Acceptable operators */
   198    198     int k;                     /* Resume scanning at this->pWC->a[this->k] */
   199    199     int aEquiv[22];            /* Cursor,Column pairs for equivalence classes */
   200    200   };
................................................................................
   372    372     ExprList *pDistinct;            /* The select-list if query is DISTINCT */
   373    373     sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */
   374    374     int i, n;                       /* Which loop is being coded; # of loops */
   375    375     WhereLevel *aLevel;             /* Info about outer loops */
   376    376     WhereCost cost;                 /* Lowest cost query plan */
   377    377   };
   378    378   
   379         -/*
   380         -** Return TRUE if the probe cost is less than the baseline cost
   381         -*/
   382         -static int compareCost(const WhereCost *pProbe, const WhereCost *pBaseline){
   383         -  if( pProbe->rCost<pBaseline->rCost ) return 1;
   384         -  if( pProbe->rCost>pBaseline->rCost ) return 0;
   385         -  if( pProbe->plan.nOBSat>pBaseline->plan.nOBSat ) return 1;
   386         -  if( pProbe->plan.nRow<pBaseline->plan.nRow ) return 1;
   387         -  return 0;
   388         -}
   389         -
   390    379   /*
   391    380   ** Initialize a preallocated WhereClause structure.
   392    381   */
   393    382   static void whereClauseInit(
   394    383     WhereClause *pWC,        /* The WhereClause to be initialized */
   395    384     Parse *pParse,           /* The parsing context */
   396    385     WhereMaskSet *pMaskSet,  /* Mapping from table cursor numbers to bitmasks */
................................................................................
  1686   1675           return i;
  1687   1676         }
  1688   1677       }
  1689   1678     }
  1690   1679   
  1691   1680     return -1;
  1692   1681   }
  1693         -
  1694         -/*
  1695         -** This routine determines if pIdx can be used to assist in processing a
  1696         -** DISTINCT qualifier. In other words, it tests whether or not using this
  1697         -** index for the outer loop guarantees that rows with equal values for
  1698         -** all expressions in the pDistinct list are delivered grouped together.
  1699         -**
  1700         -** For example, the query 
  1701         -**
  1702         -**   SELECT DISTINCT a, b, c FROM tbl WHERE a = ?
  1703         -**
  1704         -** can benefit from any index on columns "b" and "c".
  1705         -*/
  1706         -static int isDistinctIndex(
  1707         -  Parse *pParse,                  /* Parsing context */
  1708         -  WhereClause *pWC,               /* The WHERE clause */
  1709         -  Index *pIdx,                    /* The index being considered */
  1710         -  int base,                       /* Cursor number for the table pIdx is on */
  1711         -  ExprList *pDistinct,            /* The DISTINCT expressions */
  1712         -  int nEqCol                      /* Number of index columns with == */
  1713         -){
  1714         -  Bitmask mask = 0;               /* Mask of unaccounted for pDistinct exprs */
  1715         -  int i;                          /* Iterator variable */
  1716         -
  1717         -  assert( pDistinct!=0 );
  1718         -  if( pIdx->zName==0 || pDistinct->nExpr>=BMS ) return 0;
  1719         -  testcase( pDistinct->nExpr==BMS-1 );
  1720         -
  1721         -  /* Loop through all the expressions in the distinct list. If any of them
  1722         -  ** are not simple column references, return early. Otherwise, test if the
  1723         -  ** WHERE clause contains a "col=X" clause. If it does, the expression
  1724         -  ** can be ignored. If it does not, and the column does not belong to the
  1725         -  ** same table as index pIdx, return early. Finally, if there is no
  1726         -  ** matching "col=X" expression and the column is on the same table as pIdx,
  1727         -  ** set the corresponding bit in variable mask.
  1728         -  */
  1729         -  for(i=0; i<pDistinct->nExpr; i++){
  1730         -    WhereTerm *pTerm;
  1731         -    Expr *p = sqlite3ExprSkipCollate(pDistinct->a[i].pExpr);
  1732         -    if( p->op!=TK_COLUMN ) return 0;
  1733         -    pTerm = findTerm(pWC, p->iTable, p->iColumn, ~(Bitmask)0, WO_EQ, 0);
  1734         -    if( pTerm ){
  1735         -      Expr *pX = pTerm->pExpr;
  1736         -      CollSeq *p1 = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
  1737         -      CollSeq *p2 = sqlite3ExprCollSeq(pParse, p);
  1738         -      if( p1==p2 ) continue;
  1739         -    }
  1740         -    if( p->iTable!=base ) return 0;
  1741         -    mask |= (((Bitmask)1) << i);
  1742         -  }
  1743         -
  1744         -  for(i=nEqCol; mask && i<pIdx->nColumn; i++){
  1745         -    int iExpr = findIndexCol(pParse, pDistinct, base, pIdx, i);
  1746         -    if( iExpr<0 ) break;
  1747         -    mask &= ~(((Bitmask)1) << iExpr);
  1748         -  }
  1749         -
  1750         -  return (mask==0);
  1751         -}
  1752         -
  1753   1682   
  1754   1683   /*
  1755   1684   ** Return true if the DISTINCT expression-list passed as the third argument
  1756   1685   ** is redundant. A DISTINCT list is redundant if the database contains a
  1757   1686   ** UNIQUE index that guarantees that the result of the query will be distinct
  1758   1687   ** anyway.
  1759   1688   */
................................................................................
  1874   1803     sqlite3DebugPrintf("  estimatedCost=%g\n", p->estimatedCost);
  1875   1804   }
  1876   1805   #else
  1877   1806   #define TRACE_IDX_INPUTS(A)
  1878   1807   #define TRACE_IDX_OUTPUTS(A)
  1879   1808   #endif
  1880   1809   
  1881         -/* 
  1882         -** Required because bestIndex() is called by bestOrClauseIndex() 
  1883         -*/
  1884         -static void bestIndex(WhereBestIdx*);
  1885         -
  1886         -/*
  1887         -** This routine attempts to find an scanning strategy that can be used 
  1888         -** to optimize an 'OR' expression that is part of a WHERE clause. 
  1889         -**
  1890         -** The table associated with FROM clause term pSrc may be either a
  1891         -** regular B-Tree table or a virtual table.
  1892         -*/
  1893         -static void bestOrClauseIndex(WhereBestIdx *p){
  1894         -#ifndef SQLITE_OMIT_OR_OPTIMIZATION
  1895         -  WhereClause *pWC = p->pWC;           /* The WHERE clause */
  1896         -  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
  1897         -  const int iCur = pSrc->iCursor;      /* The cursor of the table  */
  1898         -  const Bitmask maskSrc = getMask(pWC->pMaskSet, iCur);  /* Bitmask for pSrc */
  1899         -  WhereTerm * const pWCEnd = &pWC->a[pWC->nTerm];        /* End of pWC->a[] */
  1900         -  WhereTerm *pTerm;                    /* A single term of the WHERE clause */
  1901         -
  1902         -  /* The OR-clause optimization is disallowed if the INDEXED BY or
  1903         -  ** NOT INDEXED clauses are used or if the WHERE_AND_ONLY bit is set. */
  1904         -  if( pSrc->notIndexed || pSrc->pIndex!=0 ){
  1905         -    return;
  1906         -  }
  1907         -  if( pWC->wctrlFlags & WHERE_AND_ONLY ){
  1908         -    return;
  1909         -  }
  1910         -
  1911         -  /* Search the WHERE clause terms for a usable WO_OR term. */
  1912         -  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  1913         -    if( (pTerm->eOperator & WO_OR)!=0
  1914         -     && ((pTerm->prereqAll & ~maskSrc) & p->notReady)==0
  1915         -     && (pTerm->u.pOrInfo->indexable & maskSrc)!=0 
  1916         -    ){
  1917         -      WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
  1918         -      WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
  1919         -      WhereTerm *pOrTerm;
  1920         -      double rTotal = 0;
  1921         -      double nRow = 0;
  1922         -      Bitmask used = 0;
  1923         -      WhereBestIdx sBOI;
  1924         -
  1925         -      sBOI = *p;
  1926         -      sBOI.pOrderBy = 0;
  1927         -      sBOI.pDistinct = 0;
  1928         -      sBOI.ppIdxInfo = 0;
  1929         -      for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
  1930         -        /*WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
  1931         -          (pOrTerm - pOrWC->a), (pTerm - pWC->a)
  1932         -        ));*/
  1933         -        if( (pOrTerm->eOperator& WO_AND)!=0 ){
  1934         -          sBOI.pWC = &pOrTerm->u.pAndInfo->wc;
  1935         -          bestIndex(&sBOI);
  1936         -        }else if( pOrTerm->leftCursor==iCur ){
  1937         -          WhereClause tempWC;
  1938         -          tempWC.pParse = pWC->pParse;
  1939         -          tempWC.pMaskSet = pWC->pMaskSet;
  1940         -          tempWC.pOuter = pWC;
  1941         -          tempWC.op = TK_AND;
  1942         -          tempWC.a = pOrTerm;
  1943         -          tempWC.wctrlFlags = 0;
  1944         -          tempWC.nTerm = 1;
  1945         -          sBOI.pWC = &tempWC;
  1946         -          bestIndex(&sBOI);
  1947         -        }else{
  1948         -          continue;
  1949         -        }
  1950         -        rTotal += sBOI.cost.rCost;
  1951         -        nRow += sBOI.cost.plan.nRow;
  1952         -        used |= sBOI.cost.used;
  1953         -        if( rTotal>=p->cost.rCost ) break;
  1954         -      }
  1955         -
  1956         -      /* If there is an ORDER BY clause, increase the scan cost to account 
  1957         -      ** for the cost of the sort. */
  1958         -      if( p->pOrderBy!=0 ){
  1959         -        /*WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n",
  1960         -                    rTotal, rTotal+nRow*estLog(nRow)));*/
  1961         -        rTotal += nRow*estLog(nRow);
  1962         -      }
  1963         -
  1964         -      /* If the cost of scanning using this OR term for optimization is
  1965         -      ** less than the current cost stored in pCost, replace the contents
  1966         -      ** of pCost. */
  1967         -      /*WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));*/
  1968         -      if( rTotal<p->cost.rCost ){
  1969         -        p->cost.rCost = rTotal;
  1970         -        p->cost.used = used;
  1971         -        p->cost.plan.nRow = nRow;
  1972         -        p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  1973         -        p->cost.plan.wsFlags = WHERE_MULTI_OR;
  1974         -        p->cost.plan.u.pTerm = pTerm;
  1975         -      }
  1976         -    }
  1977         -  }
  1978         -#endif /* SQLITE_OMIT_OR_OPTIMIZATION */
  1979         -}
  1980         -
  1981   1810   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  1982   1811   /*
  1983   1812   ** Return TRUE if the WHERE clause term pTerm is of a form where it
  1984   1813   ** could be used with an index to access pSrc, assuming an appropriate
  1985   1814   ** index existed.
  1986   1815   */
  1987   1816   static int termCanDriveIndex(
................................................................................
  1996   1825     if( pTerm->u.leftColumn<0 ) return 0;
  1997   1826     aff = pSrc->pTab->aCol[pTerm->u.leftColumn].affinity;
  1998   1827     if( !sqlite3IndexAffinityOk(pTerm->pExpr, aff) ) return 0;
  1999   1828     return 1;
  2000   1829   }
  2001   1830   #endif
  2002   1831   
  2003         -#ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  2004         -/*
  2005         -** If the query plan for pSrc specified in pCost is a full table scan
  2006         -** and indexing is allows (if there is no NOT INDEXED clause) and it
  2007         -** possible to construct a transient index that would perform better
  2008         -** than a full table scan even when the cost of constructing the index
  2009         -** is taken into account, then alter the query plan to use the
  2010         -** transient index.
  2011         -*/
  2012         -static void bestAutomaticIndex(WhereBestIdx *p){
  2013         -  Parse *pParse = p->pParse;            /* The parsing context */
  2014         -  WhereClause *pWC = p->pWC;            /* The WHERE clause */
  2015         -  struct SrcList_item *pSrc = p->pSrc;  /* The FROM clause term to search */
  2016         -  double nTableRow;                     /* Rows in the input table */
  2017         -  double logN;                          /* log(nTableRow) */
  2018         -  double costTempIdx;         /* per-query cost of the transient index */
  2019         -  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  2020         -  WhereTerm *pWCEnd;          /* End of pWC->a[] */
  2021         -  Table *pTable;              /* Table tht might be indexed */
  2022         -
  2023         -  if( pParse->nQueryLoop<=(double)1 ){
  2024         -    /* There is no point in building an automatic index for a single scan */
  2025         -    return;
  2026         -  }
  2027         -  if( (pParse->db->flags & SQLITE_AutoIndex)==0 ){
  2028         -    /* Automatic indices are disabled at run-time */
  2029         -    return;
  2030         -  }
  2031         -  if( (p->cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0
  2032         -   && (p->cost.plan.wsFlags & WHERE_COVER_SCAN)==0
  2033         -  ){
  2034         -    /* We already have some kind of index in use for this query. */
  2035         -    return;
  2036         -  }
  2037         -  if( pSrc->viaCoroutine ){
  2038         -    /* Cannot index a co-routine */
  2039         -    return;
  2040         -  }
  2041         -  if( pSrc->notIndexed ){
  2042         -    /* The NOT INDEXED clause appears in the SQL. */
  2043         -    return;
  2044         -  }
  2045         -  if( pSrc->isCorrelated ){
  2046         -    /* The source is a correlated sub-query. No point in indexing it. */
  2047         -    return;
  2048         -  }
  2049         -
  2050         -  assert( pParse->nQueryLoop >= (double)1 );
  2051         -  pTable = pSrc->pTab;
  2052         -  nTableRow = pTable->nRowEst;
  2053         -  logN = estLog(nTableRow);
  2054         -  costTempIdx = 2*logN*(nTableRow/pParse->nQueryLoop + 1);
  2055         -  if( costTempIdx>=p->cost.rCost ){
  2056         -    /* The cost of creating the transient table would be greater than
  2057         -    ** doing the full table scan */
  2058         -    return;
  2059         -  }
  2060         -
  2061         -  /* Search for any equality comparison term */
  2062         -  pWCEnd = &pWC->a[pWC->nTerm];
  2063         -  for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  2064         -    if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){
  2065         -      /*WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n",
  2066         -                    p->cost.rCost, costTempIdx));*/
  2067         -      p->cost.rCost = costTempIdx;
  2068         -      p->cost.plan.nRow = logN + 1;
  2069         -      p->cost.plan.wsFlags = WHERE_TEMP_INDEX;
  2070         -      p->cost.used = pTerm->prereqRight;
  2071         -      break;
  2072         -    }
  2073         -  }
  2074         -}
  2075         -#else
  2076         -# define bestAutomaticIndex(A)  /* no-op */
  2077         -#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
  2078         -
  2079   1832   
  2080   1833   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  2081   1834   /*
  2082   1835   ** Generate code to construct the Index object for an automatic index
  2083   1836   ** and to set up the WhereLevel object pLevel so that the code generator
  2084   1837   ** makes use of the automatic index.
  2085   1838   */
................................................................................
  2101   1854     KeyInfo *pKeyinfo;          /* Key information for the index */   
  2102   1855     int addrTop;                /* Top of the index fill loop */
  2103   1856     int regRecord;              /* Register holding an index record */
  2104   1857     int n;                      /* Column counter */
  2105   1858     int i;                      /* Loop counter */
  2106   1859     int mxBitCol;               /* Maximum column in pSrc->colUsed */
  2107   1860     CollSeq *pColl;             /* Collating sequence to on a column */
         1861  +  WhereLoop *pLoop;           /* The Loop object */
  2108   1862     Bitmask idxCols;            /* Bitmap of columns used for indexing */
  2109   1863     Bitmask extraCols;          /* Bitmap of additional columns */
  2110   1864   
  2111   1865     /* Generate code to skip over the creation and initialization of the
  2112   1866     ** transient index on 2nd and subsequent iterations of the loop. */
  2113   1867     v = pParse->pVdbe;
  2114   1868     assert( v!=0 );
................................................................................
  2115   1869     addrInit = sqlite3CodeOnce(pParse);
  2116   1870   
  2117   1871     /* Count the number of columns that will be added to the index
  2118   1872     ** and used to match WHERE clause constraints */
  2119   1873     nColumn = 0;
  2120   1874     pTable = pSrc->pTab;
  2121   1875     pWCEnd = &pWC->a[pWC->nTerm];
         1876  +  pLoop = pLevel->pWLoop;
  2122   1877     idxCols = 0;
  2123   1878     for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){
  2124   1879       if( termCanDriveIndex(pTerm, pSrc, notReady) ){
  2125   1880         int iCol = pTerm->u.leftColumn;
  2126   1881         Bitmask cMask = iCol>=BMS ? ((Bitmask)1)<<(BMS-1) : ((Bitmask)1)<<iCol;
  2127   1882         testcase( iCol==BMS );
  2128   1883         testcase( iCol==BMS-1 );
................................................................................
  2129   1884         if( (idxCols & cMask)==0 ){
  2130   1885           nColumn++;
  2131   1886           idxCols |= cMask;
  2132   1887         }
  2133   1888       }
  2134   1889     }
  2135   1890     assert( nColumn>0 );
  2136         -  pLevel->plan.nEq = nColumn;
         1891  +  pLoop->u.btree.nEq = nColumn;
  2137   1892   
  2138   1893     /* Count the number of additional columns needed to create a
  2139   1894     ** covering index.  A "covering index" is an index that contains all
  2140   1895     ** columns that are needed by the query.  With a covering index, the
  2141   1896     ** original table never needs to be accessed.  Automatic indices must
  2142   1897     ** be a covering index because the index will not be updated if the
  2143   1898     ** original table changes and the index and table cannot both be used
................................................................................
  2149   1904     testcase( pTable->nCol==BMS-2 );
  2150   1905     for(i=0; i<mxBitCol; i++){
  2151   1906       if( extraCols & (((Bitmask)1)<<i) ) nColumn++;
  2152   1907     }
  2153   1908     if( pSrc->colUsed & (((Bitmask)1)<<(BMS-1)) ){
  2154   1909       nColumn += pTable->nCol - BMS + 1;
  2155   1910     }
  2156         -  pLevel->plan.wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY;
         1911  +  pLoop->wsFlags |= WHERE_COLUMN_EQ | WHERE_IDX_ONLY;
  2157   1912   
  2158   1913     /* Construct the Index object to describe this index */
  2159   1914     nByte = sizeof(Index);
  2160   1915     nByte += nColumn*sizeof(int);     /* Index.aiColumn */
  2161   1916     nByte += nColumn*sizeof(char*);   /* Index.azColl */
  2162   1917     nByte += nColumn;                 /* Index.aSortOrder */
  2163   1918     pIdx = sqlite3DbMallocZero(pParse->db, nByte);
  2164   1919     if( pIdx==0 ) return;
  2165         -  pLevel->plan.u.pIdx = pIdx;
         1920  +  pLoop->u.btree.pIndex = pIdx;
  2166   1921     pIdx->azColl = (char**)&pIdx[1];
  2167   1922     pIdx->aiColumn = (int*)&pIdx->azColl[nColumn];
  2168   1923     pIdx->aSortOrder = (u8*)&pIdx->aiColumn[nColumn];
  2169   1924     pIdx->zName = "auto-index";
  2170   1925     pIdx->nColumn = nColumn;
  2171   1926     pIdx->pTable = pTable;
  2172   1927     n = 0;
................................................................................
  2181   1936           pIdx->aiColumn[n] = pTerm->u.leftColumn;
  2182   1937           pColl = sqlite3BinaryCompareCollSeq(pParse, pX->pLeft, pX->pRight);
  2183   1938           pIdx->azColl[n] = ALWAYS(pColl) ? pColl->zName : "BINARY";
  2184   1939           n++;
  2185   1940         }
  2186   1941       }
  2187   1942     }
  2188         -  assert( (u32)n==pLevel->plan.nEq );
         1943  +  assert( (u32)n==pLoop->u.btree.nEq );
  2189   1944   
  2190   1945     /* Add additional columns needed to make the automatic index into
  2191   1946     ** a covering index */
  2192   1947     for(i=0; i<mxBitCol; i++){
  2193   1948       if( extraCols & (((Bitmask)1)<<i) ){
  2194   1949         pIdx->aiColumn[n] = i;
  2195   1950         pIdx->azColl[n] = "BINARY";
................................................................................
  2380   2135         sqlite3ErrorMsg(pParse, 
  2381   2136             "table %s: xBestIndex returned an invalid plan", pTab->zName);
  2382   2137       }
  2383   2138     }
  2384   2139   
  2385   2140     return pParse->nErr;
  2386   2141   }
  2387         -
  2388         -
  2389         -/*
  2390         -** Compute the best index for a virtual table.
  2391         -**
  2392         -** The best index is computed by the xBestIndex method of the virtual
  2393         -** table module.  This routine is really just a wrapper that sets up
  2394         -** the sqlite3_index_info structure that is used to communicate with
  2395         -** xBestIndex.
  2396         -**
  2397         -** In a join, this routine might be called multiple times for the
  2398         -** same virtual table.  The sqlite3_index_info structure is created
  2399         -** and initialized on the first invocation and reused on all subsequent
  2400         -** invocations.  The sqlite3_index_info structure is also used when
  2401         -** code is generated to access the virtual table.  The whereInfoDelete() 
  2402         -** routine takes care of freeing the sqlite3_index_info structure after
  2403         -** everybody has finished with it.
  2404         -*/
  2405         -static void bestVirtualIndex(WhereBestIdx *p){
  2406         -  Parse *pParse = p->pParse;      /* The parsing context */
  2407         -  WhereClause *pWC = p->pWC;      /* The WHERE clause */
  2408         -  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
  2409         -  Table *pTab = pSrc->pTab;
  2410         -  sqlite3_index_info *pIdxInfo;
  2411         -  struct sqlite3_index_constraint *pIdxCons;
  2412         -  struct sqlite3_index_constraint_usage *pUsage;
  2413         -  WhereTerm *pTerm;
  2414         -  int i, j;
  2415         -  int nOrderBy;
  2416         -  int bAllowIN;                   /* Allow IN optimizations */
  2417         -  double rCost;
  2418         -
  2419         -  /* Make sure wsFlags is initialized to some sane value. Otherwise, if the 
  2420         -  ** malloc in allocateIndexInfo() fails and this function returns leaving
  2421         -  ** wsFlags in an uninitialized state, the caller may behave unpredictably.
  2422         -  */
  2423         -  memset(&p->cost, 0, sizeof(p->cost));
  2424         -  p->cost.plan.wsFlags = WHERE_VIRTUALTABLE;
  2425         -
  2426         -  /* If the sqlite3_index_info structure has not been previously
  2427         -  ** allocated and initialized, then allocate and initialize it now.
  2428         -  */
  2429         -  pIdxInfo = *p->ppIdxInfo;
  2430         -  if( pIdxInfo==0 ){
  2431         -    *p->ppIdxInfo = pIdxInfo = allocateIndexInfo(pParse,pWC,pSrc,p->pOrderBy);
  2432         -  }
  2433         -  if( pIdxInfo==0 ){
  2434         -    return;
  2435         -  }
  2436         -
  2437         -  /* At this point, the sqlite3_index_info structure that pIdxInfo points
  2438         -  ** to will have been initialized, either during the current invocation or
  2439         -  ** during some prior invocation.  Now we just have to customize the
  2440         -  ** details of pIdxInfo for the current invocation and pass it to
  2441         -  ** xBestIndex.
  2442         -  */
  2443         -
  2444         -  /* The module name must be defined. Also, by this point there must
  2445         -  ** be a pointer to an sqlite3_vtab structure. Otherwise
  2446         -  ** sqlite3ViewGetColumnNames() would have picked up the error. 
  2447         -  */
  2448         -  assert( pTab->azModuleArg && pTab->azModuleArg[0] );
  2449         -  assert( sqlite3GetVTable(pParse->db, pTab) );
  2450         -
  2451         -  /* Try once or twice.  On the first attempt, allow IN optimizations.
  2452         -  ** If an IN optimization is accepted by the virtual table xBestIndex
  2453         -  ** method, but the  pInfo->aConstrainUsage.omit flag is not set, then
  2454         -  ** the query will not work because it might allow duplicate rows in
  2455         -  ** output.  In that case, run the xBestIndex method a second time
  2456         -  ** without the IN constraints.  Usually this loop only runs once.
  2457         -  ** The loop will exit using a "break" statement.
  2458         -  */
  2459         -  for(bAllowIN=1; 1; bAllowIN--){
  2460         -    assert( bAllowIN==0 || bAllowIN==1 );
  2461         -
  2462         -    /* Set the aConstraint[].usable fields and initialize all 
  2463         -    ** output variables to zero.
  2464         -    **
  2465         -    ** aConstraint[].usable is true for constraints where the right-hand
  2466         -    ** side contains only references to tables to the left of the current
  2467         -    ** table.  In other words, if the constraint is of the form:
  2468         -    **
  2469         -    **           column = expr
  2470         -    **
  2471         -    ** and we are evaluating a join, then the constraint on column is 
  2472         -    ** only valid if all tables referenced in expr occur to the left
  2473         -    ** of the table containing column.
  2474         -    **
  2475         -    ** The aConstraints[] array contains entries for all constraints
  2476         -    ** on the current table.  That way we only have to compute it once
  2477         -    ** even though we might try to pick the best index multiple times.
  2478         -    ** For each attempt at picking an index, the order of tables in the
  2479         -    ** join might be different so we have to recompute the usable flag
  2480         -    ** each time.
  2481         -    */
  2482         -    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2483         -    pUsage = pIdxInfo->aConstraintUsage;
  2484         -    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2485         -      j = pIdxCons->iTermOffset;
  2486         -      pTerm = &pWC->a[j];
  2487         -      if( (pTerm->prereqRight&p->notReady)==0
  2488         -       && (bAllowIN || (pTerm->eOperator & WO_IN)==0)
  2489         -      ){
  2490         -        pIdxCons->usable = 1;
  2491         -      }else{
  2492         -        pIdxCons->usable = 0;
  2493         -      }
  2494         -    }
  2495         -    memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  2496         -    if( pIdxInfo->needToFreeIdxStr ){
  2497         -      sqlite3_free(pIdxInfo->idxStr);
  2498         -    }
  2499         -    pIdxInfo->idxStr = 0;
  2500         -    pIdxInfo->idxNum = 0;
  2501         -    pIdxInfo->needToFreeIdxStr = 0;
  2502         -    pIdxInfo->orderByConsumed = 0;
  2503         -    /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  2504         -    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
  2505         -    nOrderBy = pIdxInfo->nOrderBy;
  2506         -    if( !p->pOrderBy ){
  2507         -      pIdxInfo->nOrderBy = 0;
  2508         -    }
  2509         -  
  2510         -    if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
  2511         -      return;
  2512         -    }
  2513         -  
  2514         -    pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  2515         -    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  2516         -      if( pUsage[i].argvIndex>0 ){
  2517         -        j = pIdxCons->iTermOffset;
  2518         -        pTerm = &pWC->a[j];
  2519         -        p->cost.used |= pTerm->prereqRight;
  2520         -        if( (pTerm->eOperator & WO_IN)!=0 ){
  2521         -          if( pUsage[i].omit==0 ){
  2522         -            /* Do not attempt to use an IN constraint if the virtual table
  2523         -            ** says that the equivalent EQ constraint cannot be safely omitted.
  2524         -            ** If we do attempt to use such a constraint, some rows might be
  2525         -            ** repeated in the output. */
  2526         -            break;
  2527         -          }
  2528         -          /* A virtual table that is constrained by an IN clause may not
  2529         -          ** consume the ORDER BY clause because (1) the order of IN terms
  2530         -          ** is not necessarily related to the order of output terms and
  2531         -          ** (2) Multiple outputs from a single IN value will not merge
  2532         -          ** together.  */
  2533         -          pIdxInfo->orderByConsumed = 0;
  2534         -        }
  2535         -      }
  2536         -    }
  2537         -    if( i>=pIdxInfo->nConstraint ) break;
  2538         -  }
  2539         -
  2540         -  /* The orderByConsumed signal is only valid if all outer loops collectively
  2541         -  ** generate just a single row of output.
  2542         -  */
  2543         -  if( pIdxInfo->orderByConsumed ){
  2544         -    for(i=0; i<p->i; i++){
  2545         -      if( (p->aLevel[i].plan.wsFlags & WHERE_UNIQUE)==0 ){
  2546         -        pIdxInfo->orderByConsumed = 0;
  2547         -      }
  2548         -    }
  2549         -  }
  2550         -  
  2551         -  /* If there is an ORDER BY clause, and the selected virtual table index
  2552         -  ** does not satisfy it, increase the cost of the scan accordingly. This
  2553         -  ** matches the processing for non-virtual tables in bestBtreeIndex().
  2554         -  */
  2555         -  rCost = pIdxInfo->estimatedCost;
  2556         -  if( p->pOrderBy && pIdxInfo->orderByConsumed==0 ){
  2557         -    rCost += estLog(rCost)*rCost;
  2558         -  }
  2559         -
  2560         -  /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
  2561         -  ** inital value of lowestCost in this loop. If it is, then the
  2562         -  ** (cost<lowestCost) test below will never be true.
  2563         -  ** 
  2564         -  ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT 
  2565         -  ** is defined.
  2566         -  */
  2567         -  if( (SQLITE_BIG_DBL/((double)2))<rCost ){
  2568         -    p->cost.rCost = (SQLITE_BIG_DBL/((double)2));
  2569         -  }else{
  2570         -    p->cost.rCost = rCost;
  2571         -  }
  2572         -  p->cost.plan.u.pVtabIdx = pIdxInfo;
  2573         -  if( pIdxInfo->orderByConsumed ){
  2574         -    p->cost.plan.wsFlags |= WHERE_ORDERED;
  2575         -    p->cost.plan.nOBSat = nOrderBy;
  2576         -  }else{
  2577         -    p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0;
  2578         -  }
  2579         -  p->cost.plan.nEq = 0;
  2580         -  pIdxInfo->nOrderBy = nOrderBy;
  2581         -
  2582         -  /* Try to find a more efficient access pattern by using multiple indexes
  2583         -  ** to optimize an OR expression within the WHERE clause. 
  2584         -  */
  2585         -  bestOrClauseIndex(p);
  2586         -}
  2587         -#endif /* SQLITE_OMIT_VIRTUALTABLE */
         2142  +#endif /* !defined(SQLITE_OMIT_VIRTUALTABLE) */
         2143  +
  2588   2144   
  2589   2145   #ifdef SQLITE_ENABLE_STAT3
  2590   2146   /*
  2591   2147   ** Estimate the location of a particular key among all keys in an
  2592   2148   ** index.  Store the results in aStat as follows:
  2593   2149   **
  2594   2150   **    aStat[0]      Est. number of rows less than pVal
................................................................................
  2975   2531       *pnRow = nRowEst;
  2976   2532       /*WHERETRACE(("IN row estimate: est=%g\n", nRowEst));*/
  2977   2533     }
  2978   2534     return rc;
  2979   2535   }
  2980   2536   #endif /* defined(SQLITE_ENABLE_STAT3) */
  2981   2537   
  2982         -/*
  2983         -** Check to see if column iCol of the table with cursor iTab will appear
  2984         -** in sorted order according to the current query plan.
  2985         -**
  2986         -** Return values:
  2987         -**
  2988         -**    0   iCol is not ordered
  2989         -**    1   iCol has only a single value
  2990         -**    2   iCol is in ASC order
  2991         -**    3   iCol is in DESC order
  2992         -*/
  2993         -static int isOrderedColumn(
  2994         -  WhereBestIdx *p,
  2995         -  int iTab,
  2996         -  int iCol
  2997         -){
  2998         -  int i, j;
  2999         -  WhereLevel *pLevel = &p->aLevel[p->i-1];
  3000         -  Index *pIdx;
  3001         -  u8 sortOrder;
  3002         -  for(i=p->i-1; i>=0; i--, pLevel--){
  3003         -    if( pLevel->iTabCur!=iTab ) continue;
  3004         -    if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3005         -      return 1;
  3006         -    }
  3007         -    assert( (pLevel->plan.wsFlags & WHERE_ORDERED)!=0 );
  3008         -    if( (pIdx = pLevel->plan.u.pIdx)!=0 ){
  3009         -      if( iCol<0 ){
  3010         -        sortOrder = 0;
  3011         -        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
  3012         -      }else{
  3013         -        int n = pIdx->nColumn;
  3014         -        for(j=0; j<n; j++){
  3015         -          if( iCol==pIdx->aiColumn[j] ) break;
  3016         -        }
  3017         -        if( j>=n ) return 0;
  3018         -        sortOrder = pIdx->aSortOrder[j];
  3019         -        testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
  3020         -      }
  3021         -    }else{
  3022         -      if( iCol!=(-1) ) return 0;
  3023         -      sortOrder = 0;
  3024         -      testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 );
  3025         -    }
  3026         -    if( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ){
  3027         -      assert( sortOrder==0 || sortOrder==1 );
  3028         -      testcase( sortOrder==1 );
  3029         -      sortOrder = 1 - sortOrder;
  3030         -    }
  3031         -    return sortOrder+2;
  3032         -  }
  3033         -  return 0;
  3034         -}
  3035         -
  3036         -/*
  3037         -** This routine decides if pIdx can be used to satisfy the ORDER BY
  3038         -** clause, either in whole or in part.  The return value is the 
  3039         -** cumulative number of terms in the ORDER BY clause that are satisfied
  3040         -** by the index pIdx and other indices in outer loops.
  3041         -**
  3042         -** The table being queried has a cursor number of "base".  pIdx is the
  3043         -** index that is postulated for use to access the table.
  3044         -**
  3045         -** The *pbRev value is set to 0 order 1 depending on whether or not
  3046         -** pIdx should be run in the forward order or in reverse order.
  3047         -*/
  3048         -static int isSortingIndex(
  3049         -  WhereBestIdx *p,    /* Best index search context */
  3050         -  Index *pIdx,        /* The index we are testing */
  3051         -  int base,           /* Cursor number for the table to be sorted */
  3052         -  int *pbRev,         /* Set to 1 for reverse-order scan of pIdx */
  3053         -  int *pbObUnique     /* ORDER BY column values will different in every row */
  3054         -){
  3055         -  int i;                        /* Number of pIdx terms used */
  3056         -  int j;                        /* Number of ORDER BY terms satisfied */
  3057         -  int sortOrder = 2;            /* 0: forward.  1: backward.  2: unknown */
  3058         -  int nTerm;                    /* Number of ORDER BY terms */
  3059         -  struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
  3060         -  Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  3061         -  ExprList *pOrderBy;           /* The ORDER BY clause */
  3062         -  Parse *pParse = p->pParse;    /* Parser context */
  3063         -  sqlite3 *db = pParse->db;     /* Database connection */
  3064         -  int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  3065         -  int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  3066         -  int uniqueNotNull;            /* pIdx is UNIQUE with all terms are NOT NULL */
  3067         -  int outerObUnique;            /* Outer loops generate different values in
  3068         -                                ** every row for the ORDER BY columns */
  3069         -
  3070         -  if( p->i==0 ){
  3071         -    nPriorSat = 0;
  3072         -    outerObUnique = 1;
  3073         -  }else{
  3074         -    u32 wsFlags = p->aLevel[p->i-1].plan.wsFlags;
  3075         -    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
  3076         -    if( (wsFlags & WHERE_ORDERED)==0 ){
  3077         -      /* This loop cannot be ordered unless the next outer loop is
  3078         -      ** also ordered */
  3079         -      return nPriorSat;
  3080         -    }
  3081         -    if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ){
  3082         -      /* Only look at the outer-most loop if the OrderByIdxJoin
  3083         -      ** optimization is disabled */
  3084         -      return nPriorSat;
  3085         -    }
  3086         -    testcase( wsFlags & WHERE_OB_UNIQUE );
  3087         -    testcase( wsFlags & WHERE_ALL_UNIQUE );
  3088         -    outerObUnique = (wsFlags & (WHERE_OB_UNIQUE|WHERE_ALL_UNIQUE))!=0;
  3089         -  }
  3090         -  pOrderBy = p->pOrderBy;
  3091         -  assert( pOrderBy!=0 );
  3092         -  if( pIdx->bUnordered ){
  3093         -    /* Hash indices (indicated by the "unordered" tag on sqlite_stat1) cannot
  3094         -    ** be used for sorting */
  3095         -    return nPriorSat;
  3096         -  }
  3097         -  nTerm = pOrderBy->nExpr;
  3098         -  uniqueNotNull = pIdx->onError!=OE_None;
  3099         -  assert( nTerm>0 );
  3100         -
  3101         -  /* Argument pIdx must either point to a 'real' named index structure, 
  3102         -  ** or an index structure allocated on the stack by bestBtreeIndex() to
  3103         -  ** represent the rowid index that is part of every table.  */
  3104         -  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
  3105         -
  3106         -  /* Match terms of the ORDER BY clause against columns of
  3107         -  ** the index.
  3108         -  **
  3109         -  ** Note that indices have pIdx->nColumn regular columns plus
  3110         -  ** one additional column containing the rowid.  The rowid column
  3111         -  ** of the index is also allowed to match against the ORDER BY
  3112         -  ** clause.
  3113         -  */
  3114         -  j = nPriorSat;
  3115         -  for(i=0,pOBItem=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){
  3116         -    Expr *pOBExpr;          /* The expression of the ORDER BY pOBItem */
  3117         -    CollSeq *pColl;         /* The collating sequence of pOBExpr */
  3118         -    int termSortOrder;      /* Sort order for this term */
  3119         -    int iColumn;            /* The i-th column of the index.  -1 for rowid */
  3120         -    int iSortOrder;         /* 1 for DESC, 0 for ASC on the i-th index term */
  3121         -    int isEq;               /* Subject to an == or IS NULL constraint */
  3122         -    int isMatch;            /* ORDER BY term matches the index term */
  3123         -    const char *zColl;      /* Name of collating sequence for i-th index term */
  3124         -    WhereTerm *pConstraint; /* A constraint in the WHERE clause */
  3125         -
  3126         -    /* If the next term of the ORDER BY clause refers to anything other than
  3127         -    ** a column in the "base" table, then this index will not be of any
  3128         -    ** further use in handling the ORDER BY. */
  3129         -    pOBExpr = sqlite3ExprSkipCollate(pOBItem->pExpr);
  3130         -    if( pOBExpr->op!=TK_COLUMN || pOBExpr->iTable!=base ){
  3131         -      break;
  3132         -    }
  3133         -
  3134         -    /* Find column number and collating sequence for the next entry
  3135         -    ** in the index */
  3136         -    if( pIdx->zName && i<pIdx->nColumn ){
  3137         -      iColumn = pIdx->aiColumn[i];
  3138         -      if( iColumn==pIdx->pTable->iPKey ){
  3139         -        iColumn = -1;
  3140         -      }
  3141         -      iSortOrder = pIdx->aSortOrder[i];
  3142         -      zColl = pIdx->azColl[i];
  3143         -      assert( zColl!=0 );
  3144         -    }else{
  3145         -      iColumn = -1;
  3146         -      iSortOrder = 0;
  3147         -      zColl = 0;
  3148         -    }
  3149         -
  3150         -    /* Check to see if the column number and collating sequence of the
  3151         -    ** index match the column number and collating sequence of the ORDER BY
  3152         -    ** clause entry.  Set isMatch to 1 if they both match. */
  3153         -    if( pOBExpr->iColumn==iColumn ){
  3154         -      if( zColl ){
  3155         -        pColl = sqlite3ExprCollSeq(pParse, pOBItem->pExpr);
  3156         -        if( !pColl ) pColl = db->pDfltColl;
  3157         -        isMatch = sqlite3StrICmp(pColl->zName, zColl)==0;
  3158         -      }else{
  3159         -        isMatch = 1;
  3160         -      }
  3161         -    }else{
  3162         -      isMatch = 0;
  3163         -    }
  3164         -
  3165         -    /* termSortOrder is 0 or 1 for whether or not the access loop should
  3166         -    ** run forward or backwards (respectively) in order to satisfy this 
  3167         -    ** term of the ORDER BY clause. */
  3168         -    assert( pOBItem->sortOrder==0 || pOBItem->sortOrder==1 );
  3169         -    assert( iSortOrder==0 || iSortOrder==1 );
  3170         -    termSortOrder = iSortOrder ^ pOBItem->sortOrder;
  3171         -
  3172         -    /* If X is the column in the index and ORDER BY clause, check to see
  3173         -    ** if there are any X= or X IS NULL constraints in the WHERE clause. */
  3174         -    pConstraint = findTerm(p->pWC, base, iColumn, p->notReady,
  3175         -                           WO_EQ|WO_ISNULL|WO_IN, pIdx);
  3176         -    if( pConstraint==0 ){
  3177         -      isEq = 0;
  3178         -    }else if( (pConstraint->eOperator & WO_IN)!=0 ){
  3179         -      isEq = 0;
  3180         -    }else if( (pConstraint->eOperator & WO_ISNULL)!=0 ){
  3181         -      uniqueNotNull = 0;
  3182         -      isEq = 1;  /* "X IS NULL" means X has only a single value */
  3183         -    }else if( pConstraint->prereqRight==0 ){
  3184         -      isEq = 1;  /* Constraint "X=constant" means X has only a single value */
  3185         -    }else{
  3186         -      Expr *pRight = pConstraint->pExpr->pRight;
  3187         -      if( pRight->op==TK_COLUMN ){
  3188         -        /*WHERETRACE(("       .. isOrderedColumn(tab=%d,col=%d)",
  3189         -                    pRight->iTable, pRight->iColumn));*/
  3190         -        isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn);
  3191         -        /*WHERETRACE((" -> isEq=%d\n", isEq));*/
  3192         -
  3193         -        /* If the constraint is of the form X=Y where Y is an ordered value
  3194         -        ** in an outer loop, then make sure the sort order of Y matches the
  3195         -        ** sort order required for X. */
  3196         -        if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){
  3197         -          testcase( isEq==2 );
  3198         -          testcase( isEq==3 );
  3199         -          break;
  3200         -        }
  3201         -      }else{
  3202         -        isEq = 0;  /* "X=expr" places no ordering constraints on X */
  3203         -      }
  3204         -    }
  3205         -    if( !isMatch ){
  3206         -      if( isEq==0 ){
  3207         -        break;
  3208         -      }else{
  3209         -        continue;
  3210         -      }
  3211         -    }else if( isEq!=1 ){
  3212         -      if( sortOrder==2 ){
  3213         -        sortOrder = termSortOrder;
  3214         -      }else if( termSortOrder!=sortOrder ){
  3215         -        break;
  3216         -      }
  3217         -    }
  3218         -    j++;
  3219         -    pOBItem++;
  3220         -    if( iColumn<0 ){
  3221         -      seenRowid = 1;
  3222         -      break;
  3223         -    }else if( pTab->aCol[iColumn].notNull==0 && isEq!=1 ){
  3224         -      testcase( isEq==0 );
  3225         -      testcase( isEq==2 );
  3226         -      testcase( isEq==3 );
  3227         -      uniqueNotNull = 0;
  3228         -    }
  3229         -  }
  3230         -  if( seenRowid ){
  3231         -    uniqueNotNull = 1;
  3232         -  }else if( uniqueNotNull==0 || i<pIdx->nColumn ){
  3233         -    uniqueNotNull = 0;
  3234         -  }
  3235         -
  3236         -  /* If we have not found at least one ORDER BY term that matches the
  3237         -  ** index, then show no progress. */
  3238         -  if( pOBItem==&pOrderBy->a[nPriorSat] ) return nPriorSat;
  3239         -
  3240         -  /* Either the outer queries must generate rows where there are no two
  3241         -  ** rows with the same values in all ORDER BY columns, or else this
  3242         -  ** loop must generate just a single row of output.  Example:  Suppose
  3243         -  ** the outer loops generate A=1 and A=1, and this loop generates B=3
  3244         -  ** and B=4.  Then without the following test, ORDER BY A,B would 
  3245         -  ** generate the wrong order output: 1,3 1,4 1,3 1,4
  3246         -  */
  3247         -  if( outerObUnique==0 && uniqueNotNull==0 ) return nPriorSat;
  3248         -  *pbObUnique = uniqueNotNull;
  3249         -
  3250         -  /* Return the necessary scan order back to the caller */
  3251         -  *pbRev = sortOrder & 1;
  3252         -
  3253         -  /* If there was an "ORDER BY rowid" term that matched, or it is only
  3254         -  ** possible for a single row from this table to match, then skip over
  3255         -  ** any additional ORDER BY terms dealing with this table.
  3256         -  */
  3257         -  if( uniqueNotNull ){
  3258         -    /* Advance j over additional ORDER BY terms associated with base */
  3259         -    WhereMaskSet *pMS = p->pWC->pMaskSet;
  3260         -    Bitmask m = ~getMask(pMS, base);
  3261         -    while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
  3262         -      j++;
  3263         -    }
  3264         -  }
  3265         -  return j;
  3266         -}
  3267         -
  3268         -/*
  3269         -** Find the best query plan for accessing a particular table.  Write the
  3270         -** best query plan and its cost into the p->cost.
  3271         -**
  3272         -** The lowest cost plan wins.  The cost is an estimate of the amount of
  3273         -** CPU and disk I/O needed to process the requested result.
  3274         -** Factors that influence cost include:
  3275         -**
  3276         -**    *  The estimated number of rows that will be retrieved.  (The
  3277         -**       fewer the better.)
  3278         -**
  3279         -**    *  Whether or not sorting must occur.
  3280         -**
  3281         -**    *  Whether or not there must be separate lookups in the
  3282         -**       index and in the main table.
  3283         -**
  3284         -** If there was an INDEXED BY clause (pSrc->pIndex) attached to the table in
  3285         -** the SQL statement, then this function only considers plans using the 
  3286         -** named index. If no such plan is found, then the returned cost is
  3287         -** SQLITE_BIG_DBL. If a plan is found that uses the named index, 
  3288         -** then the cost is calculated in the usual way.
  3289         -**
  3290         -** If a NOT INDEXED clause was attached to the table 
  3291         -** in the SELECT statement, then no indexes are considered. However, the 
  3292         -** selected plan may still take advantage of the built-in rowid primary key
  3293         -** index.
  3294         -*/
  3295         -static void bestBtreeIndex(WhereBestIdx *p){
  3296         -  Parse *pParse = p->pParse;  /* The parsing context */
  3297         -  WhereClause *pWC = p->pWC;  /* The WHERE clause */
  3298         -  struct SrcList_item *pSrc = p->pSrc; /* The FROM clause term to search */
  3299         -  int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  3300         -  Index *pProbe;              /* An index we are evaluating */
  3301         -  Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
  3302         -  int eqTermMask;             /* Current mask of valid equality operators */
  3303         -  int idxEqTermMask;          /* Index mask of valid equality operators */
  3304         -  Index sPk;                  /* A fake index object for the primary key */
  3305         -  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
  3306         -  int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  3307         -  int wsFlagMask;             /* Allowed flags in p->cost.plan.wsFlag */
  3308         -  int nPriorSat;              /* ORDER BY terms satisfied by outer loops */
  3309         -  int nOrderBy;               /* Number of ORDER BY terms */
  3310         -  char bSortInit;             /* Initializer for bSort in inner loop */
  3311         -  char bDistInit;             /* Initializer for bDist in inner loop */
  3312         -
  3313         -
  3314         -  /* Initialize the cost to a worst-case value */
  3315         -  memset(&p->cost, 0, sizeof(p->cost));
  3316         -  p->cost.rCost = SQLITE_BIG_DBL;
  3317         -
  3318         -  /* If the pSrc table is the right table of a LEFT JOIN then we may not
  3319         -  ** use an index to satisfy IS NULL constraints on that table.  This is
  3320         -  ** because columns might end up being NULL if the table does not match -
  3321         -  ** a circumstance which the index cannot help us discover.  Ticket #2177.
  3322         -  */
  3323         -  if( pSrc->jointype & JT_LEFT ){
  3324         -    idxEqTermMask = WO_EQ|WO_IN;
  3325         -  }else{
  3326         -    idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
  3327         -  }
  3328         -
  3329         -  if( pSrc->pIndex ){
  3330         -    /* An INDEXED BY clause specifies a particular index to use */
  3331         -    pIdx = pProbe = pSrc->pIndex;
  3332         -    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
  3333         -    eqTermMask = idxEqTermMask;
  3334         -  }else{
  3335         -    /* There is no INDEXED BY clause.  Create a fake Index object in local
  3336         -    ** variable sPk to represent the rowid primary key index.  Make this
  3337         -    ** fake index the first in a chain of Index objects with all of the real
  3338         -    ** indices to follow */
  3339         -    Index *pFirst;                  /* First of real indices on the table */
  3340         -    memset(&sPk, 0, sizeof(Index));
  3341         -    sPk.nColumn = 1;
  3342         -    sPk.aiColumn = &aiColumnPk;
  3343         -    sPk.aiRowEst = aiRowEstPk;
  3344         -    sPk.onError = OE_Replace;
  3345         -    sPk.pTable = pSrc->pTab;
  3346         -    aiRowEstPk[0] = pSrc->pTab->nRowEst;
  3347         -    aiRowEstPk[1] = 1;
  3348         -    pFirst = pSrc->pTab->pIndex;
  3349         -    if( pSrc->notIndexed==0 ){
  3350         -      /* The real indices of the table are only considered if the
  3351         -      ** NOT INDEXED qualifier is omitted from the FROM clause */
  3352         -      sPk.pNext = pFirst;
  3353         -    }
  3354         -    pProbe = &sPk;
  3355         -    wsFlagMask = ~(
  3356         -        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
  3357         -    );
  3358         -    eqTermMask = WO_EQ|WO_IN;
  3359         -    pIdx = 0;
  3360         -  }
  3361         -
  3362         -  nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0;
  3363         -  if( p->i ){
  3364         -    nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
  3365         -    bSortInit = nPriorSat<nOrderBy;
  3366         -    bDistInit = 0;
  3367         -  }else{
  3368         -    nPriorSat = 0;
  3369         -    bSortInit = nOrderBy>0;
  3370         -    bDistInit = p->pDistinct!=0;
  3371         -  }
  3372         -
  3373         -  /* Loop over all indices looking for the best one to use
  3374         -  */
  3375         -  for(; pProbe; pIdx=pProbe=pProbe->pNext){
  3376         -    const tRowcnt * const aiRowEst = pProbe->aiRowEst;
  3377         -    WhereCost pc;               /* Cost of using pProbe */
  3378         -    double log10N = (double)1;  /* base-10 logarithm of nRow (inexact) */
  3379         -
  3380         -    /* The following variables are populated based on the properties of
  3381         -    ** index being evaluated. They are then used to determine the expected
  3382         -    ** cost and number of rows returned.
  3383         -    **
  3384         -    **  pc.plan.nEq: 
  3385         -    **    Number of equality terms that can be implemented using the index.
  3386         -    **    In other words, the number of initial fields in the index that
  3387         -    **    are used in == or IN or NOT NULL constraints of the WHERE clause.
  3388         -    **
  3389         -    **  nInMul:  
  3390         -    **    The "in-multiplier". This is an estimate of how many seek operations 
  3391         -    **    SQLite must perform on the index in question. For example, if the 
  3392         -    **    WHERE clause is:
  3393         -    **
  3394         -    **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
  3395         -    **
  3396         -    **    SQLite must perform 9 lookups on an index on (a, b), so nInMul is 
  3397         -    **    set to 9. Given the same schema and either of the following WHERE 
  3398         -    **    clauses:
  3399         -    **
  3400         -    **      WHERE a =  1
  3401         -    **      WHERE a >= 2
  3402         -    **
  3403         -    **    nInMul is set to 1.
  3404         -    **
  3405         -    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
  3406         -    **    the sub-select is assumed to return 25 rows for the purposes of 
  3407         -    **    determining nInMul.
  3408         -    **
  3409         -    **  bInEst:  
  3410         -    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
  3411         -    **    in determining the value of nInMul.  Note that the RHS of the
  3412         -    **    IN operator must be a SELECT, not a value list, for this variable
  3413         -    **    to be true.
  3414         -    **
  3415         -    **  rangeDiv:
  3416         -    **    An estimate of a divisor by which to reduce the search space due
  3417         -    **    to inequality constraints.  In the absence of sqlite_stat3 ANALYZE
  3418         -    **    data, a single inequality reduces the search space to 1/4rd its
  3419         -    **    original size (rangeDiv==4).  Two inequalities reduce the search
  3420         -    **    space to 1/16th of its original size (rangeDiv==16).
  3421         -    **
  3422         -    **  bSort:   
  3423         -    **    Boolean. True if there is an ORDER BY clause that will require an 
  3424         -    **    external sort (i.e. scanning the index being evaluated will not 
  3425         -    **    correctly order records).
  3426         -    **
  3427         -    **  bDist:
  3428         -    **    Boolean. True if there is a DISTINCT clause that will require an 
  3429         -    **    external btree.
  3430         -    **
  3431         -    **  bLookup: 
  3432         -    **    Boolean. True if a table lookup is required for each index entry
  3433         -    **    visited.  In other words, true if this is not a covering index.
  3434         -    **    This is always false for the rowid primary key index of a table.
  3435         -    **    For other indexes, it is true unless all the columns of the table
  3436         -    **    used by the SELECT statement are present in the index (such an
  3437         -    **    index is sometimes described as a covering index).
  3438         -    **    For example, given the index on (a, b), the second of the following 
  3439         -    **    two queries requires table b-tree lookups in order to find the value
  3440         -    **    of column c, but the first does not because columns a and b are
  3441         -    **    both available in the index.
  3442         -    **
  3443         -    **             SELECT a, b    FROM tbl WHERE a = 1;
  3444         -    **             SELECT a, b, c FROM tbl WHERE a = 1;
  3445         -    */
  3446         -    int bInEst = 0;               /* True if "x IN (SELECT...)" seen */
  3447         -    int nInMul = 1;               /* Number of distinct equalities to lookup */
  3448         -    double rangeDiv = (double)1;  /* Estimated reduction in search space */
  3449         -    int nBound = 0;               /* Number of range constraints seen */
  3450         -    char bSort = bSortInit;       /* True if external sort required */
  3451         -    char bDist = bDistInit;       /* True if index cannot help with DISTINCT */
  3452         -    char bLookup = 0;             /* True if not a covering index */
  3453         -    WhereTerm *pTerm;             /* A single term of the WHERE clause */
  3454         -#ifdef SQLITE_ENABLE_STAT3
  3455         -    WhereTerm *pFirstTerm = 0;    /* First term matching the index */
  3456         -#endif
  3457         -
  3458         -    /*WHERETRACE((
  3459         -      "   %s(%s):\n",
  3460         -      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk")
  3461         -    ));*/
  3462         -    memset(&pc, 0, sizeof(pc));
  3463         -    pc.plan.nOBSat = nPriorSat;
  3464         -
  3465         -    /* Determine the values of pc.plan.nEq and nInMul */
  3466         -    for(pc.plan.nEq=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){
  3467         -      int j = pProbe->aiColumn[pc.plan.nEq];
  3468         -      pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx);
  3469         -      if( pTerm==0 ) break;
  3470         -      pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
  3471         -      testcase( pTerm->pWC!=pWC );
  3472         -      if( pTerm->eOperator & WO_IN ){
  3473         -        Expr *pExpr = pTerm->pExpr;
  3474         -        pc.plan.wsFlags |= WHERE_COLUMN_IN;
  3475         -        if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  3476         -          /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  3477         -          nInMul *= 25;
  3478         -          bInEst = 1;
  3479         -        }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  3480         -          /* "x IN (value, value, ...)" */
  3481         -          nInMul *= pExpr->x.pList->nExpr;
  3482         -        }
  3483         -      }else if( pTerm->eOperator & WO_ISNULL ){
  3484         -        pc.plan.wsFlags |= WHERE_COLUMN_NULL;
  3485         -      }
  3486         -#ifdef SQLITE_ENABLE_STAT3
  3487         -      if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm;
  3488         -#endif
  3489         -      pc.used |= pTerm->prereqRight;
  3490         -    }
  3491         - 
  3492         -    /* If the index being considered is UNIQUE, and there is an equality 
  3493         -    ** constraint for all columns in the index, then this search will find
  3494         -    ** at most a single row. In this case set the WHERE_UNIQUE flag to 
  3495         -    ** indicate this to the caller.
  3496         -    **
  3497         -    ** Otherwise, if the search may find more than one row, test to see if
  3498         -    ** there is a range constraint on indexed column (pc.plan.nEq+1) that
  3499         -    ** can be optimized using the index. 
  3500         -    */
  3501         -    if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){
  3502         -      testcase( pc.plan.wsFlags & WHERE_COLUMN_IN );
  3503         -      testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL );
  3504         -      if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  3505         -        pc.plan.wsFlags |= WHERE_UNIQUE;
  3506         -        if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3507         -          pc.plan.wsFlags |= WHERE_ALL_UNIQUE;
  3508         -        }
  3509         -      }
  3510         -    }else if( pProbe->bUnordered==0 ){
  3511         -      int j;
  3512         -      j = (pc.plan.nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[pc.plan.nEq]);
  3513         -      if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
  3514         -        WhereTerm *pTop, *pBtm;
  3515         -        pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx);
  3516         -        pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx);
  3517         -        whereRangeScanEst(pParse, pProbe, pc.plan.nEq, pBtm, pTop, &rangeDiv);
  3518         -        if( pTop ){
  3519         -          nBound = 1;
  3520         -          pc.plan.wsFlags |= WHERE_TOP_LIMIT;
  3521         -          pc.used |= pTop->prereqRight;
  3522         -          testcase( pTop->pWC!=pWC );
  3523         -        }
  3524         -        if( pBtm ){
  3525         -          nBound++;
  3526         -          pc.plan.wsFlags |= WHERE_BTM_LIMIT;
  3527         -          pc.used |= pBtm->prereqRight;
  3528         -          testcase( pBtm->pWC!=pWC );
  3529         -        }
  3530         -        pc.plan.wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
  3531         -      }
  3532         -    }
  3533         -
  3534         -    /* If there is an ORDER BY clause and the index being considered will
  3535         -    ** naturally scan rows in the required order, set the appropriate flags
  3536         -    ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
  3537         -    ** the index will scan rows in a different order, set the bSort
  3538         -    ** variable.  */
  3539         -    if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
  3540         -      int bRev = 2;
  3541         -      int bObUnique = 0;
  3542         -      /*WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));*/
  3543         -      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique);
  3544         -      /*WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
  3545         -                  bRev, bObUnique, pc.plan.nOBSat));*/
  3546         -      if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3547         -        pc.plan.wsFlags |= WHERE_ORDERED;
  3548         -        if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE;
  3549         -      }
  3550         -      if( nOrderBy==pc.plan.nOBSat ){
  3551         -        bSort = 0;
  3552         -        pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
  3553         -      }
  3554         -      if( bRev & 1 ) pc.plan.wsFlags |= WHERE_REVERSE;
  3555         -    }
  3556         -
  3557         -    /* If there is a DISTINCT qualifier and this index will scan rows in
  3558         -    ** order of the DISTINCT expressions, clear bDist and set the appropriate
  3559         -    ** flags in pc.plan.wsFlags. */
  3560         -    if( bDist
  3561         -     && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, pc.plan.nEq)
  3562         -     && (pc.plan.wsFlags & WHERE_COLUMN_IN)==0
  3563         -    ){
  3564         -      bDist = 0;
  3565         -      pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT;
  3566         -    }
  3567         -
  3568         -    /* If currently calculating the cost of using an index (not the IPK
  3569         -    ** index), determine if all required column data may be obtained without 
  3570         -    ** using the main table (i.e. if the index is a covering
  3571         -    ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
  3572         -    ** pc.plan.wsFlags. Otherwise, set the bLookup variable to true.  */
  3573         -    if( pIdx ){
  3574         -      Bitmask m = pSrc->colUsed;
  3575         -      int j;
  3576         -      for(j=0; j<pIdx->nColumn; j++){
  3577         -        int x = pIdx->aiColumn[j];
  3578         -        if( x<BMS-1 ){
  3579         -          m &= ~(((Bitmask)1)<<x);
  3580         -        }
  3581         -      }
  3582         -      if( m==0 ){
  3583         -        pc.plan.wsFlags |= WHERE_IDX_ONLY;
  3584         -      }else{
  3585         -        bLookup = 1;
  3586         -      }
  3587         -    }
  3588         -
  3589         -    /*
  3590         -    ** Estimate the number of rows of output.  For an "x IN (SELECT...)"
  3591         -    ** constraint, do not let the estimate exceed half the rows in the table.
  3592         -    */
  3593         -    pc.plan.nRow = (double)(aiRowEst[pc.plan.nEq] * nInMul);
  3594         -    if( bInEst && pc.plan.nRow*2>aiRowEst[0] ){
  3595         -      pc.plan.nRow = aiRowEst[0]/2;
  3596         -      nInMul = (int)(pc.plan.nRow / aiRowEst[pc.plan.nEq]);
  3597         -    }
  3598         -
  3599         -#ifdef SQLITE_ENABLE_STAT3
  3600         -    /* If the constraint is of the form x=VALUE or x IN (E1,E2,...)
  3601         -    ** and we do not think that values of x are unique and if histogram
  3602         -    ** data is available for column x, then it might be possible
  3603         -    ** to get a better estimate on the number of rows based on
  3604         -    ** VALUE and how common that value is according to the histogram.
  3605         -    */
  3606         -    if( pc.plan.nRow>(double)1 && pc.plan.nEq==1
  3607         -     && pFirstTerm!=0 && aiRowEst[1]>1 ){
  3608         -      assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 );
  3609         -      if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){
  3610         -        testcase( pFirstTerm->eOperator & WO_EQ );
  3611         -        testcase( pFirstTerm->eOperator & WO_EQUIV );
  3612         -        testcase( pFirstTerm->eOperator & WO_ISNULL );
  3613         -        whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight,
  3614         -                          &pc.plan.nRow);
  3615         -      }else if( bInEst==0 ){
  3616         -        assert( pFirstTerm->eOperator & WO_IN );
  3617         -        whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList,
  3618         -                       &pc.plan.nRow);
  3619         -      }
  3620         -    }
  3621         -#endif /* SQLITE_ENABLE_STAT3 */
  3622         -
  3623         -    /* Adjust the number of output rows and downward to reflect rows
  3624         -    ** that are excluded by range constraints.
  3625         -    */
  3626         -    pc.plan.nRow = pc.plan.nRow/rangeDiv;
  3627         -    if( pc.plan.nRow<1 ) pc.plan.nRow = 1;
  3628         -
  3629         -    /* Experiments run on real SQLite databases show that the time needed
  3630         -    ** to do a binary search to locate a row in a table or index is roughly
  3631         -    ** log10(N) times the time to move from one row to the next row within
  3632         -    ** a table or index.  The actual times can vary, with the size of
  3633         -    ** records being an important factor.  Both moves and searches are
  3634         -    ** slower with larger records, presumably because fewer records fit
  3635         -    ** on one page and hence more pages have to be fetched.
  3636         -    **
  3637         -    ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do
  3638         -    ** not give us data on the relative sizes of table and index records.
  3639         -    ** So this computation assumes table records are about twice as big
  3640         -    ** as index records
  3641         -    */
  3642         -    if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED|WHERE_OB_UNIQUE))
  3643         -                                                              ==WHERE_IDX_ONLY
  3644         -     && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  3645         -     && sqlite3GlobalConfig.bUseCis
  3646         -     && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan)
  3647         -    ){
  3648         -      /* This index is not useful for indexing, but it is a covering index.
  3649         -      ** A full-scan of the index might be a little faster than a full-scan
  3650         -      ** of the table, so give this case a cost slightly less than a table
  3651         -      ** scan. */
  3652         -      pc.rCost = aiRowEst[0]*3 + pProbe->nColumn;
  3653         -      pc.plan.wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE;
  3654         -    }else if( (pc.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
  3655         -      /* The cost of a full table scan is a number of move operations equal
  3656         -      ** to the number of rows in the table.
  3657         -      **
  3658         -      ** We add an additional 4x penalty to full table scans.  This causes
  3659         -      ** the cost function to err on the side of choosing an index over
  3660         -      ** choosing a full scan.  This 4x full-scan penalty is an arguable
  3661         -      ** decision and one which we expect to revisit in the future.  But
  3662         -      ** it seems to be working well enough at the moment.
  3663         -      */
  3664         -      pc.rCost = aiRowEst[0]*4;
  3665         -      pc.plan.wsFlags &= ~WHERE_IDX_ONLY;
  3666         -      if( pIdx ){
  3667         -        pc.plan.wsFlags &= ~WHERE_ORDERED;
  3668         -        pc.plan.nOBSat = nPriorSat;
  3669         -      }
  3670         -    }else{
  3671         -      log10N = estLog(aiRowEst[0]);
  3672         -      pc.rCost = pc.plan.nRow;
  3673         -      if( pIdx ){
  3674         -        if( bLookup ){
  3675         -          /* For an index lookup followed by a table lookup:
  3676         -          **    nInMul index searches to find the start of each index range
  3677         -          **  + nRow steps through the index
  3678         -          **  + nRow table searches to lookup the table entry using the rowid
  3679         -          */
  3680         -          pc.rCost += (nInMul + pc.plan.nRow)*log10N;
  3681         -        }else{
  3682         -          /* For a covering index:
  3683         -          **     nInMul index searches to find the initial entry 
  3684         -          **   + nRow steps through the index
  3685         -          */
  3686         -          pc.rCost += nInMul*log10N;
  3687         -        }
  3688         -      }else{
  3689         -        /* For a rowid primary key lookup:
  3690         -        **    nInMult table searches to find the initial entry for each range
  3691         -        **  + nRow steps through the table
  3692         -        */
  3693         -        pc.rCost += nInMul*log10N;
  3694         -      }
  3695         -    }
  3696         -
  3697         -    /* Add in the estimated cost of sorting the result.  Actual experimental
  3698         -    ** measurements of sorting performance in SQLite show that sorting time
  3699         -    ** adds C*N*log10(N) to the cost, where N is the number of rows to be 
  3700         -    ** sorted and C is a factor between 1.95 and 4.3.  We will split the
  3701         -    ** difference and select C of 3.0.
  3702         -    */
  3703         -    if( bSort ){
  3704         -      double m = estLog(pc.plan.nRow*(nOrderBy - pc.plan.nOBSat)/nOrderBy);
  3705         -      m *= (double)(pc.plan.nOBSat ? 2 : 3);
  3706         -      pc.rCost += pc.plan.nRow*m;
  3707         -    }
  3708         -    if( bDist ){
  3709         -      pc.rCost += pc.plan.nRow*estLog(pc.plan.nRow)*3;
  3710         -    }
  3711         -
  3712         -    /**** Cost of using this index has now been computed ****/
  3713         -
  3714         -    /* If there are additional constraints on this table that cannot
  3715         -    ** be used with the current index, but which might lower the number
  3716         -    ** of output rows, adjust the nRow value accordingly.  This only 
  3717         -    ** matters if the current index is the least costly, so do not bother
  3718         -    ** with this step if we already know this index will not be chosen.
  3719         -    ** Also, never reduce the output row count below 2 using this step.
  3720         -    **
  3721         -    ** It is critical that the notValid mask be used here instead of
  3722         -    ** the notReady mask.  When computing an "optimal" index, the notReady
  3723         -    ** mask will only have one bit set - the bit for the current table.
  3724         -    ** The notValid mask, on the other hand, always has all bits set for
  3725         -    ** tables that are not in outer loops.  If notReady is used here instead
  3726         -    ** of notValid, then a optimal index that depends on inner joins loops
  3727         -    ** might be selected even when there exists an optimal index that has
  3728         -    ** no such dependency.
  3729         -    */
  3730         -    if( pc.plan.nRow>2 && pc.rCost<=p->cost.rCost ){
  3731         -      int k;                       /* Loop counter */
  3732         -      int nSkipEq = pc.plan.nEq;   /* Number of == constraints to skip */
  3733         -      int nSkipRange = nBound;     /* Number of < constraints to skip */
  3734         -      Bitmask thisTab;             /* Bitmap for pSrc */
  3735         -
  3736         -      thisTab = getMask(pWC->pMaskSet, iCur);
  3737         -      for(pTerm=pWC->a, k=pWC->nTerm; pc.plan.nRow>2 && k; k--, pTerm++){
  3738         -        if( pTerm->wtFlags & TERM_VIRTUAL ) continue;
  3739         -        if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue;
  3740         -        if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){
  3741         -          if( nSkipEq ){
  3742         -            /* Ignore the first pc.plan.nEq equality matches since the index
  3743         -            ** has already accounted for these */
  3744         -            nSkipEq--;
  3745         -          }else{
  3746         -            /* Assume each additional equality match reduces the result
  3747         -            ** set size by a factor of 10 */
  3748         -            pc.plan.nRow /= 10;
  3749         -          }
  3750         -        }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){
  3751         -          if( nSkipRange ){
  3752         -            /* Ignore the first nSkipRange range constraints since the index
  3753         -            ** has already accounted for these */
  3754         -            nSkipRange--;
  3755         -          }else{
  3756         -            /* Assume each additional range constraint reduces the result
  3757         -            ** set size by a factor of 3.  Indexed range constraints reduce
  3758         -            ** the search space by a larger factor: 4.  We make indexed range
  3759         -            ** more selective intentionally because of the subjective 
  3760         -            ** observation that indexed range constraints really are more
  3761         -            ** selective in practice, on average. */
  3762         -            pc.plan.nRow /= 3;
  3763         -          }
  3764         -        }else if( (pTerm->eOperator & WO_NOOP)==0 ){
  3765         -          /* Any other expression lowers the output row count by half */
  3766         -          pc.plan.nRow /= 2;
  3767         -        }
  3768         -      }
  3769         -      if( pc.plan.nRow<2 ) pc.plan.nRow = 2;
  3770         -    }
  3771         -
  3772         -
  3773         -    /*WHERETRACE((
  3774         -      "      nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n"
  3775         -      "      notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n"
  3776         -      "      used=0x%llx nOBSat=%d\n",
  3777         -      pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags,
  3778         -      p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used,
  3779         -      pc.plan.nOBSat
  3780         -    ));*/
  3781         -
  3782         -    /* If this index is the best we have seen so far, then record this
  3783         -    ** index and its cost in the p->cost structure.
  3784         -    */
  3785         -    if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){
  3786         -      p->cost = pc;
  3787         -      p->cost.plan.wsFlags &= wsFlagMask;
  3788         -      p->cost.plan.u.pIdx = pIdx;
  3789         -    }
  3790         -
  3791         -    /* If there was an INDEXED BY clause, then only that one index is
  3792         -    ** considered. */
  3793         -    if( pSrc->pIndex ) break;
  3794         -
  3795         -    /* Reset masks for the next index in the loop */
  3796         -    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
  3797         -    eqTermMask = idxEqTermMask;
  3798         -  }
  3799         -
  3800         -  /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
  3801         -  ** is set, then reverse the order that the index will be scanned
  3802         -  ** in. This is used for application testing, to help find cases
  3803         -  ** where application behavior depends on the (undefined) order that
  3804         -  ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
  3805         -  if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
  3806         -    p->cost.plan.wsFlags |= WHERE_REVERSE;
  3807         -  }
  3808         -
  3809         -  assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 );
  3810         -  assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 );
  3811         -  assert( pSrc->pIndex==0 
  3812         -       || p->cost.plan.u.pIdx==0 
  3813         -       || p->cost.plan.u.pIdx==pSrc->pIndex 
  3814         -  );
  3815         -
  3816         -  /*WHERETRACE(("   best index is %s cost=%.1f\n",
  3817         -         p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk",
  3818         -         p->cost.rCost));*/
  3819         -  
  3820         -  bestOrClauseIndex(p);
  3821         -  bestAutomaticIndex(p);
  3822         -  if( eqTermMask & WO_ISNULL ) p->cost.plan.wsFlags |= WHERE_NULL_OK;
  3823         -}
  3824         -
  3825         -/*
  3826         -** Find the query plan for accessing table pSrc->pTab. Write the
  3827         -** best query plan and its cost into the WhereCost object supplied 
  3828         -** as the last parameter. This function may calculate the cost of
  3829         -** both real and virtual table scans.
  3830         -**
  3831         -** This function does not take ORDER BY or DISTINCT into account.  Nor
  3832         -** does it remember the virtual table query plan.  All it does is compute
  3833         -** the cost while determining if an OR optimization is applicable.  The
  3834         -** details will be reconsidered later if the optimization is found to be
  3835         -** applicable.
  3836         -*/
  3837         -static void bestIndex(WhereBestIdx *p){
  3838         -#ifndef SQLITE_OMIT_VIRTUALTABLE
  3839         -  if( IsVirtual(p->pSrc->pTab) ){
  3840         -    sqlite3_index_info *pIdxInfo = 0;
  3841         -    p->ppIdxInfo = &pIdxInfo;
  3842         -    bestVirtualIndex(p);
  3843         -    assert( pIdxInfo!=0 || p->pParse->db->mallocFailed );
  3844         -    if( pIdxInfo && pIdxInfo->needToFreeIdxStr ){
  3845         -      sqlite3_free(pIdxInfo->idxStr);
  3846         -    }
  3847         -    sqlite3DbFree(p->pParse->db, pIdxInfo);
  3848         -  }else
  3849         -#endif
  3850         -  {
  3851         -    bestBtreeIndex(p);
  3852         -  }
  3853         -}
  3854         -
  3855   2538   /*
  3856   2539   ** Disable a term in the WHERE clause.  Except, do not disable the term
  3857   2540   ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
  3858   2541   ** or USING clause of that join.
  3859   2542   **
  3860   2543   ** Consider the term t2.z='ok' in the following queries:
  3861   2544   **
................................................................................
  3945   2628   ** this routine sets up a loop that will iterate over all values of X.
  3946   2629   */
  3947   2630   static int codeEqualityTerm(
  3948   2631     Parse *pParse,      /* The parsing context */
  3949   2632     WhereTerm *pTerm,   /* The term of the WHERE clause to be coded */
  3950   2633     WhereLevel *pLevel, /* The level of the FROM clause we are working on */
  3951   2634     int iEq,            /* Index of the equality term within this level */
         2635  +  int bRev,           /* True for reverse-order IN operations */
  3952   2636     int iTarget         /* Attempt to leave results in this register */
  3953   2637   ){
  3954   2638     Expr *pX = pTerm->pExpr;
  3955   2639     Vdbe *v = pParse->pVdbe;
  3956   2640     int iReg;                  /* Register holding results */
  3957   2641   
  3958   2642     assert( iTarget>0 );
................................................................................
  3962   2646       iReg = iTarget;
  3963   2647       sqlite3VdbeAddOp2(v, OP_Null, 0, iReg);
  3964   2648   #ifndef SQLITE_OMIT_SUBQUERY
  3965   2649     }else{
  3966   2650       int eType;
  3967   2651       int iTab;
  3968   2652       struct InLoop *pIn;
  3969         -    u8 bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
         2653  +    WhereLoop *pLoop = pLevel->pWLoop;
  3970   2654   
  3971         -    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 
  3972         -      && pLevel->plan.u.pIdx->aSortOrder[iEq]
         2655  +    if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0
         2656  +      && pLoop->u.btree.pIndex!=0
         2657  +      && pLoop->u.btree.pIndex->aSortOrder[iEq]
  3973   2658       ){
  3974   2659         testcase( iEq==0 );
  3975   2660         testcase( iEq==pLevel->plan.u.pIdx->nColumn-1 );
  3976   2661         testcase( iEq>0 && iEq+1<pLevel->plan.u.pIdx->nColumn );
  3977   2662         testcase( bRev );
  3978   2663         bRev = !bRev;
  3979   2664       }
................................................................................
  3982   2667       eType = sqlite3FindInIndex(pParse, pX, 0);
  3983   2668       if( eType==IN_INDEX_INDEX_DESC ){
  3984   2669         testcase( bRev );
  3985   2670         bRev = !bRev;
  3986   2671       }
  3987   2672       iTab = pX->iTable;
  3988   2673       sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0);
  3989         -    assert( pLevel->plan.wsFlags & WHERE_IN_ABLE );
         2674  +    assert( pLoop->wsFlags & WHERE_IN_ABLE );
  3990   2675       if( pLevel->u.in.nIn==0 ){
  3991   2676         pLevel->addrNxt = sqlite3VdbeMakeLabel(v);
  3992   2677       }
  3993   2678       pLevel->u.in.nIn++;
  3994   2679       pLevel->u.in.aInLoop =
  3995   2680          sqlite3DbReallocOrFree(pParse->db, pLevel->u.in.aInLoop,
  3996   2681                                 sizeof(pLevel->u.in.aInLoop[0])*pLevel->u.in.nIn);
................................................................................
  4054   2739   ** string in this example would be set to SQLITE_AFF_NONE.
  4055   2740   */
  4056   2741   static int codeAllEqualityTerms(
  4057   2742     Parse *pParse,        /* Parsing context */
  4058   2743     WhereLevel *pLevel,   /* Which nested loop of the FROM we are coding */
  4059   2744     WhereClause *pWC,     /* The WHERE clause */
  4060   2745     Bitmask notReady,     /* Which parts of FROM have not yet been coded */
         2746  +  int bRev,             /* Reverse the order of IN operators */
  4061   2747     int nExtraReg,        /* Number of extra registers to allocate */
  4062   2748     char **pzAff          /* OUT: Set to point to affinity string */
  4063   2749   ){
  4064         -  int nEq = pLevel->plan.nEq;   /* The number of == or IN constraints to code */
         2750  +  int nEq;                      /* The number of == or IN constraints to code */
  4065   2751     Vdbe *v = pParse->pVdbe;      /* The vm under construction */
  4066   2752     Index *pIdx;                  /* The index being used for this loop */
  4067         -  int iCur = pLevel->iTabCur;   /* The cursor of the table */
  4068   2753     WhereTerm *pTerm;             /* A single constraint term */
         2754  +  WhereLoop *pLoop;             /* The WhereLoop object */
  4069   2755     int j;                        /* Loop counter */
  4070   2756     int regBase;                  /* Base register */
  4071   2757     int nReg;                     /* Number of registers to allocate */
  4072   2758     char *zAff;                   /* Affinity string to return */
  4073         -  int eqFlags;                  /* WO_EQ|WO_IN and maybe also WO_ISNULL */
  4074   2759   
  4075   2760     /* This module is only called on query plans that use an index. */
  4076         -  assert( pLevel->plan.wsFlags & WHERE_INDEXED );
  4077         -  pIdx = pLevel->plan.u.pIdx;
         2761  +  pLoop = pLevel->pWLoop;
         2762  +  assert( (pLoop->wsFlags & WHERE_VIRTUALTABLE)==0 );
         2763  +  nEq = pLoop->u.btree.nEq;
         2764  +  pIdx = pLoop->u.btree.pIndex;
         2765  +  assert( pIdx!=0 );
  4078   2766   
  4079   2767     /* Figure out how many memory cells we will need then allocate them.
  4080   2768     */
  4081   2769     regBase = pParse->nMem + 1;
  4082         -  nReg = pLevel->plan.nEq + nExtraReg;
         2770  +  nReg = pLoop->u.btree.nEq + nExtraReg;
  4083   2771     pParse->nMem += nReg;
  4084   2772   
  4085   2773     zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  4086   2774     if( !zAff ){
  4087   2775       pParse->db->mallocFailed = 1;
  4088   2776     }
  4089   2777   
  4090   2778     /* Evaluate the equality constraints
  4091   2779     */
  4092   2780     assert( pIdx->nColumn>=nEq );
  4093         -  eqFlags = (pLevel->plan.wsFlags&WHERE_NULL_OK) ? (WO_EQ|WO_IN|WO_ISNULL)
  4094         -                                                 : (WO_EQ|WO_IN);
  4095   2781     for(j=0; j<nEq; j++){
  4096   2782       int r1;
  4097         -    int k = pIdx->aiColumn[j];
  4098         -    pTerm = findTerm(pWC, iCur, k, notReady, eqFlags, pIdx);
  4099         -    if( pTerm==0 ) break;
         2783  +    pTerm = pLoop->aTerm[j];
         2784  +    assert( pTerm!=0 );
  4100   2785       /* The following true for indices with redundant columns. 
  4101   2786       ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
  4102   2787       testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
  4103   2788       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  4104         -    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, regBase+j);
         2789  +    r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
  4105   2790       if( r1!=regBase+j ){
  4106   2791         if( nReg==1 ){
  4107   2792           sqlite3ReleaseTempReg(pParse, regBase);
  4108   2793           regBase = r1;
  4109   2794         }else{
  4110   2795           sqlite3VdbeAddOp2(v, OP_SCopy, r1, regBase+j);
  4111   2796         }
................................................................................
  4302   2987   ){
  4303   2988     int j, k;            /* Loop counters */
  4304   2989     int iCur;            /* The VDBE cursor for the table */
  4305   2990     int addrNxt;         /* Where to jump to continue with the next IN case */
  4306   2991     int omitTable;       /* True if we use the index only */
  4307   2992     int bRev;            /* True if we need to scan in reverse order */
  4308   2993     WhereLevel *pLevel;  /* The where level to be coded */
         2994  +  WhereLoop *pLoop;    /* The WhereLoop object being coded */
  4309   2995     WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
  4310   2996     WhereTerm *pTerm;               /* A WHERE clause term */
  4311   2997     Parse *pParse;                  /* Parsing context */
  4312   2998     Vdbe *v;                        /* The prepared stmt under constructions */
  4313   2999     struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  4314   3000     int addrBrk;                    /* Jump here to break out of the loop */
  4315   3001     int addrCont;                   /* Jump here to continue with next cycle */
................................................................................
  4317   3003     int iReleaseReg = 0;      /* Temp register to free before returning */
  4318   3004     Bitmask newNotReady;      /* Return value */
  4319   3005   
  4320   3006     pParse = pWInfo->pParse;
  4321   3007     v = pParse->pVdbe;
  4322   3008     pWC = pWInfo->pWC;
  4323   3009     pLevel = &pWInfo->a[iLevel];
         3010  +  pLoop = pLevel->pWLoop;
  4324   3011     pTabItem = &pWInfo->pTabList->a[pLevel->iFrom];
  4325   3012     iCur = pTabItem->iCursor;
  4326         -  bRev = (pLevel->plan.wsFlags & WHERE_REVERSE)!=0;
  4327         -  omitTable = (pLevel->plan.wsFlags & WHERE_IDX_ONLY)!=0 
         3013  +  bRev = (pWInfo->revMask>>iLevel)&1;
         3014  +  omitTable = (pLoop->wsFlags & WHERE_IDX_ONLY)!=0 
  4328   3015              && (wctrlFlags & WHERE_FORCE_TABLE)==0;
  4329   3016     VdbeNoopComment((v, "Begin Join Loop %d", iLevel));
  4330   3017   
  4331   3018     /* Create labels for the "break" and "continue" instructions
  4332   3019     ** for the current loop.  Jump to addrBrk to break out of a loop.
  4333   3020     ** Jump to cont to go immediately to the next iteration of the
  4334   3021     ** loop.
................................................................................
  4358   3045       pLevel->p2 =  sqlite3VdbeAddOp1(v, OP_Yield, regYield);
  4359   3046       VdbeComment((v, "next row of co-routine %s", pTabItem->pTab->zName));
  4360   3047       sqlite3VdbeAddOp2(v, OP_If, regYield+1, addrBrk);
  4361   3048       pLevel->op = OP_Goto;
  4362   3049     }else
  4363   3050   
  4364   3051   #ifndef SQLITE_OMIT_VIRTUALTABLE
  4365         -  if(  (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  4366         -    /* Case 0:  The table is a virtual-table.  Use the VFilter and VNext
         3052  +  if(  (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
         3053  +    /* Case 1:  The table is a virtual-table.  Use the VFilter and VNext
  4367   3054       **          to access the data.
  4368   3055       */
  4369   3056       int iReg;   /* P3 Value for OP_VFilter */
  4370   3057       int addrNotFound;
  4371         -    sqlite3_index_info *pVtabIdx = pLevel->plan.u.pVtabIdx;
  4372         -    int nConstraint = pVtabIdx->nConstraint;
  4373         -    struct sqlite3_index_constraint_usage *aUsage =
  4374         -                                                pVtabIdx->aConstraintUsage;
  4375         -    const struct sqlite3_index_constraint *aConstraint =
  4376         -                                                pVtabIdx->aConstraint;
         3058  +    int nConstraint = pLoop->nTerm;
  4377   3059   
  4378   3060       sqlite3ExprCachePush(pParse);
  4379   3061       iReg = sqlite3GetTempRange(pParse, nConstraint+2);
  4380   3062       addrNotFound = pLevel->addrBrk;
  4381         -    for(j=1; j<=nConstraint; j++){
  4382         -      for(k=0; k<nConstraint; k++){
  4383         -        if( aUsage[k].argvIndex==j ){
  4384         -          int iTarget = iReg+j+1;
  4385         -          pTerm = &pWC->a[aConstraint[k].iTermOffset];
  4386         -          if( pTerm->eOperator & WO_IN ){
  4387         -            codeEqualityTerm(pParse, pTerm, pLevel, k, iTarget);
  4388         -            addrNotFound = pLevel->addrNxt;
  4389         -          }else{
  4390         -            sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
  4391         -          }
  4392         -          break;
  4393         -        }
         3063  +    for(j=0; j<nConstraint; j++){
         3064  +      int iTarget = iReg+j+1;
         3065  +      pTerm = pLoop->aTerm[j];
         3066  +      if( pTerm->eOperator & WO_IN ){
         3067  +        codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
         3068  +        addrNotFound = pLevel->addrNxt;
         3069  +      }else{
         3070  +        sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
  4394   3071         }
  4395         -      if( k==nConstraint ) break;
  4396   3072       }
  4397         -    sqlite3VdbeAddOp2(v, OP_Integer, pVtabIdx->idxNum, iReg);
         3073  +    sqlite3VdbeAddOp2(v, OP_Integer, pLoop->u.vtab.idxNum, iReg);
  4398   3074       sqlite3VdbeAddOp2(v, OP_Integer, j-1, iReg+1);
  4399         -    sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg, pVtabIdx->idxStr,
  4400         -                      pVtabIdx->needToFreeIdxStr ? P4_MPRINTF : P4_STATIC);
  4401         -    pVtabIdx->needToFreeIdxStr = 0;
  4402         -    for(j=0; j<nConstraint; j++){
  4403         -      if( aUsage[j].omit ){
  4404         -        int iTerm = aConstraint[j].iTermOffset;
  4405         -        disableTerm(pLevel, &pWC->a[iTerm]);
         3075  +    sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
         3076  +                      pLoop->u.vtab.idxStr,
         3077  +                      pLoop->u.vtab.needFree ? P4_MPRINTF : P4_STATIC);
         3078  +    pLoop->u.vtab.needFree = 0;
         3079  +    for(j=0; j<nConstraint && j<16; j++){
         3080  +      if( (pLoop->u.vtab.omitMask>>j)&1 ){
         3081  +        disableTerm(pLevel, pLoop->aTerm[j]);
  4406   3082         }
  4407   3083       }
  4408   3084       pLevel->op = OP_VNext;
  4409   3085       pLevel->p1 = iCur;
  4410   3086       pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  4411   3087       sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  4412   3088       sqlite3ExprCachePop(pParse, 1);
  4413   3089     }else
  4414   3090   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  4415   3091   
  4416         -  if( pLevel->plan.wsFlags & WHERE_ROWID_EQ ){
  4417         -    /* Case 1:  We can directly reference a single row using an
         3092  +  if( (pLoop->wsFlags & WHERE_IPK)!=0
         3093  +   && (pLoop->wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_EQ))!=0
         3094  +  ){
         3095  +    /* Case 2:  We can directly reference a single row using an
  4418   3096       **          equality comparison against the ROWID field.  Or
  4419   3097       **          we reference multiple rows using a "rowid IN (...)"
  4420   3098       **          construct.
  4421   3099       */
         3100  +    assert( pLoop->u.btree.nEq==1 );
  4422   3101       iReleaseReg = sqlite3GetTempReg(pParse);
  4423         -    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
         3102  +    pTerm = pLoop->aTerm[0];
  4424   3103       assert( pTerm!=0 );
  4425   3104       assert( pTerm->pExpr!=0 );
  4426   3105       assert( omitTable==0 );
  4427   3106       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  4428         -    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, iReleaseReg);
         3107  +    iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
  4429   3108       addrNxt = pLevel->addrNxt;
  4430   3109       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
  4431   3110       sqlite3VdbeAddOp3(v, OP_NotExists, iCur, addrNxt, iRowidReg);
  4432   3111       sqlite3ExprCacheAffinityChange(pParse, iRowidReg, 1);
  4433   3112       sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
  4434   3113       VdbeComment((v, "pk"));
  4435   3114       pLevel->op = OP_Noop;
  4436         -  }else if( pLevel->plan.wsFlags & WHERE_ROWID_RANGE ){
  4437         -    /* Case 2:  We have an inequality comparison against the ROWID field.
         3115  +  }else if( (pLoop->wsFlags & WHERE_IPK)!=0
         3116  +         && (pLoop->wsFlags & WHERE_COLUMN_RANGE)!=0
         3117  +  ){
         3118  +    /* Case 3:  We have an inequality comparison against the ROWID field.
  4438   3119       */
  4439   3120       int testOp = OP_Noop;
  4440   3121       int start;
  4441   3122       int memEndValue = 0;
  4442   3123       WhereTerm *pStart, *pEnd;
  4443   3124   
  4444   3125       assert( omitTable==0 );
  4445         -    pStart = findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0);
  4446         -    pEnd = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0);
         3126  +    j = 0;
         3127  +    pStart = pEnd = 0;
         3128  +    if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aTerm[j++];
         3129  +    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aTerm[j++];
  4447   3130       if( bRev ){
  4448   3131         pTerm = pStart;
  4449   3132         pStart = pEnd;
  4450   3133         pEnd = pTerm;
  4451   3134       }
  4452   3135       if( pStart ){
  4453   3136         Expr *pX;             /* The expression that defines the start bound */
................................................................................
  4506   3189       if( testOp!=OP_Noop ){
  4507   3190         iRowidReg = iReleaseReg = sqlite3GetTempReg(pParse);
  4508   3191         sqlite3VdbeAddOp2(v, OP_Rowid, iCur, iRowidReg);
  4509   3192         sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
  4510   3193         sqlite3VdbeAddOp3(v, testOp, memEndValue, addrBrk, iRowidReg);
  4511   3194         sqlite3VdbeChangeP5(v, SQLITE_AFF_NUMERIC | SQLITE_JUMPIFNULL);
  4512   3195       }
  4513         -  }else if( pLevel->plan.wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ) ){
  4514         -    /* Case 3: A scan using an index.
         3196  +  }else if( pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_COLUMN_EQ|WHERE_IDX_ONLY) ){
         3197  +    /* Case 4: A scan using an index.
  4515   3198       **
  4516   3199       **         The WHERE clause may contain zero or more equality 
  4517   3200       **         terms ("==" or "IN" operators) that refer to the N
  4518   3201       **         left-most columns of the index. It may also contain
  4519   3202       **         inequality constraints (>, <, >= or <=) on the indexed
  4520   3203       **         column that immediately follows the N equalities. Only 
  4521   3204       **         the right-most column can be an inequality - the rest must
................................................................................
  4553   3236         OP_SeekLe            /* 7: (start_constraints  &&  startEq &&  bRev) */
  4554   3237       };
  4555   3238       static const u8 aEndOp[] = {
  4556   3239         OP_Noop,             /* 0: (!end_constraints) */
  4557   3240         OP_IdxGE,            /* 1: (end_constraints && !bRev) */
  4558   3241         OP_IdxLT             /* 2: (end_constraints && bRev) */
  4559   3242       };
  4560         -    int nEq = pLevel->plan.nEq;  /* Number of == or IN terms */
  4561         -    int isMinQuery = 0;          /* If this is an optimized SELECT min(x).. */
         3243  +    int nEq = pLoop->u.btree.nEq;  /* Number of == or IN terms */
         3244  +    int isMinQuery = 0;            /* If this is an optimized SELECT min(x).. */
  4562   3245       int regBase;                 /* Base register holding constraint values */
  4563   3246       int r1;                      /* Temp register */
  4564   3247       WhereTerm *pRangeStart = 0;  /* Inequality constraint at range start */
  4565   3248       WhereTerm *pRangeEnd = 0;    /* Inequality constraint at range end */
  4566   3249       int startEq;                 /* True if range start uses ==, >= or <= */
  4567   3250       int endEq;                   /* True if range end uses ==, >= or <= */
  4568   3251       int start_constraints;       /* Start of range is constrained */
................................................................................
  4570   3253       Index *pIdx;                 /* The index we will be using */
  4571   3254       int iIdxCur;                 /* The VDBE cursor for the index */
  4572   3255       int nExtraReg = 0;           /* Number of extra registers needed */
  4573   3256       int op;                      /* Instruction opcode */
  4574   3257       char *zStartAff;             /* Affinity for start of range constraint */
  4575   3258       char *zEndAff;               /* Affinity for end of range constraint */
  4576   3259   
  4577         -    pIdx = pLevel->plan.u.pIdx;
         3260  +    pIdx = pLoop->u.btree.pIndex;
  4578   3261       iIdxCur = pLevel->iIdxCur;
  4579   3262       k = (nEq==pIdx->nColumn ? -1 : pIdx->aiColumn[nEq]);
  4580   3263   
  4581   3264       /* If this loop satisfies a sort order (pOrderBy) request that 
  4582   3265       ** was passed to this function to implement a "SELECT min(x) ..." 
  4583   3266       ** query, then the caller will only allow the loop to run for
  4584   3267       ** a single iteration. This means that the first row returned
  4585   3268       ** should not have a NULL value stored in 'x'. If column 'x' is
  4586   3269       ** the first one after the nEq equality constraints in the index,
  4587   3270       ** this requires some special handling.
  4588   3271       */
  4589   3272       if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0
  4590         -     && (pLevel->plan.wsFlags&WHERE_ORDERED)
         3273  +     && (pWInfo->nOBSat>0)
  4591   3274        && (pIdx->nColumn>nEq)
  4592   3275       ){
  4593   3276         /* assert( pOrderBy->nExpr==1 ); */
  4594   3277         /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */
  4595   3278         isMinQuery = 1;
  4596   3279         nExtraReg = 1;
  4597   3280       }
  4598   3281   
  4599   3282       /* Find any inequality constraint terms for the start and end 
  4600   3283       ** of the range. 
  4601   3284       */
  4602         -    if( pLevel->plan.wsFlags & WHERE_TOP_LIMIT ){
  4603         -      pRangeEnd = findTerm(pWC, iCur, k, notReady, (WO_LT|WO_LE), pIdx);
         3285  +    j = nEq;
         3286  +    if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
         3287  +      pRangeStart = pLoop->aTerm[j++];
  4604   3288         nExtraReg = 1;
  4605   3289       }
  4606         -    if( pLevel->plan.wsFlags & WHERE_BTM_LIMIT ){
  4607         -      pRangeStart = findTerm(pWC, iCur, k, notReady, (WO_GT|WO_GE), pIdx);
         3290  +    if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
         3291  +      pRangeEnd = pLoop->aTerm[j++];
  4608   3292         nExtraReg = 1;
  4609   3293       }
  4610   3294   
  4611   3295       /* Generate code to evaluate all constraint terms using == or IN
  4612   3296       ** and store the values of those terms in an array of registers
  4613   3297       ** starting at regBase.
  4614   3298       */
  4615   3299       regBase = codeAllEqualityTerms(
  4616         -        pParse, pLevel, pWC, notReady, nExtraReg, &zStartAff
         3300  +        pParse, pLevel, pWC, notReady, bRev, nExtraReg, &zStartAff
  4617   3301       );
  4618   3302       zEndAff = sqlite3DbStrDup(pParse->db, zStartAff);
  4619   3303       addrNxt = pLevel->addrNxt;
  4620   3304   
  4621   3305       /* If we are doing a reverse order scan on an ascending index, or
  4622   3306       ** a forward order scan on a descending index, interchange the 
  4623   3307       ** start and end terms (pRangeStart and pRangeEnd).
................................................................................
  4719   3403       /* If there are inequality constraints, check that the value
  4720   3404       ** of the table column that the inequality contrains is not NULL.
  4721   3405       ** If it is, jump to the next iteration of the loop.
  4722   3406       */
  4723   3407       r1 = sqlite3GetTempReg(pParse);
  4724   3408       testcase( pLevel->plan.wsFlags & WHERE_BTM_LIMIT );
  4725   3409       testcase( pLevel->plan.wsFlags & WHERE_TOP_LIMIT );
  4726         -    if( (pLevel->plan.wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
         3410  +    if( (pLoop->wsFlags & (WHERE_BTM_LIMIT|WHERE_TOP_LIMIT))!=0 ){
  4727   3411         sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, nEq, r1);
  4728   3412         sqlite3VdbeAddOp2(v, OP_IsNull, r1, addrCont);
  4729   3413       }
  4730   3414       sqlite3ReleaseTempReg(pParse, r1);
  4731   3415   
  4732   3416       /* Seek the table cursor, if required */
  4733   3417       disableTerm(pLevel, pRangeStart);
................................................................................
  4738   3422         sqlite3ExprCacheStore(pParse, iCur, -1, iRowidReg);
  4739   3423         sqlite3VdbeAddOp2(v, OP_Seek, iCur, iRowidReg);  /* Deferred seek */
  4740   3424       }
  4741   3425   
  4742   3426       /* Record the instruction used to terminate the loop. Disable 
  4743   3427       ** WHERE clause terms made redundant by the index range scan.
  4744   3428       */
  4745         -    if( pLevel->plan.wsFlags & WHERE_UNIQUE ){
         3429  +    if( pLoop->wsFlags & WHERE_UNIQUE ){
  4746   3430         pLevel->op = OP_Noop;
  4747   3431       }else if( bRev ){
  4748   3432         pLevel->op = OP_Prev;
  4749   3433       }else{
  4750   3434         pLevel->op = OP_Next;
  4751   3435       }
  4752   3436       pLevel->p1 = iIdxCur;
  4753         -    if( pLevel->plan.wsFlags & WHERE_COVER_SCAN ){
         3437  +    if( pLoop->wsFlags & WHERE_COVER_SCAN ){
  4754   3438         pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  4755   3439       }else{
  4756   3440         assert( pLevel->p5==0 );
  4757   3441       }
  4758   3442     }else
  4759   3443   
  4760   3444   #ifndef SQLITE_OMIT_OR_OPTIMIZATION
  4761         -  if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
  4762         -    /* Case 4:  Two or more separately indexed terms connected by OR
         3445  +  if( pLoop->wsFlags & WHERE_MULTI_OR ){
         3446  +    /* Case 5:  Two or more separately indexed terms connected by OR
  4763   3447       **
  4764   3448       ** Example:
  4765   3449       **
  4766   3450       **   CREATE TABLE t1(a,b,c,d);
  4767   3451       **   CREATE INDEX i1 ON t1(a);
  4768   3452       **   CREATE INDEX i2 ON t1(b);
  4769   3453       **   CREATE INDEX i3 ON t1(c);
................................................................................
  4808   3492       int regRowid = 0;                         /* Register holding rowid */
  4809   3493       int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
  4810   3494       int iRetInit;                             /* Address of regReturn init */
  4811   3495       int untestedTerms = 0;             /* Some terms not completely tested */
  4812   3496       int ii;                            /* Loop counter */
  4813   3497       Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  4814   3498      
  4815         -    pTerm = pLevel->plan.u.pTerm;
         3499  +    pTerm = pLoop->aTerm[0];
  4816   3500       assert( pTerm!=0 );
  4817   3501       assert( pTerm->eOperator & WO_OR );
  4818   3502       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  4819   3503       pOrWc = &pTerm->u.pOrInfo->wc;
  4820   3504       pLevel->op = OP_Return;
  4821   3505       pLevel->p1 = regReturn;
  4822   3506   
................................................................................
  4900   3584           }
  4901   3585           /* Loop through table entries that match term pOrTerm. */
  4902   3586           pSubWInfo = sqlite3WhereBegin(pParse, pOrTab, pOrExpr, 0, 0,
  4903   3587                           WHERE_OMIT_OPEN_CLOSE | WHERE_AND_ONLY |
  4904   3588                           WHERE_FORCE_TABLE | WHERE_ONETABLE_ONLY, iCovCur);
  4905   3589           assert( pSubWInfo || pParse->nErr || pParse->db->mallocFailed );
  4906   3590           if( pSubWInfo ){
  4907         -          WhereLevel *pLvl;
         3591  +          WhereLoop *pSubLoop;
  4908   3592             explainOneScan(
  4909   3593                 pParse, pOrTab, &pSubWInfo->a[0], iLevel, pLevel->iFrom, 0
  4910   3594             );
  4911   3595             if( (wctrlFlags & WHERE_DUPLICATES_OK)==0 ){
  4912   3596               int iSet = ((ii==pOrWc->nTerm-1)?-1:ii);
  4913   3597               int r;
  4914   3598               r = sqlite3ExprCodeGetColumn(pParse, pTabItem->pTab, -1, iCur, 
................................................................................
  4933   3617             ** If the call to sqlite3WhereBegin() above resulted in a scan that
  4934   3618             ** uses an index, and this is either the first OR-connected term
  4935   3619             ** processed or the index is the same as that used by all previous
  4936   3620             ** terms, set pCov to the candidate covering index. Otherwise, set 
  4937   3621             ** pCov to NULL to indicate that no candidate covering index will 
  4938   3622             ** be available.
  4939   3623             */
  4940         -          pLvl = &pSubWInfo->a[0];
  4941         -          if( (pLvl->plan.wsFlags & WHERE_INDEXED)!=0
  4942         -           && (pLvl->plan.wsFlags & WHERE_TEMP_INDEX)==0
  4943         -           && (ii==0 || pLvl->plan.u.pIdx==pCov)
         3624  +          pSubLoop = pSubWInfo->a[0].pWLoop;
         3625  +          if( (pSubLoop->wsFlags & WHERE_INDEXED)!=0
         3626  +           && (pSubLoop->wsFlags & WHERE_TEMP_INDEX)==0
         3627  +           && (ii==0 || pSubLoop->u.btree.pIndex==pCov)
  4944   3628             ){
  4945         -            assert( pLvl->iIdxCur==iCovCur );
  4946         -            pCov = pLvl->plan.u.pIdx;
         3629  +            assert( pSubWInfo->a[0].iIdxCur==iCovCur );
         3630  +            pCov = pLoop->u.btree.pIndex;
  4947   3631             }else{
  4948   3632               pCov = 0;
  4949   3633             }
  4950   3634   
  4951   3635             /* Finish the loop through table entries that match term pOrTerm. */
  4952   3636             sqlite3WhereEnd(pSubWInfo);
  4953   3637           }
................................................................................
  4965   3649   
  4966   3650       if( pWInfo->nLevel>1 ) sqlite3StackFree(pParse->db, pOrTab);
  4967   3651       if( !untestedTerms ) disableTerm(pLevel, pTerm);
  4968   3652     }else
  4969   3653   #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
  4970   3654   
  4971   3655     {
  4972         -    /* Case 5:  There is no usable index.  We must do a complete
         3656  +    /* Case 6:  There is no usable index.  We must do a complete
  4973   3657       **          scan of the entire table.
  4974   3658       */
  4975   3659       static const u8 aStep[] = { OP_Next, OP_Prev };
  4976   3660       static const u8 aStart[] = { OP_Rewind, OP_Last };
  4977   3661       assert( bRev==0 || bRev==1 );
  4978         -    assert( omitTable==0 );
  4979   3662       pLevel->op = aStep[bRev];
  4980   3663       pLevel->p1 = iCur;
  4981   3664       pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
  4982   3665       pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  4983   3666     }
  4984   3667     newNotReady = notReady & ~getMask(pWC->pMaskSet, iCur);
  4985   3668   
................................................................................
  5141   3824   /*
  5142   3825   ** Free a WhereInfo structure
  5143   3826   */
  5144   3827   static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){
  5145   3828     if( ALWAYS(pWInfo) ){
  5146   3829       int i;
  5147   3830       for(i=0; i<pWInfo->nLevel; i++){
  5148         -      sqlite3_index_info *pInfo = pWInfo->a[i].pIdxInfo;
  5149         -      if( pInfo ){
  5150         -        /* assert( pInfo->needToFreeIdxStr==0 || db->mallocFailed ); */
  5151         -        if( pInfo->needToFreeIdxStr ){
  5152         -          sqlite3_free(pInfo->idxStr);
  5153         -        }
  5154         -        sqlite3DbFree(db, pInfo);
  5155         -      }
  5156         -      if( pWInfo->a[i].plan.wsFlags & WHERE_TEMP_INDEX ){
  5157         -        Index *pIdx = pWInfo->a[i].plan.u.pIdx;
         3831  +      if( pWInfo->a[i].pWLoop->wsFlags & WHERE_TEMP_INDEX ){
         3832  +        Index *pIdx = pWInfo->a[i].pWLoop->u.btree.pIndex;
  5158   3833           if( pIdx ){
  5159   3834             sqlite3DbFree(db, pIdx->zColAff);
  5160   3835             sqlite3DbFree(db, pIdx);
  5161   3836           }
  5162   3837         }
  5163   3838       }
  5164   3839       whereClauseClear(pWInfo->pWC);
................................................................................
  5329   4004     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  5330   4005                           opMask, pProbe);
  5331   4006     savedLoop = *pNew;
  5332   4007     pNew->rSetup = (double)0;
  5333   4008     rLogSize = estLog(pProbe->aiRowEst[0]);
  5334   4009     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  5335   4010       int nIn = 1;
         4011  +    pNew->wsFlags = savedLoop.wsFlags;
  5336   4012       pNew->u.btree.nEq = savedLoop.u.btree.nEq;
  5337   4013       pNew->nTerm = savedLoop.nTerm;
  5338   4014       if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */
  5339   4015       pNew->aTerm[pNew->nTerm++] = pTerm;
  5340   4016       pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
  5341   4017       if( pTerm->eOperator & WO_IN ){
  5342   4018         Expr *pExpr = pTerm->pExpr;
................................................................................
  6179   4855     pFrom = aFrom;
  6180   4856     for(ii=1; ii<nFrom; ii++){
  6181   4857       if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  6182   4858     }
  6183   4859     assert( pWInfo->nLevel==nLoop );
  6184   4860     /* Load the lowest cost path into pWInfo */
  6185   4861     for(iLoop=0; iLoop<nLoop; iLoop++){
  6186         -    pWInfo->a[iLoop].pWLoop = pFrom->aLoop[iLoop];
         4862  +    WhereLevel *pLevel = pWInfo->a + iLoop;
         4863  +    pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
         4864  +    pLevel->iFrom = pWLoop->iTab; /* FIXME: Omit the iFrom field */
         4865  +    pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;
  6187   4866     }
  6188   4867     if( pFrom->isOrdered ){
  6189   4868       pWInfo->nOBSat = pWInfo->pOrderBy->nExpr;
  6190   4869       pWInfo->revMask = pFrom->revLoop;
  6191   4870     }
  6192   4871     pWInfo->nRowOut = pFrom->nRow;
  6193   4872   
................................................................................
  6298   4977     WhereInfo *pWInfo;         /* Will become the return value of this function */
  6299   4978     Vdbe *v = pParse->pVdbe;   /* The virtual database engine */
  6300   4979     Bitmask notReady;          /* Cursors that are not yet positioned */
  6301   4980     WhereBestIdx sWBI;         /* Best index search context */
  6302   4981     WhereLoopBuilder sWLB;     /* The WhereLoop builder */
  6303   4982     WhereMaskSet *pMaskSet;    /* The expression mask set */
  6304   4983     WhereLevel *pLevel;        /* A single level in pWInfo->a[] */
  6305         -  int iFrom;                 /* First unused FROM clause element */
  6306         -  int andFlags;              /* AND-ed combination of all pWC->a[].wtFlags */
  6307   4984     int ii;                    /* Loop counter */
  6308   4985     sqlite3 *db;               /* Database connection */
  6309   4986     int rc;                    /* Return code */
  6310   4987   
  6311   4988   
  6312   4989     /* Variable initialization */
  6313   4990     memset(&sWBI, 0, sizeof(sWBI));
................................................................................
  6472   5149       }
  6473   5150       for(ii=0; ii<nTabList; ii++){
  6474   5151         whereLoopPrint(pWInfo->a[ii].pWLoop, pTabList);
  6475   5152       }
  6476   5153     }
  6477   5154   #endif
  6478   5155   
  6479         -  /* Chose the best index to use for each table in the FROM clause.
  6480         -  **
  6481         -  ** This loop fills in the following fields:
  6482         -  **
  6483         -  **   pWInfo->a[].pIdx      The index to use for this level of the loop.
  6484         -  **   pWInfo->a[].wsFlags   WHERE_xxx flags associated with pIdx
  6485         -  **   pWInfo->a[].nEq       The number of == and IN constraints
  6486         -  **   pWInfo->a[].iFrom     Which term of the FROM clause is being coded
  6487         -  **   pWInfo->a[].iTabCur   The VDBE cursor for the database table
  6488         -  **   pWInfo->a[].iIdxCur   The VDBE cursor for the index
  6489         -  **   pWInfo->a[].pTerm     When wsFlags==WO_OR, the OR-clause term
  6490         -  **
  6491         -  ** This loop also figures out the nesting order of tables in the FROM
  6492         -  ** clause.
  6493         -  */
  6494         -  sWBI.notValid = ~(Bitmask)0;
  6495         -  sWBI.pOrderBy = pOrderBy;
  6496         -  sWBI.n = nTabList;
  6497         -  sWBI.pDistinct = pDistinct;
  6498         -  andFlags = ~0;
  6499         -  for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){
  6500         -    WhereCost bestPlan;         /* Most efficient plan seen so far */
  6501         -    Index *pIdx;                /* Index for FROM table at pTabItem */
  6502         -    int j;                      /* For looping over FROM tables */
  6503         -    int bestJ = -1;             /* The value of j */
  6504         -    Bitmask m;                  /* Bitmask value for j or bestJ */
  6505         -    int isOptimal;              /* Iterator for optimal/non-optimal search */
  6506         -    int ckOptimal;              /* Do the optimal scan check */
  6507         -    int nUnconstrained;         /* Number tables without INDEXED BY */
  6508         -    Bitmask notIndexed;         /* Mask of tables that cannot use an index */
  6509         -
  6510         -    memset(&bestPlan, 0, sizeof(bestPlan));
  6511         -    bestPlan.rCost = SQLITE_BIG_DBL;
  6512         -    /*WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i));*/
  6513         -
  6514         -    /* Loop through the remaining entries in the FROM clause to find the
  6515         -    ** next nested loop. The loop tests all FROM clause entries
  6516         -    ** either once or twice. 
  6517         -    **
  6518         -    ** The first test is always performed if there are two or more entries
  6519         -    ** remaining and never performed if there is only one FROM clause entry
  6520         -    ** to choose from.  The first test looks for an "optimal" scan.  In
  6521         -    ** this context an optimal scan is one that uses the same strategy
  6522         -    ** for the given FROM clause entry as would be selected if the entry
  6523         -    ** were used as the innermost nested loop.  In other words, a table
  6524         -    ** is chosen such that the cost of running that table cannot be reduced
  6525         -    ** by waiting for other tables to run first.  This "optimal" test works
  6526         -    ** by first assuming that the FROM clause is on the inner loop and finding
  6527         -    ** its query plan, then checking to see if that query plan uses any
  6528         -    ** other FROM clause terms that are sWBI.notValid.  If no notValid terms
  6529         -    ** are used then the "optimal" query plan works.
  6530         -    **
  6531         -    ** Note that the WhereCost.nRow parameter for an optimal scan might
  6532         -    ** not be as small as it would be if the table really were the innermost
  6533         -    ** join.  The nRow value can be reduced by WHERE clause constraints
  6534         -    ** that do not use indices.  But this nRow reduction only happens if the
  6535         -    ** table really is the innermost join.  
  6536         -    **
  6537         -    ** The second loop iteration is only performed if no optimal scan
  6538         -    ** strategies were found by the first iteration. This second iteration
  6539         -    ** is used to search for the lowest cost scan overall.
  6540         -    **
  6541         -    ** Without the optimal scan step (the first iteration) a suboptimal
  6542         -    ** plan might be chosen for queries like this:
  6543         -    **   
  6544         -    **   CREATE TABLE t1(a, b); 
  6545         -    **   CREATE TABLE t2(c, d);
  6546         -    **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
  6547         -    **
  6548         -    ** The best strategy is to iterate through table t1 first. However it
  6549         -    ** is not possible to determine this with a simple greedy algorithm.
  6550         -    ** Since the cost of a linear scan through table t2 is the same 
  6551         -    ** as the cost of a linear scan through table t1, a simple greedy 
  6552         -    ** algorithm may choose to use t2 for the outer loop, which is a much
  6553         -    ** costlier approach.
  6554         -    */
  6555         -    nUnconstrained = 0;
  6556         -    notIndexed = 0;
  6557         -
  6558         -    /* The optimal scan check only occurs if there are two or more tables
  6559         -    ** available to be reordered */
  6560         -    if( iFrom==nTabList-1 ){
  6561         -      ckOptimal = 0;  /* Common case of just one table in the FROM clause */
  6562         -    }else{
  6563         -      ckOptimal = -1;
  6564         -      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
  6565         -        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
  6566         -        if( (m & sWBI.notValid)==0 ){
  6567         -          if( j==iFrom ) iFrom++;
  6568         -          continue;
  6569         -        }
  6570         -        if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0 ) break;
  6571         -        if( ++ckOptimal ) break;
  6572         -        if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
  6573         -      }
  6574         -    }
  6575         -    assert( ckOptimal==0 || ckOptimal==1 );
  6576         -
  6577         -    for(isOptimal=ckOptimal; isOptimal>=0 && bestJ<0; isOptimal--){
  6578         -      for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){
  6579         -        if( j>iFrom && (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0 ){
  6580         -          /* This break and one like it in the ckOptimal computation loop
  6581         -          ** above prevent table reordering across LEFT and CROSS JOINs.
  6582         -          ** The LEFT JOIN case is necessary for correctness.  The prohibition
  6583         -          ** against reordering across a CROSS JOIN is an SQLite feature that
  6584         -          ** allows the developer to control table reordering */
  6585         -          break;
  6586         -        }
  6587         -        m = getMask(pMaskSet, sWBI.pSrc->iCursor);
  6588         -        if( (m & sWBI.notValid)==0 ){
  6589         -          assert( j>iFrom );
  6590         -          continue;
  6591         -        }
  6592         -        sWBI.notReady = (isOptimal ? m : sWBI.notValid);
  6593         -        if( sWBI.pSrc->pIndex==0 ) nUnconstrained++;
  6594         -  
  6595         -        /*WHERETRACE(("   === trying table %d (%s) with isOptimal=%d ===\n",
  6596         -                    j, sWBI.pSrc->pTab->zName, isOptimal));*/
  6597         -        assert( sWBI.pSrc->pTab );
  6598         -#ifndef SQLITE_OMIT_VIRTUALTABLE
  6599         -        if( IsVirtual(sWBI.pSrc->pTab) ){
  6600         -          sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo;
  6601         -          bestVirtualIndex(&sWBI);
  6602         -        }else 
  6603         -#endif
  6604         -        {
  6605         -          bestBtreeIndex(&sWBI);
  6606         -        }
  6607         -        assert( isOptimal || (sWBI.cost.used&sWBI.notValid)==0 );
  6608         -
  6609         -        /* If an INDEXED BY clause is present, then the plan must use that
  6610         -        ** index if it uses any index at all */
  6611         -        assert( sWBI.pSrc->pIndex==0 
  6612         -                  || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0
  6613         -                  || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex );
  6614         -
  6615         -        if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){
  6616         -          notIndexed |= m;
  6617         -        }
  6618         -        if( isOptimal ){
  6619         -          pWInfo->a[j].rOptCost = sWBI.cost.rCost;
  6620         -        }else if( ckOptimal ){
  6621         -          /* If two or more tables have nearly the same outer loop cost, but
  6622         -          ** very different inner loop (optimal) cost, we want to choose
  6623         -          ** for the outer loop that table which benefits the least from
  6624         -          ** being in the inner loop.  The following code scales the 
  6625         -          ** outer loop cost estimate to accomplish that. */
  6626         -          /*WHERETRACE(("   scaling cost from %.1f to %.1f\n",
  6627         -                      sWBI.cost.rCost,
  6628         -                      sWBI.cost.rCost/pWInfo->a[j].rOptCost));*/
  6629         -          sWBI.cost.rCost /= pWInfo->a[j].rOptCost;
  6630         -        }
  6631         -
  6632         -        /* Conditions under which this table becomes the best so far:
  6633         -        **
  6634         -        **   (1) The table must not depend on other tables that have not
  6635         -        **       yet run.  (In other words, it must not depend on tables
  6636         -        **       in inner loops.)
  6637         -        **
  6638         -        **   (2) (This rule was removed on 2012-11-09.  The scaling of the
  6639         -        **       cost using the optimal scan cost made this rule obsolete.)
  6640         -        **
  6641         -        **   (3) All tables have an INDEXED BY clause or this table lacks an
  6642         -        **       INDEXED BY clause or this table uses the specific
  6643         -        **       index specified by its INDEXED BY clause.  This rule ensures
  6644         -        **       that a best-so-far is always selected even if an impossible
  6645         -        **       combination of INDEXED BY clauses are given.  The error
  6646         -        **       will be detected and relayed back to the application later.
  6647         -        **       The NEVER() comes about because rule (2) above prevents
  6648         -        **       An indexable full-table-scan from reaching rule (3).
  6649         -        **
  6650         -        **   (4) The plan cost must be lower than prior plans, where "cost"
  6651         -        **       is defined by the compareCost() function above. 
  6652         -        */
  6653         -        if( (sWBI.cost.used&sWBI.notValid)==0                    /* (1) */
  6654         -            && (nUnconstrained==0 || sWBI.pSrc->pIndex==0        /* (3) */
  6655         -                || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0))
  6656         -            && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan))   /* (4) */
  6657         -        ){
  6658         -          /*WHERETRACE(("   === table %d (%s) is best so far\n"
  6659         -                      "       cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n",
  6660         -                      j, sWBI.pSrc->pTab->zName,
  6661         -                      sWBI.cost.rCost, sWBI.cost.plan.nRow,
  6662         -                      sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags));*/
  6663         -          bestPlan = sWBI.cost;
  6664         -          bestJ = j;
  6665         -        }
  6666         -
  6667         -        /* In a join like "w JOIN x LEFT JOIN y JOIN z"  make sure that
  6668         -        ** table y (and not table z) is always the next inner loop inside
  6669         -        ** of table x. */
  6670         -        if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break;
  6671         -      }
  6672         -    }
  6673         -    assert( bestJ>=0 );
  6674         -    assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  6675         -    assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 );
  6676         -    testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 );
  6677         -    testcase( bestJ>iFrom && bestJ<nTabList-1
  6678         -                          && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 );
  6679         -    /*WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n"
  6680         -                "    cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n",
  6681         -                bestJ, pTabList->a[bestJ].pTab->zName,
  6682         -                pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow,
  6683         -                bestPlan.plan.nOBSat, bestPlan.plan.wsFlags));*/
  6684         -    if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){
  6685         -      assert( pWInfo->eDistinct==0 );
  6686         -      pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  6687         -    }
  6688         -    andFlags &= bestPlan.plan.wsFlags;
  6689         -    pLevel->plan = bestPlan.plan;
  6690         -    pLevel->iTabCur = pTabList->a[bestJ].iCursor;
  6691         -    testcase( bestPlan.plan.wsFlags & WHERE_INDEXED );
  6692         -    testcase( bestPlan.plan.wsFlags & WHERE_TEMP_INDEX );
  6693         -    if( bestPlan.plan.wsFlags & (WHERE_INDEXED|WHERE_TEMP_INDEX) ){
  6694         -      if( (wctrlFlags & WHERE_ONETABLE_ONLY) 
  6695         -       && (bestPlan.plan.wsFlags & WHERE_TEMP_INDEX)==0 
  6696         -      ){
  6697         -        pLevel->iIdxCur = iIdxCur;
  6698         -      }else{
  6699         -        pLevel->iIdxCur = pParse->nTab++;
  6700         -      }
  6701         -    }else{
  6702         -      pLevel->iIdxCur = -1;
  6703         -    }
  6704         -    sWBI.notValid &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor);
  6705         -    pLevel->iFrom = (u8)bestJ;
  6706         -    if( bestPlan.plan.nRow>=(double)1 ){
  6707         -      pParse->nQueryLoop *= bestPlan.plan.nRow;
  6708         -    }
  6709         -
  6710         -    /* Check that if the table scanned by this loop iteration had an
  6711         -    ** INDEXED BY clause attached to it, that the named index is being
  6712         -    ** used for the scan. If not, then query compilation has failed.
  6713         -    ** Return an error.
  6714         -    */
  6715         -    pIdx = pTabList->a[bestJ].pIndex;
  6716         -    if( pIdx ){
  6717         -      if( (bestPlan.plan.wsFlags & WHERE_INDEXED)==0 ){
  6718         -        sqlite3ErrorMsg(pParse, "cannot use index: %s", pIdx->zName);
  6719         -        goto whereBeginError;
  6720         -      }else{
  6721         -        /* If an INDEXED BY clause is used, the bestIndex() function is
  6722         -        ** guaranteed to find the index specified in the INDEXED BY clause
  6723         -        ** if it find an index at all. */
  6724         -        assert( bestPlan.plan.u.pIdx==pIdx );
  6725         -      }
  6726         -    }
  6727         -  }
  6728         -  WHERETRACE(("*** Optimizer Finished ***\n"));
  6729         -  if( pParse->nErr || db->mallocFailed ){
  6730         -    goto whereBeginError;
  6731         -  }
  6732         -  if( nTabList ){
  6733         -    pLevel--;
  6734         -    pWInfo->nOBSat = pLevel->plan.nOBSat;
  6735         -  }else{
  6736         -    pWInfo->nOBSat = 0;
  6737         -  }
  6738         -
  6739         -  /* If the total query only selects a single row, then the ORDER BY
  6740         -  ** clause is irrelevant.
  6741         -  */
  6742         -  if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){
  6743         -    assert( nTabList==0 || (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 );
  6744         -    pWInfo->nOBSat = pOrderBy->nExpr;
  6745         -  }
  6746         -
         5156  +#if 0  /* FIXME: Add this back in? */
  6747   5157     /* If the caller is an UPDATE or DELETE statement that is requesting
  6748   5158     ** to use a one-pass algorithm, determine if this is appropriate.
  6749   5159     ** The one-pass algorithm only works if the WHERE clause constraints
  6750   5160     ** the statement to update a single row.
  6751   5161     */
  6752   5162     assert( (wctrlFlags & WHERE_ONEPASS_DESIRED)==0 || pWInfo->nLevel==1 );
  6753   5163     if( (wctrlFlags & WHERE_ONEPASS_DESIRED)!=0 && (andFlags & WHERE_UNIQUE)!=0 ){
  6754   5164       pWInfo->okOnePass = 1;
  6755   5165       pWInfo->a[0].plan.wsFlags &= ~WHERE_IDX_ONLY;
  6756   5166     }
  6757         -
  6758         -#if 1
  6759         -  /* Scaffolding:  Check the new query plan against the old.  Report any
  6760         -  ** discrepencies */
  6761         -  for(ii=0; ii<nTabList; ii++){
  6762         -    if( pWInfo->a[ii].iFrom!=pWInfo->a[ii].pWLoop->iTab ){
  6763         -      sqlite3DebugPrintf("(QP-Mismatch)");
  6764         -      break;
  6765         -    }
  6766         -  }
  6767   5167   #endif
  6768   5168   
  6769   5169     /* Open all tables in the pTabList and any indices selected for
  6770   5170     ** searching those tables.
  6771   5171     */
  6772   5172     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  6773   5173     notReady = ~(Bitmask)0;
  6774   5174     pWInfo->nRowOut = (double)1;
  6775   5175     for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
  6776   5176       Table *pTab;     /* Table to open */
  6777   5177       int iDb;         /* Index of database containing table/index */
  6778   5178       struct SrcList_item *pTabItem;
         5179  +    WhereLoop *pLoop;
  6779   5180   
  6780   5181       pTabItem = &pTabList->a[pLevel->iFrom];
  6781   5182       pTab = pTabItem->pTab;
  6782         -    pWInfo->nRowOut *= pLevel->plan.nRow;
  6783   5183       iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
         5184  +    pLoop = pLevel->pWLoop;
  6784   5185       if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
  6785   5186         /* Do nothing */
  6786   5187       }else
  6787   5188   #ifndef SQLITE_OMIT_VIRTUALTABLE
  6788         -    if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
         5189  +    if( (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  6789   5190         const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);
  6790   5191         int iCur = pTabItem->iCursor;
  6791   5192         sqlite3VdbeAddOp4(v, OP_VOpen, iCur, 0, 0, pVTab, P4_VTAB);
  6792   5193       }else if( IsVirtual(pTab) ){
  6793   5194         /* noop */
  6794   5195       }else
  6795   5196   #endif
  6796         -    if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
         5197  +    if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
  6797   5198            && (wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0 ){
  6798   5199         int op = pWInfo->okOnePass ? OP_OpenWrite : OP_OpenRead;
  6799   5200         sqlite3OpenTable(pParse, pTabItem->iCursor, iDb, pTab, op);
  6800   5201         testcase( pTab->nCol==BMS-1 );
  6801   5202         testcase( pTab->nCol==BMS );
  6802   5203         if( !pWInfo->okOnePass && pTab->nCol<BMS ){
  6803   5204           Bitmask b = pTabItem->colUsed;
................................................................................
  6807   5208                               SQLITE_INT_TO_PTR(n), P4_INT32);
  6808   5209           assert( n<=pTab->nCol );
  6809   5210         }
  6810   5211       }else{
  6811   5212         sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName);
  6812   5213       }
  6813   5214   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  6814         -    if( (pLevel->plan.wsFlags & WHERE_TEMP_INDEX)!=0 ){
         5215  +    if( (pLoop->wsFlags & WHERE_TEMP_INDEX)!=0 ){
  6815   5216         constructAutomaticIndex(pParse, sWBI.pWC, pTabItem, notReady, pLevel);
  6816   5217       }else
  6817   5218   #endif
  6818         -    if( (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 ){
  6819         -      Index *pIx = pLevel->plan.u.pIdx;
         5219  +    if( pLoop->u.btree.pIndex!=0 ){
         5220  +      Index *pIx = pLoop->u.btree.pIndex;
  6820   5221         KeyInfo *pKey = sqlite3IndexKeyinfo(pParse, pIx);
  6821         -      int iIndexCur = pLevel->iIdxCur;
         5222  +      /* FIXME:  Might need to be the iIdxCur parameter.  As an optimization
         5223  +      ** use pTabItem->iCursor if WHERE_IDX_ONLY */
         5224  +      int iIndexCur = pLevel->iIdxCur = pParse->nTab++;
  6822   5225         assert( pIx->pSchema==pTab->pSchema );
  6823   5226         assert( iIndexCur>=0 );
  6824   5227         sqlite3VdbeAddOp4(v, OP_OpenRead, iIndexCur, pIx->tnum, iDb,
  6825   5228                           (char*)pKey, P4_KEYINFO_HANDOFF);
  6826   5229         VdbeComment((v, "%s", pIx->zName));
  6827   5230       }
  6828   5231       sqlite3CodeVerifySchema(pParse, iDb);
................................................................................
  6839   5242     for(ii=0; ii<nTabList; ii++){
  6840   5243       pLevel = &pWInfo->a[ii];
  6841   5244       explainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags);
  6842   5245       notReady = codeOneLoopStart(pWInfo, ii, wctrlFlags, notReady);
  6843   5246       pWInfo->iContinue = pLevel->addrCont;
  6844   5247     }
  6845   5248   
  6846         -#ifdef SQLITE_TEST  /* For testing and debugging use only */
         5249  +#if defined(SQLITE_TEST) && 0  /* For testing and debugging use only */
  6847   5250     /* Record in the query plan information about the current table
  6848   5251     ** and the index used to access it (if any).  If the table itself
  6849   5252     ** is not used, its name is just '{}'.  If no index is used
  6850   5253     ** the index is listed as "{}".  If the primary key is used the
  6851   5254     ** index name is '*'.
  6852   5255     */
  6853   5256     for(ii=0; ii<nTabList; ii++){
................................................................................
  6915   5318   ** sqlite3WhereBegin() for additional information.
  6916   5319   */
  6917   5320   void sqlite3WhereEnd(WhereInfo *pWInfo){
  6918   5321     Parse *pParse = pWInfo->pParse;
  6919   5322     Vdbe *v = pParse->pVdbe;
  6920   5323     int i;
  6921   5324     WhereLevel *pLevel;
         5325  +  WhereLoop *pLoop;
  6922   5326     SrcList *pTabList = pWInfo->pTabList;
  6923   5327     sqlite3 *db = pParse->db;
  6924   5328   
  6925   5329     /* Generate loop termination code.
  6926   5330     */
  6927   5331     sqlite3ExprCacheClear(pParse);
  6928   5332     for(i=pWInfo->nLevel-1; i>=0; i--){
  6929   5333       pLevel = &pWInfo->a[i];
         5334  +    pLoop = pLevel->pWLoop;
  6930   5335       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  6931   5336       if( pLevel->op!=OP_Noop ){
  6932   5337         sqlite3VdbeAddOp2(v, pLevel->op, pLevel->p1, pLevel->p2);
  6933   5338         sqlite3VdbeChangeP5(v, pLevel->p5);
  6934   5339       }
  6935         -    if( pLevel->plan.wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
         5340  +    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  6936   5341         struct InLoop *pIn;
  6937   5342         int j;
  6938   5343         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  6939   5344         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  6940   5345           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);
  6941   5346           sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
  6942   5347           sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
................................................................................
  6943   5348         }
  6944   5349         sqlite3DbFree(db, pLevel->u.in.aInLoop);
  6945   5350       }
  6946   5351       sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
  6947   5352       if( pLevel->iLeftJoin ){
  6948   5353         int addr;
  6949   5354         addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
  6950         -      assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
  6951         -           || (pLevel->plan.wsFlags & WHERE_INDEXED)!=0 );
  6952         -      if( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0 ){
         5355  +      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
         5356  +           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
         5357  +      if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
  6953   5358           sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);
  6954   5359         }
  6955   5360         if( pLevel->iIdxCur>=0 ){
  6956   5361           sqlite3VdbeAddOp1(v, OP_NullRow, pLevel->iIdxCur);
  6957   5362         }
  6958   5363         if( pLevel->op==OP_Return ){
  6959   5364           sqlite3VdbeAddOp2(v, OP_Gosub, pLevel->p1, pLevel->addrFirst);
................................................................................
  6973   5378     */
  6974   5379     assert( pWInfo->nLevel==1 || pWInfo->nLevel==pTabList->nSrc );
  6975   5380     for(i=0, pLevel=pWInfo->a; i<pWInfo->nLevel; i++, pLevel++){
  6976   5381       Index *pIdx = 0;
  6977   5382       struct SrcList_item *pTabItem = &pTabList->a[pLevel->iFrom];
  6978   5383       Table *pTab = pTabItem->pTab;
  6979   5384       assert( pTab!=0 );
         5385  +    pLoop = pLevel->pWLoop;
  6980   5386       if( (pTab->tabFlags & TF_Ephemeral)==0
  6981   5387        && pTab->pSelect==0
  6982   5388        && (pWInfo->wctrlFlags & WHERE_OMIT_OPEN_CLOSE)==0
  6983   5389       ){
  6984         -      int ws = pLevel->plan.wsFlags;
         5390  +      int ws = pLoop->wsFlags;
  6985   5391         if( !pWInfo->okOnePass && (ws & WHERE_IDX_ONLY)==0 ){
  6986   5392           sqlite3VdbeAddOp1(v, OP_Close, pTabItem->iCursor);
  6987   5393         }
  6988         -      if( (ws & WHERE_INDEXED)!=0 && (ws & WHERE_TEMP_INDEX)==0 ){
         5394  +      if( (ws & WHERE_INDEXED)!=0 && (ws & (WHERE_IPK|WHERE_TEMP_INDEX))==0 ){
  6989   5395           sqlite3VdbeAddOp1(v, OP_Close, pLevel->iIdxCur);
  6990   5396         }
  6991   5397       }
  6992   5398   
  6993   5399       /* If this scan uses an index, make code substitutions to read data
  6994   5400       ** from the index in preference to the table. Sometimes, this means
  6995   5401       ** the table need never be read from. This is a performance boost,
................................................................................
  6999   5405       ** 
  7000   5406       ** Calls to the code generator in between sqlite3WhereBegin and
  7001   5407       ** sqlite3WhereEnd will have created code that references the table
  7002   5408       ** directly.  This loop scans all that code looking for opcodes
  7003   5409       ** that reference the table and converts them into opcodes that
  7004   5410       ** reference the index.
  7005   5411       */
  7006         -    if( pLevel->plan.wsFlags & WHERE_INDEXED ){
  7007         -      pIdx = pLevel->plan.u.pIdx;
  7008         -    }else if( pLevel->plan.wsFlags & WHERE_MULTI_OR ){
         5412  +    if( pLoop->wsFlags & (WHERE_INDEXED|WHERE_IDX_ONLY) ){
         5413  +      pIdx = pLoop->u.btree.pIndex;
         5414  +    }else if( pLoop->wsFlags & WHERE_MULTI_OR ){
  7009   5415         pIdx = pLevel->u.pCovidx;
  7010   5416       }
  7011         -    if( pIdx && !db->mallocFailed){
         5417  +    if( pIdx && !db->mallocFailed ){
  7012   5418         int k, j, last;
  7013   5419         VdbeOp *pOp;
  7014   5420   
  7015   5421         pOp = sqlite3VdbeGetOp(v, pWInfo->iTop);
  7016   5422         last = sqlite3VdbeCurrentAddr(v);
  7017   5423         for(k=pWInfo->iTop; k<last; k++, pOp++){
  7018   5424           if( pOp->p1!=pLevel->iTabCur ) continue;
................................................................................
  7020   5426             for(j=0; j<pIdx->nColumn; j++){
  7021   5427               if( pOp->p2==pIdx->aiColumn[j] ){
  7022   5428                 pOp->p2 = j;
  7023   5429                 pOp->p1 = pLevel->iIdxCur;
  7024   5430                 break;
  7025   5431               }
  7026   5432             }
  7027         -          assert( (pLevel->plan.wsFlags & WHERE_IDX_ONLY)==0
  7028         -               || j<pIdx->nColumn );
         5433  +          assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 || j<pIdx->nColumn );
  7029   5434           }else if( pOp->opcode==OP_Rowid ){
  7030   5435             pOp->p1 = pLevel->iIdxCur;
  7031   5436             pOp->opcode = OP_IdxRowid;
  7032   5437           }
  7033   5438         }
  7034   5439       }
  7035   5440     }