Index: src/select.c ================================================================== --- src/select.c +++ src/select.c @@ -1688,11 +1688,11 @@ Table *pTab; /* Table associated with this expression */ while( pColExpr->op==TK_DOT ){ pColExpr = pColExpr->pRight; assert( pColExpr!=0 ); } - if( pColExpr->op==TK_COLUMN && ALWAYS(pColExpr->pTab!=0) ){ + if( pColExpr->op==TK_COLUMN && pColExpr->pTab!=0 ){ /* For columns use the column name name */ int iCol = pColExpr->iColumn; pTab = pColExpr->pTab; if( iCol<0 ) iCol = pTab->iPKey; zName = iCol>=0 ? pTab->aCol[iCol].zName : "rowid"; Index: src/where.c ================================================================== --- src/where.c +++ src/where.c @@ -3435,11 +3435,11 @@ whereLoopClear(db, pNew); return rc; } /* -** Examine a WherePath (with the addition of the extra WhereLoop of the 5th +** Examine a WherePath (with the addition of the extra WhereLoop of the 6th ** parameters) to see if it outputs rows in the requested ORDER BY ** (or GROUP BY) without requiring a separate sort operation. Return N: ** ** N>0: N terms of the ORDER BY clause are satisfied ** N==0: No terms of the ORDER BY clause are satisfied @@ -3530,10 +3530,12 @@ pLoop = pLast; } if( pLoop->wsFlags & WHERE_VIRTUALTABLE ){ if( pLoop->u.vtab.isOrdered ) obSat = obDone; break; + }else{ + pLoop->u.btree.nIdxCol = 0; } iCur = pWInfo->pTabList->a[pLoop->iTab].iCursor; /* Mark off any ORDER BY term X that is a column in the table of ** the current loop for which there is term in the WHERE @@ -3675,10 +3677,11 @@ if( iColumn>=0 ){ pColl = sqlite3ExprCollSeq(pWInfo->pParse, pOrderBy->a[i].pExpr); if( !pColl ) pColl = db->pDfltColl; if( sqlite3StrICmp(pColl->zName, pIndex->azColl[j])!=0 ) continue; } + pLoop->u.btree.nIdxCol = j+1; isMatch = 1; break; } if( isMatch && (wctrlFlags & WHERE_GROUPBY)==0 ){ /* Make sure the sort order is compatible in an ORDER BY clause. @@ -4756,10 +4759,11 @@ sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb); sqlite3VdbeSetP4KeyInfo(pParse, pIx); if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0 && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0 && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0 + && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED ){ sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */ } VdbeComment((v, "%s", pIx->zName)); #ifdef SQLITE_ENABLE_COLUMN_USED_MASK @@ -4844,18 +4848,47 @@ sqlite3ExprCacheClear(pParse); for(i=pWInfo->nLevel-1; i>=0; i--){ int addr; pLevel = &pWInfo->a[i]; pLoop = pLevel->pWLoop; - sqlite3VdbeResolveLabel(v, pLevel->addrCont); if( pLevel->op!=OP_Noop ){ +#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT + int addrSeek = 0; + Index *pIdx; + int n; + if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED + && (pLoop->wsFlags & WHERE_INDEXED)!=0 + && (pIdx = pLoop->u.btree.pIndex)->hasStat1 + && (n = pLoop->u.btree.nIdxCol)>0 + && pIdx->aiRowLogEst[n]>=36 + ){ + int r1 = pParse->nMem+1; + int j, op; + for(j=0; jiIdxCur, j, r1+j); + } + pParse->nMem += n+1; + op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT; + addrSeek = sqlite3VdbeAddOp4Int(v, op, pLevel->iIdxCur, 0, r1, n); + VdbeCoverageIf(v, op==OP_SeekLT); + VdbeCoverageIf(v, op==OP_SeekGT); + sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2); + } +#endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */ + /* The common case: Advance to the next row */ + sqlite3VdbeResolveLabel(v, pLevel->addrCont); sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3); sqlite3VdbeChangeP5(v, pLevel->p5); VdbeCoverage(v); VdbeCoverageIf(v, pLevel->op==OP_Next); VdbeCoverageIf(v, pLevel->op==OP_Prev); VdbeCoverageIf(v, pLevel->op==OP_VNext); +#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT + if( addrSeek ) sqlite3VdbeJumpHere(v, addrSeek); +#endif + }else{ + sqlite3VdbeResolveLabel(v, pLevel->addrCont); } if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){ struct InLoop *pIn; int j; sqlite3VdbeResolveLabel(v, pLevel->addrNxt); Index: src/whereInt.h ================================================================== --- src/whereInt.h +++ src/whereInt.h @@ -122,10 +122,11 @@ union { struct { /* Information for internal btree tables */ u16 nEq; /* Number of equality constraints */ u16 nBtm; /* Size of BTM vector */ u16 nTop; /* Size of TOP vector */ + u16 nIdxCol; /* Index column used for ORDER BY */ Index *pIndex; /* Index used, or NULL */ } btree; struct { /* Information for virtual tables */ int idxNum; /* Index number */ u8 needFree; /* True if sqlite3_free(idxStr) is needed */ ADDED test/distinct2.test Index: test/distinct2.test ================================================================== --- /dev/null +++ test/distinct2.test @@ -0,0 +1,183 @@ +# 2016-04-15 +# +# 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 script is DISTINCT queries using the skip-ahead +# optimization. +# + +set testdir [file dirname $argv0] +source $testdir/tester.tcl + +set testprefix distinct2 + +do_execsql_test 100 { + CREATE TABLE t1(x INTEGER PRIMARY KEY); + INSERT INTO t1 VALUES(0),(1),(2); + CREATE TABLE t2 AS + SELECT DISTINCT a.x AS aa, b.x AS bb + FROM t1 a, t1 b; + SELECT *, '|' FROM t2 ORDER BY aa, bb; +} {0 0 | 0 1 | 0 2 | 1 0 | 1 1 | 1 2 | 2 0 | 2 1 | 2 2 |} +do_execsql_test 110 { + DROP TABLE t2; + CREATE TABLE t2 AS + SELECT DISTINCT a.x AS aa, b.x AS bb + FROM t1 a, t1 b + WHERE a.x IN t1 AND b.x IN t1; + SELECT *, '|' FROM t2 ORDER BY aa, bb; +} {0 0 | 0 1 | 0 2 | 1 0 | 1 1 | 1 2 | 2 0 | 2 1 | 2 2 |} +do_execsql_test 120 { + CREATE TABLE t102 (i0 TEXT UNIQUE NOT NULL); + INSERT INTO t102 VALUES ('0'),('1'),('2'); + DROP TABLE t2; + CREATE TABLE t2 AS + SELECT DISTINCT * + FROM t102 AS t0 + JOIN t102 AS t4 ON (t2.i0 IN t102) + NATURAL JOIN t102 AS t3 + JOIN t102 AS t1 ON (t0.i0 IN t102) + JOIN t102 AS t2 ON (t2.i0=+t0.i0 OR (t0.i0<>500 AND t2.i0=t1.i0)); + SELECT *, '|' FROM t2 ORDER BY 1, 2, 3, 4, 5; +} {0 0 0 0 | 0 0 1 0 | 0 0 1 1 | 0 0 2 0 | 0 0 2 2 | 0 1 0 0 | 0 1 1 0 | 0 1 1 1 | 0 1 2 0 | 0 1 2 2 | 0 2 0 0 | 0 2 1 0 | 0 2 1 1 | 0 2 2 0 | 0 2 2 2 | 1 0 0 0 | 1 0 0 1 | 1 0 1 1 | 1 0 2 1 | 1 0 2 2 | 1 1 0 0 | 1 1 0 1 | 1 1 1 1 | 1 1 2 1 | 1 1 2 2 | 1 2 0 0 | 1 2 0 1 | 1 2 1 1 | 1 2 2 1 | 1 2 2 2 | 2 0 0 0 | 2 0 0 2 | 2 0 1 1 | 2 0 1 2 | 2 0 2 2 | 2 1 0 0 | 2 1 0 2 | 2 1 1 1 | 2 1 1 2 | 2 1 2 2 | 2 2 0 0 | 2 2 0 2 | 2 2 1 1 | 2 2 1 2 | 2 2 2 2 |} + +do_execsql_test 400 { + CREATE TABLE t4(a,b,c,d,e,f,g,h,i,j); + INSERT INTO t4 VALUES(0,1,2,3,4,5,6,7,8,9); + INSERT INTO t4 SELECT * FROM t4; + INSERT INTO t4 SELECT * FROM t4; + CREATE INDEX t4x ON t4(c,d,e); + SELECT DISTINCT a,b,c FROM t4 WHERE a=0 AND b=1; +} {0 1 2} +do_execsql_test 410 { + SELECT DISTINCT a,b,c,d FROM t4 WHERE a=0 AND b=1; +} {0 1 2 3} +do_execsql_test 411 { + SELECT DISTINCT d,a,b,c FROM t4 WHERE a=0 AND b=1; +} {3 0 1 2} +do_execsql_test 420 { + SELECT DISTINCT a,b,c,d,e FROM t4 WHERE a=0 AND b=1; +} {0 1 2 3 4} +do_execsql_test 430 { + SELECT DISTINCT a,b,c,d,e,f FROM t4 WHERE a=0 AND b=1; +} {0 1 2 3 4 5} + +do_execsql_test 500 { + CREATE TABLE t5(a INT, b INT); + CREATE UNIQUE INDEX t5x ON t5(a+b); + INSERT INTO t5(a,b) VALUES(0,0),(1,0),(1,1),(0,3); + CREATE TEMP TABLE out AS SELECT DISTINCT a+b FROM t5; + SELECT * FROM out ORDER BY 1; +} {0 1 2 3} + +do_execsql_test 600 { + CREATE TABLE t6a(x INTEGER PRIMARY KEY); + INSERT INTO t6a VALUES(1); + CREATE TABLE t6b(y INTEGER PRIMARY KEY); + INSERT INTO t6b VALUES(2),(3); + SELECT DISTINCT x, x FROM t6a, t6b; +} {1 1} + +do_execsql_test 700 { + CREATE TABLE t7(a, b, c); + WITH s(i) AS ( + SELECT 1 UNION ALL SELECT i+1 FROM s WHERE (i+1)<200 + ) + INSERT INTO t7 SELECT i/100, i/50, i FROM s; +} +do_execsql_test 710 { + SELECT DISTINCT a, b FROM t7; +} { + 0 0 0 1 + 1 2 1 3 +} +do_execsql_test 720 { + SELECT DISTINCT a, b+1 FROM t7; +} { + 0 1 0 2 + 1 3 1 4 +} +do_execsql_test 730 { + CREATE INDEX i7 ON t7(a, b+1); + ANALYZE; + SELECT DISTINCT a, b+1 FROM t7; +} { + 0 1 0 2 + 1 3 1 4 +} + +do_execsql_test 800 { + CREATE TABLE t8(a, b, c); + WITH s(i) AS ( + SELECT 1 UNION ALL SELECT i+1 FROM s WHERE (i+1)<100 + ) + INSERT INTO t8 SELECT i/40, i/20, i/40 FROM s; +} + +do_execsql_test 820 { + SELECT DISTINCT a, b, c FROM t8; +} { + 0 0 0 0 1 0 + 1 2 1 1 3 1 + 2 4 2 +} + +do_execsql_test 820 { + SELECT DISTINCT a, b, c FROM t8 WHERE b=3; +} {1 3 1} + +do_execsql_test 830 { + CREATE INDEX i8 ON t8(a, c); + ANALYZE; + SELECT DISTINCT a, b, c FROM t8 WHERE b=3; +} {1 3 1} + +do_execsql_test 900 { + CREATE TABLE t9(v); + INSERT INTO t9 VALUES + ('abcd'), ('Abcd'), ('aBcd'), ('ABcd'), ('abCd'), ('AbCd'), ('aBCd'), + ('ABCd'), ('abcD'), ('AbcD'), ('aBcD'), ('ABcD'), ('abCD'), ('AbCD'), + ('aBCD'), ('ABCD'), + ('wxyz'), ('Wxyz'), ('wXyz'), ('WXyz'), ('wxYz'), ('WxYz'), ('wXYz'), + ('WXYz'), ('wxyZ'), ('WxyZ'), ('wXyZ'), ('WXyZ'), ('wxYZ'), ('WxYZ'), + ('wXYZ'), ('WXYZ'); +} + +do_execsql_test 910 { + SELECT DISTINCT v COLLATE NOCASE, v FROM t9 ORDER BY +v; +} { + ABCD ABCD ABCd ABCd ABcD ABcD ABcd ABcd AbCD + AbCD AbCd AbCd AbcD AbcD Abcd Abcd + WXYZ WXYZ WXYz WXYz WXyZ WXyZ WXyz WXyz WxYZ + WxYZ WxYz WxYz WxyZ WxyZ Wxyz Wxyz + aBCD aBCD aBCd aBCd aBcD aBcD aBcd aBcd abCD + abCD abCd abCd abcD abcD abcd abcd + wXYZ wXYZ wXYz wXYz wXyZ wXyZ wXyz wXyz wxYZ + wxYZ wxYz wxYz wxyZ wxyZ wxyz wxyz +} + +do_execsql_test 920 { + CREATE INDEX i9 ON t9(v COLLATE NOCASE, v); + ANALYZE; + + SELECT DISTINCT v COLLATE NOCASE, v FROM t9 ORDER BY +v; +} { + ABCD ABCD ABCd ABCd ABcD ABcD ABcd ABcd AbCD + AbCD AbCd AbCd AbcD AbcD Abcd Abcd + WXYZ WXYZ WXYz WXYz WXyZ WXyZ WXyz WXyz WxYZ + WxYZ WxYz WxYz WxyZ WxyZ Wxyz Wxyz + aBCD aBCD aBCd aBCd aBcD aBcD aBcd aBcd abCD + abCD abCd abCd abcD abcD abcd abcd + wXYZ wXYZ wXYz wXYz wXyZ wXyZ wXyz wXyz wxYZ + wxYZ wxYz wxYz wxyZ wxyZ wxyz wxyz +} + + +finish_test