SQLite

Check-in [6caec9082b]
Login

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

Overview
Comment:Enhance the min/max optimization so that it works with indexes on expressions.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: 6caec9082b3ad6d3f89f6291084a8f5c80f296630e2e94bc764389ac1a47a833
User & Date: drh 2017-10-26 20:04:28.629
Context
2017-10-27
12:27
Additional test case demonstrating the ability to access structure elements using quoted names in the JSON1 extension. (check-in: 8d3cc928a8 user: drh tags: trunk)
2017-10-26
20:04
Enhance the min/max optimization so that it works with indexes on expressions. (check-in: 6caec9082b user: drh tags: trunk)
18:43
Extra ".selecttrace" output following aggregate analysis. No changes to production builds. (check-in: 6fbf74ab31 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925


3926
3927
3928

3929
3930
3931
3932
3933

3934
3935
3936
3937
3938
3939
3940
3941
3942

3943

3944
3945
3946
3947
3948
3949
3950
3951
3952
3953

3954
3955
3956
3957

3958
3959
3960
3961
3962
3963
3964
    }
  }
  return nChng;
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

/*
** Based on the contents of the AggInfo structure indicated by the first
** argument, this function checks if the following are true:
**
**    * the query contains just a single aggregate function,


**    * the aggregate function is either min() or max(), and
**    * the argument to the aggregate function is a column value.
**

** If all of the above are true, then WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX
** is returned as appropriate. Also, *ppMinMax is set to point to the 
** list of arguments passed to the aggregate before returning.
**
** Or, if the conditions above are not met, *ppMinMax is set to 0 and

** WHERE_ORDERBY_NORMAL is returned.
*/
static u8 minMaxQuery(AggInfo *pAggInfo, ExprList **ppMinMax){
  int eRet = WHERE_ORDERBY_NORMAL;          /* Return value */

  *ppMinMax = 0;
  if( pAggInfo->nFunc==1 ){
    Expr *pExpr = pAggInfo->aFunc[0].pExpr; /* Aggregate function */
    ExprList *pEList = pExpr->x.pList;      /* Arguments to agg function */



    assert( pExpr->op==TK_AGG_FUNCTION );
    if( pEList && pEList->nExpr==1 && pEList->a[0].pExpr->op==TK_AGG_COLUMN ){
      const char *zFunc = pExpr->u.zToken;
      if( sqlite3StrICmp(zFunc, "min")==0 ){
        eRet = WHERE_ORDERBY_MIN;
        *ppMinMax = pEList;
      }else if( sqlite3StrICmp(zFunc, "max")==0 ){
        eRet = WHERE_ORDERBY_MAX;
        *ppMinMax = pEList;
      }

    }
  }

  assert( *ppMinMax==0 || (*ppMinMax)->nExpr==1 );

  return eRet;
}

/*
** The select statement passed as the first argument is an aggregate query.
** The second argument is the associated aggregate-info object. This 
** function tests if the SELECT is of the form:







|
|

|
>
>
|
<

>
|
<
<

|
>
|

|
|
|
<
<
|
|
>

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







3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928

3929
3930
3931


3932
3933
3934
3935
3936
3937
3938
3939


3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956

3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
    }
  }
  return nChng;
}
#endif /* !defined(SQLITE_OMIT_SUBQUERY) || !defined(SQLITE_OMIT_VIEW) */

/*
** The pFunc is the only aggregate function in the query.  Check to see
** if the query is a candidate for the min/max optimization. 
**
** If the query is a candidate for the min/max optimization, then set
** *ppMinMax to be an ORDER BY clause to be used for the optimization
** and return either WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX depending on
** whether pFunc is a min() or max() function.

**
** If the query is not a candidate for the min/max optimization, return
** WHERE_ORDERBY_NORMAL (which must be zero).


**
** This routine must be called after aggregate functions have been
** located but before their arguments have been subjected to aggregate
** analysis.
*/
static u8 minMaxQuery(sqlite3 *db, Expr *pFunc, ExprList **ppMinMax){
  int eRet = WHERE_ORDERBY_NORMAL;      /* Return value */
  ExprList *pEList = pFunc->x.pList;    /* Arguments to agg function */


  const char *zFunc;                    /* Name of aggregate function pFunc */
  ExprList *pOrderBy;
  u8 sortOrder;

  assert( *ppMinMax==0 );
  assert( pFunc->op==TK_AGG_FUNCTION );
  if( pEList==0 || pEList->nExpr!=1 ) return eRet;
  zFunc = pFunc->u.zToken;
  if( sqlite3StrICmp(zFunc, "min")==0 ){
    eRet = WHERE_ORDERBY_MIN;
    sortOrder = SQLITE_SO_ASC;
  }else if( sqlite3StrICmp(zFunc, "max")==0 ){
    eRet = WHERE_ORDERBY_MAX;
    sortOrder = SQLITE_SO_DESC;
  }else{
    return eRet;
  }

  *ppMinMax = pOrderBy = sqlite3ExprListDup(db, pEList, 0);
  assert( pOrderBy!=0 || db->mallocFailed );
  if( pOrderBy ) pOrderBy->a[0].sortOrder = sortOrder;
  return eRet;
}

