/ Check-in [d4141ecb]
Login

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

Overview
Comment:Improved management of the space to hold WhereLoop.aLTerm[].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:d4141ecbea3abbe83525910684fbd89eb74eeb34
User & Date: drh 2013-06-06 23:02:03
Context
2013-06-06
23:44
Performance improvements. check-in: 9f8e84ab user: drh tags: nextgen-query-plan-exp
23:02
Improved management of the space to hold WhereLoop.aLTerm[]. check-in: d4141ecb user: drh tags: nextgen-query-plan-exp
19:25
Remove some commented-out code that was mistakenly left in the previous check-in. check-in: b4a5dbad user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

    41     41   typedef struct WhereAndInfo WhereAndInfo;
    42     42   typedef struct WhereLevel WhereLevel;
    43     43   typedef struct WhereLoop WhereLoop;
    44     44   typedef struct WherePath WherePath;
    45     45   typedef struct WhereTerm WhereTerm;
    46     46   typedef struct WhereLoopBuilder WhereLoopBuilder;
    47     47   typedef struct WhereScan WhereScan;
           48  +typedef float WhereCost;
    48     49   
    49     50   /*
    50     51   ** For each nested loop in a WHERE clause implementation, the WhereInfo
    51     52   ** structure contains a single instance of this structure.  This structure
    52     53   ** is intended to be private to the where.c module and should not be
    53     54   ** access or modified by other modules.
    54     55   **
................................................................................
    94     95     Bitmask prereq;       /* Bitmask of other loops that must run first */
    95     96     Bitmask maskSelf;     /* Bitmask identifying table iTab */
    96     97   #ifdef SQLITE_DEBUG
    97     98     char cId;             /* Symbolic ID of this loop for debugging use */
    98     99   #endif
    99    100     u8 iTab;              /* Position in FROM clause of table for this loop */
   100    101     u8 iSortIdx;          /* Sorting index number.  0==None */
   101         -  u16 nTerm;            /* Number of entries in aTerm[] */
          102  +  u16 nLTerm;           /* Number of entries in aLTerm[] */
          103  +  u16 nLSlot;           /* Number of slots allocated for aLTerm[] */
   102    104     u32 wsFlags;          /* WHERE_* flags describing the plan */
   103         -  double rSetup;        /* One-time setup cost (ex: create transient index) */
   104         -  double rRun;          /* Cost of running each loop */
   105         -  double nOut;          /* Estimated number of output rows */
          105  +  WhereCost rSetup;     /* One-time setup cost (ex: create transient index) */
          106  +  WhereCost rRun;       /* Cost of running each loop */
          107  +  WhereCost nOut;       /* Estimated number of output rows */
   106    108     union {
   107    109       struct {               /* Information for internal btree tables */
   108    110         int nEq;               /* Number of equality constraints */
   109    111         Index *pIndex;         /* Index used, or NULL */
   110    112       } btree;
   111    113       struct {               /* Information for virtual tables */
   112    114         int idxNum;            /* Index number */
   113    115         u8 needFree;           /* True if sqlite3_free(idxStr) is needed */
   114    116         u8 isOrdered;          /* True if satisfies ORDER BY */
   115    117         u16 omitMask;          /* Terms that may be omitted */
   116    118         char *idxStr;          /* Index identifier string */
   117    119       } vtab;
   118    120     } u;
   119         -  WhereTerm **aTerm;    /* WhereTerms used */
          121  +  WhereTerm **aLTerm;   /* WhereTerms used */
   120    122     WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */
          123  +  WhereTerm *aLTermSpace[4];  /* Initial aLTerm[] space */
   121    124   };
   122    125   
          126  +/* Forward declaration of methods */
          127  +static int whereLoopResize(sqlite3*, WhereLoop*, int);
          128  +
   123    129   /*
   124    130   ** Each instance of this object holds a sequence of WhereLoop objects
   125    131   ** that implement some or all of the entire query plan.  
   126    132   */
   127    133   struct WherePath {
   128    134     Bitmask maskLoop;     /* Bitmask of all WhereLoop objects in this path */
   129    135     Bitmask revLoop;      /* aLoop[]s that should be reversed for ORDER BY */
   130         -  double nRow;          /* Estimated number of rows generated by this path */
   131         -  double rCost;         /* Total cost of this path */
          136  +  WhereCost nRow;       /* Estimated number of rows generated by this path */
          137  +  WhereCost rCost;      /* Total cost of this path */
   132    138     u8 isOrdered;         /* True if this path satisfies ORDER BY */
   133    139     u8 isOrderedValid;    /* True if the isOrdered field is valid */
   134    140     WhereLoop **aLoop;    /* Array of WhereLoop objects implementing this path */
   135    141   };
   136    142   
   137    143   /*
   138    144   ** The query generator uses an array of instances of this structure to
................................................................................
   314    320   */
   315    321   struct WhereLoopBuilder {
   316    322     WhereInfo *pWInfo;        /* Information about this WHERE */
   317    323     WhereClause *pWC;         /* WHERE clause terms */
   318    324     ExprList *pOrderBy;       /* ORDER BY clause */
   319    325     WhereLoop *pNew;          /* Template WhereLoop */
   320    326     WhereLoop *pBest;         /* If non-NULL, store single best loop here */
   321         -  int mxTerm;               /* Maximum number of aTerm[] entries on pNew */
   322    327   };
   323    328   
   324    329   /*
   325    330   ** The WHERE clause processing routine has two halves.  The
   326    331   ** first part does the start of the WHERE loop and the second
   327    332   ** half does the tail of the WHERE loop.  An instance of
   328    333   ** this structure is returned by the first half and passed
................................................................................
   342    347     int iTop;                 /* The very beginning of the WHERE loop */
   343    348     int iContinue;            /* Jump here to continue with next record */
   344    349     int iBreak;               /* Jump here to break out of the loop */
   345    350     int nLevel;               /* Number of nested loop */
   346    351     WhereMaskSet sMaskSet;    /* Map cursor numbers to bitmasks */
   347    352     WhereClause sWC;          /* Decomposition of the WHERE clause */
   348    353     WhereLoop *pLoops;        /* List of all WhereLoop objects */
   349         -  double savedNQueryLoop;   /* pParse->nQueryLoop outside the WHERE loop */
   350         -  double nRowOut;           /* Estimated number of output rows */
          354  +  WhereCost savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */
          355  +  WhereCost nRowOut;        /* Estimated number of output rows */
   351    356     WhereLevel a[1];          /* Information about each nest loop in WHERE */
   352    357   };
   353    358   
   354    359   /*
   355    360   ** Bitmasks for the operators that indices are able to exploit.  An
   356    361   ** OR-ed combination of these values can be used when searching for
   357    362   ** terms in the where clause.
................................................................................
   395    400   #define WHERE_TEMP_INDEX   0x00004000  /* Uses an ephemeral index */
   396    401   #define WHERE_COVER_SCAN   0x00008000  /* Full scan of a covering index */
   397    402   
   398    403   /*
   399    404   ** Return the estimated number of output rows from a WHERE clause
   400    405   */
   401    406   double sqlite3WhereOutputRowCount(WhereInfo *pWInfo){
   402         -  return pWInfo->nRowOut;
          407  +  return (double)pWInfo->nRowOut;
   403    408   }
   404    409   
   405    410   /*
   406    411   ** Return one of the WHERE_DISTINCT_xxxxx values to indicate how this
   407    412   ** WHERE clause returns outputs for DISTINCT processing.
   408    413   */
   409    414   int sqlite3WhereIsDistinct(WhereInfo *pWInfo){
................................................................................
  1819   1824   /*
  1820   1825   ** Prepare a crude estimate of the logarithm of the input value.
  1821   1826   ** The results need not be exact.  This is only used for estimating
  1822   1827   ** the total cost of performing operations with O(logN) or O(NlogN)
  1823   1828   ** complexity.  Because N is just a guess, it is no great tragedy if
  1824   1829   ** logN is a little off.
  1825   1830   */
  1826         -static double estLog(double N){
  1827         -  double logN = 1;
  1828         -  double x = 10;
         1831  +static WhereCost estLog(WhereCost N){
         1832  +  WhereCost logN = 1;
         1833  +  WhereCost x = 10;
  1829   1834     while( N>x ){
  1830   1835       logN += 1;
  1831   1836       x *= 10;
  1832   1837     }
  1833   1838     return logN;
  1834   1839   }
  1835   1840   
................................................................................
  1942   1947     /* Count the number of columns that will be added to the index
  1943   1948     ** and used to match WHERE clause constraints */
  1944   1949     nColumn = 0;
  1945   1950     pTable = pSrc->pTab;
  1946   1951     pWCEnd = &pWC->a[pWC->nTerm];
  1947   1952     pLoop = pLevel->pWLoop;
  1948   1953     idxCols = 0;
  1949         -  pLoop->aTerm = sqlite3DbRealloc(pParse->db, pLoop->aTerm,
  1950         -                                  mxConstraint*sizeof(pLoop->aTerm[0]));
  1951         -  if( pLoop->aTerm==0 ) return;
  1952         -  for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nTerm<mxConstraint; pTerm++){
         1954  +  for(pTerm=pWC->a; pTerm<pWCEnd && pLoop->nLTerm<mxConstraint; pTerm++){
  1953   1955       if( termCanDriveIndex(pTerm, pSrc, notReady) ){
  1954   1956         int iCol = pTerm->u.leftColumn;
  1955   1957         Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol);
  1956   1958         testcase( iCol==BMS );
  1957   1959         testcase( iCol==BMS-1 );
  1958   1960         if( (idxCols & cMask)==0 ){
  1959         -        pLoop->aTerm[nColumn++] = pTerm;
         1961  +        if( whereLoopResize(pParse->db, pLoop, nColumn+1) ) return;
         1962  +        pLoop->aLTerm[nColumn++] = pTerm;
  1960   1963           idxCols |= cMask;
  1961   1964         }
  1962   1965       }
  1963   1966     }
  1964   1967     assert( nColumn>0 );
  1965         -  pLoop->u.btree.nEq = pLoop->nTerm = nColumn;
         1968  +  pLoop->u.btree.nEq = pLoop->nLTerm = nColumn;
  1966   1969     pLoop->wsFlags = WHERE_COLUMN_EQ | WHERE_IDX_ONLY | WHERE_INDEXED
  1967   1970                        | WHERE_TEMP_INDEX;
  1968   1971   
  1969   1972     /* Count the number of additional columns needed to create a
  1970   1973     ** covering index.  A "covering index" is an index that contains all
  1971   1974     ** columns that are needed by the query.  With a covering index, the
  1972   1975     ** original table never needs to be accessed.  Automatic indices must
................................................................................
  2114   2117     /* Allocate the sqlite3_index_info structure
  2115   2118     */
  2116   2119     pIdxInfo = sqlite3DbMallocZero(pParse->db, sizeof(*pIdxInfo)
  2117   2120                              + (sizeof(*pIdxCons) + sizeof(*pUsage))*nTerm
  2118   2121                              + sizeof(*pIdxOrderBy)*nOrderBy );
  2119   2122     if( pIdxInfo==0 ){
  2120   2123       sqlite3ErrorMsg(pParse, "out of memory");
  2121         -    /* (double)0 In case of SQLITE_OMIT_FLOATING_POINT... */
  2122   2124       return 0;
  2123   2125     }
  2124   2126   
  2125   2127     /* Initialize the structure.  The sqlite3_index_info structure contains
  2126   2128     ** many fields that are declared "const" to prevent xBestIndex from
  2127   2129     ** changing them.  We have to do some funky casting in order to
  2128   2130     ** initialize those fields.
................................................................................
  2237   2239     tRowcnt *aStat              /* OUT: stats written here */
  2238   2240   ){
  2239   2241     tRowcnt n;
  2240   2242     IndexSample *aSample;
  2241   2243     int i, eType;
  2242   2244     int isEq = 0;
  2243   2245     i64 v;
  2244         -  double r, rS;
         2246  +  WhereCost r, rS;
  2245   2247   
  2246   2248     assert( roundUp==0 || roundUp==1 );
  2247   2249     assert( pIdx->nSample>0 );
  2248   2250     if( pVal==0 ) return SQLITE_ERROR;
  2249   2251     n = pIdx->aiRowEst[0];
  2250   2252     aSample = pIdx->aSample;
  2251   2253     eType = sqlite3_value_type(pVal);
................................................................................
  2455   2457   */
  2456   2458   static int whereRangeScanEst(
  2457   2459     Parse *pParse,       /* Parsing & code generating context */
  2458   2460     Index *p,            /* The index containing the range-compared column; "x" */
  2459   2461     int nEq,             /* index into p->aCol[] of the range-compared column */
  2460   2462     WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  2461   2463     WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  2462         -  double *pRangeDiv   /* OUT: Reduce search space by this divisor */
         2464  +  WhereCost *pRangeDiv /* OUT: Reduce search space by this divisor */
  2463   2465   ){
  2464   2466     int rc = SQLITE_OK;
  2465   2467   
  2466   2468   #ifdef SQLITE_ENABLE_STAT3
  2467   2469   
  2468   2470     if( nEq==0 && p->nSample ){
  2469   2471       sqlite3_value *pRangeVal;
................................................................................
  2494   2496           iUpper = a[0];
  2495   2497           if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
  2496   2498         }
  2497   2499         sqlite3ValueFree(pRangeVal);
  2498   2500       }
  2499   2501       if( rc==SQLITE_OK ){
  2500   2502         if( iUpper<=iLower ){
  2501         -        *pRangeDiv = (double)p->aiRowEst[0];
         2503  +        *pRangeDiv = (WhereCost)p->aiRowEst[0];
  2502   2504         }else{
  2503         -        *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower);
         2505  +        *pRangeDiv = (WhereCost)p->aiRowEst[0]/(WhereCost)(iUpper - iLower);
  2504   2506         }
  2505   2507         /*WHERETRACE(("range scan regions: %u..%u  div=%g\n",
  2506   2508                     (u32)iLower, (u32)iUpper, *pRangeDiv));*/
  2507   2509         return SQLITE_OK;
  2508   2510       }
  2509   2511     }
  2510   2512   #else
  2511   2513     UNUSED_PARAMETER(pParse);
  2512   2514     UNUSED_PARAMETER(p);
  2513   2515     UNUSED_PARAMETER(nEq);
  2514   2516   #endif
  2515   2517     assert( pLower || pUpper );
  2516         -  *pRangeDiv = (double)1;
  2517         -  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= (double)4;
  2518         -  if( pUpper ) *pRangeDiv *= (double)4;
         2518  +  *pRangeDiv = (WhereCost)1;
         2519  +  if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *pRangeDiv *= (WhereCost)4;
         2520  +  if( pUpper ) *pRangeDiv *= (WhereCost)4;
  2519   2521     return rc;
  2520   2522   }
  2521   2523   
  2522   2524   #ifdef SQLITE_ENABLE_STAT3
  2523   2525   /*
  2524   2526   ** Estimate the number of rows that will be returned based on
  2525   2527   ** an equality constraint x=VALUE and where that VALUE occurs in
................................................................................
  2537   2539   ** for a UTF conversion required for comparison.  The error is stored
  2538   2540   ** in the pParse structure.
  2539   2541   */
  2540   2542   static int whereEqualScanEst(
  2541   2543     Parse *pParse,       /* Parsing & code generating context */
  2542   2544     Index *p,            /* The index whose left-most column is pTerm */
  2543   2545     Expr *pExpr,         /* Expression for VALUE in the x=VALUE constraint */
  2544         -  double *pnRow        /* Write the revised row estimate here */
         2546  +  WhereCost *pnRow     /* Write the revised row estimate here */
  2545   2547   ){
  2546   2548     sqlite3_value *pRhs = 0;  /* VALUE on right-hand side of pTerm */
  2547   2549     u8 aff;                   /* Column affinity */
  2548   2550     int rc;                   /* Subfunction return code */
  2549   2551     tRowcnt a[2];             /* Statistics */
  2550   2552   
  2551   2553     assert( p->aSample!=0 );
................................................................................
  2586   2588   ** for a UTF conversion required for comparison.  The error is stored
  2587   2589   ** in the pParse structure.
  2588   2590   */
  2589   2591   static int whereInScanEst(
  2590   2592     Parse *pParse,       /* Parsing & code generating context */
  2591   2593     Index *p,            /* The index whose left-most column is pTerm */
  2592   2594     ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  2593         -  double *pnRow        /* Write the revised row estimate here */
         2595  +  WhereCost *pnRow     /* Write the revised row estimate here */
  2594   2596   ){
  2595   2597     int rc = SQLITE_OK;         /* Subfunction return code */
  2596         -  double nEst;                /* Number of rows for a single term */
  2597         -  double nRowEst = (double)0; /* New estimate of the number of rows */
         2598  +  WhereCost nEst;                /* Number of rows for a single term */
         2599  +  WhereCost nRowEst = (WhereCost)0; /* New estimate of the number of rows */
  2598   2600     int i;                      /* Loop counter */
  2599   2601   
  2600   2602     assert( p->aSample!=0 );
  2601   2603     for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
  2602   2604       nEst = p->aiRowEst[0];
  2603   2605       rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst);
  2604   2606       nRowEst += nEst;
................................................................................
  2854   2856     }
  2855   2857   
  2856   2858     /* Evaluate the equality constraints
  2857   2859     */
  2858   2860     assert( pIdx->nColumn>=nEq );
  2859   2861     for(j=0; j<nEq; j++){
  2860   2862       int r1;
  2861         -    pTerm = pLoop->aTerm[j];
         2863  +    pTerm = pLoop->aLTerm[j];
  2862   2864       assert( pTerm!=0 );
  2863   2865       /* The following true for indices with redundant columns. 
  2864   2866       ** Ex: CREATE INDEX i1 ON t1(a,b,a); SELECT * FROM t1 WHERE a=0 AND b=0; */
  2865   2867       testcase( (pTerm->wtFlags & TERM_CODED)!=0 );
  2866   2868       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  2867   2869       r1 = codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, regBase+j);
  2868   2870       if( r1!=regBase+j ){
................................................................................
  3128   3130   #ifndef SQLITE_OMIT_VIRTUALTABLE
  3129   3131     if(  (pLoop->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  3130   3132       /* Case 1:  The table is a virtual-table.  Use the VFilter and VNext
  3131   3133       **          to access the data.
  3132   3134       */
  3133   3135       int iReg;   /* P3 Value for OP_VFilter */
  3134   3136       int addrNotFound;
  3135         -    int nConstraint = pLoop->nTerm;
         3137  +    int nConstraint = pLoop->nLTerm;
  3136   3138   
  3137   3139       sqlite3ExprCachePush(pParse);
  3138   3140       iReg = sqlite3GetTempRange(pParse, nConstraint+2);
  3139   3141       addrNotFound = pLevel->addrBrk;
  3140   3142       for(j=0; j<nConstraint; j++){
  3141   3143         int iTarget = iReg+j+2;
  3142         -      pTerm = pLoop->aTerm[j];
         3144  +      pTerm = pLoop->aLTerm[j];
  3143   3145         if( pTerm->eOperator & WO_IN ){
  3144   3146           codeEqualityTerm(pParse, pTerm, pLevel, j, bRev, iTarget);
  3145   3147           addrNotFound = pLevel->addrNxt;
  3146   3148         }else{
  3147   3149           sqlite3ExprCode(pParse, pTerm->pExpr->pRight, iTarget);
  3148   3150         }
  3149   3151       }
................................................................................
  3151   3153       sqlite3VdbeAddOp2(v, OP_Integer, nConstraint, iReg+1);
  3152   3154       sqlite3VdbeAddOp4(v, OP_VFilter, iCur, addrNotFound, iReg,
  3153   3155                         pLoop->u.vtab.idxStr,
  3154   3156                         pLoop->u.vtab.needFree ? P4_MPRINTF : P4_STATIC);
  3155   3157       pLoop->u.vtab.needFree = 0;
  3156   3158       for(j=0; j<nConstraint && j<16; j++){
  3157   3159         if( (pLoop->u.vtab.omitMask>>j)&1 ){
  3158         -        disableTerm(pLevel, pLoop->aTerm[j]);
         3160  +        disableTerm(pLevel, pLoop->aLTerm[j]);
  3159   3161         }
  3160   3162       }
  3161   3163       pLevel->op = OP_VNext;
  3162   3164       pLevel->p1 = iCur;
  3163   3165       pLevel->p2 = sqlite3VdbeCurrentAddr(v);
  3164   3166       sqlite3ReleaseTempRange(pParse, iReg, nConstraint+2);
  3165   3167       sqlite3ExprCachePop(pParse, 1);
................................................................................
  3172   3174       /* Case 2:  We can directly reference a single row using an
  3173   3175       **          equality comparison against the ROWID field.  Or
  3174   3176       **          we reference multiple rows using a "rowid IN (...)"
  3175   3177       **          construct.
  3176   3178       */
  3177   3179       assert( pLoop->u.btree.nEq==1 );
  3178   3180       iReleaseReg = sqlite3GetTempReg(pParse);
  3179         -    pTerm = pLoop->aTerm[0];
         3181  +    pTerm = pLoop->aLTerm[0];
  3180   3182       assert( pTerm!=0 );
  3181   3183       assert( pTerm->pExpr!=0 );
  3182   3184       assert( omitTable==0 );
  3183   3185       testcase( pTerm->wtFlags & TERM_VIRTUAL ); /* EV: R-30575-11662 */
  3184   3186       iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg);
  3185   3187       addrNxt = pLevel->addrNxt;
  3186   3188       sqlite3VdbeAddOp2(v, OP_MustBeInt, iRowidReg, addrNxt);
................................................................................
  3198   3200       int start;
  3199   3201       int memEndValue = 0;
  3200   3202       WhereTerm *pStart, *pEnd;
  3201   3203   
  3202   3204       assert( omitTable==0 );
  3203   3205       j = 0;
  3204   3206       pStart = pEnd = 0;
  3205         -    if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aTerm[j++];
  3206         -    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aTerm[j++];
         3207  +    if( pLoop->wsFlags & WHERE_BTM_LIMIT ) pStart = pLoop->aLTerm[j++];
         3208  +    if( pLoop->wsFlags & WHERE_TOP_LIMIT ) pEnd = pLoop->aLTerm[j++];
  3207   3209       if( bRev ){
  3208   3210         pTerm = pStart;
  3209   3211         pStart = pEnd;
  3210   3212         pEnd = pTerm;
  3211   3213       }
  3212   3214       if( pStart ){
  3213   3215         Expr *pX;             /* The expression that defines the start bound */
................................................................................
  3357   3359       }
  3358   3360   
  3359   3361       /* Find any inequality constraint terms for the start and end 
  3360   3362       ** of the range. 
  3361   3363       */
  3362   3364       j = nEq;
  3363   3365       if( pLoop->wsFlags & WHERE_BTM_LIMIT ){
  3364         -      pRangeStart = pLoop->aTerm[j++];
         3366  +      pRangeStart = pLoop->aLTerm[j++];
  3365   3367         nExtraReg = 1;
  3366   3368       }
  3367   3369       if( pLoop->wsFlags & WHERE_TOP_LIMIT ){
  3368         -      pRangeEnd = pLoop->aTerm[j++];
         3370  +      pRangeEnd = pLoop->aLTerm[j++];
  3369   3371         nExtraReg = 1;
  3370   3372       }
  3371   3373   
  3372   3374       /* Generate code to evaluate all constraint terms using == or IN
  3373   3375       ** and store the values of those terms in an array of registers
  3374   3376       ** starting at regBase.
  3375   3377       */
................................................................................
  3570   3572       int regRowid = 0;                         /* Register holding rowid */
  3571   3573       int iLoopBody = sqlite3VdbeMakeLabel(v);  /* Start of loop body */
  3572   3574       int iRetInit;                             /* Address of regReturn init */
  3573   3575       int untestedTerms = 0;             /* Some terms not completely tested */
  3574   3576       int ii;                            /* Loop counter */
  3575   3577       Expr *pAndExpr = 0;                /* An ".. AND (...)" expression */
  3576   3578      
  3577         -    pTerm = pLoop->aTerm[0];
         3579  +    pTerm = pLoop->aLTerm[0];
  3578   3580       assert( pTerm!=0 );
  3579   3581       assert( pTerm->eOperator & WO_OR );
  3580   3582       assert( (pTerm->wtFlags & TERM_ORINFO)!=0 );
  3581   3583       pOrWc = &pTerm->u.pOrInfo->wc;
  3582   3584       pLevel->op = OP_Return;
  3583   3585       pLevel->p1 = regReturn;
  3584   3586   
................................................................................
  3856   3858                   p->u.vtab.idxNum, p->u.vtab.idxStr, p->u.vtab.omitMask);
  3857   3859       }else{
  3858   3860         z = sqlite3_mprintf("(%d,%x)", p->u.vtab.idxNum, p->u.vtab.omitMask);
  3859   3861       }
  3860   3862       sqlite3DebugPrintf(" %-15s", z);
  3861   3863       sqlite3_free(z);
  3862   3864     }
  3863         -  sqlite3DebugPrintf(" fg %05x N %d", p->wsFlags, p->nTerm);
         3865  +  sqlite3DebugPrintf(" fg %05x N %d", p->wsFlags, p->nLTerm);
  3864   3866     sqlite3DebugPrintf(" cost %.2g,%.2g,%.2g\n",
  3865   3867                        p->prereq, p->rSetup, p->rRun, p->nOut);
  3866   3868   }
  3867   3869   #endif
  3868   3870   
  3869   3871   /*
  3870         -** Deallocate internal memory used by a WhereLoop object
         3872  +** Convert bulk memory into a valid WhereLoop that can be passed
         3873  +** to whereLoopClear harmlessly.
  3871   3874   */
  3872         -static void whereLoopClear(sqlite3 *db, WhereLoop *p){
  3873         -  sqlite3DbFree(db, p->aTerm);
  3874         -  p->aTerm = 0;
  3875         -  p->nTerm = 0;
         3875  +static void whereLoopInit(WhereLoop *p){
         3876  +  p->aLTerm = p->aLTermSpace;
         3877  +  p->nLTerm = 0;
         3878  +  p->nLSlot = ArraySize(p->aLTermSpace);
         3879  +  p->wsFlags = 0;
         3880  +}
         3881  +
         3882  +/*
         3883  +** Clear the WhereLoop.u union.  Leave WhereLoop.pLTerm intact.
         3884  +*/
         3885  +static void whereLoopClearUnion(sqlite3 *db, WhereLoop *p){
  3876   3886     if( (p->wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  3877   3887       if( p->u.vtab.needFree ) sqlite3_free(p->u.vtab.idxStr);
  3878   3888       p->u.vtab.needFree = 0;
  3879   3889       p->u.vtab.idxStr = 0;
  3880   3890     }else if( (p->wsFlags & WHERE_TEMP_INDEX)!=0 && p->u.btree.pIndex!=0 ){
  3881   3891       sqlite3DbFree(db, p->u.btree.pIndex->zColAff);
  3882   3892       sqlite3DbFree(db, p->u.btree.pIndex);
  3883   3893       p->u.btree.pIndex = 0;
  3884   3894     }
  3885   3895   }
  3886   3896   
         3897  +
         3898  +/*
         3899  +** Deallocate internal memory used by a WhereLoop object
         3900  +*/
         3901  +static void whereLoopClear(sqlite3 *db, WhereLoop *p){
         3902  +  if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);
         3903  +  whereLoopClearUnion(db, p);
         3904  +  whereLoopInit(p);
         3905  +}
         3906  +
         3907  +/*
         3908  +** Increase the memory allocation for pLoop->aLTerm[] to be at least n.
         3909  +*/
         3910  +static int whereLoopResize(sqlite3 *db, WhereLoop *p, int n){
         3911  +  WhereTerm **paNew;
         3912  +  if( p->nLSlot>=n ) return SQLITE_OK;
         3913  +  n = (n+7)&~7;
         3914  +  paNew = sqlite3DbMallocRaw(db, sizeof(p->aLTerm[0])*n);
         3915  +  if( paNew==0 ) return SQLITE_NOMEM;
         3916  +  memcpy(paNew, p->aLTerm, sizeof(p->aLTerm[0])*p->nLSlot);
         3917  +  if( p->aLTerm!=p->aLTermSpace ) sqlite3DbFree(db, p->aLTerm);
         3918  +  p->aLTerm = paNew;
         3919  +  p->nLSlot = n;
         3920  +  return SQLITE_OK;
         3921  +}
         3922  +
         3923  +/*
         3924  +** Transfer content from the second pLoop into the first.
         3925  +*/
         3926  +static int whereLoopXfer(sqlite3 *db, WhereLoop *pTo, WhereLoop *pFrom){
         3927  +  if( whereLoopResize(db, pTo, pFrom->nLTerm) ) return SQLITE_NOMEM;
         3928  +  whereLoopClearUnion(db, pTo);
         3929  +  pTo->prereq = pFrom->prereq;
         3930  +  pTo->maskSelf = pFrom->maskSelf;
         3931  +  pTo->iTab = pFrom->iTab;
         3932  +  pTo->iSortIdx = pFrom->iSortIdx;
         3933  +  pTo->nLTerm = pFrom->nLTerm;
         3934  +  pTo->rSetup = pFrom->rSetup;
         3935  +  pTo->rRun = pFrom->rRun;
         3936  +  pTo->nOut = pFrom->nOut;
         3937  +  if( pTo->nLTerm ){
         3938  +    memcpy(pTo->aLTerm, pFrom->aLTerm, pTo->nLTerm*sizeof(pTo->aLTerm[0]));
         3939  +  }
         3940  +  pTo->wsFlags = pFrom->wsFlags;
         3941  +  pTo->u = pFrom->u;
         3942  +  if( pFrom->wsFlags & WHERE_VIRTUALTABLE ){
         3943  +    pFrom->u.vtab.needFree = 0;
         3944  +  }else if( (pFrom->wsFlags & WHERE_TEMP_INDEX)!=0 && pFrom->u.btree.pIndex!=0 ){
         3945  +    sqlite3DbFree(db, pFrom->u.btree.pIndex->zColAff);
         3946  +    sqlite3DbFree(db, pFrom->u.btree.pIndex);
         3947  +    pFrom->u.btree.pIndex = 0;
         3948  +  }
         3949  +  return SQLITE_OK;
         3950  +}
         3951  +
  3887   3952   /*
  3888   3953   ** Delete a WhereLoop object
  3889   3954   */
  3890   3955   static void whereLoopDelete(sqlite3 *db, WhereLoop *p){
  3891   3956     whereLoopClear(db, p);
  3892   3957     sqlite3DbFree(db, p);
  3893   3958   }
................................................................................
  3930   3995   **    (2)  They have the same iSortIdx.
  3931   3996   **    (3)  The template has same or fewer dependencies than the current loop
  3932   3997   **    (4)  The template has the same or lower cost than the current loop
  3933   3998   **    (5)  The template uses more terms of the same index but has no additional
  3934   3999   **         dependencies          
  3935   4000   */
  3936   4001   static int whereLoopInsert(WhereLoopBuilder *pBuilder, WhereLoop *pTemplate){
  3937         -  WhereLoop **ppPrev, *p, *pNext = 0, *pToFree = 0;
  3938         -  WhereTerm **paTerm = 0;
         4002  +  WhereLoop **ppPrev, *p, *pNext = 0;
  3939   4003     WhereInfo *pWInfo = pBuilder->pWInfo;
  3940   4004     sqlite3 *db = pWInfo->pParse->db;
  3941   4005   
  3942   4006     /* If pBuilder->pBest is defined, then only keep track of the single
  3943   4007     ** best WhereLoop.  pBuilder->pBest->maskSelf==0 indicates that no
  3944   4008     ** prior WhereLoops have been evaluated and that the current pTemplate
  3945   4009     ** is therefore the first and hence the best and should be retained.
  3946   4010     */
  3947   4011     if( (p = pBuilder->pBest)!=0 ){
  3948   4012       if( p->maskSelf!=0 ){
  3949         -      if( p->rRun+p->rSetup < pTemplate->rRun+pTemplate->rSetup ){
         4013  +      WhereCost rCost = p->rRun + p->rSetup;
         4014  +      WhereCost rTemplate = pTemplate->rRun + pTemplate->rSetup;
         4015  +      if( rCost < rTemplate ){
  3950   4016           goto whereLoopInsert_noop;
  3951   4017         }
  3952         -      if( p->rRun+p->rSetup == pTemplate->rRun+pTemplate->rSetup
  3953         -       && p->prereq <= pTemplate->prereq ){
         4018  +      if( rCost == rTemplate && p->prereq <= pTemplate->prereq ){
  3954   4019           goto whereLoopInsert_noop;
  3955   4020         }
  3956   4021       }
  3957         -    *p = *pTemplate;
  3958         -    p->aTerm = 0;
  3959         -    p->u.vtab.needFree = 0;
         4022  +    whereLoopXfer(db, p, pTemplate);
  3960   4023   #if WHERETRACE_ENABLED
  3961   4024       if( sqlite3WhereTrace & 0x8 ){
  3962   4025         sqlite3DebugPrintf("ins-best: ");
  3963   4026         whereLoopPrint(pTemplate, pWInfo->pTabList);
  3964   4027       }
  3965   4028   #endif
  3966   4029       return SQLITE_OK;
................................................................................
  3972   4035     for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){
  3973   4036       if( p->iTab!=pTemplate->iTab || p->iSortIdx!=pTemplate->iSortIdx ) continue;
  3974   4037       if( (p->prereq & pTemplate->prereq)==p->prereq
  3975   4038        && p->rSetup<=pTemplate->rSetup
  3976   4039        && p->rRun<=pTemplate->rRun
  3977   4040       ){
  3978   4041         /* p is equal or better than pTemplate */
  3979         -      if( p->nTerm<pTemplate->nTerm
         4042  +      if( p->nLTerm<pTemplate->nLTerm
  3980   4043          && (p->wsFlags & WHERE_INDEXED)!=0
  3981   4044          && (pTemplate->wsFlags & WHERE_INDEXED)!=0
  3982   4045          && p->u.btree.pIndex==pTemplate->u.btree.pIndex
  3983   4046          && p->prereq==pTemplate->prereq
  3984   4047         ){
  3985   4048           /* Overwrite an existing WhereLoop with an similar one that uses
  3986   4049           ** more terms of the index */
................................................................................
  4015   4078         whereLoopPrint(p, pWInfo->pTabList);
  4016   4079       }
  4017   4080       sqlite3DebugPrintf("ins-new:  ");
  4018   4081       whereLoopPrint(pTemplate, pWInfo->pTabList);
  4019   4082     }
  4020   4083   #endif
  4021   4084     if( p==0 ){
  4022         -    p = pToFree = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
         4085  +    p = sqlite3DbMallocRaw(db, sizeof(WhereLoop));
  4023   4086       if( p==0 ) return SQLITE_NOMEM;
         4087  +    whereLoopInit(p);
  4024   4088     }
  4025         -  if( pTemplate->nTerm ){
  4026         -    paTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0]));
  4027         -    if( paTerm==0 ){
  4028         -      sqlite3DbFree(db, pToFree);
  4029         -      return SQLITE_NOMEM;
  4030         -    }
  4031         -  }
  4032         -  *p = *pTemplate;
         4089  +  whereLoopXfer(db, p, pTemplate);
  4033   4090     p->pNextLoop = pNext;
  4034   4091     *ppPrev = p;
  4035         -  p->aTerm = paTerm;
  4036         -  if( p->nTerm ){
  4037         -    memcpy(p->aTerm, pTemplate->aTerm, p->nTerm*sizeof(p->aTerm[0]));
  4038         -  }
  4039   4092     if( (p->wsFlags & WHERE_VIRTUALTABLE)==0 ){
  4040   4093       Index *pIndex = p->u.btree.pIndex;
  4041   4094       if( pIndex && pIndex->tnum==0 ){
  4042   4095         p->u.btree.pIndex = 0;
  4043   4096       }
  4044         -  }else{
  4045         -    pTemplate->u.vtab.needFree = 0;
  4046   4097     }
  4047   4098     return SQLITE_OK;
  4048   4099   
  4049   4100     /* Jump here if the insert is a no-op */
  4050   4101   whereLoopInsert_noop:
  4051   4102   #if WHERETRACE_ENABLED
  4052   4103     if( sqlite3WhereTrace & 0x8 ){
................................................................................
  4073   4124     WhereInfo *pWInfo = pBuilder->pWInfo;  /* WHERE analyse context */
  4074   4125     Parse *pParse = pWInfo->pParse;        /* Parsing context */
  4075   4126     sqlite3 *db = pParse->db;       /* Database connection malloc context */
  4076   4127     WhereLoop *pNew;                /* Template WhereLoop under construction */
  4077   4128     WhereTerm *pTerm;               /* A WhereTerm under consideration */
  4078   4129     int opMask;                     /* Valid operators for constraints */
  4079   4130     WhereScan scan;                 /* Iterator for WHERE terms */
  4080         -  WhereLoop savedLoop;            /* Saved original content of pNew[] */
         4131  +  Bitmask saved_prereq;           /* Original value of pNew->prereq */
         4132  +  u16 saved_nLTerm;               /* Original value of pNew->nLTerm */
         4133  +  int saved_nEq;                  /* Original value of pNew->u.btree.nEq */
         4134  +  u32 saved_wsFlags;              /* Original value of pNew->wsFlags */
         4135  +  WhereCost saved_nOut;           /* Original value of pNew->nOut */
  4081   4136     int iCol;                       /* Index of the column in the table */
  4082   4137     int rc = SQLITE_OK;             /* Return code */
  4083   4138     tRowcnt iRowEst;                /* Estimated index selectivity */
  4084         -  double rLogSize;                /* Logarithm of table size */
         4139  +  WhereCost rLogSize;             /* Logarithm of table size */
  4085   4140     WhereTerm *pTop, *pBtm;         /* Top and bottom range constraints */
  4086   4141   
  4087   4142     pNew = pBuilder->pNew;
  4088   4143     if( db->mallocFailed ) return SQLITE_NOMEM;
  4089   4144   
  4090   4145     assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 );
  4091   4146     assert( pNew->u.btree.nEq<=pProbe->nColumn );
................................................................................
  4104   4159       iRowEst = pProbe->aiRowEst[pNew->u.btree.nEq+1];
  4105   4160     }else{
  4106   4161       iCol = -1;
  4107   4162       iRowEst = 1;
  4108   4163     }
  4109   4164     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  4110   4165                           opMask, pProbe);
  4111         -  savedLoop = *pNew;
  4112         -  pNew->rSetup = (double)0;
         4166  +  saved_nEq = pNew->u.btree.nEq;
         4167  +  saved_nLTerm = pNew->nLTerm;
         4168  +  saved_wsFlags = pNew->wsFlags;
         4169  +  saved_prereq = pNew->prereq;
         4170  +  saved_nOut = pNew->nOut;
         4171  +  pNew->rSetup = (WhereCost)0;
  4113   4172     rLogSize = estLog(pProbe->aiRowEst[0]);
  4114   4173     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  4115   4174       int nIn = 1;
  4116   4175       if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4117         -    pNew->wsFlags = savedLoop.wsFlags;
  4118         -    pNew->u.btree.nEq = savedLoop.u.btree.nEq;
  4119         -    pNew->nTerm = savedLoop.nTerm;
  4120         -    if( pNew->nTerm>=pBuilder->mxTerm ) break; /* Repeated column in index */
  4121         -    pNew->aTerm[pNew->nTerm++] = pTerm;
  4122         -    pNew->prereq = (savedLoop.prereq | pTerm->prereqRight) & ~pNew->maskSelf;
         4176  +    pNew->wsFlags = saved_wsFlags;
         4177  +    pNew->u.btree.nEq = saved_nEq;
         4178  +    pNew->nLTerm = saved_nLTerm;
         4179  +    if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */
         4180  +    pNew->aLTerm[pNew->nLTerm++] = pTerm;
         4181  +    pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf;
  4123   4182       pNew->rRun = rLogSize;
  4124   4183       if( pTerm->eOperator & WO_IN ){
  4125   4184         Expr *pExpr = pTerm->pExpr;
  4126   4185         pNew->wsFlags |= WHERE_COLUMN_IN;
  4127   4186         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  4128   4187           /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  4129   4188           nIn = 25;
  4130   4189         }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  4131   4190           /* "x IN (value, value, ...)" */
  4132   4191           nIn = pExpr->x.pList->nExpr;
  4133   4192         }
  4134   4193         pNew->rRun *= nIn;
  4135   4194         pNew->u.btree.nEq++;
  4136         -      pNew->nOut = (double)iRowEst * nInMul * nIn;
         4195  +      pNew->nOut = (WhereCost)iRowEst * nInMul * nIn;
  4137   4196       }else if( pTerm->eOperator & (WO_EQ) ){
  4138   4197         assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
  4139   4198                     || nInMul==1 );
  4140   4199         pNew->wsFlags |= WHERE_COLUMN_EQ;
  4141   4200         if( iCol<0  
  4142   4201          || (pProbe->onError!=OE_None && nInMul==1
  4143   4202              && pNew->u.btree.nEq==pProbe->nColumn-1)
  4144   4203         ){
  4145   4204           testcase( pNew->wsFlags & WHERE_COLUMN_IN );
  4146   4205           pNew->wsFlags |= WHERE_ONEROW;
  4147   4206         }
  4148   4207         pNew->u.btree.nEq++;
  4149         -      pNew->nOut = (double)iRowEst * nInMul;
         4208  +      pNew->nOut = (WhereCost)iRowEst * nInMul;
  4150   4209       }else if( pTerm->eOperator & (WO_ISNULL) ){
  4151   4210         pNew->wsFlags |= WHERE_COLUMN_NULL;
  4152   4211         pNew->u.btree.nEq++;
  4153   4212         nIn = 2;  /* Assume IS NULL matches two rows */
  4154         -      pNew->nOut = (double)iRowEst * nInMul * nIn;
         4213  +      pNew->nOut = (WhereCost)iRowEst * nInMul * nIn;
  4155   4214       }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
  4156   4215         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
  4157   4216         pBtm = pTerm;
  4158   4217         pTop = 0;
  4159   4218       }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
  4160   4219         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
  4161   4220         pTop = pTerm;
  4162   4221         pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ?
  4163         -                     pNew->aTerm[pNew->nTerm-2] : 0;
         4222  +                     pNew->aLTerm[pNew->nLTerm-2] : 0;
  4164   4223       }
  4165   4224       if( pNew->wsFlags & WHERE_COLUMN_RANGE ){
  4166   4225         /* Adjust nOut and rRun for STAT3 range values */
  4167         -      double rDiv;
         4226  +      WhereCost rDiv;
  4168   4227         whereRangeScanEst(pParse, pProbe, pNew->u.btree.nEq,
  4169   4228                           pBtm, pTop, &rDiv);
  4170         -      pNew->nOut = savedLoop.nOut/rDiv;
         4229  +      pNew->nOut = saved_nOut/rDiv;
  4171   4230       }
  4172   4231   #ifdef SQLITE_ENABLE_STAT3
  4173   4232       if( pNew->u.btree.nEq==1 && pProbe->nSample ){
  4174   4233         if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
  4175   4234           rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight,
  4176   4235                                  &pNew->nOut);
  4177   4236         }else if( (pTerm->eOperator & WO_IN)
................................................................................
  4194   4253       if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
  4195   4254        && pNew->u.btree.nEq<=pProbe->nColumn
  4196   4255        && pProbe->zName!=0
  4197   4256       ){
  4198   4257         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul*nIn);
  4199   4258       }
  4200   4259     }
  4201         -  *pNew = savedLoop;
         4260  +  pNew->prereq = saved_prereq;
         4261  +  pNew->u.btree.nEq = saved_nEq;
         4262  +  pNew->wsFlags = saved_wsFlags;
         4263  +  pNew->nOut = saved_nOut;
         4264  +  pNew->nLTerm = saved_nLTerm;
  4202   4265     return rc;
  4203   4266   }
  4204   4267   
  4205   4268   /*
  4206   4269   ** Return True if it is possible that pIndex might be useful in
  4207   4270   ** implementing the ORDER BY clause in pBuilder.
  4208   4271   **
................................................................................
  4248   4311     int aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  4249   4312     SrcList *pTabList;          /* The FROM clause */
  4250   4313     struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  4251   4314     WhereLoop *pNew;            /* Template WhereLoop object */
  4252   4315     int rc = SQLITE_OK;         /* Return code */
  4253   4316     int iSortIdx = 1;           /* Index number */
  4254   4317     int b;                      /* A boolean value */
  4255         -  double rSize;               /* number of rows in the table */
  4256         -  double rLogSize;            /* Logarithm of the number of rows in the table */
         4318  +  WhereCost rSize;               /* number of rows in the table */
         4319  +  WhereCost rLogSize;            /* Logarithm of the number of rows in the table */
  4257   4320     
  4258   4321     pNew = pBuilder->pNew;
  4259   4322     pWInfo = pBuilder->pWInfo;
  4260   4323     pTabList = pWInfo->pTabList;
  4261   4324     pSrc = pTabList->a + pNew->iTab;
  4262   4325     assert( !IsVirtual(pSrc->pTab) );
  4263   4326   
