/ Check-in [74aec5dd]
Login

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

Overview
Comment:Refactor the code that figures out which SELECT in a cascade of nested queries a particular aggregate function belongs to. This fixes the problem reported by forum post c7cc2aa3546e39c1. New test cases in dbsqlfuzz and th3.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 74aec5dd1df95b5635f4da1f13753f113ea1d61de3dc3a1523ba51089c1900e4
User & Date: drh 2021-11-08 23:24:00
Context
2021-11-09
01:48
Fix lempar.c so that Lemon can compile with NDEBUG defined. Forum post f331adca0b (check-in: ba4fb518 user: drh tags: trunk)
2021-11-08
23:24
Refactor the code that figures out which SELECT in a cascade of nested queries a particular aggregate function belongs to. This fixes the problem reported by forum post c7cc2aa3546e39c1. New test cases in dbsqlfuzz and th3. (check-in: 74aec5dd user: drh tags: trunk)
19:35
Fix the zeroblob() function and related APIs so that they work with SQLITE_OMIT_INCRBLOB builds. (check-in: bc401a75 user: dan tags: trunk)
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/expr.c.

5875
5876
5877
5878
5879
5880
5881
5882
5883
5884
5885
5886
5887
5888

5889
5890
5891
5892
5893
5894
5895
5896

5897
5898

5899

5900
5901
5902




5903








5904
5905
5906
5907






5908



5909
5910




5911
5912
5913
5914
5915
5916
5917
5918
5919


5920
5921
5922
5923
5924
5925


5926
5927
5928

5929
5930
5931
5932
5933

5934
5935
5936
5937
5938
5939
5940
5941




5942


5943



5944
5945
5946
5947
5948
5949

5950
5951

5952

5953
5954
5955
5956

5957
5958
5959
5960
5961
5962
5963


5964





5965
5966
5967
5968
5969
5970
5971
  w.xExprCallback = exprIdxCover;
  w.u.pIdxCover = &xcov;
  sqlite3WalkExpr(&w, pExpr);
  return !w.eCode;
}


/*
** An instance of the following structure is used by the tree walker
** to count references to table columns in the arguments of an 
** aggregate function, in order to implement the
** sqlite3FunctionThisSrc() routine.
*/
struct SrcCount {

  SrcList *pSrc;   /* One particular FROM clause in a nested query */
  int iSrcInner;   /* Smallest cursor number in this context */
  int nThis;       /* Number of references to columns in pSrcList */
  int nOther;      /* Number of references to columns in other FROM clauses */
};

/*
** xSelect callback for sqlite3FunctionUsesThisSrc(). If this is the first

** SELECT with a FROM clause encountered during this iteration, set
** SrcCount.iSrcInner to the cursor number of the leftmost object in

** the FROM cause.

*/
static int selectSrcCount(Walker *pWalker, Select *pSel){
  struct SrcCount *p = pWalker->u.pSrcCount;




  if( p->iSrcInner==0x7FFFFFFF && ALWAYS(pSel->pSrc) && pSel->pSrc->nSrc ){








    pWalker->u.pSrcCount->iSrcInner = pSel->pSrc->a[0].iCursor;
  }
  return WRC_Continue;
}










/*
** Count the number of references to columns.




*/
static int exprSrcCount(Walker *pWalker, Expr *pExpr){
  /* There was once a NEVER() on the second term on the grounds that
  ** sqlite3FunctionUsesThisSrc() was always called before 
  ** sqlite3ExprAnalyzeAggregates() and so the TK_COLUMNs have not yet 
  ** been converted into TK_AGG_COLUMN. But this is no longer true due
  ** to window functions - sqlite3WindowRewrite() may now indirectly call
  ** FunctionUsesThisSrc() when creating a new sub-select. */
  if( pExpr->op==TK_COLUMN || pExpr->op==TK_AGG_COLUMN ){


    int i;
    struct SrcCount *p = pWalker->u.pSrcCount;
    SrcList *pSrc = p->pSrc;
    int nSrc = pSrc ? pSrc->nSrc : 0;
    for(i=0; i<nSrc; i++){
      if( pExpr->iTable==pSrc->a[i].iCursor ) break;


    }
    if( i<nSrc ){
      p->nThis++;

    }else if( pExpr->iTable<p->iSrcInner ){
      /* In a well-formed parse tree (no name resolution errors),
      ** TK_COLUMN nodes with smaller Expr.iTable values are in an
      ** outer context.  Those are the only ones to count as "other" */
      p->nOther++;

    }
  }
  return WRC_Continue;
}