/*
** The select statement passed as the first argument is an aggregate query.
** The second argument is the associated aggregate-info object. This 
** function tests if the SELECT is of the form:
5131
5132
5133
5134
5135
5136
5137


5138
5139
5140
5141
5142
5143
5144
  Expr *pHaving;         /* The HAVING clause.  May be NULL */
  int rc = 1;            /* Value to return from this function */
  DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
  SortCtx sSort;         /* Info on how to code the ORDER BY clause */
  AggInfo sAggInfo;      /* Information used by aggregate queries */
  int iEnd;              /* Address of the end of the query */
  sqlite3 *db;           /* The database connection */



#ifndef SQLITE_OMIT_EXPLAIN
  int iRestoreSelectId = pParse->iSelectId;
  pParse->iSelectId = pParse->iNextSelectId++;
#endif

  db = pParse->db;







>
>







5133
5134
5135
5136
5137
5138
5139
5140
5141
5142
5143
5144
5145
5146
5147
5148
  Expr *pHaving;         /* The HAVING clause.  May be NULL */
  int rc = 1;            /* Value to return from this function */
  DistinctCtx sDistinct; /* Info on how to code the DISTINCT keyword */
  SortCtx sSort;         /* Info on how to code the ORDER BY clause */
  AggInfo sAggInfo;      /* Information used by aggregate queries */
  int iEnd;              /* Address of the end of the query */
  sqlite3 *db;           /* The database connection */
  ExprList *pMinMaxOrderBy = 0;  /* Added ORDER BY for min/max queries */
  u8 minMaxFlag;                 /* Flag for min/max queries */

#ifndef SQLITE_OMIT_EXPLAIN
  int iRestoreSelectId = pParse->iSelectId;
  pParse->iSelectId = pParse->iNextSelectId++;
#endif

  db = pParse->db;
5647
5648
5649
5650
5651
5652
5653





5654
5655
5656
5657
5658
5659
5660
        assert( pWhere==p->pWhere );
        havingToWhere(pParse, pGroupBy, pHaving, &p->pWhere);
        pWhere = p->pWhere;
      }
      sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
    }
    sAggInfo.nAccumulator = sAggInfo.nColumn;





    for(i=0; i<sAggInfo.nFunc; i++){
      assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
      sNC.ncFlags |= NC_InAggFunc;
      sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);
      sNC.ncFlags &= ~NC_InAggFunc;
    }
    sAggInfo.mxReg = pParse->nMem;







>
>
>
>
>







