Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further refinement of the idea of multiplying run-time cost estimates by the estimated row size. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | row-size-est |
Files: | files | file ages | folders |
SHA1: |
18bd6ba96d19de6047baebfa15b1f739 |
User & Date: | drh 2013-10-08 18:40:37.532 |
Context
2013-10-08
| ||
20:01 | Use #ifdefs to omit unused code in the columnType() routine depending on compile-time options. (check-in: 3fd5e33217 user: drh tags: row-size-est) | |
18:40 | Further refinement of the idea of multiplying run-time cost estimates by the estimated row size. (check-in: 18bd6ba96d user: drh tags: row-size-est) | |
2013-10-07
| ||
17:32 | Multiply all cursor step cost estimates by the estimated size of the row in bytes, in order to get the query planner ot make use of estimated row sizes. This check-in uses magic numbers in a few places (for example, estimates of the size of output rows) and needs lots of refinement. Consider this a proof-of-concept only. (check-in: cb34cfe57c user: drh tags: row-size-est) | |
Changes
Changes to src/build.c.
︙ | ︙ | |||
875 876 877 878 879 880 881 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; | | | 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; pTable->nRowEst = 1048576; assert( pParse->pNewTable==0 ); pParse->pNewTable = pTable; /* If this is the magic sqlite_sequence table used by autoincrement, ** then record a pointer to this table in the main database structure ** so that INSERT can find the table easily. */ |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
1420 1421 1422 1423 1424 1425 1426 | ** routine goes through and adds the types and collations. ** ** This routine requires that all identifiers in the SELECT ** statement be resolved. */ static void selectAddColumnTypeAndCollation( Parse *pParse, /* Parsing contexts */ | | < > | | > > > | 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 | ** routine goes through and adds the types and collations. ** ** This routine requires that all identifiers in the SELECT ** statement be resolved. */ static void selectAddColumnTypeAndCollation( Parse *pParse, /* Parsing contexts */ Table *pTab, /* Add column type information to this table */ Select *pSelect /* SELECT used to determine types and collations */ ){ sqlite3 *db = pParse->db; NameContext sNC; Column *pCol; CollSeq *pColl; int i; Expr *p; struct ExprList_item *a; u64 szAll = 0; assert( pSelect!=0 ); assert( (pSelect->selFlags & SF_Resolved)!=0 ); assert( pTab->nCol==pSelect->pEList->nExpr || db->mallocFailed ); if( db->mallocFailed ) return; memset(&sNC, 0, sizeof(sNC)); sNC.pSrcList = pSelect->pSrc; a = pSelect->pEList->a; for(i=0, pCol=pTab->aCol; i<pTab->nCol; i++, pCol++){ p = a[i].pExpr; pCol->zType = sqlite3DbStrDup(db, columnType(&sNC, p, 0, 0, 0)); sqlite3AffinityType(pCol->zType, &pCol->szEst); szAll += pCol->szEst; pCol->affinity = sqlite3ExprAffinity(p); if( pCol->affinity==0 ) pCol->affinity = SQLITE_AFF_NONE; pColl = sqlite3ExprCollSeq(pParse, p); if( pColl ){ pCol->zColl = sqlite3DbStrDup(db, pColl->zName); } } pTab->szTabRow = sqlite3LogEst(szAll*4); } /* ** Given a SELECT statement, generate a Table structure that describes ** the result set of that SELECT. */ Table *sqlite3ResultSetOfSelect(Parse *pParse, Select *pSelect){ |
︙ | ︙ | |||
1476 1477 1478 1479 1480 1481 1482 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; | | | | 1479 1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; pTab->nRowEst = 1048576; selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol); selectAddColumnTypeAndCollation(pParse, pTab, pSelect); pTab->iPKey = -1; if( db->mallocFailed ){ sqlite3DeleteTable(db, pTab); return 0; } return pTab; } |
︙ | ︙ | |||
3390 3391 3392 3393 3394 3395 3396 | /* A sub-query in the FROM clause of a SELECT */ assert( pSel!=0 ); assert( pFrom->pTab==0 ); sqlite3WalkSelect(pWalker, pSel); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; | | | | 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 | /* A sub-query in the FROM clause of a SELECT */ assert( pSel!=0 ); assert( pFrom->pTab==0 ); sqlite3WalkSelect(pWalker, pSel); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab); while( pSel->pPrior ){ pSel = pSel->pPrior; } selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol); pTab->iPKey = -1; pTab->nRowEst = 1048576; pTab->tabFlags |= TF_Ephemeral; #endif }else{ /* An ordinary table or view name in the FROM clause */ assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom); if( pTab==0 ) return WRC_Abort; |
︙ | ︙ | |||
3678 3679 3680 3681 3682 3683 3684 | for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab = pFrom->pTab; if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){ /* A sub-query in the FROM clause of a SELECT */ Select *pSel = pFrom->pSelect; assert( pSel ); while( pSel->pPrior ) pSel = pSel->pPrior; | | | 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 | for(i=0, pFrom=pTabList->a; i<pTabList->nSrc; i++, pFrom++){ Table *pTab = pFrom->pTab; if( ALWAYS(pTab!=0) && (pTab->tabFlags & TF_Ephemeral)!=0 ){ /* A sub-query in the FROM clause of a SELECT */ Select *pSel = pFrom->pSelect; assert( pSel ); while( pSel->pPrior ) pSel = pSel->pPrior; selectAddColumnTypeAndCollation(pParse, pTab, pSel); } } } return WRC_Continue; } #endif |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
2446 2447 2448 2449 2450 2451 2452 | ** rows visited by a factor of 16. */ static int whereRangeScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ | | | > | < | 2446 2447 2448 2449 2450 2451 2452 2453 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 | ** rows visited by a factor of 16. */ static int whereRangeScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, WhereTerm *pLower, /* Lower bound on the range. ex: "x>123" Might be NULL */ WhereTerm *pUpper, /* Upper bound on the range. ex: "x<455" Might be NULL */ WhereLoop *pLoop /* Modify the .nOut and maybe .rRun fields */ ){ int rc = SQLITE_OK; int nOut = pLoop->nOut; int nEq = pLoop->u.btree.nEq; LogEst nNew; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 Index *p = pLoop->u.btree.pIndex; if( p->nSample>0 && nEq==pBuilder->nRecValid && nEq<p->nSampleCol && OptimizationEnabled(pParse->db, SQLITE_Stat3) ){ UnpackedRecord *pRec = pBuilder->pRec; |
︙ | ︙ | |||
2542 2543 2544 2545 2546 2547 2548 | nNew = sqlite3LogEst(iUpper - iLower); }else{ nNew = 10; assert( 10==sqlite3LogEst(2) ); } if( nNew<nOut ){ nOut = nNew; } | | | 2542 2543 2544 2545 2546 2547 2548 2549 2550 2551 2552 2553 2554 2555 2556 | nNew = sqlite3LogEst(iUpper - iLower); }else{ nNew = 10; assert( 10==sqlite3LogEst(2) ); } if( nNew<nOut ){ nOut = nNew; } pLoop->nOut = (LogEst)nOut; WHERETRACE(0x100, ("range scan regions: %u..%u est=%d\n", (u32)iLower, (u32)iUpper, nOut)); return SQLITE_OK; } } #else UNUSED_PARAMETER(pParse); |
︙ | ︙ | |||
2566 2567 2568 2569 2570 2571 2572 | } if( pUpper ){ nNew -= 20; assert( 20==sqlite3LogEst(4) ); nOut--; } if( nNew<10 ) nNew = 10; if( nNew<nOut ) nOut = nNew; | | | 2566 2567 2568 2569 2570 2571 2572 2573 2574 2575 2576 2577 2578 2579 2580 | } if( pUpper ){ nNew -= 20; assert( 20==sqlite3LogEst(4) ); nOut--; } if( nNew<10 ) nNew = 10; if( nNew<nOut ) nOut = nNew; pLoop->nOut = (LogEst)nOut; return rc; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 /* ** Estimate the number of rows that will be returned based on ** an equality constraint x=VALUE and where that VALUE occurs in |
︙ | ︙ | |||
4333 4334 4335 4336 4337 4338 4339 | pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ assert( pNew->nOut==saved_nOut ); | | > > > > > > | 4333 4334 4335 4336 4337 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 | pTop = pTerm; pBtm = (pNew->wsFlags & WHERE_BTM_LIMIT)!=0 ? pNew->aLTerm[pNew->nLTerm-2] : 0; } if( pNew->wsFlags & WHERE_COLUMN_RANGE ){ /* Adjust nOut and rRun for STAT3 range values */ assert( pNew->nOut==saved_nOut ); whereRangeScanEst(pParse, pBuilder, pBtm, pTop, pNew); /* If the range constraint is the only constraint on the index and ** if the range constraint does not reduce the search space, ** then this is really just an index scan which has already ** been analyzed. */ if( pNew->nOut>=saved_nOut && pNew->u.btree.nEq==0 ) continue; } #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( nInMul==0 && pProbe->nSample && pNew->u.btree.nEq<=pProbe->nSampleCol && OptimizationEnabled(db, SQLITE_Stat3) ){ |
︙ | ︙ | |||
4812 4813 4814 4815 4816 4817 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 | struct SrcList_item *pItem; pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int once = 1; int i, j; | > > < < | 4818 4819 4820 4821 4822 4823 4824 4825 4826 4827 4828 4829 4830 4831 4832 4833 4834 4835 4836 4837 4838 4839 4840 4841 4842 4843 4844 | struct SrcList_item *pItem; pWC = pBuilder->pWC; if( pWInfo->wctrlFlags & WHERE_AND_ONLY ) return SQLITE_OK; pWCEnd = pWC->a + pWC->nTerm; pNew = pBuilder->pNew; memset(&sSum, 0, sizeof(sSum)); pItem = pWInfo->pTabList->a + pNew->iTab; iCur = pItem->iCursor; for(pTerm=pWC->a; pTerm<pWCEnd && rc==SQLITE_OK; pTerm++){ if( (pTerm->eOperator & WO_OR)!=0 && (pTerm->u.pOrInfo->indexable & pNew->maskSelf)!=0 ){ WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc; WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm]; WhereTerm *pOrTerm; int once = 1; int i, j; sSubBuild = *pBuilder; sSubBuild.pOrderBy = 0; sSubBuild.pOrSet = &sCur; for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){ if( (pOrTerm->eOperator & WO_AND)!=0 ){ sSubBuild.pWC = &pOrTerm->u.pAndInfo->wc; |
︙ | ︙ | |||
5262 5263 5264 5265 5266 5267 5268 | /* 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{ | | | > > | 5268 5269 5270 5271 5272 5273 5274 5275 5276 5277 5278 5279 5280 5281 5282 5283 5284 5285 | /* 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 48*N*log2(N) where N is the ** number of output rows. The 48 is the expected size of a row to sort. ** FIXME: compute a better estimate of the 48 multiplier based on the ** result set expressions. */ rSortCost = nRowEst + estLog(nRowEst) + 55; 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 */ |
︙ | ︙ |
Changes to test/e_select.test.
︙ | ︙ | |||
446 447 448 449 450 451 452 | } [concat {-60.06 {} {}} {-39.24 {} encompass -1}] # EVIDENCE-OF: R-44414-54710 There is a row in the cartesian product # dataset formed by combining each unique combination of a row from the # left-hand and right-hand datasets. # do_join_test e_select-1.4.2.1 { | | | < | > | < | > | 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 | } [concat {-60.06 {} {}} {-39.24 {} encompass -1}] # EVIDENCE-OF: R-44414-54710 There is a row in the cartesian product # dataset formed by combining each unique combination of a row from the # left-hand and right-hand datasets. # do_join_test e_select-1.4.2.1 { SELECT * FROM x2 %JOIN% x3 ORDER BY +c, +f } [list -60.06 {} {} -39.24 {} encompass -1 \ -60.06 {} {} alerting {} -93.79 {} \ -60.06 {} {} coldest -96 dramatists 82.3 \ -60.06 {} {} conducting -87.24 37.56 {} \ -60.06 {} {} presenting 51 reformation dignified \ -58 {} 1.21 -39.24 {} encompass -1 \ -58 {} 1.21 alerting {} -93.79 {} \ -58 {} 1.21 coldest -96 dramatists 82.3 \ -58 {} 1.21 conducting -87.24 37.56 {} \ -58 {} 1.21 presenting 51 reformation dignified \ ] # TODO: Come back and add a few more like the above. # EVIDENCE-OF: R-20659-43267 In other words, if the left-hand dataset # consists of Nlhs rows of Mlhs columns, and the right-hand dataset of # Nrhs rows of Mrhs columns, then the cartesian product is a dataset of # Nlhs.Nrhs rows, each containing Mlhs+Mrhs columns. |
︙ | ︙ |
Changes to test/where9.test.
︙ | ︙ | |||
777 778 779 780 781 782 783 | catchsql { UPDATE t1 INDEXED BY t1b SET a=a+100 WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL) OR (b NOT NULL AND c IS NULL AND d NOT NULL) OR (b NOT NULL AND c NOT NULL AND d IS NULL) } } {1 {no query solution}} | < < < < < < < < < < < | < < < < < < < < < | 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 | catchsql { UPDATE t1 INDEXED BY t1b SET a=a+100 WHERE (+b IS NULL AND c NOT NULL AND d NOT NULL) OR (b NOT NULL AND c IS NULL AND d NOT NULL) OR (b NOT NULL AND c NOT NULL AND d IS NULL) } } {1 {no query solution}} if {1} { do_test where9-6.8.3 { catchsql { UPDATE t1 INDEXED BY t1b SET a=a+100 WHERE (b IS NULL AND c NOT NULL AND d NOT NULL) OR (b NOT NULL AND c IS NULL AND d NOT NULL) OR (b NOT NULL AND c NOT NULL AND d IS NULL) } |
︙ | ︙ |