/ Check-in [de9a490f]
Login

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

Overview
Comment:Avoid discarding an ORDER BY clause in the case where an identical GROUP BY clauses uses an index to group, but not sort, the rows. Fix for [b75a9ca6b0].
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: de9a490f594183f337a2ec9e0f87792eac83548b
User & Date: dan 2014-04-21 13:21:56
Context
2014-04-21
13:36
Comment tweaks on the test case for the [b75a9ca6b0] bug fix. check-in: 65d2544a user: drh tags: trunk
13:21
Avoid discarding an ORDER BY clause in the case where an identical GROUP BY clauses uses an index to group, but not sort, the rows. Fix for [b75a9ca6b0]. check-in: de9a490f user: dan tags: trunk
2014-04-18
22:20
Clean up the proper-subset cost adjustment logic to make it more compact and easier to read and so that full branch test coverage is more easily obtained. check-in: 9a5d38c7 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  4715   4715     if( p->pPrior ){
  4716   4716       rc = multiSelect(pParse, p, pDest);
  4717   4717       explainSetInteger(pParse->iSelectId, iRestoreSelectId);
  4718   4718       return rc;
  4719   4719     }
  4720   4720   #endif
  4721   4721   
  4722         -  /* If there is both a GROUP BY and an ORDER BY clause and they are
  4723         -  ** identical, then disable the ORDER BY clause since the GROUP BY
  4724         -  ** will cause elements to come out in the correct order.  This is
  4725         -  ** an optimization - the correct answer should result regardless.
  4726         -  ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER
  4727         -  ** to disable this optimization for testing purposes.
  4728         -  */
  4729         -  if( sqlite3ExprListCompare(p->pGroupBy, sSort.pOrderBy, -1)==0
  4730         -         && OptimizationEnabled(db, SQLITE_GroupByOrder) ){
  4731         -    sSort.pOrderBy = 0;
  4732         -  }
  4733         -
  4734   4722     /* If the query is DISTINCT with an ORDER BY but is not an aggregate, and 
  4735   4723     ** if the select-list is the same as the ORDER BY list, then this query
  4736   4724     ** can be rewritten as a GROUP BY. In other words, this:
  4737   4725     **
  4738   4726     **     SELECT DISTINCT xyz FROM ... ORDER BY xyz
  4739   4727     **
  4740   4728     ** is transformed to:
................................................................................
  4855   4843                           ** one row of the input to the aggregator has been
  4856   4844                           ** processed */
  4857   4845       int iAbortFlag;     /* Mem address which causes query abort if positive */
  4858   4846       int groupBySort;    /* Rows come from source in GROUP BY order */
  4859   4847       int addrEnd;        /* End of processing for this SELECT */
  4860   4848       int sortPTab = 0;   /* Pseudotable used to decode sorting results */
  4861   4849       int sortOut = 0;    /* Output register from the sorter */
         4850  +    int orderByGrp = 0; /* True if the GROUP BY and ORDER BY are the same */
  4862   4851   
  4863   4852       /* Remove any and all aliases between the result set and the
  4864   4853       ** GROUP BY clause.
  4865   4854       */
  4866   4855       if( pGroupBy ){
  4867   4856         int k;                        /* Loop counter */
  4868   4857         struct ExprList_item *pItem;  /* For looping over expression in a list */
................................................................................
  4874   4863           pItem->u.x.iAlias = 0;
  4875   4864         }
  4876   4865         if( p->nSelectRow>100 ) p->nSelectRow = 100;
  4877   4866       }else{
  4878   4867         p->nSelectRow = 1;
  4879   4868       }
  4880   4869   
         4870  +
         4871  +    /* If there is both a GROUP BY and an ORDER BY clause and they are
         4872  +    ** identical, then it may be possible to disable the ORDER BY clause 
         4873  +    ** on the grounds that the GROUP BY will cause elements to come out 
         4874  +    ** in the correct order. It also may not - the GROUP BY may use a
         4875  +    ** database index that causes rows to be grouped together as required
         4876  +    ** but not actually sorted. Either way, record the fact that the
         4877  +    ** ORDER BY and GROUP BY clauses are the same by setting the orderByGrp
         4878  +    ** variable.  */
         4879  +    if( sqlite3ExprListCompare(pGroupBy, sSort.pOrderBy, -1)==0 ){
         4880  +      orderByGrp = 1;
         4881  +    }
  4881   4882    
  4882   4883       /* Create a label to jump to when we want to abort the query */
  4883   4884       addrEnd = sqlite3VdbeMakeLabel(v);
  4884   4885   
  4885   4886       /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in
  4886   4887       ** sAggInfo for all TK_AGG_FUNCTION nodes in expressions of the
  4887   4888       ** SELECT statement.
