/ Check-in [6e2e9d38]
Login

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

Overview
Comment:Reenable the SQLITE_EXPR_REF optimization for "SELECT DISTINCT ... ORDER BY" queries.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | sorter-opt
Files: files | file ages | folders
SHA1:6e2e9d383f5fc4a0cbf05fe83ec7425812c0f556
User & Date: dan 2016-11-11 18:08:59
Context
2016-11-11
18:45
Merge trunk with this branch. Closed-Leaf check-in: dd62d2de user: dan tags: sorter-opt
18:08
Reenable the SQLITE_EXPR_REF optimization for "SELECT DISTINCT ... ORDER BY" queries. check-in: 6e2e9d38 user: dan tags: sorter-opt
2016-11-10
20:14
Avoid storing redundant fields in sorter records when the sort-key and data have fields in common (as in "SELECT a FROM t1 ORDER BY 1"). check-in: 0af62fdb user: dan tags: sorter-opt
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to src/select.c.

517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
...
678
679
680
681
682
683
684
685
686
687
688
689
690








691
692
693
694
695
696
697
...
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
...
730
731
732
733
734
735
736

737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
...
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
...
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
...
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
  int regBase;                                     /* Regs for sorter record */
  int regRecord = ++pParse->nMem;                  /* Assembled sorter record */
  int nOBSat = pSort->nOBSat;                      /* ORDER BY terms to skip */
  int op;                            /* Opcode to add sorter record to sorter */
  int iLimit;                        /* LIMIT counter */

  assert( bSeq==0 || bSeq==1 );
  assert( nData==1 || regData==regOrigData );
  if( nPrefixReg ){
    assert( nPrefixReg==nExpr+bSeq );
    regBase = regData - nExpr - bSeq;
  }else{
    regBase = pParse->nMem + 1;
    pParse->nMem += nBase;
  }
  assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
  iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
  pSort->labelDone = sqlite3VdbeMakeLabel(v);
  sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,
                          SQLITE_ECEL_DUP);
  if( bSeq ){
    sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
  }
  if( nPrefixReg==0 && nData>0 ){
    sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
  }
  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
................................................................................
  SelectDest *pDest,      /* How to dispose of the results */
  int iContinue,          /* Jump here to continue with next row */
  int iBreak              /* Jump here to break out of the inner loop */
){
  Vdbe *v = pParse->pVdbe;
  int i;
  int hasDistinct;        /* True if the DISTINCT keyword is present */
  int regResult;              /* Start of memory holding result set */
  int eDest = pDest->eDest;   /* How to dispose of results */
  int iParm = pDest->iSDParm; /* First argument to disposal method */
  int nResultCol;             /* Number of result columns */
  int nPrefixReg = 0;         /* Number of extra registers before regResult */









  assert( v );
  assert( pEList!=0 );
  hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
  if( pSort && pSort->pOrderBy==0 ) pSort = 0;
  if( pSort==0 && !hasDistinct ){
    assert( iContinue!=0 );
    codeOffset(v, p->iOffset, iContinue);
................................................................................
    ** on the right-hand side of an INSERT contains more result columns than
    ** there are columns in the table on the left.  The error will be caught
    ** and reported later.  But we need to make sure enough memory is allocated
    ** to avoid other spurious errors in the meantime. */
    pParse->nMem += nResultCol;
  }
  pDest->nSdst = nResultCol;
  regResult = pDest->iSdst;
  if( srcTab>=0 ){
    for(i=0; i<nResultCol; i++){
      sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
      VdbeComment((v, "%s", pEList->a[i].zName));
    }
  }else if( eDest!=SRT_Exists ){
    /* If the destination is an EXISTS(...) expression, the actual
................................................................................
    */
    u8 ecelFlags;
    if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
      ecelFlags = SQLITE_ECEL_DUP;
    }else{
      ecelFlags = 0;
    }

    if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab && eDest!=SRT_Table ){
      /* For each expression in pEList that is a copy of an expression in
      ** the ORDER BY clause (pSort->pOrderBy), set the associated 
      ** iOrderByCol value to one more than the index of the ORDER BY 
      ** expression within the sort-key that pushOntoSorter() will generate.
      ** This allows the pEList field to be omitted from the sorted record,
      ** saving space and CPU cycles.  */
      ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
      for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
        int j;
        if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
          pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
        }
      }

      assert( eDest==SRT_Set || eDest==SRT_Mem 
           || eDest==SRT_Coroutine || eDest==SRT_Output );
    }
    nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags);
  }

  /* If the DISTINCT keyword was present on the SELECT statement
................................................................................
    case SRT_Set: {
      if( pSort ){
        /* At first glance you would think we could optimize out the
        ** ORDER BY in this case since the order of entries in the set
        ** does not matter.  But there might be a LIMIT clause, in which
        ** case the order does matter */
        pushOntoSorter(
            pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg);
      }else{
        int r1 = sqlite3GetTempReg(pParse);
        assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol, 
            r1, pDest->zAffSdst, nResultCol);
        sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
        sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
