Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | When the estimated sorting cost overwhelms the estimated lookup cost, ensure that lookup costs are still taken into account when selecting a lookup algorithm. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
2af630c5720a4d71f22a952af29346a0 |
User & Date: | drh 2014-08-07 20:42:33.655 |
References
2014-08-08
| ||
16:52 | Because SQLite internally calculates query plan costs using a logarithmic scale, very large estimated sorting costs can cause all other estimated costs to be rounded down to zero. In these cases break ties between plans with the same total cost by comparing the costs with sorting excluded. This is an alternative fix for the problem addressed by [2af630c572]. (check-in: 299b957027 user: dan tags: query-planner-fix) | |
Context
2014-08-08
| ||
12:51 | Reworking the documentation on integer result codes. This is a comment and documentation change only. There are no changes to code. (check-in: 54f1df7b63 user: drh tags: trunk) | |
2014-08-07
| ||
20:42 | When the estimated sorting cost overwhelms the estimated lookup cost, ensure that lookup costs are still taken into account when selecting a lookup algorithm. (check-in: 2af630c572 user: drh tags: trunk) | |
20:37 | Clarify the computation of compatible isOrdered by in the plan solver of the query planner. (Closed-Leaf check-in: b5e8fd575a user: drh tags: query-planner-fix) | |
2014-08-06
| ||
18:50 | A couple more harmless compiler warnings eliminated. (check-in: bcf6d775f9 user: drh tags: trunk) | |
Changes
Changes to src/where.c.
︙ | ︙ | |||
5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 | int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ int nOrderBy; /* Number of ORDER BY clause terms */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ WhereLoop *pWLoop; /* One of the WhereLoop objects */ WhereLoop **pX; /* Used to divy up the pSpace memory */ char *pSpace; /* Temporary memory used by this routine */ pParse = pWInfo->pParse; db = pParse->db; nLoop = pWInfo->nLevel; /* TUNING: For simple queries, only the best path is tracked. ** For 2-way joins, the 5 best paths are followed. ** For joins of 3 or more tables, track the 10 best paths */ mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10); assert( nLoop<=pWInfo->pTabList->nSrc ); | > | | 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 5444 5445 5446 5447 5448 5449 5450 5451 5452 | int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ int mxI = 0; /* Index of next entry to replace */ int nOrderBy; /* Number of ORDER BY clause terms */ LogEst rCost; /* Cost of a path */ LogEst nOut; /* Number of outputs */ LogEst mxCost = 0; /* Maximum cost of a set of paths */ LogEst mxOut = 0; /* nOut value for maximum cost path */ int nTo, nFrom; /* Number of valid entries in aTo[] and aFrom[] */ WherePath *aFrom; /* All nFrom paths at the previous level */ WherePath *aTo; /* The nTo best paths at the current level */ WherePath *pFrom; /* An element of aFrom[] that we are working on */ WherePath *pTo; /* An element of aTo[] that we are working on */ WhereLoop *pWLoop; /* One of the WhereLoop objects */ WhereLoop **pX; /* Used to divy up the pSpace memory */ char *pSpace; /* Temporary memory used by this routine */ pParse = pWInfo->pParse; db = pParse->db; nLoop = pWInfo->nLevel; /* TUNING: For simple queries, only the best path is tracked. ** For 2-way joins, the 5 best paths are followed. ** For joins of 3 or more tables, track the 10 best paths */ mxChoice = (nLoop<=1) ? 1 : (nLoop==2 ? 5 : 10); assert( nLoop<=pWInfo->pTabList->nSrc ); WHERETRACE(0x002, ("---- begin solver. (nRowEst=%d)\n", nRowEst)); /* Allocate and initialize space for aTo and aFrom */ ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2; pSpace = sqlite3DbMallocRaw(db, ii); if( pSpace==0 ) return SQLITE_NOMEM; aTo = (WherePath*)pSpace; aFrom = aTo+mxChoice; |
︙ | ︙ | |||
5525 5526 5527 5528 5529 5530 5531 | rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost, sqlite3LogEstAdd(rCost,rSortCost))); rCost = sqlite3LogEstAdd(rCost, rSortCost); } }else{ revMask = pFrom->revLoop; } | | > > > > > > > > > > | > | > > > > > > | > > > > | > | > | 5526 5527 5528 5529 5530 5531 5532 5533 5534 5535 5536 5537 5538 5539 5540 5541 5542 5543 5544 5545 5546 5547 5548 5549 5550 5551 5552 5553 5554 5555 5556 5557 5558 5559 5560 5561 5562 5563 5564 5565 5566 5567 5568 5569 5570 5571 5572 5573 5574 5575 5576 5577 5578 5579 5580 5581 5582 5583 5584 5585 5586 5587 5588 5589 5590 5591 5592 5593 5594 5595 5596 5597 5598 5599 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 5615 5616 | rSortCost, (nOrderBy-isOrdered), nOrderBy, rCost, sqlite3LogEstAdd(rCost,rSortCost))); rCost = sqlite3LogEstAdd(rCost, rSortCost); } }else{ revMask = pFrom->revLoop; } /* Check to see if pWLoop should be added to the set of ** mxChoice best-so-far paths. ** ** First look for an existing path among best-so-far paths ** that covers the same set of loops and has the same isOrdered ** setting as the current path candidate. ** ** The term "((pTo->isOrdered^isOrdered)&0x80)==0" is equivalent ** to (pTo->isOrdered==(-1))==(isOrdered==(-1))" for the range ** of legal values for isOrdered, -1..64. */ for(jj=0, pTo=aTo; jj<nTo; jj++, pTo++){ if( pTo->maskLoop==maskNew && ((pTo->isOrdered^isOrdered)&0x80)==0 ){ testcase( jj==nTo-1 ); break; } } if( jj>=nTo ){ /* None of the existing best-so-far paths match the candidate. */ if( nTo>=mxChoice && (rCost>mxCost || (rCost==mxCost && nOut>=mxOut)) ){ /* The current candidate is no better than any of the mxChoice ** paths currently in the best-so-far buffer. So discard ** this candidate as not viable. */ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("Skip %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); } #endif continue; } /* If we reach this points it means that the new candidate path ** needs to be added to the set of best-so-far paths. */ if( nTo<mxChoice ){ /* Increase the size of the aTo set by one */ jj = nTo++; }else{ /* New path replaces the prior worst to keep count below mxChoice */ jj = mxI; } pTo = &aTo[jj]; #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf("New %s cost=%-3d,%3d order=%c\n", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); } #endif }else{ /* Control reaches here if best-so-far path pTo=aTo[jj] covers the ** same set of loops and has the sam isOrdered setting as the ** candidate path. Check to see if the candidate should replace ** pTo or if the candidate should be skipped */ if( pTo->rCost<rCost || (pTo->rCost==rCost && pTo->nRow<=nOut) ){ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( "Skip %s cost=%-3d,%3d order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); sqlite3DebugPrintf(" vs %s cost=%-3d,%d order=%c\n", wherePathName(pTo, iLoop+1, 0), pTo->rCost, pTo->nRow, pTo->isOrdered>=0 ? pTo->isOrdered+'0' : '?'); } #endif /* Discard the candidate path from further consideration */ testcase( pTo->rCost==rCost ); continue; } testcase( pTo->rCost==rCost+1 ); /* Control reaches here if the candidate path is better than the ** pTo path. Replace pTo with the candidate. */ #ifdef WHERETRACE_ENABLED /* 0x4 */ if( sqlite3WhereTrace&0x4 ){ sqlite3DebugPrintf( "Update %s cost=%-3d,%3d order=%c", wherePathName(pFrom, iLoop, pWLoop), rCost, nOut, isOrdered>=0 ? isOrdered+'0' : '?'); sqlite3DebugPrintf(" was %s cost=%-3d,%3d order=%c\n", |
︙ | ︙ | |||
5602 5603 5604 5605 5606 5607 5608 5609 | pTo->rCost = rCost; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; mxCost = aTo[0].rCost; for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ | > | > | 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 5636 5637 5638 5639 5640 5641 5642 5643 5644 | pTo->rCost = rCost; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; mxCost = aTo[0].rCost; mxOut = aTo[0].nRow; for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->nRow>mxOut) ){ mxCost = pTo->rCost; mxOut = pTo->nRow; mxI = jj; } } } } } |
︙ | ︙ |
Changes to test/whereJ.test.
1 2 3 4 5 6 7 8 9 10 11 | # 2014-06-06 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | # 2014-06-06 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #*********************************************************************** # # This file implements regression tests for a complex # query planning case. # set testdir [file dirname $argv0] source $testdir/tester.tcl set ::testprefix whereJ |
︙ | ︙ | |||
323 324 325 326 327 328 329 330 331 | SELECT aid, sid, MAX(edate) edate FROM tx1 WHERE cid = 115790 AND sid = 9100 AND edate <= 20140430 AND edate >= 20120429 GROUP BY aid; } {/B-TREE/} finish_test | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 | SELECT aid, sid, MAX(edate) edate FROM tx1 WHERE cid = 115790 AND sid = 9100 AND edate <= 20140430 AND edate >= 20120429 GROUP BY aid; } {/B-TREE/} ############################################################################ # Ensure that the sorting cost does not swamp the loop costs and cause # distinctions between individual loop costs to get lost, and hence for # sub-optimal loops to be chosen. # do_execsql_test whereJ-2.1 { CREATE TABLE tab( id INTEGER PRIMARY KEY, minChild INTEGER REFERENCES t1, maxChild INTEGER REFERENCES t1, x INTEGER ); EXPLAIN QUERY PLAN SELECT t4.x FROM tab AS t0, tab AS t1, tab AS t2, tab AS t3, tab AS t4 WHERE t0.id=0 AND t1.id BETWEEN t0.minChild AND t0.maxChild AND t2.id BETWEEN t1.minChild AND t1.maxChild AND t3.id BETWEEN t2.minChild AND t2.maxChild AND t4.id BETWEEN t3.minChild AND t3.maxChild ORDER BY t4.x; } {~/SCAN/} do_execsql_test whereJ-2.2 { EXPLAIN QUERY PLAN SELECT t4.x FROM tab AS t0a, tab AS t0b, tab AS t1a, tab AS t1b, tab AS t2a, tab AS t2b, tab AS t3a, tab AS t3b, tab AS t4 WHERE 1 AND t0a.id=1 AND t1a.id BETWEEN t0a.minChild AND t0a.maxChild AND t2a.id BETWEEN t1a.minChild AND t1a.maxChild AND t3a.id BETWEEN t2a.minChild AND t2a.maxChild AND t0b.id=2 AND t1b.id BETWEEN t0b.minChild AND t0b.maxChild AND t2b.id BETWEEN t1b.minChild AND t1b.maxChild AND t3b.id BETWEEN t2b.minChild AND t2b.maxChild AND t4.id BETWEEN t3a.minChild AND t3b.maxChild ORDER BY t4.x; } {~/SCAN/} finish_test |