/ Check-in [1bd74c49]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | experimental-costs
Files: files | file ages | folders
SHA1: 1bd74c49ddab6f53bb6eaa57907eff44c2580dd6
User & Date: dan 2014-04-25 15:01:01
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: c51efaa5 user: dan tags: experimental-costs
15:01
Store values loaded from the stat1 table as logarithmic values in memory. check-in: 1bd74c49 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: c5a6ec0a user: dan tags: experimental-costs
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/analyze.c.

  1367   1367   ** list of space separated integers. Read the first nOut of these into
  1368   1368   ** the array aOut[].
  1369   1369   */
  1370   1370   static void decodeIntArray(
  1371   1371     char *zIntArray,       /* String containing int array to decode */
  1372   1372     int nOut,              /* Number of slots in aOut[] */
  1373   1373     tRowcnt *aOut,         /* Store integers here */
         1374  +  LogEst *aLog,          /* Or, if aOut==0, here */
  1374   1375     Index *pIndex          /* Handle extra flags for this index, if not NULL */
  1375   1376   ){
  1376   1377     char *z = zIntArray;
  1377   1378     int c;
  1378   1379     int i;
  1379   1380     tRowcnt v;
  1380   1381   
................................................................................
  1385   1386   #endif
  1386   1387     for(i=0; *z && i<nOut; i++){
  1387   1388       v = 0;
  1388   1389       while( (c=z[0])>='0' && c<='9' ){
  1389   1390         v = v*10 + c - '0';
  1390   1391         z++;
  1391   1392       }
  1392         -    aOut[i] = v;
         1393  +    if( aOut ){
         1394  +      aOut[i] = v;
         1395  +    }else{
         1396  +      aLog[i] = sqlite3LogEst(v);
         1397  +    }
  1393   1398       if( *z==' ' ) z++;
  1394   1399     }
  1395   1400   #ifndef SQLITE_ENABLE_STAT3_OR_STAT4
  1396   1401     assert( pIndex!=0 );
  1397   1402   #else
  1398   1403     if( pIndex )
  1399   1404   #endif
................................................................................
  1441   1446       pIndex = sqlite3PrimaryKeyIndex(pTable);
  1442   1447     }else{
  1443   1448       pIndex = sqlite3FindIndex(pInfo->db, argv[1], pInfo->zDatabase);
  1444   1449     }
  1445   1450     z = argv[2];
  1446   1451   
  1447   1452     if( pIndex ){
  1448         -    decodeIntArray((char*)z, pIndex->nKeyCol+1, pIndex->aiRowEst, pIndex);
  1449         -    if( pIndex->pPartIdxWhere==0 ) pTable->nRowEst = pIndex->aiRowEst[0];
         1453  +    decodeIntArray((char*)z, pIndex->nKeyCol+1, 0, pIndex->aiRowLogEst, pIndex);
         1454  +    if( pIndex->pPartIdxWhere==0 ) pTable->nRowLogEst = pIndex->aiRowLogEst[0];
  1450   1455     }else{
  1451   1456       Index fakeIdx;
  1452   1457       fakeIdx.szIdxRow = pTable->szTabRow;
  1453         -    decodeIntArray((char*)z, 1, &pTable->nRowEst, &fakeIdx);
         1458  +    decodeIntArray((char*)z, 1, 0, &pTable->nRowLogEst, &fakeIdx);
  1454   1459       pTable->szTabRow = fakeIdx.szIdxRow;
  1455   1460     }
  1456   1461   
  1457   1462     return 0;
  1458   1463   }
  1459   1464   
  1460   1465   /*
................................................................................
  1638   1643       nCol = pIdx->nSampleCol;
  1639   1644       if( bStat3 && nCol>1 ) continue;
  1640   1645       if( pIdx!=pPrevIdx ){
  1641   1646         initAvgEq(pPrevIdx);
  1642   1647         pPrevIdx = pIdx;
  1643   1648       }
  1644   1649       pSample = &pIdx->aSample[pIdx->nSample];
  1645         -    decodeIntArray((char*)sqlite3_column_text(pStmt,1), nCol, pSample->anEq, 0);
  1646         -    decodeIntArray((char*)sqlite3_column_text(pStmt,2), nCol, pSample->anLt, 0);
  1647         -    decodeIntArray((char*)sqlite3_column_text(pStmt,3), nCol, pSample->anDLt,0);
         1650  +    decodeIntArray((char*)sqlite3_column_text(pStmt,1),nCol,pSample->anEq,0,0);
         1651  +    decodeIntArray((char*)sqlite3_column_text(pStmt,2),nCol,pSample->anLt,0,0);
         1652  +    decodeIntArray((char*)sqlite3_column_text(pStmt,3),nCol,pSample->anDLt,0,0);
  1648   1653   
  1649   1654       /* Take a copy of the sample. Add two 0x00 bytes the end of the buffer.
  1650   1655       ** This is in case the sample record is corrupted. In that case, the
  1651   1656       ** sqlite3VdbeRecordCompare() may read up to two varints past the
  1652   1657       ** end of the allocated buffer before it realizes it is dealing with
  1653   1658       ** a corrupt record. Adding the two 0x00 bytes prevents this from causing
  1654   1659       ** a buffer overread.  */

