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: |
5e75ab93881b85801cb4ebf70f2063ff |
| 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
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));
|