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 | SQL 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 |
Context
|
2018-07-26
| ||
| 23:54 | Add a test case demonstrating the collation problem with constant propagation. check-in: 50add839 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: 57eb2abd user: drh tags: propagate-const-opt | |
| 21:16 | Initial implementation of the WHERE-clause constant propagation optimization. check-in: 2fb82ad8 user: drh tags: propagate-const-opt | |
Changes
Changes to src/expr.c.
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( 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;
|
| |
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 .... 5721 5722 5723 5724 5725 5726 5727 5728 5729 5730 5731 5732 5733 5734 .... 5786 5787 5788 5789 5790 5791 5792 5793 5794 5795 5796 5797 5798 5799 5800 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 |
){
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
................................................................................
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];
................................................................................
** 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);
/* 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"));
}
/* 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)
){
|
> > > > > > > > > > > > > > > < < < < < < < < < < < < < < |
4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 .... 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 .... 5801 5802 5803 5804 5805 5806 5807 5808 5809 5810 5811 5812 5813 5814 |
){
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
................................................................................
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];
................................................................................
** 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 |