................................................................................
  4954   4955         /* Begin a loop that will extract all source rows in GROUP BY order.
  4955   4956         ** This might involve two separate loops with an OP_Sort in between, or
  4956   4957         ** it might be a single loop that uses an index to extract information
  4957   4958         ** in the right order to begin with.
  4958   4959         */
  4959   4960         sqlite3VdbeAddOp2(v, OP_Gosub, regReset, addrReset);
  4960   4961         pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, pGroupBy, 0,
  4961         -                                 WHERE_GROUPBY, 0);
         4962  +          WHERE_GROUPBY | (orderByGrp ? WHERE_SORTBYGROUP : 0), 0
         4963  +      );
  4962   4964         if( pWInfo==0 ) goto select_end;
  4963   4965         if( sqlite3WhereIsOrdered(pWInfo)==pGroupBy->nExpr ){
  4964   4966           /* The optimizer is able to deliver rows in group by order so
  4965   4967           ** we do not have to sort.  The OP_OpenEphemeral table will be
  4966   4968           ** cancelled later because we still need to use the pKeyInfo
  4967   4969           */
  4968   4970           groupBySort = 0;
................................................................................
  5019   5021           sAggInfo.sortingIdxPTab = sortPTab = pParse->nTab++;
  5020   5022           sortOut = sqlite3GetTempReg(pParse);
  5021   5023           sqlite3VdbeAddOp3(v, OP_OpenPseudo, sortPTab, sortOut, nCol);
  5022   5024           sqlite3VdbeAddOp2(v, OP_SorterSort, sAggInfo.sortingIdx, addrEnd);
  5023   5025           VdbeComment((v, "GROUP BY sort")); VdbeCoverage(v);
  5024   5026           sAggInfo.useSortingIdx = 1;
  5025   5027           sqlite3ExprCacheClear(pParse);
         5028  +
         5029  +      }
         5030  +
         5031  +      /* If the index or temporary table used by the GROUP BY sort
         5032  +      ** will naturally deliver rows in the order required by the ORDER BY
         5033  +      ** clause, cancel the ephemeral table open coded earlier.
         5034  +      **
         5035  +      ** This is an optimization - the correct answer should result regardless.
         5036  +      ** Use the SQLITE_GroupByOrder flag with SQLITE_TESTCTRL_OPTIMIZER to 
         5037  +      ** disable this optimization for testing purposes.  */
         5038  +      if( orderByGrp && OptimizationEnabled(db, SQLITE_GroupByOrder) 
         5039  +       && (groupBySort || sqlite3WhereIsSorted(pWInfo))
         5040  +      ){
         5041  +        sSort.pOrderBy = 0;
         5042  +        sqlite3VdbeChangeToNoop(v, sSort.addrSortIndex);
  5026   5043         }
  5027   5044   
  5028   5045         /* Evaluate the current GROUP BY terms and store in b0, b1, b2...
  5029   5046         ** (b0 is memory location iBMem+0, b1 is iBMem+1, and so forth)
  5030   5047         ** Then compare the current GROUP BY terms against the GROUP BY terms
  5031   5048         ** from the previous row currently stored in a0, a1, a2...
  5032   5049         */

