diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/btree.c | 24 | ||||
| -rw-r--r-- | src/btree.h | 1 | ||||
| -rw-r--r-- | src/build.c | 14 | ||||
| -rw-r--r-- | src/resolve.c | 5 | ||||
| -rw-r--r-- | src/select.c | 100 | ||||
| -rw-r--r-- | src/shell.c.in | 1 | ||||
| -rw-r--r-- | src/sqliteInt.h | 4 | ||||
| -rw-r--r-- | src/vdbe.c | 26 | ||||
| -rw-r--r-- | src/where.c | 11 | ||||
| -rw-r--r-- | src/wherecode.c | 6 | ||||
| -rw-r--r-- | src/whereexpr.c | 2 |
11 files changed, 182 insertions, 12 deletions
diff --git a/src/btree.c b/src/btree.c index 00cdc9760..a931b0d12 100644 --- a/src/btree.c +++ b/src/btree.c @@ -5667,6 +5667,30 @@ int sqlite3BtreeFirst(BtCursor *pCur, int *pRes){ return rc; } +/* Set *pRes to 1 (true) if the BTree pointed to by cursor pCur contains zero +** rows of content. Set *pRes to 0 (false) if the table contains content. +** Return SQLITE_OK on success or some error code (ex: SQLITE_NOMEM) if +** something goes wrong. +*/ +int sqlite3BtreeIsEmpty(BtCursor *pCur, int *pRes){ + int rc; + + assert( cursorOwnsBtShared(pCur) ); + assert( sqlite3_mutex_held(pCur->pBtree->db->mutex) ); + if( pCur->eState==CURSOR_VALID ){ + *pRes = 0; + return SQLITE_OK; + } + rc = moveToRoot(pCur); + if( rc==SQLITE_EMPTY ){ + *pRes = 1; + rc = SQLITE_OK; + }else{ + *pRes = 0; + } + return rc; +} + #ifdef SQLITE_DEBUG /* The cursors is CURSOR_VALID and has BTCF_AtLast set. Verify that ** this flags are true for a consistent database. diff --git a/src/btree.h b/src/btree.h index 241261dc6..96f4c4c60 100644 --- a/src/btree.h +++ b/src/btree.h @@ -317,6 +317,7 @@ struct BtreePayload { int sqlite3BtreeInsert(BtCursor*, const BtreePayload *pPayload, int flags, int seekResult); int sqlite3BtreeFirst(BtCursor*, int *pRes); +int sqlite3BtreeIsEmpty(BtCursor *pCur, int *pRes); int sqlite3BtreeLast(BtCursor*, int *pRes); int sqlite3BtreeNext(BtCursor*, int flags); int sqlite3BtreeEof(BtCursor*); diff --git a/src/build.c b/src/build.c index 27d7b499d..5495cef18 100644 --- a/src/build.c +++ b/src/build.c @@ -5137,16 +5137,22 @@ void sqlite3SrcListIndexedBy(Parse *pParse, SrcList *p, Token *pIndexedBy){ ** are deleted by this function. */ SrcList *sqlite3SrcListAppendList(Parse *pParse, SrcList *p1, SrcList *p2){ - assert( p1 && p1->nSrc==1 ); + assert( p1 ); + assert( p2 || pParse->nErr ); + assert( p2==0 || p2->nSrc>=1 ); + testcase( p1->nSrc==0 ); if( p2 ){ - SrcList *pNew = sqlite3SrcListEnlarge(pParse, p1, p2->nSrc, 1); + int nOld = p1->nSrc; + SrcList *pNew = sqlite3SrcListEnlarge(pParse, p1, p2->nSrc, nOld); if( pNew==0 ){ sqlite3SrcListDelete(pParse->db, p2); }else{ p1 = pNew; - memcpy(&p1->a[1], p2->a, p2->nSrc*sizeof(SrcItem)); + memcpy(&p1->a[nOld], p2->a, p2->nSrc*sizeof(SrcItem)); + assert( nOld==1 || (p2->a[0].fg.jointype & JT_LTORJ)==0 ); + assert( p1->nSrc>=1 ); + p1->a[0].fg.jointype |= (JT_LTORJ & p2->a[0].fg.jointype); sqlite3DbFree(pParse->db, p2); - p1->a[0].fg.jointype |= (JT_LTORJ & p1->a[1].fg.jointype); } } return p1; diff --git a/src/resolve.c b/src/resolve.c index 3961a2009..57ccd0c07 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -1358,11 +1358,13 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ return WRC_Prune; } #ifndef SQLITE_OMIT_SUBQUERY + case TK_EXISTS: case TK_SELECT: - case TK_EXISTS: testcase( pExpr->op==TK_EXISTS ); #endif case TK_IN: { testcase( pExpr->op==TK_IN ); + testcase( pExpr->op==TK_EXISTS ); + testcase( pExpr->op==TK_SELECT ); if( ExprUseXSelect(pExpr) ){ int nRef = pNC->nRef; testcase( pNC->ncFlags & NC_IsCheck ); @@ -1370,6 +1372,7 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ testcase( pNC->ncFlags & NC_IdxExpr ); testcase( pNC->ncFlags & NC_GenCol ); assert( pExpr->x.pSelect ); + if( pExpr->op==TK_EXISTS ) pParse->bHasExists = 1; if( pNC->ncFlags & NC_SelfRef ){ notValidImpl(pParse, pNC, "subqueries", pExpr, pExpr); }else{ diff --git a/src/select.c b/src/select.c index 1e54747fc..99b05c76a 100644 --- a/src/select.c +++ b/src/select.c @@ -384,7 +384,7 @@ static int tableAndColumnIndex( int iEnd, /* Last member of pSrc->a[] to check */ const char *zCol, /* Name of the column we are looking for */ int *piTab, /* Write index of pSrc->a[] here */ - int *piCol, /* Write index of pSrc->a[*piTab].pTab->aCol[] here */ + int *piCol, /* Write index of pSrc->a[*piTab].pSTab->aCol[] here */ int bIgnoreHidden /* Ignore hidden columns */ ){ int i; /* For looping over tables in pSrc */ @@ -3036,7 +3036,9 @@ static int multiSelect( int priorOp; /* The SRT_ operation to apply to prior selects */ Expr *pLimit; /* Saved values of p->nLimit */ int addr; + int emptyBypass = 0; /* IfEmpty opcode to bypass RHS */ SelectDest uniondest; + testcase( p->op==TK_EXCEPT ); testcase( p->op==TK_UNION ); @@ -3075,6 +3077,8 @@ static int multiSelect( */ if( p->op==TK_EXCEPT ){ op = SRT_Except; + emptyBypass = sqlite3VdbeAddOp1(v, OP_IfEmpty, unionTab); + VdbeCoverage(v); }else{ assert( p->op==TK_UNION ); op = SRT_Union; @@ -3095,6 +3099,7 @@ static int multiSelect( if( p->op==TK_UNION ){ p->nSelectRow = sqlite3LogEstAdd(p->nSelectRow, pPrior->nSelectRow); } + if( emptyBypass ) sqlite3VdbeJumpHere(v, emptyBypass); sqlite3ExprDelete(db, p->pLimit); p->pLimit = pLimit; p->iLimit = 0; @@ -3128,6 +3133,7 @@ static int multiSelect( int addr; SelectDest intersectdest; int r1; + int emptyBypass; /* INTERSECT is different from the others since it requires ** two temporary tables. Hence it has its own case. Begin @@ -3151,6 +3157,7 @@ static int multiSelect( if( rc ){ goto multi_select_end; } + emptyBypass = sqlite3VdbeAddOp1(v, OP_IfEmpty, tab1); VdbeCoverage(v); /* Code the current SELECT into temporary table "tab2" */ @@ -3182,7 +3189,7 @@ static int multiSelect( iBreak = sqlite3VdbeMakeLabel(pParse); iCont = sqlite3VdbeMakeLabel(pParse); computeLimitRegisters(pParse, p, iBreak); - sqlite3VdbeAddOp2(v, OP_Rewind, tab1, iBreak); VdbeCoverage(v); + sqlite3VdbeAddOp1(v, OP_Rewind, tab1); r1 = sqlite3GetTempReg(pParse); iStart = sqlite3VdbeAddOp2(v, OP_RowData, tab1, r1); sqlite3VdbeAddOp4Int(v, OP_NotFound, tab2, iCont, r1, 0); @@ -3194,6 +3201,7 @@ static int multiSelect( sqlite3VdbeAddOp2(v, OP_Next, tab1, iStart); VdbeCoverage(v); sqlite3VdbeResolveLabel(v, iBreak); sqlite3VdbeAddOp2(v, OP_Close, tab2, 0); + sqlite3VdbeJumpHere(v, emptyBypass); sqlite3VdbeAddOp2(v, OP_Close, tab1, 0); break; } @@ -4650,7 +4658,7 @@ static int flattenSubquery( ** complete, since there may still exist Expr.pTab entries that ** refer to the subquery even after flattening. Ticket #3346. ** - ** pSubitem->pTab is always non-NULL by test restrictions and tests above. + ** pSubitem->pSTab is always non-NULL by test restrictions and tests above. */ if( ALWAYS(pSubitem->pSTab!=0) ){ Table *pTabToDel = pSubitem->pSTab; @@ -5764,7 +5772,7 @@ With *sqlite3WithPush(Parse *pParse, With *pWith, u8 bFree){ ** CTE expression, through routine checks to see if the reference is ** a recursive reference to the CTE. ** -** If pFrom matches a CTE according to either of these two above, pFrom->pTab +** If pFrom matches a CTE according to either of these two above, pFrom->pSTab ** and other fields are populated accordingly. ** ** Return 0 if no match is found. @@ -7392,6 +7400,83 @@ static int fromClauseTermCanBeCoroutine( } /* +** Argument pWhere is the WHERE clause belonging to SELECT statement p. This +** function attempts to transform expressions of the form: +** +** EXISTS (SELECT ...) +** +** into joins. For example, given +** +** CREATE TABLE sailors(sid INTEGER PRIMARY KEY, name TEXT); +** CREATE TABLE reserves(sid INT, day DATE, PRIMARY KEY(sid, day)); +** +** SELECT name FROM sailors AS S WHERE EXISTS ( +** SELECT * FROM reserves AS R WHERE S.sid = R.sid AND R.day = '2022-10-25' +** ); +** +** the SELECT statement may be transformed as follows: +** +** SELECT name FROM sailors AS S, reserves AS R +** WHERE S.sid = R.sid AND R.day = '2022-10-25'; +** +** **Approximately**. Really, we have to ensure that the FROM-clause term +** that was formerly inside the EXISTS is only executed once. This is handled +** by setting the SrcItem.fg.fromExists flag, which then causes code in +** the where.c file to exit the corresponding loop after the first successful +** match (if any). +*/ +static SQLITE_NOINLINE void existsToJoin( + Parse *pParse, /* Parsing context */ + Select *p, /* The SELECT statement being optimized */ + Expr *pWhere /* part of the WHERE clause currently being examined */ +){ + if( pParse->nErr==0 + && pWhere!=0 + && !ExprHasProperty(pWhere, EP_OuterON|EP_InnerON) + && ALWAYS(p->pSrc!=0) + && p->pSrc->nSrc<BMS + ){ + if( pWhere->op==TK_AND ){ + Expr *pRight = pWhere->pRight; + existsToJoin(pParse, p, pWhere->pLeft); + existsToJoin(pParse, p, pRight); + } + else if( pWhere->op==TK_EXISTS ){ + Select *pSub = pWhere->x.pSelect; + Expr *pSubWhere = pSub->pWhere; + if( pSub->pSrc->nSrc==1 + && (pSub->selFlags & SF_Aggregate)==0 + && !pSub->pSrc->a[0].fg.isSubquery + ){ + memset(pWhere, 0, sizeof(*pWhere)); + pWhere->op = TK_INTEGER; + pWhere->u.iValue = 1; + ExprSetProperty(pWhere, EP_IntValue); + + assert( p->pWhere!=0 ); + pSub->pSrc->a[0].fg.fromExists = 1; + pSub->pSrc->a[0].fg.jointype |= JT_CROSS; + p->pSrc = sqlite3SrcListAppendList(pParse, p->pSrc, pSub->pSrc); + if( pSubWhere ){ + p->pWhere = sqlite3PExpr(pParse, TK_AND, p->pWhere, pSubWhere); + pSub->pWhere = 0; + } + pSub->pSrc = 0; + sqlite3ParserAddCleanup(pParse, sqlite3SelectDeleteGeneric, pSub); +#if TREETRACE_ENABLED + if( sqlite3TreeTrace & 0x100000 ){ + TREETRACE(0x100000,pParse,p, + ("After EXISTS-to-JOIN optimization:\n")); + sqlite3TreeViewSelect(0, p, 0); + } +#endif + existsToJoin(pParse, p, pSubWhere); + } + } + } +} + +/* ** Generate byte-code for the SELECT statement given in the p argument. ** ** The results are returned according to the SelectDest structure. @@ -7759,6 +7844,13 @@ int sqlite3Select( } #endif + /* If there may be an "EXISTS (SELECT ...)" in the WHERE clause, attempt + ** to change it into a join. */ + if( pParse->bHasExists && OptimizationEnabled(db,SQLITE_ExistsToJoin) ){ + existsToJoin(pParse, p, p->pWhere); + pTabList = p->pSrc; + } + /* Do the WHERE-clause constant propagation optimization if this is ** a join. No need to spend time on this operation for non-join queries ** as the equivalent optimization will be handled by query planner in diff --git a/src/shell.c.in b/src/shell.c.in index 33dd30697..5cda6a1a1 100644 --- a/src/shell.c.in +++ b/src/shell.c.in @@ -11710,6 +11710,7 @@ static int do_meta_command(char *zLine, ShellState *p){ { 0x08000000, 1, "OnePass" }, { 0x10000000, 1, "OrderBySubq" }, { 0x20000000, 1, "StarQuery" }, + { 0x40000000, 1, "ExistsToJoin" }, { 0xffffffff, 0, "All" }, }; unsigned int curOpt; diff --git a/src/sqliteInt.h b/src/sqliteInt.h index a05cf75ad..7b914d958 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1154,6 +1154,7 @@ extern u32 sqlite3TreeTrace; ** 0x00040000 SELECT tree dump after all code has been generated ** 0x00080000 NOT NULL strength reduction ** 0x00100000 Pointers are all shown as zero +** 0x00200000 EXISTS-to-JOIN optimization */ /* @@ -1926,6 +1927,7 @@ struct sqlite3 { #define SQLITE_OnePass 0x08000000 /* Single-pass DELETE and UPDATE */ #define SQLITE_OrderBySubq 0x10000000 /* ORDER BY in subquery helps outer */ #define SQLITE_StarQuery 0x20000000 /* Heurists for star queries */ +#define SQLITE_ExistsToJoin 0x40000000 /* The EXISTS-to-JOIN optimization */ #define SQLITE_AllOpts 0xffffffff /* All optimizations */ /* @@ -3369,6 +3371,7 @@ struct SrcItem { unsigned rowidUsed :1; /* The ROWID of this table is referenced */ unsigned fixedSchema :1; /* Uses u4.pSchema, not u4.zDatabase */ unsigned hadSchema :1; /* Had u4.zDatabase before u4.pSchema */ + unsigned fromExists :1; /* Comes from WHERE EXISTS(...) */ } fg; int iCursor; /* The VDBE cursor number used to access this table */ Bitmask colUsed; /* Bit N set if column N used. Details above for N>62 */ @@ -3899,6 +3902,7 @@ struct Parse { u8 disableLookaside; /* Number of times lookaside has been disabled */ u8 prepFlags; /* SQLITE_PREPARE_* flags */ u8 withinRJSubrtn; /* Nesting level for RIGHT JOIN body subroutines */ + u8 bHasExists; /* Has a correlated "EXISTS (SELECT ....)" expression */ u8 mSubrtnSig; /* mini Bloom filter on available SubrtnSig.selId */ u8 eTriggerOp; /* TK_UPDATE, TK_INSERT or TK_DELETE */ u8 bReturning; /* Coding a RETURNING trigger */ diff --git a/src/vdbe.c b/src/vdbe.c index 0020b52bf..9e456a1cd 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -6398,6 +6398,32 @@ case OP_Rewind: { /* jump0, ncycle */ break; } +/* Opcode: IfEmpty P1 P2 * * * +** Synopsis: if( empty(P1) ) goto P2 +** +** Check to see if the b-tree table that cursor P1 references is empty +** and jump to P2 if it is. +*/ +case OP_IfEmpty: { /* jump */ + VdbeCursor *pC; + BtCursor *pCrsr; + int res; + + assert( pOp->p1>=0 && pOp->p1<p->nCursor ); + assert( pOp->p2>=0 && pOp->p2<p->nOp ); + + pC = p->apCsr[pOp->p1]; + assert( pC!=0 ); + assert( pC->eCurType==CURTYPE_BTREE ); + pCrsr = pC->uc.pCursor; + assert( pCrsr ); + rc = sqlite3BtreeIsEmpty(pCrsr, &res); + if( rc ) goto abort_due_to_error; + VdbeBranchTaken(res!=0,2); + if( res ) goto jump_to_p2; + break; +} + /* Opcode: Next P1 P2 P3 * P5 ** ** Advance cursor P1 so that it points to the next key/data pair in its diff --git a/src/where.c b/src/where.c index 5d80dd3d6..ab1b419a2 100644 --- a/src/where.c +++ b/src/where.c @@ -3532,6 +3532,7 @@ static int whereLoopAddBtreeIndex( && pProbe->hasStat1!=0 && OptimizationEnabled(db, SQLITE_SkipScan) && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */ + && pSrc->fg.fromExists==0 && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK ){ LogEst nIter; @@ -7148,6 +7149,13 @@ WhereInfo *sqlite3WhereBegin( sqlite3VdbeAddOp4Dup8(v, OP_ColumnsUsed, pTabItem->iCursor, 0, 0, (const u8*)&pTabItem->colUsed, P4_INT64); #endif + if( ii>=2 + && (pTabItem[0].fg.jointype & (JT_LTORJ|JT_LEFT))==0 + && pLevel->addrHalt==pWInfo->a[0].addrHalt + ){ + sqlite3VdbeAddOp2(v, OP_IfEmpty, pTabItem->iCursor, pWInfo->iBreak); + VdbeCoverage(v); + } }else{ sqlite3TableLock(pParse, iDb, pTab->tnum, 0, pTab->zName); } @@ -7404,6 +7412,9 @@ void sqlite3WhereEnd(WhereInfo *pWInfo){ sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2); } #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */ + if( pTabList->a[pLevel->iFrom].fg.fromExists ){ + sqlite3VdbeAddOp2(v, OP_Goto, 0, sqlite3VdbeCurrentAddr(v)+2); + } /* The common case: Advance to the next row */ if( pLevel->addrCont ) sqlite3VdbeResolveLabel(v, pLevel->addrCont); sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3); diff --git a/src/wherecode.c b/src/wherecode.c index 839304c11..43a669d81 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -126,7 +126,6 @@ void sqlite3WhereAddExplainText( #endif { VdbeOp *pOp = sqlite3VdbeGetOp(pParse->pVdbe, addr); - SrcItem *pItem = &pTabList->a[pLevel->iFrom]; sqlite3 *db = pParse->db; /* Database handle */ int isSearch; /* True for a SEARCH. False for SCAN. */ @@ -149,7 +148,10 @@ void sqlite3WhereAddExplainText( sqlite3StrAccumInit(&str, db, zBuf, sizeof(zBuf), SQLITE_MAX_LENGTH); str.printfFlags = SQLITE_PRINTF_INTERNAL; - sqlite3_str_appendf(&str, "%s %S", isSearch ? "SEARCH" : "SCAN", pItem); + sqlite3_str_appendf(&str, "%s %S%s", + isSearch ? "SEARCH" : "SCAN", + pItem, + pItem->fg.fromExists ? " EXISTS" : ""); if( (flags & (WHERE_IPK|WHERE_VIRTUALTABLE))==0 ){ const char *zFmt = 0; Index *pIdx; diff --git a/src/whereexpr.c b/src/whereexpr.c index e4be8d9d6..e9fa4a143 100644 --- a/src/whereexpr.c +++ b/src/whereexpr.c @@ -948,7 +948,7 @@ static int termIsEquivalence(Parse *pParse, Expr *pExpr, SrcList *pSrc){ if( ExprHasProperty(pExpr, EP_OuterON) ) return 0; /* (3) */ assert( pSrc!=0 ); if( pExpr->op==TK_IS - && pSrc->nSrc + && pSrc->nSrc>=2 && (pSrc->a[0].fg.jointype & JT_LTORJ)!=0 ){ return 0; /* (4) */ |