/ Check-in [5e75ab93]
Login

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

Overview
Comment:Improve the way that skip-scan loops are constructued. Add test cases. Improved the scoring of skip-scan loops.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | skip-scan
Files: files | file ages | folders
SHA1: 5e75ab93881b85801cb4ebf70f2063ff7c51ac19
User & Date: drh 2013-11-13 16:58:54
Context
2013-11-13
17:24
Add VDBE comments to the beginning and end of skip-scan loops. check-in: 0c85d93b user: drh tags: skip-scan
16:58
Improve the way that skip-scan loops are constructued. Add test cases. Improved the scoring of skip-scan loops. check-in: 5e75ab93 user: drh tags: skip-scan
15:32
Add test cases for skip-scan. Enhance "do_test" so that if the expected result is of the form "/*..*/" or "~/*..*/" it treats the expected result as a glob pattern rather than as a regular expression. Fix a bug in ANALYZE result loading associated with WITHOUT ROWID tables. check-in: d3e6e9b2 user: drh tags: skip-scan
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/where.c.

2500
2501
2502
2503
2504
2505
2506
2507

2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
....
3924
3925
3926
3927
3928
3929
3930

3931
3932
3933
3934

3935
3936
3937
3938
3939
3940
3941
3942
....
3965
3966
3967
3968
3969
3970
3971

3972
3973

3974
3975
3976
3977
3978
3979
3980
....
5780
5781
5782
5783
5784
5785
5786
5787
5788
5789
5790
5791
5792
5793
5794
5795
5796
5797
5798
  zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  if( nSkip ){
    int iIdxCur = pLevel->iIdxCur;
    sqlite3VdbeAddOp2(v, (bRev?OP_Last:OP_Rewind), iIdxCur, pLevel->addrNxt);

    pLevel->addrSkip = sqlite3VdbeCurrentAddr(v);
    pLevel->opSkip = bRev ? OP_SeekLt : OP_SeekGt;
    pLevel->p3Skip = regBase;
    pLevel->p4Skip = nSkip;
    for(j=0; j<nSkip; j++){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
      assert( pIdx->aiColumn[j]>=0 );
      VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName));
    }
  }    

................................................................................
  pNew->rSetup = 0;
  rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
  if( pTerm==0
   && saved_nEq==saved_nSkip
   && saved_nEq+1<pProbe->nKeyCol
   && pProbe->aiRowEst[saved_nEq+1]>50
  ){

    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIP_SCAN;

    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nInMul);
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
................................................................................
        /* "x IN (value, value, ...)" */
        nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
      }
      pNew->rRun += nIn;
      pNew->u.btree.nEq++;
      pNew->nOut = nRowEst + nInMul + nIn;
    }else if( pTerm->eOperator & (WO_EQ) ){

      assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
                  || nInMul==0 );

      pNew->wsFlags |= WHERE_COLUMN_EQ;
      if( iCol<0  
       || (pProbe->onError!=OE_None && nInMul==0
           && pNew->u.btree.nEq==pProbe->nKeyCol-1)
      ){
        assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
        pNew->wsFlags |= WHERE_ONEROW;
................................................................................
        sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
      sqlite3DbFree(db, pLevel->u.in.aInLoop);
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->addrSkip ){
      addr = sqlite3VdbeAddOp4Int(v, pLevel->opSkip, pLevel->iIdxCur, 0,
                                  pLevel->p3Skip, pLevel->p4Skip);
      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip-1);
      sqlite3VdbeJumpHere(v, addr);
    }
    if( pLevel->iLeftJoin ){
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
      if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);







|
>
|
<
|
|







 







>



|
>
|







 







>
|
|
>







 







<
<

|
|







2500
2501
2502
2503
2504
2505
2506
2507
2508
2509

2510
2511
2512
2513
2514
2515
2516
2517
2518
....
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
....
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
....
5784
5785
5786
5787
5788
5789
5790