/*
** Determine if any of the arguments to the pExpr Function reference
** pSrcList.  Return true if they do.  Also return true if the function




** has no arguments or has only constant arguments.  Return false if pExpr


** references columns but not columns of tables found in pSrcList.



*/
int sqlite3FunctionUsesThisSrc(Expr *pExpr, SrcList *pSrcList){
  Walker w;
  struct SrcCount cnt;
  assert( pExpr->op==TK_AGG_FUNCTION );
  memset(&w, 0, sizeof(w));

  w.xExprCallback = exprSrcCount;
  w.xSelectCallback = selectSrcCount;

  w.u.pSrcCount = &cnt;

  cnt.pSrc = pSrcList;
  cnt.iSrcInner = (pSrcList&&pSrcList->nSrc)?pSrcList->a[0].iCursor:0x7FFFFFFF;
  cnt.nThis = 0;
  cnt.nOther = 0;

  assert( ExprUseXList(pExpr) );
  sqlite3WalkExprList(&w, pExpr->x.pList);
#ifndef SQLITE_OMIT_WINDOWFUNC
  if( ExprHasProperty(pExpr, EP_WinFunc) ){
    sqlite3WalkExpr(&w, pExpr->y.pWin->pFilter);
  }
#endif


  return cnt.nThis>0 || cnt.nOther==0;





}

/*
** This is a Walker expression node callback.
**
** For Expr nodes that contain pAggInfo pointers, make sure the AggInfo
** object that is referenced does not refer directly to the Expr.  If







<
|
<
|
<

|
>
|
<
|
|



|
>
|
<
>
|
>

|
|
>
>
>
>
|
>
>
>
>
>
>
>
>
|



>
>
>
>
>
>
|
>
>
>
|
|
>
>
>
>

|
<
<
<
<
<
<
|
>
>

|
|


|
>
>
|
<
<
>
|
<
<
<
|
>






|
|
>
>
>
>
|
>
>
|
>
>
>

|

|
<

>
|
|
>
|
>
|
<
<
<
>







>
>
|
>
>
>
>
>







5875
5876
5877
5878
5879
5880
5881

5882

5883

5884
5885
5886
5887

5888
5889
5890
5891
5892
5893
5894
5895

5896
5897
5898
5899
5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914
5915
5916
5917
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927
5928
5929
5930
5931
5932
5933
5934
5935
5936






5937
5938
5939
5940
5941
5942
5943
5944
5945
5946
5947
5948


5949
5950



5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975

5976
5977
5978
5979
5980
5981
5982
5983



5984
5985
5986
5987
5988
5989
5990
5991
5992
5993
5994
5995
5996
5997
5998
5999
6000
6001
6002
6003
6004
6005
6006
  w.xExprCallback = exprIdxCover;
  w.u.pIdxCover = &xcov;
  sqlite3WalkExpr(&w, pExpr);
  return !w.eCode;
}



/* Structure used to pass information throught the Walker in order to

** implement sqlite3ReferencesSrcList().

*/
struct RefSrcList {
  sqlite3 *db;         /* Database connection used for sqlite3DbRealloc() */
  SrcList *pRef;       /* Looking for references to these tables */

  int nExclude;        /* Number of tables to exclude from the search */
  int *aiExclude;      /* Cursor IDs for tables to exclude from the search */
};

/*
** Walker SELECT callbacks for sqlite3ReferencesSrcList().
**
** When entering a new subquery on the pExpr argument, add all FROM clause

** entries for that subquery to the exclude list.
**
** When leaving the subquery, remove those entries from the exclude list.
*/
static int selectRefEnter(Walker *pWalker, Select *pSelect){
  struct RefSrcList *p = pWalker->u.pRefSrcList;
  SrcList *pSrc = pSelect->pSrc;
  int i, j, *piNew;
  if( pSrc->nSrc==0 ) return WRC_Continue;
  j = p->nExclude;
  p->nExclude += pSrc->nSrc;
  piNew = sqlite3DbRealloc(p->db, p->aiExclude, p->nExclude*sizeof(int));
  if( piNew==0 ){
    p->nExclude = 0;
    return WRC_Abort;
  }else{
    p->aiExclude = piNew;
  }
  for(i=0; i<pSrc->nSrc; i++, j++){
     p->aiExclude[j] = pSrc->a[i].iCursor;
  }
  return WRC_Continue;
}
static void selectRefLeave(Walker *pWalker, Select *pSelect){
  struct RefSrcList *p = pWalker->u.pRefSrcList;
  SrcList *pSrc = pSelect->pSrc;
  if( p->nExclude ){
    assert( p->nExclude>=pSrc->nSrc );
    p->nExclude -= pSrc->nSrc;
  }
}

