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