For a table on the rhs of a LEFT JOIN operator, do not include terms like "IS NULL" from the WHERE clause in the cursor-hint. These may be false for rows that the cursor would otherwise visit, but true for a row of all NULL values generated by the LEFT JOIN.
FossilOrigin-Name: 913e595615e2ef40fb431f6e7678f6fc8439782e
diff --git a/manifest b/manifest
index b6450cc..f7bf4fc 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Add\sa\smissing\sOP_ColumnsUsed\sopcode\sto\scode\sfor\sexpressions\slike\s"?\sIN\s(SELECT\s...)"\sin\scases\swhere\sexpression\scan\suse\san\sindex\sthat\smay\scontain\sNULL\svalues.
-D 2016-06-16T17:14:02.375
+C For\sa\stable\son\sthe\srhs\sof\sa\sLEFT\sJOIN\soperator,\sdo\snot\sinclude\sterms\slike\s"IS\sNULL"\sfrom\sthe\sWHERE\sclause\sin\sthe\scursor-hint.\sThese\smay\sbe\sfalse\sfor\srows\sthat\sthe\scursor\swould\sotherwise\svisit,\sbut\strue\sfor\sa\srow\sof\sall\sNULL\svalues\sgenerated\sby\sthe\sLEFT\sJOIN.
+D 2016-06-20T17:25:50.750
F Makefile.in f3f7d2060ce03af4584e711ef3a626ef0b1d6340
F Makefile.linux-gcc 7bc79876b875010e8c8f9502eb935ca92aa3c434
F Makefile.msc 50149765ef72f4e652b9a0f1f6462c4784bb9423
@@ -464,7 +464,7 @@
F src/walker.c 0f142b5bd3ed2041fc52d773880748b212e63354
F src/where.c 74f0798525b6306682d7234f230ea93f86959b9b
F src/whereInt.h e5b939701a7ceffc5a3a8188a37f9746416ebcd0
-F src/wherecode.c ba71a4e4bada29aa9842200e6299714bf18c812c
+F src/wherecode.c e20cb381ff621e56a4684c71e31999aca2547ca6
F src/whereexpr.c c32d47085dbaca0b8fd013210f56693c7d220d48
F test/8_3_names.test ebbb5cd36741350040fd28b432ceadf495be25b2
F test/affinity2.test a6d901b436328bd67a79b41bb0ac2663918fe3bd
@@ -617,6 +617,7 @@
F test/csv01.test 0929a9ce47021519512be92861f29e32d2538e5f
F test/ctime.test 7bd009071e242aac4f18521581536b652b789a47
F test/cursorhint.test 7bc346788390475e77a345da2b92270d04d35856
+F test/cursorhint2.test 2b45341d32d1aae9991a00ef31ebca339b274255
F test/date.test 984ac1e3e5e031386866f034006148d3972b4a65
F test/dbstatus.test 8de104bb5606f19537d23cd553b41349b5ab1204
F test/dbstatus2.test e93ab03bfae6d62d4d935f20de928c19ca0ed0ab
@@ -1375,7 +1376,7 @@
F test/walthread.test de8dbaf6d9e41481c460ba31ca61e163d7348f8e
F test/where.test f0c325563acde44f2c4ea6ba348e9e29f7121757
F test/where2.test 478d2170637b9211f593120648858593bf2445a1
-F test/where3.test 1ad55ba900bd7747f98b6082e65bd3e442c5004e
+F test/where3.test 54cdeb02157acc979de41530b804ae7b09552bf1
F test/where4.test 4a371bfcc607f41d233701bdec33ac2972908ba8
F test/where5.test fdf66f96d29a064b63eb543e28da4dfdccd81ad2
F test/where6.test 5da5a98cec820d488e82708301b96cb8c18a258b
@@ -1501,7 +1502,8 @@
F vsixtest/vsixtest.vcxproj.data 2ed517e100c66dc455b492e1a33350c1b20fbcdc
F vsixtest/vsixtest.vcxproj.filters 37e51ffedcdb064aad6ff33b6148725226cd608e
F vsixtest/vsixtest_TemporaryKey.pfx e5b1b036facdb453873e7084e1cae9102ccc67a0
-P 48b555c42de1cbc031fb6c2c93ef170e491c7d76
-R 7c056b92500e212b6fa7144618e1e6e0
+P 0b1579caf06a2c42433b8bc9dc28c9ad381aa07c 7455d932f5079ffe40462a8c119fc22b8a9bcbcc
+R 6b36cf1cbd5dc0e94253a2a90e40c230
+T +closed 7455d932f5079ffe40462a8c119fc22b8a9bcbcc
U dan
-Z 6cf13efbb72ea4474e244da36e8952f1
+Z 537cf80c06fd3994884c97d3059d4966
diff --git a/manifest.uuid b/manifest.uuid
index 6347d15..5380697 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-0b1579caf06a2c42433b8bc9dc28c9ad381aa07c
\ No newline at end of file
+913e595615e2ef40fb431f6e7678f6fc8439782e
\ No newline at end of file
diff --git a/src/wherecode.c b/src/wherecode.c
index 83ee48a..a017b40 100644
--- a/src/wherecode.c
+++ b/src/wherecode.c
@@ -626,6 +626,38 @@
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
@@ -678,6 +710,7 @@
** 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 */
@@ -708,7 +741,42 @@
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
@@ -742,7 +810,7 @@
}
}
#else
-# define codeCursorHint(A,B,C) /* No-op */
+# define codeCursorHint(A,B,C,D) /* No-op */
#endif /* SQLITE_ENABLE_CURSOR_HINTS */
/*
@@ -998,7 +1066,7 @@
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 */
@@ -1212,7 +1280,7 @@
** 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];
@@ -1660,7 +1728,7 @@
** 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);
diff --git a/test/cursorhint2.test b/test/cursorhint2.test
new file mode 100644
index 0000000..3444fdf
--- /dev/null
+++ b/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
+
diff --git a/test/where3.test b/test/where3.test
index c2804b5..6edbe2b 100644
--- a/test/where3.test
+++ b/test/where3.test
@@ -45,7 +45,7 @@
}
} {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}
@@ -86,7 +86,7 @@
}
} {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
