/ Check-in [56bbc539]
Login

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

Overview
Comment:Use the estimated number of rows computed for subqueries in the cost computations for outer queries.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 56bbc539246a6dc9f1ae1edb898db7a4f6f6d322
User & Date: drh 2010-11-16 02:49:16
Context
2010-11-16
23:10
Adding the sqlite3_stmt_readonly() interface. check-in: fd5b2f23 user: drh tags: trunk
18:56
Add experimental command "PRAGMA wal_blocking_checkpoint", which uses the busy-handler to block until all readers have finished in order to ensure the next writer will be able to wrap around to the start of the log file. check-in: 7e3fc2c8 user: dan tags: blocking-checkpoint
02:49
Use the estimated number of rows computed for subqueries in the cost computations for outer queries. check-in: 56bbc539 user: drh tags: trunk
2010-11-15
21:50
Change the EQP output for the min/max optimization from "SCAN" to "SEARCH". Other changes in where.c in support of full branch coverage testing. check-in: d52b5939 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/select.c.

  1429   1429       v = sqlite3GetVdbe(pParse);
  1430   1430       if( NEVER(v==0) ) return;  /* VDBE should have already been allocated */
  1431   1431       if( sqlite3ExprIsInteger(p->pLimit, &n) ){
  1432   1432         sqlite3VdbeAddOp2(v, OP_Integer, n, iLimit);
  1433   1433         VdbeComment((v, "LIMIT counter"));
  1434   1434         if( n==0 ){
  1435   1435           sqlite3VdbeAddOp2(v, OP_Goto, 0, iBreak);
         1436  +      }else{
         1437  +        if( p->nSelectRow > (double)n ) p->nSelectRow = (double)n;
  1436   1438         }
  1437   1439       }else{
  1438   1440         sqlite3ExprCode(pParse, p->pLimit, iLimit);
  1439   1441         sqlite3VdbeAddOp1(v, OP_MustBeInt, iLimit);
  1440   1442         VdbeComment((v, "LIMIT counter"));
  1441   1443         sqlite3VdbeAddOp2(v, OP_IfZero, iLimit, iBreak);
  1442   1444       }
