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