Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | 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]. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
2936f7466e162dfb003bda26d35358d1 |
User & Date: | drh 2013-03-27 17:20:10.024 |
Context
2013-03-27
| ||
19:46 | Increment the version number to 3.7.16.1. (check-in: 7e32eb7b66 user: drh tags: trunk) | |
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: 2936f7466e user: drh tags: trunk) | |
16:42 | Restore additional ORDER BY optimizations that where broken by the recent ORDER BY fix. (Closed-Leaf check-in: c77ee6e20d 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: 322a5f086d user: drh tags: trunk) | |
Changes
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 3115 3116 3117 3118 3119 3120 | }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; /* Either the outer queries must generate rows where there are no two ** rows with the same values in all ORDER BY columns, or else this ** loop must generate just a single row of output. Example: Suppose ** the outer loops generate A=1 and A=1, and this loop generates B=3 ** and B=4. Then without the following test, ORDER BY A,B would ** generate the wrong order output: 1,3 1,4 1,3 1,4 */ 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; | > | | | | > | 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 | /* 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 */ | | > | 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 | ** 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 |