Changes to src/sqliteInt.h.

  2121   2121   #define WHERE_OMIT_OPEN_CLOSE  0x0010 /* Table cursors are already open */
  2122   2122   #define WHERE_FORCE_TABLE      0x0020 /* Do not use an index-only search */
  2123   2123   #define WHERE_ONETABLE_ONLY    0x0040 /* Only code the 1st table in pTabList */
  2124   2124   #define WHERE_AND_ONLY         0x0080 /* Don't use indices for OR terms */
  2125   2125   #define WHERE_GROUPBY          0x0100 /* pOrderBy is really a GROUP BY */
  2126   2126   #define WHERE_DISTINCTBY       0x0200 /* pOrderby is really a DISTINCT clause */
  2127   2127   #define WHERE_WANT_DISTINCT    0x0400 /* All output needs to be distinct */
         2128  +#define WHERE_SORTBYGROUP      0x0800 /* Support sqlite3WhereIsSorted() */
  2128   2129   
  2129   2130   /* Allowed return values from sqlite3WhereIsDistinct()
  2130   2131   */
  2131   2132   #define WHERE_DISTINCT_NOOP      0  /* DISTINCT keyword not used */
  2132   2133   #define WHERE_DISTINCT_UNIQUE    1  /* No duplicates */
  2133   2134   #define WHERE_DISTINCT_ORDERED   2  /* All duplicates are adjacent */
  2134   2135   #define WHERE_DISTINCT_UNORDERED 3  /* Duplicates are scattered */
................................................................................
  3088   3089   void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
  3089   3090   void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
  3090   3091   WhereInfo *sqlite3WhereBegin(Parse*,SrcList*,Expr*,ExprList*,ExprList*,u16,int);
  3091   3092   void sqlite3WhereEnd(WhereInfo*);
  3092   3093   u64 sqlite3WhereOutputRowCount(WhereInfo*);
  3093   3094   int sqlite3WhereIsDistinct(WhereInfo*);
  3094   3095   int sqlite3WhereIsOrdered(WhereInfo*);
         3096  +int sqlite3WhereIsSorted(WhereInfo*);
  3095   3097   int sqlite3WhereContinueLabel(WhereInfo*);
  3096   3098   int sqlite3WhereBreakLabel(WhereInfo*);
  3097   3099   int sqlite3WhereOkOnePass(WhereInfo*, int*);
  3098   3100   int sqlite3ExprCodeGetColumn(Parse*, Table*, int, int, int, u8);
  3099   3101   void sqlite3ExprCodeGetColumnOfTable(Vdbe*, Table*, int, int, int);
  3100   3102   void sqlite3ExprCodeMove(Parse*, int, int, int);
  3101   3103   void sqlite3ExprCacheStore(Parse*, int, int, int);

