Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch stat4-skipscan Excluding Merge-Ins
This is equivalent to a diff from fb32e374 to c96de490
2014-06-30
| ||
19:07 | Attempt to use STAT4 information to estimate the selectivity of WHERE clause terms when using the skip-scan optimization. (check-in: d09ca6d5 user: drh tags: trunk) | |
11:14 | Add makefile targets for various diagnostic tools, such as showstat4. Fix harmless compiler warnings in diagnostic tools. (check-in: 6f86d89b user: drh tags: trunk) | |
2014-06-28
| ||
19:06 | Add an OOM fault injection test for the new code on this branch. (Closed-Leaf check-in: c96de490 user: dan tags: stat4-skipscan) | |
17:35 | Add further tests to skipscan5.test. (check-in: 4b8230e8 user: dan tags: stat4-skipscan) | |
14:25 | Merge fixes from trunk with this branch. (check-in: 6af219d1 user: dan tags: stat4-skipscan) | |
2014-06-26
| ||
22:17 | Add some more IN operator tests. (check-in: fb32e374 user: mistachkin tags: trunk) | |
21:28 | Revise the affinity returned for expressions flagged as 'generic'. Fix for [9a8b09f8e6]. (check-in: 92f7ad43 user: mistachkin tags: trunk) | |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 | void sqlite3BackupRestart(sqlite3_backup *); void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *); #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 void sqlite3AnalyzeFunctions(void); int sqlite3Stat4ProbeSetValue(Parse*,Index*,UnpackedRecord**,Expr*,u8,int,int*); void sqlite3Stat4ProbeFree(UnpackedRecord*); #endif /* ** The interface to the LEMON-generated parser */ void *sqlite3ParserAlloc(void*(*)(size_t)); void sqlite3ParserFree(void*, void(*)(void*)); | > > | 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 | void sqlite3BackupRestart(sqlite3_backup *); void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *); #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 void sqlite3AnalyzeFunctions(void); int sqlite3Stat4ProbeSetValue(Parse*,Index*,UnpackedRecord**,Expr*,u8,int,int*); int sqlite3Stat4ValueFromExpr(Parse*, Expr*, u8, sqlite3_value**); void sqlite3Stat4ProbeFree(UnpackedRecord*); int sqlite3Stat4Column(sqlite3*, const void*, int, int, sqlite3_value**); #endif /* ** The interface to the LEMON-generated parser */ void *sqlite3ParserAlloc(void*(*)(size_t)); void sqlite3ParserFree(void*, void(*)(void*)); |
︙ | ︙ |
Changes to src/vdbe.h.
︙ | ︙ | |||
205 206 207 208 209 210 211 212 213 214 215 216 217 218 | void sqlite3VdbeSwap(Vdbe*,Vdbe*); VdbeOp *sqlite3VdbeTakeOpArray(Vdbe*, int*, int*); sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8); void sqlite3VdbeSetVarmask(Vdbe*, int); #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*,int); UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); typedef int (*RecordCompare)(int,const void*,UnpackedRecord*,int); RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*); | > | 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 | void sqlite3VdbeSwap(Vdbe*,Vdbe*); VdbeOp *sqlite3VdbeTakeOpArray(Vdbe*, int*, int*); sqlite3_value *sqlite3VdbeGetBoundValue(Vdbe*, int, u8); void sqlite3VdbeSetVarmask(Vdbe*, int); #ifndef SQLITE_OMIT_TRACE char *sqlite3VdbeExpandSql(Vdbe*, const char*); #endif int sqlite3MemCompare(const Mem*, const Mem*, const CollSeq*); void sqlite3VdbeRecordUnpack(KeyInfo*,int,const void*,UnpackedRecord*); int sqlite3VdbeRecordCompare(int,const void*,UnpackedRecord*,int); UnpackedRecord *sqlite3VdbeAllocUnpackedRecord(KeyInfo *, char *, int, char **); typedef int (*RecordCompare)(int,const void*,UnpackedRecord*,int); RecordCompare sqlite3VdbeFindCompare(UnpackedRecord*); |
︙ | ︙ |
Changes to src/vdbeInt.h.
︙ | ︙ | |||
390 391 392 393 394 395 396 | u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32); u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*); void sqlite3VdbeDeleteAuxData(Vdbe*, int, int); int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *); int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*); int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *); | < | 390 391 392 393 394 395 396 397 398 399 400 401 402 403 | u32 sqlite3VdbeSerialPut(unsigned char*, Mem*, u32); u32 sqlite3VdbeSerialGet(const unsigned char*, u32, Mem*); void sqlite3VdbeDeleteAuxData(Vdbe*, int, int); int sqlite2BtreeKeyCompare(BtCursor *, const void *, int, int, int *); int sqlite3VdbeIdxKeyCompare(VdbeCursor*,UnpackedRecord*,int*); int sqlite3VdbeIdxRowid(sqlite3*, BtCursor *, i64 *); int sqlite3VdbeExec(Vdbe*); int sqlite3VdbeList(Vdbe*); int sqlite3VdbeHalt(Vdbe*); int sqlite3VdbeChangeEncoding(Mem *, int); int sqlite3VdbeMemTooBig(Mem*); int sqlite3VdbeMemCopy(Mem*, const Mem*); void sqlite3VdbeMemShallowCopy(Mem*, const Mem*, int); |
︙ | ︙ |
Changes to src/vdbeaux.c.
︙ | ︙ | |||
3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 | assert( mem1.zMalloc==0 ); /* rc==0 here means that one or both of the keys ran out of fields and ** all the fields up to that point were equal. Return the the default_rc ** value. */ assert( CORRUPT_DB || pPKey2->default_rc==vdbeRecordCompareDebug(nKey1, pKey1, pPKey2) ); return pPKey2->default_rc; } /* ** This function is an optimized version of sqlite3VdbeRecordCompare() ** that (a) the first field of pPKey2 is an integer, and (b) the | > | 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 | assert( mem1.zMalloc==0 ); /* rc==0 here means that one or both of the keys ran out of fields and ** all the fields up to that point were equal. Return the the default_rc ** value. */ assert( CORRUPT_DB || pPKey2->default_rc==vdbeRecordCompareDebug(nKey1, pKey1, pPKey2) || pKeyInfo->db->mallocFailed ); return pPKey2->default_rc; } /* ** This function is an optimized version of sqlite3VdbeRecordCompare() ** that (a) the first field of pPKey2 is an integer, and (b) the |
︙ | ︙ | |||
3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 | } } assert( (res==0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)==0) || (res<0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)<0) || (res>0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)>0) || CORRUPT_DB ); return res; } /* ** Return a pointer to an sqlite3VdbeRecordCompare() compatible function ** suitable for comparing serialized records to the unpacked record passed | > | 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 | } } assert( (res==0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)==0) || (res<0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)<0) || (res>0 && vdbeRecordCompareDebug(nKey1, pKey1, pPKey2)>0) || CORRUPT_DB || pPKey2->pKeyInfo->db->mallocFailed ); return res; } /* ** Return a pointer to an sqlite3VdbeRecordCompare() compatible function ** suitable for comparing serialized records to the unpacked record passed |
︙ | ︙ |
Changes to src/vdbemem.c.
︙ | ︙ | |||
1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 | int i; FuncDefHash *pHash = &GLOBAL(FuncDefHash, sqlite3GlobalFunctions); FuncDef *aFunc = (FuncDef*)&GLOBAL(FuncDef, aAnalyzeTableFuncs); for(i=0; i<ArraySize(aAnalyzeTableFuncs); i++){ sqlite3FuncDefInsert(pHash, &aFunc[i]); } } /* ** This function is used to allocate and populate UnpackedRecord ** structures intended to be compared against sample index keys stored ** in the sqlite_stat4 table. ** ** A single call to this function attempts to populates field iVal (leftmost | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 | int i; FuncDefHash *pHash = &GLOBAL(FuncDefHash, sqlite3GlobalFunctions); FuncDef *aFunc = (FuncDef*)&GLOBAL(FuncDef, aAnalyzeTableFuncs); for(i=0; i<ArraySize(aAnalyzeTableFuncs); i++){ sqlite3FuncDefInsert(pHash, &aFunc[i]); } } /* ** Attempt to extract a value from pExpr and use it to construct *ppVal. ** ** If pAlloc is not NULL, then an UnpackedRecord object is created for ** pAlloc if one does not exist and the new value is added to the ** UnpackedRecord object. ** ** A value is extracted in the following cases: ** ** * (pExpr==0). In this case the value is assumed to be an SQL NULL, ** ** * The expression is a bound variable, and this is a reprepare, or ** ** * The expression is a literal value. ** ** On success, *ppVal is made to point to the extracted value. The caller ** is responsible for ensuring that the value is eventually freed. */ static int stat4ValueFromExpr( Parse *pParse, /* Parse context */ Expr *pExpr, /* The expression to extract a value from */ u8 affinity, /* Affinity to use */ struct ValueNewStat4Ctx *pAlloc,/* How to allocate space. Or NULL */ sqlite3_value **ppVal /* OUT: New value object (or NULL) */ ){ int rc = SQLITE_OK; sqlite3_value *pVal = 0; sqlite3 *db = pParse->db; /* Skip over any TK_COLLATE nodes */ pExpr = sqlite3ExprSkipCollate(pExpr); if( !pExpr ){ pVal = valueNew(db, pAlloc); if( pVal ){ sqlite3VdbeMemSetNull((Mem*)pVal); } }else if( pExpr->op==TK_VARIABLE || NEVER(pExpr->op==TK_REGISTER && pExpr->op2==TK_VARIABLE) ){ Vdbe *v; int iBindVar = pExpr->iColumn; sqlite3VdbeSetVarmask(pParse->pVdbe, iBindVar); if( (v = pParse->pReprepare)!=0 ){ pVal = valueNew(db, pAlloc); if( pVal ){ rc = sqlite3VdbeMemCopy((Mem*)pVal, &v->aVar[iBindVar-1]); if( rc==SQLITE_OK ){ sqlite3ValueApplyAffinity(pVal, affinity, ENC(db)); } pVal->db = pParse->db; } } }else{ rc = valueFromExpr(db, pExpr, ENC(db), affinity, &pVal, pAlloc); } assert( pVal==0 || pVal->db==db ); *ppVal = pVal; return rc; } /* ** This function is used to allocate and populate UnpackedRecord ** structures intended to be compared against sample index keys stored ** in the sqlite_stat4 table. ** ** A single call to this function attempts to populates field iVal (leftmost |
︙ | ︙ | |||
1187 1188 1189 1190 1191 1192 1193 | Index *pIdx, /* Index being probed */ UnpackedRecord **ppRec, /* IN/OUT: Probe record */ Expr *pExpr, /* The expression to extract a value from */ u8 affinity, /* Affinity to use */ int iVal, /* Array element to populate */ int *pbOk /* OUT: True if value was extracted */ ){ | | < | < > > > > > | > > > > > > > > > > > > > > > > > > | > > > > > > > > > > | | | < | < < < | > > > > | | | < < | < < < | > > > | > > > > > > > | < | < > > > > > < | < > | | 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 | Index *pIdx, /* Index being probed */ UnpackedRecord **ppRec, /* IN/OUT: Probe record */ Expr *pExpr, /* The expression to extract a value from */ u8 affinity, /* Affinity to use */ int iVal, /* Array element to populate */ int *pbOk /* OUT: True if value was extracted */ ){ int rc; sqlite3_value *pVal = 0; struct ValueNewStat4Ctx alloc; alloc.pParse = pParse; alloc.pIdx = pIdx; alloc.ppRec = ppRec; alloc.iVal = iVal; rc = stat4ValueFromExpr(pParse, pExpr, affinity, &alloc, &pVal); assert( pVal==0 || pVal->db==pParse->db ); *pbOk = (pVal!=0); return rc; } /* ** Attempt to extract a value from expression pExpr using the methods ** as described for sqlite3Stat4ProbeSetValue() above. ** ** If successful, set *ppVal to point to a new value object and return ** SQLITE_OK. If no value can be extracted, but no other error occurs ** (e.g. OOM), return SQLITE_OK and set *ppVal to NULL. Or, if an error ** does occur, return an SQLite error code. The final value of *ppVal ** is undefined in this case. */ int sqlite3Stat4ValueFromExpr( Parse *pParse, /* Parse context */ Expr *pExpr, /* The expression to extract a value from */ u8 affinity, /* Affinity to use */ sqlite3_value **ppVal /* OUT: New value object (or NULL) */ ){ return stat4ValueFromExpr(pParse, pExpr, affinity, 0, ppVal); } /* ** Extract the iCol-th column from the nRec-byte record in pRec. Write ** the column value into *ppVal. If *ppVal is initially NULL then a new ** sqlite3_value object is allocated. ** ** If *ppVal is initially NULL then the caller is responsible for ** ensuring that the value written into *ppVal is eventually freed. */ int sqlite3Stat4Column( sqlite3 *db, /* Database handle */ const void *pRec, /* Pointer to buffer containing record */ int nRec, /* Size of buffer pRec in bytes */ int iCol, /* Column to extract */ sqlite3_value **ppVal /* OUT: Extracted value */ ){ u32 t; /* a column type code */ int nHdr; /* Size of the header in the record */ int iHdr; /* Next unread header byte */ int iField; /* Next unread data byte */ int szField; /* Size of the current data field */ int i; /* Column index */ u8 *a = (u8*)pRec; /* Typecast byte array */ Mem *pMem = *ppVal; /* Write result into this Mem object */ assert( iCol>0 ); iHdr = getVarint32(a, nHdr); if( nHdr>nRec || iHdr>=nHdr ) return SQLITE_CORRUPT_BKPT; iField = nHdr; for(i=0; i<=iCol; i++){ iHdr += getVarint32(&a[iHdr], t); testcase( iHdr==nHdr ); testcase( iHdr==nHdr+1 ); if( iHdr>nHdr ) return SQLITE_CORRUPT_BKPT; szField = sqlite3VdbeSerialTypeLen(t); iField += szField; } testcase( iField==nRec ); testcase( iField==nRec+1 ); if( iField>nRec ) return SQLITE_CORRUPT_BKPT; if( pMem==0 ){ pMem = *ppVal = sqlite3ValueNew(db); if( pMem==0 ) return SQLITE_NOMEM; } sqlite3VdbeSerialGet(&a[iField-szField], t, pMem); pMem->enc = ENC(db); return SQLITE_OK; } /* ** Unless it is NULL, the argument must be an UnpackedRecord object returned ** by an earlier call to sqlite3Stat4ProbeSetValue(). This call deletes ** the object. */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 | }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){ nRet -= 20; assert( 20==sqlite3LogEst(4) ); } } return nRet; } /* ** This function is used to estimate the number of rows that will be visited ** by scanning an index for a range of values. The range may have an upper ** bound, a lower bound, or both. The WHERE clause terms that set the upper ** and lower bounds are represented by pLower and pUpper respectively. For ** example, assuming that index p is on t1(a): ** | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 | }else if( (pTerm->wtFlags & TERM_VNULL)==0 ){ nRet -= 20; assert( 20==sqlite3LogEst(4) ); } } return nRet; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 /* ** This function is called to estimate the number of rows visited by a ** range-scan on a skip-scan index. For example: ** ** CREATE INDEX i1 ON t1(a, b, c); ** SELECT * FROM t1 WHERE a=? AND c BETWEEN ? AND ?; ** ** Value pLoop->nOut is currently set to the estimated number of rows ** visited for scanning (a=? AND b=?). This function reduces that estimate ** by some factor to account for the (c BETWEEN ? AND ?) expression based ** on the stat4 data for the index. this scan will be peformed multiple ** times (once for each (a,b) combination that matches a=?) is dealt with ** by the caller. ** ** It does this by scanning through all stat4 samples, comparing values ** extracted from pLower and pUpper with the corresponding column in each ** sample. If L and U are the number of samples found to be less than or ** equal to the values extracted from pLower and pUpper respectively, and ** N is the total number of samples, the pLoop->nOut value is adjusted ** as follows: ** ** nOut = nOut * ( min(U - L, 1) / N ) ** ** If pLower is NULL, or a value cannot be extracted from the term, L is ** set to zero. If pUpper is NULL, or a value cannot be extracted from it, ** U is set to N. ** ** Normally, this function sets *pbDone to 1 before returning. However, ** if no value can be extracted from either pLower or pUpper (and so the ** estimate of the number of rows delivered remains unchanged), *pbDone ** is left as is. ** ** If an error occurs, an SQLite error code is returned. Otherwise, ** SQLITE_OK. */ static int whereRangeSkipScanEst( Parse *pParse, /* Parsing & code generating context */ WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ WhereLoop *pLoop, /* Update the .nOut value of this loop */ int *pbDone /* Set to true if at least one expr. value extracted */ ){ Index *p = pLoop->u.btree.pIndex; int nEq = pLoop->u.btree.nEq; sqlite3 *db = pParse->db; int nLower = -1; int nUpper = p->nSample+1; int rc = SQLITE_OK; u8 aff = p->pTable->aCol[ p->aiColumn[nEq] ].affinity; CollSeq *pColl; sqlite3_value *p1 = 0; /* Value extracted from pLower */ sqlite3_value *p2 = 0; /* Value extracted from pUpper */ sqlite3_value *pVal = 0; /* Value extracted from record */ pColl = sqlite3LocateCollSeq(pParse, p->azColl[nEq]); if( pLower ){ rc = sqlite3Stat4ValueFromExpr(pParse, pLower->pExpr->pRight, aff, &p1); nLower = 0; } if( pUpper && rc==SQLITE_OK ){ rc = sqlite3Stat4ValueFromExpr(pParse, pUpper->pExpr->pRight, aff, &p2); nUpper = p2 ? 0 : p->nSample; } if( p1 || p2 ){ int i; int nDiff; for(i=0; rc==SQLITE_OK && i<p->nSample; i++){ rc = sqlite3Stat4Column(db, p->aSample[i].p, p->aSample[i].n, nEq, &pVal); if( rc==SQLITE_OK && p1 ){ int res = sqlite3MemCompare(p1, pVal, pColl); if( res>=0 ) nLower++; } if( rc==SQLITE_OK && p2 ){ int res = sqlite3MemCompare(p2, pVal, pColl); if( res>=0 ) nUpper++; } } nDiff = (nUpper - nLower); if( nDiff<=0 ) nDiff = 1; /* If there is both an upper and lower bound specified, and the ** comparisons indicate that they are close together, use the fallback ** method (assume that the scan visits 1/64 of the rows) for estimating ** the number of rows visited. Otherwise, estimate the number of rows ** using the method described in the header comment for this function. */ if( nDiff!=1 || pUpper==0 || pLower==0 ){ int nAdjust = (sqlite3LogEst(p->nSample) - sqlite3LogEst(nDiff)); pLoop->nOut -= nAdjust; *pbDone = 1; WHERETRACE(0x10, ("range skip-scan regions: %u..%u adjust=%d est=%d\n", nLower, nUpper, nAdjust*-1, pLoop->nOut)); } }else{ assert( *pbDone==0 ); } sqlite3ValueFree(p1); sqlite3ValueFree(p2); sqlite3ValueFree(pVal); return rc; } #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ /* ** This function is used to estimate the number of rows that will be visited ** by scanning an index for a range of values. The range may have an upper ** bound, a lower bound, or both. The WHERE clause terms that set the upper ** and lower bounds are represented by pLower and pUpper respectively. For ** example, assuming that index p is on t1(a): ** |
︙ | ︙ | |||
2050 2051 2052 2053 2054 2055 2056 | LogEst nNew; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 Index *p = pLoop->u.btree.pIndex; int nEq = pLoop->u.btree.nEq; if( p->nSample>0 | < > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | > > > > > | 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 2197 2198 2199 2200 2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 | LogEst nNew; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 Index *p = pLoop->u.btree.pIndex; int nEq = pLoop->u.btree.nEq; if( p->nSample>0 && nEq<p->nSampleCol && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ if( nEq==pBuilder->nRecValid ){ UnpackedRecord *pRec = pBuilder->pRec; tRowcnt a[2]; u8 aff; /* Variable iLower will be set to the estimate of the number of rows in ** the index that are less than the lower bound of the range query. The ** lower bound being the concatenation of $P and $L, where $P is the ** key-prefix formed by the nEq values matched against the nEq left-most ** columns of the index, and $L is the value in pLower. ** ** Or, if pLower is NULL or $L cannot be extracted from it (because it ** is not a simple variable or literal value), the lower bound of the ** range is $P. Due to a quirk in the way whereKeyStats() works, even ** if $L is available, whereKeyStats() is called for both ($P) and ** ($P:$L) and the larger of the two returned values used. ** ** Similarly, iUpper is to be set to the estimate of the number of rows ** less than the upper bound of the range query. Where the upper bound ** is either ($P) or ($P:$U). Again, even if $U is available, both values ** of iUpper are requested of whereKeyStats() and the smaller used. */ tRowcnt iLower; tRowcnt iUpper; if( nEq==p->nKeyCol ){ aff = SQLITE_AFF_INTEGER; }else{ aff = p->pTable->aCol[p->aiColumn[nEq]].affinity; } /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; iUpper = sqlite3LogEstToInt(p->aiRowLogEst[0]); }else{ /* Note: this call could be optimized away - since the same values must ** have been requested when testing key $P in whereEqualScanEst(). */ whereKeyStats(pParse, p, pRec, 0, a); iLower = a[0]; iUpper = a[0] + a[1]; } /* If possible, improve on the iLower estimate using ($P:$L). */ if( pLower ){ int bOk; /* True if value is extracted from pExpr */ Expr *pExpr = pLower->pExpr->pRight; assert( (pLower->eOperator & (WO_GT|WO_GE))!=0 ); rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk); if( rc==SQLITE_OK && bOk ){ tRowcnt iNew; whereKeyStats(pParse, p, pRec, 0, a); iNew = a[0] + ((pLower->eOperator & WO_GT) ? a[1] : 0); if( iNew>iLower ) iLower = iNew; nOut--; } } /* If possible, improve on the iUpper estimate using ($P:$U). */ if( pUpper ){ int bOk; /* True if value is extracted from pExpr */ Expr *pExpr = pUpper->pExpr->pRight; assert( (pUpper->eOperator & (WO_LT|WO_LE))!=0 ); rc = sqlite3Stat4ProbeSetValue(pParse, p, &pRec, pExpr, aff, nEq, &bOk); if( rc==SQLITE_OK && bOk ){ tRowcnt iNew; whereKeyStats(pParse, p, pRec, 1, a); iNew = a[0] + ((pUpper->eOperator & WO_LE) ? a[1] : 0); if( iNew<iUpper ) iUpper = iNew; nOut--; } } pBuilder->pRec = pRec; if( rc==SQLITE_OK ){ if( iUpper>iLower ){ nNew = sqlite3LogEst(iUpper - iLower); }else{ nNew = 10; assert( 10==sqlite3LogEst(2) ); } if( nNew<nOut ){ nOut = nNew; } pLoop->nOut = (LogEst)nOut; WHERETRACE(0x10, ("range scan regions: %u..%u est=%d\n", (u32)iLower, (u32)iUpper, nOut)); return SQLITE_OK; } }else{ int bDone = 0; rc = whereRangeSkipScanEst(pParse, pLower, pUpper, pLoop, &bDone); if( bDone ) return rc; } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(pBuilder); #endif assert( pLower || pUpper ); |
︙ | ︙ |
Changes to test/mallocK.test.
︙ | ︙ | |||
12 13 14 15 16 17 18 19 20 21 22 23 24 25 | # This test script checks malloc failures in WHERE clause analysis. # # $Id: mallocK.test,v 1.3 2009/01/08 21:00:03 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl source $testdir/malloc_common.tcl set sql {SELECT * FROM t1, t2 WHERE (a=1 OR a=2)} for {set x 1} {$x<5} {incr x} { append sql " AND b=y" do_malloc_test mallocK-1.$x -sqlbody $sql -sqlprep { CREATE TABLE t1(a,b); CREATE TABLE t2(x,y); | > | 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | # This test script checks malloc failures in WHERE clause analysis. # # $Id: mallocK.test,v 1.3 2009/01/08 21:00:03 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl source $testdir/malloc_common.tcl set testprefix mallocK set sql {SELECT * FROM t1, t2 WHERE (a=1 OR a=2)} for {set x 1} {$x<5} {incr x} { append sql " AND b=y" do_malloc_test mallocK-1.$x -sqlbody $sql -sqlprep { CREATE TABLE t1(a,b); CREATE TABLE t2(x,y); |
︙ | ︙ | |||
64 65 66 67 68 69 70 | CREATE TABLE t1(a,b); CREATE VIRTUAL TABLE t2 USING echo(t1); } } } } | > > > | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | CREATE TABLE t1(a,b); CREATE VIRTUAL TABLE t2 USING echo(t1); } } } } #------------------------------------------------------------------------- # Test that OOM errors are correctly handled by the code that uses stat4 # data to estimate the number of rows visited by a skip-scan range query. # add_alignment_test_collations db do_execsql_test 6.0 { CREATE TABLE t3(a TEXT, b TEXT COLLATE utf16_aligned, c); INSERT INTO t3 VALUES('one', '.....', 0); INSERT INTO t3 VALUES('one', '....x', 1); INSERT INTO t3 VALUES('one', '...x.', 2); INSERT INTO t3 VALUES('one', '...xx', 3); INSERT INTO t3 VALUES('one', '..x..', 4); INSERT INTO t3 VALUES('one', '..x.x', 5); INSERT INTO t3 VALUES('one', '..xx.', 6); INSERT INTO t3 VALUES('one', '..xxx', 7); INSERT INTO t3 VALUES('one', '.x...', 8); INSERT INTO t3 VALUES('one', '.x..x', 9); INSERT INTO t3 VALUES('one', '.x.x.', 10); INSERT INTO t3 VALUES('one', '.x.xx', 11); INSERT INTO t3 VALUES('one', '.xx..', 12); INSERT INTO t3 VALUES('one', '.xx.x', 13); INSERT INTO t3 VALUES('one', '.xxx.', 14); INSERT INTO t3 VALUES('one', '.xxxx', 15); INSERT INTO t3 VALUES('two', 'x....', 16); INSERT INTO t3 VALUES('two', 'x...x', 17); INSERT INTO t3 VALUES('two', 'x..x.', 18); INSERT INTO t3 VALUES('two', 'x..xx', 19); INSERT INTO t3 VALUES('two', 'x.x..', 20); INSERT INTO t3 VALUES('two', 'x.x.x', 21); INSERT INTO t3 VALUES('two', 'x.xx.', 22); INSERT INTO t3 VALUES('two', 'x.xxx', 23); INSERT INTO t3 VALUES('two', 'xx...', 24); INSERT INTO t3 VALUES('two', 'xx..x', 25); INSERT INTO t3 VALUES('two', 'xx.x.', 26); INSERT INTO t3 VALUES('two', 'xx.xx', 27); INSERT INTO t3 VALUES('two', 'xxx..', 28); INSERT INTO t3 VALUES('two', 'xxx.x', 29); INSERT INTO t3 VALUES('two', 'xxxx.', 30); INSERT INTO t3 VALUES('two', 'xxxxx', 31); INSERT INTO t3 SELECT * FROM t3; CREATE INDEX i3 ON t3(a, b); ANALYZE; SELECT 'x' > '.'; } {1} ifcapable stat4 { do_eqp_test 6.1 { SELECT DISTINCT c FROM t3 WHERE b BETWEEN '.xx..' AND '.xxxx'; } { 0 0 0 {SEARCH TABLE t3 USING INDEX i3 (ANY(a) AND b>? AND b<?)} 0 0 0 {USE TEMP B-TREE FOR DISTINCT} } } do_faultsim_test 6 -faults oom* -body { db cache flush db eval { SELECT DISTINCT c FROM t3 WHERE b BETWEEN '.xx..' AND '.xxxx' } } -test { faultsim_test_result {0 {12 13 14 15}} } finish_test |
Added test/skipscan5.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 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 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 | # 2013-11-13 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # This file implements tests of the "skip-scan" query strategy. In # particular it tests that stat4 data can be used by a range query # that uses the skip-scan approach. # set testdir [file dirname $argv0] source $testdir/tester.tcl set testprefix skipscan5 ifcapable !stat4 { finish_test return } do_execsql_test 1.1 { CREATE TABLE t1(a INT, b INT, c INT); CREATE INDEX i1 ON t1(a, b); } {} expr srand(4) do_test 1.2 { for {set i 0} {$i < 100} {incr i} { set a [expr int(rand()*4.0) + 1] set b [expr int(rand()*20.0) + 1] execsql { INSERT INTO t1 VALUES($a, $b, NULL) } } execsql ANALYZE } {} foreach {tn q res} { 1 "b = 5" {/*ANY(a) AND b=?*/} 2 "b > 12 AND b < 16" {/*ANY(a) AND b>? AND b<?*/} 3 "b > 2 AND b < 16" {/*SCAN TABLE t1*/} 4 "b > 18 AND b < 25" {/*ANY(a) AND b>? AND b<?*/} 5 "b > 15" {/*ANY(a) AND b>?*/} 6 "b > 5" {/*SCAN TABLE t1*/} 7 "b < 15" {/*SCAN TABLE t1*/} 8 "b < 5" {/*ANY(a) AND b<?*/} 9 "5 > b" {/*ANY(a) AND b<?*/} 10 "b = '5'" {/*ANY(a) AND b=?*/} 11 "b > '12' AND b < '16'" {/*ANY(a) AND b>? AND b<?*/} 12 "b > '2' AND b < '16'" {/*SCAN TABLE t1*/} 13 "b > '18' AND b < '25'" {/*ANY(a) AND b>? AND b<?*/} 14 "b > '15'" {/*ANY(a) AND b>?*/} 15 "b > '5'" {/*SCAN TABLE t1*/} 16 "b < '15'" {/*SCAN TABLE t1*/} 17 "b < '5'" {/*ANY(a) AND b<?*/} 18 "'5' > b" {/*ANY(a) AND b<?*/} } { set sql "EXPLAIN QUERY PLAN SELECT * FROM t1 WHERE $q" do_execsql_test 1.3.$tn $sql $res } #------------------------------------------------------------------------- # Test that range-query/skip-scan estimation works with text values. # And on UTF-16 databases when there is no UTF-16 collation sequence # available. # proc test_collate {enc lhs rhs} { string compare $lhs $rhs } foreach {tn dbenc coll} { 1 UTF-8 { add_test_collate db 0 0 1 } 2 UTF-16 { add_test_collate db 1 0 0 } 3 UTF-8 { add_test_collate db 0 1 0 } } { reset_db eval $coll do_execsql_test 2.$tn.1 " PRAGMA encoding = '$dbenc' " do_execsql_test 2.$tn.2 { CREATE TABLE t2(a TEXT, b TEXT, c TEXT COLLATE test_collate, d TEXT); CREATE INDEX i2 ON t2(a, b, c); } set vocab(d) { :) } set vocab(c) { a b c d e f g h i j k l m n o p q r s t } set vocab(b) { one two three } set vocab(a) { sql } do_test 2.$tn.3 { for {set i 0} {$i < 100} {incr i} { foreach var {a b c d} { set $var [lindex $vocab($var) [expr $i % [llength $vocab($var)]]] } execsql { INSERT INTO t2 VALUES($a, $b, $c, $d) } } execsql ANALYZE } {} foreach {tn2 q res} { 1 { c BETWEEN 'd' AND 'e' } {/*ANY(a) AND ANY(b) AND c>? AND c<?*/} 2 { c BETWEEN 'b' AND 'r' } {/*SCAN TABLE t2*/} 3 { c > 'q' } {/*ANY(a) AND ANY(b) AND c>?*/} 4 { c > 'e' } {/*SCAN TABLE t2*/} 5 { c < 'q' } {/*SCAN TABLE t2*/} 4 { c < 'e' } {/*ANY(a) AND ANY(b) AND c<?*/} } { set sql "EXPLAIN QUERY PLAN SELECT * FROM t2 WHERE $q" do_execsql_test 2.$tn.$tn2 $sql $res } } #------------------------------------------------------------------------- # Test that range-query/skip-scan estimation works on columns that contain # a variety of types. # reset_db do_execsql_test 3.1 { CREATE TABLE t3(a, b, c); CREATE INDEX i3 ON t3(a, b); } set values { NULL NULL NULL NULL -9567 -9240 -8725 -8659 -8248.340244520614 -8208 -7939 -7746.985758536954 -7057 -6550 -5916 -5363 -4935.781822975623 -4935.063633571875 -3518.4554911770183 -2537 -2026 -1511.2603881914456 -1510.4195994839156 -1435 -1127.4210136045804 -1045 99 1353 1457 1563.2908193223611 2245 2286 2552 2745.18831295203 2866.279926554429 3075.0468527316334 3447 3867 4237.892420141907 4335 5052.9775000424015 5232.178240656935 5541.784919585003 5749.725576373621 5758 6005 6431 7263.477992854769 7441 7541 8667.279760663994 8857 9199.638673662972 'dl' 'dro' 'h' 'igprfq' 'jnbd' 'k' 'kordee' 'lhwcv' 'mzlb' 'nbjked' 'nufpo' 'nxqkdq' 'shelln' 'tvzn' 'wpnt' 'wylf' 'ydkgu' 'zdb' X'' X'0a' X'203f6429f1f33f' X'23858e324545e0362b' X'3f9f8a' X'516f7ddd4b' X'68f1df0930ac6b' X'9ea60d' X'a06f' X'aefd342a39ce36df' X'afaa020fe2' X'be201c' X'c47d97b209601e45' } do_test 3.2 { set c 0 foreach v $values { execsql "INSERT INTO t3 VALUES($c % 2, $v, $c)" incr c } execsql ANALYZE } {} foreach {tn q res} { 1 "b BETWEEN -10000 AND -8000" {/*ANY(a) AND b>? AND b<?*/} 2 "b BETWEEN -10000 AND 'qqq'" {/*SCAN TABLE t3*/} 3 "b < X'5555'" {/*SCAN TABLE t3*/} 4 "b > X'5555'" {/*ANY(a) AND b>?*/} 5 "b > 'zzz'" {/*ANY(a) AND b>?*/} 6 "b < 'zzz'" {/*SCAN TABLE t3*/} } { set sql "EXPLAIN QUERY PLAN SELECT * FROM t3 WHERE $q" do_execsql_test 3.3.$tn $sql $res } finish_test |