/ Check-in [e2c9f71a]
Login

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

Overview
Comment:Merge all recent trunk changes into the threads branch.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | threads
Files: files | file ages | folders
SHA1: e2c9f71a451e44040624b9f255b4510743513019
User & Date: drh 2014-04-23 12:57:55
Context
2014-04-24
12:28
Improvements to comments. Store some extra information in SqliteThread that is useful for debugging. check-in: 9fb5e212 user: drh tags: threads
2014-04-23
12:57
Merge all recent trunk changes into the threads branch. check-in: e2c9f71a user: drh tags: threads
2014-04-21
13:36
Comment tweaks on the test case for the [b75a9ca6b0] bug fix. check-in: 65d2544a user: drh tags: trunk
2014-04-18
13:57
Add to speedtest1.c the --threads option for setting the SQLITE_CONFIG_WORKER_THREADS configuration. check-in: 5fce40c4 user: drh tags: threads
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/select.c.

4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
....
4888
4889
4890
4891
4892
4893
4894

4895
4896
4897
4898
4899
4900
4901
....
4907
4908
4909
4910
4911
4912
4913












4914
4915
4916
4917
4918
4919
4920
....
4987
4988
4989
4990
4991
4992
4993
4994

4995
4996
4997
4998
4999
5000
5001
....
5051
5052
5053
5054
5055
5056
5057















5058
5059
5060
5061
5062
5063
5064
  if( p->pPrior ){
    rc = multiSelect(pParse, p, pDest);
    explainSetInteger(pParse->iSelectId, iRestoreSelectId);
    return rc;
  }
#endif

  /* If there is both a GROUP BY and an ORDER BY clause and they are
  ** identical, then disable the ORDER BY clause since the GROUP BY
  ** will cause elements to come out in the correct order.  This is
  ** an optimization - the correct answer should result regardless.
  ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  ** to disable this optimization for testing purposes.
  */
  if( sqlite3ExprListCompare(p->pGroupBy, sSort.pOrderBy, -1)==0
         && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
    sSort.pOrderBy = 0;
  }

  /* 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
  **
  ** is transformed to:
................................................................................
                        ** one row of the input to the aggregator has been
                        ** processed */
    int iAbortFlag;     /* Mem address which causes query abort if positive */
    int groupBySort;    /* Rows come from source in GROUP BY order */
    int addrEnd;        /* End of processing for this SELECT */
    int sortPTab = 0;   /* Pseudotable used to decode sorting results */
    int sortOut = 0;    /* Output register from the sorter */


    /* Remove any and all aliases between the result set and the
    ** GROUP BY clause.
    */
    if( pGroupBy ){
      int k;                        /* Loop counter */
      struct ExprList_item *pItem;  /* For looping over expression in a list */
................................................................................
        pItem->u.x.iAlias = 0;
      }
      if( p->nSelectRow>100 ) p->nSelectRow = 100;
    }else{
      p->nSelectRow = 1;
    }













 
    /* Create a label to jump to when we want to abort the query */
    addrEnd = sqlite3VdbeMakeLabel(v);

    /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
    ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
    ** SELECT statement.
................................................................................
      /* Begin a loop that will extract all source rows in GROUP BY order.
      ** This might involve two separate loops with an OP_Sort in between, or
      ** it might be a single loop that uses an index to extract information
      ** in the right order to begin with.
      */
      sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
                                 WHERE_GROUPBY, 0);

      if( pWInfo==0 ) goto select_end;
      if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
        /* The optimizer is able to deliver rows in group by order so
        ** we do not have to sort.  The OP_OpenEphemeral table will be
        ** cancelled later because we still need to use the pKeyInfo
        */
        groupBySort = 0;
................................................................................
        sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;
        sortOut = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
        sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
        VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);
        sAggInfo.useSortingIdx = 1;
        sqlite3ExprCacheClear(pParse);















      }

      /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
      ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
      ** Then compare the current GROUP BY terms against the GROUP BY terms
      ** from the previous row currently stored in a0, a1, a2...
      */







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







 







>







 







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







 







|
>







 







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







4747
4748
4749
4750
4751
4752
4753












