/ Check-in [70ac9ea1]
Login

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

Overview
Comment:New test cases and minor fixes for the optimization on this branch.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | skip-ahead-distinct
Files: files | file ages | folders
SHA3-256: 70ac9ea1a6cb2f4906f00f1a04f668e5ba5eeed8d4d0fa4be57a9c9eb0683697
User & Date: dan 2017-04-13 18:33:33
Context
2017-04-13
19:48
Simplification of the skip-ahead-distinct logic. There is still an issue with handling COLLATE. check-in: 57c5173b user: drh tags: skip-ahead-distinct
18:33
New test cases and minor fixes for the optimization on this branch. check-in: 70ac9ea1 user: dan tags: skip-ahead-distinct
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
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to src/where.c.

4843
4844
4845
4846
4847
4848
4849
4850
4851
4852
4853
4854
4855
4856
4857
....
4863
4864
4865
4866
4867
4868
4869



4870
4871

4872





4873
4874
4875
4876
4877
4878
4879
4880
4881

4882
4883
4884
4885
4886
4887
4888
....
4891
4892
4893
4894
4895
4896
4897


4898
4899
4900
4901
4902

4903
4904
4905
4906
4907
4908
4909


4910
4911
4912
4913
4914
4915
4916
  */
  VdbeModuleComment((v, "End WHERE-core"));
  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 n = -1;
      int j, k, op;
      int r1 = pParse->nMem+1;
      Index *pIdx;
      if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED
................................................................................
        ** that has WHERE_DISTINCT_ORDERED, use OP_SkipGT/OP_SkipLT to skip
        ** over all duplicate entries, rather than visiting all duplicates
        ** using OP_Next/OP_Prev. */
        ExprList *pX = pWInfo->pResultSet;
        for(j=0; j<pX->nExpr; j++){
          Expr *pE = sqlite3ExprSkipCollate(pX->a[j].pExpr);
          if( pE->op==TK_COLUMN ){



            if( pE->iTable!=pLevel->iTabCur ) continue;
            k = 1+sqlite3ColumnOfIndex(pIdx, pE->iColumn);

            if( k>n ) n = k;





          }else if( pIdx->aColExpr ){
            for(k=n+1; k<pIdx->nKeyCol; k++){
              Expr *pI = pIdx->aColExpr->a[k].pExpr;
              if( pI && sqlite3ExprCompare(pE,pI,0)<2 ){
                n = k+1;
                break;
              }
            }
          }

        }
      }
      /* TUNING: Only try to skip ahead using OP_Seek if we expect to
      ** skip over 11 or more rows.  Otherwise, OP_Next is just as fast.
      */
      assert( 36==sqlite3LogEst(12) );
      if( n>0 && pIdx->aiRowLogEst[n]>=36 ){
................................................................................
        }
        pParse->nMem += n;
        op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT;
        k = 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);


        sqlite3VdbeJumpHere(v, k);
      }else
#endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
      {
        /* The common case: Advance to the next row */

        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);
      }


    }
    if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
      struct InLoop *pIn;
      int j;
      sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
      for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
        sqlite3VdbeJumpHere(v, pIn->addrInTop+1);







<







 







>
>
>
|
|
>

>
>
>
>
>
|
|

|
<
<
|
|
<
>







 







>
>





>







>
>







4843
4844
4845
4846
4847
4848
4849

4850
4851
4852
4853
4854
4855
4856
....
4862
4863
4864
4865
4866
4867
4868
4869
4870
4871
4872
4873
4874
4875
4876
4877
4878
4879
4880
4881
4882
4883
4884


4885
4886

4887
4888
4889
4890
4891
4892
4893
4894
....
4897
4898
4899
4900
4901
4902
4903
4904
4905
4906
4907
4908
4909
4910
4911
4912
4913
4914
4915
4916
4917
4918
4919
4920
4921
4922
4923
4924
4925
4926
4927
  */
  VdbeModuleComment((v, "End WHERE-core"));
  sqlite3ExprCacheClear(pParse);
  for(i=pWInfo->nLevel-1; i>=0; i--){
    int addr;
    pLevel = &pWInfo->a[i];
    pLoop = pLevel->pWLoop;

    if( pLevel->op!=OP_Noop ){
#ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
      int n = -1;
      int j, k, op;
      int r1 = pParse->nMem+1;
      Index *pIdx;
      if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED
................................................................................
        ** that has WHERE_DISTINCT_ORDERED, use OP_SkipGT/OP_SkipLT to skip
        ** over all duplicate entries, rather than visiting all duplicates
        ** using OP_Next/OP_Prev. */
        ExprList *pX = pWInfo->pResultSet;
        for(j=0; j<pX->nExpr; j++){
          Expr *pE = sqlite3ExprSkipCollate(pX->a[j].pExpr);
          if( pE->op==TK_COLUMN ){
            if( pE->iTable==pLevel->iIdxCur ){
              k = pE->iColumn+1;
            }else{
              if( pE->iTable!=pLevel->iTabCur ) continue;
              k = 1+sqlite3ColumnOfIndex(pIdx, pE->iColumn);
            }
            if( k>n ) n = k;
          }
#ifdef SQLITE_DEBUG
          /* Any expressions in the result-set that match columns of the
          ** index should have already been transformed to TK_COLUMN 
          ** operations by whereIndexExprTrans().  */
          else if( pIdx->aColExpr ){
            for(k=0; k<pIdx->nKeyCol; k++){
              Expr *pI = pIdx->aColExpr->a[k].pExpr;
              assert( pI==0 || sqlite3ExprCompare(pE, pI, pE->iTable)!=0 );


            }
          }

#endif
        }
      }
      /* TUNING: Only try to skip ahead using OP_Seek if we expect to
      ** skip over 11 or more rows.  Otherwise, OP_Next is just as fast.
      */
      assert( 36==sqlite3LogEst(12) );
      if( n>0 && pIdx->aiRowLogEst[n]>=36 ){
................................................................................
        }
        pParse->nMem += n;
        op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT;
        k = 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);
        sqlite3VdbeResolveLabel(v, pLevel->addrCont);
        sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
        sqlite3VdbeJumpHere(v, k);
      }else
#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);
      }
    }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);
      for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
        sqlite3VdbeJumpHere(v, pIn->addrInTop+1);

Changes to test/distinct2.test.

80
81
82
83
84
85
86
87























































88

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}
























































finish_test









>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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}


finish_test