Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Adjustments to the WHERE term scanning, to better handle scanning terms of an index. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | index-expr |
Files: | files | file ages | folders |
SHA1: |
5611130a595e7f0b6d5f21d76f2755e9 |
User & Date: | drh 2015-08-27 15:58:51.073 |
Context
2015-08-27
| ||
16:07 | Merge changes from trunk. (check-in: c80e9e8e8c user: drh tags: index-expr) | |
15:58 | Adjustments to the WHERE term scanning, to better handle scanning terms of an index. (check-in: 5611130a59 user: drh tags: index-expr) | |
2015-08-26
| ||
18:04 | Merge enhancements from trunk. (check-in: ec6ddb3d48 user: drh tags: index-expr) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
269 270 271 272 273 274 275 | Index *pIdx /* Must be compatible with this index */ ){ int j; /* memset(pScan, 0, sizeof(*pScan)); */ pScan->pOrigWC = pWC; pScan->pWC = pWC; | | | | < | > > > > > | 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 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 310 | Index *pIdx /* Must be compatible with this index */ ){ int j; /* memset(pScan, 0, sizeof(*pScan)); */ pScan->pOrigWC = pWC; pScan->pWC = pWC; if( pIdx ){ j = iColumn; iColumn = pIdx->aiColumn[j]; } if( pIdx && iColumn>=0 ){ pScan->idxaff = pIdx->pTable->aCol[iColumn].affinity; pScan->zCollName = pIdx->azColl[j]; }else{ pScan->idxaff = 0; pScan->zCollName = 0; } pScan->opMask = opMask; pScan->k = 0; pScan->aEquiv[0] = iCur; pScan->aEquiv[1] = iColumn; pScan->nEquiv = 2; pScan->iEquiv = 2; return whereScanNext(pScan); } /* ** Search for a term in the WHERE clause that is of the form "X <op> <expr>" ** where X is a reference to the iColumn of table iCur and <op> is one of ** the WO_xx operator codes specified by the op parameter. ** Return a pointer to the term. Return 0 if not found. ** ** If pIdx!=0 then search for terms matching the iColumn-th column of pIdx ** rather than the iColumn-th column of table iCur. ** ** The term returned might by Y=<expr> if there is another constraint in ** the WHERE clause that specifies that X=Y. Any such constraints will be ** identified by the WO_EQUIV bit in the pTerm->eOperator field. The ** aEquiv[] array holds X and all its equivalents, with each SQL variable ** taking up two slots in aEquiv[]. The first slot is for the cursor number ** and the second is for the column number. There are 22 slots in aEquiv[] |
︙ | ︙ | |||
370 371 372 373 374 375 376 377 378 379 380 381 382 383 | return i; } } } return -1; } /* ** Return true if the DISTINCT expression-list passed as the third argument ** is redundant. ** ** A DISTINCT list is redundant if any subset of the columns in the ** DISTINCT list are collectively unique and individually non-null. | > > > > > > > > > > > > > > > > > > | 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 | return i; } } } return -1; } /* ** Return TRUE if the iCol-th column of index pIdx is NOT NULL */ static int indexColumnNotNull(Index *pIdx, int iCol){ int j; assert( pIdx!=0 ); assert( iCol>=0 && iCol<pIdx->nColumn ); j = pIdx->aiColumn[iCol]; if( j>=0 ){ return pIdx->pTable->aCol[j].notNull; }else if( j==(-1) ){ return 1; }else{ assert( j==(-2) ); return !sqlite3ExprCanBeNull(pIdx->aColExpr->a[iCol].pExpr); } } /* ** Return true if the DISTINCT expression-list passed as the third argument ** is redundant. ** ** A DISTINCT list is redundant if any subset of the columns in the ** DISTINCT list are collectively unique and individually non-null. |
︙ | ︙ | |||
421 422 423 424 425 426 427 | ** ** 3. All of those index columns for which the WHERE clause does not ** contain a "col=X" term are subject to a NOT NULL constraint. */ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( !IsUniqueIndex(pIdx) ) continue; for(i=0; i<pIdx->nKeyCol; i++){ | < | | < | < | 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 | ** ** 3. All of those index columns for which the WHERE clause does not ** contain a "col=X" term are subject to a NOT NULL constraint. */ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( !IsUniqueIndex(pIdx) ) continue; for(i=0; i<pIdx->nKeyCol; i++){ if( 0==sqlite3WhereFindTerm(pWC, iBase, i, ~(Bitmask)0, WO_EQ, pIdx) ){ if( findIndexCol(pParse, pDistinct, iBase, pIdx, i)<0 ) break; if( indexColumnNotNull(pIdx, i)==0 ) break; } } if( i==pIdx->nKeyCol ){ /* This index implies that the DISTINCT qualifier is redundant. */ return 1; } } |
︙ | ︙ | |||
2122 2123 2124 2125 2126 2127 2128 | WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ u16 saved_nSkip; /* Original value of pNew->nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ | < < < < > > | | 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 | WhereScan scan; /* Iterator for WHERE terms */ Bitmask saved_prereq; /* Original value of pNew->prereq */ u16 saved_nLTerm; /* Original value of pNew->nLTerm */ u16 saved_nEq; /* Original value of pNew->u.btree.nEq */ u16 saved_nSkip; /* Original value of pNew->nSkip */ u32 saved_wsFlags; /* Original value of pNew->wsFlags */ LogEst saved_nOut; /* Original value of pNew->nOut */ int rc = SQLITE_OK; /* Return code */ LogEst rSize; /* Number of rows in the table */ LogEst rLogSize; /* Logarithm of table size */ WhereTerm *pTop = 0, *pBtm = 0; /* Top and bottom range constraints */ pNew = pBuilder->pNew; if( db->mallocFailed ) return SQLITE_NOMEM; assert( (pNew->wsFlags & WHERE_VIRTUALTABLE)==0 ); assert( (pNew->wsFlags & WHERE_TOP_LIMIT)==0 ); if( pNew->wsFlags & WHERE_BTM_LIMIT ){ opMask = WO_LT|WO_LE; }else if( /*pProbe->tnum<=0 ||*/ (pSrc->fg.jointype & JT_LEFT)!=0 ){ opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE; }else{ opMask = WO_EQ|WO_IN|WO_GT|WO_GE|WO_LT|WO_LE|WO_ISNULL|WO_IS; } if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE); assert( pNew->u.btree.nEq<pProbe->nColumn ); saved_nEq = pNew->u.btree.nEq; saved_nSkip = pNew->nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, saved_nEq, opMask, pProbe); pNew->rSetup = 0; rSize = pProbe->aiRowLogEst[0]; rLogSize = estLog(rSize); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ u16 eOp = pTerm->eOperator; /* Shorthand for pTerm->eOperator */ LogEst rCostIdx; LogEst nOutUnadjusted; /* nOut before IN() and WHERE adjustments */ int nIn = 0; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 int nRecValid = pBuilder->nRecValid; #endif if( (eOp==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0) && indexColumnNotNull(pProbe, saved_nEq) ){ continue; /* ignore IS [NOT] NULL constraints on NOT NULL columns */ } if( pTerm->prereqRight & pNew->maskSelf ) continue; /* Do not allow the upper bound of a LIKE optimization range constraint ** to mix with a lower range bound from some other source */ |
︙ | ︙ | |||
2202 2203 2204 2205 2206 2207 2208 2209 | /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); } assert( nIn>0 ); /* RHS always has 2 or more terms... The parser ** changes "x IN (?)" into "x=?". */ }else if( eOp & (WO_EQ|WO_IS) ){ pNew->wsFlags |= WHERE_COLUMN_EQ; | > > | | 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 | /* "x IN (value, value, ...)" */ nIn = sqlite3LogEst(pExpr->x.pList->nExpr); } assert( nIn>0 ); /* RHS always has 2 or more terms... The parser ** changes "x IN (?)" into "x=?". */ }else if( eOp & (WO_EQ|WO_IS) ){ int iCol = pProbe->aiColumn[saved_nEq]; pNew->wsFlags |= WHERE_COLUMN_EQ; assert( saved_nEq==pNew->u.btree.nEq ); if( iCol==(-1) || (nInMul==0 && saved_nEq==pProbe->nKeyCol-1) ){ if( iCol>=0 && pProbe->uniqNotNull==0 ){ pNew->wsFlags |= WHERE_UNQ_WANTED; }else{ pNew->wsFlags |= WHERE_ONEROW; } } }else if( eOp & WO_ISNULL ){ |
︙ | ︙ | |||
2254 2255 2256 2257 2258 2259 2260 | ** data, using some other estimate. */ whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); }else{ int nEq = ++pNew->u.btree.nEq; assert( eOp & (WO_ISNULL|WO_EQ|WO_IN|WO_IS) ); assert( pNew->nOut==saved_nOut ); | | | 2273 2274 2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 | ** data, using some other estimate. */ whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); }else{ int nEq = ++pNew->u.btree.nEq; assert( eOp & (WO_ISNULL|WO_EQ|WO_IN|WO_IS) ); assert( pNew->nOut==saved_nOut ); if( pTerm->truthProb<=0 && pProbe->aiColumn[saved_nEq]>=0 ){ assert( (eOp & WO_IN) || nIn==0 ); testcase( eOp & WO_IN ); pNew->nOut += pTerm->truthProb; pNew->nOut -= nIn; }else{ #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 tRowcnt nOut = 0; |
︙ | ︙ | |||
3781 3782 3783 3784 3785 3786 3787 | assert( pLoop->aLTermSpace==pLoop->aLTerm ); if( !IsUniqueIndex(pIdx) || pIdx->pPartIdxWhere!=0 || pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace) ) continue; opMask = pIdx->uniqNotNull ? (WO_EQ|WO_IS) : WO_EQ; for(j=0; j<pIdx->nKeyCol; j++){ | | | 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 | assert( pLoop->aLTermSpace==pLoop->aLTerm ); if( !IsUniqueIndex(pIdx) || pIdx->pPartIdxWhere!=0 || pIdx->nKeyCol>ArraySize(pLoop->aLTermSpace) ) continue; opMask = pIdx->uniqNotNull ? (WO_EQ|WO_IS) : WO_EQ; for(j=0; j<pIdx->nKeyCol; j++){ pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx); if( pTerm==0 ) break; testcase( pTerm->eOperator & WO_IS ); pLoop->aLTerm[j] = pTerm; } if( j!=pIdx->nKeyCol ) continue; pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED; if( pIdx->isCovering || (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){ |
︙ | ︙ |