4754
4755
4756
4757
4758
4759
4760
....
4876
4877
4878
4879
4880
4881
4882
4883
4884
4885
4886
4887
4888
4889
4890
....
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
....
4988
4989
4990
4991
4992
4993
4994
4995
4996
4997
4998
4999
5000
5001
5002
5003
....
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
  if( p->pPrior ){
    rc = multiSelect(pParse, p, pDest);
    explainSetInteger(pParse->iSelectId, iRestoreSelectId);
    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
  **
  ** is transformed to:
................................................................................
                        ** one row of the input to the aggregator has been
                        ** processed */
    int iAbortFlag;     /* Mem address which causes query abort if positive */
    int groupBySort;    /* Rows come from source in GROUP BY order */
    int addrEnd;        /* End of processing for this SELECT */
    int sortPTab = 0;   /* Pseudotable used to decode sorting results */
    int sortOut = 0;    /* Output register from the sorter */
    int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */

    /* Remove any and all aliases between the result set and the
    ** GROUP BY clause.
    */
    if( pGroupBy ){
      int k;                        /* Loop counter */
      struct ExprList_item *pItem;  /* For looping over expression in a list */
................................................................................
        pItem->u.x.iAlias = 0;
      }
      if( p->nSelectRow>100 ) p->nSelectRow = 100;
    }else{
      p->nSelectRow = 1;
    }


    /* If there is both a GROUP BY and an ORDER BY clause and they are
    ** identical, then it may be possible to disable the ORDER BY clause 
    ** on the grounds that the GROUP BY will cause elements to come out 
    ** in the correct order. It also may not - the GROUP BY may use a
    ** database index that causes rows to be grouped together as required
    ** but not actually sorted. Either way, record the fact that the
    ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
    ** variable.  */
    if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){
      orderByGrp = 1;
    }
 
    /* Create a label to jump to when we want to abort the query */
    addrEnd = sqlite3VdbeMakeLabel(v);

    /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
    ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
    ** SELECT statement.
................................................................................
      /* Begin a loop that will extract all source rows in GROUP BY order.
      ** This might involve two separate loops with an OP_Sort in between, or
      ** it might be a single loop that uses an index to extract information
      ** in the right order to begin with.
      */
      sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
      pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
          WHERE_GROUPBY | (orderByGrp ? WHERE_SORTBYGROUP : 0), 0
      );
      if( pWInfo==0 ) goto select_end;
      if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
        /* The optimizer is able to deliver rows in group by order so
        ** we do not have to sort.  The OP_OpenEphemeral table will be
        ** cancelled later because we still need to use the pKeyInfo
        */
        groupBySort = 0;
................................................................................
        sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;
        sortOut = sqlite3GetTempReg(pParse);
        sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
        sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
        VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);
        sAggInfo.useSortingIdx = 1;
        sqlite3ExprCacheClear(pParse);

      }

      /* If the index or temporary table used by the GROUP BY sort
      ** will naturally deliver rows in the order required by the ORDER BY
      ** clause, cancel the ephemeral table open coded earlier.
      **
      ** This is an optimization - the correct answer should result regardless.
      ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to 
      ** disable this optimization for testing purposes.  */
      if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder) 
       && (groupBySort || sqlite3WhereIsSorted(pWInfo))
      ){
        sSort.pOrderBy = 0;
        sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
      }

      /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
      ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
      ** Then compare the current GROUP BY terms against the GROUP BY terms
      ** from the previous row currently stored in a0, a1, a2...
      */

Changes to src/sqliteInt.h.

2136
2137
2138
2139
2140
2141
2142

2143
2144
2145
2146
2147
2148
2149
....
3104
3105
3106
3107
3108
3109
3110

3111
3112
3113
3114
3115
3116
3117
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
#define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */
#define WHERE_WANT_DISTINCT    0x0400 /* All output needs to be distinct */


/* Allowed return values from sqlite3WhereIsDistinct()
*/
#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
#define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
#define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
#define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */
................................................................................
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
void sqlite3WhereEnd(WhereInfo*);
u64 sqlite3WhereOutputRowCount(WhereInfo*);
int sqlite3WhereIsDistinct(WhereInfo*);
int sqlite3WhereIsOrdered(WhereInfo*);