/* This is the Walker EXPR callback for sqlite3ReferencesSrcList().
** 
** Set the 0x01 bit of pWalker->eCode if there is a reference to any
** of the tables shown in RefSrcList.pRef.
**
** Set the 0x02 bit of pWalker->eCode if there is a reference to a
** table is in neither RefSrcList.pRef nor RefSrcList.aiExclude.
*/
static int exprRefToSrcList(Walker *pWalker, Expr *pExpr){






  if( pExpr->op==TK_COLUMN
   || pExpr->op==TK_AGG_COLUMN
  ){
    int i;
    struct RefSrcList *p = pWalker->u.pRefSrcList;
    SrcList *pSrc = p->pRef;
    int nSrc = pSrc ? pSrc->nSrc : 0;
    for(i=0; i<nSrc; i++){
      if( pExpr->iTable==pSrc->a[i].iCursor ){
        pWalker->eCode |= 1;
        return WRC_Continue;
      }


    }
    for(i=0; i<p->nExclude && p->aiExclude[i]!=pExpr->iTable; i++){}



    if( i>=p->nExclude ){
      pWalker->eCode |= 2;
    }
  }
  return WRC_Continue;
}

/*
** Check to see if pExpr references any tables in pSrcList.
** Possible return values:
**
**    1         pExpr does references a table in pSrcList.
**
**    0         pExpr references some table that is not defined in either
**              pSrcList or in subqueries of pExpr itself.
**
**   -1         pExpr only references no tables at all, or it only
**              references tables defined in subqueries of pExpr itself.
**
** As currently used, pExpr is always an aggregate function call.  That
** fact is exploited for efficiency.
*/
int sqlite3ReferencesSrcList(Parse *pParse, Expr *pExpr, SrcList *pSrcList){
  Walker w;
  struct RefSrcList x;

  memset(&w, 0, sizeof(w));
  memset(&x, 0, sizeof(x));
  w.xExprCallback = exprRefToSrcList;
  w.xSelectCallback = selectRefEnter;
  w.xSelectCallback2 = selectRefLeave;
  w.u.pRefSrcList = &x;
  x.db = pParse->db;
  x.pRef = pSrcList;



  assert( pExpr->op==TK_AGG_FUNCTION );
  assert( ExprUseXList(pExpr) );
  sqlite3WalkExprList(&w, pExpr->x.pList);
#ifndef SQLITE_OMIT_WINDOWFUNC
  if( ExprHasProperty(pExpr, EP_WinFunc) ){
    sqlite3WalkExpr(&w, pExpr->y.pWin->pFilter);
  }
#endif
  sqlite3DbFree(pParse->db, x.aiExclude);
  if( w.eCode & 0x01 ){
    return 1;
  }else if( w.eCode ){
    return 0;
  }else{
    return -1;
  }
}