5651
5652
5653
5654
5655
5656
5657
5658
5659
5660
5661
5662
5663
5664
5665
5666
5667
5668
5669
        assert( pWhere==p->pWhere );
        havingToWhere(pParse, pGroupBy, pHaving, &p->pWhere);
        pWhere = p->pWhere;
      }
      sqlite3ExprAnalyzeAggregates(&sNC, pHaving);
    }
    sAggInfo.nAccumulator = sAggInfo.nColumn;
    if( p->pGroupBy==0 && p->pHaving==0 && sAggInfo.nFunc==1 ){
      minMaxFlag = minMaxQuery(db, sAggInfo.aFunc[0].pExpr, &pMinMaxOrderBy);
    }else{
      minMaxFlag = WHERE_ORDERBY_NORMAL;
    }
    for(i=0; i<sAggInfo.nFunc; i++){
      assert( !ExprHasProperty(sAggInfo.aFunc[i].pExpr, EP_xIsSelect) );
      sNC.ncFlags |= NC_InAggFunc;
      sqlite3ExprAnalyzeAggList(&sNC, sAggInfo.aFunc[i].pExpr->x.pList);
      sNC.ncFlags &= ~NC_InAggFunc;
    }
    sAggInfo.mxReg = pParse->nMem;
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914
5915
5916
      */
      sqlite3VdbeResolveLabel(v, addrReset);
      resetAccumulator(pParse, &sAggInfo);
      sqlite3VdbeAddOp1(v, OP_Return, regReset);
     
    } /* endif pGroupBy.  Begin aggregate queries without GROUP BY: */
    else {
      ExprList *pDel = 0;
#ifndef SQLITE_OMIT_BTREECOUNT
      Table *pTab;
      if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){
        /* If isSimpleCount() returns a pointer to a Table structure, then
        ** the SQL statement is of the form:
        **
        **   SELECT count(*) FROM <tbl>







<







5911
5912
5913
5914
5915
5916
5917

5918
5919
5920
5921
5922
5923
5924
      */
      sqlite3VdbeResolveLabel(v, addrReset);
      resetAccumulator(pParse, &sAggInfo);
      sqlite3VdbeAddOp1(v, OP_Return, regReset);
     
    } /* endif pGroupBy.  Begin aggregate queries without GROUP BY: */
    else {

#ifndef SQLITE_OMIT_BTREECOUNT
      Table *pTab;
      if( (pTab = isSimpleCount(p, &sAggInfo))!=0 ){
        /* If isSimpleCount() returns a pointer to a Table structure, then
        ** the SQL statement is of the form:
        **
        **   SELECT count(*) FROM <tbl>
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
6007
6008
6009
6010
6011
6012
6013
6014
6015
6016
6017
6018
6019


6020
6021

6022
6023
6024
6025
6026
6027
6028
6029
6030
6031
6032
6033
6034
6035
6036
6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);
        explainSimpleCount(pParse, pTab, pBest);
      }else
#endif /* SQLITE_OMIT_BTREECOUNT */
      {
        /* Check if the query is of one of the following forms:
        **
        **   SELECT min(x) FROM ...
        **   SELECT max(x) FROM ...
        **
        ** If it is, then ask the code in where.c to attempt to sort results
        ** as if there was an "ORDER BY x" or "ORDER BY x DESC" clause. 
        ** If where.c is able to produce results sorted in this order, then
        ** add vdbe code to break out of the processing loop after the 
        ** first iteration (since the first iteration of the loop is 
        ** guaranteed to operate on the row with the minimum or maximum 
        ** value of x, the only row required).
        **
        ** A special flag must be passed to sqlite3WhereBegin() to slightly
        ** modify behavior as follows:
        **
        **   + If the query is a "SELECT min(x)", then the loop coded by
        **     where.c should not iterate over any values with a NULL value
        **     for x.
        **
        **   + The optimizer code in where.c (the thing that decides which
        **     index or indices to use) should place a different priority on 
        **     satisfying the 'ORDER BY' clause than it does in other cases.
        **     Refer to code and comments in where.c for details.
        */
        ExprList *pMinMax = 0;
        u8 flag = WHERE_ORDERBY_NORMAL;
        
        assert( p->pGroupBy==0 );
        assert( flag==0 );
        if( p->pHaving==0 ){
          flag = minMaxQuery(&sAggInfo, &pMinMax);
        }
        assert( flag==0 || (pMinMax!=0 && pMinMax->nExpr==1) );

        if( flag ){
          pMinMax = sqlite3ExprListDup(db, pMinMax, 0);
          pDel = pMinMax;
          assert( db->mallocFailed || pMinMax!=0 );
          if( !db->mallocFailed ){
            pMinMax->a[0].sortOrder = flag!=WHERE_ORDERBY_MIN ?1:0;
            pMinMax->a[0].pExpr->op = TK_COLUMN;
          }
        }
  
        /* This case runs if the aggregate has no GROUP BY clause.  The
        ** processing is much simpler since there is only a single row
        ** of output.
        */


        resetAccumulator(pParse, &sAggInfo);
        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMax, 0,flag,0);

        if( pWInfo==0 ){
          sqlite3ExprListDelete(db, pDel);
          goto select_end;
        }
        updateAccumulator(pParse, &sAggInfo);
        assert( pMinMax==0 || pMinMax->nExpr==1 );
        if( sqlite3WhereIsOrdered(pWInfo)>0 ){
          sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));
          VdbeComment((v, "%s() by index",
                (flag==WHERE_ORDERBY_MIN?"min":"max")));
        }
        sqlite3WhereEnd(pWInfo);
        finalizeAggFunctions(pParse, &sAggInfo);
      }

      sSort.pOrderBy = 0;
      sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
      selectInnerLoop(pParse, p, -1, 0, 0, 
                      pDest, addrEnd, addrEnd);
      sqlite3ExprListDelete(db, pDel);
    }
    sqlite3VdbeResolveLabel(v, addrEnd);
    
  } /* endif aggregate query */

  if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
    explainTempTable(pParse, "DISTINCT");







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

<
<
<

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

>
>
|
|
>

<



<



|









<







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
6007
6008
6009
6010
6011
6012

6013
6014
6015
6016
6017
6018
6019
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, sAggInfo.aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);
        explainSimpleCount(pParse, pTab, pBest);
      }else