5791
5792
5793
5794
5795
5796
5797
5798
5799
5800
  zAff = sqlite3DbStrDup(pParse->db, sqlite3IndexAffinityStr(v, pIdx));
  if( !zAff ){
    pParse->db->mallocFailed = 1;
  }

  if( nSkip ){
    int iIdxCur = pLevel->iIdxCur;
    sqlite3VdbeAddOp1(v, (bRev?OP_Last:OP_Rewind), iIdxCur);
    j = sqlite3VdbeAddOp0(v, OP_Goto);
    pLevel->addrSkip = sqlite3VdbeAddOp4Int(v, (bRev?OP_SeekLt:OP_SeekGt),

                            iIdxCur, 0, regBase, nSkip);
    sqlite3VdbeJumpHere(v, j);
    for(j=0; j<nSkip; j++){
      sqlite3VdbeAddOp3(v, OP_Column, iIdxCur, j, regBase+j);
      assert( pIdx->aiColumn[j]>=0 );
      VdbeComment((v, "%s", pIdx->pTable->aCol[pIdx->aiColumn[j]].zName));
    }
  }    

................................................................................
  pNew->rSetup = 0;
  rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
  if( pTerm==0
   && saved_nEq==saved_nSkip
   && saved_nEq+1<pProbe->nKeyCol
   && pProbe->aiRowEst[saved_nEq+1]>50
  ){
    LogEst nIter;
    pNew->u.btree.nEq++;
    pNew->u.btree.nSkip++;
    pNew->aLTerm[pNew->nLTerm++] = 0;
    pNew->wsFlags |= WHERE_SKIPSCAN;
    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
    whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
  }
  for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
    int nIn = 0;
#ifdef SQLITE_ENABLE_STAT3_OR_STAT4
    int nRecValid = pBuilder->nRecValid;