Changes to src/where.c.

  4792   4792   **   N>0:   N terms of the ORDER BY clause are satisfied
  4793   4793   **   N==0:  No terms of the ORDER BY clause are satisfied
  4794   4794   **   N<0:   Unknown yet how many terms of ORDER BY might be satisfied.   
  4795   4795   **
  4796   4796   ** Note that processing for WHERE_GROUPBY and WHERE_DISTINCTBY is not as
  4797   4797   ** strict.  With GROUP BY and DISTINCT the only requirement is that
  4798   4798   ** equivalent rows appear immediately adjacent to one another.  GROUP BY
  4799         -** and DISTINT do not require rows to appear in any particular order as long
         4799  +** and DISTINCT do not require rows to appear in any particular order as long
  4800   4800   ** as equivelent rows are grouped together.  Thus for GROUP BY and DISTINCT
  4801   4801   ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  4802   4802   ** pOrderBy terms must be matched in strict left-to-right order.
  4803   4803   */
  4804   4804   static i8 wherePathSatisfiesOrderBy(
  4805   4805     WhereInfo *pWInfo,    /* The WHERE clause */
  4806   4806     ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
................................................................................
  4961   4961            && j>=pLoop->u.btree.nEq
  4962   4962            && pIndex->pTable->aCol[iColumn].notNull==0
  4963   4963           ){
  4964   4964             isOrderDistinct = 0;
  4965   4965           }
  4966   4966   
  4967   4967           /* Find the ORDER BY term that corresponds to the j-th column
  4968         -        ** of the index and and mark that ORDER BY term off 
         4968  +        ** of the index and mark that ORDER BY term off 
  4969   4969           */
  4970   4970           bOnce = 1;
  4971   4971           isMatch = 0;
  4972   4972           for(i=0; bOnce && i<nOrderBy; i++){
  4973   4973             if( MASKBIT(i) & obSat ) continue;
  4974   4974             pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  4975   4975             testcase( wctrlFlags & WHERE_GROUPBY );
................................................................................
  5041   5041         if( (obSat&m)==m ) return i;
  5042   5042       }
  5043   5043       return 0;
  5044   5044     }
  5045   5045     return -1;
  5046   5046   }
  5047   5047   
         5048  +
         5049  +/*
         5050  +** If the WHERE_GROUPBY flag is set in the mask passed to sqlite3WhereBegin(),
         5051  +** the planner assumes that the specified pOrderBy list is actually a GROUP
         5052  +** BY clause - and so any order that groups rows as required satisfies the
         5053  +** request.
         5054  +**
         5055  +** Normally, in this case it is not possible for the caller to determine
         5056  +** whether or not the rows are really being delivered in sorted order, or
         5057  +** just in some other order that provides the required grouping. However,
         5058  +** if the WHERE_SORTBYGROUP flag is also passed to sqlite3WhereBegin(), then
         5059  +** this function may be called on the returned WhereInfo object. It returns
         5060  +** true if the rows really will be sorted in the specified order, or false
         5061  +** otherwise.
         5062  +**
         5063  +** For example, assuming:
         5064  +**
         5065  +**   CREATE INDEX i1 ON t1(x, Y);
         5066  +**
         5067  +** then
         5068  +**
         5069  +**   SELECT * FROM t1 GROUP BY x,y ORDER BY x,y;   -- IsSorted()==1
         5070  +**   SELECT * FROM t1 GROUP BY y,x ORDER BY y,x;   -- IsSorted()==0
         5071  +*/
         5072  +int sqlite3WhereIsSorted(WhereInfo *pWInfo){
         5073  +  assert( pWInfo->wctrlFlags & WHERE_GROUPBY );
         5074  +  assert( pWInfo->wctrlFlags & WHERE_SORTBYGROUP );
         5075  +  return pWInfo->sorted;
         5076  +}
         5077  +
  5048   5078   #ifdef WHERETRACE_ENABLED
  5049   5079   /* For debugging use only: */
  5050   5080   static const char *wherePathName(WherePath *pPath, int nLoop, WhereLoop *pLast){
  5051   5081     static char zName[65];
  5052   5082     int i;
  5053   5083     for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; }
  5054   5084     if( pLast ) zName[i++] = pLast->cId;
  5055   5085     zName[i] = 0;
  5056   5086     return zName;
  5057   5087   }
  5058   5088   #endif
  5059         -
  5060   5089   
  5061   5090   /*
  5062   5091   ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine
  5063   5092   ** attempts to find the lowest cost path that visits each WhereLoop
  5064   5093   ** once.  This path is then loaded into the pWInfo->a[].pWLoop fields.
  5065   5094   **
  5066   5095   ** Assume that the total number of output rows that will need to be sorted
................................................................................
  5334   5363           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  5335   5364         }
  5336   5365       }else{
  5337   5366         pWInfo->nOBSat = pFrom->isOrdered;
  5338   5367         if( pWInfo->nOBSat<0 ) pWInfo->nOBSat = 0;
  5339   5368         pWInfo->revMask = pFrom->revLoop;
  5340   5369       }
         5370  +    if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
         5371  +        && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr
         5372  +    ){
         5373  +      Bitmask notUsed = 0;
         5374  +      int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, 
         5375  +          pFrom, 0, nLoop-1, pFrom->aLoop[nLoop-1], &notUsed
         5376  +      );
         5377  +      assert( pWInfo->sorted==0 );
         5378  +      pWInfo->sorted = (nOrder==pWInfo->pOrderBy->nExpr);
         5379  +    }
  5341   5380     }
         5381  +
         5382  +
  5342   5383     pWInfo->nRowOut = pFrom->nRow;
  5343   5384   
  5344   5385     /* Free temporary memory and return success */
  5345   5386     sqlite3DbFree(db, pSpace);
  5346   5387     return SQLITE_OK;
  5347   5388   }
  5348   5389   