#endif /* SQLITE_OMIT_BTREECOUNT */
      {
        /* This case runs if the aggregate has no GROUP BY clause.  The







        ** processing is much simpler since there is only a single row



        ** of output.











        */



        assert( p->pGroupBy==0 );


        resetAccumulator(pParse, &sAggInfo);


        /* If this query is a candidate for the min/max optimization, then


        ** minMaxFlag will have been previously set to either


        ** WHERE_ORDERBY_MIN or WHERE_ORDERBY_MAX and pMinMaxOrderBy will



        ** be an appropriate ORDER BY expression for the optimization.



        */
        assert( minMaxFlag==WHERE_ORDERBY_NORMAL || pMinMaxOrderBy!=0 );
        assert( pMinMaxOrderBy==0 || pMinMaxOrderBy->nExpr==1 );

        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMaxOrderBy,
                                   0, minMaxFlag, 0);
        if( pWInfo==0 ){

          goto select_end;
        }
        updateAccumulator(pParse, &sAggInfo);

        if( sqlite3WhereIsOrdered(pWInfo)>0 ){
          sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));
          VdbeComment((v, "%s() by index",
                (minMaxFlag==WHERE_ORDERBY_MIN?"min":"max")));
        }
        sqlite3WhereEnd(pWInfo);
        finalizeAggFunctions(pParse, &sAggInfo);
      }

      sSort.pOrderBy = 0;
      sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
      selectInnerLoop(pParse, p, -1, 0, 0, 
                      pDest, addrEnd, addrEnd);

    }
    sqlite3VdbeResolveLabel(v, addrEnd);
    
  } /* endif aggregate query */

  if( sDistinct.eTnctType==WHERE_DISTINCT_UNORDERED ){
    explainTempTable(pParse, "DISTINCT");
6066
6067
6068
6069
6070
6071
6072
6073
6074
6075
6076
6077
6078
6079
6080
6081
  rc = (pParse->nErr>0);

  /* Control jumps to here if an error is encountered above, or upon
  ** successful coding of the SELECT.
  */
select_end:
  explainSetInteger(pParse->iSelectId, iRestoreSelectId);

  sqlite3DbFree(db, sAggInfo.aCol);
  sqlite3DbFree(db, sAggInfo.aFunc);
#if SELECTTRACE_ENABLED
  SELECTTRACE(1,pParse,p,("end processing\n"));
  pParse->nSelectIndent--;
#endif
  return rc;
}







|








6037
6038
6039
6040
6041
6042
6043
6044
6045
6046
6047
6048
6049
6050
6051
6052
  rc = (pParse->nErr>0);

  /* Control jumps to here if an error is encountered above, or upon
  ** successful coding of the SELECT.
  */
select_end:
  explainSetInteger(pParse->iSelectId, iRestoreSelectId);
  sqlite3ExprListDelete(db, pMinMaxOrderBy);
  sqlite3DbFree(db, sAggInfo.aCol);
  sqlite3DbFree(db, sAggInfo.aFunc);
#if SELECTTRACE_ENABLED
  SELECTTRACE(1,pParse,p,("end processing\n"));
  pParse->nSelectIndent--;
#endif
  return rc;
}
Changes to test/minmax2.test.
379
380
381
382
383
384
385


































386
387
}
do_test minmax2-10.12 {
  execsql {
    SELECT min(x), max(x) FROM t6;
  }
} {{} {}}




































finish_test







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


379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
}
do_test minmax2-10.12 {
  execsql {
    SELECT min(x), max(x) FROM t6;
  }
} {{} {}}

# 2017-10-26.  Extend the min/max optimization to indexes on expressions
#
do_execsql_test minmax2-11.100 {
  CREATE TABLE t11(a,b,c);
  INSERT INTO t11(a,b,c) VALUES(1,10,5),(2,8,11),(3,1,4),(4,20,1),(5,16,4);
  CREATE INDEX t11bc ON t11(b+c);
  SELECT max(b+c) FROM t11;
} {21}
do_execsql_test minmax2-11.110 {
  SELECT a, max(b+c) FROM t11;
} {4 21}
do_test minmax2-11.111 {
  db eval {SELECT max(b+c) FROM t11}
  db status step
} {0}
do_test minmax2-11.112 {
  db eval {SELECT max(c+b) FROM t11}
  db status step
} {4}
do_execsql_test minmax2-11.120 {
  SELECT a, min(b+c) FROM t11;
} {3 5}
do_test minmax2-11.121 {
  db eval {SELECT min(b+c) FROM t11}
  db status step
} {0}
do_test minmax2-11.122 {
  db eval {SELECT min(c+b) FROM t11}
  db status step
} {4}
do_execsql_test minmax2-11.130 {
  INSERT INTO t11(a,b,c) VALUES(6,NULL,0),(7,0,NULL);
  SELECT a, min(b+c) FROM t11;
} {3 5}

finish_test