int sqlite3WhereContinueLabel(WhereInfo*);
int sqlite3WhereBreakLabel(WhereInfo*);
int sqlite3WhereOkOnePass(WhereInfo*, int*);
int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);
void sqlite3ExprCodeMove(Parse*, int, int, int);
void sqlite3ExprCacheStore(Parse*, int, int, int);







>







 







>







2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
....
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
#define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
#define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
#define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
#define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
#define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
#define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */
#define WHERE_WANT_DISTINCT    0x0400 /* All output needs to be distinct */
#define WHERE_SORTBYGROUP      0x0800 /* Support sqlite3WhereIsSorted() */

/* Allowed return values from sqlite3WhereIsDistinct()
*/
#define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
#define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
#define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
#define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */
................................................................................
void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
void sqlite3WhereEnd(WhereInfo*);
u64 sqlite3WhereOutputRowCount(WhereInfo*);
int sqlite3WhereIsDistinct(WhereInfo*);
int sqlite3WhereIsOrdered(WhereInfo*);
int sqlite3WhereIsSorted(WhereInfo*);
int sqlite3WhereContinueLabel(WhereInfo*);
int sqlite3WhereBreakLabel(WhereInfo*);
int sqlite3WhereOkOnePass(WhereInfo*, int*);
int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);
void sqlite3ExprCodeMove(Parse*, int, int, int);
void sqlite3ExprCacheStore(Parse*, int, int, int);

Changes to src/where.c.

3708
3709
3710
3711
3712
3713
3714
3715
3716










3717
3718




3719
3720





3721
3722
3723

3724

3725
3726

3727
3728
3729
3730
3731
3732
3733
....
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
....
4779
4780
4781
4782
4783
4784
4785
4786
4787
4788
4789
4790
4791
4792
4793
....
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
4962
....
5028
5029
5030
5031
5032
5033
5034






























5035
5036
5037
5038
5039
5040
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
....
5321
5322
5323
5324
5325
5326
5327









5328



5329
5330
5331
5332
5333
5334
5335
      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if the set of WHERE clause terms used by pA is a proper
** subset of the WHERE clause terms used by pB.










*/
static int whereLoopProperSubset(const WhereLoop *pA, const WhereLoop *pB){




  int i, j;
  assert( pA->nLTerm<pB->nLTerm );  /* Checked by calling function */





  for(j=0, i=pA->nLTerm-1; i>=0 && j>=0; i--){
    for(j=pB->nLTerm-1; j>=0; j--){
      if( pB->aLTerm[j]==pA->aLTerm[i] ) break;

    }

  }
  return j>=0;

}

/*
** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
** that:
**
**   (1) pTemplate costs less than any other WhereLoops that are a proper
................................................................................
** also used by Y.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( p->nLTerm<pTemplate->nLTerm
     && (p->rRun<pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut<=pTemplate->nOut))
     && whereLoopProperSubset(p, pTemplate)
    ){
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else
    if( p->nLTerm>pTemplate->nLTerm
     && (p->rRun>pTemplate->rRun || (p->rRun==pTemplate->rRun &&
                                     p->nOut>=pTemplate->nOut))
     && whereLoopProperSubset(pTemplate, p)
    ){
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut + 1;
    }
  }
}

/*
................................................................................
**   N>0:   N terms of the ORDER BY clause are satisfied
**   N==0:  No terms of the ORDER BY clause are satisfied
**   N<0:   Unknown yet how many terms of ORDER BY might be satisfied.   
**
** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
** strict.  With GROUP BY and DISTINCT the only requirement is that
** equivalent rows appear immediately adjacent to one another.  GROUP BY
** and DISTINT do not require rows to appear in any particular order as long
** as equivelent rows are grouped together.  Thus for GROUP BY and DISTINCT
** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
** pOrderBy terms must be matched in strict left-to-right order.
*/
static i8 wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
................................................................................
         && j>=pLoop->u.btree.nEq
         && pIndex->pTable->aCol[iColumn].notNull==0
        ){
          isOrderDistinct = 0;
        }

        /* Find the ORDER BY term that corresponds to the j-th column
        ** of the index and and mark that ORDER BY term off 
        */
        bOnce = 1;
        isMatch = 0;
        for(i=0; bOnce && i<nOrderBy; i++){
          if( MASKBIT(i) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
          testcase( wctrlFlags & WHERE_GROUPBY );
................................................................................
      if( (obSat&m)==m ) return i;
    }
    return 0;
  }
  return -1;
}































