Index: src/delete.c ================================================================== --- src/delete.c +++ src/delete.c @@ -206,10 +206,322 @@ return 0; } #endif /* defined(SQLITE_ENABLE_UPDATE_DELETE_LIMIT) */ /* && !defined(SQLITE_OMIT_SUBQUERY) */ + + +/* +** sqlite3WalkExpr() callback used by deleteSetColUsed(). +*/ +static int deleteSetColUsedExpr(Walker *pWalker, Expr *pExpr){ + int iCol; + if( pExpr->op==TK_COLUMN && (iCol = pExpr->iColumn)>=0 ){ + struct SrcList_item *pItem = &pWalker->u.pSrcList->a[0]; + if( pItem->iCursor==pExpr->iTable ){ + pItem->colUsed |= ((Bitmask)1)<<(iCol>=BMS ? BMS-1 : iCol); + } + } + return WRC_Continue; +} + +/* +** No-op sqlite3WalkExpr() callback used by deleteSetColUsed(). +*/ +static void deleteSetColUsedSelect(Walker *pWalker, Select *pSelect){ + UNUSED_PARAMETER2(pWalker, pSelect); +} + +/* +** Argument pSrc is guaranteed to contain a single table. All column +** references within expression pExpr have already been successfully +** resolved to this table. This function sets the pSrc->a[0].colUsed +** field to reflect the set of table columns used by pExpr (and no +** others). +*/ +static void deleteSetColUsed(Parse *pParse, SrcList *pSrc, Expr *pExpr){ + Walker w; + assert( pSrc->nSrc==1 ); + memset(&w, 0, sizeof(w)); + w.pParse = pParse; + w.u.pSrcList = pSrc; + w.xExprCallback = deleteSetColUsedExpr; + w.xSelectCallback2 = deleteSetColUsedSelect; + pSrc->a[0].colUsed = 0; + sqlite3WalkExpr(&w, pExpr); +} + +/* +** Generate code for a DELETE statement. This function is called by +** sqlite3DeleteFrom() after all table names and column references have +** been resolved. SQLITE_OK is returned if successful, or an SQLite +** error code otherwise. +** +** DELETE FROM table_wxyz WHERE a<5 AND b NOT NULL; +** \________/ \________________/ +** pTabList pWhere +*/ +int deleteFrom( + Parse *pParse, /* The parser context */ + SrcList *pTabList, /* Table from which we should delete things */ + Expr *pWhere, /* The WHERE clause. May be null */ + int isView, /* True if attempting to delete from a view */ + Trigger *pTrigger, /* List of table triggers, if required */ + int bComplex, /* True if there are either triggers or FKs */ + int memCnt, /* Cell used for count-changes */ + int nIdx /* Number of indexes on table */ +){ + Vdbe *v = pParse->pVdbe; /* VM being coded */ + sqlite3 *db = pParse->db; /* Database handle */ + int iEphCur = 0; /* Ephemeral table holding all primary key values */ + int iRowSet = 0; /* Register for rowset of rows to delete */ + int iKey; /* Memory cell holding key of row to be deleted */ + i16 nKey; /* Number of memory cells in the row key */ + int addrBypass = 0; /* Address of jump over the delete logic */ + int addrLoop = 0; /* Top of the delete loop */ + int addrEphOpen = 0; /* Instruction to open the Ephemeral table */ + WhereInfo *pWInfo; /* Information about the WHERE clause */ + int eOnePass; /* ONEPASS_OFF or _SINGLE or _MULTI */ + int aiCurOnePass[2]; /* The write cursors opened by WHERE_ONEPASS */ + u8 *aToOpen = 0; /* Open cursor iTabCur+j if aToOpen[j] is true */ + Index *pPk = 0; /* The PRIMARY KEY index on the table */ + int iPk = 0; /* First of nPk reg holding PRIMARY KEY value */ + i16 nPk = 1; /* Number of columns in the PRIMARY KEY */ + int iTabCur; /* Cursor number for the table */ + int iDataCur = 0; /* VDBE cursor for the canonical data source */ + int iIdxCur = 0; /* Cursor number of the first index */ + Table *pTab = pTabList->a[0].pTab; + u16 wcf = WHERE_ONEPASS_DESIRED|WHERE_DUPLICATES_OK; + + iTabCur = pTabList->a[0].iCursor; + if( !HasRowid(pTab) ){ + pPk = sqlite3PrimaryKeyIndex(pTab); + assert( pPk!=0 ); + nPk = pPk->nKeyCol; + iPk = pParse->nMem+1; + pParse->nMem += nPk; + } + + if( isView ){ + iDataCur = iIdxCur = iTabCur; + } + + /* If there are triggers to fire or foreign keys to enforce, or the + ** table is a virtual table, the two pass strategy may be required. In + ** this case allocate either the rowset register (IPK tables) or an + ** ephemeral table (WITHOUT ROWID tables) in which the list of rows + ** to delete will be accumulated. + ** + ** Otherwise, if there are no triggers or foreign keys and this is not + ** a virtual table, set the WHERE_ONEPASS_MULTIROW flag on the mask of + ** flags that will be passed to sqlite3WhereBegin(). */ + if( bComplex || IsVirtual(pTab) ){ + if( HasRowid(pTab) ){ + /* For a rowid table, initialize the RowSet to an empty set */ + pPk = 0; + nPk = 1; + iRowSet = ++pParse->nMem; + sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet); + }else{ + /* For a WITHOUT ROWID table, create an ephemeral table used to + ** hold all primary keys for rows to be deleted. */ + iEphCur = pParse->nTab++; + addrEphOpen = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iEphCur, nPk); + sqlite3VdbeSetP4KeyInfo(pParse, pPk); + } + }else{ + wcf |= WHERE_ONEPASS_MULTIROW; + } + + /* Construct a query to find the rowid or primary key for every row + ** to be deleted, based on the WHERE clause. Set variable eOnePass + ** to indicate the strategy used to implement this delete: + ** + ** ONEPASS_OFF: Two-pass approach - use a FIFO for rowids/PK values. + ** ONEPASS_SINGLE: One-pass approach - at most one row deleted. + ** ONEPASS_MULTI: One-pass approach - any number of rows may be deleted. + ** ONEPASS_SPLIT_DELETE: See special case below. + */ + pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, wcf, iTabCur+1); + if( pWInfo==0 ) return SQLITE_NOMEM; + eOnePass = sqlite3WhereOkOnePass(pWInfo, aiCurOnePass); + assert( IsVirtual(pTab)==0 || eOnePass!=ONEPASS_MULTI ); + assert( IsVirtual(pTab) || bComplex || eOnePass!=ONEPASS_OFF ); + + /* If sqlite3WhereOkOnePass() returns SPLIT_DELETE, then the WHERE clause + ** consists of one or more indexable terms connected by OR operators. In + ** this case it is more efficient to run a separate delete program for + ** each OR'd term. */ + if( eOnePass==ONEPASS_SPLIT_DELETE ){ + int rc = SQLITE_OK; /* Return code */ + Expr *pExpr = 0; /* OR'd expression */ + int i; /* Counter variable */ + assert( !IsVirtual(pTab) && bComplex==0 ); + + /* This loop iterates once for each OR-connected term in the WHERE clause */ + for(i=0; rc==SQLITE_OK && (pExpr=sqlite3WhereSplitExpr(pWInfo, i)); i++){ + if( db->mallocFailed==0 ){ + deleteSetColUsed(pParse, pTabList, pExpr); + rc = deleteFrom(pParse, pTabList, pExpr, 0, 0, 0, memCnt, nIdx); + } + sqlite3ExprDelete(db, pExpr); + } + sqlite3WhereInfoFree(db, pWInfo); + return rc; + } + + /* Keep track of the number of rows to be deleted */ + if( db->flags & SQLITE_CountRows ){ + sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1); + } + + /* Extract the rowid or primary key for the current row */ + if( pPk ){ + int i; + for(i=0; iaiColumn[i]>=0 ); + sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur, + pPk->aiColumn[i], iPk+i); + } + iKey = iPk; + }else{ + iKey = pParse->nMem + 1; + iKey = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iTabCur, iKey, 0); + if( iKey>pParse->nMem ) pParse->nMem = iKey; + } + + if( eOnePass!=ONEPASS_OFF ){ + /* For a one-pass strategy, no need to store the rowid/primary-key in + ** a RowSet or temporary table. It is read directly from its register(s) + ** by the delete code below. */ + nKey = nPk; /* OP_Found will use an unpacked key */ + aToOpen = sqlite3DbMallocRaw(db, nIdx+2); + if( aToOpen==0 ){ + sqlite3WhereEnd(pWInfo); + return SQLITE_NOMEM; + } + memset(aToOpen, 1, nIdx+1); + aToOpen[nIdx+1] = 0; + if( aiCurOnePass[0]>=0 ) aToOpen[aiCurOnePass[0]-iTabCur] = 0; + if( aiCurOnePass[1]>=0 ) aToOpen[aiCurOnePass[1]-iTabCur] = 0; + if( addrEphOpen ) sqlite3VdbeChangeToNoop(v, addrEphOpen); + }else{ + if( pPk ){ + /* Add the PK key for this row to the temporary table */ + iKey = ++pParse->nMem; + nKey = 0; /* Zero tells OP_Found to use a composite key */ + sqlite3VdbeAddOp4(v, OP_MakeRecord, iPk, nPk, iKey, + sqlite3IndexAffinityStr(pParse->db, pPk), nPk); + sqlite3VdbeAddOp2(v, OP_IdxInsert, iEphCur, iKey); + }else{ + /* Add the rowid of the row to be deleted to the RowSet */ + nKey = 1; /* OP_Seek always uses a single rowid */ + sqlite3VdbeAddOp2(v, OP_RowSetAdd, iRowSet, iKey); + } + } + + /* If not using a one-pass strategy, this is the end of the first loop. + ** A second loop, to iterate through the contents of the RowSet or + ** temporary table populated above, is opened below. */ + if( eOnePass!=ONEPASS_OFF ){ + addrBypass = sqlite3VdbeMakeLabel(v); + }else{ + sqlite3WhereEnd(pWInfo); + } + + /* Unless this is a view, open cursors for the table we are + ** deleting from and all its indices. If this is a view, then the + ** only effect this statement has is to fire the INSTEAD OF + ** triggers. */ + if( !isView ){ + int iAddrOnce = 0; + u8 p5 = (eOnePass==ONEPASS_OFF ? 0 : OPFLAG_FORDELETE); + if( eOnePass==ONEPASS_MULTI ){ + iAddrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v); + } + testcase( IsVirtual(pTab) ); + sqlite3OpenTableAndIndices(pParse, pTab, OP_OpenWrite, p5, iTabCur, + aToOpen, &iDataCur, &iIdxCur); + assert( pPk || IsVirtual(pTab) || iDataCur==iTabCur ); + assert( pPk || IsVirtual(pTab) || iIdxCur==iDataCur+1 ); + if( eOnePass==ONEPASS_MULTI ) sqlite3VdbeJumpHere(v, iAddrOnce); + } + + /* If using a one-pass strategy, seek the data-cursor to the entry + ** in the main table b-tree if where.c has not already done so. + ** + ** If using the two-pass strategy, start a loop over the contents + ** of the RowSet or temporary table populated by the first loop. */ + if( eOnePass!=ONEPASS_OFF ){ + assert( nKey==nPk ); /* OP_Found will use an unpacked key */ + if( !IsVirtual(pTab) && aToOpen[iDataCur-iTabCur] ){ + assert( pPk!=0 || pTab->pSelect!=0 ); + sqlite3VdbeAddOp4Int(v, OP_NotFound, iDataCur, addrBypass, iKey, nKey); + VdbeCoverage(v); + } + }else if( pPk ){ + addrLoop = sqlite3VdbeAddOp1(v, OP_Rewind, iEphCur); VdbeCoverage(v); + sqlite3VdbeAddOp2(v, OP_RowKey, iEphCur, iKey); + assert( nKey==0 ); /* OP_Found will use a composite key */ + }else{ + addrLoop = sqlite3VdbeAddOp3(v, OP_RowSetRead, iRowSet, 0, iKey); + VdbeCoverage(v); + assert( nKey==1 ); + } + + /* Delete the row */ +#ifndef SQLITE_OMIT_VIRTUALTABLE + if( IsVirtual(pTab) ){ + const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); + sqlite3VtabMakeWritable(pParse, pTab); + sqlite3VdbeAddOp4(v, OP_VUpdate, 0, 1, iKey, pVTab, P4_VTAB); + sqlite3VdbeChangeP5(v, OE_Abort); + assert( eOnePass==ONEPASS_OFF || eOnePass==ONEPASS_SINGLE ); + sqlite3MayAbort(pParse); + if( eOnePass==ONEPASS_SINGLE && sqlite3IsToplevel(pParse) ){ + pParse->isMultiWrite = 0; + } + }else +#endif + { + int count = (pParse->nested==0); /* True to count changes */ + int iIdxNoSeek = -1; + if( bComplex==0 && aiCurOnePass[1]!=iDataCur ){ + iIdxNoSeek = aiCurOnePass[1]; + } + sqlite3GenerateRowDelete(pParse, pTab, pTrigger, iDataCur, iIdxCur, + iKey, nKey, count, OE_Default, eOnePass, iIdxNoSeek); + } + + /* For a one-pass strategy, this is the end of the single loop. For a + ** two-pass strategy, the end of the loop over the rowids/primary-keys + ** stored in the RowSet/temporary table. */ + if( eOnePass!=ONEPASS_OFF ){ + sqlite3VdbeResolveLabel(v, addrBypass); + sqlite3WhereEnd(pWInfo); + }else if( pPk ){ + sqlite3VdbeAddOp2(v, OP_Next, iEphCur, addrLoop+1); VdbeCoverage(v); + sqlite3VdbeJumpHere(v, addrLoop); + }else{ + sqlite3VdbeGoto(v, addrLoop); + sqlite3VdbeJumpHere(v, addrLoop); + } + + /* Close the cursors open on the table and its indexes. */ + if( !isView && !IsVirtual(pTab) ){ + Index *pIdx; + int i; + if( !pPk ) sqlite3VdbeAddOp1(v, OP_Close, iDataCur); + for(i=0, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){ + sqlite3VdbeAddOp1(v, OP_Close, iIdxCur + i); + } + } + + sqlite3DbFree(db, aToOpen); + return SQLITE_OK; +} + /* ** Generate code for a DELETE FROM statement. ** ** DELETE FROM table_wxyz WHERE a<5 AND b NOT NULL; ** \________/ \________________/ @@ -218,39 +530,22 @@ void sqlite3DeleteFrom( Parse *pParse, /* The parser context */ SrcList *pTabList, /* The table from which we should delete things */ Expr *pWhere /* The WHERE clause. May be null */ ){ + sqlite3 *db; Vdbe *v; /* The virtual database engine */ Table *pTab; /* The table from which records will be deleted */ const char *zDb; /* Name of database holding pTab */ - int i; /* Loop counter */ - WhereInfo *pWInfo; /* Information about the WHERE clause */ Index *pIdx; /* For looping over indices of the table */ int iTabCur; /* Cursor number for the table */ - int iDataCur = 0; /* VDBE cursor for the canonical data source */ - int iIdxCur = 0; /* Cursor number of the first index */ int nIdx; /* Number of indices */ - sqlite3 *db; /* Main database structure */ AuthContext sContext; /* Authorization context */ NameContext sNC; /* Name context to resolve expressions in */ int iDb; /* Database number */ int memCnt = -1; /* Memory cell used for change counting */ int rcauth; /* Value returned by authorization callback */ - int eOnePass; /* ONEPASS_OFF or _SINGLE or _MULTI */ - int aiCurOnePass[2]; /* The write cursors opened by WHERE_ONEPASS */ - u8 *aToOpen = 0; /* Open cursor iTabCur+j if aToOpen[j] is true */ - Index *pPk; /* The PRIMARY KEY index on the table */ - int iPk = 0; /* First of nPk registers holding PRIMARY KEY value */ - i16 nPk = 1; /* Number of columns in the PRIMARY KEY */ - int iKey; /* Memory cell holding key of row to be deleted */ - i16 nKey; /* Number of memory cells in the row key */ - int iEphCur = 0; /* Ephemeral table holding all primary key values */ - int iRowSet = 0; /* Register for rowset of rows to delete */ - int addrBypass = 0; /* Address of jump over the delete logic */ - int addrLoop = 0; /* Top of the delete loop */ - int addrEphOpen = 0; /* Instruction to open the Ephemeral table */ #ifndef SQLITE_OMIT_TRIGGER int isView; /* True if attempting to delete from a view */ Trigger *pTrigger; /* List of table triggers, if required */ int bComplex; /* True if there are either triggers or FKs */ @@ -334,11 +629,10 @@ ** an ephemeral table. */ #if !defined(SQLITE_OMIT_VIEW) && !defined(SQLITE_OMIT_TRIGGER) if( isView ){ sqlite3MaterializeView(pParse, pTab, pWhere, iTabCur); - iDataCur = iIdxCur = iTabCur; } #endif /* Resolve the column names in the WHERE clause. */ @@ -377,184 +671,16 @@ assert( pIdx->pSchema==pTab->pSchema ); sqlite3VdbeAddOp2(v, OP_Clear, pIdx->tnum, iDb); } }else #endif /* SQLITE_OMIT_TRUNCATE_OPTIMIZATION */ - { - u16 wcf = WHERE_ONEPASS_DESIRED|WHERE_DUPLICATES_OK; - wcf |= (bComplex ? 0 : WHERE_ONEPASS_MULTIROW); - if( HasRowid(pTab) ){ - /* For a rowid table, initialize the RowSet to an empty set */ - pPk = 0; - nPk = 1; - iRowSet = ++pParse->nMem; - sqlite3VdbeAddOp2(v, OP_Null, 0, iRowSet); - }else{ - /* For a WITHOUT ROWID table, create an ephemeral table used to - ** hold all primary keys for rows to be deleted. */ - pPk = sqlite3PrimaryKeyIndex(pTab); - assert( pPk!=0 ); - nPk = pPk->nKeyCol; - iPk = pParse->nMem+1; - pParse->nMem += nPk; - iEphCur = pParse->nTab++; - addrEphOpen = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, iEphCur, nPk); - sqlite3VdbeSetP4KeyInfo(pParse, pPk); - } - - /* Construct a query to find the rowid or primary key for every row - ** to be deleted, based on the WHERE clause. Set variable eOnePass - ** to indicate the strategy used to implement this delete: - ** - ** ONEPASS_OFF: Two-pass approach - use a FIFO for rowids/PK values. - ** ONEPASS_SINGLE: One-pass approach - at most one row deleted. - ** ONEPASS_MULTI: One-pass approach - any number of rows may be deleted. - */ - pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 0, wcf, iTabCur+1); - if( pWInfo==0 ) goto delete_from_cleanup; - eOnePass = sqlite3WhereOkOnePass(pWInfo, aiCurOnePass); - assert( IsVirtual(pTab)==0 || eOnePass!=ONEPASS_MULTI ); - assert( IsVirtual(pTab) || bComplex || eOnePass!=ONEPASS_OFF ); - - /* Keep track of the number of rows to be deleted */ - if( db->flags & SQLITE_CountRows ){ - sqlite3VdbeAddOp2(v, OP_AddImm, memCnt, 1); - } - - /* Extract the rowid or primary key for the current row */ - if( pPk ){ - for(i=0; iaiColumn[i]>=0 ); - sqlite3ExprCodeGetColumnOfTable(v, pTab, iTabCur, - pPk->aiColumn[i], iPk+i); - } - iKey = iPk; - }else{ - iKey = pParse->nMem + 1; - iKey = sqlite3ExprCodeGetColumn(pParse, pTab, -1, iTabCur, iKey, 0); - if( iKey>pParse->nMem ) pParse->nMem = iKey; - } - - if( eOnePass!=ONEPASS_OFF ){ - /* For ONEPASS, no need to store the rowid/primary-key. There is only - ** one, so just keep it in its register(s) and fall through to the - ** delete code. */ - nKey = nPk; /* OP_Found will use an unpacked key */ - aToOpen = sqlite3DbMallocRaw(db, nIdx+2); - if( aToOpen==0 ){ - sqlite3WhereEnd(pWInfo); - goto delete_from_cleanup; - } - memset(aToOpen, 1, nIdx+1); - aToOpen[nIdx+1] = 0; - if( aiCurOnePass[0]>=0 ) aToOpen[aiCurOnePass[0]-iTabCur] = 0; - if( aiCurOnePass[1]>=0 ) aToOpen[aiCurOnePass[1]-iTabCur] = 0; - if( addrEphOpen ) sqlite3VdbeChangeToNoop(v, addrEphOpen); - }else{ - if( pPk ){ - /* Add the PK key for this row to the temporary table */ - iKey = ++pParse->nMem; - nKey = 0; /* Zero tells OP_Found to use a composite key */ - sqlite3VdbeAddOp4(v, OP_MakeRecord, iPk, nPk, iKey, - sqlite3IndexAffinityStr(pParse->db, pPk), nPk); - sqlite3VdbeAddOp2(v, OP_IdxInsert, iEphCur, iKey); - }else{ - /* Add the rowid of the row to be deleted to the RowSet */ - nKey = 1; /* OP_Seek always uses a single rowid */ - sqlite3VdbeAddOp2(v, OP_RowSetAdd, iRowSet, iKey); - } - } - - /* If this DELETE cannot use the ONEPASS strategy, this is the - ** end of the WHERE loop */ - if( eOnePass!=ONEPASS_OFF ){ - addrBypass = sqlite3VdbeMakeLabel(v); - }else{ - sqlite3WhereEnd(pWInfo); - } - - /* Unless this is a view, open cursors for the table we are - ** deleting from and all its indices. If this is a view, then the - ** only effect this statement has is to fire the INSTEAD OF - ** triggers. - */ - if( !isView ){ - int iAddrOnce = 0; - u8 p5 = (eOnePass==ONEPASS_OFF ? 0 : OPFLAG_FORDELETE); - if( eOnePass==ONEPASS_MULTI ){ - iAddrOnce = sqlite3CodeOnce(pParse); VdbeCoverage(v); - } - testcase( IsVirtual(pTab) ); - sqlite3OpenTableAndIndices(pParse, pTab, OP_OpenWrite, p5, iTabCur, - aToOpen, &iDataCur, &iIdxCur); - assert( pPk || IsVirtual(pTab) || iDataCur==iTabCur ); - assert( pPk || IsVirtual(pTab) || iIdxCur==iDataCur+1 ); - if( eOnePass==ONEPASS_MULTI ) sqlite3VdbeJumpHere(v, iAddrOnce); - } - - /* Set up a loop over the rowids/primary-keys that were found in the - ** where-clause loop above. - */ - if( eOnePass!=ONEPASS_OFF ){ - assert( nKey==nPk ); /* OP_Found will use an unpacked key */ - if( !IsVirtual(pTab) && aToOpen[iDataCur-iTabCur] ){ - assert( pPk!=0 || pTab->pSelect!=0 ); - sqlite3VdbeAddOp4Int(v, OP_NotFound, iDataCur, addrBypass, iKey, nKey); - VdbeCoverage(v); - } - }else if( pPk ){ - addrLoop = sqlite3VdbeAddOp1(v, OP_Rewind, iEphCur); VdbeCoverage(v); - sqlite3VdbeAddOp2(v, OP_RowKey, iEphCur, iKey); - assert( nKey==0 ); /* OP_Found will use a composite key */ - }else{ - addrLoop = sqlite3VdbeAddOp3(v, OP_RowSetRead, iRowSet, 0, iKey); - VdbeCoverage(v); - assert( nKey==1 ); - } - - /* Delete the row */ -#ifndef SQLITE_OMIT_VIRTUALTABLE - if( IsVirtual(pTab) ){ - const char *pVTab = (const char *)sqlite3GetVTable(db, pTab); - sqlite3VtabMakeWritable(pParse, pTab); - sqlite3VdbeAddOp4(v, OP_VUpdate, 0, 1, iKey, pVTab, P4_VTAB); - sqlite3VdbeChangeP5(v, OE_Abort); - assert( eOnePass==ONEPASS_OFF || eOnePass==ONEPASS_SINGLE ); - sqlite3MayAbort(pParse); - if( eOnePass==ONEPASS_SINGLE && sqlite3IsToplevel(pParse) ){ - pParse->isMultiWrite = 0; - } - }else -#endif - { - int count = (pParse->nested==0); /* True to count changes */ - int iIdxNoSeek = -1; - if( bComplex==0 && aiCurOnePass[1]!=iDataCur ){ - iIdxNoSeek = aiCurOnePass[1]; - } - sqlite3GenerateRowDelete(pParse, pTab, pTrigger, iDataCur, iIdxCur, - iKey, nKey, count, OE_Default, eOnePass, iIdxNoSeek); - } - - /* End of the loop over all rowids/primary-keys. */ - if( eOnePass!=ONEPASS_OFF ){ - sqlite3VdbeResolveLabel(v, addrBypass); - sqlite3WhereEnd(pWInfo); - }else if( pPk ){ - sqlite3VdbeAddOp2(v, OP_Next, iEphCur, addrLoop+1); VdbeCoverage(v); - sqlite3VdbeJumpHere(v, addrLoop); - }else{ - sqlite3VdbeGoto(v, addrLoop); - sqlite3VdbeJumpHere(v, addrLoop); - } - - /* Close the cursors open on the table and its indexes. */ - if( !isView && !IsVirtual(pTab) ){ - if( !pPk ) sqlite3VdbeAddOp1(v, OP_Close, iDataCur); - for(i=0, pIdx=pTab->pIndex; pIdx; i++, pIdx=pIdx->pNext){ - sqlite3VdbeAddOp1(v, OP_Close, iIdxCur + i); - } + + { + if( deleteFrom(pParse, pTabList, pWhere, isView, pTrigger, bComplex, + memCnt, nIdx) + ){ + goto delete_from_cleanup; } } /* End non-truncate path */ /* Update the sqlite_sequence table by storing the content of the ** maximum rowid counter values recorded while inserting into @@ -576,11 +702,10 @@ delete_from_cleanup: sqlite3AuthContextPop(&sContext); sqlite3SrcListDelete(db, pTabList); sqlite3ExprDelete(db, pWhere); - sqlite3DbFree(db, aToOpen); return; } /* Make sure "isView" and other macros defined above are undefined. Otherwise ** they may interfere with compilation of other functions in this file ** (or in another file, if this file becomes part of the amalgamation). */ Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -3437,20 +3437,23 @@ #endif void sqlite3DeleteFrom(Parse*, SrcList*, Expr*); void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int); WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int); void sqlite3WhereEnd(WhereInfo*); +void sqlite3WhereInfoFree(sqlite3*, WhereInfo*); +Expr *sqlite3WhereSplitExpr(WhereInfo*, int); u64 sqlite3WhereOutputRowCount(WhereInfo*); int sqlite3WhereIsDistinct(WhereInfo*); int sqlite3WhereIsOrdered(WhereInfo*); int sqlite3WhereIsSorted(WhereInfo*); int sqlite3WhereContinueLabel(WhereInfo*); int sqlite3WhereBreakLabel(WhereInfo*); int sqlite3WhereOkOnePass(WhereInfo*, int*); -#define ONEPASS_OFF 0 /* Use of ONEPASS not allowed */ -#define ONEPASS_SINGLE 1 /* ONEPASS valid for a single row update */ -#define ONEPASS_MULTI 2 /* ONEPASS is valid for multiple rows */ +#define ONEPASS_OFF 0 /* Use of ONEPASS not allowed */ +#define ONEPASS_SINGLE 1 /* ONEPASS valid for a single row update */ +#define ONEPASS_MULTI 2 /* ONEPASS is valid for multiple rows */ +#define ONEPASS_SPLIT_DELETE 3 /* DELETE should be split into multiple ops */ void sqlite3ExprCodeLoadIndexColumn(Parse*, Index*, int, int, int); int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8); void sqlite3ExprCodeGetColumnToReg(Parse*, Table*, int, int, int); void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int); void sqlite3ExprCodeMove(Parse*, int, int, int); Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -1772,11 +1772,11 @@ } /* ** Free a WhereInfo structure */ -static void whereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ +void sqlite3WhereInfoFree(sqlite3 *db, WhereInfo *pWInfo){ if( ALWAYS(pWInfo) ){ int i; for(i=0; inLevel; i++){ WhereLevel *pLevel = &pWInfo->a[i]; if( pLevel->pWLoop && (pLevel->pWLoop->wsFlags & WHERE_IN_ABLE) ){ @@ -1790,10 +1790,57 @@ whereLoopDelete(db, p); } sqlite3DbFree(db, pWInfo); } } + +/* +** This function may only be called if sqlite3WhereOkOnePass() on the same +** WhereInfo object has returned ONEPASS_SPLIT_DELETE, indicating that the +** WHERE clause consists of a series of sub-expressions connected by OR +** operators. This function is used to access elements of this set of +** sub-expressions. +** +** OR-connected sub-expressions are numbered contiguously starting from +** zero. The sub-expression to return is identified by the iExpr parameter +** passed to this function. If iExpr is equal to or greater than the number +** of sub-expressions, NULL is returned. Otherwise, a pointer to a copy of +** sub-expression iExpr is returned. The caller is responsible for eventually +** deleting this object using sqlite3ExprDelete(). +** +** If an OOM error occurs, the mallocFailed field of the database handle +** (pWInfo->pParse->db->mallocFailed) is set to record the error. Even +** if an OOM error occurs, this function may return a non-NULL pointer. In +** this case the caller is still responsible for deleting the returned +** object, even though it is not safe to use. +*/ +Expr *sqlite3WhereSplitExpr(WhereInfo *pWInfo, int iExpr){ + sqlite3 *db = pWInfo->pParse->db; + WhereLoop *pLoop = pWInfo->a[0].pWLoop; + WhereTerm *pTerm = pLoop->aLTerm[0]; + WhereClause *pOrWC = &pTerm->u.pOrInfo->wc; + Expr *pExpr = 0; + + assert( pWInfo->eOnePass==ONEPASS_SPLIT_DELETE ); + assert( (pTerm->wtFlags & TERM_ORINFO)!=0 ); + + if( iExprnTerm ){ + pExpr = sqlite3ExprDup(db, pOrWC->a[iExpr].pExpr, 0); + if( pExpr ){ + WhereClause *pWC = &pWInfo->sWC; + int ii; + for(ii=0; iinTerm; ii++){ + if( &pWC->a[ii]!=pTerm ){ + Expr *pLeft = sqlite3ExprDup(db, pWC->a[ii].pExpr, 0); + pExpr = sqlite3ExprAnd(db, pLeft, pExpr); + } + } + } + } + + return pExpr; +} /* ** Return TRUE if all of the following are true: ** ** (1) X has the same or lower cost that Y @@ -4253,11 +4300,10 @@ pWInfo->nLevel--; nTabList--; } } WHERETRACE(0xffff,("*** Optimizer Finished ***\n")); - pWInfo->pParse->nQueryLoop += pWInfo->nRowOut; /* If the caller is an UPDATE or DELETE statement that is requesting ** to use a one-pass algorithm, determine if this is appropriate. ** The one-pass algorithm only works if the WHERE clause constrains ** the statement to update or delete a single row. @@ -4267,19 +4313,31 @@ int wsFlags = pWInfo->a[0].pWLoop->wsFlags; int bOnerow = (wsFlags & WHERE_ONEROW)!=0; if( bOnerow || ( (wctrlFlags & WHERE_ONEPASS_MULTIROW) && 0==(wsFlags & WHERE_VIRTUALTABLE) )){ + if( (wsFlags & WHERE_MULTI_OR) && (wctrlFlags & WHERE_ONEPASS_MULTIROW) ){ + /* This call is being made as part of a DELETE program and the + ** optimizer has indicated that the OR-optimization is the best + ** approach. In this case it is better to let the caller generate + ** a separate loop for each OR'd term than to actually go ahead + ** and code the OR-optimized loop. Set the value returned by + ** sqlite3WhereOkOnePass() to ONEPASS_SPLIT_DELETE to communicate + ** this to the caller and return early. */ + pWInfo->eOnePass = ONEPASS_SPLIT_DELETE; + return pWInfo; + } pWInfo->eOnePass = bOnerow ? ONEPASS_SINGLE : ONEPASS_MULTI; if( HasRowid(pTabList->a[0].pTab) && (wsFlags & WHERE_IDX_ONLY) ){ if( wctrlFlags & WHERE_ONEPASS_MULTIROW ){ bFordelete = OPFLAG_FORDELETE; } pWInfo->a[0].pWLoop->wsFlags = (wsFlags & ~WHERE_IDX_ONLY); } } } + pWInfo->pParse->nQueryLoop += pWInfo->nRowOut; /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ for(ii=0, pLevel=pWInfo->a; iinQueryLoop = pWInfo->savedNQueryLoop; - whereInfoFree(db, pWInfo); + sqlite3WhereInfoFree(db, pWInfo); } return 0; } /* @@ -4619,8 +4677,8 @@ } /* Final cleanup */ pParse->nQueryLoop = pWInfo->savedNQueryLoop; - whereInfoFree(db, pWInfo); + sqlite3WhereInfoFree(db, pWInfo); return; } Index: test/delete4.test ================================================================== --- test/delete4.test +++ test/delete4.test @@ -137,9 +137,94 @@ CREATE INDEX idx_t4_0 ON t4 (col1, col0); DELETE FROM t4 WHERE col0=69 OR col0>7; PRAGMA integrity_check; } {ok} +#------------------------------------------------------------------------- +# Further tests for DELETE statements that use the OR optimization. +# +array unset -nocomplain res +foreach {tn tbl} { + 0 { CREATE TABLE t5(i INTEGER, a, b, c) } + 1 { + CREATE TABLE t5(i INTEGER PRIMARY KEY, a, b, c); + CREATE INDEX t5a ON t5(a); + CREATE INDEX t5bc ON t5(b, c); + CREATE INDEX t5c ON t5(c); + } + 2 { + CREATE TABLE t5(i INT PRIMARY KEY, a, b, c) WITHOUT ROWID; + CREATE INDEX t5a ON t5(a); + CREATE INDEX t5bc ON t5(b, c); + CREATE INDEX t5c ON t5(c); + } +} { + do_test 5.$tn.0 { + execsql { DROP TABLE IF EXISTS t5 } + execsql $tbl + + for {set i 1} {$i <= 100} {incr i} { + set a [expr $i*2] + set b [expr ($i*7 % 100)] + set c [expr 100-$i] + execsql { INSERT INTO t5 VALUES($i, $a, $b, $c) } + } + } {} + + foreach {tn2 sql} { + 1 { DELETE FROM t5 WHERE a=4 OR b=10 OR c=17 } + 2 { DELETE FROM t5 WHERE (a=4 OR b=22) AND c=98 } + 3 { DELETE FROM t5 WHERE (b=49 AND c=93) OR a=14 } + 4 { DELETE FROM t5 WHERE (b=70 AND c=90) OR a=150 } + 5 { DELETE FROM t5 WHERE (a BETWEEN 2 AND 20) OR (b BETWEEN 1 AND 10) } + 6 { DELETE FROM t5 WHERE a IN (2, 4, 6, 8) OR b IN (63, 70, 77) } + } { + execsql BEGIN + execsql $sql + do_execsql_test 5.$tn.$tn2.1 { PRAGMA integrity_check } ok + if {$tn==0} { + set res($tn2) [db eval { SELECT count(*), md5sum(i, a, b, c) FROM t5 }] + } + + do_execsql_test 5.$tn.$tn2.2 { + SELECT count(*), md5sum(i, a, b, c) FROM t5 + } $res($tn2) + + execsql ROLLBACK + } +} + +#------------------------------------------------------------------------- +# Test that nested OR optimizations work. +# +do_execsql_test 6.0 { + CREATE TABLE t6(a, b, c, d); + CREATE INDEX t6a ON t6(a); + CREATE INDEX t6b ON t6(b); + CREATE INDEX t6c ON t6(c); + WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<1000 ) + INSERT INTO t6 SELECT i, i*2, i*3, i%2 FROM s; +} + +proc do_61_test {tn sql lDel} { + uplevel [list do_execsql_test $tn " + BEGIN; + $sql; + WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<1000 ) + SELECT i FROM s EXCEPT SELECT a FROM t6 ORDER BY 1; + ROLLBACK; + " $lDel] +} + +do_61_test 6.1 { + DELETE FROM t6 WHERE a=22 OR b=90 OR (d=0 AND (b=400 OR c=303)); +} {22 45 200} +do_61_test 6.2 { + DELETE FROM t6 WHERE a=22 OR b=90 OR (d=1 AND (b=400 OR c=303)); +} {22 45 101} +do_61_test 6.3 { + DELETE FROM t6 WHERE (d=0 AND (a=100 OR b=150)) OR (d=1 AND (b=50 OR c=603)); +} {25 100 201} finish_test ADDED test/delete_fault.test Index: test/delete_fault.test ================================================================== --- /dev/null +++ test/delete_fault.test @@ -0,0 +1,50 @@ +# 2015 December 10 +# +# The author disclaims copyright to this source code. In place of +# a legal notice, here is a blessing: +# +# May you do good and not evil. +# May you find forgiveness for yourself and forgive others. +# May you share freely, never taking more than you give. +# +#*********************************************************************** +# This file implements regression tests for SQLite library. The focus +# of this file is fault-injection into DELETE statements. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set testprefix delete_fault + +do_execsql_test 1.0 { + CREATE TABLE t6(a, b, c, d); + CREATE INDEX t6a ON t6(a); + CREATE INDEX t6b ON t6(b); + CREATE INDEX t6c ON t6(c); + WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<1000 ) + INSERT INTO t6 SELECT i, i*2, i*3, i%2 FROM s; +} +faultsim_save_and_close + +proc deleted_t6_rows {} { + db eval { + WITH s(i) AS ( SELECT 1 UNION ALL SELECT i+1 FROM s WHERE i<1000 ) + SELECT i FROM s EXCEPT SELECT a FROM t6 ORDER BY 1; + } +} + +do_faultsim_test 1 -faults oom-t* -prep { + faultsim_restore_and_reopen +} -body { + execsql { + DELETE FROM t6 WHERE (d=0 AND (a=100 OR b=150)) OR (d=1 AND (b=50 OR c=603)) + } +} -test { + faultsim_test_result {0 {}} + if {$testrc==0} { + set lDel [deleted_t6_rows] + if {$lDel != "25 100 201"} { error "lDel is $lDel" } + } +} + +finish_test Index: test/fordelete.test ================================================================== --- test/fordelete.test +++ test/fordelete.test @@ -59,25 +59,90 @@ 4 { DELETE FROM t1 WHERE rowid=? } { sqlite_autoindex_t1_1* t1 } } { do_adp_test 1.$tn $sql $res } -do_execsql_test 2.0 { +do_execsql_test 2.1.0 { CREATE TABLE t2(a, b, c); CREATE INDEX t2a ON t2(a); CREATE INDEX t2b ON t2(b); CREATE INDEX t2c ON t2(c); } foreach {tn sql res} { 1 { DELETE FROM t2 WHERE a=?} { t2* t2a t2b* t2c* } 2 { DELETE FROM t2 WHERE a=? AND +b=?} { t2 t2a t2b* t2c* } - 3 { DELETE FROM t2 WHERE a=? OR b=?} { t2 t2a* t2b* t2c* } + 3 { DELETE FROM t2 WHERE a=? OR b=?} { t2* t2* t2a t2a* t2b t2b* t2c* t2c* } 4 { DELETE FROM t2 WHERE +a=? } { t2 t2a* t2b* t2c* } 5 { DELETE FROM t2 WHERE rowid=? } { t2 t2a* t2b* t2c* } } { - do_adp_test 2.$tn $sql $res + do_adp_test 2.1.$tn $sql $res +} + +foreach {tn where res} { + 1 { a=? OR b=? } { t2* t2* t2a t2a* t2b t2b* t2c* t2c* } + 2 { a=? OR (b=? AND +c=?) } { t2 t2* t2a t2a* t2b t2b* t2c* t2c* } + 3 { (a=? OR b=?) AND +c=? } { t2 t2 t2a t2a* t2b t2b* t2c* t2c* } + 4 { (c=? OR b=?) } { t2* t2* t2a* t2a* t2b t2b* t2c t2c* } + 5 { (c=? OR b=?) AND EXISTS (SELECT 1 FROM t1 WHERE t1.a=?) } + { t2* t2* t2a* t2a* t2b t2b* t2c t2c* } +} { + do_adp_test 2.2.$tn "DELETE FROM t2 WHERE $where" $res +} + +do_execsql_test 2.3.0 { + CREATE TABLE t3(x, y, z); + CREATE INDEX t3xy ON t3(x, y); + CREATE INDEX t3zy ON t3(z, y); + CREATE INDEX t3zx ON t3(z, x); + CREATE INDEX t3x ON t3(x); +} + +foreach {tn where res} { + 1 { x=? OR z=? } + { t3* t3* t3x t3x* t3xy* t3xy* t3zx t3zx* t3zy* t3zy* } + + 2 { (x=? OR z=?) AND y=? } + { t3* t3* t3x* t3x* t3xy t3xy* t3zx* t3zx* t3zy t3zy* } + + 3 { (y=? OR z=?) AND x=? } { t3 t3x t3xy* t3zx* t3zy* } +} { + do_adp_test 2.3.$tn "DELETE FROM t3 WHERE $where" $res +} + +do_execsql_test 2.4.0 { + CREATE TABLE t6(a, b, c, d); + CREATE INDEX t6a ON t6(a); + CREATE INDEX t6b ON t6(b); + CREATE INDEX t6c ON t6(c); } + +do_adp_test 2.4.1 { + DELETE FROM t6 WHERE a=22 OR b=90 OR (d=0 AND (b=400 OR c=303)); +} [lsort { + t6* t6a t6b* t6c* + t6* t6a* t6b t6c* + t6 t6a* t6b t6c* + t6 t6a* t6b* t6c +}] + +do_adp_test 2.4.2 { + DELETE FROM t6 WHERE a=22 OR b=90 OR (d=1 AND (b=400 OR c=303)); +} [lsort { + t6* t6a t6b* t6c* + t6* t6a* t6b t6c* + t6 t6a* t6b t6c* + t6 t6a* t6b* t6c +}] + +do_adp_test 2.4.3 { + DELETE FROM t6 WHERE (d=0 AND (a=100 OR b=150)) OR (d=1 AND (b=50 OR c=603)); +} [lsort { + t6 t6a t6b* t6c* + t6 t6a* t6b t6c* + t6 t6a* t6b t6c* + t6 t6a* t6b* t6c +}] #------------------------------------------------------------------------- # Test that a record that consists of the bytes: # # 0x01 0x00 Index: test/table.test ================================================================== --- test/table.test +++ test/table.test @@ -832,8 +832,19 @@ do_execsql_test table-19.1 { CREATE TABLE t19 AS SELECT * FROM sqlite_master; SELECT name FROM t19 ORDER BY name; } {{} savepoint t10 t11 t12 t13 t16 t2 t3 t3\"xyz t4\"abc t7 t8 t9 tablet8 test1 weird} +# At one point the DROP TABLE in the following was causing problems on an +# experimental branch. +# +reset_db +do_execsql_test table-20.0 { + CREATE TABLE t20(a PRIMARY KEY, b, c); + CREATE TRIGGER tr6 AFTER INSERT ON t20 BEGIN SELECT 1+1+1; END; + ANALYZE; + DROP TABLE t20; + SELECT name FROM sqlite_master +} {sqlite_stat1 sqlite_stat4} finish_test