Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix problems caused by over-agressive optimization of ORDER BY in joins. Lots more testing needed. (CVS 2571) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
1a4e526d46280970b43505a5c8a40907 |
User & Date: | drh 2005-07-29 19:43:58.000 |
Context
2005-08-02
| ||
12:21 | Add the "transaction" coommand to the TCL interface. Untested. (CVS 2572) (check-in: a5ce6c58c3 user: drh tags: trunk) | |
2005-07-29
| ||
19:43 | Fix problems caused by over-agressive optimization of ORDER BY in joins. Lots more testing needed. (CVS 2571) (check-in: 1a4e526d46 user: drh tags: trunk) | |
15:36 | Fix authentication so that it works with AS aliases. Ticket #1338. (CVS 2570) (check-in: cc7ae73ed0 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
12 13 14 15 16 17 18 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is reponsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** | | | 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | ** This module contains C code that generates VDBE code used to process ** the WHERE clause of SQL statements. This module is reponsible for ** generating the code that loops through a table looking for applicable ** rows. Indices are selected and used to speed the search when doing ** so is applicable. Because this module is responsible for selecting ** indices, you might also think of this module as the "query optimizer". ** ** $Id: where.c,v 1.158 2005/07/29 19:43:58 drh Exp $ */ #include "sqliteInt.h" /* ** The number of bits in a Bitmask. "BMS" means "BitMask Size". */ #define BMS (sizeof(Bitmask)*8) |
︙ | ︙ | |||
167 168 169 170 171 172 173 174 175 176 177 178 179 180 | #define WHERE_COLUMN_RANGE 0x0020 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x0040 /* x IN (...) */ #define WHERE_TOP_LIMIT 0x0100 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x0200 /* x>EXPR or x>=EXPR constraint */ #define WHERE_IDX_ONLY 0x0800 /* Use index only - omit table */ #define WHERE_ORDERBY 0x1000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x2000 /* Scan in reverse order */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit(WhereClause *pWC, Parse *pParse){ pWC->pParse = pParse; pWC->nTerm = 0; | > | 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 | #define WHERE_COLUMN_RANGE 0x0020 /* x<EXPR and/or x>EXPR */ #define WHERE_COLUMN_IN 0x0040 /* x IN (...) */ #define WHERE_TOP_LIMIT 0x0100 /* x<EXPR or x<=EXPR constraint */ #define WHERE_BTM_LIMIT 0x0200 /* x>EXPR or x>=EXPR constraint */ #define WHERE_IDX_ONLY 0x0800 /* Use index only - omit table */ #define WHERE_ORDERBY 0x1000 /* Output will appear in correct order */ #define WHERE_REVERSE 0x2000 /* Scan in reverse order */ #define WHERE_UNIQUE 0x4000 /* Selects no more than one row */ /* ** Initialize a preallocated WhereClause structure. */ static void whereClauseInit(WhereClause *pWC, Parse *pParse){ pWC->pParse = pParse; pWC->nTerm = 0; |
︙ | ︙ | |||
637 638 639 640 641 642 643 | struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ sqlite3 *db = pParse->db; assert( pOrderBy!=0 ); nTerm = pOrderBy->nExpr; assert( nTerm>0 ); | < < < < < < < < | 638 639 640 641 642 643 644 645 646 647 648 649 650 651 | struct ExprList_item *pTerm; /* A term of the ORDER BY clause */ sqlite3 *db = pParse->db; assert( pOrderBy!=0 ); nTerm = pOrderBy->nExpr; assert( nTerm>0 ); /* Match terms of the ORDER BY clause against columns of ** the index. */ for(i=j=0, pTerm=pOrderBy->a; j<nTerm && i<pIdx->nColumn; i++){ Expr *pExpr; /* The expression of the ORDER BY pTerm */ CollSeq *pColl; /* The collating sequence of pExpr */ |
︙ | ︙ | |||
791 792 793 794 795 796 797 | if( pTerm ){ Expr *pExpr; *ppIndex = 0; bestFlags = WHERE_ROWID_EQ; if( pTerm->operator & WO_EQ ){ /* Rowid== is always the best pick. Look no further. Because only ** a single row is generated, output is always in sorted order */ | | < | 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 | if( pTerm ){ Expr *pExpr; *ppIndex = 0; bestFlags = WHERE_ROWID_EQ; if( pTerm->operator & WO_EQ ){ /* Rowid== is always the best pick. Look no further. Because only ** a single row is generated, output is always in sorted order */ *pFlags = WHERE_ROWID_EQ | WHERE_UNIQUE; *pnEq = 1; TRACE(("... best is rowid\n")); return 0.0; }else if( (pExpr = pTerm->pExpr)->pList!=0 ){ /* Rowid IN (LIST): cost is NlogN where N is the number of list ** elements. */ lowestCost = pExpr->pList->nExpr; lowestCost *= estLog(lowestCost); |
︙ | ︙ | |||
882 883 884 885 886 887 888 889 890 891 892 893 894 895 | }else if( pExpr->pList!=0 ){ inMultiplier *= pExpr->pList->nExpr + 1.0; } } } cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier); nEq = i; TRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost)); /* Look for range constraints */ if( nEq<pProbe->nColumn ){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe); | > > > > | 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 | }else if( pExpr->pList!=0 ){ inMultiplier *= pExpr->pList->nExpr + 1.0; } } } cost = pProbe->aiRowEst[i] * inMultiplier * estLog(inMultiplier); nEq = i; if( pProbe->onError!=OE_None && (flags & WHERE_COLUMN_IN)==0 && nEq==pProbe->nColumn ){ flags |= WHERE_UNIQUE; } TRACE(("...... nEq=%d inMult=%.9g cost=%.9g\n", nEq, inMultiplier, cost)); /* Look for range constraints */ if( nEq<pProbe->nColumn ){ int j = pProbe->aiColumn[nEq]; pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe); |
︙ | ︙ | |||
1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 | Bitmask notReady; /* Cursors that are not yet positioned */ WhereTerm *pTerm; /* A single term in the WHERE clause */ ExprMaskSet maskSet; /* The expression mask set */ WhereClause wc; /* The WHERE clause is divided into these terms */ struct SrcList_item *pTabItem; /* A single entry from pTabList */ WhereLevel *pLevel; /* A single level in the pWInfo list */ int iFrom; /* First unused FROM clause element */ /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); return 0; | > | 1254 1255 1256 1257 1258 1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 | Bitmask notReady; /* Cursors that are not yet positioned */ WhereTerm *pTerm; /* A single term in the WHERE clause */ ExprMaskSet maskSet; /* The expression mask set */ WhereClause wc; /* The WHERE clause is divided into these terms */ struct SrcList_item *pTabItem; /* A single entry from pTabList */ WhereLevel *pLevel; /* A single level in the pWInfo list */ int iFrom; /* First unused FROM clause element */ int andFlags; /* AND-ed combination of all wc.a[].flags */ /* The number of tables in the FROM clause is limited by the number of ** bits in a Bitmask */ if( pTabList->nSrc>BMS ){ sqlite3ErrorMsg(pParse, "at most %d tables in a join", BMS); return 0; |
︙ | ︙ | |||
1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 | ** ** This loop also figures out the nesting order of tables in the FROM ** clause. */ notReady = ~(Bitmask)0; pTabItem = pTabList->a; pLevel = pWInfo->a; for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){ Index *pIdx; /* Index for FROM table at pTabItem */ int flags; /* Flags asssociated with pIdx */ int nEq; /* Number of == or IN constraints */ double cost; /* The cost for pIdx */ int j; /* For looping over FROM tables */ Index *pBest = 0; /* The best index seen so far */ | > | 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 | ** ** This loop also figures out the nesting order of tables in the FROM ** clause. */ notReady = ~(Bitmask)0; pTabItem = pTabList->a; pLevel = pWInfo->a; andFlags = ~0; for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){ Index *pIdx; /* Index for FROM table at pTabItem */ int flags; /* Flags asssociated with pIdx */ int nEq; /* Number of == or IN constraints */ double cost; /* The cost for pIdx */ int j; /* For looping over FROM tables */ Index *pBest = 0; /* The best index seen so far */ |
︙ | ︙ | |||
1355 1356 1357 1358 1359 1360 1361 | } if( (pTabItem->jointype & JT_LEFT)!=0 || (j>0 && (pTabItem[-1].jointype & JT_LEFT)!=0) ){ break; } } | | > > > > > > > > | 1353 1354 1355 1356 1357 1358 1359 1360 1361 1362 1363 1364 1365 1366 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 | } if( (pTabItem->jointype & JT_LEFT)!=0 || (j>0 && (pTabItem[-1].jointype & JT_LEFT)!=0) ){ break; } } if( (bestFlags & WHERE_ORDERBY)!=0 ){ *ppOrderBy = 0; } andFlags &= bestFlags; pLevel->flags = bestFlags; pLevel->pIdx = pBest; pLevel->nEq = bestNEq; pLevel->aInLoop = 0; pLevel->nIn = 0; if( pBest ){ pLevel->iIdxCur = pParse->nTab++; }else{ pLevel->iIdxCur = -1; } notReady &= ~getMask(&maskSet, pTabList->a[bestJ].iCursor); pLevel->iFrom = bestJ; } /* If the total query only selects a single row, then the ORDER BY ** clause is irrelevant. */ if( (andFlags & WHERE_UNIQUE)!=0 && ppOrderBy ){ *ppOrderBy = 0; } /* Open all tables in the pTabList and any indices selected for ** searching those tables. */ sqlite3CodeVerifySchema(pParse, -1); /* Insert the cookie verifier Goto */ pLevel = pWInfo->a; for(i=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){ |
︙ | ︙ |
Changes to test/where2.test.
︙ | ︙ | |||
8 9 10 11 12 13 14 | # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clauses # based on recent changes to the optimizer. # | | | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | # May you share freely, never taking more than you give. # #*********************************************************************** # This file implements regression tests for SQLite library. The # focus of this file is testing the use of indices in WHERE clauses # based on recent changes to the optimizer. # # $Id: where2.test,v 1.4 2005/07/29 19:43:59 drh Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl # Build some test data # do_test where2-1.0 { |
︙ | ︙ | |||
219 220 221 222 223 224 225 | } } {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}} do_test where2-6.4 { queryplan { SELECT * FROM t1 WHERE w=99 OR +w=100 OR 6=w ORDER BY +w } } {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}} | < < | 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | } } {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}} do_test where2-6.4 { queryplan { SELECT * FROM t1 WHERE w=99 OR +w=100 OR 6=w ORDER BY +w } } {6 2 49 51 99 6 10000 10006 100 6 10201 10207 sort t1 {}} do_test where2-6.5 { queryplan { SELECT b.* FROM t1 a, t1 b WHERE a.w=1 AND (a.y=b.z OR b.z=10) ORDER BY +b.w } } {1 0 4 4 2 1 9 10 sort a i1w b i1zyx} do_test where2-6.6 { queryplan { SELECT b.* FROM t1 a, t1 b WHERE a.w=1 AND (b.z=10 OR a.y=b.z OR b.z=10) ORDER BY +b.w } } {1 0 4 4 2 1 9 10 sort a i1w b i1zyx} finish_test |