/ Check-in [bc446449]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Adjust the query planner to take into account WHERE clause terms that do not drive indices. Add the unlikely() and likelihood() functions used to give hints to the query planner about the selectivity of WHERE clause terms.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: bc446449a19171c0fa0681973b06bc80d3c0517f
User & Date: drh 2013-09-13 17:47:57
Context
2013-09-13
18:15
Remove one unreachable branch and add asserts() to dupedExprStructSize(). New asserts verify that removed branch is unused and that constants that are ORed together in the output do not overlap. check-in: 86ad358b user: drh tags: trunk
17:47
Adjust the query planner to take into account WHERE clause terms that do not drive indices. Add the unlikely() and likelihood() functions used to give hints to the query planner about the selectivity of WHERE clause terms. check-in: bc446449 user: drh tags: trunk
16:56
Enhance the pragma lookup table generator script to output a comment that gives the number of pragmas. check-in: ca052050 user: drh tags: trunk
2013-09-12
23:42
Refactor the ExprSetIrreducible() macro into ExprSetVVAProperty(*,EP_NoReduce). This is a naming change only. The logic is the same. Closed-Leaf check-in: 695aee46 user: drh tags: unlikely-func
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/attach.c.

   505    505     return 0;
   506    506   }
   507    507   int sqlite3FixExpr(
   508    508     DbFixer *pFix,     /* Context of the fixation */
   509    509     Expr *pExpr        /* The expression to be fixed to one database */
   510    510   ){
   511    511     while( pExpr ){
   512         -    if( ExprHasAnyProperty(pExpr, EP_TokenOnly) ) break;
          512  +    if( ExprHasProperty(pExpr, EP_TokenOnly) ) break;
   513    513       if( ExprHasProperty(pExpr, EP_xIsSelect) ){
   514    514         if( sqlite3FixSelect(pFix, pExpr->x.pSelect) ) return 1;
   515    515       }else{
   516    516         if( sqlite3FixExprList(pFix, pExpr->x.pList) ) return 1;
   517    517       }
   518    518       if( sqlite3FixExpr(pFix, pExpr->pRight) ){
   519    519         return 1;

Changes to src/expr.c.

    66     66   ** and the pExpr parameter is returned unchanged.
    67     67   */
    68     68   Expr *sqlite3ExprAddCollateToken(Parse *pParse, Expr *pExpr, Token *pCollName){
    69     69     if( pCollName->n>0 ){
    70     70       Expr *pNew = sqlite3ExprAlloc(pParse->db, TK_COLLATE, pCollName, 1);
    71     71       if( pNew ){
    72     72         pNew->pLeft = pExpr;
    73         -      pNew->flags |= EP_Collate;
           73  +      pNew->flags |= EP_Collate|EP_Skip;
    74     74         pExpr = pNew;
    75     75       }
    76     76     }
    77     77     return pExpr;
    78     78   }
    79     79   Expr *sqlite3ExprAddCollateString(Parse *pParse, Expr *pExpr, const char *zC){
    80     80     Token s;
................................................................................
    81     81     assert( zC!=0 );
    82     82     s.z = zC;
    83     83     s.n = sqlite3Strlen30(s.z);
    84     84     return sqlite3ExprAddCollateToken(pParse, pExpr, &s);
    85     85   }
    86     86   
    87     87   /*
    88         -** Skip over any TK_COLLATE and/or TK_AS operators at the root of
    89         -** an expression.
           88  +** Skip over any TK_COLLATE or TK_AS operators and any unlikely()
           89  +** or likelihood() function at the root of an expression.
    90     90   */
    91     91   Expr *sqlite3ExprSkipCollate(Expr *pExpr){
    92         -  while( pExpr && (pExpr->op==TK_COLLATE || pExpr->op==TK_AS) ){
    93         -    pExpr = pExpr->pLeft;
    94         -  }
           92  +  while( pExpr && ExprHasProperty(pExpr, EP_Skip) ){
           93  +    if( ExprHasProperty(pExpr, EP_Unlikely) ){
           94  +      assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
           95  +      assert( pExpr->x.pList->nExpr>0 );
           96  +      assert( pExpr->op==TK_FUNCTION );
           97  +      pExpr = pExpr->x.pList->a[0].pExpr;
           98  +    }else{
           99  +      assert( pExpr->op==TK_COLLATE || pExpr->op==TK_AS );
          100  +      pExpr = pExpr->pLeft;
          101  +    }
          102  +  }   
    95    103     return pExpr;
    96    104   }
    97    105   
    98    106   /*
    99    107   ** Return the collation sequence for the expression pExpr. If
   100    108   ** there is no defined collating sequence, return NULL.
   101    109   **
................................................................................
   592    600   ** assigned.
   593    601   */
   594    602   void sqlite3ExprAssignVarNumber(Parse *pParse, Expr *pExpr){
   595    603     sqlite3 *db = pParse->db;
   596    604     const char *z;
   597    605   
   598    606     if( pExpr==0 ) return;
   599         -  assert( !ExprHasAnyProperty(pExpr, EP_IntValue|EP_Reduced|EP_TokenOnly) );
          607  +  assert( !ExprHasProperty(pExpr, EP_IntValue|EP_Reduced|EP_TokenOnly) );
   600    608     z = pExpr->u.zToken;
   601    609     assert( z!=0 );
   602    610     assert( z[0]!=0 );
   603    611     if( z[1]==0 ){
   604    612       /* Wildcard of the form "?".  Assign the next variable number */
   605    613       assert( z[0]=='?' );
   606    614       pExpr->iColumn = (ynVar)(++pParse->nVar);
................................................................................
   662    670   /*
   663    671   ** Recursively delete an expression tree.
   664    672   */
   665    673   void sqlite3ExprDelete(sqlite3 *db, Expr *p){
   666    674     if( p==0 ) return;
   667    675     /* Sanity check: Assert that the IntValue is non-negative if it exists */
   668    676     assert( !ExprHasProperty(p, EP_IntValue) || p->u.iValue>=0 );
   669         -  if( !ExprHasAnyProperty(p, EP_TokenOnly) ){
          677  +  if( !ExprHasProperty(p, EP_TokenOnly) ){
          678  +    /* The Expr.x union is never used at the same time as Expr.pRight */
          679  +    assert( p->x.pList==0 || p->pRight==0 );
   670    680       sqlite3ExprDelete(db, p->pLeft);
   671    681       sqlite3ExprDelete(db, p->pRight);
   672         -    if( !ExprHasProperty(p, EP_Reduced) && (p->flags2 & EP2_MallocedToken)!=0 ){
   673         -      sqlite3DbFree(db, p->u.zToken);
   674         -    }
          682  +    if( ExprHasProperty(p, EP_MemToken) ) sqlite3DbFree(db, p->u.zToken);
   675    683       if( ExprHasProperty(p, EP_xIsSelect) ){
   676    684         sqlite3SelectDelete(db, p->x.pSelect);
   677    685       }else{
   678    686         sqlite3ExprListDelete(db, p->x.pList);
   679    687       }
   680    688     }
   681    689     if( !ExprHasProperty(p, EP_Static) ){
................................................................................
   730    738   */
   731    739   static int dupedExprStructSize(Expr *p, int flags){
   732    740     int nSize;
   733    741     assert( flags==EXPRDUP_REDUCE || flags==0 ); /* Only one flag value allowed */
   734    742     if( 0==(flags&EXPRDUP_REDUCE) ){
   735    743       nSize = EXPR_FULLSIZE;
   736    744     }else{
   737         -    assert( !ExprHasAnyProperty(p, EP_TokenOnly|EP_Reduced) );
          745  +    assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );
   738    746       assert( !ExprHasProperty(p, EP_FromJoin) ); 
   739         -    assert( (p->flags2 & EP2_MallocedToken)==0 );
   740         -    assert( (p->flags2 & EP2_Irreducible)==0 );
          747  +    assert( !ExprHasProperty(p, EP_MemToken) );
          748  +    assert( !ExprHasProperty(p, EP_NoReduce) );
   741    749       if( p->pLeft || p->pRight || p->x.pList ){
   742    750         nSize = EXPR_REDUCEDSIZE | EP_Reduced;
   743    751       }else{
   744    752         nSize = EXPR_TOKENONLYSIZE | EP_TokenOnly;
   745    753       }
   746    754     }
   747    755     return nSize;
................................................................................
   830    838         }else{
   831    839           int nSize = exprStructSize(p);
   832    840           memcpy(zAlloc, p, nSize);
   833    841           memset(&zAlloc[nSize], 0, EXPR_FULLSIZE-nSize);
   834    842         }
   835    843   
   836    844         /* Set the EP_Reduced, EP_TokenOnly, and EP_Static flags appropriately. */
   837         -      pNew->flags &= ~(EP_Reduced|EP_TokenOnly|EP_Static);
          845  +      pNew->flags &= ~(EP_Reduced|EP_TokenOnly|EP_Static|EP_MemToken);
   838    846         pNew->flags |= nStructSize & (EP_Reduced|EP_TokenOnly);
   839    847         pNew->flags |= staticFlag;
   840    848   
   841    849         /* Copy the p->u.zToken string, if any. */
   842    850         if( nToken ){
   843    851           char *zToken = pNew->u.zToken = (char*)&zAlloc[nNewSize];
   844    852           memcpy(zToken, p->u.zToken, nToken);
................................................................................
   850    858             pNew->x.pSelect = sqlite3SelectDup(db, p->x.pSelect, isReduced);
   851    859           }else{
   852    860             pNew->x.pList = sqlite3ExprListDup(db, p->x.pList, isReduced);
   853    861           }
   854    862         }
   855    863   
   856    864         /* Fill in pNew->pLeft and pNew->pRight. */
   857         -      if( ExprHasAnyProperty(pNew, EP_Reduced|EP_TokenOnly) ){
          865  +      if( ExprHasProperty(pNew, EP_Reduced|EP_TokenOnly) ){
   858    866           zAlloc += dupedExprNodeSize(p, flags);
   859    867           if( ExprHasProperty(pNew, EP_Reduced) ){
   860    868             pNew->pLeft = exprDup(db, p->pLeft, EXPRDUP_REDUCE, &zAlloc);
   861    869             pNew->pRight = exprDup(db, p->pRight, EXPRDUP_REDUCE, &zAlloc);
   862    870           }
   863    871           if( pzBuffer ){
   864    872             *pzBuffer = zAlloc;
   865    873           }
   866    874         }else{
   867         -        pNew->flags2 = 0;
   868         -        if( !ExprHasAnyProperty(p, EP_TokenOnly) ){
          875  +        if( !ExprHasProperty(p, EP_TokenOnly) ){
   869    876             pNew->pLeft = sqlite3ExprDup(db, p->pLeft, 0);
   870    877             pNew->pRight = sqlite3ExprDup(db, p->pRight, 0);
   871    878           }
   872    879         }
   873    880   
   874    881       }
   875    882     }
................................................................................
  1171   1178   **
  1172   1179   */
  1173   1180   static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){
  1174   1181   
  1175   1182     /* If pWalker->u.i is 3 then any term of the expression that comes from
  1176   1183     ** the ON or USING clauses of a join disqualifies the expression
  1177   1184     ** from being considered constant. */
  1178         -  if( pWalker->u.i==3 && ExprHasAnyProperty(pExpr, EP_FromJoin) ){
         1185  +  if( pWalker->u.i==3 && ExprHasProperty(pExpr, EP_FromJoin) ){
  1179   1186       pWalker->u.i = 0;
  1180   1187       return WRC_Abort;
  1181   1188     }
  1182   1189   
  1183   1190     switch( pExpr->op ){
  1184   1191       /* Consider functions to be constant if all their arguments are constant
  1185   1192       ** and pWalker->u.i==2 */
................................................................................
  1602   1609       eType = IN_INDEX_EPH;
  1603   1610       if( prNotFound ){
  1604   1611         *prNotFound = rMayHaveNull = ++pParse->nMem;
  1605   1612         sqlite3VdbeAddOp2(v, OP_Null, 0, *prNotFound);
  1606   1613       }else{
  1607   1614         testcase( pParse->nQueryLoop>0 );
  1608   1615         pParse->nQueryLoop = 0;
  1609         -      if( pX->pLeft->iColumn<0 && !ExprHasAnyProperty(pX, EP_xIsSelect) ){
         1616  +      if( pX->pLeft->iColumn<0 && !ExprHasProperty(pX, EP_xIsSelect) ){
  1610   1617           eType = IN_INDEX_ROWID;
  1611   1618         }
  1612   1619       }
  1613   1620       sqlite3CodeSubselect(pParse, pX, rMayHaveNull, eType==IN_INDEX_ROWID);
  1614   1621       pParse->nQueryLoop = savedNQueryLoop;
  1615   1622     }else{
  1616   1623       pX->iTable = iTab;
................................................................................
  1671   1678     **    *  The right-hand side is a correlated subquery
  1672   1679     **    *  The right-hand side is an expression list containing variables
  1673   1680     **    *  We are inside a trigger
  1674   1681     **
  1675   1682     ** If all of the above are false, then we can run this code just once
  1676   1683     ** save the results, and reuse the same result on subsequent invocations.
  1677   1684     */
  1678         -  if( !ExprHasAnyProperty(pExpr, EP_VarSelect) ){
         1685  +  if( !ExprHasProperty(pExpr, EP_VarSelect) ){
  1679   1686       testAddr = sqlite3CodeOnce(pParse);
  1680   1687     }
  1681   1688   
  1682   1689   #ifndef SQLITE_OMIT_EXPLAIN
  1683   1690     if( pParse->explain==2 ){
  1684   1691       char *zMsg = sqlite3MPrintf(
  1685   1692           pParse->db, "EXECUTE %s%s SUBQUERY %d", testAddr>=0?"":"CORRELATED ",
................................................................................
  1840   1847         pSel->pLimit = sqlite3PExpr(pParse, TK_INTEGER, 0, 0,
  1841   1848                                     &sqlite3IntTokens[1]);
  1842   1849         pSel->iLimit = 0;
  1843   1850         if( sqlite3Select(pParse, pSel, &dest) ){
  1844   1851           return 0;
  1845   1852         }
  1846   1853         rReg = dest.iSDParm;
  1847         -      ExprSetIrreducible(pExpr);
         1854  +      ExprSetVVAProperty(pExpr, EP_NoReduce);
  1848   1855         break;
  1849   1856       }
  1850   1857     }
  1851   1858   
  1852   1859     if( testAddr>=0 ){
  1853   1860       sqlite3VdbeJumpHere(v, testAddr);
  1854   1861     }
................................................................................
  2311   2318     for(i=0, p=pParse->aColCache; i<SQLITE_N_COLCACHE; i++, p++){
  2312   2319       int r = p->iReg;
  2313   2320       if( r>=iFrom && r<=iTo ) return 1;    /*NO_TEST*/
  2314   2321     }
  2315   2322     return 0;
  2316   2323   }
  2317   2324   #endif /* SQLITE_DEBUG || SQLITE_COVERAGE_TEST */
         2325  +
         2326  +/*
         2327  +** Convert an expression node to a TK_REGISTER
         2328  +*/
         2329  +static void exprToRegister(Expr *p, int iReg){
         2330  +  p->op2 = p->op;
         2331  +  p->op = TK_REGISTER;
         2332  +  p->iTable = iReg;
         2333  +  ExprClearProperty(p, EP_Skip);
         2334  +}
  2318   2335   
  2319   2336   /*
  2320   2337   ** Generate code into the current Vdbe to evaluate the given
  2321   2338   ** expression.  Attempt to store the results in register "target".
  2322   2339   ** Return the register where results are stored.
  2323   2340   **
  2324   2341   ** With this routine, there is no guarantee that results will
................................................................................
  2611   2628         int i;                 /* Loop counter */
  2612   2629         u8 enc = ENC(db);      /* The text encoding used by this database */
  2613   2630         CollSeq *pColl = 0;    /* A collating sequence */
  2614   2631   
  2615   2632         assert( !ExprHasProperty(pExpr, EP_xIsSelect) );
  2616   2633         testcase( op==TK_CONST_FUNC );
  2617   2634         testcase( op==TK_FUNCTION );
  2618         -      if( ExprHasAnyProperty(pExpr, EP_TokenOnly) ){
         2635  +      if( ExprHasProperty(pExpr, EP_TokenOnly) ){
  2619   2636           pFarg = 0;
  2620   2637         }else{
  2621   2638           pFarg = pExpr->x.pList;
  2622   2639         }
  2623   2640         nFarg = pFarg ? pFarg->nExpr : 0;
  2624   2641         assert( !ExprHasProperty(pExpr, EP_IntValue) );
  2625   2642         zId = pExpr->u.zToken;
................................................................................
  2645   2662             sqlite3ExprCode(pParse, pFarg->a[i].pExpr, target);
  2646   2663             sqlite3ExprCachePop(pParse, 1);
  2647   2664           }
  2648   2665           sqlite3VdbeResolveLabel(v, endCoalesce);
  2649   2666           break;
  2650   2667         }
  2651   2668   
         2669  +      /* The UNLIKELY() function is a no-op.  The result is the value
         2670  +      ** of the first argument.
         2671  +      */
         2672  +      if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
         2673  +        assert( nFarg>=1 );
         2674  +        sqlite3ExprCode(pParse, pFarg->a[0].pExpr, target);
         2675  +        break;
         2676  +      }
  2652   2677   
  2653   2678         if( pFarg ){
  2654   2679           r1 = sqlite3GetTempRange(pParse, nFarg);
  2655   2680   
  2656   2681           /* For length() and typeof() functions with a column argument,
  2657   2682           ** set the P5 parameter to the OP_Column opcode to OPFLAG_LENGTHARG
  2658   2683           ** or OPFLAG_TYPEOFARG respectively, to avoid unnecessary data
................................................................................
  2842   2867       **   CASE WHEN e1 THEN r1 WHEN e2 THEN r2 ... WHEN eN THEN rN ELSE y END
  2843   2868       **
  2844   2869       ** Form A is can be transformed into the equivalent form B as follows:
  2845   2870       **   CASE WHEN x=e1 THEN r1 WHEN x=e2 THEN r2 ...
  2846   2871       **        WHEN x=eN THEN rN ELSE y END
  2847   2872       **
  2848   2873       ** X (if it exists) is in pExpr->pLeft.
  2849         -    ** Y is in pExpr->pRight.  The Y is also optional.  If there is no
  2850         -    ** ELSE clause and no other term matches, then the result of the
  2851         -    ** exprssion is NULL.
         2874  +    ** Y is in the last element of pExpr->x.pList if pExpr->x.pList->nExpr is
         2875  +    ** odd.  The Y is also optional.  If the number of elements in x.pList
         2876  +    ** is even, then Y is omitted and the "otherwise" result is NULL.
  2852   2877       ** Ei is in pExpr->pList->a[i*2] and Ri is pExpr->pList->a[i*2+1].
  2853   2878       **
  2854   2879       ** The result of the expression is the Ri for the first matching Ei,
  2855   2880       ** or if there is no matching Ei, the ELSE term Y, or if there is
  2856   2881       ** no ELSE term, NULL.
  2857   2882       */
  2858   2883       default: assert( op==TK_CASE ); {
................................................................................
  2865   2890         Expr opCompare;                   /* The X==Ei expression */
  2866   2891         Expr cacheX;                      /* Cached expression X */
  2867   2892         Expr *pX;                         /* The X expression */
  2868   2893         Expr *pTest = 0;                  /* X==Ei (form A) or just Ei (form B) */
  2869   2894         VVA_ONLY( int iCacheLevel = pParse->iCacheLevel; )
  2870   2895   
  2871   2896         assert( !ExprHasProperty(pExpr, EP_xIsSelect) && pExpr->x.pList );
  2872         -      assert((pExpr->x.pList->nExpr % 2) == 0);
  2873   2897         assert(pExpr->x.pList->nExpr > 0);
  2874   2898         pEList = pExpr->x.pList;
  2875   2899         aListelem = pEList->a;
  2876   2900         nExpr = pEList->nExpr;
  2877   2901         endLabel = sqlite3VdbeMakeLabel(v);
  2878   2902         if( (pX = pExpr->pLeft)!=0 ){
  2879   2903           cacheX = *pX;
  2880   2904           testcase( pX->op==TK_COLUMN );
  2881   2905           testcase( pX->op==TK_REGISTER );
  2882         -        cacheX.iTable = sqlite3ExprCodeTemp(pParse, pX, &regFree1);
         2906  +        exprToRegister(&cacheX, sqlite3ExprCodeTemp(pParse, pX, &regFree1));
  2883   2907           testcase( regFree1==0 );
  2884         -        cacheX.op = TK_REGISTER;
  2885   2908           opCompare.op = TK_EQ;
  2886   2909           opCompare.pLeft = &cacheX;
  2887   2910           pTest = &opCompare;
  2888   2911           /* Ticket b351d95f9cd5ef17e9d9dbae18f5ca8611190001:
  2889   2912           ** The value in regFree1 might get SCopy-ed into the file result.
  2890   2913           ** So make sure that the regFree1 register is not reused for other
  2891   2914           ** purposes and possibly overwritten.  */
  2892   2915           regFree1 = 0;
  2893   2916         }
  2894         -      for(i=0; i<nExpr; i=i+2){
         2917  +      for(i=0; i<nExpr-1; i=i+2){
  2895   2918           sqlite3ExprCachePush(pParse);
  2896   2919           if( pX ){
  2897   2920             assert( pTest!=0 );
  2898   2921             opCompare.pRight = aListelem[i].pExpr;
  2899   2922           }else{
  2900   2923             pTest = aListelem[i].pExpr;
  2901   2924           }
................................................................................
  2905   2928           testcase( aListelem[i+1].pExpr->op==TK_COLUMN );
  2906   2929           testcase( aListelem[i+1].pExpr->op==TK_REGISTER );
  2907   2930           sqlite3ExprCode(pParse, aListelem[i+1].pExpr, target);
  2908   2931           sqlite3VdbeAddOp2(v, OP_Goto, 0, endLabel);
  2909   2932           sqlite3ExprCachePop(pParse, 1);
  2910   2933           sqlite3VdbeResolveLabel(v, nextCase);
  2911   2934         }
  2912         -      if( pExpr->pRight ){
         2935  +      if( (nExpr&1)!=0 ){
  2913   2936           sqlite3ExprCachePush(pParse);
  2914         -        sqlite3ExprCode(pParse, pExpr->pRight, target);
         2937  +        sqlite3ExprCode(pParse, pEList->a[nExpr-1].pExpr, target);
  2915   2938           sqlite3ExprCachePop(pParse, 1);
  2916   2939         }else{
  2917   2940           sqlite3VdbeAddOp2(v, OP_Null, 0, target);
  2918   2941         }
  2919   2942         assert( db->mallocFailed || pParse->nErr>0 
  2920   2943              || pParse->iCacheLevel==iCacheLevel );
  2921   2944         sqlite3VdbeResolveLabel(v, endLabel);
................................................................................
  3019   3042     ** no way for a TK_REGISTER to exist here.  But it seems prudent to
  3020   3043     ** keep the ALWAYS() in case the conditions above change with future
  3021   3044     ** modifications or enhancements. */
  3022   3045     if( ALWAYS(pExpr->op!=TK_REGISTER) ){  
  3023   3046       int iMem;
  3024   3047       iMem = ++pParse->nMem;
  3025   3048       sqlite3VdbeAddOp2(v, OP_Copy, inReg, iMem);
  3026         -    pExpr->iTable = iMem;
  3027         -    pExpr->op2 = pExpr->op;
  3028         -    pExpr->op = TK_REGISTER;
         3049  +    exprToRegister(pExpr, iMem);
  3029   3050     }
  3030   3051     return inReg;
  3031   3052   }
  3032   3053   
  3033   3054   #if defined(SQLITE_ENABLE_TREE_EXPLAIN)
  3034   3055   /*
  3035   3056   ** Generate a human-readable explanation of an expression tree.
................................................................................
  3151   3172         break;
  3152   3173       }
  3153   3174   
  3154   3175       case TK_AGG_FUNCTION:
  3155   3176       case TK_CONST_FUNC:
  3156   3177       case TK_FUNCTION: {
  3157   3178         ExprList *pFarg;       /* List of function arguments */
  3158         -      if( ExprHasAnyProperty(pExpr, EP_TokenOnly) ){
         3179  +      if( ExprHasProperty(pExpr, EP_TokenOnly) ){
  3159   3180           pFarg = 0;
  3160   3181         }else{
  3161   3182           pFarg = pExpr->x.pList;
  3162   3183         }
  3163   3184         if( op==TK_AGG_FUNCTION ){
  3164   3185           sqlite3ExplainPrintf(pOut, "AGG_FUNCTION%d:%s(",
  3165   3186                                pExpr->op2, pExpr->u.zToken);
................................................................................
  3400   3421     if( isAppropriateForFactoring(pExpr) ){
  3401   3422       int r1 = ++pParse->nMem;
  3402   3423       int r2 = sqlite3ExprCodeTarget(pParse, pExpr, r1);
  3403   3424       /* If r2!=r1, it means that register r1 is never used.  That is harmless
  3404   3425       ** but suboptimal, so we want to know about the situation to fix it.
  3405   3426       ** Hence the following assert: */
  3406   3427       assert( r2==r1 );
  3407         -    pExpr->op2 = pExpr->op;
  3408         -    pExpr->op = TK_REGISTER;
  3409         -    pExpr->iTable = r2;
         3428  +    exprToRegister(pExpr, r2);
  3410   3429       return WRC_Prune;
  3411   3430     }
  3412   3431     return WRC_Continue;
  3413   3432   }
  3414   3433   
  3415   3434   /*
  3416   3435   ** Preevaluate constant subexpressions within pExpr and store the
................................................................................
  3500   3519     exprAnd.pRight = &compRight;
  3501   3520     compLeft.op = TK_GE;
  3502   3521     compLeft.pLeft = &exprX;
  3503   3522     compLeft.pRight = pExpr->x.pList->a[0].pExpr;
  3504   3523     compRight.op = TK_LE;
  3505   3524     compRight.pLeft = &exprX;
  3506   3525     compRight.pRight = pExpr->x.pList->a[1].pExpr;
  3507         -  exprX.iTable = sqlite3ExprCodeTemp(pParse, &exprX, &regFree1);
  3508         -  exprX.op2 = exprX.op;
  3509         -  exprX.op = TK_REGISTER;
         3526  +  exprToRegister(&exprX, sqlite3ExprCodeTemp(pParse, &exprX, &regFree1));
  3510   3527     if( jumpIfTrue ){
  3511   3528       sqlite3ExprIfTrue(pParse, &exprAnd, dest, jumpIfNull);
  3512   3529     }else{
  3513   3530       sqlite3ExprIfFalse(pParse, &exprAnd, dest, jumpIfNull);
  3514   3531     }
  3515   3532     sqlite3ReleaseTempReg(pParse, regFree1);
  3516   3533   
................................................................................
  3817   3834   ** just might result in some slightly slower code.  But returning
  3818   3835   ** an incorrect 0 or 1 could lead to a malfunction.
  3819   3836   */
  3820   3837   int sqlite3ExprCompare(Expr *pA, Expr *pB, int iTab){
  3821   3838     if( pA==0||pB==0 ){
  3822   3839       return pB==pA ? 0 : 2;
  3823   3840     }
  3824         -  assert( !ExprHasAnyProperty(pA, EP_TokenOnly|EP_Reduced) );
  3825         -  assert( !ExprHasAnyProperty(pB, EP_TokenOnly|EP_Reduced) );
         3841  +  assert( !ExprHasProperty(pA, EP_TokenOnly|EP_Reduced) );
         3842  +  assert( !ExprHasProperty(pB, EP_TokenOnly|EP_Reduced) );
  3826   3843     if( ExprHasProperty(pA, EP_xIsSelect) || ExprHasProperty(pB, EP_xIsSelect) ){
  3827   3844       return 2;
  3828   3845     }
  3829   3846     if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2;
  3830   3847     if( pA->op!=pB->op && (pA->op!=TK_REGISTER || pA->op2!=pB->op) ){
  3831   3848       if( pA->op==TK_COLLATE && sqlite3ExprCompare(pA->pLeft, pB, iTab)<2 ){
  3832   3849         return 1;
................................................................................
  4032   4049         testcase( pExpr->op==TK_COLUMN );
  4033   4050         /* Check to see if the column is in one of the tables in the FROM
  4034   4051         ** clause of the aggregate query */
  4035   4052         if( ALWAYS(pSrcList!=0) ){
  4036   4053           struct SrcList_item *pItem = pSrcList->a;
  4037   4054           for(i=0; i<pSrcList->nSrc; i++, pItem++){
  4038   4055             struct AggInfo_col *pCol;
  4039         -          assert( !ExprHasAnyProperty(pExpr, EP_TokenOnly|EP_Reduced) );
         4056  +          assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
  4040   4057             if( pExpr->iTable==pItem->iCursor ){
  4041   4058               /* If we reach this point, it means that pExpr refers to a table
  4042   4059               ** that is in the FROM clause of the aggregate query.  
  4043   4060               **
  4044   4061               ** Make an entry for the column in pAggInfo->aCol[] if there
  4045   4062               ** is not an entry there already.
  4046   4063               */
................................................................................
  4081   4098                 }
  4082   4099               }
  4083   4100               /* There is now an entry for pExpr in pAggInfo->aCol[] (either
  4084   4101               ** because it was there before or because we just created it).
  4085   4102               ** Convert the pExpr to be a TK_AGG_COLUMN referring to that
  4086   4103               ** pAggInfo->aCol[] entry.
  4087   4104               */
  4088         -            ExprSetIrreducible(pExpr);
         4105  +            ExprSetVVAProperty(pExpr, EP_NoReduce);
  4089   4106               pExpr->pAggInfo = pAggInfo;
  4090   4107               pExpr->op = TK_AGG_COLUMN;
  4091   4108               pExpr->iAgg = (i16)k;
  4092   4109               break;
  4093   4110             } /* endif pExpr->iTable==pItem->iCursor */
  4094   4111           } /* end loop over pSrcList */
  4095   4112         }
................................................................................
  4127   4144               }else{
  4128   4145                 pItem->iDistinct = -1;
  4129   4146               }
  4130   4147             }
  4131   4148           }
  4132   4149           /* Make pExpr point to the appropriate pAggInfo->aFunc[] entry
  4133   4150           */
  4134         -        assert( !ExprHasAnyProperty(pExpr, EP_TokenOnly|EP_Reduced) );
  4135         -        ExprSetIrreducible(pExpr);
         4151  +        assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
         4152  +        ExprSetVVAProperty(pExpr, EP_NoReduce);
  4136   4153           pExpr->iAgg = (i16)i;
  4137   4154           pExpr->pAggInfo = pAggInfo;
  4138   4155           return WRC_Prune;
  4139   4156         }else{
  4140   4157           return WRC_Continue;
  4141   4158         }
  4142   4159       }

Changes to src/func.c.

   414    414         }
   415    415         sqlite3_result_text(context, z1, n, sqlite3_free);
   416    416       }
   417    417     }
   418    418   }
   419    419   
   420    420   /*
   421         -** The COALESCE() and IFNULL() functions are implemented as VDBE code so
   422         -** that unused argument values do not have to be computed.  However, we
   423         -** still need some kind of function implementation for this routines in
   424         -** the function table.  That function implementation will never be called
   425         -** so it doesn't matter what the implementation is.  We might as well use
   426         -** the "version()" function as a substitute.
          421  +** Some functions like COALESCE() and IFNULL() and UNLIKELY() are implemented
          422  +** as VDBE code so that unused argument values do not have to be computed.
          423  +** However, we still need some kind of function implementation for this
          424  +** routines in the function table.  The noopFunc macro provides this.
          425  +** noopFunc will never be called so it doesn't matter what the implementation
          426  +** is.  We might as well use the "version()" function as a substitute.
   427    427   */
   428         -#define ifnullFunc versionFunc   /* Substitute function - never called */
          428  +#define noopFunc versionFunc   /* Substitute function - never called */
   429    429   
   430    430   /*
   431    431   ** Implementation of random().  Return a random integer.  
   432    432   */
   433    433   static void randomFunc(
   434    434     sqlite3_context *context,
   435    435     int NotUsed,
................................................................................
  1655   1655       FUNCTION(round,              1, 0, 0, roundFunc        ),
  1656   1656       FUNCTION(round,              2, 0, 0, roundFunc        ),
  1657   1657   #endif
  1658   1658       FUNCTION(upper,              1, 0, 0, upperFunc        ),
  1659   1659       FUNCTION(lower,              1, 0, 0, lowerFunc        ),
  1660   1660       FUNCTION(coalesce,           1, 0, 0, 0                ),
  1661   1661       FUNCTION(coalesce,           0, 0, 0, 0                ),
  1662         -    FUNCTION2(coalesce,         -1, 0, 0, ifnullFunc,  SQLITE_FUNC_COALESCE),
         1662  +    FUNCTION2(coalesce,         -1, 0, 0, noopFunc,  SQLITE_FUNC_COALESCE),
  1663   1663       FUNCTION(hex,                1, 0, 0, hexFunc          ),
  1664         -    FUNCTION2(ifnull,            2, 0, 0, ifnullFunc,  SQLITE_FUNC_COALESCE),
         1664  +    FUNCTION2(ifnull,            2, 0, 0, noopFunc,  SQLITE_FUNC_COALESCE),
         1665  +    FUNCTION2(unlikely,          1, 0, 0, noopFunc,  SQLITE_FUNC_UNLIKELY),
         1666  +    FUNCTION2(likelihood,        2, 0, 0, noopFunc,  SQLITE_FUNC_UNLIKELY),
  1665   1667       FUNCTION(random,             0, 0, 0, randomFunc       ),
  1666   1668       FUNCTION(randomblob,         1, 0, 0, randomBlob       ),
  1667   1669       FUNCTION(nullif,             2, 0, 1, nullifFunc       ),
  1668   1670       FUNCTION(sqlite_version,     0, 0, 0, versionFunc      ),
  1669   1671       FUNCTION(sqlite_source_id,   0, 0, 0, sourceidFunc     ),
  1670   1672       FUNCTION(sqlite_log,         2, 0, 0, errlogFunc       ),
  1671   1673   #ifndef SQLITE_OMIT_COMPILEOPTION_DIAGS

Changes to src/parse.y.

  1077   1077       A.zStart = B.z;
  1078   1078       A.zEnd = &E.z[E.n];
  1079   1079     }
  1080   1080   %endif SQLITE_OMIT_SUBQUERY
  1081   1081   
  1082   1082   /* CASE expressions */
  1083   1083   expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
  1084         -  A.pExpr = sqlite3PExpr(pParse, TK_CASE, X, Z, 0);
         1084  +  A.pExpr = sqlite3PExpr(pParse, TK_CASE, X, 0, 0);
  1085   1085     if( A.pExpr ){
  1086         -    A.pExpr->x.pList = Y;
         1086  +    A.pExpr->x.pList = Z ? sqlite3ExprListAppend(pParse,Y,Z) : Y;
  1087   1087       sqlite3ExprSetHeight(pParse, A.pExpr);
  1088   1088     }else{
  1089   1089       sqlite3ExprListDelete(pParse->db, Y);
         1090  +    sqlite3ExprDelete(pParse->db, Z);
  1090   1091     }
  1091   1092     A.zStart = C.z;
  1092   1093     A.zEnd = &E.z[E.n];
  1093   1094   }
  1094   1095   %type case_exprlist {ExprList*}
  1095   1096   %destructor case_exprlist {sqlite3ExprListDelete(pParse->db, $$);}
  1096   1097   case_exprlist(A) ::= case_exprlist(X) WHEN expr(Y) THEN expr(Z). {

Changes to src/resolve.c.

   103    103     db = pParse->db;
   104    104     pDup = sqlite3ExprDup(db, pOrig, 0);
   105    105     if( pDup==0 ) return;
   106    106     if( pOrig->op!=TK_COLUMN && zType[0]!='G' ){
   107    107       incrAggFunctionDepth(pDup, nSubquery);
   108    108       pDup = sqlite3PExpr(pParse, TK_AS, pDup, 0, 0);
   109    109       if( pDup==0 ) return;
          110  +    ExprSetProperty(pDup, EP_Skip);
   110    111       if( pEList->a[iCol].iAlias==0 ){
   111    112         pEList->a[iCol].iAlias = (u16)(++pParse->nAlias);
   112    113       }
   113    114       pDup->iTable = pEList->a[iCol].iAlias;
   114    115     }
   115    116     if( pExpr->op==TK_COLLATE ){
   116    117       pDup = sqlite3ExprAddCollateString(pParse, pDup, pExpr->u.zToken);
................................................................................
   125    126     */
   126    127     ExprSetProperty(pExpr, EP_Static);
   127    128     sqlite3ExprDelete(db, pExpr);
   128    129     memcpy(pExpr, pDup, sizeof(*pExpr));
   129    130     if( !ExprHasProperty(pExpr, EP_IntValue) && pExpr->u.zToken!=0 ){
   130    131       assert( (pExpr->flags & (EP_Reduced|EP_TokenOnly))==0 );
   131    132       pExpr->u.zToken = sqlite3DbStrDup(db, pExpr->u.zToken);
   132         -    pExpr->flags2 |= EP2_MallocedToken;
          133  +    pExpr->flags |= EP_MemToken;
   133    134     }
   134    135     sqlite3DbFree(db, pDup);
   135    136   }
   136    137   
   137    138   
   138    139   /*
   139    140   ** Return TRUE if the name zCol occurs anywhere in the USING clause.
................................................................................
   225    226     struct SrcList_item *pMatch = 0;  /* The matching pSrcList item */
   226    227     NameContext *pTopNC = pNC;        /* First namecontext in the list */
   227    228     Schema *pSchema = 0;              /* Schema of the expression */
   228    229     int isTrigger = 0;
   229    230   
   230    231     assert( pNC );     /* the name context cannot be NULL. */
   231    232     assert( zCol );    /* The Z in X.Y.Z cannot be NULL */
   232         -  assert( !ExprHasAnyProperty(pExpr, EP_TokenOnly|EP_Reduced) );
          233  +  assert( !ExprHasProperty(pExpr, EP_TokenOnly|EP_Reduced) );
   233    234   
   234    235     /* Initialize the node to no-match */
   235    236     pExpr->iTable = -1;
   236    237     pExpr->pTab = 0;
   237         -  ExprSetIrreducible(pExpr);
          238  +  ExprSetVVAProperty(pExpr, EP_NoReduce);
   238    239   
   239    240     /* Translate the schema name in zDb into a pointer to the corresponding
   240    241     ** schema.  If not found, pSchema will remain NULL and nothing will match
   241    242     ** resulting in an appropriate error message toward the end of this routine
   242    243     */
   243    244     if( zDb ){
   244    245       testcase( pNC->ncFlags & NC_PartIdx );
................................................................................
   566    567       sqlite3ErrorMsg(pParse,"%s prohibited in CHECK constraints", zMsg);
   567    568     }
   568    569   }
   569    570   #else
   570    571   # define notValidCheckConstraint(P,N,M)
   571    572   #endif
   572    573   
          574  +/*
          575  +** Expression p should encode a floating point value between 1.0 and 0.0.
          576  +** Return 1024 times this value.  Or return -1 if p is not a floating point
          577  +** value between 1.0 and 0.0.
          578  +*/
          579  +static int exprProbability(Expr *p){
          580  +  double r = -1.0;
          581  +  if( p->op!=TK_FLOAT ) return -1;
          582  +  sqlite3AtoF(p->u.zToken, &r, sqlite3Strlen30(p->u.zToken), SQLITE_UTF8);
          583  +  assert( r>=0.0 );
          584  +  if( r>1.0 ) return -1;
          585  +  return (int)(r*1000.0);
          586  +}
   573    587   
   574    588   /*
   575    589   ** This routine is callback for sqlite3WalkExpr().
   576    590   **
   577    591   ** Resolve symbolic names into TK_COLUMN operators for the current
   578    592   ** node in the expression tree.  Return 0 to continue the search down
   579    593   ** the tree or 2 to abort the tree walk.
................................................................................
   587    601     Parse *pParse;
   588    602   
   589    603     pNC = pWalker->u.pNC;
   590    604     assert( pNC!=0 );
   591    605     pParse = pNC->pParse;
   592    606     assert( pParse==pWalker->pParse );
   593    607   
   594         -  if( ExprHasAnyProperty(pExpr, EP_Resolved) ) return WRC_Prune;
          608  +  if( ExprHasProperty(pExpr, EP_Resolved) ) return WRC_Prune;
   595    609     ExprSetProperty(pExpr, EP_Resolved);
   596    610   #ifndef NDEBUG
   597    611     if( pNC->pSrcList && pNC->pSrcList->nAlloc>0 ){
   598    612       SrcList *pSrcList = pNC->pSrcList;
   599    613       int i;
   600    614       for(i=0; i<pNC->pSrcList->nSrc; i++){
   601    615         assert( pSrcList->a[i].iCursor>=0 && pSrcList->a[i].iCursor<pParse->nTab);
................................................................................
   679    693           if( pDef==0 ){
   680    694             no_such_func = 1;
   681    695           }else{
   682    696             wrong_num_args = 1;
   683    697           }
   684    698         }else{
   685    699           is_agg = pDef->xFunc==0;
          700  +        if( pDef->funcFlags & SQLITE_FUNC_UNLIKELY ){
          701  +          ExprSetProperty(pExpr, EP_Unlikely|EP_Skip);
          702  +          if( n==2 ){
          703  +            pExpr->iTable = exprProbability(pList->a[1].pExpr);
          704  +            if( pExpr->iTable<0 ){
          705  +              sqlite3ErrorMsg(pParse, "second argument to likelihood() must be a "
          706  +                                      "constant between 0.0 and 1.0");
          707  +              pNC->nErr++;
          708  +            }
          709  +          }else{
          710  +            pExpr->iTable = 62;  /* TUNING:  Default 2nd arg to unlikely() is 0.0625 */
          711  +          }             
          712  +        }
   686    713         }
   687    714   #ifndef SQLITE_OMIT_AUTHORIZATION
   688    715         if( pDef ){
   689    716           auth = sqlite3AuthCheck(pParse, SQLITE_FUNCTION, 0, pDef->zName, 0);
   690    717           if( auth!=SQLITE_OK ){
   691    718             if( auth==SQLITE_DENY ){
   692    719               sqlite3ErrorMsg(pParse, "not authorized to use function: %s",

Changes to src/select.c.

   260    260   
   261    261     pE1 = sqlite3CreateColumnExpr(db, pSrc, iLeft, iColLeft);
   262    262     pE2 = sqlite3CreateColumnExpr(db, pSrc, iRight, iColRight);
   263    263   
   264    264     pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2, 0);
   265    265     if( pEq && isOuterJoin ){
   266    266       ExprSetProperty(pEq, EP_FromJoin);
   267         -    assert( !ExprHasAnyProperty(pEq, EP_TokenOnly|EP_Reduced) );
   268         -    ExprSetIrreducible(pEq);
          267  +    assert( !ExprHasProperty(pEq, EP_TokenOnly|EP_Reduced) );
          268  +    ExprSetVVAProperty(pEq, EP_NoReduce);
   269    269       pEq->iRightJoinTable = (i16)pE2->iTable;
   270    270     }
   271    271     *ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);
   272    272   }
   273    273   
   274    274   /*
   275    275   ** Set the EP_FromJoin property on all terms of the given expression.
................................................................................
   296    296   ** defer the handling of t1.x=5, it will be processed immediately
   297    297   ** after the t1 loop and rows with t1.x!=5 will never appear in
   298    298   ** the output, which is incorrect.
   299    299   */
   300    300   static void setJoinExpr(Expr *p, int iTable){
   301    301     while( p ){
   302    302       ExprSetProperty(p, EP_FromJoin);
   303         -    assert( !ExprHasAnyProperty(p, EP_TokenOnly|EP_Reduced) );
   304         -    ExprSetIrreducible(p);
          303  +    assert( !ExprHasProperty(p, EP_TokenOnly|EP_Reduced) );
          304  +    ExprSetVVAProperty(p, EP_NoReduce);
   305    305       p->iRightJoinTable = (i16)iTable;
   306    306       setJoinExpr(p->pLeft, iTable);
   307    307       p = p->pRight;
   308    308     } 
   309    309   }
   310    310   
   311    311   /*

Changes to src/sqliteInt.h.

  1026   1026   #define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
  1027   1027   #define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
  1028   1028   #define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
  1029   1029   #define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
  1030   1030   #define SQLITE_Transitive     0x0200   /* Transitive constraints */
  1031   1031   #define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
  1032   1032   #define SQLITE_Stat3          0x0800   /* Use the SQLITE_STAT3 table */
         1033  +#define SQLITE_AdjustOutEst   0x1000   /* Adjust output estimates using WHERE */
  1033   1034   #define SQLITE_AllOpts        0xffff   /* All optimizations */
  1034   1035   
  1035   1036   /*
  1036   1037   ** Macros for testing whether or not optimizations are enabled or disabled.
  1037   1038   */
  1038   1039   #ifndef SQLITE_OMIT_BUILTIN_TEST
  1039   1040   #define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)
................................................................................
  1718   1719   ** are contained within the same memory allocation.  Note, however, that
  1719   1720   ** the subtrees in Expr.x.pList or Expr.x.pSelect are always separately
  1720   1721   ** allocated, regardless of whether or not EP_Reduced is set.
  1721   1722   */
  1722   1723   struct Expr {
  1723   1724     u8 op;                 /* Operation performed by this node */
  1724   1725     char affinity;         /* The affinity of the column or 0 if not a column */
  1725         -  u16 flags;             /* Various flags.  EP_* See below */
         1726  +  u32 flags;             /* Various flags.  EP_* See below */
  1726   1727     union {
  1727   1728       char *zToken;          /* Token value. Zero terminated and dequoted */
  1728   1729       int iValue;            /* Non-negative integer value if EP_IntValue */
  1729   1730     } u;
  1730   1731   
  1731   1732     /* If the EP_TokenOnly flag is set in the Expr.flags mask, then no
  1732   1733     ** space is allocated for the fields below this point. An attempt to
  1733   1734     ** access them will result in a segfault or malfunction. 
  1734   1735     *********************************************************************/
  1735   1736   
  1736   1737     Expr *pLeft;           /* Left subnode */
  1737   1738     Expr *pRight;          /* Right subnode */
  1738   1739     union {
  1739         -    ExprList *pList;     /* Function arguments or in "<expr> IN (<expr-list)" */
  1740         -    Select *pSelect;     /* Used for sub-selects and "<expr> IN (<select>)" */
         1740  +    ExprList *pList;     /* op = IN, EXISTS, SELECT, CASE, FUNCTION, BETWEEN */
         1741  +    Select *pSelect;     /* EP_xIsSelect and op = IN, EXISTS, SELECT */
  1741   1742     } x;
  1742   1743   
  1743   1744     /* If the EP_Reduced flag is set in the Expr.flags mask, then no
  1744   1745     ** space is allocated for the fields below this point. An attempt to
  1745   1746     ** access them will result in a segfault or malfunction.
  1746   1747     *********************************************************************/
  1747   1748   
  1748   1749   #if SQLITE_MAX_EXPR_DEPTH>0
  1749   1750     int nHeight;           /* Height of the tree headed by this node */
  1750   1751   #endif
  1751   1752     int iTable;            /* TK_COLUMN: cursor number of table holding column
  1752   1753                            ** TK_REGISTER: register number
  1753         -                         ** TK_TRIGGER: 1 -> new, 0 -> old */
         1754  +                         ** TK_TRIGGER: 1 -> new, 0 -> old
         1755  +                         ** EP_Unlikely:  1000 times likelihood */
  1754   1756     ynVar iColumn;         /* TK_COLUMN: column index.  -1 for rowid.
  1755   1757                            ** TK_VARIABLE: variable number (always >= 1). */
  1756   1758     i16 iAgg;              /* Which entry in pAggInfo->aCol[] or ->aFunc[] */
  1757   1759     i16 iRightJoinTable;   /* If EP_FromJoin, the right table of the join */
  1758         -  u8 flags2;             /* Second set of flags.  EP2_... */
  1759   1760     u8 op2;                /* TK_REGISTER: original value of Expr.op
  1760   1761                            ** TK_COLUMN: the value of p5 for OP_Column
  1761   1762                            ** TK_AGG_FUNCTION: nesting depth */
  1762   1763     AggInfo *pAggInfo;     /* Used by TK_AGG_COLUMN and TK_AGG_FUNCTION */
  1763   1764     Table *pTab;           /* Table for TK_COLUMN expressions. */
  1764   1765   };
  1765   1766   
  1766   1767   /*
  1767   1768   ** The following are the meanings of bits in the Expr.flags field.
  1768   1769   */
  1769         -#define EP_FromJoin   0x0001  /* Originated in ON or USING clause of a join */
  1770         -#define EP_Agg        0x0002  /* Contains one or more aggregate functions */
  1771         -#define EP_Resolved   0x0004  /* IDs have been resolved to COLUMNs */
  1772         -#define EP_Error      0x0008  /* Expression contains one or more errors */
  1773         -#define EP_Distinct   0x0010  /* Aggregate function with DISTINCT keyword */
  1774         -#define EP_VarSelect  0x0020  /* pSelect is correlated, not constant */
  1775         -#define EP_DblQuoted  0x0040  /* token.z was originally in "..." */
  1776         -#define EP_InfixFunc  0x0080  /* True for an infix function: LIKE, GLOB, etc */
  1777         -#define EP_Collate    0x0100  /* Tree contains a TK_COLLATE opeartor */
  1778         -#define EP_FixedDest  0x0200  /* Result needed in a specific register */
  1779         -#define EP_IntValue   0x0400  /* Integer value contained in u.iValue */
  1780         -#define EP_xIsSelect  0x0800  /* x.pSelect is valid (otherwise x.pList is) */
  1781         -#define EP_Hint       0x1000  /* Not used */
  1782         -#define EP_Reduced    0x2000  /* Expr struct is EXPR_REDUCEDSIZE bytes only */
  1783         -#define EP_TokenOnly  0x4000  /* Expr struct is EXPR_TOKENONLYSIZE bytes only */
  1784         -#define EP_Static     0x8000  /* Held in memory not obtained from malloc() */
  1785         -
  1786         -/*
  1787         -** The following are the meanings of bits in the Expr.flags2 field.
  1788         -*/
  1789         -#define EP2_MallocedToken  0x0001  /* Need to sqlite3DbFree() Expr.zToken */
  1790         -#define EP2_Irreducible    0x0002  /* Cannot EXPRDUP_REDUCE this Expr */
  1791         -
  1792         -/*
  1793         -** The pseudo-routine sqlite3ExprSetIrreducible sets the EP2_Irreducible
  1794         -** flag on an expression structure.  This flag is used for VV&A only.  The
  1795         -** routine is implemented as a macro that only works when in debugging mode,
  1796         -** so as not to burden production code.
  1797         -*/
  1798         -#ifdef SQLITE_DEBUG
  1799         -# define ExprSetIrreducible(X)  (X)->flags2 |= EP2_Irreducible
  1800         -#else
  1801         -# define ExprSetIrreducible(X)
  1802         -#endif
         1770  +#define EP_FromJoin  0x000001 /* Originated in ON or USING clause of a join */
         1771  +#define EP_Agg       0x000002 /* Contains one or more aggregate functions */
         1772  +#define EP_Resolved  0x000004 /* IDs have been resolved to COLUMNs */
         1773  +#define EP_Error     0x000008 /* Expression contains one or more errors */
         1774  +#define EP_Distinct  0x000010 /* Aggregate function with DISTINCT keyword */
         1775  +#define EP_VarSelect 0x000020 /* pSelect is correlated, not constant */
         1776  +#define EP_DblQuoted 0x000040 /* token.z was originally in "..." */
         1777  +#define EP_InfixFunc 0x000080 /* True for an infix function: LIKE, GLOB, etc */
         1778  +#define EP_Collate   0x000100 /* Tree contains a TK_COLLATE opeartor */
         1779  +#define EP_FixedDest 0x000200 /* Result needed in a specific register */
         1780  +#define EP_IntValue  0x000400 /* Integer value contained in u.iValue */
         1781  +#define EP_xIsSelect 0x000800 /* x.pSelect is valid (otherwise x.pList is) */
         1782  +#define EP_Skip      0x001000 /* COLLATE, AS, or UNLIKELY */
         1783  +#define EP_Reduced   0x002000 /* Expr struct EXPR_REDUCEDSIZE bytes only */
         1784  +#define EP_TokenOnly 0x004000 /* Expr struct EXPR_TOKENONLYSIZE bytes only */
         1785  +#define EP_Static    0x008000 /* Held in memory not obtained from malloc() */
         1786  +#define EP_MemToken  0x010000 /* Need to sqlite3DbFree() Expr.zToken */
         1787  +#define EP_NoReduce  0x020000 /* Cannot EXPRDUP_REDUCE this Expr */
         1788  +#define EP_Unlikely  0x040000 /* unlikely() or likelihood() function */
  1803   1789   
  1804   1790   /*
  1805   1791   ** These macros can be used to test, set, or clear bits in the 
  1806   1792   ** Expr.flags field.
  1807   1793   */
  1808         -#define ExprHasProperty(E,P)     (((E)->flags&(P))==(P))
  1809         -#define ExprHasAnyProperty(E,P)  (((E)->flags&(P))!=0)
         1794  +#define ExprHasProperty(E,P)     (((E)->flags&(P))!=0)
         1795  +#define ExprHasAllProperty(E,P)  (((E)->flags&(P))==(P))
  1810   1796   #define ExprSetProperty(E,P)     (E)->flags|=(P)
  1811   1797   #define ExprClearProperty(E,P)   (E)->flags&=~(P)
         1798  +
         1799  +/* The ExprSetVVAProperty() macro is used for Verification, Validation,
         1800  +** and Accreditation only.  It works like ExprSetProperty() during VVA
         1801  +** processes but is a no-op for delivery.
         1802  +*/
         1803  +#ifdef SQLITE_DEBUG
         1804  +# define ExprSetVVAProperty(E,P)  (E)->flags|=(P)
         1805  +#else
         1806  +# define ExprSetVVAProperty(E,P)
         1807  +#endif
  1812   1808   
  1813   1809   /*
  1814   1810   ** Macros to determine the number of bytes required by a normal Expr 
  1815   1811   ** struct, an Expr struct with the EP_Reduced flag set in Expr.flags 
  1816   1812   ** and an Expr struct with the EP_TokenOnly flag set.
  1817   1813   */
  1818   1814   #define EXPR_FULLSIZE           sizeof(Expr)           /* Full size */

Changes to src/walker.c.

    39     39   int sqlite3WalkExpr(Walker *pWalker, Expr *pExpr){
    40     40     int rc;
    41     41     if( pExpr==0 ) return WRC_Continue;
    42     42     testcase( ExprHasProperty(pExpr, EP_TokenOnly) );
    43     43     testcase( ExprHasProperty(pExpr, EP_Reduced) );
    44     44     rc = pWalker->xExprCallback(pWalker, pExpr);
    45     45     if( rc==WRC_Continue
    46         -              && !ExprHasAnyProperty(pExpr,EP_TokenOnly) ){
           46  +              && !ExprHasProperty(pExpr,EP_TokenOnly) ){
    47     47       if( sqlite3WalkExpr(pWalker, pExpr->pLeft) ) return WRC_Abort;
    48     48       if( sqlite3WalkExpr(pWalker, pExpr->pRight) ) return WRC_Abort;
    49     49       if( ExprHasProperty(pExpr, EP_xIsSelect) ){
    50     50         if( sqlite3WalkSelect(pWalker, pExpr->x.pSelect) ) return WRC_Abort;
    51     51       }else{
    52     52         if( sqlite3WalkExprList(pWalker, pExpr->x.pList) ) return WRC_Abort;
    53     53       }

Changes to src/where.c.

    48     48   typedef struct WhereOrCost WhereOrCost;
    49     49   typedef struct WhereOrSet WhereOrSet;
    50     50   
    51     51   /*
    52     52   ** Cost X is tracked as 10*log2(X) stored in a 16-bit integer.  The
    53     53   ** maximum cost for ordinary tables is 64*(2**63) which becomes 6900.
    54     54   ** (Virtual tables can return a larger cost, but let's assume they do not.)
    55         -** So all costs can be stored in a 16-bit unsigned integer without risk
           55  +** So all costs can be stored in a 16-bit integer without risk
    56     56   ** of overflow.
    57     57   **
    58     58   ** Costs are estimates, so no effort is made to compute 10*log2(X) exactly.
    59         -** Instead, a close estimate is used.  Any value of X<=1 is stored as 0.
    60         -** X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.
           59  +** Instead, a close estimate is used.  Any value of X=1 is stored as 0.
           60  +** X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.  Negative values are allowed.
           61  +** A WhereCost of -10 means 0.5.  WhereCost of -20 means 0.25.  And so forth.
    61     62   **
    62     63   ** The tool/wherecosttest.c source file implements a command-line program
    63     64   ** that will convert WhereCosts to integers, convert integers to WhereCosts
    64     65   ** and do addition and multiplication on WhereCost values.  The wherecosttest
    65     66   ** command-line program is a useful utility to have around when working with
    66     67   ** this module.
    67     68   */
    68         -typedef unsigned short int WhereCost;
           69  +typedef short int WhereCost;
    69     70   
    70     71   /*
    71     72   ** This object contains information needed to implement a single nested
    72     73   ** loop in WHERE clause.
    73     74   **
    74     75   ** Contrast this object with WhereLoop.  This object describes the
    75     76   ** implementation of the loop.  WhereLoop describes the algorithm.
................................................................................
   265    266     int iParent;            /* Disable pWC->a[iParent] when this term disabled */
   266    267     int leftCursor;         /* Cursor number of X in "X <op> <expr>" */
   267    268     union {
   268    269       int leftColumn;         /* Column number of X in "X <op> <expr>" */
   269    270       WhereOrInfo *pOrInfo;   /* Extra information if (eOperator & WO_OR)!=0 */
   270    271       WhereAndInfo *pAndInfo; /* Extra information if (eOperator& WO_AND)!=0 */
   271    272     } u;
          273  +  WhereCost truthProb;    /* Probability of truth for this expression */
   272    274     u16 eOperator;          /* A WO_xx value describing <op> */
   273    275     u8 wtFlags;             /* TERM_xxx bit flags.  See below */
   274    276     u8 nChild;              /* Number of children that must disable us */
   275    277     WhereClause *pWC;       /* The clause this term is part of */
   276    278     Bitmask prereqRight;    /* Bitmask of tables used by pExpr->pRight */
   277    279     Bitmask prereqAll;      /* Bitmask of tables referenced by pExpr */
   278    280   };
................................................................................
   639    641       }
   640    642     }
   641    643     if( pWC->a!=pWC->aStatic ){
   642    644       sqlite3DbFree(db, pWC->a);
   643    645     }
   644    646   }
   645    647   
          648  +/* Forward declaration */
          649  +static WhereCost whereCost(tRowcnt x);
          650  +
   646    651   /*
   647    652   ** Add a single new WhereTerm entry to the WhereClause object pWC.
   648    653   ** The new WhereTerm object is constructed from Expr p and with wtFlags.
   649    654   ** The index in pWC->a[] of the new WhereTerm is returned on success.
   650    655   ** 0 is returned if the new WhereTerm could not be added due to a memory
   651    656   ** allocation error.  The memory allocation failure will be recorded in
   652    657   ** the db->mallocFailed flag so that higher-level functions can detect it.
................................................................................
   680    685       memcpy(pWC->a, pOld, sizeof(pWC->a[0])*pWC->nTerm);
   681    686       if( pOld!=pWC->aStatic ){
   682    687         sqlite3DbFree(db, pOld);
   683    688       }
   684    689       pWC->nSlot = sqlite3DbMallocSize(db, pWC->a)/sizeof(pWC->a[0]);
   685    690     }
   686    691     pTerm = &pWC->a[idx = pWC->nTerm++];
          692  +  if( p && ExprHasProperty(p, EP_Unlikely) ){
          693  +    pTerm->truthProb = whereCost(p->iTable) - 99;
          694  +  }else{
          695  +    pTerm->truthProb = -1;
          696  +  }
   687    697     pTerm->pExpr = sqlite3ExprSkipCollate(p);
   688    698     pTerm->wtFlags = wtFlags;
   689    699     pTerm->pWC = pWC;
   690    700     pTerm->iParent = -1;
   691    701     return idx;
   692    702   }
   693    703   
................................................................................
  2541   2551     WhereLoopBuilder *pBuilder,
  2542   2552     WhereTerm *pLower,   /* Lower bound on the range. ex: "x>123" Might be NULL */
  2543   2553     WhereTerm *pUpper,   /* Upper bound on the range. ex: "x<455" Might be NULL */
  2544   2554     WhereCost *pnOut     /* IN/OUT: Number of rows visited */
  2545   2555   ){
  2546   2556     int rc = SQLITE_OK;
  2547   2557     int nOut = (int)*pnOut;
         2558  +  WhereCost nNew;
  2548   2559   
  2549   2560   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  2550   2561     Index *p = pBuilder->pNew->u.btree.pIndex;
  2551   2562     int nEq = pBuilder->pNew->u.btree.nEq;
  2552   2563   
  2553   2564     if( p->nSample>0
  2554   2565      && nEq==pBuilder->nRecValid
................................................................................
  2603   2614         assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 );
  2604   2615         rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
  2605   2616         if( rc==SQLITE_OK && bOk ){
  2606   2617           tRowcnt iNew;
  2607   2618           whereKeyStats(pParse, p, pRec, 0, a);
  2608   2619           iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0);
  2609   2620           if( iNew>iLower ) iLower = iNew;
         2621  +        nOut--;
  2610   2622         }
  2611   2623       }
  2612   2624   
  2613   2625       /* If possible, improve on the iUpper estimate using ($P:$U). */
  2614   2626       if( pUpper ){
  2615   2627         int bOk;                    /* True if value is extracted from pExpr */
  2616   2628         Expr *pExpr = pUpper->pExpr->pRight;
................................................................................
  2617   2629         assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 );
  2618   2630         rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk);
  2619   2631         if( rc==SQLITE_OK && bOk ){
  2620   2632           tRowcnt iNew;
  2621   2633           whereKeyStats(pParse, p, pRec, 1, a);
  2622   2634           iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0);
  2623   2635           if( iNew<iUpper ) iUpper = iNew;
         2636  +        nOut--;
  2624   2637         }
  2625   2638       }
  2626   2639   
  2627   2640       pBuilder->pRec = pRec;
  2628   2641       if( rc==SQLITE_OK ){
  2629         -      WhereCost nNew;
  2630   2642         if( iUpper>iLower ){
  2631   2643           nNew = whereCost(iUpper - iLower);
  2632   2644         }else{
  2633   2645           nNew = 10;        assert( 10==whereCost(2) );
  2634   2646         }
  2635   2647         if( nNew<nOut ){
  2636   2648           nOut = nNew;
................................................................................
  2644   2656   #else
  2645   2657     UNUSED_PARAMETER(pParse);
  2646   2658     UNUSED_PARAMETER(pBuilder);
  2647   2659   #endif
  2648   2660     assert( pLower || pUpper );
  2649   2661     /* TUNING:  Each inequality constraint reduces the search space 4-fold.
  2650   2662     ** A BETWEEN operator, therefore, reduces the search space 16-fold */
         2663  +  nNew = nOut;
  2651   2664     if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
  2652         -    nOut -= 20;        assert( 20==whereCost(4) );
         2665  +    nNew -= 20;        assert( 20==whereCost(4) );
         2666  +    nOut--;
  2653   2667     }
  2654   2668     if( pUpper ){
  2655         -    nOut -= 20;        assert( 20==whereCost(4) );
         2669  +    nNew -= 20;        assert( 20==whereCost(4) );
         2670  +    nOut--;
  2656   2671     }
  2657         -  if( nOut<10 ) nOut = 10;
         2672  +  if( nNew<10 ) nNew = 10;
         2673  +  if( nNew<nOut ) nOut = nNew;
  2658   2674     *pnOut = (WhereCost)nOut;
  2659   2675     return rc;
  2660   2676   }
  2661   2677   
  2662   2678   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  2663   2679   /*
  2664   2680   ** Estimate the number of rows that will be returned based on
................................................................................
  4185   4201       ){
  4186   4202         /* This branch taken when p is equal or better than pTemplate in 
  4187   4203         ** all of (1) dependencies (2) setup-cost, (3) run-cost, and
  4188   4204         ** (4) number of output rows. */
  4189   4205         assert( p->rSetup==pTemplate->rSetup );
  4190   4206         if( p->prereq==pTemplate->prereq
  4191   4207          && p->nLTerm<pTemplate->nLTerm
  4192         -       && (p->wsFlags & WHERE_INDEXED)!=0
  4193         -       && (pTemplate->wsFlags & WHERE_INDEXED)!=0
  4194         -       && p->u.btree.pIndex==pTemplate->u.btree.pIndex
         4208  +       && (p->wsFlags & pTemplate->wsFlags & WHERE_INDEXED)!=0
         4209  +       && (p->u.btree.pIndex==pTemplate->u.btree.pIndex
         4210  +          || pTemplate->rRun+p->nLTerm<=p->rRun+pTemplate->nLTerm)
  4195   4211         ){
  4196   4212           /* Overwrite an existing WhereLoop with an similar one that uses
  4197   4213           ** more terms of the index */
  4198   4214           pNext = p->pNextLoop;
  4199   4215           break;
  4200   4216         }else{
  4201   4217           /* pTemplate is not helpful.
................................................................................
  4202   4218           ** Return without changing or adding anything */
  4203   4219           goto whereLoopInsert_noop;
  4204   4220         }
  4205   4221       }
  4206   4222       if( (p->prereq & pTemplate->prereq)==pTemplate->prereq
  4207   4223        && p->rRun>=pTemplate->rRun
  4208   4224        && p->nOut>=pTemplate->nOut
  4209         -     && ALWAYS(p->rSetup>=pTemplate->rSetup) /* See SETUP-INVARIANT above */
  4210   4225       ){
  4211   4226         /* Overwrite an existing WhereLoop with a better one: one that is
  4212   4227         ** better at one of (1) dependencies, (2) setup-cost, (3) run-cost
  4213   4228         ** or (4) number of output rows, and is no worse in any of those
  4214   4229         ** categories. */
         4230  +      assert( p->rSetup>=pTemplate->rSetup ); /* SETUP-INVARIANT above */
  4215   4231         pNext = p->pNextLoop;
  4216   4232         break;
  4217   4233       }
  4218   4234     }
  4219   4235   
  4220   4236     /* If we reach this point it means that either p[] should be overwritten
  4221   4237     ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new
................................................................................
  4253   4269     if( sqlite3WhereTrace & 0x8 ){
  4254   4270       sqlite3DebugPrintf("ins-noop: ");
  4255   4271       whereLoopPrint(pTemplate, pWInfo->pTabList);
  4256   4272     }
  4257   4273   #endif
  4258   4274     return SQLITE_OK;  
  4259   4275   }
         4276  +
         4277  +/*
         4278  +** Adjust the WhereLoop.nOut value downward to account for terms of the
         4279  +** WHERE clause that reference the loop but which are not used by an
         4280  +** index.
         4281  +**
         4282  +** In the current implementation, the first extra WHERE clause term reduces
         4283  +** the number of output rows by a factor of 10 and each additional term
         4284  +** reduces the number of output rows by sqrt(2).
         4285  +*/
         4286  +static void whereLoopOutputAdjust(WhereClause *pWC, WhereLoop *pLoop, int iCur){
         4287  +  WhereTerm *pTerm, *pX;
         4288  +  Bitmask notAllowed = ~(pLoop->prereq|pLoop->maskSelf);
         4289  +  int i, j;
         4290  +
         4291  +  if( !OptimizationEnabled(pWC->pWInfo->pParse->db, SQLITE_AdjustOutEst) ){
         4292  +    return;
         4293  +  }
         4294  +  for(i=pWC->nTerm, pTerm=pWC->a; i>0; i--, pTerm++){
         4295  +    if( (pTerm->wtFlags & TERM_VIRTUAL)!=0 ) break;
         4296  +    if( (pTerm->prereqAll & pLoop->maskSelf)==0 ) continue;
         4297  +    if( (pTerm->prereqAll & notAllowed)!=0 ) continue;
         4298  +    for(j=pLoop->nLTerm-1; j>=0; j--){
         4299  +      pX = pLoop->aLTerm[j];
         4300  +      if( pX==pTerm ) break;
         4301  +      if( pX->iParent>=0 && (&pWC->a[pX->iParent])==pTerm ) break;
         4302  +    }
         4303  +    if( j<0 ) pLoop->nOut += pTerm->truthProb;
         4304  +  }
         4305  +}
  4260   4306   
  4261   4307   /*
  4262   4308   ** We have so far matched pBuilder->pNew->u.btree.nEq terms of the index pIndex.
  4263   4309   ** Try to match one more.
  4264   4310   **
  4265   4311   ** If pProbe->tnum==0, that means pIndex is a fake index used for the
  4266   4312   ** INTEGER PRIMARY KEY.
................................................................................
  4420   4466       if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
  4421   4467         /* Each row involves a step of the index, then a binary search of
  4422   4468         ** the main table */
  4423   4469         pNew->rRun =  whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10);
  4424   4470       }
  4425   4471       /* Step cost for each output row */
  4426   4472       pNew->rRun = whereCostAdd(pNew->rRun, pNew->nOut);
  4427         -    /* TBD: Adjust nOut for additional constraints */
         4473  +    whereLoopOutputAdjust(pBuilder->pWC, pNew, pSrc->iCursor);
  4428   4474       rc = whereLoopInsert(pBuilder, pNew);
  4429   4475       if( (pNew->wsFlags & WHERE_TOP_LIMIT)==0
  4430   4476        && pNew->u.btree.nEq<(pProbe->nColumn + (pProbe->zName!=0))
  4431   4477       ){
  4432   4478         whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul+nIn);
  4433   4479       }
  4434   4480       pNew->nOut = saved_nOut;
