Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Query planner optimization to detect empty tables in a join early and bail out without doing excess work. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
58797e9bafa95709e0f706a15f42f93b |
User & Date: | drh 2017-02-15 22:36:15.061 |
Context
2017-02-16
| ||
14:48 | Always use the IsVirtual() macro to determine if a Table object is a virtual table. Slightly smaller and faster code. (check-in: 6affb1c89d user: drh tags: trunk) | |
14:02 | Merge recent enhancements from trunk. (check-in: 325ccfa95e user: drh tags: est_count_pragma) | |
2017-02-15
| ||
22:36 | Query planner optimization to detect empty tables in a join early and bail out without doing excess work. (check-in: 58797e9baf user: drh tags: trunk) | |
18:30 | Minor enhancement to mutex tracing on Win32. (check-in: 830b923567 user: mistachkin tags: trunk) | |
Changes
Changes to src/wherecode.c.
︙ | ︙ | |||
1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 | WhereClause *pWC; /* Decomposition of the entire WHERE clause */ WhereTerm *pTerm; /* A WHERE clause term */ Parse *pParse; /* Parsing context */ sqlite3 *db; /* Database connection */ Vdbe *v; /* The prepared stmt under constructions */ struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ int addrCont; /* Jump here to continue with next cycle */ int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ int iReleaseReg = 0; /* Temp register to free before returning */ pParse = pWInfo->pParse; v = pParse->pVdbe; pWC = &pWInfo->sWC; | > | 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 | WhereClause *pWC; /* Decomposition of the entire WHERE clause */ WhereTerm *pTerm; /* A WHERE clause term */ Parse *pParse; /* Parsing context */ sqlite3 *db; /* Database connection */ Vdbe *v; /* The prepared stmt under constructions */ struct SrcList_item *pTabItem; /* FROM clause term being coded */ int addrBrk; /* Jump here to break out of the loop */ int addrHalt; /* addrBrk for the outermost loop */ int addrCont; /* Jump here to continue with next cycle */ int iRowidReg = 0; /* Rowid is stored in this register, if not zero */ int iReleaseReg = 0; /* Temp register to free before returning */ pParse = pWInfo->pParse; v = pParse->pVdbe; pWC = &pWInfo->sWC; |
︙ | ︙ | |||
1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 | ** row of the left table of the join. */ if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){ pLevel->iLeftJoin = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin); VdbeComment((v, "init LEFT JOIN no-match flag")); } /* Special case of a FROM clause subquery implemented as a co-routine */ if( pTabItem->fg.viaCoroutine ){ int regYield = pTabItem->regReturn; sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub); pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); VdbeCoverage(v); | > > > > > | 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 | ** row of the left table of the join. */ if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){ pLevel->iLeftJoin = ++pParse->nMem; sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin); VdbeComment((v, "init LEFT JOIN no-match flag")); } /* Compute a safe address to jump to if we discover that the table for ** this loop is empty and can never contribute content. */ for(j=iLevel; j>0 && pWInfo->a[j].iLeftJoin==0; j--){} addrHalt = pWInfo->a[j].addrBrk; /* Special case of a FROM clause subquery implemented as a co-routine */ if( pTabItem->fg.viaCoroutine ){ int regYield = pTabItem->regReturn; sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub); pLevel->p2 = sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk); VdbeCoverage(v); |
︙ | ︙ | |||
1283 1284 1285 1286 1287 1288 1289 | VdbeCoverageIf(v, pX->op==TK_GT); VdbeCoverageIf(v, pX->op==TK_LE); VdbeCoverageIf(v, pX->op==TK_LT); VdbeCoverageIf(v, pX->op==TK_GE); sqlite3ExprCacheAffinityChange(pParse, r1, 1); sqlite3ReleaseTempReg(pParse, rTemp); }else{ | | | 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 | VdbeCoverageIf(v, pX->op==TK_GT); VdbeCoverageIf(v, pX->op==TK_LE); VdbeCoverageIf(v, pX->op==TK_LT); VdbeCoverageIf(v, pX->op==TK_GE); sqlite3ExprCacheAffinityChange(pParse, r1, 1); sqlite3ReleaseTempReg(pParse, rTemp); }else{ sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt); VdbeCoverageIf(v, bRev==0); VdbeCoverageIf(v, bRev!=0); } if( pEnd ){ Expr *pX; pX = pEnd->pExpr; assert( pX!=0 ); |
︙ | ︙ | |||
1929 1930 1931 1932 1933 1934 1935 | /* Tables marked isRecursive have only a single row that is stored in ** a pseudo-cursor. No need to Rewind or Next such cursors. */ pLevel->op = OP_Noop; }else{ codeCursorHint(pTabItem, pWInfo, pLevel, 0); pLevel->op = aStep[bRev]; pLevel->p1 = iCur; | | | 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 | /* Tables marked isRecursive have only a single row that is stored in ** a pseudo-cursor. No need to Rewind or Next such cursors. */ pLevel->op = OP_Noop; }else{ codeCursorHint(pTabItem, pWInfo, pLevel, 0); pLevel->op = aStep[bRev]; pLevel->p1 = iCur; pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt); VdbeCoverageIf(v, bRev==0); VdbeCoverageIf(v, bRev!=0); pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP; } } #ifdef SQLITE_ENABLE_STMT_SCANSTATUS |
︙ | ︙ |
Added test/emptytable.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | # 2017-02-15 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # Test cases to show that a join involving an empty table is very fast. # set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_execsql_test emptytable-100 { CREATE TABLE t1(a); WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100) INSERT INTO t1(a) SELECT x FROM c; CREATE TABLE empty(x); SELECT count(*) FROM t1; } {100} # Interrupt queries after 1M cycles to prevent burning excess CPU proc stopDb {args} { db interrupt } db progress 1000000 {stopDb} # Prior to the query planner optimization on 2017-02-15, this query would # take a ridiculous amount of time. If that optimization stops working, # the result here will be in interrupt for running too long. # do_catchsql_test emptytable-110 { SELECT count(*) FROM t1, t1, t1, t1, t1, t1, empty; } {0 0} do_catchsql_test emptytable-120 { SELECT count(*) FROM t1, t1 LEFT JOIN empty; } {0 10000} do_catchsql_test emptytable-121 { SELECT count(*) FROM t1, t1 LEFT JOIN t1, empty; } {0 0} finish_test |