Changes to src/build.c.

   901    901       pParse->nErr++;
   902    902       goto begin_table_error;
   903    903     }
   904    904     pTable->zName = zName;
   905    905     pTable->iPKey = -1;
   906    906     pTable->pSchema = db->aDb[iDb].pSchema;
   907    907     pTable->nRef = 1;
   908         -  pTable->nRowEst = 1048576;
          908  +  pTable->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
   909    909     assert( pParse->pNewTable==0 );
   910    910     pParse->pNewTable = pTable;
   911    911   
   912    912     /* If this is the magic sqlite_sequence table used by autoincrement,
   913    913     ** then record a pointer to this table in the main database structure
   914    914     ** so that INSERT can find the table easily.
   915    915     */
................................................................................
  2726   2726     char **ppExtra       /* Pointer to the "extra" space */
  2727   2727   ){
  2728   2728     Index *p;            /* Allocated index object */
  2729   2729     int nByte;           /* Bytes of space for Index object + arrays */
  2730   2730   
  2731   2731     nByte = ROUND8(sizeof(Index)) +              /* Index structure  */
  2732   2732             ROUND8(sizeof(char*)*nCol) +         /* Index.azColl     */
  2733         -          ROUND8(sizeof(tRowcnt)*(nCol+1) +    /* Index.aiRowEst   */
         2733  +          ROUND8(sizeof(LogEst)*(nCol+1) +     /* Index.aiRowLogEst   */
  2734   2734                    sizeof(i16)*nCol +            /* Index.aiColumn   */
  2735   2735                    sizeof(u8)*nCol);             /* Index.aSortOrder */
  2736   2736     p = sqlite3DbMallocZero(db, nByte + nExtra);
  2737   2737     if( p ){
  2738   2738       char *pExtra = ((char*)p)+ROUND8(sizeof(Index));
  2739         -    p->azColl = (char**)pExtra;      pExtra += ROUND8(sizeof(char*)*nCol);
  2740         -    p->aiRowEst = (tRowcnt*)pExtra;  pExtra += sizeof(tRowcnt)*(nCol+1);
  2741         -    p->aiColumn = (i16*)pExtra;      pExtra += sizeof(i16)*nCol;
         2739  +    p->azColl = (char**)pExtra;       pExtra += ROUND8(sizeof(char*)*nCol);
         2740  +    p->aiRowLogEst = (LogEst*)pExtra; pExtra += sizeof(LogEst)*(nCol+1);
         2741  +    p->aiColumn = (i16*)pExtra;       pExtra += sizeof(i16)*nCol;
  2742   2742       p->aSortOrder = (u8*)pExtra;
  2743   2743       p->nColumn = nCol;
  2744   2744       p->nKeyCol = nCol - 1;
  2745   2745       *ppExtra = ((char*)p) + nByte;
  2746   2746     }
  2747   2747     return p;
  2748   2748   }
................................................................................
  2964   2964     nName = sqlite3Strlen30(zName);
  2965   2965     nExtraCol = pPk ? pPk->nKeyCol : 1;
  2966   2966     pIndex = sqlite3AllocateIndexObject(db, pList->nExpr + nExtraCol,
  2967   2967                                         nName + nExtra + 1, &zExtra);
  2968   2968     if( db->mallocFailed ){
  2969   2969       goto exit_create_index;
  2970   2970     }
  2971         -  assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowEst) );
         2971  +  assert( EIGHT_BYTE_ALIGNMENT(pIndex->aiRowLogEst) );
  2972   2972     assert( EIGHT_BYTE_ALIGNMENT(pIndex->azColl) );
  2973   2973     pIndex->zName = zExtra;
  2974   2974     zExtra += nName + 1;
  2975   2975     memcpy(pIndex->zName, zName, nName+1);
  2976   2976     pIndex->pTable = pTab;
  2977   2977     pIndex->onError = (u8)onError;
  2978   2978     pIndex->uniqNotNull = onError!=OE_None;