................................................................................
    ** store the results in the appropriate memory cell or array of 
    ** memory cells and break out of the scan loop.
    */
    case SRT_Mem: {
      if( pSort ){
        assert( nResultCol<=pDest->nSdst );
        pushOntoSorter(
            pParse, pSort, p, regResult, regResult, nResultCol, nPrefixReg);
      }else{
        assert( nResultCol==pDest->nSdst );
        assert( regResult==iParm );
        /* The LIMIT clause will jump out of the loop for us */
      }
      break;
    }
................................................................................
#endif /* #ifndef SQLITE_OMIT_SUBQUERY */

    case SRT_Coroutine:       /* Send data to a co-routine */
    case SRT_Output: {        /* Return the results */
      testcase( eDest==SRT_Coroutine );
      testcase( eDest==SRT_Output );
      if( pSort ){
        pushOntoSorter(pParse, pSort, p, regResult, regResult, nResultCol,
                       nPrefixReg);
      }else if( eDest==SRT_Coroutine ){
        sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
      }else{
        sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
        sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
      }







|











|







 







<





>
>
>
>
>
>
>
>







 







|







 







>
|













|







 







|







 







|







 







|







517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
...
678
679
680
681
682
683
684

685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
...
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
...
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
...
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
...
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
...
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
  int regBase;                                     /* Regs for sorter record */
  int regRecord = ++pParse->nMem;                  /* Assembled sorter record */
  int nOBSat = pSort->nOBSat;                      /* ORDER BY terms to skip */
  int op;                            /* Opcode to add sorter record to sorter */
  int iLimit;                        /* LIMIT counter */

  assert( bSeq==0 || bSeq==1 );
  assert( nData==1 || regData==regOrigData || regOrigData==0 );
  if( nPrefixReg ){
    assert( nPrefixReg==nExpr+bSeq );
    regBase = regData - nExpr - bSeq;
  }else{
    regBase = pParse->nMem + 1;
    pParse->nMem += nBase;
  }
  assert( pSelect->iOffset==0 || pSelect->iLimit!=0 );
  iLimit = pSelect->iOffset ? pSelect->iOffset+1 : pSelect->iLimit;
  pSort->labelDone = sqlite3VdbeMakeLabel(v);
  sqlite3ExprCodeExprList(pParse, pSort->pOrderBy, regBase, regOrigData,
                          SQLITE_ECEL_DUP | (regOrigData? SQLITE_ECEL_REF : 0));
  if( bSeq ){
    sqlite3VdbeAddOp2(v, OP_Sequence, pSort->iECursor, regBase+nExpr);
  }
  if( nPrefixReg==0 && nData>0 ){
    sqlite3ExprCodeMove(pParse, regData, regBase+nExpr+bSeq, nData);
  }
  sqlite3VdbeAddOp3(v, OP_MakeRecord, regBase+nOBSat, nBase-nOBSat, regRecord);
................................................................................
  SelectDest *pDest,      /* How to dispose of the results */
  int iContinue,          /* Jump here to continue with next row */
  int iBreak              /* Jump here to break out of the inner loop */
){
  Vdbe *v = pParse->pVdbe;
  int i;
  int hasDistinct;            /* True if the DISTINCT keyword is present */

  int eDest = pDest->eDest;   /* How to dispose of results */
  int iParm = pDest->iSDParm; /* First argument to disposal method */
  int nResultCol;             /* Number of result columns */
  int nPrefixReg = 0;         /* Number of extra registers before regResult */

  /* Usually, regResult is the first cell in an array of memory cells
  ** containing the current result row. In this case regOrig is set to the
  ** same value. However, if the results are being sent to the sorter, the
  ** values for any expressions that are also part of the sort-key are omitted
  ** from this array. In this case regOrig is set to zero.  */
  int regResult;              /* Start of memory holding current results */
  int regOrig;                /* Start of memory holding full result (or 0) */

  assert( v );
  assert( pEList!=0 );
  hasDistinct = pDistinct ? pDistinct->eTnctType : WHERE_DISTINCT_NOOP;
  if( pSort && pSort->pOrderBy==0 ) pSort = 0;
  if( pSort==0 && !hasDistinct ){
    assert( iContinue!=0 );
    codeOffset(v, p->iOffset, iContinue);
................................................................................
    ** on the right-hand side of an INSERT contains more result columns than
    ** there are columns in the table on the left.  The error will be caught
    ** and reported later.  But we need to make sure enough memory is allocated
    ** to avoid other spurious errors in the meantime. */
    pParse->nMem += nResultCol;
  }
  pDest->nSdst = nResultCol;
  regOrig = regResult = pDest->iSdst;
  if( srcTab>=0 ){
    for(i=0; i<nResultCol; i++){
      sqlite3VdbeAddOp3(v, OP_Column, srcTab, i, regResult+i);
      VdbeComment((v, "%s", pEList->a[i].zName));
    }
  }else if( eDest!=SRT_Exists ){
    /* If the destination is an EXISTS(...) expression, the actual
................................................................................
    */
    u8 ecelFlags;
    if( eDest==SRT_Mem || eDest==SRT_Output || eDest==SRT_Coroutine ){
      ecelFlags = SQLITE_ECEL_DUP;
    }else{
      ecelFlags = 0;
    }
    assert( eDest!=SRT_Table || pSort==0 );
    if( pSort && hasDistinct==0 && eDest!=SRT_EphemTab ){
      /* For each expression in pEList that is a copy of an expression in
      ** the ORDER BY clause (pSort->pOrderBy), set the associated 
      ** iOrderByCol value to one more than the index of the ORDER BY 
      ** expression within the sort-key that pushOntoSorter() will generate.
      ** This allows the pEList field to be omitted from the sorted record,
      ** saving space and CPU cycles.  */
      ecelFlags |= (SQLITE_ECEL_OMITREF|SQLITE_ECEL_REF);
      for(i=pSort->nOBSat; i<pSort->pOrderBy->nExpr; i++){
        int j;
        if( (j = pSort->pOrderBy->a[i].u.x.iOrderByCol)>0 ){
          pEList->a[j-1].u.x.iOrderByCol = i+1-pSort->nOBSat;
        }
      }
      regOrig = 0;
      assert( eDest==SRT_Set || eDest==SRT_Mem 
           || eDest==SRT_Coroutine || eDest==SRT_Output );
    }
    nResultCol = sqlite3ExprCodeExprList(pParse,pEList,regResult,0,ecelFlags);
  }

  /* If the DISTINCT keyword was present on the SELECT statement
................................................................................
    case SRT_Set: {
      if( pSort ){
        /* At first glance you would think we could optimize out the
        ** ORDER BY in this case since the order of entries in the set
        ** does not matter.  But there might be a LIMIT clause, in which
        ** case the order does matter */
        pushOntoSorter(
            pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
      }else{
        int r1 = sqlite3GetTempReg(pParse);
        assert( sqlite3Strlen30(pDest->zAffSdst)==nResultCol );
        sqlite3VdbeAddOp4(v, OP_MakeRecord, regResult, nResultCol, 
            r1, pDest->zAffSdst, nResultCol);
        sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
        sqlite3VdbeAddOp2(v, OP_IdxInsert, iParm, r1);
................................................................................
    ** store the results in the appropriate memory cell or array of 
    ** memory cells and break out of the scan loop.
    */
    case SRT_Mem: {
      if( pSort ){
        assert( nResultCol<=pDest->nSdst );
        pushOntoSorter(
            pParse, pSort, p, regResult, regOrig, nResultCol, nPrefixReg);
      }else{
        assert( nResultCol==pDest->nSdst );
        assert( regResult==iParm );
        /* The LIMIT clause will jump out of the loop for us */
      }
      break;
    }
................................................................................
#endif /* #ifndef SQLITE_OMIT_SUBQUERY */

    case SRT_Coroutine:       /* Send data to a co-routine */
    case SRT_Output: {        /* Return the results */
      testcase( eDest==SRT_Coroutine );
      testcase( eDest==SRT_Output );
      if( pSort ){
        pushOntoSorter(pParse, pSort, p, regResult, regOrig, nResultCol,
                       nPrefixReg);
      }else if( eDest==SRT_Coroutine ){
        sqlite3VdbeAddOp1(v, OP_Yield, pDest->iSDParm);
      }else{
        sqlite3VdbeAddOp2(v, OP_ResultRow, regResult, nResultCol);
        sqlite3ExprCacheAffinityChange(pParse, regResult, nResultCol);
      }