/ Check-in [990fe50c]
Login

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

Overview
Comment:Appears to work now. Needs test cases, more comments, and code optimization.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | orderby-limit
Files: files | file ages | folders
SHA1:990fe50c9182f74c9b54a12602c4c30d891273e6
User & Date: drh 2016-05-19 22:40:04
Context
2016-05-20
00:21
A few simple test cases for the ORDER BY LIMIT optimization. check-in: 08849eab user: drh tags: orderby-limit
2016-05-19
22:40
Appears to work now. Needs test cases, more comments, and code optimization. check-in: 990fe50c user: drh tags: orderby-limit
22:13
In a query with both ORDER BY and LIMIT, if the inner loop satisfies the ORDER BY then try to cut short each invocation of the inner loop once the LIMIT has been satisfied. This check-in is a partial implementation only. check-in: 852d1eda user: drh tags: orderby-limit
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/sqliteInt.h.

  2536   2536   #define WHERE_OR_SUBCLAUSE     0x0020 /* Processing a sub-WHERE as part of
  2537   2537                                         ** the OR optimization  */
  2538   2538   #define WHERE_GROUPBY          0x0040 /* pOrderBy is really a GROUP BY */
  2539   2539   #define WHERE_DISTINCTBY       0x0080 /* pOrderby is really a DISTINCT clause */
  2540   2540   #define WHERE_WANT_DISTINCT    0x0100 /* All output needs to be distinct */
  2541   2541   #define WHERE_SORTBYGROUP      0x0200 /* Support sqlite3WhereIsSorted() */
  2542   2542   #define WHERE_SEEK_TABLE       0x0400 /* Do not defer seeks on main table */
  2543         -                        /*     0x0800    not currently used */
         2543  +#define WHERE_ORDERBY_LIMIT    0x0800 /* ORDERBY+LIMIT on the inner loop */
  2544   2544                           /*     0x1000    not currently used */
  2545   2545                           /*     0x2000    not currently used */
  2546   2546   #define WHERE_USE_LIMIT        0x4000 /* Use the LIMIT in cost estimates */
  2547   2547                           /*     0x8000    not currently used */
  2548   2548   
  2549   2549   /* Allowed return values from sqlite3WhereIsDistinct()
  2550   2550   */