................................................................................
  3245   3245   ** Fill the Index.aiRowEst[] array with default information - information
  3246   3246   ** to be used when we have not run the ANALYZE command.
  3247   3247   **
  3248   3248   ** aiRowEst[0] is suppose to contain the number of elements in the index.
  3249   3249   ** Since we do not know, guess 1 million.  aiRowEst[1] is an estimate of the
  3250   3250   ** number of rows in the table that match any particular value of the
  3251   3251   ** first column of the index.  aiRowEst[2] is an estimate of the number
  3252         -** of rows that match any particular combiniation of the first 2 columns
         3252  +** of rows that match any particular combination of the first 2 columns
  3253   3253   ** of the index.  And so forth.  It must always be the case that
  3254   3254   *
  3255   3255   **           aiRowEst[N]<=aiRowEst[N-1]
  3256   3256   **           aiRowEst[N]>=1
  3257   3257   **
  3258   3258   ** Apart from that, we have little to go on besides intuition as to
  3259   3259   ** how aiRowEst[] should be initialized.  The numbers generated here
  3260   3260   ** are based on typical values found in actual indices.
  3261   3261   */
  3262   3262   void sqlite3DefaultRowEst(Index *pIdx){
         3263  +#if 0
  3263   3264     tRowcnt *a = pIdx->aiRowEst;
  3264   3265     int i;
  3265   3266     tRowcnt n;
  3266   3267     assert( a!=0 );
  3267   3268     a[0] = pIdx->pTable->nRowEst;
  3268   3269     if( a[0]<10 ) a[0] = 10;
  3269   3270     n = 10;
................................................................................
  3270   3271     for(i=1; i<=pIdx->nKeyCol; i++){
  3271   3272       a[i] = n;
  3272   3273       if( n>5 ) n--;
  3273   3274     }
  3274   3275     if( pIdx->onError!=OE_None ){
  3275   3276       a[pIdx->nKeyCol] = 1;
  3276   3277     }
         3278  +#endif
         3279  +  /*            1000000, 10,  9,  8,  7,  6,  5,  4,  3,  2 */
         3280  +  LogEst aVal[] = { 33, 32, 30, 28, 26, 23, 20, 16, 10 };
         3281  +  LogEst *a = pIdx->aiRowLogEst;
         3282  +  int nCopy = MIN(ArraySize(aVal), pIdx->nKeyCol);
         3283  +
         3284  +  a[0] = pIdx->pTable->nRowLogEst;
         3285  +  memcpy(&a[1], aVal, nCopy*sizeof(LogEst));
         3286  +  if( pIdx->onError!=OE_None ){
         3287  +    a[pIdx->nKeyCol] = 0;
         3288  +  }
  3277   3289   }
  3278   3290   
  3279   3291   /*
  3280   3292   ** This routine will drop an existing named index.  This routine
  3281   3293   ** implements the DROP INDEX statement.
  3282   3294   */
  3283   3295   void sqlite3DropIndex(Parse *pParse, SrcList *pName, int ifExists){

Changes to src/pragma.c.

  1484   1484       sqlite3VdbeSetColName(v, 3, COLNAME_NAME, "height", SQLITE_STATIC);
  1485   1485       for(i=sqliteHashFirst(&pDb->pSchema->tblHash); i; i=sqliteHashNext(i)){
  1486   1486         Table *pTab = sqliteHashData(i);
  1487   1487         sqlite3VdbeAddOp4(v, OP_String8, 0, 1, 0, pTab->zName, 0);
  1488   1488         sqlite3VdbeAddOp2(v, OP_Null, 0, 2);
  1489   1489         sqlite3VdbeAddOp2(v, OP_Integer,
  1490   1490                              (int)sqlite3LogEstToInt(pTab->szTabRow), 3);
  1491         -      sqlite3VdbeAddOp2(v, OP_Integer, (int)pTab->nRowEst, 4);
         1491  +      sqlite3VdbeAddOp2(v, OP_Integer, 
         1492  +          (int)sqlite3LogEstToInt(pTab->nRowLogEst), 4);
  1492   1493         sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
  1493   1494         for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
  1494   1495           sqlite3VdbeAddOp4(v, OP_String8, 0, 2, 0, pIdx->zName, 0);
  1495   1496           sqlite3VdbeAddOp2(v, OP_Integer,
  1496   1497                                (int)sqlite3LogEstToInt(pIdx->szIdxRow), 3);
  1497         -        sqlite3VdbeAddOp2(v, OP_Integer, (int)pIdx->aiRowEst[0], 4);
         1498  +        sqlite3VdbeAddOp2(v, OP_Integer, 
         1499  +            (int)sqlite3LogEstToInt(pIdx->aiRowLogEst[0]), 4);
  1498   1500           sqlite3VdbeAddOp2(v, OP_ResultRow, 1, 4);
  1499   1501         }
  1500   1502       }
  1501   1503     }
  1502   1504     break;
  1503   1505   
  1504   1506     case PragTyp_INDEX_INFO: if( zRight ){

Changes to src/select.c.

  1686   1686       return 0;
  1687   1687     }
  1688   1688     /* The sqlite3ResultSetOfSelect() is only used n contexts where lookaside
  1689   1689     ** is disabled */
  1690   1690     assert( db->lookaside.bEnabled==0 );
  1691   1691     pTab->nRef = 1;
  1692   1692     pTab->zName = 0;
  1693         -  pTab->nRowEst = 1048576;
         1693  +  pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
  1694   1694     selectColumnsFromExprList(pParse, pSelect->pEList, &pTab->nCol, &pTab->aCol);
  1695   1695     selectAddColumnTypeAndCollation(pParse, pTab, pSelect);
  1696   1696     pTab->iPKey = -1;
  1697   1697     if( db->mallocFailed ){
  1698   1698       sqlite3DeleteTable(db, pTab);
  1699   1699       return 0;
  1700   1700     }
