Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch unlikely-func Excluding Merge-Ins
This is equivalent to a diff from 75a8a8c1b3 to 695aee46e9
|
2013-09-13
| ||
| 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: bc446449a1 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: 695aee46e9 user: drh tags: unlikely-func) | |
| 23:12 | Fix typo in a macro name: "GlogUpperToLower" should be "GlobUpperToLower" (check-in: 73634ca463 user: drh tags: trunk) | |
| 17:29 | Merge in the Expr.flags expansion to 32-bits. Use an extra bit to help optimize the sqlite3ExprSkipCollate() routine. (check-in: 4c84d1b4c2 user: drh tags: unlikely-func) | |
| 16:50 | Increase the number of bits available in Expr.flags. Other tweaks aimed at making expression processing more robust. (Closed-Leaf check-in: 579a512538 user: drh tags: expr-tuning) | |
| 02:09 | For error log messages generated by the Win32 native allocator, make sure the correct format specifier is used for the value returned by GetLastError(). (check-in: 75a8a8c1b3 user: mistachkin tags: trunk) | |
| 01:47 | Fix a couple more harmless compiler warnings. (check-in: 59708674f6 user: mistachkin tags: trunk) | |
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, ®Free1); 2906 + exprToRegister(&cacheX, sqlite3ExprCodeTemp(pParse, pX, ®Free1)); 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, ®Free1); 3508 - exprX.op2 = exprX.op; 3509 - exprX.op = TK_REGISTER; 3526 + exprToRegister(&exprX, sqlite3ExprCodeTemp(pParse, &exprX, ®Free1)); 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