Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Store values loaded from the stat1 table as logarithmic values in memory. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | experimental-costs |
Files: | files | file ages | folders |
SHA1: |
1bd74c49ddab6f53bb6eaa57907eff44 |
User & Date: | dan 2014-04-25 15:01:01.691 |
Context
2014-04-25
| ||
20:22 | If the user provides likelihood() data for a WHERE clause term used as part of an index key, have the planner use it when calculating the expected number of rows visited by the loop. (check-in: c51efaa5d2 user: dan tags: experimental-costs) | |
15:01 | Store values loaded from the stat1 table as logarithmic values in memory. (check-in: 1bd74c49dd user: dan tags: experimental-costs) | |
2014-04-24
| ||
20:04 | Changes to the way the planner calculates the costs of various table and index scans. Some test cases still failing. (check-in: c5a6ec0a88 user: dan tags: experimental-costs) | |
Changes
Changes to src/analyze.c.
︙ | ︙ | |||
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 | ** list of space separated integers. Read the first nOut of these into ** the array aOut[]. */ static void decodeIntArray( char *zIntArray, /* String containing int array to decode */ int nOut, /* Number of slots in aOut[] */ tRowcnt *aOut, /* Store integers here */ Index *pIndex /* Handle extra flags for this index, if not NULL */ ){ char *z = zIntArray; int c; int i; tRowcnt v; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( z==0 ) z = ""; #else if( NEVER(z==0) ) z = ""; #endif for(i=0; *z && i<nOut; i++){ v = 0; while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } | > > | > > > | 1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397 1398 1399 1400 1401 1402 1403 1404 | ** list of space separated integers. Read the first nOut of these into ** the array aOut[]. */ static void decodeIntArray( char *zIntArray, /* String containing int array to decode */ int nOut, /* Number of slots in aOut[] */ tRowcnt *aOut, /* Store integers here */ LogEst *aLog, /* Or, if aOut==0, here */ Index *pIndex /* Handle extra flags for this index, if not NULL */ ){ char *z = zIntArray; int c; int i; tRowcnt v; #ifdef SQLITE_ENABLE_STAT3_OR_STAT4 if( z==0 ) z = ""; #else if( NEVER(z==0) ) z = ""; #endif for(i=0; *z && i<nOut; i++){ v = 0; while( (c=z[0])>='0' && c<='9' ){ v = v*10 + c - '0'; z++; } if( aOut ){ aOut[i] = v; }else{ aLog[i] = sqlite3LogEst(v); } if( *z==' ' ) z++; } #ifndef SQLITE_ENABLE_STAT3_OR_STAT4 assert( pIndex!=0 ); #else if( pIndex ) #endif |
︙ | ︙ | |||
1441 1442 1443 1444 1445 1446 1447 | pIndex = sqlite3PrimaryKeyIndex(pTable); }else{ pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); } z = argv[2]; if( pIndex ){ | | | | | 1446 1447 1448 1449 1450 1451 1452 1453 1454 1455 1456 1457 1458 1459 1460 1461 1462 1463 1464 1465 | pIndex = sqlite3PrimaryKeyIndex(pTable); }else{ pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase); } z = argv[2]; if( pIndex ){ decodeIntArray((char*)z, pIndex->nKeyCol+1, 0, pIndex->aiRowLogEst, pIndex); if( pIndex->pPartIdxWhere==0 ) pTable->nRowLogEst = pIndex->aiRowLogEst[0]; }else{ Index fakeIdx; fakeIdx.szIdxRow = pTable->szTabRow; decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx); pTable->szTabRow = fakeIdx.szIdxRow; } return 0; } /* |
︙ | ︙ | |||
1638 1639 1640 1641 1642 1643 1644 | nCol = pIdx->nSampleCol; if( bStat3 && nCol>1 ) continue; if( pIdx!=pPrevIdx ){ initAvgEq(pPrevIdx); pPrevIdx = pIdx; } pSample = &pIdx->aSample[pIdx->nSample]; | | | | | 1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 | nCol = pIdx->nSampleCol; if( bStat3 && nCol>1 ) continue; if( pIdx!=pPrevIdx ){ initAvgEq(pPrevIdx); pPrevIdx = pIdx; } pSample = &pIdx->aSample[pIdx->nSample]; decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0); decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0); decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0); /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer. ** This is in case the sample record is corrupted. In that case, the ** sqlite3VdbeRecordCompare() may read up to two varints past the ** end of the allocated buffer before it realizes it is dealing with ** a corrupt record. Adding the two 0x00 bytes prevents this from causing ** a buffer overread. */ |
︙ | ︙ |
Changes to src/build.c.
︙ | ︙ | |||
901 902 903 904 905 906 907 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; | | | 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 | pParse->nErr++; goto begin_table_error; } pTable->zName = zName; pTable->iPKey = -1; pTable->pSchema = db->aDb[iDb].pSchema; pTable->nRef = 1; pTable->nRowLogEst = 200; assert( 200==sqlite3LogEst(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. */ |
︙ | ︙ | |||
2726 2727 2728 2729 2730 2731 2732 | char **ppExtra /* Pointer to the "extra" space */ ){ Index *p; /* Allocated index object */ int nByte; /* Bytes of space for Index object + arrays */ nByte = ROUND8(sizeof(Index)) + /* Index structure */ ROUND8(sizeof(char*)*nCol) + /* Index.azColl */ | | | | | | 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 2741 2742 2743 2744 2745 2746 2747 2748 | char **ppExtra /* Pointer to the "extra" space */ ){ Index *p; /* Allocated index object */ int nByte; /* Bytes of space for Index object + arrays */ nByte = ROUND8(sizeof(Index)) + /* Index structure */ ROUND8(sizeof(char*)*nCol) + /* Index.azColl */ ROUND8(sizeof(LogEst)*(nCol+1) + /* Index.aiRowLogEst */ sizeof(i16)*nCol + /* Index.aiColumn */ sizeof(u8)*nCol); /* Index.aSortOrder */ p = sqlite3DbMallocZero(db, nByte + nExtra); if( p ){ char *pExtra = ((char*)p)+ROUND8(sizeof(Index)); p->azColl = (char**)pExtra; pExtra += ROUND8(sizeof(char*)*nCol); p->aiRowLogEst = (LogEst*)pExtra; pExtra += sizeof(LogEst)*(nCol+1); p->aiColumn = (i16*)pExtra; pExtra += sizeof(i16)*nCol; p->aSortOrder = (u8*)pExtra; p->nColumn = nCol; p->nKeyCol = nCol - 1; *ppExtra = ((char*)p) + nByte; } return p; } |
︙ | ︙ | |||
2964 2965 2966 2967 2968 2969 2970 | nName = sqlite3Strlen30(zName); nExtraCol = pPk ? pPk->nKeyCol : 1; pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol, nName + nExtra + 1, &zExtra); if( db->mallocFailed ){ goto exit_create_index; } | | | 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 | nName = sqlite3Strlen30(zName); nExtraCol = pPk ? pPk->nKeyCol : 1; pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol, nName + nExtra + 1, &zExtra); if( db->mallocFailed ){ goto exit_create_index; } assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowLogEst) ); assert( EIGHT_BYTE_ALIGNMENT(pIndex->azColl) ); pIndex->zName = zExtra; zExtra += nName + 1; memcpy(pIndex->zName, zName, nName+1); pIndex->pTable = pTab; pIndex->onError = (u8)onError; pIndex->uniqNotNull = onError!=OE_None; |
︙ | ︙ | |||
3245 3246 3247 3248 3249 3250 3251 | ** Fill the Index.aiRowEst[] array with default information - information ** to be used when we have not run the ANALYZE command. ** ** aiRowEst[0] is suppose to contain the number of elements in the index. ** Since we do not know, guess 1 million. aiRowEst[1] is an estimate of the ** number of rows in the table that match any particular value of the ** first column of the index. aiRowEst[2] is an estimate of the number | | > > > > > > > > > > > > | 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 | ** Fill the Index.aiRowEst[] array with default information - information ** to be used when we have not run the ANALYZE command. ** ** aiRowEst[0] is suppose to contain the number of elements in the index. ** Since we do not know, guess 1 million. aiRowEst[1] is an estimate of the ** number of rows in the table that match any particular value of the ** first column of the index. aiRowEst[2] is an estimate of the number ** of rows that match any particular combination of the first 2 columns ** of the index. And so forth. It must always be the case that * ** aiRowEst[N]<=aiRowEst[N-1] ** aiRowEst[N]>=1 ** ** Apart from that, we have little to go on besides intuition as to ** how aiRowEst[] should be initialized. The numbers generated here ** are based on typical values found in actual indices. */ void sqlite3DefaultRowEst(Index *pIdx){ #if 0 tRowcnt *a = pIdx->aiRowEst; int i; tRowcnt n; assert( a!=0 ); a[0] = pIdx->pTable->nRowEst; if( a[0]<10 ) a[0] = 10; n = 10; for(i=1; i<=pIdx->nKeyCol; i++){ a[i] = n; if( n>5 ) n--; } if( pIdx->onError!=OE_None ){ a[pIdx->nKeyCol] = 1; } #endif /* 1000000, 10, 9, 8, 7, 6, 5, 4, 3, 2 */ LogEst aVal[] = { 33, 32, 30, 28, 26, 23, 20, 16, 10 }; LogEst *a = pIdx->aiRowLogEst; int nCopy = MIN(ArraySize(aVal), pIdx->nKeyCol); a[0] = pIdx->pTable->nRowLogEst; memcpy(&a[1], aVal, nCopy*sizeof(LogEst)); if( pIdx->onError!=OE_None ){ a[pIdx->nKeyCol] = 0; } } /* ** This routine will drop an existing named index. This routine ** implements the DROP INDEX statement. */ void sqlite3DropIndex(Parse *pParse, SrcList *pName, int ifExists){ |
︙ | ︙ |
Changes to src/pragma.c.
︙ | ︙ | |||
1484 1485 1486 1487 1488 1489 1490 | sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC); for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){ Table *pTab = sqliteHashData(i); sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0); sqlite3VdbeAddOp2(v, OP_Null, 0, 2); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->szTabRow), 3); | | > | > | 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500 1501 1502 1503 1504 1505 1506 | sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC); for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){ Table *pTab = sqliteHashData(i); sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0); sqlite3VdbeAddOp2(v, OP_Null, 0, 2); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->szTabRow), 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pTab->nRowLogEst), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){ sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pIdx->szIdxRow), 3); sqlite3VdbeAddOp2(v, OP_Integer, (int)sqlite3LogEstToInt(pIdx->aiRowLogEst[0]), 4); sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4); } } } break; case PragTyp_INDEX_INFO: if( zRight ){ |
︙ | ︙ |
Changes to src/select.c.
︙ | ︙ | |||
1686 1687 1688 1689 1690 1691 1692 | return 0; } /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside ** is disabled */ assert( db->lookaside.bEnabled==0 ); pTab->nRef = 1; pTab->zName = 0; | | | 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 | 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->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol); selectAddColumnTypeAndCollation(pParse, pTab, pSelect); pTab->iPKey = -1; if( db->mallocFailed ){ sqlite3DeleteTable(db, pTab); return 0; } |
︙ | ︙ | |||
3825 3826 3827 3828 3829 3830 3831 | assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3DbStrDup(db, pCte->zName); pTab->iPKey = -1; | | | 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 | assert( pFrom->pTab==0 ); pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table)); if( pTab==0 ) return WRC_Abort; pTab->nRef = 1; pTab->zName = sqlite3DbStrDup(db, pCte->zName); pTab->iPKey = -1; pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) ); pTab->tabFlags |= TF_Ephemeral; pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0); if( db->mallocFailed ) return SQLITE_NOMEM; assert( pFrom->pSelect ); /* Check if this is a recursive CTE. */ pSel = pFrom->pSelect; |
︙ | ︙ | |||
4001 4002 4003 4004 4005 4006 4007 | 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; | | | 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 | 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->nRowLogEst = 200; assert( 200==sqlite3LogEst(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; |
︙ | ︙ | |||
4651 4652 4653 4654 4655 4656 4657 | pItem->regReturn = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); VdbeComment((v, "%s", pItem->pTab->zName)); pItem->addrFillSub = addrTop; sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); | | | 4651 4652 4653 4654 4655 4656 4657 4658 4659 4660 4661 4662 4663 4664 4665 | pItem->regReturn = ++pParse->nMem; sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop); VdbeComment((v, "%s", pItem->pTab->zName)); pItem->addrFillSub = addrTop; sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); pItem->viaCoroutine = 1; pItem->regResult = dest.iSdst; sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn); sqlite3VdbeJumpHere(v, addrTop-1); sqlite3ClearTempRegCache(pParse); }else{ /* Generate a subroutine that will fill an ephemeral table with |
︙ | ︙ | |||
4682 4683 4684 4685 4686 4687 4688 | VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); }else{ VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); } sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); | | | 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 | VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName)); }else{ VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName)); } sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor); explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId); sqlite3Select(pParse, pSub, &dest); pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow); if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr); retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn); VdbeComment((v, "end %s", pItem->pTab->zName)); sqlite3VdbeChangeP1(v, topAddr, retAddr); sqlite3ClearTempRegCache(pParse); } if( /*pParse->nErr ||*/ db->mallocFailed ){ |
︙ | ︙ |
Changes to src/sqliteInt.h.
︙ | ︙ | |||
1467 1468 1469 1470 1471 1472 1473 | Index *pIndex; /* List of SQL indexes on this table. */ Select *pSelect; /* NULL for tables. Points to definition if a view. */ FKey *pFKey; /* Linked list of all foreign keys in this table */ char *zColAff; /* String defining the affinity of each column */ #ifndef SQLITE_OMIT_CHECK ExprList *pCheck; /* All CHECK constraints */ #endif | | | 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479 1480 1481 | Index *pIndex; /* List of SQL indexes on this table. */ Select *pSelect; /* NULL for tables. Points to definition if a view. */ FKey *pFKey; /* Linked list of all foreign keys in this table */ char *zColAff; /* String defining the affinity of each column */ #ifndef SQLITE_OMIT_CHECK ExprList *pCheck; /* All CHECK constraints */ #endif LogEst nRowLogEst; /* Estimated rows in table - from sqlite_stat1 table */ int tnum; /* Root BTree node for this table (see note above) */ i16 iPKey; /* If not negative, use aCol[iPKey] as the primary key */ i16 nCol; /* Number of columns in this table */ u16 nRef; /* Number of pointers to this Table */ LogEst szTabRow; /* Estimated size of each table row in bytes */ u8 tabFlags; /* Mask of TF_* values */ u8 keyConf; /* What to do in case of uniqueness conflict on iPKey */ |
︙ | ︙ | |||
1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 | ** and the value of Index.onError indicate the which conflict resolution ** algorithm to employ whenever an attempt is made to insert a non-unique ** element. */ struct Index { char *zName; /* Name of this index */ i16 *aiColumn; /* Which columns are used by this index. 1st is 0 */ tRowcnt *aiRowEst; /* From ANALYZE: Est. rows selected by each column */ Table *pTable; /* The SQL table being indexed */ char *zColAff; /* String defining the affinity of each column */ Index *pNext; /* The next index associated with the same table */ Schema *pSchema; /* Schema containing this index */ u8 *aSortOrder; /* for each column: True==DESC, False==ASC */ char **azColl; /* Array of collation sequence names for index */ Expr *pPartIdxWhere; /* WHERE clause for partial indices */ | > > > | 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 | ** and the value of Index.onError indicate the which conflict resolution ** algorithm to employ whenever an attempt is made to insert a non-unique ** element. */ struct Index { char *zName; /* Name of this index */ i16 *aiColumn; /* Which columns are used by this index. 1st is 0 */ #if 0 tRowcnt *aiRowEst; /* From ANALYZE: Est. rows selected by each column */ #endif LogEst *aiRowLogEst; /* From ANALYZE: Est. rows selected by each column */ Table *pTable; /* The SQL table being indexed */ char *zColAff; /* String defining the affinity of each column */ Index *pNext; /* The next index associated with the same table */ Schema *pSchema; /* Schema containing this index */ u8 *aSortOrder; /* for each column: True==DESC, False==ASC */ char **azColl; /* Array of collation sequence names for index */ Expr *pPartIdxWhere; /* WHERE clause for partial indices */ |
︙ | ︙ |
Changes to src/where.c.
︙ | ︙ | |||
1952 1953 1954 1955 1956 1957 1958 | aStat[1] = aSample[i].anEq[iCol]; }else{ tRowcnt iLower, iUpper, iGap; if( i==0 ){ iLower = 0; iUpper = aSample[0].anLt[iCol]; }else{ | > | | 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 | aStat[1] = aSample[i].anEq[iCol]; }else{ tRowcnt iLower, iUpper, iGap; if( i==0 ){ iLower = 0; iUpper = aSample[0].anLt[iCol]; }else{ i64 nRow0 = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]); iUpper = i>=pIdx->nSample ? nRow0 : aSample[i].anLt[iCol]; iLower = aSample[i-1].anEq[iCol] + aSample[i-1].anLt[iCol]; } aStat[1] = (pIdx->nKeyCol>iCol ? pIdx->aAvgEq[iCol] : 1); if( iLower>=iUpper ){ iGap = 0; }else{ iGap = iUpper - iLower; |
︙ | ︙ | |||
2088 2089 2090 2091 2092 2093 2094 | aff = SQLITE_AFF_INTEGER; }else{ aff = p->pTable->aCol[p->aiColumn[nEq]].affinity; } /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; | | | 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 | aff = SQLITE_AFF_INTEGER; }else{ aff = p->pTable->aCol[p->aiColumn[nEq]].affinity; } /* Determine iLower and iUpper using ($P) only. */ if( nEq==0 ){ iLower = 0; iUpper = sqlite3LogEstToInt(p->aiRowLogEst[0]); }else{ /* Note: this call could be optimized away - since the same values must ** have been requested when testing key $P in whereEqualScanEst(). */ whereKeyStats(pParse, p, pRec, 0, a); iLower = a[0]; iUpper = a[0] + a[1]; } |
︙ | ︙ | |||
2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 | static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; int nRecValid = pBuilder->nRecValid; int rc = SQLITE_OK; /* Subfunction return code */ tRowcnt nEst; /* Number of rows for a single term */ tRowcnt nRowEst = 0; /* New estimate of the number of rows */ int i; /* Loop counter */ assert( p->aSample!=0 ); for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ | > | | | 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 | static int whereInScanEst( Parse *pParse, /* Parsing & code generating context */ WhereLoopBuilder *pBuilder, ExprList *pList, /* The value list on the RHS of "x IN (v1,v2,v3,...)" */ tRowcnt *pnRow /* Write the revised row estimate here */ ){ Index *p = pBuilder->pNew->u.btree.pIndex; i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]); int nRecValid = pBuilder->nRecValid; int rc = SQLITE_OK; /* Subfunction return code */ tRowcnt nEst; /* Number of rows for a single term */ tRowcnt nRowEst = 0; /* New estimate of the number of rows */ int i; /* Loop counter */ assert( p->aSample!=0 ); for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){ nEst = nRow0; rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst); nRowEst += nEst; pBuilder->nRecValid = nRecValid; } if( rc==SQLITE_OK ){ if( nRowEst > nRow0 ) nRowEst = nRow0; *pnRow = nRowEst; WHERETRACE(0x10,("IN row estimate: est=%g\n", nRowEst)); } assert( pBuilder->nRecValid==nRecValid ); return rc; } #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */ |
︙ | ︙ | |||
4055 4056 4057 4058 4059 4060 4061 | 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); assert( pNew->u.btree.nEq<=pProbe->nKeyCol ); if( pNew->u.btree.nEq < pProbe->nKeyCol ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; | | < | > | | | 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 | 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); assert( pNew->u.btree.nEq<=pProbe->nKeyCol ); if( pNew->u.btree.nEq < pProbe->nKeyCol ){ iCol = pProbe->aiColumn[pNew->u.btree.nEq]; nRowEst = pProbe->aiRowLogEst[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_nSkip = pNew->u.btree.nSkip; saved_nLTerm = pNew->nLTerm; saved_wsFlags = pNew->wsFlags; saved_prereq = pNew->prereq; saved_nOut = pNew->nOut; pNew->rSetup = 0; rLogSize = estLog(pProbe->aiRowLogEst[0]); /* Consider using a skip-scan if there are no WHERE clause constraints ** available for the left-most terms of the index, and if the average ** number of repeats in the left-most terms is at least 18. The magic ** number 18 was found by experimentation to be the payoff point where ** skip-scan become faster than a full-scan. */ assert( 42==sqlite3LogEst(18) ); if( pTerm==0 && saved_nEq==saved_nSkip && saved_nEq+1<pProbe->nKeyCol && pProbe->aiRowLogEst[saved_nEq+1]>=42 /* TUNING: Minimum for skip-scan */ && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK ){ LogEst nIter; pNew->u.btree.nEq++; pNew->u.btree.nSkip++; pNew->aLTerm[pNew->nLTerm++] = 0; pNew->wsFlags |= WHERE_SKIPSCAN; nIter = pProbe->aiRowLogEst[0] - pProbe->aiRowLogEst[saved_nEq+1]; pNew->rRun = rLogSize + nIter; pNew->nOut += nIter; whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter); pNew->nOut = saved_nOut; } for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){ LogEst rCostIdx; |
︙ | ︙ | |||
4301 4302 4303 4304 4305 4306 4307 | static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ WhereInfo *pWInfo; /* WHERE analysis context */ Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ | | | 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315 4316 4317 | static int whereLoopAddBtree( WhereLoopBuilder *pBuilder, /* WHERE clause information */ Bitmask mExtra /* Extra prerequesites for using this table */ ){ WhereInfo *pWInfo; /* WHERE analysis context */ Index *pProbe; /* An index we are evaluating */ Index sPk; /* A fake index object for the primary key */ LogEst aiRowEstPk[2]; /* The aiRowLogEst[] value for the sPk index */ i16 aiColumnPk = -1; /* The aColumn[] value for the sPk index */ SrcList *pTabList; /* The FROM clause */ struct SrcList_item *pSrc; /* The FROM clause btree term to add */ WhereLoop *pNew; /* Template WhereLoop object */ int rc = SQLITE_OK; /* Return code */ int iSortIdx = 1; /* Index number */ int b; /* A boolean value */ |
︙ | ︙ | |||
4336 4337 4338 4339 4340 4341 4342 | ** variable sPk to represent the rowid primary key index. Make this ** fake index the first in a chain of Index objects with all of the real ** indices to follow */ Index *pFirst; /* First of real indices on the table */ memset(&sPk, 0, sizeof(Index)); sPk.nKeyCol = 1; sPk.aiColumn = &aiColumnPk; | | | | | | 4338 4339 4340 4341 4342 4343 4344 4345 4346 4347 4348 4349 4350 4351 4352 4353 4354 4355 4356 4357 4358 4359 4360 4361 4362 4363 4364 4365 4366 | ** variable sPk to represent the rowid primary key index. Make this ** fake index the first in a chain of Index objects with all of the real ** indices to follow */ Index *pFirst; /* First of real indices on the table */ memset(&sPk, 0, sizeof(Index)); sPk.nKeyCol = 1; sPk.aiColumn = &aiColumnPk; sPk.aiRowLogEst = aiRowEstPk; sPk.onError = OE_Replace; sPk.pTable = pTab; sPk.szIdxRow = pTab->szTabRow; aiRowEstPk[0] = pTab->nRowLogEst; aiRowEstPk[1] = 0; pFirst = pSrc->pTab->pIndex; 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 = pTab->nRowLogEst; rLogSize = estLog(rSize); #ifndef SQLITE_OMIT_AUTOMATIC_INDEX /* Automatic indexes */ if( !pBuilder->pOrSet && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0 && pSrc->pIndex==0 |
︙ | ︙ |