#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  static char zName[65];
  int i;
  for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
  if( pLast ) zName[i++] = pLast->cId;
  zName[i] = 0;
  return zName;
}
#endif


/*
** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Assume that the total number of output rows that will need to be sorted
................................................................................
        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
      }
    }else{
      pWInfo->nOBSat = pFrom->isOrdered;
      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
      pWInfo->revMask = pFrom->revLoop;
    }









  }



  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}








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

<
>
>
>
>

<
>
>
>
>
>
|
|
<
>

>

<
>







 







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







 







|







 







|







 







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











<







 







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







3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727

3728
3729
3730
3731
3732

3733
3734
3735
3736
3737
3738
3739

3740
3741
3742
3743

3744
3745
3746
3747
3748
3749
3750
3751
....
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773





3774
3775
3776
3777
3778
3779
3780
....
4792
4793
4794
4795
4796
4797
4798
4799
4800
4801
4802
4803
4804
4805
4806
....
4961
4962
4963
4964
4965
4966
4967
4968
4969
4970
4971
4972
4973
4974
4975
....
5041
5042
5043
5044
5045
5046
5047
5048
5049
5050
5051
5052
5053
5054
5055
5056
5057
5058
5059
5060
5061
5062
5063
5064
5065
5066
5067
5068
5069
5070
5071
5072
5073
5074
5075
5076
5077
5078
5079
5080
5081
5082
5083
5084
5085
5086
5087
5088

5089
5090
5091
5092
5093
5094
5095
....
5363
5364
5365
5366
5367
5368
5369
5370
5371
5372
5373
5374
5375
5376
5377
5378
5379
5380
5381
5382
5383
5384
5385
5386
5387
5388
5389
      whereLoopDelete(db, p);
    }
    sqlite3DbFree(db, pWInfo);
  }
}

/*
** Return TRUE if both of the following are true:
**
**   (1)  X has the same or lower cost that Y
**   (2)  X is a proper subset of Y
**
** By "proper subset" we mean that X uses fewer WHERE clause terms
** than Y and that every WHERE clause term used by X is also used
** by Y.
**
** If X is a proper subset of Y then Y is a better choice and ought
** to have a lower cost.  This routine returns TRUE when that cost 
** relationship is inverted and needs to be adjusted.
*/

static int whereLoopCheaperProperSubset(
  const WhereLoop *pX,       /* First WhereLoop to compare */
  const WhereLoop *pY        /* Compare against this WhereLoop */
){
  int i, j;

  if( pX->nLTerm >= pY->nLTerm ) return 0; /* X is not a subset of Y */
  if( pX->rRun >= pY->rRun ){
    if( pX->rRun > pY->rRun ) return 0;    /* X costs more than Y */
    if( pX->nOut > pY->nOut ) return 0;    /* X costs more than Y */
  }
  for(j=0, i=pX->nLTerm-1; i>=0; i--){
    for(j=pY->nLTerm-1; j>=0; j--){

      if( pY->aLTerm[j]==pX->aLTerm[i] ) break;
    }
    if( j<0 ) return 0;  /* X not a subset of Y since term X[i] not used by Y */
  }

  return 1;  /* All conditions meet */
}

/*
** Try to adjust the cost of WhereLoop pTemplate upwards or downwards so
** that:
**
**   (1) pTemplate costs less than any other WhereLoops that are a proper
................................................................................
** also used by Y.
*/
static void whereLoopAdjustCost(const WhereLoop *p, WhereLoop *pTemplate){
  if( (pTemplate->wsFlags & WHERE_INDEXED)==0 ) return;
  for(; p; p=p->pNextLoop){
    if( p->iTab!=pTemplate->iTab ) continue;
    if( (p->wsFlags & WHERE_INDEXED)==0 ) continue;
    if( whereLoopCheaperProperSubset(p, pTemplate) ){
      /* Adjust pTemplate cost downward so that it is cheaper than its 
      ** subset p */
      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut - 1;
    }else if( whereLoopCheaperProperSubset(pTemplate, p) ){
      /* Adjust pTemplate cost upward so that it is costlier than p since
      ** pTemplate is a proper subset of p */





      pTemplate->rRun = p->rRun;
      pTemplate->nOut = p->nOut + 1;
    }
  }
}