................................................................................
  4624   4670         pNew->iSortIdx = b ? iSortIdx : 0;
  4625   4671         /* TUNING: Cost of full table scan is 3*(N + log2(N)).
  4626   4672         **  +  The extra 3 factor is to encourage the use of indexed lookups
  4627   4673         **     over full scans.  A smaller constant 2 is used for covering
  4628   4674         **     index scans so that a covering index scan will be favored over
  4629   4675         **     a table scan. */
  4630   4676         pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
         4677  +      whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
  4631   4678         rc = whereLoopInsert(pBuilder, pNew);
         4679  +      pNew->nOut = rSize;
  4632   4680         if( rc ) break;
  4633   4681       }else{
  4634   4682         Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
  4635   4683         pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
  4636   4684   
  4637   4685         /* Full scan via index */
  4638   4686         if( b
................................................................................
  4656   4704             pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b;
  4657   4705           }else{
  4658   4706             assert( b!=0 ); 
  4659   4707             /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
  4660   4708             ** which we will simplify to just N*log2(N) */
  4661   4709             pNew->rRun = rSize + rLogSize;
  4662   4710           }
         4711  +        whereLoopOutputAdjust(pWC, pNew, pSrc->iCursor);
  4663   4712           rc = whereLoopInsert(pBuilder, pNew);
         4713  +        pNew->nOut = rSize;
  4664   4714           if( rc ) break;
  4665   4715         }
  4666   4716       }
  4667   4717   
  4668   4718       rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);
  4669   4719   #ifdef SQLITE_ENABLE_STAT3_OR_STAT4
  4670   4720       sqlite3Stat4ProbeFree(pBuilder->pRec);
