Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -260,10 +260,12 @@ #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 */ @@ -2901,11 +2903,12 @@ */ 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 *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 */ @@ -2915,25 +2918,32 @@ 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( (p->aLevel[p->i-1].plan.wsFlags & WHERE_ORDERED)==0 ){ + 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 @@ -3071,23 +3081,32 @@ testcase( isEq==2 ); testcase( isEq==3 ); uniqueNotNull = 0; } } + if( seenRowid ){ + uniqueNotNull = 1; + }else if( uniqueNotNull==0 || inColumn ){ + 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( seenRowid || (uniqueNotNull && i>=pIdx->nColumn) ){ + if( uniqueNotNull ){ /* Advance j over additional ORDER BY terms associated with base */ WhereMaskSet *pMS = p->pWC->pMaskSet; Bitmask m = ~getMask(pMS, base); while( ja[j].pExpr)&m)==0 ){ j++; @@ -3367,16 +3386,18 @@ ** 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; - WHERETRACE((" --> before isSortingIndex: nPriorSat=%d\n",nPriorSat)); - pc.plan.nOBSat = isSortingIndex(p, pProbe, iCur, &bRev); - WHERETRACE((" --> after isSortingIndex: bRev=%d nOBSat=%d\n", - bRev, pc.plan.nOBSat)); + 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( nPriorSatwctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pParse->db, SQLITE_CoverIdxScan) ){ /* This index is not useful for indexing, but it is a covering index. ADDED test/orderby4.test Index: test/orderby4.test ================================================================== --- /dev/null +++ test/orderby4.test @@ -0,0 +1,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