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: |
56bbc539246a6dc9f1ae1edb898db7a4 |
| 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
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" {