................................................................................
  5263   5313   static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
  5264   5314     int mxChoice;             /* Maximum number of simultaneous paths tracked */
  5265   5315     int nLoop;                /* Number of terms in the join */
  5266   5316     Parse *pParse;            /* Parsing context */
  5267   5317     sqlite3 *db;              /* The database connection */
  5268   5318     int iLoop;                /* Loop counter over the terms of the join */
  5269   5319     int ii, jj;               /* Loop counters */
  5270         -  WhereCost rCost;             /* Cost of a path */
  5271         -  WhereCost mxCost = 0;        /* Maximum cost of a set of paths */
  5272         -  WhereCost rSortCost;         /* Cost to do a sort */
         5320  +  int mxI = 0;              /* Index of next entry to replace */
         5321  +  WhereCost rCost;          /* Cost of a path */
         5322  +  WhereCost nOut;           /* Number of outputs */
         5323  +  WhereCost mxCost = 0;     /* Maximum cost of a set of paths */
         5324  +  WhereCost mxOut = 0;      /* Maximum nOut value on the set of paths */
         5325  +  WhereCost rSortCost;      /* Cost to do a sort */
  5273   5326     int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
  5274   5327     WherePath *aFrom;         /* All nFrom paths at the previous level */
  5275   5328     WherePath *aTo;           /* The nTo best paths at the current level */
  5276   5329     WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  5277   5330     WherePath *pTo;           /* An element of aTo[] that we are working on */
  5278   5331     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  5279   5332     WhereLoop **pX;           /* Used to divy up the pSpace memory */
