diff options
author | drh <drh@noemail.net> | 2018-12-24 02:34:49 +0000 |
---|---|---|
committer | drh <drh@noemail.net> | 2018-12-24 02:34:49 +0000 |
commit | 2c04131ca7e485cd6e6f0741c14b2c570c65122c (patch) | |
tree | f1f70c8d2ef62ad25f941530935a5f8a97b509be /src | |
parent | 85bcdce270575e78258148c00f2efff7e81e7bc1 (diff) | |
download | sqlite-2c04131ca7e485cd6e6f0741c14b2c570c65122c.tar.gz sqlite-2c04131ca7e485cd6e6f0741c14b2c570c65122c.zip |
Experimental code that tries to put the computation of subqueries inside a
subroutine, and reuse that subroutine if the same subquery is evaluated more
than once. Current code does not work for CHECK constraints.
FossilOrigin-Name: 6c44838adbe5dc482bc010e91a6dd7a0f777c989f443dd600740d2c783208e0d
Diffstat (limited to 'src')
-rw-r--r-- | src/expr.c | 127 | ||||
-rw-r--r-- | src/sqliteInt.h | 9 | ||||
-rw-r--r-- | src/vdbe.c | 5 | ||||
-rw-r--r-- | src/where.c | 1 | ||||
-rw-r--r-- | src/wherecode.c | 10 |
5 files changed, 107 insertions, 45 deletions
diff --git a/src/expr.c b/src/expr.c index 8ef2ee30b..dba01b4d8 100644 --- a/src/expr.c +++ b/src/expr.c @@ -2350,7 +2350,8 @@ int sqlite3FindInIndex( Expr *pX, /* The right-hand side (RHS) of the IN operator */ u32 inFlags, /* IN_INDEX_LOOP, _MEMBERSHIP, and/or _NOOP_OK */ int *prRhsHasNull, /* Register holding NULL status. See notes */ - int *aiMap /* Mapping from Index fields to RHS fields */ + int *aiMap, /* Mapping from Index fields to RHS fields */ + int *piTab /* OUT: index to use */ ){ Select *p; /* SELECT to the right of IN operator */ int eType = 0; /* Type of RHS table. IN_INDEX_* */ @@ -2543,13 +2544,11 @@ int sqlite3FindInIndex( *prRhsHasNull = rMayHaveNull = ++pParse->nMem; } assert( pX->op==TK_IN ); - sqlite3CodeRhsOfIN(pParse, pX, eType==IN_INDEX_ROWID); + sqlite3CodeRhsOfIN(pParse, pX, iTab, eType==IN_INDEX_ROWID); if( rMayHaveNull ){ - sqlite3SetHasNullFlag(v, pX->iTable, rMayHaveNull); + sqlite3SetHasNullFlag(v, iTab, rMayHaveNull); } pParse->nQueryLoop = savedNQueryLoop; - }else{ - pX->iTable = iTab; } if( aiMap && eType!=IN_INDEX_INDEX_ASC && eType!=IN_INDEX_INDEX_DESC ){ @@ -2557,6 +2556,7 @@ int sqlite3FindInIndex( n = sqlite3ExprVectorSize(pX->pLeft); for(i=0; i<n; i++) aiMap[i] = i; } + *piTab = iTab; return eType; } #endif @@ -2639,7 +2639,11 @@ void sqlite3VectorErrorMsg(Parse *pParse, Expr *pExpr){ ** x IN (4,5,11) -- IN operator with list on right-hand side ** x IN (SELECT a FROM b) -- IN operator with subquery on the right ** -** The pExpr parameter is the IN operator. +** The pExpr parameter is the IN operator. The cursor number for the +** constructed ephermeral table is returned. The first time the ephemeral +** table is computed, the cursor number is also stored in pExpr->iTable, +** however the cursor number returned might not be the same, as it might +** have been duplicated using OP_OpenDup. ** ** If parameter isRowid is non-zero, then LHS of the IN operator is guaranteed ** to be a non-null integer. In this case, the ephemeral table can be an @@ -2658,30 +2662,50 @@ void sqlite3VectorErrorMsg(Parse *pParse, Expr *pExpr){ void sqlite3CodeRhsOfIN( Parse *pParse, /* Parsing context */ Expr *pExpr, /* The IN operator */ + int iTab, /* Use this cursor number */ int isRowid /* If true, LHS is a rowid */ ){ - int jmpIfDynamic = -1; /* One-time test address */ + int addrOnce = 0; /* Address of the OP_Once instruction at top */ int addr; /* Address of OP_OpenEphemeral instruction */ Expr *pLeft; /* the LHS of the IN operator */ KeyInfo *pKeyInfo = 0; /* Key information */ int nVal; /* Size of vector pLeft */ Vdbe *v; /* The prepared statement under construction */ - v = sqlite3GetVdbe(pParse); + v = pParse->pVdbe; assert( v!=0 ); - /* The evaluation of the RHS of IN operator must be repeated every time it + /* The evaluation of the IN must be repeated every time it ** is encountered if any of the following is true: ** ** * The right-hand side is a correlated subquery ** * The right-hand side is an expression list containing variables ** * We are inside a trigger ** - ** If all of the above are false, then we can run this code just once - ** save the results, and reuse the same result on subsequent invocations. + ** If all of the above are false, then we can compute the RHS just once + ** and reuse it many names. */ if( !ExprHasProperty(pExpr, EP_VarSelect) ){ - jmpIfDynamic = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); + /* Reuse of the RHS is allowed */ + /* If this routine has already been coded, but the previous code + ** might not have been invoked yet, so invoke it now as a subroutine. + */ + if( ExprHasProperty(pExpr, EP_Subrtn) ){ + sqlite3VdbeAddOp2(v, OP_Once, 0, sqlite3VdbeCurrentAddr(v)+3); + sqlite3VdbeAddOp2(v, OP_Gosub, pExpr->y.sub.regReturn, + pExpr->y.sub.iAddr); + sqlite3VdbeAddOp2(v, OP_OpenDup, iTab, pExpr->iTable); + return; + } + + /* Begin coding the subroutine */ + ExprSetProperty(pExpr, EP_Subrtn); + pExpr->y.sub.regReturn = ++pParse->nMem; + pExpr->y.sub.iAddr = + sqlite3VdbeAddOp2(v, OP_Integer, 0, pExpr->y.sub.regReturn) + 1; + VdbeComment((v, "return address")); + + addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); } /* Check to see if this is a vector IN operator */ @@ -2692,9 +2716,16 @@ void sqlite3CodeRhsOfIN( /* Construct the ephemeral table that will contain the content of ** RHS of the IN operator. */ - pExpr->iTable = pParse->nTab++; + pExpr->iTable = iTab; addr = sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pExpr->iTable, (isRowid?0:nVal)); +#ifdef SQLITE_ENABLE_EXPLAIN_COMMENTS + if( ExprHasProperty(pExpr, EP_xIsSelect) ){ + VdbeComment((v, "Result of SELECT %u", pExpr->x.pSelect->selId)); + }else{ + VdbeComment((v, "RHS of IN operator")); + } +#endif pKeyInfo = isRowid ? 0 : sqlite3KeyInfoAlloc(pParse->db, nVal, 1); if( ExprHasProperty(pExpr, EP_xIsSelect) ){ @@ -2706,8 +2737,8 @@ void sqlite3CodeRhsOfIN( Select *pSelect = pExpr->x.pSelect; ExprList *pEList = pSelect->pEList; - ExplainQueryPlan((pParse, 1, "%sLIST SUBQUERY", - jmpIfDynamic>=0?"":"CORRELATED " + ExplainQueryPlan((pParse, 1, "%sLIST SUBQUERY %d", + addrOnce?"":"CORRELATED ", pSelect->selId )); assert( !isRowid ); /* If the LHS and RHS of the IN operator do not match, that @@ -2772,9 +2803,9 @@ void sqlite3CodeRhsOfIN( ** this code only executes once. Because for a non-constant ** expression we need to rerun this code each time. */ - if( jmpIfDynamic>=0 && !sqlite3ExprIsConstant(pE2) ){ - sqlite3VdbeChangeToNoop(v, jmpIfDynamic); - jmpIfDynamic = -1; + if( addrOnce && !sqlite3ExprIsConstant(pE2) ){ + sqlite3VdbeChangeToNoop(v, addrOnce); + addrOnce = 0; } /* Evaluate the expression and insert it into the temp table */ @@ -2799,8 +2830,11 @@ void sqlite3CodeRhsOfIN( if( pKeyInfo ){ sqlite3VdbeChangeP4(v, addr, (void *)pKeyInfo, P4_KEYINFO); } - if( jmpIfDynamic>=0 ){ - sqlite3VdbeJumpHere(v, jmpIfDynamic); + if( addrOnce ){ + sqlite3VdbeJumpHere(v, addrOnce); + /* Subroutine return */ + sqlite3VdbeAddOp1(v, OP_Return, pExpr->y.sub.regReturn); + sqlite3VdbeChangeP1(v, pExpr->y.sub.iAddr-1, sqlite3VdbeCurrentAddr(v)-1); } } #endif /* SQLITE_OMIT_SUBQUERY */ @@ -2821,16 +2855,30 @@ void sqlite3CodeRhsOfIN( */ #ifndef SQLITE_OMIT_SUBQUERY int sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){ - int jmpIfDynamic = -1; /* One-time test address */ + int addrOnce = 0; /* Address of OP_Once at top of subroutine */ int rReg = 0; /* Register storing resulting */ Select *pSel; /* SELECT statement to encode */ SelectDest dest; /* How to deal with SELECT result */ int nReg; /* Registers to allocate */ Expr *pLimit; /* New limit expression */ - Vdbe *v = sqlite3GetVdbe(pParse); + + Vdbe *v = pParse->pVdbe; assert( v!=0 ); - /* The evaluation of the EXISTS/SELECT must be repeated every time it + /* If this routine has already been coded, then invoke it as a subroutine. */ + if( ExprHasProperty(pExpr, EP_Subrtn) ){ + sqlite3VdbeAddOp2(v, OP_Gosub, pExpr->y.sub.regReturn, pExpr->y.sub.iAddr); + return pExpr->iTable; + } + + /* Begin coding the subroutine */ + ExprSetProperty(pExpr, EP_Subrtn); + pExpr->y.sub.regReturn = ++pParse->nMem; + pExpr->y.sub.iAddr = + sqlite3VdbeAddOp2(v, OP_Integer, 0, pExpr->y.sub.regReturn) + 1; + VdbeComment((v, "return address")); + + /* The evaluation of the IN/EXISTS/SELECT must be repeated every time it ** is encountered if any of the following is true: ** ** * The right-hand side is a correlated subquery @@ -2841,7 +2889,7 @@ int sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){ ** save the results, and reuse the same result on subsequent invocations. */ if( !ExprHasProperty(pExpr, EP_VarSelect) ){ - jmpIfDynamic = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); + addrOnce = sqlite3VdbeAddOp0(v, OP_Once); VdbeCoverage(v); } /* For a SELECT, generate code to put the values for all columns of @@ -2861,7 +2909,7 @@ int sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){ pSel = pExpr->x.pSelect; ExplainQueryPlan((pParse, 1, "%sSCALAR SUBQUERY", - jmpIfDynamic>=0?"":"CORRELATED ")); + addrOnce?"":"CORRELATED ")); nReg = pExpr->op==TK_SELECT ? pSel->pEList->nExpr : 1; sqlite3SelectDestInit(&dest, 0, pParse->nMem+1); pParse->nMem += nReg; @@ -2887,13 +2935,16 @@ int sqlite3CodeSubselect(Parse *pParse, Expr *pExpr){ if( sqlite3Select(pParse, pSel, &dest) ){ return 0; } - rReg = dest.iSDParm; + pExpr->iTable = rReg = dest.iSDParm; ExprSetVVAProperty(pExpr, EP_NoReduce); - - if( jmpIfDynamic>=0 ){ - sqlite3VdbeJumpHere(v, jmpIfDynamic); + if( addrOnce ){ + sqlite3VdbeJumpHere(v, addrOnce); } + /* Subroutine return */ + sqlite3VdbeAddOp1(v, OP_Return, pExpr->y.sub.regReturn); + sqlite3VdbeChangeP1(v, pExpr->y.sub.iAddr-1, sqlite3VdbeCurrentAddr(v)-1); + return rReg; } #endif /* SQLITE_OMIT_SUBQUERY */ @@ -2968,6 +3019,7 @@ static void sqlite3ExprCodeIN( int addrTruthOp; /* Address of opcode that determines the IN is true */ int destNotNull; /* Jump here if a comparison is not true in step 6 */ int addrTop; /* Top of the step-6 loop */ + int iTab = 0; /* Index to use */ pLeft = pExpr->pLeft; if( sqlite3ExprCheckIN(pParse, pExpr) ) return; @@ -2979,7 +3031,7 @@ static void sqlite3ExprCodeIN( if( pParse->db->mallocFailed ) goto sqlite3ExprCodeIN_oom_error; /* Attempt to compute the RHS. After this step, if anything other than - ** IN_INDEX_NOOP is returned, the table opened ith cursor pExpr->iTable + ** IN_INDEX_NOOP is returned, the table opened with cursor iTab ** contains the values that make up the RHS. If IN_INDEX_NOOP is returned, ** the RHS has not yet been coded. */ v = pParse->pVdbe; @@ -2987,7 +3039,8 @@ static void sqlite3ExprCodeIN( VdbeNoopComment((v, "begin IN expr")); eType = sqlite3FindInIndex(pParse, pExpr, IN_INDEX_MEMBERSHIP | IN_INDEX_NOOP_OK, - destIfFalse==destIfNull ? 0 : &rRhsHasNull, aiMap); + destIfFalse==destIfNull ? 0 : &rRhsHasNull, + aiMap, &iTab); assert( pParse->nErr || nVector==1 || eType==IN_INDEX_EPH || eType==IN_INDEX_INDEX_ASC || eType==IN_INDEX_INDEX_DESC @@ -3095,19 +3148,19 @@ static void sqlite3ExprCodeIN( /* In this case, the RHS is the ROWID of table b-tree and so we also ** know that the RHS is non-NULL. Hence, we combine steps 3 and 4 ** into a single opcode. */ - sqlite3VdbeAddOp3(v, OP_SeekRowid, pExpr->iTable, destIfFalse, rLhs); + sqlite3VdbeAddOp3(v, OP_SeekRowid, iTab, destIfFalse, rLhs); VdbeCoverage(v); addrTruthOp = sqlite3VdbeAddOp0(v, OP_Goto); /* Return True */ }else{ sqlite3VdbeAddOp4(v, OP_Affinity, rLhs, nVector, 0, zAff, nVector); if( destIfFalse==destIfNull ){ /* Combine Step 3 and Step 5 into a single opcode */ - sqlite3VdbeAddOp4Int(v, OP_NotFound, pExpr->iTable, destIfFalse, + sqlite3VdbeAddOp4Int(v, OP_NotFound, iTab, destIfFalse, rLhs, nVector); VdbeCoverage(v); goto sqlite3ExprCodeIN_finished; } /* Ordinary Step 3, for the case where FALSE and NULL are distinct */ - addrTruthOp = sqlite3VdbeAddOp4Int(v, OP_Found, pExpr->iTable, 0, + addrTruthOp = sqlite3VdbeAddOp4Int(v, OP_Found, iTab, 0, rLhs, nVector); VdbeCoverage(v); } @@ -3132,7 +3185,7 @@ static void sqlite3ExprCodeIN( ** of the RHS. */ if( destStep6 ) sqlite3VdbeResolveLabel(v, destStep6); - addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, pExpr->iTable, destIfFalse); + addrTop = sqlite3VdbeAddOp2(v, OP_Rewind, iTab, destIfFalse); VdbeCoverage(v); if( nVector>1 ){ destNotNull = sqlite3VdbeMakeLabel(v); @@ -3147,7 +3200,7 @@ static void sqlite3ExprCodeIN( int r3 = sqlite3GetTempReg(pParse); p = sqlite3VectorFieldSubexpr(pLeft, i); pColl = sqlite3ExprCollSeq(pParse, p); - sqlite3VdbeAddOp3(v, OP_Column, pExpr->iTable, i, r3); + sqlite3VdbeAddOp3(v, OP_Column, iTab, i, r3); sqlite3VdbeAddOp4(v, OP_Ne, rLhs+i, destNotNull, r3, (void*)pColl, P4_COLLSEQ); VdbeCoverage(v); @@ -3156,7 +3209,7 @@ static void sqlite3ExprCodeIN( sqlite3VdbeAddOp2(v, OP_Goto, 0, destIfNull); if( nVector>1 ){ sqlite3VdbeResolveLabel(v, destNotNull); - sqlite3VdbeAddOp2(v, OP_Next, pExpr->iTable, addrTop+1); + sqlite3VdbeAddOp2(v, OP_Next, iTab, addrTop+1); VdbeCoverage(v); /* Step 7: If we reach this point, we know that the result must diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 2af59ecf8..57938fa9b 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -2485,6 +2485,10 @@ struct Expr { Table *pTab; /* TK_COLUMN: Table containing column. Can be NULL ** for a column of an index on an expression */ Window *pWin; /* TK_FUNCTION: Window definition for the func */ + struct { /* TK_IN, TK_SELECT, and TK_EXISTS */ + int iAddr; /* Subroutine entry address */ + int regReturn; /* Register used to hold return address */ + } sub; } y; }; @@ -2516,6 +2520,7 @@ struct Expr { #define EP_Alias 0x400000 /* Is an alias for a result set column */ #define EP_Leaf 0x800000 /* Expr.pLeft, .pRight, .u.pSelect all NULL */ #define EP_WinFunc 0x1000000 /* TK_FUNCTION with Expr.y.pWin set */ +#define EP_Subrtn 0x2000000 /* Uses Expr.y.sub. TK_IN, _SELECT, or _EXISTS */ /* ** The EP_Propagate mask is a set of properties that automatically propagate @@ -4258,7 +4263,7 @@ void sqlite3AlterRenameColumn(Parse*, SrcList*, Token*, Token*); int sqlite3GetToken(const unsigned char *, int *); void sqlite3NestedParse(Parse*, const char*, ...); void sqlite3ExpirePreparedStatements(sqlite3*, int); -void sqlite3CodeRhsOfIN(Parse*, Expr*, int); +void sqlite3CodeRhsOfIN(Parse*, Expr*, int, int); int sqlite3CodeSubselect(Parse*, Expr*); void sqlite3SelectPrep(Parse*, Select*, NameContext*); void sqlite3SelectWrongNumTermsError(Parse *pParse, Select *p); @@ -4511,7 +4516,7 @@ const char *sqlite3JournalModename(int); #define IN_INDEX_NOOP_OK 0x0001 /* OK to return IN_INDEX_NOOP */ #define IN_INDEX_MEMBERSHIP 0x0002 /* IN operator used for membership test */ #define IN_INDEX_LOOP 0x0004 /* IN operator used as a loop */ -int sqlite3FindInIndex(Parse *, Expr *, u32, int*, int*); +int sqlite3FindInIndex(Parse *, Expr *, u32, int*, int*, int*); int sqlite3JournalOpen(sqlite3_vfs *, const char *, sqlite3_file *, int, int); int sqlite3JournalSize(sqlite3_vfs *); diff --git a/src/vdbe.c b/src/vdbe.c index 590964713..007147d5d 100644 --- a/src/vdbe.c +++ b/src/vdbe.c @@ -3610,7 +3610,8 @@ case OP_OpenDup: { pCx->isEphemeral = 1; pCx->pKeyInfo = pOrig->pKeyInfo; pCx->isTable = pOrig->isTable; - rc = sqlite3BtreeCursor(pOrig->pBtx, MASTER_ROOT, BTREE_WRCSR, + pCx->pgnoRoot = pOrig->pgnoRoot; + rc = sqlite3BtreeCursor(pOrig->pBtx, pCx->pgnoRoot, BTREE_WRCSR, pCx->pKeyInfo, pCx->uc.pCursor); /* The sqlite3BtreeCursor() routine can only fail for the first cursor ** opened for a database. Since there is already an open cursor when this @@ -3682,6 +3683,7 @@ case OP_OpenEphemeral: { assert( pgno==MASTER_ROOT+1 ); assert( pKeyInfo->db==db ); assert( pKeyInfo->enc==ENC(db) ); + pCx->pgnoRoot = pgno; rc = sqlite3BtreeCursor(pCx->pBtx, pgno, BTREE_WRCSR, pKeyInfo, pCx->uc.pCursor); } @@ -3690,6 +3692,7 @@ case OP_OpenEphemeral: { rc = sqlite3BtreeCursor(pCx->pBtx, MASTER_ROOT, BTREE_WRCSR, 0, pCx->uc.pCursor); pCx->isTable = 1; + pCx->pgnoRoot = MASTER_ROOT; } } if( rc ) goto abort_due_to_error; diff --git a/src/where.c b/src/where.c index 8e016604d..077abf777 100644 --- a/src/where.c +++ b/src/where.c @@ -854,6 +854,7 @@ static void constructAutomaticIndex( translateColumnToCopy(pParse, addrTop, pLevel->iTabCur, pTabItem->regResult, 1); sqlite3VdbeGoto(v, addrTop); + pTabItem->fg.viaCoroutine = 0; }else{ sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v); } diff --git a/src/wherecode.c b/src/wherecode.c index acd72a955..946bd0eb7 100644 --- a/src/wherecode.c +++ b/src/wherecode.c @@ -538,16 +538,17 @@ static int codeEqualityTerm( if( pLoop->aLTerm[i]->pExpr==pX ) nEq++; } + iTab = 0; if( (pX->flags & EP_xIsSelect)==0 || pX->x.pSelect->pEList->nExpr==1 ){ - eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0); + eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, 0, &iTab); }else{ sqlite3 *db = pParse->db; pX = removeUnindexableInClauseTerms(pParse, iEq, pLoop, pX); if( !db->mallocFailed ){ aiMap = (int*)sqlite3DbMallocZero(pParse->db, sizeof(int)*nEq); - eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap); - pTerm->pExpr->iTable = pX->iTable; + eType = sqlite3FindInIndex(pParse, pX, IN_INDEX_LOOP, 0, aiMap, &iTab); + pTerm->pExpr->iTable = iTab; } sqlite3ExprDelete(db, pX); pX = pTerm->pExpr; @@ -557,7 +558,6 @@ static int codeEqualityTerm( testcase( bRev ); bRev = !bRev; } - iTab = pX->iTable; sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iTab, 0); VdbeCoverageIf(v, bRev); VdbeCoverageIf(v, !bRev); @@ -2197,7 +2197,7 @@ Bitmask sqlite3WhereCodeOneLoopStart( if( pAlt->wtFlags & (TERM_CODED) ) continue; if( (pAlt->eOperator & WO_IN) && (pAlt->pExpr->flags & EP_xIsSelect) - && (pAlt->pExpr->x.pSelect->pEList->nExpr>1) +// && (pAlt->pExpr->x.pSelect->pEList->nExpr>1) ){ continue; } |