Changes to src/whereInt.h.

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

Added test/tkt-b75a9ca6b0.test.

            1  +# 2014 April 21
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +#
           12  +# Test that ticket [b75a9ca6b0] has been fixed.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +set testprefix tkt-b75a9ca6b0
           18  +
           19  +do_execsql_test 1 {
           20  +  CREATE TABLE t1 (x, y);
           21  +  INSERT INTO t1 VALUES (1, 3); 
           22  +  INSERT INTO t1 VALUES (2, 2);
           23  +  INSERT INTO t1 VALUES (3, 1);
           24  +}
           25  +
           26  +do_execsql_test 1.1 {
           27  +  CREATE INDEX i1 ON t1(x, y);
           28  +} 
           29  +
           30  +set idxscan {0 0 0 {SCAN TABLE t1 USING COVERING INDEX i1}}
           31  +set tblscan {0 0 0 {SCAN TABLE t1}}
           32  +set grpsort {0 0 0 {USE TEMP B-TREE FOR GROUP BY}}
           33  +set sort    {0 0 0 {USE TEMP B-TREE FOR ORDER BY}}
           34  +
           35  +foreach {tn q res eqp} [subst -nocommands {
           36  +  1 "SELECT * FROM t1 GROUP BY x, y ORDER BY x,y"
           37  +  {1 3  2 2  3 1} {$idxscan}
           38  +
           39  +  2 "SELECT * FROM t1 GROUP BY x, y ORDER BY x"
           40  +  {1 3  2 2  3 1} {$idxscan $sort}
           41  +
           42  +  3 "SELECT * FROM t1 GROUP BY y, x ORDER BY y, x"
           43  +  {3 1  2 2  1 3} {$idxscan $sort}
           44  +  
           45  +  4 "SELECT * FROM t1 GROUP BY x ORDER BY x"
           46  +  {1 3  2 2  3 1} {$idxscan}
           47  +
           48  +  5 "SELECT * FROM t1 GROUP BY y ORDER BY y"
           49  +  {3 1  2 2  1 3} {$tblscan $grpsort}
           50  +
           51  +  6 "SELECT * FROM t1 GROUP BY y ORDER BY x"
           52  +  {1 3  2 2  3 1} {$tblscan $grpsort $sort}
           53  +
           54  +  7 "SELECT * FROM t1 GROUP BY x, y ORDER BY x, y DESC"
           55  +  {1 3  2 2  3 1} {$idxscan $sort}
           56  +
           57  +  8 "SELECT * FROM t1 GROUP BY x, y ORDER BY x DESC, y DESC"
           58  +  {3 1  2 2  1 3} {$idxscan $sort}
           59  +
           60  +  9 "SELECT * FROM t1 GROUP BY x, y ORDER BY x ASC, y ASC"
           61  +  {1 3  2 2  3 1} {$idxscan}
           62  +
           63  +  10 "SELECT * FROM t1 GROUP BY x, y ORDER BY x COLLATE nocase, y"
           64  +  {1 3  2 2  3 1} {$idxscan $sort}
           65  +
           66  +}] {
           67  +  do_execsql_test 1.$tn.1 $q $res
           68  +  do_eqp_test     1.$tn.2 $q $eqp
           69  +}
           70  +
           71  +
           72  +finish_test
           73  +
           74  +
           75  +