#endif
    if( (pTerm->eOperator==WO_ISNULL || (pTerm->wtFlags&TERM_VNULL)!=0)
................................................................................
        /* "x IN (value, value, ...)" */
        nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
      }
      pNew->rRun += nIn;
      pNew->u.btree.nEq++;
      pNew->nOut = nRowEst + nInMul + nIn;
    }else if( pTerm->eOperator & (WO_EQ) ){
      assert(
        (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN|WHERE_SKIPSCAN))!=0
        || nInMul==0
      );
      pNew->wsFlags |= WHERE_COLUMN_EQ;
      if( iCol<0  
       || (pProbe->onError!=OE_None && nInMul==0
           && pNew->u.btree.nEq==pProbe->nKeyCol-1)
      ){
        assert( (pNew->wsFlags & WHERE_COLUMN_IN)==0 || iCol<0 );
        pNew->wsFlags |= WHERE_ONEROW;
................................................................................
        sqlite3VdbeAddOp2(v, pIn->eEndLoopOp, pIn->iCur, pIn->addrInTop);
        sqlite3VdbeJumpHere(v, pIn->addrInTop-1);
      }
      sqlite3DbFree(db, pLevel->u.in.aInLoop);
    }
    sqlite3VdbeResolveLabel(v, pLevel->addrBrk);
    if( pLevel->addrSkip ){


      sqlite3VdbeAddOp2(v, OP_Goto, 0, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip);
      sqlite3VdbeJumpHere(v, pLevel->addrSkip-2);
    }
    if( pLevel->iLeftJoin ){
      addr = sqlite3VdbeAddOp1(v, OP_IfPos, pLevel->iLeftJoin);
      assert( (pLoop->wsFlags & WHERE_IDX_ONLY)==0
           || (pLoop->wsFlags & WHERE_INDEXED)!=0 );
      if( (pLoop->wsFlags & WHERE_IDX_ONLY)==0 ){
        sqlite3VdbeAddOp1(v, OP_NullRow, pTabList->a[i].iCursor);

Changes to src/whereInt.h.

67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
...
455
456
457
458
459
460
461
462
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */
  u8 opSkip;            /* Opcode to terminate the skip-scan */
  int p1, p2;           /* Operands of the opcode used to ends the loop */
  int p3Skip;           /* P3 operand for the skip-scan terminator */
  u16 p4Skip;           /* P4 operand for the skip-scan terminator */
  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
................................................................................
#define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
#define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIP_SCAN    0x00008000  /* Uses the skip-scan algorithm */







<

<
<







 







|
67
68
69
70
71
72
73

74


75
76
77
78
79
80
81
...
452
453
454
455
456
457
458
459
  int addrNxt;          /* Jump here to start the next IN combination */
  int addrSkip;         /* Jump here for next iteration of skip-scan */
  int addrCont;         /* Jump here to continue with the next loop cycle */
  int addrFirst;        /* First instruction of interior of the loop */
  int addrBody;         /* Beginning of the body of this loop */
  u8 iFrom;             /* Which entry in the FROM clause */
  u8 op, p5;            /* Opcode and P5 of the opcode that ends the loop */

  int p1, p2;           /* Operands of the opcode used to ends the loop */


  union {               /* Information that depends on pWLoop->wsFlags */
    struct {
      int nIn;              /* Number of entries in aInLoop[] */
      struct InLoop {
        int iCur;              /* The VDBE cursor used by this IN operator */
        int addrInTop;         /* Top of the IN loop */
        u8 eEndLoopOp;         /* IN Loop terminator. OP_Next or OP_Prev */
................................................................................
#define WHERE_IPK          0x00000100  /* x is the INTEGER PRIMARY KEY */
#define WHERE_INDEXED      0x00000200  /* WhereLoop.u.btree.pIndex is valid */
#define WHERE_VIRTUALTABLE 0x00000400  /* WhereLoop.u.vtab is valid */
#define WHERE_IN_ABLE      0x00000800  /* Able to support an IN operator */
#define WHERE_ONEROW       0x00001000  /* Selects no more than one row */
#define WHERE_MULTI_OR     0x00002000  /* OR using multiple indices */
#define WHERE_AUTO_INDEX   0x00004000  /* Uses an ephemeral index */
#define WHERE_SKIPSCAN     0x00008000  /* Uses the skip-scan algorithm */

Changes to test/skipscan1.test.

69
70
71
72
73
74
75
76

























77
78
79
80
81


82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
do_execsql_test skipscan1-1.4sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {~/*ORDER BY*/}


























# Joins
#
do_execsql_test skipscan1-1.5 {
  CREATE TABLE t1j(x TEXT, y INTEGER);
  INSERT INTO t1j VALUES('one',1),('six',6),('ninty-nine',99);


  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {six abc 234 6 7 | six bcd 100 6 11 |}
do_execsql_test skipscan1-1.5eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-1.6 {
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {one {} {} {} {} | six abc 234 6 7 | six bcd 100 6 11 | ninty-nine {} {} {} {} |}
do_execsql_test skipscan1-1.6eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-2.1 {
  CREATE TABLE t2(a TEXT, b INT, c INT, d INT,
                  PRIMARY KEY(a,b,c));








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


|


>
>


|




|


|







69
70
71
72
73
74
75
76
77
78
79
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
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
do_execsql_test skipscan1-1.4sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c=6 ORDER BY a, b, c;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.5 {
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
do_execsql_test skipscan1-1.5eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}
do_execsql_test skipscan1-1.5sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c IN (6,7) ORDER BY a, b, c;
} {~/*ORDER BY*/}

do_execsql_test skipscan1-1.6 {
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {abc 234 6 7 | abc 345 7 8 | bcd 100 6 11 |}
do_execsql_test skipscan1-1.6eqp {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {/* USING INDEX t1abc (ANY(a) AND ANY(b) AND c>? AND c<?)*/}
do_execsql_test skipscan1-1.6sort {
  EXPLAIN QUERY PLAN
  SELECT a,b,c,d,'|' FROM t1 WHERE c BETWEEN 6 AND 7 ORDER BY a, b, c;
} {~/*ORDER BY*/}


# Joins
#
do_execsql_test skipscan1-1.51 {
  CREATE TABLE t1j(x TEXT, y INTEGER);
  INSERT INTO t1j VALUES('one',1),('six',6),('ninty-nine',99);
  INSERT INTO sqlite_stat1 VALUES('t1j',null,'3');
  ANALYZE sqlite_master;
  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {six abc 234 6 7 | six bcd 100 6 11 |}
do_execsql_test skipscan1-1.51eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j, t1 WHERE c=y ORDER BY +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-1.52 {
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {one {} {} {} {} | six abc 234 6 7 | six bcd 100 6 11 | ninty-nine {} {} {} {} |}
do_execsql_test skipscan1-1.52eqp {
  EXPLAIN QUERY PLAN
  SELECT x, a, b, c, d, '|' FROM t1j LEFT JOIN t1 ON c=y ORDER BY +y, +a;
} {/* INDEX t1abc (ANY(a) AND ANY(b) AND c=?)*/}

do_execsql_test skipscan1-2.1 {
  CREATE TABLE t2(a TEXT, b INT, c INT, d INT,
                  PRIMARY KEY(a,b,c));