From 059b2d50e1c6a57ca301f3c9639f92f7e16ff96e Mon Sep 17 00:00:00 2001 From: drh Date: Fri, 24 Oct 2014 19:28:09 +0000 Subject: [PATCH] Enhance the automatic index logic so that it creates a partial index when doing so gives the same answer for less work. FossilOrigin-Name: d95d0313c447f5baeabdb17284d8606331ab7d49 --- manifest | 19 +++++----- manifest.uuid | 2 +- src/expr.c | 85 +++++++++++++++++++++++++++----------------- src/resolve.c | 4 +-- src/sqliteInt.h | 5 ++- src/where.c | 23 ++++++++++-- test/autoindex4.test | 52 +++++++++++++++++++++++++++ 7 files changed, 143 insertions(+), 47 deletions(-) create mode 100644 test/autoindex4.test diff --git a/manifest b/manifest index e98be71834..e831ecb526 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Honor\sa\shigh\slikelihood()\son\srange\sconstraints. -D 2014-10-24T15:26:29.800 +C Enhance\sthe\sautomatic\sindex\slogic\sso\sthat\sit\screates\sa\spartial\sindex\swhen\ndoing\sso\sgives\sthe\ssame\sanswer\sfor\sless\swork. +D 2014-10-24T19:28:09.216 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in cf57f673d77606ab0f2d9627ca52a9ba1464146a F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -181,7 +181,7 @@ F src/complete.c 535183afb3c75628b78ce82612931ac7cdf26f14 F src/ctime.c bb434068b5308a857b181c2d204a320ff0d6c638 F src/date.c 57a7f9ba9f6b4d5268f5e411739066a611f99036 F src/delete.c fae81cc2eb14b75267d4f47d3cfc9ae02aae726f -F src/expr.c fc204d08af06437ddaffe5a1b1f1f6f9e1a55d6d +F src/expr.c 0391a657df4959eaf2a2fd7d77de5ebe750686ee F src/fault.c 160a0c015b6c2629d3899ed2daf63d75754a32bb F src/fkey.c da985ae673efef2c712caef825a5d2edb087ead7 F src/func.c ba47c1671ab3cfdafa6e9d6ee490939ea578adee @@ -225,14 +225,14 @@ F src/pragma.c 3f3e959390a10c0131676f0e307acce372777e0f F src/prepare.c 6ef0cf2f9274982988ed6b7cab1be23147e94196 F src/printf.c 090fac0f779c93c8a95089a125339686648835e4 F src/random.c d10c1f85b6709ca97278428fd5db5bbb9c74eece -F src/resolve.c a3466128b52a86c466e47ac1a19e2174f7b5cf89 +F src/resolve.c 57d5ad93913beb43ad9b8ade435a54e5fb8ccd40 F src/rowset.c eccf6af6d620aaa4579bd3b72c1b6395d9e9fa1e F src/select.c 428165951748151e87a15295b7357221433e311b F src/shell.c 282f8f5278e0c78eb442217531172ec9e1538796 F src/sqlite.h.in 4a5e5158c189d2bcd45c7c4607c2c0eb6d25c153 F src/sqlite3.rc 992c9f5fb8285ae285d6be28240a7e8d3a7f2bad F src/sqlite3ext.h 17d487c3c91b0b8c584a32fbeb393f6f795eea7d -F src/sqliteInt.h 6e9e125698c1e5c78a51050ea61f179a281c766d +F src/sqliteInt.h 123b28f3552d4ffdd3e53707fe8120a069df69e4 F src/sqliteLimit.h 164b0e6749d31e0daa1a4589a169d31c0dec7b3d F src/status.c 961d5926e5a8fda611d385ec22c226b8635cd1cb F src/table.c 2e99ef7ef16187e17033d9398dc962ce22dab5cb @@ -302,7 +302,7 @@ F src/vtab.c cb0c194303fea276b48d7d4b6d970b5a96bde8de F src/wal.c 10e7de7ce90865a68153f001a61f1d985cd17983 F src/wal.h df01efe09c5cb8c8e391ff1715cca294f89668a4 F src/walker.c c253b95b4ee44b21c406e2a1052636c31ea27804 -F src/where.c f5c13d9c1929bcc9d571f1e7bf7bfeb8b872ef99 +F src/where.c cc0733c59bd8bf6027d28b7d24b1887f4a870215 F src/whereInt.h 4b459cdbfc9b01f5f27673a35f9967e4dea917e8 F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 @@ -346,6 +346,7 @@ F test/autoinc.test c58912526998a39e11f66b533e23cfabea7f25b7 F test/autoindex1.test 6ff78b94f43a59616c06c11c55b12935173506d7 F test/autoindex2.test 60d2fc6f38364308ce73a9beb01b47ded38697de F test/autoindex3.test 8254f689c3241081fad52b7bea18ba53e07e14a2 +F test/autoindex4.test fc807f9efd158bec60f5dfdf34ebe46fb274612d F test/autovacuum.test 941892505d2c0f410a0cb5970dfa1c7c4e5f6e74 F test/autovacuum_ioerr2.test 8a367b224183ad801e0e24dcb7d1501f45f244b4 F test/avtrans.test 0252654f4295ddda3b2cce0e894812259e655a85 @@ -1205,7 +1206,7 @@ F tool/vdbe_profile.tcl 67746953071a9f8f2f668b73fe899074e2c6d8c1 F tool/warnings-clang.sh f6aa929dc20ef1f856af04a730772f59283631d4 F tool/warnings.sh 0abfd78ceb09b7f7c27c688c8e3fe93268a13b32 F tool/win/sqlite.vsix deb315d026cc8400325c5863eef847784a219a2f -P 03d0498d0f24bec2383d5d79edf25069effecd59 -R eb013b99b9ff12a41d5ffc947e4a6227 +P 401235edf40fcd665eaf426cf5155ac6855e8537 +R def8f7d87d0f5784d9eaab2c56b2a690 U drh -Z 3215dd92b9608b7b9136fb91eb8178e8 +Z cb611c4b71e8fc233ea4e1005f56a9e0 diff --git a/manifest.uuid b/manifest.uuid index 4ee03d34ab..7417ef4fc1 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -401235edf40fcd665eaf426cf5155ac6855e8537 \ No newline at end of file +d95d0313c447f5baeabdb17284d8606331ab7d49 \ No newline at end of file diff --git a/src/expr.c b/src/expr.c index 1ad9a879a3..13a9cb46fd 100644 --- a/src/expr.c +++ b/src/expr.c @@ -1210,20 +1210,24 @@ void sqlite3ExprListDelete(sqlite3 *db, ExprList *pList){ } /* -** These routines are Walker callbacks. Walker.u.pi is a pointer -** to an integer. These routines are checking an expression to see -** if it is a constant. Set *Walker.u.i to 0 if the expression is -** not constant. +** These routines are Walker callbacks used to check expressions to +** see if they are "constant" for some definition of constant. The +** Walker.eCode value determines the type of "constant" we are looking +** for. ** ** These callback routines are used to implement the following: ** -** sqlite3ExprIsConstant() pWalker->u.i==1 -** sqlite3ExprIsConstantNotJoin() pWalker->u.i==2 -** sqlite3ExprIsConstantOrFunction() pWalker->u.i==3 or 4 +** sqlite3ExprIsConstant() pWalker->eCode==1 +** sqlite3ExprIsConstantNotJoin() pWalker->eCode==2 +** sqlite3ExprRefOneTableOnly() pWalker->eCode==3 +** sqlite3ExprIsConstantOrFunction() pWalker->eCode==4 or 5 +** +** In all cases, the callbacks set Walker.eCode=0 and abort if the expression +** is found to not be a constant. ** ** The sqlite3ExprIsConstantOrFunction() is used for evaluating expressions -** in a CREATE TABLE statement. The Walker.u.i value is 4 when parsing -** an existing schema and 3 when processing a new statement. A bound +** in a CREATE TABLE statement. The Walker.eCode value is 5 when parsing +** an existing schema and 4 when processing a new statement. A bound ** parameter raises an error for new statements, but is silently converted ** to NULL for existing schemas. This allows sqlite_master tables that ** contain a bound parameter because they were generated by older versions @@ -1232,23 +1236,25 @@ void sqlite3ExprListDelete(sqlite3 *db, ExprList *pList){ */ static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){ - /* If pWalker->u.i is 2 then any term of the expression that comes from - ** the ON or USING clauses of a join disqualifies the expression + /* If pWalker->eCode is 2 then any term of the expression that comes from + ** the ON or USING clauses of a left join disqualifies the expression ** from being considered constant. */ - if( pWalker->u.i==2 && ExprHasProperty(pExpr, EP_FromJoin) ){ - pWalker->u.i = 0; + if( pWalker->eCode==2 && ExprHasProperty(pExpr, EP_FromJoin) ){ + pWalker->eCode = 0; return WRC_Abort; } switch( pExpr->op ){ /* Consider functions to be constant if all their arguments are constant - ** and either pWalker->u.i==3 or 4 or the function as the SQLITE_FUNC_CONST - ** flag. */ + ** and either pWalker->eCode==4 or 5 or the function has the + ** SQLITE_FUNC_CONST flag. */ case TK_FUNCTION: - if( pWalker->u.i>=3 || ExprHasProperty(pExpr,EP_Constant) ){ + if( pWalker->eCode>=4 || ExprHasProperty(pExpr,EP_Constant) ){ return WRC_Continue; + }else{ + pWalker->eCode = 0; + return WRC_Abort; } - /* Fall through */ case TK_ID: case TK_COLUMN: case TK_AGG_FUNCTION: @@ -1257,18 +1263,22 @@ static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){ testcase( pExpr->op==TK_COLUMN ); testcase( pExpr->op==TK_AGG_FUNCTION ); testcase( pExpr->op==TK_AGG_COLUMN ); - pWalker->u.i = 0; - return WRC_Abort; + if( pWalker->eCode==3 && pExpr->iTable==pWalker->u.iCur ){ + return WRC_Continue; + }else{ + pWalker->eCode = 0; + return WRC_Abort; + } case TK_VARIABLE: - if( pWalker->u.i==4 ){ + if( pWalker->eCode==5 ){ /* Silently convert bound parameters that appear inside of CREATE ** statements into a NULL when parsing the CREATE statement text out ** of the sqlite_master table */ pExpr->op = TK_NULL; - }else if( pWalker->u.i==3 ){ + }else if( pWalker->eCode==4 ){ /* A bound parameter in a CREATE statement that originates from ** sqlite3_prepare() causes an error */ - pWalker->u.i = 0; + pWalker->eCode = 0; return WRC_Abort; } /* Fall through */ @@ -1280,21 +1290,22 @@ static int exprNodeIsConstant(Walker *pWalker, Expr *pExpr){ } static int selectNodeIsConstant(Walker *pWalker, Select *NotUsed){ UNUSED_PARAMETER(NotUsed); - pWalker->u.i = 0; + pWalker->eCode = 0; return WRC_Abort; } -static int exprIsConst(Expr *p, int initFlag){ +static int exprIsConst(Expr *p, int initFlag, int iCur){ Walker w; memset(&w, 0, sizeof(w)); - w.u.i = initFlag; + w.eCode = initFlag; w.xExprCallback = exprNodeIsConstant; w.xSelectCallback = selectNodeIsConstant; + w.u.iCur = iCur; sqlite3WalkExpr(&w, p); - return w.u.i; + return w.eCode; } /* -** Walk an expression tree. Return 1 if the expression is constant +** Walk an expression tree. Return non-zero if the expression is constant ** and 0 if it involves variables or function calls. ** ** For the purposes of this function, a double-quoted string (ex: "abc") @@ -1302,21 +1313,31 @@ static int exprIsConst(Expr *p, int initFlag){ ** a constant. */ int sqlite3ExprIsConstant(Expr *p){ - return exprIsConst(p, 1); + return exprIsConst(p, 1, 0); } /* -** Walk an expression tree. Return 1 if the expression is constant +** Walk an expression tree. Return non-zero if the expression is constant ** that does no originate from the ON or USING clauses of a join. ** Return 0 if it involves variables or function calls or terms from ** an ON or USING clause. */ int sqlite3ExprIsConstantNotJoin(Expr *p){ - return exprIsConst(p, 2); + return exprIsConst(p, 2, 0); +} + +/* +** Walk an expression tree. Return non-zero if the expression constant +** for any single row of the table with cursor iCur. In other words, the +** expression must not refer to any non-deterministic function nor any +** table other than iCur. +*/ +int sqlite3ExprIsTableConstant(Expr *p, int iCur){ + return exprIsConst(p, 3, iCur); } /* -** Walk an expression tree. Return 1 if the expression is constant +** Walk an expression tree. Return non-zero if the expression is constant ** or a function call with constant arguments. Return and 0 if there ** are any variables. ** @@ -1326,7 +1347,7 @@ int sqlite3ExprIsConstantNotJoin(Expr *p){ */ int sqlite3ExprIsConstantOrFunction(Expr *p, u8 isInit){ assert( isInit==0 || isInit==1 ); - return exprIsConst(p, 3+isInit); + return exprIsConst(p, 4+isInit, 0); } /* diff --git a/src/resolve.c b/src/resolve.c index d6a865caef..e507ccb810 100644 --- a/src/resolve.c +++ b/src/resolve.c @@ -28,7 +28,7 @@ ** is a helper function - a callback for the tree walker. */ static int incrAggDepth(Walker *pWalker, Expr *pExpr){ - if( pExpr->op==TK_AGG_FUNCTION ) pExpr->op2 += pWalker->u.i; + if( pExpr->op==TK_AGG_FUNCTION ) pExpr->op2 += pWalker->u.n; return WRC_Continue; } static void incrAggFunctionDepth(Expr *pExpr, int N){ @@ -36,7 +36,7 @@ static void incrAggFunctionDepth(Expr *pExpr, int N){ Walker w; memset(&w, 0, sizeof(w)); w.xExprCallback = incrAggDepth; - w.u.i = N; + w.u.n = N; sqlite3WalkExpr(&w, pExpr); } } diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 1b3138be44..b7f992c34d 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -2892,9 +2892,11 @@ struct Walker { void (*xSelectCallback2)(Walker*,Select*);/* Second callback for SELECTs */ Parse *pParse; /* Parser context. */ int walkerDepth; /* Number of subqueries */ + u8 eCode; /* A small processing code */ union { /* Extra data for callback */ NameContext *pNC; /* Naming context */ - int i; /* Integer value */ + int n; /* A counter */ + int iCur; /* A cursor number */ SrcList *pSrcList; /* FROM clause */ struct SrcCount *pSrcCount; /* Counting column references */ } u; @@ -3295,6 +3297,7 @@ void sqlite3LeaveMutexAndCloseZombie(sqlite3*); int sqlite3ExprIsConstant(Expr*); int sqlite3ExprIsConstantNotJoin(Expr*); int sqlite3ExprIsConstantOrFunction(Expr*, u8); +int sqlite3ExprIsTableConstant(Expr*,int); int sqlite3ExprIsInteger(Expr*, int*); int sqlite3ExprCanBeNull(const Expr*); int sqlite3ExprNeedsNoAffinityChange(const Expr*, char); diff --git a/src/where.c b/src/where.c index e13b223366..8d2a891870 100644 --- a/src/where.c +++ b/src/where.c @@ -1594,6 +1594,8 @@ static void constructAutomaticIndex( Bitmask idxCols; /* Bitmap of columns used for indexing */ Bitmask extraCols; /* Bitmap of additional columns */ u8 sentWarning = 0; /* True if a warnning has been issued */ + Expr *pPartial = 0; /* Partial Index Expression */ + int iContinue = 0; /* Jump here to skip excluded rows */ /* Generate code to skip over the creation and initialization of the ** transient index on 2nd and subsequent iterations of the loop. */ @@ -1609,6 +1611,11 @@ static void constructAutomaticIndex( pLoop = pLevel->pWLoop; idxCols = 0; for(pTerm=pWC->a; pTermprereq==0 + && sqlite3ExprIsTableConstant(pTerm->pExpr, pSrc->iCursor) ){ + pPartial = sqlite3ExprAnd(pParse->db, pPartial, + sqlite3ExprDup(pParse->db, pTerm->pExpr, 0)); + } if( termCanDriveIndex(pTerm, pSrc, notReady) ){ int iCol = pTerm->u.leftColumn; Bitmask cMask = iCol>=BMS ? MASKBIT(BMS-1) : MASKBIT(iCol); @@ -1621,7 +1628,9 @@ static void constructAutomaticIndex( sentWarning = 1; } if( (idxCols & cMask)==0 ){ - if( whereLoopResize(pParse->db, pLoop, nKeyCol+1) ) return; + if( whereLoopResize(pParse->db, pLoop, nKeyCol+1) ){ + goto end_auto_index_create; + } pLoop->aLTerm[nKeyCol++] = pTerm; idxCols |= cMask; } @@ -1654,7 +1663,7 @@ static void constructAutomaticIndex( /* Construct the Index object to describe this index */ pIdx = sqlite3AllocateIndexObject(pParse->db, nKeyCol+1, 0, &zNotUsed); - if( pIdx==0 ) return; + if( pIdx==0 ) goto end_auto_index_create; pLoop->u.btree.pIndex = pIdx; pIdx->zName = "auto-index"; pIdx->pTable = pTable; @@ -1706,18 +1715,28 @@ static void constructAutomaticIndex( VdbeComment((v, "for %s", pTable->zName)); /* Fill the automatic index with content */ + sqlite3ExprCachePush(pParse); addrTop = sqlite3VdbeAddOp1(v, OP_Rewind, pLevel->iTabCur); VdbeCoverage(v); + if( pPartial ){ + iContinue = sqlite3VdbeMakeLabel(v); + sqlite3ExprIfFalse(pParse, pPartial, iContinue, SQLITE_JUMPIFNULL); + } regRecord = sqlite3GetTempReg(pParse); sqlite3GenerateIndexKey(pParse, pIdx, pLevel->iTabCur, regRecord, 0, 0, 0, 0); sqlite3VdbeAddOp2(v, OP_IdxInsert, pLevel->iIdxCur, regRecord); sqlite3VdbeChangeP5(v, OPFLAG_USESEEKRESULT); + if( pPartial ) sqlite3VdbeResolveLabel(v, iContinue); sqlite3VdbeAddOp2(v, OP_Next, pLevel->iTabCur, addrTop+1); VdbeCoverage(v); sqlite3VdbeChangeP5(v, SQLITE_STMTSTATUS_AUTOINDEX); sqlite3VdbeJumpHere(v, addrTop); sqlite3ReleaseTempReg(pParse, regRecord); + sqlite3ExprCachePop(pParse); /* Jump here when skipping the initialization */ sqlite3VdbeJumpHere(v, addrInit); + +end_auto_index_create: + sqlite3ExprDelete(pParse->db, pPartial); } #endif /* SQLITE_OMIT_AUTOMATIC_INDEX */ diff --git a/test/autoindex4.test b/test/autoindex4.test new file mode 100644 index 0000000000..6d0865bf72 --- /dev/null +++ b/test/autoindex4.test @@ -0,0 +1,52 @@ +# 2014-10-24 +# +# 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 script is testing automatic index creation logic, +# and specifically creation of automatic partial indexes. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +do_execsql_test autoindex4-1.0 { + CREATE TABLE t1(a,b); + INSERT INTO t1 VALUES(123,'abc'),(234,'def'),(234,'ghi'),(345,'jkl'); + CREATE TABLE t2(x,y); + INSERT INTO t2 VALUES(987,'zyx'),(654,'wvu'),(987,'rqp'); + + SELECT *, '|' FROM t1, t2 WHERE a=234 AND x=987 ORDER BY +b; +} {234 def 987 rqp | 234 def 987 zyx | 234 ghi 987 rqp | 234 ghi 987 zyx |} +do_execsql_test autoindex4-1.1 { + SELECT *, '|' FROM t1, t2 WHERE a=234 AND x=555; +} {} + +do_execsql_test autoindex4-1.2 { + SELECT *, '|' FROM t1 LEFT JOIN t2 ON a=234 AND x=555; +} {123 abc {} {} | 234 def {} {} | 234 ghi {} {} | 345 jkl {} {} |} +do_execsql_test autoindex4-1.3 { + SELECT *, '|' FROM t1 LEFT JOIN t2 ON x=555 WHERE a=234; +} {234 def {} {} | 234 ghi {} {} |} +do_execsql_test autoindex4-1.4 { + SELECT *, '|' FROM t1 LEFT JOIN t2 WHERE a=234 AND x=555; +} {} + + +do_execsql_test autoindex4-2.0 { + CREATE TABLE t3(e,f); + INSERT INTO t3 VALUES(123,654),(555,444),(234,987); + + SELECT (SELECT count(*) FROM t1, t2 WHERE a=e AND x=f), e, f, '|' + FROM t3 + ORDER BY rowid; +} {1 123 654 | 0 555 444 | 4 234 987 |} + +finish_test -- 2.47.2