................................................................................
  5334   5387           u8 isOrdered = pFrom->isOrdered;
  5335   5388           if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue;
  5336   5389           if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue;
  5337   5390           /* At this point, pWLoop is a candidate to be the next loop. 
  5338   5391           ** Compute its cost */
  5339   5392           rCost = whereCostAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow);
  5340   5393           rCost = whereCostAdd(rCost, pFrom->rCost);
         5394  +        nOut = pFrom->nRow + pWLoop->nOut;
  5341   5395           maskNew = pFrom->maskLoop | pWLoop->maskSelf;
  5342   5396           if( !isOrderedValid ){
  5343   5397             switch( wherePathSatisfiesOrderBy(pWInfo,
  5344   5398                          pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags,
  5345   5399                          iLoop, pWLoop, &revMask) ){
  5346   5400               case 1:  /* Yes.  pFrom+pWLoop does satisfy the ORDER BY clause */
  5347   5401                 isOrdered = 1;
................................................................................
  5356   5410                 break;
  5357   5411             }
  5358   5412           }else{
  5359   5413             revMask = pFrom->revLoop;
  5360   5414           }
  5361   5415           /* Check to see if pWLoop should be added to the mxChoice best so far */
  5362   5416           for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){
  5363         -          if( pTo->maskLoop==maskNew && pTo->isOrderedValid==isOrderedValid ){
         5417  +          if( pTo->maskLoop==maskNew
         5418  +           && pTo->isOrderedValid==isOrderedValid
         5419  +           && ((pTo->rCost<=rCost && pTo->nRow<=nOut) ||
         5420  +                (pTo->rCost>=rCost && pTo->nRow>=nOut))
         5421  +          ){
  5364   5422               testcase( jj==nTo-1 );
  5365   5423               break;
  5366   5424             }
  5367   5425           }
  5368   5426           if( jj>=nTo ){
  5369   5427             if( nTo>=mxChoice && rCost>=mxCost ){
  5370   5428   #ifdef WHERETRACE_ENABLED
  5371   5429               if( sqlite3WhereTrace&0x4 ){
  5372         -              sqlite3DebugPrintf("Skip   %s cost=%3d order=%c\n",
  5373         -                  wherePathName(pFrom, iLoop, pWLoop), rCost,
         5430  +              sqlite3DebugPrintf("Skip   %s cost=%-3d,%3d order=%c\n",
         5431  +                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5374   5432                     isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
  5375   5433               }
  5376   5434   #endif
  5377   5435               continue;
  5378   5436             }
  5379   5437             /* Add a new Path to the aTo[] set */
  5380   5438             if( nTo<mxChoice ){
  5381   5439               /* Increase the size of the aTo set by one */
  5382   5440               jj = nTo++;
  5383   5441             }else{
  5384   5442               /* New path replaces the prior worst to keep count below mxChoice */
  5385         -            for(jj=nTo-1; aTo[jj].rCost<mxCost; jj--){ assert(jj>0); }
         5443  +            jj = mxI;
  5386   5444             }
  5387   5445             pTo = &aTo[jj];
  5388   5446   #ifdef WHERETRACE_ENABLED
  5389   5447             if( sqlite3WhereTrace&0x4 ){
  5390         -            sqlite3DebugPrintf("New    %s cost=%-3d order=%c\n",
  5391         -                wherePathName(pFrom, iLoop, pWLoop), rCost,
         5448  +            sqlite3DebugPrintf("New    %s cost=%-3d,%3d order=%c\n",
         5449  +                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5392   5450                   isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
  5393   5451             }
  5394   5452   #endif
  5395   5453           }else{
  5396         -          if( pTo->rCost<=rCost ){
         5454  +          if( pTo->rCost<=rCost && pTo->nRow<=nOut ){
  5397   5455   #ifdef WHERETRACE_ENABLED
  5398   5456               if( sqlite3WhereTrace&0x4 ){
  5399   5457                 sqlite3DebugPrintf(
  5400         -                  "Skip   %s cost=%-3d order=%c",
  5401         -                  wherePathName(pFrom, iLoop, pWLoop), rCost,
         5458  +                  "Skip   %s cost=%-3d,%3d order=%c",
         5459  +                  wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5402   5460                     isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
  5403         -              sqlite3DebugPrintf("   vs %s cost=%-3d order=%c\n",
  5404         -                  wherePathName(pTo, iLoop+1, 0), pTo->rCost,
         5461  +              sqlite3DebugPrintf("   vs %s cost=%-3d,%d order=%c\n",
         5462  +                  wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  5405   5463                     pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
  5406   5464               }
  5407   5465   #endif
  5408   5466               testcase( pTo->rCost==rCost );
  5409   5467               continue;
  5410   5468             }
  5411   5469             testcase( pTo->rCost==rCost+1 );
  5412   5470             /* A new and better score for a previously created equivalent path */
  5413   5471   #ifdef WHERETRACE_ENABLED
  5414   5472             if( sqlite3WhereTrace&0x4 ){
  5415   5473               sqlite3DebugPrintf(
  5416         -                "Update %s cost=%-3d order=%c",
  5417         -                wherePathName(pFrom, iLoop, pWLoop), rCost,
         5474  +                "Update %s cost=%-3d,%3d order=%c",
         5475  +                wherePathName(pFrom, iLoop, pWLoop), rCost, nOut,
  5418   5476                   isOrderedValid ? (isOrdered ? 'Y' : 'N') : '?');
  5419         -            sqlite3DebugPrintf("  was %s cost=%-3d order=%c\n",
  5420         -                wherePathName(pTo, iLoop+1, 0), pTo->rCost,
         5477  +            sqlite3DebugPrintf("  was %s cost=%-3d,%3d order=%c\n",
         5478  +                wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow,
  5421   5479                   pTo->isOrderedValid ? (pTo->isOrdered ? 'Y' : 'N') : '?');
  5422   5480             }
  5423   5481   #endif
  5424   5482           }
  5425   5483           /* pWLoop is a winner.  Add it to the set of best so far */
  5426   5484           pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf;
  5427   5485           pTo->revLoop = revMask;
  5428         -        pTo->nRow = pFrom->nRow + pWLoop->nOut;
         5486  +        pTo->nRow = nOut;
  5429   5487           pTo->rCost = rCost;
  5430   5488           pTo->isOrderedValid = isOrderedValid;
  5431   5489           pTo->isOrdered = isOrdered;
  5432   5490           memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop);
  5433   5491           pTo->aLoop[iLoop] = pWLoop;
  5434   5492           if( nTo>=mxChoice ){
         5493  +          mxI = 0;
  5435   5494             mxCost = aTo[0].rCost;
         5495  +          mxOut = aTo[0].nRow;
  5436   5496             for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){
  5437         -            if( pTo->rCost>mxCost ) mxCost = pTo->rCost;
         5497  +            if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->nRow>mxOut) ){
         5498  +              mxCost = pTo->rCost;
         5499  +              mxOut = pTo->nRow;
         5500  +              mxI = jj;
         5501  +            }
  5438   5502             }
  5439   5503           }
  5440   5504         }
  5441   5505       }
  5442   5506   
  5443   5507   #ifdef WHERETRACE_ENABLED
  5444   5508       if( sqlite3WhereTrace>=2 ){
................................................................................
  5467   5531       sqlite3ErrorMsg(pParse, "no query solution");
  5468   5532       sqlite3DbFree(db, pSpace);
  5469   5533       return SQLITE_ERROR;
  5470   5534     }
  5471   5535     
  5472   5536     /* Find the lowest cost path.  pFrom will be left pointing to that path */
  5473   5537     pFrom = aFrom;
  5474         -  assert( nFrom==1 );
  5475         -#if 0 /* The following is needed if nFrom is ever more than 1 */
  5476   5538     for(ii=1; ii<nFrom; ii++){
  5477   5539       if( pFrom->rCost>aFrom[ii].rCost ) pFrom = &aFrom[ii];
  5478   5540     }
  5479         -#endif
  5480   5541     assert( pWInfo->nLevel==nLoop );
  5481   5542     /* Load the lowest cost path into pWInfo */
  5482   5543     for(iLoop=0; iLoop<nLoop; iLoop++){
  5483   5544       WhereLevel *pLevel = pWInfo->a + iLoop;
  5484   5545       pLevel->pWLoop = pWLoop = pFrom->aLoop[iLoop];
  5485   5546       pLevel->iFrom = pWLoop->iTab;
  5486   5547       pLevel->iTabCur = pWInfo->pTabList->a[pLevel->iFrom].iCursor;

Changes to test/analyze9.test.

   841    841     SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
   842    842   } {/USING INDEX i1/}
   843    843   do_eqp_test 17.3 {
   844    844     SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;
   845    845   } {/USING INDEX i1/}
   846    846   
   847    847   do_execsql_test 17.4 {
   848         -  CREATE INDEX i2 ON t1(c);
          848  +  CREATE INDEX i2 ON t1(c, d);
   849    849     ANALYZE main.i2;
   850    850   }
   851    851   do_eqp_test 17.5 {
   852    852     SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=10 AND c=10;
   853    853   } {/USING INDEX i1/}
   854    854   do_eqp_test 17.6 {
   855    855     SELECT * FROM t1 WHERE d IS NOT NULL AND a=0 AND b=0 AND c=10;

Added test/whereG.test.

            1  +# 2013-09-05
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +# 
           12  +# Test cases for query planning decisions and the unlikely() and
           13  +# likelihood() functions.
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +do_execsql_test whereG-1.0 {
           19  +  CREATE TABLE composer(
           20  +    cid INTEGER PRIMARY KEY,
           21  +    cname TEXT
           22  +  );
           23  +  CREATE TABLE album(
           24  +    aid INTEGER PRIMARY KEY,
           25  +    aname TEXT
           26  +  );
           27  +  CREATE TABLE track(
           28  +    tid INTEGER PRIMARY KEY,
           29  +    cid INTEGER REFERENCES composer,
           30  +    aid INTEGER REFERENCES album,
           31  +    title TEXT
           32  +  );
           33  +  CREATE INDEX track_i1 ON track(cid);
           34  +  CREATE INDEX track_i2 ON track(aid);
           35  +  INSERT INTO composer VALUES(1, 'W. A. Mozart');
           36  +  INSERT INTO composer VALUES(2, 'Beethoven');
           37  +  INSERT INTO composer VALUES(3, 'Thomas Tallis');
           38  +  INSERT INTO composer VALUES(4, 'Joseph Hayden');
           39  +  INSERT INTO composer VALUES(5, 'Thomas Weelkes');
           40  +  INSERT INTO composer VALUES(6, 'J. S. Bach');
           41  +  INSERT INTO composer VALUES(7, 'Orlando Gibbons');
           42  +  INSERT INTO composer VALUES(8, 'Josquin des Prés');
           43  +  INSERT INTO composer VALUES(9, 'Byrd');
           44  +  INSERT INTO composer VALUES(10, 'Francis Poulenc');
           45  +  INSERT INTO composer VALUES(11, 'Mendelsshon');
           46  +  INSERT INTO composer VALUES(12, 'Zoltán Kodály');
           47  +  INSERT INTO composer VALUES(13, 'Handel');
           48  +  INSERT INTO album VALUES(100, 'Kodály: Missa Brevis');
           49  +  INSERT INTO album VALUES(101, 'Messiah');
           50  +  INSERT INTO album VALUES(102, 'Missa Brevis in D-, K.65');
           51  +  INSERT INTO album VALUES(103, 'The complete English anthems');
           52  +  INSERT INTO album VALUES(104, 'Mass in B Minor, BWV 232');
           53  +  INSERT INTO track VALUES(10005, 12, 100, 'Sanctus');
           54  +  INSERT INTO track VALUES(10007, 12, 100, 'Agnus Dei');
           55  +  INSERT INTO track VALUES(10115, 13, 101, 'Surely He Hath Borne Our Griefs');
           56  +  INSERT INTO track VALUES(10129, 13, 101, 'Since By Man Came Death');
           57  +  INSERT INTO track VALUES(10206, 1, 102, 'Agnus Dei');
           58  +  INSERT INTO track VALUES(10301, 3, 103, 'If Ye Love Me');
           59  +  INSERT INTO track VALUES(10402, 6, 104, 'Domine Deus');
           60  +  INSERT INTO track VALUES(10403, 6, 104, 'Qui tollis');
           61  +} {}
           62  +do_eqp_test whereG-1.1 {
           63  +  SELECT DISTINCT aname
           64  +    FROM album, composer, track
           65  +   WHERE unlikely(cname LIKE '%bach%')
           66  +     AND composer.cid=track.cid
           67  +     AND album.aid=track.aid;
           68  +} {/.*composer.*track.*album.*/}
           69  +do_execsql_test whereG-1.2 {
           70  +  SELECT DISTINCT aname
           71  +    FROM album, composer, track
           72  +   WHERE unlikely(cname LIKE '%bach%')
           73  +     AND composer.cid=track.cid
           74  +     AND album.aid=track.aid;
           75  +} {{Mass in B Minor, BWV 232}}
           76  +
           77  +do_eqp_test whereG-1.3 {
           78  +  SELECT DISTINCT aname
           79  +    FROM album, composer, track
           80  +   WHERE likelihood(cname LIKE '%bach%', 0.5)
           81  +     AND composer.cid=track.cid
           82  +     AND album.aid=track.aid;
           83  +} {/.*track.*composer.*album.*/}
           84  +do_execsql_test whereG-1.4 {
           85  +  SELECT DISTINCT aname
           86  +    FROM album, composer, track
           87  +   WHERE likelihood(cname LIKE '%bach%', 0.5)
           88  +     AND composer.cid=track.cid
           89  +     AND album.aid=track.aid;
           90  +} {{Mass in B Minor, BWV 232}}
           91  +
           92  +do_eqp_test whereG-1.5 {
           93  +  SELECT DISTINCT aname
           94  +    FROM album, composer, track
           95  +   WHERE cname LIKE '%bach%'
           96  +     AND composer.cid=track.cid
           97  +     AND album.aid=track.aid;
           98  +} {/.*track.*composer.*album.*/}
           99  +do_execsql_test whereG-1.6 {
          100  +  SELECT DISTINCT aname
          101  +    FROM album, composer, track
          102  +   WHERE cname LIKE '%bach%'
          103  +     AND composer.cid=track.cid
          104  +     AND album.aid=track.aid;
          105  +} {{Mass in B Minor, BWV 232}}
          106  +
          107  +do_eqp_test whereG-1.7 {
          108  +  SELECT DISTINCT aname
          109  +    FROM album, composer, track
          110  +   WHERE cname LIKE '%bach%'
          111  +     AND unlikely(composer.cid=track.cid)
          112  +     AND unlikely(album.aid=track.aid);
          113  +} {/.*track.*composer.*album.*/}
          114  +do_execsql_test whereG-1.8 {
          115  +  SELECT DISTINCT aname
          116  +    FROM album, composer, track
          117  +   WHERE cname LIKE '%bach%'
          118  +     AND unlikely(composer.cid=track.cid)
          119  +     AND unlikely(album.aid=track.aid);
          120  +} {{Mass in B Minor, BWV 232}}
          121  +
          122  +do_test whereG-2.1 {
          123  +  catchsql {
          124  +    SELECT DISTINCT aname
          125  +      FROM album, composer, track
          126  +     WHERE likelihood(cname LIKE '%bach%', -0.01)
          127  +       AND composer.cid=track.cid
          128  +       AND album.aid=track.aid;
          129  +  }
          130  +} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
          131  +do_test whereG-2.2 {
          132  +  catchsql {
          133  +    SELECT DISTINCT aname
          134  +      FROM album, composer, track
          135  +     WHERE likelihood(cname LIKE '%bach%', 1.01)
          136  +       AND composer.cid=track.cid
          137  +       AND album.aid=track.aid;
          138  +  }
          139  +} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
          140  +do_test whereG-2.3 {
          141  +  catchsql {
          142  +    SELECT DISTINCT aname
          143  +      FROM album, composer, track
          144  +     WHERE likelihood(cname LIKE '%bach%', track.cid)
          145  +       AND composer.cid=track.cid
          146  +       AND album.aid=track.aid;
          147  +  }
          148  +} {1 {second argument to likelihood() must be a constant between 0.0 and 1.0}}
          149  +
          150  +# Commuting a term of the WHERE clause should not change the query plan
          151  +#
          152  +do_execsql_test whereG-3.0 {
          153  +  CREATE TABLE a(a1 PRIMARY KEY, a2);
          154  +  CREATE TABLE b(b1 PRIMARY KEY, b2);
          155  +} {}
          156  +do_eqp_test whereG-3.1 {
          157  +  SELECT * FROM a, b WHERE b1=a1 AND a2=5;
          158  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          159  +do_eqp_test whereG-3.2 {
          160  +  SELECT * FROM a, b WHERE a1=b1 AND a2=5;
          161  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          162  +do_eqp_test whereG-3.3 {
          163  +  SELECT * FROM a, b WHERE a2=5 AND b1=a1;
          164  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          165  +do_eqp_test whereG-3.4 {
          166  +  SELECT * FROM a, b WHERE a2=5 AND a1=b1;
          167  +} {/.*SCAN TABLE a.*SEARCH TABLE b USING INDEX .*b_1 .b1=..*/}
          168  +
          169  +
          170  +finish_test