/ Check-in [132339a1]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Forward port the skip-ahead-distinct branch which was abandoned for some reason that I do not recall. This port should have been achived by a merge of trunk into the previous head of skip-ahead-distinct, but that did not work. So I had to manually "rebase" the changes.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | skip-ahead-distinct
Files: files | file ages | folders
SHA3-256:132339a1fb0b9664df4d3eefbed6e77ef100ba95a91dcc622da7bd3fcdfcd6af
User & Date: drh 2017-04-13 01:19:30
Context
2017-04-13
13:01
Only use the skip-ahead-distinct optimization if the index has been analyzed and we know that a skip-head is likely to skip over at least 11 rows. The magic number 11 was determined by experimentation. check-in: 0cf16dec user: drh tags: skip-ahead-distinct
01:19
Forward port the skip-ahead-distinct branch which was abandoned for some reason that I do not recall. This port should have been achived by a merge of trunk into the previous head of skip-ahead-distinct, but that did not work. So I had to manually "rebase" the changes. check-in: 132339a1 user: drh tags: skip-ahead-distinct
00:12
Fix a regression caused by the fix for ticket [6c9b5514077fed34551f98e64c09a1] - control characters allowed in JSON. check-in: 8e7b6118 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  1686   1686       }else{
  1687   1687         Expr *pColExpr = p;  /* The expression that is the result column name */
  1688   1688         Table *pTab;         /* Table associated with this expression */
  1689   1689         while( pColExpr->op==TK_DOT ){
  1690   1690           pColExpr = pColExpr->pRight;
  1691   1691           assert( pColExpr!=0 );
  1692   1692         }
  1693         -      if( pColExpr->op==TK_COLUMN && ALWAYS(pColExpr->pTab!=0) ){
         1693  +      if( pColExpr->op==TK_COLUMN && pColExpr->pTab!=0 ){
  1694   1694           /* For columns use the column name name */
  1695   1695           int iCol = pColExpr->iColumn;
  1696   1696           pTab = pColExpr->pTab;
  1697   1697           if( iCol<0 ) iCol = pTab->iPKey;
  1698   1698           zName = iCol>=0 ? pTab->aCol[iCol].zName : "rowid";
  1699   1699         }else if( pColExpr->op==TK_ID ){
  1700   1700           assert( !ExprHasProperty(pColExpr, EP_IntValue) );

Changes to src/sqliteInt.h.

  1497   1497   #define SQLITE_DistinctOpt    0x0020   /* DISTINCT using indexes */
  1498   1498   #define SQLITE_CoverIdxScan   0x0040   /* Covering index scans */
  1499   1499   #define SQLITE_OrderByIdxJoin 0x0080   /* ORDER BY of joins via index */
  1500   1500   #define SQLITE_SubqCoroutine  0x0100   /* Evaluate subqueries as coroutines */
  1501   1501   #define SQLITE_Transitive     0x0200   /* Transitive constraints */
  1502   1502   #define SQLITE_OmitNoopJoin   0x0400   /* Omit unused tables in joins */
  1503   1503   #define SQLITE_Stat34         0x0800   /* Use STAT3 or STAT4 data */
         1504  +#define SQLITE_SkipAhead      0x1000   /* Skip ahead on DISTINCT */
  1504   1505   #define SQLITE_CursorHints    0x2000   /* Add OP_CursorHint opcodes */
  1505   1506   #define SQLITE_AllOpts        0xffff   /* All optimizations */
  1506   1507   
  1507   1508   /*
  1508   1509   ** Macros for testing whether or not optimizations are enabled or disabled.
  1509   1510   */
  1510   1511   #define OptimizationDisabled(db, mask)  (((db)->dbOptFlags&(mask))!=0)

Changes to src/where.c.

  4754   4754         assert( iIndexCur>=0 );
  4755   4755         if( op ){
  4756   4756           sqlite3VdbeAddOp3(v, op, iIndexCur, pIx->tnum, iDb);
  4757   4757           sqlite3VdbeSetP4KeyInfo(pParse, pIx);
  4758   4758           if( (pLoop->wsFlags & WHERE_CONSTRAINT)!=0
  4759   4759            && (pLoop->wsFlags & (WHERE_COLUMN_RANGE|WHERE_SKIPSCAN))==0
  4760   4760            && (pWInfo->wctrlFlags&WHERE_ORDERBY_MIN)==0
         4761  +         && pWInfo->eDistinct!=WHERE_DISTINCT_ORDERED
  4761   4762           ){
  4762   4763             sqlite3VdbeChangeP5(v, OPFLAG_SEEKEQ); /* Hint to COMDB2 */
  4763   4764           }
  4764   4765           VdbeComment((v, "%s", pIx->zName));
  4765   4766   #ifdef SQLITE_ENABLE_COLUMN_USED_MASK
  4766   4767           {
  4767   4768             u64 colUsed = 0;
................................................................................
  4844   4845     sqlite3ExprCacheClear(pParse);
  4845   4846     for(i=pWInfo->nLevel-1; i>=0; i--){
  4846   4847       int addr;
  4847   4848       pLevel = &pWInfo->a[i];
  4848   4849       pLoop = pLevel->pWLoop;
  4849   4850       sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  4850   4851       if( pLevel->op!=OP_Noop ){
  4851         -      sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  4852         -      sqlite3VdbeChangeP5(v, pLevel->p5);
  4853         -      VdbeCoverage(v);
  4854         -      VdbeCoverageIf(v, pLevel->op==OP_Next);
  4855         -      VdbeCoverageIf(v, pLevel->op==OP_Prev);
  4856         -      VdbeCoverageIf(v, pLevel->op==OP_VNext);
         4852  +#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
         4853  +      int n = -1;
         4854  +      int j, k, op;
         4855  +      int r1 = pParse->nMem+1;
         4856  +      if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED
         4857  +       && (pLoop->wsFlags & WHERE_INDEXED)!=0
         4858  +       && OptimizationEnabled(db, SQLITE_SkipAhead)
         4859  +      ){
         4860  +        /* This is the Skip-ahead optimization.  When doing a DISTINCT query
         4861  +        ** that has WHERE_DISTINCT_ORDERED, use OP_SkipGT/OP_SkipLT to skip
         4862  +        ** over all duplicate entries, rather than visiting all duplicates
         4863  +        ** using OP_Next/OP_Prev. */
         4864  +        ExprList *pX = pWInfo->pResultSet;
         4865  +        Index *pIdx = pLoop->u.btree.pIndex;
         4866  +        for(j=0; j<pX->nExpr; j++){
         4867  +          Expr *pE = sqlite3ExprSkipCollate(pX->a[j].pExpr);
         4868  +          if( pE->op==TK_COLUMN ){
         4869  +            if( pE->iTable!=pLevel->iTabCur ) continue;
         4870  +            k = 1+sqlite3ColumnOfIndex(pIdx, pE->iColumn);
         4871  +            if( k>n ) n = k;
         4872  +          }else if( pIdx->aColExpr ){
         4873  +            for(k=n+1; k<pIdx->nKeyCol; k++){
         4874  +              Expr *pI = pIdx->aColExpr->a[k].pExpr;
         4875  +              if( pI && sqlite3ExprCompare(pE,pI,0)<2 ){
         4876  +                n = k+1;
         4877  +                break;
         4878  +              }
         4879  +            }
         4880  +          }
         4881  +        }
         4882  +      }
         4883  +      if( n>0 ){
         4884  +        for(j=0; j<n; j++){
         4885  +          sqlite3VdbeAddOp3(v, OP_Column, pLevel->iIdxCur, j, r1+j);
         4886  +        }
         4887  +        pParse->nMem += n;
         4888  +        op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT;
         4889  +        k = sqlite3VdbeAddOp4Int(v, op, pLevel->iIdxCur, 0, r1, n);
         4890  +        VdbeCoverageIf(v, op==OP_SeekLT);
         4891  +        VdbeCoverageIf(v, op==OP_SeekGT);
         4892  +        sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2);
         4893  +        sqlite3VdbeJumpHere(v, k);
         4894  +      }else
         4895  +#endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
         4896  +      {
         4897  +        /* The common case: Advance to the next row */
         4898  +        sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
         4899  +        sqlite3VdbeChangeP5(v, pLevel->p5);
         4900  +        VdbeCoverage(v);
         4901  +        VdbeCoverageIf(v, pLevel->op==OP_Next);
         4902  +        VdbeCoverageIf(v, pLevel->op==OP_Prev);
         4903  +        VdbeCoverageIf(v, pLevel->op==OP_VNext);
         4904  +      }
  4857   4905       }
  4858   4906       if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  4859   4907         struct InLoop *pIn;
  4860   4908         int j;
  4861   4909         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  4862   4910         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  4863   4911           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);

Added test/distinct2.test.

            1  +# 2016-04-15
            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 script is DISTINCT queries using the skip-ahead 
           13  +# optimization.
           14  +#
           15  +
           16  +set testdir [file dirname $argv0]
           17  +source $testdir/tester.tcl
           18  +
           19  +set testprefix distinct2
           20  +
           21  +do_execsql_test 100 {
           22  +  CREATE TABLE t1(x INTEGER PRIMARY KEY);
           23  +  INSERT INTO t1 VALUES(0),(1),(2);
           24  +  CREATE TABLE t2 AS
           25  +     SELECT DISTINCT a.x AS aa, b.x AS bb
           26  +      FROM t1 a, t1 b;
           27  +  SELECT *, '|' FROM t2 ORDER BY aa, bb;
           28  +} {0 0 | 0 1 | 0 2 | 1 0 | 1 1 | 1 2 | 2 0 | 2 1 | 2 2 |}
           29  +do_execsql_test 110 {
           30  +  DROP TABLE t2;
           31  +  CREATE TABLE t2 AS
           32  +     SELECT DISTINCT a.x AS aa, b.x AS bb
           33  +       FROM t1 a, t1 b
           34  +      WHERE a.x IN t1 AND b.x IN t1;
           35  +  SELECT *, '|' FROM t2 ORDER BY aa, bb;
           36  +} {0 0 | 0 1 | 0 2 | 1 0 | 1 1 | 1 2 | 2 0 | 2 1 | 2 2 |}
           37  +do_execsql_test 120 {
           38  +  CREATE TABLE t102 (i0 TEXT UNIQUE NOT NULL);
           39  +  INSERT INTO t102 VALUES ('0'),('1'),('2');
           40  +  DROP TABLE t2;
           41  +  CREATE TABLE t2 AS
           42  +    SELECT DISTINCT * 
           43  +    FROM t102 AS t0 
           44  +    JOIN t102 AS t4 ON (t2.i0 IN t102)
           45  +    NATURAL JOIN t102 AS t3
           46  +    JOIN t102 AS t1 ON (t0.i0 IN t102)
           47  +    JOIN t102 AS t2 ON (t2.i0=+t0.i0 OR (t0.i0<>500 AND t2.i0=t1.i0));
           48  +  SELECT *, '|' FROM t2 ORDER BY 1, 2, 3, 4, 5;
           49  +} {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 |}
           50  +
           51  +do_execsql_test 400 {
           52  +  CREATE TABLE t4(a,b,c,d,e,f,g,h,i,j);
           53  +  INSERT INTO t4 VALUES(0,1,2,3,4,5,6,7,8,9);
           54  +  INSERT INTO t4 SELECT * FROM t4;
           55  +  INSERT INTO t4 SELECT * FROM t4;
           56  +  CREATE INDEX t4x ON t4(c,d,e);
           57  +  SELECT DISTINCT a,b,c FROM t4 WHERE a=0 AND b=1;
           58  +} {0 1 2}
           59  +do_execsql_test 410 {
           60  +  SELECT DISTINCT a,b,c,d FROM t4 WHERE a=0 AND b=1;
           61  +} {0 1 2 3}
           62  +do_execsql_test 411 {
           63  +  SELECT DISTINCT d,a,b,c FROM t4 WHERE a=0 AND b=1;
           64  +} {3 0 1 2}
           65  +do_execsql_test 420 {
           66  +  SELECT DISTINCT a,b,c,d,e FROM t4 WHERE a=0 AND b=1;
           67  +} {0 1 2 3 4}
           68  +do_execsql_test 430 {
           69  +  SELECT DISTINCT a,b,c,d,e,f FROM t4 WHERE a=0 AND b=1;
           70  +} {0 1 2 3 4 5}
           71  +
           72  +do_execsql_test 500 {
           73  +  CREATE TABLE t5(a INT, b INT);
           74  +  CREATE UNIQUE INDEX t5x ON t5(a+b);
           75  +  INSERT INTO t5(a,b) VALUES(0,0),(1,0),(1,1),(0,3);
           76  +  CREATE TEMP TABLE out AS SELECT DISTINCT a+b FROM t5;
           77  +  SELECT * FROM out ORDER BY 1;
           78  +} {0 1 2 3}
           79  +
           80  +do_execsql_test 600 {
           81  +  CREATE TABLE t6a(x INTEGER PRIMARY KEY);
           82  +  INSERT INTO t6a VALUES(1);
           83  +  CREATE TABLE t6b(y INTEGER PRIMARY KEY);
           84  +  INSERT INTO t6b VALUES(2),(3);
           85  +  SELECT DISTINCT x, x FROM t6a, t6b;
           86  +} {1 1}
           87  +
           88  +finish_test