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: |
70ac9ea1a6cb2f4906f00f1a04f668e5 |
| 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
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
|