Index: src/wherecode.c ================================================================== --- src/wherecode.c +++ src/wherecode.c @@ -624,10 +624,42 @@ pWalker->eCode = 1; } return WRC_Continue; } +/* +** Test whether or not expression pExpr, which was part of a WHERE clause, +** should be included in the cursor-hint for a table that is on the rhs +** of a LEFT JOIN. Set Walker.eCode to non-zero before returning if the +** expression is not suitable. +** +** An expression is unsuitable if it might evaluate to non NULL even if +** a TK_COLUMN node that does affect the value of the expression is set +** to NULL. For example: +** +** col IS NULL +** col IS NOT NULL +** coalesce(col, 1) +** CASE WHEN col THEN 0 ELSE 1 END +*/ +static int codeCursorHintIsOrFunction(Walker *pWalker, Expr *pExpr){ + if( pExpr->op==TK_IS + || pExpr->op==TK_ISNULL || pExpr->op==TK_ISNOT + || pExpr->op==TK_NOTNULL || pExpr->op==TK_CASE + ){ + pWalker->eCode = 1; + }else if( pExpr->op==TK_FUNCTION ){ + int d1; + char d2[3]; + if( 0==sqlite3IsLikeFunction(pWalker->pParse->db, pExpr, &d1, d2) ){ + pWalker->eCode = 1; + } + } + + return WRC_Continue; +} + /* ** This function is called on every node of an expression tree used as an ** argument to the OP_CursorHint instruction. If the node is a TK_COLUMN ** that accesses any table other than the one identified by @@ -676,10 +708,11 @@ /* ** Insert an OP_CursorHint instruction if it is appropriate to do so. */ static void codeCursorHint( + struct SrcList_item *pTabItem, /* FROM clause item */ WhereInfo *pWInfo, /* The where clause */ WhereLevel *pLevel, /* Which loop to provide hints for */ WhereTerm *pEndRange /* Hint this end-of-scan boundary term if not NULL */ ){ Parse *pParse = pWInfo->pParse; @@ -706,11 +739,46 @@ pWC = &pWInfo->sWC; for(i=0; inTerm; i++){ pTerm = &pWC->a[i]; if( pTerm->wtFlags & (TERM_VIRTUAL|TERM_CODED) ) continue; if( pTerm->prereqAll & pLevel->notReady ) continue; - if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) continue; + + /* Any terms specified as part of the ON(...) clause for any LEFT + ** JOIN for which the current table is not the rhs are omitted + ** from the cursor-hint. + ** + ** If this table is the rhs of a LEFT JOIN, "IS" or "IS NULL" terms + ** that were specified as part of the WHERE clause must be excluded. + ** This is to address the following: + ** + ** SELECT ... t1 LEFT JOIN t2 ON (t1.a=t2.b) WHERE t2.c IS NULL; + ** + ** Say there is a single row in t2 that matches (t1.a=t2.b), but its + ** t2.c values is not NULL. If the (t2.c IS NULL) constraint is + ** pushed down to the cursor, this row is filtered out, causing + ** SQLite to synthesize a row of NULL values. Which does match the + ** WHERE clause, and so the query returns a row. Which is incorrect. + ** + ** For the same reason, WHERE terms such as: + ** + ** WHERE 1 = (t2.c IS NULL) + ** + ** are also excluded. See codeCursorHintIsOrFunction() for details. + */ + if( pTabItem->fg.jointype & JT_LEFT ){ + Expr *pExpr = pTerm->pExpr; + if( !ExprHasProperty(pExpr, EP_FromJoin) + || pExpr->iRightJoinTable!=pTabItem->iCursor + ){ + sWalker.eCode = 0; + sWalker.xExprCallback = codeCursorHintIsOrFunction; + sqlite3WalkExpr(&sWalker, pTerm->pExpr); + if( sWalker.eCode ) continue; + } + }else{ + if( ExprHasProperty(pTerm->pExpr, EP_FromJoin) ) continue; + } /* All terms in pWLoop->aLTerm[] except pEndRange are used to initialize ** the cursor. These terms are not needed as hints for a pure range ** scan (that has no == terms) so omit them. */ if( pLoop->u.btree.nEq==0 && pTerm!=pEndRange ){ @@ -740,11 +808,11 @@ (sHint.pIdx ? sHint.iIdxCur : sHint.iTabCur), 0, 0, (const char*)pExpr, P4_EXPR); } } #else -# define codeCursorHint(A,B,C) /* No-op */ +# define codeCursorHint(A,B,C,D) /* No-op */ #endif /* SQLITE_ENABLE_CURSOR_HINTS */ /* ** Cursor iCur is open on an intkey b-tree (a table). Register iRowid contains ** a rowid value just read from cursor iIdxCur, open on index pIdx. This @@ -996,11 +1064,11 @@ if( bRev ){ pTerm = pStart; pStart = pEnd; pEnd = pTerm; } - codeCursorHint(pWInfo, pLevel, pEnd); + codeCursorHint(pTabItem, pWInfo, pLevel, pEnd); if( pStart ){ Expr *pX; /* The expression that defines the start bound */ int r1, rTemp; /* Registers for holding the start boundary */ /* The following constant maps TK_xx codes into corresponding @@ -1210,11 +1278,11 @@ /* Generate code to evaluate all constraint terms using == or IN ** and store the values of those terms in an array of registers ** starting at regBase. */ - codeCursorHint(pWInfo, pLevel, pRangeEnd); + codeCursorHint(pTabItem, pWInfo, pLevel, pRangeEnd); regBase = codeAllEqualityTerms(pParse,pLevel,bRev,nExtraReg,&zStartAff); assert( zStartAff==0 || sqlite3Strlen30(zStartAff)>=nEq ); if( zStartAff ) cEndAff = zStartAff[nEq]; addrNxt = pLevel->addrNxt; @@ -1658,11 +1726,11 @@ if( pTabItem->fg.isRecursive ){ /* Tables marked isRecursive have only a single row that is stored in ** a pseudo-cursor. No need to Rewind or Next such cursors. */ pLevel->op = OP_Noop; }else{ - codeCursorHint(pWInfo, pLevel, 0); + codeCursorHint(pTabItem, pWInfo, pLevel, 0); pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk); VdbeCoverageIf(v, bRev==0); VdbeCoverageIf(v, bRev!=0); ADDED test/cursorhint2.test Index: test/cursorhint2.test ================================================================== --- /dev/null +++ test/cursorhint2.test @@ -0,0 +1,180 @@ +# 2016 June 17 +# +# 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 is on testing that cursor-hints are correct for queries +# involving LEFT JOIN. +# + + +set testdir [file dirname $argv0] +source $testdir/tester.tcl +set ::testprefix cursorhint2 + +ifcapable !cursorhints { + finish_test + return +} + +proc extract_hints {sql} { + + db eval "SELECT tbl_name, rootpage FROM sqlite_master where rootpage" { + set lookup($rootpage) $tbl_name + } + + set ret [list] + db eval "EXPLAIN $sql" a { + switch -- $a(opcode) { + OpenRead { + set csr($a(p1)) $lookup($a(p2)) + } + CursorHint { + lappend ret $csr($a(p1)) $a(p4) + } + } + } + + set ret +} + +proc do_extract_hints_test {tn sql ret} { + uplevel [list do_test $tn [list extract_hints $sql] [list {*}$ret]] +} + +do_execsql_test 1.0 { + PRAGMA automatic_index = 0; + CREATE TABLE t1(a, b); + CREATE TABLE t2(c, d); + CREATE TABLE t3(e, f); +} + +do_extract_hints_test 1.1 { + SELECT * FROM t1 WHERE a=1; +} { + t1 EQ(c0,1) +} + +do_extract_hints_test 1.2 { + SELECT * FROM t1 CROSS JOIN t2 ON (a=c) WHERE d IS NULL; +} { + t2 {AND(ISNULL(c1),EQ(r[1],c0))} +} + +do_extract_hints_test 1.3 { + SELECT * FROM t1 LEFT JOIN t2 ON (a=c) WHERE d IS NULL; +} { + t2 {EQ(r[2],c0)} +} + +do_extract_hints_test 1.4 { + SELECT * FROM t1 LEFT JOIN t2 ON (a=c AND a=10) WHERE d IS NULL; +} { + t2 {AND(EQ(r[2],c0),EQ(r[3],10))} +} + +do_extract_hints_test 1.5 { + SELECT * FROM t1 CROSS JOIN t2 ON (a=c AND a=10) WHERE d IS NULL; +} { + t1 EQ(c0,10) t2 {AND(ISNULL(c1),EQ(r[3],c0))} +} + +do_extract_hints_test 1.6 { + SELECT * FROM t1 LEFT JOIN t2 ON (a=c) LEFT JOIN t3 ON (d=f); +} { + t2 {EQ(r[2],c0)} t3 {EQ(r[6],c1)} +} + +do_extract_hints_test 1.7 { + SELECT * FROM t1 LEFT JOIN t2 ON (a=c AND d=e) LEFT JOIN t3 ON (d=f); +} { + t2 {EQ(r[2],c0)} t3 {AND(EQ(r[6],c0),EQ(r[7],c1))} +} + +#------------------------------------------------------------------------- +# +do_execsql_test 2.0 { + CREATE TABLE x1(x, y); + CREATE TABLE x2(a, b); +} + +do_extract_hints_test 2.1 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE b IS NULL; +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.2 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE b IS +NULL; +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.3 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 1 = (b IS NULL) +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.4 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 1 = coalesce(b, 1) +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.5 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 1 = coalesce(b, 1) +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.6 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 0 = (b IS NOT NULL) +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.7 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE 0 = (b IS NOT +NULL) +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.8 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE b IS NOT +NULL +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.9 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE CASE b WHEN 0 THEN 0 ELSE 1 END; +} { + x2 {EQ(c0,r[2])} +} + +do_extract_hints_test 2.10 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b = 32+32 +} { + x2 {AND(EQ(c1,ADD(32,32)),EQ(c0,r[2]))} +} + +do_extract_hints_test 2.11 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE x2.b LIKE 'abc%' +} { + x2 {AND(expr,EQ(c0,r[2]))} +} + +do_extract_hints_test 2.11 { + SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE coalesce(x2.b, 1) +} { + x2 {EQ(c0,r[2])} +} + +finish_test + Index: test/where3.test ================================================================== --- test/where3.test +++ test/where3.test @@ -43,11 +43,11 @@ SELECT * FROM t1, t2 LEFT JOIN t3 ON q=x WHERE p=2 AND a=q; } } {222 two 2 222 {} {}} -ifcapable explain { +ifcapable explain&&!cursorhints { do_test where3-1.1.1 { explain_no_trace {SELECT * FROM t1, t2 LEFT JOIN t3 ON q=x WHERE p=2 AND a=q} } [explain_no_trace {SELECT * FROM t1, t2 LEFT JOIN t3 ON x=q WHERE p=2 AND a=q}] @@ -84,11 +84,11 @@ LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key INNER JOIN child2 ON child2.child2key = parent1.child2key; } } {1 {Value for C1.1} {Value for C2.1} 2 {} {Value for C2.2} 3 {Value for C1.3} {Value for C2.3}} -ifcapable explain { +ifcapable explain&&!cursorhints { do_test where3-1.2.1 { explain_no_trace { SELECT parent1.parent1key, child1.value, child2.value FROM parent1 LEFT OUTER JOIN child1 ON child1.child1key = parent1.child1key