diff options
| -rw-r--r-- | manifest | 14 | ||||
| -rw-r--r-- | manifest.uuid | 2 | ||||
| -rw-r--r-- | src/where.c | 122 | ||||
| -rw-r--r-- | src/whereInt.h | 1 |
4 files changed, 126 insertions, 13 deletions
@@ -1,5 +1,5 @@ -C Merge\sthe\ssqlite3WhereBegin()\ssimplification\sfrom\strunk. -D 2021-12-03T19:10:17.141 +C First\sattempt\sto\suse\sBloom\sfilters\sto\soptimize\sstar-schema\squeries. +D 2021-12-04T13:43:57.343 F .fossil-settings/empty-dirs dbb81e8fc0401ac46a1491ab34a7f2c7c0452f2f06b54ebb845d024ca8283ef1 F .fossil-settings/ignore-glob 35175cdfcf539b2318cb04a9901442804be81cd677d8b889fcc9149c21f239ea F LICENSE.md df5091916dbb40e6e9686186587125e1b2ff51f022cc334e886c19a0e9982724 @@ -637,8 +637,8 @@ F src/vxworks.h d2988f4e5a61a4dfe82c6524dd3d6e4f2ce3cdb9 F src/wal.c ed0398a7adf02c31e34aada42cc86c58f413a7afe5f741a5d373ad087abde028 F src/wal.h c3aa7825bfa2fe0d85bef2db94655f99870a285778baa36307c0a16da32b226a F src/walker.c f890a3298418d7cba3b69b8803594fdc484ea241206a8dfa99db6dd36f8cbb3b -F src/where.c a0787ad0a3447685e553725dab50e52c9763b5f10e2506255713dbd736c89998 -F src/whereInt.h 83ae6f7d0fce8b5164d97698790e0005a909b3d06d73df86a4a6bb0d9411861e +F src/where.c e9cfeae040b60c21244f40fed1a3473f048ee20cb2fb987d5028350e4bead886 +F src/whereInt.h 2c9d149b1b41c59f977deb1882e95632800946fcf15c83eaffb227afece04e51 F src/wherecode.c 620e81077588a727876a86f87aab310c02fc4e4960691e48153d8a87ca1fa453 F src/whereexpr.c 19394cb463003e9cc9305730b1508b8817a22bb7247170d81234b691a7f05b89 F src/window.c 5d3b397b0c026d0ff5890244ac41359e524c01ae31e78782e1ff418c3e271a9e @@ -1933,7 +1933,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 11d97fb8be6b5155f38df130d7e828edd0f381e32f651458939b1cb9cb973fff 6225e9abcb0261fefca4a26530524ffc449f937f8ae1ece718af2c3c3d73d78d -R 91b705f2730ed0122ffcaf8efbe0af73 +P 41ba2dfdd3a18671fc78d60935a16fa50f36af3d6481eff2ca9fba88e7093997 +R a2ed82c3d908c8671ab026e425f8c4f5 U drh -Z dab48a2f628412943ed7bfde21b0a086 +Z 92e3ffa168d28fa3c757a00a1d8afcc3 diff --git a/manifest.uuid b/manifest.uuid index 6adb3fed2..383563aee 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -41ba2dfdd3a18671fc78d60935a16fa50f36af3d6481eff2ca9fba88e7093997
\ No newline at end of file +28161fba9bcde5ae4b36b22d766c881b795af111a3a323c90f6149d0fea9297d
\ No newline at end of file diff --git a/src/where.c b/src/where.c index 371bf5230..22ed0c9b5 100644 --- a/src/where.c +++ b/src/where.c @@ -750,7 +750,7 @@ static int termCanDriveIndex( ** and to set up the WhereLevel object pLevel so that the code generator ** makes use of the automatic index. */ -static void constructAutomaticIndex( +static SQLITE_NOINLINE void constructAutomaticIndex( Parse *pParse, /* The parsing context */ WhereClause *pWC, /* The WHERE clause */ SrcItem *pSrc, /* The FROM clause term to get the next index */ @@ -965,6 +965,62 @@ end_auto_index_create: } #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ +/* +** Create a Bloom filter for the WhereLevel in the parameter. +*/ +static SQLITE_NOINLINE void constructBloomFilter( + WhereInfo *pWInfo, /* The WHERE clause */ + WhereLevel *pLevel /* Make a Bloom filter for this FROM term */ +){ + int addrTop; + int addrCont; + WhereTerm *pTerm; + WhereTerm *pWCEnd; + Parse *pParse = pWInfo->pParse; + Vdbe *v = pParse->pVdbe; + WhereLoop *pLoop = pLevel->pWLoop; + int iCur; + + + assert( pLoop!=0 ); + assert( v!=0 ); + iCur = pLevel->iTabCur; + addrCont = sqlite3VdbeMakeLabel(pParse); + addrTop = sqlite3VdbeAddOp0(v, OP_Once); + pLevel->regFilter = ++pParse->nMem; + sqlite3VdbeAddOp1(v, OP_FilterInit, pLevel->regFilter); + sqlite3VdbeAddOp1(v, OP_Rewind, iCur); + pWCEnd = &pWInfo->sWC.a[pWInfo->sWC.nTerm]; + for(pTerm=pWInfo->sWC.a; pTerm<pWCEnd; pTerm++){ + Expr *pExpr = pTerm->pExpr; + if( (pTerm->wtFlags & TERM_VIRTUAL)==0 + && sqlite3ExprIsTableConstant(pExpr, iCur) + ){ + sqlite3ExprIfFalse(pParse, pTerm->pExpr, addrCont, SQLITE_JUMPIFNULL); + } + } + if( pLoop->wsFlags & WHERE_IPK ){ + int r1 = sqlite3GetTempReg(pParse); + sqlite3VdbeAddOp2(v, OP_Rowid, iCur, r1); + sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, r1, 1); + }else{ + Index *pIdx = pLoop->u.btree.pIndex; + int r1 = sqlite3GetTempRange(pParse, pIdx->nKeyCol); + int n = pIdx->nKeyCol; + int jj; + for(jj=0; jj<n; jj++){ + int iCol = pIdx->aiColumn[jj]; + sqlite3ExprCodeGetColumnOfTable(v, pIdx->pTable, iCur, iCol,r1+jj); + } + sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, r1, n); + } + sqlite3VdbeResolveLabel(v, addrCont); + sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+3); + sqlite3VdbeJumpHere(v, addrTop); + sqlite3VdbeJumpHere(v, addrTop+2); +} + + #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the @@ -4842,6 +4898,49 @@ static SQLITE_NOINLINE Bitmask whereOmitNoopJoin( } /* +** Check to see if there are any SEARCH loops that might benefit from +** using a Bloom filter. Consider a Bloom filter if: +** +** (1) The SEARCH happens more than N times where N is the number +** of rows in the table that is being considered for the Bloom +** filter. (TO DO: Make this condition more precise.) +** (2) Most searches are expected to find zero rows +** (3) The table being searched is not the right table of a LEFT JOIN +** (4) Bloom-filter processing is not disabled +** +** This block of code merely checks to see if a Bloom filter would be +** appropriate, and if so sets the WHERE_BLOOMFILTER flag on the +** WhereLoop. The implementation of the Bloom filter comes further +** down where the code for each WhereLoop is generated. +*/ +static SQLITE_NOINLINE void whereCheckIfBloomFilterIsUseful( + WhereInfo *pWInfo, + sqlite3 *db +){ + int i; + LogEst nSearch; + SrcItem *pItem; + + assert( pWInfo->nLevel>=2 ); + assert( OptimizationEnabled(db, SQLITE_BloomFilter) ); + nSearch = pWInfo->a[0].pWLoop->nOut; + for(i=1; i<pWInfo->nLevel; i++){ + WhereLoop *pLoop = pWInfo->a[i].pWLoop; + if( (pLoop->wsFlags & (WHERE_IPK|WHERE_INDEXED))!=0 + && (pLoop->wsFlags & WHERE_COLUMN_EQ)!=0 + && pLoop->nOut<0 + && nSearch > (pItem = &pWInfo->pTabList->a[pLoop->iTab])->pTab->nRowLogEst + && (pItem->fg.jointype & JT_LEFT)==0 + ){ + pLoop->wsFlags |= WHERE_BLOOMFILTER; + pLoop->wsFlags &= ~WHERE_IDX_ONLY; + WHERETRACE(0xffff, ("-> use Bloom-filter on loop %c\n", pLoop->cId)); + } + nSearch += pLoop->nOut; + } +} + +/* ** 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 @@ -5230,6 +5329,15 @@ WhereInfo *sqlite3WhereBegin( assert( nTabList>0 ); } + /* Check to see if there are any SEARCH loops that might benefit from + ** using a Bloom filter. + */ + if( pWInfo->nLevel>=2 + && OptimizationEnabled(db, SQLITE_BloomFilter) + ){ + whereCheckIfBloomFilterIsUseful(pWInfo, db); + } + #if defined(WHERETRACE_ENABLED) if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */ sqlite3DebugPrintf("---- WHERE clause at end of analysis:\n"); @@ -5418,13 +5526,17 @@ WhereInfo *sqlite3WhereBegin( if( pParse->nErr ) goto whereBeginError; pLevel = &pWInfo->a[ii]; wsFlags = pLevel->pWLoop->wsFlags; + if( (wsFlags & (WHERE_AUTO_INDEX|WHERE_BLOOMFILTER))!=0 ){ + if( (wsFlags & WHERE_AUTO_INDEX)!=0 ){ #ifndef SQLITE_OMIT_AUTOMATIC_INDEX - if( (pLevel->pWLoop->wsFlags & WHERE_AUTO_INDEX)!=0 ){ - constructAutomaticIndex(pParse, &pWInfo->sWC, - &pTabList->a[pLevel->iFrom], notReady, pLevel); + constructAutomaticIndex(pParse, &pWInfo->sWC, + &pTabList->a[pLevel->iFrom], notReady, pLevel); +#endif + }else{ + constructBloomFilter(pWInfo, pLevel); + } if( db->mallocFailed ) goto whereBeginError; } -#endif addrExplain = sqlite3WhereExplainOneScan( pParse, pTabList, pLevel, wctrlFlags ); diff --git a/src/whereInt.h b/src/whereInt.h index ff6ac4c39..fbe84787f 100644 --- a/src/whereInt.h +++ b/src/whereInt.h @@ -600,5 +600,6 @@ void sqlite3WhereTabFuncArgs(Parse*, SrcItem*, WhereClause*); #define WHERE_BIGNULL_SORT 0x00080000 /* Column nEq of index is BIGNULL */ #define WHERE_IN_SEEKSCAN 0x00100000 /* Seek-scan optimization for IN */ #define WHERE_TRANSCONS 0x00200000 /* Uses a transitive constraint */ +#define WHERE_BLOOMFILTER 0x00400000 /* Consider using a Bloom-filter */ #endif /* !defined(SQLITE_WHEREINT_H) */ |