Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further attempts to optimize out unnecessary ORDER BY clauses. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | qp-enhancements |
Files: | files | file ages | folders |
SHA1: |
6744d9a37faffed59b4d5cb96c8671ec |
User & Date: | drh 2012-10-03 00:25:54.662 |
Context
2012-10-03
| ||
12:38 | Fix a query planner problem that only occurs when covering-index-scan is disabled. Fix to tests whose output changed due to the new and more aggressive ORDER BY optimization. (Closed-Leaf check-in: 0f9bb90100 user: drh tags: qp-enhancements) | |
00:25 | Further attempts to optimize out unnecessary ORDER BY clauses. (check-in: 6744d9a37f user: drh tags: qp-enhancements) | |
2012-10-02
| ||
22:54 | Work around an optimization issue with the MSVC compiler for ARM. (check-in: 7d301fdfee user: mistachkin tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
254 255 256 257 258 259 260 | #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */ #define WHERE_IDX_ONLY 0x00400000 /* Use index only - omit table */ | | | 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 | #define WHERE_INDEXED 0x000f0000 /* Anything that uses an index */ #define WHERE_NOT_FULLSCAN 0x100f3000 /* Does not do a full table scan */ #define WHERE_IN_ABLE 0x000f1000 /* Able to support an IN operator */ #define WHERE_TOP_LIMIT 0x00100000 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x00200000 /* x>EXPR or x>=EXPR constraint */ #define WHERE_BOTH_LIMIT 0x00300000 /* Both x>EXPR and x<EXPR */ #define WHERE_IDX_ONLY 0x00400000 /* Use index only - omit table */ #define WHERE_ORDERED 0x00800000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x01000000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x02000000 /* Selects no more than one row */ #define WHERE_ALL_UNIQUE 0x04000000 /* This and all prior have one row */ #define WHERE_VIRTUALTABLE 0x08000000 /* Use virtual-table processing */ #define WHERE_MULTI_OR 0x10000000 /* OR using multiple indices */ #define WHERE_TEMP_INDEX 0x20000000 /* Uses an ephemeral index */ #define WHERE_DISTINCT 0x40000000 /* Correct order for DISTINCT */ |
︙ | ︙ | |||
285 286 287 288 289 290 291 292 293 294 295 296 297 298 | ExprList *pOrderBy; /* The ORDER BY clause */ ExprList *pDistinct; /* The select-list if query is DISTINCT */ sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */ int i, n; /* Which loop is being coded; # of loops */ WhereLevel *aLevel; /* Info about outer loops */ WhereCost cost; /* Lowest cost query plan */ }; /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ | > > > > > > > > > > > | 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 | ExprList *pOrderBy; /* The ORDER BY clause */ ExprList *pDistinct; /* The select-list if query is DISTINCT */ sqlite3_index_info **ppIdxInfo; /* Index information passed to xBestIndex */ int i, n; /* Which loop is being coded; # of loops */ WhereLevel *aLevel; /* Info about outer loops */ WhereCost cost; /* Lowest cost query plan */ }; /* ** Return TRUE if the probe cost is less than the baseline cost */ static int compareCost(const WhereCost *pProbe, const WhereCost *pBaseline){ if( pProbe->rCost<pBaseline->rCost ) return 1; if( pProbe->rCost>pBaseline->rCost ) return 0; if( pProbe->plan.nOBSat>pBaseline->plan.nOBSat ) return 1; if( pProbe->plan.nRow<pBaseline->plan.nRow ) return 1; return 0; } /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( WhereClause *pWC, /* The WhereClause to be initialized */ Parse *pParse, /* The parsing context */ |
︙ | ︙ | |||
1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 | ** less than the current cost stored in pCost, replace the contents ** of pCost. */ WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow)); if( rTotal<p->cost.rCost ){ p->cost.rCost = rTotal; p->cost.used = used; p->cost.plan.nRow = nRow; p->cost.plan.wsFlags = flags; p->cost.plan.u.pTerm = pTerm; } } } #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ } | > | 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781 1782 1783 | ** less than the current cost stored in pCost, replace the contents ** of pCost. */ WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow)); if( rTotal<p->cost.rCost ){ p->cost.rCost = rTotal; p->cost.used = used; p->cost.plan.nRow = nRow; p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0; p->cost.plan.wsFlags = flags; p->cost.plan.u.pTerm = pTerm; } } } #endif /* SQLITE_OMIT_OR_OPTIMIZATION */ } |
︙ | ︙ | |||
2300 2301 2302 2303 2304 2305 2306 | if( (SQLITE_BIG_DBL/((double)2))<rCost ){ p->cost.rCost = (SQLITE_BIG_DBL/((double)2)); }else{ p->cost.rCost = rCost; } p->cost.plan.u.pVtabIdx = pIdxInfo; if( pIdxInfo->orderByConsumed ){ | | > > > | 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 | if( (SQLITE_BIG_DBL/((double)2))<rCost ){ p->cost.rCost = (SQLITE_BIG_DBL/((double)2)); }else{ p->cost.rCost = rCost; } p->cost.plan.u.pVtabIdx = pIdxInfo; if( pIdxInfo->orderByConsumed ){ p->cost.plan.wsFlags |= WHERE_ORDERED; p->cost.plan.nOBSat = nOrderBy; }else{ p->cost.plan.nOBSat = p->i ? p->aLevel[p->i-1].plan.nOBSat : 0; } p->cost.plan.nEq = 0; pIdxInfo->nOrderBy = nOrderBy; /* Try to find a more efficient access pattern by using multiple indexes ** to optimize an OR expression within the WHERE clause. */ |
︙ | ︙ | |||
2726 2727 2728 2729 2730 2731 2732 | Index *pIdx; u8 sortOrder; for(i=p->i-1; i>=0; i--, pLevel--){ if( pLevel->iTabCur!=iTab ) continue; if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ return 1; } | | > > | | 2741 2742 2743 2744 2745 2746 2747 2748 2749 2750 2751 2752 2753 2754 2755 2756 2757 2758 | Index *pIdx; u8 sortOrder; for(i=p->i-1; i>=0; i--, pLevel--){ if( pLevel->iTabCur!=iTab ) continue; if( (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ return 1; } if( (pLevel->plan.wsFlags & WHERE_ORDERED)==0 ){ return 0; } if( (pIdx = pLevel->plan.u.pIdx)!=0 ){ if( iCol<0 ){ sortOrder = 0; testcase( (pLevel->plan.wsFlags & WHERE_REVERSE)!=0 ); }else{ int n = pIdx->nColumn; for(j=0; j<n; j++){ if( iCol==pIdx->aiColumn[j] ) break; |
︙ | ︙ | |||
2829 2830 2831 2832 2833 2834 2835 | if( p->i==0 ){ nPriorSat = 0; }else{ nPriorSat = p->aLevel[p->i-1].plan.nOBSat; if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat; } | > > > > > | < | 2846 2847 2848 2849 2850 2851 2852 2853 2854 2855 2856 2857 2858 2859 2860 2861 2862 2863 2864 2865 2866 2867 | if( p->i==0 ){ nPriorSat = 0; }else{ nPriorSat = p->aLevel[p->i-1].plan.nOBSat; if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ) return nPriorSat; } if( nEqCol==0 ){ if( p->i && (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){ return nPriorSat; } nEqOneRow = 0; }else if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ nEqOneRow = nEqCol; }else{ sortOrder = bOuterRev; nEqOneRow = -1; } pOrderBy = p->pOrderBy; assert( pOrderBy!=0 ); if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat; if( pIdx->bUnordered ) return nPriorSat; |
︙ | ︙ | |||
3039 3040 3041 3042 3043 3044 3045 | pIdx = 0; } /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; | | < | < | | 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 | pIdx = 0; } /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; WhereCost pc; /* Cost of using pProbe */ double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */ int bRev = 2; /* 0=forward scan. 1=reverse. 2=undecided */ memset(&pc, 0, sizeof(pc)); /* The following variables are populated based on the properties of ** index being evaluated. They are then used to determine the expected ** cost and number of rows returned. ** ** pc.plan.nEq: ** Number of equality terms that can be implemented using the index. ** In other words, the number of initial fields in the index that ** are used in == or IN or NOT NULL constraints of the WHERE clause. ** ** nInMul: ** The "in-multiplier". This is an estimate of how many seek operations ** SQLite must perform on the index in question. For example, if the |
︙ | ︙ | |||
3116 3117 3118 3119 3120 3121 3122 | ** two queries requires table b-tree lookups in order to find the value ** of column c, but the first does not because columns a and b are ** both available in the index. ** ** SELECT a, b FROM tbl WHERE a = 1; ** SELECT a, b, c FROM tbl WHERE a = 1; */ | < | > > > > > > | | | > | | | | | | | | | | | | | | | | | > | | | | | | | | | > | | > > > | | | | | | | | | | | | | > | | > | > | | | | | | | | | | | | | > > | | | | | | | | | | | > | | < < < | < | < < | 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 3180 3181 3182 3183 3184 3185 3186 3187 3188 3189 3190 3191 3192 3193 3194 3195 3196 3197 3198 3199 3200 3201 3202 3203 3204 3205 3206 3207 3208 3209 3210 3211 3212 3213 3214 3215 3216 3217 3218 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 | ** two queries requires table b-tree lookups in order to find the value ** of column c, but the first does not because columns a and b are ** both available in the index. ** ** SELECT a, b FROM tbl WHERE a = 1; ** SELECT a, b, c FROM tbl WHERE a = 1; */ int nOrdered; /* Number of ordered terms matching index */ int bInEst = 0; /* True if "x IN (SELECT...)" seen */ int nInMul = 1; /* Number of distinct equalities to lookup */ double rangeDiv = (double)1; /* Estimated reduction in search space */ int nBound = 0; /* Number of range constraints seen */ int bSort; /* True if external sort required */ int bDist; /* True if index cannot help with DISTINCT */ int bLookup = 0; /* True if not a covering index */ int nPriorSat; /* ORDER BY terms satisfied by outer loops */ int nOrderBy; /* Number of ORDER BY terms */ WhereTerm *pTerm; /* A single term of the WHERE clause */ #ifdef SQLITE_ENABLE_STAT3 WhereTerm *pFirstTerm = 0; /* First term matching the index */ #endif nOrderBy = p->pOrderBy ? p->pOrderBy->nExpr : 0; if( p->i ){ nPriorSat = pc.plan.nOBSat = p->aLevel[p->i-1].plan.nOBSat; bSort = nPriorSat<nOrderBy; bDist = 0; }else{ nPriorSat = pc.plan.nOBSat = 0; bSort = nOrderBy>0; bDist = p->pDistinct!=0; } /* Determine the values of pc.plan.nEq and nInMul */ for(pc.plan.nEq=nOrdered=0; pc.plan.nEq<pProbe->nColumn; pc.plan.nEq++){ int j = pProbe->aiColumn[pc.plan.nEq]; pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx); if( pTerm==0 ) break; pc.plan.wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ); testcase( pTerm->pWC!=pWC ); if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; pc.plan.wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": Assume the SELECT returns 25 rows */ nInMul *= 25; bInEst = 1; }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nInMul *= pExpr->x.pList->nExpr; } }else if( pTerm->eOperator & WO_ISNULL ){ pc.plan.wsFlags |= WHERE_COLUMN_NULL; if( pc.plan.nEq==nOrdered ) nOrdered++; }else if( bSort && pc.plan.nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){ nOrdered++; } #ifdef SQLITE_ENABLE_STAT3 if( pc.plan.nEq==0 && pProbe->aSample ) pFirstTerm = pTerm; #endif pc.used |= pTerm->prereqRight; } /* If the index being considered is UNIQUE, and there is an equality ** constraint for all columns in the index, then this search will find ** at most a single row. In this case set the WHERE_UNIQUE flag to ** indicate this to the caller. ** ** Otherwise, if the search may find more than one row, test to see if ** there is a range constraint on indexed column (pc.plan.nEq+1) that can be ** optimized using the index. */ if( pc.plan.nEq==pProbe->nColumn && pProbe->onError!=OE_None ){ testcase( pc.plan.wsFlags & WHERE_COLUMN_IN ); testcase( pc.plan.wsFlags & WHERE_COLUMN_NULL ); if( (pc.plan.wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){ pc.plan.wsFlags |= WHERE_UNIQUE; if( p->i==0 || (p->aLevel[p->i-1].plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ pc.plan.wsFlags |= WHERE_ALL_UNIQUE; } } }else if( pProbe->bUnordered==0 ){ int j; j = (pc.plan.nEq==pProbe->nColumn ? -1 : pProbe->aiColumn[pc.plan.nEq]); if( findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){ WhereTerm *pTop, *pBtm; pTop = findTerm(pWC, iCur, j, p->notReady, WO_LT|WO_LE, pIdx); pBtm = findTerm(pWC, iCur, j, p->notReady, WO_GT|WO_GE, pIdx); whereRangeScanEst(pParse, pProbe, pc.plan.nEq, pBtm, pTop, &rangeDiv); if( pTop ){ nBound = 1; pc.plan.wsFlags |= WHERE_TOP_LIMIT; pc.used |= pTop->prereqRight; testcase( pTop->pWC!=pWC ); } if( pBtm ){ nBound++; pc.plan.wsFlags |= WHERE_BTM_LIMIT; pc.used |= pBtm->prereqRight; testcase( pBtm->pWC!=pWC ); } pc.plan.wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE); } } /* If there is an ORDER BY clause and the index being considered will ** naturally scan rows in the required order, set the appropriate flags ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but ** the index will scan rows in a different order, set the bSort ** variable. */ assert( bRev>=0 && bRev<=2 ); if( bSort ){ testcase( bRev==0 ); testcase( bRev==1 ); testcase( bRev==2 ); pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered, pc.plan.wsFlags, bRev&1, &bRev); if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_UNIQUE)!=0 ){ pc.plan.wsFlags |= WHERE_ORDERED; } if( nOrderBy==pc.plan.nOBSat ){ bSort = 0; pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE; } if( bRev & 1 ) pc.plan.wsFlags |= WHERE_REVERSE; } /* If there is a DISTINCT qualifier and this index will scan rows in ** order of the DISTINCT expressions, clear bDist and set the appropriate ** flags in pc.plan.wsFlags. */ if( bDist && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, pc.plan.nEq) && (pc.plan.wsFlags & WHERE_COLUMN_IN)==0 ){ bDist = 0; pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT; } /* If currently calculating the cost of using an index (not the IPK ** index), determine if all required column data may be obtained without ** using the main table (i.e. if the index is a covering ** index for this query). If it is, set the WHERE_IDX_ONLY flag in ** pc.plan.wsFlags. Otherwise, set the bLookup variable to true. */ if( pIdx ){ Bitmask m = pSrc->colUsed; int j; for(j=0; j<pIdx->nColumn; j++){ int x = pIdx->aiColumn[j]; if( x<BMS-1 ){ m &= ~(((Bitmask)1)<<x); } } if( m==0 ){ pc.plan.wsFlags |= WHERE_IDX_ONLY; }else{ bLookup = 1; } } /* ** Estimate the number of rows of output. For an "x IN (SELECT...)" ** constraint, do not let the estimate exceed half the rows in the table. */ pc.plan.nRow = (double)(aiRowEst[pc.plan.nEq] * nInMul); if( bInEst && pc.plan.nRow*2>aiRowEst[0] ){ pc.plan.nRow = aiRowEst[0]/2; nInMul = (int)(pc.plan.nRow / aiRowEst[pc.plan.nEq]); } #ifdef SQLITE_ENABLE_STAT3 /* If the constraint is of the form x=VALUE or x IN (E1,E2,...) ** and we do not think that values of x are unique and if histogram ** data is available for column x, then it might be possible ** to get a better estimate on the number of rows based on ** VALUE and how common that value is according to the histogram. */ if( pc.plan.nRow>(double)1 && pc.plan.nEq==1 && pFirstTerm!=0 && aiRowEst[1]>1 ){ assert( (pFirstTerm->eOperator & (WO_EQ|WO_ISNULL|WO_IN))!=0 ); if( pFirstTerm->eOperator & (WO_EQ|WO_ISNULL) ){ testcase( pFirstTerm->eOperator==WO_EQ ); testcase( pFirstTerm->eOperator==WO_ISNULL ); whereEqualScanEst(pParse, pProbe, pFirstTerm->pExpr->pRight, &pc.plan.nRow); }else if( bInEst==0 ){ assert( pFirstTerm->eOperator==WO_IN ); whereInScanEst(pParse, pProbe, pFirstTerm->pExpr->x.pList, &pc.plan.nRow); } } #endif /* SQLITE_ENABLE_STAT3 */ /* Adjust the number of output rows and downward to reflect rows ** that are excluded by range constraints. */ pc.plan.nRow = pc.plan.nRow/rangeDiv; if( pc.plan.nRow<1 ) pc.plan.nRow = 1; /* Experiments run on real SQLite databases show that the time needed ** to do a binary search to locate a row in a table or index is roughly ** log10(N) times the time to move from one row to the next row within ** a table or index. The actual times can vary, with the size of ** records being an important factor. Both moves and searches are ** slower with larger records, presumably because fewer records fit ** on one page and hence more pages have to be fetched. ** ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do ** not give us data on the relative sizes of table and index records. ** So this computation assumes table records are about twice as big ** as index records */ if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED))==WHERE_IDX_ONLY && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan) ){ /* This index is not useful for indexing, but it is a covering index. ** A full-scan of the index might be a little faster than a full-scan ** of the table, so give this case a cost slightly less than a table ** scan. */ pc.rCost = aiRowEst[0]*3 + pProbe->nColumn; pc.plan.wsFlags |= WHERE_COVER_SCAN|WHERE_COLUMN_RANGE; }else if( (pc.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){ /* The cost of a full table scan is a number of move operations equal ** to the number of rows in the table. ** ** We add an additional 4x penalty to full table scans. This causes ** the cost function to err on the side of choosing an index over ** choosing a full scan. This 4x full-scan penalty is an arguable ** decision and one which we expect to revisit in the future. But ** it seems to be working well enough at the moment. */ pc.rCost = aiRowEst[0]*4; pc.plan.wsFlags &= ~WHERE_IDX_ONLY; }else{ log10N = estLog(aiRowEst[0]); pc.rCost = pc.plan.nRow; if( pIdx ){ if( bLookup ){ /* For an index lookup followed by a table lookup: ** nInMul index searches to find the start of each index range ** + nRow steps through the index ** + nRow table searches to lookup the table entry using the rowid */ pc.rCost += (nInMul + pc.plan.nRow)*log10N; }else{ /* For a covering index: ** nInMul index searches to find the initial entry ** + nRow steps through the index */ pc.rCost += nInMul*log10N; } }else{ /* For a rowid primary key lookup: ** nInMult table searches to find the initial entry for each range ** + nRow steps through the table */ pc.rCost += nInMul*log10N; } } /* Add in the estimated cost of sorting the result. Actual experimental ** measurements of sorting performance in SQLite show that sorting time ** adds C*N*log10(N) to the cost, where N is the number of rows to be ** sorted and C is a factor between 1.95 and 4.3. We will split the ** difference and select C of 3.0. */ if( bSort ){ double m = estLog(pc.plan.nRow*(nOrderBy - pc.plan.nOBSat)/nOrderBy); m *= (double)(pc.plan.nOBSat ? 2 : 3); pc.rCost += pc.plan.nRow*m; } if( bDist ){ pc.rCost += pc.plan.nRow*estLog(pc.plan.nRow)*3; } /**** Cost of using this index has now been computed ****/ /* If there are additional constraints on this table that cannot ** be used with the current index, but which might lower the number ** of output rows, adjust the nRow value accordingly. This only ** matters if the current index is the least costly, so do not bother ** with this step if we already know this index will not be chosen. ** Also, never reduce the output row count below 2 using this step. ** ** It is critical that the notValid mask be used here instead of ** the notReady mask. When computing an "optimal" index, the notReady ** mask will only have one bit set - the bit for the current table. ** The notValid mask, on the other hand, always has all bits set for ** tables that are not in outer loops. If notReady is used here instead ** of notValid, then a optimal index that depends on inner joins loops ** might be selected even when there exists an optimal index that has ** no such dependency. */ if( pc.plan.nRow>2 && pc.rCost<=p->cost.rCost ){ int k; /* Loop counter */ int nSkipEq = pc.plan.nEq; /* Number of == constraints to skip */ int nSkipRange = nBound; /* Number of < constraints to skip */ Bitmask thisTab; /* Bitmap for pSrc */ thisTab = getMask(pWC->pMaskSet, iCur); for(pTerm=pWC->a, k=pWC->nTerm; pc.plan.nRow>2 && k; k--, pTerm++){ if( pTerm->wtFlags & TERM_VIRTUAL ) continue; if( (pTerm->prereqAll & p->notValid)!=thisTab ) continue; if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){ if( nSkipEq ){ /* Ignore the first pc.plan.nEq equality matches since the index ** has already accounted for these */ nSkipEq--; }else{ /* Assume each additional equality match reduces the result ** set size by a factor of 10 */ pc.plan.nRow /= 10; } }else if( pTerm->eOperator & (WO_LT|WO_LE|WO_GT|WO_GE) ){ if( nSkipRange ){ /* Ignore the first nSkipRange range constraints since the index ** has already accounted for these */ nSkipRange--; }else{ /* Assume each additional range constraint reduces the result ** set size by a factor of 3. Indexed range constraints reduce ** the search space by a larger factor: 4. We make indexed range ** more selective intentionally because of the subjective ** observation that indexed range constraints really are more ** selective in practice, on average. */ pc.plan.nRow /= 3; } }else if( pTerm->eOperator!=WO_NOOP ){ /* Any other expression lowers the output row count by half */ pc.plan.nRow /= 2; } } if( pc.plan.nRow<2 ) pc.plan.nRow = 2; } WHERETRACE(( "%s(%s):\n" " nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%08x\n" " notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f\n" " used=0x%llx nOrdered=%d nOBSat=%d\n", pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags, p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, nOrdered, pc.plan.nOBSat )); /* If this index is the best we have seen so far, then record this ** index and its cost in the p->cost structure. */ if( (!pIdx || pc.plan.wsFlags) && compareCost(&pc, &p->cost) ){ p->cost = pc; p->cost.plan.wsFlags &= wsFlagMask; p->cost.plan.u.pIdx = pIdx; } /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; |
︙ | ︙ | |||
3473 3474 3475 3476 3477 3478 3479 | ** in. This is used for application testing, to help find cases ** where application behaviour depends on the (undefined) order that ** SQLite outputs rows in in the absence of an ORDER BY clause. */ if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){ p->cost.plan.wsFlags |= WHERE_REVERSE; } | | | < | < | 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 | ** in. This is used for application testing, to help find cases ** where application behaviour depends on the (undefined) order that ** SQLite outputs rows in in the absence of an ORDER BY clause. */ if( !p->pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){ p->cost.plan.wsFlags |= WHERE_REVERSE; } assert( p->pOrderBy || (p->cost.plan.wsFlags&WHERE_ORDERED)==0 ); assert( p->cost.plan.u.pIdx==0 || (p->cost.plan.wsFlags&WHERE_ROWID_EQ)==0 ); assert( pSrc->pIndex==0 || p->cost.plan.u.pIdx==0 || p->cost.plan.u.pIdx==pSrc->pIndex ); WHERETRACE(("best index is: %s\n", p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk")); bestOrClauseIndex(p); bestAutomaticIndex(p); p->cost.plan.wsFlags |= eqTermMask; } /* |
︙ | ︙ | |||
4211 4212 4213 4214 4215 4216 4217 | ** query, then the caller will only allow the loop to run for ** a single iteration. This means that the first row returned ** should not have a NULL value stored in 'x'. If column 'x' is ** the first one after the nEq equality constraints in the index, ** this requires some special handling. */ if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0 | | | 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 | ** query, then the caller will only allow the loop to run for ** a single iteration. This means that the first row returned ** should not have a NULL value stored in 'x'. If column 'x' is ** the first one after the nEq equality constraints in the index, ** this requires some special handling. */ if( (wctrlFlags&WHERE_ORDERBY_MIN)!=0 && (pLevel->plan.wsFlags&WHERE_ORDERED) && (pIdx->nColumn>nEq) ){ /* assert( pOrderBy->nExpr==1 ); */ /* assert( pOrderBy->a[0].pExpr->iColumn==pIdx->aiColumn[nEq] ); */ isMinQuery = 1; nExtraReg = 1; } |
︙ | ︙ | |||
5074 5075 5076 5077 5078 5079 5080 | ** index specified by its INDEXED BY clause. This rule ensures ** that a best-so-far is always selected even if an impossible ** combination of INDEXED BY clauses are given. The error ** will be detected and relayed back to the application later. ** The NEVER() comes about because rule (2) above prevents ** An indexable full-table-scan from reaching rule (3). ** | | | | < < | | | | < < < | 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 | ** index specified by its INDEXED BY clause. This rule ensures ** that a best-so-far is always selected even if an impossible ** combination of INDEXED BY clauses are given. The error ** will be detected and relayed back to the application later. ** The NEVER() comes about because rule (2) above prevents ** An indexable full-table-scan from reaching rule (3). ** ** (4) The plan cost must be lower than prior plans, where "cost" ** is defined by the compareCost() function above. */ if( (sWBI.cost.used&sWBI.notValid)==0 /* (1) */ && (bestJ<0 || (notIndexed&m)!=0 /* (2) */ || (bestPlan.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0) && (nUnconstrained==0 || sWBI.pSrc->pIndex==0 /* (3) */ || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)) && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan)) /* (4) */ ){ WHERETRACE(("=== table %d (%s) is best so far\n" " cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=%08x\n", j, sWBI.pSrc->pTab->zName, sWBI.cost.rCost, sWBI.cost.plan.nRow, sWBI.cost.plan.nOBSat, sWBI.cost.plan.wsFlags)); bestPlan = sWBI.cost; bestJ = j; } if( doNotReorder ) break; } } assert( bestJ>=0 ); assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) ); WHERETRACE(("*** Optimizer selects table %d (%s) for loop %d with:\n" " cost=%.1f, nRow=%.1f, nOBSat=%d, wsFlags=0x%08x\n", bestJ, pTabList->a[bestJ].pTab->zName, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow, bestPlan.plan.nOBSat, bestPlan.plan.wsFlags)); if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){ assert( pWInfo->eDistinct==0 ); pWInfo->eDistinct = WHERE_DISTINCT_ORDERED; } andFlags &= bestPlan.plan.wsFlags; pLevel->plan = bestPlan.plan; pLevel->iTabCur = pTabList->a[bestJ].iCursor; |
︙ | ︙ | |||
5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173 5174 | } } } WHERETRACE(("*** Optimizer Finished ***\n")); if( pParse->nErr || db->mallocFailed ){ goto whereBeginError; } /* If the total query only selects a single row, then the ORDER BY ** clause is irrelevant. */ if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){ pWInfo->nOBSat = pOrderBy->nExpr; } /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. ** The one-pass algorithm only works if the WHERE clause constraints ** the statement to update a single row. | > > > > > > > | 5179 5180 5181 5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 5196 5197 5198 5199 5200 5201 5202 5203 5204 | } } } WHERETRACE(("*** Optimizer Finished ***\n")); if( pParse->nErr || db->mallocFailed ){ goto whereBeginError; } if( nTabList ){ pLevel--; pWInfo->nOBSat = pLevel->plan.nOBSat; }else{ pWInfo->nOBSat = 0; } /* If the total query only selects a single row, then the ORDER BY ** clause is irrelevant. */ if( (andFlags & WHERE_UNIQUE)!=0 && pOrderBy ){ assert( nTabList==0 || (pLevel->plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ); pWInfo->nOBSat = pOrderBy->nExpr; } /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. ** The one-pass algorithm only works if the WHERE clause constraints ** the statement to update a single row. |
︙ | ︙ |
Changes to test/fuzzer1.test.
︙ | ︙ | |||
1860 1861 1862 1863 1864 1865 1866 | INSERT INTO x5_rules VALUES(0, 'a', '0.1.2.3.4.5.6.7.8.9.a', 1); DROP TABLE x5; CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules); SELECT length(word) FROM x5 WHERE word MATCH 'a' LIMIT 50; } {1 21 41 61 81} finish_test | < < | 1860 1861 1862 1863 1864 1865 1866 | INSERT INTO x5_rules VALUES(0, 'a', '0.1.2.3.4.5.6.7.8.9.a', 1); DROP TABLE x5; CREATE VIRTUAL TABLE x5 USING fuzzer(x5_rules); SELECT length(word) FROM x5 WHERE word MATCH 'a' LIMIT 50; } {1 21 41 61 81} finish_test |
Changes to test/orderby2.test.
︙ | ︙ | |||
88 89 90 91 92 93 94 | do_test 2.1 { db eval { SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34 WHERE c=b AND e=d AND g=f ORDER BY +a ASC, +c ASC, +e DESC, +g ASC; } } {1,3,7,10 1,3,7,14 1,3,6,11 1,4,8,12 1,4,8,12 1,4,8,13 1,4,5,9 2,3,7,10 2,3,7,14 2,3,6,11} | | | 88 89 90 91 92 93 94 95 96 97 | do_test 2.1 { db eval { SELECT a||','||c||','||e||','||g FROM t31, t32, t33, t34 WHERE c=b AND e=d AND g=f ORDER BY +a ASC, +c ASC, +e DESC, +g ASC; } } {1,3,7,10 1,3,7,14 1,3,6,11 1,4,8,12 1,4,8,12 1,4,8,13 1,4,5,9 2,3,7,10 2,3,7,14 2,3,6,11} finish_test |