SQLite

Check-in [57eb2abd5b]
Login

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: 57eb2abd5b270d65be5e0f138f0d46899fa6091df3ba20b0ea7ef04244a15d48
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
Unified Diff Ignore Whitespace Patch
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
){
  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
5793
5794
5795
5796
5797
5798
5799
5800
5801
5802
5803
5804
5805
5806
5807
5808
5809
5810
5811
5812
5813
    ** 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)
    ){







<
<
<
<
<
<
<
<
<
<
<
<
<
<







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