/ Check-in [58797e9b]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 58797e9bafa95709e0f706a15f42f93b409e2db5
User & Date: drh 2017-02-15 22:36:15
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: 6affb1c8 user: drh tags: trunk
14:02
Merge recent enhancements from trunk. check-in: 325ccfa9 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: 58797e9b user: drh tags: trunk
18:30
Minor enhancement to mutex tracing on Win32. check-in: 830b9235 user: mistachkin tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/wherecode.c.

  1058   1058     WhereClause *pWC;    /* Decomposition of the entire WHERE clause */
  1059   1059     WhereTerm *pTerm;               /* A WHERE clause term */
  1060   1060     Parse *pParse;                  /* Parsing context */
  1061   1061     sqlite3 *db;                    /* Database connection */
  1062   1062     Vdbe *v;                        /* The prepared stmt under constructions */
  1063   1063     struct SrcList_item *pTabItem;  /* FROM clause term being coded */
  1064   1064     int addrBrk;                    /* Jump here to break out of the loop */
         1065  +  int addrHalt;                   /* addrBrk for the outermost loop */
  1065   1066     int addrCont;                   /* Jump here to continue with next cycle */
  1066   1067     int iRowidReg = 0;        /* Rowid is stored in this register, if not zero */
  1067   1068     int iReleaseReg = 0;      /* Temp register to free before returning */
  1068   1069   
  1069   1070     pParse = pWInfo->pParse;
  1070   1071     v = pParse->pVdbe;
  1071   1072     pWC = &pWInfo->sWC;
................................................................................
  1098   1099     ** row of the left table of the join.
  1099   1100     */
  1100   1101     if( pLevel->iFrom>0 && (pTabItem[0].fg.jointype & JT_LEFT)!=0 ){
  1101   1102       pLevel->iLeftJoin = ++pParse->nMem;
  1102   1103       sqlite3VdbeAddOp2(v, OP_Integer, 0, pLevel->iLeftJoin);
  1103   1104       VdbeComment((v, "init LEFT JOIN no-match flag"));
  1104   1105     }
         1106  +
         1107  +  /* Compute a safe address to jump to if we discover that the table for
         1108  +  ** this loop is empty and can never contribute content. */
         1109  +  for(j=iLevel; j>0 && pWInfo->a[j].iLeftJoin==0; j--){}
         1110  +  addrHalt = pWInfo->a[j].addrBrk;
  1105   1111   
  1106   1112     /* Special case of a FROM clause subquery implemented as a co-routine */
  1107   1113     if( pTabItem->fg.viaCoroutine ){
  1108   1114       int regYield = pTabItem->regReturn;
  1109   1115       sqlite3VdbeAddOp3(v, OP_InitCoroutine, regYield, 0, pTabItem->addrFillSub);
  1110   1116       pLevel->p2 =  sqlite3VdbeAddOp2(v, OP_Yield, regYield, addrBrk);
  1111   1117       VdbeCoverage(v);
................................................................................
  1283   1289         VdbeCoverageIf(v, pX->op==TK_GT);
  1284   1290         VdbeCoverageIf(v, pX->op==TK_LE);
  1285   1291         VdbeCoverageIf(v, pX->op==TK_LT);
  1286   1292         VdbeCoverageIf(v, pX->op==TK_GE);
  1287   1293         sqlite3ExprCacheAffinityChange(pParse, r1, 1);
  1288   1294         sqlite3ReleaseTempReg(pParse, rTemp);
  1289   1295       }else{
  1290         -      sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrBrk);
         1296  +      sqlite3VdbeAddOp2(v, bRev ? OP_Last : OP_Rewind, iCur, addrHalt);
  1291   1297         VdbeCoverageIf(v, bRev==0);
  1292   1298         VdbeCoverageIf(v, bRev!=0);
  1293   1299       }
  1294   1300       if( pEnd ){
  1295   1301         Expr *pX;
  1296   1302         pX = pEnd->pExpr;
  1297   1303         assert( pX!=0 );
................................................................................
  1929   1935         /* Tables marked isRecursive have only a single row that is stored in
  1930   1936         ** a pseudo-cursor.  No need to Rewind or Next such cursors. */
  1931   1937         pLevel->op = OP_Noop;
  1932   1938       }else{
  1933   1939         codeCursorHint(pTabItem, pWInfo, pLevel, 0);
  1934   1940         pLevel->op = aStep[bRev];
  1935   1941         pLevel->p1 = iCur;
  1936         -      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrBrk);
         1942  +      pLevel->p2 = 1 + sqlite3VdbeAddOp2(v, aStart[bRev], iCur, addrHalt);
  1937   1943         VdbeCoverageIf(v, bRev==0);
  1938   1944         VdbeCoverageIf(v, bRev!=0);
  1939   1945         pLevel->p5 = SQLITE_STMTSTATUS_FULLSCAN_STEP;
  1940   1946       }
  1941   1947     }
  1942   1948   
  1943   1949   #ifdef SQLITE_ENABLE_STMT_SCANSTATUS

Added test/emptytable.test.

            1  +# 2017-02-15
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#***********************************************************************
           11  +#
           12  +# Test cases to show that a join involving an empty table is very fast.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +
           18  +# Build some test data
           19  +#
           20  +do_execsql_test emptytable-100 {
           21  +  CREATE TABLE t1(a);
           22  +  WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100)
           23  +    INSERT INTO t1(a) SELECT x FROM c;
           24  +  CREATE TABLE empty(x);
           25  +  SELECT count(*) FROM t1;
           26  +} {100}
           27  +
           28  +# Interrupt queries after 1M cycles to prevent burning excess CPU
           29  +proc stopDb {args} {
           30  +  db interrupt
           31  +}
           32  +db progress 1000000 {stopDb}
           33  +
           34  +# Prior to the query planner optimization on 2017-02-15, this query would
           35  +# take a ridiculous amount of time.  If that optimization stops working,
           36  +# the result here will be in interrupt for running too long.
           37  +#
           38  +do_catchsql_test emptytable-110 {
           39  +  SELECT count(*) FROM t1, t1, t1, t1, t1, t1, empty;
           40  +} {0 0}
           41  +
           42  +do_catchsql_test emptytable-120 {
           43  +  SELECT count(*) FROM t1, t1 LEFT JOIN empty;
           44  +} {0 10000}
           45  +do_catchsql_test emptytable-121 {
           46  +  SELECT count(*) FROM t1, t1 LEFT JOIN t1, empty;
           47  +} {0 0}
           48  +
           49  +
           50  +finish_test