................................................................................
  1590   1592     }
  1591   1593   
  1592   1594     /* Generate code for the left and right SELECT statements.
  1593   1595     */
  1594   1596     switch( p->op ){
  1595   1597       case TK_ALL: {
  1596   1598         int addr = 0;
         1599  +      int nLimit;
  1597   1600         assert( !pPrior->pLimit );
  1598   1601         pPrior->pLimit = p->pLimit;
  1599   1602         pPrior->pOffset = p->pOffset;
  1600   1603         explainSetInteger(iSub1, pParse->iNextSelectId);
  1601   1604         rc = sqlite3Select(pParse, pPrior, &dest);
  1602   1605         p->pLimit = 0;
  1603   1606         p->pOffset = 0;
................................................................................
  1612   1615           VdbeComment((v, "Jump ahead if LIMIT reached"));
  1613   1616         }
  1614   1617         explainSetInteger(iSub2, pParse->iNextSelectId);
  1615   1618         rc = sqlite3Select(pParse, p, &dest);
  1616   1619         testcase( rc!=SQLITE_OK );
  1617   1620         pDelete = p->pPrior;
  1618   1621         p->pPrior = pPrior;
         1622  +      p->nSelectRow += pPrior->nSelectRow;
         1623  +      if( pPrior->pLimit
         1624  +       && sqlite3ExprIsInteger(pPrior->pLimit, &nLimit)
         1625  +       && p->nSelectRow > (double)nLimit 
         1626  +      ){
         1627  +        p->nSelectRow = (double)nLimit;
         1628  +      }
  1619   1629         if( addr ){
  1620   1630           sqlite3VdbeJumpHere(v, addr);
  1621   1631         }
  1622   1632         break;
  1623   1633       }
  1624   1634       case TK_EXCEPT:
  1625   1635       case TK_UNION: {
................................................................................
  1684   1694         testcase( rc!=SQLITE_OK );
  1685   1695         /* Query flattening in sqlite3Select() might refill p->pOrderBy.
  1686   1696         ** Be sure to delete p->pOrderBy, therefore, to avoid a memory leak. */
  1687   1697         sqlite3ExprListDelete(db, p->pOrderBy);
  1688   1698         pDelete = p->pPrior;
  1689   1699         p->pPrior = pPrior;
  1690   1700         p->pOrderBy = 0;
         1701  +      if( p->op==TK_UNION ) p->nSelectRow += pPrior->nSelectRow;
  1691   1702         sqlite3ExprDelete(db, p->pLimit);
  1692   1703         p->pLimit = pLimit;
  1693   1704         p->pOffset = pOffset;
  1694   1705         p->iLimit = 0;
  1695   1706         p->iOffset = 0;
  1696   1707   
  1697   1708         /* Convert the data in the temporary table into whatever form
................................................................................
  1763   1774         p->pOffset = 0;
  1764   1775         intersectdest.iParm = tab2;
  1765   1776         explainSetInteger(iSub2, pParse->iNextSelectId);
  1766   1777         rc = sqlite3Select(pParse, p, &intersectdest);
  1767   1778         testcase( rc!=SQLITE_OK );
  1768   1779         pDelete = p->pPrior;
  1769   1780         p->pPrior = pPrior;
         1781  +      if( p->nSelectRow>pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
  1770   1782         sqlite3ExprDelete(db, p->pLimit);
  1771   1783         p->pLimit = pLimit;
  1772   1784         p->pOffset = pOffset;
  1773   1785   
  1774   1786         /* Generate code to take the intersection of the two temporary
  1775   1787         ** tables.
  1776   1788         */
................................................................................
  2349   2361     if( op==TK_EXCEPT || op==TK_INTERSECT ){
  2350   2362       addrEofA = sqlite3VdbeAddOp2(v, OP_Goto, 0, labelEnd);
  2351   2363     }else{  
  2352   2364       addrEofA = sqlite3VdbeAddOp2(v, OP_If, regEofB, labelEnd);
  2353   2365       sqlite3VdbeAddOp2(v, OP_Gosub, regOutB, addrOutB);
  2354   2366       sqlite3VdbeAddOp1(v, OP_Yield, regAddrB);
  2355   2367       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofA);
         2368  +    p->nSelectRow += pPrior->nSelectRow;
  2356   2369     }
  2357   2370   
  2358   2371     /* Generate a subroutine to run when the results from select B
  2359   2372     ** are exhausted and only data in select A remains.
  2360   2373     */
  2361   2374     if( op==TK_INTERSECT ){
  2362   2375       addrEofB = addrEofA;
         2376  +    if( p->nSelectRow > pPrior->nSelectRow ) p->nSelectRow = pPrior->nSelectRow;
  2363   2377     }else{  
  2364   2378       VdbeNoopComment((v, "eof-B subroutine"));
  2365   2379       addrEofB = sqlite3VdbeAddOp2(v, OP_If, regEofA, labelEnd);
  2366   2380       sqlite3VdbeAddOp2(v, OP_Gosub, regOutA, addrOutA);
  2367   2381       sqlite3VdbeAddOp1(v, OP_Yield, regAddrA);
  2368   2382       sqlite3VdbeAddOp2(v, OP_Goto, 0, addrEofB);
  2369   2383     }