................................................................................
  4282   4345       if( pSrc->notIndexed==0 ){
  4283   4346         /* The real indices of the table are only considered if the
  4284   4347         ** NOT INDEXED qualifier is omitted from the FROM clause */
  4285   4348         sPk.pNext = pFirst;
  4286   4349       }
  4287   4350       pProbe = &sPk;
  4288   4351     }
  4289         -  rSize = (double)pSrc->pTab->nRowEst;
         4352  +  rSize = (WhereCost)pSrc->pTab->nRowEst;
  4290   4353     rLogSize = estLog(rSize);
  4291   4354   
  4292   4355     /* Automatic indexes */
  4293   4356     if( !pBuilder->pBest
  4294   4357      && pTabList->nSrc>1
  4295   4358      && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 
  4296   4359      && !pSrc->viaCoroutine
................................................................................
  4302   4365       WhereTerm *pTerm;
  4303   4366       WhereTerm *pWCEnd = pWC->a + pWC->nTerm;
  4304   4367       for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
  4305   4368         if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4306   4369         if( termCanDriveIndex(pTerm, pSrc, 0) ){
  4307   4370           pNew->u.btree.nEq = 1;
  4308   4371           pNew->u.btree.pIndex = 0;
  4309         -        pNew->nTerm = 1;
  4310         -        pNew->aTerm[0] = pTerm;
         4372  +        pNew->nLTerm = 1;
         4373  +        pNew->aLTerm[0] = pTerm;
  4311   4374           pNew->rSetup = 20*rLogSize*pSrc->pTab->nRowEst;
  4312         -        pNew->nOut = (double)10;
         4375  +        pNew->nOut = (WhereCost)10;
  4313   4376           pNew->rRun = rLogSize + pNew->nOut;
  4314   4377           pNew->wsFlags = WHERE_TEMP_INDEX;
  4315   4378           pNew->prereq = mExtra | pTerm->prereqRight;
  4316   4379           rc = whereLoopInsert(pBuilder, pNew);
  4317   4380         }
  4318   4381       }
  4319   4382     }
  4320   4383   
  4321   4384     /* Loop over all indices
  4322   4385     */
  4323   4386     for(; rc==SQLITE_OK && pProbe; pProbe=pProbe->pNext, iSortIdx++){
  4324   4387       pNew->u.btree.nEq = 0;
  4325         -    pNew->nTerm = 0;
         4388  +    pNew->nLTerm = 0;
  4326   4389       pNew->iSortIdx = 0;
  4327         -    pNew->rSetup = (double)0;
         4390  +    pNew->rSetup = (WhereCost)0;
  4328   4391       pNew->prereq = mExtra;
  4329   4392       pNew->u.btree.pIndex = pProbe;
  4330   4393       b = indexMightHelpWithOrderBy(pBuilder, pProbe, pSrc->iCursor);
  4331   4394       if( pProbe->tnum<=0 ){
  4332   4395         /* Integer primary key index */
  4333   4396         pNew->wsFlags = WHERE_IPK;
  4334   4397   
................................................................................
  4388   4451     sqlite3 *db;
  4389   4452     sqlite3_index_info *pIdxInfo;
  4390   4453     struct sqlite3_index_constraint *pIdxCons;
  4391   4454     struct sqlite3_index_constraint_usage *pUsage;
  4392   4455     WhereTerm *pTerm;
  4393   4456     int i, j;
  4394   4457     int iTerm, mxTerm;
         4458  +  int nConstraint;
  4395   4459     int seenIn = 0;              /* True if an IN operator is seen */
  4396   4460     int seenVar = 0;             /* True if a non-constant constraint is seen */
  4397   4461     int iPhase;                  /* 0: const w/o IN, 1: const, 2: no IN,  2: IN */
  4398   4462     WhereLoop *pNew;
  4399   4463     int rc = SQLITE_OK;
  4400   4464   
  4401   4465     pWInfo = pBuilder->pWInfo;
................................................................................
  4407   4471     pTab = pSrc->pTab;
  4408   4472     assert( IsVirtual(pTab) );
  4409   4473     pIdxInfo = allocateIndexInfo(pParse, pWC, pSrc, pBuilder->pOrderBy);
  4410   4474     if( pIdxInfo==0 ) return SQLITE_NOMEM;
  4411   4475     pNew->prereq = 0;
  4412   4476     pNew->rSetup = 0;
  4413   4477     pNew->wsFlags = WHERE_VIRTUALTABLE;
  4414         -  pNew->nTerm = 0;
         4478  +  pNew->nLTerm = 0;
  4415   4479     pNew->u.vtab.needFree = 0;
  4416   4480     pUsage = pIdxInfo->aConstraintUsage;
         4481  +  nConstraint = pIdxInfo->nConstraint;
         4482  +  if( whereLoopResize(db, pNew, nConstraint) ) return SQLITE_NOMEM;
  4417   4483   
  4418   4484     for(iPhase=0; iPhase<=3; iPhase++){
  4419   4485       if( !seenIn && (iPhase&1)!=0 ){
  4420   4486         iPhase++;
  4421   4487         if( iPhase>3 ) break;
  4422   4488       }
  4423   4489       if( !seenVar && iPhase>1 ) break;
................................................................................
  4452   4518       }
  4453   4519       memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  4454   4520       if( pIdxInfo->needToFreeIdxStr ) sqlite3_free(pIdxInfo->idxStr);
  4455   4521       pIdxInfo->idxStr = 0;
  4456   4522       pIdxInfo->idxNum = 0;
  4457   4523       pIdxInfo->needToFreeIdxStr = 0;
  4458   4524       pIdxInfo->orderByConsumed = 0;
  4459         -    /* ((double)2) In case of SQLITE_OMIT_FLOATING_POINT... */
  4460         -    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((double)2);
         4525  +    /* ((WhereCost)2) In case of SQLITE_OMIT_FLOATING_POINT... */
         4526  +    pIdxInfo->estimatedCost = SQLITE_BIG_DBL / ((WhereCost)2);
  4461   4527       rc = vtabBestIndex(pParse, pTab, pIdxInfo);
  4462   4528       if( rc ) goto whereLoopAddVtab_exit;
  4463   4529       pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  4464   4530       pNew->prereq = 0;
  4465   4531       mxTerm = -1;
  4466         -    for(i=0; i<pBuilder->mxTerm; i++) pNew->aTerm[i] = 0;
         4532  +    assert( pNew->nLSlot>=nConstraint );
         4533  +    for(i=0; i<nConstraint; i++) pNew->aLTerm[i] = 0;
  4467   4534       pNew->u.vtab.omitMask = 0;
  4468         -    for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
         4535  +    for(i=0; i<nConstraint; i++, pIdxCons++){
  4469   4536         if( (iTerm = pUsage[i].argvIndex - 1)>=0 ){
  4470         -        if( iTerm>=pBuilder->mxTerm ) break;
  4471   4537           j = pIdxCons->iTermOffset;
  4472         -        if( iTerm>=pIdxInfo->nConstraint
         4538  +        if( iTerm>=nConstraint
  4473   4539            || j<0
  4474   4540            || j>=pWC->nTerm
  4475         -         || pNew->aTerm[iTerm]!=0
         4541  +         || pNew->aLTerm[iTerm]!=0
  4476   4542           ){
  4477   4543             rc = SQLITE_ERROR;
  4478   4544             sqlite3ErrorMsg(pParse, "%s.xBestIndex() malfunction", pTab->zName);
  4479   4545             goto whereLoopAddVtab_exit;
  4480   4546           }
  4481   4547           pTerm = &pWC->a[j];
  4482   4548           pNew->prereq |= pTerm->prereqRight;
  4483         -        pNew->aTerm[iTerm] = pTerm;
         4549  +        assert( iTerm<pNew->nLSlot );
         4550  +        pNew->aLTerm[iTerm] = pTerm;
  4484   4551           if( iTerm>mxTerm ) mxTerm = iTerm;
  4485   4552           if( iTerm<16 && pUsage[i].omit ) pNew->u.vtab.omitMask |= 1<<iTerm;
  4486   4553           if( (pTerm->eOperator & WO_IN)!=0 ){
  4487   4554             if( pUsage[i].omit==0 ){
  4488   4555               /* Do not attempt to use an IN constraint if the virtual table
  4489   4556               ** says that the equivalent EQ constraint cannot be safely omitted.
  4490   4557               ** If we do attempt to use such a constraint, some rows might be
................................................................................
  4496   4563             ** is not necessarily related to the order of output terms and
  4497   4564             ** (2) Multiple outputs from a single IN value will not merge
  4498   4565             ** together.  */
  4499   4566             pIdxInfo->orderByConsumed = 0;
  4500   4567           }
  4501   4568         }
  4502   4569       }
  4503         -    if( i>=pIdxInfo->nConstraint ){
  4504         -      pNew->nTerm = mxTerm+1;
         4570  +    if( i>=nConstraint ){
         4571  +      pNew->nLTerm = mxTerm+1;
         4572  +      assert( pNew->nLTerm<=pNew->nLSlot );
  4505   4573         pNew->u.vtab.idxNum = pIdxInfo->idxNum;
  4506   4574         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  4507   4575         pIdxInfo->needToFreeIdxStr = 0;
  4508   4576         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  4509   4577         pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
  4510   4578                                        && pIdxInfo->orderByConsumed);
  4511         -      pNew->rSetup = (double)0;
         4579  +      pNew->rSetup = (WhereCost)0;
  4512   4580         pNew->rRun = pIdxInfo->estimatedCost;
  4513         -      pNew->nOut = (double)25;
         4581  +      pNew->nOut = (WhereCost)25;
  4514   4582         whereLoopInsert(pBuilder, pNew);
  4515   4583         if( pNew->u.vtab.needFree ){
  4516   4584           sqlite3_free(pNew->u.vtab.idxStr);
  4517   4585           pNew->u.vtab.needFree = 0;
  4518   4586         }
  4519   4587       }
  4520   4588     }  
................................................................................
  4541   4609     WhereLoop sBest;
  4542   4610     struct SrcList_item *pItem;
  4543   4611     
  4544   4612     pWC = pBuilder->pWC;
  4545   4613     if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK;
  4546   4614     pWCEnd = pWC->a + pWC->nTerm;
  4547   4615     pNew = pBuilder->pNew;
         4616  +  whereLoopInit(&sBest);
  4548   4617   
  4549   4618     for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){
  4550   4619       if( (pTerm->eOperator & WO_OR)!=0
  4551   4620        && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 
  4552   4621       ){
  4553   4622         WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
  4554   4623         WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
  4555   4624         WhereTerm *pOrTerm;
  4556         -      double rTotal = 0;
  4557         -      double nRow = 0;
         4625  +      WhereCost rTotal = 0;
         4626  +      WhereCost nRow = 0;
  4558   4627         Bitmask prereq = mExtra;
  4559   4628       
  4560   4629         pItem = pWInfo->pTabList->a + pNew->iTab;
  4561   4630         iCur = pItem->iCursor;
  4562   4631         sSubBuild = *pBuilder;
  4563   4632         sSubBuild.pOrderBy = 0;
  4564   4633         sSubBuild.pBest = &sBest;
................................................................................
  4573   4642             tempWC.nTerm = 1;
  4574   4643             tempWC.a = pOrTerm;
  4575   4644             sSubBuild.pWC = &tempWC;
  4576   4645           }else{
  4577   4646             continue;
  4578   4647           }
  4579   4648           sBest.maskSelf = 0;
         4649  +        sBest.rSetup = 0;
         4650  +        sBest.rRun = 0;
  4580   4651           if( IsVirtual(pItem->pTab) ){
  4581   4652             rc = whereLoopAddVirtual(&sSubBuild, mExtra);
  4582   4653           }else{
  4583   4654             rc = whereLoopAddBtree(&sSubBuild, mExtra);
  4584   4655           }
  4585   4656           if( sBest.maskSelf==0 ) break;
  4586         -        assert( sBest.rSetup==(double)0 );
         4657  +        assert( sBest.rSetup==(WhereCost)0 );
  4587   4658           rTotal += sBest.rRun;
  4588   4659           nRow += sBest.nOut;
  4589   4660           prereq |= sBest.prereq;
  4590   4661         }
  4591         -      pNew->nTerm = 1;
  4592         -      pNew->aTerm[0] = pTerm;
         4662  +      assert( pNew->nLSlot>=1 );
         4663  +      pNew->nLTerm = 1;
         4664  +      pNew->aLTerm[0] = pTerm;
  4593   4665         pNew->wsFlags = WHERE_MULTI_OR;
  4594         -      pNew->rSetup = (double)0;
         4666  +      pNew->rSetup = (WhereCost)0;
  4595   4667         pNew->rRun = rTotal;
  4596   4668         pNew->nOut = nRow;
  4597   4669         pNew->prereq = prereq;
  4598   4670         memset(&pNew->u, 0, sizeof(pNew->u));
  4599   4671         rc = whereLoopInsert(pBuilder, pNew);
  4600   4672       }
  4601   4673     }
         4674  +  whereLoopClear(pWInfo->pParse->db, &sBest);
  4602   4675     return rc;
  4603   4676   }
  4604   4677   
  4605   4678   /*
  4606   4679   ** Add all WhereLoop objects for all tables 
  4607   4680   */
  4608   4681   static int whereLoopAddAll(WhereLoopBuilder *pBuilder){
  4609   4682     WhereInfo *pWInfo = pBuilder->pWInfo;
  4610   4683     Bitmask mExtra = 0;
  4611   4684     Bitmask mPrior = 0;
  4612   4685     int iTab;
  4613   4686     SrcList *pTabList = pWInfo->pTabList;
  4614   4687     struct SrcList_item *pItem;
  4615         -  WhereClause *pWC = pBuilder->pWC;
  4616   4688     sqlite3 *db = pWInfo->pParse->db;
  4617   4689     int nTabList = pWInfo->nLevel;
  4618   4690     int rc = SQLITE_OK;
  4619   4691     WhereLoop *pNew;
  4620   4692   
  4621   4693     /* Loop over the tables in the join, from left to right */
  4622   4694     pBuilder->pNew = pNew = sqlite3DbMallocZero(db, sizeof(WhereLoop));
  4623   4695     if( pNew==0 ) return SQLITE_NOMEM;
  4624         -  pBuilder->mxTerm = pWC->nTerm+1;
  4625         -  while( pWC->pOuter ){
  4626         -    pWC = pWC->pOuter;
  4627         -    pBuilder->mxTerm += pWC->nTerm;
  4628         -  }
  4629         -  pWC = pBuilder->pWC;
  4630         -  pNew->aTerm = sqlite3DbMallocZero(db,pBuilder->mxTerm*sizeof(pNew->aTerm[0]));
  4631         -  if( pNew->aTerm==0 ){
  4632         -    rc = SQLITE_NOMEM;
  4633         -    goto whereLoopAddAll_end;
  4634         -  }
         4696  +  pNew->aLTerm = pNew->aLTermSpace;
         4697  +  pNew->nLSlot = ArraySize(pNew->aLTermSpace);
  4635   4698     for(iTab=0, pItem=pTabList->a; iTab<nTabList; iTab++, pItem++){
  4636   4699       pNew->iTab = iTab;
  4637   4700       pNew->maskSelf = getMask(&pWInfo->sMaskSet, pItem->iCursor);
  4638   4701       if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){
  4639   4702         mExtra = mPrior;
  4640   4703       }
  4641   4704       if( IsVirtual(pItem->pTab) ){
................................................................................
  4645   4708       }
  4646   4709       if( rc==SQLITE_OK ){
  4647   4710         rc = whereLoopAddOr(pBuilder, mExtra);
  4648   4711       }
  4649   4712       mPrior |= pNew->maskSelf;
  4650   4713       if( rc || db->mallocFailed ) break;
  4651   4714     }
  4652         -whereLoopAddAll_end:
  4653   4715     whereLoopDelete(db, pBuilder->pNew);
  4654   4716     pBuilder->pNew = 0;
  4655   4717     return rc;
  4656   4718   }
  4657   4719   
  4658   4720   /*
  4659   4721   ** Examine a WherePath (with the addition of the extra WhereLoop of the 5th
................................................................................
  4751   4813         }
  4752   4814   
  4753   4815         /* For every term of the index that is constrained by == or IS NULL,
  4754   4816         ** mark off corresponding ORDER BY terms wherever they occur
  4755   4817         ** in the ORDER BY clause.
  4756   4818         */
  4757   4819         for(i=0; i<pLoop->u.btree.nEq; i++){
  4758         -        pTerm = pLoop->aTerm[i];
         4820  +        pTerm = pLoop->aLTerm[i];
  4759   4821           if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))==0 ) continue;
  4760   4822           iColumn = pTerm->u.leftColumn;
  4761   4823           for(j=0; j<nOrderBy; j++){
  4762   4824             if( MASKBIT(j) & obSat ) continue;
  4763   4825             pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[j].pExpr);
  4764   4826             if( pOBExpr->op!=TK_COLUMN ) continue;
  4765   4827             if( pOBExpr->iTable!=iCur ) continue;