................................................................................
  3825   3825   
  3826   3826       assert( pFrom->pTab==0 );
  3827   3827       pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
  3828   3828       if( pTab==0 ) return WRC_Abort;
  3829   3829       pTab->nRef = 1;
  3830   3830       pTab->zName = sqlite3DbStrDup(db, pCte->zName);
  3831   3831       pTab->iPKey = -1;
  3832         -    pTab->nRowEst = 1048576;
         3832  +    pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
  3833   3833       pTab->tabFlags |= TF_Ephemeral;
  3834   3834       pFrom->pSelect = sqlite3SelectDup(db, pCte->pSelect, 0);
  3835   3835       if( db->mallocFailed ) return SQLITE_NOMEM;
  3836   3836       assert( pFrom->pSelect );
  3837   3837   
  3838   3838       /* Check if this is a recursive CTE. */
  3839   3839       pSel = pFrom->pSelect;
................................................................................
  4001   4001         pFrom->pTab = pTab = sqlite3DbMallocZero(db, sizeof(Table));
  4002   4002         if( pTab==0 ) return WRC_Abort;
  4003   4003         pTab->nRef = 1;
  4004   4004         pTab->zName = sqlite3MPrintf(db, "sqlite_sq_%p", (void*)pTab);
  4005   4005         while( pSel->pPrior ){ pSel = pSel->pPrior; }
  4006   4006         selectColumnsFromExprList(pParse, pSel->pEList, &pTab->nCol, &pTab->aCol);
  4007   4007         pTab->iPKey = -1;
  4008         -      pTab->nRowEst = 1048576;
         4008  +      pTab->nRowLogEst = 200; assert( 200==sqlite3LogEst(1048576) );
  4009   4009         pTab->tabFlags |= TF_Ephemeral;
  4010   4010   #endif
  4011   4011       }else{
  4012   4012         /* An ordinary table or view name in the FROM clause */
  4013   4013         assert( pFrom->pTab==0 );
  4014   4014         pFrom->pTab = pTab = sqlite3LocateTableItem(pParse, 0, pFrom);
  4015   4015         if( pTab==0 ) return WRC_Abort;
................................................................................
  4651   4651         pItem->regReturn = ++pParse->nMem;
  4652   4652         sqlite3VdbeAddOp3(v, OP_InitCoroutine, pItem->regReturn, 0, addrTop);
  4653   4653         VdbeComment((v, "%s", pItem->pTab->zName));
  4654   4654         pItem->addrFillSub = addrTop;
  4655   4655         sqlite3SelectDestInit(&dest, SRT_Coroutine, pItem->regReturn);
  4656   4656         explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
  4657   4657         sqlite3Select(pParse, pSub, &dest);
  4658         -      pItem->pTab->nRowEst = (unsigned)pSub->nSelectRow;
         4658  +      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
  4659   4659         pItem->viaCoroutine = 1;
  4660   4660         pItem->regResult = dest.iSdst;
  4661   4661         sqlite3VdbeAddOp1(v, OP_EndCoroutine, pItem->regReturn);
  4662   4662         sqlite3VdbeJumpHere(v, addrTop-1);
  4663   4663         sqlite3ClearTempRegCache(pParse);
  4664   4664       }else{
  4665   4665         /* Generate a subroutine that will fill an ephemeral table with
................................................................................
  4682   4682           VdbeComment((v, "materialize \"%s\"", pItem->pTab->zName));
  4683   4683         }else{
  4684   4684           VdbeNoopComment((v, "materialize \"%s\"", pItem->pTab->zName));
  4685   4685         }
  4686   4686         sqlite3SelectDestInit(&dest, SRT_EphemTab, pItem->iCursor);
  4687   4687         explainSetInteger(pItem->iSelectId, (u8)pParse->iNextSelectId);
  4688   4688         sqlite3Select(pParse, pSub, &dest);
  4689         -      pItem->pTab->nRowEst = (unsigned)pSub->nSelectRow;
         4689  +      pItem->pTab->nRowLogEst = sqlite3LogEst(pSub->nSelectRow);
  4690   4690         if( onceAddr ) sqlite3VdbeJumpHere(v, onceAddr);
  4691   4691         retAddr = sqlite3VdbeAddOp1(v, OP_Return, pItem->regReturn);
  4692   4692         VdbeComment((v, "end %s", pItem->pTab->zName));
  4693   4693         sqlite3VdbeChangeP1(v, topAddr, retAddr);
  4694   4694         sqlite3ClearTempRegCache(pParse);
  4695   4695       }
  4696   4696       if( /*pParse->nErr ||*/ db->mallocFailed ){

Changes to src/sqliteInt.h.

  1467   1467     Index *pIndex;       /* List of SQL indexes on this table. */
  1468   1468     Select *pSelect;     /* NULL for tables.  Points to definition if a view. */
  1469   1469     FKey *pFKey;         /* Linked list of all foreign keys in this table */
  1470   1470     char *zColAff;       /* String defining the affinity of each column */
  1471   1471   #ifndef SQLITE_OMIT_CHECK
  1472   1472     ExprList *pCheck;    /* All CHECK constraints */
  1473   1473   #endif
  1474         -  tRowcnt nRowEst;     /* Estimated rows in table - from sqlite_stat1 table */
         1474  +  LogEst nRowLogEst;   /* Estimated rows in table - from sqlite_stat1 table */
  1475   1475     int tnum;            /* Root BTree node for this table (see note above) */
  1476   1476     i16 iPKey;           /* If not negative, use aCol[iPKey] as the primary key */
  1477   1477     i16 nCol;            /* Number of columns in this table */
  1478   1478     u16 nRef;            /* Number of pointers to this Table */
  1479   1479     LogEst szTabRow;     /* Estimated size of each table row in bytes */
  1480   1480     u8 tabFlags;         /* Mask of TF_* values */
  1481   1481     u8 keyConf;          /* What to do in case of uniqueness conflict on iPKey */
................................................................................
  1676   1676   ** and the value of Index.onError indicate the which conflict resolution 
  1677   1677   ** algorithm to employ whenever an attempt is made to insert a non-unique
  1678   1678   ** element.
  1679   1679   */
  1680   1680   struct Index {
  1681   1681     char *zName;             /* Name of this index */
  1682   1682     i16 *aiColumn;           /* Which columns are used by this index.  1st is 0 */
         1683  +#if 0
  1683   1684     tRowcnt *aiRowEst;       /* From ANALYZE: Est. rows selected by each column */
         1685  +#endif
         1686  +  LogEst *aiRowLogEst;     /* From ANALYZE: Est. rows selected by each column */
  1684   1687     Table *pTable;           /* The SQL table being indexed */
  1685   1688     char *zColAff;           /* String defining the affinity of each column */
  1686   1689     Index *pNext;            /* The next index associated with the same table */
  1687   1690     Schema *pSchema;         /* Schema containing this index */
  1688   1691     u8 *aSortOrder;          /* for each column: True==DESC, False==ASC */
  1689   1692     char **azColl;           /* Array of collation sequence names for index */
  1690   1693     Expr *pPartIdxWhere;     /* WHERE clause for partial indices */

Changes to src/where.c.

  1952   1952       aStat[1] = aSample[i].anEq[iCol];
  1953   1953     }else{
  1954   1954       tRowcnt iLower, iUpper, iGap;
  1955   1955       if( i==0 ){
  1956   1956         iLower = 0;
  1957   1957         iUpper = aSample[0].anLt[iCol];
  1958   1958       }else{
  1959         -      iUpper = i>=pIdx->nSample ? pIdx->aiRowEst[0] : aSample[i].anLt[iCol];
         1959  +      i64 nRow0 = sqlite3LogEstToInt(pIdx->aiRowLogEst[0]);
         1960  +      iUpper = i>=pIdx->nSample ? nRow0 : aSample[i].anLt[iCol];
  1960   1961         iLower = aSample[i-1].anEq[iCol] + aSample[i-1].anLt[iCol];
  1961   1962       }
  1962   1963       aStat[1] = (pIdx->nKeyCol>iCol ? pIdx->aAvgEq[iCol] : 1);
  1963   1964       if( iLower>=iUpper ){
  1964   1965         iGap = 0;
  1965   1966       }else{
  1966   1967         iGap = iUpper - iLower;
................................................................................
  2088   2089         aff = SQLITE_AFF_INTEGER;
  2089   2090       }else{
  2090   2091         aff = p->pTable->aCol[p->aiColumn[nEq]].affinity;
  2091   2092       }
  2092   2093       /* Determine iLower and iUpper using ($P) only. */
  2093   2094       if( nEq==0 ){
  2094   2095         iLower = 0;
  2095         -      iUpper = p->aiRowEst[0];
         2096  +      iUpper = sqlite3LogEstToInt(p->aiRowLogEst[0]);
  2096   2097       }else{
  2097   2098         /* Note: this call could be optimized away - since the same values must 
  2098   2099         ** have been requested when testing key $P in whereEqualScanEst().  */
  2099   2100         whereKeyStats(pParse, p, pRec, 0, a);
  2100   2101         iLower = a[0];
  2101   2102         iUpper = a[0] + a[1];
  2102   2103       }
................................................................................
  2247   2248   static int whereInScanEst(
  2248   2249     Parse *pParse,       /* Parsing & code generating context */
  2249   2250     WhereLoopBuilder *pBuilder,
  2250   2251     ExprList *pList,     /* The value list on the RHS of "x IN (v1,v2,v3,...)" */
  2251   2252     tRowcnt *pnRow       /* Write the revised row estimate here */
  2252   2253   ){
  2253   2254     Index *p = pBuilder->pNew->u.btree.pIndex;
         2255  +  i64 nRow0 = sqlite3LogEstToInt(p->aiRowLogEst[0]);
  2254   2256     int nRecValid = pBuilder->nRecValid;
  2255   2257     int rc = SQLITE_OK;     /* Subfunction return code */
  2256   2258     tRowcnt nEst;           /* Number of rows for a single term */
  2257   2259     tRowcnt nRowEst = 0;    /* New estimate of the number of rows */
  2258   2260     int i;                  /* Loop counter */
  2259   2261   
  2260   2262     assert( p->aSample!=0 );
  2261   2263     for(i=0; rc==SQLITE_OK && i<pList->nExpr; i++){
  2262         -    nEst = p->aiRowEst[0];
         2264  +    nEst = nRow0;
  2263   2265       rc = whereEqualScanEst(pParse, pBuilder, pList->a[i].pExpr, &nEst);
  2264   2266       nRowEst += nEst;
  2265   2267       pBuilder->nRecValid = nRecValid;
  2266   2268     }
  2267   2269   
  2268   2270     if( rc==SQLITE_OK ){
  2269         -    if( nRowEst > p->aiRowEst[0] ) nRowEst = p->aiRowEst[0];
         2271  +    if( nRowEst > nRow0 ) nRowEst = nRow0;
  2270   2272       *pnRow = nRowEst;
  2271   2273       WHERETRACE(0x10,("IN row estimate: est=%g\n", nRowEst));
  2272   2274     }
  2273   2275     assert( pBuilder->nRecValid==nRecValid );
  2274   2276     return rc;
  2275   2277   }
  2276   2278   #endif /* SQLITE_ENABLE_STAT3_OR_STAT4 */
................................................................................
  4055   4057       opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE;
  4056   4058     }
  4057   4059     if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE);
  4058   4060   
  4059   4061     assert( pNew->u.btree.nEq<=pProbe->nKeyCol );
  4060   4062     if( pNew->u.btree.nEq < pProbe->nKeyCol ){
  4061   4063       iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  4062         -    nRowEst = sqlite3LogEst(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
  4063         -    if( nRowEst==0 && pProbe->onError==OE_None ) nRowEst = 1;
         4064  +    nRowEst = pProbe->aiRowLogEst[pNew->u.btree.nEq+1];
  4064   4065     }else{
  4065   4066       iCol = -1;
  4066   4067       nRowEst = 0;
  4067   4068     }
  4068   4069     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  4069   4070                           opMask, pProbe);
  4070   4071     saved_nEq = pNew->u.btree.nEq;
  4071   4072     saved_nSkip = pNew->u.btree.nSkip;
  4072   4073     saved_nLTerm = pNew->nLTerm;
  4073   4074     saved_wsFlags = pNew->wsFlags;
  4074   4075     saved_prereq = pNew->prereq;
  4075   4076     saved_nOut = pNew->nOut;
  4076   4077     pNew->rSetup = 0;
  4077         -  rLogSize = estLog(sqlite3LogEst(pProbe->aiRowEst[0]));
         4078  +  rLogSize = estLog(pProbe->aiRowLogEst[0]);
  4078   4079   
  4079   4080     /* Consider using a skip-scan if there are no WHERE clause constraints
  4080   4081     ** available for the left-most terms of the index, and if the average
  4081   4082     ** number of repeats in the left-most terms is at least 18.  The magic
  4082   4083     ** number 18 was found by experimentation to be the payoff point where
  4083   4084     ** skip-scan become faster than a full-scan.
  4084   4085     */
         4086  +  assert( 42==sqlite3LogEst(18) );
  4085   4087     if( pTerm==0
  4086   4088      && saved_nEq==saved_nSkip
  4087   4089      && saved_nEq+1<pProbe->nKeyCol
  4088         -   && pProbe->aiRowEst[saved_nEq+1]>=18  /* TUNING: Minimum for skip-scan */
         4090  +   && pProbe->aiRowLogEst[saved_nEq+1]>=42  /* TUNING: Minimum for skip-scan */
  4089   4091      && (rc = whereLoopResize(db, pNew, pNew->nLTerm+1))==SQLITE_OK
  4090   4092     ){
  4091   4093       LogEst nIter;
  4092   4094       pNew->u.btree.nEq++;
  4093   4095       pNew->u.btree.nSkip++;
  4094   4096       pNew->aLTerm[pNew->nLTerm++] = 0;
  4095   4097       pNew->wsFlags |= WHERE_SKIPSCAN;
  4096         -    nIter = sqlite3LogEst(pProbe->aiRowEst[0]/pProbe->aiRowEst[saved_nEq+1]);
         4098  +    nIter = pProbe->aiRowLogEst[0] - pProbe->aiRowLogEst[saved_nEq+1];
  4097   4099       pNew->rRun = rLogSize + nIter;
  4098   4100       pNew->nOut += nIter;
  4099   4101       whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, nIter);
  4100   4102       pNew->nOut = saved_nOut;
  4101   4103     }
  4102   4104     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  4103   4105       LogEst rCostIdx;