................................................................................
  3750   3764         i = -1;
  3751   3765       }else{
  3752   3766         sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
  3753   3767         assert( pItem->isPopulated==0 );
  3754   3768         explainSetInteger(pItem->iSelectId, pParse->iNextSelectId);
  3755   3769         sqlite3Select(pParse, pSub, &dest);
  3756   3770         pItem->isPopulated = 1;
         3771  +      pItem->pTab->nRowEst = (unsigned)pSub->nSelectRow;
  3757   3772       }
  3758   3773       if( /*pParse->nErr ||*/ db->mallocFailed ){
  3759   3774         goto select_end;
  3760   3775       }
  3761   3776       pParse->nHeight -= sqlite3SelectExprHeight(p);
  3762   3777       pTabList = p->pSrc;
  3763   3778       if( !IgnorableOrderby(pDest) ){
................................................................................
  3842   3857     if( pDest->eDest==SRT_EphemTab ){
  3843   3858       sqlite3VdbeAddOp2(v, OP_OpenEphemeral, pDest->iParm, pEList->nExpr);
  3844   3859     }
  3845   3860   
  3846   3861     /* Set the limiter.
  3847   3862     */
  3848   3863     iEnd = sqlite3VdbeMakeLabel(v);
         3864  +  p->nSelectRow = (double)LARGEST_INT64;
  3849   3865     computeLimitRegisters(pParse, p, iEnd);
  3850   3866   
  3851   3867     /* Open a virtual index to use for the distinct set.
  3852   3868     */
  3853   3869     if( p->selFlags & SF_Distinct ){
  3854   3870       KeyInfo *pKeyInfo;
  3855   3871       assert( isAgg || pGroupBy );
................................................................................
  3865   3881     /* Aggregate and non-aggregate queries are handled differently */
  3866   3882     if( !isAgg && pGroupBy==0 ){
  3867   3883       /* This case is for non-aggregate queries
  3868   3884       ** Begin the database scan
  3869   3885       */
  3870   3886       pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, &pOrderBy, 0);
  3871   3887       if( pWInfo==0 ) goto select_end;
         3888  +    if( pWInfo->nRowOut < p->nSelectRow ) p->nSelectRow = pWInfo->nRowOut;
  3872   3889   
  3873   3890       /* If sorting index that was created by a prior OP_OpenEphemeral 
  3874   3891       ** instruction ended up not being needed, then change the OP_OpenEphemeral
  3875   3892       ** into an OP_Noop.
  3876   3893       */
  3877   3894       if( addrSortIndex>=0 && pOrderBy==0 ){
  3878   3895         sqlite3VdbeChangeToNoop(v, addrSortIndex, 1);
................................................................................
  3909   3926   
  3910   3927         for(k=p->pEList->nExpr, pItem=p->pEList->a; k>0; k--, pItem++){
  3911   3928           pItem->iAlias = 0;
  3912   3929         }
  3913   3930         for(k=pGroupBy->nExpr, pItem=pGroupBy->a; k>0; k--, pItem++){
  3914   3931           pItem->iAlias = 0;
  3915   3932         }
         3933  +      if( p->nSelectRow>(double)100 ) p->nSelectRow = (double)100;
         3934  +    }else{
         3935  +      p->nSelectRow = (double)1;
  3916   3936       }
  3917   3937   
  3918   3938    
  3919   3939       /* Create a label to jump to when we want to abort the query */
  3920   3940       addrEnd = sqlite3VdbeMakeLabel(v);
  3921   3941   
  3922   3942       /* Convert TK_COLUMN nodes into TK_AGG_COLUMN and make entries in

Changes to src/sqliteInt.h.

  1943   1943     SrcList *pTabList;             /* List of tables in the join */
  1944   1944     int iTop;                      /* The very beginning of the WHERE loop */
  1945   1945     int iContinue;                 /* Jump here to continue with next record */
  1946   1946     int iBreak;                    /* Jump here to break out of the loop */
  1947   1947     int nLevel;                    /* Number of nested loop */
  1948   1948     struct WhereClause *pWC;       /* Decomposition of the WHERE clause */
  1949   1949     double savedNQueryLoop;        /* pParse->nQueryLoop outside the WHERE loop */
         1950  +  double nRowOut;                /* Estimated number of output rows */
  1950   1951     WhereLevel a[1];               /* Information about each nest loop in WHERE */
  1951   1952   };
  1952   1953   
  1953   1954   /*
  1954   1955   ** A NameContext defines a context in which to resolve table and column
  1955   1956   ** names.  The context consists of a list of tables (the pSrcList) field and
  1956   1957   ** a list of named expression (pEList).  The named expression list may
................................................................................
  2018   2019     Select *pPrior;        /* Prior select in a compound select statement */
  2019   2020     Select *pNext;         /* Next select to the left in a compound */
  2020   2021     Select *pRightmost;    /* Right-most select in a compound select statement */
  2021   2022     Expr *pLimit;          /* LIMIT expression. NULL means not used. */
  2022   2023     Expr *pOffset;         /* OFFSET expression. NULL means not used. */
  2023   2024     int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
  2024   2025     int addrOpenEphm[3];   /* OP_OpenEphem opcodes related to this select */
         2026  +  double nSelectRow;     /* Estimated number of result rows */
  2025   2027   };
  2026   2028   
  2027   2029   /*
  2028   2030   ** Allowed values for Select.selFlags.  The "SF" prefix stands for
  2029   2031   ** "Select Flag".
  2030   2032   */
  2031   2033   #define SF_Distinct        0x0001  /* Output should be DISTINCT */