................................................................................
  4780   4842         rev = revSet = 0;
  4781   4843         distinctColumns = 0;
  4782   4844         for(j=0; j<=nColumn; j++){
  4783   4845           u8 bOnce;   /* True to run the ORDER BY search loop */
  4784   4846   
  4785   4847           /* Skip over == and IS NULL terms */
  4786   4848           if( j<pLoop->u.btree.nEq
  4787         -         && ((i = pLoop->aTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
         4849  +         && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL))!=0
  4788   4850           ){
  4789   4851             if( i & WO_ISNULL ) isOrderDistinct = 0;
  4790   4852             continue;  
  4791   4853           }
  4792   4854   
  4793   4855           /* Get the column number in the table (iColumn) and sort order
  4794   4856           ** (revIdx) for the j-th column of the index.
................................................................................
  4894   4956   ** Given the list of WhereLoop objects on pWInfo->pLoops, this routine
  4895   4957   ** attempts to find the lowest cost path that visits each WhereLoop
  4896   4958   ** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
  4897   4959   **
  4898   4960   ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
  4899   4961   ** error occurs.
  4900   4962   */
  4901         -static int wherePathSolver(WhereInfo *pWInfo, double nRowEst){
         4963  +static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
  4902   4964     int mxChoice;             /* Maximum number of simultaneous paths tracked */
  4903   4965     int nLoop;                /* Number of terms in the join */
  4904   4966     sqlite3 *db;              /* The database connection */
  4905   4967     int iLoop;                /* Loop counter over the terms of the join */
  4906   4968     int ii, jj;               /* Loop counters */
  4907         -  double rCost;             /* Cost of a path */
  4908         -  double mxCost;            /* Maximum cost of a set of paths */
  4909         -  double rSortCost;         /* Cost to do a sort */
         4969  +  WhereCost rCost;             /* Cost of a path */
         4970  +  WhereCost mxCost;            /* Maximum cost of a set of paths */
         4971  +  WhereCost rSortCost;         /* Cost to do a sort */
  4910   4972     int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  4911   4973     WherePath *aFrom;         /* All nFrom paths at the previous level */
  4912   4974     WherePath *aTo;           /* The nTo best paths at the current level */
  4913   4975     WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  4914   4976     WherePath *pTo;           /* An element of aTo[] that we are working on */
  4915   4977     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  4916   4978     WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
  4933   4995     memset(aFrom, 0, sizeof(aFrom[0]));
  4934   4996     pX = (WhereLoop**)(aFrom+mxChoice);
  4935   4997     for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){
  4936   4998       pFrom->aLoop = pX;
  4937   4999     }
  4938   5000   
  4939   5001     /* Seed the search with a single WherePath containing zero WhereLoops */
  4940         -  aFrom[0].nRow = (double)1;
         5002  +  aFrom[0].nRow = (WhereCost)1;
  4941   5003     nFrom = 1;
  4942   5004   
  4943   5005     /* Precompute the cost of sorting the final result set, if the caller
  4944   5006     ** to sqlite3WhereBegin() was concerned about sorting */
  4945         -  rSortCost = (double)0;
         5007  +  rSortCost = (WhereCost)0;
  4946   5008     if( pWInfo->pOrderBy==0 || nRowEst<=0.0 ){
  4947   5009       aFrom[0].isOrderedValid = 1;
  4948   5010     }else{
  4949   5011       /* Compute an estimate on the cost to sort the entire result set */
  4950   5012       rSortCost = nRowEst*estLog(nRowEst);
  4951   5013   #ifdef WHERETRACE_ENABLED
  4952   5014       if( sqlite3WhereTrace>=2 ){
................................................................................
  5408   5470   #endif
  5409   5471   
  5410   5472     /* Open all tables in the pTabList and any indices selected for
  5411   5473     ** searching those tables.
  5412   5474     */
  5413   5475     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  5414   5476     notReady = ~(Bitmask)0;
  5415         -  pWInfo->nRowOut = (double)1;
         5477  +  pWInfo->nRowOut = (WhereCost)1;
  5416   5478     for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
  5417   5479       Table *pTab;     /* Table to open */
  5418   5480       int iDb;         /* Index of database containing table/index */
  5419   5481       struct SrcList_item *pTabItem;
  5420   5482       WhereLoop *pLoop;
  5421   5483   
  5422   5484       pTabItem = &pTabList->a[pLevel->iFrom];