Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | 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. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | qp-enhancements |
Files: | files | file ages | folders |
SHA1: |
4226e51ff837f0ffe16355491a655d91 |
User & Date: | drh 2012-09-25 20:43:35.989 |
Context
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) | |
14:29 | Pass information around between the major routines of the query planner using a single pointer to a structure rather than a long list of parameters. (check-in: 1104d42e10 user: drh tags: qp-enhancements) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
280 281 282 283 284 285 286 287 288 289 290 291 292 293 | WhereClause *pWC; /* The WHERE clause */ 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 */ WhereCost cost; /* Lowest cost query plan */ }; /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( | > > | 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 | WhereClause *pWC; /* The WHERE clause */ 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 *a; /* Info about outer loops */ WhereCost cost; /* Lowest cost query plan */ }; /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit( |
︙ | ︙ | |||
3033 3034 3035 3036 3037 3038 3039 | ** 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 */ | | | > > > > > > > > | 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 | ** 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 */ for(nEq=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); |
︙ | ︙ | |||
3110 3111 3112 3113 3114 3115 3116 | } } /* 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. */ | | > | | 3120 3121 3122 3123 3124 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 3141 3142 3143 3144 3145 3146 | } } /* 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. */ if( bSort && isSortingIndex( pParse, pWC->pMaskSet, pProbe, iCur, p->pOrderBy, nEq, wsFlags, &rev) ){ bSort = 0; wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY; wsFlags |= (rev ? 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) && (wsFlags & WHERE_COLUMN_IN)==0 ){ bDist = 0; wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_DISTINCT; } /* If currently calculating the cost of using an index (not the IPK |
︙ | ︙ | |||
4686 4687 4688 4689 4690 4691 4692 | SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ | < > | 4697 4698 4699 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 4716 4717 4718 4719 4720 4721 | SrcList *pTabList, /* A list of all tables to be scanned */ Expr *pWhere, /* The WHERE clause */ ExprList *pOrderBy, /* An ORDER BY clause, or NULL */ ExprList *pDistinct, /* The select-list for DISTINCT queries - or NULL */ u16 wctrlFlags, /* One of the WHERE_* flags defined in sqliteInt.h */ int iIdxCur /* If WHERE_ONETABLE_ONLY is set, index cursor number */ ){ int nByteWInfo; /* Num. bytes allocated for WhereInfo struct */ int nTabList; /* Number of elements in pTabList */ WhereInfo *pWInfo; /* Will become the return value of this function */ Vdbe *v = pParse->pVdbe; /* The virtual database engine */ Bitmask notReady; /* Cursors that are not yet positioned */ WhereBestIdx sWBI; /* Best index search context */ WhereMaskSet *pMaskSet; /* The expression mask set */ WhereLevel *pLevel; /* A single level in pWInfo->a[] */ int iFrom; /* First unused FROM clause element */ int andFlags; /* AND-ed combination of all pWC->a[].wtFlags */ int ii; /* Loop counter */ sqlite3 *db; /* Database connection */ /* Variable initialization */ memset(&sWBI, 0, sizeof(sWBI)); sWBI.pParse = pParse; |
︙ | ︙ | |||
4747 4748 4749 4750 4751 4752 4753 4754 4755 4756 4757 4758 4759 4760 | 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]; /* 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. | > | 4758 4759 4760 4761 4762 4763 4764 4765 4766 4767 4768 4769 4770 4771 4772 | 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.a = 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. |
︙ | ︙ | |||
4790 4791 4792 4793 4794 4795 4796 | ** ** Note that bitmasks are created for all pTabList->nSrc tables in ** pTabList, not just the first nTabList tables. nTabList is normally ** equal to pTabList->nSrc but might be shortened to 1 if the ** WHERE_ONETABLE_ONLY flag is set. */ assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 ); | | | | | | | | 4802 4803 4804 4805 4806 4807 4808 4809 4810 4811 4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 | ** ** Note that bitmasks are created for all pTabList->nSrc tables in ** pTabList, not just the first nTabList tables. nTabList is normally ** equal to pTabList->nSrc but might be shortened to 1 if the ** WHERE_ONETABLE_ONLY flag is set. */ assert( sWBI.pWC->vmask==0 && pMaskSet->n==0 ); for(ii=0; ii<pTabList->nSrc; ii++){ createMask(pMaskSet, pTabList->a[ii].iCursor); #ifndef SQLITE_OMIT_VIRTUALTABLE if( ALWAYS(pTabList->a[ii].pTab) && IsVirtual(pTabList->a[ii].pTab) ){ sWBI.pWC->vmask |= ((Bitmask)1 << ii); } #endif } #ifndef NDEBUG { Bitmask toTheLeft = 0; for(ii=0; ii<pTabList->nSrc; ii++){ Bitmask m = getMask(pMaskSet, pTabList->a[ii].iCursor); assert( (m-1)==toTheLeft ); toTheLeft |= m; } } #endif /* Analyze all of the subexpressions. Note that exprAnalyze() might |
︙ | ︙ | |||
4843 4844 4845 4846 4847 4848 4849 | ** pWInfo->a[].iTabCur The VDBE cursor for the database table ** pWInfo->a[].iIdxCur The VDBE cursor for the index ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term ** ** This loop also figures out the nesting order of tables in the FROM ** clause. */ | | > > > | | | | | 4855 4856 4857 4858 4859 4860 4861 4862 4863 4864 4865 4866 4867 4868 4869 4870 4871 4872 4873 4874 4875 4876 4877 4878 4879 4880 4881 4882 4883 4884 4885 4886 4887 4888 4889 4890 4891 4892 4893 4894 4895 4896 4897 4898 4899 4900 4901 4902 4903 4904 | ** pWInfo->a[].iTabCur The VDBE cursor for the database table ** pWInfo->a[].iIdxCur The VDBE cursor for the index ** pWInfo->a[].pTerm When wsFlags==WO_OR, the OR-clause term ** ** This loop also figures out the nesting order of tables in the FROM ** clause. */ sWBI.notValid = ~(Bitmask)0; sWBI.pOrderBy = pOrderBy; sWBI.n = nTabList; sWBI.pDistinct = pDistinct; andFlags = ~0; WHERETRACE(("*** Optimizer Start ***\n")); for(sWBI.i=iFrom=0, pLevel=pWInfo->a; sWBI.i<nTabList; sWBI.i++, pLevel++){ WhereCost bestPlan; /* Most efficient plan seen so far */ Index *pIdx; /* Index for FROM table at pTabItem */ int j; /* For looping over FROM tables */ int bestJ = -1; /* The value of j */ Bitmask m; /* Bitmask value for j or bestJ */ int isOptimal; /* Iterator for optimal/non-optimal search */ int nUnconstrained; /* Number tables without INDEXED BY */ Bitmask notIndexed; /* Mask of tables that cannot use an index */ memset(&bestPlan, 0, sizeof(bestPlan)); bestPlan.rCost = SQLITE_BIG_DBL; WHERETRACE(("*** Begin search for loop %d ***\n", sWBI.i)); /* Loop through the remaining entries in the FROM clause to find the ** next nested loop. The loop tests all FROM clause entries ** either once or twice. ** ** The first test is always performed if there are two or more entries ** remaining and never performed if there is only one FROM clause entry ** to choose from. The first test looks for an "optimal" scan. In ** this context an optimal scan is one that uses the same strategy ** for the given FROM clause entry as would be selected if the entry ** were used as the innermost nested loop. In other words, a table ** is chosen such that the cost of running that table cannot be reduced ** by waiting for other tables to run first. This "optimal" test works ** by first assuming that the FROM clause is on the inner loop and finding ** its query plan, then checking to see if that query plan uses any ** other FROM clause terms that are sWBI.notValid. If no notValid terms ** are used then the "optimal" query plan works. ** ** Note that the WhereCost.nRow parameter for an optimal scan might ** not be as small as it would be if the table really were the innermost ** join. The nRow value can be reduced by WHERE clause constraints ** that do not use indices. But this nRow reduction only happens if the ** table really is the innermost join. ** |
︙ | ︙ | |||
4912 4913 4914 4915 4916 4917 4918 | for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){ for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){ int doNotReorder; /* True if this table should not be reordered */ doNotReorder = (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0; if( j!=iFrom && doNotReorder ) break; m = getMask(pMaskSet, sWBI.pSrc->iCursor); | | < | < < | | > | | | 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 4946 4947 4948 4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 4981 4982 4983 4984 4985 4986 4987 4988 4989 4990 4991 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 | for(isOptimal=(iFrom<nTabList-1); isOptimal>=0 && bestJ<0; isOptimal--){ for(j=iFrom, sWBI.pSrc=&pTabList->a[j]; j<nTabList; j++, sWBI.pSrc++){ int doNotReorder; /* True if this table should not be reordered */ doNotReorder = (sWBI.pSrc->jointype & (JT_LEFT|JT_CROSS))!=0; if( j!=iFrom && doNotReorder ) break; m = getMask(pMaskSet, sWBI.pSrc->iCursor); if( (m & sWBI.notValid)==0 ){ if( j==iFrom ) iFrom++; continue; } sWBI.notReady = (isOptimal ? m : sWBI.notValid); if( sWBI.pSrc->pIndex==0 ) nUnconstrained++; WHERETRACE(("=== trying table %d with isOptimal=%d ===\n", j, isOptimal)); assert( sWBI.pSrc->pTab ); #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(sWBI.pSrc->pTab) ){ sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo; bestVirtualIndex(&sWBI); }else #endif { bestBtreeIndex(&sWBI); } assert( isOptimal || (sWBI.cost.used&sWBI.notValid)==0 ); /* If an INDEXED BY clause is present, then the plan must use that ** index if it uses any index at all */ assert( sWBI.pSrc->pIndex==0 || (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 || sWBI.cost.plan.u.pIdx==sWBI.pSrc->pIndex ); if( isOptimal && (sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)==0 ){ notIndexed |= m; } /* Conditions under which this table becomes the best so far: ** ** (1) The table must not depend on other tables that have not ** yet run. (In other words, it must not depend on tables ** in inner loops.) ** ** (2) A full-table-scan plan cannot supercede indexed plan unless ** the full-table-scan is an "optimal" plan as defined above. ** ** (3) All tables have an INDEXED BY clause or this table lacks an ** INDEXED BY clause or this table uses the specific ** 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 or else the ** cost must be the same and the number of rows must be lower. */ 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 || sWBI.cost.rCost<bestPlan.rCost /* (4) */ || (sWBI.cost.rCost<=bestPlan.rCost && sWBI.cost.plan.nRow<bestPlan.plan.nRow)) ){ WHERETRACE(("=== table %d is best so far" " with cost=%g and nRow=%g\n", j, sWBI.cost.rCost, sWBI.cost.plan.nRow)); 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 for loop %d" " with cost=%g and nRow=%g\n", bestJ, pLevel-pWInfo->a, bestPlan.rCost, bestPlan.plan.nRow)); if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){ pWInfo->nOBSat = pOrderBy->nExpr; } if( (bestPlan.plan.wsFlags & WHERE_DISTINCT)!=0 ){ |
︙ | ︙ | |||
5012 5013 5014 5015 5016 5017 5018 | pLevel->iIdxCur = iIdxCur; }else{ pLevel->iIdxCur = pParse->nTab++; } }else{ pLevel->iIdxCur = -1; } | | | 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 | pLevel->iIdxCur = iIdxCur; }else{ pLevel->iIdxCur = pParse->nTab++; } }else{ pLevel->iIdxCur = -1; } sWBI.notValid &= ~getMask(pMaskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = (u8)bestJ; if( bestPlan.plan.nRow>=(double)1 ){ pParse->nQueryLoop *= bestPlan.plan.nRow; } /* Check that if the table scanned by this loop iteration had an ** INDEXED BY clause attached to it, that the named index is being |
︙ | ︙ | |||
5065 5066 5067 5068 5069 5070 5071 | /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; | | | 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 | /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ notReady = ~(Bitmask)0; pWInfo->nRowOut = (double)1; for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){ Table *pTab; /* Table to open */ int iDb; /* Index of database containing table/index */ struct SrcList_item *pTabItem; pTabItem = &pTabList->a[pLevel->iFrom]; pTab = pTabItem->pTab; pLevel->iTabCur = pTabItem->iCursor; |
︙ | ︙ | |||
5128 5129 5130 5131 5132 5133 5134 | if( db->mallocFailed ) goto whereBeginError; /* Generate the code to do the search. Each iteration of the for ** loop below generates code for a single nested loop of the VM ** program. */ notReady = ~(Bitmask)0; | | | | | | | | 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159 5160 5161 5162 5163 5164 5165 5166 5167 5168 5169 5170 5171 5172 5173 5174 5175 | if( db->mallocFailed ) goto whereBeginError; /* Generate the code to do the search. Each iteration of the for ** loop below generates code for a single nested loop of the VM ** program. */ notReady = ~(Bitmask)0; for(ii=0; ii<nTabList; ii++){ pLevel = &pWInfo->a[ii]; explainOneScan(pParse, pTabList, pLevel, ii, pLevel->iFrom, wctrlFlags); notReady = codeOneLoopStart(pWInfo, ii, wctrlFlags, notReady); pWInfo->iContinue = pLevel->addrCont; } #ifdef SQLITE_TEST /* For testing and debugging use only */ /* Record in the query plan information about the current table ** and the index used to access it (if any). If the table itself ** is not used, its name is just '{}'. If no index is used ** the index is listed as "{}". If the primary key is used the ** index name is '*'. */ for(ii=0; ii<nTabList; ii++){ char *z; int n; int w; struct SrcList_item *pTabItem; pLevel = &pWInfo->a[ii]; w = pLevel->plan.wsFlags; pTabItem = &pTabList->a[pLevel->iFrom]; z = pTabItem->zAlias; if( z==0 ) z = pTabItem->pTab->zName; n = sqlite3Strlen30(z); if( n+nQPlan < sizeof(sqlite3_query_plan)-10 ){ if( (w & WHERE_IDX_ONLY)!=0 && (w & WHERE_COVER_SCAN)==0 ){ |
︙ | ︙ |