/ Changes On Branch orderby-fix
Login

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

Changes In Branch orderby-fix Excluding Merge-Ins

This is equivalent to a diff from 322a5f08 to c77ee6e2

2013-03-27
17:20
In order to optimize out the ORDER BY clause, outer loops must generate values for ORDER BY terms that are unique or else the inner loops must generate no more than a single row. Fix for ticket [a179fe7465]. (check-in: 2936f746 user: drh tags: trunk)
16:42
Restore additional ORDER BY optimizations that where broken by the recent ORDER BY fix. (Closed-Leaf check-in: c77ee6e2 user: drh tags: orderby-fix)
16:05
Improved optimization of ORDER BY. (check-in: 97e5c70f user: drh tags: orderby-fix)
15:04
A fix and test-case for the ORDER BY problem identified by ticket [a179fe7465]. This change causes sorting to occur in some cases where it is not strictly necessary. Further work is needed to avoid those extra sorts. (check-in: 488089e6 user: drh tags: orderby-fix)
03:15
Candidate fix for ticket [6bfb98dfc0c]: Make sure invalid cursors drop all references to database pages prior to doing any insert or update. (check-in: 322a5f08 user: drh tags: trunk)
2013-03-25
12:02
Add a second test for [38b1ae018f]. (check-in: 5062db67 user: dan tags: trunk)

