From fc0cb3a0b846d285eb0e43299867d4f952a367cf Mon Sep 17 00:00:00 2001 From: drh Date: Mon, 29 Feb 2016 21:27:16 +0000 Subject: [PATCH] The ANALYZE command automatically appends "noskipscan" to sqlite_stat1 entries that have large worst-case repeat estimates but small average repeat estimates. FossilOrigin-Name: 6326ba5891fae9c6be0c0c51cebcbe44c9f3f057 --- manifest | 19 ++++++++----------- manifest.uuid | 2 +- src/analyze.c | 24 +++++++++++++++++------- src/sqliteInt.h | 9 +++++++++ src/where.c | 4 ++-- 5 files changed, 37 insertions(+), 21 deletions(-) diff --git a/manifest b/manifest index 530227dd48..32bc41890c 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Modify\sthe\sANALYZE\scommand\sto\sstore\sworst-case\sstatistics\sin\ssqlite_stat1,\nrather\sthn\saverage\scase. -D 2016-02-29T18:30:30.116 +C The\sANALYZE\scommand\sautomatically\sappends\s"noskipscan"\sto\ssqlite_stat1\sentries\nthat\shave\slarge\sworst-case\srepeat\sestimates\sbut\ssmall\saverage\srepeat\sestimates. +D 2016-02-29T21:27:16.923 F Makefile.in 4e90dc1521879022aa9479268a4cd141d1771142 F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434 F Makefile.msc 4f319afb7c049d40aff7af6e8c4e7cc2ba18e079 @@ -286,7 +286,7 @@ F sqlite.pc.in 42b7bf0d02e08b9e77734a47798d1a55a9e0716b F sqlite3.1 fc7ad8990fc8409983309bb80de8c811a7506786 F sqlite3.pc.in 48fed132e7cb71ab676105d2a4dc77127d8c1f3a F src/alter.c 44e18dfd78e8942d65d3cdaec4de972b5cd9f1f2 -F src/analyze.c 37343619c6c560722aac521d156d34ebff746526 +F src/analyze.c 95b2e37e92cbeb9093700b8248e1ec73b3da417b F src/attach.c a3724c64de1099d85e30751213d285752aed9505 F src/auth.c b56c78ebe40a2110fd361379f7e8162d23f92240 F src/backup.c f60f0aa55d25d853ffde53d0b0370a7bb7ee41ce @@ -354,7 +354,7 @@ F src/shell.c 5e0ab1e708dc294330ccd8230536e1801f60822e F src/sqlite.h.in 57d2a02b14c9ec4f7cb294153eaf62294dc5aa68 F src/sqlite3.rc 5121c9e10c3964d5755191c80dd1180c122fc3a8 F src/sqlite3ext.h dfbe62ffd95b99afe2140d8c35b180d11924072d -F src/sqliteInt.h 01b43972162c2b5ed864060a23502af3abe0e4f4 +F src/sqliteInt.h e05c48a2b90836452d47d03b2c90a7b7ec9f8ba4 F src/sqliteLimit.h 216557999cb45f2e3578ed53ebefe228d779cb46 F src/status.c 70912d7be68e9e2dbc4010c93d344af61d4c59ba F src/table.c 5226df15ab9179b9ed558d89575ea0ce37b03fc9 @@ -428,7 +428,7 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9 F src/wal.c 10deb6b43887662691e5f53d10b3c171c401169b F src/wal.h 2f7c831cf3b071fa548bf2d5cac640846a7ff19c F src/walker.c 0f142b5bd3ed2041fc52d773880748b212e63354 -F src/where.c 32051597188dc632bafb32d50a9c3a04fb97ce39 +F src/where.c 2786a5f385dedd67e9cedaa00645bf44444f3c68 F src/whereInt.h 93297d56edd137b7ea004490690fb6e2ce028a34 F src/wherecode.c 39c1ef4598bedf1d66249334c74efd23ddd182ac F src/whereexpr.c fb87944b1254234e5bba671aaf6dee476241506a @@ -1451,10 +1451,7 @@ F vsixtest/vsixtest.tcl 6a9a6ab600c25a91a7acc6293828957a386a8a93 F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0 -P c9a30e117f2c6c9ef0cc0c6ca5227d2961715b8f -R 180de557065fd2bddac753825b6be69a -T *branch * analyze-worst-case -T *sym-analyze-worst-case * -T -sym-trunk * +P 5a0143c94ec0682798f3c09fba63593e695d2e2d +R 177b6cf14f8f11e0a114dc66d2d822d0 U drh -Z 3d046dcd3035333c5259dea36a77e4b0 +Z ca3d3ef3ca17a24048e080e522e9cbee diff --git a/manifest.uuid b/manifest.uuid index 49afe15d1c..f8a9fd14ea 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -5a0143c94ec0682798f3c09fba63593e695d2e2d \ No newline at end of file +6326ba5891fae9c6be0c0c51cebcbe44c9f3f057 \ No newline at end of file diff --git a/src/analyze.c b/src/analyze.c index f4c058e232..776d9c44c5 100644 --- a/src/analyze.c +++ b/src/analyze.c @@ -420,8 +420,8 @@ static void statInit( n = sizeof(*p) + sizeof(tRowcnt)*nColUp /* Stat4Accum.anEq */ + sizeof(tRowcnt)*nColUp /* Stat4Accum.amxEq */ -#ifdef SQLITE_ENABLE_STAT3_OR_STAT4 + sizeof(tRowcnt)*nColUp /* Stat4Accum.anDLt */ +#ifdef SQLITE_ENABLE_STAT3_OR_STAT4 + sizeof(tRowcnt)*nColUp /* Stat4Accum.anLt */ + sizeof(Stat4Sample)*(nCol+mxSample) /* Stat4Accum.aBest[], a[] */ + sizeof(tRowcnt)*3*nColUp*(nCol+mxSample) @@ -440,6 +440,7 @@ static void statInit( p->nKeyCol = nKeyCol; p->current.anEq = (tRowcnt*)&p[1]; p->current.amxEq = &p->current.anEq[nColUp]; + p->current.anDLt = &p->current.amxEq[nColUp]; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 { @@ -449,7 +450,6 @@ static void statInit( p->iGet = -1; p->mxSample = mxSample; p->nPSample = (tRowcnt)(sqlite3_value_int64(argv[2])/(mxSample/3+1) + 1); - p->current.anDLt = &p->current.amxEq[nColUp]; p->current.anLt = &p->current.anDLt[nColUp]; p->iPrn = 0x689e962d*(u32)nCol ^ 0xd0944565*(u32)sqlite3_value_int(argv[2]); @@ -739,8 +739,8 @@ static void statPush( p->current.anEq[i]++; } for(i=iChng; inCol; i++){ -#ifdef SQLITE_ENABLE_STAT3_OR_STAT4 p->current.anDLt[i]++; +#ifdef SQLITE_ENABLE_STAT3_OR_STAT4 p->current.anLt[i] += p->current.anEq[i]; #endif p->current.anEq[i] = 1; @@ -845,12 +845,18 @@ static void statGet( ** * "WHERE a=? AND b=?" matches 2 rows. ** ** Use the worst-case estimate: the maximum number of repeated entries - ** in the index. + ** in the index. The worst-case estimate is best for picking indexes. + ** But for skip-scan, we want an average case estimate. The worst-case + ** estimate might be too high. To avoid undesirable skip-scans, if the + ** worst-case estimate is above the WHERE_SKIPSCAN_ONSET but the average + ** estimate is below, simply disable skipscans on this index by adding + ** the "noskipscan" modifier onto the end of the stat line. */ char *z; int i; + int noSkipScan = 0; - char *zRet = sqlite3MallocZero( (p->nKeyCol+1)*25 ); + char *zRet = sqlite3MallocZero( (p->nKeyCol+2)*25 ); if( zRet==0 ){ sqlite3_result_error_nomem(context); return; @@ -863,9 +869,13 @@ static void statGet( sqlite3_snprintf(24, z, " %llu", iVal); z += sqlite3Strlen30(z); assert( p->current.anEq[i] ); + if( i>0 && iVal>=WHERE_SKIPSCAN_ONSET+5 ){ + iVal = p->current.anDLt[i]; + iVal = (p->nRow + iVal)/(iVal + 1); + if( iValzRet ); - + if( noSkipScan ) sqlite3_snprintf(14, z, " noskipscan"); sqlite3_result_text(context, zRet, -1, sqlite3_free); } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 diff --git a/src/sqliteInt.h b/src/sqliteInt.h index d6acc3227b..9441bb5027 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -2422,6 +2422,15 @@ struct SrcList { #define JT_OUTER 0x0020 /* The "OUTER" keyword is present */ #define JT_ERROR 0x0040 /* unknown or unsupported join type */ +/* +** TUNING: The skip-scan optimization is only profitable if the average +** number of repeats of an entry in the index is greater than or equal to +** WHERE_SKIPSCAN_ONSET. If the average numbe of repeats is less +** than WHERE_SKIPSCAN_ONSET, then it is faster to do a full table +** scan. +*/ +#define WHERE_SKIPSCAN_ONSET 18 +#define WHERE_SKIPSCAN_ONSET_LOG 42 /* ** Flags appropriate for the wctrlFlags parameter of sqlite3WhereBegin() diff --git a/src/where.c b/src/where.c index 71d3cb01ef..9c9e216e74 100644 --- a/src/where.c +++ b/src/where.c @@ -2411,11 +2411,11 @@ static int whereLoopAddBtreeIndex( ** the code). And, even if it is not, it should not be too much slower. ** On the other hand, the extra seeks could end up being significantly ** more expensive. */ - assert( 42==sqlite3LogEst(18) ); + assert( WHERE_SKIPSCAN_ONSET_LOG==sqlite3LogEst(WHERE_SKIPSCAN_ONSET) ); if( saved_nEq==saved_nSkip && saved_nEq+1nKeyCol && pProbe->noSkipScan==0 - && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */ + && pProbe->aiRowLogEst[saved_nEq+1]>=WHERE_SKIPSCAN_ONSET_LOG && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK ){ LogEst nIter; -- 2.47.2