/ 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 Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  4843   4843     */
  4844   4844     VdbeModuleComment((v, "End WHERE-core"));
  4845   4845     sqlite3ExprCacheClear(pParse);
  4846   4846     for(i=pWInfo->nLevel-1; i>=0; i--){
  4847   4847       int addr;
  4848   4848       pLevel = &pWInfo->a[i];
  4849   4849       pLoop = pLevel->pWLoop;
  4850         -    sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  4851   4850       if( pLevel->op!=OP_Noop ){
  4852   4851   #ifndef SQLITE_DISABLE_SKIPAHEAD_DISTINCT
  4853   4852         int n = -1;
  4854   4853         int j, k, op;
  4855   4854         int r1 = pParse->nMem+1;
  4856   4855         Index *pIdx;
  4857   4856         if( pWInfo->eDistinct==WHERE_DISTINCT_ORDERED
................................................................................
  4863   4862           ** that has WHERE_DISTINCT_ORDERED, use OP_SkipGT/OP_SkipLT to skip
  4864   4863           ** over all duplicate entries, rather than visiting all duplicates
  4865   4864           ** using OP_Next/OP_Prev. */
  4866   4865           ExprList *pX = pWInfo->pResultSet;
  4867   4866           for(j=0; j<pX->nExpr; j++){
  4868   4867             Expr *pE = sqlite3ExprSkipCollate(pX->a[j].pExpr);
  4869   4868             if( pE->op==TK_COLUMN ){
  4870         -            if( pE->iTable!=pLevel->iTabCur ) continue;
  4871         -            k = 1+sqlite3ColumnOfIndex(pIdx, pE->iColumn);
         4869  +            if( pE->iTable==pLevel->iIdxCur ){
         4870  +              k = pE->iColumn+1;
         4871  +            }else{
         4872  +              if( pE->iTable!=pLevel->iTabCur ) continue;
         4873  +              k = 1+sqlite3ColumnOfIndex(pIdx, pE->iColumn);
         4874  +            }
  4872   4875               if( k>n ) n = k;
  4873         -          }else if( pIdx->aColExpr ){
  4874         -            for(k=n+1; k<pIdx->nKeyCol; k++){
         4876  +          }
         4877  +#ifdef SQLITE_DEBUG
         4878  +          /* Any expressions in the result-set that match columns of the
         4879  +          ** index should have already been transformed to TK_COLUMN 
         4880  +          ** operations by whereIndexExprTrans().  */
         4881  +          else if( pIdx->aColExpr ){
         4882  +            for(k=0; k<pIdx->nKeyCol; k++){
  4875   4883                 Expr *pI = pIdx->aColExpr->a[k].pExpr;
  4876         -              if( pI && sqlite3ExprCompare(pE,pI,0)<2 ){
  4877         -                n = k+1;
  4878         -                break;
  4879         -              }
         4884  +              assert( pI==0 || sqlite3ExprCompare(pE, pI, pE->iTable)!=0 );
  4880   4885               }
  4881   4886             }
         4887  +#endif
  4882   4888           }
  4883   4889         }
  4884   4890         /* TUNING: Only try to skip ahead using OP_Seek if we expect to
  4885   4891         ** skip over 11 or more rows.  Otherwise, OP_Next is just as fast.
  4886   4892         */
  4887   4893         assert( 36==sqlite3LogEst(12) );
  4888   4894         if( n>0 && pIdx->aiRowLogEst[n]>=36 ){
................................................................................
  4891   4897           }
  4892   4898           pParse->nMem += n;
  4893   4899           op = pLevel->op==OP_Prev ? OP_SeekLT : OP_SeekGT;
  4894   4900           k = sqlite3VdbeAddOp4Int(v, op, pLevel->iIdxCur, 0, r1, n);
  4895   4901           VdbeCoverageIf(v, op==OP_SeekLT);
  4896   4902           VdbeCoverageIf(v, op==OP_SeekGT);
  4897   4903           sqlite3VdbeAddOp2(v, OP_Goto, 1, pLevel->p2);
         4904  +        sqlite3VdbeResolveLabel(v, pLevel->addrCont);
         4905  +        sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  4898   4906           sqlite3VdbeJumpHere(v, k);
  4899   4907         }else
  4900   4908   #endif /* SQLITE_DISABLE_SKIPAHEAD_DISTINCT */
  4901   4909         {
  4902   4910           /* The common case: Advance to the next row */
         4911  +        sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  4903   4912           sqlite3VdbeAddOp3(v, pLevel->op, pLevel->p1, pLevel->p2, pLevel->p3);
  4904   4913           sqlite3VdbeChangeP5(v, pLevel->p5);
  4905   4914           VdbeCoverage(v);
  4906   4915           VdbeCoverageIf(v, pLevel->op==OP_Next);
  4907   4916           VdbeCoverageIf(v, pLevel->op==OP_Prev);
  4908   4917           VdbeCoverageIf(v, pLevel->op==OP_VNext);
  4909   4918         }
         4919  +    }else{
         4920  +      sqlite3VdbeResolveLabel(v, pLevel->addrCont);
  4910   4921       }
  4911   4922       if( pLoop->wsFlags & WHERE_IN_ABLE && pLevel->u.in.nIn>0 ){
  4912   4923         struct InLoop *pIn;
  4913   4924         int j;
  4914   4925         sqlite3VdbeResolveLabel(v, pLevel->addrNxt);
  4915   4926         for(j=pLevel->u.in.nIn, pIn=&pLevel->u.in.aInLoop[j-1]; j>0; j--, pIn--){
  4916   4927           sqlite3VdbeJumpHere(v, pIn->addrInTop+1);

Changes to test/distinct2.test.

    80     80   do_execsql_test 600 {
    81     81     CREATE TABLE t6a(x INTEGER PRIMARY KEY);
    82     82     INSERT INTO t6a VALUES(1);
    83     83     CREATE TABLE t6b(y INTEGER PRIMARY KEY);
    84     84     INSERT INTO t6b VALUES(2),(3);
    85     85     SELECT DISTINCT x, x FROM t6a, t6b;
    86     86   } {1 1}
           87  +
           88  +do_execsql_test 700 {
           89  +  CREATE TABLE t7(a, b, c);
           90  +  WITH s(i) AS (
           91  +    SELECT 1 UNION ALL SELECT i+1 FROM s WHERE (i+1)<200
           92  +  )
           93  +  INSERT INTO t7 SELECT i/100, i/50, i FROM s;
           94  +}
           95  +do_execsql_test 710 {
           96  +  SELECT DISTINCT a, b FROM t7;
           97  +} {
           98  +  0 0    0 1
           99  +  1 2    1 3
          100  +}
          101  +do_execsql_test 720 {
          102  +  SELECT DISTINCT a, b+1 FROM t7;
          103  +} {
          104  +  0 1    0 2
          105  +  1 3    1 4
          106  +}
          107  +do_execsql_test 730 {
          108  +  CREATE INDEX i7 ON t7(a, b+1);
          109  +  ANALYZE;
          110  +  SELECT DISTINCT a, b+1 FROM t7;
          111  +} {
          112  +  0 1    0 2
          113  +  1 3    1 4
          114  +}
          115  +
          116  +do_execsql_test 800 {
          117  +  CREATE TABLE t8(a, b, c);
          118  +  WITH s(i) AS (
          119  +    SELECT 1 UNION ALL SELECT i+1 FROM s WHERE (i+1)<100
          120  +  )
          121  +  INSERT INTO t8 SELECT i/40, i/20, i/40 FROM s;
          122  +}
          123  +
          124  +do_execsql_test 820 {
          125  +  SELECT DISTINCT a, b, c FROM t8;
          126  +} {
          127  +  0 0 0    0 1 0
          128  +  1 2 1    1 3 1
          129  +  2 4 2
          130  +}
          131  +
          132  +do_execsql_test 820 {
          133  +  SELECT DISTINCT a, b, c FROM t8 WHERE b=3;
          134  +} {1 3 1}
          135  +
          136  +do_execsql_test 830 {
          137  +  CREATE INDEX i8 ON t8(a, c);
          138  +  ANALYZE;
          139  +  SELECT DISTINCT a, b, c FROM t8 WHERE b=3;
          140  +} {1 3 1}
          141  +
    87    142   
    88    143   finish_test
          144  +