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