Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Changes In Branch query-planner-fix Excluding Merge-Ins
This is equivalent to a diff from 36b7c5cefc to 43c59c8543
2014-08-08
| ||
17:49 | Improvements to the way the query planner handles sorting costs, so that very large sorting costs do not overwhelm the loop costs. (check-in: bdaa694737 user: drh tags: trunk) | |
17:25 | Fix a buffer overrun in the previous commit. (Closed-Leaf check-in: 43c59c8543 user: dan tags: query-planner-fix) | |
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) | |
15:38 | The SQLITE_IOERR_BLOCKED extended error code is not longer used, so remove assert() statements and documentation for that error code. Also make other documentation improvements. (check-in: 36b7c5cefc user: drh tags: trunk) | |
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) | |
Changes to src/where.c.
︙ | ︙ | |||
5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 | int i; for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; } if( pLast ) zName[i++] = pLast->cId; zName[i] = 0; return zName; } #endif /* ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine ** attempts to find the lowest cost path that visits each WhereLoop ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. ** ** Assume that the total number of output rows that will need to be sorted | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 5406 5407 5408 5409 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 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 | int i; for(i=0; i<nLoop; i++){ zName[i] = pPath->aLoop[i]->cId; } if( pLast ) zName[i++] = pLast->cId; zName[i] = 0; return zName; } #endif /* ** Return the cost of sorting nRow rows, assuming that the keys have ** nOrderby columns and that the first nSorted columns are already in ** order. */ static LogEst whereSortingCost( WhereInfo *pWInfo, LogEst nRow, int nOrderBy, int nSorted ){ /* TUNING: Estimated cost of a full external sort, where N is ** the number of rows to sort is: ** ** cost = (3.0 * N * log(N)). ** ** Or, if the order-by clause has X terms but only the last Y ** terms are out of order, then block-sorting will reduce the ** sorting cost to: ** ** cost = (3.0 * N * log(N)) * (Y/X) ** ** The (Y/X) term is implemented using stack variable rScale ** below. */ LogEst rScale, rSortCost; assert( nOrderBy>0 && 66==sqlite3LogEst(100) ); rScale = sqlite3LogEst((nOrderBy-nSorted)*100/nOrderBy) - 66; rSortCost = nRow + estLog(nRow) + rScale + 16; /* TUNING: The cost of implementing DISTINCT using a B-TREE is ** similar but with a larger constant of proportionality. ** Multiply by an additional factor of 3.0. */ if( pWInfo->wctrlFlags & WHERE_WANT_DISTINCT ){ rSortCost += 16; } return rSortCost; } /* ** Given the list of WhereLoop objects at pWInfo->pLoops, this routine ** attempts to find the lowest cost path that visits each WhereLoop ** once. This path is then loaded into the pWInfo->a[].pWLoop fields. ** ** Assume that the total number of output rows that will need to be sorted |
︙ | ︙ | |||
5417 5418 5419 5420 5421 5422 5423 | int nLoop; /* Number of terms in the join */ Parse *pParse; /* Parsing context */ sqlite3 *db; /* The database connection */ 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 */ | < < | > > > > > > > > > > > > > | | > | > > > > > > > > > > > > < < < < | | > > > > | > | < > > > > | | | | | > > > | < < < < < < < < < < < < < | < | | > | < < < < | | | | | | > | | < < | | 5456 5457 5458 5459 5460 5461 5462 5463 5464 5465 5466 5467 5468 5469 5470 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 5522 5523 5524 5525 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 | int nLoop; /* Number of terms in the join */ Parse *pParse; /* Parsing context */ sqlite3 *db; /* The database connection */ 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 mxCost = 0; /* Maximum cost of a set of paths */ LogEst mxUnsorted = 0; /* Maximum unsorted cost of a set of 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 */ LogEst *aSortCost = 0; /* Sorting and partial sorting costs */ char *pSpace; /* Temporary memory used by this routine */ int nSpace; /* Bytes of space allocated at pSpace */ 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)); /* If nRowEst is zero and there is an ORDER BY clause, ignore it. In this ** case the purpose of this call is to estimate the number of rows returned ** by the overall query. Once this estimate has been obtained, the caller ** will invoke this function a second time, passing the estimate as the ** nRowEst parameter. */ if( pWInfo->pOrderBy==0 || nRowEst==0 ){ nOrderBy = 0; }else{ nOrderBy = pWInfo->pOrderBy->nExpr; } /* Allocate and initialize space for aTo, aFrom and aSortCost[] */ nSpace = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2; nSpace += sizeof(LogEst) * nOrderBy; pSpace = sqlite3DbMallocRaw(db, nSpace); if( pSpace==0 ) return SQLITE_NOMEM; aTo = (WherePath*)pSpace; aFrom = aTo+mxChoice; memset(aFrom, 0, sizeof(aFrom[0])); pX = (WhereLoop**)(aFrom+mxChoice); for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){ pFrom->aLoop = pX; } if( nOrderBy ){ /* If there is an ORDER BY clause and it is not being ignored, set up ** space for the aSortCost[] array. Each element of the aSortCost array ** is either zero - meaning it has not yet been initialized - or the ** cost of sorting nRowEst rows of data where the first X terms of ** the ORDER BY clause are already in order, where X is the array ** index. */ aSortCost = (LogEst*)pX; memset(aSortCost, 0, sizeof(LogEst) * nOrderBy); } assert( aSortCost==0 || &pSpace[nSpace]==(char*)&aSortCost[nOrderBy] ); assert( aSortCost!=0 || &pSpace[nSpace]==(char*)pX ); /* Seed the search with a single WherePath containing zero WhereLoops. ** ** TUNING: Do not let the number of iterations go above 25. If the cost ** of computing an automatic index is not paid back within the first 25 ** rows, then do not use the automatic index. */ aFrom[0].nRow = MIN(pParse->nQueryLoop, 46); assert( 46==sqlite3LogEst(25) ); nFrom = 1; assert( aFrom[0].isOrdered==0 ); if( nOrderBy ){ /* If nLoop is zero, then there are no FROM terms in the query. Since ** in this case the query may return a maximum of one row, the results ** are already in the requested order. Set isOrdered to nOrderBy to ** indicate this. Or, if nLoop is greater than zero, set isOrdered to ** -1, indicating that the result set may or may not be ordered, ** depending on the loops added to the current plan. */ aFrom[0].isOrdered = nLoop>0 ? -1 : nOrderBy; } /* Compute successively longer WherePaths using the previous generation ** of WherePaths as the basis for the next. Keep track of the mxChoice ** best paths at each generation */ for(iLoop=0; iLoop<nLoop; iLoop++){ nTo = 0; for(ii=0, pFrom=aFrom; ii<nFrom; ii++, pFrom++){ for(pWLoop=pWInfo->pLoops; pWLoop; pWLoop=pWLoop->pNextLoop){ LogEst nOut; /* Rows visited by (pFrom+pWLoop) */ LogEst rCost; /* Cost of path (pFrom+pWLoop) */ LogEst rUnsorted; /* Unsorted cost of (pFrom+pWLoop) */ i8 isOrdered = pFrom->isOrdered; /* isOrdered for (pFrom+pWLoop) */ Bitmask maskNew; /* Mask of src visited by (..) */ Bitmask revMask = 0; /* Mask of rev-order loops for (..) */ if( (pWLoop->prereq & ~pFrom->maskLoop)!=0 ) continue; if( (pWLoop->maskSelf & pFrom->maskLoop)!=0 ) continue; /* At this point, pWLoop is a candidate to be the next loop. ** Compute its cost */ rUnsorted = sqlite3LogEstAdd(pWLoop->rSetup,pWLoop->rRun + pFrom->nRow); rUnsorted = sqlite3LogEstAdd(rUnsorted, pFrom->rUnsorted); nOut = pFrom->nRow + pWLoop->nOut; maskNew = pFrom->maskLoop | pWLoop->maskSelf; if( isOrdered<0 ){ isOrdered = wherePathSatisfiesOrderBy(pWInfo, pWInfo->pOrderBy, pFrom, pWInfo->wctrlFlags, iLoop, pWLoop, &revMask); }else{ revMask = pFrom->revLoop; } if( isOrdered>=0 && isOrdered<nOrderBy ){ if( aSortCost[isOrdered]==0 ){ aSortCost[isOrdered] = whereSortingCost( pWInfo, nRowEst, nOrderBy, isOrdered ); } rCost = sqlite3LogEstAdd(rUnsorted, aSortCost[isOrdered]); WHERETRACE(0x002, ("---- sort cost=%-3d (%d/%d) increases cost %3d to %-3d\n", aSortCost[isOrdered], (nOrderBy-isOrdered), nOrderBy, rUnsorted, rCost)); }else{ rCost = rUnsorted; } /* 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. ** |
︙ | ︙ | |||
5548 5549 5550 5551 5552 5553 5554 | testcase( jj==nTo-1 ); break; } } if( jj>=nTo ){ /* None of the existing best-so-far paths match the candidate. */ if( nTo>=mxChoice | | | 5600 5601 5602 5603 5604 5605 5606 5607 5608 5609 5610 5611 5612 5613 5614 | 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 && rUnsorted>=mxUnsorted)) ){ /* 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", |
︙ | ︙ | |||
5620 5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 | #endif } /* pWLoop is a winner. Add it to the set of best so far */ pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; pTo->revLoop = revMask; pTo->nRow = nOut; 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; | > | | > > | | 5672 5673 5674 5675 5676 5677 5678 5679 5680 5681 5682 5683 5684 5685 5686 5687 5688 5689 5690 5691 5692 5693 5694 5695 5696 5697 5698 5699 | #endif } /* pWLoop is a winner. Add it to the set of best so far */ pTo->maskLoop = pFrom->maskLoop | pWLoop->maskSelf; pTo->revLoop = revMask; pTo->nRow = nOut; pTo->rCost = rCost; pTo->rUnsorted = rUnsorted; pTo->isOrdered = isOrdered; memcpy(pTo->aLoop, pFrom->aLoop, sizeof(WhereLoop*)*iLoop); pTo->aLoop[iLoop] = pWLoop; if( nTo>=mxChoice ){ mxI = 0; mxCost = aTo[0].rCost; mxUnsorted = aTo[0].nRow; for(jj=1, pTo=&aTo[1]; jj<mxChoice; jj++, pTo++){ if( pTo->rCost>mxCost || (pTo->rCost==mxCost && pTo->rUnsorted>mxUnsorted) ){ mxCost = pTo->rCost; mxUnsorted = pTo->rUnsorted; mxI = jj; } } } } } |
︙ | ︙ |
Changes to src/whereInt.h.
︙ | ︙ | |||
179 180 181 182 183 184 185 186 187 188 189 190 191 192 | ** at the end is the choosen query plan. */ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ LogEst nRow; /* Estimated number of rows generated by this path */ LogEst rCost; /* Total cost of this path */ i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */ WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ }; /* ** The query generator uses an array of instances of this structure to ** help it analyze the subexpressions of the WHERE clause. Each WHERE | > | 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 | ** at the end is the choosen query plan. */ struct WherePath { Bitmask maskLoop; /* Bitmask of all WhereLoop objects in this path */ Bitmask revLoop; /* aLoop[]s that should be reversed for ORDER BY */ LogEst nRow; /* Estimated number of rows generated by this path */ LogEst rCost; /* Total cost of this path */ LogEst rUnsorted; /* Total cost of this path ignoring sorting costs */ i8 isOrdered; /* No. of ORDER BY terms satisfied. -1 for unknown */ WhereLoop **aLoop; /* Array of WhereLoop objects implementing this path */ }; /* ** The query generator uses an array of instances of this structure to ** help it analyze the subexpressions of the WHERE clause. Each WHERE |
︙ | ︙ |