From c49de5d98c035e8c5a26dd462fe1730db4367322 Mon Sep 17 00:00:00 2001 From: drh Date: Fri, 19 Jan 2007 01:06:01 +0000 Subject: [PATCH] Make sure the IS NULL optimization introduced by check-in (3494) correctly handles a LEFT JOIN where the a term from the right table of the join uses an IS NULL constraint. Ticket #2177. This check-in also adds the new test cases that were suppose to have been added with (3494) but which were mistakenly omitted. (CVS 3595) FossilOrigin-Name: 335863e4d16113fb9ecebce35d2db043771d98b1 --- manifest | 15 ++--- manifest.uuid | 2 +- src/sqliteInt.h | 9 ++- src/where.c | 20 +++++-- test/where4.test | 144 +++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 176 insertions(+), 14 deletions(-) create mode 100644 test/where4.test diff --git a/manifest b/manifest index eccd6e42e8..2dbd83a558 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Additional\smemory\sinitialization\sin\slemon\s-\sbug\sreported\sfrom\swireshark.\nTicket\s#2172.\s\sNote\sthis\sproblem\sonly\scomes\sup\swith\scertain\sgrammars,\nand\sdoes\snot\simpact\sSQLite.\s\sOn\sthe\sother\shand,\sit\smight\scause\sSQLite\nto\srun\sslower.\s\sSo\swe\smight\swant\sto\srevisit\sthis\schange\sat\ssome\spoint.\s(CVS\s3594) -D 2007-01-16T18:19:13 +C Make\ssure\sthe\sIS\sNULL\soptimization\sintroduced\sby\scheck-in\s(3494)\scorrectly\nhandles\sa\sLEFT\sJOIN\swhere\sthe\sa\sterm\sfrom\sthe\sright\stable\sof\sthe\sjoin\suses\nan\sIS\sNULL\sconstraint.\s\sTicket\s#2177.\s\sThis\scheck-in\salso\sadds\sthe\snew\stest\ncases\sthat\swere\ssuppose\sto\shave\sbeen\sadded\swith\s(3494)\sbut\swhich\swere\nmistakenly\somitted.\s(CVS\s3595) +D 2007-01-19T01:06:02 F Makefile.in 7fa74bf4359aa899da5586e394d17735f221315f F Makefile.linux-gcc 2d8574d1ba75f129aba2019f0b959db380a90935 F README 9c4e2d6706bdcc3efdd773ce752a8cdab4f90028 @@ -97,7 +97,7 @@ F src/server.c 087b92a39d883e3fa113cae259d64e4c7438bc96 F src/shell.c d13ca007cd18192c07a668aeddcdd6a9fe639be9 F src/sqlite.h.in d264fe6241fee33491b1ab90885c2f0c0d2c7e8f F src/sqlite3ext.h 011c75fd6459a61454514af07c7a4f1f5c767f27 -F src/sqliteInt.h 90dad3c0ba7a5151c48361748ccdada9ff2eff78 +F src/sqliteInt.h f15bb7b1bcf750a3202bfae85d6d3beb4e5f64e1 F src/table.c 6d0da66dde26ee75614ed8f584a1996467088d06 F src/tclsqlite.c d344c7f394d6f055ce3abfe0049b0480c5e34e56 F src/test1.c 053f5224697efaefff1f4c647fd90fdea9346cc5 @@ -129,7 +129,7 @@ F src/vdbeaux.c c5324d62f51529bccc5be3b04bac2e4eeae1569a F src/vdbefifo.c 9efb94c8c3f4c979ebd0028219483f88e57584f5 F src/vdbemem.c 26623176bf1c616aa478da958fac49502491a921 F src/vtab.c 7fbda947e28cbe7adb3ba752a76ca9ef29936750 -F src/where.c f55d4459a122457a135cf9ec859bf28777d9156f +F src/where.c 46dea18bc3b0fa2d71447bb6408a6c49e6a7c187 F tclinstaller.tcl 046e3624671962dc50f0481d7c25b38ef803eb42 F test/aggerror.test a867e273ef9e3d7919f03ef4f0e8c0d2767944f2 F test/all.test b62fcd122052efaff1b0979aefa2dd65cfc8ee52 @@ -352,6 +352,7 @@ F test/vtab_err.test 224cc80ad700797c48b9cd2c1e0bd7a8517d8609 F test/where.test 8dcc1b1a6f17b6bad2dc6a9917eafe62d4ea57eb F test/where2.test 61d5b20d9bedc8788a773bbdc5b2ef887725928e F test/where3.test 0a30fe9808b0fa01c46d0fcf4fac0bf6cf75bb30 +F test/where4.test c6b6cca0859b96f79ab47e6955fce787076e6a60 F tool/diffdb.c 7524b1b5df217c20cd0431f6789851a4e0cb191b F tool/lemon.c 2938bec507110397c937bd8a03b0c9596a709a04 F tool/lempar.c fdc1672e97f72f72e76553038501da40fec9d251 @@ -424,7 +425,7 @@ F www/tclsqlite.tcl bb0d1357328a42b1993d78573e587c6dcbc964b9 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl 890248cf7b70e60c383b0e84d77d5132b3ead42b F www/whentouse.tcl 97e2b5cd296f7d8057e11f44427dea8a4c2db513 -P 0c5c1b931dfdc163f300f458e4b305c9f50e17f8 -R 6f01158303ccfd20d2d6b3101557a041 +P d537aa5edecb5c7b84d8eb876453f385f6f3d91a +R 99965f5a2fabd1d4a2a67c894b4ff62b U drh -Z a3648b01ded082bd6cd70ae0b6771f9c +Z e72acdbefc9562f5a7ceb3d6bfdf02c8 diff --git a/manifest.uuid b/manifest.uuid index d096e60bbb..227624640f 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -d537aa5edecb5c7b84d8eb876453f385f6f3d91a \ No newline at end of file +335863e4d16113fb9ecebce35d2db043771d98b1 \ No newline at end of file diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 7a3002dcf2..a6c944f015 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -11,7 +11,7 @@ ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.532 2006/12/21 01:29:23 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.533 2007/01/19 01:06:02 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ @@ -1091,6 +1091,11 @@ typedef unsigned int Bitmask; ** is modified by an INSERT, DELETE, or UPDATE statement. In standard SQL, ** such a table must be a simple name: ID. But in SQLite, the table can ** now be identified by a database name, a dot, then the table name: ID.ID. +** +** The jointype starts out showing the join type between the current table +** and the next table on the list. The parser builds the list this way. +** But sqlite3SrcListShiftJoinType() later shifts the jointypes so that each +** jointype expresses the join between the table and the previous table. */ struct SrcList { i16 nSrc; /* Number of tables or subqueries in the FROM clause */ @@ -1102,7 +1107,7 @@ struct SrcList { Table *pTab; /* An SQL table corresponding to zName */ Select *pSelect; /* A SELECT statement used in place of a table name */ u8 isPopulated; /* Temporary table associated with SELECT is populated */ - u8 jointype; /* Type of join between this table and the next */ + u8 jointype; /* Type of join between this able and the previous */ i16 iCursor; /* The VDBE cursor number used to access this table */ Expr *pOn; /* The ON clause of a join */ IdList *pUsing; /* The USING clause of a join */ diff --git a/src/where.c b/src/where.c index a0d2f81096..83e52cacaf 100644 --- a/src/where.c +++ b/src/where.c @@ -16,7 +16,7 @@ ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** -** $Id: where.c,v 1.234 2006/12/20 03:24:19 drh Exp $ +** $Id: where.c,v 1.235 2007/01/19 01:06:03 drh Exp $ */ #include "sqliteInt.h" @@ -1275,6 +1275,7 @@ static double bestIndex( int rev; /* True to scan in reverse order */ int flags; /* Flags associated with pProbe */ int nEq; /* Number of == or IN constraints */ + int eqTermMask; /* Mask of valid equality operators */ double cost; /* Cost of using pProbe */ TRACE(("bestIndex: tbl=%s notReady=%x\n", pSrc->pTab->zName, notReady)); @@ -1366,6 +1367,17 @@ static double bestIndex( bestFlags = flags; } + /* If the pSrc table is the right table of a LEFT JOIN then we may not + ** use an index to satisfy IS NULL constraints on that table. This is + ** because columns might end up being NULL if the table does not match - + ** a circumstance which the index cannot help us discover. Ticket #2177. + */ + if( (pSrc->jointype & JT_LEFT)!=0 ){ + eqTermMask = WO_EQ|WO_IN; + }else{ + eqTermMask = WO_EQ|WO_IN|WO_ISNULL; + } + /* Look at each index. */ for(; pProbe; pProbe=pProbe->pNext){ @@ -1380,7 +1392,7 @@ static double bestIndex( flags = 0; for(i=0; inColumn; i++){ int j = pProbe->aiColumn[i]; - pTerm = findTerm(pWC, iCur, j, notReady, WO_EQ|WO_IN|WO_ISNULL, pProbe); + pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe); if( pTerm==0 ) break; flags |= WHERE_COLUMN_EQ; if( pTerm->eOperator & WO_IN ){ @@ -1636,7 +1648,8 @@ static void codeAllEqualityTerms( /* Evaluate the equality constraints */ - for(j=0; jnColumn; j++){ + assert( pIdx->nColumn>=nEq ); + for(j=0; jaiColumn[j]; pTerm = findTerm(pWC, iCur, k, notReady, WO_EQ|WO_IN|WO_ISNULL, pIdx); if( pTerm==0 ) break; @@ -1649,7 +1662,6 @@ static void codeAllEqualityTerms( sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem+j+1, 1); } } - assert( j==nEq ); /* Make sure all the constraint values are on the top of the stack */ diff --git a/test/where4.test b/test/where4.test new file mode 100644 index 0000000000..00afaa7767 --- /dev/null +++ b/test/where4.test @@ -0,0 +1,144 @@ +# 2006 October 27 +# +# 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 testing the use of indices in WHERE clauses. +# This file was created when support for optimizing IS NULL phrases +# was added. And so the principle purpose of this file is to test +# that IS NULL phrases are correctly optimized. But you can never +# have too many tests, so some other tests are thrown in as well. +# +# $Id: where4.test,v 1.1 2007/01/19 01:06:03 drh Exp $ + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +# Build some test data +# +do_test where4-1.0 { + execsql { + CREATE TABLE t1(w, x, y); + CREATE INDEX i1wxy ON t1(w,x,y); + INSERT INTO t1 VALUES(1,2,3); + INSERT INTO t1 VALUES(1,NULL,3); + INSERT INTO t1 VALUES('a','b','c'); + INSERT INTO t1 VALUES('a',NULL,'c'); + INSERT INTO t1 VALUES(X'78',x'79',x'7a'); + INSERT INTO t1 VALUES(X'78',NULL,X'7A'); + INSERT INTO t1 VALUES(NULL,NULL,NULL); + SELECT count(*) FROM t1; + } +} {7} + +# Do an SQL statement. Append the search count to the end of the result. +# +proc count sql { + set ::sqlite_search_count 0 + return [concat [execsql $sql] $::sqlite_search_count] +} + +# Verify that queries use an index. We are using the special variable +# "sqlite_search_count" which tallys the number of executions of MoveTo +# and Next operators in the VDBE. By verifing that the search count is +# small we can be assured that indices are being used properly. +# +do_test where4-1.1 { + count {SELECT rowid FROM t1 WHERE w IS NULL} +} {7 2} +do_test where4-1.2 { + count {SELECT rowid FROM t1 WHERE +w IS NULL} +} {7 6} +do_test where4-1.3 { + count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL} +} {2 2} +do_test where4-1.4 { + count {SELECT rowid FROM t1 WHERE w=1 AND +x IS NULL} +} {2 3} +do_test where4-1.5 { + count {SELECT rowid FROM t1 WHERE w=1 AND x>0} +} {1 2} +do_test where4-1.6 { + count {SELECT rowid FROM t1 WHERE w=1 AND x<9} +} {1 3} +do_test where4-1.7 { + count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y=3} +} {2 2} +do_test where4-1.8 { + count {SELECT rowid FROM t1 WHERE w=1 AND x IS NULL AND y>2} +} {2 2} +do_test where4-1.9 { + count {SELECT rowid FROM t1 WHERE w='a' AND x IS NULL AND y='c'} +} {4 2} +do_test where4-1.10 { + count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL} +} {6 2} +do_test where4-1.11 { + count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=123} +} {1} +do_test where4-1.12 { + count {SELECT rowid FROM t1 WHERE w=x'78' AND x IS NULL AND y=x'7A'} +} {6 2} +do_test where4-1.13 { + count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL} +} {7 2} +do_test where4-1.14 { + count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y IS NULL} +} {7 2} +do_test where4-1.15 { + count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y<0} +} {2} +do_test where4-1.16 { + count {SELECT rowid FROM t1 WHERE w IS NULL AND x IS NULL AND y>=0} +} {1} + +do_test where4-2.1 { + execsql {SELECT rowid FROM t1 ORDER BY w, x, y} +} {7 2 1 4 3 6 5} +do_test where4-2.2 { + execsql {SELECT rowid FROM t1 ORDER BY w DESC, x, y} +} {6 5 4 3 2 1 7} +do_test where4-2.3 { + execsql {SELECT rowid FROM t1 ORDER BY w, x DESC, y} +} {7 1 2 3 4 5 6} + + +# Ticket #2177 +# +# Suppose you have a left join where the right table of the left +# join (the one that can be NULL) has an index on two columns. +# The first indexed column is used in the ON clause of the join. +# The second indexed column is used in the WHERE clause with an IS NULL +# constraint. It is not allowed to use the IS NULL optimization to +# optimize the query because the second column might be NULL because +# the right table did not match - something the index does not know +# about. +# +do_test where4-3.1 { + execsql { + CREATE TABLE t2(a); + INSERT INTO t2 VALUES(1); + INSERT INTO t2 VALUES(2); + INSERT INTO t2 VALUES(3); + CREATE TABLE t3(x,y,UNIQUE(x,y)); + INSERT INTO t3 VALUES(1,11); + INSERT INTO t3 VALUES(2,NULL); + + SELECT * FROM t2 LEFT JOIN t3 ON a=x WHERE +y IS NULL; + } +} {2 2 {} 3 {} {}} +do_test where4-3.2 { + execsql { + SELECT * FROM t2 LEFT JOIN t3 ON a=x WHERE y IS NULL; + } +} {2 2 {} 3 {} {}} + +integrity_check {where4-99.0} + +finish_test -- 2.47.2