................................................................................
  4301   4303   static int whereLoopAddBtree(
  4302   4304     WhereLoopBuilder *pBuilder, /* WHERE clause information */
  4303   4305     Bitmask mExtra              /* Extra prerequesites for using this table */
  4304   4306   ){
  4305   4307     WhereInfo *pWInfo;          /* WHERE analysis context */
  4306   4308     Index *pProbe;              /* An index we are evaluating */
  4307   4309     Index sPk;                  /* A fake index object for the primary key */
  4308         -  tRowcnt aiRowEstPk[2];      /* The aiRowEst[] value for the sPk index */
         4310  +  LogEst aiRowEstPk[2];       /* The aiRowLogEst[] value for the sPk index */
  4309   4311     i16 aiColumnPk = -1;        /* The aColumn[] value for the sPk index */
  4310   4312     SrcList *pTabList;          /* The FROM clause */
  4311   4313     struct SrcList_item *pSrc;  /* The FROM clause btree term to add */
  4312   4314     WhereLoop *pNew;            /* Template WhereLoop object */
  4313   4315     int rc = SQLITE_OK;         /* Return code */
  4314   4316     int iSortIdx = 1;           /* Index number */
  4315   4317     int b;                      /* A boolean value */
................................................................................
  4336   4338       ** variable sPk to represent the rowid primary key index.  Make this
  4337   4339       ** fake index the first in a chain of Index objects with all of the real
  4338   4340       ** indices to follow */
  4339   4341       Index *pFirst;                  /* First of real indices on the table */
  4340   4342       memset(&sPk, 0, sizeof(Index));
  4341   4343       sPk.nKeyCol = 1;
  4342   4344       sPk.aiColumn = &aiColumnPk;
  4343         -    sPk.aiRowEst = aiRowEstPk;
         4345  +    sPk.aiRowLogEst = aiRowEstPk;
  4344   4346       sPk.onError = OE_Replace;
  4345   4347       sPk.pTable = pTab;
  4346   4348       sPk.szIdxRow = pTab->szTabRow;
  4347         -    aiRowEstPk[0] = pTab->nRowEst;
  4348         -    aiRowEstPk[1] = 1;
         4349  +    aiRowEstPk[0] = pTab->nRowLogEst;
         4350  +    aiRowEstPk[1] = 0;
  4349   4351       pFirst = pSrc->pTab->pIndex;
  4350   4352       if( pSrc->notIndexed==0 ){
  4351   4353         /* The real indices of the table are only considered if the
  4352   4354         ** NOT INDEXED qualifier is omitted from the FROM clause */
  4353   4355         sPk.pNext = pFirst;
  4354   4356       }
  4355   4357       pProbe = &sPk;
  4356   4358     }
  4357         -  rSize = sqlite3LogEst(pTab->nRowEst);
         4359  +  rSize = pTab->nRowLogEst;
  4358   4360     rLogSize = estLog(rSize);
  4359   4361   
  4360   4362   #ifndef SQLITE_OMIT_AUTOMATIC_INDEX
  4361   4363     /* Automatic indexes */
  4362   4364     if( !pBuilder->pOrSet
  4363   4365      && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
  4364   4366      && pSrc->pIndex==0