/*
** This is a Walker expression node callback.
**
** For Expr nodes that contain pAggInfo pointers, make sure the AggInfo
** object that is referenced does not refer directly to the Expr.  If

Changes to src/resolve.c.

1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102

1103


1104
1105
1106
1107
1108
1109
1110
          sqlite3WalkExprList(pWalker, pWin->pOrderBy);
          sqlite3WalkExpr(pWalker, pWin->pFilter);
          sqlite3WindowLink(pSel, pWin);
          pNC->ncFlags |= NC_HasWin;
        }else
#endif /* SQLITE_OMIT_WINDOWFUNC */
        {
          NameContext *pNC2 = pNC;
          pExpr->op = TK_AGG_FUNCTION;
          pExpr->op2 = 0;
#ifndef SQLITE_OMIT_WINDOWFUNC
          if( ExprHasProperty(pExpr, EP_WinFunc) ){
            sqlite3WalkExpr(pWalker, pExpr->y.pWin->pFilter);
          }
#endif

          while( pNC2 && !sqlite3FunctionUsesThisSrc(pExpr, pNC2->pSrcList) ){


            pExpr->op2++;
            pNC2 = pNC2->pNext;
          }
          assert( pDef!=0 || IN_RENAME_OBJECT );
          if( pNC2 && pDef ){
            assert( SQLITE_FUNC_MINMAX==NC_MinMaxAgg );
            assert( SQLITE_FUNC_ANYORDER==NC_OrderAgg );







|







>
|
>
>







1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
          sqlite3WalkExprList(pWalker, pWin->pOrderBy);
          sqlite3WalkExpr(pWalker, pWin->pFilter);
          sqlite3WindowLink(pSel, pWin);
          pNC->ncFlags |= NC_HasWin;
        }else
#endif /* SQLITE_OMIT_WINDOWFUNC */
        {
          NameContext *pNC2;          /* For looping up thru outer contexts */
          pExpr->op = TK_AGG_FUNCTION;
          pExpr->op2 = 0;
#ifndef SQLITE_OMIT_WINDOWFUNC
          if( ExprHasProperty(pExpr, EP_WinFunc) ){
            sqlite3WalkExpr(pWalker, pExpr->y.pWin->pFilter);
          }
#endif
          pNC2 = pNC;
          while( pNC2 
              && sqlite3ReferencesSrcList(pParse, pExpr, pNC2->pSrcList)==0
          ){
            pExpr->op2++;
            pNC2 = pNC2->pNext;
          }
          assert( pDef!=0 || IN_RENAME_OBJECT );
          if( pNC2 && pDef ){
            assert( SQLITE_FUNC_MINMAX==NC_MinMaxAgg );
            assert( SQLITE_FUNC_ANYORDER==NC_OrderAgg );

Changes to src/sqliteInt.h.

3960
3961
3962
3963
3964
3965
3966
3967
3968

3969
3970
3971
3972
3973
3974
3975
  int walkerDepth;                          /* Number of subqueries */
  u16 eCode;                                /* A small processing code */
  union {                                   /* Extra data for callback */
    NameContext *pNC;                         /* Naming context */
    int n;                                    /* A counter */
    int iCur;                                 /* A cursor number */
    SrcList *pSrcList;                        /* FROM clause */
    struct SrcCount *pSrcCount;               /* Counting column references */
    struct CCurHint *pCCurHint;               /* Used by codeCursorHint() */

    int *aiCol;                               /* array of column indexes */
    struct IdxCover *pIdxCover;               /* Check for index coverage */
    struct IdxExprTrans *pIdxTrans;           /* Convert idxed expr to column */
    ExprList *pGroupBy;                       /* GROUP BY clause */
    Select *pSelect;                          /* HAVING to WHERE clause ctx */
    struct WindowRewrite *pRewrite;           /* Window rewrite context */
    struct WhereConst *pConst;                /* WHERE clause constants */







<

>







3960
3961
3962
3963
3964
3965
3966

3967
3968
3969
3970
3971
3972
3973
3974
3975
  int walkerDepth;                          /* Number of subqueries */
  u16 eCode;                                /* A small processing code */
  union {                                   /* Extra data for callback */
    NameContext *pNC;                         /* Naming context */
    int n;                                    /* A counter */
    int iCur;                                 /* A cursor number */
    SrcList *pSrcList;                        /* FROM clause */

    struct CCurHint *pCCurHint;               /* Used by codeCursorHint() */
    struct RefSrcList *pRefSrcList;           /* sqlite3ReferencesSrcList() */
    int *aiCol;                               /* array of column indexes */
    struct IdxCover *pIdxCover;               /* Check for index coverage */
    struct IdxExprTrans *pIdxTrans;           /* Convert idxed expr to column */
    ExprList *pGroupBy;                       /* GROUP BY clause */
    Select *pSelect;                          /* HAVING to WHERE clause ctx */
    struct WindowRewrite *pRewrite;           /* Window rewrite context */
    struct WhereConst *pConst;                /* WHERE clause constants */
4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
int sqlite3ExprListCompare(const ExprList*,const ExprList*, int);
int sqlite3ExprImpliesExpr(const Parse*,const Expr*,const Expr*, int);
int sqlite3ExprImpliesNonNullRow(Expr*,int);
void sqlite3AggInfoPersistWalkerInit(Walker*,Parse*);
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);
void sqlite3PrngRestoreState(void);
#endif
void sqlite3RollbackAll(sqlite3*,int);
void sqlite3CodeVerifySchema(Parse*, int);







|







4619
4620
4621
4622
4623
4624
4625
4626
4627
4628
4629
4630
4631
4632
4633
int sqlite3ExprListCompare(const ExprList*,const ExprList*, int);
int sqlite3ExprImpliesExpr(const Parse*,const Expr*,const Expr*, int);
int sqlite3ExprImpliesNonNullRow(Expr*,int);
void sqlite3AggInfoPersistWalkerInit(Walker*,Parse*);
void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
int sqlite3ExprCoveredByIndex(Expr*, int iCur, Index *pIdx);
int sqlite3ReferencesSrcList(Parse*, Expr*, SrcList*);
Vdbe *sqlite3GetVdbe(Parse*);
#ifndef SQLITE_UNTESTABLE
void sqlite3PrngSaveState(void);
void sqlite3PrngRestoreState(void);
#endif
void sqlite3RollbackAll(sqlite3*,int);
void sqlite3CodeVerifySchema(Parse*, int);