SQLite

Check-in [be8e3fc70e]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Split FROM-clause subquery flattening and code generation into separate loops.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | view-optimization
Files: files | file ages | folders
SHA1: be8e3fc70e4c13b28b07985df3457960f58ffddd
User & Date: drh 2015-06-05 22:33:39.408
Context
2015-06-06
00:18
Minor cleanup of the sqlite3Select() procedure. (check-in: f4c90d06bb user: drh tags: view-optimization)
2015-06-05
22:33
Split FROM-clause subquery flattening and code generation into separate loops. (check-in: be8e3fc70e user: drh tags: view-optimization)
20:27
Provide one final Select tree dump prior to WHERE clause analysis when ".selecttrace 0x400" tracing bit is set with SELECTTRACE_ENABLED. Analysis and debug changes only - normal builds are unaffected. (check-in: 283bf0b64d user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/expr.c.
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
  if( zLabel==0 || zLabel[0]==0 ) zLabel = "LIST";
  if( pList==0 ){
    sqlite3TreeViewLine(pView, "%s (empty)", zLabel);
  }else{
    sqlite3TreeViewLine(pView, "%s", zLabel);
    for(i=0; i<pList->nExpr; i++){
      sqlite3TreeViewExpr(pView, pList->a[i].pExpr, i<pList->nExpr-1);
#if 0
     if( pList->a[i].zName ){
        sqlite3ExplainPrintf(pOut, " AS %s", pList->a[i].zName);
      }
      if( pList->a[i].bSpanIsTab ){
        sqlite3ExplainPrintf(pOut, " (%s)", pList->a[i].zSpan);
      }
#endif
    }
  }
  sqlite3TreeViewPop(pView);
}
#endif /* SQLITE_DEBUG */

/*







<
<
<
<
<
<
<
<







3555
3556
3557
3558
3559
3560
3561








3562
3563
3564
3565
3566
3567
3568
  if( zLabel==0 || zLabel[0]==0 ) zLabel = "LIST";
  if( pList==0 ){
    sqlite3TreeViewLine(pView, "%s (empty)", zLabel);
  }else{
    sqlite3TreeViewLine(pView, "%s", zLabel);
    for(i=0; i<pList->nExpr; i++){
      sqlite3TreeViewExpr(pView, pList->a[i].pExpr, i<pList->nExpr-1);








    }
  }
  sqlite3TreeViewPop(pView);
}
#endif /* SQLITE_DEBUG */

/*
Changes to src/select.c.
4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849
4850
4851
4852









































4853
4854
4855
4856
4857
4858
4859
  */
#ifndef SQLITE_OMIT_SUBQUERY
  if( checkForMultiColumnSelectError(pParse, pDest, pEList->nExpr) ){
    goto select_end;
  }
#endif

  /* Generate code for all sub-queries in the FROM clause
  */
#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];
    SelectDest dest;
    Select *pSub = pItem->pSelect;
    int isAggSub;










































    if( pSub==0 ) continue;

    /* Sometimes the code for a subquery will be generated more than
    ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
    ** for example.  In that case, do not regenerate the code to manifest
    ** a view or the co-routine to implement a view.  The first instance







|




<


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







4838
4839
4840
4841
4842
4843
4844
4845
4846
4847
4848
4849

4850
4851
4852
4853
4854
4855
4856
4857
4858
4859
4860
4861
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
  */
#ifndef SQLITE_OMIT_SUBQUERY
  if( checkForMultiColumnSelectError(pParse, pDest, pEList->nExpr) ){
    goto select_end;
  }
#endif

  /* Try to flatten subqueries in the FROM clause 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;
    int isAggSub;
    if( pSub==0 ) continue;
    isAggSub = (pSub->selFlags & SF_Aggregate)!=0;
    if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
      /* This subquery can be absorbed into its parent. */
      if( isAggSub ){
        isAgg = 1;
        p->selFlags |= SF_Aggregate;
      }
      i = -1;
    }
    pTabList = p->pSrc;
    if( db->mallocFailed ) goto select_end;
    if( !IgnorableOrderby(pDest) ){
      sSort.pOrderBy = p->pOrderBy;
    }
  }
