diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/malloc.c | 21 | ||||
| -rw-r--r-- | src/shell.c.in | 7 | ||||
| -rw-r--r-- | src/sqlite.h.in | 9 | ||||
| -rw-r--r-- | src/sqliteInt.h | 10 | ||||
| -rw-r--r-- | src/util.c | 14 | ||||
| -rw-r--r-- | src/vdbe.c | 127 | ||||
| -rw-r--r-- | src/vdbeInt.h | 4 | ||||
| -rw-r--r-- | src/vdbemem.c | 4 | ||||
| -rw-r--r-- | src/where.c | 206 | ||||
| -rw-r--r-- | src/whereInt.h | 8 | ||||
| -rw-r--r-- | src/wherecode.c | 145 |
11 files changed, 512 insertions, 43 deletions
diff --git a/src/malloc.c b/src/malloc.c index 932cecc21..9a2eaeec1 100644 --- a/src/malloc.c +++ b/src/malloc.c @@ -211,6 +211,27 @@ sqlite3_int64 sqlite3_memory_highwater(int resetFlag){ return mx; } +#if 0 +/* +** Return an estimate of the amount of unallocated memory. +** +** This the hard heap limit minus the current memory usage. It might +** not be possible to allocate this much memory all at once. This is +** only an estimate. +*/ +sqlite3_int64 sqlite3EstMemoryAvailable(void){ + sqlite3_int64 n; + sqlite3_mutex_enter(mem0.mutex); + n = mem0.alarmThreshold; + if( n<=0 ) n = mem0.hardLimit; + sqlite3_mutex_leave(mem0.mutex); + if( n<=0 ) n = LARGEST_INT64; + n -= sqlite3_memory_used(); + if( n<0 ) n = 0; + return n; +} +#endif + /* ** Trigger the alarm */ diff --git a/src/shell.c.in b/src/shell.c.in index 543141c9e..c46eaffd6 100644 --- a/src/shell.c.in +++ b/src/shell.c.in @@ -2790,6 +2790,7 @@ static int display_stats( } if( pArg->pStmt ){ + int iHit, iMiss; iCur = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_FULLSCAN_STEP, bReset); raw_printf(pArg->out, "Fullscan Steps: %d\n", iCur); @@ -2797,6 +2798,12 @@ static int display_stats( raw_printf(pArg->out, "Sort Operations: %d\n", iCur); iCur = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_AUTOINDEX,bReset); raw_printf(pArg->out, "Autoindex Inserts: %d\n", iCur); + iHit = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_FILTER_HIT, bReset); + iMiss = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_FILTER_MISS, bReset); + if( iHit || iMiss ){ + raw_printf(pArg->out, "Bloom filter bypass taken: %d/%d\n", + iHit, iHit+iMiss); + } iCur = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_VM_STEP, bReset); raw_printf(pArg->out, "Virtual Machine Steps: %d\n", iCur); iCur = sqlite3_stmt_status(pArg->pStmt, SQLITE_STMTSTATUS_REPREPARE,bReset); diff --git a/src/sqlite.h.in b/src/sqlite.h.in index 98a028b0b..4125122e1 100644 --- a/src/sqlite.h.in +++ b/src/sqlite.h.in @@ -8467,6 +8467,13 @@ int sqlite3_stmt_status(sqlite3_stmt*, int op,int resetFlg); ** The counter is incremented on the first [sqlite3_step()] call of each ** cycle. ** +** [[SQLITE_STMTSTATUS_FILTER HIT]] <dt>SQLITE_STMTSTATUS_FILTER_HIT</dt> +** <dd>^This is the number of times that a join step was bypassed because +** a Bloom filtered returned non-found. The corresponding +** SQLITE_STMTSTATUS_FILTER_MISS value is the number of times that the +** Bloom filter returned a find, and thus the join step had to be processed +** as normal. +** ** [[SQLITE_STMTSTATUS_MEMUSED]] <dt>SQLITE_STMTSTATUS_MEMUSED</dt> ** <dd>^This is the approximate number of bytes of heap memory ** used to store the prepared statement. ^This value is not actually @@ -8481,6 +8488,8 @@ int sqlite3_stmt_status(sqlite3_stmt*, int op,int resetFlg); #define SQLITE_STMTSTATUS_VM_STEP 4 #define SQLITE_STMTSTATUS_REPREPARE 5 #define SQLITE_STMTSTATUS_RUN 6 +#define SQLITE_STMTSTATUS_FILTER_MISS 7 +#define SQLITE_STMTSTATUS_FILTER_HIT 8 #define SQLITE_STMTSTATUS_MEMUSED 99 /* diff --git a/src/sqliteInt.h b/src/sqliteInt.h index c1a0d9853..90e60d30b 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1761,6 +1761,8 @@ struct sqlite3 { #define SQLITE_SeekScan 0x00020000 /* The OP_SeekScan optimization */ #define SQLITE_OmitOrderBy 0x00040000 /* Omit pointless ORDER BY */ /* TH3 expects this value ^^^^^^^^^^ to be 0x40000. Coordinate any change */ +#define SQLITE_BloomFilter 0x00080000 /* Use a Bloom filter on searches */ +#define SQLITE_BloomPulldown 0x00100000 /* Run Bloom filters early */ #define SQLITE_AllOpts 0xffffffff /* All optimizations */ /* @@ -3925,6 +3927,7 @@ struct Sqlite3Config { int iOnceResetThreshold; /* When to reset OP_Once counters */ u32 szSorterRef; /* Min size in bytes to use sorter-refs */ unsigned int iPrngSeed; /* Alternative fixed seed for the PRNG */ + int iEstCountScale; /* Multiple RowCountEst() by this amount */ /* vvvv--- must be last ---vvv */ #ifdef SQLITE_DEBUG sqlite3_int64 aTune[SQLITE_NTUNE]; /* Tuning parameters */ @@ -4291,6 +4294,9 @@ void sqlite3MemSetDefault(void); void sqlite3BenignMallocHooks(void (*)(void), void (*)(void)); #endif int sqlite3HeapNearlyFull(void); +#if 0 +sqlite3_int64 sqlite3EstMemoryAvailable(void); +#endif /* ** On systems with ample stack space and that support alloca(), make @@ -4777,11 +4783,7 @@ LogEst sqlite3LogEstAdd(LogEst,LogEst); #ifndef SQLITE_OMIT_VIRTUALTABLE LogEst sqlite3LogEstFromDouble(double); #endif -#if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \ - defined(SQLITE_ENABLE_STAT4) || \ - defined(SQLITE_EXPLAIN_ESTIMATED_ROWS) u64 sqlite3LogEstToInt(LogEst); -#endif VList *sqlite3VListAdd(sqlite3*,VList*,const char*,int,int); const char *sqlite3VListNumToName(VList*,int); int sqlite3VListNameToNum(VList*,const char*,int); diff --git a/src/util.c b/src/util.c index 8452aea66..d93c29811 100644 --- a/src/util.c +++ b/src/util.c @@ -1603,14 +1603,8 @@ LogEst sqlite3LogEstFromDouble(double x){ } #endif /* SQLITE_OMIT_VIRTUALTABLE */ -#if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \ - defined(SQLITE_ENABLE_STAT4) || \ - defined(SQLITE_EXPLAIN_ESTIMATED_ROWS) /* ** Convert a LogEst into an integer. -** -** Note that this routine is only used when one or more of various -** non-standard compile-time options is enabled. */ u64 sqlite3LogEstToInt(LogEst x){ u64 n; @@ -1618,17 +1612,9 @@ u64 sqlite3LogEstToInt(LogEst x){ x /= 10; if( n>=5 ) n -= 2; else if( n>=1 ) n -= 1; -#if defined(SQLITE_ENABLE_STMT_SCANSTATUS) || \ - defined(SQLITE_EXPLAIN_ESTIMATED_ROWS) if( x>60 ) return (u64)LARGEST_INT64; -#else - /* If only SQLITE_ENABLE_STAT4 is on, then the largest input - ** possible to this routine is 310, resulting in a maximum x of 31 */ - assert( x<=60 ); -#endif return x>=3 ? (n+8)<<(x-3) : (n+8)>>(3-x); } -#endif /* defined SCANSTAT or STAT4 or ESTIMATED_ROWS */ /* ** Add a new name/number pair to a VList. This might require that the diff --git a/src/vdbe.c b/src/vdbe.c index 7dfe37917..0abe64a71 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -672,6 +672,48 @@ static Mem *out2Prerelease(Vdbe *p, VdbeOp *pOp){ } /* +** The minimum size (in bytes) for a Bloom filter. +** +** No Bloom filter will be smaller than this many bytes. But they +** may be larger. +*/ +#ifndef SQLITE_BLOOM_MIN +# define SQLITE_BLOOM_MIN 10000 +#endif + +/* +** The maximum size (in bytes) for a Bloom filter. +*/ +#ifndef SQLITE_BLOOM_MAX +# define SQLITE_BLOOM_MAX 1000000 +#endif + +/* +** Compute a bloom filter hash using pOp->p4.i registers from aMem[] beginning +** with pOp->p3. Return the hash. +*/ +static u64 filterHash(const Mem *aMem, const Op *pOp){ + int i, mx; + u64 h = 0; + + i = pOp->p3; + assert( pOp->p4type==P4_INT32 ); + mx = i + pOp->p4.i; + for(i=pOp->p3, mx=i+pOp->p4.i; i<mx; i++){ + const Mem *p = &aMem[i]; + if( p->flags & (MEM_Int|MEM_IntReal) ){ + h += p->u.i; + }else if( p->flags & MEM_Real ){ + h += sqlite3VdbeIntValue(p); + }else if( p->flags & (MEM_Str|MEM_Blob) ){ + h += p->n; + if( p->flags & MEM_Zero ) h += p->u.nZero; + } + } + return h; +} + +/* ** Return the symbolic name for the data type of a pMem */ static const char *vdbeMemTypeName(Mem *pMem){ @@ -1325,12 +1367,18 @@ case OP_SoftNull: { ** Synopsis: r[P2]=P4 (len=P1) ** ** P4 points to a blob of data P1 bytes long. Store this -** blob in register P2. +** blob in register P2. If P4 is a NULL pointer, then construct +** a zero-filled blob that is P1 bytes long in P2. */ case OP_Blob: { /* out2 */ assert( pOp->p1 <= SQLITE_MAX_LENGTH ); pOut = out2Prerelease(p, pOp); - sqlite3VdbeMemSetStr(pOut, pOp->p4.z, pOp->p1, 0, 0); + if( pOp->p4.z==0 ){ + sqlite3VdbeMemSetZeroBlob(pOut, pOp->p1); + if( sqlite3VdbeMemExpandBlob(pOut) ) goto no_mem; + }else{ + sqlite3VdbeMemSetStr(pOut, pOp->p4.z, pOp->p1, 0, 0); + } pOut->enc = encoding; UPDATE_MAX_BLOBSIZE(pOut); break; @@ -3341,7 +3389,7 @@ case OP_MakeRecord: { break; } -/* Opcode: Count P1 P2 p3 * * +/* Opcode: Count P1 P2 P3 * * ** Synopsis: r[P2]=count() ** ** Store the number of entries (an integer value) in the table or index @@ -8127,6 +8175,79 @@ case OP_Function: { /* group */ break; } +/* Opcode: FilterAdd P1 * P3 P4 * +** Synopsis: filter(P1) += key(P3@P4) +** +** Compute a hash on the P4 registers starting with r[P3] and +** add that hash to the bloom filter contained in r[P1]. +*/ +case OP_FilterAdd: { + u64 h; + + assert( pOp->p1>0 && pOp->p1<=(p->nMem+1 - p->nCursor) ); + pIn1 = &aMem[pOp->p1]; + assert( pIn1->flags & MEM_Blob ); + assert( pIn1->n>0 ); + h = filterHash(aMem, pOp); +#ifdef SQLITE_DEBUG + if( db->flags&SQLITE_VdbeTrace ){ + int ii; + for(ii=pOp->p3; ii<pOp->p3+pOp->p4.i; ii++){ + registerTrace(ii, &aMem[ii]); + } + printf("hash: %llu modulo %d -> %u\n", h, pIn1->n, (int)(h%pIn1->n)); + } +#endif + h %= pIn1->n; + pIn1->z[h/8] |= 1<<(h&7); + break; +} + +/* Opcode: Filter P1 P2 P3 P4 * +** Synopsis: if key(P3@P4) not in filter(P1) goto P2 +** +** Compute a hash on the key contained in the P4 registers starting +** with r[P3]. Check to see if that hash is found in the +** bloom filter hosted by register P1. If it is not present then +** maybe jump to P2. Otherwise fall through. +** +** False negatives are harmless. It is always safe to fall through, +** even if the value is in the bloom filter. A false negative causes +** more CPU cycles to be used, but it should still yield the correct +** answer. However, an incorrect answer may well arise from a +** false positive - if the jump is taken when it should fall through. +*/ +case OP_Filter: { /* jump */ + u64 h; + + assert( pOp->p1>0 && pOp->p1<=(p->nMem+1 - p->nCursor) ); + pIn1 = &aMem[pOp->p1]; + if( (pIn1->flags & MEM_Blob)==0 || NEVER(pIn1->n<=0) ){ + VdbeBranchTaken(0, 2); + break; + } + h = filterHash(aMem, pOp); +#ifdef SQLITE_DEBUG + if( db->flags&SQLITE_VdbeTrace ){ + int ii; + for(ii=pOp->p3; ii<pOp->p3+pOp->p4.i; ii++){ + registerTrace(ii, &aMem[ii]); + } + printf("hash: %llu modulo %d -> %u\n", h, pIn1->n, (int)(h%pIn1->n)); + } +#endif + h %= pIn1->n; + if( (pIn1->z[h/8] & (1<<(h&7)))==0 ){ + VdbeBranchTaken(1, 2); + p->aCounter[SQLITE_STMTSTATUS_FILTER_HIT]++; + goto jump_to_p2; + }else{ + p->aCounter[SQLITE_STMTSTATUS_FILTER_MISS]++; + VdbeBranchTaken(0, 2); + } + break; +} + /* Opcode: Trace P1 P2 * P4 * ** ** Write P4 on the statement trace output if statement tracing is diff --git a/src/vdbeInt.h b/src/vdbeInt.h index 599d06416..38863f6d6 100644 --- a/src/vdbeInt.h +++ b/src/vdbeInt.h @@ -430,7 +430,7 @@ struct Vdbe { bft bIsReader:1; /* True for statements that read */ yDbMask btreeMask; /* Bitmask of db->aDb[] entries referenced */ yDbMask lockMask; /* Subset of btreeMask that requires a lock */ - u32 aCounter[7]; /* Counters used by sqlite3_stmt_status() */ + u32 aCounter[9]; /* Counters used by sqlite3_stmt_status() */ char *zSql; /* Text of the SQL statement that generated this */ #ifdef SQLITE_ENABLE_NORMALIZE char *zNormSql; /* Normalization of the associated SQL statement */ @@ -538,7 +538,7 @@ int sqlite3VdbeMemSetRowSet(Mem*); int sqlite3VdbeMemMakeWriteable(Mem*); int sqlite3VdbeMemStringify(Mem*, u8, u8); int sqlite3IntFloatCompare(i64,double); -i64 sqlite3VdbeIntValue(Mem*); +i64 sqlite3VdbeIntValue(const Mem*); int sqlite3VdbeMemIntegerify(Mem*); double sqlite3VdbeRealValue(Mem*); int sqlite3VdbeBooleanValue(Mem*, int ifNull); diff --git a/src/vdbemem.c b/src/vdbemem.c index 570a2eb38..5a9d15f46 100644 --- a/src/vdbemem.c +++ b/src/vdbemem.c @@ -596,12 +596,12 @@ static SQLITE_NOINLINE i64 doubleToInt64(double r){ ** ** If pMem represents a string value, its encoding might be changed. */ -static SQLITE_NOINLINE i64 memIntValue(Mem *pMem){ +static SQLITE_NOINLINE i64 memIntValue(const Mem *pMem){ i64 value = 0; sqlite3Atoi64(pMem->z, &value, pMem->n, pMem->enc); return value; } -i64 sqlite3VdbeIntValue(Mem *pMem){ +i64 sqlite3VdbeIntValue(const Mem *pMem){ int flags; assert( pMem!=0 ); assert( pMem->db==0 || sqlite3_mutex_held(pMem->db->mutex) ); diff --git a/src/where.c b/src/where.c index 649b78652..bf10262a7 100644 --- a/src/where.c +++ b/src/where.c @@ -717,9 +717,9 @@ static void whereTraceIndexInfoOutputs(sqlite3_index_info *p){ ** index existed. */ static int termCanDriveIndex( - WhereTerm *pTerm, /* WHERE clause term to check */ - SrcItem *pSrc, /* Table we are trying to access */ - Bitmask notReady /* Tables in outer loops of the join */ + const WhereTerm *pTerm, /* WHERE clause term to check */ + const SrcItem *pSrc, /* Table we are trying to access */ + const Bitmask notReady /* Tables in outer loops of the join */ ){ char aff; if( pTerm->leftCursor!=pSrc->iCursor ) return 0; @@ -750,11 +750,11 @@ 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 */ - Bitmask notReady, /* Mask of cursors that are not available */ + const WhereClause *pWC, /* The WHERE clause */ + const SrcItem *pSrc, /* The FROM clause term to get the next index */ + const Bitmask notReady, /* Mask of cursors that are not available */ WhereLevel *pLevel /* Write new index here */ ){ int nKeyCol; /* Number of columns in the constructed index */ @@ -909,6 +909,10 @@ static void constructAutomaticIndex( sqlite3VdbeAddOp2(v, OP_OpenAutoindex, pLevel->iIdxCur, nKeyCol+1); sqlite3VdbeSetP4KeyInfo(pParse, pIdx); VdbeComment((v, "for %s", pTable->zName)); + if( OptimizationEnabled(pParse->db, SQLITE_BloomFilter) ){ + pLevel->regFilter = ++pParse->nMem; + sqlite3VdbeAddOp2(v, OP_Blob, 10000, pLevel->regFilter); + } /* Fill the automatic index with content */ pTabItem = &pWC->pWInfo->pTabList->a[pLevel->iFrom]; @@ -931,6 +935,10 @@ static void constructAutomaticIndex( regBase = sqlite3GenerateIndexKey( pParse, pIdx, pLevel->iTabCur, regRecord, 0, 0, 0, 0 ); + if( pLevel->regFilter ){ + sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, + regBase, pLoop->u.btree.nEq); + } sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue); @@ -957,6 +965,127 @@ end_auto_index_create: } #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ +/* +** Generate bytecode that will initialize a Bloom filter that is appropriate +** for pLevel. +** +** If there are inner loops within pLevel that have the WHERE_BLOOMFILTER +** flag set, initialize a Bloomfilter for them as well. Except don't do +** this recursive initialization if the SQLITE_BloomPulldown optimization has +** been turned off. +** +** When the Bloom filter is initialized, the WHERE_BLOOMFILTER flag is cleared +** from the loop, but the regFilter value is set to a register that implements +** the Bloom filter. When regFilter is positive, the +** sqlite3WhereCodeOneLoopStart() will generate code to test the Bloom filter +** and skip the subsequence B-Tree seek if the Bloom filter indicates that +** no matching rows exist. +** +** This routine may only be called if it has previously been determined that +** the loop would benefit from a Bloom filter, and the WHERE_BLOOMFILTER bit +** is set. +*/ +static SQLITE_NOINLINE void constructBloomFilter( + WhereInfo *pWInfo, /* The WHERE clause */ + int iLevel, /* Index in pWInfo->a[] that is pLevel */ + WhereLevel *pLevel, /* Make a Bloom filter for this FROM term */ + Bitmask notReady /* Loops that are not ready */ +){ + int addrOnce; /* Address of opening OP_Once */ + int addrTop; /* Address of OP_Rewind */ + int addrCont; /* Jump here to skip a row */ + const WhereTerm *pTerm; /* For looping over WHERE clause terms */ + const WhereTerm *pWCEnd; /* Last WHERE clause term */ + Parse *pParse = pWInfo->pParse; /* Parsing context */ + Vdbe *v = pParse->pVdbe; /* VDBE under construction */ + WhereLoop *pLoop = pLevel->pWLoop; /* The loop being coded */ + int iCur; /* Cursor for table getting the filter */ + + assert( pLoop!=0 ); + assert( v!=0 ); + assert( pLoop->wsFlags & WHERE_BLOOMFILTER ); + + addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); + do{ + const SrcItem *pItem; + const Table *pTab; + int sz; + sqlite3WhereExplainBloomFilter(pParse, pWInfo, pLevel); + addrCont = sqlite3VdbeMakeLabel(pParse); + iCur = pLevel->iTabCur; + pLevel->regFilter = ++pParse->nMem; + + /* The Bloom filter is a Blob held in a register. Initialize it + ** to zero-filled blob of at least 80K bits, but maybe more if the + ** estimated size of the table is larger. We could actually + ** measure the size of the table at run-time using OP_Count with + ** P3==1 and use that value to initialize the blob. But that makes + ** testing complicated. By basing the blob size on the value in the + ** sqlite_stat1 table, testing is much easier. + */ + pItem = &pWInfo->pTabList->a[pLevel->iFrom]; + assert( pItem!=0 ); + pTab = pItem->pTab; + assert( pTab!=0 ); + if( pTab->tabFlags & TF_HasStat1 ){ + sz = sqlite3LogEstToInt(pItem->pTab->nRowLogEst); + if( sz<10000 ){ + sz = 10000; + }else if( sz>10000000 ){ + sz = 10000000; + } + }else{ + sz = 10000; + } + sqlite3VdbeAddOp2(v, OP_Blob, sz, pLevel->regFilter); + + addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, iCur); VdbeCoverage(v); + 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); + sqlite3ReleaseTempReg(pParse, r1); + }else{ + Index *pIdx = pLoop->u.btree.pIndex; + int n = pLoop->u.btree.nEq; + int r1 = sqlite3GetTempRange(pParse, n); + int jj; + for(jj=0; jj<n; jj++){ + int iCol = pIdx->aiColumn[jj]; + assert( pIdx->pTable==pItem->pTab ); + sqlite3ExprCodeGetColumnOfTable(v, pIdx->pTable, iCur, iCol,r1+jj); + } + sqlite3VdbeAddOp4Int(v, OP_FilterAdd, pLevel->regFilter, 0, r1, n); + sqlite3ReleaseTempRange(pParse, r1, n); + } + sqlite3VdbeResolveLabel(v, addrCont); + sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); + VdbeCoverage(v); + sqlite3VdbeJumpHere(v, addrTop); + pLoop->wsFlags &= ~WHERE_BLOOMFILTER; + if( OptimizationDisabled(pParse->db, SQLITE_BloomPulldown) ) break; + while( iLevel < pWInfo->nLevel ){ + iLevel++; + pLevel = &pWInfo->a[iLevel]; + pLoop = pLevel->pWLoop; + if( pLoop==0 ) continue; + if( pLoop->prereq & notReady ) continue; + if( pLoop->wsFlags & WHERE_BLOOMFILTER ) break; + } + }while( iLevel < pWInfo->nLevel ); + sqlite3VdbeJumpHere(v, addrOnce); +} + + #ifndef SQLITE_OMIT_VIRTUALTABLE /* ** Allocate and populate an sqlite3_index_info structure. It is the @@ -4835,6 +4964,48 @@ 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( + const WhereInfo *pWInfo +){ + int i; + LogEst nSearch; + SrcItem *pItem; + + assert( pWInfo->nLevel>=2 ); + assert( OptimizationEnabled(pWInfo->pParse->db, SQLITE_BloomFilter) ); + nSearch = pWInfo->a[0].pWLoop->nOut; + for(i=1; i<pWInfo->nLevel; i++){ + WhereLoop *pLoop = pWInfo->a[i].pWLoop; + if( pLoop->nOut<0 + && (pLoop->wsFlags & (WHERE_IPK|WHERE_INDEXED))!=0 + && (pLoop->wsFlags & WHERE_COLUMN_EQ)!=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 @@ -5223,6 +5394,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); + } + #if defined(WHERETRACE_ENABLED) if( sqlite3WhereTrace & 0x100 ){ /* Display all terms of the WHERE clause */ sqlite3DebugPrintf("---- WHERE clause at end of analysis:\n"); @@ -5411,13 +5591,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, ii, pLevel, notReady); + } if( db->mallocFailed ) goto whereBeginError; } -#endif addrExplain = sqlite3WhereExplainOneScan( pParse, pTabList, pLevel, wctrlFlags ); diff --git a/src/whereInt.h b/src/whereInt.h index 0df84ad6c..558a1e3eb 100644 --- a/src/whereInt.h +++ b/src/whereInt.h @@ -64,6 +64,7 @@ struct WhereLevel { u32 iLikeRepCntr; /* LIKE range processing counter register (times 2) */ int addrLikeRep; /* LIKE range processing address */ #endif + int regFilter; /* Bloom filter */ u8 iFrom; /* Which entry in the FROM clause */ u8 op, p3, p5; /* Opcode, P3 & P5 of the opcode that ends the loop */ int p1, p2; /* Operands of the opcode used to end the loop */ @@ -506,8 +507,14 @@ int sqlite3WhereExplainOneScan( WhereLevel *pLevel, /* Scan to write OP_Explain opcode for */ u16 wctrlFlags /* Flags passed to sqlite3WhereBegin() */ ); +int sqlite3WhereExplainBloomFilter( + const Parse *pParse, /* Parse context */ + const WhereInfo *pWInfo, /* WHERE clause */ + const WhereLevel *pLevel /* Bloom filter on this level */ +); #else # define sqlite3WhereExplainOneScan(u,v,w,x) 0 +# define sqlite3WhereExplainBloomFilter(u,v,w) 0 #endif /* SQLITE_OMIT_EXPLAIN */ #ifdef SQLITE_ENABLE_STMT_SCANSTATUS void sqlite3WhereAddScanStatus( @@ -600,5 +607,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) */ diff --git a/src/wherecode.c b/src/wherecode.c index a6633967a..42cfcc9ea 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -176,19 +176,27 @@ int sqlite3WhereExplainOneScan( explainIndexRange(&str, pLoop); } }else if( (flags & WHERE_IPK)!=0 && (flags & WHERE_CONSTRAINT)!=0 ){ - const char *zRangeOp; + char cRangeOp; +#if 0 /* Better output, but breaks many tests */ + const Table *pTab = pItem->pTab; + const char *zRowid = pTab->iPKey>=0 ? pTab->aCol[pTab->iPKey].zCnName: + "rowid"; +#else + const char *zRowid = "rowid"; +#endif + sqlite3_str_appendf(&str, " USING INTEGER PRIMARY KEY (%s", zRowid); if( flags&(WHERE_COLUMN_EQ|WHERE_COLUMN_IN) ){ - zRangeOp = "="; + cRangeOp = '='; }else if( (flags&WHERE_BOTH_LIMIT)==WHERE_BOTH_LIMIT ){ - zRangeOp = ">? AND rowid<"; + sqlite3_str_appendf(&str, ">? AND %s", zRowid); + cRangeOp = '<'; }else if( flags&WHERE_BTM_LIMIT ){ - zRangeOp = ">"; + cRangeOp = '>'; }else{ assert( flags&WHERE_TOP_LIMIT); - zRangeOp = "<"; + cRangeOp = '<'; } - sqlite3_str_appendf(&str, - " USING INTEGER PRIMARY KEY (rowid%s?)",zRangeOp); + sqlite3_str_appendf(&str, "%c?)", cRangeOp); } #ifndef SQLITE_OMIT_VIRTUALTABLE else if( (flags & WHERE_VIRTUALTABLE)!=0 ){ @@ -211,6 +219,61 @@ int sqlite3WhereExplainOneScan( } return ret; } + +/* +** Add a single OP_Explain opcode that describes a Bloom filter. +** +** Or if not processing EXPLAIN QUERY PLAN and not in a SQLITE_DEBUG and/or +** SQLITE_ENABLE_STMT_SCANSTATUS build, then OP_Explain opcodes are not +** required and this routine is a no-op. +** +** If an OP_Explain opcode is added to the VM, its address is returned. +** Otherwise, if no OP_Explain is coded, zero is returned. +*/ +int sqlite3WhereExplainBloomFilter( + const Parse *pParse, /* Parse context */ + const WhereInfo *pWInfo, /* WHERE clause */ + const WhereLevel *pLevel /* Bloom filter on this level */ +){ + int ret = 0; +#if !defined(SQLITE_DEBUG) && !defined(SQLITE_ENABLE_STMT_SCANSTATUS) + if( sqlite3ParseToplevel(pParse)->explain==2 ) +#endif + { + SrcItem *pItem = &pWInfo->pTabList->a[pLevel->iFrom]; + Vdbe *v = pParse->pVdbe; /* VM being constructed */ + sqlite3 *db = pParse->db; /* Database handle */ + char *zMsg; /* Text to add to EQP output */ + int i; /* Loop counter */ + WhereLoop *pLoop; /* The where loop */ + StrAccum str; /* EQP output string */ + char zBuf[100]; /* Initial space for EQP output string */ + + sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH); + str.printfFlags = SQLITE_PRINTF_INTERNAL; + sqlite3_str_appendf(&str, "BLOOM FILTER ON %S (", pItem); + pLoop = pLevel->pWLoop; + if( pLoop->wsFlags & WHERE_IPK ){ + const Table *pTab = pItem->pTab; + if( pTab->iPKey>=0 ){ + sqlite3_str_appendf(&str, "%s=?", pTab->aCol[pTab->iPKey].zCnName); + }else{ + sqlite3_str_appendf(&str, "rowid=?"); + } + }else{ + for(i=pLoop->nSkip; i<pLoop->u.btree.nEq; i++){ + const char *z = explainIndexColumnName(pLoop->u.btree.pIndex, i); + if( i>pLoop->nSkip ) sqlite3_str_append(&str, " AND ", 5); + sqlite3_str_appendf(&str, "%s=?", z); + } + } + sqlite3_str_append(&str, ")", 1); + zMsg = sqlite3StrAccumFinish(&str); + ret = sqlite3VdbeAddOp4(v, OP_Explain, sqlite3VdbeCurrentAddr(v), + pParse->addrExplain, 0, zMsg,P4_DYNAMIC); + } + return ret; +} #endif /* SQLITE_OMIT_EXPLAIN */ #ifdef SQLITE_ENABLE_STMT_SCANSTATUS @@ -1302,6 +1365,62 @@ static void whereApplyPartialIndexConstraints( } /* +** This routine is called right after An OP_Filter has been generated and +** before the corresponding index search has been performed. This routine +** checks to see if there are additional Bloom filters in inner loops that +** can be checked prior to doing the index lookup. If there are available +** inner-loop Bloom filters, then evaluate those filters now, before the +** index lookup. The idea is that a Bloom filter check is way faster than +** an index lookup, and the Bloom filter might return false, meaning that +** the index lookup can be skipped. +** +** We know that an inner loop uses a Bloom filter because it has the +** WhereLevel.regFilter set. If an inner-loop Bloom filter is checked, +** then clear the WhereLoeve.regFilter value to prevent the Bloom filter +** from being checked a second time when the inner loop is evaluated. +*/ +static SQLITE_NOINLINE void filterPullDown( + Parse *pParse, /* Parsing context */ + WhereInfo *pWInfo, /* Complete information about the WHERE clause */ + int iLevel, /* Which level of pWInfo->a[] should be coded */ + int addrNxt, /* Jump here to bypass inner loops */ + Bitmask notReady /* Loops that are not ready */ +){ + while( ++iLevel < pWInfo->nLevel ){ + WhereLevel *pLevel = &pWInfo->a[iLevel]; + WhereLoop *pLoop = pLevel->pWLoop; + if( pLevel->regFilter==0 ) continue; + if( pLoop->prereq & notReady ) continue; + if( pLoop->wsFlags & WHERE_IPK ){ + WhereTerm *pTerm = pLoop->aLTerm[0]; + int r1, regRowid; + assert( pTerm!=0 ); + assert( pTerm->pExpr!=0 ); + testcase( pTerm->wtFlags & TERM_VIRTUAL ); + r1 = sqlite3GetTempReg(pParse); + regRowid = codeEqualityTerm(pParse, pTerm, pLevel, 0, 0, r1); + if( regRowid!=r1 ) sqlite3ReleaseTempReg(pParse, r1); + sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter, + addrNxt, regRowid, 1); + VdbeCoverage(pParse->pVdbe); + }else{ + u16 nEq = pLoop->u.btree.nEq; + int r1; + char *zStartAff; + + assert( pLoop->wsFlags & WHERE_INDEXED ); + r1 = codeAllEqualityTerms(pParse,pLevel,0,0,&zStartAff); + codeApplyAffinity(pParse, r1, nEq, zStartAff); + sqlite3DbFree(pParse->db, zStartAff); + sqlite3VdbeAddOp4Int(pParse->pVdbe, OP_Filter, pLevel->regFilter, + addrNxt, r1, nEq); + VdbeCoverage(pParse->pVdbe); + } + pLevel->regFilter = 0; + } +} + +/* ** Generate code for the start of the iLevel-th loop in the WHERE clause ** implementation described by pWInfo. */ @@ -1511,6 +1630,12 @@ Bitmask sqlite3WhereCodeOneLoopStart( iRowidReg = codeEqualityTerm(pParse, pTerm, pLevel, 0, bRev, iReleaseReg); if( iRowidReg!=iReleaseReg ) sqlite3ReleaseTempReg(pParse, iReleaseReg); addrNxt = pLevel->addrNxt; + if( pLevel->regFilter ){ + sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt, + iRowidReg, 1); + VdbeCoverage(v); + filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady); + } sqlite3VdbeAddOp3(v, OP_SeekRowid, iCur, addrNxt, iRowidReg); VdbeCoverage(v); pLevel->op = OP_Noop; @@ -1836,6 +1961,12 @@ Bitmask sqlite3WhereCodeOneLoopStart( sqlite3VdbeAddOp2(v, OP_Integer, 1, regBignull); VdbeComment((v, "NULL-scan pass ctr")); } + if( pLevel->regFilter ){ + sqlite3VdbeAddOp4Int(v, OP_Filter, pLevel->regFilter, addrNxt, + regBase, nEq); + VdbeCoverage(v); + filterPullDown(pParse, pWInfo, iLevel, addrNxt, notReady); + } op = aStartOp[(start_constraints<<2) + (startEq<<1) + bRev]; assert( op!=0 ); |