Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Resolve FROM-clause subqueries after query planning instead of before. Greatly reduce the estimated cost of automatic indexes for VIEWs and ephemeral tables since performance problems there cannot be mitigated via a CREATE INDEX. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | view-optimization |
| Files: | files | file ages | folders |
| SHA1: |
a1eaf1718e4544c17495ad7a4e333276 |
| User & Date: | drh 2015-06-10 17:20:42 |
Context
|
2015-06-10
| ||
| 20:00 | Merge enhancements from trunk. check-in: 0e23a079 user: drh tags: view-optimization | |
| 17:20 | Resolve FROM-clause subqueries after query planning instead of before. Greatly reduce the estimated cost of automatic indexes for VIEWs and ephemeral tables since performance problems there cannot be mitigated via a CREATE INDEX. check-in: a1eaf171 user: drh tags: view-optimization | |
|
2015-06-08
| ||
| 22:59 | Code refactoring to try to shift FROM-clause subquery manifesting until after the query planner runs. Except this does not currently work because the query planner needs an estimated of the number of rows in the manifested table. Work in progress. check-in: cabf2187 user: drh tags: view-optimization | |
Changes
Changes to src/select.c.
4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 |
SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
pParse->nSelectIndent--;
#endif
return rc;
}
#endif
#if 1
/* Manifest the subqueries. This needs to be done before calling
** sqlite3WhereBegin() so that the Table.nRowLogEst value can be set
** correctly for the subqueries. */
sqlite3ManifestSubqueries(pParse, p, pTabList);
if( db->mallocFailed ) goto select_end;
#endif
/* Various elements of the SELECT copied into local variables for
** convenience */
pEList = p->pEList;
pWhere = p->pWhere;
pGroupBy = p->pGroupBy;
pHaving = p->pHaving;
|
| | | | | | < > |
4995 4996 4997 4998 4999 5000 5001 5002 5003 5004 5005 5006 5007 5008 5009 5010 5011 5012 5013 5014 5015 |
SELECTTRACE(1,pParse,p,("end compound-select processing\n"));
pParse->nSelectIndent--;
#endif
return rc;
}
#endif
if( !OptimizationEnabled(db, SQLITE_LateSubquery) ){
/* Manifest the subqueries. This needs to be done before calling
** sqlite3WhereBegin() so that the Table.nRowLogEst value can be set
** correctly for the subqueries. */
sqlite3ManifestSubqueries(pParse, p, pTabList);
if( db->mallocFailed ) goto select_end;
}
/* Various elements of the SELECT copied into local variables for
** convenience */
pEList = p->pEList;
pWhere = p->pWhere;
pGroupBy = p->pGroupBy;
pHaving = p->pHaving;
|
Changes to src/sqliteInt.h.
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 |
#define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */ #define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */ #define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */ #define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */ #define SQLITE_Transitive 0x0200 /* Transitive constraints */ #define SQLITE_OmitNoopJoin 0x0400 /* Omit unused tables in joins */ #define SQLITE_Stat34 0x0800 /* Use STAT3 or STAT4 data */ #define SQLITE_AllOpts 0xffff /* All optimizations */ /* ** Macros for testing whether or not optimizations are enabled or disabled. */ #ifndef SQLITE_OMIT_BUILTIN_TEST #define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0) |
> |
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 |
#define SQLITE_DistinctOpt 0x0020 /* DISTINCT using indexes */
#define SQLITE_CoverIdxScan 0x0040 /* Covering index scans */
#define SQLITE_OrderByIdxJoin 0x0080 /* ORDER BY of joins via index */
#define SQLITE_SubqCoroutine 0x0100 /* Evaluate subqueries as coroutines */
#define SQLITE_Transitive 0x0200 /* Transitive constraints */
#define SQLITE_OmitNoopJoin 0x0400 /* Omit unused tables in joins */
#define SQLITE_Stat34 0x0800 /* Use STAT3 or STAT4 data */
#define SQLITE_LateSubquery 0x1000 /* Plan main Q before rendering subQ */
#define SQLITE_AllOpts 0xffff /* All optimizations */
/*
** Macros for testing whether or not optimizations are enabled or disabled.
*/
#ifndef SQLITE_OMIT_BUILTIN_TEST
#define OptimizationDisabled(db, mask) (((db)->dbOptFlags&(mask))!=0)
|
Changes to src/where.c.
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
....
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
4151
|
pNew->nSkip = 0;
pNew->u.btree.pIndex = 0;
pNew->nLTerm = 1;
pNew->aLTerm[0] = pTerm;
/* TUNING: One-time cost for computing the automatic index is
** estimated to be X*N*log2(N) where N is the number of rows in
** the table being indexed and where X is 7 (LogEst=28) for normal
** tables or 1.375 (LogEst=4) for views and subqueries. The value
** of X is smaller for views and subqueries so that the query planner
** will be more aggressive about generating automatic indexes for
** those objects, since there is no opportunity to add schema
** indexes on subqueries and views. */
pNew->rSetup = rLogSize + rSize + 4;
if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
pNew->rSetup += 24;
}
ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
/* TUNING: Each index lookup yields 20 rows in the table. This
** is more than the usual guess of 10 rows, since we have no way
** of knowing how selective the index will ultimately be. It would
** not be unreasonable to make this value much larger. */
pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );
pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
................................................................................
&& (pWInfo->a[0].pWLoop->wsFlags & WHERE_ONEROW)!=0 ){
pWInfo->okOnePass = 1;
if( HasRowid(pTabList->a[0].pTab) ){
pWInfo->a[0].pWLoop->wsFlags &= ~WHERE_IDX_ONLY;
}
}
#if 0
/* If this WHERE clause is part of a SELECT statement, then there
** might be subqueries in the FROM clause that need to be manifested.
** This works mostly - except the Table.nRowLogEst value is not set
** correctly for the subquery, resulting in a bad plan in some cases.
*/
if( pSelect!=0 ){
sqlite3ManifestSubqueries(pParse, pSelect, pTabList);
if( db->mallocFailed ) goto whereBeginError;
}
#endif
/* Open all tables in the pTabList and any indices selected for
** searching those tables.
*/
for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
Table *pTab; /* Table to open */
int iDb; /* Index of database containing table/index */
|
|
|
|
>
<
|
<
|
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
....
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
4138
4139
4140
4141
4142
4143
4144
4145
4146
4147
4148
4149
4150
|
pNew->nSkip = 0;
pNew->u.btree.pIndex = 0;
pNew->nLTerm = 1;
pNew->aLTerm[0] = pTerm;
/* TUNING: One-time cost for computing the automatic index is
** estimated to be X*N*log2(N) where N is the number of rows in
** the table being indexed and where X is 7 (LogEst=28) for normal
** tables or 0.3333 (LogEst=-16) for views and subqueries. The value
** of X is smaller for views and subqueries so that the query planner
** will be more aggressive about generating automatic indexes for
** those objects, since there is no opportunity to add schema
** indexes on subqueries and views. */
pNew->rSetup = rLogSize + rSize - 16;
if( pTab->pSelect==0 && (pTab->tabFlags & TF_Ephemeral)==0 ){
pNew->rSetup += 44;
}
if( pNew->rSetup<1 ) pNew->rSetup = 1;
ApplyCostMultiplier(pNew->rSetup, pTab->costMult);
/* TUNING: Each index lookup yields 20 rows in the table. This
** is more than the usual guess of 10 rows, since we have no way
** of knowing how selective the index will ultimately be. It would
** not be unreasonable to make this value much larger. */
pNew->nOut = 43; assert( 43==sqlite3LogEst(20) );
pNew->rRun = sqlite3LogEstAdd(rLogSize,pNew->nOut);
................................................................................
&& (pWInfo->a[0].pWLoop->wsFlags & WHERE_ONEROW)!=0 ){
pWInfo->okOnePass = 1;
if( HasRowid(pTabList->a[0].pTab) ){
pWInfo->a[0].pWLoop->wsFlags &= ~WHERE_IDX_ONLY;
}
}
/* If this WHERE clause is part of a SELECT statement, then there
** might be subqueries in the FROM clause that need to be manifested.
** This works mostly - except the Table.nRowLogEst value is not set
** correctly for the subquery, resulting in a bad plan in some cases.
*/
if( OptimizationEnabled(db, SQLITE_LateSubquery) && pSelect!=0 ){
sqlite3ManifestSubqueries(pParse, pSelect, pTabList);
if( db->mallocFailed ) goto whereBeginError;
}
/* Open all tables in the pTabList and any indices selected for
** searching those tables.
*/
for(ii=0, pLevel=pWInfo->a; ii<nTabList; ii++, pLevel++){
Table *pTab; /* Table to open */
int iDb; /* Index of database containing table/index */
|
Changes to test/eqp.test.
77 78 79 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 |
0 0 0 {USE TEMP B-TREE FOR GROUP BY}
0 0 0 {USE TEMP B-TREE FOR DISTINCT}
}
do_eqp_test 1.7 {
SELECT * FROM t3 JOIN (SELECT 1)
} {
0 0 1 {SCAN SUBQUERY 1}
0 1 0 {SCAN TABLE t3}
}
do_eqp_test 1.8 {
SELECT * FROM t3 JOIN (SELECT 1 UNION SELECT 2)
} {
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)}
0 0 1 {SCAN SUBQUERY 1}
0 1 0 {SCAN TABLE t3}
}
do_eqp_test 1.9 {
SELECT * FROM t3 JOIN (SELECT 1 EXCEPT SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (EXCEPT)}
0 0 1 {SCAN SUBQUERY 1}
0 1 0 {SCAN TABLE t3}
}
do_eqp_test 1.10 {
SELECT * FROM t3 JOIN (SELECT 1 INTERSECT SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (INTERSECT)}
0 0 1 {SCAN SUBQUERY 1}
0 1 0 {SCAN TABLE t3}
}
do_eqp_test 1.11 {
SELECT * FROM t3 JOIN (SELECT 1 UNION ALL SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 (UNION ALL)}
0 0 1 {SCAN SUBQUERY 1}
0 1 0 {SCAN TABLE t3}
}
#-------------------------------------------------------------------------
# Test cases eqp-2.* - tests for single select statements.
#
drop_all_tables
do_execsql_test 2.1 {
|
< | > < | > < | > < | > < | > |
77 78 79 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 |
0 0 0 {USE TEMP B-TREE FOR GROUP BY}
0 0 0 {USE TEMP B-TREE FOR DISTINCT}
}
do_eqp_test 1.7 {
SELECT * FROM t3 JOIN (SELECT 1)
} {
0 0 0 {SCAN TABLE t3}
0 1 1 {SCAN SUBQUERY 1}
}
do_eqp_test 1.8 {
SELECT * FROM t3 JOIN (SELECT 1 UNION SELECT 2)
} {
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (UNION)}
0 0 0 {SCAN TABLE t3}
0 1 1 {SCAN SUBQUERY 1}
}
do_eqp_test 1.9 {
SELECT * FROM t3 JOIN (SELECT 1 EXCEPT SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (EXCEPT)}
0 0 0 {SCAN TABLE t3}
0 1 1 {SCAN SUBQUERY 1}
}
do_eqp_test 1.10 {
SELECT * FROM t3 JOIN (SELECT 1 INTERSECT SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 USING TEMP B-TREE (INTERSECT)}
0 0 0 {SCAN TABLE t3}
0 1 1 {SCAN SUBQUERY 1}
}
do_eqp_test 1.11 {
SELECT * FROM t3 JOIN (SELECT 1 UNION ALL SELECT a FROM t3 LIMIT 17)
} {
3 0 0 {SCAN TABLE t3}
1 0 0 {COMPOUND SUBQUERIES 2 AND 3 (UNION ALL)}
0 0 0 {SCAN TABLE t3}
0 1 1 {SCAN SUBQUERY 1}
}
#-------------------------------------------------------------------------
# Test cases eqp-2.* - tests for single select statements.
#
drop_all_tables
do_execsql_test 2.1 {
|