#endif


#ifndef SQLITE_OMIT_COMPOUND_SELECT
  /* Handle compound SELECT statements using the separate multiSelect()
  ** procedure.
  */
  if( p->pPrior ){
    rc = multiSelect(pParse, p, pDest);
    explainSetInteger(pParse->iSelectId, iRestoreSelectId);
#if SELECTTRACE_ENABLED
    SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
    pParse->nSelectIndent--;
#endif
    return rc;
  }
#endif

  /* Generate code for all sub-queries in the FROM clause
  */
#if !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW)
  for(i=0; i<pTabList->nSrc; i++){
    struct SrcList_item *pItem = &pTabList->a[i];
    SelectDest dest;
    Select *pSub = pItem->pSelect;

    if( pSub==0 ) continue;

    /* Sometimes the code for a subquery will be generated more than
    ** once, if the subquery is part of the WHERE clause in a LEFT JOIN,
    ** for example.  In that case, do not regenerate the code to manifest
    ** a view or the co-routine to implement a view.  The first instance
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
4891
4892
4893
4894
4895
4896
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
4976
4977
4978
4979
4980
4981
4982
4983
4984
4985
4986
4987
4988
4989
4990
4991
4992
    ** 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);

    isAggSub = (pSub->selFlags & SF_Aggregate)!=0;
    if( flattenSubquery(pParse, p, i, isAgg, isAggSub) ){
      /* This subquery can be absorbed into its parent. */
      if( isAggSub ){
        isAgg = 1;
        p->selFlags |= SF_Aggregate;
      }
      i = -1;
    }else{
      if( (pItem->jointype & JT_OUTER)==0
       && pushDownWhereTerms(db, 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);
        }
#endif
      }
      if( pTabList->nSrc==1
       && (p->selFlags & SF_All)==0
       && OptimizationEnabled(db, SQLITE_SubqCoroutine)
      ){
        /* Implement a co-routine that will return a single row of the result
        ** set on each invocation.
        */
        int addrTop = sqlite3VdbeCurrentAddr(v)+1;
        pItem->regReturn = ++pParse->nMem;
        sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
        VdbeComment((v, "%s", pItem->pTab->zName));
        pItem->addrFillSub = addrTop;
        sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
        explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
        sqlite3Select(pParse, pSub, &dest);
        pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
        pItem->viaCoroutine = 1;
        pItem->regResult = dest.iSdst;
        sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);
        sqlite3VdbeJumpHere(v, addrTop-1);
        sqlite3ClearTempRegCache(pParse);
      }else{
        /* Generate a subroutine that will fill an ephemeral table with
        ** the content of this subquery.  pItem->addrFillSub will point
        ** to the address of the generated subroutine.  pItem->regReturn
        ** is a register allocated to hold the subroutine return address
        */
        int topAddr;
        int onceAddr = 0;
        int retAddr;
        assert( pItem->addrFillSub==0 );
        pItem->regReturn = ++pParse->nMem;
        topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
        pItem->addrFillSub = topAddr+1;
        if( pItem->isCorrelated==0 ){
          /* If the subquery is not correlated and if we are not inside of
          ** a trigger, then we only need to compute the value of the subquery
          ** once. */
          onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);
          VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
        }else{
          VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
        }
        sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
        explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
        sqlite3Select(pParse, pSub, &dest);
        pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
        if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
        retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
        VdbeComment((v, "end %s", pItem->pTab->zName));
        sqlite3VdbeChangeP1(v, topAddr, retAddr);
        sqlite3ClearTempRegCache(pParse);
      }
    }
    if( db->mallocFailed ){
      goto select_end;
    }
    pParse->nHeight -= sqlite3SelectExprHeight(p);
    pTabList = p->pSrc;
    if( !IgnorableOrderby(pDest) ){
      sSort.pOrderBy = p->pOrderBy;
    }
  }
  pEList = p->pEList;
#endif
  pWhere = p->pWhere;
  pGroupBy = p->pGroupBy;
  pHaving = p->pHaving;
  sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;

