Index: src/expr.c ================================================================== --- src/expr.c +++ src/expr.c @@ -4998,10 +4998,62 @@ testcase( pX!=pE1->pLeft ); if( sqlite3ExprCompare(pParse, pX, pE2->pLeft, iTab)==0 ) return 1; } return 0; } + +/* +** This is the Expr node callback for sqlite3ExprImpliesNotNullRow(). +** If the expression node requires that the table at pWalker->iCur +** have a non-NULL column, then set pWalker->eCode to 1 and abort. +*/ +static int impliesNotNullRow(Walker *pWalker, Expr *pExpr){ + if( ExprHasProperty(pExpr, EP_FromJoin) ) return WRC_Prune; + switch( pExpr->op ){ + case TK_ISNULL: + case TK_IS: + case TK_OR: + case TK_FUNCTION: + case TK_AGG_FUNCTION: + return WRC_Prune; + case TK_COLUMN: + case TK_AGG_COLUMN: + if( pWalker->u.iCur==pExpr->iTable ){ + pWalker->eCode = 1; + return WRC_Abort; + } + return WRC_Prune; + default: + return WRC_Continue; + } +} + +/* +** Return true (non-zero) if expression p can only be true if at least +** one column of table iTab is non-null. In other words, return true +** if expression p will always be NULL or false if every column of iTab +** is NULL. +** +** Terms of p that are marked with EP_FromJoin (and hence that come from +** the ON or USING clauses of LEFT JOINS) are excluded from the analysis. +** +** This routine is used to check if a LEFT JOIN can be converted into +** an ordinary JOIN. The p argument is the WHERE clause. If the WHERE +** clause requires that some column of the right table of the LEFT JOIN +** be non-NULL, then the LEFT JOIN can be safely converted into an +** ordinary join. +*/ +int sqlite3ExprImpliesNonNullRow(Expr *p, int iTab){ + Walker w; + w.xExprCallback = impliesNotNullRow; + w.xSelectCallback = 0; + w.xSelectCallback2 = 0; + w.eCode = 0; + w.u.iCur = iTab; + sqlite3WalkExpr(&w, p); + return w.eCode; +} /* ** An instance of the following structure is used by the tree walker ** to determine if an expression can be evaluated by reference to the ** index only, without having to do a search for the corresponding Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -379,10 +379,33 @@ } setJoinExpr(p->pLeft, iTable); p = p->pRight; } } + +/* Undo the work of setJoinExpr(). In the expression tree p, convert every +** term that is marked with EP_FromJoin and iRightJoinTable==iTable into +** an ordinary term that omits the EP_FromJoin mark. +** +** This happens when a LEFT JOIN is simplified into an ordinary JOIN. +*/ +static void unsetJoinExpr(Expr *p, int iTable){ + while( p ){ + if( ExprHasProperty(p, EP_FromJoin) + && (iTable<0 || p->iRightJoinTable==iTable) ){ + ExprClearProperty(p, EP_FromJoin); + } + if( p->op==TK_FUNCTION && p->x.pList ){ + int i; + for(i=0; ix.pList->nExpr; i++){ + unsetJoinExpr(p->x.pList->a[i].pExpr, iTable); + } + } + unsetJoinExpr(p->pLeft, iTable); + p = p->pRight; + } +} /* ** This routine processes the join information for a SELECT statement. ** ON and USING clauses are converted into extra terms of the WHERE clause. ** NATURAL joins also create extra WHERE clause terms. @@ -3832,16 +3855,25 @@ ** (2) The inner query is the recursive part of a common table expression. ** ** (3) The inner query has a LIMIT clause (since the changes to the WHERE ** close would change the meaning of the LIMIT). ** -** (4) The inner query is the right operand of a LEFT JOIN. (The caller -** enforces this restriction since this routine does not have enough -** information to know.) +** (4) (** This restriction was removed on 2018-03-21. It used to read: +** The inner query is the right operand of a LEFT JOIN. **) ** ** (5) The WHERE clause expression originates in the ON or USING clause -** of a LEFT JOIN. +** of a LEFT JOIN where iCursor is not the right-hand table of that +** left join. An example: +** +** SELECT * +** FROM (SELECT 1 AS a1 UNION ALL SELECT 2) AS aa +** JOIN (SELECT 1 AS b2 UNION ALL SELECT 2) AS bb ON (a1=b2) +** LEFT JOIN (SELECT 8 AS c3 UNION ALL SELECT 9) AS cc ON (b2=2); +** +** The correct answer is three rows: (1,1,NULL),(2,2,8),(2,2,9). +** But if the (b2=2) term were to be pushed down into the bb subquery, +** then the (1,1,NULL) row would be suppressed. ** ** Return 0 if no changes are made and non-zero if one or more WHERE clause ** terms are duplicated into the subquery. */ static int pushDownWhereTerms( @@ -3873,16 +3905,19 @@ } while( pWhere->op==TK_AND ){ nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor); pWhere = pWhere->pLeft; } - if( ExprHasProperty(pWhere,EP_FromJoin) ) return 0; /* restriction (5) */ + if( ExprHasProperty(pWhere,EP_FromJoin) && pWhere->iRightJoinTable!=iCursor ){ + return 0; /* restriction (5) */ + } if( sqlite3ExprIsTableConstant(pWhere, iCursor) ){ nChng++; while( pSubq ){ SubstContext x; pNew = sqlite3ExprDup(pParse->db, pWhere, 0); + unsetJoinExpr(pNew, -1); x.pParse = pParse; x.iTable = iCursor; x.iNewTable = iCursor; x.isLeftJoin = 0; x.pEList = pSubq->pEList; @@ -5173,17 +5208,33 @@ if( v==0 ) goto select_end; if( pDest->eDest==SRT_Output ){ generateColumnNames(pParse, p); } - /* Try to flatten subqueries in the FROM clause up into the main query + /* Try to various optimizations (flattening subqueries, and strength + ** reduction of join operators) in the FROM clause up into the main query */ #if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) for(i=0; !p->pPrior && inSrc; i++){ struct SrcList_item *pItem = &pTabList->a[i]; Select *pSub = pItem->pSelect; Table *pTab = pItem->pTab; + + /* Convert LEFT JOIN into JOIN if there are terms of the right table + ** of the LEFT JOIN used in the WHERE clause. + */ + if( (pItem->fg.jointype & JT_LEFT)!=0 + && sqlite3ExprImpliesNonNullRow(p->pWhere, pItem->iCursor) + && OptimizationEnabled(db, SQLITE_SimplifyJoin) + ){ + SELECTTRACE(0x100,pParse,p, + ("LEFT-JOIN simplifies to JOIN on term %d\n",i)); + pItem->fg.jointype &= ~(JT_LEFT|JT_OUTER); + unsetJoinExpr(p->pWhere, pItem->iCursor); + } + + /* No futher action if this term of the FROM clause is no a subquery */ if( pSub==0 ) continue; /* Catch mismatch in the declared columns of a view and the number of ** columns in the SELECT on the RHS */ if( pTab->nCol!=pSub->pEList->nExpr ){ @@ -5320,12 +5371,11 @@ pParse->nHeight += sqlite3SelectExprHeight(p); /* Make copies of constant WHERE-clause terms in the outer query down ** inside the subquery. This can help the subquery to run more efficiently. */ - if( (pItem->fg.jointype & JT_OUTER)==0 - && OptimizationEnabled(db, SQLITE_PushDown) + if( OptimizationEnabled(db, SQLITE_PushDown) && pushDownWhereTerms(pParse, pSub, p->pWhere, pItem->iCursor) ){ #if SELECTTRACE_ENABLED if( sqlite3SelectTrace & 0x100 ){ SELECTTRACE(0x100,pParse,p,("After WHERE-clause push-down:\n")); Index: src/sqliteInt.h ================================================================== --- src/sqliteInt.h +++ src/sqliteInt.h @@ -1531,10 +1531,11 @@ #define SQLITE_CountOfView 0x0200 /* The count-of-view optimization */ #define SQLITE_CursorHints 0x0400 /* Add OP_CursorHint opcodes */ #define SQLITE_Stat34 0x0800 /* Use STAT3 or STAT4 data */ /* TH3 expects the Stat34 ^^^^^^ value to be 0x0800. Don't change it */ #define SQLITE_PushDown 0x1000 /* The push-down optimization */ +#define SQLITE_SimplifyJoin 0x2000 /* Convert LEFT JOIN to JOIN */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ @@ -3821,10 +3822,11 @@ char *sqlite3NameFromToken(sqlite3*, Token*); int sqlite3ExprCompare(Parse*,Expr*, Expr*, int); int sqlite3ExprCompareSkip(Expr*, Expr*, int); int sqlite3ExprListCompare(ExprList*, ExprList*, int); int sqlite3ExprImpliesExpr(Parse*,Expr*, Expr*, int); +int sqlite3ExprImpliesNonNullRow(Expr*,int); void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*); void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*); int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx); int sqlite3FunctionUsesThisSrc(Expr*, SrcList*); Vdbe *sqlite3GetVdbe(Parse*); Index: test/cursorhint2.test ================================================================== --- test/cursorhint2.test +++ test/cursorhint2.test @@ -134,49 +134,54 @@ 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]))} -} - -ifcapable !icu { - # This test only works using the built-in LIKE, not the ICU LIKE extension. - 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]))} - } -} - +if {0} { + # These tests no longer work due to the LEFT-JOIN strength reduction + # optimization + do_extract_hints_test 2.6 { + SELECT * FROM x1 CROSS 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]))} + } + + ifcapable !icu { + # This test only works using the built-in LIKE, not the ICU LIKE extension. + 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.12 { SELECT * FROM x1 LEFT JOIN x2 ON (a=x) WHERE coalesce(x2.b, 1) } { x2 {EQ(c0,r[2])} } Index: test/e_select.test ================================================================== --- test/e_select.test +++ test/e_select.test @@ -746,11 +746,11 @@ do_execsql_test e_select-3.2.1a { SELECT k FROM x1 LEFT JOIN x2 USING(k) } {1 2 3 4 5 6} do_execsql_test e_select-3.2.1b { - SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k + SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k ORDER BY +k } {1 3 5} do_execsql_test e_select-3.2.2 { SELECT k FROM x1 LEFT JOIN x2 USING(k) WHERE x2.k IS NULL } {2 4 6} Index: test/join2.test ================================================================== --- test/join2.test +++ test/join2.test @@ -84,11 +84,11 @@ INSERT INTO bb VALUES('one'); INSERT INTO cc VALUES('one'); } do_catchsql_test 2.1 { - SELECT * FROM aa LEFT JOIN cc ON (a=b) JOIN bb ON (b=c); + SELECT * FROM aa LEFT JOIN cc ON (a=b) JOIN bb ON (b=coalesce(c,1)); } {1 {ON clause references tables to its right}} do_catchsql_test 2.2 { SELECT * FROM aa JOIN cc ON (a=b) JOIN bb ON (b=c); } {0 {one one one}}