Changes to src/where.c.

  4419   4419     }
  4420   4420   
  4421   4421     /* Open all tables in the pTabList and any indices selected for
  4422   4422     ** searching those tables.
  4423   4423     */
  4424   4424     sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */
  4425   4425     notReady = ~(Bitmask)0;
         4426  +  pWInfo->nRowOut = (double)1;
  4426   4427     for(i=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
  4427   4428       Table *pTab;     /* Table to open */
  4428   4429       int iDb;         /* Index of database containing table/index */
  4429   4430   
  4430   4431       pTabItem = &pTabList->a[pLevel->iFrom];
  4431   4432       pTab = pTabItem->pTab;
  4432   4433       pLevel->iTabCur = pTabItem->iCursor;
         4434  +    pWInfo->nRowOut *= pLevel->plan.nRow;
  4433   4435       iDb = sqlite3SchemaToIndex(db, pTab->pSchema);
  4434   4436       if( (pTab->tabFlags & TF_Ephemeral)!=0 || pTab->pSelect ){
  4435   4437         /* Do nothing */
  4436   4438       }else
  4437   4439   #ifndef SQLITE_OMIT_VIRTUALTABLE
  4438   4440       if( (pLevel->plan.wsFlags & WHERE_VIRTUALTABLE)!=0 ){
  4439   4441         const char *pVTab = (const char *)sqlite3GetVTable(db, pTab);

Changes to test/autoindex1.test.

   241    241      ORDER BY x.registering_flock;
   242    242   } {
   243    243     1 0 0 {SCAN TABLE sheep AS s (~1000000 rows)} 
   244    244     1 1 1 {SEARCH TABLE flock_owner AS prev USING INDEX sqlite_autoindex_flock_owner_1 (flock_no=? AND owner_change_date<?) (~2 rows)} 
   245    245     1 0 0 {EXECUTE CORRELATED SCALAR SUBQUERY 2} 
   246    246     2 0 0 {SEARCH TABLE flock_owner AS later USING COVERING INDEX sqlite_autoindex_flock_owner_1 (flock_no=? AND owner_change_date>? AND owner_change_date<?) (~1 rows)} 
   247    247     0 0 0 {SCAN TABLE sheep AS x USING INDEX sheep_reg_flock_index (~1000000 rows)} 
   248         -  0 1 1 {SEARCH SUBQUERY 1 AS y USING AUTOMATIC COVERING INDEX (sheep_no=?) (~7 rows)}
          248  +  0 1 1 {SEARCH SUBQUERY 1 AS y USING AUTOMATIC COVERING INDEX (sheep_no=?) (~8 rows)}
   249    249   }
   250    250   
   251    251   finish_test

Changes to test/eqp.test.

    66     66   do_eqp_test 1.6 {
    67     67     SELECT DISTINCT count(*) FROM t3 GROUP BY a;
    68     68   } {
    69     69     0 0 0 {SCAN TABLE t3 (~1000000 rows)}
    70     70     0 0 0 {USE TEMP B-TREE FOR GROUP BY}
    71     71     0 0 0 {USE TEMP B-TREE FOR DISTINCT}
    72     72   }
           73  +
           74  +do_eqp_test 1.7 {
           75  +  SELECT * FROM t3 JOIN (SELECT 1)
           76  +} {
           77  +  0 0 1 {SCAN SUBQUERY 1 (~1 rows)}
           78  +  0 1 0 {SCAN TABLE t3 (~1000000 rows)}
           79  +}
           80  +do_eqp_test 1.8 {
           81  +  SELECT * FROM t3 JOIN (SELECT 1 UNION SELECT 2)
           82  +} {
           83  +  1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)}
           84  +  0 0 1 {SCAN SUBQUERY 1 (~2 rows)}
           85  +  0 1 0 {SCAN TABLE t3 (~1000000 rows)}
           86  +}
           87  +do_eqp_test 1.9 {
           88  +  SELECT * FROM t3 JOIN (SELECT 1 EXCEPT SELECT a FROM t3 LIMIT 17)
           89  +} {
           90  +  3 0 0 {SCAN TABLE t3 (~1000000 rows)}
           91  +  1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (EXCEPT)}
           92  +  0 0 1 {SCAN SUBQUERY 1 (~17 rows)}
           93  +  0 1 0 {SCAN TABLE t3 (~1000000 rows)}
           94  +}
           95  +do_eqp_test 1.10 {
           96  +  SELECT * FROM t3 JOIN (SELECT 1 INTERSECT SELECT a FROM t3 LIMIT 17)
           97  +} {
           98  +  3 0 0 {SCAN TABLE t3 (~1000000 rows)}
           99  +  1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (INTERSECT)}
          100  +  0 0 1 {SCAN SUBQUERY 1 (~1 rows)}
          101  +  0 1 0 {SCAN TABLE t3 (~1000000 rows)}
          102  +}
          103  +
          104  +do_eqp_test 1.11 {
          105  +  SELECT * FROM t3 JOIN (SELECT 1 UNION ALL SELECT a FROM t3 LIMIT 17)
          106  +} {
          107  +  3 0 0 {SCAN TABLE t3 (~1000000 rows)}
          108  +  1 0 0 {COMPOUND SUBQUERIES 2 AND 3 (UNION ALL)}
          109  +  0 0 1 {SCAN SUBQUERY 1 (~17 rows)}
          110  +  0 1 0 {SCAN TABLE t3 (~1000000 rows)}
          111  +}
    73    112   
    74    113   #-------------------------------------------------------------------------
    75    114   # Test cases eqp-2.* - tests for single select statements.
    76    115   #
    77    116   drop_all_tables
    78    117   do_execsql_test 2.1 {
    79    118     CREATE TABLE t1(x, y);
................................................................................
   163    202   }
   164    203   
   165    204   det 3.2.1 {
   166    205     SELECT * FROM (SELECT * FROM t1 ORDER BY x LIMIT 10) ORDER BY y LIMIT 5
   167    206   } {
   168    207     1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
   169    208     1 0 0 {USE TEMP B-TREE FOR ORDER BY} 
   170         -  0 0 0 {SCAN SUBQUERY 1 (~1000000 rows)} 
          209  +  0 0 0 {SCAN SUBQUERY 1 (~10 rows)} 
   171    210     0 0 0 {USE TEMP B-TREE FOR ORDER BY}
   172    211   }
   173    212   det 3.2.2 {
   174    213     SELECT * FROM 
   175    214       (SELECT * FROM t1 ORDER BY x LIMIT 10) AS x1,
   176    215       (SELECT * FROM t2 ORDER BY x LIMIT 10) AS x2
   177    216     ORDER BY x2.y LIMIT 5
   178    217   } {
   179    218     1 0 0 {SCAN TABLE t1 (~1000000 rows)} 
   180    219     1 0 0 {USE TEMP B-TREE FOR ORDER BY} 
   181    220     2 0 0 {SCAN TABLE t2 USING INDEX t2i1 (~1000000 rows)} 
   182         -  0 0 0 {SCAN SUBQUERY 1 AS x1 (~1000000 rows)} 
   183         -  0 1 1 {SCAN SUBQUERY 2 AS x2 (~1000000 rows)} 
          221  +  0 0 0 {SCAN SUBQUERY 1 AS x1 (~10 rows)} 
          222  +  0 1 1 {SCAN SUBQUERY 2 AS x2 (~10 rows)} 
   184    223     0 0 0 {USE TEMP B-TREE FOR ORDER BY}
   185    224   }
   186    225   
   187    226   det 3.3.1 {
   188    227     SELECT * FROM t1 WHERE y IN (SELECT y FROM t2)
   189    228   } {
   190    229     0 0 0 {SCAN TABLE t1 (~100000 rows)} 
................................................................................
   412    451   # count(*) FROM (SELECT max(b) AS x FROM t1 GROUP BY a) GROUP BY x;
   413    452   # 1|0|0|SCAN TABLE t1 USING COVERING INDEX i2 (~1000000 rows) 0|0|0|SCAN
   414    453   # SUBQUERY 1 (~1000000 rows) 0|0|0|USE TEMP B-TREE FOR GROUP BY
   415    454   det 5.10 {
   416    455     SELECT count(*) FROM (SELECT max(b) AS x FROM t1 GROUP BY a) GROUP BY x
   417    456   } {
   418    457     1 0 0 {SCAN TABLE t1 USING COVERING INDEX i2 (~1000000 rows)}
   419         -  0 0 0 {SCAN SUBQUERY 1 (~1000000 rows)}
          458  +  0 0 0 {SCAN SUBQUERY 1 (~100 rows)}
   420    459     0 0 0 {USE TEMP B-TREE FOR GROUP BY}
   421    460   }
   422    461   
   423    462   # EVIDENCE-OF: R-18544-33103 sqlite> EXPLAIN QUERY PLAN SELECT * FROM
   424    463   # (SELECT * FROM t2 WHERE c=1), t1; 0|0|0|SEARCH TABLE t2 USING INDEX i4
   425    464   # (c=?) (~10 rows) 0|1|1|SCAN TABLE t1 (~1000000 rows)
   426    465   det 5.11 "SELECT * FROM (SELECT * FROM t2 WHERE c=1), t1" {