Changes to src/where.c.

  3258   3258   ** the pOrderBy terms can be matched in any order.  With ORDER BY, the 
  3259   3259   ** pOrderBy terms must be matched in strict left-to-right order.
  3260   3260   */
  3261   3261   static i8 wherePathSatisfiesOrderBy(
  3262   3262     WhereInfo *pWInfo,    /* The WHERE clause */
  3263   3263     ExprList *pOrderBy,   /* ORDER BY or GROUP BY or DISTINCT clause to check */
  3264   3264     WherePath *pPath,     /* The WherePath to check */
  3265         -  u16 wctrlFlags,       /* Might contain WHERE_GROUPBY or WHERE_DISTINCTBY */
         3265  +  u16 wctrlFlags,       /* WHERE_GROUPBY or _DISTINCTBY or _ORDERBY_LIMIT */
  3266   3266     u16 nLoop,            /* Number of entries in pPath->aLoop[] */
  3267   3267     WhereLoop *pLast,     /* Add this WhereLoop to the end of pPath->aLoop[] */
  3268   3268     Bitmask *pRevMask     /* OUT: Mask of WhereLoops to run in reverse order */
  3269   3269   ){
  3270   3270     u8 revSet;            /* True if rev is known */
  3271   3271     u8 rev;               /* Composite sort order */
  3272   3272     u8 revIdx;            /* Index sort order */
  3273   3273     u8 isOrderDistinct;   /* All prior WhereLoops are order-distinct */
  3274   3274     u8 distinctColumns;   /* True if the loop has UNIQUE NOT NULL columns */
  3275   3275     u8 isMatch;           /* iColumn matches a term of the ORDER BY clause */
         3276  +  u16 eqOpMask;         /* Allowed equality operators */
  3276   3277     u16 nKeyCol;          /* Number of key columns in pIndex */
  3277   3278     u16 nColumn;          /* Total number of ordered columns in the index */
  3278   3279     u16 nOrderBy;         /* Number terms in the ORDER BY clause */
  3279   3280     int iLoop;            /* Index of WhereLoop in pPath being processed */
  3280   3281     int i, j;             /* Loop counters */
  3281   3282     int iCur;             /* Cursor number for current WhereLoop */
  3282   3283     int iColumn;          /* A column number within table iCur */
................................................................................
  3319   3320     nOrderBy = pOrderBy->nExpr;
  3320   3321     testcase( nOrderBy==BMS-1 );
  3321   3322     if( nOrderBy>BMS-1 ) return 0;  /* Cannot optimize overly large ORDER BYs */
  3322   3323     isOrderDistinct = 1;
  3323   3324     obDone = MASKBIT(nOrderBy)-1;
  3324   3325     orderDistinctMask = 0;
  3325   3326     ready = 0;
         3327  +  eqOpMask = WO_EQ | WO_IS | WO_ISNULL;
         3328  +  if( wctrlFlags & WHERE_ORDERBY_LIMIT ) eqOpMask |= WO_IN;
  3326   3329     for(iLoop=0; isOrderDistinct && obSat<obDone && iLoop<=nLoop; iLoop++){
  3327   3330       if( iLoop>0 ) ready |= pLoop->maskSelf;
  3328         -    pLoop = iLoop<nLoop ? pPath->aLoop[iLoop] : pLast;
         3331  +    if( iLoop<nLoop ){
         3332  +      pLoop = pPath->aLoop[iLoop];
         3333  +      if( wctrlFlags & WHERE_ORDERBY_LIMIT ) continue;
         3334  +    }else{
         3335  +      pLoop = pLast;
         3336  +    }
  3329   3337       if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){
  3330   3338         if( pLoop->u.vtab.isOrdered ) obSat = obDone;
  3331   3339         break;
  3332   3340       }
  3333   3341       iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor;
  3334   3342   
  3335   3343       /* Mark off any ORDER BY term X that is a column in the table of
................................................................................
  3339   3347       */
  3340   3348       for(i=0; i<nOrderBy; i++){
  3341   3349         if( MASKBIT(i) & obSat ) continue;
  3342   3350         pOBExpr = sqlite3ExprSkipCollate(pOrderBy->a[i].pExpr);
  3343   3351         if( pOBExpr->op!=TK_COLUMN ) continue;
  3344   3352         if( pOBExpr->iTable!=iCur ) continue;
  3345   3353         pTerm = sqlite3WhereFindTerm(&pWInfo->sWC, iCur, pOBExpr->iColumn,
  3346         -                       ~ready, WO_EQ|WO_ISNULL|WO_IS, 0);
         3354  +                       ~ready, eqOpMask, 0);
  3347   3355         if( pTerm==0 ) continue;
  3348   3356         if( (pTerm->eOperator&(WO_EQ|WO_IS))!=0 && pOBExpr->iColumn>=0 ){
  3349   3357           const char *z1, *z2;
  3350   3358           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr);
  3351   3359           if( !pColl ) pColl = db->pDfltColl;
  3352   3360           z1 = pColl->zName;
  3353   3361           pColl = sqlite3ExprCollSeq(pWInfo->pParse, pTerm->pExpr);
................................................................................
  3379   3387         ** that are not constrained by == or IN.
  3380   3388         */
  3381   3389         rev = revSet = 0;
  3382   3390         distinctColumns = 0;
  3383   3391         for(j=0; j<nColumn; j++){
  3384   3392           u8 bOnce;   /* True to run the ORDER BY search loop */
  3385   3393   
  3386         -        /* Skip over == and IS NULL terms */
         3394  +        /* Skip over == and IS and ISNULL terms.
         3395  +        ** (Also skip IN terms when doing WHERE_ORDERBY_LIMIT processing)
         3396  +        */
  3387   3397           if( j<pLoop->u.btree.nEq
  3388   3398            && pLoop->nSkip==0
  3389         -         && ((i = pLoop->aLTerm[j]->eOperator) & (WO_EQ|WO_ISNULL|WO_IS))!=0
         3399  +         && ((i = pLoop->aLTerm[j]->eOperator) & eqOpMask)!=0
  3390   3400           ){
  3391   3401             if( i & WO_ISNULL ){
  3392   3402               testcase( isOrderDistinct );
  3393   3403               isOrderDistinct = 0;
  3394   3404             }
  3395   3405             continue;  
  3396   3406           }
................................................................................
  3909   3919           pWInfo->eDistinct = WHERE_DISTINCT_ORDERED;
  3910   3920         }
  3911   3921       }else{
  3912   3922         pWInfo->nOBSat = pFrom->isOrdered;
  3913   3923         pWInfo->revMask = pFrom->revLoop;
  3914   3924         if( pWInfo->nOBSat<=0 ){
  3915   3925           pWInfo->nOBSat = 0;
         3926  +        if( nLoop>0 ){
         3927  +          Bitmask m;
         3928  +          int rc = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom,
         3929  +                      WHERE_ORDERBY_LIMIT, nLoop-1, pFrom->aLoop[nLoop-1], &m);
         3930  +          if( rc==pWInfo->pOrderBy->nExpr ){
         3931  +            pWInfo->bOrderedInnerLoop = 1;
         3932  +            pWInfo->revMask = m;
         3933  +          }
         3934  +        }
  3916   3935         }
  3917   3936       }
  3918   3937       if( (pWInfo->wctrlFlags & WHERE_SORTBYGROUP)
  3919   3938           && pWInfo->nOBSat==pWInfo->pOrderBy->nExpr && nLoop>0
  3920   3939       ){
  3921   3940         Bitmask revMask = 0;
  3922   3941         int nOrder = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy,