Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch join-strength-reduction Excluding Merge-Ins
This is equivalent to a diff from 4661ac81 to b5d3dd8c
2018-03-22
| ||
12:00 | Add the left join strength reduction optimization. Enhance the push-down optimization so that it works with many LEFT JOINs. (check-in: dd568c27 user: drh tags: trunk) | |
2018-03-21
| ||
19:25 | Add the optfuzz.c program for verifying the query planner using a fuzzer. This is an initial code check-in. (check-in: 3fb21251 user: drh tags: trunk) | |
01:59 | Relax LEFT-JOIN restrictions on the push-down optimization. (Closed-Leaf check-in: b5d3dd8c user: drh tags: join-strength-reduction) | |
2018-03-20
| ||
22:52 | Do a more thorough job of cleaning traces of the strength-reduced LEFT JOIN. (check-in: 08833dda user: drh tags: join-strength-reduction) | |
21:16 | If terms of the WHERE clause require that the right table in a LEFT JOIN not be a null row, then simplify the LEFT JOIN into an ordinary JOIN. (check-in: 5b7abecc user: drh tags: join-strength-reduction) | |
19:02 | Fix incorrect testcase labels on two cases in join5.test. No changes to code. (check-in: 4661ac81 user: drh tags: trunk) | |
18:08 | Improvements to the HAVING-to-WHERE optimization. The code uses less space and less CPU, and there is now ".selecttrace" output. (check-in: 5ad668d4 user: drh tags: trunk) | |
Changes to src/expr.c.
︙ | ︙ | |||
4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 | if( pE2->op==TK_NOTNULL && pE1->op!=TK_ISNULL && pE1->op!=TK_IS ){ Expr *pX = sqlite3ExprSkipCollate(pE1->pLeft); testcase( pX!=pE1->pLeft ); if( sqlite3ExprCompare(pParse, pX, pE2->pLeft, iTab)==0 ) return 1; } return 0; } /* ** 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 ** table entry. The IdxCover.pIdx field is the index. IdxCover.iCur ** is the cursor for the table. | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 5016 5017 5018 5019 5020 5021 5022 5023 5024 5025 5026 5027 5028 5029 5030 5031 5032 5033 5034 5035 5036 5037 5038 5039 5040 5041 5042 5043 5044 5045 5046 5047 5048 5049 5050 5051 5052 5053 5054 5055 5056 5057 5058 5059 5060 5061 | if( pE2->op==TK_NOTNULL && pE1->op!=TK_ISNULL && pE1->op!=TK_IS ){ Expr *pX = sqlite3ExprSkipCollate(pE1->pLeft); 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 ** table entry. The IdxCover.pIdx field is the index. IdxCover.iCur ** is the cursor for the table. |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
377 378 379 380 381 382 383 384 385 386 387 388 389 390 | setJoinExpr(p->x.pList->a[i].pExpr, iTable); } } setJoinExpr(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. ** ** The terms of a FROM clause are contained in the Select.pSrc structure. | > > > > > > > > > > > > > > > > > > > > > > > | 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 | setJoinExpr(p->x.pList->a[i].pExpr, iTable); } } 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; i<p->x.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. ** ** The terms of a FROM clause are contained in the Select.pSrc structure. |
︙ | ︙ | |||
3830 3831 3832 3833 3834 3835 3836 | ** to suppress it. **) ** ** (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). ** | > | < < | > > > > > > > > > > | 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 | ** to suppress it. **) ** ** (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) (** 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 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( Parse *pParse, /* Parse context (for malloc() and error reporting) */ Select *pSubq, /* The subquery whose WHERE clause is to be augmented */ |
︙ | ︙ | |||
3871 3872 3873 3874 3875 3876 3877 | if( pSubq->pLimit!=0 ){ return 0; /* restriction (3) */ } while( pWhere->op==TK_AND ){ nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor); pWhere = pWhere->pLeft; } | | > > > | 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 | if( pSubq->pLimit!=0 ){ return 0; /* restriction (3) */ } while( pWhere->op==TK_AND ){ nChng += pushDownWhereTerms(pParse, pSubq, pWhere->pRight, iCursor); pWhere = pWhere->pLeft; } 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; pNew = substExpr(&x, pNew); if( pSubq->selFlags & SF_Aggregate ){ |
︙ | ︙ | |||
5171 5172 5173 5174 5175 5176 5177 | ** does not already exist */ v = sqlite3GetVdbe(pParse); if( v==0 ) goto select_end; if( pDest->eDest==SRT_Output ){ generateColumnNames(pParse, p); } | > | > > > > > > > > > > > > > > > | 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 5218 5219 5220 5221 5222 5223 5224 5225 5226 5227 5228 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 | ** does not already exist */ v = sqlite3GetVdbe(pParse); if( v==0 ) goto select_end; if( pDest->eDest==SRT_Output ){ generateColumnNames(pParse, p); } /* 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 && i<pTabList->nSrc; 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 ){ sqlite3ErrorMsg(pParse, "expected %d columns for '%s' but got %d", pTab->nCol, pTab->zName, pSub->pEList->nExpr); |
︙ | ︙ | |||
5318 5319 5320 5321 5322 5323 5324 | ** an exact limit. */ 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. */ | < | | 5369 5370 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 | ** an exact limit. */ 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( 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")); sqlite3TreeViewSelect(0, p, 0); } |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 | #define SQLITE_Transitive 0x0080 /* Transitive constraints */ #define SQLITE_OmitNoopJoin 0x0100 /* Omit unused tables in joins */ #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_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0) #define OptimizationEnabled(db, mask) (((db)->dbOptFlags&(mask))==0) | > | 1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 | #define SQLITE_Transitive 0x0080 /* Transitive constraints */ #define SQLITE_OmitNoopJoin 0x0100 /* Omit unused tables in joins */ #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. */ #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0) #define OptimizationEnabled(db, mask) (((db)->dbOptFlags&(mask))==0) |
︙ | ︙ | |||
3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 | void sqlite3Vacuum(Parse*,Token*); int sqlite3RunVacuum(char**, sqlite3*, int); 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); void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*); void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*); int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx); int sqlite3FunctionUsesThisSrc(Expr*, SrcList*); Vdbe *sqlite3GetVdbe(Parse*); #ifndef SQLITE_UNTESTABLE void sqlite3PrngSaveState(void); | > | 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 | void sqlite3Vacuum(Parse*,Token*); int sqlite3RunVacuum(char**, sqlite3*, int); 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*); #ifndef SQLITE_UNTESTABLE void sqlite3PrngSaveState(void); |
︙ | ︙ |
Changes to test/cursorhint2.test.
︙ | ︙ | |||
132 133 134 135 136 137 138 | 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])} } | > > > | | | | | | | | | | | | | | | | | | | | > | | | | | | | | | | | | | | | | | | | > | 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 | 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])} } 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])} } finish_test |
Changes to test/e_select.test.
︙ | ︙ | |||
744 745 746 747 748 749 750 | do_execsql_test e_select-3.1.5 { SELECT k FROM x1 WHERE x IS NULL } {4 5} do_execsql_test e_select-3.1.6 { SELECT k FROM x1 WHERE z - 78.43 } {2 4 6} 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 { | | | 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 | do_execsql_test e_select-3.1.5 { SELECT k FROM x1 WHERE x IS NULL } {4 5} do_execsql_test e_select-3.1.6 { SELECT k FROM x1 WHERE z - 78.43 } {2 4 6} 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 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} do_execsql_test e_select-3.2.3 { SELECT k FROM x1 NATURAL JOIN x2 WHERE x2.k |
︙ | ︙ |
Changes to test/join2.test.
︙ | ︙ | |||
82 83 84 85 86 87 88 | CREATE TABLE cc(c); INSERT INTO aa VALUES('one'); INSERT INTO bb VALUES('one'); INSERT INTO cc VALUES('one'); } do_catchsql_test 2.1 { | | | 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | CREATE TABLE cc(c); INSERT INTO aa VALUES('one'); 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=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}} #------------------------------------------------------------------------- # Test that a problem causing where.c to overlook opportunities to |
︙ | ︙ |