Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further refactoring of the ORDER BY related query-planning logic in order to make it easier to extend to support optimizing out ORDER BY on joins. No actual behavior changes, yet. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | qp-enhancements |
Files: | files | file ages | folders |
SHA1: |
96496ddae12a239b30a1fc997fbea43e |
User & Date: | drh 2012-09-26 23:17:01.276 |
Context
2012-09-27
| ||
12:05 | Further tweaks to the query planner logic in preparation for adding ORDER BY opt-out for joins. (check-in: 53efc10af9 user: drh tags: qp-enhancements) | |
2012-09-26
| ||
23:17 | Further refactoring of the ORDER BY related query-planning logic in order to make it easier to extend to support optimizing out ORDER BY on joins. No actual behavior changes, yet. (check-in: 96496ddae1 user: drh tags: qp-enhancements) | |
2012-09-25
| ||
20:43 | Augment the WhereBestIdx structure to pass down into the query planner information that might be used to better detect ORDER BY and DISTINCT optimizations spanning multiple tables of a join. (check-in: 4226e51ff8 user: drh tags: qp-enhancements) | |
Changes
Changes to src/select.c.
︙ | ︙ | |||
4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 | resetAccumulator(pParse, &sAggInfo); pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0); if( pWInfo==0 ){ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); if( pWInfo->nOBSat>0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); | > | 4502 4503 4504 4505 4506 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 | resetAccumulator(pParse, &sAggInfo); pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax,0,flag,0); if( pWInfo==0 ){ sqlite3ExprListDelete(db, pDel); goto select_end; } updateAccumulator(pParse, &sAggInfo); assert( pMinMax==0 || pMinMax->nExpr==1 ); if( pWInfo->nOBSat>0 ){ sqlite3VdbeAddOp2(v, OP_Goto, 0, pWInfo->iBreak); VdbeComment((v, "%s() by index", (flag==WHERE_ORDERBY_MIN?"min":"max"))); } sqlite3WhereEnd(pWInfo); finalizeAggFunctions(pParse, &sAggInfo); |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1902 1903 1904 1905 1906 1907 1908 | ** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true. ** pTerm is only used when wsFlags&WHERE_MULTI_OR is true. And pVtabIdx ** is only used when wsFlags&WHERE_VIRTUALTABLE is true. It is never the ** case that more than one of these conditions is true. */ struct WherePlan { u32 wsFlags; /* WHERE_* flags that describe the strategy */ | | > | 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 | ** Within the union, pIdx is only used when wsFlags&WHERE_INDEXED is true. ** pTerm is only used when wsFlags&WHERE_MULTI_OR is true. And pVtabIdx ** is only used when wsFlags&WHERE_VIRTUALTABLE is true. It is never the ** case that more than one of these conditions is true. */ struct WherePlan { u32 wsFlags; /* WHERE_* flags that describe the strategy */ u16 nEq; /* Number of == constraints */ u16 nOBSat; /* Number of ORDER BY terms satisfied */ double nRow; /* Estimated number of rows (for EQP) */ union { Index *pIdx; /* Index when WHERE_INDEXED is true */ struct WhereTerm *pTerm; /* WHERE clause term for OR-search */ sqlite3_index_info *pVtabIdx; /* Virtual table index to use */ } u; }; |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
281 282 283 284 285 286 287 | struct SrcList_item *pSrc; /* The FROM clause term to search */ Bitmask notReady; /* Mask of cursors not available */ Bitmask notValid; /* Cursors not available for any purpose */ 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 */ | | | 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 | struct SrcList_item *pSrc; /* The FROM clause term to search */ Bitmask notReady; /* Mask of cursors not available */ Bitmask notValid; /* Cursors not available for any purpose */ 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( |
︙ | ︙ | |||
1427 1428 1429 1430 1431 1432 1433 | /* Prevent ON clause terms of a LEFT JOIN from being used to drive ** an index for tables to the left of the join. */ pTerm->prereqRight |= extraRight; } /* | | | | | < < | > | < < < > | | < | | 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 | /* Prevent ON clause terms of a LEFT JOIN from being used to drive ** an index for tables to the left of the join. */ pTerm->prereqRight |= extraRight; } /* ** Return TRUE if the given index is UNIQUE and all columns past the ** first nSkip columns are NOT NULL. */ static int indexIsUniqueNotNull(Index *pIdx, int nSkip){ Table *pTab = pIdx->pTable; int i; if( pIdx->onError==OE_None ) return 0; for(i=nSkip; i<pIdx->nColumn; i++){ int j = pIdx->aiColumn[i]; if( j>=0 && pTab->aCol[j].notNull==0 ) return 0; } return 1; } /* ** This function searches the expression list passed as the second argument ** for an expression of type TK_COLUMN that refers to the same column and ** uses the same collation sequence as the iCol'th column of index pIdx. ** Argument iBase is the cursor number used for the table that pIdx refers |
︙ | ︙ | |||
1608 1609 1610 1611 1612 1613 1614 | } return 0; } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY | | | > < < | > | > > > > | < < | < < > | < | | < | | > | > | | | | > > | > > > > > > > > > | | | < | | 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 | } return 0; } /* ** This routine decides if pIdx can be used to satisfy the ORDER BY ** clause, either in whole or in part. The return value is the ** cumulative number of terms in the ORDER BY clause that are satisfied ** by the index pIdx and other indices in outer loops. ** ** The table being queried has a cursor number of "base". pIdx is the ** index that is postulated for use to access the table. ** ** nEqCol is the number of columns of pIdx that are used as equality ** constraints and where the other side of the == is an ordered column ** or constant. An "order column" in the previous sentence means a column ** in table from an outer loop whose values will always appear in the ** correct order due to othre index, or because the outer loop generates ** a unique result. Any of the first nEqCol columns of pIdx may be missing ** from the ORDER BY clause and the match can still be a success. ** ** The *pbRev value is set to 0 order 1 depending on whether or not ** pIdx should be run in the forward order or in reverse order. */ static int isSortingIndex( WhereBestIdx *p, /* Best index search context */ Index *pIdx, /* The index we are testing */ int base, /* Cursor number for the table to be sorted */ int nEqCol, /* Number of index columns with ordered == constraints */ int wsFlags, /* Index usages flags */ int bOuterRev, /* True if outer loops scan in reverse order */ int *pbRev /* Set to 1 for reverse-order scan of pIdx */ ){ int i; /* Number of pIdx terms used */ int j; /* Number of ORDER BY terms satisfied */ int sortOrder = 0; /* XOR of index and ORDER BY sort direction */ int nTerm; /* Number of ORDER BY terms */ struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ ExprList *pOrderBy; /* The ORDER BY clause */ Parse *pParse = p->pParse; /* Parser context */ sqlite3 *db = pParse->db; /* Database connection */ int nPriorSat; /* ORDER BY terms satisfied by outer loops */ int seenRowid = 0; /* True if an ORDER BY rowid term is seen */ if( p->i==0 ){ nPriorSat = 0; }else{ nPriorSat = p->aLevel[p->i-1].plan.nOBSat; } if( p->i>0 && nEqCol==0 /*&& !allOuterLoopsUnique(p)*/ ) return nPriorSat; pOrderBy = p->pOrderBy; if( !pOrderBy ) return nPriorSat; if( wsFlags & WHERE_COLUMN_IN ) return nPriorSat; if( pIdx->bUnordered ) return nPriorSat; nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Argument pIdx must either point to a 'real' named index structure, ** or an index structure allocated on the stack by bestBtreeIndex() to ** represent the rowid index that is part of every table. */ assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) ); /* Match terms of the ORDER BY clause against columns of ** the index. ** ** Note that indices have pIdx->nColumn regular columns plus ** one additional column containing the rowid. The rowid column ** of the index is also allowed to match against the ORDER BY ** clause. */ for(i=0,j=nPriorSat,pTerm=&pOrderBy->a[j]; j<nTerm && i<=pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ int termSortOrder; /* Sort order for this term */ int iColumn; /* The i-th column of the index. -1 for rowid */ int iSortOrder; /* 1 for DESC, 0 for ASC on the i-th index term */ const char *zColl; /* Name of the collating sequence for i-th index term */ |
︙ | ︙ | |||
1705 1706 1707 1708 1709 1710 1711 | }else if( i==pIdx->nColumn ){ /* Index column i is the rowid. All other terms match. */ break; }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ | | | | < < < < < < | > < | < < < < | > > > > | | < < | > | > | < < < < < < < < < < > > > | < < | | 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 1729 1730 1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741 1742 1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 | }else if( i==pIdx->nColumn ){ /* Index column i is the rowid. All other terms match. */ break; }else{ /* If an index column fails to match and is not constrained by == ** then the index cannot satisfy the ORDER BY constraint. */ return nPriorSat; } } assert( pIdx->aSortOrder!=0 || iColumn==-1 ); assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 ); assert( iSortOrder==0 || iSortOrder==1 ); termSortOrder = iSortOrder ^ pTerm->sortOrder; if( i>nEqCol ){ if( termSortOrder!=sortOrder ){ /* Indices can only be used if all ORDER BY terms past the ** equality constraints are all either DESC or ASC. */ break; } }else{ sortOrder = termSortOrder; } j++; pTerm++; if( iColumn<0 ){ seenRowid = 1; break; } } *pbRev = bOuterRev ^ sortOrder; /* If there was an "ORDER BY rowid" term that matched, or it is only ** possible for a single row from this table to match, then skip over ** any additional ORDER BY terms dealing with this table. */ if( seenRowid || ( (wsFlags & WHERE_COLUMN_NULL)==0 && i>=pIdx->nColumn && indexIsUniqueNotNull(pIdx, nEqCol) ) ){ /* Advance j over additional ORDER BY terms associated with base */ WhereMaskSet *pMS = p->pWC->pMaskSet; Bitmask m = ~getMask(pMS, base); while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){ j++; } } return j; } /* ** Prepare a crude estimate of the logarithm of the input value. ** The results need not be exact. This is only used for estimating ** the total cost of performing operations with O(logN) or O(NlogN) ** complexity. Because N is just a guess, it is no great tragedy if |
︙ | ︙ | |||
2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 | *pnRow = nRowEst; WHERETRACE(("IN row estimate: est=%g\n", nRowEst)); } return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ /* ** Find the best query plan for accessing a particular table. Write the ** best query plan and its cost into the p->cost. ** ** The lowest cost plan wins. The cost is an estimate of the amount of ** CPU and disk I/O needed to process the requested result. | > > > > > > > > > > > > > > > > | 2859 2860 2861 2862 2863 2864 2865 2866 2867 2868 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 | *pnRow = nRowEst; WHERETRACE(("IN row estimate: est=%g\n", nRowEst)); } return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ /* ** pTerm is an == constraint. Check to see if the other side of ** the == is a constant or a value that is guaranteed to be ordered ** by outer loops. Return 1 if pTerm is ordered, and 0 if not. */ static int isOrderedTerm(WhereBestIdx *p, WhereTerm *pTerm, int *pbRev){ if( p->i==0 ){ return 1; /* All == are ordered in the outer loop */ } /* If we cannot prove that the constraint is ordered, assume it is not */ return 0; } /* ** Find the best query plan for accessing a particular table. Write the ** best query plan and its cost into the p->cost. ** ** The lowest cost plan wins. The cost is an estimate of the amount of ** CPU and disk I/O needed to process the requested result. |
︙ | ︙ | |||
2964 2965 2966 2967 2968 2969 2970 | /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */ | | | 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 | /* Loop over all indices looking for the best one to use */ for(; pProbe; pIdx=pProbe=pProbe->pNext){ const tRowcnt * const aiRowEst = pProbe->aiRowEst; double cost; /* Cost of using pProbe */ double nRow; /* Estimated number of rows in result set */ double log10N = (double)1; /* base-10 logarithm of nRow (inexact) */ int bRev = 2; /* 0=forward scan. 1=reverse. 2=undecided */ int wsFlags = 0; Bitmask used = 0; /* 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. ** |
︙ | ︙ | |||
2997 2998 2999 3000 3001 3002 3003 3004 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 | ** ** nInMul is set to 1. ** ** If there exists a WHERE term of the form "x IN (SELECT ...)", then ** the sub-select is assumed to return 25 rows for the purposes of ** determining nInMul. ** ** bInEst: ** Set to true if there was at least one "x IN (SELECT ...)" term used ** in determining the value of nInMul. Note that the RHS of the ** IN operator must be a SELECT, not a value list, for this variable ** to be true. ** ** rangeDiv: ** An estimate of a divisor by which to reduce the search space due ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE ** data, a single inequality reduces the search space to 1/4rd its ** original size (rangeDiv==4). Two inequalities reduce the search ** space to 1/16th of its original size (rangeDiv==16). ** ** bSort: ** Boolean. True if there is an ORDER BY clause that will require an ** external sort (i.e. scanning the index being evaluated will not ** correctly order records). ** ** bLookup: ** Boolean. True if a table lookup is required for each index entry ** visited. In other words, true if this is not a covering index. ** This is always false for the rowid primary key index of a table. ** For other indexes, it is true unless all the columns of the table ** used by the SELECT statement are present in the index (such an ** index is sometimes described as a covering index). ** For example, given the index on (a, b), the second of the following ** 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 nEq; /* Number of == or IN 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 */ WhereTerm *pTerm; /* A single term of the WHERE clause */ #ifdef SQLITE_ENABLE_STAT3 WhereTerm *pFirstTerm = 0; /* First term matching the index */ #endif if( (p->i) > 0 ){ bSort = 0; bDist = 0; }else{ bSort = p->pOrderBy!=0; bDist = p->pDistinct!=0; } /* Determine the values of nEq and nInMul */ | > > > > > > > > > > > > | > > | 3005 3006 3007 3008 3009 3010 3011 3012 3013 3014 3015 3016 3017 3018 3019 3020 3021 3022 3023 3024 3025 3026 3027 3028 3029 3030 3031 3032 3033 3034 3035 3036 3037 3038 3039 3040 3041 3042 3043 3044 3045 3046 3047 3048 3049 3050 3051 3052 3053 3054 3055 3056 3057 3058 3059 3060 3061 3062 3063 3064 3065 3066 3067 3068 3069 3070 3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 | ** ** nInMul is set to 1. ** ** If there exists a WHERE term of the form "x IN (SELECT ...)", then ** the sub-select is assumed to return 25 rows for the purposes of ** determining nInMul. ** ** nOrdered: ** The number of equality terms that are constrainted by outer loop ** variables that are well-ordered. ** ** bInEst: ** Set to true if there was at least one "x IN (SELECT ...)" term used ** in determining the value of nInMul. Note that the RHS of the ** IN operator must be a SELECT, not a value list, for this variable ** to be true. ** ** rangeDiv: ** An estimate of a divisor by which to reduce the search space due ** to inequality constraints. In the absence of sqlite_stat3 ANALYZE ** data, a single inequality reduces the search space to 1/4rd its ** original size (rangeDiv==4). Two inequalities reduce the search ** space to 1/16th of its original size (rangeDiv==16). ** ** bSort: ** Boolean. True if there is an ORDER BY clause that will require an ** external sort (i.e. scanning the index being evaluated will not ** correctly order records). ** ** bDistinct: ** Boolean. True if there is a DISTINCT clause that will require an ** external btree. ** ** bLookup: ** Boolean. True if a table lookup is required for each index entry ** visited. In other words, true if this is not a covering index. ** This is always false for the rowid primary key index of a table. ** For other indexes, it is true unless all the columns of the table ** used by the SELECT statement are present in the index (such an ** index is sometimes described as a covering index). ** For example, given the index on (a, b), the second of the following ** 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 nEq; /* Number of == or IN terms matching index */ 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 nOBSat = 0; /* Number of ORDER BY terms satisfied */ 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) > 0 ){ bSort = 0; bDist = 0; }else{ bSort = p->pOrderBy!=0; bDist = p->pDistinct!=0; } /* Determine the values of nEq and nInMul */ for(nEq=nOrdered=0; nEq<pProbe->nColumn; nEq++){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, p->notReady, eqTermMask, pIdx); if( pTerm==0 ) break; wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ); testcase( pTerm->pWC!=pWC ); if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; 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 ){ wsFlags |= WHERE_COLUMN_NULL; }else if( bSort && nEq==nOrdered && isOrderedTerm(p, pTerm, &bRev) ){ nOrdered++; } #ifdef SQLITE_ENABLE_STAT3 if( nEq==0 && pProbe->aSample ) pFirstTerm = pTerm; #endif used |= pTerm->prereqRight; } |
︙ | ︙ | |||
3120 3121 3122 3123 3124 3125 3126 | } } /* 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 wsFlags. Otherwise, if there is an ORDER BY clause but the index ** will scan rows in a different order, set the bSort variable. */ | > | > > > | > | | | | > | 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 | } } /* 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 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 ); nOBSat = isSortingIndex(p, pProbe, iCur, nOrdered, wsFlags, bRev&1, &bRev); if( nOrderBy==nOBSat ){ bSort = 0; wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY; wsFlags |= (bRev==1 ? WHERE_REVERSE : 0); } } /* 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 wsFlags. */ if( bDist && isDistinctIndex(pParse, pWC, pProbe, iCur, p->pDistinct, nEq) |
︙ | ︙ | |||
3268 3269 3270 3271 3272 3273 3274 | /* 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 ){ | | | 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 | /* 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 ){ cost += nRow*estLog(nRow*(nOrderBy - nOBSat)/nOrderBy)*3; } if( bDist ){ cost += nRow*estLog(nRow)*3; } /**** Cost of using this index has now been computed ****/ |
︙ | ︙ | |||
3337 3338 3339 3340 3341 3342 3343 | } if( nRow<2 ) nRow = 2; } WHERETRACE(( "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n" | | > | > | 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 | } if( nRow<2 ) nRow = 2; } WHERETRACE(( "%s(%s): nEq=%d nInMul=%d rangeDiv=%d bSort=%d bLookup=%d wsFlags=0x%x\n" " notReady=0x%llx log10N=%.1f nRow=%.1f cost=%.1f used=0x%llx\n" " nOrdered=%d nOBSat=%d\n", pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), nEq, nInMul, (int)rangeDiv, bSort, bLookup, wsFlags, p->notReady, log10N, nRow, cost, used, nOrdered, nOBSat )); /* If this index is the best we have seen so far, then record this ** index and its cost in the pCost structure. */ if( (!pIdx || wsFlags) && (cost<p->cost.rCost || (cost<=p->cost.rCost && nRow<p->cost.plan.nRow)) ){ p->cost.rCost = cost; p->cost.used = used; p->cost.plan.nRow = nRow; p->cost.plan.wsFlags = (wsFlags&wsFlagMask); p->cost.plan.nEq = nEq; p->cost.plan.nOBSat = nOBSat; p->cost.plan.u.pIdx = pIdx; } /* If there was an INDEXED BY clause, then only that one index is ** considered. */ if( pSrc->pIndex ) break; |
︙ | ︙ | |||
4758 4759 4760 4761 4762 4763 4764 | pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&sWBI.pWC[1]; | | | 4788 4789 4790 4791 4792 4793 4794 4795 4796 4797 4798 4799 4800 4801 4802 | pWInfo->pParse = pParse; pWInfo->pTabList = pTabList; pWInfo->iBreak = sqlite3VdbeMakeLabel(v); pWInfo->pWC = sWBI.pWC = (WhereClause *)&((u8 *)pWInfo)[nByteWInfo]; pWInfo->wctrlFlags = wctrlFlags; pWInfo->savedNQueryLoop = pParse->nQueryLoop; pMaskSet = (WhereMaskSet*)&sWBI.pWC[1]; sWBI.aLevel = pWInfo->a; /* Disable the DISTINCT optimization if SQLITE_DistinctOpt is set via ** sqlite3_test_ctrl(SQLITE_TESTCTRL_OPTIMIZATIONS,...) */ if( db->flags & SQLITE_DistinctOpt ) pDistinct = 0; /* Split the WHERE clause into separate subexpressions where each ** subexpression is separated by an AND operator. |
︙ | ︙ |