SQLite

Check-in [b8ba2f17]
Login

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

Overview
Comment:Improvements to the min()/max() optimization so that it is able to use indexes where terms are constrained by IN operators.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: b8ba2f17f938c03543a89dd29d6987163f7a4085a51de1aa14ea5504501c4f72
User & Date: drh 2020-07-14 23:58:04
References
2021-01-14
20:57
Improvements to the min/max optimization. Fix for a performance regression introduced at [b8ba2f17f938c035] reported by forum post 4050026ab8 (check-in: 249a71cc user: drh tags: trunk)
2021-01-13
15:23
Further enhancements to the min/max optimization of check-in b8ba2f17f938c035 to fix the performance regression identified by forum post 4050026ab8. (check-in: 188772a1 user: drh tags: minmax-opt-exp)
Context
2020-07-15
02:15
New test cases for decimal and ieee754. (check-in: 73d62f82 user: drh tags: trunk)
2020-07-14
23:58
Improvements to the min()/max() optimization so that it is able to use indexes where terms are constrained by IN operators. (check-in: b8ba2f17 user: drh tags: trunk)
22:20
Now appears to work. All legacy tests pass. Need to add new tests, however. (Closed-Leaf check-in: 81e64509 user: drh tags: minmax-opt-exp)
15:30
Fix an obsolete header comment on the sqlite3WhereIsOrdered() routine. (check-in: 5041f6a1 user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/select.c.
︙︙
6702
6703
6704
6705
6706
6707
6708

6709
6710
6711
6712
6713
6714
6715

          sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, pAggInfo->aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);
        explainSimpleCount(pParse, pTab, pBest);
      }else{
        int regAcc = 0;           /* "populate accumulators" flag */


        /* If there are accumulator registers but no min() or max() functions
        ** without FILTER clauses, allocate register regAcc. Register regAcc
        ** will contain 0 the first time the inner loop runs, and 1 thereafter.
        ** The code generated by updateAccumulator() uses this to ensure
        ** that the accumulator registers are (a) updated only once if
        ** there are no min() or max functions or (b) always updated for the








>








6702
6703
6704
6705
6706
6707
6708
6709
6710
6711
6712
6713
6714
6715
6716

          sqlite3VdbeChangeP4(v, -1, (char *)pKeyInfo, P4_KEYINFO);
        }
        sqlite3VdbeAddOp2(v, OP_Count, iCsr, pAggInfo->aFunc[0].iMem);
        sqlite3VdbeAddOp1(v, OP_Close, iCsr);
        explainSimpleCount(pParse, pTab, pBest);
      }else{
        int regAcc = 0;           /* "populate accumulators" flag */
        int addrSkip;

        /* If there are accumulator registers but no min() or max() functions
        ** without FILTER clauses, allocate register regAcc. Register regAcc
        ** will contain 0 the first time the inner loop runs, and 1 thereafter.
        ** The code generated by updateAccumulator() uses this to ensure
        ** that the accumulator registers are (a) updated only once if
        ** there are no min() or max functions or (b) always updated for the
︙︙
6750
6751
6752
6753
6754
6755
6756
6757

6758
6759
6760
6761
6762
6763
6764
6765
6766
6767

        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMaxOrderBy,
                                   0, minMaxFlag, 0);
        if( pWInfo==0 ){
          goto select_end;
        }
        updateAccumulator(pParse, regAcc, pAggInfo);
        if( regAcc ) sqlite3VdbeAddOp2(v, OP_Integer, 1, regAcc);
        if( sqlite3WhereIsOrdered(pWInfo)>0 ){

          sqlite3VdbeGoto(v, sqlite3WhereBreakLabel(pWInfo));
          VdbeComment((v, "%s() by index",
                (minMaxFlag==WHERE_ORDERBY_MIN?"min":"max")));
        }
        sqlite3WhereEnd(pWInfo);
        finalizeAggFunctions(pParse, pAggInfo);
      }

      sSort.pOrderBy = 0;
      sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);








|
>
|
<
<








6751
6752
6753
6754
6755
6756
6757
6758
6759
6760


6761
6762
6763
6764
6765
6766
6767

        pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pMinMaxOrderBy,
                                   0, minMaxFlag, 0);
        if( pWInfo==0 ){
          goto select_end;
        }
        updateAccumulator(pParse, regAcc, pAggInfo);
        if( regAcc ) sqlite3VdbeAddOp2(v, OP_Integer, 1, regAcc);
        addrSkip = sqlite3WhereOrderByLimitOptLabel(pWInfo);
        if( addrSkip!=sqlite3WhereContinueLabel(pWInfo) ){
          sqlite3VdbeGoto(v, addrSkip);


        }
        sqlite3WhereEnd(pWInfo);
        finalizeAggFunctions(pParse, pAggInfo);
      }

      sSort.pOrderBy = 0;
      sqlite3ExprIfFalse(pParse, pHaving, addrEnd, SQLITE_JUMPIFNULL);
︙︙
Changes to src/where.c.
︙︙
3740
3741
3742
3743
3744
3745
3746

3747

3748
3749
3750
3751
3752
3753
3754

  testcase( nOrderBy==BMS-1 );
  if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  isOrderDistinct = 1;
  obDone = MASKBIT(nOrderBy)-1;
  orderDistinctMask = 0;
  ready = 0;
  eqOpMask = WO_EQ | WO_IS | WO_ISNULL;

  if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN;

  for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
    if( iLoop>0 ) ready |= pLoop->maskSelf;
    if( iLoop<nLoop ){
      pLoop = pPath->aLoop[iLoop];
      if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
    }else{
      pLoop = pLast;








>
|
>








3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756

  testcase( nOrderBy==BMS-1 );
  if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  isOrderDistinct = 1;
  obDone = MASKBIT(nOrderBy)-1;
  orderDistinctMask = 0;
  ready = 0;
  eqOpMask = WO_EQ | WO_IS | WO_ISNULL;
  if( wctrlFlags & (WHERE_ORDERBY_LIMIT|WHERE_ORDERBY_MAX|WHERE_ORDERBY_MIN) ){
    eqOpMask |= WO_IN;
  }
  for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
    if( iLoop>0 ) ready |= pLoop->maskSelf;
    if( iLoop<nLoop ){
      pLoop = pPath->aLoop[iLoop];
      if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
    }else{
      pLoop = pLast;
︙︙
3776
3777
3778
3779
3780
3781
3782
3783

3784
3785
3786
3787
3788
3789
3790

      pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
                       ~ready, eqOpMask, 0);
      if( pTerm==0 ) continue;
      if( pTerm->eOperator==WO_IN ){
        /* IN terms are only valid for sorting in the ORDER BY LIMIT 
        ** optimization, and then only if they are actually used
        ** by the query plan */
        assert( wctrlFlags & WHERE_ORDERBY_LIMIT );

        for(j=0; j<pLoop->nLTerm && pTerm!=pLoop->aLTerm[j]; j++){}
        if( j>=pLoop->nLTerm ) continue;
      }
      if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){
        Parse *pParse = pWInfo->pParse;
        CollSeq *pColl1 = sqlite3ExprNNCollSeq(pParse, pOrderBy->a[i].pExpr);
        CollSeq *pColl2 = sqlite3ExprCompareCollSeq(pParse, pTerm->pExpr);








|
>








3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793

      pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
                       ~ready, eqOpMask, 0);
      if( pTerm==0 ) continue;
      if( pTerm->eOperator==WO_IN ){
        /* IN terms are only valid for sorting in the ORDER BY LIMIT 
        ** optimization, and then only if they are actually used
        ** by the query plan */
        assert( wctrlFlags & 
               (WHERE_ORDERBY_LIMIT|WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX) );
        for(j=0; j<pLoop->nLTerm && pTerm!=pLoop->aLTerm[j]; j++){}
        if( j>=pLoop->nLTerm ) continue;
      }
      if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){
        Parse *pParse = pWInfo->pParse;
        CollSeq *pColl1 = sqlite3ExprNNCollSeq(pParse, pOrderBy->a[i].pExpr);
        CollSeq *pColl2 = sqlite3ExprCompareCollSeq(pParse, pTerm->pExpr);
︙︙
4424
4425
4426
4427
4428
4429
4430





4431
4432
4433
4434
4435
4436
4437

            testcase( wsFlags & WHERE_COLUMN_IN );
            if( rc==pWInfo->pOrderBy->nExpr ){
              pWInfo->bOrderedInnerLoop = 1;
              pWInfo->revMask = m;
            }
          }
        }





      }
    }
    if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
        && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
    ){
      Bitmask revMask = 0;
      int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 








>
>
>
>
>








4427
4428
4429
4430
4431
4432
4433
4434
4435
4436
4437
4438
4439
4440
4441
4442
4443
4444
4445

            testcase( wsFlags & WHERE_COLUMN_IN );
            if( rc==pWInfo->pOrderBy->nExpr ){
              pWInfo->bOrderedInnerLoop = 1;
              pWInfo->revMask = m;
            }
          }
        }
      }else if( nLoop
            && pWInfo->nOBSat==1
            && (pWInfo->wctrlFlags & (WHERE_ORDERBY_MIN|WHERE_ORDERBY_MAX))!=0
            ){
        pWInfo->bOrderedInnerLoop = 1;
      }
    }
    if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
        && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
    ){
      Bitmask revMask = 0;
      int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy,
︙︙