Changes to src/where.c.

   258    258   #define WHERE_BTM_LIMIT    0x00200000  /* x>EXPR or x>=EXPR constraint */
   259    259   #define WHERE_BOTH_LIMIT   0x00300000  /* Both x>EXPR and x<EXPR */
   260    260   #define WHERE_IDX_ONLY     0x00400000  /* Use index only - omit table */
   261    261   #define WHERE_ORDERED      0x00800000  /* Output will appear in correct order */
   262    262   #define WHERE_REVERSE      0x01000000  /* Scan in reverse order */
   263    263   #define WHERE_UNIQUE       0x02000000  /* Selects no more than one row */
   264    264   #define WHERE_ALL_UNIQUE   0x04000000  /* This and all prior have one row */
          265  +#define WHERE_OB_UNIQUE    0x00004000  /* Values in ORDER BY columns are 
          266  +                                       ** different for every output row */
   265    267   #define WHERE_VIRTUALTABLE 0x08000000  /* Use virtual-table processing */
   266    268   #define WHERE_MULTI_OR     0x10000000  /* OR using multiple indices */
   267    269   #define WHERE_TEMP_INDEX   0x20000000  /* Uses an ephemeral index */
   268    270   #define WHERE_DISTINCT     0x40000000  /* Correct order for DISTINCT */
   269    271   #define WHERE_COVER_SCAN   0x80000000  /* Full scan of a covering index */
   270    272   
   271    273   /*
................................................................................
  2899   2901   ** The *pbRev value is set to 0 order 1 depending on whether or not
  2900   2902   ** pIdx should be run in the forward order or in reverse order.
  2901   2903   */
  2902   2904   static int isSortingIndex(
  2903   2905     WhereBestIdx *p,    /* Best index search context */
  2904   2906     Index *pIdx,        /* The index we are testing */
  2905   2907     int base,           /* Cursor number for the table to be sorted */
  2906         -  int *pbRev          /* Set to 1 for reverse-order scan of pIdx */
         2908  +  int *pbRev,         /* Set to 1 for reverse-order scan of pIdx */
         2909  +  int *pbObUnique     /* ORDER BY column values will different in every row */
  2907   2910   ){
  2908   2911     int i;                        /* Number of pIdx terms used */
  2909   2912     int j;                        /* Number of ORDER BY terms satisfied */
  2910   2913     int sortOrder = 2;            /* 0: forward.  1: backward.  2: unknown */
  2911   2914     int nTerm;                    /* Number of ORDER BY terms */
  2912   2915     struct ExprList_item *pOBItem;/* A term of the ORDER BY clause */
  2913   2916     Table *pTab = pIdx->pTable;   /* Table that owns index pIdx */
  2914   2917     ExprList *pOrderBy;           /* The ORDER BY clause */
  2915   2918     Parse *pParse = p->pParse;    /* Parser context */
  2916   2919     sqlite3 *db = pParse->db;     /* Database connection */
  2917   2920     int nPriorSat;                /* ORDER BY terms satisfied by outer loops */
  2918   2921     int seenRowid = 0;            /* True if an ORDER BY rowid term is seen */
  2919   2922     int uniqueNotNull;            /* pIdx is UNIQUE with all terms are NOT NULL */
         2923  +  int outerObUnique;            /* Outer loops generate different values in
         2924  +                                ** every row for the ORDER BY columns */
  2920   2925   
  2921   2926     if( p->i==0 ){
  2922   2927       nPriorSat = 0;
         2928  +    outerObUnique = 1;
  2923   2929     }else{
         2930  +    u32 wsFlags = p->aLevel[p->i-1].plan.wsFlags;
  2924   2931       nPriorSat = p->aLevel[p->i-1].plan.nOBSat;
  2925         -    if( (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){
         2932  +    if( (wsFlags & WHERE_ORDERED)==0 ){
  2926   2933         /* This loop cannot be ordered unless the next outer loop is
  2927   2934         ** also ordered */
  2928   2935         return nPriorSat;
  2929   2936       }
  2930   2937       if( OptimizationDisabled(db, SQLITE_OrderByIdxJoin) ){
  2931   2938         /* Only look at the outer-most loop if the OrderByIdxJoin
  2932   2939         ** optimization is disabled */
  2933   2940         return nPriorSat;
  2934   2941       }
         2942  +    testcase( wsFlags & WHERE_OB_UNIQUE );
         2943  +    testcase( wsFlags & WHERE_ALL_UNIQUE );
         2944  +    outerObUnique = (wsFlags & (WHERE_OB_UNIQUE|WHERE_ALL_UNIQUE))!=0;
  2935   2945     }
  2936   2946     pOrderBy = p->pOrderBy;
  2937   2947     assert( pOrderBy!=0 );
  2938   2948     if( pIdx->bUnordered ){
  2939   2949       /* Hash indices (indicated by the "unordered" tag on sqlite_stat1) cannot
  2940   2950       ** be used for sorting */
  2941   2951       return nPriorSat;
................................................................................
  3069   3079       }else if( pTab->aCol[iColumn].notNull==0 && isEq!=1 ){
  3070   3080         testcase( isEq==0 );
  3071   3081         testcase( isEq==2 );
  3072   3082         testcase( isEq==3 );
  3073   3083         uniqueNotNull = 0;
  3074   3084       }
  3075   3085     }
         3086  +  if( seenRowid ){
         3087  +    uniqueNotNull = 1;
         3088  +  }else if( uniqueNotNull==0 || i<pIdx->nColumn ){
         3089  +    uniqueNotNull = 0;
         3090  +  }
  3076   3091   
  3077   3092     /* If we have not found at least one ORDER BY term that matches the
  3078   3093     ** index, then show no progress. */
  3079   3094     if( pOBItem==&pOrderBy->a[nPriorSat] ) return nPriorSat;
  3080   3095   
         3096  +  /* */  
         3097  +  if( outerObUnique==0 && uniqueNotNull==0 ) return nPriorSat;
         3098  +  *pbObUnique = uniqueNotNull;
         3099  +
  3081   3100     /* Return the necessary scan order back to the caller */
  3082   3101     *pbRev = sortOrder & 1;
  3083   3102   
  3084   3103     /* If there was an "ORDER BY rowid" term that matched, or it is only
  3085   3104     ** possible for a single row from this table to match, then skip over
  3086   3105     ** any additional ORDER BY terms dealing with this table.
  3087   3106     */
  3088         -  if( seenRowid || (uniqueNotNull && i>=pIdx->nColumn) ){
         3107  +  if( uniqueNotNull ){
  3089   3108       /* Advance j over additional ORDER BY terms associated with base */
  3090   3109       WhereMaskSet *pMS = p->pWC->pMaskSet;
  3091   3110       Bitmask m = ~getMask(pMS, base);
  3092   3111       while( j<nTerm && (exprTableUsage(pMS, pOrderBy->a[j].pExpr)&m)==0 ){
  3093   3112         j++;
  3094   3113       }
  3095   3114     }
................................................................................
  3365   3384       /* If there is an ORDER BY clause and the index being considered will
  3366   3385       ** naturally scan rows in the required order, set the appropriate flags
  3367   3386       ** in pc.plan.wsFlags. Otherwise, if there is an ORDER BY clause but
  3368   3387       ** the index will scan rows in a different order, set the bSort
  3369   3388       ** variable.  */
  3370   3389       if( bSort && (pSrc->jointype & JT_LEFT)==0 ){
  3371   3390         int bRev = 2;
  3372         -      WHERETRACE(("      --> before isSortingIndex: nPriorSat=%d\n",nPriorSat));
  3373         -      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev);
  3374         -      WHERETRACE(("      --> after  isSortingIndex: bRev=%d nOBSat=%d\n",
  3375         -                  bRev, pc.plan.nOBSat));
         3391  +      int bObUnique = 0;
         3392  +      WHERETRACE(("      --> before isSortIndex: nPriorSat=%d\n",nPriorSat));
         3393  +      pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev, &bObUnique);
         3394  +      WHERETRACE(("      --> after  isSortIndex: bRev=%d bObU=%d nOBSat=%d\n",
         3395  +                  bRev, bObUnique, pc.plan.nOBSat));
  3376   3396         if( nPriorSat<pc.plan.nOBSat || (pc.plan.wsFlags & WHERE_ALL_UNIQUE)!=0 ){
  3377   3397           pc.plan.wsFlags |= WHERE_ORDERED;
         3398  +        if( bObUnique ) pc.plan.wsFlags |= WHERE_OB_UNIQUE;
  3378   3399         }
  3379   3400         if( nOrderBy==pc.plan.nOBSat ){
  3380   3401           bSort = 0;
  3381   3402           pc.plan.wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE;
  3382   3403         }
  3383   3404         if( bRev & 1 ) pc.plan.wsFlags |= WHERE_REVERSE;
  3384   3405       }
................................................................................
  3464   3485       ** on one page and hence more pages have to be fetched.
  3465   3486       **
  3466   3487       ** The ANALYZE command and the sqlite_stat1 and sqlite_stat3 tables do
  3467   3488       ** not give us data on the relative sizes of table and index records.
  3468   3489       ** So this computation assumes table records are about twice as big
  3469   3490       ** as index records
  3470   3491       */
  3471         -    if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED))==WHERE_IDX_ONLY
         3492  +    if( (pc.plan.wsFlags&~(WHERE_REVERSE|WHERE_ORDERED|WHERE_OB_UNIQUE))
         3493  +                                                              ==WHERE_IDX_ONLY
  3472   3494        && (pWC->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  3473   3495        && sqlite3GlobalConfig.bUseCis
  3474   3496        && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan)
  3475   3497       ){
  3476   3498         /* This index is not useful for indexing, but it is a covering index.
  3477   3499         ** A full-scan of the index might be a little faster than a full-scan
  3478   3500         ** of the table, so give this case a cost slightly less than a table

Added test/orderby4.test.

            1  +# 2013 March 26
            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  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this file is testing that the optimizations that disable
           13  +# ORDER BY clauses work correctly on multi-value primary keys and
           14  +# unique indices when only some prefix of the terms in the key are
           15  +# used.  See ticket http://www.sqlite.org/src/info/a179fe74659
           16  +#
           17  +
           18  +
           19  +set testdir [file dirname $argv0]
           20  +source $testdir/tester.tcl
           21  +set ::testprefix orderby4
           22  +
           23  +# Generate test data for a join.  Verify that the join gets the
           24  +# correct answer.
           25  +#
           26  +do_execsql_test 1.1 {
           27  +  CREATE TABLE t1(a, b, PRIMARY KEY(a,b));
           28  +  INSERT INTO t1 VALUES(1,1),(1,2);
           29  +  CREATE TABLE t2(x, y, PRIMARY KEY(x,y));
           30  +  INSERT INTO t2 VALUES(3,3),(4,4);
           31  +  SELECT a, x FROM t1, t2 ORDER BY 1, 2;
           32  +} {1 3 1 3 1 4 1 4}
           33  +do_execsql_test 1.2 {
           34  +  SELECT a, x FROM t1 CROSS JOIN t2 ORDER BY 1, 2;
           35  +} {1 3 1 3 1 4 1 4}
           36  +do_execsql_test 1.3 {
           37  +  SELECT a, x FROM t2 CROSS JOIN t1 ORDER BY 1, 2;
           38  +} {1 3 1 3 1 4 1 4}
           39  +
           40  +do_execsql_test 2.1 {
           41  +  CREATE TABLE t3(a);
           42  +  INSERT INTO t3 VALUES(1),(1);
           43  +  CREATE INDEX t3a ON t3(a);
           44  +  CREATE TABLE t4(x);
           45  +  INSERT INTO t4 VALUES(3),(4);
           46  +  CREATE INDEX t4x ON t4(x);
           47  +  SELECT a, x FROM t3, t4 ORDER BY 1, 2;
           48  +} {1 3 1 3 1 4 1 4}
           49  +do_execsql_test 2.2 {
           50  +  SELECT a, x FROM t3 CROSS JOIN t4 ORDER BY 1, 2;
           51  +} {1 3 1 3 1 4 1 4}
           52  +do_execsql_test 2.3 {
           53  +  SELECT a, x FROM t4 CROSS JOIN t3 ORDER BY 1, 2;
           54  +} {1 3 1 3 1 4 1 4}
           55  +
           56  +finish_test