aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/sqliteInt.h1
-rw-r--r--src/where.c131
-rw-r--r--src/whereInt.h7
-rw-r--r--src/wherecode.c77
4 files changed, 149 insertions, 67 deletions
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index e96947e81..896b2aa42 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -1762,6 +1762,7 @@ struct sqlite3 {
#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 */
/*
diff --git a/src/where.c b/src/where.c
index 2f7eb0609..1d88c3ed3 100644
--- a/src/where.c
+++ b/src/where.c
@@ -966,61 +966,92 @@ end_auto_index_create:
#endif /* SQLITE_OMIT_AUTOMATIC_INDEX */
/*
-** Create a Bloom filter for the WhereLevel in the parameter.
+** 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.
*/
-SQLITE_NOINLINE void sqlite3ConstructBloomFilter(
- const WhereInfo *pWInfo, /* The WHERE clause */
- WhereLevel *pLevel /* Make a Bloom filter for this FROM term */
+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 */
){
- int addrTop;
- int addrCont;
- const WhereTerm *pTerm;
- const WhereTerm *pWCEnd;
- Parse *pParse = pWInfo->pParse;
- Vdbe *v = pParse->pVdbe;
- const WhereLoop *pLoop = pLevel->pWLoop;
- int iCur;
-
+ 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 );
- iCur = pLevel->iTabCur;
- addrCont = sqlite3VdbeMakeLabel(pParse);
- addrTop = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
- pLevel->regFilter = ++pParse->nMem;
- sqlite3VdbeAddOp1(v, OP_FilterInit, pLevel->regFilter);
- 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);
+ assert( pLoop->wsFlags & WHERE_BLOOMFILTER );
+
+ addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v);
+ do{
+ sqlite3WhereExplainBloomFilter(pParse, pWInfo, pLevel);
+ addrCont = sqlite3VdbeMakeLabel(pParse);
+ iCur = pLevel->iTabCur;
+ pLevel->regFilter = ++pParse->nMem;
+ sqlite3VdbeAddOp1(v, OP_FilterInit, 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];
- 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+3);
- VdbeCoverage(v);
- sqlite3VdbeJumpHere(v, addrTop);
- sqlite3VdbeJumpHere(v, addrTop+2);
+ 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];
+ 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 && pLoop->wsFlags & WHERE_BLOOMFILTER ) break;
+ }
+ }while( iLevel < pWInfo->nLevel );
+ sqlite3VdbeJumpHere(v, addrOnce);
}
@@ -5535,7 +5566,7 @@ WhereInfo *sqlite3WhereBegin(
&pTabList->a[pLevel->iFrom], notReady, pLevel);
#endif
}else{
- sqlite3ConstructBloomFilter(pWInfo, pLevel);
+ constructBloomFilter(pWInfo, ii, pLevel);
}
if( db->mallocFailed ) goto whereBeginError;
}
diff --git a/src/whereInt.h b/src/whereInt.h
index 19261ca39..4da6015f1 100644
--- a/src/whereInt.h
+++ b/src/whereInt.h
@@ -484,7 +484,6 @@ struct WhereInfo {
** where.c:
*/
Bitmask sqlite3WhereGetMask(WhereMaskSet*,int);
-void sqlite3ConstructBloomFilter(const WhereInfo*, WhereLevel*);
#ifdef WHERETRACE_ENABLED
void sqlite3WhereClausePrint(WhereClause *pWC);
void sqlite3WhereTermPrint(WhereTerm *pTerm, int iTerm);
@@ -507,8 +506,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(
diff --git a/src/wherecode.c b/src/wherecode.c
index adc7d5b8e..dfe697f24 100644
--- a/src/wherecode.c
+++ b/src/wherecode.c
@@ -196,9 +196,6 @@ int sqlite3WhereExplainOneScan(
pLoop->u.vtab.idxNum, pLoop->u.vtab.idxStr);
}
#endif
- if( flags & WHERE_BLOOMFILTER ){
- sqlite3_str_appendf(&str, " WITH BLOOM FILTER");
- }
#ifdef SQLITE_EXPLAIN_ESTIMATED_ROWS
if( pLoop->nOut>=10 ){
sqlite3_str_appendf(&str, " (~%llu rows)",
@@ -214,6 +211,52 @@ 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;
+ for(i=pLoop->nSkip; i<pLoop->u.btree.nEq; i++){
+ const char *z = pItem->pTab->aCol[i].zCnName;
+ 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
@@ -1304,14 +1347,20 @@ static void whereApplyPartialIndexConstraints(
}
}
-#if 1
/*
-** An OP_Filter has just been generated, but the corresponding
-** index search has not yet been performed. This routine
-** checks to see if there are additional WHERE_BLOOMFILTER in
-** inner loops that can be evaluated right away, and if there are,
-** it evaluates those filters as well, and removes the WHERE_BLOOMFILTER
-** tag.
+** 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 */
@@ -1323,9 +1372,8 @@ static SQLITE_NOINLINE void filterPullDown(
while( ++iLevel < pWInfo->nLevel ){
WhereLevel *pLevel = &pWInfo->a[iLevel];
WhereLoop *pLoop = pLevel->pWLoop;
- if( (pLoop->wsFlags & WHERE_BLOOMFILTER)==0 ) continue;
+ if( pLevel->regFilter==0 ) continue;
if( pLoop->prereq & notReady ) continue;
- sqlite3ConstructBloomFilter(pWInfo, &pWInfo->a[iLevel]);
if( pLoop->wsFlags & WHERE_IPK ){
WhereTerm *pTerm = pLoop->aLTerm[0];
int r1, regRowid;
@@ -1351,12 +1399,9 @@ static SQLITE_NOINLINE void filterPullDown(
addrNxt, r1, nEq);
VdbeCoverage(pParse->pVdbe);
}
- pLoop->wsFlags &= ~WHERE_BLOOMFILTER;
+ pLevel->regFilter = 0;
}
}
-#else
-#define filterPullDown(A,B,C,D,E)
-#endif
/*
** Generate code for the start of the iLevel-th loop in the WHERE clause
generated by cgit v1.2.3 (git 2.25.1) at 2025-07-19 04:11:54 +0000