Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Begin inserting some experimental code for the next generation query planner. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
ccaf4c3f7e1ec45e058d594d9b5c2681 |
User & Date: | drh 2013-05-02 00:15:01.231 |
Context
2013-05-04
| ||
20:25 | In where.c, make findTerm() a wrapper around methods to a new WhereScan object which is capable of finding all suitable matching terms, not just the first. This check-in includes some prototype functions for building WhereLoop objects. (check-in: dd92b8fa92 user: drh tags: nextgen-query-plan-exp) | |
2013-05-02
| ||
00:15 | Begin inserting some experimental code for the next generation query planner. (check-in: ccaf4c3f7e user: drh tags: nextgen-query-plan-exp) | |
2013-05-01
| ||
17:58 | Do not use a transitive constraint to an IN operator where the RHS is a constant if there exists a direct == operator to another table in an outer loop. (check-in: faedaeace9 user: drh tags: trunk) | |
Changes
Changes to src/sqliteInt.h.
︙ | ︙ | |||
2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 | u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ int iBreak; /* Jump here to break out of the loop */ int nLevel; /* Number of nested loop */ struct WhereClause *pWC; /* Decomposition of the WHERE clause */ double savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ double nRowOut; /* Estimated number of output rows */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; /* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */ #define WHERE_DISTINCT_NOOP 0 /* DISTINCT keyword not used */ | > | 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 | u8 untestedTerms; /* Not all WHERE terms resolved by outer loop */ u8 eDistinct; /* One of the WHERE_DISTINCT_* values below */ int iTop; /* The very beginning of the WHERE loop */ int iContinue; /* Jump here to continue with next record */ int iBreak; /* Jump here to break out of the loop */ int nLevel; /* Number of nested loop */ struct WhereClause *pWC; /* Decomposition of the WHERE clause */ struct WhereLoop *pLoops; /* List of all WhereLoop objects */ double savedNQueryLoop; /* pParse->nQueryLoop outside the WHERE loop */ double nRowOut; /* Estimated number of output rows */ WhereLevel a[1]; /* Information about each nest loop in WHERE */ }; /* Allowed values for WhereInfo.eDistinct and DistinctCtx.eTnctType */ #define WHERE_DISTINCT_NOOP 0 /* DISTINCT keyword not used */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
35 36 37 38 39 40 41 42 43 44 45 46 47 48 | /* Forward reference */ typedef struct WhereClause WhereClause; typedef struct WhereMaskSet WhereMaskSet; typedef struct WhereOrInfo WhereOrInfo; typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereCost WhereCost; /* ** The query generator uses an array of instances of this structure to ** help it analyze the subexpressions of the WHERE clause. Each WHERE ** clause subexpression is separated from the others by AND operators, ** usually, or sometimes subexpressions separated by OR. ** | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | /* Forward reference */ typedef struct WhereClause WhereClause; typedef struct WhereMaskSet WhereMaskSet; typedef struct WhereOrInfo WhereOrInfo; typedef struct WhereAndInfo WhereAndInfo; typedef struct WhereCost WhereCost; typedef struct WhereLoop WhereLoop; typedef struct WherePath WherePath; typedef struct WhereTerm WhereTerm; /* ** Each instance of this object represents a way of evaluating one ** term of a join. The WhereClause object holds a table of these ** objects using (iTab,prereq,iOb,nOb) as the primary key. Note that the ** same join term might have multiple associated WhereLoop objects. */ struct WhereLoop { Bitmask prereq; /* Bitmask of other loops that must run first */ int iTab; /* Index of the table coded by this loop */ u16 iOb, nOb; /* ORDER BY terms satisfied by this strategy */ double rSetup; /* One-time setup cost (ex: create transient index) */ double rRun; /* Cost of running each loop */ double nOut; /* Estimated number of output rows */ u32 wsFlags; /* WHERE_* flags describing the plan */ u16 nEq; /* Number of equality constraints */ u16 nTerm; /* Number of entries in aTerm[] */ Index *pIndex; /* Index used */ WhereTerm *aTerm; /* WhereTerms used */ WhereLoop *pNextLoop; /* Next WhereLoop object in the WhereClause */ }; /* ** Each instance of this object holds a sequence of WhereLoop objects ** that implement some or all of the entire query plan. */ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ double nRow; /* Estimated number of rows generated by this path */ double rCost; /* Total cost of this path */ WhereLoop *aLoop[1]; /* Array of WhereLoop objects implementing this path */ WherePath *pNextPath; /* Next path in order of increasing cost */ WherePath *pPrevPath; /* Previous path in cost order */ }; /* ** The query generator uses an array of instances of this structure to ** help it analyze the subexpressions of the WHERE clause. Each WHERE ** clause subexpression is separated from the others by AND operators, ** usually, or sometimes subexpressions separated by OR. ** |
︙ | ︙ | |||
87 88 89 90 91 92 93 | ** bits in the Bitmask. So, in the example above, the cursor numbers ** would be mapped into integers 0 through 7. ** ** The number of terms in a join is limited by the number of bits ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite ** is only able to process joins with 64 or fewer tables. */ | < | 124 125 126 127 128 129 130 131 132 133 134 135 136 137 | ** bits in the Bitmask. So, in the example above, the cursor numbers ** would be mapped into integers 0 through 7. ** ** The number of terms in a join is limited by the number of bits ** in prereqRight and prereqAll. The default is 64 bits, hence SQLite ** is only able to process joins with 64 or fewer tables. */ struct WhereTerm { Expr *pExpr; /* Pointer to the subexpression that is this term */ int iParent; /* Disable pWC->a[iParent] when this term disabled */ int leftCursor; /* Cursor number of X in "X <op> <expr>" */ union { int leftColumn; /* Column number of X in "X <op> <expr>" */ WhereOrInfo *pOrInfo; /* Extra information if (eOperator & WO_OR)!=0 */ |
︙ | ︙ | |||
1789 1790 1791 1792 1793 1794 1795 | WhereBestIdx sBOI; sBOI = *p; sBOI.pOrderBy = 0; sBOI.pDistinct = 0; sBOI.ppIdxInfo = 0; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ | | | | 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 | WhereBestIdx sBOI; sBOI = *p; sBOI.pOrderBy = 0; sBOI.pDistinct = 0; sBOI.ppIdxInfo = 0; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ /*WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", (pOrTerm - pOrWC->a), (pTerm - pWC->a) ));*/ if( (pOrTerm->eOperator& WO_AND)!=0 ){ sBOI.pWC = &pOrTerm->u.pAndInfo->wc; bestIndex(&sBOI); }else if( pOrTerm->leftCursor==iCur ){ WhereClause tempWC; tempWC.pParse = pWC->pParse; tempWC.pMaskSet = pWC->pMaskSet; |
︙ | ︙ | |||
1818 1819 1820 1821 1822 1823 1824 | used |= sBOI.cost.used; if( rTotal>=p->cost.rCost ) break; } /* If there is an ORDER BY clause, increase the scan cost to account ** for the cost of the sort. */ if( p->pOrderBy!=0 ){ | | | | | 1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 | used |= sBOI.cost.used; if( rTotal>=p->cost.rCost ) break; } /* If there is an ORDER BY clause, increase the scan cost to account ** for the cost of the sort. */ if( p->pOrderBy!=0 ){ /*WHERETRACE(("... sorting increases OR cost %.9g to %.9g\n", rTotal, rTotal+nRow*estLog(nRow)));*/ rTotal += nRow*estLog(nRow); } /* If the cost of scanning using this OR term for optimization is ** 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; |
︙ | ︙ | |||
1923 1924 1925 1926 1927 1928 1929 | return; } /* Search for any equality comparison term */ pWCEnd = &pWC->a[pWC->nTerm]; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){ | | | | 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 | return; } /* Search for any equality comparison term */ pWCEnd = &pWC->a[pWC->nTerm]; for(pTerm=pWC->a; pTerm<pWCEnd; pTerm++){ if( termCanDriveIndex(pTerm, pSrc, p->notReady) ){ /*WHERETRACE(("auto-index reduces cost from %.1f to %.1f\n", p->cost.rCost, costTempIdx));*/ p->cost.rCost = costTempIdx; p->cost.plan.nRow = logN + 1; p->cost.plan.wsFlags = WHERE_TEMP_INDEX; p->cost.used = pTerm->prereqRight; break; } } |
︙ | ︙ | |||
2109 2110 2111 2112 2113 2114 2115 | struct sqlite3_index_constraint *pIdxCons; struct sqlite3_index_orderby *pIdxOrderBy; struct sqlite3_index_constraint_usage *pUsage; WhereTerm *pTerm; int nOrderBy; sqlite3_index_info *pIdxInfo; | | | 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 | struct sqlite3_index_constraint *pIdxCons; struct sqlite3_index_orderby *pIdxOrderBy; struct sqlite3_index_constraint_usage *pUsage; WhereTerm *pTerm; int nOrderBy; sqlite3_index_info *pIdxInfo; /*WHERETRACE(("Recomputing index info for %s...\n", pSrc->pTab->zName));*/ /* Count the number of possible WHERE clause constraints referring ** to this virtual table */ for(i=nTerm=0, pTerm=pWC->a; i<pWC->nTerm; i++, pTerm++){ if( pTerm->leftCursor != pSrc->iCursor ) continue; assert( IsPowerOfTwo(pTerm->eOperator & ~WO_EQUIV) ); testcase( pTerm->eOperator & WO_IN ); |
︙ | ︙ | |||
2218 2219 2220 2221 2222 2223 2224 | ** that this is required. */ static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){ sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab; int i; int rc; | | | 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 | ** that this is required. */ static int vtabBestIndex(Parse *pParse, Table *pTab, sqlite3_index_info *p){ sqlite3_vtab *pVtab = sqlite3GetVTable(pParse->db, pTab)->pVtab; int i; int rc; /*WHERETRACE(("xBestIndex for %s\n", pTab->zName));*/ TRACE_IDX_INPUTS(p); rc = pVtab->pModule->xBestIndex(pVtab, p); TRACE_IDX_OUTPUTS(p); if( rc!=SQLITE_OK ){ if( rc==SQLITE_NOMEM ){ pParse->db->mallocFailed = 1; |
︙ | ︙ | |||
2729 2730 2731 2732 2733 2734 2735 | } if( rc==SQLITE_OK ){ if( iUpper<=iLower ){ *pRangeDiv = (double)p->aiRowEst[0]; }else{ *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower); } | | | | 2765 2766 2767 2768 2769 2770 2771 2772 2773 2774 2775 2776 2777 2778 2779 2780 | } if( rc==SQLITE_OK ){ if( iUpper<=iLower ){ *pRangeDiv = (double)p->aiRowEst[0]; }else{ *pRangeDiv = (double)p->aiRowEst[0]/(double)(iUpper - iLower); } /*WHERETRACE(("range scan regions: %u..%u div=%g\n", (u32)iLower, (u32)iUpper, *pRangeDiv));*/ return SQLITE_OK; } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(p); UNUSED_PARAMETER(nEq); |
︙ | ︙ | |||
2787 2788 2789 2790 2791 2792 2793 | if( rc ) goto whereEqualScanEst_cancel; }else{ pRhs = sqlite3ValueNew(pParse->db); } if( pRhs==0 ) return SQLITE_NOTFOUND; rc = whereKeyStats(pParse, p, pRhs, 0, a); if( rc==SQLITE_OK ){ | | | 2823 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2834 2835 2836 2837 | if( rc ) goto whereEqualScanEst_cancel; }else{ pRhs = sqlite3ValueNew(pParse->db); } if( pRhs==0 ) return SQLITE_NOTFOUND; rc = whereKeyStats(pParse, p, pRhs, 0, a); if( rc==SQLITE_OK ){ /*WHERETRACE(("equality scan regions: %d\n", (int)a[1]));*/ *pnRow = a[1]; } whereEqualScanEst_cancel: sqlite3ValueFree(pRhs); return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ |
︙ | ︙ | |||
2833 2834 2835 2836 2837 2838 2839 | nEst = p->aiRowEst[0]; rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst); nRowEst += nEst; } if( rc==SQLITE_OK ){ if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0]; *pnRow = nRowEst; | | | 2869 2870 2871 2872 2873 2874 2875 2876 2877 2878 2879 2880 2881 2882 2883 | nEst = p->aiRowEst[0]; rc = whereEqualScanEst(pParse, p, pList->a[i].pExpr, &nEst); nRowEst += nEst; } if( rc==SQLITE_OK ){ if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0]; *pnRow = nRowEst; /*WHERETRACE(("IN row estimate: est=%g\n", nRowEst));*/ } return rc; } #endif /* defined(SQLITE_ENABLE_STAT3) */ /* ** Check to see if column iCol of the table with cursor iTab will appear |
︙ | ︙ | |||
3045 3046 3047 3048 3049 3050 3051 | uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ Expr *pRight = pConstraint->pExpr->pRight; if( pRight->op==TK_COLUMN ){ | | | | | 3081 3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092 3093 3094 3095 3096 3097 3098 | uniqueNotNull = 0; isEq = 1; /* "X IS NULL" means X has only a single value */ }else if( pConstraint->prereqRight==0 ){ isEq = 1; /* Constraint "X=constant" means X has only a single value */ }else{ Expr *pRight = pConstraint->pExpr->pRight; if( pRight->op==TK_COLUMN ){ /*WHERETRACE((" .. isOrderedColumn(tab=%d,col=%d)", pRight->iTable, pRight->iColumn));*/ isEq = isOrderedColumn(p, pRight->iTable, pRight->iColumn); /*WHERETRACE((" -> isEq=%d\n", isEq));*/ /* If the constraint is of the form X=Y where Y is an ordered value ** in an outer loop, then make sure the sort order of Y matches the ** sort order required for X. */ if( isMatch && isEq>=2 && isEq!=pOBItem->sortOrder+2 ){ testcase( isEq==2 ); testcase( isEq==3 ); |
︙ | ︙ | |||
3315 3316 3317 3318 3319 3320 3321 | char bDist = bDistInit; /* True if index cannot help with DISTINCT */ char 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 | | | | 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 | char bDist = bDistInit; /* True if index cannot help with DISTINCT */ char 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 /*WHERETRACE(( " %s(%s):\n", pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk") ));*/ memset(&pc, 0, sizeof(pc)); pc.plan.nOBSat = nPriorSat; /* Determine the values of pc.plan.nEq and nInMul */ for(pc.plan.nEq=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); |
︙ | ︙ | |||
3399 3400 3401 3402 3403 3404 3405 | ** 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. */ if( bSort && (pSrc->jointype & JT_LEFT)==0 ){ int bRev = 2; int bObUnique = 0; | | | | | 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 | ** 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. */ if( bSort && (pSrc->jointype & JT_LEFT)==0 ){ int bRev = 2; int bObUnique = 0; /*WHERETRACE((" --> before isSortIndex: nPriorSat=%d\n",nPriorSat));*/ pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique); /*WHERETRACE((" --> after isSortIndex: bRev=%d bObU=%d nOBSat=%d\n", bRev, bObUnique, pc.plan.nOBSat));*/ if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){ pc.plan.wsFlags |= WHERE_ORDERED; if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE; } if( nOrderBy==pc.plan.nOBSat ){ bSort = 0; pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE; |
︙ | ︙ | |||
3630 3631 3632 3633 3634 3635 3636 | pc.plan.nRow /= 2; } } if( pc.plan.nRow<2 ) pc.plan.nRow = 2; } | | | | 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 | pc.plan.nRow /= 2; } } if( pc.plan.nRow<2 ) pc.plan.nRow = 2; } /*WHERETRACE(( " 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 nOBSat=%d\n", pc.plan.nEq, nInMul, (int)rangeDiv, bSort, bLookup, pc.plan.wsFlags, p->notReady, log10N, pc.plan.nRow, pc.rCost, pc.used, 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; |
︙ | ︙ | |||
3673 3674 3675 3676 3677 3678 3679 | 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 ); | | | | 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 | 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 cost=%.1f\n", p->cost.plan.u.pIdx ? p->cost.plan.u.pIdx->zName : "ipk", p->cost.rCost));*/ bestOrClauseIndex(p); bestAutomaticIndex(p); p->cost.plan.wsFlags |= eqTermMask; } /* |
︙ | ︙ | |||
4924 4925 4926 4927 4928 4929 4930 4931 4932 4933 4934 4935 4936 4937 | ** analysis only. */ char sqlite3_query_plan[BMS*2*40]; /* Text of the join */ static int nQPlan = 0; /* Next free slow in _query_plan[] */ #endif /* SQLITE_TEST */ /* ** Free a WhereInfo structure */ static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ if( ALWAYS(pWInfo) ){ int i; | > > > > > > > | 4960 4961 4962 4963 4964 4965 4966 4967 4968 4969 4970 4971 4972 4973 4974 4975 4976 4977 4978 4979 4980 | ** analysis only. */ char sqlite3_query_plan[BMS*2*40]; /* Text of the join */ static int nQPlan = 0; /* Next free slow in _query_plan[] */ #endif /* SQLITE_TEST */ /* ** Delete a WhereLoop object */ static void whereLoopDelete(sqlite3 *db, WhereLoop *p){ sqlite3DbFree(db, p->aTerm); sqlite3DbFree(db, p); } /* ** Free a WhereInfo structure */ static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ if( ALWAYS(pWInfo) ){ int i; |
︙ | ︙ | |||
4949 4950 4951 4952 4953 4954 4955 4956 4957 4958 4959 4960 4961 4962 4963 4964 4965 | if( pIdx ){ sqlite3DbFree(db, pIdx->zColAff); sqlite3DbFree(db, pIdx); } } } whereClauseClear(pWInfo->pWC); sqlite3DbFree(db, pWInfo); } } /* ** Generate the beginning of the loop used for WHERE clause processing. ** The return value is a pointer to an opaque structure that contains ** information needed to terminate the loop. Later, the calling routine ** should invoke sqlite3WhereEnd() with the return value of this function | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4992 4993 4994 4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 5084 5085 5086 5087 5088 5089 5090 5091 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 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 | if( pIdx ){ sqlite3DbFree(db, pIdx->zColAff); sqlite3DbFree(db, pIdx); } } } whereClauseClear(pWInfo->pWC); while( pWInfo->pLoops ){ WhereLoop *p = pWInfo->pLoops; pWInfo->pLoops = p->pNextLoop; whereLoopDelete(db, p); } sqlite3DbFree(db, pWInfo); } } /* ** Insert or replace a WhereLoop entry using the template supplied. ** ** An existing WhereLoop entry might be overwritten if the new template ** is better and has fewer dependencies. Or the template will be ignored ** and no insert will occur if an existing WhereLoop is faster and has ** fewer dependencies than the template. Otherwise a new WhereLoop is ** added based no the template. */ static int whereLoopInsert(WhereInfo *pWInfo, WhereLoop *pTemplate){ WhereLoop **ppPrev, *p; sqlite3 *db = pWInfo->pParse->db; /* Search for an existing WhereLoop to overwrite, or which takes ** priority over pTemplate. */ for(ppPrev=&pWInfo->pLoops, p=*ppPrev; p; ppPrev=&p->pNextLoop, p=*ppPrev){ if( p->iTab!=pTemplate->iTab ) continue; if( (p->prereq & pTemplate->prereq)==p->prereq && p->nOb>=pTemplate->nOb && p->iOb==pTemplate->iOb && p->rSetup<=pTemplate->rSetup && p->rRun<=pTemplate->rRun ){ /* Already holding an equal or better WhereLoop. ** Return without changing or adding anything */ return SQLITE_OK; } if( (p->prereq & pTemplate->prereq)==pTemplate->prereq && p->nOb<=pTemplate->nOb && p->iOb==pTemplate->iOb && p->rSetup>=pTemplate->rSetup && p->rRun>=pTemplate->rRun ){ /* Overwrite an existing WhereLoop with a better one */ sqlite3DbFree(db, p->aTerm); *ppPrev = p->pNextLoop; break; } } /* If we reach this point it means that either p[] should be overwritten ** with pTemplate[] if p[] exists, or if p==NULL then allocate a new ** WhereLoop and insert it. */ if( p==0 ){ p = sqlite3DbMallocRaw(db, sizeof(WhereLoop)); if( p==0 ) return SQLITE_NOMEM; } *p = *pTemplate; p->pNextLoop = pWInfo->pLoops; pWInfo->pLoops = p; if( pTemplate->nTerm<=0 ) return SQLITE_OK; p->aTerm = sqlite3DbMallocRaw(db, pTemplate->nTerm*sizeof(p->aTerm[0])); if( p->aTerm==0 ){ p->nTerm = 0; return SQLITE_NOMEM; } memcpy(p->aTerm, pTemplate->aTerm, pTemplate->nTerm*sizeof(p->aTerm[0])); return SQLITE_OK; } /* ** Add all WhereLoop objects for the iTab-th table of the join. That ** table is guaranteed to be a b-tree table, not a virtual table. */ static void whereLoopAddBtree( WhereInfo *pWInfo, /* WHERE clause information */ int iTab, /* The table to process */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ WhereLoop *pNew; /* Template WhereLoop object */ sqlite3 *db = pWInfo->pParse->db; pNew = sqlite3DbMallocZero(db, sizeof(*pNew)); if( pNew==0 ) return; /* Insert a full table scan */ pNew->iTab = iTab; pNew->rSetup = (double)0; pNew->rRun = (double)1000000; pNew->nOut = (double)1000000; whereLoopInsert(pWInfo, pNew); whereLoopDelete(db, pNew); } /* ** Add all WhereLoop objects for the iTab-th table of the join. That ** table is guaranteed to be a virtual table. */ static void whereLoopAddVirtual( WhereInfo *pWInfo, /* WHERE clause information */ int iTab, /* The table to process */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ } /* ** Add all WhereLoop objects for all tables */ static void whereLoopAddAll(WhereInfo *pWInfo){ Bitmask mExtra = 0; Bitmask mPrior = 0; int iTab; SrcList *pTabList = pWInfo->pTabList; struct SrcList_item *pItem; WhereClause *pWC = pWInfo->pWC; sqlite3 *db = pWInfo->pParse->db; /* Loop over the tables in the join, from left to right */ for(iTab=0, pItem=pTabList->a; iTab<pTabList->nSrc; iTab++, pItem++){ if( IsVirtual(pItem->pTab) ){ whereLoopAddVirtual(pWInfo, iTab, mExtra); }else{ whereLoopAddBtree(pWInfo, iTab, mExtra); } mPrior |= getMask(pWC->pMaskSet, pItem->iCursor); if( (pItem->jointype & (JT_LEFT|JT_CROSS))!=0 ){ mExtra = mPrior; } if( db->mallocFailed ) break; } } /* ** Generate the beginning of the loop used for WHERE clause processing. ** The return value is a pointer to an opaque structure that contains ** information needed to terminate the loop. Later, the calling routine ** should invoke sqlite3WhereEnd() with the return value of this function |
︙ | ︙ | |||
5182 5183 5184 5185 5186 5187 5188 5189 5190 5191 5192 5193 5194 5195 | ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT. */ if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){ pDistinct = 0; pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } /* Chose the best index to use for each table in the FROM clause. ** ** This loop fills in the following fields: ** ** pWInfo->a[].pIdx The index to use for this level of the loop. ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 5355 5356 5357 5358 5359 5360 5361 5362 5363 5364 5365 5366 5367 5368 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 | ** If it is, then set pDistinct to NULL and WhereInfo.eDistinct to ** WHERE_DISTINCT_UNIQUE to tell the caller to ignore the DISTINCT. */ if( pDistinct && isDistinctRedundant(pParse, pTabList, sWBI.pWC, pDistinct) ){ pDistinct = 0; pWInfo->eDistinct = WHERE_DISTINCT_UNIQUE; } /* Construct the WhereLoop objects */ WHERETRACE(("*** Optimizer Start ***\n")); whereLoopAddAll(pWInfo); /* Display all of the WhereLoop objects if wheretrace is enabled */ #if defined(SQLITE_DEBUG) \ && (defined(SQLITE_TEST) || defined(SQLITE_ENABLE_WHERETRACE)) if( sqlite3WhereTrace ){ WhereLoop *p; int nb = 2*((nTabList+15)/16); for(p=pWInfo->pLoops; p; p=p->pNextLoop){ struct SrcList_item *pItem = pTabList->a + p->iTab; Table *pTab = pItem->pTab; sqlite3DebugPrintf("%02d.%0*llx", p->iTab, nb, p->prereq); sqlite3DebugPrintf(" %s", pItem->zAlias ? pItem->zAlias : pTab->zName); if( p->pIndex ){ sqlite3DebugPrintf(" index %s nEq %d", p->pIndex->zName, p->nEq); }else{ sqlite3DebugPrintf("\n"); } sqlite3DebugPrintf(" wsFlags %08x OB %d,%d nTerm %d\n", p->wsFlags, p->iOb, p->nOb, p->nTerm); sqlite3DebugPrintf(" cost %.2e + %.2e nOut %.2e\n", p->prereq, p->rSetup, p->rRun, p->nOut); } } #endif /* Chose the best index to use for each table in the FROM clause. ** ** This loop fills in the following fields: ** ** pWInfo->a[].pIdx The index to use for this level of the loop. ** pWInfo->a[].wsFlags WHERE_xxx flags associated with pIdx |
︙ | ︙ | |||
5203 5204 5205 5206 5207 5208 5209 | ** clause. */ sWBI.notValid = ~(Bitmask)0; sWBI.pOrderBy = pOrderBy; sWBI.n = nTabList; sWBI.pDistinct = pDistinct; andFlags = ~0; | < | | 5405 5406 5407 5408 5409 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 | ** clause. */ sWBI.notValid = ~(Bitmask)0; sWBI.pOrderBy = pOrderBy; sWBI.n = nTabList; sWBI.pDistinct = pDistinct; andFlags = ~0; 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 ckOptimal; /* Do the optimal scan check */ 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 |
︙ | ︙ | |||
5300 5301 5302 5303 5304 5305 5306 | if( (m & sWBI.notValid)==0 ){ assert( j>iFrom ); continue; } sWBI.notReady = (isOptimal ? m : sWBI.notValid); if( sWBI.pSrc->pIndex==0 ) nUnconstrained++; | | | | 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 | if( (m & sWBI.notValid)==0 ){ assert( j>iFrom ); continue; } sWBI.notReady = (isOptimal ? m : sWBI.notValid); if( sWBI.pSrc->pIndex==0 ) nUnconstrained++; /*WHERETRACE((" === trying table %d (%s) with isOptimal=%d ===\n", j, sWBI.pSrc->pTab->zName, isOptimal));*/ assert( sWBI.pSrc->pTab ); #ifndef SQLITE_OMIT_VIRTUALTABLE if( IsVirtual(sWBI.pSrc->pTab) ){ sWBI.ppIdxInfo = &pWInfo->a[j].pIdxInfo; bestVirtualIndex(&sWBI); }else #endif |
︙ | ︙ | |||
5331 5332 5333 5334 5335 5336 5337 | pWInfo->a[j].rOptCost = sWBI.cost.rCost; }else if( ckOptimal ){ /* If two or more tables have nearly the same outer loop cost, but ** very different inner loop (optimal) cost, we want to choose ** for the outer loop that table which benefits the least from ** being in the inner loop. The following code scales the ** outer loop cost estimate to accomplish that. */ | | | | 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 | pWInfo->a[j].rOptCost = sWBI.cost.rCost; }else if( ckOptimal ){ /* If two or more tables have nearly the same outer loop cost, but ** very different inner loop (optimal) cost, we want to choose ** for the outer loop that table which benefits the least from ** being in the inner loop. The following code scales the ** outer loop cost estimate to accomplish that. */ /*WHERETRACE((" scaling cost from %.1f to %.1f\n", sWBI.cost.rCost, sWBI.cost.rCost/pWInfo->a[j].rOptCost));*/ sWBI.cost.rCost /= pWInfo->a[j].rOptCost; } /* 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 |
︙ | ︙ | |||
5363 5364 5365 5366 5367 5368 5369 | ** is defined by the compareCost() function above. */ if( (sWBI.cost.used&sWBI.notValid)==0 /* (1) */ && (nUnconstrained==0 || sWBI.pSrc->pIndex==0 /* (3) */ || NEVER((sWBI.cost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)) && (bestJ<0 || compareCost(&sWBI.cost, &bestPlan)) /* (4) */ ){ | | | | | | 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 | ** is defined by the compareCost() function above. */ if( (sWBI.cost.used&sWBI.notValid)==0 /* (1) */ && (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; } /* In a join like "w JOIN x LEFT JOIN y JOIN z" make sure that ** table y (and not table z) is always the next inner loop inside ** of table x. */ if( (sWBI.pSrc->jointype & JT_LEFT)!=0 ) break; } } assert( bestJ>=0 ); assert( sWBI.notValid & getMask(pMaskSet, pTabList->a[bestJ].iCursor) ); assert( bestJ==iFrom || (pTabList->a[iFrom].jointype & JT_LEFT)==0 ); testcase( bestJ>iFrom && (pTabList->a[iFrom].jointype & JT_CROSS)!=0 ); testcase( bestJ>iFrom && bestJ<nTabList-1 && (pTabList->a[bestJ+1].jointype & JT_LEFT)!=0 ); /*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; |
︙ | ︙ |