Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add the ability to use indices for constraints of the form "x IS NOT NULL" when sqlite_stat2 is available and most entries for column x are NULL. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | stat2-enhancement |
Files: | files | file ages | folders |
SHA1: |
5d5bddd290e71a7b03bcc23ff29881c2 |
User & Date: | drh 2011-01-22 00:10:45.721 |
Context
2011-01-24
| ||
15:11 | Change the cost estimator in the query planner to take into account the logN rowid lookup cost when going from an index to a table. (check-in: b442525b0b user: drh tags: stat2-enhancement) | |
2011-01-22
| ||
00:10 | Add the ability to use indices for constraints of the form "x IS NOT NULL" when sqlite_stat2 is available and most entries for column x are NULL. (check-in: 5d5bddd290 user: drh tags: stat2-enhancement) | |
2011-01-21
| ||
18:18 | Adjustments to the result row estimator for the IN operator so that it gives the same estimates as the equivalent OR operator. Test cases for the same. (check-in: c82cb9c028 user: drh tags: stat2-enhancement) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
113 114 115 116 117 118 119 | #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */ #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */ #define TERM_CODED 0x04 /* This term is already coded */ #define TERM_COPIED 0x08 /* Has a child */ #define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */ #define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */ #define TERM_OR_OK 0x40 /* Used during OR-clause processing */ | | | 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 | #define TERM_DYNAMIC 0x01 /* Need to call sqlite3ExprDelete(db, pExpr) */ #define TERM_VIRTUAL 0x02 /* Added by the optimizer. Do not code */ #define TERM_CODED 0x04 /* This term is already coded */ #define TERM_COPIED 0x08 /* Has a child */ #define TERM_ORINFO 0x10 /* Need to free the WhereTerm.u.pOrInfo object */ #define TERM_ANDINFO 0x20 /* Need to free the WhereTerm.u.pAndInfo obj */ #define TERM_OR_OK 0x40 /* Used during OR-clause processing */ #define TERM_VNULL 0x80 /* Manufactured x>NULL or x<=NULL term */ /* ** An instance of the following structure holds all information about a ** WHERE clause. Mostly this is a container for one or more WhereTerms. */ struct WhereClause { Parse *pParse; /* The parser context */ |
︙ | ︙ | |||
207 208 209 210 211 212 213 214 215 216 217 218 219 220 | #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ #define WO_AND 0x200 /* Two or more AND-connected terms */ #define WO_ALL 0xfff /* Mask of all possible WO_* values */ #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ /* ** Value for wsFlags returned by bestIndex() and stored in ** WhereLevel.wsFlags. These flags determine which search | > | 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 | #define WO_LE (WO_EQ<<(TK_LE-TK_EQ)) #define WO_GT (WO_EQ<<(TK_GT-TK_EQ)) #define WO_GE (WO_EQ<<(TK_GE-TK_EQ)) #define WO_MATCH 0x040 #define WO_ISNULL 0x080 #define WO_OR 0x100 /* Two or more OR-connected terms */ #define WO_AND 0x200 /* Two or more AND-connected terms */ #define WO_NOOP 0x800 /* This term does not restrict search space */ #define WO_ALL 0xfff /* Mask of all possible WO_* values */ #define WO_SINGLE 0x0ff /* Mask of all non-compound WO_* values */ /* ** Value for wsFlags returned by bestIndex() and stored in ** WhereLevel.wsFlags. These flags determine which search |
︙ | ︙ | |||
1057 1058 1059 1060 1061 1062 1063 | exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; pTerm->nChild = 1; }else{ sqlite3ExprListDelete(db, pList); } | < | | 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 | exprAnalyze(pSrc, pWC, idxNew); pTerm = &pWC->a[idxTerm]; pWC->a[idxNew].iParent = idxTerm; pTerm->nChild = 1; }else{ sqlite3ExprListDelete(db, pList); } pTerm->eOperator = WO_NOOP; /* case 1 trumps case 2 */ } } } #endif /* !SQLITE_OMIT_OR_OPTIMIZATION && !SQLITE_OMIT_SUBQUERY */ /* |
︙ | ︙ | |||
1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 | pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; pNewTerm->prereqAll = pTerm->prereqAll; } } #endif /* SQLITE_OMIT_VIRTUALTABLE */ /* 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; } /* | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345 1346 1347 1348 1349 1350 1351 1352 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 | pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; pNewTerm->prereqAll = pTerm->prereqAll; } } #endif /* SQLITE_OMIT_VIRTUALTABLE */ #ifdef SQLITE_ENABLE_STAT2 /* When sqlite_stat2 histogram data is available an operator of the ** form "x IS NOT NULL" can sometimes be evaluated more efficiently ** as "x>NULL" if x is not an INTEGER PRIMARY KEY. So construct a ** virtual term of that form. ** ** Note that the virtual term must be tagged with TERM_VNULL. This ** TERM_VNULL tag will suppress the not-null check at the beginning ** of the loop. Without the TERM_VNULL flag, the not-null check at ** the start of the loop will prevent any results from being returned. */ if( pExpr->op==TK_NOTNULL && pExpr->pLeft->iColumn>=0 ){ Expr *pNewExpr; Expr *pLeft = pExpr->pLeft; int idxNew; WhereTerm *pNewTerm; pNewExpr = sqlite3PExpr(pParse, TK_GT, sqlite3ExprDup(db, pLeft, 0), sqlite3PExpr(pParse, TK_NULL, 0, 0, 0), 0); idxNew = whereClauseInsert(pWC, pNewExpr, TERM_VIRTUAL|TERM_DYNAMIC|TERM_VNULL); testcase( idxNew==0 ); pNewTerm = &pWC->a[idxNew]; pNewTerm->leftCursor = pLeft->iTable; pNewTerm->u.leftColumn = pLeft->iColumn; pNewTerm->eOperator = WO_GT; pNewTerm->iParent = idxTerm; pTerm = &pWC->a[idxTerm]; pTerm->nChild = 1; pTerm->wtFlags |= TERM_COPIED; pNewTerm->prereqAll = pTerm->prereqAll; } #endif /* SQLITE_ENABLE_STAT2 */ /* 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; } /* |
︙ | ︙ | |||
2457 2458 2459 2460 2461 2462 2463 | range_est_fallback: #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(p); UNUSED_PARAMETER(nEq); #endif assert( pLower || pUpper ); | < | < > | < | 2493 2494 2495 2496 2497 2498 2499 2500 2501 2502 2503 2504 2505 2506 2507 2508 2509 | range_est_fallback: #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(p); UNUSED_PARAMETER(nEq); #endif assert( pLower || pUpper ); *piEst = 100; if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ) *piEst /= 3; if( pUpper ) *piEst /= 3; return rc; } #ifdef SQLITE_ENABLE_STAT2 /* ** Estimate the number of rows that will be returned based on ** an equality constraint x=VALUE and where that VALUE occurs in |
︙ | ︙ | |||
2932 2933 2934 2935 2936 2937 2938 | int k; /* Loop counter */ int nSkipEq = 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; nRow>2 && k; k--, pTerm++){ | | | 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 | int k; /* Loop counter */ int nSkipEq = 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; nRow>2 && k; k--, pTerm++){ if( pTerm->wtFlags & TERM_VIRTUAL ) continue; if( (pTerm->prereqAll & notValid)!=thisTab ) continue; if( pTerm->eOperator & (WO_EQ|WO_IN|WO_ISNULL) ){ if( nSkipEq ){ /* Ignore the first nEq equality matches since the index ** has already accounted for these */ nSkipEq--; }else{ |
︙ | ︙ | |||
2954 2955 2956 2957 2958 2959 2960 | ** has already accounted for these */ nSkipRange--; }else{ /* Assume each additional range constraint reduces the result ** set size by a factor of 3 */ nRow /= 3; } | | | 2988 2989 2990 2991 2992 2993 2994 2995 2996 2997 2998 2999 3000 3001 3002 | ** has already accounted for these */ nSkipRange--; }else{ /* Assume each additional range constraint reduces the result ** set size by a factor of 3 */ nRow /= 3; } }else if( pTerm->eOperator!=WO_NOOP ){ /* Any other expression lowers the output row count by half */ nRow /= 2; } } if( nRow<2 ) nRow = 2; } |
︙ | ︙ | |||
3792 3793 3794 3795 3796 3797 3798 | start_constraints = pRangeStart || nEq>0; /* Seek the index cursor to the start of the range. */ nConstraint = nEq; if( pRangeStart ){ Expr *pRight = pRangeStart->pExpr->pRight; sqlite3ExprCode(pParse, pRight, regBase+nEq); | > | > | 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 | start_constraints = pRangeStart || nEq>0; /* Seek the index cursor to the start of the range. */ nConstraint = nEq; if( pRangeStart ){ Expr *pRight = pRangeStart->pExpr->pRight; sqlite3ExprCode(pParse, pRight, regBase+nEq); if( (pRangeStart->wtFlags & TERM_VNULL)==0 ){ sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt); } if( zStartAff ){ if( sqlite3CompareAffinity(pRight, zStartAff[nEq])==SQLITE_AFF_NONE){ /* Since the comparison is to be performed with no conversions ** applied to the operands, set the affinity to apply to pRight to ** SQLITE_AFF_NONE. */ zStartAff[nEq] = SQLITE_AFF_NONE; } |
︙ | ︙ | |||
3831 3832 3833 3834 3835 3836 3837 | ** range (if any). */ nConstraint = nEq; if( pRangeEnd ){ Expr *pRight = pRangeEnd->pExpr->pRight; sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); sqlite3ExprCode(pParse, pRight, regBase+nEq); | > | > | 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 | ** range (if any). */ nConstraint = nEq; if( pRangeEnd ){ Expr *pRight = pRangeEnd->pExpr->pRight; sqlite3ExprCacheRemove(pParse, regBase+nEq, 1); sqlite3ExprCode(pParse, pRight, regBase+nEq); if( (pRangeEnd->wtFlags & TERM_VNULL)==0 ){ sqlite3ExprCodeIsNullJump(v, pRight, regBase+nEq, addrNxt); } if( zEndAff ){ if( sqlite3CompareAffinity(pRight, zEndAff[nEq])==SQLITE_AFF_NONE){ /* Since the comparison is to be performed with no conversions ** applied to the operands, set the affinity to apply to pRight to ** SQLITE_AFF_NONE. */ zEndAff[nEq] = SQLITE_AFF_NONE; } |
︙ | ︙ |