/*
................................................................................
**   N>0:   N terms of the ORDER BY clause are satisfied
**   N==0:  No terms of the ORDER BY clause are satisfied
**   N<0:   Unknown yet how many terms of ORDER BY might be satisfied.   
**
** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
** strict.  With GROUP BY and DISTINCT the only requirement is that
** equivalent rows appear immediately adjacent to one another.  GROUP BY
** and DISTINCT do not require rows to appear in any particular order as long
** as equivelent rows are grouped together.  Thus for GROUP BY and DISTINCT
** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
** pOrderBy terms must be matched in strict left-to-right order.
*/
static i8 wherePathSatisfiesOrderBy(
  WhereInfo *pWInfo,    /* The WHERE clause */
  ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
................................................................................
         && j>=pLoop->u.btree.nEq
         && pIndex->pTable->aCol[iColumn].notNull==0
        ){
          isOrderDistinct = 0;
        }

        /* Find the ORDER BY term that corresponds to the j-th column
        ** of the index and mark that ORDER BY term off 
        */
        bOnce = 1;
        isMatch = 0;
        for(i=0; bOnce && i<nOrderBy; i++){
          if( MASKBIT(i) & obSat ) continue;
          pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
          testcase( wctrlFlags & WHERE_GROUPBY );
................................................................................
      if( (obSat&m)==m ) return i;
    }
    return 0;
  }
  return -1;
}


/*
** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
** the planner assumes that the specified pOrderBy list is actually a GROUP
** BY clause - and so any order that groups rows as required satisfies the
** request.
**
** Normally, in this case it is not possible for the caller to determine
** whether or not the rows are really being delivered in sorted order, or
** just in some other order that provides the required grouping. However,
** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
** this function may be called on the returned WhereInfo object. It returns
** true if the rows really will be sorted in the specified order, or false
** otherwise.
**
** For example, assuming:
**
**   CREATE INDEX i1 ON t1(x, Y);
**
** then
**
**   SELECT * FROM t1 GROUP BY x,y ORDER BY x,y;   -- IsSorted()==1
**   SELECT * FROM t1 GROUP BY y,x ORDER BY y,x;   -- IsSorted()==0
*/
int sqlite3WhereIsSorted(WhereInfo *pWInfo){
  assert( pWInfo->wctrlFlags & WHERE_GROUPBY );
  assert( pWInfo->wctrlFlags & WHERE_SORTBYGROUP );
  return pWInfo->sorted;
}

#ifdef WHERETRACE_ENABLED
/* For debugging use only: */
static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  static char zName[65];
  int i;
  for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
  if( pLast ) zName[i++] = pLast->cId;
  zName[i] = 0;
  return zName;
}
#endif


/*
** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
** attempts to find the lowest cost path that visits each WhereLoop
** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
**
** Assume that the total number of output rows that will need to be sorted
................................................................................
        pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
      }
    }else{
      pWInfo->nOBSat = pFrom->isOrdered;
      if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
      pWInfo->revMask = pFrom->revLoop;
    }
    if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
        && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr
    ){
      Bitmask notUsed = 0;
      int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 
          pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed
      );
      assert( pWInfo->sorted==0 );
      pWInfo->sorted = (nOrder==pWInfo->pOrderBy->nExpr);
    }
  }


  pWInfo->nRowOut = pFrom->nRow;

  /* Free temporary memory and return success */
  sqlite3DbFree(db, pSpace);
  return SQLITE_OK;
}

Changes to src/whereInt.h.

394
395
396
397
398
399
400

401
402
403
404
405
406
407
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pResultSet;     /* Result set. DISTINCT operates on these */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */
  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  LogEst nRowOut;           /* Estimated number of output rows */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */

  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  u8 nLevel;                /* Number of nested loop */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */







>







394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
  ExprList *pOrderBy;       /* The ORDER BY clause or NULL */
  ExprList *pResultSet;     /* Result set. DISTINCT operates on these */
  WhereLoop *pLoops;        /* List of all WhereLoop objects */
  Bitmask revMask;          /* Mask of ORDER BY terms that need reversing */
  LogEst nRowOut;           /* Estimated number of output rows */
  u16 wctrlFlags;           /* Flags originally passed to sqlite3WhereBegin() */
  i8 nOBSat;                /* Number of ORDER BY terms satisfied by indices */
  u8 sorted;                /* True if really sorted (not just grouped) */
  u8 okOnePass;             /* Ok to use one-pass algorithm for UPDATE/DELETE */
  u8 untestedTerms;         /* Not all WHERE terms resolved by outer loop */
  u8 eDistinct;             /* One of the WHERE_DISTINCT_* values below */
  u8 nLevel;                /* Number of nested loop */
  int iTop;                 /* The very beginning of the WHERE loop */
  int iContinue;            /* Jump here to continue with next record */
  int iBreak;               /* Jump here to break out of the loop */

Added test/tkt-b75a9ca6b0.test.



























































































































































>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
# 2014-04-21
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#*************************************************************************
#
# Test that ticket [b75a9ca6b0] has been fixed.
#
# Ticket [b75a9ca6b0] concerns queries that have both a GROUP BY
# and an ORDER BY.  This code verifies that SQLite is able to
# optimize out the ORDER BY in some circumstances, but retains the
# ORDER BY when necessary.
#

set testdir [file dirname $argv0]
source $testdir/tester.tcl
set testprefix tkt-b75a9ca6b0

do_execsql_test 1 {
  CREATE TABLE t1 (x, y);
  INSERT INTO t1 VALUES (1, 3); 
  INSERT INTO t1 VALUES (2, 2);
  INSERT INTO t1 VALUES (3, 1);
}

do_execsql_test 1.1 {
  CREATE INDEX i1 ON t1(x, y);
} 

set idxscan {0 0 0 {SCAN TABLE t1 USING COVERING INDEX i1}}
set tblscan {0 0 0 {SCAN TABLE t1}}
set grpsort {0 0 0 {USE TEMP B-TREE FOR GROUP BY}}
set sort    {0 0 0 {USE TEMP B-TREE FOR ORDER BY}}

foreach {tn q res eqp} [subst -nocommands {
  1 "SELECT * FROM t1 GROUP BY x, y ORDER BY x,y"
  {1 3  2 2  3 1} {$idxscan}

  2 "SELECT * FROM t1 GROUP BY x, y ORDER BY x"
  {1 3  2 2  3 1} {$idxscan $sort}

  3 "SELECT * FROM t1 GROUP BY y, x ORDER BY y, x"
  {3 1  2 2  1 3} {$idxscan $sort}
  
  4 "SELECT * FROM t1 GROUP BY x ORDER BY x"
  {1 3  2 2  3 1} {$idxscan}

  5 "SELECT * FROM t1 GROUP BY y ORDER BY y"
  {3 1  2 2  1 3} {$tblscan $grpsort}

  6 "SELECT * FROM t1 GROUP BY y ORDER BY x"
  {1 3  2 2  3 1} {$tblscan $grpsort $sort}

  7 "SELECT * FROM t1 GROUP BY x, y ORDER BY x, y DESC"
  {1 3  2 2  3 1} {$idxscan $sort}

  8 "SELECT * FROM t1 GROUP BY x, y ORDER BY x DESC, y DESC"
  {3 1  2 2  1 3} {$idxscan $sort}

  9 "SELECT * FROM t1 GROUP BY x, y ORDER BY x ASC, y ASC"
  {1 3  2 2  3 1} {$idxscan}

  10 "SELECT * FROM t1 GROUP BY x, y ORDER BY x COLLATE nocase, y"
  {1 3  2 2  3 1} {$idxscan $sort}

}] {
  do_execsql_test 1.$tn.1 $q $res
  do_eqp_test     1.$tn.2 $q $eqp
}


finish_test