diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/build.c | 9 | ||||
| -rw-r--r-- | src/resolve.c | 1 | ||||
| -rw-r--r-- | src/select.c | 164 | ||||
| -rw-r--r-- | src/sqliteInt.h | 3 |
4 files changed, 174 insertions, 3 deletions
diff --git a/src/build.c b/src/build.c index 9747810e8..e6de79e77 100644 --- a/src/build.c +++ b/src/build.c @@ -5049,14 +5049,17 @@ 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 ); 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->nSrc==1 && (p2->a[0].fg.jointype&JT_LTORJ)==0) ); + assert( p1->nSrc>=2 ); sqlite3DbFree(pParse->db, p2); p1->a[0].fg.jointype |= (JT_LTORJ & p1->a[1].fg.jointype); } diff --git a/src/resolve.c b/src/resolve.c index d5c1515a7..9cb366262 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -1367,6 +1367,7 @@ static int resolveExprStep(Walker *pWalker, Expr *pExpr){ if( nRef!=pNC->nRef ){ ExprSetProperty(pExpr, EP_VarSelect); pExpr->x.pSelect->selFlags |= SF_Correlated; + if( pExpr->op==TK_EXISTS ) pParse->bHasExists = 1; } pNC->ncFlags |= NC_Subquery; } diff --git a/src/select.c b/src/select.c index 4b0b55429..6a4d0397f 100644 --- a/src/select.c +++ b/src/select.c @@ -7296,6 +7296,163 @@ static int fromClauseTermCanBeCoroutine( } /* +** sqlite3WalkExpr() callback used by exprReferencesTable(). +*/ +static int exprReferencesTableExprCb(Walker *pWalker, Expr *pExpr){ + if( pExpr->op==TK_COLUMN && pExpr->iTable==pWalker->u.iCur ){ + pWalker->eCode = 1; + } + return WRC_Continue; +} + +/* +** Return true if the expression passed as the first argument refers +** to cursor number iCur. Otherwise return false. +*/ +static int exprReferencesTable(Expr *pExpr, int iCur){ + Walker w; + memset(&w, 0, sizeof(w)); + w.u.iCur = iCur; + w.xExprCallback = exprReferencesTableExprCb; + w.xSelectCallback = sqlite3SelectWalkNoop; + sqlite3WalkExpr(&w, pExpr); + return w.eCode; +} + +/* +** Index pIdx is a UNIQUE index on the table accessed by cursor number +** iCsr. This function returns a mask of the index columns that are +** constrained to match a single, non-NULL value by the WHERE clause +** passed as the 4th argument. For example, if the index is: +** +** CREATE UNIQUE INDEX idx ON tbl(a, b, c); +** +** and pWhere: +** +** WHERE a=? AND c=? +** +** then this function returns 5. +*/ +static u64 findConstIdxTerms( + Parse *pParse, + int iCsr, + Index *pIdx, + Expr *pWhere +){ + u64 m = 0; + if( pWhere->op==TK_AND ){ + m = findConstIdxTerms(pParse, iCsr, pIdx, pWhere->pLeft); + m |= findConstIdxTerms(pParse, iCsr, pIdx, pWhere->pRight); + }else if( pWhere->op==TK_EQ ){ + Expr *pLeft = sqlite3ExprSkipCollateAndLikely(pWhere->pLeft); + Expr *pRight = sqlite3ExprSkipCollateAndLikely(pWhere->pRight); + if( pRight->op==TK_COLUMN && pRight->iTable==iCsr ){ + SWAP(Expr*, pLeft, pRight); + } + if( pLeft->op==TK_COLUMN + && pLeft->iTable==iCsr + && exprReferencesTable(pRight, iCsr)==0 + ){ + if( pIdx ){ + int ii; + for(ii=0; ii<pIdx->nKeyCol; ii++){ + assert( pIdx->azColl[ii] ); + if( pLeft->iColumn==pIdx->aiColumn[ii] ){ + CollSeq *pColl = sqlite3ExprCompareCollSeq(pParse, pWhere); + if( pColl && sqlite3StrICmp(pColl->zName, pIdx->azColl[ii])==0 ){ + m |= ((u64)1 << ii); + break; + } + } + } + }else{ + if( pLeft->iColumn<0 ) m = 1; + } + } + } + return m; +} + +/* +** 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'; +*/ +static void existsToJoin(Parse *pParse, Select *p, Expr *pWhere){ + if( pWhere + && !ExprHasProperty(pWhere, EP_OuterON|EP_InnerON) + && p->pSrc->nSrc>0 + && p->pSrc->nSrc<BMS + && pParse->db->mallocFailed==0 + ){ + 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; + if( pSub->pSrc->nSrc==1 + && (pSub->selFlags & (SF_Aggregate|SF_Correlated))==SF_Correlated + && pSub->pWhere + ){ + int bTransform = 0; /* True if EXISTS can be made into join */ + Table *pTab = pSub->pSrc->a[0].pTab; + int iCsr = pSub->pSrc->a[0].iCursor; + Index *pIdx; + if( HasRowid(pTab) && findConstIdxTerms(pParse, iCsr, 0,pSub->pWhere) ){ + bTransform = 1; + } + for(pIdx=pTab->pIndex; pIdx && bTransform==0; pIdx=pIdx->pNext){ + if( pIdx->onError && pIdx->nKeyCol<=63 ){ + u64 c = findConstIdxTerms(pParse, iCsr, pIdx, pSub->pWhere); + if( c==((u64)1 << pIdx->nKeyCol)-1 ){ + bTransform = 1; + } + } + } + if( bTransform ){ + memset(pWhere, 0, sizeof(*pWhere)); + pWhere->op = TK_INTEGER; + pWhere->u.iValue = 1; + ExprSetProperty(pWhere, EP_IntValue); + + assert( p->pWhere!=0 ); + p->pSrc = sqlite3SrcListAppendList(pParse, p->pSrc, pSub->pSrc); + p->pWhere = sqlite3PExpr(pParse, TK_AND, p->pWhere, pSub->pWhere); + + 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 + } + } + } + } +} + +/* ** Generate code for the SELECT statement given in the p argument. ** ** The results are returned according to the SelectDest structure. @@ -7624,6 +7781,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 speed time on this operation for non-join queries ** as the equivalent optimization will be handled by query planner in diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 6a92befe0..bfe0bf94b 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -1129,6 +1129,7 @@ extern u32 sqlite3TreeTrace; ** 0x00020000 Transform DISTINCT into GROUP BY ** 0x00040000 SELECT tree dump after all code has been generated ** 0x00080000 NOT NULL strength reduction +** 0x00100000 EXISTS-to-JOIN optimization */ /* @@ -1927,6 +1928,7 @@ struct sqlite3 { #define SQLITE_Coroutines 0x02000000 /* Co-routines for subqueries */ #define SQLITE_NullUnusedCols 0x04000000 /* NULL unused columns in subqueries */ #define SQLITE_OnePass 0x08000000 /* Single-pass DELETE and UPDATE */ +#define SQLITE_ExistsToJoin 0x10000000 /* The EXISTS-to-JOIN optimization */ #define SQLITE_AllOpts 0xffffffff /* All optimizations */ /* @@ -3834,6 +3836,7 @@ struct Parse { u8 prepFlags; /* SQLITE_PREPARE_* flags */ u8 withinRJSubrtn; /* Nesting level for RIGHT JOIN body subroutines */ u8 bHasWith; /* True if statement contains WITH */ + u8 bHasExists; /* Has a correlated "EXISTS (SELECT ....)" expression */ u8 mSubrtnSig; /* mini Bloom filter on available SubrtnSig.selId */ #if defined(SQLITE_DEBUG) || defined(SQLITE_COVERAGE_TEST) u8 earlyCleanup; /* OOM inside sqlite3ParserAddCleanup() */ |