Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Make the MIN() and MAX() macros available in sqliteInt.h. Add TUNING comments to the NGQP and adjust costs slightly. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | nextgen-query-plan-exp |
Files: | files | file ages | folders |
SHA1: |
3a72af2a95b04b8e195ef17cb3e9d902 |
User & Date: | drh 2013-06-13 15:16:53.047 |
Context
2013-06-13
| ||
15:50 | Restore the ability to do a BETWEEN query on the rowid. Also fix a nearby comment. (check-in: 459a7b9068 user: drh tags: nextgen-query-plan-exp) | |
15:16 | Make the MIN() and MAX() macros available in sqliteInt.h. Add TUNING comments to the NGQP and adjust costs slightly. (check-in: 3a72af2a95 user: drh tags: nextgen-query-plan-exp) | |
14:51 | Fix an off-by-one error in the WhereCost to integer conversion. (check-in: b5ca80d924 user: drh tags: nextgen-query-plan-exp) | |
Changes
Changes to src/backup.c.
︙ | ︙ | |||
11 12 13 14 15 16 17 | ************************************************************************* ** This file contains the implementation of the sqlite3_backup_XXX() ** API functions and the related features. */ #include "sqliteInt.h" #include "btreeInt.h" | < < < < < < | 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | ************************************************************************* ** This file contains the implementation of the sqlite3_backup_XXX() ** API functions and the related features. */ #include "sqliteInt.h" #include "btreeInt.h" /* ** Structure allocated for each backup operation. */ struct sqlite3_backup { sqlite3* pDestDb; /* Destination database handle */ Btree *pDest; /* Destination b-tree file */ u32 iDestSchema; /* Original schema cookie in destination */ |
︙ | ︙ |
Changes to src/memjournal.c.
︙ | ︙ | |||
27 28 29 30 31 32 33 | ** The size chosen is a little less than a power of two. That way, ** the FileChunk object will have a size that almost exactly fills ** a power-of-two allocation. This mimimizes wasted space in power-of-two ** memory allocators. */ #define JOURNAL_CHUNKSIZE ((int)(1024-sizeof(FileChunk*))) | < < < < < < | 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | ** The size chosen is a little less than a power of two. That way, ** the FileChunk object will have a size that almost exactly fills ** a power-of-two allocation. This mimimizes wasted space in power-of-two ** memory allocators. */ #define JOURNAL_CHUNKSIZE ((int)(1024-sizeof(FileChunk*))) /* ** The rollback journal is composed of a linked list of these structures. */ struct FileChunk { FileChunk *pNext; /* Next chunk in the journal */ u8 zChunk[JOURNAL_CHUNKSIZE]; /* Content of this chunk */ }; |
︙ | ︙ |
Changes to src/os_win.c.
︙ | ︙ | |||
80 81 82 83 84 85 86 | /* ** This file mapping API is common to both Win32 and WinRT. */ WINBASEAPI BOOL WINAPI UnmapViewOfFile(LPCVOID); #endif /* SQLITE_WIN32_FILEMAPPING_API && !defined(SQLITE_OMIT_WAL) */ | < < < < < < < | 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | /* ** This file mapping API is common to both Win32 and WinRT. */ WINBASEAPI BOOL WINAPI UnmapViewOfFile(LPCVOID); #endif /* SQLITE_WIN32_FILEMAPPING_API && !defined(SQLITE_OMIT_WAL) */ /* ** Some Microsoft compilers lack this definition. */ #ifndef INVALID_FILE_ATTRIBUTES # define INVALID_FILE_ATTRIBUTES ((DWORD)-1) #endif |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
391 392 393 394 395 396 397 398 399 400 401 402 403 404 | ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD)) #endif /* ** Check to see if this machine uses EBCDIC. (Yes, believe it or ** not, there are still machines out there that use EBCDIC.) */ #if 'A' == '\301' # define SQLITE_EBCDIC 1 #else | > > > > > > | 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 | ** GCC does not define the offsetof() macro so we'll have to do it ** ourselves. */ #ifndef offsetof #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD)) #endif /* ** Macros to compute minimum and maximum of two numbers. */ #define MIN(A,B) ((A)<(B)?(A):(B)) #define MAX(A,B) ((A)>(B)?(A):(B)) /* ** Check to see if this machine uses EBCDIC. (Yes, believe it or ** not, there are still machines out there that use EBCDIC.) */ #if 'A' == '\301' # define SQLITE_EBCDIC 1 #else |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
53 54 55 56 57 58 59 60 61 62 63 64 65 66 | ** So all costs can be stored in a 16-bit unsigned integer without risk ** of overflow. ** ** Costs are estimates, so don't go to the computational trouble to compute ** 10*log2(X) exactly. Instead, a close estimate is used. Any value of ** X<=1 is stored as 0. X=2 is 10. X=3 is 16. X=1000 is 99. etc. ** */ typedef unsigned short int WhereCost; /* ** This object contains information needed to implement a single nestd ** loop in WHERE clause. ** | > > > > | 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | ** So all costs can be stored in a 16-bit unsigned integer without risk ** of overflow. ** ** Costs are estimates, so don't go to the computational trouble to compute ** 10*log2(X) exactly. Instead, a close estimate is used. Any value of ** X<=1 is stored as 0. X=2 is 10. X=3 is 16. X=1000 is 99. etc. ** ** The tool/wherecosttest.c source file implements a command-line program ** that will convert between WhereCost to integers and do addition and ** multiplication on WhereCost values. That command-line program is a ** useful utility to have around when working with this module. */ typedef unsigned short int WhereCost; /* ** This object contains information needed to implement a single nestd ** loop in WHERE clause. ** |
︙ | ︙ | |||
1897 1898 1899 1900 1901 1902 1903 | } } /* ** Convert an integer into a WhereCost. In other words, compute a ** good approximatation for 10*log2(x). */ | | | 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 | } } /* ** Convert an integer into a WhereCost. In other words, compute a ** good approximatation for 10*log2(x). */ static WhereCost whereCost(tRowcnt x){ static WhereCost a[] = { 0, 2, 3, 5, 6, 7, 8, 9 }; WhereCost y = 40; if( x<8 ){ if( x<2 ) return 0; while( x<8 ){ y -= 10; x <<= 1; } }else{ while( x>255 ){ y += 40; x >>= 4; } |
︙ | ︙ | |||
1921 1922 1923 1924 1925 1926 1927 | ** 10*log2(x). */ static WhereCost whereCostFromDouble(double x){ u64 a; WhereCost e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=1 ) return 0; | | | | 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 | ** 10*log2(x). */ static WhereCost whereCostFromDouble(double x){ u64 a; WhereCost e; assert( sizeof(x)==8 && sizeof(a)==8 ); if( x<=1 ) return 0; if( x<=2000000000 ) return whereCost((tRowcnt)x); memcpy(&a, &x, 8); e = (a>>52) - 1022; return e*10; } #endif /* SQLITE_OMIT_VIRTUALTABLE */ /* ** Estimate the logarithm of the input value to base 2. */ static WhereCost estLog(WhereCost N){ WhereCost x = whereCost(N); return x>33 ? x - 33 : 0; } /* ** Two routines for printing the content of an sqlite3_index_info ** structure. Used for testing and debugging only. If neither ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines |
︙ | ︙ | |||
2594 2595 2596 2597 2598 2599 2600 | ){ iUpper = a[0]; if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK ){ | | | > > | | | 2598 2599 2600 2601 2602 2603 2604 2605 2606 2607 2608 2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622 2623 2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635 | ){ iUpper = a[0]; if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1]; } sqlite3ValueFree(pRangeVal); } if( rc==SQLITE_OK ){ WhereCost iBase = whereCost(p->aiRowEst[0]); if( iUpper>iLower ){ iBase -= whereCost(iUpper - iLower); } *pRangeDiv = iBase; WHERETRACE(0x100, ("range scan regions: %u..%u div=%d\n", (u32)iLower, (u32)iUpper, *pRangeDiv)); return SQLITE_OK; } } #else UNUSED_PARAMETER(pParse); UNUSED_PARAMETER(p); UNUSED_PARAMETER(nEq); #endif assert( pLower || pUpper ); *pRangeDiv = 0; /* TUNING: Each inequality constraint reduces the search space 4-fold. ** A BETWEEN operator, therefore, reduces the search space 16-fold */ if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){ *pRangeDiv += 20; assert( 20==whereCost(4) ); } if( pUpper ){ *pRangeDiv += 20; assert( 20==whereCost(4) ); } return rc; } #ifdef SQLITE_ENABLE_STAT3 /* ** Estimate the number of rows that will be returned based on |
︙ | ︙ | |||
4240 4241 4242 4243 4244 4245 4246 | }else{ opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE; } if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE); if( pNew->u.btree.nEq < pProbe->nColumn ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; | | | | | | | > | | 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 4262 4263 4264 4265 4266 4267 4268 4269 4270 4271 4272 4273 4274 4275 4276 4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 | }else{ opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE; } if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE); if( pNew->u.btree.nEq < pProbe->nColumn ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; nRowEst = whereCost(pProbe->aiRowEst[pNew->u.btree.nEq+1]); }else{ iCol = -1; nRowEst = 0; } pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol, opMask, pProbe); saved_nEq = pNew->u.btree.nEq; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(whereCost(pProbe->aiRowEst[0])); for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ int nIn = 0; if( pTerm->prereqRight & pNew->maskSelf ) continue; pNew->wsFlags = saved_wsFlags; pNew->u.btree.nEq = saved_nEq; pNew->nLTerm = saved_nLTerm; if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */ pNew->aLTerm[pNew->nLTerm++] = pTerm; pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf; pNew->rRun = rLogSize; /* Baseline cost is log2(N). Adjustments below */ if( pTerm->eOperator & WO_IN ){ Expr *pExpr = pTerm->pExpr; pNew->wsFlags |= WHERE_COLUMN_IN; if( ExprHasProperty(pExpr, EP_xIsSelect) ){ /* "x IN (SELECT ...)": TUNING: the SELECT returns 25 rows */ nIn = 46; assert( 46==whereCost(25) ); }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){ /* "x IN (value, value, ...)" */ nIn = whereCost(pExpr->x.pList->nExpr); } pNew->rRun += nIn; pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_EQ) ){ assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0 || nInMul==0 ); pNew->wsFlags |= WHERE_COLUMN_EQ; if( iCol<0 || (pProbe->onError!=OE_None && nInMul==0 && pNew->u.btree.nEq==pProbe->nColumn-1) ){ testcase( pNew->wsFlags & WHERE_COLUMN_IN ); pNew->wsFlags |= WHERE_ONEROW; } pNew->u.btree.nEq++; pNew->nOut = nRowEst + nInMul; }else if( pTerm->eOperator & (WO_ISNULL) ){ pNew->wsFlags |= WHERE_COLUMN_NULL; pNew->u.btree.nEq++; /* TUNING: IS NULL selects 2 rows */ nIn = 10; assert( 10==whereCost(2) ); pNew->nOut = nRowEst + nInMul + nIn; }else if( pTerm->eOperator & (WO_GT|WO_GE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT; pBtm = pTerm; pTop = 0; }else if( pTerm->eOperator & (WO_LT|WO_LE) ){ pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT; |
︙ | ︙ | |||
4321 4322 4323 4324 4325 4326 4327 | tRowcnt nOut = 0; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut); }else if( (pTerm->eOperator & WO_IN) && !ExprHasProperty(pTerm->pExpr, EP_xIsSelect) ){ rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut); } | | | 4328 4329 4330 4331 4332 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 | tRowcnt nOut = 0; if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){ rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut); }else if( (pTerm->eOperator & WO_IN) && !ExprHasProperty(pTerm->pExpr, EP_xIsSelect) ){ rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut); } pNew->nOut = whereCost(nOut); } #endif if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){ /* Each row involves a step of the index, then a binary search of ** the main table */ pNew->rRun = whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10); } |
︙ | ︙ | |||
4447 4448 4449 4450 4451 4452 4453 | if( pSrc->notIndexed==0 ){ /* The real indices of the table are only considered if the ** NOT INDEXED qualifier is omitted from the FROM clause */ sPk.pNext = pFirst; } pProbe = &sPk; } | | | 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463 4464 4465 4466 4467 4468 | if( pSrc->notIndexed==0 ){ /* The real indices of the table are only considered if the ** NOT INDEXED qualifier is omitted from the FROM clause */ sPk.pNext = pFirst; } pProbe = &sPk; } rSize = whereCost(pSrc->pTab->nRowEst); rLogSize = estLog(rSize); /* Automatic indexes */ if( !pBuilder->pBest && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 && !pSrc->viaCoroutine |
︙ | ︙ | |||
4469 4470 4471 4472 4473 4474 4475 | for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ if( pTerm->prereqRight & pNew->maskSelf ) continue; if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; | > | > | > | | 4476 4477 4478 4479 4480 4481 4482 4483 4484 4485 4486 4487 4488 4489 4490 4491 4492 4493 4494 4495 | for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){ if( pTerm->prereqRight & pNew->maskSelf ) continue; if( termCanDriveIndex(pTerm, pSrc, 0) ){ pNew->u.btree.nEq = 1; pNew->u.btree.pIndex = 0; pNew->nLTerm = 1; pNew->aLTerm[0] = pTerm; /* TUNING: One-time cost for computing the automatic index is ** approximately 6*N*log2(N) where N is the number of rows in ** the table being indexed. */ pNew->rSetup = rLogSize + rSize + 26; assert( 26==whereCost(6) ); /* TUNING: Each index lookup yields 10 rows in the table */ pNew->nOut = 33; assert( 33==whereCost(10) ); pNew->rRun = whereCostAdd(rLogSize,pNew->nOut); pNew->wsFlags = WHERE_TEMP_INDEX; pNew->prereq = mExtra | pTerm->prereqRight; rc = whereLoopInsert(pBuilder, pNew); } } } |
︙ | ︙ | |||
4497 4498 4499 4500 4501 4502 4503 | if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; pNew->nOut = rSize; | > > > > > | > > > > > > > > > | > > > > | > | 4507 4508 4509 4510 4511 4512 4513 4514 4515 4516 4517 4518 4519 4520 4521 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554 4555 4556 4557 | if( pProbe->tnum<=0 ){ /* Integer primary key index */ pNew->wsFlags = WHERE_IPK; /* Full table scan */ pNew->iSortIdx = b ? iSortIdx : 0; pNew->nOut = rSize; /* TUNING: Cost of full table scan is 3*(N + log2(N)). ** + The extra 3 factor is to encourage the use of indexed lookups ** over full scans. A smaller constant 2 is used for covering ** index scans so that a covering index scan will be favored over ** a table scan. */ pNew->rRun = whereCostAdd(rSize,rLogSize) + 16; rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; }else{ Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe); pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED; /* Full scan via index */ if( (m==0 || b) && pProbe->bUnordered==0 && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0 && sqlite3GlobalConfig.bUseCis && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan) ){ pNew->iSortIdx = b ? iSortIdx : 0; pNew->nOut = rSize; if( m==0 ){ /* TUNING: Cost of a covering index scan is 2*(N + log2(N)). ** + The extra 2 factor is to encourage the use of indexed lookups ** over index scans. A table scan uses a factor of 3 so that ** index scans are favored over table scans. ** + If this covering index might also help satisfy the ORDER BY ** clause, then the cost is fudged down slightly so that this ** index is favored above other indices that have no hope of ** helping with the ORDER BY. */ pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b; }else{ assert( b!=0 ); /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N) ** which we will simplify to just N*log2(N) */ pNew->rRun = rSize + rLogSize; } rc = whereLoopInsert(pBuilder, pNew); if( rc ) break; } } rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0); /* If there was an INDEXED BY clause, then only that one index is |
︙ | ︙ | |||
4671 4672 4673 4674 4675 4676 4677 | pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost); | > | | 4700 4701 4702 4703 4704 4705 4706 4707 4708 4709 4710 4711 4712 4713 4714 4715 | pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr; pIdxInfo->needToFreeIdxStr = 0; pNew->u.vtab.idxStr = pIdxInfo->idxStr; pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0) && pIdxInfo->orderByConsumed); pNew->rSetup = 0; pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost); /* TUNING: Every virtual table query returns 25 rows */ pNew->nOut = 46; assert( 46==whereCost(25) ); whereLoopInsert(pBuilder, pNew); if( pNew->u.vtab.needFree ){ sqlite3_free(pNew->u.vtab.idxStr); pNew->u.vtab.needFree = 0; } } } |
︙ | ︙ | |||
5062 5063 5064 5065 5066 5067 5068 5069 5070 5071 5072 5073 5074 5075 5076 5077 5078 5079 5080 5081 5082 5083 | ** ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation ** error occurs. */ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ int mxChoice; /* Maximum number of simultaneous paths tracked */ int nLoop; /* Number of terms in the join */ sqlite3 *db; /* The database connection */ int iLoop; /* Loop counter over the terms of the join */ int ii, jj; /* Loop counters */ WhereCost rCost; /* Cost of a path */ WhereCost mxCost; /* Maximum cost of a set of paths */ WhereCost rSortCost; /* Cost to do a sort */ 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 */ | > | > > > > | > > > > | | > | 5092 5093 5094 5095 5096 5097 5098 5099 5100 5101 5102 5103 5104 5105 5106 5107 5108 5109 5110 5111 5112 5113 5114 5115 5116 5117 5118 5119 5120 5121 5122 5123 5124 5125 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 5143 5144 5145 5146 5147 5148 5149 5150 5151 5152 5153 5154 5155 5156 5157 5158 5159 | ** ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation ** error occurs. */ static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){ int mxChoice; /* Maximum number of simultaneous paths tracked */ 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 */ WhereCost rCost; /* Cost of a path */ WhereCost mxCost; /* Maximum cost of a set of paths */ WhereCost rSortCost; /* Cost to do a sort */ 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\n")); /* 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; 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; } /* 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==whereCost(25) ); nFrom = 1; /* Precompute the cost of sorting the final result set, if the caller ** to sqlite3WhereBegin() was concerned about sorting */ rSortCost = 0; if( pWInfo->pOrderBy==0 || nRowEst==0 ){ aFrom[0].isOrderedValid = 1; }else{ /* TUNING: Estimated cost of sorting is N*log2(N) where N is the ** number of output rows. */ rSortCost = nRowEst + estLog(nRowEst); WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost)); } /* 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 */ |
︙ | ︙ | |||
5250 5251 5252 5253 5254 5255 5256 | pFrom = aTo; aTo = aFrom; aFrom = pFrom; nFrom = nTo; } if( nFrom==0 ){ | | | 5290 5291 5292 5293 5294 5295 5296 5297 5298 5299 5300 5301 5302 5303 5304 | pFrom = aTo; aTo = aFrom; aFrom = pFrom; nFrom = nTo; } if( nFrom==0 ){ sqlite3ErrorMsg(pParse, "no query solution"); sqlite3DbFree(db, pSpace); return SQLITE_ERROR; } /* Find the lowest cost path. pFrom will be left pointing to that path */ pFrom = aFrom; for(ii=1; ii<nFrom; ii++){ |
︙ | ︙ | |||
5331 5332 5333 5334 5335 5336 5337 | pLoop->wsFlags = 0; pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; pLoop->u.btree.nEq = 1; | > | > | | 5371 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 5400 5401 5402 5403 5404 5405 | pLoop->wsFlags = 0; pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0); if( pTerm ){ pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW; pLoop->aLTerm[0] = pTerm; pLoop->nLTerm = 1; pLoop->u.btree.nEq = 1; /* TUNING: Cost of a rowid lookup is 10 */ pLoop->rRun = 33; /* 33==whereCost(10) */ }else{ for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ if( pIdx->onError==OE_None ) continue; for(j=0; j<pIdx->nColumn; j++){ pTerm = findTerm(pWC, iCur, pIdx->aiColumn[j], 0, WO_EQ, pIdx); if( pTerm==0 ) break; whereLoopResize(pWInfo->pParse->db, pLoop, j); pLoop->aLTerm[j] = pTerm; } if( j!=pIdx->nColumn ) continue; pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED; if( (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){ pLoop->wsFlags |= WHERE_IDX_ONLY; } pLoop->nLTerm = j; pLoop->u.btree.nEq = j; pLoop->u.btree.pIndex = pIdx; /* TUNING: Cost of a unique index lookup is 15 */ pLoop->rRun = 39; /* 39==whereCost(15) */ break; } } if( pLoop->wsFlags ){ pLoop->nOut = (WhereCost)1; pWInfo->a[0].pWLoop = pLoop; pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur); |
︙ | ︙ |
Changes to test/autoindex1.test.
︙ | ︙ | |||
74 75 76 77 78 79 80 81 82 83 84 85 86 87 | } {35} do_test autoindex1-202 { db status autoindex } {0} do_test autoindex1-210 { db eval { PRAGMA automatic_index=ON; SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1; } } {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988} do_test autoindex1-211 { db status step } {7} do_test autoindex1-212 { | > > > | 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 | } {35} do_test autoindex1-202 { db status autoindex } {0} do_test autoindex1-210 { db eval { PRAGMA automatic_index=ON; ANALYZE; UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1'; ANALYZE sqlite_master; SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1; } } {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988} do_test autoindex1-211 { db status step } {7} do_test autoindex1-212 { |
︙ | ︙ | |||
139 140 141 142 143 144 145 146 147 148 149 150 151 152 | # Ticket [8011086c85c6c404014c947fcf3eb9f42b184a0d] from 2010-07-08 # Make sure automatic indices are not created for the RHS of an IN expression # that is not a correlated subquery. # do_execsql_test autoindex1-500 { CREATE TABLE t501(a INTEGER PRIMARY KEY, b); CREATE TABLE t502(x INTEGER PRIMARY KEY, y); EXPLAIN QUERY PLAN SELECT b FROM t501 WHERE t501.a IN (SELECT x FROM t502 WHERE y=?); } { 0 0 0 {SEARCH TABLE t501 USING INTEGER PRIMARY KEY (rowid=?)} 0 0 0 {EXECUTE LIST SUBQUERY 1} 1 0 0 {SCAN TABLE t502} | > > > | 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 | # Ticket [8011086c85c6c404014c947fcf3eb9f42b184a0d] from 2010-07-08 # Make sure automatic indices are not created for the RHS of an IN expression # that is not a correlated subquery. # do_execsql_test autoindex1-500 { CREATE TABLE t501(a INTEGER PRIMARY KEY, b); CREATE TABLE t502(x INTEGER PRIMARY KEY, y); INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t501',null,'1000000'); INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t502',null,'1000'); ANALYZE sqlite_master; EXPLAIN QUERY PLAN SELECT b FROM t501 WHERE t501.a IN (SELECT x FROM t502 WHERE y=?); } { 0 0 0 {SEARCH TABLE t501 USING INTEGER PRIMARY KEY (rowid=?)} 0 0 0 {EXECUTE LIST SUBQUERY 1} 1 0 0 {SCAN TABLE t502} |
︙ | ︙ |