#if SELECTTRACE_ENABLED
  if( sqlite3SelectTrace & 0x400 ){
    SELECTTRACE(0x400,pParse,p,("After all FROM-clause analysis:\n"));
    sqlite3TreeViewSelect(0, p, 0);
  }
#endif

#ifndef SQLITE_OMIT_COMPOUND_SELECT
  /* If there is are a sequence of queries, do the earlier ones first.
  */
  if( p->pPrior ){
    rc = multiSelect(pParse, p, pDest);
    explainSetInteger(pParse->iSelectId, iRestoreSelectId);
#if SELECTTRACE_ENABLED
    SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
    pParse->nSelectIndent--;
#endif
    return rc;
  }
#endif

  /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  ** if the select-list is the same as the ORDER BY list, then this query
  ** can be rewritten as a GROUP BY. In other words, this:
  **
  **     SELECT DISTINCT xyz FROM ... ORDER BY xyz







<
<
<
<
<
<
<
<
<
|
|
|

|
|
|
|

|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
<





<
<
<
<













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







4911
4912
4913
4914
4915
4916
4917









4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
4976
4977
4978
4979

4980
4981
4982
4983
4984




4985
4986
4987
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997














4998
4999
5000
5001
5002
5003
5004
    ** 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);










    if( (pItem->jointype & JT_OUTER)==0
     && pushDownWhereTerms(db, 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);
      }
#endif
    }
    if( pTabList->nSrc==1
     && (p->selFlags & SF_All)==0
     && OptimizationEnabled(db, SQLITE_SubqCoroutine)
    ){
      /* Implement a co-routine that will return a single row of the result
      ** set on each invocation.
      */
      int addrTop = sqlite3VdbeCurrentAddr(v)+1;
      pItem->regReturn = ++pParse->nMem;
      sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
      VdbeComment((v, "%s", pItem->pTab->zName));
      pItem->addrFillSub = addrTop;
      sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);
      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
      pItem->viaCoroutine = 1;
      pItem->regResult = dest.iSdst;
      sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);
      sqlite3VdbeJumpHere(v, addrTop-1);
      sqlite3ClearTempRegCache(pParse);
    }else{
      /* Generate a subroutine that will fill an ephemeral table with
      ** the content of this subquery.  pItem->addrFillSub will point
      ** to the address of the generated subroutine.  pItem->regReturn
      ** is a register allocated to hold the subroutine return address
      */
      int topAddr;
      int onceAddr = 0;
      int retAddr;
      assert( pItem->addrFillSub==0 );
      pItem->regReturn = ++pParse->nMem;
      topAddr = sqlite3VdbeAddOp2(v, OP_Integer, 0, pItem->regReturn);
      pItem->addrFillSub = topAddr+1;
      if( pItem->isCorrelated==0 ){
        /* If the subquery is not correlated and if we are not inside of
        ** a trigger, then we only need to compute the value of the subquery
        ** once. */
        onceAddr = sqlite3CodeOnce(pParse); VdbeCoverage(v);
        VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
      }else{
        VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
      }
      sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
      explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
      sqlite3Select(pParse, pSub, &dest);
      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
      if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
      retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
      VdbeComment((v, "end %s", pItem->pTab->zName));
      sqlite3VdbeChangeP1(v, topAddr, retAddr);
      sqlite3ClearTempRegCache(pParse);

    }
    if( db->mallocFailed ){
      goto select_end;
    }
    pParse->nHeight -= sqlite3SelectExprHeight(p);




  }
  pEList = p->pEList;
#endif
  pWhere = p->pWhere;
  pGroupBy = p->pGroupBy;
  pHaving = p->pHaving;
  sDistinct.isTnct = (p->selFlags & SF_Distinct)!=0;

#if SELECTTRACE_ENABLED
  if( sqlite3SelectTrace & 0x400 ){
    SELECTTRACE(0x400,pParse,p,("After all FROM-clause analysis:\n"));
    sqlite3TreeViewSelect(0, p, 0);
  }














#endif

  /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  ** if the select-list is the same as the ORDER BY list, then this query
  ** can be rewritten as a GROUP BY. In other words, this:
  **
  **     SELECT DISTINCT xyz FROM ... ORDER BY xyz