Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Generalize the constant propagation optimization so that it applies on every WHERE close, not just those that contain a subquery. This then demonstrates that the current implementation is inadequate since it does not take into account collating sequences. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | propagate-const-opt |
Files: | files | file ages | folders |
SHA3-256: |
57eb2abd5b270d65be5e0f138f0d4689 |
User & Date: | drh 2018-07-26 23:47:11.108 |
Context
2018-07-26
| ||
23:54 | Add a test case demonstrating the collation problem with constant propagation. (check-in: 50add839fd user: drh tags: propagate-const-opt) | |
23:47 | Generalize the constant propagation optimization so that it applies on every WHERE close, not just those that contain a subquery. This then demonstrates that the current implementation is inadequate since it does not take into account collating sequences. (check-in: 57eb2abd5b user: drh tags: propagate-const-opt) | |
21:16 | Initial implementation of the WHERE-clause constant propagation optimization. (check-in: 2fb82ad8eb user: drh tags: propagate-const-opt) | |
Changes
Changes to src/expr.c.
︙ | ︙ | |||
4931 4932 4933 4934 4935 4936 4937 | return 2; } if( pA->op!=TK_COLUMN && pA->op!=TK_AGG_COLUMN && pA->u.zToken ){ if( pA->op==TK_FUNCTION ){ if( sqlite3StrICmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; }else if( pA->op==TK_COLLATE ){ if( sqlite3_stricmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; | | | 4931 4932 4933 4934 4935 4936 4937 4938 4939 4940 4941 4942 4943 4944 4945 | return 2; } if( pA->op!=TK_COLUMN && pA->op!=TK_AGG_COLUMN && pA->u.zToken ){ if( pA->op==TK_FUNCTION ){ if( sqlite3StrICmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; }else if( pA->op==TK_COLLATE ){ if( sqlite3_stricmp(pA->u.zToken,pB->u.zToken)!=0 ) return 2; }else if( pA->op!=TK_UPLUS && strcmp(pA->u.zToken,pB->u.zToken)!=0 ){ return 2; } } if( (pA->flags & EP_Distinct)!=(pB->flags & EP_Distinct) ) return 2; if( ALWAYS((combinedFlags & EP_TokenOnly)==0) ){ if( combinedFlags & EP_xIsSelect ) return 2; if( sqlite3ExprCompare(pParse, pA->pLeft, pB->pLeft, iTab) ) return 2; |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 | ){ pConst->nConst++; pConst->apExpr = sqlite3DbReallocOrFree(pConst->db, pConst->apExpr, pConst->nConst*2*sizeof(Expr*)); if( pConst->apExpr==0 ){ pConst->nConst = 0; }else{ pConst->apExpr[pConst->nConst*2-2] = pColumn; pConst->apExpr[pConst->nConst*2-1] = pValue; } } /* ** Find all instances of COLUMN=CONSTANT or CONSTANT=COLUMN in pExpr that | > | 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 | ){ pConst->nConst++; pConst->apExpr = sqlite3DbReallocOrFree(pConst->db, pConst->apExpr, pConst->nConst*2*sizeof(Expr*)); if( pConst->apExpr==0 ){ pConst->nConst = 0; }else{ while( pValue->op==TK_UPLUS ) pValue = pValue->pLeft; pConst->apExpr[pConst->nConst*2-2] = pColumn; pConst->apExpr[pConst->nConst*2-1] = pValue; } } /* ** Find all instances of COLUMN=CONSTANT or CONSTANT=COLUMN in pExpr that |
︙ | ︙ | |||
5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 | sqlite3TreeViewSelect(0, p, 0); } #endif if( p->pNext==0 ) ExplainQueryPlanPop(pParse); return rc; } #endif /* For each term in the FROM clause, do two things: ** (1) Authorized unreferenced tables ** (2) Generate code for all sub-queries */ for(i=0; i<pTabList->nSrc; i++){ struct SrcList_item *pItem = &pTabList->a[i]; | > > > > > > > > > > > > > > | 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 5735 5736 5737 5738 5739 5740 5741 5742 5743 5744 5745 5746 5747 5748 5749 | sqlite3TreeViewSelect(0, p, 0); } #endif if( p->pNext==0 ) ExplainQueryPlanPop(pParse); return rc; } #endif /* Do the constant propagation optimization */ if( OptimizationEnabled(db, SQLITE_PropagateConst) && propagateConstants(pParse, p) ){ #if SELECTTRACE_ENABLED if( sqlite3SelectTrace & 0x100 ){ SELECTTRACE(0x100,pParse,p,("After constant propagation:\n")); sqlite3TreeViewSelect(0, p, 0); } #endif }else{ SELECTTRACE(0x100,pParse,p,("Constant propagation not possible\n")); } /* For each term in the FROM clause, do two things: ** (1) Authorized unreferenced tables ** (2) Generate code for all sub-queries */ for(i=0; i<pTabList->nSrc; i++){ struct SrcList_item *pItem = &pTabList->a[i]; |
︙ | ︙ | |||
5786 5787 5788 5789 5790 5791 5792 | ** may contain expression trees of at most ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit ** more conservative than necessary, but much easier than enforcing ** an exact limit. */ pParse->nHeight += sqlite3SelectExprHeight(p); | < < < < < < < < < < < < < < | 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 | ** may contain expression trees of at most ** (SQLITE_MAX_EXPR_DEPTH-Parse.nHeight) height. This is a bit ** more conservative than necessary, but much easier than enforcing ** 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, (pItem->fg.jointype & JT_OUTER)!=0) ){ |
︙ | ︙ |
Changes to test/whereL.test.
︙ | ︙ | |||
31 32 33 34 35 36 37 38 39 | | |--LEFT-MOST SUBQUERY | | `--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?) | `--UNION ALL | `--SEARCH TABLE t3 USING INDEX sqlite_autoindex_t3_1 (a=?) |--SCAN SUBQUERY xxxxxx `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?) } finish_test | > > > > > > > > > > > > > > > | 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | | |--LEFT-MOST SUBQUERY | | `--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?) | `--UNION ALL | `--SEARCH TABLE t3 USING INDEX sqlite_autoindex_t3_1 (a=?) |--SCAN SUBQUERY xxxxxx `--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?) } # The scan of the t1 table goes first since that enables the ORDER BY # sort to be omitted. This would not be possible without constant # propagation because without it the t1 table would depend on t3. # do_eqp_test 120 { SELECT * FROM t1, t2, t3 WHERE t1.a=t2.a AND t2.a=t3.j AND t3.j=5 ORDER BY t1.a; } { QUERY PLAN |--SEARCH TABLE t1 USING INDEX sqlite_autoindex_t1_1 (a=?) |--SEARCH TABLE t2 USING INDEX sqlite_autoindex_t2_1 (a=?) `--SCAN TABLE t3 } finish_test |